由于早期的 Lisp 編譯器生成的代碼效率普遍低下，成為了 Lisp 失敗的主要原因之一。而現在的高性能 Lisp 編譯器（比如 Chez Scheme），其實已經可以生成非常高效的代碼，甚至可以匹敵 C 程序的速度。如果你看得到我腦子里的東西，就會明白這完全不是吹牛，對我來說這是科學的結論。我在這里介紹一下我寫 Scheme 編譯器的經歷，也許你就會從根本上明白為什么我會這么自信。這里的介紹其實不止針對函數式語言，而且針對所有語言的編譯器。

編譯器是一種神秘，有趣，又無聊的的程序。說它神秘，是因為只有非常少的人知道如何寫出優(yōu)秀的編譯器。這些會寫編譯器的人，就像身懷絕技的武林高手一樣神出鬼沒。說它有趣，是因為編譯器的技術里面含有大量的“哲學問題”和深刻的理論（比如 partial evaluation）。但為什么又說它無聊呢？因為你一旦掌握了編譯器技術里面最精華的原理，就會發(fā)現其實說來說去就那么點東西。編譯器代碼里面的“創(chuàng)造性含量”其實非常低。有些固定的“模式”，幾十年都不變。寫了幾個編譯器之后你就會發(fā)現，自己越來越喜歡做被很多人不齒的“界面”一類的東西。這就像做科學做到頭了，想嘗嘗藝術的滋味。

好了不打擊你積極性了，先來說一說為什么早期的 Lisp 編譯器生成的代碼效率低下吧。在函數式語言的早期，由于它比普通的語言多了一些表達力強大的構造（比如函數作為值傳遞），人們其實都不知道如何實現它的編譯器。很多 Scheme 的編譯器其實只是把 Scheme 編譯成 C，然后再調用 C 語言的編譯器。Haskell 的編譯器 GHC 在早期也是這樣的。而且由于 C 編譯器生成的匯編代碼不完全符合 Haskell 的需求，GHC 里面含有一個 Perl 腳本，專門用于調整這匯編代碼的結構。這個 Perl 腳本，由于它的工作方式毫無原則，被叫做 evil mangler?，F在這個東西已經不存在于 GHC 里面，但從它曾經的存在你可以看出，其實函數式編譯器的技術在早期是相當混沌的。

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

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

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

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

Kent 單槍匹馬的寫出了 Chez Scheme，世界上唯一的商業(yè) Scheme 編譯器，并且為此成立了自己的公司（Cadence Research Systems）。Chez Scheme 價格不菲，并且不明碼實價。它的價格跟項目的大小和公司的規(guī)模有關。有些大公司花重金購買 Chez Scheme 用于一些核心的項目。其中有些為了保證這編譯器的安全，又花了好幾倍的價錢買下了它的源代碼。Kent 的公司只有他一個人，不用操心管理，也不用操心銷售。所以他過的非常舒服，基本是一個不愁吃穿，不問世事的人。

Kent 是我一生中見過的最神秘，最酷的人。他幾乎從來不表揚任何人，但也不貶低任何人。從冷漠的言語之中，你能感覺到他的內心相對于任何人的完全平等。他的心里有許許多多的秘密，你需要一些技巧才能套出他的真言。他很少發(fā)表論文，卻把別人的論文全都看得很透。沒有人知道他的核心技術，他也從來不在乎別人是否了解他的水平。他的名字叫 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 的代碼，你就會發(fā)現 Kent 的水平其實遠在這些知名的大牛之上。我為什么可以這么說呢？因為如果你的水平在別人之下，你自己都會對這種判斷產生懷疑。而如果你超過了別人，他們的一言一行，他們的每一個錯誤，都像是處于你的顯微鏡底下，看得一清二楚。實話實說吧，在編譯器這個領域，我覺得 Kent 很有可能就是世界的 No.1。

如果你不了解 Scheme 的編譯器里面有什么東西，也許就會輕視它的難度。Scheme 是比 C 語言高級很多的語言，所以它的編譯器需要做比 C 語言的編譯器多很多的事情。在 Kent 的編譯器課程的前半段，我們其實本質上是在實現一個 C 語言的編譯器，把一種用“S表達式”表示的中間語言，編譯為 X64 匯編代碼。在后半學期的課程中，我們才加入了各種 Scheme 的先進功能，比如函數作為值（需要進行 closure conversion 以及 closure 優(yōu)化），尾遞歸優(yōu)化（tail-call optimization），等等。另外，我還自己為它加入了一種非常漂亮而先進的技術，叫做 online partial evaluation。這種技術可以在一個 pass 就完成普通編譯器需要好幾個 pass 才能完成的優(yōu)化。所以你看到了，C 語言的編譯器其實連這個 Scheme 編譯器的一半難度都不到。

Kent 的課程編譯器有非常好的結構，它被叫做“nanopass 編譯器構架”。因為它的每一個 pass 只做很小的一件事情，然后這些 pass 被串聯起來，形成一個完整的編譯器。你也許發(fā)現了，這其實就是 LLVM 的構架。但是我可以告訴你，我們的課程編譯器比 LLVM 干凈利落許多，處于遠遠領先的地位。每一節(jié)課，我們都學會一個 pass。每一個講義，都非常精確的告訴你需要干什么。每一次的作業(yè)，提交的時候都會經過上百個測試（當然 Kent 不可能把 Chez Scheme 的測試都給我們），如果沒有通過就會被拒絕接受。這些測試也可以下載，用于自己的調試。有趣的是，每一次作業(yè)我們都需要提交一些自己寫的新測試，目的是用于“破壞”別人的編譯器。所以我們每次都會想出很刁鉆的輸入代碼，讓同學的日子不好過。當然是開玩笑的，這種做法其實大大的提高了我們對編譯器測試的理解和興趣，以及同學之間的友誼。這比起我曾經在 Cornell 選過（然后 drop 掉）的編譯器課程，真是天壤之別。

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

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

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

責任編輯：lq6