Zero-Cost ‘Tagless Final’ in Rust with GADT-style Enums

使用 GADT 风格枚举在 Rust 中实现零成本“无标签最终”（Tagless Final）

Introduction: The Allure of Tagless Final

引言：无标签最终（Tagless Final）的魅力

In the world of functional programming, the “Tagless Final” pattern is a wonderful abstraction for creating embedded domain-specific languages (DSLs). It allows you to define an interface for your language’s operations and then write multiple interpreters (e.g., one to evaluate, one to pretty-print, one to optimize) without changing the core program logic. 在函数式编程领域，“无标签最终”（Tagless Final）模式是一种用于创建嵌入式领域特定语言（DSL）的绝佳抽象。它允许你为语言的操作定义接口，然后编写多个解释器（例如：一个用于求值，一个用于美化打印，一个用于优化），而无需更改核心程序逻辑。

A key test for a systems language like Rust is its ability to adopt such high-level abstractions without sacrificing its core promise: zero-cost performance. This post explores how to implement the “tagless initial” variant of this pattern, which relies on Generalized Algebraic Data Types (GADTs), in Rust. We will demonstrate that with careful type-level programming, we can build these expressive structures and have the compiler completely erase them, resulting in optimal assembly code. 对于像 Rust 这样的系统语言来说，一个关键的考验是它能否在不牺牲其核心承诺——零成本性能——的前提下采用此类高级抽象。本文探讨了如何在 Rust 中实现该模式的“无标签初始”（Tagless Initial）变体，它依赖于广义代数数据类型（GADT）。我们将证明，通过精心的类型级编程，我们可以构建这些富有表现力的结构，并让编译器将其完全擦除，从而生成最优的汇编代码。

The Goal: “Tagless Initial” Encoding

目标：“无标签初始”编码

The “tagless initial” encoding, as described in resources like Serokell’s Introduction to Tagless Final, uses a GADT to represent expressions. In Haskell, it looks like this: 正如 Serokell 的《无标签最终入门》等资源中所述，“无标签初始”编码使用 GADT 来表示表达式。在 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)

Notice that the type of the expression Expr a is tied to the type of value it will produce (a). Our goal is to replicate this structure and its eval function in Rust and verify that it compiles down to nothing but the computed result. 请注意，表达式 Expr a 的类型与其将产生的值的类型 (a) 是绑定的。我们的目标是在 Rust 中复制这种结构及其 eval 函数，并验证它在编译后只会剩下计算结果。

A First Look: The Rust Expression and Its Assembly

初探：Rust 表达式及其汇编

Let’s dive right in. Here is a Rust function that constructs a complex expression using our GADT-style encoding. It defines several integer constants, lambdas (including a higher-order one), and applications. 让我们直接开始。这是一个使用我们的 GADT 风格编码构建复杂表达式的 Rust 函数。它定义了几个整数常量、Lambda（包括一个高阶 Lambda）以及应用操作。

fn expr(u: isize, v: isize, w: isize) -> Gadt<cu::Int, impl Attic> {
    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()
}

This looks like a heavy, complex structure. However, when we compile this in release mode and inspect the assembly for eval_expr, we see something magical: 这看起来像是一个沉重且复杂的结构。然而，当我们以 release 模式编译并检查 eval_expr 的汇编代码时，我们看到了神奇的一幕：

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

The entire expression tree, the lambdas, the apply calls—it has all been boiled down to a series of arithmetic instructions (leaq, addq). There is no interpreter loop, no dynamic dispatch, no memory allocation. This is the “zero-cost” promise fulfilled. 整个表达式树、Lambda、apply 调用——所有这些都被简化为一系列算术指令 (leaq, addq)。没有解释器循环，没有动态分发，没有内存分配。这就是“零成本”承诺的实现。

The Interpreter: A Simple eval Implementation

解释器：简单的 eval 实现

How is this possible? The evaluation logic is defined in an Eval trait. Its implementation for our Gadt type is a simple match statement that recursively calls eval on its components. 这是如何实现的？求值逻辑定义在 Eval trait 中。它针对我们的 Gadt 类型的实现是一个简单的 match 语句，递归地对其组件调用 eval。

pub trait Eval<Cur: Cursor, Att: Attic> {
    fn eval(self) -> SolOf<Cur, Att>;
}

impl<Cur: Cursor, Att: Attic> Eval<Cur, Att> for Gadt<Cur, Att> {
    fn eval(self) -> SolOf<Cur, Att> {
        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
            }),
        }
    }
}

At first glance, this looks like a standard interpreter that would involve runtime overhead. The key to its optimization lies in the definition of the Gadt and Enum types. 乍一看，这看起来像是一个会产生运行时开销的标准解释器。其优化的关键在于 Gadt 和 Enum 类型的定义。

The Magic Behind the Curtain: GADT-like Enums

幕后的魔法：GADT 风格的枚举

The core of this technique is an enum that uses Rust’s never type (!) to ensure that for any given type signature, only one variant is actually constructible. This effectively removes the “tag” from the enum, as the compiler knows at compile time which variant is in use. 这项技术的核心是一个枚举，它利用 Rust 的 never 类型 (!) 来确保对于任何给定的类型签名，实际上只有一个变体是可构造的。这有效地从枚举中移除了“标签”，因为编译器在编译时就知道正在使用哪个变体。

pub struct Gadt<Cur: Cursor, Att: Attic>(
    Enum<Cur::_V01<Att>, Cur::_V02<Att>, Cur::_V03<Att>, Cur::_V04<Att>, Cur, Att>,
);

pub enum Enum<V01: Ng, V02: Ng, V03: Ng, V04: Ng, Cur: Cursor, Att: Attic> {
    __Ph__(!, Ph<(V01, V02, V03, V04, Cur, Att)>),
    IntConst(V01, V01::NGuard<isize, Cur, cu::Int, Att>),
    Lambda(V02, V02::NGuard<...>),
    Apply(V03, V03::NGuard<...>),
    Add(V04, V04::NGuard<...>),
}

The types V01 through V04 are controlled by the Attic trait. By setting these to !, we make it impossible to construct the corresponding variant. Since a value of type ! can never be created, the compiler can prove that code path is unreachable. The NGuard trait is a helper that ensures any variant “disabled” with ! has a size of zero, allowing the enum to collapse to the size of its single active variant. 类型 V01 到 V04 由 Attic trait 控制。通过将它们设置为 !，我们使得构造相应的变体变得不可能。由于类型 ! 的值永远无法被创建，编译器可以证明该代码路径是不可达的。NGuard trait 是一个辅助工具，它确保任何被 ! “禁用”的变体大小为零，从而允许枚举坍缩为其唯一活跃变体的大小。

Core Components: Cursor and Attic

核心组件：Cursor 和 Attic

The two orchestrating traits are Cursor and Attic. They work together as a type-level configuration system: 这两个协调 trait 是 Cursor 和 Attic。它们共同构成了一个类型级的配置系统：

• Attic: This trait holds the actual information about which Enum constructors are disab…
• Attic：此 trait 保存了关于哪些 Enum 构造函数被禁用的实际信息……