C++、Python、Rust、Scala构建编译器的差异性究竟有多大？-精品文档资料整理.docx

《C++、Python、Rust、Scala构建编译器的差异性究竟有多大？-精品文档资料整理.docx》由会员分享，可在线阅读，更多相关《C++、Python、Rust、Scala构建编译器的差异性究竟有多大？-精品文档资料整理.docx（30页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、C+、Python、Rust、Scala构建编译器的差异性究竟有多大？ C+编程资源合集：海量资源免费下载 C+编程/华为C+编程标准/C+编程练习题大全/编程思想/C+编程实例等资源下载 【编者按】编程语言之争是开发者们热议的永久话题 在不同语言的选择以及设计决定上也都观点不一。那么在面对大型工程时该怎样选择详细实现呢 本文的作者借课程工程之机 比拟了Rust、Haskell、OCaml、C 、Python、Scala 等语言编写的编译器差异 最终发现 这些语言在代码量以及功能实现上简直千差万别 作者 |Tristan Hume 译者 |弯月 责编 | 郭芮 出品 | CSDN ID CSD

2、Nnews 以下为译文 我在滑铁卢大学的最后一个学期选了CS444 编译原理这门课程 课程工程是编写一个编译器 将Java语言的子集编译成x86代码 三人结组 语言自由选择。 这是个难得的时机 我可以在同样的大型工程下比拟不同的实现 而且我的朋友们的程度也跟我很相近 所以我可以借这个时机看看不同的设计以及语言选择。我从这个工程中获得了不少心得 尽管这个比拟并不完美 但比那些仅靠个人观点来比拟编程语言的人要好多了。 我们的编译器是用Rust写成的 首先与另一个使用了Haskell的组进展了比拟。我认为他们的编译器应该更简洁 但实际的代码行数差不多。与另一个使用了OCaml的团队的比拟也得到了同样

3、的结果。然后我与一个使用了C 的团队比拟 结果如我意料的那样 由于有头文件 和缺乏汇总类型以及形式匹配的支持 导致他们的编译器大了30%。下一个是跟我一个朋友的Python实现进展的比拟 他的代码量不到我们的一半 这要归功于元编程以及动态类型。另一个朋友的团队使用了Scala 实现的编译器代码量也小于我们。最让我惊讶的比拟就是与另一个同样使用Rust的团队的比拟 他们的代码量是我们的三倍 因为他们采用了不同的设计决定 这最终导致了同样的功能需要的代码量产生了宏大差异 本文中首先我会来解释一下此次比拟的意义 介绍各个工程的根本情况 然后再解释引发编译器大小差异的局部原因。最后 我会谈一谈从各个比

4、拟中学到的东西。 比拟的意义 你也许会认为 代码行数 我同时比拟了代码行数以及字节数 是个很糟糕的度量 但我认为在这个工程中这种度量可以给出很有用的信息。在我看来 至少代码行数是各个不同的团队在同一个大型工程上工作时最可控的一个变数。 直到我们的工程完成之前 没有任何人 包括我 知道我会统计代码行数 所以没有人在行数度量上做手脚 每个人都尽最大努力来快速、正确地完成工程。每个人 除了后面我会谈到的使用Python的工程之外 都在实现同一个程序 目的只有一个 就是在同样的截止日期之前通过同样的自动化测试套件 所以也不会有某个组试图解决不同的问题 或解决更难的问题的情况。每个组都在这个工程上花了数

5、月的时间 大众都在逐步地添加功能 进而通过已知以及未知的测试。这意味着代码整洁易读 没有任何取巧的地方。 除了要通过的课程测试之外 代码不会被用于任何其他用处 也没人会浏览它 而且由于它只能编译Java语言的一个子集 所以它也没有任何其他用处。除了标准库之外也不允许使用任何库 甚至连辅助解析的库都不允许 假如标准库中没有包含此功能的话 。这意味着也不会出现任何仅有局部团队使用的、强大的编译器库来干扰比拟。 在最终的提交截止日期之后 会运行一次机密的测试 我们看不到该测试 也就是讲 自己编写测试用例并测试代码 可以保证编译器的强健、正确 可以以处理边界情况。 尽管介入的每个人都是学生 但我讨论的

