Prolog - Return result instead of printing in algorithm

Question

I know there is technically no 'return' in Prolog but I did not know how to formulate the question otherwise.

I found some sample code of an algorithm for finding routes between metro stations. It works well, however it is supposed to just print the result so it makes it hard to be extended or to do a findall/3 for example.

% direct routes
findRoute(X,Y,Lines,Output) :- 
    line(Line,Stations),
    \+ member(Line,Lines),
    member(X,Stations),
    member(Y,Stations),
    append(Output,[[X,Line,Y]],NewOutput),
    print(NewOutput).

% needs intermediate stop
findRoute(X,Y,Lines,Output) :- 
    line(Line,Stations),
    \+ member(Line,Lines),
    member(X,Stations),
    member(Intermediate,Stations),
    X\=Intermediate,Intermediate\=Y,
    append(Output,[[X,Line,Intermediate]],NewOutput),
    findRoute(Intermediate,Y,[Line|Lines],NewOutput).

line is a predicate with an atom and a list containing the stations.
For ex: line(s1, [first_stop, second_stop, third_stop])

So what I am trying to do is get rid of that print at line 11 and add an extra variable to my rule to store the result for later use. However I failed miserably because no matter what I try it either enters infinite loop or returns false.

Now:

?- findRoute(first_stop, third_stop, [], []).
% prints [[first_stop,s1,third_stop]]

Want:

?- findRoute(first_stop, third_stop, [], R).
% [[first_stop,s1,third_stop]] is stored in R

Answer 1

Like you, I also see this pattern frequently among Prolog beginners, especially if they are using bad books and other material:

solve :-
     .... some goals ...
     compute(A),
     write(A).

Almost every line in the above is problematic, for the following reasons:

1. "solve" is imperative. This does not make sense in a declarative languague like Prolog, because you can use predicates in several directions.
2. "compute" is also imperative.
3. write/1 is a side-effect, and its output is only available on the system terminal. This gives us no easy way to actually test the predicate.

Such patterns should always simply look similar to:

solution(S) :-
     condition1(...),
     condition2(...),
     condition_n(S).

where condition1 etc. are simply pure goals that describe what it means that S is a solution.

When querying

?- solution(S).

then bindings for S will automatically be printed on the toplevel. Let the toplevel do the printing for you!

In your case, there is a straight-forward fix: Simply make NewOutput one of the arguments, and remove the final side-effect:

route(X, Y, Lines, Output, NewOutput) :- 
    line(Line, Stations),
    \+ member(Line, Lines),
    member(X, Stations),
    member(Y, Stations),
    append(Output, [[X,Line,Y]], NewOutput).

Note also that I have changed the name to just route/5, because the predicate makes sense also if the arguments are all already instantiated, which is useful for testing etc.

Moreover, when describing lists, you will often benefit a lot from using dcg notation.

The code will look similar to this:

route(S, S, _) --> [].          % case 1: already there
route(S0, S, Lines) -->         % case 2: needs intermediate stop
    { line_stations(Line, Stations0),
      maplist(dif(Line), Lines),
      select(S0, Stations0, Stations),
      member(S1, Stations) },
    [link(S0,Line,S1)],
    route(S1, S, [Line|Lines]).

Conveniently, you can use this to describe the concatenation of lists without needing append/3 so much. I have also made a few other changes to enhance purity and readability, and I leave figuring out the exact differences as an easy exercise.

You call this using the DCG interface predicate phrase/2, using:

?- phrase(route(X,Y,[]), Rs).

where Rs is the found route. Note also that I am using terms of the form link/3 to denote the links of the route. It is good practice to use dedicated terms when the arity is known. Lists are for example good if you do not know beforehand how many elements you need to represent.