Backtracking & the Search Tree

Course 1 · Ch 4

Nondeterminism baked into the entire execution model — not one opt-in type, the way haskell2-3's own [] monad is

prolog1-1 showed ; producing a second answer without explaining how. Here's the real machinery underneath — and a genuinely rich comparison to a mechanism Haskell only offers as one specific, opt-in monad.

The Search Tree — How Prolog Actually Finds Answers

When a goal has multiple clauses that could match, Prolog tries the first one. If that path later leads to failure, Prolog automatically backtracks to try the next alternative. A useful mental model: a tree of choices, explored via depth-first search, backing up and trying a different branch whenever the current one dead-ends.

Conjunction and the Order Goals Are Tried

?- parent(X, Y), age(Y, 25).

Goals are tried left to right — and if a later goal fails, Prolog backtracks into an earlier goal to try its next alternative there, not just moving on independently. Genuinely sequential dependency, matching haskell2-3's own >>= chaining in spirit (each step can depend on what came before) — but Prolog explores every alternative automatically, with no explicit lambda written per step.

; for Explicit Alternatives (Disjunction)

likes(mary, wine) ; likes(mary, beer).

; is logical OR, usable directly inside a rule body — not just something the top-level REPL shows between answers. Worth naming explicitly: the top-level's own ; prompt and rule-body ; are genuinely the same underlying mechanism, just triggered in two different places.

Comparison to Haskell's Own [] Monad

A genuinely rich comparison: haskell2-3's own list monad represents nondeterminism — >>= on [] explores every combination of possible results, conceptually similar in spirit to Prolog's backtracking search. But Prolog's version is baked into the entire language's execution model by default — every goal call is implicitly a potential source of backtracking, not something wrapped in one specific type a programmer opts into. The same distinction haskell1-5 drew between Java's opt-in Stream laziness and Haskell's own language-wide laziness, appearing again here in a new context: Haskell's [] monad is one specific tool; Prolog's backtracking is the language's own default way of running everything.

A Practical Example — Generating Combinations

?- member(X, [1,2,3]), member(Y, [a,b]).
X = 1, Y = a ;
X = 1, Y = b ;
X = 2, Y = a ;
-- ...and so on — every combination, generated automatically

Real, useful combinatorial work — no explicit nested loop was written anywhere. Backtracking generates every pairing automatically, on demand.

Backtracking Can Be Expensive — A Real, Honest Performance Note

Searching a large tree with many choice points can be genuinely slow if the search space isn't constrained somehow. Chapter 8's own ! (cut) is one real tool for controlling this — foreshadowed here without going deep into it yet.

Aspect	Haskell [] monad (haskell2-3)	Prolog backtracking
Scope	one specific type, opted into	the language's own default execution model
Exploration	explicit >>= chains	automatic, on every goal call
Getting the "next" result	the list itself already holds all results	; requests the next one on demand

Prefer separate clauses over inline ; when readability allows

Multiple rules for the same predicate often read more clearly than one rule with an inline ; disjunction — reach for ; specifically when the alternatives are genuinely local to one small piece of logic.

"Slow" and "will never terminate" can look identical while waiting

A deeply recursive predicate with many choice points can search a genuinely huge space before failing completely — from the outside, a program that's merely slow and one that will never finish look exactly the same while you're waiting on it. A real, practical debugging concern worth being aware of early.

Coding Challenges

Challenge 1

Write three color/1 facts and three size/1 facts, then run a single query combining color(X), size(Y) and use ; to retrieve all combinations.

📄 View solution

Challenge 2

Write a rule using an inline ; disjunction (e.g. drink(mary, X) :- X = wine ; X = beer.) and query it, retrieving both answers.

📄 View solution

Challenge 3

Write a short comment explaining the real difference in SCOPE between Prolog's own backtracking and Haskell's [] monad, using a concrete example of ordinary Prolog code (not wrapped in anything special) that is automatically backtracking-capable.

📄 View solution

Chapter 4 Quick Reference

Prolog explores a search tree depth-first, automatically backtracking to the next alternative on failure
Goals in a conjunction are tried left to right, with backtracking able to reach back into an earlier goal — sequential dependency in spirit like haskell2-3's own >>=, but automatic
; is logical OR, usable directly in a rule body — the same mechanism as the top-level's own "next answer" prompt
Prolog's backtracking is the language's own default execution model — a real scope difference from Haskell's own opt-in [] monad, echoing haskell1-5's Java-Streams-vs-language-wide-laziness distinction
A large, unconstrained search space can be genuinely slow — "slow" and "never terminates" look identical while waiting
Next chapter: lists — Prolog's own [H|T] syntax, a genuine visual convergence with Haskell's own (x:xs)