Prolog query not terminating

Question

This is a very basic query, but I'm new to prolog and have trouble finding why this query does not terminate:

% fact 
progeny(dexter, mark).
progeny(mark, bill).
progeny(bill, lisa).


% rule
progeny(X, Y) :- progeny(X, Z), progeny(Z, Y).

The query, progeny(dexter, X), gives mark, bill and lisa, but does not terminate.
Whereas the query, progeny(Y, lisa), gives bill and dexter and does not terminate (this query answer also misses mentioning mark).
It should be noted that I am using the same name for fact and rule to test for some values.
Any help or clarification for this problem would be much appreciated.

Answer 1

You can also use tabling. Read the docs I linked for background, explanations, details.

To fix your program, you just add a table directive for your predicate progeny/2.

:- table progeny/2.

% fact
progeny(dexter, mark).
progeny(mark, bill).
progeny(bill, lisa).


% rule
progeny(X, Y) :- progeny(X, Z), progeny(Z, Y).

You should now get:

?- [progeny].
true.

?- progeny(dexter, X).
X = bill ;
X = mark ;
X = lisa. % query terminates

?- progeny(Y, lisa).
Y = bill ;
Y = dexter ;
Y = mark. % no missing solutions, query terminates.

Answer 2

You need to define another predicate that will act as transitive relation. The code below works just as fine (notice the predicate progenyt that is the actual transitive relation).

progeny(dexter, mark).
progeny(mark, bill).
progeny(bill, lisa).

progenyt(X, Y) :- progeny(X, Y).
progenyt(X, Y) :- progeny(X, Z), progenyt(Z, Y).

Clarification

When you write progeny(X, Y) :- progeny(X, Z), progeny(Z, Y)., you will, at some point, have prolog trying to match progeny(dexter, Y) :- progeny(dexter, lisa), progeny(lisa, Y)., which is the moment where prolog gets 'confused'.

Namely, it will try to match progeny(lisa, Y) with some fact, which will fail for all entries. Then, prolog will try rule progeny(lisa, Y) :- progeny(lisa, Z), progeny(Z, Y)., which calls for evaluating progeny(lisa, Z). Here you are met with stack overflow, because for progeny(lisa, Y) to succeed, progeny(lisa, Z) has to succeed as well, which induces sort of infinite loop, and that is why your query never terminates.

In the solution I've posted, that can never happen, because for progenyt(lisa, Y) to succeed, progeny(lisa, Z) has to, and that never happens (it fails for all facts). Therefore, it will produce only those three results and will terminate immediately afterwards.

Note that, if progeny and progenyt were to be swapped in the last line, the query will also run into the same problem as before (for progenyt(lisa, Y) to succeed, progenyt(lisa, Z) has to succeed as well first, will causes the infinite loop).