Disclaimer: Yes, this is for an assignment, but I think I have an alternative solution already. I just want to figure out why this initial attempt did not work because I can't understand why it isn't functioning as intended.
I'm coding a predicate path/2 (path(+Node1, +Node2)) that takes two nodes and returns true if there is a valid path from Node1 to Node2 through a separately defined edge/2 predicate (semantically, edge(A, B). represents a directed edge from A to B).
% WRAPPER
path(N1, N2) :-
pathHelper(N1, N2, []).
% HELPER
pathHelper(N1, N2, Checked) :-
\+ member(N1, Checked),
(
(N1 = N2, !); % sort of a base case?
NewChecked = [N1 | Checked],
(
edge(N1, Next),
pathHelper(Next, N2, NewChecked)
)
).
To my understanding, once it hits (N1 = N2, !); and is indeed able to unify N1 with N2, it should proceed to the ! cut and discard all previous choice points, and then proceed to short-circuit out of the rest of the statements, meaning it won't look for other nodes that can form a path. However, given the following knowledge base:
% KNOWLEDGE BASE
edge(a,b).
edge(b,c).
edge(c,d).
edge(d,a).
edge(d,e).
edge(b,a).
and the query:
?- path(b, d).
the program displays true. for the path 'b' -> 'c' -> 'd' (verified through trace mode), but also steps back to check 'b' for other connected nodes, landing on 'a' and checking again, then displaying false. From my understanding of how choice points work, the ! should have stopped it from backtracking to 'b' to check for more nodes.
What is flawed about my understanding of the cut operator that is preventing me from understanding why the code results in this output?
"discard all previous choice points"
... made by this invocation of the predicate.
Consider
p(A) :- ( (A=1 ; A=2), !
; A=3
).
q(A):- (A=3 ; A=A), p(A).
Whatever cuts p/1 might have on the inside, we do not want it to affect the specific choices we've explicitly enumerated in our q/1 definition, before the call to p/1, do we? Of course we don't.
Indeed
?- q(X).
X = 3 ;
X = 1 ;
X = 2.
The cut is said to have the predicate where it appears as its scope. Here, it is p/1, not q/1.
If you want q/1 to stop searching after finding its first solution, you need to tell it to stop searching:
s(A):- (A=3 ; A=A), p(A), !.
Now
?- s(X).
X = 3.
In your case, you can float the cut up into the wrapper predicate:
% WRAPPER
path(N1, N2) :-
pathHelper(N1, N2, []),
!.
Now it will stop searching after finding its first solution, as generated by pathHelper/3 inside it.
Recursion doesn't change this. Each invocation of a predicate lives and performs on its own. How could it be otherwise? Imagine p1 invoking p2 and p2 invoking p3 which invokes p1 again. Now, when the deepest invocation of p1 encounters a cut inside it, what would it stop, if not itself? Would it stop p3 above it? Why? How?
To put this differently, your code is fully equivalent to
% WRAPPER
path1(N1, N2) :-
pathHelper1(N1, N2, []).
% one-step HELPER
pathHelper1(N1, N2, Checked) :-
\+ member(N1, Checked),
(
(N1 = N2, !); % sort of a base case?
NewChecked = [N1 | Checked],
(
edge(N1, Next),
pathHelper(Next, N2, NewChecked)
)
).
% recursive HELPER
pathHelper(N1, N2, Checked) :-
\+ member(N1, Checked),
(
(N1 = N2, !); % sort of a base case?
NewChecked = [N1 | Checked],
(
edge(N1, Next),
pathHelper(Next, N2, NewChecked)
)
).
and now it is clear that the cut inside pathHelper should not affect the choices generated by edge/2 inside pathHelper1 above it.