Rust中基于GADT风格枚举的零成本'Tagless Final'实现

# 使用GADT风格枚举在Rust中实现零开销"Tagless Final" 来源：http://inferara.com/blog/rust-tagless-final-gadt/ ## 引言：Tagless Final的魅力 在函数式编程领域，"Tagless Final"模式是构建嵌入式领域特定语言（DSL）的绝佳抽象方案。它允许你定义语言操作的接口，然后编写多个解释器（例如：一个用于求值、一个用于美化打印、一个用于优化），而无需修改核心程序逻辑。对于Rust这样的系统编程语言而言，关键考验在于能否在不牺牲其核心承诺——零开销性能——的前提下，吸收此类高级抽象。本文将探讨如何在Rust中实现基于广义代数数据类型（GADT）的"tagless initial"变体模式。我们将证明，通过精细的类型级编程，我们可以构建这些表现力丰富的结构，并让编译器完全擦除它们，最终生成优化的汇编代码。 ## 目标："Tagless Initial"编码方式 如Serokell的《Tagless Final入门》(https://serokell.io/blog/introduction-tagless-final)等资料所述，"tagless initial"编码使用GADT来表示表达式。在Haskell中，其形式如下： ```haskell data Expr a where IntConst :: Int -> Expr Int Lambda :: (Expr a -> Expr b) -> Expr (Expr a -> Expr b) Apply :: Expr (Expr a -> Expr b) -> Expr a -> Expr b Add :: Expr Int -> Expr Int -> Expr Int eval :: Expr a -> a eval (IntConst x) = x eval (Lambda f) = f eval (Apply f x) = eval (eval f x) eval (Add l r) = (eval l) + (eval r) ``` 注意表达式类型`Expr a`与其将产生的值类型`a`相关联。我们的目标是在Rust中复现这种结构及其`eval`函数，并验证它是否能编译为仅包含计算结果的高效代码。 ## 初探：Rust表达式及其汇编结果 让我们直接切入正题。下面是一个Rust函数，它使用我们的GADT风格编码构建了一个复杂表达式。该函数定义了几个整数常量、lambda（包括一个高阶lambda）和应用。 ```rust fn expr(u: isize, v: isize, w: isize) -> Gadt { let a = int_const(u); let b = int_const(v); let c = add::<(), _, _>(a, b); let d = lambda::<(), _, _, _, _, _>(move |x| { let a = int_const(u * 2 + v * 3 + w * 5); add::<(), _, _>(a, x) }); let e = apply::<(), _, _, _>(d, c); let f = lambda::<(), _, _, _, _, _>(move |x| { let a = int_const(u * 3 + v * 5 + w * 13); add::<(), _, _>(add::<(), _, _>(a, x), c) }); let j = lambda::<(), _, _, _, _, _>(move |x: Gadt<_, _>| -> Gadt<_, _> { apply::<(), _, cu::Int, _>(x, e) }); apply::<(), _, _, _>(j, f) } #[inline(never)] pub extern "C" fn eval_expr(u: isize, v: isize, w: isize) -> isize { expr(u, v, w).eval() } ``` 这看起来像一个庞大复杂的结构。然而，当我们以release模式编译并检查`eval_expr`的汇编代码时，我们看到了神奇之处： ```assembly playground::eval_expr: # @playground::eval_expr # %bb.0: leaq (%rdx,%rdx,2), %rax leaq (%rdx,%rax,4), %r8 addq %rsi, %rdx leaq (%rdx,%rdx,4), %rdx leaq (%rsi,%rdi,2), %rax leaq (%rax,%rax,2), %rcx leaq (%rdi,%rsi,2), %rax addq %r8, %rax addq %rdx, %rax addq %rcx, %rax retq ``` 整个表达式树、lambda、`apply`调用——所有这些都被归结为一系列算术指令（`leaq`、`addq`）。没有解释器循环，没有动态分发，没有内存分配。这就是"零开销"承诺的兑现。 ## 解释器：简单的`eval`实现 这是如何可能的？求值逻辑定义在`Eval` trait中。它对我们`Gadt`类型的实现是一个简单的`match`语句，递归调用其组件的`eval`。 ```rust pub trait Eval { fn eval(self) -> SolOf; } impl Eval for Gadt { fn eval(self) -> SolOf { match self.0 { Enum::IntConst(v01, a) => v01.vu_cast::<_, _, _, _>(&a)(v01.get(a)), Enum::Lambda(v02, f) => v02.vu_cast::<_, _, _, _>(&f)(v02.get(f)), Enum::Apply(v03, t) => v03._vu_cast::<_, _, _, _, _>(&t)({ let (f, a) = v03.get(t); let f = f.eval(); f(a).eval() }), Enum::Add(v04, t) => v04.vu_cast::<_, _, _, _>(&t)({ let (a, b) = v04.get(t); let a = a.eval(); let b = b.eval(); a + b }), } } } ``` 乍一看，这像是一个会引入运行时开销的标准解释器。其优化的关键在于`Gadt`和`Enum`类型的定义。 ## 魔法背后：类GADT枚举 该技术的核心是一个使用Rust的`never`类型（`!`）的`enum`，它确保对于任何给定的类型签名，只有一个变体是实际可构造的。这有效地移除了枚举的"标签"，因为编译器在编译时就知道正在使用哪个变体。 ```rust pub struct Gadt( Enum<Cur::_V02, Cur::_V03, Cur::_V04, Cur, Att>, ); pub enum Enum<V01, V02, V03, V04, Cur, Att> { __Ph__(!, Ph<(V01, V02, V03, V04, Cur, Att)>), IntConst(V01, V01::NGuard), Lambda( V02, V02::NGuard< Att::Fun, ReprOf, Cur, cu::ReprFun, Att, >, ), Apply( V03, V03::NGuard< ( ReprOf, Att::FunAtt, ReprOf, ), Cur, V03::CGuard, _2Of, >, ), Add( V04, V04::NGuard< (ReprOf, ReprOf), Cur, cu::Int, Att, >, ), } ``` 类型`V01`到`V04`由`Attic` trait控制。通过将它们设置为`!`，我们使得构造相应的变体成为不可能。由于`!`类型的值永远无法被创建，编译器可以证明该代码路径不可达。`NGuard` trait是一个辅助工具，确保任何用`!`"禁用"的变体大小为零，允许`enum`折叠为其单个活动变体的大小。 ## 核心组件：`Cursor`与`Attic` 两个协调的trait是`Cursor`和`Attic`。它们共同工作，作为一个类型级配置系统： - **`Attic`**：此trait保存关于哪些`Enum`构造器被禁用的实际信息。在其默认状态下，它将所有`\_V\*`类型设置为`!`，从而有效地禁用所有变体。要启用一个构造器，特定的`Attic`实现将提供一个非`!`类型。 - **`Cursor`**：此trait充当过滤器或视图，选择在表达式树中的每个点应用`Attic`中的哪个配置。 ```rust pub trait Attic { // ... 默认值为 `!` ... type _V01: NGuard = !; type _V02: NGuard = !; type _V03: NGuard = !; type _V04: NGuard = !; // ... 其他关联类型 ... } pub trait Cursor { // ... 使用来自 Attic 的配置 ... type _V01: NGuard = Att::_V01; type _V02: NGuard = Att::_V02; type _V03: NGuard = Att::_V03; type _V04: NGuard = Att::_V04; // ... 其他关联类型 ... } ``` 通过这种机制，我们可以构造一个`Gadt`类型，其中`Enum`的变体只有一个有效，使得`eval`中的模式匹配在编译时完全可预测。 ## 零开销证明：使用`never`类型的实验 如果我们破坏这个不变性会发生什么？让我们进行一个实验。我们将用具体的零大小类型（如`((),)`）替换`Attic` trait中的`!`。这意味着所有变体现在理论上都是可构造的。 ```rust // 在 Attic 中，我们改变默认值： // 从: type _V01: NGuard = !; // 改为: type _V01: NGuard = ((),); // 并且对 V02, V03, V04 也做同样修改 ``` 突然之间，编译器不再能保证哪个变体是活动的。它现在必须包含一个标签（判别值）并进行运行时检查。生成的汇编代码急剧膨胀： ```assembly playground::eval_expr: # @playground::eval_expr # %bb.0: pushq %r15 pushq %r14 pushq %r13 pushq %r12 pushq %rbx subq $32, %rsp ... callq <playground::Gadt as playground::Eval>::eval ... callq <playground::Gadt as playground::Eval>::eval ... popq %r15 retq ``` 我们现在看到了对`eval`的显式调用。抽象不再是零开销；它正在被运行时解释。这表明`never`类型是实现无标签性和启用编译器优化的关键组件。 有人可能认为只需给`eval`添加`#[inline(always)]`就能解决。确实，在这个简单情况下，内联可以帮助优化器解开调用并产生好得多的汇编代码。然而，这不是一个稳健的解决方案。它依赖于优化器的超常发挥，并且在更复杂、模块化的程序中（DSL嵌套或跨crate定义）可能会失败。`never`类型方法通过构造来保证优化。 ## 结论 通过仔细使用Rust的类型系统，特别是`never`类型（`!`），我们可以成功地实现"tagless initial"模式。我们创建了一个类GADT的枚举，对于任何给定类型，只有一个变体是可构造的，这有效地消除了运行时标签的需求。这使编译器能够完全看透抽象，将复杂表达式树折叠为其原始的计算等价物。该技术为在Rust中构建高级、表现力丰富的DSL提供了一个强大的蓝图，同时不妥协于系统编程语言的性能期望。 你可以亲自实验完整代码： - Rust Playground (https://play.rust-lang.org/?version=nightly&mode=release&edition=2021&gist=37b15966e1c1359cff23ba28af2424dd) - 完整源代码的Gist (https://gist.github.com/rust-play/37b15966e1c1359cff23ba28af2424dd)