Course 1 ended with prolog1-4's backtracking and prolog1-8's cut — both about controlling a search that hands back one solution at a time, via ;. Course 2 opens with the natural next question: what if you want all of them, at once, as an ordinary list you can pass around? That's exactly what findall/3, bagof/3, and setof/3 do — three meta-predicates, genuinely different from each other, that collect a backtracking search's results into one concrete value.

The Problem: Backtracking Gives You Answers One At A Time

Recall the family facts from Course 1:

Each ; press asks Prolog to backtrack and try again. That's fine at the interactive top level, but it's useless inside a program — a predicate that wants "every child of tom, as a list" has no way to press ; for you. Something has to drive the backtracking to exhaustion and gather the results.

findall/3 — The Simplest Collector

findall(Template, Goal, List) runs Goal, collecting Template for every solution found by backtracking, and unifies List with the result — all in one call, no interactive ; needed. This is genuinely close to the mental model Haskell's own list monad gives you (haskell2-3): both collect every result of a nondeterministic computation into one concrete list. The difference is Haskell builds that list through do-notation over [] as a monad instance; Prolog's findall is a dedicated meta-predicate that drives Prolog's own SLD search directly.

findall has one important, very forgiving property: if Goal has no solutions at all, findall still succeeds — with an empty list, not a failure.

bagof/3 — Respecting Free Variables

bagof/3 looks like a drop-in replacement for findall at first glance, but it behaves genuinely differently whenever the goal contains a variable — like Parent below — that isn't in the template:

Instead of one combined list, bagof groups the results by every possible binding of the free variable Parent, backtracking through each group separately. This is a genuine, easy-to-miss surprise coming from findall — the same query, one predicate swapped for another, produces three separate answers instead of one merged list.

To get findall-style behaviour — one combined list, ignoring who the parent was — use the ^ operator to tell bagof to treat Parent as existentially quantified ("for some Parent," not "grouped by Parent"):

setof/3 — Sorted, Deduplicated Results

setof/3 shares bagof's free-variable grouping behaviour exactly, with two extra guarantees: the resulting list is sorted (Prolog's standard order of terms) and has all duplicates removed.

Compare this to what findall would have produced for the same query — [bob, liz, ann, pat, jim], in whatever order the facts were tried and with any duplicates left in. setof is the right choice specifically when the caller needs a canonical, duplicate-free answer rather than a raw trace of the search.

Coding Challenges

Every predicate this course has used so far — from Course 1's parent/2 facts through prolog2-1's findall queries — has been fixed: written once in the source file, unchanging for the life of the program. This chapter introduces a genuinely different capability — changing the fact database itself, while the program runs — and is honest about what that costs.

assertz/1 and asserta/1 — Adding Facts at Runtime

assertz/1 adds a new fact (or rule) to the end of the database for that predicate — as if it had been written in the source file all along, but happening live, mid-query. asserta/1 does the same thing at the beginning instead, so it's tried first on the next query. Neither existed anywhere in this course's vocabulary before now — every predicate up to this point was defined once, statically, and stayed that way.

retract/1 — Removing Facts at Runtime

retract/1 removes the first fact matching its argument from the database. Combined, assertz and retract give a predicate the ability to update a fact — retract the old value, assert the new one — something no purely declarative set of facts and rules can do to itself.

A Practical Use — a Runtime Counter

The clearest demonstration of what this actually buys: a predicate that remembers how many times it's been called, something genuinely impossible using only Course 1's tools.

counter(0) is retracted and a new counter(N1) asserted on every call to increment — real, persistent, mutable state living inside Prolog's own database, surviving across separate top-level queries the way a variable in an imperative language would.

The Real Tension With Declarative Purity

prolog1-8's cut already cost this course one honest admission — that a predicate's search could depend on execution order. assert/retract goes further: it means the facts themselves can differ depending on when a query is run relative to other goals, not just how the search through them is pruned. A query against score/2 run before an assertz call can produce a genuinely different answer than the identical query run after it — the same textual query, two different truths, depending purely on timing. That is about as far from "a fixed set of relations, true regardless of when you ask" as Prolog gets.

