Teaching the Compiler to Jump

The previous part ended on a diagnosis: the self-hosted code generator lowered every function call the same way, as an ordinary call that pushes a stack frame, and so tail-recursive code — the disciplined kind that is supposed to loop without growing the stack — grew the stack anyway when compiled by it. The reference generator, the one written in the host language, knew to emit a guaranteed tail call in that position. The one written in Mere did not. The whole behavioural fixpoint was waiting on a single missing instruction, and this part is about putting it in.

What “tail position” actually requires

A tail call is a call whose result is the result of the enclosing function — nothing happens after it returns, so there is no reason to keep the caller’s frame around, and the call can become a jump. Recognising one sounds like a local check, but it is not: tail position is a property that flows inward through a program’s structure. The last thing a function does might be an if, and then both of its branches are in tail position. It might be a match, and then every arm is. It might be a let whose body is the real tail. So the code generator cannot simply look at a call and decide; it has to carry, as it walks the program, a single bit of context — are we currently in tail position? — and propagate that bit correctly into the branches of every construct that can end a function, while clearing it everywhere else, because a call buried in the middle of an expression is emphatically not a tail call and must keep its frame.

The change, then, was to thread that bit through the generator. The state the generator carries as it walks gained a flag for whether the current expression is in tail position. Entering a function body sets it; the branches of an if, the arms of a match, the body of a let inherit it; an ordinary sub-expression clears it. And at the single point where a call is finally emitted, the flag decides between two instructions: the ordinary call that pushes a frame, or the guaranteed tail call that jumps. Most of the work was this patient propagation, one construct at a time, getting the bit to arrive in exactly the right places and nowhere else.

The objection that revealed something

There was one snag, and it is worth telling because of what it exposed rather than what it cost. The natural way to flip the tail-position flag was to take the generator’s state and produce a copy with that one field changed — an ordinary record update. But the type inferencer refused it, in a context where the functions of the generator all refer to one another and their types are still being worked out together. The value being updated wasn’t yet pinned to a concrete record type at that point, and updating a field of a value whose exact type is still open is precisely the kind of thing a strict inferencer cannot let pass, because it cannot yet know the update is well-formed. The fix was small — flip the flag through a little helper that applies the change as a function call rather than an inline update, which gave the inferencer the concrete type it needed. But the objection was not noise. It was the type system doing its job at the exact moment the language was being asked to compile itself, an honest reminder that the strictness which sometimes feels pedantic is the same strictness that makes the guarantees real.

Two hundred thousand frames, flat

With the instruction threaded in, the test that mattered was a recursion whose depth grows with its input — the shape that had been overflowing. A tail-recursive counter driven two hundred thousand levels deep, compiled by the self-hosted generator and run as a WebAssembly binary, now ran to completion without touching the stack limit, where before it had crashed. The tail calls had become jumps; the frames no longer piled up; the depth of the recursion no longer mattered. The overflow that had blocked the fixpoint was simply gone. The generator had learned to emit the instruction it had never known, and the resource limit that the interpreter’s generous stack had hidden was now handled at the source, in the compiled code itself.

The worse thing on the other side

And then the compiled compiler, no longer crashing from stack exhaustion, ran further than it ever had — and stopped again, differently. This time it did not overflow; it hit an explicit failure and exited, silently, on input it should have compiled. The meaning of this was not obvious at first, and it was easy to read as a regression in the tail-call work. It was the opposite. The tail calls had done exactly their job: they had flattened the recursion so thoroughly that the compiled compiler now ran all the way through its own logic for the first time — far enough to reach a defect that the overflow had always crashed before ever touching. Structural self-hosting had only ever proven the compiler could emit a valid binary; the binary had never executed its own logic end to end. Now it did, and running end to end for the first time is exactly when the bugs that live deep in a program come out to meet you.

So the single missing instruction turned out to be the easy half. It removed the wall that had stopped the compiled compiler early, and in doing so it let the compiler reach, for the first time in its existence, the parts of itself that had never actually run. What it found there was not one bug but three, and each of them was the kind that only appears when a program is compiled by itself. The next part is the hunt.