【CSDN 編者按】編程語言之爭是開發者們熱議的永恒話題，在不同語言的選擇和設計決定上也都觀點不一。那么在面對大型項目時該如何選擇具體實現呢？本文的作者借課程項目之機，比較了Rust、Haskell、OCaml、C++、Python、Scala 等語言編寫的編譯器差異，最終發現，這些語言在代碼量和功能實現上簡直千差萬別！

作者 |?Tristan Hume

譯者 |?彎月，責編 | 郭芮

出品 | CSDN（ID：CSDNnews）

以下為譯文：

我在滑鐵盧大學的最后一個學期選了CS444：編譯原理這門課程，課程項目是編寫一個編譯器，將Java語言的子集編譯成x86代碼，三人結組，語言自由選擇。

?

這是個難得的機會，我可以在同樣的大型項目下比較不同的實現，而且我的朋友們的水平也跟我很相近，所以我可以借這個機會看看不同的設計和語言選擇。我從這個項目中獲得了不少心得，盡管這個比較并不完美，但比那些僅靠個人觀點來比較編程語言的人要好多了。

?

我們的編譯器是用Rust寫成的，首先與另一個使用了Haskell的組進行了比較。我認為他們的編譯器應該更簡潔，但實際的代碼行數差不多。與另一個使用了OCaml的團隊的比較也得到了同樣的結果。然后我與一個使用了C++的團隊比較，結果如我預料的那樣，由于有頭文件，以及缺乏匯總類型和模式匹配的支持，導致他們的編譯器大了30%。下一個是跟我一個朋友的Python實現進行的比較，他的代碼量不到我們的一半，這要歸功于元編程和動態類型。另一個朋友的團隊使用了Scala，實現的編譯器代碼量也小于我們。最讓我驚訝的比較就是與另一個同樣使用Rust的團隊的比較，他們的代碼量是我們的三倍，因為他們采用了不同的設計決定，這最終導致了同樣的功能需要的代碼量產生了巨大差異！

?

本文中首先我會來解釋一下此次比較的意義，介紹各個項目的基本情況，然后再解釋引發編譯器大小差異的部分原因。最后，我會談一談從各個比較中學到的東西。

?

?

比較的意義

?

?

你也許會認為，代碼行數（我同時比較了代碼行數和字節數）是個很糟糕的度量，但我認為在這個項目中這種度量可以給出很有用的信息。在我看來，至少代碼行數是各個不同的團隊在同一個大型項目上工作時最可控的一個變數。

?

• 直到我們的項目完成之前，沒有任何人（包括我）知道我會統計代碼行數，所以沒有人在行數度量上做手腳，每個人都盡最大努力來快速、正確地完成項目。每個人（除了后面我會談到的使用Python的項目之外）都在實現同一個程序，目的只有一個，就是在同樣的截止日期之前通過同樣的自動化測試套件，所以也不會有某個組試圖解決不同的問題，或者解決更難的問題的情況。每個組都在這個項目上花了數月的時間，大家都在逐步地添加功能，從而通過已知和未知的測試。這意味著代碼整潔易讀，沒有任何取巧的地方。

?

• 除了要通過的課程測試之外，代碼不會被用于任何其他用途，也沒人會閱讀它，而且由于它只能編譯Java語言的一個子集，所以它也沒有任何其他用途。除了標準庫之外也不允許使用任何庫，甚至連輔助解析的庫都不允許（如果標準庫中沒有包含此功能的話）。這意味著也不會出現任何僅有部分團隊使用的、強大的編譯器庫來干擾比較。

?

• 在最終的提交截止日期之后，會運行一次秘密的測試（我們看不到該測試），也就是說，自己編寫測試用例并測試代碼，可以保證編譯器的健壯、正確，也可以處理邊界情況。

?

• 盡管參與的每個人都是學生，但我討論的這些團隊都是我認為非常優秀的程序員。每個人都至少有兩年全職的實習經驗，大多數都在高端的科技公司，一些公司甚至還在開發編譯器。幾乎每個人都有7-13年的編程經驗，都十分熱衷在網上閱讀課程之外的東西。

?

