A Hitchhiker's Guide to Language Runtimes

Everything you are about to build was invented by someone, usually decades ago, usually to solve a problem that still exists. This chapter is the family tree. Read it once for orientation; come back to it when a design decision feels arbitrary, because it almost never is — someone hit the wall you are standing in front of, and wrote it down.

Nothing here is required to write code. All of it is required to have opinions.

1. The One-Paragraph History

In 1957 a compiler turned text into machine code and that was the whole story. In 1960 McCarthy's Lisp needed to run on a machine with less memory than the program wanted, so he invented garbage collection. In the 1970s UCSD Pascal shipped an interpreter for a fake machine so one compiler could target many real ones, and called its instruction set p-code. In 1983 Smalltalk-80 made that idea an entire system, with bytecode, an object memory, and — crucially — the observation that a dynamic language spends most of its time looking things up. In 1984 Deutsch and Schiffman noticed that a lookup usually finds the same answer as last time, and invented the inline cache; two years later they and others were translating bytecode to machine code at run time, which is a JIT. In 1987 Self pushed dynamic dispatch to its limit and invented maps (hidden classes), polymorphic inline caches, and deoptimization. In 1993 three people at PUC-Rio in Rio de Janeiro wanted a configuration language for engineering software and built Lua. In 1999 Sun shipped HotSpot, which is Self's ideas in an industrial JVM. In 2008 V8 brought them to JavaScript and, eventually, to everyone. In 2005 Mike Pall started LuaJIT and demonstrated that a tiny dynamic language could run within a small factor of C. In 2017 WebAssembly standardized "portable bytecode" for the fourth or fifth time, and got it right enough to stick.

Ember is a tour of that paragraph.

2. The Idea Lineage

flowchart TD
  A["Compiler to machine code (1957)"] --> B["Interpreter over a tree (Lisp, 1960)"]
  B --> C["Bytecode for a virtual machine (p-code 1970s, Smalltalk-80 1983)"]
  C --> D["Stack machines (JVM 1995, CPython, WebAssembly)"]
  C --> E["Register machines (Lua 5.0 2003, Dalvik 2008, V8 Ignition 2016, SQLite VDBE)"]
  D --> F["Inline caches (Deutsch and Schiffman 1984)"]
  E --> F
  F --> G["Polymorphic inline caches + maps (Self, 1987-1991)"]
  G --> H["Method JIT with deoptimization (HotSpot 1999, V8 2008)"]
  G --> I["Trace JIT (HotpathVM 2006, LuaJIT 2, TraceMonkey)"]
  H --> J["Tiered compilation (HotSpot C1/C2, V8 Sparkplug/Maglev/TurboFan)"]
  I --> J
  B --> K["Mark and sweep GC (McCarthy 1960)"]
  K --> L["Copying / Cheney 1970"]
  L --> M["Generational (Ungar 1984)"]
  K --> N["Tri-color incremental (Dijkstra et al. 1978)"]
  M --> O["Modern collectors: Go, JVM G1/ZGC, V8 Orinoco, Lua 5.4 generational"]
  N --> O

Ember implements, by hand, the boxes on the left and centre: tree interpreter, bytecode, stack machine, mark-and-sweep, inline caches, and a taste of a method JIT. Everything else it explains and points you at.

3. Lua: Why Imitate This Particular Language

Lua was created in 1993 at Tecgraf, PUC-Rio, by Roberto Ierusalimschy, Luiz Henrique de Figueiredo, and Waldemar Celes. Brazil had import restrictions on software through the 1980s, which pushed Tecgraf to build its own tools; Lua grew out of two small configuration languages for petroleum engineering applications. That origin explains almost everything about it:

