为什么ML/OCaml适合编写编译器（1998）

# 为什么 ML/OCaml 适合编写编译器 来源：https://flint.cs.yale.edu/cs421/case-for-ml.html --- ### 为什么 ML/OCaml 适合编写编译器 **作者：** Dwight VandenBerghe **邮箱：** [email protected] **日期：** 1998/07/28 **论坛：** comp.compilers --- 我们用术语“ML”来指代 Standard ML 或 Objective Caml。我是 Ocaml 的忠实追随者，但也安装了 SML/NJ。虽然我更喜欢 Ocaml 的发行版、工具和整体实现，但如果没有 Ocaml，我很乐意使用 SML/NJ 来编写代码。（我无法代表 Haskell、gofer、hugs 或任何惰性求值语言发言。我认为存在不同类型的人，有些人喜欢延迟求值这类特性，有些人则喜欢严格按值调用。我坚定地属于后者；我喜欢严格求值的干净利落，喜欢它让我能精确理解正在发生的事情，而使用 Haskell 时我感觉不得不放弃一部分这种清晰度。但你的情况可能不同。）因此，尽管我在写“ML”时指的是 Ocaml，但我认为我的观点同样适用于 SML/NJ。 以下是我认为能让编写编译器成为一件乐事而非可怕苦差事的语言特性列表，顺序不分先后。 1. **垃圾回收。** 提到这一点可能很基础，但对于有大量复杂数据结构且具有短到中等生命周期的程序来说，垃圾回收是一个巨大的福音。而编译器首先是具有复杂数据结构的程序。要喜欢编译器，你必须是个数据结构迷。然而，C/C++、Pascal 及其同类语言，配合无限制的指针、malloc 及其近亲，让你必须自己清理垃圾。你必须同时扮演程序员和清洁工。我们中有些人是更好的程序员，而非更好的清洁工。ML 拥有或许是当下最好的垃圾回收器；它速度快到在许多实际应用中与 C++ 的 malloc/free 不相上下，在某些情况下甚至更快。你不必像使用 Java 的慢速垃圾回收那样为 ML 的 GC 忧心忡忡。它就在那里，无形、极快，始终工作，你的生活因此变得轻松许多。 2. **尾递归得到优化。** 因此，一旦你懂得如何利用这一特性，就可以编写不消耗栈空间且非常快速的树遍历代码。公平地说，有些 C++ 编译器（如 Visual C++ 5）据说能消除部分尾递归，但你不能依赖它（VC 在这方面有很多 bug）。ML 与递归高度匹配，而编译器中的许多数据结构往往最适合用递归过程来处理，因此两者搭配得很好。 3. **ML 的数据类型与编译过程相匹配。** 编译器通常不关心无符号短整型与有符号字符的区别，而是到处使用“int”以及字符串。字符串在编译器中随处可见，而 C/C++ 在处理字符串方面相当糟糕，即使有了模板也是如此。在编译器的某些地方，能对稍大于 int 的量进行算术运算是很方便的，因此“大数”工具在这些情况下实际上很有用（例如，当你需要以比底层数值类型更高的精度进行常量折叠或词法分析，然后再转换回原生形式时）。如果没有大数，你就得自己实现，或者诉诸于变通手段。（参见大师级编译器编写者 Dave Hanson 的《C 接口与实现》以了解我的意思。） 4. **ML 的类型构造器对于描述 AST（抽象语法树）之类的东西简直棒极了。** 它们实现了有时被称为“带标签的联合体”的东西——一种高效、小巧的联合数据类型，与 C/C++ 不同，它自带一个标签字段来说明联合中当前存储的是什么。这是强制性的：换句话说，没有办法绕过它。ML 的模式匹配被设计为与带标签的联合体协同工作，使得接受数据结构作为参数的函数源代码极具可读性。将这一点与类型推断和尾递归消除相结合，你就拥有了一种为递归函数而优化的语言，这些函数以复杂数据结构为参数……听起来熟悉吗？ 5. **安全性。** ML 当初被构想出来，就是为了解决使用自动定理证明器的数学家面临的主要问题：由于该领域常用语言（Lisp）的无类型、危险、随意的性质，你永远无法确定程序是否能正常工作。当然，所有语言都可能存在这个问题，但 ML 试图在限定领域的同时增加效率和安全性。ML 程序无法使系统崩溃；如果编译通过，它就能运行，并且你不会遇到段错误。你可以证明程序的某些属性，可以信任某些类型的错误根本不可能发生。例如，由于列表是不可变的，并且必须包含单一类型的元素，你不必担心意外地将整数放入字符串列表（就像在 Scheme 和 Lisp 中可能发生的那样）。实际上，你根本不能向列表中添加任何东西；你必须创建一个新列表。这使得底层例程能够比其它语言的列表快得多，在那些语言中，你必须担心双向链接、破坏性更新等问题。配合一个极快的垃圾回收系统，这一切都能完美运作……并且你晚上能睡得更踏实。 6. **ML 被设计为应用于一个以庞大、棘手、递归的数据结构以及运行在其上的复杂算法为特征的领域（定理证明）。** 听起来熟悉吗？ 7. **异常。** ML 实现了快速且干净的异常处理，如果你以前从未享受过使用异常的乐趣，这真是一种享受。你可以假设键会被找到的方式来编写表查找，然后将搜索过程包装在一个“try”块中，以捕获异常情况（“未找到”）。这样你就绝不会因为忘记测试未找到的情况而搞乱程序；如果你那样做了，运行时系统会因未捕获的异常而停止，并准确告诉你异常是在哪里抛出的。当你学会使用异常后，程序变得更易读、更清晰、更健壮。 8. **类型推断。** 在一千行 ML 代码中，你可能只需要声明两个或最多三个变量。编译器会根据变量的使用方式来推断类型。而且它不是像（比如）Perl 那样猜测。它确切地知道。我喜欢 Ocaml 胜过 SML 的一个原因是 Ocaml 不喜欢运算符重载：例如，浮点数加法有单独的运算符（“+.”），整数加法有（“+”）。类型推断和运算符重载是不舒服的床伴；在我看来，语言设计者应该两者择一，而不是试图讨好双方。但无论如何，这比 Pascal 或 C 要好，在那些语言中，编译器抛弃了所有关于用法的信息，让你一遍又一遍地陈述显而易见的事情。我们所能做的就是搞砸它，而我们也确实一遍又一遍地搞砸。 9. **Lex/yacc/burg。** ML 有这些标准工具的出色实现，一旦你知道如何使用它们，它们就能让很多工作变得简单。不，我不是 Lex 的狂热粉丝，也不认为 lalr(1) 优于 ll(k)，但我是一个实用主义者：只要工具在那里，并且实现良好，我就会使用它。Ocaml 和 SML/NJ 都有真正优秀、扎实的编译器工具实现，并且其开发者自己也在使用。没有多少语言能配带更好的工具包。 10. **我提过 Ocaml 很快吗？** 我用 Ocaml 编写了一个精算金融建模语言的编译器，大约 1 万行代码，如果用 C++ 写可能需要 2 万行或更多。在我的奔腾 200 上，它编译最大的已知程序只需 3 秒。大多数程序在不到 1 秒内编译完成。我觉得这太惊人了。 11. **支持。** 我从 Inria（特别是 Xavier Leroy 和 Pierre Weis 等人）获得的支持比我以往从任何其他语言供应商获得的支持都要好。语言本身的问题很少，而且我遇到的少数问题都在几天内得到了修复。相比之下，比如 VC++ 或 Turbo Pascal 的支持就差远了。 12. **库。** ML 的标准库包含很多数据结构相关的内容，这对开发帮助很大。我发现它比大多数其他语言那种通常拼凑在一起的混乱库更加完整、简洁、可用。 13. **模块系统。** ML 对分离编译有强大且深思熟虑的支持，允许一个单独编译的模块支持多态性（即它可以操作任意类型）。模块内部的可视性可以被精确控制。“函子”可以将一个模块特化为一个具体的实例。这非常酷，就像 C++ 模板但没有痛苦和折磨。 所以，这主要与数据结构有关。ML 非常擅长让你表达复杂的数据结构以及围绕它们的递归算法。最基础的数据结构（列表、数组、结构体、联合体、属性列表、哈希表、二叉树、队列等等）已经存在于语言中，实现良好，随时可用。你从一个在其他语言中需要自己构建的地方起步。 ML 是完美的语言吗？天哪，不是。它有许多缺点，就像所有其他语言一样。语法很奇怪，有些部分难以学习，有些部分难以使用。像 Printf 这样简单的东西表达起来可能非常奇怪。对于许多问题领域（比如我经常工作的嵌入式系统），你无法利用 ML 的优势。用它来编写数字信号处理器芯片上的 FFT 可能会很糟糕。就我所见，ML 与图形用户界面的配合还不够好，对面向对象编程的支持也欠缺（尽管我认为这是一个特性，而不是限制）。 但所有语言都有一些能使其大放异彩的问题领域。我认为编译器实现是 ML 的强项之一。你正在编写一个编译器，在某个函数中间，你需要一个 9 毫米的开口–梅花组合扳手。你打开工具箱……它就在那里，放在最上层抽屉里，明亮、闪亮、坚固。你使用了它，几分钟后，你又需要一把带夹子和磁铁的小号十字螺丝刀……它就在那里，明亮、闪亮、坚固。 这并不是说工具箱里有数量惊人的工具。（不；事实上，工具箱比通常的工具箱要小得多，你的朋友使用的那些工具箱除了洗菜盆什么都有。）而是这个工具箱由一些非常聪明的工具匠经过深思熟虑地组装而成，凝聚了他们数十年的经验，并且像所有好的工具包一样，是为一个非常特定的目的而设计的：构建快速、安全、稳固的程序，这些程序围绕函数的分开编译而组织，而这些函数主要对极其复杂的数据结构进行递归操作。 比如……编译器的程序。 —— Dwight