关于如何选择最合适的编程语言来开发编译器，这个话题在编程语言爱好者中经常引起热议。具体可参考以下讨论：链接 1、链接 2 和链接 3。遗憾的是，许多人的回答要么局限于自己偏爱的语言，没有提供合理解释，要么给出模糊的解释却缺乏具体的例证。这两种回答对提问者来说几乎没有任何帮助。在本文中，我将尝试通过比较两种语言——Rust 和 OCaml，来对这个话题提供更详细的阐述。
在阐述我的具体观点之前，我会展示一个非常简单的语言的 CPS（延续传递风格）转换的两个相似实现，并不做任何结论性陈述。这一通用方法源于 Andrew W. Appel 的“Compiling with Continuations”。即使你对这个概念不太了解，也不必担心；你只需要关注 Rust 和 OCaml 中是如何具体实现这个理念的。
以下是用 Rust 编写的 CPS 转换：
代码包括注释和空行共 145 行。
同样的算法用地道的 OCaml 编写：
代码包括注释和空行总共有 74 行。这比 Rust 版本短了约 2.0 倍。
开发的核心特点涵盖了：
大量使用递归定义的数据结构。
复杂的数据转换流程。
下面简要概述 Rust 和 OCaml 在这两方面的处理差异：
递归数据结构：
OCaml：直接支持递归数据结构。
Rust：递归数据结构的实现需要借助Rc 和 Box将TermTree和CpsTerm的递归结构进行封装。
复杂数据转换：
OCaml：
a、递归广泛应用，拥有尾调用和“ Tail Modulo Constructor (TMC )”优化。
b、模式匹配的实现便捷高效，无需额外缩进和复杂的参数描述。
c、标准数据结构主要为不可变类型，有助于代码理解。
Rust：
a、递归使用较少，且尾递归并不保证。
b、模式匹配的实现相对复杂，涉及额外的缩进和参数详述。
c、标准数据结构大多为可变类型，倾向于使用命令式风格，需要进行迭代操作才能实现流水线编程。
与 OCaml 相比，Rust 的语法更冗长。作为一门无垃圾回收的语言，它要求开发者必须精确处理内存管理。这确实增加了对执行过程的透明度，但对理解算法本身的帮助却不明显。
在 Rust 中，修改变量或数据结构的值也相对复杂：
与之相比，在 OCaml 中比较简单：
为何选择RefCell<u32>而非&mut u32？因为 Rust 强制在任何时刻只允许一个可变引用指向特定值。尽管在多线程代码中这是合理的，但在单线程的算法中，我们需用RefCell来绕过这个限制。
另外，Rust 中convert_list的实现也值得注意。由于fn本质上只是代码指针，所以我们每次调用go都必须明确传递gen和finish，导致了变量类型的重复声明。与之相对，OCaml则会自动捕获gen和finish。
虽然上述算法不算特别复杂，但已经足以体现 ML 家族语言在编程方面的便利性。下面，我们将深入探讨两种语言类型系统的更多细节。
与 Rust 相比，OCaml 的类型系统通常更具表现力，并且在资源管理之外具有更多优势。例如，OCaml 支持广义代数数据类型（GADTs），以强化数据结构的某些不变性。考虑一种包含布尔值、整数及其操作的对象语言，其描述如下：
那么，我们该如何编写该语言的求值器呢？以下是一个可能的解决方案：
虽然该解决方案相对简单，但并不够稳健。如果对eval的输入类型不合适会怎样呢？以下示例说明了问题：
程序会因为“And运算符的第二操作数必须为布尔值”而出现问题。
为了避免此类错误，我们可以在 OCaml 中采用 GADTs ：
现在，尝试构造一个不合适的类型会是什么情况呢？
类型检查不会通过！
之所以会这样，是因为我们在term的定义中实质上编码了对象语言的类型系统。OCaml 知道And只接受布尔类型的项，而不是整数类型。在实际应用场景中，我们可以有一个无限制的、类似 Rust 的Term项，该项是解析生成的，并可进一步详细阐述为合适的 GADT 风格的term。无论采用eval还是compile，后者均可被处理。
OCaml 中具备一项 Rust 所不具备的独特功能：First-Class Modules。First-Class Modules允许模块存储于变量、作为参数传递，甚至可以从常规函数返回。假设你的目标语言涵盖了各种固定大小的整数，如i8/u8、i16/u16等，那么你可以通过 OCaml 中的（常规）模块来表示这些类型：
fixed_ints.mli
在抽象语法树（AST）中，整数值可以按照以下方式表示：
那么，在存在诸多算术运算符add/sub/mul/div/rem和多种类型的操作数时，该如何高效地实现评估呢？
解决方案如下：
定义函数pair_exn，将两个generic映射为一个一等模块Pair。
为特定的整数对定义模块Pair，并实现S。
定义函数do_int_bin_op，接收Pair作为参数，并执行整数对上的操作op。
从eval中调用do_int_bin_op。
在 OCaml 中:
fixed_ints.mli
pair的实现如下：
fixed_ints.ml
现在，我们可以按如下方式编写 eval：
extract_int_exn 取出一个值，并提取一个整型 generic，如果该值不是整数则抛出异常。
最后，do_int_bin_op 定义如下：
S.to_value 将类型化的整数转换回持有 generic 的值。
通过借助 First-Class Modules，我们能够在无需过多样板代码的前提下实现固定大小整数的评估。而在 Rust 中的最佳实践则是使用macro_rules!。然而，该方法因其难以理解的语法、与编程语言其他部分集成不深入，以及较差的 IDE 支持而备受诟病。
虽然 Rust 在资源管理方面表现优秀，但 OCaml 更适合于编译器的开发。这其中涉及许多引人注目的特性，如多态变体、自定义绑定操作符和Effect Handlers。得益于完全静态且灵活的类型系统，OCaml 在历史上已广泛应用于众多项目，包括 Frama-C 工具链、Coq 定理证明器，以及 Rust 编译器的早期版本。
然而，OCaml 也不是完美的。OCaml 的标准库和整体生态系统与 Rust 相比显得略逊一筹。在 OCaml 中直接使用 Rust 的完整固定大小整数集合并不可行。不过，通过整合原生 OCaml 整数、Int32、Int64模块和 C FFI，可以达到同样的效果。（专业提示：避免使用
随着 Rust 的日益普及，更多的开发者开始在 GitHub 上使用它来启动编译器项目。我认为，如果你试图借助Rust 编写大量编译器来深入学习 Rust ，或者确切了解自己的目标，这可能是明智之举。如果你主要关注的是编译器开发，那么 OCaml 将能够为你节省大量时间和精力。
其他值得考虑的选项包括 Haskell 和各类 Lisp 方言。如果你已经熟练掌握了 Haskell（对此我同时表示祝贺和哀悼），那么仅为了编写编译器而学习 OCaml 可能是不必要的。如果你尚未掌握 Haskell，OCaml 可能是更容易上手的选择。尽管 Lisps 极具灵活性， 但由于它们通常缺少静态类型安全性，运行时错误可能成为一个棘手问题。
CPS 是编译器 Standard ML of New Jersey 的核心表示形式。
代码和附带的测试可在此处访问。
选择 Rc 是为了减轻在某些地方昂贵的克隆 TermTree 的负担。
从严格意义上讲，OCaml 中的所有函数都是柯里化（Currying）的，因此 function 只是定义了一个单一参数的函数，并在其上进行模式匹配。
在此处闭包未能提供解决方案，因为它们不能递归调用，至少在未进行一些复杂操作之前不能调用。
网友们围绕 Rust 和 OCaml 的优劣以及如何选择展开了激烈讨论。
关于 Rust和 OCaml 优劣对比。有些网友认为 Rust 的优点在于其内存安全性和性能，这使得它在系统编程和高性能计算中非常有用。然而，Rust 的学习曲线相对较陡，可能需要更多的时间和精力去掌握。有网友表示，OCaml 在函数式编程和类型推断方面非常强大，它的语法简洁，易于学习。然而，OCaml 的生态系统相对较小，可能没有 Rust 那么多的库和工具可供选择。也有网友认为，Rust 和 OCaml 都有一些独特的特性，如 Rust 的所有权系统和 OCaml 的模式匹配，这些特性在编译器开发中可能非常有用。
关于如何选择。有网友认为，如果项目的主要目标是快速开发和原型设计，那么 OCaml 可能是更好的选择。如果项目需要处理复杂的并发和内存管理问题，那么 Rust 可能更适合。也有网友认为，Rust 和 OCaml 都是优秀的编程语言，但在编译器开发中，它们各有优势和劣势，选择编程语言不仅仅是技术问题，还涉及到团队动力、项目管理和人力资源等多个方面。因此，选择哪种语言需要综合考虑多个因素。
参考链接
链接 1：https://www.reddit.com/r/ProgrammingLanguages/comments/k3zgjy/which_language_to_write_a_compiler_in/
链接 2：https://www.reddit.com/r/ProgrammingLanguages/comments/13eztdp/good_languages_for_writing_compilers_in/
链接 3：https://www.reddit.com/r/ProgrammingLanguages/comments/15gz8rb/how_good_is_go_for_writing_a_compiler/
CPS（延续传递风格：https://en.wikipedia.org/wiki/Continuation-passing_style
“Compiling with Continuations”：https://www.amazon.com/Compiling-Continuations-Andrew-W-Appel/dp/052103311X
“ Tail Modulo Constructor (TMC )”：https://v2.ocaml.org/manual/tail_mod_cons.html
并不保证：https://stackoverflow.com/questions/59257543/when-is-tail-recursion-guaranteed-in-rust
广义代数数据类型（GADTs）：https://v2.ocaml.org/manual/gadts-tutorial.html
First-Class Modules：https://dev.realworldocaml.org/first-class-modules.html
多态变体：https://v2.ocaml.org/releases/4.14/htmlman/polyvariant.html
自定义绑定操作符：https://v2.ocaml.org/manual/bindingops.html
Effect Handlers：https://v2.ocaml.org/manual/effects.html
Frama-C 工具链：https://frama-c.com/
Coq 定理证明器：https://coq.inria.fr/
此处：https://gist.github.com/Hirrolot/d16dc5e78639db6e546b5054afefd142
