The data structure behind Prolog's depth-first search
Depth-first search is associated with the stack data structure. A stack
is a structure where entries are pushed onto the top of the stack and are
popped off (ie taken off) the top of the stack. The process is sometimes
known as LIFO (Last In, First Out) or FILO
(First
In, Last Out).
Prolog uses an algorithm to manipulate the stack, starting with the
user's query.
-
Stage 1: push query onto the stack:
-
route(a,_956)
-
Stage 2: pop first entry off the stack and expand it:
-
route(a, _956) :-
-
path(a, _956).
-
route(a, _956) :-
-
path(a, _957),
-
route(_957, _956).
This is done by finding the procedure that has the same functor
and number of arguments as the query (ie route/2). All clauses from the
procedure are placed on the stack.
-
Stage 3: pop first entry off the stack and expand it:
-
route(a, 1) :-
-
path(a,1).
-
route(a, 3) :-
-
path(a,3).
-
route(a, 6) :-
-
path(a,6).
-
route(a, _956) :-
-
path(a, _957),
-
route(_957, _956).
This is done by finding the procedure that has the same functor
and number of arguments as the first goal of the first entry (ie path/2).
Note that the three new instantiations of the clauses are put on the stack
in place of the entry that was popped. Note also that the second route/2
clause added in Stage 2 is left at the bottom of the stack.
-
Stage 3: pop first entry off the stack and expand it. The first entry cannot
be further expanded, so it is counted as success.
-
...
-
Stage n: the stack is empty so there are no more goals to be proved.
Take time to work through Self-Test
3.
It is important to realise that in Prolog, the user doesn't have to manipulate
the stack themself. It is necessary to understand Prolog's search to enable
you to write efficient programs, and because it is a common search method
in Computer Science generally and in Artificial Intelligence in particular.
