王垠談編譯器

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

編譯器是一種神秘，有趣，又無聊的的程序。說它神秘，是因?yàn)橹挥蟹浅Ｉ俚娜酥廊绾螌懗鰞?yōu)秀的編譯器。這些會(huì)寫編譯器的人，就像身懷絕技的武林高手一樣神出鬼沒。說它有趣，是因?yàn)榫幾g器的技術(shù)里面含有大量的“哲學(xué)問題”和深刻的理論（比如 partial evaluation）。但為什么又說它無聊呢？因?yàn)槟阋坏┱莆樟司幾g器技術(shù)里面最精華的原理，就會(huì)發(fā)現(xiàn)其實(shí)說來說去就那么點(diǎn)東西。編譯器代碼里面的“創(chuàng)造性含量”其實(shí)非常低。有些固定的“模式”，幾十年都不變。寫了幾個(gè)編譯器之后你就會(huì)發(fā)現(xiàn)，自己越來越喜歡做被很多人不齒的“界面”一類的東西。這就像做科學(xué)做到頭了，想嘗嘗藝術(shù)的滋味。

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

在我看來，早期 Lisp 編譯器出現(xiàn)的主要問題，其實(shí)在于對(duì)編譯的本質(zhì)的理解，以及編譯器與解釋器的區(qū)別。解釋器之所以大部分時(shí)候比編譯器慢，是因?yàn)榻忉屍鳌皢柼嗟膯栴}”。每當(dāng)看到一個(gè)構(gòu)造，解釋器就會(huì)問：“這是一個(gè)整數(shù)嗎？”“這是一個(gè)函數(shù)嗎？”…… 這些問題，在編譯器的理論里面叫做“解釋開銷”（interpretive overhead）。編譯的本質(zhì)，其實(shí)就是在程序運(yùn)行之前分析并且一勞永逸的回答這些“問題”。這樣編譯后的代碼就不再問這些問題，因?yàn)樗苯泳椭滥莻€(gè)位置應(yīng)該出現(xiàn)什么構(gòu)造，應(yīng)該做什么事。早期的 Lisp 編譯器，以及現(xiàn)在的很多 Scheme 編譯器出現(xiàn)的問題其實(shí)在于，它們并沒有完全的消除這些問題，或者根本沒有消除這些問題。

當(dāng)我最早學(xué)習(xí) Scheme 語言的時(shí)候，我發(fā)現(xiàn) Scheme 有太多的實(shí)現(xiàn)，PLT Scheme（現(xiàn)在叫 Racket）， MIT Scheme， VSCM， Scheme 48， Bigloo， Chicken， Guile， 。。。讓人搞不清楚哪一個(gè)更好。有些 Scheme 實(shí)現(xiàn)顯得更高級(jí)一些，但實(shí)際用起來總是感覺不放心，因?yàn)槟阈睦锟傁胫?，這代碼編譯出來到底能不能跟 C 語言代碼比？這也是我后來開始使用 Common Lisp 的原因，因?yàn)?Common Lisp 似乎有挺多高效的編譯器（CMUCL，Lispworks，Allegro 等等）。

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

Chez Scheme 導(dǎo)致了我命運(yùn)的改變，怎么也沒有想到，我最終會(huì)成為它的作者的學(xué)生。我非常有幸的在 Indiana 大學(xué)參加了 Chez Scheme 的作者 R. Kent Dybvig（大家都叫他 Kent，雖然他的名字其實(shí)叫 R.）所授的編譯器課程，并且跟他合作研究了一個(gè)學(xué)期。我可以說，這個(gè)課程恐怕是世界上最好的編譯器課程，而我搭上了它的“末班車”。Kent 現(xiàn)在已經(jīng)離開了 Indiana 大學(xué)，被重金聘請(qǐng)到某大公司進(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 的公司只有他一個(gè)人，不用操心管理，也不用操心銷售。所以他過的非常舒服，基本是一個(gè)不愁吃穿，不問世事的人。

Kent 是我一生中見過的最神秘，最酷的人。他幾乎從來不表揚(yáng)任何人，但也不貶低任何人。從冷漠的言語之中，你能感覺到他的內(nèi)心相對(duì)于任何人的完全平等。他的心里有許許多多的秘密，你需要一些技巧才能套出他的真言。他很少發(fā)表論文，卻把別人的論文全都看得很透。沒有人知道他的核心技術(shù)，他也從來不在乎別人是否了解他的水平。他的名字叫 R. Kent Dybvig，卻從來沒有人知道那個(gè) R. 是哪一個(gè)名字的簡(jiǎn)寫。他的照片從來不放在網(wǎng)上，如果你真想知道他長得什么樣，我在網(wǎng)上找到一個(gè)跟他長得非常相似的人的照片：

Chez Scheme 生成的“目標(biāo)代碼”效率之高，我還沒有見到任何其它 Scheme 編譯器可以與之匹敵。而它的“編譯速度”之快，沒有任何語言的任何編譯器可以相提并論（注意我去掉了“Scheme”這個(gè)限定詞）。Chez Scheme 可以在 5 秒鐘之內(nèi)完成從頭到尾的自我編譯。想想編譯 GCC 或者 GHC 需要多少時(shí)間，你就明白差距了。

另外值得一提的是，Chez Scheme 從頭到尾都是 Kent 一個(gè)人的作品。它的工作原理是從 Scheme 源程序一直編譯到機(jī)器代碼，而不依賴任何其他語言的編譯器。它甚至不依賴第三方的匯編器，所有三種體系構(gòu)架（Intel， ARM， Sparc）的匯編器，都是 Kent 自己寫的。為什么這樣做呢？因?yàn)閹缀鯖]有其它人的編譯器代碼能夠達(dá)到他的標(biāo)準(zhǔn)。連 Intel 自己給自己的處理器寫的匯編器，都不能滿足他的要求。

如果你上了 Kent 的課，再來看看普通的編譯器書籍（比如有名的 Dragon Book），或者 LLVM 的代碼，你就會(huì)發(fā)現(xiàn) Kent 的水平其實(shí)遠(yuǎn)在這些知名的大牛之上。我為什么可以這么說呢？因?yàn)槿绻愕乃皆趧e人之下，你自己都會(huì)對(duì)這種判斷產(chǎn)生懷疑。而如果你超過了別人，他們的一言一行，他們的每一個(gè)錯(cuò)誤，都像是處于你的顯微鏡底下，看得一清二楚。實(shí)話實(shí)說吧，在編譯器這個(gè)領(lǐng)域，我覺得 Kent 很有可能就是世界的 No.1。

如果你不了解 Scheme 的編譯器里面有什么東西，也許就會(huì)輕視它的難度。Scheme 是比 C 語言高級(jí)很多的語言，所以它的編譯器需要做比 C 語言的編譯器多很多的事情。在 Kent 的編譯器課程的前半段，我們其實(shí)本質(zhì)上是在實(shí)現(xiàn)一個(gè) 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ù)可以在一個(gè) pass 就完成普通編譯器需要好幾個(gè) pass 才能完成的優(yōu)化。所以你看到了，C 語言的編譯器其實(shí)連這個(gè) Scheme 編譯器的一半難度都不到。

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

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

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

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

責(zé)任編輯：lq6