译文：为什么 ML/OCaml 适用于编译器开发（1998）

这封 Dwight VandenBerghe 写于 1998 年的邮件将带来有关于 ML 系语言尤其适用于编译器开发的观点。

作者: Dwight VandenBerghe

电邮地址: dwight@pentasoft.com

日期: 1998/07/28

让我们用“ML”系列来指代 SML 或 Objective Caml 等语言。我是 OCaml 的拥簇，虽然我更喜欢 OCaml 的发行版、工具链和总体实现，但我也同时使用 SML/NJ。在不能使用 OCaml 的情况下，我会很乐意用 SML/NJ 进行开发（我并不青睐 Haskell、Gofer、Hugs 等惰性求值语言；人的喜好不同，有人偏爱延迟求值（Deferred Evaluation），也有人更喜欢严格值传递，我的喜好则属于后者。我喜欢严格求值的清爽和了解每一步动作的便利，这是我为什么放弃 Haskell 的原因）。本文中用 ML 来指代，但同样适用于 OCaml 和 SML/NJ 这一类语言。

我列出来的这类语言会让编写编译器不再枯燥乏味，反而会变成一件趣事。

1. 垃圾回收（GC）

   GC 听起来非常基础，但它对有很多较短生命周期的复杂数据结构的程序非常重要。首先，编译器就是一个充满复杂数据结构的程序，如果你喜欢编译器，那你肯定着迷于数据结构。C/C++、Pascal 等语言用智能指针或malloc等手段让程序员可以手动进行垃圾回收，程序员也扮演着垃圾清道夫的角色，甚至有时候清道夫的角色会多过程序员的角色。而 ML 或许具有最好的 GC 功能，在实际运用中，ML 的 GC 速度足以与 C++的malloc/free匹敌，有时候甚至会更快。在使用 ML 的 GC 时我们不必花费精力，就像在使用 Java 一样，但 Java 的 GC 更慢。ML 的 GC 非常自然、高效、稳定，让我们的开发更加轻松。

2. 优化的尾递归

   一旦懂得利用它，就可以编写不占用过多栈空间的快速树遍历。当前，有些 C++编译器（例如 Visual C++ 5）据说已经进行了部分尾递归优化，但不能指望它们（VC 中有许多错误）。ML 非常适合编写递归，又因为编译器中的许多数据结构都能利用递归进行很好的处理，因而 ML 非常适合编写编译器。

3. ML 的数据类型适合编译处理

   编译器无需担心unsigned short和signed char，而可以只使用int（对字符串也一样）。在 C/C++中，String被广泛使用，而即使有模板类型，C/C++中的字符串类型也相当糟糕。在开发编译器时我们会遇到算术运算需要比int范围更大的数值进行运算(例如常量折叠，又或者是把基础数值类型向更精确的类型进行 tokenize，然后再转回原来的形式)，这时候就需要bignum了。如果这时候没有bignum，那么我们需要自己进行对应的实现，或者用其它的奇技淫巧。（这方面更详细的例子可以参阅了不起的编译器作者 Dave Hanson 写的《C Interfaces and Implementations》[1]）

4. ML 的类型构造器非常适合描述类似 AST（抽象语法树）的结构。

   它们实现了 tagged unions（标签联合）[2]，这是一种比 C/C++的 union 小巧而高效的 union 数据类型；它带有标签字段标记 union 中的类型，并且标签字段是强制使用的。在 ML 中，tagged union 与模式匹配一起使用，因此以数据结构为参数的函数的代码可读性会非常好。再结合类型推导和尾递归优化，ML 对采用复杂数据结构的递归函数进行了针对性优化。听起来有些耳熟是吗？

5. 安全

   ML 被认为是数学家进行自动化定理证明的解决方案，因为这一领域的常用语言（Lisp）具有无类型、危险、灵巧的特性，导致不能确定程序是否能正常工作。ML 对此加上了一些限制来提高效率和安全性；ML 程序不会导致系统崩溃，如果它正确完成了编译，那么它就会正常运行，可以保证不会发生普通的类型错误。比如，List是不可变的（immutable），并且只能包含一种类型的元素，因此不必担心意外将整数放入字符串List导致字符串List出错（就像使用 Scheme 和 Lisp 时常发生的错误）；在 ML 中，我们无法更改List中的内容，必须创建一个新List进行替换，这使得底层运行时比其他语言中的List要快得多，在其他语言中，您必须担心双向链表、破坏性更新等。再搭配上默默工作的快速 GC 系统，这一切是如此的自然…让我们可以早些下班。

6. ML 是为了单独的应用领域（即自动化定理证明[3]）而设计的。

   这一领域的特点是有庞大、棘手、递归的数据结构，它们有着与之对应的复杂算法。听起来有些耳熟是吗？

7. 异常处理（Exceptions）

   ML 实现了快速且整洁的异常处理，让开发者在使用它们时没有心智负担。假设要开发一个使用键名的表查找程序，我们会把查询功能代码放在try的代码块中并且在catch中捕获未查找到键名的异常。这样就不用担心未测试出未查找到键名的情况下程序崩溃，如果真的发生这样的异常，运行时会抛出异常消息并告知异常发生的具体位置。当我们学会使用异常处理后，程序会变得更加容易调试、整洁、鲁棒。

