奇链 奇链
← 文章 / 编程开发
Hacker News 3小时前 · 2026-09-30 18:27:04 · 2 阅读

为了算 1+1，我手写了一套函数式编程语言

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

几天之后，我已经用 C 实现了闭包、垃圾回收器、自定义内存分配器、REPL、FFI，还有一堆其他东西。

graphLang

这道数据结构作业题

题目是：用二叉树求值 1 + 1 + 1，得到 3。

怎么做到呢？

首先，为 1+1+1 构建这样一棵树：

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

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

现在来求值这棵树。

先求根节点左边的操作数。它是另一个 + 表达式，必须先把它折叠成一个值，外层的 + 才能执行。

    (+)
    / \
  (2) (1)

然后再求值一次。

(3) <--- 这就是结果

这等价于执行了：

(+ (+ 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 types）。当我看到它们的结构时：

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(・∀・)

那……具体该怎么实现呢？我以前从没写过。 我像原始人一样去谷歌搜了一下，结果发现了这篇精彩的文章。

如何在 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 头部） = 48 字节！

所以，为了计算一个 (+) 操作，也就是这 3 个节点，我们需要 144 字节！

而且你会发现，我们要进行大量的小块独立内存分配。 我们需要一种更好的方式来分配这些节点。

显然，我们需要一个自定义的分配器。

于是，我又像原始人一样去查可以用什么分配器，最后决定写一个 Arena Allocator。

Arena Allocator

Arena 分配器的原理很简单：一开始分配一大块内存，自己管理分配，最后把整块内存一次性释放掉。 所以我的 arena 分配器就长这样： 
    #define SIZE 1024
    Node arena[SIZE]
分配节点时，只需记录顶部位置即可： 
    int top = 0;
需要分配节点时，直接返回： 
    &arena[top++];
我写好了分配器，并定义了一个 C 函数来分配节点： 
Node *allocNode();
效果很棒！接下来开始调用实际函数。 然后我突然意识到：

变量和函数可以存在同一个环境里！也就是说，函数本身也可以作为值（°◇°）

还记得之前创建的哈希表吗？是时候升级它了。

构建 Env 表

在 Env 表里我们存了两样东西：变量和函数。

但函数到底是什么？对于我们的求值器而言，它是一个实体，一边接收参数，另一边输出结果。

    (func node)
    /         \
 (arg 1)    (arg 2)

最初的想法是，函数就是指向 C 函数的指针。听起来挺简单。

但这有个大问题：用户怎么编写自己的函数？

此外还有另一个问题。

当用户在我们的语言中输入代码时，代码不会 magically 变成原生 C 函数指针。它只能构建 AST（节点树）。

如果函数仅仅是 C 指针，它们就变成了不透明的值。当函数返回另一个函数时会发生什么？我们需要能把那个函数放回图中并稍后求值。但 C 函数指针不是求值器能遍历的东西。

因此我们需要一种节点类型，告诉求值器：“嘿，我是函数，但我的代码不是 C 指针，就是这棵树。”它需要把函数体存储为树，这样求值器就能分多步进行求值。对于我们来说，这就是闭包的表示形式。

与黑盒 C 函数不同，闭包是图中实际存在的节点。它一边保存参数，另一边保存操作树（即函数体）。

         (闭包)
         /        \
 (参数)          (函数体)
                 /      \
            (数学运算)  (字面量)

严格来说，闭包还包含一个环境，但我们还没讲到局部变量。

把函数做成真正的节点后，我们就可以把它传来传去、从其他函数中返回，还能随时一步步地对它求值！

现在用户终于可以自定义函数，完全不用碰 C 代码了！！！

好了，接下来就动手用 C 实现。我们需要些什么？

变量和函数都是值，所以环境需要把名字映射到节点。这样 env entry 就可以定义成：

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

现在哈希表把名字（key）映射到作为值的 Node *。

但这个 val 到底是什么？

val 是一个 Node！但我们的 Node 还不认识闭包和 native 函数。所以要把它们加进之前的节点定义里。

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;
};

nativeFunc 是表示 C 函数的节点，而闭包是由节点组成的用户自定义函数。

native 函数 = 不透明的 C 实现 闭包 = 语言层面的图结构表示

好了，所有部件都齐了：

  • 一个内存分配器

  • 一张环境表，存放变量、C 函数和用户自定义函数

  • 一个求值器，遍历程序并应用函数

来跑我们的第一个程序吧！！

现在还没有 lexer/parser，所以 AST 直接手工构造就行。

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

于是我把程序写好，输入 fib(5)。

然后……

崩了

升级内存分配器

原因？因为我们 fib(5) 创建出了13k个节点。但我们的分配器总容量仅为 1024 个节点！ 你可能会想：“好吧，很明显：重新分配内存块并扩大容量，把它变成一个动态数组” 问题恰恰就出在这里。事实是，我们所有的节点在这个内存块内部都指向彼此。 当我们以更大的尺寸进行 realloc 时，它可能会被移动到一个新的内存地址。 这会彻底破坏我们所有的指针，导致段错误！ 我们该如何解决这个问题？

与其扩展单个分配器，我们只需将多个内存块链接在一起即可！

我们可以构建一个已分配内存块的链表。当一个块空间用完时，我们只需分配一个新块并指向它！我们不需要移动任何数据！

这被称为 chunk 分配器！我们的每个块都是存储内存的 chunk，我们通过 next 指针将它们像链表一样串联起来。

typedef struct Chunk {
    Node nodes[CHUNK_SIZE];
    struct Chunk *next;
} Chunk;

我们可以跟踪第一个 chunk 以及当前正在从中分配内存的 chunk。

我们拥有：

  • Chunk 内存分配器（新增）

  • 一个 Environment 表，用于存储我们的变量、C 函数和用户自定义函数

  • 一个 Evaluator，通过递归遍历程序并使用 env 查找来对其进行归约

让我们再次执行我们的第一个程序

并且……

它成功了！

我们得到了结果 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+ GIGABYTES 的内存。

为什么？因为它会产生约 13 亿个节点。

每个节点占 48 字节，这意味着需要分配约 62.4 GB 的内存。

问题在于……

我们分配了节点，但在使用结束后从未释放它们。

为了解决这个问题，我必须实现一个垃圾回收器。

构建垃圾回收器

什么是“回收垃圾”？

基本上，我们需要清理掉程序中不再可达的节点。

当我们计算 1+1+1 时，求值器会执行以下操作：

    1. 构建 AST
      (+)
      / \
    (1) (+)
        / \
      (1) (1)
    1. 求值左侧。左侧已经是字面量，因此跳过，继续求值右侧。
    1. 右侧是一个函数，所以先求值它，并变更（mutate）树结构。
      (+)
      / \
    (1) (2)

那两个 1 怎么办？

它们仍留在分配器中！直到程序结束才会被释放！

我们需要垃圾回收器从根节点开始，标记所有仍然可达的节点。

请注意，当一个节点被求值为字面量后，它的旧子节点通过该节点就不再可达了！

我们可以这样做：一旦节点被变异为字面量，就将两个子节点设为 null。这样垃圾回收器就无法从图的这部分到达那些旧节点。

这称为标记阶段。垃圾回收器从根节点开始，标记它能到达的每一个节点。

标记完成后，让垃圾回收器遍历我们的内存块，检查未标记的节点，并将其加入名为 freeList 的链表。

现在，当我们需要新节点时，可以复用 freeList 中的节点，而不是分配新的内存。

只有当 freeList 为空时，才从当前内存块分配一个新节点。 否则，只需弹出头部并复用那块内存即可。

这样就有效地回收了节点！！

让我们应用 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) 的内存占用从 12 GB 降到了 1.7 MB

