prologtransitive-closure

Having trouble thinking in prolog. Infinite recursion problem

In reading a book on prolog I have come across trouble with this problem.

% Write a predicate travel_to/2 which determines whether it is possible to 
% travel from one place to another by chaining together car, train, and
% plane journeys. For example, your program should answer yes to the
% query travel_to(valmont,raglan).

by_car(auckland,hamilton).
by_car(hamilton,raglan).
by_car(valmont,saarbruecken).
by_car(valmont,metz).

by_train(metz,frankfurt).
by_train(saarbruecken,frankfurt).
by_train(metz,paris).
by_train(saarbruecken,paris).

by_plane(frankfurt,bangkok).
by_plane(frankfurt,singapore).
by_plane(paris,losAngeles).
by_plane(bangkok,auckland).
by_plane(singapore,auckland).
by_plane(losAngeles,auckland).

travel_to(X,Y) :- ( by_car(X,Y)
                  ; by_train(X,Y)
                  ; by_plane(X,Y)
                  ).
travel_to(X,Y) :-
    travel_to(X,Z),
    travel_to(Z,Y).

I am having a hard time seeing where the infinite recursion is coming from. I think about this code as so: "If X can travel to Y directly then we satisfy the predicate. Otherwise lets see if we can find recursive connections. Is there a Z that X connects to that then connects to Y?

swipl:

?- travel_to(valmont,raglan).
true ; % So it works?
ERROR: Stack limit (1.0Gb) exceeded
ERROR:   Stack sizes: local: 0.9Gb, global: 84.2Mb, trail: 0Kb
ERROR:   Stack depth: 11,028,501, last-call: 0%, Choice points: 12
ERROR:   Probable infinite recursion (cycle):
ERROR:     [11,028,501] user:travel_to(raglan, _22060066)
ERROR:     [11,028,500] user:travel_to(raglan, _22060086)

This should be false:

?- travel_to(losAngeles,metz).
ERROR: Stack limit (1.0Gb) exceeded
ERROR:   Stack sizes: local: 0.9Gb, global: 84.1Mb, trail: 0Kb
ERROR:   Stack depth: 11,028,558, last-call: 0%, Choice points: 6
ERROR:   Probable infinite recursion (cycle):
ERROR:     [11,028,558] user:travel_to(raglan, _22059564)
ERROR:     [11,028,557] user:travel_to(raglan, _22059584)
Solution

  • The problem is that your second clause:

    travel_to(X, Y) :-
    travel_to(X, Z),
    travel_to(Z, Y).

    will always match. Even if there is no destination originating from the X at all, travel_to/2 will simply fallback on the recursive clause.

    Even if we manage to fix that, it is still possible to get into infinite recursion, if for example there is by_car(a, b), and a by_train(b, a), then it is possible that prolog will search a path a - b - a - b - ….

    There are basically two problems:

    1. there is no guaranteed progress, so if no travel path leaves from X it will still keep calling travel_to; and
    2. there is no guarantee we do not run into a cycle.

    We can fix the first one by introducing a predicate step/2 for example:

    step(X,Y) :-
    by_car(X,Y).
step(X,Y) :-
    by_train(X,Y).
step(X,Y) :-
    by_plane(X,Y).

    and next we can make a travel_to/2 predicate which is the transitive closure of step:

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

    This predicate fixes the problem with the guaranteed progress, since the call to step/2 forces Prolog to pick a path and thus make a hop. But it still can run into a cycle.

    We can solve the second problem by maintaining a list of already visited nodes, and reject visiting the same node a second time:

    travel_to(X, Y) :-
    travel_to(X, Y, [X]).

travel_to(X, X, _).
travel_to(X, Z, L) :-
    step(X, Y),
    \+ member(Y, L),
    travel_to(Y, Z, [Y|L]).