.png)
4 months ago
5
Table of Contents
- Introduction: The Allure of Tagless Final
- The Goal: “Tagless Initial” Encoding
- A First Look: The Rust Expression and Its Assembly
- The Interpreter: A Simple eval Implementation
- The Magic Behind the Curtain: GADT-like Enums
- Core Components: Cursor and Attic
- The Zero-Cost Proof: An Experiment with the never Type
- Conclusion
Introduction: The Allure of 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.
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.
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:
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.
A First Look: The Rust Expression and Its Assembly
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.
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:
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.
The Interpreter: A Simple eval Implementation
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.
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.
The Magic Behind the Curtain: GADT-like Enums
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.
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.
Core Components: Cursor and Attic
The two orchestrating traits are Cursor and Attic. They work together as a type-level configuration system:
- Attic: This trait holds the actual information about which Enum constructors are disabled. In its default state, it sets all _V* types to !, effectively disabling all variants. To enable a constructor, a specific Attic implementation will provide a non-! type.
- Cursor: This trait acts as a filter or view, selecting which configuration from Attic to apply at each point in the expression tree.
Through this mechanism, we can construct a Gadt type where only one of the Enum variants is valid, making pattern matching in eval fully predictable at compile time.
The Zero-Cost Proof: An Experiment with the never Type
What happens if we break this invariant? Let’s conduct an experiment. We’ll replace ! with a concrete, zero-sized type like ((),) in our Attic trait. This means that all variants are now theoretically constructible.
Suddenly, the compiler can no longer guarantee which variant is active. It must now include a tag (discriminant) and perform runtime checks. The generated assembly explodes:
We now see explicit calls to eval. The abstraction is no longer zero-cost; it’s being interpreted at runtime. This demonstrates that the never type is the critical component for achieving taglessness and enabling compiler optimization.
One might think that simply adding #[inline(always)] to eval could fix this. Indeed, in this simple case, inlining can help the optimizer untangle the calls and produce much better assembly. However, this is not a robust solution. It relies on optimizer heroics and will likely fail in more complex, modular programs where DSLs are nested or defined across different crates. The never type approach guarantees the optimization by construction.
Conclusion
By carefully using Rust’s type system, particularly the never type (!), we can successfully implement the “tagless initial” pattern. We created a Gadt-style enum where only one variant is constructible for any given type, effectively removing the need for a runtime tag. This allows the compiler to see through the abstraction entirely, collapsing a complex expression tree into its raw computational equivalent.
This technique provides a powerful blueprint for building high-level, expressive DSLs in Rust without compromising on the performance expectations of a systems language.
You can experiment with the full code yourself:
Join this blog discussion:
