Out of local stack error in Prolog route planner

Question

I am trying to write Prolog route planner between towns. Here's my code:

road(meath,dublin,5). 
road(dublin,kildare,9).
road(kildare,wicklow,7).
road(wicklow,wexford,10).

/*Rules:*/
route(X,Y,[H|_ ],N) :-
   road(H,Y,_),
   routen(X,Y,N1),
   N is N1.
route(X,Y,[H|T],N) :-
   road(X,H,_ ),
   routen(X,Y,N1), 
   N is N1,
   route(H,Y,T,_),
   !.
route(X,Y,[],N) :-
   road(X,Y,N1),
   N is N1.

routen(X,Y,N) :-
   road(X,Y,N).
routen(X,Y,N) :-
   road(X,Z,N1),
   road(Z,Y,N2),
   N is N1+N2.
routen(X,Y,N) :-
   routen(X,Z,N1),
   routen(Z,Y,N2),
   N is N1+N2,
   !.

The predicate road has the two towns and the distance between them. The rule route finds the list of towns between X and Y and routen finds the overall distance between two towns.

When I run route, it sometimes works and other times I get a ERROR: Out of local stack.

Example:

?- route(meath,wexford,[dublin,kildare,wicklow],31).
true. 

?- route(meath,wexford,[dublin,kildare,wicklow],30).
false.

?- route(meath,kerry,[dublin,kildare,wicklow],31).
ERROR: Out of local stack

The last one should return false, as a route between meath and kerry doesn't exist. Does anyone know why I am getting an error?

Answer 1

Rules in Prolog are LEFT RECURSIVE. In you last rule you did:

routen(X,Y,N) :- routen(X,Z,N1),routen(Z,Y,N2),N is N1+N2,!.

wich it makes your program try the rule routen(X,Z,N1) infinite times. This means that at one point the stack will be full.

Here what happens:

1. find a route from meath to kerry.

2. It doens't exist a direct road between the cities: try to find another intermediate city. It find meath-dublin.

3. Then it try dublin-kerry. But, again, it doens't exist a direct road between the cities: try to find another intermediate city. It find dublin-kildare. And so on.

4. Finally it arrives to find micklow-wexford. So The route found so far is: meath-dublin-kildare-wicklow-wexford.

5. Now it try for wexford-kerry with the first

   route(X,Y,[H|_ ],N) :- road(H,Y,_),routen(X,Y,N1), N is N1.
   

   It satisfy the first one

   road(H,Y,_)
   

   then it reduces

   routen(X,Y,N1), N is N1.
   

   5.1 It tries with the first rule

   routen(wexford,kerry,N) :- road(wexford,kerry,N).
   

   that fails, cause doesn't exist a direct road between them. So it call:

   routen(wexford,kerry,N) :- road(wexford,Z,N1),road(Z,kerry,N2),N is N1+N2.
   

   which fails cause it can't satify

   road(wexford,Z,N1).
   

   At the end, it tries with the last rule

   routen(wexford,kerry,N) :- routen(wexford,Z,N1),routen(Z,kerry,N2),N is N1+N2,!.
   

   So it reduces

   routen(wexford,Z,N1),routen(Z,kerry,N2),N is N1+N2,!.
   

6. It tries to satisfy the first one

   routen(wexford,Z,N1).
   

   with

   routen(X,Y,N) :- road(X,Y,N).
   routen(X,Y,N) :- road(X,Z,N1),road(Z,Y,N2),N is N1+N2.
   routen(X,Y,N) :- routen(X,Z,N1),routen(Z,Y,N2),N is N1+N2,!.
   

   respectively, with

   X=wexford
   Z=DG51_  % or something like that. That is, an not instantiated variable
   

   and repeat the step 5.1

As you can see, it will never find the city "kerry" and it fall in an infinite loop.

Here the new code:

road(meath,dublin,5). 
road(dublin,kildare,9).
road(kildare,wicklow,7).
road(wicklow,wexford,10).

/*Rules:*/

route(X,Y,[H|_ ],N) :- routen(X,Y,N),!.
%route(X,Y,[H|T],N) :- road(X,H,_ ),routen(X,Y,N1), N is N1, route(H,Y,T,_).
route(X,Y,[],N) :- road(X,Y,N1), N is N1.
routen(X,Y,N) :- road(X,Y,N).
%routen(X,Y,N) :- road(X,Z,N1),road(Z,Y,N2),N is N1+N2.
routen(X,Y,N) :- road(X,Z,N1),routen(Z,Y,N2),N is N1+N2.

Notice that at the last rule I put

road(X,Z,N1)

before

routen(Z,Y,N2)

So, if the first clause of that body fails, you'll never fall in a loop with the second one.