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.