Build a programming language

Walk the source one character at a time and emit tokens: keywords, identifiers, numbers, strings and punctuation. Two-character operators like == and <= need one character of lookahead. Identifiers are scanned first and then checked against a keyword table.

Record the line (and ideally column) on every token now. You'll want it for every error message you ever print, and it's painful to thread through later.

Write one function per precedence level: equality calls comparison, comparison calls term, term calls factor, factor calls unary, unary calls primary. Each level loops while it sees its own operators. That's recursive descent, and it handles precedence and left-associativity without any tables.

Add a printer that shows the tree in Lisp-style parentheses. It's the fastest way to see whether your parser agrees with you about what a - b - c means.

Add statements to the parser, then write an evaluate function that switches on the node type and returns a value. Variables live in an environment: a hash map from name to value, with a pointer to the enclosing environment. A block creates a new one; a lookup walks outward until it finds the name.

Decide now how values are represented. A tagged union of number, bool, nil and a pointer to a heap object carries you all the way to the VM.

A function value holds its parameter list, its body and the environment it was defined in. Calling it creates a new environment whose parent is that captured one, not the caller's. That single rule is lexical scoping, and closures fall out of it for free.

Then add a resolver pass. Without it, a closure that refers to an outer variable can end up seeing a different variable with the same name, declared later in the enclosing block. A resolver computes, at compile time, how many scopes up each variable lives, which fixes the bug and makes lookups faster.

Design a small instruction set for a stack machine: CONSTANT, ADD, GET_LOCAL, SET_GLOBAL, JUMP_IF_FALSE, CALL, RETURN. Your compiler walks the AST and appends bytes; the VM is a loop around a big switch.

Locals stop being hash map entries and become slots on the value stack, indexed by a number the compiler worked out. Forward jumps for if and while need backpatching: emit a placeholder offset, compile the body, then go back and fill it in. Write the disassembler before anything else here. You'll use it on every bug.

Closures are the hardest part of moving to a stack VM. A local lives on the stack, but a closure can outlive the function that declared it. What Lua uses, and Crafting Interpreters teaches, is the upvalue: a reference that points at the stack slot while the variable is alive, and is "closed" by copying the value to the heap when the enclosing function returns.

Keep a list of open upvalues sorted by stack slot, so two closures over the same variable share one upvalue instead of getting separate copies.

Link every heap object into one list as you allocate it. To collect, mark everything reachable from the roots (the value stack, call frames, globals, open upvalues, and anything the compiler is holding mid-compilation), then sweep the list and free what isn't marked. Trigger a collection when allocated bytes pass a threshold, then set the next threshold to a multiple of what survived.

Add a "stress GC" flag that collects on every single allocation. Missing-root bugs are rare under normal load and constant under stress. That's what you want while debugging.

Profile before touching anything. It'll probably be one of the usual suspects: global lookups hashing a string every time (intern all strings so equality is a pointer compare), a slow hash table, and branch mispredictions in the dispatch loop.

Then try the classic tricks one at a time and measure each: computed goto instead of switch where your compiler supports it, caching the instruction pointer in a local, and packing values into 64 bits with NaN boxing. Some will help a lot on your machine and some will do roughly nothing. That's its own lesson. Chapter 01 explains why.