That last point is the one worth internalizing. Lua is the most-embedded language in existence — games (World of Warcraft, Roblox, Garry's Mod), network devices, Redis, nginx via OpenResty, Neovim, Adobe Lightroom, and countless internal tools — because it is designed to be a guest. Python and JavaScript are designed to be hosts. That difference shows up in every API decision, and Ember copies Lua's side of it.

What Lua's implementation is famous for, technically:

1. A register-based VM (since Lua 5.0, 2003) — one of the first mainstream ones. The paper is The Implementation of Lua 5.0 (Ierusalimschy, de Figueiredo, Celes), and it is short, readable, and worth an hour of your life.
2. The hybrid table — every table has an array part and a hash part, and Lua picks the split automatically on rehash so that t[1], t[2], t[3] costs an array index and t.name costs a hash lookup, in the same object.
3. Brent's-variation chained scatter hashing — collisions live inside the node array rather than in separate allocations, so a table is one or two allocations, not one per entry.
4. Upvalues with open/closed states — the mechanism this curriculum's Section 4 spends a whole lab on, and the cleanest solution to "a closure captured a local that lived on the stack."
5. An incremental mark-and-sweep collector (5.1+), with a generational mode added in 5.4.
6. The integer/float split (5.4) — 3 and 3.0 are different subtypes of number, with defined coercion rules. Ember copies this because policy engines need exact integers.

Where to actually read it:

git clone https://github.com/lua/lua && cd lua
rg -n 'luaV_execute'        lvm.c        # the interpreter loop — the heart
rg -n 'luaD_precall|luaD_poscall' ldo.c  # calling convention
rg -n 'luaH_getint|mainposition'  ltable.c  # the hybrid table
rg -n 'luaF_findupval|luaF_close' lfunc.c   # upvalues
rg -n 'propagatemark|sweeplist'   lgc.c     # the collector
rg -n 'luaK_code|luaK_exp2reg'    lcode.c   # code generation
wc -l *.c *.h | tail -1                     # see how small the whole thing is

Tip: Read lobject.h first. In one header you get the value representation, the string object, the table, the closure, and the upvalue. It is the densest 700 lines in the codebase and it makes everything else legible.

4. The Great Divide: Stack Machines vs. Register Machines

This is the first real design decision you will make, in Section 3, and it splits the world.

     a = b + c

STACK MACHINE                        REGISTER MACHINE
(JVM, CPython, WebAssembly,          (Lua 5.0+, Dalvik, V8 Ignition,
 Ember's default)                     SQLite VDBE, BEAM)

  GET_LOCAL  1     ; push b            ADD  0, 1, 2      ; R0 = R1 + R2
  GET_LOCAL  2     ; push c
  ADD              ; pop 2, push 1
  SET_LOCAL  0     ; pop into a

  4 instructions                       1 instruction
  operands implicit                    operands explicit
  simple compiler                      needs slot allocation
  more dispatches                      fewer dispatches, wider instructions

Ember starts as a stack machine because the compiler for one is fifty lines and the compiler for the other is a chapter, and because you cannot appreciate what registers buy until you have felt the dispatch cost. Then capstone project 1 has you port it and measure. Read docs/adr/ADR-002 — you write it in Section 3.

Warning: "Register machine" here means virtual registers — slots in a frame, not CPU registers. A register VM does not map its registers onto hardware registers; that is what a JIT does, later, and it is a completely different problem.

5. Values: How Do You Fit a Dynamic Type in a Machine Word?

Every dynamic language answers this, and the answers are a spectrum from "readable" to "unhinged."

Ember uses a Rust enum. The reasons are in ADR-004 and they are honest ones: it is 16 bytes rather than 8, and you will measure exactly what that costs in Section 7 before deciding whether to care. What you get is that match value { ... } is checked by the compiler for exhaustiveness, which eliminates an entire class of bug that NaN boxing reintroduces.

Note: NaN boxing is not a trick to reach for casually. It works because IEEE-754 defines a huge space of NaN bit patterns that no arithmetic produces, so you can smuggle a 48-bit pointer and a 3-bit tag inside one. It is elegant and it is unsafe in Rust by construction. Capstone project 2 has you implement it behind a feature flag and benchmark it. Doing it then is education; doing it now would be cargo-culting.

6. Memory: The Three Families

MANUAL              REFERENCE COUNTING          TRACING
malloc/free         Rc / PyObject refcount      mark & sweep, copying, generational
                    ┌────────────────────┐      ┌──────────────────────────────┐
                    │ immediate reclaim  │      │ collects cycles              │
                    │ predictable pauses │      │ amortized, no per-op cost    │
                    │ CANNOT COLLECT     │      │ pauses (unless incremental)  │
                    │ CYCLES             │      │ needs to find all ROOTS      │
                    └────────────────────┘      └──────────────────────────────┘

The single most important fact in this whole chapter: a scripting language with closures and tables produces cycles constantly, so reference counting alone is not an option.

local t = {}
t.self = t              -- a one-line cycle

function make_counter()
  local n = 0
  return function() n = n + 1; return n end   -- closure ⟷ upvalue ⟷ closure
end

CPython is the famous case study: it uses reference counting plus a cycle-detecting collector, because refcounting alone leaked. That combination costs it an atomic-ish increment on essentially every value operation — one of the reasons CPython's per-operation overhead is what it is, and a central topic in the GIL-removal work (PEP 703).

Ember's collector is the simplest one that is actually correct in the presence of cycles, which is the whole point. Section 4 builds it, breaks it (deliberately — the "forgot a root" bug is a lab step), fixes it, and then explains precisely what an incremental collector would change and why a write barrier becomes mandatory the moment you make marking interruptible.

Read: Jones, Hosking & Moss, The Garbage Collection Handbook (2nd ed.) is the reference. Lua's lgc.c is the readable production example. Go's runtime/mgc.go has unusually good comments for a concurrent collector.

7. Making It Fast: The Three Big Ideas

Inline caches (Deutsch & Schiffman, 1984)

article.semantic_score in a dynamic language is a hash lookup on a string key. But at any given call site, the object is almost always the same shape as it was last time. So cache the answer at the site, with a guard:

  site: article.semantic_score
  ┌──────────────────────────────────────────┐
  │ cached_shape: Table#17-layout            │  ← the guard
  │ cached_slot:  3                          │  ← the answer
  └──────────────────────────────────────────┘
  if shape(article) == cached_shape { read slot 3 }   // fast: one compare, one index
  else { full hash lookup; update the cache }         // slow: fall back

Monomorphic (one shape seen), polymorphic (a few), megamorphic (many) — the three regimes, named by the Self team, and still the vocabulary V8 uses today. Section 7 implements a monomorphic one and measures it.

Type feedback and specialization

The interpreter watches. "This ADD has received two integers 10,000 times in a row." So rewrite that instruction, in place, to ADD_INT — which checks the types cheaply and falls back if wrong. This is what CPython 3.11+ does via PEP 659 ("specializing adaptive interpreter") and it is a remarkably good return on complexity: no machine code generation at all, just self-modifying bytecode with guards.

JIT compilation, guards, and deoptimization

Once you have type feedback, you can generate machine code that assumes the feedback is right — and the assumption is what makes it fast, because now the addition really is one add instruction. The catch is the assumption might be wrong on the next call. So the compiled code contains guards, and when a guard fails the runtime must reconstruct the interpreter state — the stack, the locals, the instruction pointer — from the compiled frame and resume interpreting. That is deoptimization, invented for Self, and it is the reason a JIT is much harder than a compiler.

  interpreter → profile → hot? → IR → optimize (assuming types) → machine code
                                                     │
                                       guard fails → deoptimize → back to interpreter

Ember's JIT will not be fast. That is stated up front and it is not an apology: the objective is that you can explain the architecture of one, and the difference between a method JIT and a trace JIT, and why both need the collector's cooperation.

8. The Reading List

Ordered by when it becomes useful. Do not read them all now.

Before Section 1

• Nystrom, Crafting Interpreters — free at craftinginterpreters.com. Read Part II alongside Sections 1–2 and Part III alongside Section 3. The single best companion to this curriculum.

Before Section 3

• Ierusalimschy, de Figueiredo & Celes, The Implementation of Lua 5.0 — 12 pages, the register VM, the table, and closures. Search for it by title.
• The CPython bytecode docs (docs.python.org, the dis module) and Python/ceval.c.
• The WebAssembly spec's "Execution" chapter, for what a validated stack machine looks like.

Before Section 4

• Lua's ltable.c and lgc.c.
• Jones, Hosking & Moss, The Garbage Collection Handbook, chapters 1–3.
• Wilson, Uniprocessor Garbage Collection Techniques (1992) — the classic survey, free online.

Before Section 5

• The Lua 5.4 Reference Manual, chapter 4 (the C API). Read it as API design, not as C.
• The mlua and rlua crates — Rust bindings to real Lua. Read how they handle lifetimes; that problem is exactly the one Section 5 solves differently.
• rune, koto, and piccolo — Rust-native scripting languages. piccolo in particular has an interesting take on GC-in-Rust that is worth comparing with Ember's.

Before Section 7

• Deutsch & Schiffman, Efficient Implementation of the Smalltalk-80 System (1984) — inline caches.
• Hölzle, Chambers & Ungar, Optimizing Dynamically-Typed Object-Oriented Languages With Polymorphic Inline Caches (1991).
• Hölzle, Chambers & Ungar, Debugging Optimized Code with Dynamic Deoptimization (1992).
• Gal, Probst & Franz, HotpathVM (2006) — trace compilation.
• PEP 659, Specializing Adaptive Interpreter.
• The Cranelift documentation in the wasmtime repository, and cranelift-frontend's examples.

Anytime, for architecture taste

• SQLite's src/vdbe.c and the "Virtual Database Engine" documentation. It is a bytecode VM inside the most-deployed database on earth, written to be auditable, and it will change how you think about the size of a "real" system.

Things to Notice

• Every idea here was invented to solve a measured problem. Inline caches came from measuring Smalltalk send sites. Generational GC came from measuring object lifetimes. If you find yourself adding a mechanism without a measurement, you are doing archaeology, not engineering.
• The stack/register question is a compiler-complexity-vs-dispatch-cost trade, and both answers ship in production systems used by billions of people. There is no correct answer, only a stated one.
• Reference counting is not a simpler garbage collector; it is a different one with a hole in it. The hole is cycles, and scripting languages fall into it immediately.
• Deoptimization is the price of speculation. Every fast dynamic runtime speculates. Therefore every fast dynamic runtime can be wrong, and must have a way back.
• Lua's smallness is a feature that required saying no thousands of times. Notice what it does not have.

Validation / Self-check

1. Why can't reference counting collect t.self = t? Draw the counts.
2. Give the four value representations and name a production runtime that uses each.
3. Compile a = b + c for a stack machine and a register machine. Which needs more dispatches, and which needs more decode work per dispatch?
4. What is an inline cache guarding against? What happens when the guard fails?
5. What is deoptimization, why does a JIT need it, and which system introduced it?
6. Name three things Lua's implementation is technically famous for, and where in its source to find each.
7. Why did WebAssembly choose a stack machine when Lua and Dalvik chose registers?

Next: The Warm-Up: An Evening With Lua.