由于早期的 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 編譯器出現的主要問題，其實在于對編譯的本質的理解，以及編譯器與解釋器的區別。解釋器之所以大部分時候比編譯器慢，是因為解釋器“問太多的問題”。每當看到一個構造，解釋器就會問：“這是一個整數嗎？”“這是一個函數嗎？”…… 這些問題，在編譯器的理論里面叫做“解釋開銷”（interpretive overhead）。編譯的本質，其實就是在程序運行之前分析并且一勞永逸的回答這些“問題”。這樣編譯后的代碼就不再問這些問題，因為它直接就知道那個位置應該出現什么構造，應該做什么事。早期的 Lisp 編譯器，以及現在的很多 Scheme 編譯器出現的問題其實在于，它們并沒有完全的消除這些問題，或者根本沒有消除這些問題。

當我最早學習 Scheme 語言的時候，我發現 Scheme 有太多的實現，PLT Scheme（現在叫 Racket）， MIT Scheme， VSCM， Scheme 48， Bigloo， Chicken， Guile， 。。。讓人搞不清楚哪一個更好。有些 Scheme 實現顯得更高級一些，但實際用起來總是感覺不放心，因為你心里總想著，這代碼編譯出來到底能不能跟 C 語言代碼比？這也是我后來開始使用 Common Lisp 的原因，因為 Common Lisp 似乎有挺多高效的編譯器（CMUCL，Lispworks，Allegro 等等）。

直到有一天，我發現了 Chez Scheme，它改變了我對 Scheme 編譯器，以至于整個編譯器概念的理解。當時我只下載了 Chez Scheme 的免費版本，叫做 Petite。Petite 與正式版 Chez Scheme 的區別是，它不輸出二進制代碼，所以你不能把編譯后的代碼拿去銷售。另外出于商業目的，Petite 的出錯信息非常的“簡約”，以至于有時候你不得不用其它的 Scheme 實現，才能找到 bug 的所在。但是一運行就見分曉，Petite 被作為一個“解釋器”直接運行 Scheme 代碼，比其他的 Scheme 實現編譯后的代碼速度還要快很多倍。

Chez Scheme 導致了我命運的改變，怎么也沒有想到，我最終會成為它的作者的學生。我非常有幸的在 Indiana 大學參加了 Chez Scheme 的作者 R. Kent Dybvig（大家都叫他 Kent，雖然他的名字其實叫 R.）所授的編譯器課程，并且跟他合作研究了一個學期。我可以說，這個課程恐怕是世界上最好的編譯器課程，而我搭上了它的“末班車”。Kent 現在已經離開了 Indiana 大學，被重金聘請到某大公司進行一些機密的項目。誰都不知到他在干什么。

Kent 單槍匹馬的寫出了 Chez Scheme，世界上唯一的商業 Scheme 編譯器，并且為此成立了自己的公司（Cadence Research Systems）。Chez Scheme 價格不菲，并且不明碼實價。它的價格跟項目的大小和公司的規模有關。有些大公司花重金購買 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 干凈利落許多，處于遠遠領先的地位。每一節課，我們都學會一個 pass。每一個講義，都非常精確的告訴你需要干什么。每一次的作業，提交的時候都會經過上百個測試（當然 Kent 不可能把 Chez Scheme 的測試都給我們），如果沒有通過就會被拒絕接受。這些測試也可以下載，用于自己的調試。有趣的是，每一次作業我們都需要提交一些自己寫的新測試，目的是用于“破壞”別人的編譯器。所以我們每次都會想出很刁鉆的輸入代碼，讓同學的日子不好過。當然是開玩笑的，這種做法其實大大的提高了我們對編譯器測試的理解和興趣，以及同學之間的友誼。這比起我曾經在 Cornell 選過（然后 drop 掉）的編譯器課程，真是天壤之別。

在課程的最后，我們做出了一個完整的編譯器，可以把 Scheme 最關鍵的子集，編譯到 X64 匯編代碼，然后通過 GNU 的匯編器，匯編成機器代碼。在最后的一節課，Kent 對我們的學期做了一個總結。他說：“你們現在寫出的這個編譯器里面，含有很多先進的技術。也許過一段時間回頭看這段代碼，你們才會發現它的價值。如果你們覺得自己已經成為了編譯器的專家，那我就告訴你們，你們提交的最快的編譯器，編譯速度比起 Chez Scheme 慢了 700 倍。但是不要灰心，我告訴你們哪些地方可以改進……”

只有極少數的人見到過 Chez Scheme 的源代碼，我沒有看見過。但是見到過它的人告訴我，Chez Scheme 里面其實只有很少幾個 pass，而不是像我們的課程編譯器有 50 個左右的 pass，這節省了很多用于“遍歷”代碼樹所需要的時間。Chez Scheme 只使用了一些非常簡單的算法，沒有使用論文里很復雜的方法，這也是它速度快的原因之一。比如它的寄存器分配，沒有使用“圖著色”（graph coloring）方法，而是使用非常簡單的類似 linear scan 的算法，最后代碼的效率卻更高。另外，Scheme 使用“S表達式”作為它的語法，使得“語法分析”的速度非常之快。其它語言由于使用了復雜的語法，挺大一部分編譯時間其實花在了語法分析上面。

實際上，Chez Scheme 早就有了超越 linear scan， SSA 之類的技術，Kent 卻從來沒有為它們發表論文。這是因為他自私嗎？不。如果你問他，他還是會告訴你他用的是什么方法。但是具體的細節，卻是解釋起來非常費事的事情，他為什么無緣無故要費工夫跟你解釋呢？所以很多時候，我都是自己摸索出解決方案，再去套他的口氣，看他是不是一樣的做法。有趣的是在課程進行之中的時候，我發現我的有些突發靈感的做法，其實超越了 Chez Scheme，以至于在某些 pass 會生成比它還要高效的代碼，然而我的編譯器代碼卻比它的還要短小（當然絕大部分時間我的代碼不如 Chez Scheme）。于是我就隱約的發現，Kent 有時候會悄悄的花時間看我的作業，想搞明白我是怎么做的，但他卻不想讓我知道。有一天開會的時候 Kent 沒有來，Kent 的編譯器課程的助教 Andy 不小心說漏了嘴：“因為你寫的代碼，Kent 還在進行一些偵探工作……” 悄悄的從任何人那里得到啟發，吸收并且融入到自己的能力里面，也許就是 Kent 練就如此蓋世神功的秘訣。

責任編輯：lq6