• 自動生成的代碼沒有統計在內，但生成的語法文件和代碼被統計了。

?

因此我認為，就各個項目需要花費的精力，以及如果是長期項目的話需要花費多少精力去維護而言，代碼量是一個很不錯的近似統計。我認為，微小的差異也能反映出巨大的問題，比如上面說過的用Haskell編寫的編譯器代碼量不到C++的一半。

?

?

Rust（比較基準）

?

?

我和團隊里的另一名成員以前分別寫過1萬多行的Rust代碼，另一個成員在某次編程馬拉松項目上寫過大約500行Rust。我們的編譯器用wc -l統計的結果是6806行，其中包括5900代碼行（不包括空行和注釋），wc -c的結果為220kb。

?

我發現的一個問題是，這幾項度量的比例在其他項目中也是相似的，只有一些微小的差異（過會兒我會介紹）。下文中提到代碼行數時，我指的都是wc -l的結果，但上述結論表明，代碼行數按照哪個規則進行統計其實是無所謂的（除非特別指出），你可以通過比例進行換算。

?

我寫過另一篇關于設計的文章（http://thume.ca/2019/04/18/writing-a-compiler-in-rust/），這個設計通過了所有公開和秘密的測試。它還包括幾個額外的特性，這些特性我們僅僅是出于興趣而開發，并沒有想著通過測試。這些特性大概占用了400行。我們總共的單元測試和測試用的代碼大約占了500行。

?

?

Haskell

?

?

Haskell團隊由我的兩個朋友組成，他們每個人大概寫過幾千行Haskel，還閱讀過許多網上的Haskell內容，以及許多其他類似的語言，如OCaml和Lean。他們還有另一個我不太熟悉的團隊成員，但似乎是個很厲害的程序員，以前也用過Haskell。

?

他們編譯器的wc -l結果是9750行，357kb，7777 SLOC（源代碼行數）。這個團隊的度量比例的差別也最大，他們的編譯器中行數為1.4倍，SLOC為1.3倍，字節數為1.6倍。他們并沒有實現任何額外功能，但通過了所有公開和秘密的測試用例。

?

需要指出的重要的一點是，只有把測試用例統計在內，對這個團隊才公平，因為他們的代碼是最正確的，包含了1600行測試用例，并且捕獲了好幾個團隊未能捕獲的邊界情況，只不過是課程提供的測試用例沒有覆蓋到這些邊界情況而已。所以，如果兩者都不統計測試用例的話，他們的代碼是8.1k行，我們的是6.3k行，僅是我們的1.3倍。

?

為了讓度量更合理，我還統計了字節數，因為Haskell項目平均每行要更長，而且沒有許多只有結束括號的行，它的單行函數也不會被rustfmt分解成多行。

?

在與團隊里的另一個朋友深入挖掘了代碼大小的問題后，我們找到了以下理由來解釋代碼大小的差異：

?

• 我們采用了手寫的詞法分析器和遞歸下降分析（recursive descent parsing），他們采用的是NFA到DFA的詞法生成器，以及一個LR分析器，然后再掃描一遍將解析樹轉換成AST（抽象語法樹，是更方便的代碼表示形式）。這需要占用更多代碼，占了2677行，比我們的1705行大約多了1k行。

  ?

• 他們使用的是更漂亮的通用AST類型，能轉換成不同的類型參數，因為每次解析都會添加更多信息。這需要更多的輔助函數，因此導致了他們的AST代碼比我們的實現多了500行——我們在解析并添加信息時使用的只是結構字面量，和可修改的Option<_>字段。

  ?

• 他們大約有400多行代碼用于實現更高的抽象程度，從而用純粹的函數式方式來實現代碼生成和組合，而我們是直接修改字符串。

?

這些差異再加上測試用例的差異，就導致了代碼行數的差別。實際上，我們的文件在中間解析階段（如常量折疊、作用域解析等）的大小跟他們的非常接近。但依然產生了字節數上的區別，原因是行的平均長度，我估計原因是他們需要更多的代碼，在每次解析時重寫整個樹，而我們只需要訪問并修改即可。

?

