谈编译器

在上一篇博文的最后，我提到了 Lisp 编译器的问题。由于早期的 Lisp 编译器生成的代码效率普遍低下，成为了 Lisp 失败的主要原因之一。而现在的高性能 Lisp 编译器（比如 Chez Scheme），其实已经可以生成非常高效的代码，甚至可以匹敌 C 程序的速度。如果你看得到我脑子里的东西，就会明白这完全不是吹牛，对我来说这是科学的结论。我在这里介绍一下我写 Scheme 编译器的经历，也许你就会从根本上明白为什么我会这么自信。这里的介绍其实不止针对函数式语言，而且针对所有语言的编译器。

编译器是一种神秘，有趣，又无聊的的程序。说它神秘，是因为只有非常少的人知道如何写出优秀的编译器。这些会写编译器的人，就像身怀绝技的武林高手一样神出鬼没。说它有趣，是因为编译器的技术里面含有大量的“哲学问题”和深刻的理论（比如 partial evaluation）。但为什么又说它无聊呢？因为你一旦掌握了编译器技术里面最精华的原理，就会发现其实说来说去就那么点东西。编译器代码里面的“创造性含量”其实非常低。有些固定的“模式”，几十年都不变。写了几个编译器之后你就会发现，自己越来越喜欢做被很多人不齿的“界面”一类的东西。这就像做科学做到头了，想尝尝艺术的滋味。

好了不打击你积极性了，先来说一说为什么早期的 Lisp 编译器生成的代码效率低下吧。在函数式语言的早期，由于它比普通的语言多了一些表达力强大的构造（比如函数作为值传递），人们其实都不知道如何实现它的编译器。很多 Scheme 的编译器其实只是把 Scheme 编译成 C，然后再调用 C 语言的编译器。Haskell 的编译器 GHC 在早期也是这样的。而且由于 C 编译器生成的汇编代码不完全符合 Haskell 的需求，GHC 里面含有一个 Perl 脚本，专门用于调整这汇编代码的结构。这个 Perl 脚本，由于它的工作方式毫无原则，被叫做 evil mangler。现在这个东西已经不存在于 GHC 里面，但从它曾经的存在你可以看出，其实函数式编译器的技术在早期是相当混沌的。

但是现在情况已经很不同了。现代的 Lisp 编译器（比如 Chez Scheme）已经可以生成非常高效的代码。如果你看见过它们的内部构造，就会发现这些编译器超乎你的想象：它们比最高级的 C 编译器还要简单很多，却生成几乎达到理论极限的机器代码。我非常有幸的在 Indiana 大学参加了 Chez Scheme 的作者 R. Kent Dybvig （下文简称 Kent）所授的编译器课程，并且跟他合作研究了一个学期。我可以说，这个课程恐怕是世界上最好的编译器课程，而我搭上了它的“末班车”。Kent 现在已经离开了 Indiana 大学，被重金聘请到某大公司进行一些机密的项目。谁都不知到他在干什么。

Kent 单枪匹马的写出了 Chez Scheme，世界上唯一的商业 Scheme 编译器，并且为此成立了自己的公司（Cadence Research Systems）。Chez Scheme 价格不菲，并且不明码实价。它的价格跟项目的大小和公司的规模有关。小型商业用途的版权费一般在 2000 美元的样子。有些大公司花重金购买 Chez Scheme 用于一些核心的项目。有些公司为了保证这编译器的安全，又花了好几倍的价钱，买下了它的源代码。Kent 的公司只有他一个人，不用操心管理，也不用操心销售。所以他过的非常舒服，基本是一个不愁吃穿，不问世事的人。

Kent 是我一生中见过的最神秘，最酷的人。他几乎从来不表扬任何人，但从冷漠的言语之中，你能感觉到他的内心相对于他人的完全的平等。他的心里有许许多多的秘密，你需要一些技巧才能套出他的真言。他很少发表论文，却把别人的论文全都看得很透。没有人知道他的核心技术，他也从来不在乎别人是否了解他的水平。他的名字叫 R. Kent Dybvig，却从来没有人知道那个 R. 是哪一个名字的简写。他的照片从来不放在网上，如果你真想知道他长得什么样，我在网上找到一个跟他长得非常相似的人的照片：

谈编译器

Chez Scheme 生成的“目标代码”效率之高，我还没有见到任何其它 Scheme 编译器可以与之匹敌。而它的“编译速度”之快，没有任何语言的任何编译器可以相提并论（注意我去掉了“Scheme”这个限定词）。Chez Scheme 可以在 5 秒钟之内完成从头到尾的自我编译。想想编译 GCC 或者 GHC 需要多少时间，你就明白差距了。

