作者 | Tristan Hume
译者 | 弯月 @CSDN（ID：CSDNnews）
授权转载 | Python猫（ID：python_cat）
以下为译文：
我在滑铁卢大学的最后一个学期选了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不需要的接口定义而已。
总结
总的来说，我对于比较结果非常满意。
我从此次比较中学到了许多，也发现了许多令我惊讶的地方。我认为整体来说，设计决定造成的影响要远远大于语言的选择，而在实现不同的设计时，语言也是重要的，因为语言提供了实现设计的工具。
原文：http://thume.ca/2019/04/29/comparing-compilers-in-rust-haskell-c-and-python
