Needed 1+1, built a functional programming language
11 hours ago
- Started with a binary tree arithmetic expression evaluator and realized operators can be generalized as functions (Add, Sub, etc. all take two operands and return one, so the evaluator only needs to apply a function).
- Added variables and implemented a custom hash table for the environment, since C lacks built-in hash tables.
- Built a tagged union node structure (Literal, Var, Func) and later added closure nodes to represent user-defined functions as tree bodies instead of opaque C function pointers.
- Developed an arena allocator to reduce malloc overhead, then upgraded to a chunk allocator (linked list of blocks) to avoid pointer invalidation when growing memory.
- Implemented a mark-and-sweep garbage collector to reclaim unreachable nodes, reducing memory usage for fib(40) from ~12 GB to ~1.7 MB.
- Noted a remaining performance problem (fib(40) took 6 minutes) due to exponential algorithm and stop-the-world GC, with plans for future optimizations like TCO and concurrent collection.
- Summarized achievements: an algebraic data type representation, a graph evaluator that mutates nodes, an environment table, a custom chunk allocator, and a mark-and-sweep garbage collector.