Prolog seemingly ending recursive call without going back up

Question

I've got the following two edges defined:

edge(a,b).
edge(b,c).

add(X, L, [X | L]).

Now I'm trying to recursively build the path from a to c (a,b,c) using this:

path(FROM,TO,W):-
    edge(FROM,TO),
    add(TO, [], X),
    add(FROM, X, W).
path(FROM,TO,W):-
    edge(FROM,Y),
    path(Y,TO, W),
    add(FROM, W, _).

It seems to work fine in the base case as path(a,b,X) will output X = [a,b]. However, path(a,c,X) only outputs X = [b,c], as if it just gets to the base case and ends it there rather than going back up the recursive call. Ultimately, I would like it to output X = [a,b,c] but I'm out of ideas.

FYI I'm using SWI-Prolog.

Yes you're right, I've edited this. Thanks! – Dragonslayer Nov 24 '21 at 13:22 — Dragonslayer, Nov 24 '21 at 13:22

score 2 · Answer 1 · answered Nov 24 '21 at 18:06

How can you identify the problem yourself? There is an easy way to do so. First, identify the cases you expect to be true and cases you expect it to fail. Here are some plus some auxiliary definitions to ease debugging

:- initialization(path(a,b,[a,b])).
:- initialization(path(a,c,[a,b,c])).   % intended to be true, initially false
:- initialization(\+path(a,b,[a,_,c])).
:- initialization(\+path(a,d,_)).       % no node d, thus no path

:- op(950, fy, *).
:- meta_predicate(*(0)).

*_G_0.   % this permits us to remove goals by adding a * in front.

Now, save the program ..and say [program]. You will get a warning like

* user:user:path(a,c,[a,b,c]) - goal failed

So we know that we have not solved the problem.

Now, try to generalize the program by adding * in front of a goal. You will note that for each and every such generalization there will be more errors appearing (and in one case even non-termination). Except for the last goal where everything remains the same. So removing or replacing that goal seems to be a good idea.

Sooner or later you will encounter cycles. For acyclic paths, use path/4:

?- path(edge, Path, A, B).

score 1 · Accepted Answer · answered Nov 24 '21 at 13:56

Your code does not work correctly because it discards the result produced by the subgoal add(FROM, W, _), in the second clause of the predicate path/3. To solve the problem, you need to modify your code as following:

path(From, To, W):-
    edge(From, To),
    add(To, [], X),
    add(From, X, W).

path(From, To, PATH):-   
    edge(From, Y),
    path(Y,To, W),
    add(From, W, PATH). % <== get PATH

An even better version of this code is as follows:

path(From, To, [From, To]) :-
    edge(From, To).

path(From, To, [From|Path]) :-
    edge(From, X),
    path(X, To, Path).

Prolog seemingly ending recursive call without going back up

2 Answers2