PrologEZ
Foundations ยท Lesson 9 of 43

Search & backtracking

How Prolog actually finds answers: depth-first, left-to-right, with undo.

Prolog answers a query by searching:

  1. Take the goals left to right.
  2. For each goal, try the matching clauses top to bottom.
  3. If a goal fails, backtrack: undo the most recent choice and try the next alternative.

This is a depth-first search of a tree of possibilities. Let's watch it happen. Each pick/1 clause announces itself before choosing:

pick(X) :- write('trying red'),   nl, X = red.
pick(X) :- write('trying green'), nl, X = green.
pick(X) :- write('trying blue'),  nl, X = blue.
?- pick(X)

Asking for all solutions makes Prolog visit every clause. Now add a test that rejects some choices:

?- pick(X), X \= red
?- pick(X), X == blue

Each time X \= red fails, Prolog backtracks into pick/1 and tries the next clause, you can see that in the output. Variable bindings made since that choice are undone.

Combinations come from nested backtracking

With two goals, the later goal cycles fastest, like an odometer:

colour(red).
colour(green).
colour(blue).
size(small).
size(large).
?- colour(C), size(S)

Order matters

Because search is depth-first and left-to-right, the order of clauses and goals affects both the answers' order and whether the program terminates at all. Here are two definitions of "ancestor", one is broken:

parent(tom, bob).
parent(bob, pat).
parent(pat, jim).

% BROKEN: the recursive call comes first, so it calls itself forever
bad_ancestor(X, Y) :- bad_ancestor(X, Z), parent(Z, Y).
bad_ancestor(X, Y) :- parent(X, Y).

% GOOD: do real work (parent) before recursing
ancestor(X, Y) :- parent(X, Y).
ancestor(X, Y) :- parent(X, Z), ancestor(Z, Y).
?- ancestor(tom, Who)
?- bad_ancestor(tom, Who)

bad_ancestor is left-recursive: its first goal is a call to itself with exactly the same arguments, so it never makes progress. Prolog keeps stacking up pending calls until it runs out of memory, SWI-Prolog stops it with a stack limit exceeded error rather than crashing.

Exercise: A terminating ancestor

Write ancestor/2 so that it terminates and finds every ancestor, however far up. The parent/2 facts are loaded already.