The Meta-Circular Evaluator: Mere Running Mere

The front end can now read Mere and write it back, verified two ways. The obvious next wish, and the one the browser demo made concrete — parse works, so run it — is the evaluator. Writing the evaluator in Mere produces something with a name and a small vertigo attached: a meta-circular interpreter, an interpreter for a language written in that same language, and therefore capable of running itself.

Evaluate before you type-check

The larger vision for this part of the self-host effort was two components, an evaluator and a type checker. The evaluator went first, for a reason that is by now a familiar pattern: it is the simpler and more immediately convincing of the two. Evaluation is dynamic — it runs a program by walking its tree and computing, without needing to know the types first — so it does not depend on the type checker existing yet. And it pays off visibly: an evaluator turns the browser demo from “paste code and see it reformatted” into “paste code and see it run.” The type checker is the harder machine, with unification and generalization to build, so the evaluator goes first to establish the ground before the difficult part.

Most of an interpreter is not the interpreter

The OCaml evaluator is nearly two thousand lines, which sounds like a daunting thing to reproduce in Mere — until you look at where the lines go. About four fifths of them are built-in functions: print, the string operations, the list and vector and map operations, file input and output, and dozens more. Those are not the interpreter. They are the standard library, and they do not need self-hosting at all — they are primitives the runtime already provides, reachable from the self-hosted evaluator the same way any Mere program reaches them.

Strip those away and what actually has to be written in Mere is small: a value type describing what a running program’s values look like, an environment mapping names to values, a pattern matcher, and the dispatch at the heart of a tree-walker — the recursive function that, given an expression and an environment, produces a value. Perhaps two hundred lines against the OCaml’s two thousand. Knowing what you do not have to rewrite is half of making self-hosting tractable: the interpreter’s core is genuinely tiny, and it is tiny because the language it interprets is small — the minimal ML core from early in the series pays off as a small evaluator now.

The core, and a closure by now familiar

The shape is the textbook tree-walker, expressed in Mere’s own types. A value is a variant — an integer, a boolean, a string, a closure, and so on. The environment is a list of name-and-value pairs, looked up by walking it. And the evaluator is a single recursive function that matches on the kind of expression: a variable looks itself up in the environment; a binary operation evaluates both sides and combines them; an if evaluates its condition and takes a branch; a function application evaluates the function and the argument and applies one to the other.

The one piece worth pausing on is the closure, because it is the same idea this series has now met at four different levels. When the evaluator meets a function expression, it builds a closure value that carries the function’s body and the environment in force at that point — the captured bindings, stored directly as a field of the closure value. That is closure conversion once more, but here it needs no cleverness at all: the captured environment is simply a value, a list of bindings held inside the closure. The reference interpreter got closures free from OCaml; the C backend built them as heap env structs; the Wasm backend split them into a memory offset and a table index; and the self-hosted evaluator holds the captured environment as an ordinary variant field. Four representations of one concept — code plus the environment it closed over — each fitted to its layer, and this last one is the most direct: the environment is right there in the data.

What “meta-circular” actually buys

The self-hosted evaluator is a Mere program like any other. It gets compiled by the same four backends, held to the same byte-identical parity, and cross-validated against the OCaml evaluator on a corpus of programs — the harness from the last episode, now checking that Mere-evaluated results match OCaml-evaluated ones. Which means it can be compiled to Wasm and run in a browser, and the demo becomes what the dogfood signal asked for: paste a Mere program, and a Mere interpreter — itself compiled from Mere — runs it and shows the result. A REPL for Mere, in the browser, powered by Mere.

The word “meta-circular” is not just a flourish. An interpreter that can interpret its own language can, in principle, interpret itself — you can hand the evaluator its own source. More than a curiosity, that is a proof about the language’s core: the features chosen back in Parts I and II — variants, recursion, pattern matching, closures — are exactly the features it takes to express evaluation itself, the most fundamental operation a language has. The language turned out to be expressive enough to describe its own execution, which is a quiet way of confirming the small core was the right core.

The evaluator runs programs without caring about their types. The component that cares about types — that rejects the ill-typed before they ever run — is the harder one, and it is next. It means rebuilding Hindley–Milner inference in Mere: unification, generalization, the whole quiet algorithm. Next: the type checker.