A playful systems write-up: starting from evaluating 1+1 as a binary tree, the author builds a graph-reduction language in C with closures, a chunk allocator, and a garbage collector that cuts fib(40) from 12GB to 1.7MB.
Needed 1+1, Built a Functional Programming Language
September 16, 2026 • 13 min read
I was given a data structures problem of converting an arithmetic expression into a binary tree. Naturally, I decided to build an evaluator.
A few days later I implemented closures, a garbage collector, a custom memory allocator, a REPL, an FFI, and a whole bunch of other stuff in C.
THE DATA STRUCTURES ASSIGNMENT
The problem was: Evaluate 1 + 1 + 1 to 3 using a binary tree. The operator becomes the root, with its two operands as children. Evaluating recursively collapses nested + expressions.
One way to represent operations is different cases in an expression type (Add, Sub, Mul, Div). But they all take two expressions and produce one — so why should the evaluator care which operation it is? Represent expressions as:
Expr ::= Func Expr Expr
| Val
The evaluator doesn't need to know what a function does. It only needs to know how to apply one.
Variables, hash tables, and C
Adding variables means an environment lookup. C doesn't have built-in hash tables — so implement one. Expression type becomes Func | Val | Var, represented as a tagged-union Node (~32 bytes plus malloc metadata → ~48 bytes per node). Evaluating 1+1 needs three nodes (~144 bytes with malloc headers). Lots of tiny allocations → time for a custom allocator.
Arena / chunk allocator
An arena grabs a big chunk up front and bumps an index. When a single 1024-node arena overflowed on fib(5) (~13k nodes), growing via realloc would invalidate interior pointers. Solution: a chunk allocator — linked list of fixed-size blocks; allocate a new chunk instead of moving memory.
Closures and the environment
Functions as opaque C pointers can't be user-defined or returned as values. Closures store parameter + body as a graph of nodes the evaluator can walk. The env table maps names to Node * values (literals, closures, or native C funcs).
Garbage collection
fib(40) without GC: ~12 GB RAM then OOM (~1.3B nodes). After mark-and-sweep (null children when reducing to literals; free-list reuse): ~1.7 MB for fib(40). Remaining problem: stop-the-world GC + exponential evaluation → ~6 minutes for fib(40). Future parts cover TCO, lexer/parser, FFI, REPL, and a Cheney copying collector.
What have we achieved so far?
Expression type as an algebraic data type (funcs, vars, literals)
Vars and funcs as values in one environment
Graph evaluator that mutates nodes after eval
Custom hashtable environment
Chunk allocator + mark-and-sweep GC
Overall: a graph reduction engine. And yes — 1+1 is in fact 2 according to graphLang.