The author began with a simple data structures assignment: evaluate the expression 1 + 1 + 1 to get 3 using a binary tree. While implementing the evaluator, they noticed that all binary operations (add, subtract, multiply, divide) share the same signature—taking two expressions and returning one—so the evaluator need not distinguish between operation types. This led to a uniform representation where an expression is either a function application or a literal value: Expr ::= Func Expr Expr | Val, forming the foundation of a new functional programming language they named graphLang.
To bring this design to life in C, the author built several supporting components. They created a custom hash table for an environment that maps variable and function names to nodes, allowing both built‑in C functions and user‑defined closures to be stored as values. Memory for the syntax‑tree nodes was managed with a chunk allocator—a linked list of fixed‑size blocks—to avoid pointer invalidation when expanding memory. Finally, a mark‑and‑sweep garbage collector was added to reclaim unreachable nodes. The impact was stark: evaluating fib(40) dropped from over 12 gigabytes of raw allocations to just 1.7 megabytes after garbage collection.
Despite the memory savings, the stop‑the‑world nature of the mark‑and‑sweep collector introduced a new bottleneck; evaluating fib(40) now required about six minutes because the algorithm being implemented is inherently exponential. The author acknowledges that further work is needed to improve performance, mentioning potential solutions such as tail‑call optimization, a proper lexer/parser, and exploring alternative garbage‑collection strategies like Cheney’s copying collector.