我兼职写 Lisp 编译器，聊聊这件事

我找了份兼职写 Lisp 编译器，所以就来聊聊这个。如果你不编程，这篇可能不太好懂。就算你编程，可能也不太好懂。需要不少背景知识。

你也许对 Lisp 的印象来自大学里用过几个学期的 Scheme 解释器。你也许会觉得它“很优雅，但日常用起来不太实际”。你也许会觉得它是“一门解释型语言”，所以不明白我说的 Lisp 编译器是什么意思。如果你没有这些想法，大概可以直接跳到下一节。

在 Lisp 里，与某些语言不同，语义基本上是围绕解释构建的。当你把一些代码交给 Lisp 解释器时，它会一步一步地遍历并执行。这就要求谨慎执行。比如说，一个像 (defun foo (x) (+ x 237)) (foo "hello world") 这样先定义一个加法函数、然后拿一个字符串去调用它的程序，你自然会期望它做些体面的事，比如弹出调试器，而不是返回垃圾数据。

但这样通常也很慢。解释器必须对所有可能的输入都做处理。比如它没法很好地把 FOO 优化成只接受一个数值参数放进寄存器，因为之后 FOO 可能被字符串调用。

于是你加一个编译器。编译器是一种优化。它接收代码，返回一个优化版本，尽量保留这些语义，同时快得多。优化版本更快，部分是因为它大概由机器码或 JVM 字节码之类能被极快解释的东西组成，部分是因为更高层的优化。比如 (defun foo (x) (+ x 237)) (+ (foo 16) 93) (mapcar (eval) '(3 898 38)) 这里编译器可能会注意到 FOO 只能接受数值，当它看到第二行那样直接拿数值调用 FOO 时，就生成跳过“这是数值吗？不是？进调试器”这项检查的代码。一个“解释器桩”保留了完整的最安全行为，可以在第三行 eval 返回 FOO 时使用。

对我来说，这在速度和自由度之间取得了不错的平衡。优化后的代码安全性并没有降低，所以我仍然可以随心所欲地写，然后看着它们在调试器里失败。

缺点是编译器必须相当聪明才能真正有效。幸运的是，已经有几个编译器相当不错的 Lisp 实现，比如 SBCL 和 CCL。两者都能不太费劲地生成快速代码。

我在做一个新的 Lisp 编译器，叫 Cleavir。Cleavir 是 Robert Strandh 博士的项目 SICL 的编译器部分。SICL 旨在为其他实现提供模块化、可复用、干净以及更多正面形容词的代码，同时本身也是一个实现。

SICL 本身还不是一个完整的实现，但 Cleavir 被用在了另一个新的 Lisp 实现 clasp 中，那是 Christian Schafmeister 博士的项目。

据我所知，Clasp 最初的想法大概是这样：

<drmeister> 我的实验室有一套设计人工类蛋白质的新系统。它们由双氨基酸构成，这也是我们发明的。 <DoD 等幕后大佬> 真他妈棒。 <drmeister> 我们叫它们 spiroligozymes。它们可能带来不可思议的影响—— <DoD 等> 好好好。给你颁个奖，表彰你是货真价实的纳米技术专家，以那位大家都喜欢的物理学家命名。 <drmeister> 好，问题是，我们做的这些东西涉及大量计算机工作。 <drmeister> 对，我们主要用 C++ 做。但我喜欢 Lisp。 <DoD 等> 很好，用吧。它有 ANSI 标准。上帝保佑美国。 <drmeister> 但我们不想丢掉 C++ 代码。Lisp 可以调用 C 函数，但 C++ 其实没什么互操作性。 <drmeister> 所以我想着花几年时间做一个新的 Lisp 实现，从头就和 C++ 紧密结合。 <DoD 等> 听起来很难，而且你是个化学家。 <DoD 等> 这里给你一亿美元。赶紧干。

我想说的是，当个受人尊敬的科学家一定很不错。

Clasp 最终基于 Embeddable Common Lisp（ECL），之所以叫这个名字，是因为它用 C 编写，设计为从 C 程序调用。ECL 提供了大量运行时。不过在编译方面，Cleavir 把 Lisp 程序编译成它的“中级中间表示”，即 MIR；Clasp 再把它编译成 LLVM-IR，然后由 LLVM 编译成机器码。

这相当绕，也带来一些问题（比如 LLVM 似乎并不太适合作为一个带有在线编译器和大量堆分配的东西的目标）。幸运的是，这些问题通常不归我管，因为我主要把自己限制在 Cleavir 里，但了解一下你头顶那个磨牙吮血的深渊是什么性质，还是挺好的。

Cleavir 的 MIR，以及 HIR（“高级”），基本上就是我做的东西。看这个（傻乎乎的）函数： (defun example (x) (flet ((getx () x) (setx (y) (setf x y))) (setx 19) (print (getx)) (+ (getx) 331))) flet 建立局部闭包，setf 进行赋值。(example anything) 会打印 19，然后返回 350。

在 HIR 中，经过一些变换后，代码长这样。基本要素是：白色矩形是“指令”，代表基本操作。椭圆和橙色矩形是“数据”。实心黑箭头表示控制流。红色虚线箭头表示指令的输入，蓝色虚线箭头表示输出。函数以名为“enter”的指令开始。

除了有闭包、并且显式分离输入和输出之外，它在形式上其实和任何汇编类语言没多大区别，但用图形表示控制流比用标签更方便。

操作节点的图作为一种中间表示相当常见，因为它与把计算机视为状态机的观念紧密对应。因此，一些优化技术已经相当成熟。

（原文较长，此处译出前 6000 字，完整内容请点「打开原文」。）