CODEWITHSUNDEEP
recursionprologtransitive-closurefailure-slice
Sam Pepper
Sam Pepper

Reputation: 11

Why does my prolog rule get stuck in infinite recursion

My code works for its intended purpose but always gets stuck in a loop at the end giving me an error saying "Stack limit exceeded." My code is below:

byCar(auckland,hamilton).
byCar(hamilton,raglan).
byCar(valmont,saarbruecken).
byCar(valmont,metz).
   
byTrain(metz,frankfurt).
byTrain(saarbruecken,frankfurt).
byTrain(metz,paris).
byTrain(saarbruecken,paris).
   
byPlane(frankfurt,bangkok).
byPlane(frankfurt,singapore).
byPlane(paris,losAngeles).
byPlane(bangkok,auckland).
byPlane(singapore,auckland).
byPlane(losAngeles,auckland).


travel(X,Y):- byCar(X,Y).
travel(X,Y):- byTrain(X,Y).
travel(X,Y):- byPlane(X,Y).
travel(X,Y):- travel(X,Z), travel(Z,Y).

Upvotes: 1

Views: 305

Answers (1)

Isabelle Newbie
Isabelle Newbie

Reputation: 9378

When you call something like travel(metz, To), the last clause of travel/2 will call travel(metz, Z) with a new variable Z, which can then call travel(metz, Z2) with a new variable Z2, and so on.

This problem is called "left recursion": You have a recursive call that is equivalent to the original goal all the way "to the left" (i.e., at the beginning) of a clause. The solution is to "make some progress" before a recursive call. In this case, you can travel one hop before the recursion:

step(X, Y) :-
    byCar(X, Y).
step(X, Y) :-
    byTrain(X, Y).
step(X, Y) :-
    byPlane(X, Y).

travel(X, Y) :-
    step(X, Y).
travel(X, Z) :-
    step(X, Y),
    travel(Y, Z).

This now terminates:

?- travel(metz, To).
To = frankfurt ;
To = paris ;
To = bangkok ;
To = singapore ;
To = auckland ;
To = hamilton ;
To = raglan ;
To = auckland ;
To = hamilton ;
To = raglan ;
To = losAngeles ;
To = auckland ;
To = hamilton ;
To = raglan ;
false.

As pointed out in a comment by false, you can use a general predicate to capture this kind of closure: Definition of Reflexive Transitive Closure. Alternatively, some Prolog systems provide a feature called "tabling" which you can use to avoid this kind of problem: https://www.swi-prolog.org/pldoc/man?section=tabling-non-termination

Upvotes: 3

Related Questions