Prolog order of clauses causes pathfinding to fail

Question

I am developing a path finding algorithm in Prolog, giving all nodes accessible by a path from a starting node. To avoid duplicate paths, visited nodes are kept in a list.

Nodes and neighbors are defined as below:

node(a).
node(b).
node(c).
node(d).
node(e).

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

neighbor(X,Y) :- edge(X,Y).
neighbor(X,Y) :- edge(Y,X).

The original algorithm below works fine:

path2(X,Y) :-
    pathHelper(X,Y,[X]).

pathHelper(X,Y,L) :-
    neighbor(X,Y),
    \+ member(Y,L).
pathHelper(X,Y,H) :-
    neighbor(X,Z),
    \+ member(Z,H),
    pathHelper(Z,Y,[Z|H]).

This works fine

[debug]  ?- path2(a,X).
X = b ;
X = c ;
X = d ;
X = d ;
X = c ;
false.

however, when changing the order of the two clauses in the second definition, such as below

pathHelper(X,Y,L) :-
    \+ member(Y,L),
    neighbor(X,Y).

When trying the same here, swipl returns the following:

[debug]  ?- path2(a,X).
false.

The query doesn't work anymore, and only returns false. I have tried to understand this through the tracecommand, but still can't make sense of what exactly is wrong.

In other words, I am failing to understand why the order of neighbor(X,Y)and \+ member(Y,L)is crucial here. It makes sense to have neighbor(X,Y) first in terms of efficiency, but not in terms of correctness to me.

Answer 1

You are now encountering the not so clean-cut borders of pure Prolog and its illogical surroundings. Welcome to the real world.

Or rather, not welcome! Instead, let's try to improve your definition. The key problem is

\+ member(Y, [a]), Y = b.

which fails while

Y = b, \+ member(Y,[a]).

succeeds. There is no logic to justify this. It's just the operational mechanism of Prolog's built-in (\+)/1.

Happily, we can improve upon this. Enter non_member/2.

non_member(_X, []).
non_member(X, [E|Es]) :-
   dif(X, E),
   non_member(X, Es).

Now,

?- non_member(Y, [a]).
dif(Y,a).

Mark this answer, it says: Yes, Y is not an element of [a], provided Y is different from a. Think of the many solutions this answer includes, like Y = 42, or Y = b and infinitely many more such solutions that are not a. Infinitely many solutions captured in nine characters!

Now, both non_member(Y, [a]), Y = b and Y = b, non_member(Y, [a]) succeed. So exchanging them has only influence on runtime and space consumption. If we are at it, note that you check for non-memberness in two clauses. You can factor this out. For a generic solution to this, see closure/3. With it, you simply say: closure(neighbor, A,B).

Also consider the case where you have only edge(a,a). Your definition fails here for path2(a,X). But shouldn't this rather succeed?

And the name path2/2 is not that fitting, rather reserve this word for an actual path.

Answer 2

The doubt you have is related to how prolog handle negation. Prolog uses negation as failure. This means that, if prolog has to negate a goal g (indicate it with not(g)), it tries to prove g by executing it and then, if the g fails, not(g) (or \+ g, i.e. the negation of g) succeeds and viceversa.

Keep in mind also that, after the execution of not(g), if the goal has variables, they will not be instantiated. This because prolog should instantiate the variables with all the terms that makes g fail, and this is likely an infinite set (for example for a list, not(member(A,[a]) should instantiate the variable A with all the elements that are not in the list).

Let's see an example. Consider this simple program:

test:-
    L = [a,b,c],
    \+member(A,L),
    writeln(A).

and run it with ?- trace, test. First of all you get a Singleton variable in \+: A warning for the reason i explained before, but let's ignore it and see what happens.

Call:test
 Call:_5204=[a, b]
 Exit:[a, b]=[a, b]
 Call:lists:member(_5204, [a, b])
 Exit:lists:member(a, [a, b]) % <-----
 Fail:test
false

You see at the highlighted line that the variable A is instantiated to a and so member/2 succeeds and so \+ member(A,L) is false.

So, in your code, if you write pathHelper(X,Y,L) :- \+ member(Y,L), neighbor(X,Y)., this clause will always fail because Y is not sufficiently instantiated. If you swap the two terms, Y will be ground and so member/2 can fail (and \+member succeeds).