Why Build an Interpreter?

A program, before anything runs it, is text. A file of characters that means nothing to the machine and — strictly speaking — nothing at all until something decides what it means. The field of programming languages focuses on that gap: between a string somebody typed and a behaviour they intended. Broadly speaking, there are two extremes for how that gap is closed: interpretation and compilation. Interpretation directly evaluates the program as written; compilation rewrites it into a different language (e.g., assembly or machine code) and runs that instead.

The shape of a language implementation

Nearly every language implementation, of every kind, begins the same way. The text is broken into tokens, and the tokens are assembled into a tree that reflects the program’s structure — an abstract syntax tree, or AST:

  source text
      │
      │   lexing — characters into tokens
      ▼
    tokens
      │
      │   parsing — tokens into structure
      ▼
     AST   ◄─── this book starts here
      │
      ├────────────►  evaluate it directly           (interpretation)
      │
      └────────────►  translate it into another      (compilation)
                      language, then run that

Everything above the AST is a translation problem: recovering structure from text. It is a well-understood and genuinely interesting body of work, and it is where a compilers course begins. This book starts at the AST and works down from there — on what the program means, and how to make a machine carry that meaning out.

Interpretation and compilation

A compiler turns your program into another program. The output might be machine code for a particular processor, bytecode for an abstract machine, or another high-level language entirely. The defining move is translation, and the compiler’s work is finished before your program ever runs. Its central concerns follow from that: which instruction sequences are efficient, how to allocate registers, which optimizations are safe.

An interpreter does not translate. It walks the program and carries out what the program says, directly. Ask it to evaluate 1 + 2 and it evaluates 1, evaluates 2, and adds them. Its central concern is not what instructions to emit but what each construct means.

That difference is why this book builds an interpreter. When you write the case that handles addition, you are not describing addition to a machine that will handle it later — you are writing down what addition is, in a form that runs. Specification and implementation become the same artifact. We will make this explicit in Program semantics, where the rule

$$\frac{e_1\Downarrow v_1{e}_2\Downarrow v_2}{e_1+e_2\Downarrow v_1+v_2}(\text{E-Add})$$

and the code implementing it turn out to be the same statement written twice.

It is worth being precise about what interpretation means, because it is broader than simply running a program. To interpret a piece of syntax is to map it to a mathematical object — its meaning. Which object depends on what you are interpreting it as. The expression 1 + 2 might mean the number 3. A function definition might mean an actual mathematical function, from arguments to results. A whole program might mean a map from inputs to outputs, or a set of possible behaviours. The evaluator you build in this book is the concrete case: the object is the value the expression produces when it runs.

But the domain is a choice, and coarser choices are useful. Interpret 1 + 2 as positive rather than as 3, and you have a program that reasons about signs without computing anything. Interpret it as Int, and you have a type checker. This is abstract interpretation — the same syntax-to-meaning mapping, aimed at a domain that deliberately forgets some detail so that questions can be answered without running the program. It is how a great deal of static analysis works, and it is exactly what the type checker in Part VI does: interpret every expression as a type rather than as a value, and reject the program if the types do not fit. The evaluator and the type checker are two interpretations of the same syntax, over different domains.

This is not a modern observation. When John McCarthy published the definition of Lisp in 1960, it included a function called eval — a Lisp program describing how to evaluate Lisp programs. He intended it as a theoretical device, written to show that Lisp was tidier than a universal Turing machine; by his own account the notation behind it was devised “with no thought that it would be used to express LISP programs in practice.” Then S. R. Russell noticed that eval could serve as an interpreter, hand-coded it, and Lisp had an interpreter nobody had set out to write. The definition was the implementation. This book leans on that same fact throughout.

A spectrum of implementations

The two branches above are a useful simplification, and like most useful simplifications it is false at the edges. Real implementations mix strategies freely:

• A tree-walking interpreter evaluates the AST directly, node by node. The simplest design, the easiest to read, the slowest to run, and the subject of this book.
• A bytecode interpreter first compiles the AST into a compact instruction set for an abstract machine, then interprets those instructions. CPython works this way: your source is compiled to bytecode, and a virtual machine executes it.
• A just-in-time compiler begins by interpreting, watches which code runs hot, and compiles those parts to native code while the program is still running. The JVM and JavaScript engines such as V8 both do this, with an interpreter and one or more optimizing compilers cooperating at run time.
• An ahead-of-time compiler translates the whole program to native code before it runs and ships the result. This is what gcc, clang, and rustc do.

So “is Java compiled or interpreted?” has no clean answer. javac compiles source to bytecode, a virtual machine interprets that bytecode, and a JIT compiler translates the frequently executed parts to machine code during execution — all three in one system. The honest description is that implementations sit somewhere on a spectrum from decide everything before running to decide everything while running, and the interesting ones occupy several points at once.

The tree-walking end of that spectrum is where meaning is most visible, because nothing has been translated away yet. Moving along the spectrum gains speed by moving toward the machine: bytecode and native code run fast because they are closer to what the hardware already knows how to do. That translation discards the program’s original structure and intent: a loop becomes a jump, a function becomes an address, a type vanishes once it has been checked. Those high-level structures — and what they were meant to express — are precisely this book’s subject. So we work at the end of the spectrum where they are still intact.

What you will build

Over the following parts you will build a tree-walking interpreter for Bridger, a language that starts out able to add two numbers and ends up with closures, a static type checker, algebraic data types, objects, and a relational sublanguage.

The interpreter will be slow — meaningfully slower than any production implementation, because walking a tree re-examines the program’s structure at every step. It will also be legible: small enough to read straight through and hold in your head, with every language feature and programming language concept corresponding to a piece of code you can point at.

Performance returns in Cost semantics, where we measure programs by counting evaluation steps rather than seconds — a measure that says something about your algorithm that a stopwatch obscures.

Further reading

Lisp, and the interpreter nobody set out to write: John McCarthy’s “Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I” (1960) defines Lisp, eval included. His “History of Lisp”, a 1979 Stanford Artificial Intelligence Laboratory draft, is his own account of the period, including the moment itself: “S.R. Russell noticed that eval could serve as an interpreter for LISP, promptly hand coded it, and we now had a programming language with an interpreter.”

Abstract interpretation: Patrick Cousot and Radhia Cousot’s “Abstract Interpretation: A Unified Lattice Model for Static Analysis of Programs by Construction or Approximation of Fixpoints” (1977) is the paper that made abstract interpretation a theory rather than a collection of tricks. It sets up the lattices, the abstraction and concretization maps, and the fixpoint construction that the sign and type examples above only sketch. The argument is carried almost entirely in the algebra, and it assumes you are comfortable with partial orders and least fixpoints. Xavier Rival and Kwangkeun Yi’s Introduction to Static Analysis: An Abstract Interpretation Perspective (MIT Press, 2020) covers the same ground at book length, starting from example analyses.

The compiling end of the spectrum: Aho, Lam, Sethi, and Ullman’s Compilers: Principles, Techniques, and Tools, 2nd ed. (2006) — the “Dragon Book” — works through the pipeline this book starts in the middle of: lexing, parsing, semantic analysis, intermediate representations, optimization, and code generation. John Aycock’s “A Brief History of Just-In-Time” (2003) traces how interpretation and compilation stopped being alternatives and began cooperating inside a single system, from Smalltalk-80 onward. For the current shape of a production pipeline, V8’s own accounts of Ignition and TurboFan and of the later Sparkplug baseline compiler describe a JIT with several tiers.

Building one yourself: Robert Nystrom’s Crafting Interpreters (2021) builds the same language twice, once as a tree-walker and once as a bytecode virtual machine — the same program at two points on the spectrum described above.

Concept checks