只想算个 1+1，结果写了一门函数式编程语言
作者拿到一道把算术表达式转成二叉树的数据结构作业，顺手写成了一个求值器，几天后就有了闭包、垃圾回收、自定义内存分配器、REPL 与 FFI。全文带 C 代码逐步讲清楚。
中文
复制
我拿到的数据结构作业，是把算术表达式转成二叉树。 很自然地，我决定顺手写个求值器。 几天后，我用 C 实现了闭包、垃圾回收器、自定义内存分配器、REPL、FFI，还有一大堆别的东西。 graphLang
那道数据结构作业
题目是： 用二叉树把 1 + 1 + 1 求值为 3。 怎么走到这一步？ 先给 1+1+1 建树。
(+)
/ \
(+) (1)
/ \运算符成为根节点，两个操作数是它的子节点。 现在来求值这棵树。 先求根节点左操作数。它又是一个 + 表达式，所以得先把它折叠成一个值，外层 + 才能执行。
(+)
/ \然后再求一次值。
(3) <--- that's our result我们刚刚做的，等价于
(+ (+ 1 1) 1)
|
v
(+ 2 1)
|
v但注意，求值器为了做到这一点，必须知道什么：+ 是什么意思。 一种表示方式，是把每种运算做成表达式类型里的一个分支：
Expr ::= Add Expr Expr
| Sub Expr Expr
| Mul Expr Expr
| Div Expr Expr可这些分支到底代表什么？ 求值器真的需要区分 Add 和 Sub 吗？ 然后我开始实现这些和类型。看着这个结构：
Add: Expr x Expr → Expr
Sub: Expr x Expr → Expr
Mul: Expr x Expr → Expr它们都是接收两个表达式，产出一个表达式。 那求值器凭什么要在意运算是 Add、Sub、Mul 还是 Div？ 看起来并不需要。 于是现在表达式可以写成：
Expr ::= Func Expr Expr求值器不需要知道函数做什么，它只需要知道怎么应用一个函数。
我们可以往里加变量。改动不大
应该只是加一点点东西，完全没问题。变量嘛，无非就是查一次哈希表，拿到一个 Expr。 哦等等。C 没有内置哈希表。 hmmm.（´-`）.｡oO( … )
那就实现一个哈希表吧。小改动！m9(・∀・) 那么……它怎么工作？我以前没实现过。 像原始人一样 Google 一下，找到这篇神文。 How to implement a hash table (in C) 于是 Expr 稍微改了一下：
Expr ::= Func Expr Expr
| Val 瞧瞧！现在有变量了，求值之后就能传给函数。就像 (+ 1 1) 那样。
真正用 C 实现它
好，那就按这个方案用 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 个给操作数
那就是 32 x 3 = 96 字节，只为算个 1+1。 但问题在这儿。在我的系统上，malloc() 一个节点会附带元数据，占掉 16 字节内存！ 于是每个节点的总开销变成 32（节点大小）+ 16（malloc 头）= 48 字节！ 所以要算一个 (+) 的 3 个节点，需要 144 字节！ 而且注意，我们会做大量零散的小块分配。 得找个更好的节点分配方式。 显然需要一个自定义分配器。 于是我去查能用什么分配器，还是像原始人一样，最后决定自己写一个 Arena Allocator。
Arena Allocator
Arena allocator 的思路很简单。一开始拿一大块内存，自己往里分配，最后一次性把整块释放掉。 所以我的 arena allocator 就是这样：
#define SIZE 1024分配节点时，我们只要用它来记录顶部位置。
int top = 0;要分配一个节点，我们直接返回。
&arena[top++];我写好了分配器，并定义了一个分配节点的 C 函数：
Node *allocNode();效果很好！接下来就是真正调用这些函数了。 然后我意识到
我们可以把变量和函数存在同一个环境里！也就是说函数本身也可以是值（°◇°）
还记得之前建的那个哈希表吗？是时候升级它了。
构建 Env 表
Env 表里存两样东西：变量和函数。 但函数是什么？ 对求值器来说，它就是个东西，一边吃参数，另一边吐出结果。
(func node)
/ \最初的想法是让它们直接指向 C 函数。看起来够简单。 但这里有个大问题：用户怎么写自己的函数？ 还有另一个问题。 当用户在我们的语言里输入代码时，它不可能凭空变成原生的 C 函数指针。它只能构建出一棵 AST（节点树）。 如果函数只是 C 指针，它们立刻就变成了不透明的值。 如果一个函数返回另一个函数怎么办？我们需要能把那个函数放回图里，之后再求值。但 C 函数指针不是求值器能遍历的东西。 所以我们需要一种节点类型，告诉求值器：“嘿，我是个函数，但我的代码不是 C 指针，而是这棵树。” 它需要把函数体存成一棵树，这样求值器就能分多步对它求值。就我们的目的而言，这就是闭包的表示。 闭包不是黑盒的 C 函数，而是我们图里一个实实在在的节点。它一边持有参数，另一边持有操作树（函数体）。
(closure)
/ \
(parameter) (body)
/ \（严格来说，闭包也有环境，只是我们还没讲到局部变量。）
把函数变成真正的节点之后，我们就能把它传来传去、从其他函数里返回它，想什么时候求值，就一步一步求值！
现在，用户自己就能定义函数了，完全不用碰 C 代码！！！
那好，来真正用 C 实现它。我们需要什么？ 既然变量和函数都是值，环境就得把名字映射到节点。 于是 env entry 可以写成
typedef struct EnvEntry {
char *key;
Node *val;
struct EnvEntry *next;
现在，哈希表把名字（key）映射到 Node *，也就是值。
但 val 到底是什么？
Val 就是一个 Node！可我们的 Node 还不知道闭包和原生函数。
那就把它们加进之前的 node 定义里。
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 则是由节点组成的用户自定义函数。 原生函数 = 不透明的 C 实现 闭包 = 语言层面的图表示 所以，零件都凑齐了：
- 一个内存分配器
- 一张环境表，装着变量、C 函数和用户自定义函数
- 一个求值器，沿着程序往下走并应用函数
来跑第一个程序吧！！
现在还没有 lexer/parser，所以直接手工构造 AST 就行。 拿什么程序来测，都比不上斐波那契数列！ 于是我写好了程序。输入 fib(5)。 然后…… 它崩了
升级内存分配器
为什么？因为 fib(5) 生成了 13k 个节点。而我们的分配器总共只有 1024 个节点！ 你可能会想：“这不显然吗：重新分配这块内存、把容量调大，做成动态数组。” 问题恰恰就在这里。关键在于，我们所有的节点都在这个内存块内部互相指向。 当我们用更大的容量 realloc 它时，它可能被搬到新的内存地址。 所有指针全部失效，直接 segfault！ 那怎么解决？
与其把一个分配器撑大，不如把多个块串起来！
我们可以把已分配的块串成一个链表。一个块的空间用完了，就再分配一个新块，然后指过去。不用搬移任何数据。
这叫 chunk allocator。每个块就是一个 chunk，负责存内存，我们用 next 指针把它们像链表一样串起来。
typedef struct Chunk {
Node nodes[CHUNK_SIZE];
struct Chunk *next;
我们只需要记录第一个 chunk，以及当前正在分配的那个 chunk。
我们有：
- 一个 Chunk Memory Allocator（新增）
- 一张 Environment 表，同时存放变量、c 函数和用户自定义函数
- 一个 Evaluator，递归地遍历程序，通过查 env 把表达式归约
再跑一次我们的第一个程序
然后…… 成功了！ 结果是 5！3+2 就是 5。 但有点不对劲。它占用了 1.32 mb 内存。 奇怪，fib(5) 又不是什么复杂操作。 于是我又跑了 fib(10) 吃掉了 40 mb 内存！！ 好吧，这确实不对劲。 所以我得测一测。我跑了个 benchmark。
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 ┼─────╯
-----------------------------------Fib(40) 在 OOM 崩溃之前，实打实吃掉了 12+ GB。 为什么？因为它大约会生成 13 亿个节点。 每个节点 48 字节，算下来就是约 62.4 GB 的节点分配量。 问题在于…… 我们一直在分配节点，但节点用完以后从来没释放过。 为了解决这个问题，我不得不写一个垃圾回收器。
构建垃圾回收器
回收垃圾是什么意思？ 简单说，就是把程序再也访问不到的节点清掉。 当我们求值 1+1+1 时，evaluator 会这么做：
- 构建 ast
(+)
/ \
(1) (+)
/ \- 求值左边。左边已经是字面量，跳过，转向右边。
- 右边是个函数，所以先求值它。然后我们修改这棵树。
(+)
/ \但那两个 1 呢？
它们就留在 allocator 里了！直到程序结束才会被释放！ 我们需要垃圾回收器做的，是从根出发，标记每一个仍然可以访问到的节点。 你会发现，当一个节点被归约成字面量之后，它原来的子节点就无法再通过这个节点访问到了！ 我们能做的是：一旦归约成字面量，就把两个子节点都置空。这样垃圾回收器就永远无法从图的这一部分走到那些旧节点。 这叫标记阶段。垃圾回收器从根出发，标记它能到达的每一个节点。 标记完成后，让垃圾回收器遍历所有 chunk，检查哪些节点没被标记，把它们加进一个叫 freeList 的链表。 这样我们需要新节点时，就可以复用这些节点，而不用再分配一个。 只有当 freeList 为空时，才从当前 chunk 里分配新节点。 否则，直接弹出头部，复用那块内存。 这样我们就能高效地回收节点了！！
加上 gc 之后再跑一次 benchmark：
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 ┼─╯
-----------------------------------看看这个！ 对于 fib(40)，内存占用从 12 GB 降到了 1.7 MB。 太离谱了。 但事情还没完。
fib 40 求值花了 6 分钟
为什么？ 我们刚写完的标记-清除垃圾回收器是 stop-the-world 的。 而我们跑的算法本身就是指数级的。 所以内存问题解决了。 但现在有了性能问题。 这两个问题都能解决。
- 可以实现并发垃圾回收器
- 也可以对 fib 本身的求值方式做点文章
后续部分会讲什么
这篇已经拖得够长了，所以我决定拆成几部分。
- 如何用 TCO 和更好的求值方式解决速度问题
- 实现了 lexer/parser
- 实现了 FFI……
- 实现了 REPL
- 从指针解引用切换……
- 把简陋的封装带进了 C
- 实现了 lambda 函数
- 加入了局部变量
- 为 Cheney 复制回收器搭好了架子
目前完成了什么？
- 意识到表达式类型可以是一个代数数据类型
- 然后意识到真正的变体就是数据的种类：函数、变量、字面量
- 接着意识到变量和函数其实不是两种东西，都只是数据
- 实现了一个图求值器，求值后就地修改当前节点
- 用自定义哈希表实现了环境表
- 实现了自定义 chunk 分配器来分配节点
- 意识到我们一直留着一大堆垃圾，于是实现了标记-清除垃圾回收器
总的来说，我造了一个图归约引擎
等等。那它能算 1+1 吗
能……我是说，现在能了。 按照 graphLang 的说法，1+1 确实等于 2！(´･ω･`) 总之，还有一大堆东西这里没讲，都在 repo 里。