Pranav Desai
September 16, 2026
D
原文
---
title: "为算 1+1,我做了一门函数式编程语言"
author: "Pranav Desai"
source_url: "https://hereticpleb.vercel.app/blog/needed-one-plus-one/"
published_at: "September 16, 2026"
fetched_at: "2026-09-30T08:29:38Z"
updated_at: "2026-09-30T08:33:40Z"
language: "zh"
review_status: "draft"
---
# 为算 1+1,我做了一门函数式编程语言
2026 年 9 月 16 日 • 13 分钟阅读
我拿到了一道数据结构题:把一个算术表达式转换成一棵二叉树。
很自然地,我决定写一个求值器。
几天之后,我已经在 C 里实现了闭包、垃圾回收器、自定义内存分配器、REPL、FFI,还有一大堆别的东西。
[graphLang](https://github.com/PranavDesai-Git/graphLang)
## 数据结构作业
题目是:
用二叉树把 1 + 1 + 1 求值为 3。
怎么做到呢?
首先,我们为 1+1+1 构造这棵树:
```
(+)
/ \
(+) (1)
/ \
(1) (1)
```
运算符成为根节点,两个操作数成为它的子节点。
现在我们来对这棵树求值。
首先,求根节点左侧操作数的值。它又是一个 + 表达式,所以在外层 + 可以执行之前,必须先把它折叠成一个值。
```
(+)
/ \
(2) (1)
```
然后再次求值。
```
(3) <--- that's our result
```
我们刚刚做的事情等价于:
```lisp
(+ (+ 1 1) 1)
|
v
(+ 2 1)
|
v
(3)
```
但注意,求值器为了做到这一点,必须知道一件事:+ 是什么意思。
一种表示方法是,在表达式类型里给每种运算都做一个不同的分支:
```haskell
Expr ::= Add Expr Expr
| Sub Expr Expr
| Mul Expr Expr
| Div Expr Expr
| Val
```
但这些不同的分支实际代表什么?
求值器真的需要知道 Add 和 Sub 的区别吗?
于是我开始实现 sum type(和类型)。看到它们的结构时,我发现:
```
Add: Expr x Expr → Expr
Sub: Expr x Expr → Expr
Mul: Expr x Expr → Expr
Div: Expr x Expr → Expr
```
它们都接收两个表达式,并产生一个表达式。
那求值器为什么要关心这个操作到底是 Add、Sub、Mul 还是 Div 呢?
看起来它确实不需要关心。
所以现在我们可以把表达式直接表示成:
```haskell
Expr ::= Func Expr Expr
| Val
```
求值器不需要知道一个函数具体做什么。它只需要知道如何应用一个函数。
## 可以给它加变量。这应该不是什么大改动
应该只是个很小的改动,完全没问题。我的意思是,变量不就是从哈希表里查一下,得到一个 Expr 吗?
哦等等。C 没有内置哈希表。
hmmm.(´-`).。oO( … )
> 那就自己实现一个哈希表吧。小改动而已!m9(・∀・)
所以……这东西怎么写?我以前从没实现过。
我像穴居人一样去 Google 上搜,然后找到了这篇很棒的文章。
[How to implement a hash table (in C)](https://benhoyt.com/writings/hash-table-in-c/)
于是现在 Expr 只需要一点小改动:
```haskell
Expr ::= Func Expr Expr
| Val
| Var
```
你看!现在我们有变量了,求值后变量也可以传给函数。就像 (+ 1 1) 一样。
## 真正在 C 里实现它
好吧,按这个计划开始写 C。看起来够简单。就是一个 tagged union(带标签联合)。
```c
typedef enum {
LITERAL,
VAR,
FUNC,
} NodeType;
struct Node {
struct Node *left;
struct Node *right;
union {
int literal;
char *var;
char *func;
} data;
NodeType type;
};
```
现在每个节点的内存大小是这样的(假设是 64 位系统):
```
+------------------------+----------+
| Field | Size |
+------------------------+----------+
| Left Pointer | 8 bytes |
| Right Pointer | 8 bytes |
| Data | 8 bytes |
| Type | 4 bytes |
| Padding | 4 bytes |
+------------------------+----------+
| Total | 32 bytes |
+------------------------+----------+
```
32 字节看起来可能不多,但我们得想想它会怎么被使用。为了求值 1+1,我们需要 3 个节点。
- 1 个给运算符
- 2 个给操作数
也就是说,为了求值 1+1,需要 32 x 3 = **96 字节**。
但问题在这里。在我的系统上,当你 malloc() 一个节点时,它会额外加上元数据,占用 **16 字节**内存!
于是每个节点总共变成 32(节点大小)+ 16(malloc header)= **48 字节!**
所以,只是为了用 3 个节点求值一个 (+),我们就需要 144 字节!
而且注意,我们会进行大量很小的独立分配。
我们需要一种更好的方式来分配这些节点。
显然,我们需要一个自定义分配器。
于是我又像穴居人一样去查可以用什么分配器,最后决定自己写一个 arena allocator(区域分配器)。
## Arena Allocator
arena allocator 的想法很简单。你一开始拿一大块内存,之后自己在里面分配东西,最后再一次性释放整块内存。
所以我的 arena allocator 大概就是:
```c
#define SIZE 1024
Node arena[SIZE]
```
分配节点时,我们只要用一个 top 记录当前位置。
```c
int top = 0;
```
需要分配节点时,直接返回:
```c
&arena[top++];
```
我写好了分配器,并定义了一个 C 函数来分配节点:
```c
Node *allocNode();
```
非常好!接下来就可以真正调用函数了。
然后我意识到:
> 我们可以把变量和函数存在同一个环境里!这意味着函数也可以只是值 (°◇°)
还记得我们前面创建的那个哈希表吗?现在该升级它了。
## 构造环境表
在 Env 表里,我们要存两种东西:变量和
函数。
但函数是什么?
从求值器的角度看,它就是一种东西:
从一侧吃进参数,从另一侧吐出
结果。
```
(func node)
/ \
(arg 1) (arg 2)
```
最初的想法是,它们就只是指向 C
函数的指针。看起来足够简单。
但这有一个大问题:用户要怎么写自己的函数?
而且还有另一个问题。
当用户在我们的语言里输入代码时,它不可能魔法般变成一个原生 C 函数指针。它只能构造出一棵 AST(一棵节点树)。
如果函数只是 C 指针,它们立刻就变成了不透明的值。
如果一个函数返回另一个函数,会发生什么?我们需要能把那个函数放回图里,并在之后继续求值。但 C 函数指针不是求值器可以继续遍历的东西。
所以我们需要一种节点类型,告诉求值器:
“嘿,我是一个函数,但我的代码不是 C
指针;它就是这里这棵树。”
它需要把函数体存成一棵树,这样求值器才能分多步对它求值。对我们来说,这就是闭包的表示方式。
闭包不是一个黑盒 C 函数,而是图里的一个
实际节点。它一侧保存参数,另一侧保存
操作树,也就是函数体。
```
(closure)
/ \
(parameter) (body)
/ \
(math) (literal)
```
(严格说闭包还会有环境,但我们还没讲到局部变量。)
把函数做成一个实际节点之后,我们就可以传递它,
从其他函数里返回它,并且在任何时候一步一步
对它求值!
> 现在用户可以定义自己的函数了,而且完全不用碰 C 代码!!!
好吧,那就在 C 里真正实现它。我们需要什么?
如果变量和函数都是值,那么环境就需要把名字映射到节点。
所以现在我们可以这样创建 env entry:
```c
typedef struct EnvEntry {
char *key;
Node *val;
struct EnvEntry *next;
} EnvEntry;
```
现在我们的哈希表把名字(key)映射到作为值的 Node *。
但 val 到底*是什么*?
Val 是一个 Node!但我们的 Node 还不知道闭包或原生函数。
所以我们把它们加到之前的节点定义里。
```c
struct Node {
struct Node *left;
struct Node *right;
union {
int literal;
char *var;
int index;
char *call;
struct Node *closure;
struct Node *nativeFunc;
} data;
NodeType type;
};
```
nativeFuncs 是表示 C 函数的节点,而 closures 是由节点组成的用户自定义函数。
native function = 不透明的 C 实现
closure = 语言层面的图表示
所以。我们已经把这些组件组装起来了:
- 一个内存分配器
- 一个保存变量、C 函数和用户自定义函数的环境表
- 一个沿着程序向下遍历并应用函数的求值器
> 来执行我们的第一个程序吧!!
现在还没有 lexer/parser,所以我们只能手工构造 AST。
还有什么程序比斐波那契数列更适合测试呢!
于是我写了程序。输入 fib(5)。
然后……
**它崩了**
## 升级内存分配器
为什么?因为 fib(5) 生成了 **1.3 万个节点**。但我们的分配器总大小只有 1024 个节点!
你可能会想:“好吧,这很明显:重新分配这块内存,把大小变大。把它做成动态数组。”
而问题恰恰就在这里。重点是,我们所有节点都在这块内存里互相指向对方。
当我们用 realloc 扩大它时,它可能会被移动到新的内存地址。
这会彻底破坏所有指针,并导致 segfault!
怎么解决这个问题?
> 与其扩展一个分配器,不如把多个块串起来!
我们可以构造一个已分配内存块的链表。当一个块用完时,就分配一个新的块,并让它指向后面的块!我们不需要移动任何数据!
这叫 chunk allocator!每个块都是一个 chunk,用来存放内存;我们像链表一样用 next 指针把它们串起来。
```c
typedef struct Chunk {
Node nodes[CHUNK_SIZE];
struct Chunk *next;
} Chunk;
```
我们可以记录第一个 chunk,以及当前正在从哪个 chunk 里分配。
现在我们有:
- 一个 Chunk Memory Allocator(新的)
- 一个同时保存变量、C 函数和用户自定义函数的环境表
- 一个只需要递归地沿程序向下走,并通过 env lookup 化简表达式的求值器
> 再来执行一次我们的第一个程序
然后……
**成功了!**
我们得到了结果 5!3+2 就是 5。
**但有件怪事发生了**。它用了 1.32 MB 内存。
这很怪,因为 fib(5) 并不是一个复杂操作。
所以我跑了 fib(10)。
它用了 40 MB RAM!!
好吧,这就很奇怪。
所以我必须测一下。我跑了一个基准测试。
```
RAM (GB) vs fib(n)
12.29 GB ┤
11.34 GB ┤ ╭───
10.40 GB ┤ ╭──────╯
9.45 GB ┤ ╭─────╯
8.51 GB ┤ ╭───╯
7.56 GB ┤ ╭╯
6.62 GB ┤ ╭╯
5.67 GB ┤ ╭╯
4.73 GB ┤ ╭─╯
3.78 GB ┤ ╭╯
2.84 GB ┤ ╭╯
1.89 GB ┤ ╭╯
0.95 GB ┤ ╭╯
0.00 GB ┼─────╯
-----------------------------------
5 10 20 40
```
Fib(40) 在 OOM 崩溃之前,真的用了 12+ GB。
为什么?因为它大约生成了 13 亿个节点。
按每个节点 48 字节算,这相当于大约 62.4 GB 的节点分配。
问题是……
我们一直在分配节点,但节点用完之后从来没有释放。
为了解决这个问题,我必须做一个垃圾回收器。
## 构建垃圾回收器
收集垃圾是什么意思?
基本上,我们需要清除那些程序已经无法再抵达的节点。
当我们求值 1+1+1 时,求值器会这样做:
1. 构建 AST
```
(+)
/ \
(1) (+)
/ \
(1) (1)
```
2. 求左侧。左侧已经是字面量。继续处理右侧。
3. 右侧是一个函数。所以它会先被求值。然后我们会修改这棵树。
```
(+)
/ \
(1) (2)
```
> 但那两个 1 会怎么样?
它们还留在分配器里!直到程序结束之前,它们都不会被释放!
我们需要垃圾回收器做的,就是从根开始,标记每一个仍然可以抵达的节点。
现在,如果你注意到了,当我们把一个节点化简成字面量时,它原来的子节点就无法再通过这个节点抵达了!
我们可以做的是,一旦把节点修改成字面量,就把它的两个子节点都置空。这样垃圾回收器就永远不能从图的这个部分抵达那些旧节点。
这叫标记阶段。垃圾回收器从根开始,标记它能抵达的每个节点。
标记完成后,让垃圾回收器遍历所有 chunk,检查哪些节点没有被标记,并把它们加入一个叫 freeList 的链表。
现在当我们需要新节点时,就可以复用这些节点中的一个,而不是再分配一个。
如果 freeList 是空的,这时才从当前 chunk 里分配一个新节点。
否则,我们只要弹出链表头,复用那块内存。
这样我们就能有效地回收利用节点!!
> 应用 GC 之后,再来跑基准测试:
```
RAM w/ GC (MB) vs fib(n)
1.7200 MB ┼
1.5886 MB ┤ ╭───
1.4571 MB ┤ ╭────╯
1.3257 MB ┤ ╭─────╯
1.1942 MB ┤ ╭────╯
1.0628 MB ┤ ╭─╯
0.9314 MB ┤ ╭╯
0.7999 MB ┤ ╭─╯
0.6685 MB ┤ ╭╯
0.5371 MB ┤ ╭─╯
0.4056 MB ┤ ╭╯
0.2742 MB ┤ ╭╯
0.1427 MB ┤ ╭───╯
0.0113 MB ┼─╯
-----------------------------------
5 10 20 40
```
**看到了吗!** fib(40) 的 RAM 使用量从 12 GB 降到了 1.7 MB。
太离谱了。
但问题还没有完全解决。
> fib 40 求值花了 6 分钟
为什么?
我们刚刚完成的 mark-and-sweep 垃圾回收器是一个 stop-the-world 垃圾回收器。
而我们正在跑的算法本身就是指数级的。
所以我们修好了内存问题。
但现在又有了性能问题。
这两个问题都可以继续处理。
- 我们可以实现一个 concurrent garbage collector(并发垃圾回收器)
- 也可以处理 fib 本身的求值方式
## 后续部分会讲什么
这篇已经够长了,所以我决定把它拆成几个部分。
- 我如何用 TCO 和更好的求值方式处理速度问题
- 实现了 lexer/parser
- 实现了 FFI……
- 实现了 REPL
- 从 pointer dereferencing(指针解引用)切换到别的方式……
- 把粗糙的封装带进 C
- 实现了 lambda functions(lambda 函数)
- 加入了 local vars(局部变量)
- 为 Cheney’s copying collector 做了一些准备
## 到目前为止,我们实现了什么?
- 意识到我们的表达式类型可以是一个 Algebraic Data Type(代数数据类型)
- 接着意识到,真正的变体其实是数据的种类:函数、变量、字面量
- 然后意识到,变量和函数其实不是两种不同的东西,它们都只是数据
- 实现了一个 graph evaluator(图求值器),它会在求值后修改当前节点
- 用自定义哈希表实现了一个 Environment Table(环境表)
- 实现了一个 custom chunk allocator(自定义 chunk 分配器)来分配节点
- 意识到我们一直留着大量垃圾,于是实现了一个 mark-and-sweep garbage collector(标记-清扫垃圾回收器)
总的来说,我做了一个 Graph Reduction engine(图归约引擎)。
## 等等。但它真的能算 1+1 吗?
嗯……我的意思是,现在可以了。
按照 graphLang 的说法,1+1 的确是 2!(´・ω・`)
总之,还有很多东西我没有在这里讲。它们都在仓库里。