6、这些团队都是我认为非常优秀的程序员。每个人都至少有两年度全职的实习经历 大多数都在高端的科技公司 一些公司甚至还在开发编译器。几乎每个人都有7-13年度的编程经历 都特别热衷在网上浏览课程之外的东西。 自动生成的代码没有统计在内 但生成的语法文件以及代码被统计了。 因此我认为 就各个工程需要花费的精力 和假如是长期工程的话需要花费多少精力去维护而言 代码量是一个很不错的近似统计。我认为 微小的差异也能反映出宏大的问题 比方上面讲过的用Haskell编写的编译器代码量不到C 的一半。 Rust 比拟基准 我以及团队里的另一名成员以前分别写过1万多行的Rust代码 另一个成员在某次编程马拉松工程上

7、写过大约500行Rust。我们的编译器用wc -l统计的结果是6806行 其中包括5900代码行 不包括空行以及注释 wc -c的结果为220kb。 我发现的一个问题是 这几项度量的比例在其他工程中也是相似的 只有一些微小的差异 过会儿我会介绍 。下文中提到代码行数时 我指的都是wc -l的结果 但上述结论说明 代码行数按照哪个规那么进展统计其实是无所谓的 除非十分指出 你可以通过比例进展换算。 我写过另一篇关于设计的文章 :/thume.ca/2019/04/18/writing-a-compiler-in-rust/ 这个设计通过了所有公开以及机密的测试。它还包括几个额外的特性 这些特性我

8、们仅仅是出于兴趣而开发 并没有想着通过测试。这些特性大概占用了400行。我们总共的单元测试以及测试用的代码大约占了500行。 Haskell Haskell团队由我的两个朋友组成 他们每个人大概写过几千行Haskel 还浏览过许多网上的Haskell内容 和许多其他类似的语言 如OCaml以及Lean。他们还有另一个我不太熟悉的团队成员 但似乎是个很厉害的程序员 以前也用过Haskell。 他们编译器的wc -l结果是9750行 357kb 7777 SLOC 源代码行数 。这个团队的度量比例的差异也最大 他们的编译器中行数为1.4倍 SLOC为1.3倍 字节数为1.6倍。他们并没有实现任何额

9、外功能 但通过了所有公开以及机密的测试用例。 需要指出的重要的一点是 只有把测试用例统计在内 对这个团队才公平 因为他们的代码是最正确的 包含了1600行测试用例 并且捕获了好几个团队未能捕获的边界情况 只不过是课程提供的测试用例没有覆盖到这些边界情况而已。所以 假如两者都不统计测试用例的话 他们的代码是8.1k行 我们的是6.3k行 仅是我们的1.3倍。 为了让度量更合理 我还统计了字节数 因为Haskell工程平均每行要更长 而且没有许多只有完毕括号的行 它的单行函数也不会被rustfmt分解成多行。 在与团队里的另一个朋友深化挖掘了代码大小的问题后 我们找到了以下理来历解释代码大小的差异

10、 我们采用了手写的词法分析器以及递归下降分析 recursive descent parsing 他们采用的是NFA到DFA的词法生成器 和一个LR分析器 然后再扫描一遍将解析树转换成AST 抽象语法树 是更方便的代码表示形式 。这需要占用更多代码 占了2677行 比我们的1705行大约多了1k行。 他们使用的是更漂亮的通用AST类型 能转换成不同的类型参数 因为每次解析都会添加更多信息。这需要更多的辅助函数 因此导致了他们的AST代码比我们的实现多了500行我们在解析并添加信息时使用的只是构造字面量 以及可修改的Option _ 字段。 他们大约有400多行代码用于实现更高的抽象程度 进而用

