Avoiding infinite recursion but still using unbound parameter passing only

Question

I have the following working program: (It can be tested on this site: http://swish.swi-prolog.org, I've removed the direct link to a saved program, because I noticed that anybody can edit it.)

It searches for a path between two points in an undirected graph. The important part is that the result is returned in the scope of the "main" predicate. (In the Track variable)

edge(a, b).
edge(b, c).
edge(d, b).
edge(d, e).
edge(v, w).

connected(Y, X) :-
    (
        edge(X, Y);
        edge(Y, X)
    ).

path(X, X, _, []) :-
    connected(X, _).

path(X, Y, _, [X, Y]) :-
    connected(Y, X).

path(X, Z, Visited, [X|Track]) :-
    connected(X, Y),
    not(member(X, Visited)),
    path(Y, Z, [X|Visited], Track).

main(X, Y) :-
    path(X, Y, [], Track),
    print(Track),
    !.

Results:

?- main(a, e).
[a, b, d, e]
true

?- main(c, c).
[]
true

?- main(b, w).
false

My questions:

1. The list of visited nodes is passed down to the predicates in 2 different ways. In the bound Visited variable and in the unbound Track variable. What are the names of these 2 different forms of parameter passing?

2. Normally I only wanted to use the unbound parameter passing (Track variable), to have the results in the scope of the main predicate. But I had to add the Visited variable too, because the member checking didn't work on the Track variable (I don't know why). Is it possible to make it work with only passing the Track in an unbound way? (without the Visited variable)

Many thanks!

Answer 1

The short answer: no, you cannot avoid the extra argument without making everything much messier. This is because this particular algorithm for finding a path needs to keep a state; basically, your extra argument is your state.

There might be other ways to keep a state, like using a global, mutable variable, or dynamically changing the Prolog data base, but both are more difficult to get right and will involve more code.

This extra argument is often called an accumulator, because it accumulates something as you go down the proof tree. The simplest example would be traversing a list:

foo([]).
foo([X|Xs]) :-
    foo(Xs).

This is fine, unless you need to know what elements you have already seen before getting here:

bar(List) :-
    bar_(List, []).

bar_([], _).
bar_([X|Xs], Acc) :-
    /* Acc is a list of all elements so far */
    bar_(Xs, [X|Acc]).

This is about the same as what you are doing in your code. And if you look at this in particular:

path(X, Z, Visited, /* here */[X|Track]) :-
    connected(X, Y),
    not(member(X, Visited)),
    path(Y, Z, [X|Visited], /* and here */Track).

The last argument of path/4 has one element more at a depth of one less in the proof tree! And, of course, the third argument is one longer (it grows as you go down the proof tree).

For example, you can reverse a list by adding another argument to the silly bar predicate above:

list_reverse(L, R) :-
    list_reverse_(L, [], R).

list_reverse_([], R, R).
list_reverse_([X|Xs], R0, R) :-
    list_reverse_(Xs, [X|R0], R).

I am not aware of any special name for the last argument, the one that is free at the beginning and holds the solution at the end. In some cases it could be an output argument, because it is meant to capture the output, after transforming the input somehow. There are many cases where it is better to avoid thinking about arguments as strictly input or output arguments. For example, length/2:

?- length([a,b], N).
N = 2.

?- length(L, 3).
L = [_2092, _2098, _2104].

?- length(L, N).
L = [],
N = 0 ;
L = [_2122],
N = 1 ;
L = [_2122, _2128],
N = 2 . % and so on

Note: there are quite a few minor issues with your code that are not critical, and giving that much advice is not a good idea on Stackoverflow. If you want you could submit this as a question on Code Review.

Edit: you should definitely study this question.

I also provided a somewhat simpler solution here. Note the use of term_expansion/2 for making directed edges from undirected edges at compile time. More important: you don't need the main, just call the predicate you want from the top level. When you drop the cut, you will get all possible solutions when one or both of your From and To arguments are free variables.