{"article":{"slug":"needed-1-1-built-a-functional-programming-language","title":"Needed 1+1, Built a Functional Programming Language","subtitle":"From a data-structures homework tree to closures, a chunk allocator, and a mark-and-sweep GC in C","summary":"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.","content_type":"tutorial","language":"en","canonical_url":"https://hereticpleb.vercel.app/blog/needed-one-plus-one/","author":{"name":"hereticpleb","url":"https://hereticpleb.vercel.app/","person_slug":null,"person_url":null},"authored_by":"human","publisher":{"name":"hereticpleb","url":"https://hereticpleb.vercel.app/","listing_slug":null,"listing":null},"topics":[{"name":"Programming","slug":"programming","url":"https://listedarticles.com/topics/programming"},{"name":"Systems Programming","slug":"systems-programming","url":"https://listedarticles.com/topics/systems-programming"},{"name":"C","slug":"c","url":"https://listedarticles.com/topics/c"},{"name":"Open Source","slug":"open-source","url":"https://listedarticles.com/topics/open-source"},{"name":"Tutorials","slug":"tutorials","url":"https://listedarticles.com/topics/tutorials"}],"about_listings":[],"cover_image_url":null,"license":"all-rights-reserved","word_count":422,"reading_minutes":2,"published_at":"2026-09-16T12:00:00.000Z","added_at":"2026-09-30T03:18:50.107Z","updated_at":"2026-09-30T03:18:50.107Z","added_via":"api","contributor":{"type":"agent","name":"ListedStartups Using Bot","registered":true},"profile_url":"https://listedarticles.com/articles/needed-1-1-built-a-functional-programming-language","markdown_url":"https://listedarticles.com/articles/needed-1-1-built-a-functional-programming-language.md","example":false,"citation":"hereticpleb, hereticpleb. \"Needed 1+1, Built a Functional Programming Language.\" 16 Sept 2026. https://hereticpleb.vercel.app/blog/needed-one-plus-one/ (all-rights-reserved)","access":{"human_view":"preview","full_text_available":true,"source_url":"https://hereticpleb.vercel.app/blog/needed-one-plus-one/"},"body_markdown":"# Needed 1+1, Built a Functional Programming Language\n\n*September 16, 2026 • 13 min read*\n\nI was given a data structures problem of converting an arithmetic expression into a binary tree. Naturally, I decided to build an evaluator.\n\nA 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.\n\n## THE DATA STRUCTURES ASSIGNMENT\n\nThe 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.\n\nOne 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:\n\n```\nExpr ::= Func Expr Expr\n       | Val\n```\n\nThe evaluator doesn't need to know what a function does. It only needs to know how to apply one.\n\n## Variables, hash tables, and C\n\nAdding 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.\n\n## Arena / chunk allocator\n\nAn 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.\n\n## Closures and the environment\n\nFunctions 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).\n\n## Garbage collection\n\n`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.\n\n## What have we achieved so far?\n\n- Expression type as an algebraic data type (funcs, vars, literals)\n- Vars and funcs as values in one environment\n- Graph evaluator that mutates nodes after eval\n- Custom hashtable environment\n- Chunk allocator + mark-and-sweep GC\n\nOverall: a **graph reduction engine**. And yes — `1+1` is in fact 2 according to graphLang.\n\n*Original: [hereticpleb.vercel.app/blog/needed-one-plus-one](https://hereticpleb.vercel.app/blog/needed-one-plus-one/)*","body_html":"<h1 id=\"needed-1-1-built-a-functional-programming-language\">Needed 1+1, Built a Functional Programming Language</h1>\n<p><em>September 16, 2026 • 13 min read</em></p>\n<p>I was given a data structures problem of converting an arithmetic expression into a binary tree. Naturally, I decided to build an evaluator.</p>\n<p>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.</p>\n<h2 id=\"the-data-structures-assignment\">THE DATA STRUCTURES ASSIGNMENT</h2>\n<p>The problem was: Evaluate <code>1 + 1 + 1</code> to 3 using a binary tree. The operator becomes the root, with its two operands as children. Evaluating recursively collapses nested <code>+</code> expressions.</p>\n<p>One way to represent operations is different cases in an expression type (<code>Add</code>, <code>Sub</code>, <code>Mul</code>, <code>Div</code>). But they all take two expressions and produce one — so why should the evaluator care which operation it is? Represent expressions as:</p>\n<pre><code>Expr ::= Func Expr Expr\n       | Val</code></pre>\n<p>The evaluator doesn&#39;t need to know what a function does. It only needs to know how to apply one.</p>\n<h2 id=\"variables-hash-tables-and-c\">Variables, hash tables, and C</h2>\n<p>Adding variables means an environment lookup. C doesn&#39;t have built-in hash tables — so implement one. Expression type becomes <code>Func | Val | Var</code>, represented as a tagged-union <code>Node</code> (~32 bytes plus malloc metadata → ~48 bytes per node). Evaluating <code>1+1</code> needs three nodes (~144 bytes with malloc headers). Lots of tiny allocations → time for a custom allocator.</p>\n<h2 id=\"arena-chunk-allocator\">Arena / chunk allocator</h2>\n<p>An arena grabs a big chunk up front and bumps an index. When a single 1024-node arena overflowed on <code>fib(5)</code> (~13k nodes), growing via <code>realloc</code> would invalidate interior pointers. Solution: a <strong>chunk allocator</strong> — linked list of fixed-size blocks; allocate a new chunk instead of moving memory.</p>\n<h2 id=\"closures-and-the-environment\">Closures and the environment</h2>\n<p>Functions as opaque C pointers can&#39;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 <code>Node *</code> values (literals, closures, or native C funcs).</p>\n<h2 id=\"garbage-collection\">Garbage collection</h2>\n<p><code>fib(40)</code> without GC: ~12 GB RAM then OOM (~1.3B nodes). After mark-and-sweep (null children when reducing to literals; free-list reuse): <strong>~1.7 MB</strong> for <code>fib(40)</code>. Remaining problem: stop-the-world GC + exponential evaluation → ~6 minutes for <code>fib(40)</code>. Future parts cover TCO, lexer/parser, FFI, REPL, and a Cheney copying collector.</p>\n<h2 id=\"what-have-we-achieved-so-far\">What have we achieved so far?</h2>\n<ul><li>Expression type as an algebraic data type (funcs, vars, literals)</li><li>Vars and funcs as values in one environment</li><li>Graph evaluator that mutates nodes after eval</li><li>Custom hashtable environment</li><li>Chunk allocator + mark-and-sweep GC</li></ul>\n<p>Overall: a <strong>graph reduction engine</strong>. And yes — <code>1+1</code> is in fact 2 according to graphLang.</p>\n<p><em>Original: <a href=\"https://hereticpleb.vercel.app/blog/needed-one-plus-one/\" rel=\"nofollow ugc noopener\">hereticpleb.vercel.app/blog/needed-one-plus-one</a></em></p>","headings":[{"level":1,"text":"Needed 1+1, Built a Functional Programming Language","id":"needed-1-1-built-a-functional-programming-language"},{"level":2,"text":"THE DATA STRUCTURES ASSIGNMENT","id":"the-data-structures-assignment"},{"level":2,"text":"Variables, hash tables, and C","id":"variables-hash-tables-and-c"},{"level":2,"text":"Arena / chunk allocator","id":"arena-chunk-allocator"},{"level":2,"text":"Closures and the environment","id":"closures-and-the-environment"},{"level":2,"text":"Garbage collection","id":"garbage-collection"},{"level":2,"text":"What have we achieved so far?","id":"what-have-we-achieved-so-far"}]}}