审校 | 重楼
关于如何选择最合适的编程语言来开发编译器,这个话题在编程语言爱好者中经常引起热议。具体可参考以下讨论:链接 1、链接 2 和链接 3。遗憾的是,许多人的回答要么局限于自己偏爱的语言,没有提供合理解释,要么给出模糊的解释却缺乏具体的例证。这两种回答对提问者来说几乎没有任何帮助。在本文中,我将尝试通过比较两种语言——Rust 和 OCaml,来对这个话题提供更详细的阐述。
CPS 转换
在阐述我的具体观点之前,我会展示一个非常简单的语言的 CPS(延续传递风格)转换的两个相似实现,并不做任何结论性陈述。这一通用方法源于 Andrew W. Appel 的“Compiling with Continuations”。即使你对这个概念不太了解,也不必担心;你只需要关注 Rust 和 OCaml 中是如何具体实现这个理念的。
以下是用 Rust 编写的 CPS 转换:
use std::cell::RefCell;
use std::ops::Deref;
use std::rc::Rc;
// lambda 语言的变量标识符 `Term`。
type Var = String;
// lambda语言;直接风格。
type Term = Rc;
enum TermTree {
Var(Var),
Fix(Vec<(Var, Vec, Term)>, Term),
Appl(Term, Vec),
Record(Vec),
Select(Term, u32),
}
use TermTree::*;
#[derive(Clone)]
enum CpsVar {
// 在 CPS 转换过程中从 lambda 项中获取。
CLamVar(Var),
// 在 CPS 转换过程中唯一生成。
CGenVar(u32),
}
use CpsVar::*;
// 结果的 CPS 项。
enum CpsTerm {
CFix(Vec<(CpsVar, Vec, CpsTerm)>, Box),
CAppl(CpsVar, Vec),
CRecord(Vec, Binder),
CSelect(CpsVar, u32, Binder),
CHalt(CpsVar),
}
use CpsTerm::*;
// 在 `CpsTerm` 内部绑定唯一的 `CpsVar`。
type Binder = (CpsVar, Box);
// 根据当前的`i` 生成一个唯一的 CPS 变量。
fn gensym(i: RefCell) -> CpsVar {
let x = CGenVar(i.clone().into_inner());
i.replace_with(|&mut i| i + 1);
x
}
// 将`Term`转换为`CpsTerm`,并将`finish`应用于结果的CPS变量。
fn convert(gen: RefCell, finish: impl FnOnce(CpsVar) -> CpsTerm, term: Term) -> CpsTerm {
match term.deref() {
Var(x) => finish(CLamVar(x.to_string())),
Fix(defs, m) => CFix(
defs.iter()
.map(|def| convert_def(gen.clone(), def.clone()))
.collect(),
Box::new(convert(gen, finish, m.clone())),
),
Appl(f, args) => {
let ret_k = gensym(gen.clone());
let ret_k_x = gensym(gen.clone());
CFix(
vec![(ret_k.clone(), vec![ret_k_x.clone()], finish(ret_k_x))],
Box::new(convert(
gen.clone(),
|f_cps| {
convert_list(
gen,
|args_cps| {
CAppl(f_cps, args_cps.into_iter().chain(vec![ret_k]).collect())
},
args,
)
},
f.clone(),
)),
)
}
Record(fields) => convert_list(
gen.clone(),
|fields_cps| {
let x = gensym(gen);
CRecord(fields_cps, (x.clone(), Box::new(finish(x))))
},
fields,
),
Select(m, i) => convert(
gen.clone(),
|m_cps| {
let x = gensym(gen);
CSelect(m_cps, *i, (x.clone(), Box::new(finish(x))))
},
m.clone(),
),
}
}
// 将`Vec`转换为`Vec`并 调用`finish`
fn convert_list(
gen: RefCell,
finish: impl FnOnce(Vec) -> CpsTerm,
terms: &[Term],
) -> CpsTerm {
fn go(
gen: RefCell,
finish: impl FnOnce(Vec) -> CpsTerm,
mut acc: Vec,
terms: &[Term],
) -> CpsTerm {
match terms.split_first() {
None => finish(acc),
Some((x, xs)) => convert(
gen.clone(),
|x_cps| {
acc.push(x_cps);
go(gen, finish, acc, xs)
},
x.clone(),
),
}
}
let acc = Vec::with_capacity(terms.len());
go(gen, finish, acc, terms)
}
// 将单个函数定义转换为其 CPS 形式。
fn convert_def(
gen: RefCell,
(f, params, m): (Var, Vec, Term),
) -> (CpsVar, Vec, CpsTerm) {
let k = gensym(gen.clone());
(
CLamVar(f),
params
.into_iter()
.map(CLamVar)
.chain(std::iter::once(k.clone()))
.collect(),
convert(gen, |m_cps| CAppl(k, vec![m_cps]), m),
)
}
代码包括注释和空行共 145 行。
同样的算法用地道的 OCaml 编写:
(* lambda语言中的变量标识符[term]。 *)
type var = string
(* lambda语言;直接风格。 *)
type term =
| Var of var
| Fix of (var * var list * term) list * term
| Appl of term * term list
| Record of term list
| Select of term * int
type cps_var =
(* 在CPS转换过程中从lambda项中提取。 *)
| CLamVar of var
(* 在CPS转换过程中独特生成。 *)
| CGenVar of int
(* 生成的CPS项。 *)
type cps_term =
| CFix of (cps_var * cps_var list * cps_term) list * cps_term
| CAppl of cps_var * cps_var list
| CRecord of cps_var list * binder
| CSelect of cps_var * int * binder
| CHalt of cps_var
(* 在[cps_term]内部绑定唯一的[cps_var]。 *)
and binder = cps_var * cps_term
(* 根据当前的[i]生成唯一的CPS变量。 *)
let gensym i =
let x = CGenVar !i in
i := !i + 1;
x
(* 将[term]转换为[cps_term],并将[finish]应用于生成的CPS变量。 *)
let rec convert gen finish = function
| Var x -> finish (CLamVar x)
| Fix (defs, m) -> CFix (List.map (convert_def gen) defs, convert gen finish m)
| Appl (f, args) ->
let ret_k = gensym gen in
let ret_k_x = gensym gen in
CFix
( [ (ret_k, [ ret_k_x ], finish ret_k_x) ],
f
|> convert gen (fun f_cps ->
args
|> convert_list gen (fun args_cps ->
CAppl (f_cps, args_cps @ [ ret_k ]))) )
| Record fields ->
fields
|> convert_list gen (fun fields_cps ->
let x = gensym gen in
CRecord (fields_cps, (x, finish x)))
| Select (m, i) ->
m
|> convert gen (fun m_cps ->
let x = gensym gen in
CSelect (m_cps, i, (x, finish x)))
(* 将[term list]转换为[cps_var list]并将[finish]应用于它。 *)
and convert_list gen finish =
let rec go acc = function
| [] -> finish (List.rev acc)
| x :: xs -> x |> convert gen (fun x_cps -> go (x_cps :: acc) xs)
in
go []
(* 将单个函数定义转换为其CPS形式。 *)
and convert_def gen (f, params, m) =
let k = gensym gen in
( CLamVar f,
List.map (fun x -> CLamVar x) params @ [ k ],
m |> convert gen (fun m_cps -> CAppl (k, [ m_cps ])) )
代码包括注释和空行总共有 74 行。这比 Rust 版本短了大概一半。
比较两种实现
开发的核心特点涵盖了:
- 大量使用递归定义的数据结构。
- 复杂的数据转换流程。
下面简要概述 Rust 和 OCaml 在这两方面的处理差异:
1.递归数据结构:
- OCaml:直接支持递归数据结构。
- Rust:递归数据结构的实现需要借助Rc 和 Box将TermTree和CpsTerm的递归结构进行封装。
2.复杂数据转换:
- OCaml:
- 递归广泛应用,拥有尾调用和“ Tail Modulo Constructor (TMC )”优化。
- 模式匹配的实现便捷高效,无需额外缩进和复杂的参数描述。
- 标准数据结构主要为不可变类型,有助于代码理解。
- Rust:
- 递归使用较少,且并不保证尾递归。
- 模式匹配的实现相对复杂,涉及额外的缩进和参数详述。
- 标准数据结构大多为可变类型,倾向于使用命令式风格,需要进行迭代操作才能实现流水线编程。
与 OCaml 相比,Rust 的语法更冗长。作为一门无垃圾回收的语言,它要求开发者必须精确处理内存管理。这确实增加了对执行过程的透明度,但对理解算法本身的帮助却不明显。
在 Rust 中,修改变量或数据结构的值也相对复杂:
fn gensym(i: RefCell) -> CpsVar {
let x = CGenVar(i.clone().into_inner());
i.replace_with(|&mut i| i + 1);
x
}
与之相比,在 OCaml 中比较简单:
let gensym i =
let x = CGenVar !i in
i := !i + 1;
x
为何选择RefCell
另外,Rust 中convert_list的实现也值得注意。由于fn本质上只是代码指针,所以我们每次调用go都必须明确传递gen和finish,导致了变量类型的重复声明。与之相对,OCaml则会自动捕获gen和finish。
虽然上述算法不算特别复杂,但已经足以体现 ML 家族语言在编程方面的便利性。下面,我们将深入探讨两种语言类型系统的更多细节。
类型安全性:GADTs
与 Rust 相比,OCaml 的类型系统通常更具表现力,并且在资源管理之外具有更多优势。例如,OCaml 支持广义代数数据类型(GADTs),以强化数据结构的某些不变性。考虑一种包含布尔值、整数及其操作的对象语言,其描述如下:
enum Term {
Bool(bool),
Not(Box),
And(Box, Box),
Int(i32),
Neg(Box),
Add(Box, Box),
}
enum Value {
Bool(bool),
Int(i32),
}
那么,我们该如何编写该语言的求值器呢?以下是一个可能的解决方案:
fn eval(term: &Term) -> Value {
use Term::*;
match term {
Bool(b) => Value::Bool(*b),
Not(m) => match eval(m) {
Value::Bool(b) => Value::Bool(!b),
_ => panic!("`Not`运算符应用于非布尔值"),
},
And(m, n) => match (eval(m), eval(n)) {
(Value::Bool(b1), Value::Bool(b2)) => Value::Bool(b1 && b2),
_ => panic!("`And`运算符应用于非布尔值"),
},
Int(i) => Value::Int(*i),
Neg(m) => match eval(m) {
Value::Int(i) => Value::Int(-i),
_ => panic!("`Neg`运算符应用于非整数值"),
},
Add(m, n) => match (eval(m), eval(n)) {
(Value::Int(i1), Value::Int(i2)) => Value::Int(i1 + i2),
_ => panic!("`Add`运算符应用于非整数值"),
},
}
}
虽然该解决方案相对简单,但并不够稳健。如果对eval的输入类型不合适会怎样呢?以下示例说明了问题:
fn main() {
use Term::*;
let term = Not(Box::new(And(Box::new(Bool(true)), Box::new(Int(42)))));
dbg!(eval(&term));
}
程序会因为“And运算符的第二操作数必须为布尔值”而出现问题。
为了避免此类错误,我们可以在 OCaml 中采用 GADTs :
type _ term =
| Bool : bool -> bool term
| Not : bool term -> bool term
| And : bool term * bool term -> bool term
| Int : int -> int term
| Neg : int term -> int term
| Add : int term * int term -> int term
let rec eval : type a. a term -> a = function
| Bool b -> b
| Not m -> not (eval m)
| And (m, n) ->
let b1, b2 = (eval m, eval n) in
b1 && b2
| Int i -> i
| Neg m -> -eval m
| Add (m, n) ->
let i1, i2 = (eval m, eval n) in
i1 + i2
现在,尝试构造一个不合适的类型会是什么情况呢?
let () =
let _term = Not (And (Bool true, Int 42)) in
()
类型检查不会通过!
File "bin/main.ml", line 22, characters 35-41:
22 | let _term = Not (And (Bool true, Int 42)) in
^^^^^^
Error: This expression has type int term
but an expression was expected of type bool term
Type int is not compatible with type bool
之所以会这样,是因为我们在term的定义中实质上编码了对象语言的类型系统。OCaml 知道And只接受布尔类型的项,而不是整数类型。在实际应用场景中,我们可以有一个无限制的、类似 Rust 的Term项,该项是解析生成的,并可进一步详细阐述为合适的 GADT 风格的term。无论采用eval还是compile,后者均可被处理。
类型灵活性:First-Class Modules
OCaml 中具备一项 Rust 所不具备的独特功能:First-Class Modules。First-Class Modules允许模块存储于变量、作为参数传递,甚至可以从常规函数返回。假设你的目标语言涵盖了各种固定大小的整数,如i8/u8、i16/u16等,那么你可以通过 OCaml 中的(常规)模块来表示这些类型:
fixed_ints.mli
(* [u8], [u16]等由我们定义。*)
module type S = sig
type t
val add : t -> t -> t
val sub : t -> t -> t
val mul : t -> t -> t
val div : t -> t -> t
val rem : t -> t -> t
(* 这里还有一些操作。*)
end
module U8 : S with type t = u8
module U16 : S with type t = u16
module U32 : S with type t = u32
module U64 : S with type t = u64
module U128 : S with type t = u128
module I8 : S with type t = i8
module I16 : S with type t = i16
module I32 : S with type t = i32
module I64 : S with type t = i64
module I128 : S with type t = i128
在抽象语法树(AST)中,整数值可以按照以下方式表示:
type generic =
| U8 of u8
| U16 of u16
| U32 of u32
| U64 of u64
| U128 of u128
| I8 of i8
| I16 of i16
| I32 of i32
| I64 of i64
| I128 of i128
那么,在存在诸多算术运算符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
module type Pair = sig
type t
include S with type t := t
val pair : t * t
end
val pair_exn : generic * generic -> (module Pair)
pair的实现如下:
fixed_ints.ml
let pair_exn =
let make (type a) (module S : S with type t = a) (x, y) =
(module struct
include S
let pair = x, y
end : Pair)
in
function
| U8 x, U8 y -> make (module U8) (x, y)
| U16 x, U16 y -> make (module U16) (x, y)
| U32 x, U32 y -> make (module U32) (x, y)
| U64 x, U64 y -> make (module U64) (x, y)
| U128 x, U128 y -> make (module U128) (x, y)
| I8 x, I8 y -> make (module I8) (x, y)
| I16 x, I16 y -> make (module I16) (x, y)
| I32 x, I32 y -> make (module I32) (x, y)
| I64 x, I64 y -> make (module I64) (x, y)
| I128 x, I128 y -> make (module I128) (x, y)
| _, _ -> raise (invalid_arg "Fixed_ints.pair_exn")
;;
现在,我们可以按如下方式编写 eval:
(* 在 [eval] 的定义中的某处。*)
| IntBinOp (op, ty, m, n) ->
let x = extract_int_exn (eval m) in
let y = extract_int_exn (eval n) in
let (module Pair) = Fixed_ints.pair_exn (x, y) in
do_int_bin_op op (module Pair)
extract_int_exn 取出一个值,并提取一个整型 generic,如果该值不是整数则抛出异常。
最后,do_int_bin_op 定义如下:
let do_int_bin_op op (module S : Fixed_ints.Pair) =
let x, y = S.pair in
match op with
| Add -> S.add x y |> S.to_value
| Sub -> S.sub x y |> S.to_value
| Mul -> S.mul x y |> S.to_value
| Div -> S.div x y |> S.to_value
| Rem -> S.rem x y |> S.to_value
;;
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,可以达到同样的效果。(专业提示:避免使用[ocaml-stdint],截至 2023 年 8 月 6 日,该库未维护且存在多个错误。[ocaml-integers]是更稳定的选择,但缺乏Int8、Int16和 128 位整数的支持,并在文档方面有所不足。)
随着 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 都是优秀的编程语言,但在编译器开发中,它们各有优势和劣势,选择编程语言不仅仅是技术问题,还涉及到团队动力、项目管理和人力资源等多个方面。因此,选择哪种语言需要综合考虑多个因素。
译者介绍
刘汪洋,51CTO社区编辑,昵称:明明如月,一个拥有 5 年开发经验的某大厂高级 Java 工程师,拥有多个主流技术博客平台博客专家称号。
Compiler Development: Rust or OCaml?,作者:Hirrolot