Hacker News 中文摘要

RSS订阅

为了算 1+1，我造了一门函数式编程语言 -- Needed 1+1, built a functional programming language

原文链接 | HN讨论 | 2026-09-30 17:48:29

我被分配了一个数据结构相关课程中的任务。这个任务最初只是要求实现最简单基础的运算功能，例如计算出 1+1 的结果，但在实际动手时，我竟然逐步构建出了一门函数式编程语言。

正文

我接到的数据结构题是把算术表达式转成二叉树。自然，我决定做一个求值器。几天后，我用 C 实现了闭包、垃圾回收器、自定义内存分配器、REPL、FFI，还有一堆别的东西。仓库在 graphLang。

数据结构作业

题目是：用二叉树求 1 + 1 + 1 等于 3。

怎么做到？先建树：

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

操作符成为根，两个操作数成为子节点。然后求值这棵树。先求根的左操作数。它是另一个 + 表达式，所以必须先塌缩成一个值，外层 + 才能执行。

(+) / \ (2) (1)

然后再求值一次。结果是 3。这相当于做 (+ (+ 1 1) 1) -> (+ 2 1) -> 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、Mul、Div 也一样。它们都接收两个表达式并产生一个表达式。那么求值器为什么要在意操作是 Add、Sub、Mul 还是 Div？似乎不需要。于是表达式可以表示成：Expr ::= Func Expr Expr | Val。求值器不需要知道函数做什么，只需要知道如何应用一个函数。

我们可以加变量。改动不会很大

变量不过是一次哈希表查找，返回一个 Expr。但 C 没有内置哈希表。

嗯……那就实现一个哈希表吧，小改动。怎么做？我之前没实现过。像原始人一样 Google，找到一篇很棒的文章：How to implement a hash table (in C)。于是 Expr 有了小改动：Expr ::= Func Expr Expr | Val | Var。现在变量可以在求值后传给函数，就像 (+ 1 1) 一样。

真正在 C 里实现

好，按计划写 C。看起来够简单，就是个 tagged union。定义枚举 LITERAL、VAR、FUNC；Node 有 left、right 指针；一个 union，包含 int literal、char *var、char *func；再加 NodeType type。

在 64 位系统上，每个节点大小是：左指针 8 字节，右指针 8 字节，data 8 字节，type 4 字节，padding 4 字节，总共 32 字节。32 字节听起来不多，但看用途：求 1+1 需要 3 个节点，一个操作符、两个操作数，32 x 3 = 96 字节。问题是，在我的系统上 malloc 一个节点会加元数据，占 16 字节。每节点变成 32 + 16 = 48 字节。求一个 (+) 的 3 个节点就要 144 字节。

而且我们会做很多小分配。需要更好的分配节点方式。显然要自定义分配器。像原始人一样查资料后，决定写 Arena Allocator。

Arena 分配器

Arena 分配器思路简单：一开始拿一大块内存，自己分配，最后把整块释放。我的 Arena 分配器差不多就是 #define SIZE 1024，Node arena[SIZE]。分配节点时用 int top = 0 追踪，返回 &arena[top++]。写分配器，定义 C 函数 Node *allocNode();。很好，接着实际调用函数。

然后我意识到：变量和函数可以放在同一个环境里！这意味着函数也可以是值。记得之前那个哈希表吗？该升级它了。

制作环境表

环境表存两样东西：变量和函数。但对求值器来说，函数就是一侧吃参数、另一侧吐出结果的东西。

最初的想法是函数只是指向 C 函数的指针。看起来够简单。但有个大问题：用户怎么写自己的函数？

还有一个问题。用户在语言里输入代码，不可能神奇地变成原生 C 函数指针。它只能构建 AST。如果函数只是 C 指针，它们立刻变成不透明值。函数返回另一个函数时怎么办？我们需要能把那个函数放回图里，稍后求值。但 C 函数指针不是求值器能遍历的东西。

