王垠：談編譯器
在上一篇博文的***，我提到了 Lisp 編譯器的問題。由于早期的 Lisp 編譯器生成的代碼效率普遍低下，成為了 Lisp 失敗的主要原因之一。而現(xiàn)在的高性能 Lisp 編譯器（比如
編譯器是一種神秘，有趣，又無聊的的程序。說它神秘，是因?yàn)橹挥蟹浅Ｉ俚娜酥廊绾螌懗鰞?yōu)秀的編譯器。這些會寫編譯器的人，就像身懷絕技的武林高手一樣神出鬼沒。說它有趣，是因?yàn)榫幾g器的技術(shù)里面含有大量的“哲學(xué)問題”和深刻的理論（比如
好了不打擊你積極性了，先來說一說為什么早期的 Lisp 編譯器生成的代碼效率低下吧。在函數(shù)式語言的早期，由于它比普通的語言多了一些表達(dá)力強(qiáng)大的構(gòu)造（比如函數(shù)作為值傳遞），人們其實(shí)都不知道如何實(shí)現(xiàn)它的編譯器。很多 Scheme 的編譯器其實(shí)只是把 Scheme 編譯成 C，然后再調(diào)用 C 語言的編譯器。Haskell 的編譯器 GHC 在早期也是這樣的。而且由于 C 編譯器生成的匯編代碼不完全符合 Haskell 的需求，GHC 里面含有一個 Perl 腳本，專門用于調(diào)整這匯編代碼的結(jié)構(gòu)。這個 Perl 腳本，由于它的工作方式毫無原則，被叫做 evil mangler。現(xiàn)在這個東西已經(jīng)不存在于 GHC 里面，但從它曾經(jīng)的存在你可以看出，其實(shí)函數(shù)式編譯器的技術(shù)在早期是相當(dāng)混沌的。
在我看來，早期 Lisp 編譯器出現(xiàn)的主要問題，其實(shí)在于對編譯的本質(zhì)的理解，以及編譯器與解釋器的區(qū)別。解釋器之所以大部分時候比編譯器慢，是因?yàn)榻忉屍?ldquo;問太多的問題”。每當(dāng)看到一個構(gòu)造，解釋器就會問：“這是一個整數(shù)嗎？”“這是一個函數(shù)嗎？”…… 這些問題，在編譯器的理論里面叫做“解釋開銷”（interpretive overhead）。編譯的本質(zhì)，其實(shí)就是在程序運(yùn)行之前分析并且一勞永逸的回答這些“問題”。這樣編譯后的代碼就不再問這些問題，因?yàn)樗苯泳椭滥莻€位置應(yīng)該出現(xiàn)什么構(gòu)造，應(yīng)該做什么事。早期的 Lisp 編譯器，以及現(xiàn)在的很多 Scheme 編譯器出現(xiàn)的問題其實(shí)在于，它們并沒有完全的消除這些問題，或者根本沒有消除這些問題。
當(dāng)我最早學(xué)習(xí) Scheme 語言的時候，我發(fā)現(xiàn) Scheme 有太多的實(shí)現(xiàn)，PLT Scheme（現(xiàn)在叫 Racket）, MIT Scheme, VSCM, Scheme 48, Bigloo, Chicken, Guile, ...讓人搞不清楚哪一個更好。有些 Scheme 實(shí)現(xiàn)顯得更高級一些，但實(shí)際用起來總是感覺不放心，因?yàn)槟阈睦锟傁胫@代碼編譯出來到底能不能跟 C 語言代碼比？這也是我后來開始使用 Common Lisp 的原因，因?yàn)?Common Lisp 似乎有挺多高效的編譯器（CMUCL，Lispworks，Allegro 等等）。
直到有一天，我發(fā)現(xiàn)了 Chez Scheme，它改變了我對 Scheme 編譯器，以至于整個編譯器概念的理解。當(dāng)時我只下載了 Chez Scheme 的免費(fèi)版本，叫做 Petite。Petite 與正式版 Chez Scheme 的區(qū)別是，它不輸出二進(jìn)制代碼，所以你不能把編譯后的代碼拿去銷售。另外出于商業(yè)目的，Petite 的出錯信息非常的“簡約”，以至于有時候你不得不用其它的 Scheme 實(shí)現(xiàn)，才能找到 bug 的所在。但是一運(yùn)行就見分曉，Petite 被作為一個“解釋器”直接運(yùn)行 Scheme 代碼，比其他的 Scheme 實(shí)現(xiàn)編譯后的代碼速度還要快很多倍。
Chez Scheme 導(dǎo)致了我命運(yùn)的改變，怎么也沒有想到，我最終會成為它的作者的學(xué)生。我非常有幸的在 Indiana 大學(xué)參加了 Chez Scheme 的作者 R. Kent Dybvig（大家都叫他 Kent，雖然他的名字其實(shí)叫 R.）所授的編譯器課程，并且跟他合作研究了一個學(xué)期。我可以說，這個課程恐怕是世界上***的編譯器課程，而我搭上了它的“末班車”。Kent 現(xiàn)在已經(jīng)離開了 Indiana 大學(xué)，被重金聘請到某大公司進(jìn)行一些機(jī)密的項(xiàng)目。誰都不知到他在干什么。
Kent 單槍匹馬的寫出了 Chez Scheme，世界上唯一的商業(yè) Scheme 編譯器，并且為此成立了自己的公司（Cadence Research Systems）。Chez Scheme 價(jià)格不菲，并且不明碼實(shí)價(jià)。它的價(jià)格跟項(xiàng)目的大小和公司的規(guī)模有關(guān)。有些大公司花重金購買 Chez Scheme 用于一些核心的項(xiàng)目。其中有些為了保證這編譯器的安全，又花了好幾倍的價(jià)錢買下了它的源代碼。Kent 的公司只有他一個人，不用操心管理，也不用操心銷售。所以他過的非常舒服，基本是一個不愁吃穿，不問世事的人。
Kent 是我一生中見過的最神秘，最酷的人。他幾乎從來不表揚(yáng)任何人，但也不貶低任何人。從冷漠的言語之中，你能感覺到他的內(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 自己寫的。為什么這樣做呢？因?yàn)閹缀鯖]有其它人的編譯器代碼能夠達(dá)到他的標(biāo)準(zhǔn)。連 Intel 自己給自己的處理器寫的匯編器，都不能滿足他的要求。
如果你上了 Kent 的課，再來看看普通的編譯器書籍（比如有名的
如果你不了解 Scheme 的編譯器里面有什么東西，也許就會輕視它的難度。Scheme 是比 C 語言高級很多的語言，所以它的編譯器需要做比 C 語言的編譯器多很多的事情。在 Kent 的編譯器課程的前半段，我們其實(shí)本質(zhì)上是在實(shí)現(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 語言的編譯器其實(shí)連這個 Scheme 編譯器的一半難度都不到。
Kent 的課程編譯器有非常好的結(jié)構(gòu)，它被叫做“nanopass 編譯器構(gòu)架”。因?yàn)樗拿恳粋€ pass 只做很小的一件事情，然后這些 pass 被串聯(lián)起來，形成一個完整的編譯器。你也許發(fā)現(xiàn)了，這其實(shí)就是 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)然是開玩笑的，這種做法其實(shí)大大的提高了我們對編譯器測試的理解和興趣，以及同學(xué)之間的友誼。這比起我曾經(jīng)在 Cornell 選過（然后 drop 掉）的編譯器課程，真是天壤之別。
在課程的***，我們做出了一個完整的編譯器，可以把 Scheme 最關(guān)鍵的子集，編譯到 X64 匯編代碼，然后通過 GNU 的匯編器，匯編成機(jī)器代碼。在***的一節(jié)課，Kent 對我們的學(xué)期做了一個總結(jié)。他說：“你們現(xiàn)在寫出的這個編譯器里面，含有很多先進(jìn)的技術(shù)。也許過一段時間回頭看這段代碼，你們才會發(fā)現(xiàn)它的價(jià)值。如果你們覺得自己已經(jīng)成為了編譯器的專家，那我就告訴你們，你們提交的最快的編譯器，編譯速度比起 Chez Scheme 慢了 700 倍。但是不要灰心，我告訴你們哪些地方可以改進(jìn)……”
只有極少數(shù)的人見到過 Chez Scheme 的源代碼，我沒有看見過。但是見到過它的人告訴我，Chez Scheme 里面其實(shí)只有很少幾個 pass，而不是像我們的課程編譯器有 50 個左右的 pass，這節(jié)省了很多用于“遍歷”代碼樹所需要的時間。Chez Scheme 只使用了一些非常簡單的算法，沒有使用論文里很復(fù)雜的方法，這也是它速度快的原因之一。比如它的寄存器分配，沒有使用“圖著色”（graph coloring）方法，而是使用非常簡單的類似 linear scan 的算法，***代碼的效率卻更高。另外，Scheme 使用“S表達(dá)式”作為它的語法，使得“語法分析”的速度非常之快。其它語言由于使用了復(fù)雜的語法，挺大一部分編譯時間其實(shí)花在了語法分析上面。
實(shí)際上，Chez Scheme 早就有了超越 linear scan， SSA 之類的技術(shù)，Kent 卻從來沒有為它們發(fā)表論文。這是因?yàn)樗运絾幔坎弧Ｈ绻銌査€是會告訴你他用的是什么方法。但是具體的細(xì)節(jié)，卻是解釋起來非常費(fèi)事的事情，他為什么無緣無故要費(fèi)工夫跟你解釋呢？所以很多時候，我都是自己摸索出解決方案，再去套他的口氣，看他是不是一樣的做法。有趣的是在課程進(jìn)行之中的時候，我發(fā)現(xiàn)我的有些突發(fā)靈感的做法，其實(shí)超越了 Chez Scheme，以至于在某些 pass 會生成比它還要高效的代碼，然而我的編譯器代碼卻比它的還要短小（當(dāng)然絕大部分時間我的代碼不如 Chez Scheme）。于是我就隱約的發(fā)現(xiàn)，Kent 有時候會悄悄的花時間看我的作業(yè)，想搞明白我是怎么做的，但他卻不想讓我知道。有一天開會的時候 Kent 沒有來，Kent 的編譯器課程的助教 Andy 不小心說漏了嘴：“因?yàn)槟銓懙拇a，Kent 還在進(jìn)行一些偵探工作……” 悄悄的從任何人那里得到啟發(fā)，吸收并且融入到自己的能力里面，也許就是 Kent 練就如此蓋世神功的秘訣。
我想，這篇文章就該到此結(jié)束了。寫這些東西的目的，其實(shí)只是樹立人們對于函數(shù)式語言編譯器的信心。它們有些其實(shí)比 C 和 C++ 之類語言的編譯器高明很多。我沒有時間也沒有精力去講述這編譯器里面的細(xì)節(jié)，因?yàn)樗鼘?shí)在是非常困難，卻又非常優(yōu)雅的程序。如果你有興趣的話，可以看看我***的代碼。由于版權(quán)原因，有些輔助部件我不能放在網(wǎng)上，所以你并不能運(yùn)行它，只能看一個大概的形狀。如果你需要一個 Scheme 版本用于學(xué)習(xí)的話，Chez Scheme 有一個免費(fèi)的版本叫做 Petite Chez Scheme，可以免費(fèi)下載。因?yàn)?Petite 不提供友好的出錯信息，所以我也推薦 Racket 作為一個替補(bǔ)。
