Skip to content
Tutorials Center
My learning

Topics

Lesson 12 of 40 ยท Unification and Backtracking

Prolog Proof Search Trees: How Prolog Finds Answers

See exactly how Prolog proves a query: goal selection left to right, clause selection top to bottom, depth-first search trees, success and failure branches and infinite loops.

You can write many Prolog programs by trial and error, but the day a query loops forever or returns answers in a strange order, you need a mental model of what the machine actually does. This lesson gives you that model: Prolog builds a search tree of possible proofs and explores it in a fixed order.

Prolog is read-only on this site. The runnable blocks use the Python mini-Prolog stand-in. One of them prints the search tree of a query using the same algorithm Prolog uses.

The algorithm in four lines

Prolog keeps a goal list, initially the query. Repeat:

  1. If the goal list is empty, succeed: report the bindings.
  2. Take the first goal (leftmost).
  3. Find the first clause in the database (top to bottom) whose head unifies with that goal. Rename the clause's variables to fresh ones. Replace the goal with the clause's body goals and apply the unification bindings to the whole list.
  4. If no clause matches, fail: go back to the most recent choice point (a goal where other clauses were still untried) and try the next clause there.

This is depth-first search with left-to-right goal order and top-to-bottom clause order. It is the whole execution model. (Its formal name is SLD resolution.)

A small example

PROLOG
parent(tom, bob).
parent(bob, ann).
parent(bob, pat).

grandparent(X, Z) :- parent(X, Y), parent(Y, Z).

Query: ?- grandparent(tom, W). The search tree:

flowchart TD
    A["grandparent(tom, W)"] -->|"clause 4"| B["parent(tom, Y), parent(Y, W)"]
    B -->|"parent(tom, bob): Y = bob"| C["parent(bob, W)"]
    C -->|"parent(bob, ann): W = ann"| D["SUCCESS: W = ann"]
    C -->|"parent(bob, pat): W = pat"| E["SUCCESS: W = pat"]
    B -->|"parent(bob, ...) no match for tom"| F["no other match for parent(tom, Y)"]

Each arrow is a clause that unifies with the selected goal. Leaves are success or failure.

Prolog walks this tree depth first: it follows the first match, and reaches W = ann. If you press ; it backtracks to the last choice point, parent(bob, W), tries the second matching clause, and reaches W = pat. Then it tries to go further up: parent(tom, Y) has no more matching clauses, so the search ends and the toplevel prints a final ..

Failure branches

A branch fails when the selected goal unifies with no clause head. Consider:

PROLOG
?- grandparent(bob, W).
false.

The rule gives goals parent(bob, Y), parent(Y, W). parent(bob, ann) binds Y = ann, then parent(ann, W) finds no clause: fail. Backtrack: parent(bob, pat) gives Y = pat, and parent(pat, W) fails. No choice points are left, so the query fails. A failed branch costs time but is otherwise harmless.

Seeing the tree

The stand-in below prints the search tree. Indentation shows depth, clause N is a head that matched (counting from the top of the program), and FAIL marks a goal with no matching clause. Run it to match the diagram above.

Python Printing the search tree (mini-Prolog stand-in)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

In the first tree, the lines SUCCESS W = ann and SUCCESS W = pat are the two leaves of the diagram. In the second, you can see both attempts at parent(Y, W) fail with FAIL.

Clause order and goal order change the tree

Because the search is ordered, it affects:

  • The order of answers: answers come in the order of the leaves from left to right.
  • Efficiency: placing the most restrictive goal first prunes the tree early. likes(X, wine), male(X) and male(X), likes(X, wine) give the same answers, but may explore different amounts of the tree.
  • Termination: some orderings run forever.

Infinite loops from left recursion

PROLOG
edge(a, b).
edge(b, c).

path(X, Y) :- path(X, Z), edge(Z, Y).   % left recursion
path(X, Y) :- edge(X, Y).

The query path(a, c) selects the first clause, whose body starts with path(a, Z), which selects the first clause again, producing path(a, Z1), then path(a, Z2), and so on. The goal list grows forever until the stack is full:

TEXT
ERROR: Stack limit exceeded

The tree has an infinite left branch, and depth-first search never gets to the second clause. Reordering the clauses or putting the recursive call after a goal that consumes input fixes it:

PROLOG
path(X, Y) :- edge(X, Y).
path(X, Y) :- edge(X, Z), path(Z, Y).   % right recursion

This is the most important rule for writing recursive predicates: base case first, and recursion after at least one step of progress. Recursion in Prolog explores it fully.

Python Left recursion loops (mini-Prolog stand-in)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Choice points and determinism

A choice point is a place in the tree where more than one clause could still match. A predicate call is deterministic if it leaves no choice points (exactly one clause can match), and non-deterministic otherwise. The toplevel shows this: if it prints X = a. with a full stop after the first answer, no choice point was left; if it prints X = a ; and waits, one remains. Efficient Prolog code avoids leaving needless choice points. A technique called first-argument indexing helps: SWI-Prolog quickly skips clauses whose first argument cannot match, so keep the discriminating argument first.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. In which order does Prolog select goals and clauses?

    Execution is deterministic: leftmost goal first, first matching clause first.
  2. 2. What kind of search does Prolog perform?

    Prolog follows one branch as deep as possible, and returns to the last choice point on failure.
  3. 3. Why does path(X, Y) :- path(X, Z), edge(Z, Y). loop forever?

    Left recursion makes an infinite left branch in the search tree.
  4. 4. What happens when no clause head unifies with the selected goal?

    Failure leads to backtracking; if there is no choice point left, the query fails.

Summary

  • Prolog proves a query by repeatedly resolving the leftmost goal against the first matching clause.
  • The result is a depth-first search tree: success leaves give answers, failure leaves cause backtracking.
  • Goal and clause order change the order of answers, speed and even termination.
  • Put base cases first and avoid left recursion.
  • A choice point is an untried alternative; the toplevel shows one by waiting after an answer.

Next: Backtracking