另外值得一提的是，Chez Scheme 从头到尾都是 Kent 一个人的作品。它的工作原理是从 Scheme 源程序一直编译到机器代码，而不依赖任何其他语言的编译器。它甚至不依赖第三方的汇编器，所有三种体系构架（Intel, ARM, Sparc）的汇编器，都是 Kent 自己写的。为什么这样做呢？因为几乎没有其它人的编译器代码能够达到他的标准。连 Intel 自己给自己的处理器写的汇编器，都不能满足他的要求。

如果你上了 Kent 的课，再来看看普通的编译器书籍（比如有名的 Dragon Book），或者 LLVM 的代码，你就会发现 Kent 的水平，远在这些知名的大牛之上。实话实说吧，在编译器这个领域，我觉得 Kent 很有可能就是世界的 No.1。

如果你不了解 Scheme 的编译器里面有什么东西，也许就会轻视它的难度。Scheme 是比 C 语言高级很多的语言，所以它的编译器需要做比 C 语言的编译器多很多的事情。在 Kent 的编译器课程的前半段，我们其实本质上是在实现一个 C 语言的编译器，把一种用“S表达式”表示的中间语言，编译为 X64 汇编代码。在后半学期的课程中，我们才加入了各种 Scheme 的先进功能，比如函数作为值（需要进行 closure conversion 以及 closure 优化），尾递归优化（tail-call optimization），等等。另外，我还自己为它加入了一种先进的技术，叫做 online partial evaluation。这种技术可以在一个 pass，就完成其它编译器需要好几个 pass 才能完成的优化。所以你看到了，C 语言的编译器其实连这个 Scheme 编译器的一半难度都不到。

Kent 的课程编译器有非常好的结构，它被叫做“nanopass 编译器构架”。因为它的每一个 pass 只做很小的一件事情，然后这些 pass 被串联起来，形成一个完整的编译器。你也许发现了，这其实就是 LLVM 的构架。但是我可以告诉你，我们的编译器比 LLVM 干净利落许多，而且比 LLVM 的历史悠久。每一节课，我们都学会一个 pass。每一个讲义，都非常精确的告诉你需要干什么。每一次的作业，提交的时候都会经过上百个测试，如果没有通过就会被拒绝接受。这些测试也可以下载，用于自己的调试。有趣的是，每一次作业我们都需要提交一些自己写的新测试，目的是用于“破坏”别人的编译器。所以我们每次都会想出很刁钻的输入代码，让同学的日子不好过。当然是开玩笑的，这种做法其实大大的提高了我们对编译器测试的理解和兴趣，以及同学之间的友谊。

在课程的最后，我们做出了一个完整的编译器，可以把 Scheme 的最核心的子集，编译到 X64 汇编代码，然后通过 GNU 的汇编器，汇编成机器代码。在最后的一节课，Kent 对我们的学期做了一个总结。他说：“你们现在写出的这个编译器里面，含有很多先进的技术。也许过一段时间回头看这段代码，你们才会发现它的价值。如果你们觉得自己已经成为了编译器的专家，那我就告诉你们，你们提交的最快的编译器，编译速度比起 Chez Scheme，慢了 700 倍。”

只有极少数的人见到过 Chez Scheme 的源代码，也许由于国籍关系，我没有这种福气成为其中之一。但是见到过它的人告诉我，Chez Scheme 里面其实只有很少几个 pass，而不是像我们的编译器有 50 个左右的 pass，这节省了很多用于“遍历”代码树所需要的时间。Chez Scheme 只使用了一些非常简单的算法，没有使用论文里很复杂的方法，这也是它速度快的原因之一。比如它的寄存器分配，没有使用“图着色”（graph coloring）方法，而是使用非常简单的类似 linear scan 的算法，最后代码的效率却非常高。实际上，Chez Scheme 早就有了类似 linear scan， SSA 之类的技术，Kent 却从来没有为它们发表论文。

这是因为他自私吗？不。如果你问他，他还是会告诉你他用的是什么方法。但是具体的细节，却是解释起来非常费事的事情，他为什么无缘无故要费工夫跟你解释呢？所以很多时候，我都是自己摸索出解决方案，再去套他的口气，看他是不是一样的做法。

我想，这篇文章就该到此结束了。写这些东西的目的，其实只是树立人们对于函数式语言编译器的信心。它们有些其实比 C 和 C++ 之类语言的编译器高明很多。我没有时间也没有精力去讲述这编译器里面的细节，因为它实在是非常困难，却又非常优雅的程序。如果你有兴趣的话，可以看看我最后的代码。另外，Chez Scheme 有一个免费的版本叫做 Petite Chez Scheme，可以免费下载。