Pranav Desai begins with an assignment to evaluate 1 + 1 + 1 as a binary tree. Following each design consequence turns that small evaluator into graphLang, a functional-leaning Lisp interpreter written in C.
The runtime grows one observed failure at a time:
- Treat operators as functions so the evaluator only needs to understand application
- Store variables and functions in one environment as named node values
- Represent user-defined functions as closures in the graph rather than opaque C pointers
- Replace many small allocations with an arena
- Chain arena chunks instead of using
realloc, which could move the block and invalidate every node pointer - Add mark-and-sweep collection when recursive evaluation leaves enormous numbers of unreachable nodes behind
The memory result is stark: the author’s naive fib(40) run exceeded 12 GB and died, while the collector held it to roughly 1.7 MB. But it still took about six minutes—the collector fixed retention, not exponential computation.
That distinction is the best part of the piece. The interpreter’s architecture is not decoration added in advance; allocation, pointer stability, reachability, and algorithmic cost each force a different mechanism, and solving one constraint exposes the next.