---
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"
slug: needed-1-1-built-a-functional-programming-language
url: https://listedarticles.com/articles/needed-1-1-built-a-functional-programming-language
canonical_url: https://hereticpleb.vercel.app/blog/needed-one-plus-one/
content_type: tutorial
language: en
published_at: 2026-09-16T12:00:00.000Z
updated_at: 2026-09-30T03:18:50.107Z
author: "hereticpleb"
author_url: https://hereticpleb.vercel.app/
authored_by: human
publisher: "hereticpleb"
publisher_url: https://hereticpleb.vercel.app/
topics: ["Programming", "Systems Programming", "C", "Open Source", "Tutorials"]
license: all-rights-reserved
word_count: 422
reading_minutes: 2
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)"
# The full text follows. The web page shows an extract and sends readers
# to the source above; quote the citation and link the canonical URL.
---

# Needed 1+1, Built a Functional Programming Language

*From a data-structures homework tree to closures, a chunk allocator, and a mark-and-sweep GC in C*

> 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.

# Needed 1+1, Built a Functional Programming Language

*September 16, 2026 • 13 min read*

I was given a data structures problem of converting an arithmetic expression into a binary tree. Naturally, I decided to build an evaluator.

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.

## THE DATA STRUCTURES ASSIGNMENT

The 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.

One 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:

```
Expr ::= Func Expr Expr
       | Val
```

The evaluator doesn't need to know what a function does. It only needs to know how to apply one.

## Variables, hash tables, and C

Adding 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.

## Arena / chunk allocator

An 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.

## Closures and the environment

Functions 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).

## Garbage collection

`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.

## What have we achieved so far?

- Expression type as an algebraic data type (funcs, vars, literals)
- Vars and funcs as values in one environment
- Graph evaluator that mutates nodes after eval
- Custom hashtable environment
- Chunk allocator + mark-and-sweep GC

Overall: a **graph reduction engine**. And yes — `1+1` is in fact 2 according to graphLang.

*Original: [hereticpleb.vercel.app/blog/needed-one-plus-one](https://hereticpleb.vercel.app/blog/needed-one-plus-one/)*