Can't understand why is prolog looping infinitly

3
votes

From Bratko's book, Prolog Programming for Artificial Intelligence (4th Edition) We have the following code which doesn't work - 

anc4(X,Z):-
    anc4(X,Y),
    parent(Y,Z).
anc4(X,Z):-
    parent(X,Z).

In the book, on page 55, figure 2.15, is shown that parent(Y,Z) is kept calling until stack is out of memory.

What I don't understand is that prolog does a recursiv call to anc4(X,Y), and not to parent (Y,Z) first. Why doesn't prolog goes over and over to the first line, anc4(X,Y), and rather goes to the second line?

Can you please elaborate why is the line parent(Y,Z) is kept being called?

Thank you.

2
recursionprologtransitive-closure
anc4(X, Z) :- anc4(X, Y), ... right there. Prolog will keep selecting the first clause until it fails or succeeds. It does neither. It just keeps calling anc4/2 again. – lurker
See failure-slice on how to diagnose such problems. – false
And see this question for a general way to define this. – false

2 Answers

5
votes

The origin of your 'problem' (i.e. goals order) is deeply rooted in the basic of the language.

Prolog is based on the simple and efficient strategy of chronological backtracking, to implement SLD resolution, and left recursive clauses, like anc4/2, cause an infinite recursion. Indeed, the comma operator (,)/2 stands for

evaluate the right expression only if the left expression holds

So, order of goals in a clause is actually an essential part of the program.

For your concrete case,

... , parent(Y,Z).

cannot be called if 

anc4(X,Y),

doesn't hold.

The counterpart to goals order is clauses order.

That is, the whole program has a different semantics after the clauses are exchanged:

anc4(X,Z):-
    parent(X,Z).
anc4(X,Z):-
    anc4(X,Y),
    parent(Y,Z).

To better understand the problem, I think it's worth to try this definition as well.

1
votes

Prolog cannot handle left recursion by default without a tabling mechanism. Only some Prolog systems support tabling and usually you need to explicitly declare which predicates are tabled.

If you're using e.g. XSB, YAP, or SWI-Prolog, try adding the following directive on top of your source file containing the definition for the anc4/2 predicate:

:- table(anc4/2).

and retry your queries. The tabling mechanism detects when a query is calling a variant (*) of itself and suspends execution of that branch until a query answer is found and tries an alternative branch (provided in your case by the second clause). If that happens, execution is resumed with that answer.

(*) Variant here means that two terms are equal upon variable renaming.