只需1+1，我却造了门函数式语言
Needed 1+1, built a functional programming language
为了完成一个将算术表达式转换为二叉树的数据结构作业，我原本只想写个简单的求值器。结果一发不可收拾，几天后我用 C 语言实现了闭包、垃圾回收器、自定义内存分配器、REPL 以及 FFI 等全套功能，最终诞生了 graphLang 这门函数式编程语言。文章详细记录了从最初简单的二叉树求值，到发现 C 标准库缺乏哈希表而被迫手写，再到为了解决内存碎片和指针失效问题而设计 Arena Allocator 和 Chunk 分配器，最后为处理递归调用导致的内存爆炸而构建垃圾回收器的全过程。这是一个典型的从“小需求”滑向“大工程”的极客故事，展示了底层系统编程的魅力与挑战。
我们需要的不仅仅是一个能计算 1+1 的求值器，而是一个能让用户在不触碰 C 代码的情况下定义自己的函数的完整系统。
HN 评论区
75- CodesInChaos
Greenspun 编程第十定律：
> 任何足够复杂的 C 或 Fortran 程序，都包含一个临时的、非正式定义的、充满 bug 且缓慢的 Common Lisp 半实现。
- tromp
> 总的来说，我构建了一个图归约引擎
我也为我高性能的纯函数式编程语言 BLC/BLC2 的实现做过同样的事。
该实现仅 400 多行代码，包含一个用于组合逻辑的图归约引擎，lambda 演算程序通过 Kiselyov 的括号抽象算法转换而来。
- andai
我手头没有现成的，但在大学时，我在一个小组项目中负责 Excel 公式解析器。我为此纠结了大概六天，直到突然灵光一闪：我完全可以只做一堆字符串匹配，然后反复重写公式，直到它变成一个数字。
更准确地说，我已经搞定了如何解析 Excel 公式（我记得要处理大括号和逗号！）。至于实际的数学符号，我只需要把它们重写为 Excel 公式即可！
3+6*2 -> 3+MUL(6,2) -> ADD(3,MUL(6,2))
按优先级顺序处理。然后只需由内向外评估生成的公式：
ADD(3,MUL(6,2)) -> ADD(3,12) -> 15
结果不知怎么的，代码写了一千行。另一个做同样作业的同学告诉我，他用正则表达式只写了 50 行。
回想起来，我当时的做法就像是用螺丝刀去钉钉子。
后来我重新审视了这个想法（只做数学解析器，不加 ADD() 语法），体验好多了，大约 30 行 JS 代码（也不用正则！）。当然，用 eval 一行就能搞定，但那是另一回事了 :)
- gnarlouse
这让我想起几十年前……等等，我三年前还在写这种代码呢。
- ancientstraits
这篇关于“如何实现哈希表”的文章 https://benhoyt.com/writings/hash-table-in-c/ 对我帮助很大。我原本以为哈希表在 C 语言里基本上是不可能实现的，但这篇文章表明其实很简单。