11、纯粹的函数式方式来实当代码生成以及组合 而我们是直接修改字符串。 这些差异再加上测试用例的差异 就导致了代码行数的差异。实际上 我们的文件在中间解析阶段 如常量折叠、作用域解析等 的大小跟他们的非常接近。但仍然产生了字节数上的区别 原因是行的平均长度 我估计原因是他们需要更多的代码 在每次解析时重写整个树 而我们只需要访问并修改即可。 我认为 考虑到Rust以及Haskell的设计决定非常相似 都是表达性的 只有细微的差异 如Rust在需要时可以很方便地修改变量等。另一点有意思的是 我们选择采用递归下降分析器以及手工编写词法分析器给我们带来了回报。固然这有点风险 因为教授并没有推荐这一点 我是

12、自学来的 但我发现它很易于使用 是个正确的决定。 我认为 这个团队可能并没有开发出Haskell的全部潜力。假如他们能更擅长使用Haskell 他们的代码应该行数更少。我相信 像Edward Kmeet之类的人可以使用更少的Haskell代码就能编写出同样的编译器 从这一点上来讲 我朋友的团队并没有使用过多超高级的抽象 而且他们也不允许使用更好的组合库 如lens等。但是 这样做的代价就是理解编译器的难度。团队的成员都是有经历的程序员 他们知道Haskell可以做非常漂亮的事情 但还是决定不这样做 因为他们认为 这样做花费的时间会超过节省的时间 而且会让代码变得难以理解。在我看来这确实是个正确

13、的选择 用“魔法的方式使用Haskell编写编译器 会产生“Haskell写编译器的门槛非常高 假如你不考虑对于不太解析Haskell的人的可维护性的话的结果 而这种结果并不是我们想要的。 另一个有趣的发现是 教授在开场时讲过 学生可以选择任何可以在学校效劳器上运行的语言 但同时针对Haskell提出了警告 讲过去使用Haskell的团队的分数的方差是最高的 因为许多项选择择Haskell的团队都高估了他们的Haskell才能 导致他们的得分比选择其他语言的团队低得多 也有另一局部Haskell团队像我朋友那样做得非常完美。 C 接下来我与另一个在团队中使用了C 的朋友进展了交谈。那个团队中我

14、只认识这一个人 但由于滑铁卢大学中使用C 的课程非常普遍 所以估计团队中的每个人都有C 经历。 他们的工程代码行数为8733 字节数为280kb 这些数字不包括测试代码 但包括大约500行的额外功能。与我们不含测试的代码 也包含500行的额外功能 相比 他们的代码行数为1.4倍。他们通过了100%的公开测试 但仅通过了90%的机密测试 很可能是因为它们没有实现工程要求的数组vtable 这个功能需要大约50-100行代码实现。 我并没有深化挖掘代码差异的原因 我感觉最有可能的解释为 他们使用了LR解析器以及树重写 而没有采用递归下降分析器 C 缺乏汇总类型以及形式匹配这两个非常常用的功能 他们

15、需要重复头文件中所有的函数签名 而Rust不需要这样做。 我们比拟的另一件事是编译时间。在我的笔记本上 我们的编译器的调试版完好编译需要9.7秒 调试版增量编译需要3.5秒。我的朋友并没有给出他们的C 编译器的构建时间 采用并行make 但讲我提供的数字与他们的非常接近 而且讲他们把一些常用的小函数的签名放到了头文件中 以增加编译时间为代价来减少函数签名的重复 也正是由于这个原因 我没有方法比拟单纯的头文件代码行数 。 Python 我的一位朋友是非常优秀的程序员 她选择使用Python独立完成工程。她还比其他团队多实现了好几个额外功能 包括带有存放器分配的SSA立即表示 还有其他优化。另一方

