★ FEATURED ARTICLE Caveman 这个项目的名字我在本地仓库里挂了大半年才真正动工。想法很简单像原始人一样不借助任何现成的解释器、编译器框架或语言运行时纯粹用手头的 C 语言把一个能跑起来的 Scheme 子集从零敲出来。它不是一个跟性能较劲的工程也不会成为谁的生产工具但它帮我彻底搞清楚了 REPL 背后那几件事——词法分析、语法解析、作用域和求值——到底是怎么一环扣一环的。如果你也一直想手写一个解释器却总觉得缺个切入点那这篇博客里从设计思路到踩坑记录的完整复盘应该能帮你省下不少自己摸索的时间。1. 项目定位与整体设计1.1 为什么叫 caveman一个故意做得原始的解释器名字起得很直白意思是这个项目像原始人用石器一样只用最基础的材料干活。我给自己定了三条规矩第一不参考其他解释器的源码第二不引入任何第三方库全部用 C 标准库完成第三代码量控制在 1500 行以内保证每一行我都能看懂、能解释、能重新写出来。这个故意原始的定位决定了功能取舍。我按能不能用 10 分钟讲清楚实现原理这个标准给特性列了一张表功能状态说明整数四则运算支持只做 long 范围内的整数define / lambda / if / begin支持Scheme 的核心特殊形式car / cdr / cons / list支持列表操作配合 quote 使用比较运算 支持底层是 C 的比较浮点数、字符串、字符不支持明确报错不搞半吊子宏、call/cc、尾调用优化不支持作为后续扩展方向砍掉这些东西不是偷懒而是为了聚焦。宏和 call/cc 涉及求值顺序和执行上下文的重构对一个目标是读懂求值原理的项目来说它们是干扰项。我见过不少新手一上来就想写完整 Scheme结果被call/cc卡住连 REPL 都没跑通。Caveman 的哲学是先让核心闭环转起来再谈别的。1.2 为什么选 C 语言而不是 Python 或 Rust很多人学解释器会用 Python因为 Python 本身动态类型、写起来快。但我刻意选了 C理由有三层。第一C 没有隐藏在背后的运行时。用 Python 写解释器列表、字典、字符串都是语言自带的高层结构很多求值过程中数据长什么样的细节被藏住了。C 里一个节点就是一个结构体一个变量就是一个内存地址你被迫面对数据到底存在哪里这个问题。第二Scheme 和 C 在理念上正好互补。Scheme 的 S-表达式天然就是树形结构而 C 的结构体加指针恰好就是描述二叉树的经典工具。一边教你用递归表达结构一边教你用指针管理数据两者结合非常顺。第三也是我个人的私心C 代码里拿到一个指针就能printf出来看调试路径最短。这对一个需要反复确认这句求值到底走到哪一步的项目来说太重要了。如果非要说缺点C 的动态内存管理确实是坑。这个问题我在第 5 节会详细讲这里先说结论对玩具解释器用 arena 分配器把内存分配做成只增长、不释放比精雕细琢地做 GC 靠谱得多。1.3 架构总览一条尽可能短的流水线这个项目的核心流程可以用一行字概括源码字符串 - token 流 - S-表达式树 - 求值器 - 打印结果简化到极致解释器就是这条流水线。每一步的输入输出都很清晰词法分析器吃进(define x 1)吐出几个 token读取器把 token 拼成树求值器拿着树和环境做计算最后打印函数把节点变成人眼能读的文本。为什么要保持这条流水线短因为解释器的调试难点在于定位。如果一条请求要穿过二十个模块才出结果出错时你得在二十个地方找原因。Caveman 把模块控制在 5 个以内任何一个输入都能手动追踪到底。我曾经为了排查一个闭包错误全程手工模拟求值了 20 步最后定位到 lambda 节点没保存环境——这么笨的方法正因为流水线短才真的可行。2. 词法与语法让文本变成树2.1 词法分析器最小的状态机词法分析器是整个项目里最不需要动脑、但最需要耐心的部分。它的任务是把原始字符串拆成四类 token左括号、右括号、符号、数字。Scheme 没有运算符优先级这个概念所以词法分析可以非常简单typedef enum { TOKEN_LPAREN, TOKEN_RPAREN, TOKEN_SYMBOL, TOKEN_NUMBER, TOKEN_EOF } TokenType; typedef struct { TokenType type; char text[64]; } Token; Token next_token(Source *src) { int c; do { c next_char(src); } while (c || c \n || c \t); if (c () return (Token){TOKEN_LPAREN, }; if (c )) return (Token){TOKEN_RPAREN, }; if (c EOF) return (Token){TOKEN_EOF, }; int n 0; while (c ! EOF c ! c ! \n c ! \t c ! ( c ! )) { if (n 63) tok.text[n] c; c next_char(src); } tok.text[n] 0; tok.type is_number(tok.text) ? TOKEN_NUMBER : TOKEN_SYMBOL; return tok; }这里有一个刚开始容易忽略的细节读取器reader需要向前看一个 token来判断)是否出现。我的做法是在 Source 结构里加一个整型标志位保存上一个读取的字符实现一个unget_char。更省事的办法是 reader 先调peek_token内部记住上一次读取的 token下次next_token时先返回缓存的。两种方式都行我选择后者因为它把向前看封装到了 token 层reader 的代码更干净。关于is_number我最初用的是atoi 全部字符都是数字双重判断但后来发现123abc这种串会被atoi静默截断成 123造成无穷无尽的困惑。最终的实现是先判断首字符是数字或负号再用strtol解析并检查结束指针是否落在字符串末尾。这才算真正识别了一个完整的数字。2.2 S-表达式读取器用递归下降拼树读取器的输入是 token 流输出是一棵由节点构成的树。核心规则只有两条(开一个新列表读到对应的)结束列表其余 token 变成叶子节点。完整的递归下降实现如下Node *read_expr(Source *src) { Token t next_token(src); if (t.type TOKEN_LPAREN) { Node *dummy make_cons(NULL, NULL); // 哨兵节点避免特判空列表 Node *tail dummy; for (;;) { Token peek peek_token(src); if (peek.type TOKEN_RPAREN) { next_token(src); // 吃掉右括号 break; } if (peek.type TOKEN_EOF) { error(unexpected EOF in list); } Node *item read_expr(src); tail-u.cons.cdr make_cons(item, NULL); tail tail-u.cons.cdr; } return dummy-u.cons.cdr; } if (t.type TOKEN_NUMBER) return make_num(atoi(t.text)); if (t.type TOKEN_SYMBOL) return make_sym(dupstr(t.text)); error(unexpected token); }这里最值得讲的是哨兵节点dummy head的用法。如果不加哨兵每次追加列表元素都要判断这是不是第一个节点是的话要把头指针指过来不是的话要顺着链表走到尾部。哨兵直接把这个问题消掉了——dummy 的 cdr 永远是当前链表的最后一个节点追加操作统一为在 token 末尾接一个新节点。这个技巧不是 Caveman 发明的但它确实是写递归 reader 时最顺手的一种结构。另外我特意在解析到 EOF 时设置了明确报错。不加这一行括号不匹配的输入会让read_expr一路递归下去直到段错误错误提示是Segmentation fault完全没法定位。加上之后用户会看到unexpected EOF in list十秒钟就知道哪里少了右括号。2.3 解析阶段三个容易踩的坑第一个坑是 token 缓存和unget的顺序问题。如果你在 reader 里先调peek_token又调next_token必须保证缓存只保存一份。我最初在peek_token里调用next_token存缓存下次next_token直接返回缓存逻辑上没问题但一旦有两处同时需要向前看两个 token缓存就不够用了。好在这个项目的语法只需要向前看一个 token一旦发现需要两个就说明语法设计超标了。第二个坑是数字识别和负数。Scheme 的-1是合法数字而-本身又是减法符号。我的处理器把-后面紧跟数字的 token 识别为数字否则识别为符号。这导致(- 1 2)里的-和(-1)里的-1被正确处理但如果用户写了(- -1)词法器能正确产出减号和负数求值器也能算对——前提是测试用例里必须覆盖这种边缘情况。第三个坑是dupstr的内存归属。读取器从 token 里拷贝出字符串给符号节点表面看没问题但如果你图省事直接让符号节点指向 token 内部的text数组下一次读取 token 就会覆盖之前的内容所有符号都变成同一个字符串。Caveman 一开始犯过这个错表现是(define x 1)跑完后再去查x发现 x 指向的字符串变成了别的符号。这个问题的修复很简单就是每个符号节点都有一份自己的字符串拷贝。3. 求值器整个解释器的核心3.1 环境模型一串简陋但清晰的作用域链求值器是整个项目的心脏而环境environment是求值器的骨架。我选择了最简单的链表式环境每个环境节点保存一个变量名 - 值的绑定并指向它的父环境。typedef struct Env { struct Env *parent; char *key; Node *val; } Env; Env *env_extend(Env *parent, Node *params, Node *args) { Env *e calloc(1, sizeof(Env)); e-parent parent; e-key params-u.sym; e-val args; return e; } Node *env_lookup(Env *e, const char *key) { while (e) { if (strcmp(e-key, key) 0) return e-val; e e-parent; } error(unbound symbol: %s, key); }这个模型的查找复杂度是 O(深度)对玩具项目完全够用。但它有一个重要的设计含义词法作用域。lambda 节点在创建时必须保存定义时环境的指针而不是在调用时才看调用者的环境。这个区别我在第 4 节的闭包案例里会实际演示这里先记住结论Caveman 的NODE_LAMBDA节点里有一个env字段保存函数诞生那一刻的环境。用生活类比解释环境链它像一排套在一起的柜子。你在最里层柜子里找钥匙找不到就往外一层找一直到最外层。每打开一个 lambda 就是在最里面套一个新柜子柜子之间是独立的但都能看到外面的柜子。3.2 特殊形式与函数调用顺序决定一切Scheme 的求值规则很朴素遇到列表先求值函数位置再从左到右求值所有实参最后调用函数。但这条规则对特殊形式不成立——if的两个分支不能同时求值define的第一个参数不能当表达式求值quote后面整个子表达式只能是数据。所以eval的入口处要先检查当前列表头部的符号是不是特殊形式Node *eval(Node *expr, Env *env) { switch (expr-type) { case NODE_NUM: return expr; case NODE_SYM: return env_lookup(env, expr-u.sym); case NODE_CONS: { Node *head expr-u.cons.car; if (head-type NODE_SYM) { if (!strcmp(head-u.sym, quote)) return quote(expr, env); if (!strcmp(head-u.sym, if)) return eval_if(expr, env); if (!strcmp(head-u.sym, define)) return eval_define(expr, env); if (!strcmp(head-u.sym, lambda)) return eval_lambda(expr, env); if (!strcmp(head-u.sym, begin)) return eval_begin(expr, env); } return apply(expr, env); } } error(bad expression); }以if为例标准的实现是先求值条件根据条件真假只求值对应分支。如果在apply里统一求值实参(if #t 1 (error boom))这种表达式就会在条件为真时仍然执行错误分支整个语言就废了。这是写解释器的人最容易犯的错误之一把特殊形式当成普通函数处理。define的实现也值得一提。它需要先求值第二个子表达式然后把绑定写进环境。这里有个顺序陷阱如果先查找define后面的变量名而这个名字尚不存在env_lookup会直接报错。正确做法是把 define 的名字和值分开处理——名字不查环境直接插入值求完后存储。3.3 内置函数让语言真正能干活的最后一公里没有内置函数Scheme 只能做语法演示。我实现了最常用的一组 - * / car cdr cons null? eq?。Node *builtin_add(Node *args, Env *env) { long sum 0; for (Node *p args; p; p p-u.cons.cdr) { sum p-u.cons.car-u.num; } return make_num(sum); }内置函数的统一签名是Node *(*BuiltinFn)(Node *args, Env *env)把实参列表和当前环境都传进去。这样设计的好处是后续如果要给内置函数加上对k之类的特殊支持签名不用改。car和cdr的实现更简单就是返回列表的第一个元素和剩余部分。真正需要小心的反而是cons它的参数是两个任意表达式返回值是一个新列表节点。我最初写的cons返回了新节点但忘了把cdr指向第二个实参导致(cons 1 2)得到(1)而不是(1 . 2)。这种错误单看代码很难发现打印结果出来才恍然大悟。3.4 让 REPL 跑起来读取-求值-打印的循环所有模块都打通之后最后一个活就是把它们串成一个 REPL。这里我又踩了一个移植性的坑最初用fmemopen把用户输入的一行字符串包装成FILE*然后喂给 tokenizer。在 Linux 上跑得很欢换到 macOS 才发现fmemopen的行为不一致。最终我改了 tokenizer 的接口让它直接吃一个const char *指针自己维护游标位置——既去掉了 FILE 依赖又让程序更容易单测。最终的main循环不到三十行打印提示符用fgets读一行调 tokenizer 和 reader调 eval最后调print_expr把结果打印成可读的 S-表达式。这里我说一个实用建议print_expr一定要在第一版就写好而且要用递归遍历完整棵树。没有打印函数你看不到任何中间结果有了它每次求值你都能立刻看到结构对不对。Caveman 的print_expr是从把数字打印出来开始的然后逐级支持符号、列表、lambda大概花了二十分钟但之后所有调试都靠它这二十分钟的回报率极高。4. 实操演示从斐波那契到闭包4.1 第一个有意义的程序递归求阶乘REPL 跑通后我随手试了试经典的递归阶乘caveman (define fact (lambda (n) (if ( n 2) 1 (* n (fact (- n 1)))))) caveman (fact 10) 3628800看到输出的一瞬间前面的所有工作都有了意义。为了确保不是碰巧我又跑了(fact 100)结果溢出了——这是预期行为因为我只支持 long 范围内的整数。Caveman 能报出溢出错误而不是静默回绕是因为我在实现*时用了带溢出检查的乘法。别小看这个细节一个玩具解释器的崩溃方式越接近真实语言你越愿意用它。这里有个理解递归的关键点define把fact的绑定写入全局环境之后 lambda 内部引用fact时顺着环境链能查到自己的名字于是递归就自然成立了。如果用let实现局部绑定而不是define整个逻辑会更绕——这也是我选择保留最简define的原因。4.2 闭包与高阶函数捕获的不是值而是整个环境阶乘是热身闭包才是检验解释器设计的试金石。我测试了经典的加法器工厂caveman (define adder (lambda (x) (lambda (y) ( x y)))) caveman (define add5 (adder 5)) caveman (add5 3) 8这个结果正确表示我的 lambda 确实保存了定义时的环境。如果我在apply里用了调用者环境那么add5被调用时只能看到全局环境找不到x会直接报unbound symbol: x。很多人写解释器时在这关翻车就是因为少了NODE_LAMBDA里保存环境这一步。我还见过一种更隐蔽的错误保存环境时保存成了指针但环境在函数返回后被释放了。Caveman 用 arena 分配器所有环境节点都放在一个不回收的内存池里天然规避了这个问题。这里我强烈建议玩具项目不要一开始就做环境的内存释放释放逻辑的错误率远高于你的想象而 arena 的代价只是程序退出前多一点内存占用。4.3 性能观察慢得明明白白我对性能做了一个粗略测量(fib 27)在 Caveman 里大约需要 1 秒出头而 Python 用同样朴素的递归实现大约 0.2 秒。这个差距完全在意料之中主要瓶颈有三个符号查找是字符串strcmp线性扫描节点分配没有特别优化递归求值每一层都有大量函数调用开销。慢不是问题问题是你要知道慢在哪里。我打开-pg编译了一次看到strcmp占了将近一半的时钟于是把符号比对在常用路径上做了一点优化——把符号节点里保存的字符串长度提前存好长度不等直接不看内容。性能提升了大概 30%代码量只增加了十几行。这个经验说明在意性能之前先量化性能量化之后每一行优化都有效果。5. 常见问题与排查技巧实录5.1 段错误的定位从懵了到有章法Caveman 开发过程中段错误应该出现了不下十次。最开始的两次我全程靠printf猜位置效率低得吓人。后来我给自己定了三个习惯一是所有节点构造函数里给节点类型赋初值防止读到未初始化内存二是在 eval 的入口处打一行调试日志打印当前表达式三是给env_lookup的报错加上符号名而不是笼统地说symbol error。这三个习惯让段错误的定位变成三步先看打印到哪一句确认是解析还是求值挂的再看报错符号是什么缩小到某个名字最后看核心转储的 backtrace找到具体函数。实测下来平均两分钟能定位一个段错误。如果想更省事可以在编译时加-fsanitizeaddress地址越界会直接变成可读的错误报告代价是编译产物跑得慢一点调试期完全能接受。5.2 闭包环境的经典陷阱变量被吞掉我最惨痛的一次调试经历是(adder 5)返回后x变量仿佛被吞掉了。错误现象是add5调用时报unbound symbol: x。排查过程让我把闭包原理彻底过了一遍。问题出在我最初实现apply时直接用了调用者环境作为函数体的父环境而不是 lambda 创建时保存的环境。修复一行代码就完成把bind_params的第三个参数从caller_env改成fn-u.lambda.env。但这一行的理解深度决定了你能不能写出正确的解释器。闭包不是函数记住了某个值而是函数记住了它诞生时的整个作用域链——那是一个链表不是快照。5.3 递归深度与 C 栈的硬边界Caveman 是递归求值的所以 Scheme 的深层递归会耗尽 C 的调用栈。测试(count 100000)这种递归程序大概率以段错误收场。这不是 bug而是递归解释器的天然限制。想绕开这个限制最直接的办法是写一个跳床trampoline把所有递归调用改写成返回到一个循环里继续执行的数据结构。但这对 Caveman 的架构改动太大v1.0 我选择接受限制在文档里写明递归深度建议在 1 万层以内。如果你想做得更彻底尾调用优化是性价比最高的升级让函数体的最后一个调用不压栈而是复用当前调用帧。这个方向列在我第 6 节的路线图里。5.4 快速排查速查表现象可能原因排查入口读入(if #t 1 2)段错误没处理布尔字面量#t被当符号查找在 eval 里对未知符号报错而不是返回 NULL递归 10 万层崩溃C 栈耗尽无尾调用优化换用跳床/限制深度闭包拿到全局环境而不是捕获值lambda 节点没保存定义时环境检查apply里bind_params的父环境参数打印数字全是 0构造数字节点时没给 union 成员赋值检查make_num括号不匹配时崩溃reader 没检测 EOF在read_expr里对 EOF 明确报错符号值不断变化符号节点直接引用 token 内部缓冲区改为在make_sym里dupstr拷贝一份这张表是我实际踩坑的浓缩。每一个问题都不是算法难题而是结构体字段没对或接口设计没考虑边界这类工程细节。写解释器最大的收获之一就是学会系统性地排查这类问题。6. 后续扩展空间与个人体会6.1 我计划中的功能路线图Caveman 的核心闭环完成后我列了一张升级路线图按性价比排序第一优先级是符号哈希表。把环境查找从线性扫描变成哈希查找性能能提升一整个数量级代码量增加不多。第二是尾调用优化打开深层递归的大门让这个语言能真正跑一些递归算法。第三是字符串与浮点数支持补全基础数据类型的半壁江山。第四是 mark-sweep GC把 arena 替换成真正的内存回收机制这也是从玩具走向有内存管理概念的一步。第五才是宏和call/cc它们会重构求值器的设计我打算等前四项都完成后再动手。这个顺序的关键是每一步都用得上前一步的成果而不是一口气全做完。我见过太多人把路线图画得很大最后连 REPL 都没跑通就放弃了。一次只加一个特性每个特性都配合测试是我从这次经历里得到的最重要的工程建议。6.2 如果再写一遍我会改变的三件事第一我会在一开始就用 arena 分配器而不是先写malloc/free。Caveman v1.0 前几版混用了两种内存策略出现了一堆该 free 还是不该 free的纠结。用 arena 之后内存问题几乎从我的调试清单里消失了。第二tokenizer 会直接设计成吃字符串指针而不是靠 FILE 流。最初用fmemopen的移植性问题浪费了我整个晚上。虽然问题不大但这类平台差异的坑和解释器本身无关能避开就避开。第三解析和求值会从一开始就分层写测试。我最初是手工在 REPL 里敲用例后来补了自动化测试发现三个隐藏的回归问题。如果早点写测试这三个问题能提前半天暴露。最后分享一个个人体会写完 Caveman 之后再回头看《计算机程序的构造和解释》第四、五章很多以前看不进去的段落突然通顺了。看别人写的解释器总有一种这也没什么的错觉等你自己动手把每一层剥开、缝合、调通才知道其中每一句都有存在的理由。如果你也想学解释器我真心建议从这种几百行的最小骨架开始别被网上那些上千行的完整实现劝退——先把闭环跑通后面的一切都来得及这个项目的源码我放在仓库里了注释写得很啰嗦因为我知道半年后自己肯定还会回来看。
阅读完成 · 觉得有帮助？
