譯者 | 劉汪洋
審校 | 重樓
關(guān)于如何選擇最合適的編程語言來開發(fā)編譯器，這個話題在編程語言愛好者中經(jīng)常引起熱議。具體可參考以下討論：鏈接 1、鏈接 2 和鏈接 3。遺憾的是，許多人的回答要么局限于自己偏愛的語言，沒有提供合理解釋，要么給出模糊的解釋卻缺乏具體的例證。這兩種回答對提問者來說幾乎沒有任何幫助。在本文中，我將嘗試通過比較兩種語言——Rust 和 OCaml，來對這個話題提供更詳細(xì)的闡述。
CPS 轉(zhuǎn)換
在闡述我的具體觀點(diǎn)之前，我會展示一個非常簡單的語言的 CPS（延續(xù)傳遞風(fēng)格）轉(zhuǎn)換的兩個相似實(shí)現(xiàn)，并不做任何結(jié)論性陳述。這一通用方法源于 Andrew W. Appel 的“Compiling with Continuations”。即使你對這個概念不太了解，也不必?fù)?dān)心；你只需要關(guān)注 Rust 和 OCaml 中是如何具體實(shí)現(xiàn)這個理念的。
以下是用 Rust 編寫的 CPS 轉(zhuǎn)換：
use std::cell::RefCell;
use std::ops::Deref;
use std::rc::Rc;
// lambda 語言的變量標(biāo)識符 `Term`。
type Var = String;
// lambda語言；直接風(fēng)格。
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 轉(zhuǎn)換過程中從 lambda 項(xiàng)中獲取。
CLamVar(Var),
// 在 CPS 轉(zhuǎn)換過程中唯一生成。
CGenVar(u32),
}
use CpsVar::*;
// 結(jié)果的 CPS 項(xiàng)。
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` 內(nèi)部綁定唯一的 `CpsVar`。
type Binder = (CpsVar, Box<CpsTerm>);
// 根據(jù)當(dāng)前的`i` 生成一個唯一的 CPS 變量。
fn gensym(i: RefCell<u32>) -> CpsVar {
let x = CGenVar(i.clone().into_inner());
i.replace_with(|&mut i| i + 1);
x
}
// 將`Term`轉(zhuǎn)換為`CpsTerm`，并將`finish`應(yīng)用于結(jié)果的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>`轉(zhuǎn)換為`Vec<CpsVar>`并 調(diào)用`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)
}
// 將單個函數(shù)定義轉(zhuǎn)換為其 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語言中的變量標(biāo)識符[term]。 *)
type var = string
(* lambda語言；直接風(fēng)格。 *)
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轉(zhuǎn)換過程中從lambda項(xiàng)中提取。 *)
| CLamVar of var
(* 在CPS轉(zhuǎn)換過程中獨(dú)特生成。 *)
| CGenVar of int
(* 生成的CPS項(xiàng)。 *)
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]內(nèi)部綁定唯一的[cps_var]。 *)
and binder = cps_var * cps_term
(* 根據(jù)當(dāng)前的[i]生成唯一的CPS變量。 *)
let gensym i =
let x = CGenVar !i in
i := !i + 1;
x
(* 將[term]轉(zhuǎn)換為[cps_term]，并將[finish]應(yīng)用于生成的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]轉(zhuǎn)換為[cps_var list]并將[finish]應(yīng)用于它。 *)
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 []
(* 將單個函數(shù)定義轉(zhuǎn)換為其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 版本短了大概一半。
比較兩種實(shí)現(xiàn)
開發(fā)的核心特點(diǎn)涵蓋了：
- 大量使用遞歸定義的數(shù)據(jù)結(jié)構(gòu)。
- 復(fù)雜的數(shù)據(jù)轉(zhuǎn)換流程。
下面簡要概述 Rust 和 OCaml 在這兩方面的處理差異：
1.遞歸數(shù)據(jù)結(jié)構(gòu)：
- OCaml：直接支持遞歸數(shù)據(jù)結(jié)構(gòu)。
- Rust：遞歸數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)需要借助Rc 和 Box將TermTree和CpsTerm的遞歸結(jié)構(gòu)進(jìn)行封裝。
2.復(fù)雜數(shù)據(jù)轉(zhuǎn)換：
- OCaml：
- 遞歸廣泛應(yīng)用，擁有尾調(diào)用和“ Tail Modulo Constructor (TMC )”優(yōu)化。
- 模式匹配的實(shí)現(xiàn)便捷高效，無需額外縮進(jìn)和復(fù)雜的參數(shù)描述。
- 標(biāo)準(zhǔn)數(shù)據(jù)結(jié)構(gòu)主要為不可變類型，有助于代碼理解。
- Rust：
- 遞歸使用較少，且并不保證尾遞歸。
- 模式匹配的實(shí)現(xiàn)相對復(fù)雜，涉及額外的縮進(jìn)和參數(shù)詳述。
- 標(biāo)準(zhǔn)數(shù)據(jù)結(jié)構(gòu)大多為可變類型，傾向于使用命令式風(fēng)格，需要進(jìn)行迭代操作才能實(shí)現(xiàn)流水線編程。
與 OCaml 相比，Rust 的語法更冗長。作為一門無垃圾回收的語言，它要求開發(fā)者必須精確處理內(nèi)存管理。這確實(shí)增加了對執(zhí)行過程的透明度，但對理解算法本身的幫助卻不明顯。
在 Rust 中，修改變量或數(shù)據(jù)結(jié)構(gòu)的值也相對復(fù)雜：
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？因?yàn)?Rust 強(qiáng)制在任何時刻只允許一個可變引用指向特定值。盡管在多線程代碼中這是合理的，但在單線程的算法中，我們需用RefCell來繞過這個限制。
另外，Rust 中convert_list的實(shí)現(xiàn)也值得注意。由于fn本質(zhì)上只是代碼指針，所以我們每次調(diào)用go都必須明確傳遞gen和finish，導(dǎo)致了變量類型的重復(fù)聲明。與之相對，OCaml則會自動捕獲gen和finish。
雖然上述算法不算特別復(fù)雜，但已經(jīng)足以體現(xiàn) ML 家族語言在編程方面的便利性。下面，我們將深入探討兩種語言類型系統(tǒng)的更多細(xì)節(jié)。
類型安全性：GADTs
與 Rust 相比，OCaml 的類型系統(tǒng)通常更具表現(xiàn)力，并且在資源管理之外具有更多優(yōu)勢。例如，OCaml 支持廣義代數(shù)數(shù)據(jù)類型（GADTs），以強(qiáng)化數(shù)據(jù)結(jié)構(gòu)的某些不變性。考慮一種包含布爾值、整數(shù)及其操作的對象語言，其描述如下：
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`運(yùn)算符應(yīng)用于非布爾值"),
},
And(m, n) => match (eval(m), eval(n)) {
(Value::Bool(b1), Value::Bool(b2)) => Value::Bool(b1 && b2),
_ => panic!("`And`運(yùn)算符應(yīng)用于非布爾值"),
},
Int(i) => Value::Int(*i),
Neg(m) => match eval(m) {
Value::Int(i) => Value::Int(-i),
_ => panic!("`Neg`運(yùn)算符應(yīng)用于非整數(shù)值"),
},
Add(m, n) => match (eval(m), eval(n)) {
(Value::Int(i1), Value::Int(i2)) => Value::Int(i1 + i2),
_ => panic!("`Add`運(yùn)算符應(yīng)用于非整數(shù)值"),
},
}
}雖然該解決方案相對簡單，但并不夠穩(wěn)健。如果對eval的輸入類型不合適會怎樣呢？以下示例說明了問題：
fn main() {
use Term::*;
let term = Not(Box::new(And(Box::new(Bool(true)), Box::new(Int(42)))));
dbg!(eval(&term));
}程序會因?yàn)椤癆nd運(yùn)算符的第二操作數(shù)必須為布爾值”而出現(xiàn)問題。
為了避免此類錯誤，我們可以在 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現(xiàn)在，嘗試構(gòu)造一個不合適的類型會是什么情況呢？
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之所以會這樣，是因?yàn)槲覀冊趖erm的定義中實(shí)質(zhì)上編碼了對象語言的類型系統(tǒng)。OCaml 知道And只接受布爾類型的項(xiàng)，而不是整數(shù)類型。在實(shí)際應(yīng)用場景中，我們可以有一個無限制的、類似 Rust 的Term項(xiàng)，該項(xiàng)是解析生成的，并可進(jìn)一步詳細(xì)闡述為合適的 GADT 風(fēng)格的term。無論采用eval還是compile，后者均可被處理。
類型靈活性：First-Class Modules
OCaml 中具備一項(xiàng) Rust 所不具備的獨(dú)特功能：First-Class Modules。First-Class Modules允許模塊存儲于變量、作為參數(shù)傳遞，甚至可以從常規(guī)函數(shù)返回。假設(shè)你的目標(biāo)語言涵蓋了各種固定大小的整數(shù)，如i8/u8、i16/u16等，那么你可以通過 OCaml 中的（常規(guī)）模塊來表示這些類型：
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）中，整數(shù)值可以按照以下方式表示：
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那么，在存在諸多算術(shù)運(yùn)算符add/sub/mul/div/rem和多種類型的操作數(shù)時，該如何高效地實(shí)現(xiàn)評估呢？
解決方案如下：
- 定義函數(shù)pair_exn，將兩個generic映射為一個一等模塊Pair。
- 為特定的整數(shù)對定義模塊Pair，并實(shí)現(xiàn)S。
- 定義函數(shù)do_int_bin_op，接收Pair作為參數(shù)，并執(zhí)行整數(shù)對上的操作op。
- 從eval中調(diào)用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的實(shí)現(xiàn)如下：
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")
;;現(xiàn)在，我們可以按如下方式編寫 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，如果該值不是整數(shù)則拋出異常。
最后，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 將類型化的整數(shù)轉(zhuǎn)換回持有 generic 的值。
通過借助 First-Class Modules，我們能夠在無需過多樣板代碼的前提下實(shí)現(xiàn)固定大小整數(shù)的評估。而在 Rust 中的最佳實(shí)踐則是使用macro_rules!。然而，該方法因其難以理解的語法、與編程語言其他部分集成不深入，以及較差的 IDE 支持而備受詬病。
結(jié)束語
雖然 Rust 在資源管理方面表現(xiàn)優(yōu)秀，但 OCaml 更適合于編譯器的開發(fā)。這其中涉及許多引人注目的特性，如多態(tài)變體、自定義綁定操作符和Effect Handlers。得益于完全靜態(tài)且靈活的類型系統(tǒng)，OCaml 在歷史上已廣泛應(yīng)用于眾多項(xiàng)目，包括 Frama-C 工具鏈、Coq 定理證明器，以及 Rust 編譯器的早期版本。
然而，OCaml 也不是完美的。 OCaml 的標(biāo)準(zhǔn)庫和整體生態(tài)系統(tǒng)與 Rust 相比顯得略遜一籌。在 OCaml 中直接使用 Rust 的完整固定大小整數(shù)集合并不可行。不過，通過整合原生 OCaml 整數(shù)、Int32、Int64模塊和 C FFI，可以達(dá)到同樣的效果。（專業(yè)提示：避免使用[ocaml-stdint]，截至 2023 年 8 月 6 日，該庫未維護(hù)且存在多個錯誤。[ocaml-integers]是更穩(wěn)定的選擇，但缺乏Int8、Int16和 128 位整數(shù)的支持，并在文檔方面有所不足。）
隨著 Rust 的日益普及，更多的開發(fā)者開始在 GitHub 上使用它來啟動編譯器項(xiàng)目。我認(rèn)為，如果你試圖借助 Rust 編寫大量編譯器來深入學(xué)習(xí) Rust ，或者確切了解自己的目標(biāo)，這可能是明智之舉。 如果你主要關(guān)注的是編譯器開發(fā)，那么 OCaml 將能夠?yàn)槟愎?jié)省大量時間和精力。
其他值得考慮的選項(xiàng)包括 Haskell 和各類 Lisp 方言。 如果你已經(jīng)熟練掌握了 Haskell（對此我同時表示祝賀和哀悼），那么僅為了編寫編譯器而學(xué)習(xí) OCaml 可能是不必要的。如果你尚未掌握 Haskell，OCaml 可能是更容易上手的選擇。盡管 Lisps 極具靈活性， 但由于它們通常缺少靜態(tài)類型安全性，運(yùn)行時錯誤可能成為一個棘手問題。
參考文獻(xiàn)
- CPS 是編譯器 Standard ML of New Jersey 的核心表示形式。
- 代碼和附帶的測試可在此處訪問。
- 選擇 Rc 是為了減輕在某些地方昂貴的克隆 TermTree 的負(fù)擔(dān)。
- 從嚴(yán)格意義上講，OCaml 中的所有函數(shù)都是柯里化（Currying）的，因此 function 只是定義了一個單一參數(shù)的函數(shù)，并在其上進(jìn)行模式匹配。
- 在此處閉包未能提供解決方案，因?yàn)樗鼈儾荒苓f歸調(diào)用，至少在未進(jìn)行一些復(fù)雜操作之前不能調(diào)用。
廣大網(wǎng)友激烈討論
網(wǎng)友們圍繞 Rust 和 OCaml 的優(yōu)劣以及如何選擇展開了激烈討論。
關(guān)于 Rust和 OCaml 優(yōu)劣對比。有些網(wǎng)友認(rèn)為 Rust 的優(yōu)點(diǎn)在于其內(nèi)存安全性和性能，這使得它在系統(tǒng)編程和高性能計算中非常有用。然而，Rust 的學(xué)習(xí)曲線相對較陡，可能需要更多的時間和精力去掌握。有網(wǎng)友表示，OCaml 在函數(shù)式編程和類型推斷方面非常強(qiáng)大，它的語法簡潔，易于學(xué)習(xí)。然而，OCaml 的生態(tài)系統(tǒng)相對較小，可能沒有 Rust 那么多的庫和工具可供選擇。也有網(wǎng)友認(rèn)為，Rust 和 OCaml 都有一些獨(dú)特的特性，如 Rust 的所有權(quán)系統(tǒng)和 OCaml 的模式匹配，這些特性在編譯器開發(fā)中可能非常有用。
關(guān)于如何選擇。有網(wǎng)友認(rèn)為，如果項(xiàng)目的主要目標(biāo)是快速開發(fā)和原型設(shè)計，那么 OCaml 可能是更好的選擇。如果項(xiàng)目需要處理復(fù)雜的并發(fā)和內(nèi)存管理問題，那么 Rust 可能更適合。也有網(wǎng)友認(rèn)為，Rust 和 OCaml 都是優(yōu)秀的編程語言，但在編譯器開發(fā)中，它們各有優(yōu)勢和劣勢，選擇編程語言不僅僅是技術(shù)問題，還涉及到團(tuán)隊(duì)動力、項(xiàng)目管理和人力資源等多個方面。因此，選擇哪種語言需要綜合考慮多個因素。
譯者介紹
劉汪洋，51CTO社區(qū)編輯，昵稱：明明如月，一個擁有 5 年開發(fā)經(jīng)驗(yàn)的某大廠高級 Java 工程師，擁有多個主流技術(shù)博客平臺博客專家稱號。
標(biāo)題：Compiler Development: Rust or OCaml?，作者：Hirrolot