This deserves the same honesty this site has given every other real language tradeoff — most recently haskell2-4's own acknowledgment that unsafePerformIO genuinely can break Haskell's IO-tracking guarantee, not just theoretically. assert/retract is Prolog's own version of that same kind of escape hatch: a real, practical, frequently-used tool that knowingly steps outside the paradigm's own core promise.

Coding Challenges

prolog1-8 ended with a brief preview: Course 2 would properly explain \+, Prolog's negation operator, commonly built internally from exactly the cut-based pattern that chapter showed. This chapter delivers on that promise — and, in keeping with this course's own honesty about assert/retract last chapter, is equally direct about what \+ genuinely does not guarantee.

What \+ Actually Means

Read this the way prolog1-8 taught you to read cut. If Goal succeeds, the first clause's body runs: the cut commits, then fail forces the whole thing to fail — so \+ Goal fails whenever Goal itself succeeds. If Goal fails, the first clause never gets past its own body, so Prolog falls through to the second clause, \+ Goal., which unconditionally succeeds. The net effect: \+ Goal succeeds exactly when Goal cannot be proven, and fails exactly when it can.

This is the classic, genuinely useful shape: "assume something is true unless it can specifically be shown otherwise." can_fly(pingu) fails because penguin(pingu) succeeds, so \+ penguin(pingu) fails — the negation working exactly as intended here.

The Closed-World Assumption

Notice what \+ Goal is actually testing: not "Goal is false," but "Goal cannot currently be proven from what's in the database." Prolog operates under the closed-world assumption — anything not provable from the known facts and rules is treated as false, full stop, with no third option for "unknown." That's a genuinely different, stronger claim than classical logical negation makes, and it's the real, well-documented limitation this chapter is named for.

This succeeds — but only because this particular flight/2 database happens not to list a Paris-Tokyo route, not because a Paris-Tokyo flight is provably impossible. Absence of evidence isn't evidence of absence: \+ can only ever report "not provable from what I currently know," and an incomplete database will report that honestly, misleadingly, exactly like a complete one would.

A Concrete Gotcha — Unbound Variables Inside a Negated Goal

The first query fails, because flight(paris, X) genuinely does succeed — for X = london, among others — so its negation fails. The second succeeds, because nothing matches flight(rome, X) at all in this database. The gotcha: with a free variable inside Goal, \+ Goal is really asking "does no value of X make this true," existentially quantified over every possible binding — not "is this specific unknown X not a flight destination." And whichever way it resolves, X itself comes back unbound either way — \+ never exposes any binding Goal might have found internally, even when it fails because of one.

Coding Challenges

prolog1-5 and prolog1-6 covered ordinary Prolog lists — [H|T], recursion over them, the everyday tools. This chapter revisits those same lists with a performance question those chapters never raised: what happens when you need to build up a large list by repeatedly concatenating pieces onto it? The naive answer turns out to be genuinely slow — and difference lists are the real, standard technique for fixing that.

The Problem — Naive append/3 Is O(n), and Repeated Appending Is Worse

Every call to append/3 walks the entire first list, one element at a time, before it can even begin producing the combined result — a call on a list of length n costs n steps. That's fine for one call. It becomes a real problem the moment you need to build a list by appending onto it repeatedly inside a loop or a recursive accumulation — say, flattening a list of ten thousand small lists one at a time. Each append call re-walks everything accumulated so far, so the total cost isn't 10,000 cheap steps — it's O(n²), the same quadratic blowup that shows up whenever repeated concatenation is done the naive way in any language.

The Idea — An Open List With a Known "Hole"

A difference list represents a list not as one closed term, but as a pair: the list itself, and a variable marking its own currently-unbound tail — conventionally written List-Hole. For example, [a, b, c | Hole] paired with that same Hole represents the list [a, b, c], but with its tail left deliberately open rather than closed off with [].

The entire point of leaving that tail open: concatenating two difference lists no longer requires walking either one. It's a single unification.