16、面 由于她是独立完成的 而且实现了许多额外的功能 因此她在代码质量上只花费了最小限度的经历 例如所有错误都会抛出统一的异常 所以调试时需要进展栈跟踪 而不是像我们一样每种错误都给出特定的错误类型以及错误信息。 她的编译器只有4581行 并且通过了所有公开测试以及机密测试。她实现的功能比所有其他团队都多得多 但很难确定那些功能占了多少行代码 因为许多额外功能与每个人都在做的功能都一样 比方常量折叠、代码生成等 但功能却更强大。额外的功能估计至少占用了10002000行 所以我很确信她的代码的表达性要比我们至少高两倍。 造成这种差异的最大原因很可能是动态类型。我们的ast.rs中类型定义就占了50

17、0行 编译器的其他局部还有更多的类型定义。我们还通过类型系统做了各种类型限制。例如 我们需要根底设施 才能在分析代码经过中向AST中添加信息供以后使用 而Python中只需要给AST结点添加新的域即可。 强大的元编程也是造成差异的原因之一。例如 尽管她用的是LR分析器而不是递归下降分析器 但她的工程代码量更小 因为她不需要进展树重写的经过 而是在LR语法中参加了Python代码片段来构建AST 而生成器可以直接利用eval变成Python函数。我们没有采用LR分析器的局部原因是 不使用树重写来构建AST需要大量的代码 生成的Rust文件或者经过式的宏 将语法绑定到Rust代码片段上。 元编程以

18、及动态类型的强大之处的另一个例子是 我们有个名为visit.rs的文件有400行 里面大局部是重复性的样板代码 仅为了实如今各种AST构造上的访问。在Python中只需要一个大约10行的函数即可递归地访问AST结点的各个域 通过_dict_属性 。 作为Rust以及静态类型语言的爱好者 我需要指出 类型系统非常有助于防止bug以及进步性能。强大的元编程同时会让代码更难理解 但是 这个比拟结果仍然让我非常惊讶 我没想到代码的差异能有如此之大。假如差异真的导致需要写两倍的代码 那我仍然认为Rust的付出是值得的 但两倍的差异确实不可无视 我以后会考虑在独立完成某项工作中的一次性代码时使用Ruby或

19、者Python。 Rust 另一个组 最后一个比拟 也是最有意思的 就是我以及另一个朋友的比拟。他们组还有另一个成员 我不认识 使用的也是Rust。我的朋友有许多Rust经历 也介入过Rust编译器 也读过许多资料。但我不解析他的组员怎样。 他们的工程有17,211行代码 不算注释的话有15000行 不包括测试代码以及生成的代码共有637kb。他们没有实现任何额外功能 仅通过了4/10个机密测试 和90%的公开测试 因为他们没有时间在截止日期之前实现工程要求中的高级局部。同样的语言 代码量却是我们的三倍 但功能却更少 这个结果非常让我吃惊 与之相比 之前的比拟都黯然无光了。所以我们比拟了wc

20、-l中的每个文件大小 和仔细检查各个功能是如何实现的。 似乎我们做出的设计决定完全不一样。例如 他们的前端 词法、解析、AST构建 包括7597行 而我们的只有2164行。他们使用的是基于DFA的词法分析器以及LALR(1)语法分析器 但其他采用了类似方案的组并没有写如此之多的代码。仔细检查他们的代码后 我发现了许多不同的设计决定 他们采用了有完好类型的解析树 而不是标准的、基于字符串的同态解析树。因此需要更多类型定义 和解析经过中需要更多的转换代码 或需要更复杂的解析生成器。 他们在验证正确性时 使用了TryFrom在解析树类型以及AST类型之间相互转换 这导致了大量的1020行的impl代

21、码块。我们使用了返回Result类型的函数来实现同样的功能 额外代码量更小 也不必对构造过度添加类型 进而参数的重用更容易。我们的局部代码仅有一行match 对于他们那么需要10行的impl语句。 我们的类型需要更少的复制粘贴。例如 他们设置了单独的is_abstract、is_native以及is_static域 由此导致的约束使得检验的代码需要被复制粘贴两次 一次在不返回结果的方法中 另一次在返回结果的方法中 两者只有微小的修改。对于我们来讲 void只是一个特殊的类型 我们想出了一个方法 按照mode以及visibility分类 进而在类型的层次上保证这些约束 约束的错误由match语句

