The Interpreter and the C Backend: Building Closures by Hand

The previous episode argued that the interpreter defines what a program means and the code generators must reproduce it byte for byte. This one looks at the first two of the four — the interpreter that sets the reference, and the C backend that first has to match it — and at the single problem that makes the gap between them concrete: how do you represent a closure in a language that doesn’t have one?

The interpreter, and closures for free

The interpreter is a tree-walker: it takes the syntax tree the parser produced and evaluates each node directly, recursively, carrying an environment that maps names to values. Evaluating x + 1 means evaluating x, evaluating 1, and adding. Evaluating a function call means evaluating the function, evaluating the argument, and applying one to the other. There is nothing clever here, and that is the point: the interpreter is meant to be the obviously correct reading of the language, the version simple enough that you can believe it by inspection. That is why it gets to be the reference the other three are measured against.

What makes it so simple is a debt being quietly paid by an earlier decision. A closure — a function that captures variables from the scope it was written in — is almost nothing to implement here, because the host language, OCaml, already has closures. When the interpreter evaluates fn x -> x + n, it can just build a host closure that holds onto the environment where n lives; the host runtime handles the capture, the storage, the lifetime. The episode early in this series on choosing OCaml made exactly this bet — that a host with algebraic data types, pattern matching, and its own closures and garbage collector would make the interpreter and type checker fall out easily. This is where the bet pays: the whole hard machinery of closures is borrowed from the host and costs the interpreter almost nothing.

The C backend has to pay in cash

The C backend cannot borrow any of that. C has no closures, no garbage collector, no tagged unions with behavior — it has functions defined at the top level, structs, and pointers. So everything the interpreter got for free from OCaml, the C backend has to build, explicitly, out of those parts. That gap — between what a rich host hands you and what a bare target forces you to construct — is most of what compilation actually is.

The build was done the way the whole project works: one language feature at a time, each a small slice checked against the interpreter before the next began. Integers first, then strings, then tuples (which become C structs), then records (typedefs), then variants (tagged unions with a match compiled to a chain of tag tests). Each step is a self-contained translation, and each is validated by the differential test from the last episode — compile it, run it, compare the bytes to what the interpreter said. Then comes the one that isn’t mechanical.

Making a closure out of a struct and a pointer

A closure is two things fused together: some code, and the captured variables the code refers to. In OCaml, and so in the interpreter, those two arrive as a single value and you never have to think about the seam. In C there is no such value, so the backend has to split the closure back into its two parts and carry them explicitly — a technique called closure conversion.

It happens in a few moves. A function written inside another function is lifted to the top level, since C only has top-level functions. Its captured variables, which it used to reach by simply naming them, can no longer be reached that way once it’s been lifted out — so they are gathered into a heap-allocated environment struct, and every reference to a captured variable is rewritten to read it out of that struct. The closure value that gets passed around is then a small pair: a pointer to the lifted function, and a pointer to its environment. Calling it means calling the function pointer with the environment pointer as a hidden first argument — c.fn(c.env, x). A plain top-level function that captures nothing still needs to be passable as a value, so it gets a trivial adapter and an empty environment, and fits the same pair shape. Where the compiler can see exactly which function is being called, it skips the pair entirely and emits a direct call as a fast path — an optimization that changes speed, never output, so parity holds.

There is a quiet echo of the language’s own philosophy in this. A closure’s captured environment is, in most languages, the very definition of something implicit — the invisible bag of surrounding state a function silently drags along. Closure conversion makes that bag explicit: a concrete struct, allocated somewhere definite, passed as an ordinary argument, its contents named and reachable. The compiler is doing to closures exactly what the language does to effects and memory — taking an ambient, invisible thing and turning it into a value you can point at. The difference is only that here it happens under the hood, in service of a C target that refuses to pretend otherwise.

Two backends, one meaning

By the end of this the two backends stand in the relationship the whole part depends on. The interpreter is the short, trustworthy definition of the language, leaning on its host for the hard parts. The C backend is the longer, more literal reconstruction of that same meaning, spelling out by hand — as lifted functions, env structs, tagged unions — everything the interpreter took on loan. And because every slice was checked against the interpreter as it landed, the two produce the same bytes: two very different implementations, held to one meaning.

That reconstruction is portable C, which runs anywhere a C compiler does. But C is not the only target worth compiling to, and it is not the one with the best story for optimization. Next: the LLVM backend — emitting LLVM’s intermediate representation instead of C source, and what changes when the target is an IR designed for compilers rather than a language designed for people.