Needed 1+1, built a functional programming language

This recounts building a tiny functional language evaluator in C, motivated by a homework task to compute expressions like 1+1+1. The author implemented a tagged-union Node AST, an environment hash table that maps names to Node values, and treated functions as first-class values by representing closures as nodes (parameter + body) so user-defined functions can be passed and returned. Memory issues drove major design choices: per-node size (32 bytes) plus malloc overhead made many small allocations expensive, so an arena allocator was introduced, then converted to a chained chunk allocator when fixed-size arenas caused segfaults on reallocation. The system includes a REPL, FFI, native C functions as opaque nodes, and an evaluator that walks and reduces the graph.

Running fib highlighted resource problems and motivated a garbage collector. The GC marks reachable nodes from roots, relies on mutating reduced nodes to literals (nulling old children) to make unreachable nodes collectible, and reclaims unmarked nodes into a free list for reuse. Benchmarks show fib(40) went from ~12+ GB down to ~1.7 MB after GC, a dramatic memory improvement, but execution remains slow (fib(40) took ~6 minutes), so correctness and memory reclamation are solved while performance optimizations remain outstanding.