Read this literally: the first difference list is "some list A, whose open tail is B." The second is "some list B, whose open tail is C." Concatenating them means unifying the first list's hole (B) directly with the second list's own list (also written B) — which is the second list, spliced straight into the first one's open tail, for free.

A Concrete Worked Example

H1 — the first list's hole — unifies with L2, the entire second list, so L1 becomes [1, 2, 3, 4, 5 | H2] without a single element of either original list ever being walked or copied. The combined difference list still has an open tail, H2 — concatenation didn't close anything, it just spliced two open lists into one, still open.

Closing a Difference List

An open difference list isn't yet an ordinary Prolog list — closing one just means unifying its remaining hole with []:

Only at this final step does the term become a genuine, closed [1, 2, 3, 4, 5] — indistinguishable at that point from a list built the ordinary way.

Coding Challenges

prolog2-4 ended with a promise: the difference-list threading built by hand there reappears, hidden, inside Prolog's own --> notation. This chapter delivers on that — DCGs are Prolog's built-in grammar-writing sugar, and no other language covered on this site has anything comparable baked directly into the language itself, not layered on as a separate parser-combinator library.

The --> Notation

A DCG rule looks like an ordinary Prolog clause, but with --> instead of :-, and its body written as a sequence of terminals — literal list elements in square brackets — to be matched against the input, left to right. phrase/2 is how you actually run one: phrase(NonTerminal, List) checks whether List can be fully consumed by the grammar rule NonTerminal.

What --> Is Actually Sugar Over

Every DCG rule is translated, automatically, into an ordinary Prolog clause with two extra hidden arguments — an input-so-far list and a remaining-list, threaded through exactly like prolog2-4's own List-Hole pair. Conceptually, greeting --> [hello], [world]. becomes:

Each terminal peels one element off the front of the "remaining input so far" list, threading the leftover tail into the next goal — S0 to S1 to S, the exact same open-list-with-a-hole pattern the previous chapter built by hand. phrase(greeting, [hello, world]) is really just calling greeting([hello, world], []) — the whole list in, nothing left over.

Nonterminals — Rules Calling Rules

A DCG rule body can reference other DCG rules, not just literal terminals — each nonterminal call receives whatever input is left after the rules before it, and passes along whatever remains after it consumes its own piece. This is exactly how a real grammar is meant to compose: small rules for individual pieces (noun, verb), combined into larger ones (noun_phrase, sentence) without any of them needing to know how the input-threading actually works underneath.

Embedding Ordinary Prolog Code — Curly Braces

Anything inside { } inside a DCG body is treated as an ordinary Prolog goal, run as-is rather than being interpreted as a grammar symbol to match against the input list — the escape hatch that lets a grammar rule check arithmetic, call another predicate, or do anything else Prolog can normally do, mid-parse.

A Practical Use — Summing an Expression List

A genuinely useful grammar, not just a toy: expr parses a term, then repeatedly looks for plus followed by another term, accumulating the running total with prolog1-7's own is/2 inside a curly-brace escape at each step, until expr_rest's empty-list base case is reached and the accumulated sum is unified with the final result.

Coding Challenges

haskell2-8 closed the Haskell track with a capstone interpreter: a hand-built Expr a GADT representing a small custom expression language as data, plus an evalM function pattern-matching over it. That interpreter needed real, deliberate design — Haskell had to invent a data representation of "a program" from scratch, entirely separate from actual Haskell syntax. This chapter builds a Prolog interpreter in Prolog, and it comes out startlingly short — for a reason worth naming precisely.

What "Meta-Interpreter" Means

A meta-interpreter is a program that executes other programs — an interpreter written in the same language it interprets. Here, that means writing a Prolog predicate, solve/1, that itself carries out the job Prolog's own engine normally does: given a goal, prove it by finding and running matching clauses.

Homoiconicity — Code Is Data

A clause body like parent(X, Y), parent(Y, Z) isn't secretly encoded as something else internally — it is the ordinary term ','(parent(X,Y), parent(Y,Z)), built from the same ,/2 functor that appears anywhere else a comma joins two things. Prolog source code is, structurally, just Prolog terms — the same terms every other chapter in this course has manipulated with unification, findall, and pattern matching. This is homoiconicity: code and data share one representation, with no translation step required to go from "a program" to "a value my own language can inspect."