我認為，考慮到Rust和Haskell的設計決定非常相似，都是表達性的，只有細微的差異，如Rust在需要時能夠很方便地修改變量等。另一點有意思的是，我們選擇采用遞歸下降分析器和手工編寫詞法分析器給我們帶來了回報。雖然這有點風險，因為教授并沒有推薦這一點，我是自學來的，但我發現它很易于使用，是個正確的決定。

?

我認為，這個團隊可能并沒有開發出Haskell的全部潛力。如果他們能更善于使用Haskell，他們的代碼應該行數更少。我相信，像Edward Kmeet之類的人可以使用更少的Haskell代碼就能編寫出同樣的編譯器，從這一點上來說，我朋友的團隊并沒有使用太多超高級的抽象，而且他們也不允許使用更好的組合庫，如lens等。但是，這樣做的代價就是理解編譯器的難度。團隊的成員都是有經驗的程序員，他們知道Haskell可以做非常漂亮的事情，但還是決定不這樣做，因為他們認為，這樣做花費的時間會超過節省的時間，而且會讓代碼變得難以理解。在我看來這的確是個正確的選擇，用“魔法”的方式使用Haskell編寫編譯器，會產生“Haskell寫編譯器的門檻非常高，如果你不考慮對于不太了解Haskell的人的可維護性的話”的結果，而這種結果并不是我們想要的。

?

另一個有趣的發現是，教授在開始時說過，學生可以選擇任何能夠在學校服務器上運行的語言，但同時針對Haskell提出了警告，說過去使用Haskell的團隊的分數的方差是最高的，因為許多選擇Haskell的團隊都高估了他們的Haskell能力，導致他們的得分比選擇其他語言的團隊低得多，也有另一部分Haskell團隊像我朋友那樣做得非常完美。

?

?

C++

?

?

接下來我與另一個在團隊中使用了C++的朋友進行了交談。那個團隊中我只認識這一個人，但由于滑鐵盧大學中使用C++的課程非常普遍，所以估計團隊中的每個人都有C++經驗。

?

他們的項目代碼行數為8733，字節數為280kb，這些數字不包括測試代碼，但包括大約500行的額外功能。與我們不含測試的代碼（也包含500行的額外功能）相比，他們的代碼行數為1.4倍。他們通過了100%的公開測試，但僅通過了90%的秘密測試，很可能是因為它們沒有實現項目要求的數組vtable，這個功能需要大約50-100行代碼實現。

?

我并沒有深入挖掘代碼差異的原因，我感覺最有可能的解釋為：

?

• 他們使用了LR解析器和樹重寫，而沒有采用遞歸下降分析器；

• C++缺乏匯總類型和模式匹配這兩個非常常用的功能；

• 他們需要重復頭文件中所有的函數簽名，而Rust不需要這樣做。

?

我們比較的另一件事是編譯時間。在我的筆記本上，我們的編譯器的調試版完整編譯需要9.7秒，調試版增量編譯需要3.5秒。我的朋友并沒有給出他們的C++編譯器的構建時間（采用并行make），但說我提供的數字與他們的非常接近，而且說他們把一些常用的小函數的簽名放到了頭文件中，以增加編譯時間為代價來減少函數簽名的重復（也正是由于這個原因，我沒有辦法比較單純的頭文件代碼行數）。

?

?

Python

?

?

我的一位朋友是非常優秀的程序員，她選擇使用Python獨立完成項目。她還比其他團隊多實現了好幾個額外功能，包括帶有寄存器分配的SSA立即表示，還有其他優化。另一方面，由于她是獨立完成的，而且實現了許多額外的功能，因此她在代碼質量上只花費了最小限度的經歷，例如所有錯誤都會拋出統一的異常（所以調試時需要進行棧跟蹤），而不是像我們一樣每種錯誤都給出特定的錯誤類型和錯誤信息。

?

她的編譯器只有4581行，并且通過了所有公開測試和秘密測試。她實現的功能比所有其他團隊都多得多，但很難確定那些功能占了多少行代碼，因為許多額外功能與每個人都在做的功能都相同，比如常量折疊、代碼生成等，但功能卻更強大。額外的功能估計至少占用了1000~2000行，所以我很確信她的代碼的表達性要比我們至少高兩倍。

