Prolog "Out of local stack" Error

2
votes

Here is my simple Prolog program:

friend(X,Y):-
   knows(X,Y).
friend(X,Z):-
   friend(X,Y),
   friend(Y,Z).

knows(brian,tom).
knows(tom,peter).

If I type the following query

friend(brian,peter).

Prolog will give the following output:

?- friend(brian,peter).
true

If a further type a semicolon, Prolog will say:

ERROR: Out of local stack

What am I doing wrong here?

2
prologfailure-slicetransitive-closure

2 Answers

5
votes

The error is in the second clause. It should be instead:

friend(X,Z):-
   knows(X,Y),
   friend(Y,Z).

Otherwise, when you ask Prolog for more solutions, you end up having the friend/2predicate recursively calling itself without first establishing a knows/2intermediate relation. You can learn more about the bug in your program by tracing the calls to the friend/2 predicate. Try:

?- trace, friend(brian,peter).
1
votes

The understand the source of non-termination in your program it suffices to look at the following failure-slice:

friend(X,Y):- false,
   knows(X,Y).
friend(X,Z):- 
   friend(X,Y), false,
   friend(Y,Z).

knows(brian,tom) :- false.
knows(tom,peter) :- false.

It is because of friend(X, Z) :- friend(X, Y), ... that your program will not terminate. It will produce answers, here and there, but ultimately it will loop. For more, see .