The Core Meta-Interpreter

Three clauses, cut-guarded so each case commits once matched, exactly the way prolog1-8 taught you to read cut. clause(Head, Body) is a built-in that looks up a user-defined clause matching Head, unifying Body with its body — true for an ordinary fact, backtracking over every matching clause if there's more than one.

Tracing solve/1 By Hand

solve(grandparent(tom, Z)) falls through to the third clause: clause(grandparent(tom, Z), Body) unifies Body with (parent(tom, Y), parent(Y, Z)). Recursing into solve/1 on that body hits the second clause instead — a conjunction — splitting into solve(parent(tom, Y)) followed by solve(parent(Y, Z)). The first call looks up parent(tom, Y) via clause/2 again, finds Body = true for Y = bob (or, on backtracking, Y = liz), and solve(true) succeeds via the first clause. The second call repeats the same process for parent(Y, Z), producing Z = ann or Z = jim depending on which Y was chosen. Nothing here is special-cased for grandparent/2 specifically — solve/1 genuinely re-derives the answer the exact same way Prolog's own engine would, using only clause/2 lookups and ordinary unification.

The Real Comparison — haskell2-8's Interpreter vs. This One

haskell2-8's Expr a GADT needed dedicated constructors for every piece of its toy language — IntLit, BoolLit, Add, Div, If — and its evalM function had to pattern-match each one out by hand, because Haskell source code and Haskell data are two entirely separate things; representing "a program" as a value required inventing a whole new type just for that purpose. solve/1 needed no such invention. It interprets actual Prolog — real conjunctions, real user-defined clauses, not a small toy subset reinvented for the exercise — because a Prolog goal already is exactly the kind of term Prolog itself is built to unify, inspect, and recurse over. Three clauses were enough precisely because nothing needed translating first.

Extending the Interpreter — Disjunction and Negation

Two new clauses, inserted before the generic fallback so their own cuts get the chance to commit first. The disjunction clause simply solves either branch. The negation clause is the most telling one — it reuses the host language's own \+ directly on the result of a recursive solve call, rather than reimplementing prolog2-3's negation-as-failure logic from scratch. solve/1 stays a thin, faithful layer over the real Prolog engine, not a full reimplementation of one.

Coding Challenges

A lighter chapter than the last — a first look, not an exhaustive tour — at a genuinely practical extension: constraint logic programming over finite domains, CLP(FD). It's exactly the right tool for problems shaped like puzzles — Sudoku, N-Queens, scheduling — and it previews the technique this course's own capstone will lean on.

The Problem With Plain Backtracking Search

Ordinary Prolog can solve this — between/3 generates candidate values one at a time, and =:= checks the constraint after both values are already committed to. That's fine here, but the pattern doesn't scale: for a harder problem with many variables and many constraints, this "generate first, test after" approach can waste enormous effort fully constructing candidates that were doomed from the very first choice, only discovering that on the very last check.

CLP(FD) — Constraints Applied Before Values Are Chosen

X in 1..9 declares X as a domain variable — not yet a number, but a variable whose eventual value is constrained to that range. Posting X + Y #= 10 and X #< Y immediately narrows both domains through constraint propagation, before either variable has been assigned any specific value at all — the underlying CLP(FD) solver actively removes impossible values from consideration up front, rather than waiting for backtracking to stumble onto them one by one.

#= vs. is vs. = — A Fourth Operator, Genuinely Different Again

prolog1-7 distinguished is, =, and ==. CLP(FD) adds a fourth, #=, distinct from all three: unlike is/2, which demands its right-hand side already be fully ground arithmetic or raises an error, #= can be posted between variables whose values aren't known yet — it behaves bidirectionally, immediately constraining both sides' domains relative to each other, rather than requiring one side to already be a concrete number.

is/2 fails outright with an unbound Y. #= instead immediately derives a constrained domain for X from whatever domain Y already has — real, useful information, produced before any concrete value has been chosen for either variable.

