Infinite loop in Prolog. How do I prevent this?

Question

I am writing a program in Prolog that represents the rules of a card game. However, I am running into an infinite loop with the following code.

succ(seven_of_hearts,eight_of_hearts).
succ(eight_of_hearts,nine_of_hearts).
succ(nine_of_hearts,ten_of_hearts).
succ(ten_of_hearts,jack_of_hearts).
succ(jack_of_hearts,queen_of_hearts).
succ(queen_of_hearts,king_of_hearts).
succ(king_of_hearts,ace_of_hearts).
succ(X,Y) :-
   succ(X,Z),
   succ(Z,Y),
   !.

beats(X,Y) :-
   succ(Y,X).

Basically, my attempt with these few lines is to set up a system for determining if one card beats another according to the succ (or succession) relationships I have established. So the query I am running is beats(X,Y), where X and Y and atoms corresponding to cards. This query terminates successfully if it is true. For example, if I query beats(jack_of_hearts,seven_of_hearts), it returns true and terminates.

However, the query enters an infinite loop if it is false. For example, when I query beats(seven_of_hearts,jack_of_hearts). I traced the query and found that due to the recursive nature of the last succ statement, the query follows the chain of succ statements all the way down to the seven_of_hearts, or all the way up to the ace_of_hearts, and then continuously tries to evaluate succ(seven_of_hearts,X) or succ(ace_of_hearts,X) instead of returning false.

I have two questions: using this current structure, how could I prevent this? Or, if that's not possible, what is an alternative structure I could use to accomplish my goal?

EDIT: Here is a screenshot of my trace for one of the failing queries:

    Call: (267) beats(seven_of_hearts, jack_of_hearts) ? creep
Call: (268) succ(jack_of_hearts, seven_of_hearts) ? creep
   Call: (269) succ(jack_of_hearts, _G7104) ? creep
   Exit: (269) succ(jack_of_hearts, queen_of_hearts) ? creep
   Call: (269) succ(queen_of_hearts, seven_of_hearts) ? creep
   Call: (270) succ(queen_of_hearts, _G7104) ? creep
   Exit: (270) succ(queen_of_hearts, king_of_hearts) ? creep
   Call: (270) succ(king_of_hearts, seven_of_hearts) ? creep
   Call: (271) succ(king_of_hearts, _G7104) ? creep
   Exit: (271) succ(king_of_hearts, ace_of_hearts) ? creep
   Call: (271) succ(ace_of_hearts, seven_of_hearts) ? creep
   Call: (272) false ? creep
   Fail: (272) false ? creep
   Redo: (271) succ(ace_of_hearts, seven_of_hearts) ? creep
   Call: (272) succ(ace_of_hearts, _G7104) ? creep
   Call: (273) false ? creep
   Fail: (273) false ? creep
   Redo: (272) succ(ace_of_hearts, _G7104) ? creep
   Call: (273) succ(ace_of_hearts, _G7104) ? creep
   Call: (274) false ? creep
   Fail: (274) false ? creep
   Redo: (273) succ(ace_of_hearts, _G7104) ? creep
   Call: (274) succ(ace_of_hearts, _G7104) ? creep
   Call: (275) false ? creep

lurker lurker · Accepted Answer · 2016-11-18T21:45:55

Your predicate obviously keeps calling itself: succ(X, Y) :- succ(Y, X), .... A simple solution is not to use the same name for your predicate as you do your facts. Get rid of your succ/2 predicate (leaving the facts) in favor of:

successor(X, Y) :- succ(X, Y).
successor(X, Y) :- succ(X, Z), succ(Z, Y).

beats(X, Y) :- successor(Y, X).

Infinite loop in Prolog. How do I prevent this?

1 Answers