I Needed 1+1, So I Built a Functional Programming Language
Needed 1+1, built a functional programming language
A simple data structures assignment to evaluate 1+1+1 with a binary tree spiraled into building a full functional language in C. The author implemented closures, a garbage collector, a custom arena allocator, a REPL, and an FFI, then watched fib(40) consume 12 GB before crashing. The post details the journey from a tagged union to a chunk allocator and the realization that a garbage collector was inevitable.
Fib(40) literally took 12+ GIGABYTES before hitting an OOM and crashing. Why? Because it spawns approximately 1.3 Billion nodes. At 48 bytes per node, that’s ~62.4 GB worth of node allocations.
- dalton74
My weekend project started as "parse a log file" and now it's a microservice mesh. Relatable.
- CodesInChaos
Greenspun's tenth rule of programming:
> Any sufficiently complicated C or Fortran program contains an ad hoc, informally-specified, bug-ridden, slow implementation of half of Common Lisp.
- tromp
> Overall, I built a Graph Reduction engine
I did the same for my performant implementation of pure functional programming language BLC/BLC2,
which in 400+ lines contains a graph reduction engine for combinatory logic, to which the lambda calculus programs are converted by Kiselyov's bracket abstraction algorithm.
- gnarlouse
This reminds me of decades ago when ...wait, I was still writing code like three years ago.
- Joker_vD
> The thing is, all of our nodes are pointing to each other inside this memory block. When we realloc it with an increased size, it might get moved to a new memory address. Completely breaking all of our pointers and causing a segfault! How do we tackle this problem?
Store indices into the arena array? You could probably even use 4-byte indices and cut down the memory usage...
> Fib(40) literally took 12+ GIGABYTES before hitting an OOM and crashing. Why? Because it spawns approximately 1.3 Billion nodes.
Okay, maybe you can keep 8-byte indices.
> The mark-and-sweep garbage collector we just completed is a stop-the-world garbage collector. And the algorithm we’re running is inherently exponential.
How about a copying collector then? The recursive Fibonacci generates a lot of garbage but IIRC its live set is actually pretty small at any single point of time. If you need a benchmark for GC when your function actually has a huge live set, then something like
def garbage(n):
if n == 0:
return None
return (garbage(n-1), garbage(n-1))
should do the trick; if you don't have proper data structure you can simulate it with closures pretty trivially.
> And we can do something about how we’re evaluating fib itself
You mean "switch from recursively walking AST" or "write a non-exponential Fibonacci"?