CODEWITHSUNDEEP
prologtransitive-closure
Paladini
Paladini

Reputation: 4572

Do I need "base step" to make a recursion on Prolog?

I'm learning Prolog at my university and I'm stuck with a question. Note that I'm a newbie in Prolog and I don't even know the correct spelling of Prolog elements.

I need to define a recursive rule in my .pl file and I don't know if I need a "base step" on my rule. Check my rule:

recur_disciplinas(X, Y) :- requisito(X, Y).
recur_disciplinas(X, Y) :- requisito(X, Z), recur_disciplinas(Z, Y).

This is working, but couldn't I do something like the following? 

recur_disciplinas(X, Y) :- requisito(X, Z), recur_disciplinas(Z, Y).

What happens when I declare the same "rule name" (recur_disciplinas(X,Y) :-) two times? Occurs somewhat like an overwrite?

I'm currently using swi-prolog. Thank you so much, guys!

Upvotes: 3

Views: 243

Answers (3)

hardmath
hardmath

Reputation: 8823

Here we say recur_disciplinas/2 is a predicate with two arguments, and you have asked about whether two clauses (rules) for the predicate are necessary.

As the other Answers have said, one needs a "base case" in recursion so that the recursion terminates, as is usually desirable! The most common arrangement is like your first example: the first rule is the terminating condition (base case) and the second rule is the recursive step (induction case). Someone reading your code will likely find this arrangement familiar and easy to understand.

However the base case and the recursion step MAY be combined into a single rule, and this is sometimes useful. For example, we could use the OR syntax:

recur_disciplinas(X, Y) :-
    requisito(X, Y) ; ( requisito(X, Z), recur_disciplinas(Z, Y) ).

Here ; means OR, and this single rule produces essentially the same search for solutions as your original two-rule version.

It is also possible that there can be multiple base cases, each with their own rules or written into a more complicated "combination" rule. As with any programming discipline, clarity and correctness should be prized over mere brevity in code.

In some unusual circumstances it can be advantageous to position the recursive step as the first rule, and move the base case (or cases) into following rules. This would require extra care to ensure the termination condition will always be reached, since it is unlikely you want code that can loop endlessly. The Prolog engine always starts with the first rule when a predicate is invoked; the following rules are tried only once the first rule fails.

Upvotes: 1

false
false

Reputation: 10102

The best way how to understand Prolog rules is to look at the :- operator which is a 1970ies rendering of an arrow (yes, the assignment operator := in Pascal was meant as an arrow, too). So you look what is there on the right-hand side and say: Provided all that is true, I can conclude what is on the left-hand side. So you are reading right-to-left with your rule:

 recur_disciplinas(X, Y) :- requisito(X, Z), recur_disciplinas(Z, Y).
 %                          ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ read

You say: provided there is some X, Y and Z such that the right-hand is true, we can conclude that recur_disciplians(X, Y) holds. Now, lets generalize this by removing requisito(X, Z). What is left now is:

 recur_disciplinas(X, Y) :- /******/ recur_disciplinas(Z, Y).

So you can conclude from recur_disciplinas(Z, Y) that recur_disciplinas(X, Y) holds. But you have nothing to start with that conclusion! So effectively this means that there is no solution to this relation at all.

Its like saying, provided I can fly, I will fly like a bird.

Maybe that is true, but as long as you do not fly, it is all in vain.

See this answer how to permit to express your relation more compactly. A goal closure(requisito, X, Y) suffices! And it would even deal with potential loops.

As a side remark, I suspect that recur is some verb, even an imperative. Right? Try to avoid imperatives for relations. Imperatives are good for changing things. Like "switch on the light" which changes the world from a world with a light switched off to one where it is switched on. Imperatives are good for telling a mindless entity what to do. If you rather want to reason about things, imperatives are just malaprop. Focus instead on what should be the case and what not.

Upvotes: 4

Little Bobby Tables
Little Bobby Tables

Reputation: 5351

If you have a rule name more than one time, it creates an or-branch in your control flow. Prolog will try to unify the first clause. If it will fail, it will try the second clause, and the third, etc.

In the code above, the recur_disciplinas rule will first try to find a matching requisito. If it will fail, it will try to find a requisito-of-a-requisito, transitively, and recursively.

If you don't put a base clause, Prolog will always try the recursive clause, thus it may enter an infinite loop.

Writing base conditions is not unique to Prolog. It is the same with every language that allows recursion. If there is no halting condition, your function will enter an infinite loop.

Consider this equivalent procedural pseudo-code:

def find_disciplinas(X, Y):
  if find_requisito(X,Y): # halting condition
    return (X, Y)
  else: # recursive call
    for all Z such that find_requisito(X, Z):
      return find_disciplinas(X, Z)

if your "requisito" records include a cycle, and you remove the halting condition, the above procedure will loop indefinitely.

Upvotes: 1

Related Questions