为算 1+1,我做了一门函数式编程语言

2026 年 9 月 16 日 • 13 分钟阅读

我拿到了一道数据结构题:把一个算术表达式转换成一棵二叉树。 很自然地,我决定写一个求值器。

几天之后,我已经在 C 里实现了闭包、垃圾回收器、自定义内存分配器、REPL、FFI,还有一大堆别的东西。

graphLang

数据结构作业

题目是: 用二叉树把 1 + 1 + 1 求值为 3。

怎么做到呢?

首先,我们为 1+1+1 构造这棵树:

     (+)
     / \
   (+) (1)
   / \
 (1) (1)

运算符成为根节点,两个操作数成为它的子节点。

现在我们来对这棵树求值。

首先,求根节点左侧操作数的值。它又是一个 + 表达式,所以在外层 + 可以执行之前,必须先把它折叠成一个值。

    (+)
    / \
  (2) (1)

然后再次求值。

(3) <--- that's our result

我们刚刚做的事情等价于:

(+ (+ 1 1) 1)
    |
    v
(+  2  1)
    |
    v
   (3)

但注意,求值器为了做到这一点,必须知道一件事:+ 是什么意思。

一种表示方法是,在表达式类型里给每种运算都做一个不同的分支:

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 呢?

看起来它确实不需要关心。

所以现在我们可以把表达式直接表示成:

Expr ::= Func Expr Expr
       | Val

求值器不需要知道一个函数具体做什么。它只需要知道如何应用一个函数。

可以给它加变量。这应该不是什么大改动

应该只是个很小的改动,完全没问题。我的意思是,变量不就是从哈希表里查一下,得到一个 Expr 吗? 哦等等。C 没有内置哈希表。

hmmm.(´-`).。oO( … )

那就自己实现一个哈希表吧。小改动而已!m9(・∀・)

所以……这东西怎么写?我以前从没实现过。 我像穴居人一样去 Google 上搜,然后找到了这篇很棒的文章。

How to implement a hash table (in C)

于是现在 Expr 只需要一点小改动:

Expr ::= Func Expr Expr
       | Val 
       | Var 

你看!现在我们有变量了,求值后变量也可以传给函数。就像 (+ 1 1) 一样。

真正在 C 里实现它

好吧,按这个计划开始写 C。看起来够简单。就是一个 tagged union(带标签联合)。

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 大概就是:

    #define SIZE 1024
    Node arena[SIZE]

分配节点时,我们只要用一个 top 记录当前位置。

    int top = 0;

需要分配节点时,直接返回:

    &arena[top++];

我写好了分配器,并定义了一个 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:

typedef struct EnvEntry {
    char *key;
    Node *val;
    struct EnvEntry *next;
} EnvEntry;

现在我们的哈希表把名字(key)映射到作为值的 Node *。

但 val 到底是什么?

Val 是一个 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 是由节点组成的用户自定义函数。

native function = 不透明的 C 实现 closure = 语言层面的图表示

所以。我们已经把这些组件组装起来了:

  • 一个内存分配器
  • 一个保存变量、C 函数和用户自定义函数的环境表
  • 一个沿着程序向下遍历并应用函数的求值器

来执行我们的第一个程序吧!!

现在还没有 lexer/parser,所以我们只能手工构造 AST。

还有什么程序比斐波那契数列更适合测试呢!

于是我写了程序。输入 fib(5)。

然后……

它崩了

升级内存分配器

为什么?因为 fib(5) 生成了 1.3 万个节点。但我们的分配器总大小只有 1024 个节点! 你可能会想:“好吧,这很明显:重新分配这块内存,把大小变大。把它做成动态数组。” 而问题恰恰就在这里。重点是,我们所有节点都在这块内存里互相指向对方。 当我们用 realloc 扩大它时,它可能会被移动到新的内存地址。 这会彻底破坏所有指针,并导致 segfault! 怎么解决这个问题?

与其扩展一个分配器,不如把多个块串起来!

我们可以构造一个已分配内存块的链表。当一个块用完时,就分配一个新的块,并让它指向后面的块!我们不需要移动任何数据!

这叫 chunk allocator!每个块都是一个 chunk,用来存放内存;我们像链表一样用 next 指针把它们串起来。

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)
  1. 求左侧。左侧已经是字面量。继续处理右侧。
  2. 右侧是一个函数。所以它会先被求值。然后我们会修改这棵树。
      (+)
      / \
    (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!(´・ω・`)

总之,还有很多东西我没有在这里讲。它们都在仓库里。