Search code examples
prologinfinite-loop

Why do I get a Infinite Loop (Prolog)

I am just starting to learn Prolog and I played around with it. Now I got to a point where I´m stuck. The program i wrote gets into an infinite loop when I ask for

?- q(b).

and I don´t understand why it does that. It would be nice if someone could explain it to me. 

p(a).    
p(b).
q(Y) :- r(X), r(Y).    
r(X) :- r(f(X)).    
r(a) :- p(c).    
r(a) :- p(a).    
r(b) :- p(b).
Solution

  • As said in the comment, the loop is caused by r/1. To show why, yust type ?- trace, q(b). Look at the trace (ignore by now the singleton warning):

     Call:q(b)
 Call:r(_4244)
 Call:r(f(_4162))
 Call:r(f(f(_4162)))
 Call:r(f(f(f(_4162))))
 Call:r(f(f(f(f(_4162)))))
 Call:r(f(f(f(f(f(_4162))))))
 Call:r(f(f(f(f(f(f(_4162)))))))
 Call:r(f(f(f(f(f(f(f(_4162))))))))

    Now you can see that it try to derives r/1 entering a loop. You can see also this question to have a more in depth explaination.

    Notice that in prolog, the order of the clauses matters. Just try to put the line r(X) :- r(f(X)). to the bottom of your program. Now try ?- q(b). On the first answer you get true because prolog unifies X with a and Y with b before entering in a loop.