由于早期的 Lisp 編譯器生成的代碼效率普遍低下,，成為了 Lisp 失敗的主要原因之一。而現(xiàn)在的高性能 Lisp 編譯器（比如 Chez Scheme）,，其實已經(jīng)可以生成非常高效的代碼，甚至可以匹敵 C 程序的速度,。如果你看得到我腦子里的東西,，就會明白這完全不是吹牛，對我來說這是科學(xué)的結(jié)論,。我在這里介紹一下我寫 Scheme 編譯器的經(jīng)歷,，也許你就會從根本上明白為什么我會這么自信,。這里的介紹其實不止針對函數(shù)式語言，而且針對所有語言的編譯器,。
　　編譯器是一種神秘,，有趣，又無聊的的程序,。說它神秘,，是因為只有非常少的人知道如何寫出優(yōu)秀的編譯器。這些會寫編譯器的人,，就像身懷絕技的武林高手一樣神出鬼沒,。說它有趣，是因為編譯器的技術(shù)里面含有大量的“哲學(xué)問題”和深刻的理論（比如 partial evaluation）,。但為什么又說它無聊呢,？因為你一旦掌握了編譯器技術(shù)里面最精華的原理，就會發(fā)現(xiàn)其實說來說去就那么點東西,。編譯器代碼里面的“創(chuàng)造性含量”其實非常低,。有些固定的“模式”，幾十年都不變,。寫了幾個編譯器之后你就會發(fā)現(xiàn),，自己越來越喜歡做被很多人不齒的“界面”一類的東西。這就像做科學(xué)做到頭了,，想嘗嘗藝術(shù)的滋味,。
　　好了不打擊你積極性了，先來說一說為什么早期的 Lisp 編譯器生成的代碼效率低下吧,。在函數(shù)式語言的早期,，由于它比普通的語言多了一些表達(dá)力強(qiáng)大的構(gòu)造（比如函數(shù)作為值傳遞），人們其實都不知道如何實現(xiàn)它的編譯器,。很多 Scheme 的編譯器其實只是把 Scheme 編譯成 C,，然后再調(diào)用 C 語言的編譯器。Haskell 的編譯器 GHC 在早期也是這樣的,。而且由于 C 編譯器生成的匯編代碼不完全符合 Haskell 的需求,，GHC 里面含有一個 Perl 腳本，專門用于調(diào)整這匯編代碼的結(jié)構(gòu),。這個 Perl 腳本,，由于它的工作方式毫無原則，被叫做 evil mangler?，F(xiàn)在這個東西已經(jīng)不存在于 GHC 里面,，但從它曾經(jīng)的存在你可以看出，其實函數(shù)式編譯器的技術(shù)在早期是相當(dāng)混沌的,。
　　在我看來,，早期 Lisp 編譯器出現(xiàn)的主要問題,，其實在于對編譯的本質(zhì)的理解，以及編譯器與解釋器的區(qū)別,。解釋器之所以大部分時候比編譯器慢,，是因為解釋器“問太多的問題”。每當(dāng)看到一個構(gòu)造,，解釋器就會問：“這是一個整數(shù)嗎,？”“這是一個函數(shù)嗎？”…… 這些問題,，在編譯器的理論里面叫做“解釋開銷”（interpretive overhead）,。編譯的本質(zhì)，其實就是在程序運行之前分析并且一勞永逸的回答這些“問題”,。這樣編譯后的代碼就不再問這些問題,，因為它直接就知道那個位置應(yīng)該出現(xiàn)什么構(gòu)造，應(yīng)該做什么事,。早期的 Lisp 編譯器,，以及現(xiàn)在的很多 Scheme 編譯器出現(xiàn)的問題其實在于，它們并沒有完全的消除這些問題,，或者根本沒有消除這些問題,。
　　當(dāng)我最早學(xué)習(xí) Scheme 語言的時候，我發(fā)現(xiàn) Scheme 有太多的實現(xiàn),，PLT Scheme（現(xiàn)在叫 Racket）, MIT Scheme, VSCM, Scheme 48, Bigloo, Chicken, Guile, ...讓人搞不清楚哪一個更好,。有些 Scheme 實現(xiàn)顯得更高級一些，但實際用起來總是感覺不放心,，因為你心里總想著,，這代碼編譯出來到底能不能跟 C 語言代碼比？這也是我后來開始使用 Common Lisp 的原因,，因為 Common Lisp 似乎有挺多高效的編譯器（CMUCL,，Lispworks，Allegro 等等）,。
　　直到有一天，我發(fā)現(xiàn)了 Chez Scheme,，它改變了我對 Scheme 編譯器,，以至于整個編譯器概念的理解。當(dāng)時我只下載了 Chez Scheme 的免費版本,，叫做 Petite,。Petite 與正式版 Chez Scheme 的區(qū)別是，它不輸出二進(jìn)制代碼,，所以你不能把編譯后的代碼拿去銷售,。另外出于商業(yè)目的,，Petite 的出錯信息非常的“簡約”，以至于有時候你不得不用其它的 Scheme 實現(xiàn),，才能找到 bug 的所在,。但是一運行就見分曉，Petite 被作為一個“解釋器”直接運行 Scheme 代碼,，比其他的 Scheme 實現(xiàn)編譯后的代碼速度還要快很多倍,。
　　Chez Scheme 導(dǎo)致了我命運的改變，怎么也沒有想到,，我最終會成為它的作者的學(xué)生,。我非常有幸的在 Indiana 大學(xué)參加了 Chez Scheme 的作者 R. Kent Dybvig（大家都叫他 Kent，雖然他的名字其實叫 R.）所授的編譯器課程,，并且跟他合作研究了一個學(xué)期,。我可以說，這個課程恐怕是世界上最好的編譯器課程,，而我搭上了它的“末班車”,。Kent 現(xiàn)在已經(jīng)離開了 Indiana 大學(xué)，被重金聘請到某大公司進(jìn)行一些機(jī)密的項目,。誰都不知到他在干什么,。
　　Kent 單槍匹馬的寫出了 Chez Scheme，世界上唯一的商業(yè) Scheme 編譯器,，并且為此成立了自己的公司（Cadence Research Systems）,。Chez Scheme 價格不菲，并且不明碼實價,。它的價格跟項目的大小和公司的規(guī)模有關(guān),。有些大公司花重金購買 Chez Scheme 用于一些核心的項目。其中有些為了保證這編譯器的安全,，又花了好幾倍的價錢買下了它的源代碼,。Kent 的公司只有他一個人，不用操心管理,，也不用操心銷售,。所以他過的非常舒服，基本是一個不愁吃穿,，不問世事的人,。
　　Kent 是我一生中見過的最神秘，最酷的人,。他幾乎從來不表揚任何人,，但也不貶低任何人。從冷漠的言語之中，你能感覺到他的內(nèi)心相對于任何人的完全平等,。他的心里有許許多多的秘密,，你需要一些技巧才能套出他的真言。他很少發(fā)表論文,，卻把別人的論文全都看得很透,。沒有人知道他的核心技術(shù)，他也從來不在乎別人是否了解他的水平,。他的名字叫 R. Kent Dybvig,，卻從來沒有人知道那個 R. 是哪一個名字的簡寫。他的照片從來不放在網(wǎng)上,，如果你真想知道他長得什么樣,，我在網(wǎng)上找到一個跟他長得非常相似的人的照片：
　　Chez Scheme 生成的“目標(biāo)代碼”效率之高，我還沒有見到任何其它 Scheme 編譯器可以與之匹敵,。而它的“編譯速度”之快,，沒有任何語言的任何編譯器可以相提并論（注意我去掉了“Scheme”這個限定詞）。Chez Scheme 可以在 5 秒鐘之內(nèi)完成從頭到尾的自我編譯,。想想編譯 GCC 或者 GHC 需要多少時間,，你就明白差距了。
　　另外值得一提的是,，Chez Scheme 從頭到尾都是 Kent 一個人的作品,。它的工作原理是從 Scheme 源程序一直編譯到機(jī)器代碼，而不依賴任何其他語言的編譯器,。它甚至不依賴第三方的匯編器,，所有三種體系構(gòu)架（Intel, ARM, Sparc）的匯編器，都是 Kent 自己寫的,。為什么這樣做呢,？因為幾乎沒有其它人的編譯器代碼能夠達(dá)到他的標(biāo)準(zhǔn)。連 Intel 自己給自己的處理器寫的匯編器,，都不能滿足他的要求,。
　　如果你上了 Kent 的課，再來看看普通的編譯器書籍（比如有名的 Dragon Book）,，或者 LLVM 的代碼,，你就會發(fā)現(xiàn) Kent 的水平其實遠(yuǎn)在這些知名的大牛之上。我為什么可以這么說呢,？因為如果你的水平在別人之下,，你自己都會對這種判斷產(chǎn)生懷疑。而如果你超過了別人,，他們的一言一行，他們的每一個錯誤,，都像是處于你的顯微鏡底下,，看得一清二楚,。實話實說吧，在編譯器這個領(lǐng)域,，我覺得 Kent 很有可能就是世界的 No.1,。
　　如果你不了解 Scheme 的編譯器里面有什么東西，也許就會輕視它的難度,。Scheme 是比 C 語言高級很多的語言,，所以它的編譯器需要做比 C 語言的編譯器多很多的事情。在 Kent 的編譯器課程的前半段,，我們其實本質(zhì)上是在實現(xiàn)一個 C 語言的編譯器,，把一種用“S表達(dá)式”表示的中間語言，編譯為 X64 匯編代碼,。在后半學(xué)期的課程中,，我們才加入了各種 Scheme 的先進(jìn)功能，比如函數(shù)作為值（需要進(jìn)行 closure conversion 以及 closure 優(yōu)化）,，尾遞歸優(yōu)化（tail-call optimization）,，等等。另外,，我還自己為它加入了一種非常漂亮而先進(jìn)的技術(shù),，叫做 online partial evaluation。這種技術(shù)可以在一個 pass 就完成普通編譯器需要好幾個 pass 才能完成的優(yōu)化,。所以你看到了,，C 語言的編譯器其實連這個 Scheme 編譯器的一半難度都不到。
　　Kent 的課程編譯器有非常好的結(jié)構(gòu),，它被叫做“nanopass 編譯器構(gòu)架”,。因為它的每一個 pass 只做很小的一件事情，然后這些 pass 被串聯(lián)起來,，形成一個完整的編譯器,。你也許發(fā)現(xiàn)了，這其實就是 LLVM 的構(gòu)架,。但是我可以告訴你,，我們的課程編譯器比 LLVM 干凈利落許多，處于遠(yuǎn)遠(yuǎn)領(lǐng)先的地位,。每一節(jié)課,，我們都學(xué)會一個 pass。每一個講義,，都非常精確的告訴你需要干什么,。每一次的作業(yè)，提交的時候都會經(jīng)過上百個測試（當(dāng)然 Kent 不可能把 Chez Scheme 的測試都給我們），如果沒有通過就會被拒絕接受,。這些測試也可以下載,，用于自己的調(diào)試。有趣的是,，每一次作業(yè)我們都需要提交一些自己寫的新測試,，目的是用于“破壞”別人的編譯器。所以我們每次都會想出很刁鉆的輸入代碼,，讓同學(xué)的日子不好過,。當(dāng)然是開玩笑的，這種做法其實大大的提高了我們對編譯器測試的理解和興趣,，以及同學(xué)之間的友誼,。這比起我曾經(jīng)在 Cornell 選過（然后 drop 掉）的編譯器課程，真是天壤之別,。
　　在課程的最后,，我們做出了一個完整的編譯器，可以把 Scheme 最關(guān)鍵的子集,，編譯到 X64 匯編代碼,，然后通過 GNU 的匯編器，匯編成機(jī)器代碼,。在最后的一節(jié)課,，Kent 對我們的學(xué)期做了一個總結(jié)。他說：“你們現(xiàn)在寫出的這個編譯器里面,，含有很多先進(jìn)的技術(shù),。也許過一段時間回頭看這段代碼，你們才會發(fā)現(xiàn)它的價值,。如果你們覺得自己已經(jīng)成為了編譯器的專家,，那我就告訴你們，你們提交的最快的編譯器,，編譯速度比起 Chez Scheme 慢了 700 倍,。但是不要灰心，我告訴你們哪些地方可以改進(jìn)……”
　　只有極少數(shù)的人見到過 Chez Scheme 的源代碼,，我沒有看見過,。但是見到過它的人告訴我，Chez Scheme 里面其實只有很少幾個 pass,，而不是像我們的課程編譯器有 50 個左右的 pass,，這節(jié)省了很多用于“遍歷”代碼樹所需要的時間。Chez Scheme 只使用了一些非常簡單的算法,，沒有使用論文里很復(fù)雜的方法,，這也是它速度快的原因之一,。比如它的寄存器分配，沒有使用“圖著色”（graph coloring）方法,，而是使用非常簡單的類似 linear scan 的算法,，最后代碼的效率卻更高,。另外,，Scheme 使用“S表達(dá)式”作為它的語法，使得“語法分析”的速度非常之快,。其它語言由于使用了復(fù)雜的語法,，挺大一部分編譯時間其實花在了語法分析上面。
　　實際上,，Chez Scheme 早就有了超越 linear scan,， SSA 之類的技術(shù)，Kent 卻從來沒有為它們發(fā)表論文,。這是因為他自私嗎,？不。如果你問他,，他還是會告訴你他用的是什么方法,。但是具體的細(xì)節(jié)，卻是解釋起來非常費事的事情,，他為什么無緣無故要費工夫跟你解釋呢,？所以很多時候，我都是自己摸索出解決方案,，再去套他的口氣,，看他是不是一樣的做法。有趣的是在課程進(jìn)行之中的時候,，我發(fā)現(xiàn)我的有些突發(fā)靈感的做法,，其實超越了 Chez Scheme，以至于在某些 pass 會生成比它還要高效的代碼,，然而我的編譯器代碼卻比它的還要短?。ó?dāng)然絕大部分時間我的代碼不如 Chez Scheme）。于是我就隱約的發(fā)現(xiàn),，Kent 有時候會悄悄的花時間看我的作業(yè),，想搞明白我是怎么做的，但他卻不想讓我知道,。有一天開會的時候 Kent 沒有來,，Kent 的編譯器課程的助教 Andy 不小心說漏了嘴：“因為你寫的代碼，Kent 還在進(jìn)行一些偵探工作……” 悄悄的從任何人那里得到啟發(fā),，吸收并且融入到自己的能力里面,，也許就是 Kent 練就如此蓋世神功的秘訣,。
　　我想，這篇文章就該到此結(jié)束了,。寫這些東西的目的,，其實只是樹立人們對于函數(shù)式語言編譯器的信心。它們有些其實比 C 和 C++ 之類語言的編譯器高明很多,。我沒有時間也沒有精力去講述這編譯器里面的細(xì)節(jié),，因為它實在是非常困難，卻又非常優(yōu)雅的程序,。如果你有興趣的話,，可以看看我最后的代碼。由于版權(quán)原因,，有些輔助部件我不能放在網(wǎng)上,，所以你并不能運行它，只能看一個大概的形狀,。如果你需要一個 Scheme 版本用于學(xué)習(xí)的話,，Chez Scheme 有一個免費的版本叫做 Petite Chez Scheme，可以免費下載,。因為 Petite 不提供友好的出錯信息,，所以我也推薦 Racket 作為一個替補(bǔ)。