8. 类型接口（Type Interface）

   通常在一千行 ML 代码中我们只需要声明两三个变量。ML 通过如何使用变量来确定类型，它不会像 Perl 那样进行类型推导，它的类型是确定的。我喜欢 OCaml 多过 SML 的其中一个原因是 OCaml 不会进行运算符重载：例如，浮点加法(+.)和整数加法（+）的运算符是不同的。类型接口和运算符重载像是同床异梦的床伴，语言的设计者应该在两者之间做出取舍，而不是同时兼容二者。

9. Lex/yacc/burg

   ML 对于这些编译器工具有很好的支持。当开始上手这些工具后，你会发现它们会让许多工作变得更轻松。我不是 Lex 的粉丝，也并不喜欢 lalr(1)多过 ll(k)，但我是一个实用主义者，如果有这样被良好实现的工具我会毫不犹豫地使用。OCaml 和 SML/NJ 都拥有很不错的编译工具实现供开发者使用。像这样提供优良工具链的语言并不多见。

10. 忘了说，OCaml 非常的快

    我用 OCaml 编写了一种精算财务建模语言的编译器。它大概有一万行代码，但倘若使用 C++则可能需要两万行以上的代码。它可以在奔腾 200 处理器的机器上在 3 秒内编译现有最大的程序，而大多数程序只需不到一秒就可以完成编译，这使我感到非常惊讶。

11. 支持（Support）

    与其它语言的维护者相比，Inria（Xavier Leroy 和 Pierre Weis 等人）提供了更好的支持。关于语言的疑问通常不会太多，我遇到的一些问题在几天之内就得到他们的支持得以解决，这比 VC++或 Turbo Pascal 的支持快很多。

12. 库（Library）

    ML 的标准库包含许多实用的数据结构，比其它语言的相对混乱的标准版更加完整、简洁和实用。

13. 模块系统（Module System）

    ML 对单独的编译具有优异且设计优良的支持，从而让单独编译的模块也可以支持多态（对任意的类型进行操作）。而模块内部的可见性也是完全可控的。Functor 可以让模块特化为特定的实例，就像没有恼人的 C++ 模板一样。

所以主要的问题是数据结构。ML 非常适合定义复杂数据结构和围绕它们的递归算法。ML 对最基本的数据结构（如列表、数组、结构、联合体、哈希表、二叉树、队列等）提供了良好支持。可以以此为基础方便地构造出另一门全新的语言。

ML 是一种完美的语言吗？答案是否定的。和其它的语言一样，它也有很多缺陷：ML 的语法有些晦涩、类似printf这样的简单功能写出来很奇怪……在很多领域 ML 都不能适用（比如我投入很多精力的嵌入式系统开发），例如，在 DSP 芯片上用 ML 来写 FFT 算法将是一场噩梦；据我所知，ML 也不适用于 GUI 开发；ML 也缺少对面向对象的支持（尽管我觉得这是 ML 的特性而非缺陷）。但所有语言都有它们适合发光发热的领域，而我认为编译器开发就是 ML 的适用领域之一。这种感觉就像你在编写编译器的其中一个函数时突然需要一个 9mm 的螺丝扳手，打开 ML 的工具箱，在箱子的抽屉里就有一个顺手的扳手；又过了几分钟，又需要一个磁吸十字螺丝刀时，工具箱里恰好也有一把顺手的螺丝刀。这不是说 ML 的工具箱里有大量工具（事实上，ML 的工具箱比其它的工具箱小得多），因为工具箱由一群能工巧匠经过深思熟虑打造而成的，他们汲取了数十年的经验，对所有好的工具进行了专门设计，目的是打造快速、安全、健壮的程序对复杂数据结构进行递归操作。

这些程序，就是编译器。

Dwight

译者注：

[1]: read.pudn.com/downloads547/ebook/2256772/CInterfacesandImplementation/C%20Interfaces%20and%20Implementations.pdf

[2]: In computer science, a tagged union, also called a variant, variant record, choice type, discriminated union, disjoint union, sum type or coproduct, is a data structure used to hold a value that could take on several different, but fixed, types. Only one of the types can be in use at any one time, and a tag field explicitly indicates which one is in use. It can be thought of as a type that has several "cases", each of which should be handled correctly when that type is manipulated. This is critical in defining recursive datatypes, in which some component of a value may have the same type as the value itself, for example in defining a type for representing trees, where it is necessary to distinguish multi-node subtrees and leafs. Like ordinary unions, tagged unions can save storage by overlapping storage areas for each type, since only one is in use at a time.

[3]: Automated theorem proving (also known as ATP or automated deduction) is a subfield of automated reasoning and mathematical logic dealing with proving mathematical theorems by computer programs. Automated reasoning over mathematical proof was a major impetus for the development of computer science.