Self-test 3 solution
How Prolog manipulates its stack
There is no one correct way to show the stack. This solution was produced
simply by writing a depth-first Prolog interpreter (with its own explicit
stack) in Prolog and getting it to output its stack at each stage.
In this solution, I've chosen to use Prolog's model of renaming variables
because it may make easier the understanding of how Prolog keeps track
of variables during recursion. Your answer is not incorrect if you have
not done this.
-
Stage 1:
-
route(4, 8). [the original query]
-
Stage 2:
-
route(4, 8) :- [this isn't true because there is no fact path(4,
8).]
-
path(4, 8).
-
route(4, 8) :-
-
path(4, _960),
-
route(_960, 8).
-
Stage 3:
-
route(4, 8) :-
-
path(4, 5), [Via is instantiated to 5: so recursively
call route/2]
-
route(5, 8).
-
Stage 4:
-
route(5, 8). [Recursive call no. 1]
-
Stage 5:
-
route(5, 8) :-
-
path(5, 8). [true: Prolog could halt here]
-
route(5, 8) :-
-
path(5, _1356),
-
route(_1356, 8).
-
Stage 6:
-
route(5, 8) :-
-
path(5, 8),
-
route(8, 8). [Interesting: trying to find a path from 8 to 8!]
-
Stage 7:
-
route(8, 8). [Recursive call no. 2]
-
Stage 8:
-
route(8, 8) :-
-
path(8, 8). [No way! - fails]
-
route(8, 8) :-
-
path(8, _1914),
-
route(_1914, 8).
-
Stage 9:
-
route(8, 8) :-
-
path(8, b), [There is a path to b]
-
route(b, 8). [Interesting: trying to find a path from b to 8!]
-
Stage 10:
-
route(b, 8). [Recursive call no. 3]
-
Stage 11:
-
route(b, 8) :-
-
path(b, 8). [No way! - fails]
-
route(b, 8) :-
-
path(b, _2310), [There is no path from b]
-
route(_2310, 8).
