A Scheme in Mere

Writing a small interpreter for another language is one of the oldest ways to find out what your own language is made of. It exercises recursion, pattern matching, and environments all at once, and it asks two questions Mere’s probes had so far avoided: can a recursive polymorphic variant serve as both the abstract syntax tree and the runtime value, and can a value carry a captured environment so that closures work? A Scheme is the natural subject — its code is already data — so I wrote one: a reader that parses s-expressions, a tree-walking evaluator, and a printer, around two hundred and sixty lines.

One variant for code, data, and value

The whole interpreter turns on a single recursive variant. An s-expression is nil, an integer, a boolean, a symbol, a pair, a closure, or a primitive — and that one type is simultaneously the syntax the reader produces, the data a program manipulates, and the values the evaluator returns. This is the defining feature of a Lisp, and expressing it cleanly is a real test of the variant: the evaluator matches deeply nested shapes like “a pair whose head is the symbol if” to recognize special forms, and the pattern matcher handled those nested cases with the exhaustiveness checking intact. Nothing about representing a self-referential syntax-as-value type strained the language; it read the way it would in any ML.

A value that closes over its scope

The harder question was closures. When a lambda is evaluated, the result has to remember the environment it was defined in, so that a function returned from another function still sees the variables it captured. Mere had never been asked to put an environment inside a value before. The closure case of the s-expression variant holds three things — the parameter list, the body, and the captured local environment, itself just an s-expression association list — and that was enough. make-adder, a function returning a lambda that adds a captured number, and compose, which builds a new function from two, both behaved exactly as lexical scoping demands: the returned closures saw the right bindings from the frames they were born in. Global definitions went through a mutable table so that recursion works — a function is in scope by the time it calls itself — while local bindings chained through the captured alist for lexical scope.

The measurement, and the friction

Every test program produced the right answer, identically on the interpreter and the C backend: factorial of ten, mapping a square over a range, folding a sum, the closure examples, quote keeping code as data, and the short-circuiting and and or. A separate probe the same day — a line-level diff built on a two-dimensional longest-common-subsequence table with a backtrack to recover the edit script — told the same story: correct against the system diff tool, new bug count zero. This is what the maturity of the language looks like when you measure it by building things: a Scheme interpreter and a diff tool, both nontrivial, both written without the compiler having to change. The one piece of friction was not a bug in the language but a collision with it — a function named run behaved differently on the two backends, because run is also a built-in. Following that thread is the next episode, and it ends a category of bug rather than an instance.