Prolog infinite loop

Question

This is a program that should find out who is compatible with john. I am new to Prolog. In order to let Prolog know eg. met(X,Y) = met (Y,X) lots of code has been written. Now when I start the query

?- compatible(john, X)

it goes into infinite looping...

Source code:

compatible(X,Y) :- reading(X), reading(Y).
compatible(X,Y) :- football(X), football(Y).
compatible(X,Y) :- friends(X,Y).
compatible(X,Y) :- mutual(X,Y).
friends(X,Y) :- havemet(X,Y), compatible(X,Y).
havemet(X,Y) :- met(X,Y).
havemet(X,Y) :- met(Y,X).
mutual(X,Y) :- friends(X,Temp), friends(Y,Temp).
mutual(X,Y) :- friends(Temp,X), friends(Y,Temp).
mutual(X,Y) :- friends(X,Temp), friends(Temp,Y).
mutual(X,Y) :- friends(Temp,X), friends(Temp,Y).

football(john).
football(james).
friends(john, carl).
friends(carl, john).
reading(carl).
reading(fred).
reading(emily).
met(carl, emily).
met(fred, james).
met(fred, emily).

I have been researching so much but I still do not understand what is the problem and how to fix that. It would be great for me to help me.

Answer 1

I am not surprised you got an infinite loop. compatible depends on friends while friends depends on compatible. Are you sure this is what you want?

Please note that if you really wanted your rules to be recursive, you would need a stopping condition. But I don't see why you would need recursion for such a simple problem as affinity matching.

Answer 2

So what is the problem with your program? Here is a way to localize the problems you have. By inserting goals false we obtain a failure slice. This is a fragment that shares still a lot of properties with the original program. In particular: if the failure-slice loops, also the original program loops. So the failure-slice shows us a part of the program that has to be modified to overcome the original problem. For your query I get the following fragment that still does not terminate:

?- compatible(john, X), false.

compatible(X,Y) :- false, reading(X), reading(Y).
compatible(X,Y) :- false, football(X), football(Y).
compatible(X,Y) :- false, friends(X,Y).
compatible(X,Y) :- mutual(X,Y), false.

friends(X,Y) :- havemet(X,Y), compatible(X,Y).
friends(john, carl) :- false.
friends(carl, john).

havemet(X,Y) :- false, met(X,Y).
havemet(X,Y) :- met(Y,X).

mutual(X,Y) :- false, friends(X,Temp), friends(Y,Temp).
mutual(X,Y) :- friends(Temp,X), friends(Y,Temp), false.
mutual(X,Y) :- friends(X,Temp), false, friends(Temp,Y).
mutual(X,Y) :- false, friends(Temp,X), friends(Temp,Y).

met(carl, emily).
met(fred, james) :- false.
met(fred, emily) :- false.

But shouldn't just any query for compatible/2 terminate? For the most general query, the failure slice can be reduced even further:

?- compatible(X, Y), false.

compatible(X,Y) :- false, reading(X), reading(Y).
compatible(X,Y) :- false, football(X), football(Y).
compatible(X,Y) :- false, friends(X,Y).
compatible(X,Y) :- mutual(X,Y), false.

friends(X,Y) :- havemet(X,Y), compatible(X,Y).
friends(john, carl) :- false.
friends(carl, john) :- false.

havemet(X,Y) :- false, met(X,Y).
havemet(X,Y) :- met(Y,X).

mutual(X,Y) :- false, friends(X,Temp), friends(Y,Temp).
mutual(X,Y) :- false, friends(Temp,X), friends(Y,Temp).
mutual(X,Y) :- friends(X,Temp), false, friends(Temp,Y).
mutual(X,Y) :- false, friends(Temp,X), friends(Temp,Y).

met(carl, emily).
met(fred, james) :- false.
met(fred, emily) :- false.

It is in the remaining part here where you have to fix the problem somehow. There might be further reasons for non-termination. But you have to fix this one in any case.

And if this is still not good enough, you might add goals V = const into the program. But I think this should suffice...

Answer 3

What Prolog system are you using? Are you required to use a particular system?

Your program as it is will not terminate in a standard Prolog, but will in a Prolog with tabling support, such as XSB-Prolog http://xsb.sourceforge.net/ or B-Prolog http://www.probp.com/ - just add :- auto_table. as a first line of your program.

| ?- compatible(john, X).
compatible(john, X).
X = john ?;
X = james ?;
X = carl ?;
X = emily ?;
no