The Formatter, and Self-Host Parsing Self-Host

The previous episode built the front end — a lexer and parser in Mere, producing a shared syntax tree — and noted that the pretty-printer had come first and defined that tree. This episode is about the pretty-printer itself: why it was the right component to self-host first, and the two-layered check that turns “it seems to work” into “it is verified against the original and against itself.”

Why the formatter went first

Self-hosting a compiler is a large job, and the order of components is a real decision. The formatter — the tool that takes a syntax tree and renders it back to clean source text — was chosen as the first piece, and the reasons are all about verifiability.

It is pure: a function from a syntax tree to a string, with no input, no output, no state. Nothing to mock, nothing to sequence — just a value in and a value out. It is expressible with what the language already had: recursion, pattern matching over variants, and string building, all of which Mere could do. And most importantly, it is easy to check, because its output is a string and there is already an OCaml formatter producing the reference string. Compare with the alternatives: the parser is large, the type checker needs unification, the evaluator and code generators are heavy with state and span four backends. The formatter is the one component that is both a genuine piece of a real compiler and small and pure enough to verify exactly. Starting self-hosting with the most-verifiable component is the language’s own first principle — optimize for what you can be sure of — applied to the bootstrapping plan itself.

The work was a faithful translation of the OCaml formatter: the same precedence-driven insertion of parentheses across a dozen levels, the same line breaks and indentation for block forms, the same restoration of syntactic sugar (ranges, cons lists, lambda shorthand), the same layout for infix operators and record literals and match arms. OCaml’s Buffer became Mere’s string builder, its List.map became the prelude’s, and because a formatter never raises, there were no exceptions to port. The result was around five hundred lines of Mere doing what six hundred lines of OCaml did.

Check one: faithful to the reference

The first verification is the parity rule, unchanged from the backends: the Mere formatter’s output must equal the OCaml formatter’s output, byte for byte, over the whole test corpus. The OCaml formatter is the reference definition of “how Mere code should look,” and the self-hosted one is obligated to reproduce it exactly — not equivalent formatting, not close, the same bytes. Run across the full suite, the two agree, which means the port didn’t just compile and run — it reproduced the original’s behavior down to the last space. This proves the translation is faithful: the Mere formatter is the OCaml formatter, rewritten, not merely a similar tool.

Check two: the round-trip, which needs no reference

The second check is more interesting, because it validates the front end against itself and needs no OCaml reference at all. Once the parser and formatter both exist, they compose into a loop: take source text, parse it to a tree, format the tree back to source. A correct formatter is idempotent — formatting already-formatted code changes nothing — so running the loop twice should reach a fixed point: parse, format, parse the result, format again, and the output must be identical to the first format. If it isn’t, the parser and formatter disagree about the tree — the parser built a structure the formatter renders differently than the source implied — and the round-trip catches it with no external oracle, because the two components check each other. This is the same idea as the four backends validating each other in Part IV, now between the two halves of the front end.

Self-host parses self-host

The sharpest form of that check is to point the front end at the most demanding input available: its own source code. The self-hosted parser parses fmt.mere and the parser’s own source; the self-hosted formatter formats them; the round-trip must hold. This is the milestone where self-hosting and dogfooding fuse into one act — the front end is itself a substantial Mere program, so running the front end on the front end is simultaneously the most realistic test it could face and a literal instance of the tool processing the tool. When the self-hosted front end parses and reformats its own source and reaches a fixed point, the claim “Mere can process Mere” stops being aspirational for this layer and becomes a thing that demonstrably happened.

And the harness that does all this is not a one-time check; it is permanent infrastructure. Cross-validation against the OCaml reference, and the round-trip against itself, become a standing test the whole rest of the self-host effort runs against. Every component built after this — the evaluator, the type checker, the code generator — inherits the same discipline: written in Mere, cross-validated against its OCaml twin, and required to agree. The formatter didn’t just port one tool; it established how every later tool would be trusted.

The front end can now read Mere and write it back, verified two ways. What it cannot yet do is run it — take a parsed tree and compute its result. That is the evaluator, and writing it in Mere produces a particular curiosity: an interpreter for Mere, written in Mere, capable of interpreting itself. Next: the meta-circular evaluator.