?

造成這種差異的最大原因很可能是動態類型。我們的ast.rs中類型定義就占了500行，編譯器的其他部分還有更多的類型定義。我們還通過類型系統做了各種類型限制。例如，我們需要基礎設施，才能在分析代碼過程中向AST中添加信息供以后使用，而Python中只需要給AST結點添加新的域即可。

?

強大的元編程也是造成差異的原因之一。例如，盡管她用的是LR分析器而不是遞歸下降分析器，但她的項目代碼量更小，因為她不需要進行樹重寫的過程，而是在LR語法中加入了Python代碼片段來構建AST，而生成器可以直接利用eval變成Python函數。我們沒有采用LR分析器的部分原因是，不使用樹重寫來構建AST需要大量的代碼（生成的Rust文件或過程式的宏）將語法綁定到Rust代碼片段上。

?

元編程和動態類型的強大之處的另一個例子是，我們有個名為visit.rs的文件有400行，里面大部分是重復性的樣板代碼，僅為了實現在各種AST結構上的訪問。在Python中只需要一個大約10行的函數即可遞歸地訪問AST結點的各個域（通過__dict__屬性）。

?

作為Rust和靜態類型語言的愛好者，我需要指出，類型系統非常有助于避免bug和提高性能。強大的元編程同時會讓代碼更難理解，但是，這個比較結果依然讓我非常驚訝，我沒想到代碼的差異能有如此之大。如果差異真的導致需要寫兩倍的代碼，那我依然認為Rust的付出是值得的，但兩倍的差異的確不可忽視，我以后會考慮在獨立完成某項工作中的一次性代碼時使用Ruby或Python。

?

?

?

Rust（另一個組）

?

?

最后一個比較，也是最有意思的，就是我和另一個朋友的比較。他們組還有另一個成員（我不認識），使用的也是Rust。我的朋友有許多Rust經驗，也參與過Rust編譯器，也讀過許多資料。但我不了解他的組員如何。

?

他們的項目有17,211行代碼，不算注釋的話有15000行，不包括測試代碼和生成的代碼共有637kb。他們沒有實現任何額外功能，僅通過了4/10個秘密測試，以及90%的公開測試，因為他們沒有時間在截止日期之前實現項目要求中的高級部分。同樣的語言，代碼量卻是我們的三倍，但功能卻更少！

?

這個結果非常讓我吃驚，與之相比，之前的比較都黯然無光了。所以我們比較了wc -l中的每個文件大小，以及仔細檢查各個功能是怎樣實現的。

?

似乎我們做出的設計決定完全不一樣。例如，他們的前端（詞法、解析、AST構建）包括7597行，而我們的只有2164行。他們使用的是基于DFA的詞法分析器和LALR(1)語法分析器，但其他采用了類似方案的組并沒有寫如此之多的代碼。仔細檢查他們的代碼后，我發現了許多不同的設計決定：

?

• 他們采用了有完整類型的解析樹，而不是標準的、基于字符串的同態解析樹。因此需要更多類型定義，以及解析過程中需要更多的轉換代碼，或者需要更復雜的解析生成器。

?

• 他們在驗證正確性時，使用了TryFrom在解析樹類型和AST類型之間互相轉換，這導致了大量的10~20行的impl代碼塊。我們使用了返回Result類型的函數來實現同樣的功能，額外代碼量更小，也不必對結構過度添加類型，從而參數的重用更容易。我們的部分代碼僅有一行match，對于他們則需要10行的impl語句。

?

• 我們的類型需要更少的復制粘貼。例如，他們設置了單獨的is_abstract、is_native和is_static域，由此導致的約束使得檢驗的代碼需要被復制粘貼兩次，一次在不返回結果的方法中，另一次在返回結果的方法中，兩者只有微小的修改。對于我們來說，void只是一個特殊的類型，我們想出了一個方法，按照mode和visibility分類，從而在類型的層次上保證這些約束，約束的錯誤由match語句的default case生成，可以直接轉變成mode和visibility所需的modifier。

?

