出品 | CSDN（ID：）
以下為譯文：
我在滑鐵盧大學(xué)的最后一個(gè)學(xué)期選了CS444：編譯原理這門課程，課程項(xiàng)目是編寫一個(gè)編譯器，將Java語言的子集編譯成x86代碼，三人結(jié)組，語言自由選擇。
這是個(gè)難得的機(jī)會(huì)，我可以在同樣的大型項(xiàng)目下比較不同的實(shí)現(xiàn)，而且我的朋友們的水平也跟我很相近，所以我可以借這個(gè)機(jī)會(huì)看看不同的設(shè)計(jì)和語言選擇。我從這個(gè)項(xiàng)目中獲得了不少心得，盡管這個(gè)比較并不完美，但比那些僅靠個(gè)人觀點(diǎn)來比較編程語言的人要好多了。
我們的編譯器是用Rust寫成的，首先與另一個(gè)使用了的組進(jìn)行了比較。我認(rèn)為他們的編譯器應(yīng)該更簡潔，但實(shí)際的代碼行數(shù)差不多。與另一個(gè)使用了OCaml的團(tuán)隊(duì)的比較也得到了同樣的結(jié)果。然后我與一個(gè)使用了C++的團(tuán)隊(duì)比較，結(jié)果如我預(yù)料的那樣，由于有頭文件，以及缺乏匯總類型和模式匹配的支持，導(dǎo)致他們的編譯器大了30%。下一個(gè)是跟我一個(gè)朋友的實(shí)現(xiàn)進(jìn)行的比較，他的代碼量不到我們的一半，這要?dú)w功于元編程和動(dòng)態(tài)類型。另一個(gè)朋友的團(tuán)隊(duì)使用了Scala，實(shí)現(xiàn)的編譯器代碼量也小于我們。最讓我驚訝的比較就是與另一個(gè)同樣使用Rust的團(tuán)隊(duì)的比較，他們的代碼量是我們的三倍，因?yàn)樗麄儾捎昧瞬煌脑O(shè)計(jì)決定，這最終導(dǎo)致了同樣的功能需要的代碼量產(chǎn)生了巨大差異！
本文中首先我會(huì)來解釋一下此次比較的意義，介紹各個(gè)項(xiàng)目的基本情況，然后再解釋引發(fā)編譯器大小差異的部分原因。最后，我會(huì)談一談從各個(gè)比較中學(xué)到的東西。
比較的意義
你也許會(huì)認(rèn)為，代碼行數(shù)（我同時(shí)比較了代碼行數(shù)和字節(jié)數(shù)）是個(gè)很糟糕的度量，但我認(rèn)為在這個(gè)項(xiàng)目中這種度量可以給出很有用的信息。在我看來，至少代碼行數(shù)是各個(gè)不同的團(tuán)隊(duì)在同一個(gè)大型項(xiàng)目上工作時(shí)最可控的一個(gè)變數(shù)。
因此我認(rèn)為，就各個(gè)項(xiàng)目需要花費(fèi)的精力，以及如果是長期項(xiàng)目的話需要花費(fèi)多少精力去維護(hù)而言，代碼量是一個(gè)很不錯(cuò)的近似統(tǒng)計(jì)。我認(rèn)為，微小的差異也能反映出巨大的問題，比如上面說過的用編寫的編譯器代碼量不到C++的一半。
Rust（比較基準(zhǔn)）
我和團(tuán)隊(duì)里的另一名成員以前分別寫過1萬多行的Rust代碼，另一個(gè)成員在某次編程馬拉松項(xiàng)目上寫過大約500行Rust。我們的編譯器用wc -l統(tǒng)計(jì)的結(jié)果是6806行，其中包括5900代碼行（不包括空行和注釋），wc -c的結(jié)果為220kb。
我發(fā)現(xiàn)的一個(gè)問題是，這幾項(xiàng)度量的比例在其他項(xiàng)目中也是相似的，只有一些微小的差異（過會(huì)兒我會(huì)介紹）。下文中提到代碼行數(shù)時(shí)，我指的都是wc -l的結(jié)果，但上述結(jié)論表明，代碼行數(shù)按照哪個(gè)規(guī)則進(jìn)行統(tǒng)計(jì)其實(shí)是無所謂的（除非特別指出），你可以通過比例進(jìn)行換算。
我寫過另一篇關(guān)于設(shè)計(jì)的文章（），這個(gè)設(shè)計(jì)通過了所有公開和秘密的測試。它還包括幾個(gè)額外的特性，這些特性我們僅僅是出于興趣而開發(fā)，并沒有想著通過測試。這些特性大概占用了400行。我們總共的單元測試和測試用的代碼大約占了500行。
團(tuán)隊(duì)由我的兩個(gè)朋友組成，他們每個(gè)人大概寫過幾千行，還閱讀過許多網(wǎng)上的內(nèi)容，以及許多其他類似的語言，如OCaml和Lean。他們還有另一個(gè)我不太熟悉的團(tuán)隊(duì)成員詞法分析器輸入的是，但似乎是個(gè)很厲害的程序員，以前也用過。
他們編譯器的wc -l結(jié)果是9750行，357kb，7777 SLOC（源代碼行數(shù)）。這個(gè)團(tuán)隊(duì)的度量比例的差別也最大，他們的編譯器中行數(shù)為1.4倍，SLOC為1.3倍，字節(jié)數(shù)為1.6倍。他們并沒有實(shí)現(xiàn)任何額外功能，但通過了所有公開和秘密的測試用例。
需要指出的重要的一點(diǎn)是，只有把測試用例統(tǒng)計(jì)在內(nèi)，對(duì)這個(gè)團(tuán)隊(duì)才公平，因?yàn)樗麄兊拇a是最正確的，包含了1600行測試用例，并且捕獲了好幾個(gè)團(tuán)隊(duì)未能捕獲的邊界情況，只不過是課程提供的測試用例沒有覆蓋到這些邊界情況而已。所以，如果兩者都不統(tǒng)計(jì)測試用例的話，他們的代碼是8.1k行，我們的是6.3k行，僅是我們的1.3倍。
為了讓度量更合理，我還統(tǒng)計(jì)了字節(jié)數(shù)，因?yàn)轫?xiàng)目平均每行要更長，而且沒有許多只有結(jié)束括號(hào)的行，它的單行函數(shù)也不會(huì)被分解成多行。
在與團(tuán)隊(duì)里的另一個(gè)朋友深入挖掘了代碼大小的問題后，我們找到了以下理由來解釋代碼大小的差異：
這些差異再加上測試用例的差異，就導(dǎo)致了代碼行數(shù)的差別。實(shí)際上，我們的文件在中間解析階段（如常量折疊、作用域解析等）的大小跟他們的非常接近。但依然產(chǎn)生了字節(jié)數(shù)上的區(qū)別，原因是行的平均長度，我估計(jì)原因是他們需要更多的代碼，在每次解析時(shí)重寫整個(gè)樹，而我們只需要訪問并修改即可。
我認(rèn)為，考慮到Rust和的設(shè)計(jì)決定非常相似，都是表達(dá)性的，只有細(xì)微的差異，如Rust在需要時(shí)能夠很方便地修改變量等。另一點(diǎn)有意思的是，我們選擇采用遞歸下降分析器和手工編寫詞法分析器給我們帶來了回報(bào)。雖然這有點(diǎn)風(fēng)險(xiǎn)，因?yàn)榻淌诓]有推薦這一點(diǎn)，我是自學(xué)來的，但我發(fā)現(xiàn)它很易于使用，是個(gè)正確的決定。
我認(rèn)為，這個(gè)團(tuán)隊(duì)可能并沒有開發(fā)出的全部潛力。如果他們能更善于使用，他們的代碼應(yīng)該行數(shù)更少。我相信，像 Kmeet之類的人可以使用更少的代碼就能編寫出同樣的編譯器，從這一點(diǎn)上來說，我朋友的團(tuán)隊(duì)并沒有使用太多超高級(jí)的抽象，而且他們也不允許使用更好的組合庫，如lens等。但是，這樣做的代價(jià)就是理解編譯器的難度。團(tuán)隊(duì)的成員都是有經(jīng)驗(yàn)的程序員，他們知道可以做非常漂亮的事情，但還是決定不這樣做，因?yàn)樗麄冋J(rèn)為，這樣做花費(fèi)的時(shí)間會(huì)超過節(jié)省的時(shí)間，而且會(huì)讓代碼變得難以理解。在我看來這的確是個(gè)正確的選擇，用“魔法”的方式使用編寫編譯器，會(huì)產(chǎn)生“寫編譯器的門檻非常高，如果你不考慮對(duì)于不太了解的人的可維護(hù)性的話”的結(jié)果，而這種結(jié)果并不是我們想要的。
另一個(gè)有趣的發(fā)現(xiàn)是，教授在開始時(shí)說過，學(xué)生可以選擇任何能夠在學(xué)校服務(wù)器上運(yùn)行的語言，但同時(shí)針對(duì)提出了警告，說過去使用的團(tuán)隊(duì)的分?jǐn)?shù)的方差是最高的，因?yàn)樵S多選擇的團(tuán)隊(duì)都高估了他們的能力，導(dǎo)致他們的得分比選擇其他語言的團(tuán)隊(duì)低得多，也有另一部分團(tuán)隊(duì)像我朋友那樣做得非常完美。
C++
接下來我與另一個(gè)在團(tuán)隊(duì)中使用了C++的朋友進(jìn)行了交談。那個(gè)團(tuán)隊(duì)中我只認(rèn)識(shí)這一個(gè)人，但由于滑鐵盧大學(xué)中使用C++的課程非常普遍，所以估計(jì)團(tuán)隊(duì)中的每個(gè)人都有C++經(jīng)驗(yàn)。
他們的項(xiàng)目代碼行數(shù)為8733，字節(jié)數(shù)為280kb，這些數(shù)字不包括測試代碼，但包括大約500行的額外功能。與我們不含測試的代碼（也包含500行的額外功能）相比，他們的代碼行數(shù)為1.4倍。他們通過了100%的公開測試，但僅通過了90%的秘密測試，很可能是因?yàn)樗鼈儧]有實(shí)現(xiàn)項(xiàng)目要求的數(shù)組，這個(gè)功能需要大約50-100行代碼實(shí)現(xiàn)。
我并沒有深入挖掘代碼差異的原因，我感覺最有可能的解釋為：
我們比較的另一件事是編譯時(shí)間。在我的筆記本上，我們的編譯器的調(diào)試版完整編譯需要9.7秒，調(diào)試版增量編譯需要3.5秒。我的朋友并沒有給出他們的C++編譯器的構(gòu)建時(shí)間（采用并行make），但說我提供的數(shù)字與他們的非常接近，而且說他們把一些常用的小函數(shù)的簽名放到了頭文件中，以增加編譯時(shí)間為代價(jià)來減少函數(shù)簽名的重復(fù)（也正是由于這個(gè)原因，我沒有辦法比較單純的頭文件代碼行數(shù)）。
我的一位朋友是非常優(yōu)秀的程序員，她選擇使用獨(dú)立完成項(xiàng)目。她還比其他團(tuán)隊(duì)多實(shí)現(xiàn)了好幾個(gè)額外功能，包括帶有寄存器分配的SSA立即表示，還有其他優(yōu)化。另一方面，由于她是獨(dú)立完成的，而且實(shí)現(xiàn)了許多額外的功能，因此她在代碼質(zhì)量上只花費(fèi)了最小限度的經(jīng)歷，例如所有錯(cuò)誤都會(huì)拋出統(tǒng)一的異常（所以調(diào)試時(shí)需要進(jìn)行棧跟蹤），而不是像我們一樣每種錯(cuò)誤都給出特定的錯(cuò)誤類型和錯(cuò)誤信息。
她的編譯器只有4581行，并且通過了所有公開測試和秘密測試。她實(shí)現(xiàn)的功能比所有其他團(tuán)隊(duì)都多得多，但很難確定那些功能占了多少行代碼，因?yàn)樵S多額外功能與每個(gè)人都在做的功能都相同，比如常量折疊、代碼生成等，但功能卻更強(qiáng)大。額外的功能估計(jì)至少占用了1000~2000行，所以我很確信她的代碼的表達(dá)性要比我們至少高兩倍。
造成這種差異的最大原因很可能是動(dòng)態(tài)類型。我們的ast.rs中類型定義就占了500行，編譯器的其他部分還有更多的類型定義。我們還通過類型系統(tǒng)做了各種類型限制。例如，我們需要基礎(chǔ)設(shè)施，才能在分析代碼過程中向AST中添加信息供以后使用，而中只需要給AST結(jié)點(diǎn)添加新的域即可。
強(qiáng)大的元編程也是造成差異的原因之一。例如，盡管她用的是LR分析器而不是遞歸下降分析器，但她的項(xiàng)目代碼量更小，因?yàn)樗恍枰M(jìn)行樹重寫的過程，而是在LR語法中加入了代碼片段來構(gòu)建AST，而生成器可以直接利用eval變成函數(shù)。我們沒有采用LR分析器的部分原因是，不使用樹重寫來構(gòu)建AST需要大量的代碼（生成的Rust文件或過程式的宏）將語法綁定到Rust代碼片段上。
元編程和動(dòng)態(tài)類型的強(qiáng)大之處的另一個(gè)例子是，我們有個(gè)名為visit.rs的文件有400行，里面大部分是重復(fù)性的樣板代碼，僅為了實(shí)現(xiàn)在各種AST結(jié)構(gòu)上的訪問。在中只需要一個(gè)大約10行的函數(shù)即可遞歸地訪問AST結(jié)點(diǎn)的各個(gè)域（通過屬性）。
作為Rust和靜態(tài)類型語言的愛好者，我需要指出，類型系統(tǒng)非常有助于避免bug和提高性能。強(qiáng)大的元編程同時(shí)會(huì)讓代碼更難理解，但是，這個(gè)比較結(jié)果依然讓我非常驚訝，我沒想到代碼的差異能有如此之大。如果差異真的導(dǎo)致需要寫兩倍的代碼，那我依然認(rèn)為Rust的付出是值得的，但兩倍的差異的確不可忽視，我以后會(huì)考慮在獨(dú)立完成某項(xiàng)工作中的一次性代碼時(shí)使用Ruby或。
Rust（另一個(gè)組）
最后一個(gè)比較，也是最有意思的，就是我和另一個(gè)朋友的比較。他們組還有另一個(gè)成員（我不認(rèn)識(shí)），使用的也是Rust。我的朋友有許多Rust經(jīng)驗(yàn)，也參與過Rust編譯器，也讀過許多資料。但我不了解他的組員如何。
他們的項(xiàng)目有17,211行代碼，不算注釋的話有15000行，不包括測試代碼和生成的代碼共有637kb。他們沒有實(shí)現(xiàn)任何額外功能，僅通過了4/10個(gè)秘密測試，以及90%的公開測試，因?yàn)樗麄儧]有時(shí)間在截止日期之前實(shí)現(xiàn)項(xiàng)目要求中的高級(jí)部分。同樣的語言，代碼量卻是我們的三倍，但功能卻更少！
這個(gè)結(jié)果非常讓我吃驚，與之相比，之前的比較都黯然無光了。所以我們比較了wc -l中的每個(gè)文件大小，以及仔細(xì)檢查各個(gè)功能是怎樣實(shí)現(xiàn)的。
似乎我們做出的設(shè)計(jì)決定完全不一樣。例如，他們的前端（詞法、解析、AST構(gòu)建）包括7597行，而我們的只有2164行。他們使用的是基于DFA的詞法分析器和LALR(1)語法分析器，但其他采用了類似方案的組并沒有寫如此之多的代碼。仔細(xì)檢查他們的代碼后，我發(fā)現(xiàn)了許多不同的設(shè)計(jì)決定：
我沒有查看他們代碼中的分析過程，但這個(gè)過程也一樣大。我跟我的朋友聊了聊，似乎他們的實(shí)現(xiàn)跟我們的訪問者基礎(chǔ)架構(gòu)完全不一樣。我猜其他一些小的設(shè)計(jì)差異也導(dǎo)致了代碼量的區(qū)別。
訪問者模式讓我們的分析過程只需要關(guān)注它們需要關(guān)注的AST，而不用去匹配整個(gè)AST結(jié)構(gòu)，從而節(jié)省了大量代碼。
他們的代碼生成部分是3594行，我們的只有1560行。我看了他們的代碼，似乎所有的差異都在于他們采用了一種中間數(shù)據(jù)結(jié)構(gòu)來生成匯編指令，而我們只使用了基本的字符串直接輸出匯編代碼。他們的做法需要為所有的指令和操作數(shù)定義類型和輸出函數(shù)，這也意味著，構(gòu)建匯編指令需要耗費(fèi)更多的代碼，而我們的只需要使用類似于mov ecx, [edx]的指令，而他們需要一條巨大得被分割成6行的語句，其中生成指令時(shí)，操作數(shù)使用了許多中間類型，還涉及了多達(dá)6層的嵌套括號(hào)。我們的輸出部分也只是一個(gè)格式化語句，而他們需要為每條指令單獨(dú)構(gòu)造。
我的團(tuán)隊(duì)也曾考慮過使用這種級(jí)別的抽象。如果能直接輸出文本形式的匯編，或者直接輸出機(jī)器碼，那就會(huì)方便許多，但這并不是課程的要求。同樣的東西可以使用加上類似于push(reg: )之類的方法很簡單地完成，代碼量更少，效率更高。我們考慮過的另一個(gè)角度是，抽象也許能讓調(diào)試和測試更簡單，但我們意識(shí)到，直接查看生成的文本匯編，可能會(huì)更容易閱讀和測試。但我們預(yù)測到（顯然是正確的），那樣做會(huì)導(dǎo)致大量的額外代碼，而且并不能給我們帶來任何實(shí)際的好處，所以我們沒有做。
可以跟C++那個(gè)組使用的中間表示形式做個(gè)比較。他們將中間表示形式作為額外功能來實(shí)現(xiàn)，占用了大約500行代碼。他們采用的數(shù)據(jù)結(jié)構(gòu)非常簡單（用于簡單的類型定義和代碼生成），它采用的操作與Java要求的很接近。也就是說，他們的IR比生成的匯編更?。ㄒ虼诵枰臉?gòu)造代碼更少），因?yàn)樵S多語言的操作（如調(diào)用、強(qiáng)制類型轉(zhuǎn)換等）需要大量的匯編指令。高層表示也使他們得以在IR上做一些簡單的優(yōu)化。C++團(tuán)隊(duì)想出了一個(gè)非常好的設(shè)計(jì)，所以他們能用更少的代碼完成更多的功能。
總的來看，3倍的代碼量似乎完全由不同的設(shè)計(jì)決定導(dǎo)致，每個(gè)設(shè)計(jì)決定的不同都導(dǎo)致了或大或小的代碼量增加。他們實(shí)現(xiàn)了大量我們沒有做的抽象，增加了許多代碼，反而我們實(shí)現(xiàn)的一些能減少代碼的抽象他們卻沒有做。
這個(gè)結(jié)果讓我非常驚訝。我知道設(shè)計(jì)決定很重要，但我沒想到會(huì)導(dǎo)致如此大的差異。考慮到我只調(diào)查了我認(rèn)為很厲害的程序員的情況下，這個(gè)結(jié)果更讓我震驚。在所有的比較中，這個(gè)比較讓我學(xué)到的東西最多。
我認(rèn)為有幫助的是，我在選這門課之前讀了許多關(guān)于怎樣編寫編譯器的東西，所以我可以借鑒他人的好的設(shè)計(jì)，發(fā)現(xiàn)AST訪問者、遞歸下降分析等在課程中沒有教過的方法真得很好用。
我認(rèn)真考慮的一件事就是抽象的代價(jià)。抽象可以讓代碼在未來更容易擴(kuò)展，或者能防止特定類型的錯(cuò)誤，但需要認(rèn)真考慮，因?yàn)樗赡軙?huì)導(dǎo)致三倍的代碼量，增加理解和重構(gòu)的工作量，也讓可能出現(xiàn)bug的位置增加了三倍，導(dǎo)致測試和后續(xù)開發(fā)的時(shí)間更少。我們的課程跟真實(shí)情況不一樣的是，我們很清楚地知道我們需要實(shí)現(xiàn)什么，而且我們永遠(yuǎn)不需要回過頭來維護(hù)代碼，所以完全抵消了抽象帶來的好處。但是，如果你想讓我擴(kuò)展編譯器，添加任意新功能，而我可以選擇從哪個(gè)編譯器上開始工作，那我肯定會(huì)選擇我們自己的代碼（即使不是出于熟悉的原因）。因?yàn)槲覀兊拇a不僅代碼量更少，更容易理解，而且我還可以在知道需要擴(kuò)展后想出一個(gè)更好的抽象方法（就像C++團(tuán)隊(duì)的IR那樣）。
我還鞏固了分類法的抽象，盡管我的目的只是根據(jù)當(dāng)前的需求（如訪問者模式）來刪除代碼，以及根據(jù)當(dāng)前的需求添加抽象而已，但它還能提供可擴(kuò)展性、可調(diào)試性和正確性等。
Scala
我還跟一個(gè)上學(xué)期用Scala的朋友討論過，他們的項(xiàng)目跟我們的完全一樣。他們的編譯器包含4141行，160kb（不算測試）。他們通過了8/10個(gè)秘密測試和100%的公共測試，沒有實(shí)現(xiàn)任何額外功能。所以與我們的5906行代碼相比，他們的代碼只有0.7倍。
他們的代碼更少的原因之一就是他們采用了不同的語法分析方式。這門課程允許你使用LR表生成器工具，這個(gè)團(tuán)隊(duì)就使用了，而我之前提到的任何團(tuán)隊(duì)都沒有使用。使用這個(gè)工具后，他們就不需要自己實(shí)現(xiàn)LR表生成器。他們還從Java語法網(wǎng)站上找到了一段150行的腳本，該腳本從Java語法網(wǎng)站的頁面上搜集語法并轉(zhuǎn)換成了生成工具的輸入，從而他們不必自己寫LR語法。他們依然要用Scala構(gòu)建樹，但他們整個(gè)分析階段只用了1073行，而我們用了1443行，大部分采用LR分析的其他團(tuán)隊(duì)的代碼量都比我們的遞歸下降分析更多。
他們的編譯器的其余部分比我們的更小詞法分析器輸入的是，但沒有明顯的設(shè)計(jì)區(qū)別，盡管我沒有深入閱讀代碼。我認(rèn)為原因應(yīng)該是Scala和Rust語言之間的表示區(qū)別。Scala和Rust擁有類似的函數(shù)式編程功能，如模式匹配，這對(duì)于編譯器很有用，但Scala的受管理的內(nèi)存能節(jié)省下一些代碼。Scala還比Rust有更多的語法糖。
OCaml
由于我們團(tuán)隊(duì)所有人都在Jane 實(shí)習(xí)，所以我們考慮過的另一門語言是OCaml。我們最后決定用Rust，但很想知道OCaml會(huì)怎樣。所以我與另一個(gè)也在Jane 實(shí)習(xí)的人談了談，他們的編譯器就是用OCaml做的。
他們的編譯器是10914行，377kb，包括一小部分測試代碼，沒有額外功能，通過了9/10的秘密測試和所有的公開測試。
與其他組類似，代碼量的差異是由于他們采用了LR分析器生成器和樹重寫，詞法分析采用了正則表達(dá)式->NFA->DFA轉(zhuǎn)換管線。他們的前端（詞法分析+語法分析+AST構(gòu)建）包含5548行，我們的只有2164行，字節(jié)比例類似。他們對(duì)于語法分析器也用了 tests，我們也使用了類似的測試，但將預(yù)期的輸出放到了代碼之外，所以他們的分析器測試占了大約600行，而我們的只有200行。
他們的編譯器的其余部分是5366行（其中461行是僅有類型定義的接口文件），而我們的是4642行，如果考慮接口定義則只有1.15倍差異，不考慮接口定義，兩者則幾乎是同樣大小。所以，除了語法分析器的設(shè)計(jì)不一樣之外，Rust和OCaml的表達(dá)性很相似，除了OCaml需要一些Rust不需要的接口定義而已。
總結(jié)
總的來說，我對(duì)于比較結(jié)果非常滿意。
我從此次比較中學(xué)到了許多，也發(fā)現(xiàn)了許多令我驚訝的地方。我認(rèn)為整體來說，設(shè)計(jì)決定造成的影響要遠(yuǎn)遠(yuǎn)大于語言的選擇，而在實(shí)現(xiàn)不同的設(shè)計(jì)時(shí)，語言也是重要的，因?yàn)檎Z言提供了實(shí)現(xiàn)設(shè)計(jì)的工具。
原文：