22、的default case生成 可以直接转变成mode以及visibility所需的modifier。 我没有查看他们代码中的分析经过 但这个经过也一样大。我跟我的朋友聊了聊 似乎他们的实现跟我们的访问者根底架构完全不一样。我猜其他一些小的设计差异也导致了代码量的区别。 访问者形式让我们的分析经过只需要关注它们需要关注的AST 而不用去匹配整个AST构造 进而节省了大量代码。 他们的代码生成局部是3594行 我们的只有1560行。我看了他们的代码 似乎所有的差异都在于他们采用了一种中间数据构造来生成汇编指令 而我们只使用了根本的字符串直接输出汇编代码。他们的做法需要为所有的指令以及操作数定义类

23、型以及输出函数 这也意味着 构建汇编指令需要消耗更多的代码 而我们的只需要使用类似于mov ecx, edx的指令 而他们需要一条宏大得被rustfmt分割成6行的语句 其中生成指令时 操作数使用了许多中间类型 还涉及了多达6层的嵌套括号。我们的输出局部也只是一个格式化语句 而他们需要为每条指令单独构造。 我的团队也曾考虑过使用这种级别的抽象。假如能直接输出文本形式的汇编 或直接输出机器码 那就会方便许多 但这并不是课程的要求。同样的东西可以使用X86Writer加上类似于push(reg: Register)之类的方法很简单地完成 代码量更少 效率更高。我们考虑过的另一个角度是 抽象也许能让

24、调试以及测试更简单 但我们意识到 直接查看生成的文本汇编 可能会更容易浏览以及测试。但我们预测到 显然是正确的 那样做会导致大量的额外代码 而且并不能给我们带来任何实际的好处 所以我们没有做。 可以跟C 那个组使用的中间表示形式做个比拟。他们将中间表示形式作为额外功能来实现 占用了大约500行代码。他们采用的数据构造非常简单 用于简单的类型定义以及代码生成 它采用的操作与Java要求的很接近。也就是讲 他们的IR比生成的汇编更小 因此需要的构造代码更少 因为许多语言的操作 如调用、强迫类型转换等 需要大量的汇编指令。高层表示也使他们得以在IR上做一些简单的优化。C 团队想出了一个非常好的设计

25、所以他们能用更少的代码完成更多的功能。 总的来看 3倍的代码量似乎完全由不同的设计决定导致 每个设计决定的不同都导致了或者大或者小的代码量增加。他们实现了大量我们没有做的抽象 增加了许多代码 反而我们实现的一些能减少代码的抽象他们却没有做。 这个结果让我非常惊讶。我知道设计决定很重要 但我没想到会导致如此大的差异。考虑到我只调查了我认为很厉害的程序员的情况下 这个结果更让我震惊。在所有的比拟中 这个比拟让我学到的东西最多。 我认为有帮助的是 我在选这门课之前读了许多关于如何编写编译器的东西 所以我可以借鉴别人的好的设计 发现AST访问者、递归下降分析等在课程中没有教过的方法真得很好用。 我认真

26、考虑的一件事就是抽象的代价。抽象可以让代码在将来更容易扩展 或能防止特定类型的错误 但需要认真考虑 因为它可能会导致三倍的代码量 增加理解以及重构的工作量 也让可能出现bug的位置增加了三倍 导致测试以及后续开发的时间更少。我们的课程跟真实情况不一样的是 我们很清楚地知道我们需要实现什么 而且我们永远不需要回过头来维护代码 所以完全抵消了抽象带来的好处。但是 假如你想让我扩展编译器 添加任意新功能 而我可以选择从哪个编译器上开场工作 那我肯定会选择我们自己的代码 即使不是出于熟悉的原因 。因为我们的代码不仅代码量更少 更容易理解 而且我还可以在知道需要扩展后想出一个更好的抽象方法 就像C 团队