我沒有查看他們代碼中的分析過程，但這個過程也一樣大。我跟我的朋友聊了聊，似乎他們的實現跟我們的訪問者基礎架構完全不一樣。我猜其他一些小的設計差異也導致了代碼量的區別。

?

訪問者模式讓我們的分析過程只需要關注它們需要關注的AST，而不用去匹配整個AST結構，從而節省了大量代碼。

?

他們的代碼生成部分是3594行，我們的只有1560行。我看了他們的代碼，似乎所有的差異都在于他們采用了一種中間數據結構來生成匯編指令，而我們只使用了基本的字符串直接輸出匯編代碼。他們的做法需要為所有的指令和操作數定義類型和輸出函數，這也意味著，構建匯編指令需要耗費更多的代碼，而我們的只需要使用類似于mov ecx, [edx]的指令，而他們需要一條巨大得被rustfmt分割成6行的語句，其中生成指令時，操作數使用了許多中間類型，還涉及了多達6層的嵌套括號。我們的輸出部分也只是一個格式化語句，而他們需要為每條指令單獨構造。

?

我的團隊也曾考慮過使用這種級別的抽象。如果能直接輸出文本形式的匯編，或者直接輸出機器碼，那就會方便許多，但這并不是課程的要求。同樣的東西可以使用X86Writer加上類似于push(reg: Register)之類的方法很簡單地完成，代碼量更少，效率更高。我們考慮過的另一個角度是，抽象也許能讓調試和測試更簡單，但我們意識到，直接查看生成的文本匯編，可能會更容易閱讀和測試。但我們預測到（顯然是正確的），那樣做會導致大量的額外代碼，而且并不能給我們帶來任何實際的好處，所以我們沒有做。

?

可以跟C++那個組使用的中間表示形式做個比較。他們將中間表示形式作為額外功能來實現，占用了大約500行代碼。他們采用的數據結構非常簡單（用于簡單的類型定義和代碼生成），它采用的操作與Java要求的很接近。也就是說，他們的IR比生成的匯編更小（因此需要的構造代碼更少），因為許多語言的操作（如調用、強制類型轉換等）需要大量的匯編指令。高層表示也使他們得以在IR上做一些簡單的優化。C++團隊想出了一個非常好的設計，所以他們能用更少的代碼完成更多的功能。

?

總的來看，3倍的代碼量似乎完全由不同的設計決定導致，每個設計決定的不同都導致了或大或小的代碼量增加。他們實現了大量我們沒有做的抽象，增加了許多代碼，反而我們實現的一些能減少代碼的抽象他們卻沒有做。

?

這個結果讓我非常驚訝。我知道設計決定很重要，但我沒想到會導致如此大的差異。考慮到我只調查了我認為很厲害的程序員的情況下，這個結果更讓我震驚。在所有的比較中，這個比較讓我學到的東西最多。

?

我認為有幫助的是，我在選這門課之前讀了許多關于怎樣編寫編譯器的東西，所以我可以借鑒他人的好的設計，發現AST訪問者、遞歸下降分析等在課程中沒有教過的方法真得很好用。

?

我認真考慮的一件事就是抽象的代價。抽象可以讓代碼在未來更容易擴展，或者能防止特定類型的錯誤，但需要認真考慮，因為它可能會導致三倍的代碼量，增加理解和重構的工作量，也讓可能出現bug的位置增加了三倍，導致測試和后續開發的時間更少。我們的課程跟真實情況不一樣的是，我們很清楚地知道我們需要實現什么，而且我們永遠不需要回過頭來維護代碼，所以完全抵消了抽象帶來的好處。但是，如果你想讓我擴展編譯器，添加任意新功能，而我可以選擇從哪個編譯器上開始工作，那我肯定會選擇我們自己的代碼（即使不是出于熟悉的原因）。因為我們的代碼不僅代碼量更少，更容易理解，而且我還可以在知道需要擴展后想出一個更好的抽象方法（就像C++團隊的IR那樣）。

?

我還鞏固了分類法的抽象，盡管我的目的只是根據當前的需求（如訪問者模式）來刪除代碼，以及根據當前的需求添加抽象而已，但它還能提供可擴展性、可調試性和正確性等。

?

?

Scala

?

?

