Compiled, interpreted, or both?

A processor is astonishingly literal. It fetches a few bytes from memory, decodes them as one instruction (“add these two registers”, “jump if zero”), executes it and fetches the next. That is all it will ever do. A line such as coin lives = 3 means nothing to it: somebody has to turn the text into those bytes, or into actions equivalent to them.

There are two classic ways to do it, and a conference gives a good picture of both. A translator takes the speaker's written text the night before and hands the audience a printed copy in their own language: slow to prepare, but then anyone can read it at full speed, as many times as they like. An interpreter sits next to the speaker and renders each sentence as it is spoken: nothing to prepare, but every sentence costs effort every time, and if the speaker contradicts themselves the interpreter only notices when they get there.

§Two ways to run a program

The difference is when the work happens. The compiler does its analysis once, before the program runs, and the result can be run many times; the interpreter does a little analysis every time a piece of the program is executed. Compilers can afford to think hard (to check types, to optimise) because their cost is paid only once. Interpreters start immediately, can run code typed a second ago, and see the actual values the program is working with.

The first high-level language implementations were interpreters. John Mauchly's Short Code (1949) let UNIVAC programmers write formulas instead of machine instructions, and was interpreted at roughly fifty times the cost of hand-written code. Programmers were not willing to pay that price, and for a decade the received wisdom was that automatic programming would always be slow. Grace Hopper's A-0 system (1952) started calling the translating approach a “compiler”, and in 1957 John Backus's team at IBM delivered FORTRAN, whose compiler produced code nearly as good as an expert's. That result, more than any argument, is what made high-level languages acceptable.

§It's the implementation, not the language

Even the most common implementations are rarely pure. CPython, the standard Python, compiles your file to bytecode before running a single line of it, and then interprets the bytecode. Java is compiled twice: once to bytecode on the programmer's machine, and again, to machine code, inside the virtual machine while the program runs. Real systems sit somewhere on a spectrum.

§The spectrum

Tree-walking interpreters

The most direct design: parse the program into a syntax tree (chapters 01 and 02) and evaluate it by walking the tree. To compute a + b * 2, visit the + node, which asks its children for their values, and so on down. John McCarthy described Lisp in 1960 through a function eval that does exactly this, and Steve Russell surprised him by implementing it, giving the world its first Lisp interpreter. Shells such as Bash still work this way, and so did Ruby until version 1.8. It is simple and flexible, but slow: every node visited costs pointer chasing and a decision about what kind of node it is.

Bytecode and virtual machines