简直离谱。

但问题还没彻底解决。

fib 40 跑了整整 6 分钟才算完

为什么？

我们刚写完的这个 mark-and-sweep 垃圾回收器是 stop-the-world 的。

而我们跑的算法本身就是指数级复杂度。

所以内存问题是解决了。

但现在又冒出了性能问题。

这两个问题都有办法解决。

  • 可以实现一个并发垃圾回收器
  • 还可以在 fib 本身的求值方式上做文章

后续几篇会讲什么

这篇已经够长了，所以我决定拆成几个部分。

  • 如何用 TCO 和更优的求值方式解决速度问题
  • 实现 lexer/parser
  • 实现 FFI…
  • 实现 REPL
  • 抛弃指针解引用…
  • 在 C 里搞出蹩脚的封装
  • 实现 lambda 函数
  • 加入局部变量
  • 为 Cheney's copying collector 做准备

目前我们已经做到了什么？

  • 意识到表达式类型可以设计成 Algebraic Data Type。
  • 进而意识到各个 variant 就对应几类数据：函数、变量、字面量
  • 又意识到变量和函数本质上不是两种东西，它们都只是数据
  • 实现了一个图求值器，每次求值后就地修改当前节点
  • 用自研 hashtable 实现了环境表（Environment Table）
  • 实现了自定义的 chunk allocator 来分配节点
  • 发现积压了大量垃圾，于是实现了 mark-and-sweep 垃圾回收器

总的来说，我造出了一个 Graph Reduction 引擎

等等，它能算 1+1 吗

是的……我的意思是，现在可以了。

在 graphLang 中，1+1 确实等于 2！（´･ω･`）

总之，还有很多这里没提到的内容，全部都在仓库里。

原始来源： Hacker News

评论 (0)