27、的IR那样 。 我还稳固了分类法的抽象 尽管我的目的只是根据当前的需求 如访问者形式 来删除代码 和根据当前的需求添加抽象而已 但它还能提供可扩展性、可调试性以及正确性等。 Scala 我还跟一个上学期用Scala的朋友讨论过 他们的工程跟我们的完全一样。他们的编译器包含4141行 160kb 不算测试 。他们通过了8/10个机密测试以及100%的公共测试 没有实现任何额外功能。所以与我们的5906行代码相比 他们的代码只有0.7倍。 他们的代码更少的原因之一就是他们采用了不同的语法分析方式。这门课程允许你使用LR表生成器工具 这个团队就使用了 而我之前提到的任何团队都没有使用。使用这个工具后

28、 他们就不需要自己实现LR表生成器。他们还从Java语法网站上找到了一段150行的Python脚本 该脚本从Java语法网站的页面上搜集语法并转换成了生成工具的输入 进而他们不必自己写LR语法。他们仍然要用Scala构建树 但他们整个分析阶段只用了1073行 而我们用了1443行 大局部采用LR分析的其他团队的代码量都比我们的递归下降分析更多。 他们的编译器的其余局部比我们的更小 但没有明显的设计区别 尽管我没有深化浏览代码。我认为原因应该是Scala以及Rust语言之间的表示区别。Scala以及Rust拥有类似的函数式编程功能 如形式匹配 这对于编译器很有用 但Scala的受管理的内存能节省

29、下一些代码。Scala还比Rust有更多的语法糖。 OCaml 由于我们团队所有人都在Jane Street实习 所以我们考虑过的另一门语言是OCaml。我们最后决定用Rust 但很想知道OCaml会如何。所以我与另一个也在Jane Street实习的人谈了谈 他们的编译器就是用OCaml做的。 他们的编译器是10914行 377kb 包括一小局部测试代码 没有额外功能 通过了9/10的机密测试以及所有的公开测试。 与其他组类似 代码量的差异是由于他们采用了LR分析器生成器以及树重写 词法分析采用了正那么表达式- NFA- DFA转换管线。他们的前端 词法分析 语法分析 AST构建 包含554

30、8行 我们的只有2164行 字节比例类似。他们对于语法分析器也用了expect tests 我们也使用了类似的测试 但将预期的输出放到了代码之外 所以他们的分析器测试占了大约600行 而我们的只有200行。 他们的编译器的其余局部是5366行 其中461行是仅有类型定义的接口文件 而我们的是4642行 假如考虑接口定义那么只有1.15倍差异 不考虑接口定义 两者那么几乎是同样大小。所以 除了语法分析器的设计不一样之外 Rust以及OCaml的表达性很相似 除了OCaml需要一些Rust不需要的接口定义而已。 总结 总的来讲 我对于比拟结果非常满意。 我从此次比拟中学到了许多 也发现了许多令我惊

31、讶的地方。我认为整体来讲 设计决定造成的影响要远远大于语言的选择 而在实现不同的设计时 语言也是重要的 因为语言提供了实现设计的工具。 原文 :/thume.ca/2019/04/29/comparing-compilers-in-rust-haskell-c-and-python/ 本文为 CSDN 翻译 转载请注明来源出处。 *本文仅代表作者观点 转载请联络原作者 精彩推荐 比写代码更重要的是抓住下一个技术风口。6月AI技术福利 亚马逊、微软、BTA、滴滴、字节跳动、美团等一线公司大牛带你一起探究机器学习、数据分析、自然语言处理、知识图谱等热门技术领域的将来方向和落地理论。 限免最后1天 速领 推荐浏览 我发现一个新的软件 用自然语言编程 非常酷 你点的每个“在看 我都认真当成了喜欢