The next step is to compile the tree into a flat list of simple instructions for an imaginary machine, the bytecode, and interpret that instead. A loop reads one instruction, jumps to the code that handles it, and repeats. Bytecode is compact, cache-friendly and easy to dispatch, which makes this design several times faster than walking a tree. Pascal's p-code (1970s) made the idea famous; today it powers CPython, Ruby, Lua, PHP, the JVM, .NET and Erlang's BEAM. Some virtual machines are stack machines (operands live on a stack, as in the JVM, CPython and WebAssembly) and others are register machines (instructions name their operands, as in Lua 5 and Android's Dalvik).

Just-in-time compilers

A JIT compiles to machine code while the program runs. It starts by interpreting, counts which functions are hot, and compiles those, using information no ahead-of-time compiler can have: the types that actually showed up, which branches are taken, which objects have which shape. If a guess turns out wrong (a function that always received integers suddenly gets a string), the JIT throws the compiled code away and falls back to the interpreter: deoptimisation. The techniques come from Smalltalk and, above all, from the Self project of the late 1980s and early 1990s; the same people went on to build Java's HotSpot (1999) and, with Lars Bak, Google's V8 (2008), which made JavaScript fast enough to run whole applications.

Ahead-of-time compilers

Translate everything before running: C, C++, Rust, Go, Swift, Haskell, Fortran. Start-up is instant and performance predictable, no compiler sits in memory while the program runs, and many mistakes are caught before anyone runs anything. The price is that the compiler must guess what the program will do, and the executable runs only on the processor and operating system it was built for.

Transpilers

A transpiler (source-to-source compiler) translates into another high-level language rather than into machine code: TypeScript and Elm to JavaScript, early C++ (Cfront) to C, Nim to C. It reuses everything the target language already has, from its optimisers to its debuggers.

§A dozen languages side by side

The same story as a table. “Becomes machine code” says when the processor-specific code appears for the most common implementation; there are alternatives for nearly every row.

§Why not always compile?

Because every choice trades one thing for another:

• Start-up versus peak speed. An interpreter starts at once; a JIT needs a warm-up before it reaches full speed; an ahead-of-time binary is fast from the first instruction. For a command-line tool that runs for 20 milliseconds, start-up is everything. For a server that runs for months, peak speed is.
• What is known when. An AOT compiler must handle every input the program could receive. A JIT sees the inputs it actually receives and can specialise for them, which is why JavaScript, a language where a + b might be an addition, a string concatenation or a call to a user's method, can still run quickly.
• Portability. Bytecode runs wherever its virtual machine runs: “write once, run anywhere” was Java's slogan. A native executable must be rebuilt for each platform.
• When errors appear. A compiler with a type checker refuses a program with a type error before it runs. A dynamically typed interpreter discovers it on the line where it happens, maybe in production, maybe never.
• Interactivity. Interpreters make REPLs, notebooks and live coding natural, because there is no separate build step.

§The JIT's bet

Consider a JavaScript function function add(a, b) { return a + b; }. Ahead of time, nothing can be assumed about a and b. V8's interpreter, Ignition, runs it a few hundred times and records that both arguments were always small integers. The optimising compiler then emits a few machine instructions: check that both are small integers, add them, check for overflow, return. If a check ever fails, execution jumps back to the interpreter and the optimised code is discarded. The bet usually pays off because real programs are far more regular than their languages allow them to be.

§Compilers that compile themselves

A compiler is just a program, so it can be written in the language it compiles. The first time is a chicken-and-egg problem solved by bootstrapping: write a first, simple compiler in another language, use it to compile a better compiler written in the new language, and from then on the language compiles itself. The Lisp 1.5 compiler of 1962 was written in Lisp; Rust's first compiler was written in OCaml until it could compile itself in 2011; Go's compiler moved from C to Go in 2015. In his 1984 Turing Award lecture, Reflections on Trusting Trust, Ken Thompson showed the unsettling side of this: a compiler can be taught to insert a back door into every program it compiles, including future versions of itself, leaving no trace in any source code.

§Where Wahoo sits

Wahoo is compiled ahead of time, but not to machine code: its target is WebAssembly, a portable bytecode designed to be compiled once more, quickly and safely, by the browser. So a Wahoo program goes through two compilers: .wahoo → .wasm by our compiler, then .wasm → machine code by your browser's engine (chapter 06). And in the playground the first compiler is itself a WebAssembly module, Rust compiled to Wasm. The next chapters open it up, one phase at a time, starting with the humblest: reading the characters.

§References

1. G. M. Hopper (1952). “The Education of a Computer”. Proceedings of the ACM National Meeting.
2. J. W. Backus et al. (1957). “The FORTRAN Automatic Coding System”. Proceedings of the Western Joint Computer Conference.
3. J. McCarthy (1960). “Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I”. Communications of the ACM, 3(4).
4. Y. Futamura (1971). “Partial Evaluation of Computation Process — An Approach to a Compiler-Compiler”. Systems, Computers, Controls, 2(5).
5. K. Thompson (1984). “Reflections on Trusting Trust”. Communications of the ACM, 27(8).
6. U. Hölzle (1994). Adaptive Optimization for Self: Reconciling High Performance with Exploratory Programming. PhD thesis, Stanford University.
7. J. Aycock (2003). “A Brief History of Just-In-Time”. ACM Computing Surveys, 35(2).
8. R. Nystrom (2021). Crafting Interpreters. Genever Benning.