1

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.

false
  • 10,264
  • 13
  • 101
  • 209
No_Name
  • 155
  • 2
  • 14

2 Answers2

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).

flyingplate
  • 106
  • 6
  • thanks a ton for the clarification. It actually made sense why the looping was happening. I just wanted to find a solution for having the same name for fact and rule and why that isn't possible. But this went an extra mile in making me understand what really happened. Thanks again :)) – No_Name Oct 17 '21 at 07:32
0

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.
TA_intern
  • 2,222
  • 4
  • 12
  • Thanks a lot for this. I wasn't aware that there was a memoization function for prolog predicates called table. This was really helpful. – No_Name Oct 17 '21 at 07:34
  • @No_Name This only works for the Prolog implementation that have it, so probably XSB and SWI-Prolog. It seems that by coincidence you are using one of those already. – TA_intern Oct 18 '21 at 02:18