CODEWITHSUNDEEP
prologinfinite-loop
Reclaimer619
Reclaimer619

Reputation: 23

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

Upvotes: 2

Views: 207

Answers (2)

false
false

Reputation: 10142

Another way to identify reasons for non-termination is to reduce the number of inferences your program will execute by adding goals false into your program:

q(Y) :- r(X), false, r(Y).

r(X) :- r(f(X)), false.
r(a) :- false, p(c).
r(a) :- false, p(a).
r(b) :- false, p(b).

?- q(Y).
   loops.

Since this program is still looping, you will need to modify something in the visible part. Note how many things have been removed entirely! No matter how p/1 is defined, this problem will persist.

If you look at q/1 closely, you see one of the problems:

q(Y) :- r(X), false, r(Y).

The variable Y is not used in the visible part at all. The X appears just once. Thus, r(X) will be the most general query possible and thus it will have the worst termination property possible (that depends on the definition of r/1, indeed). In any case, the argument of q/1 has no influence on termination!

There is another property to conclude: The order of clauses does not have any influence on the termination property! You can see this easily: No matter where the clauses that have been removed entirely with false appear, they can be removed.

For more, see .

Upvotes: 1

damianodamiano
damianodamiano

Reputation: 2662

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.

Upvotes: 4

Related Questions