1

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).
false
  • 10,264
  • 13
  • 101
  • 209
Sam Pepper
  • 11
  • 1
  • `byAny(X,Y) :- byCar(X,Y) ; byTrain(X,Y) ; byPlane(X, Y). travel(X,Y) :- closure(byAny,X,Y).` See [this](https://stackoverflow.com/q/26946133/772868) for `closure/3` – false Aug 12 '20 at 08:51
  • See [this](https://stackoverflow.com/a/55209297/772868) for the answer to why it loops. – false Aug 12 '20 at 10:26

1 Answers1

3

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

Isabelle Newbie
  • 9,258
  • 1
  • 20
  • 32
  • Another approach is to add a parameter that tracks which places you've seen and check (using `member/2`) whether a new location is in the list. There are many examples of this in textbooks. – Peter Ludemann Aug 13 '20 at 02:38
  • I don't think that's "another" approach as such. Wouldn't you need to solve the left recursion problem anyway, in essentially the same way? It would be great if you could post an alternative answer! – Isabelle Newbie Aug 13 '20 at 06:48
  • If you change `travel(X,Y):- travel(X,Z), travel(Z,Y).` to `travel(X,Seen0, Seen, Y):- \+ member(X, Seen), travel(X,[X|Seen], Seen1, Z), travel(Z,[Z|Seen1], Seen,Y).`, then I think it works (haven't tested). Tabling is much easier. ;) And of course, you can also change that line to `travel(X,Y):- travel0(X,Z), travel(Z,Y).` if you define `travel0(X,Y) :- byCar(X,Y).` etc. (in essence, query stratification done by hand) – Peter Ludemann Aug 14 '20 at 03:12