Keeping Them Identical at Scale

By now there are four implementations of the language — the interpreter and three code generators — and the rule is that all four produce byte-identical output. It is easy to hold that line on a ten-line demo. This episode is about holding it on a program that isn’t small: a SQL-ish engine, over a thousand lines, with dozens of its own self-tests. That is where parity stops being a slogan and starts finding bugs, because a large program exercises the language in ways no small one does.

Small programs prove features; large ones prove composition

A short example tends to exercise one feature at a time — here is a match, here is a closure, here is a record. It confirms the feature exists and lowers correctly in isolation. What it can’t confirm is what happens when features meet: a closure that captures a variable that was rebound, inside a region, holding a collection that outlives the region, printed by a show that recurses through a variant. Real code lives in those combinations, and so do the bugs. Compiling a thousand-line program on four backends and demanding identical bytes is a way of testing the combinations automatically — and the ones that broke are worth seeing, because each is a place where two implementations of “the same meaning” quietly drifted apart.

Three ways the same meaning drifted

One bug was in how the C backend handled rebinding a name to a value computed from itself — let x = f x. The obvious translation put x on both sides of a C initializer, which C forbids (a variable may not appear in its own initializer), so clang rejected it. The interpreter had no such rule and evaluated it fine. The fix was to compile the binding in two steps through a temporary, so the old x is still visible while the new one is computed. Nothing about this shows up in a demo that never shadows a name; it shows up the moment real code writes the ordinary let x = step(x) pattern.

Another was subtler and lived in the Wasm backend’s memory model. A region reclaims its memory by rewinding a bump pointer — but if a program allocates a collection inside a region and lets it escape to outlive the region, rewinding the pointer frees memory the escaped value still points into, and the next allocation overwrites it. The other backends managed escaping collections separately and didn’t hit this; Wasm alone shared the region allocator with the escaped value. The fix aligned Wasm’s region semantics with the others. This is precisely a bug that cannot appear without a program structured richly enough to allocate-in-a-region and escape — which is to say, without something realistic.

A third was in string equality: a string built at runtime compared against a string baked into the program’s data was being compared by pointer rather than by contents, so two equal strings of different origins silently tested unequal. A demo that only compares string literals never triggers it; a parser that compares runtime tokens against expected keywords triggers it constantly.

None of these is a dramatic failure. They are quiet disagreements — the kind that produce plausible output that happens to be wrong on one backend — and the only reason they were caught is that the outputs were compared byte for byte against the interpreter. Inspection would have sailed past all three.

When the fix is to the reference

Not every divergence is a compiler bug to be squashed on the codegen side. One was about the order a map iterates its entries. The backends didn’t agree, which under a strict byte-identical rule is a failure even though every backend’s answer was arguably correct — a map has no inherent order. The resolution was to fix the order in the interpreter, making it iterate in insertion order, so that there is one defined answer and all four backends match it.

That is worth dwelling on, because it shows what the reference is for. The interpreter isn’t sacred; it is the agreed-upon definition, and when the definition is underspecified — as “iteration order of a map” genuinely is — the right move can be to pin it down there, in the one place everything else is measured against, rather than to argue four backends into coincidentally agreeing. And the bar stays strict on purpose: a merely cosmetic difference, like ordering, is still a difference, and tolerating “close enough” would reopen the exact door the parity rule exists to close — letting which backend you used quietly change what you see.

What it costs to keep

Holding four implementations identical is not a one-time achievement; it is a standing cost. The realistic programs become a regression corpus: more than a dozen of them, the largest over a thousand lines, run on every backend and diffed, every time. A divergence introduced by a later change is caught the next time the corpus runs, not discovered by a user. And the discipline from the coverage ledger holds — a new feature isn’t done until it lands on all backends and the corpus still comes out identical. The price of “the backend is not a semantic variable” is paid continuously, in a test suite of real programs and a refusal to let any of them drift.

The payoff is concrete enough to state as a fact rather than a hope: a language implementation where a thousand-line program, run four different ways — walked by the interpreter, compiled through C, compiled through LLVM, compiled to WebAssembly — prints the identical bytes. That is the whole discipline cashed out on something real.

Three of the four backends have now been through the same feature ladder and held to the same output. The fourth has been present in every comparison but not yet looked at directly, and it is the one with the most unusual constraints — a sandboxed target with linear memory and no native notion of a function pointer. Next: the WebAssembly backend, and what it takes to compile a language to a machine that runs inside a web page.