我還跟一個上學期用Scala的朋友討論過，他們的項目跟我們的完全一樣。他們的編譯器包含4141行，160kb（不算測試）。他們通過了8/10個秘密測試和100%的公共測試，沒有實現任何額外功能。所以與我們的5906行代碼相比，他們的代碼只有0.7倍。

?

他們的代碼更少的原因之一就是他們采用了不同的語法分析方式。這門課程允許你使用LR表生成器工具，這個團隊就使用了，而我之前提到的任何團隊都沒有使用。使用這個工具后，他們就不需要自己實現LR表生成器。他們還從Java語法網站上找到了一段150行的Python腳本，該腳本從Java語法網站的頁面上搜集語法并轉換成了生成工具的輸入，從而他們不必自己寫LR語法。他們依然要用Scala構建樹，但他們整個分析階段只用了1073行，而我們用了1443行，大部分采用LR分析的其他團隊的代碼量都比我們的遞歸下降分析更多。

?

他們的編譯器的其余部分比我們的更小，但沒有明顯的設計區別，盡管我沒有深入閱讀代碼。我認為原因應該是Scala和Rust語言之間的表示區別。Scala和Rust擁有類似的函數式編程功能，如模式匹配，這對于編譯器很有用，但Scala的受管理的內存能節省下一些代碼。Scala還比Rust有更多的語法糖。

?

?

OCaml

?

?

由于我們團隊所有人都在Jane Street實習，所以我們考慮過的另一門語言是OCaml。我們最后決定用Rust，但很想知道OCaml會怎樣。所以我與另一個也在Jane Street實習的人談了談，他們的編譯器就是用OCaml做的。

?

他們的編譯器是10914行，377kb，包括一小部分測試代碼，沒有額外功能，通過了9/10的秘密測試和所有的公開測試。

?

與其他組類似，代碼量的差異是由于他們采用了LR分析器生成器和樹重寫，詞法分析采用了正則表達式->NFA->DFA轉換管線。他們的前端（詞法分析+語法分析+AST構建）包含5548行，我們的只有2164行，字節比例類似。他們對于語法分析器也用了expect tests，我們也使用了類似的測試，但將預期的輸出放到了代碼之外，所以他們的分析器測試占了大約600行，而我們的只有200行。

?

他們的編譯器的其余部分是5366行（其中461行是僅有類型定義的接口文件），而我們的是4642行，如果考慮接口定義則只有1.15倍差異，不考慮接口定義，兩者則幾乎是同樣大小。所以，除了語法分析器的設計不一樣之外，Rust和OCaml的表達性很相似，除了OCaml需要一些Rust不需要的接口定義而已。

別驚訝！人工智能時代即將到來！

https://edu.csdn.net/topic/ai30?utm_source=csdn_bw

?

總結

?

?

總的來說，我對于比較結果非常滿意。

?

我從此次比較中學到了許多，也發現了許多令我驚訝的地方。我認為整體來說，設計決定造成的影響要遠遠大于語言的選擇，而在實現不同的設計時，語言也是重要的，因為語言提供了實現設計的工具。

?

原文：http://thume.ca/2019/04/29/comparing-compilers-in-rust-haskell-c-and-python/

本文為 CSDN 翻譯，轉載請注明來源出處。

?

?熱 文 ?推 薦?

? 微信解封快手鏈接；AWS 證實宕機；微軟內部疑禁用 Slack | 極客頭條

? 為什么我不使用 Web 組件？

V 語言強勢登頂 GitHub TOP1，欲取 Go 而代之？

? 華為最強自研 NPU 問世，麒麟 810 “拋棄”寒武紀

? LinkedIn最新報告: 區塊鏈成職位需求增長最快領域, 這些地區對區塊鏈人才渴求度最高……

? 中文NLP的分詞真有必要嗎？李紀為團隊四項任務評測一探究竟 | ACL 2019

? 6月技術福利限時免費領

? 搞不懂SDN？那是因為你沒看這個小故事…

她說：程序員離開電腦就是 “廢物” ！

點擊閱讀原文，輸入關鍵詞，搜索CSDN文章。

你點的每個“在看”，我都認真當成了喜歡