在 Lisp 方言的生态中，实现一个既轻量又高效的解释器始终是技术挑战。femtolisp 由 Julia 语言创始人 Jeff Bezanson 创建，仅用约 150KB 代码实现了完整的 Scheme 方言解释器，其核心设计哲学是 “以最少的代码实现最强大的功能”。本文聚焦 femtolisp 的两项核心技术 —— 压缩式垃圾回收（GC）与词法作用域 —— 剖析其实现细节并提取可落地的工程参数。
压缩式 GC：Cheney 半空间收集器
femtolisp 在其 tiny 子目录中采用了一种极为简洁的压缩式 GC 策略，即 Cheney 半空间收集器。与传统标记 - 清除算法不同，这种设计将堆划分为两个等大的连续空间 ——from-space 和 to-space，收集过程同时完成垃圾回收与内存压缩。
核心工作机制包含三个步骤：首先交换 from-space 与 to-space 的指针，将分配指针重置为新 to-space 的起始位置；然后遍历所有根对象（VM 栈、全局变量及隐式根），调用 relocate 函数将它们搬迁到 to-space；最后执行 Cheney 扫描，在 to-space 中线性遍历已搬迁对象，递归处理其所有指针字段直到扫描指针追上分配指针。这种广度优先的遍历确保每个活跃对象仅被复制一次，且最终在 to-space 中连续排列。
relocate 函数的设计是整个 GC 的关键。对于每个值 v，它执行以下判断：若 v 是立即数（fixnum、字符等）则直接返回；若 v 已位于 to-space 说明已被处理；若 v 位于 from-space 且尚未设置转发指针，则在 to-space 分配同大小空间，复制对象头与字段，并在原位置写入转发指针指向新位置；若已存在转发指针则直接返回新位置。这种双重检查机制避免了重复复制，同时通过在对象头部嵌入转发信息实现了高效的地址更新。
从工程角度审视，femtolisp 的 GC 设计提供了几个重要参数：堆空间通常建议设置为最大活跃内存的 2 倍以容纳完整的 from-space 和 to-space；由于采用 bump-pointer 分配策略，分配操作仅涉及指针递增，时间复杂度为 O (1)；压缩特性消除了内存碎片，无需维护空闲链表。代价在于峰值内存需求是活跃数据的 2 倍，且所有堆引用必须通过 tagged value_t 类型封装，以便 GC 能够识别指针与立即数。
词法作用域与 Lisp-1 设计
femtolisp 采用词法作用域（lexical scoping）并遵循 Lisp-1 语义，即函数与变量共享同一命名空间。这种设计使得函数闭包能够正确捕获其定义时的词法环境，同时保持语言语义的简洁性。
在实现层面，femtalisp 的词法作用域通过环境链（environment chain）结构维护。每当进入一个新的词法作用域时，会创建一个新的环境帧，其中包含当前作用域的变量绑定，并指向父级环境。变量查找时从当前帧开始，沿环境链向上搜索，直到找到匹配的名字或抵达顶层。这种结构天然支持闭包 —— 当函数被创建时，它捕获创建时的环境链，后续调用时在该捕获的环境中查找自由变量。
femtolisp 的特殊形式仅需 12 个，内置函数仅 33 个，却实现了完整的 Scheme 语义。这得益于词法作用域的简洁实现：无需像动态作用域那样维护全局关联列表，变量绑定的生命周期与词法作用域紧密耦合，GC 能够安全地回收不可达的环境帧。
尾调用优化的工程实现
femtolisp 实现了 proper tail recursion，即尾调用优化（TCO）。这一特性对于函数式编程至关重要，允许无限递归而不导致栈溢出。其实现方式相对直接：在解释器中维护一个标志位，记录当前是否处于尾位置。当函数调用出现在尾位置时，解释器不创建新的栈帧，而是用新函数的参数替换当前帧的内容并跳转执行。这种设计使得尾递归调用在语义上等价于迭代，但在代码层面保持递归的结构清晰度。
从工程参数角度看，尾调用优化需要确保：调用点分析准确识别尾位置；栈帧布局允许参数的高效传递；解释器循环能够正确处理尾调用标志。建议在实现时为每条指令增加 tail_position 属性，编译器生成代码时自动标记尾调用位置。
实践建议
基于 femtolisp 的设计经验，若要实现轻量级 Lisp 解释器，可遵循以下工程清单：GC 方面，采用半空间压缩式收集器时，堆大小设为预期活跃内存的 2 倍，使用 tagged pointer 区分指针与立即数，实现 relocate 函数时注意转发指针的设置时机；词法作用域方面，使用环境链结构维护嵌套作用域，确保闭包捕获创建时的环境而非调用时的环境；尾调用方面，在解释器循环中增加尾位置标志，尾调用时复用当前栈帧。
femtolisp 的设计证明，轻量级实现并不意味着功能残缺。通过精心选择的核心特性集合 —— 压缩式 GC、词法作用域、尾调用优化 —— 可以在极小的代码量内构建出功能完整且高效的 Lisp 解释器。这种设计思路对于嵌入式脚本引擎、教学用解释器或领域特定语言实现都具有重要的参考价值。
参考资料：
- femtolisp 官方仓库：https://github.com/jeffbezanson/femtolisp
- tiny 子目录 GC 实现：https://github.com/JeffBezanson/femtolisp/blob/master/tiny/lisp.c