Search code examples
prologlogicswi-prolog

Why is my prolog program stucked in endless recursion

I have the following experimental code

s(a,b).
s(b,c).
s(c,b).
r(a).
r(c).
r(d).
p(X,Y) :- s(X,Y), not(r(Y)).
q(X,Y) :- q(Y,X), r(X).
q(X,Y) :- p(Y,X), s(X,Y).
t(X,Y) :- r(X), q(X,Y).

Querying for t(X,Y) will result in a endless recursion blowing up the stack. But I can actually think of X=c,Y=b being the solution because

t(c,b) <- r(c), q(c,b)
q(c,b) <- q(b,c), r(c)
q(b,c) <- p(c,b), s(b,c)
p(c,b) <- s(c,b), not(r(b))

Can someone explain to me, why prolog doesn't come to this solution and gets caught in an endless recursion around q(c,b) and q(b,c)

Many thanks!

Solution

  • In SWI-Prolog, you can solve the problem using tabled execution.

    :- table q/2.

s(a,b).
s(b,c).
s(c,b).
r(a).
r(c).
r(d).
p(X,Y) :- s(X,Y), not(r(Y)).
q(X,Y) :- q(Y,X), r(X).
q(X,Y) :- p(Y,X), s(X,Y).
t(X,Y) :- r(X), q(X,Y).

    Examples:

    ?- t(X,Y).
X = c,
Y = b ;
false.

?- q(X,Y).
X = c,
Y = b ;
X = b,
Y = c.