Building a Meta-Interpreter

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