所以需要一种节点告诉求值器：“我是函数，但我的代码不是 C 指针，而是这棵树。”它需要把函数体存为树，以便求值器分多步求值。对我们来说，这就是闭包表示。闭包不是黑盒 C 函数，而是图里的实际节点。一边是参数，一边是操作树（函数体）。（技术上闭包还有环境，但还没做到局部变量。）把函数变成实际节点后，就可以传递它、从其他函数返回它、随时逐步求值它。这样用户就能定义自己的函数，而不用碰 C 代码。

好，用 C 实现。需要什么？如果变量和函数都是值，环境就需要把名字映射到节点。EnvEntry 结构有 char *key; Node *val; struct EnvEntry *next;。哈希表把名字（key）映射到 Node *（值）。但 val 是什么？val 是 Node。可我们的 Node 还不知道闭包或原生函数。于是给 Node 定义加上：union 里增加 int index; char *call; struct Node *closure; struct Node *nativeFunc; 等。nativeFuncs 是代表 C 函数的节点；closures 是用户定义的函数，由节点组成。原生函数 = 不透明的 C 实现；闭包 = 语言级图表示。

现在组件齐了： * 一个内存分配器 * 一个环境表，保存变量、C 函数和用户定义函数 * 一个求值器，遍历程序并应用函数

执行第一个程序吧。现在还没有 lexer/parser，所以手工构造 AST。测试什么程序好？当然是斐波那契。于是写程序，输入 fib(5)。

然后……它崩溃了。

升级内存分配器

为什么？因为 fib(5) 生成了 13k 个节点，而分配器总共只有 1024 个节点。你可能想：“很明显，重新分配块，增大尺寸，做成动态数组。”问题就在这里。我们所有节点都指向这个内存块内部。realloc 增大尺寸时，块可能移到新地址，所有指针全坏，段错误。

怎么解决？不要增长一个分配器，而是把多个块链起来。建一个已分配块的链表。一个块空间用完，就分配一个新块并指过去。不用移动任何数据。这叫 chunk allocator。每个块存节点，用 next 指针链成链表。定义 Chunk { Node nodes[CHUNK_SIZE]; struct Chunk *next; }。追踪第一个块和当前正在分配的块。

现在有： * 一个新的 Chunk 内存分配器 * 一个环境表，保存变量、C 函数和用户定义函数 * 一个求值器，递归遍历程序，用环境查找来归约

再次执行第一个程序……

它成功了！结果是 5。3 + 2 = 5。

但奇怪的事发生了。它用了 1.32 MB 内存。fib(5) 不复杂。于是运行 fib(10)，用了 40 MB。好吧，这很奇怪。测试一下，跑基准。

RAM 对 fib(n) 大致是：fib(40) 在崩溃前用了 12+ GB，然后 OOM。为什么？它生成约 13 亿个节点。每节点 48 字节，约 62.4 GB 的节点分配。问题是：我们分配节点，但用完后从不释放。

要解决这个问题，必须构建垃圾回收器。

构建垃圾回收器

收集垃圾是什么意思？基本上，要摆脱程序再也无法到达的节点。

求值 1+1+1 时，求值器这样做： 1. 构建 AST。 2. 求值左边。左边已经是字面量，继续右边。 3. 右边是函数，所以先求值它。然后变异树。

但原来那两个 1 会怎样？它们留在分配器里，直到程序结束才释放。

我们需要 GC 从根开始，标记每个仍能到达的节点。注意，当一个节点被归约为字面量，它原来的子节点就不再能通过该节点到达。我们可以在变异为字面量后，把两个子节点置空。这样 GC 永远无法从图的这部分到达旧节点。这叫标记阶段。GC 从根开始，标记每个可达节点。

标记完成后，GC 遍历所有块，检查节点是否未标记，把它加入一个叫 freeList 的链表。需要新节点时，复用这些节点，而不是再分配。freeList 为空时，才从当前块分配新节点。否则弹出头部复用内存。这样就能有效回收节点。

