The Compiler That Had Never Run Itself
Self-hosting has two meanings that are easy to confuse. One is that the compiler can emit itself as a valid binary; the other is that the emitted binary is itself a working compiler. The first had been achieved parts ago and had felt like the summit. It was a false one — because emitting a program is not running it, and the self-compiled compiler had never once been executed. The first time it was, it overflowed the stack immediately, on a trivial input, and the reason it did was not a bug in the logic but a single instruction the compiler had never learned to emit.
There is a word that had been used for something Mere achieved several parts ago — self-hosting — and it turned out to mean two different things that are easy to run together. One is that the compiler, written in Mere, can take its own source and emit a valid binary: every module, including the code generator compiling its own code, lowered to WebAssembly that a validator accepts. That had been done, and it was real, and at the time it had felt like the summit of the whole project. The other meaning is stronger and was quietly still out of reach: that the emitted binary, run as a program, is itself a working compiler — that if you hand it a source file it produces the right output. The gap between those two is the whole of this part, and it is a gap that stays invisible until you do the one thing the first meaning never requires: actually run the thing.
The test that had never been run
The way to settle the stronger claim is a fixpoint test, and it is simple to state. Take a small program. Compile it twice. The first time, with the compiler running the ordinary way, under the interpreter, and keep the output. The second time, with the compiler that has been compiled by itself into a WebAssembly binary and is now running as that binary — hand it the same program and keep its output. If the two outputs are identical, and if running either of them does the right thing, then the compiled compiler is a faithful copy of the compiler: a true bootstrap fixpoint. Structural self-hosting had produced the binary needed for the second half of that test, but it had stopped there. Emitting a valid binary and executing it are different acts, and the second had never been performed.
The first run
So it was performed, and it failed at once. The self-compiled compiler, handed a program as trivial as could be, did not produce wrong output — it produced no output at all, because it ran off the end of the stack and crashed. Raising the runtime’s stack limit, the reflexive first move, did nothing useful; pushed high enough, the runtime itself gave out before the program did. Whatever was wrong was not going to be fixed by giving it more room. Something in the compiled compiler was consuming stack without bound.
Not a bug — a limit
The decisive clue was a comparison. That same trivial program, compiled the first way — by the compiler under the interpreter — finished without trouble and produced its answer. The computation therefore terminated; it was finite. So the crash was not infinite recursion, not a logic error that looped forever. It was a resource limit: the exact same finite computation completed on the interpreter’s generous stack and overflowed the far shallower stack of the WebAssembly runtime. This is the same lesson a generous host had taught twice already in this series, wearing new clothes. The interpreter, running on a large native stack, had been hiding a cost the whole time. Only when the computation was moved onto a stack that counted every frame did the cost become visible — and it was not a defect in what the program computed, but in how deeply it had to descend to compute it.
The instruction the compiler never emitted
Why descend so deeply? The tokenizer and parser were written in a tail-recursive style, the disciplined kind that accumulates a result and loops rather than nesting — precisely the shape that is supposed not to grow the stack. And it made no difference, which was the mystery, until the cause turned out to be one level down. A tail-recursive style only stays flat if the compiler turns the tail call into a jump rather than a call that pushes a frame. WebAssembly has an instruction for exactly this, a guaranteed tail call, and the reference code generator emitted it. The self-hosted code generator — the one written in Mere, the one that had just compiled itself — did not. It lowered every call the same way, as an ordinary call that pushes a frame and waits for a return. So tail-recursive Mere, compiled by the self-hosted compiler, piled up frames anyway, and any recursion whose depth grew with the size of its input — walking a long list of tokens, say — would climb until the stack ran out. The source was disciplined; the target was stack-based; and the compiler in between refused to bridge them.
That refusal was invisible for as long as the compiler was only ever emitted and never run as a compiler. Structural self-hosting had been a real achievement and a partial one, a summit that turned out to have a taller peak behind it. The behavioural fixpoint — the compiled compiler actually working — waited on a single missing instruction, and the only reason the gap could finally be seen was that the thing had, at last, been made to run. The next part is about teaching it the instruction it had never learned to emit.