譯者 | 劉汪洋
審校 | 重樓
關于如何選擇最合適的編程語言來開發編譯器，這個話題在編程語言愛好者中經常引起熱議。具體可參考以下討論：鏈接 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<TermTree>;
enum TermTree {
Var(Var),
Fix(Vec<(Var, Vec<Var>, Term)>, Term),
Appl(Term, Vec<Term>),
Record(Vec<Term>),
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<CpsVar>, CpsTerm)>, Box<CpsTerm>),
CAppl(CpsVar, Vec<CpsVar>),
CRecord(Vec<CpsVar>, Binder),
CSelect(CpsVar, u32, Binder),
CHalt(CpsVar),
}
use CpsTerm::*;
// 在 `CpsTerm` 內部綁定唯一的 `CpsVar`。
type Binder = (CpsVar, Box<CpsTerm>);
// 根據當前的`i` 生成一個唯一的 CPS 變量。
fn gensym(i: RefCell<u32>) -> CpsVar {
let x = CGenVar(i.clone().into_inner());
i.replace_with(|&mut i| i + 1);
x
}
// 將`Term`轉換為`CpsTerm`，并將`finish`應用于結果的CPS變量。
fn convert(gen: RefCell<u32>, 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<Term>`轉換為`Vec<CpsVar>`并 調用`finish`
fn convert_list(
gen: RefCell<u32>,
finish: impl FnOnce(Vec<CpsVar>) -> CpsTerm,
terms: &[Term],
) -> CpsTerm {
fn go(
gen: RefCell<u32>,
finish: impl FnOnce(Vec<CpsVar>) -> CpsTerm,
mut acc: Vec<CpsVar>,
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<u32>,
(f, params, m): (Var, Vec<Var>, Term),
) -> (CpsVar, Vec<CpsVar>, 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<u32>) -> 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<u32>而非&mut u32？因為 Rust 強制在任何時刻只允許一個可變引用指向特定值。盡管在多線程代碼中這是合理的，但在單線程的算法中，我們需用RefCell來繞過這個限制。
另外，Rust 中convert_list的實現也值得注意。由于fn本質上只是代碼指針，所以我們每次調用go都必須明確傳遞gen和finish，導致了變量類型的重復聲明。與之相對，OCaml則會自動捕獲gen和finish。
雖然上述算法不算特別復雜，但已經足以體現 ML 家族語言在編程方面的便利性。下面，我們將深入探討兩種語言類型系統的更多細節。
類型安全性：GADTs
與 Rust 相比，OCaml 的類型系統通常更具表現力，并且在資源管理之外具有更多優勢。例如，OCaml 支持廣義代數數據類型（GADTs），以強化數據結構的某些不變性。考慮一種包含布爾值、整數及其操作的對象語言，其描述如下：
enum Term {
Bool(bool),
Not(Box<Term>),
And(Box<Term>, Box<Term>),
Int(i32),
Neg(Box<Term>),
Add(Box<Term>, Box<Term>),
}
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
