10 — Proving it

A compiler is a program whose output is another program. That makes it unusually hard to test, because “did it work?” is not a question about the compiler’s own behaviour — it is a question about the behaviour of something the compiler produced.

This chapter is about the answer these two compilers use, which is available to anyone and is worth more than most of what gets called testing.

The problem with testing a compiler

Suppose you change the register allocator and want to know whether you broke anything. What do you check?

You cannot check that the assembly is correct, because “correct” for assembly is a semantic property, not a textual one. You cannot check it against the previous assembly, because you changed the allocator — the output is meant to differ. You cannot check only that the program still runs, because a miscompiled program usually still runs; it just produces a different answer, sometimes only for inputs you did not try.

The trap is that a compiler’s bugs are overwhelmingly silent. It does not crash; it emits plausible code that computes the wrong thing.

The answer: a second implementation

The compilers in this series have two back ends that share a front end. That is not only a design nicety — it is a test instrument:

                          ┌──→  pcode ──→ interpret ──→ output A
   one parse, one AST-free walk
                          └──→ spectra ──→ Dragon ──→ link ──→ run ──→ output B

If A ≠ B, something is wrong, and you know a great deal about what: the front end is shared, so a divergence is in one of the back ends, and the p-code one is 450 lines of obvious code while the other is a production optimizer.

This is differential testing, and its power comes from the two implementations being independent in the way that matters — one interprets an idealized machine, one drives an optimizing native compiler — while consuming identical input.

Why the slow one earns its keep

The natural instinct, once the native road works, is to delete the interpreter. It is slower, it is not the product, and it duplicates functionality.

Keep it. What it gives you is an oracle: an implementation simple enough to audit by eye, whose answers you are willing to call definitional. Every claim about the fast road becomes checkable.

The properties that make the interpreter a good oracle are worth naming, because they are properties you can deliberately build into a reference implementation:

• It is small. 450 lines, no optimization, no cleverness. You can read it and believe it.
• It is total. It has no undefined behaviour — recall the explicit wrap_multiply in chapter 8. A reference with undefined behaviour cannot settle a disagreement.
• It fails loudly. Stack overflow is a sentence, not a crash.
• It observes everything. Every store prints, so a divergence is caught at the first differing value rather than at the end.

That last property is PL/0’s accident of design, and it is worth stealing on purpose. A reference implementation should be maximally observable, even where the real one is not.

The twins check each other too

There is a second axis. The whole compiler exists twice — once in C23, once in Mica — and the two are held to byte equality:

So a change to the shared idea of the compiler has to survive being expressed twice, in two languages, by two type systems — and the artifacts have to match exactly.

You can run the comparison yourself:

diff <(../build/c/pl0 run ../testdata/gcd.pl0) \
     <(echo "run ../testdata/gcd.pl0" | ../build/Pl0/Pl0)

Silence is the answer you want.

There is exactly one place they legitimately differ, and it is instructive: the C twin’s diagnostic table has one row the Mica twin does not — an identifier longer than the compiler’s fixed buffer. Mica’s strings are dynamic, so the error cannot occur. When two implementations differ, the difference is either a bug or a fact about the languages. Being forced to classify it is itself valuable.

The self-checking error table

Correct programs are the easy half. Both twins carry a table of incorrect programs, each provoking exactly one diagnostic:

../build/c/pl0 diagnostics | tail -3

code 9 a program without its period: ok
recovery: 5 diagnostics
diagnostics: 25 of 25

Twenty-five cases, each the smallest program that provokes its error, each carrying the number Wirth gave it. The table is run through the compiler’s own parser, in the same process — which is only possible because the parser’s state is a struct rather than a pile of globals (chapter 6).

And one case is not a single error at all:

recovery: 5 diagnostics

That is the six-line program with five mistakes from chapter 6. The check is not what the messages say — it is that there are five. A recovery bug shows up as a count, and nothing else catches it: every individual message is still correct when a parser starts cascading.

Test the count, not just the content. It is the cheapest possible guard on error recovery.

What “byte-identical” is actually worth

It is worth being precise about what these comparisons do and do not establish.

They do establish that a change did not alter behaviour on the covered programs — which for a compiler is most of what you want, because most regressions are behaviour changes nobody intended.

They do not establish correctness. Six programs is six programs. A bug that only appears with four levels of nesting, or with a constant at the boundary of the address field, is not covered by any of them, and no amount of byte-equality on the six will find it.

What differential testing buys is a very cheap, very sensitive alarm on the behaviour you have exercised. What it costs is the discipline of keeping a second implementation alive. For a compiler — where bugs are silent and consequences are downstream — that is one of the best trades available.

Two directions to take it further, both standard practice:

• Generate the programs. A random PL/0 program generator, run through both roads, comparing output, will find divergences a hand-written corpus never reaches. This is how production compilers are fuzzed.
• Cover the optimizer’s regimes. The twins’ native road is checked at three optimization levels and on two architectures, because a miscompile that only appears at full optimization is exactly the kind that ships.

What this is like in a real compiler

Every part of this chapter scales up, and the Mica compiler this series comes from does all of it:

The technique does not change with scale. Only the number of things being compared does.

The habit worth taking

If you write a compiler, an interpreter, a serializer, a query planner — anything whose output is hard to eyeball — build the slow obvious version first, keep it, and make the fast version answer to it.

It will feel like carrying dead weight right up to the first time it catches something. Then it will feel like the only reason you found the bug at all.

Next: 11 — Exercises, where you change the language yourself.