label/1 — Forcing Concrete Values

A domain variable stays exactly that — a range of still-possible values, narrowed by propagation — until something forces the search to actually commit to specific numbers. label(Vars) does that: it backtracks through concrete values for each variable in Vars, but only within whatever each domain has already been narrowed down to by constraint propagation, not the original full range.

Coding Challenges

The final chapter of the full Prolog track. This capstone builds a real N-Queens solver — combining prolog2-7's CLP(FD), prolog1-8's cut, prolog2-1's findall, and prolog2-5's DCG notation into one working project — and closes with the comparison this entire track was framed around from its very first chapter: two languages, both routinely called "declarative," solving computation in genuinely different ways.

The Problem — N-Queens

Place N queens on an N×N chessboard so that no two attack each other — no shared row, no shared column, no shared diagonal. A classic constraint-satisfaction problem, and exactly the shape prolog2-7 named as CLP(FD)'s natural strength.

Modeling With CLP(FD)

Queens is a list of N domain variables, one per column, each holding that column's queen's row — column position is implicit in the list index, so "no shared column" is automatic. ins is prolog2-7's own in, pluralized to apply one domain declaration to an entire list at once. safe_queens/1 walks the list, posting a #\= (row clash) and a diagonal-distance constraint between every pair of queens — real unification and real constraint propagation, narrowing the search before label/1 ever commits to a single value.

One Solution vs. All Solutions

The cut after queens(4, Qs) is prolog1-8's own backtracking-control tool, put to genuine use — it commits to the first solution label/1 finds rather than leaving choice points open for a caller who only wants one answer. findall — prolog2-1's own meta-predicate — does the opposite: it drives queens/2 to exhaustion, collecting every valid 6-queens board into one list. Four is the well-known correct count of distinct solutions for N = 6.

Rendering a Board With a DCG

prolog2-5's --> notation, reused to generate a row rather than parse one — DCGs run perfectly well in either direction. For each column C, symbol/2 emits q if that column's queen sits in the row currently being rendered, otherwise e.

The cut in symbol(Row, Row) --> !, [q]. is genuinely load-bearing, not just tidy — and it's a red cut by prolog1-8's own test. Without it, backtracking into symbol/2 at a queen's own column could still also match the catch-all second clause, producing an additional, factually wrong reading of that cell as empty. Removing this cut would genuinely change which results the predicate can produce — the defining test for red vs. green.

One last, quiet connection: forall/2 is standardly defined as forall(Cond, Action) :- \+ (Cond, \+ Action). — double negation, built directly from prolog2-3's own \+. This capstone never calls \+ by name, but it's running underneath every row printed, exactly the way prolog2-6 showed a meta-predicate can be a thin layer reusing something more fundamental.

Chapter Attribution

Two Declarative Paradigms — Closing the Prolog Track

Every earlier chapter that named Haskell did so piece by piece — unification against pattern matching, backtracking against the [] monad, cut and assert against unsafePerformIO. This capstone is the place to say the whole comparison plainly, using N-Queens itself as the concrete anchor.

A Haskell N-Queens solver would be a genuine function — most naturally built over the [] monad's own do-notation (haskell2-3), generating candidate placements, filtering out attacking ones, and returning a concrete list of valid boards as its result. The search is real, but it's expressed as ordinary values flowing through ordinary function composition — solve(N) :: [[Int]] is a pure computation, evaluated to produce a value, the same as any other Haskell expression.

This chapter's queens/2 is not a function computing a value — it's a relation, and Queens is not returned so much as discovered: a set of variable bindings that happen to satisfy every constraint posted against them, found by an engine built to search exactly that way. CLP(FD) makes the search efficient, but it doesn't change what's actually happening underneath — Prolog was never evaluating an expression to a value; it was finding bindings that make a relation true.

Both are honestly "declarative" — neither language makes you write an explicit loop or a mutable counter to find these boards. But they earn that label in two structurally different ways, and this whole track, from prolog1-1's very first "no main" surprise to this capstone's own solver, has been the concrete demonstration of exactly what that difference looks like in practice.

Coding Challenges