应用 GC 后再跑基准：fib(40) 的内存从 12 GB 降到 1.7 MB。很疯狂。

但问题还没完全解决。fib(40) 求值花了 6 分钟。为什么？刚完成的 mark-and-sweep GC 是 stop-the-world GC。而且我们运行的算法本身是指数级。内存问题解决了，现在有了性能问题。两者都可以处理：实现并发 GC；以及改进 fib 本身的求值方式。

下一部分会讲什么

这已经够长了，所以我决定拆成几部分： * 如何用 TCO 和更好的求值解决速度问题 * 实现 lexer/parser * 实现 FFI…… * 实现 REPL * 从指针解引用切换…… * 把粗糙的封装带进 C * 实现 lambda 函数 * 添加局部变量 * 为 Cheney 的复制收集器做准备

目前完成了什么

  • 意识到表达式类型可以是代数数据类型。
  • 然后意识到实际变体是数据的种类：函数、变量、字面量。
  • 然后意识到变量和函数不是两种不同东西，都只是数据。
  • 实现了图求值器，求值后变异当前节点。
  • 用自定义哈希表实现了环境表。
  • 实现了自定义 chunk 分配器来分配节点。
  • 意识到留了大量垃圾，实现了 mark-and-sweep 垃圾回收器。

总体上，我构建了一个图归约引擎。

等等，它能算 1+1 吗

能……我是说，现在能了。按照 graphLang，1+1 确实是 2！还有更多东西没写在这里，都在仓库里。

评论

社区整体赞赏从零实现语言解释器的探索式写作，并分享诸多类似项目与历史资源，少数人针对原帖的内存管理与垃圾回收提出了具体优化质疑。

认为边做边改的写作风格降低了底层实现门槛

  • 读者觉得作者暴露问题再解决的叙述方式亲切，原本以为在 C 里做哈希表或语言解释器很难，实际文章展示比想象简单（较多人） > 喜欢这种“做一件事→搞砸→循环”的阐述风格，图归约也就是求值（@winwang）

分享自己实现的图归约引擎与旧文资源

  • 有开发者表示自己也在数百行内写出了包含组合逻辑图归约引擎的函数式语言实现；另有人补充了1999年讲解 Perl 内含 lambda 演算的演讲以及用 C 写哈希表的教程，认为对理解很有帮助（较多人） > 我也在四百多行里实现了纯函数式语言的图归约引擎，lambda 程序通过括号抽象算法转为组合逻辑（@tromp）

指出原帖的内存与垃圾回收设计可优化

  • 针对 realloc 导致指针失效和斐波那契指数爆炸的问题，建议用 arena 数组索引代替指针以省内存，并采用复制式收集器应对大量临时垃圾，同时质疑原帖“改进 fib 求值”的表述模糊（少数人） > 可用 arena 数组索引代替指针，斐波那契活对象很小，适合复制式收集器（@Joker_vD）

自创语言实验与老程序员共鸣

  • 有人展示过一切皆对象、纯消息传递的语言原型，有人回忆少年时造深奥编程语言的乐趣，另有读者共鸣深陷无谓查询优化兔子洞的经历（少数人） > 我曾发明一种一切皆对象、无关键字的语言，向1发送加号得到可加1的对象（@herodotus）

有价值的补充

  • 任何足够复杂的 C 或 Fortran 程序都包含一个临时拼凑、bug 频出且缓慢的半套 Common Lisp 实现，此即 Greenspun 第十规则（@CodesInChaos）
  • 原帖博客页面可能 404，有读者提供了实际可访问的博客地址（@vivzkestrel）
  • 测试垃圾回收器在大活对象集表现的基准可写成递归返回二元组的结构，而非原帖的指数斐波那契（@Joker_vD）
  • 1999 年就有演讲展示 Perl 程序如何包含 lambda 演算，说明这类底层探索历史悠久（@gbacon）