200 Advanced

Tagless Final

DSLsType System

Tutorial Video

Text description (accessibility)

This video demonstrates the "Tagless Final" functional Rust example. Difficulty level: Advanced. Key concepts covered: DSLs, Type System. Embed a typed DSL directly as trait/module methods so that multiple interpreters (evaluate, pretty-print, type-check…) can share one program definition without building an intermediate AST. Key difference from OCaml: 1. **Type abstraction:** OCaml uses `type 'a repr` (higher

Tutorial

The Problem

Embed a typed DSL directly as trait/module methods so that multiple interpreters (evaluate, pretty-print, type-check…) can share one program definition without building an intermediate AST.

🎯 Learning Outcomes

• How OCaml module types with abstract type constructors (type 'a repr) map to Rust traits with Generic Associated Types (type Repr<T>)

• Why Generic Associated Types (GATs) are the key enabler for tagless final in Rust

• The contrast between initial encoding (explicit AST enum) and final encoding (trait methods): the former centralises interpretation, the latter distributes it

• How Repr<T> = T (evaluate) and Repr<T> = String (pretty-print) express two completely different semantics through the same interface

🦀 The Rust Way

Rust replaces the OCaml module type with a trait Expr whose associated type Repr<T> is a Generic Associated Type (GAT). Each interpreter is a zero-sized struct (Eval, Pretty) implementing Expr. The program is a generic function fn program<E: Expr>() -> E::Repr<i64> — calling it with program::<Eval>() evaluates; program::<Pretty>() pretty-prints. No runtime dispatch, no heap allocation.

Code Example

pub trait Expr {
    type Repr<T>;
    fn int(n: i64) -> Self::Repr<i64>;
    fn bool_val(b: bool) -> Self::Repr<bool>;
    fn add(a: Self::Repr<i64>, b: Self::Repr<i64>) -> Self::Repr<i64>;
    fn mul(a: Self::Repr<i64>, b: Self::Repr<i64>) -> Self::Repr<i64>;
    fn leq(a: Self::Repr<i64>, b: Self::Repr<i64>) -> Self::Repr<bool>;
    fn if_<T>(c: Self::Repr<bool>, t: Self::Repr<T>, e: Self::Repr<T>) -> Self::Repr<T>;
}

pub struct Eval;
impl Expr for Eval {
    type Repr<T> = T;
    fn int(n: i64) -> i64 { n }
    fn bool_val(b: bool) -> bool { b }
    fn add(a: i64, b: i64) -> i64 { a + b }
    fn mul(a: i64, b: i64) -> i64 { a * b }
    fn leq(a: i64, b: i64) -> bool { a <= b }
    fn if_<T>(c: bool, t: T, e: T) -> T { if c { t } else { e } }
}

pub struct Pretty;
impl Expr for Pretty {
    type Repr<T> = String;
    fn int(n: i64) -> String { n.to_string() }
    fn bool_val(b: bool) -> String { b.to_string() }
    fn add(a: String, b: String) -> String { format!("({a} + {b})") }
    fn mul(a: String, b: String) -> String { format!("({a} * {b})") }
    fn leq(a: String, b: String) -> String { format!("({a} <= {b})") }
    fn if_<T>(c: String, t: String, e: String) -> String {
        format!("(if {c} then {t} else {e})")
    }
}

pub fn program<E: Expr>() -> E::Repr<i64> {
    E::if_(
        E::leq(E::add(E::int(3), E::int(4)), E::mul(E::int(2), E::int(5))),
        E::int(42),
        E::int(0),
    )
}

module type EXPR = sig
  type 'a repr
  val int  : int  -> int repr
  val bool : bool -> bool repr
  val add  : int repr -> int repr -> int repr
  val mul  : int repr -> int repr -> int repr
  val leq  : int repr -> int repr -> bool repr
  val if_  : bool repr -> 'a repr -> 'a repr -> 'a repr
end

module Eval : EXPR = struct
  type 'a repr = 'a
  let int  n    = n
  let bool b    = b
  let add  a b  = a + b
  let mul  a b  = a * b
  let leq  a b  = a <= b
  let if_ c t e = if c then t else e
end

module Pretty : EXPR = struct
  type 'a repr = string
  let int  n    = string_of_int n
  let bool b    = string_of_bool b
  let add  a b  = Printf.sprintf "(%s + %s)" a b
  let mul  a b  = Printf.sprintf "(%s * %s)" a b
  let leq  a b  = Printf.sprintf "(%s <= %s)" a b
  let if_ c t e = Printf.sprintf "(if %s then %s else %s)" c t e
end

let program (type a) (module E : EXPR with type 'x repr = 'x a) =
  let open E in
  if_ (leq (add (int 3) (int 4)) (mul (int 2) (int 5)))
      (int 42) (int 0)

Key Differences

Type abstraction: OCaml uses type 'a repr (higher-kinded); Rust uses type Repr<T> (Generic Associated Type, stable since 1.65)

Module vs. trait: OCaml passes interpreters as first-class modules; Rust uses monomorphisation over a type parameter

**bool keyword:** OCaml names the constructor bool; Rust must rename to bool_val since bool is a built-in type

Zero-cost: Both encodings are zero-cost — no boxing or dynamic dispatch in the final encoding

OCaml Approach

OCaml uses a first-class module type EXPR with an abstract type constructor 'a repr. Each interpreter is a module that instantiates repr differently — Eval sets type 'a repr = 'a (the identity) and Pretty sets type 'a repr = string. The program is a polymorphic function parameterised over any module satisfying EXPR, so calling it with different modules yields different results.

Full Source

#![allow(clippy::all)]
// Tagless Final: embed DSLs as trait methods — no intermediate AST.
// Multiple interpreters share one program definition.

// =============================================================
// Solution 1: Tagless Final — Generic Associated Types (GATs)
// Direct translation of OCaml's module type with type constructor
// =============================================================

/// The DSL signature — written once, interpreted many ways.
///
/// `Repr<T>` is the "representation" type: what this interpreter
/// produces for a value of type `T`.  For `Eval`, `Repr<T> = T`
/// (the value itself).  For `Pretty`, `Repr<T> = String` (always
/// a string, regardless of `T`).
pub trait Expr {
    type Repr<T>;

    fn int(n: i64) -> Self::Repr<i64>;
    fn bool_val(b: bool) -> Self::Repr<bool>;
    fn add(a: Self::Repr<i64>, b: Self::Repr<i64>) -> Self::Repr<i64>;
    fn mul(a: Self::Repr<i64>, b: Self::Repr<i64>) -> Self::Repr<i64>;
    fn leq(a: Self::Repr<i64>, b: Self::Repr<i64>) -> Self::Repr<bool>;
    fn if_<T>(c: Self::Repr<bool>, t: Self::Repr<T>, e: Self::Repr<T>) -> Self::Repr<T>;
}

// --- Interpreter 1: Evaluate ---
// Repr<T> = T — the representation IS the value.
pub struct Eval;

impl Expr for Eval {
    type Repr<T> = T;

    fn int(n: i64) -> i64 {
        n
    }
    fn bool_val(b: bool) -> bool {
        b
    }
    fn add(a: i64, b: i64) -> i64 {
        a + b
    }
    fn mul(a: i64, b: i64) -> i64 {
        a * b
    }
    fn leq(a: i64, b: i64) -> bool {
        a <= b
    }
    fn if_<T>(c: bool, t: T, e: T) -> T {
        if c {
            t
        } else {
            e
        }
    }
}

// --- Interpreter 2: Pretty-print ---
// Repr<T> = String — always produces a string, ignoring T.
pub struct Pretty;

impl Expr for Pretty {
    type Repr<T> = String;

    fn int(n: i64) -> String {
        n.to_string()
    }
    fn bool_val(b: bool) -> String {
        b.to_string()
    }
    fn add(a: String, b: String) -> String {
        format!("({a} + {b})")
    }
    fn mul(a: String, b: String) -> String {
        format!("({a} * {b})")
    }
    fn leq(a: String, b: String) -> String {
        format!("({a} <= {b})")
    }
    fn if_<T>(c: String, t: String, e: String) -> String {
        format!("(if {c} then {t} else {e})")
    }
}

/// The program — written once, run through any interpreter.
///
/// Encodes: `if (3 + 4) <= (2 * 5) then 42 else 0`
pub fn program<E: Expr>() -> E::Repr<i64> {
    E::if_(
        E::leq(E::add(E::int(3), E::int(4)), E::mul(E::int(2), E::int(5))),
        E::int(42),
        E::int(0),
    )
}

// =============================================================
// Solution 2: Initial Encoding — explicit AST for comparison
// Adding a new interpreter requires modifying eval_ast here.
// Tagless final avoids that: new interpreter = new impl block.
// =============================================================

#[derive(Debug, Clone, PartialEq)]
pub enum Ast {
    Int(i64),
    Bool(bool),
    Add(Box<Ast>, Box<Ast>),
    Mul(Box<Ast>, Box<Ast>),
    Leq(Box<Ast>, Box<Ast>),
    If(Box<Ast>, Box<Ast>, Box<Ast>),
}

#[derive(Debug, Clone, PartialEq)]
pub enum Value {
    Int(i64),
    Bool(bool),
}

/// Evaluate an AST to a `Value`.
pub fn eval_ast(ast: &Ast) -> Value {
    match ast {
        Ast::Int(n) => Value::Int(*n),
        Ast::Bool(b) => Value::Bool(*b),
        Ast::Add(a, b) => match (eval_ast(a), eval_ast(b)) {
            (Value::Int(x), Value::Int(y)) => Value::Int(x + y),
            _ => panic!("type error: add requires integers"),
        },
        Ast::Mul(a, b) => match (eval_ast(a), eval_ast(b)) {
            (Value::Int(x), Value::Int(y)) => Value::Int(x * y),
            _ => panic!("type error: mul requires integers"),
        },
        Ast::Leq(a, b) => match (eval_ast(a), eval_ast(b)) {
            (Value::Int(x), Value::Int(y)) => Value::Bool(x <= y),
            _ => panic!("type error: leq requires integers"),
        },
        Ast::If(c, t, e) => match eval_ast(c) {
            Value::Bool(true) => eval_ast(t),
            Value::Bool(false) => eval_ast(e),
            _ => panic!("type error: if condition must be bool"),
        },
    }
}

/// The same program built with the initial (AST) encoding.
pub fn program_ast() -> Ast {
    Ast::If(
        Box::new(Ast::Leq(
            Box::new(Ast::Add(Box::new(Ast::Int(3)), Box::new(Ast::Int(4)))),
            Box::new(Ast::Mul(Box::new(Ast::Int(2)), Box::new(Ast::Int(5)))),
        )),
        Box::new(Ast::Int(42)),
        Box::new(Ast::Int(0)),
    )
}

#[cfg(test)]
mod tests {
    use super::*;

    // --- Tagless Final ---

    #[test]
    fn test_eval_program() {
        // (3+4)=7, (2*5)=10, 7<=10 → true → result=42
        assert_eq!(program::<Eval>(), 42);
    }

    #[test]
    fn test_pretty_program() {
        assert_eq!(
            program::<Pretty>(),
            "(if ((3 + 4) <= (2 * 5)) then 42 else 0)"
        );
    }

    #[test]
    fn test_eval_false_branch() {
        // (1+1)=2, (0*5)=0, 2<=0 → false → result=0
        let result = Eval::if_(
            Eval::leq(
                Eval::add(Eval::int(1), Eval::int(1)),
                Eval::mul(Eval::int(0), Eval::int(5)),
            ),
            Eval::int(99),
            Eval::int(0),
        );
        assert_eq!(result, 0);
    }

    #[test]
    fn test_pretty_primitives() {
        assert_eq!(Pretty::int(42), "42");
        assert_eq!(Pretty::bool_val(true), "true");
        assert_eq!(Pretty::add("3".to_string(), "4".to_string()), "(3 + 4)");
        assert_eq!(Pretty::leq("7".to_string(), "10".to_string()), "(7 <= 10)");
    }

    #[test]
    fn test_eval_arithmetic() {
        assert_eq!(Eval::add(Eval::int(10), Eval::int(32)), 42);
        assert_eq!(Eval::mul(Eval::int(6), Eval::int(7)), 42);
        assert_eq!(Eval::leq(Eval::int(5), Eval::int(5)), true);
    }

    // --- Initial encoding ---

    #[test]
    fn test_ast_program_matches_tagless() {
        let tagless = program::<Eval>();
        let initial = eval_ast(&program_ast());
        assert_eq!(initial, Value::Int(tagless));
    }

    #[test]
    fn test_ast_false_branch() {
        // leq(4, 3) → false → else branch = 0
        let ast = Ast::If(
            Box::new(Ast::Leq(Box::new(Ast::Int(4)), Box::new(Ast::Int(3)))),
            Box::new(Ast::Int(99)),
            Box::new(Ast::Int(0)),
        );
        assert_eq!(eval_ast(&ast), Value::Int(0));
    }
}

(* Tagless final: instead of building an AST (initial encoding),
   interpret expressions directly through type class (module type) methods.
   Multiple interpreters without touching the program. *)

module type EXPR = sig
  type 'a repr
  val int  : int  -> int repr
  val bool : bool -> bool repr
  val add  : int repr -> int repr -> int repr
  val mul  : int repr -> int repr -> int repr
  val leq  : int repr -> int repr -> bool repr
  val if_  : bool repr -> 'a repr -> 'a repr -> 'a repr
end

(* Interpreter 1: evaluate *)
module Eval : EXPR = struct
  type 'a repr = 'a
  let int  n     = n
  let bool b     = b
  let add  a b   = a + b
  let mul  a b   = a * b
  let leq  a b   = a <= b
  let if_ c t e  = if c then t else e
end

(* Interpreter 2: pretty-print *)
module Pretty : EXPR = struct
  type 'a repr = string
  let int  n     = string_of_int n
  let bool b     = string_of_bool b
  let add  a b   = Printf.sprintf "(%s + %s)" a b
  let mul  a b   = Printf.sprintf "(%s * %s)" a b
  let leq  a b   = Printf.sprintf "(%s <= %s)" a b
  let if_ c t e  = Printf.sprintf "(if %s then %s else %s)" c t e
end

(* The program — written once, interpreted many ways *)
let program (type a) (module E : EXPR with type 'x repr = 'x a) =
  let open E in
  if_ (leq (add (int 3) (int 4)) (mul (int 2) (int 5)))
      (int 42)
      (int 0)

let () =
  let result = program (module Eval : EXPR with type 'x repr = 'x) in
  Printf.printf "eval:   %d\n" result;
  let printed = program (module Pretty : EXPR with type 'x repr = string) in
  Printf.printf "pretty: %s\n" printed

✓ Tests Rust test suite

#[cfg(test)]
mod tests {
    use super::*;

    // --- Tagless Final ---

    #[test]
    fn test_eval_program() {
        // (3+4)=7, (2*5)=10, 7<=10 → true → result=42
        assert_eq!(program::<Eval>(), 42);
    }

    #[test]
    fn test_pretty_program() {
        assert_eq!(
            program::<Pretty>(),
            "(if ((3 + 4) <= (2 * 5)) then 42 else 0)"
        );
    }

    #[test]
    fn test_eval_false_branch() {
        // (1+1)=2, (0*5)=0, 2<=0 → false → result=0
        let result = Eval::if_(
            Eval::leq(
                Eval::add(Eval::int(1), Eval::int(1)),
                Eval::mul(Eval::int(0), Eval::int(5)),
            ),
            Eval::int(99),
            Eval::int(0),
        );
        assert_eq!(result, 0);
    }

    #[test]
    fn test_pretty_primitives() {
        assert_eq!(Pretty::int(42), "42");
        assert_eq!(Pretty::bool_val(true), "true");
        assert_eq!(Pretty::add("3".to_string(), "4".to_string()), "(3 + 4)");
        assert_eq!(Pretty::leq("7".to_string(), "10".to_string()), "(7 <= 10)");
    }

    #[test]
    fn test_eval_arithmetic() {
        assert_eq!(Eval::add(Eval::int(10), Eval::int(32)), 42);
        assert_eq!(Eval::mul(Eval::int(6), Eval::int(7)), 42);
        assert_eq!(Eval::leq(Eval::int(5), Eval::int(5)), true);
    }

    // --- Initial encoding ---

    #[test]
    fn test_ast_program_matches_tagless() {
        let tagless = program::<Eval>();
        let initial = eval_ast(&program_ast());
        assert_eq!(initial, Value::Int(tagless));
    }

    #[test]
    fn test_ast_false_branch() {
        // leq(4, 3) → false → else branch = 0
        let ast = Ast::If(
            Box::new(Ast::Leq(Box::new(Ast::Int(4)), Box::new(Ast::Int(3)))),
            Box::new(Ast::Int(99)),
            Box::new(Ast::Int(0)),
        );
        assert_eq!(eval_ast(&ast), Value::Int(0));
    }
}

Deep Comparison

OCaml vs Rust: Tagless Final

Side-by-Side Code

OCaml

module type EXPR = sig
  type 'a repr
  val int  : int  -> int repr
  val bool : bool -> bool repr
  val add  : int repr -> int repr -> int repr
  val mul  : int repr -> int repr -> int repr
  val leq  : int repr -> int repr -> bool repr
  val if_  : bool repr -> 'a repr -> 'a repr -> 'a repr
end

module Eval : EXPR = struct
  type 'a repr = 'a
  let int  n    = n
  let bool b    = b
  let add  a b  = a + b
  let mul  a b  = a * b
  let leq  a b  = a <= b
  let if_ c t e = if c then t else e
end

module Pretty : EXPR = struct
  type 'a repr = string
  let int  n    = string_of_int n
  let bool b    = string_of_bool b
  let add  a b  = Printf.sprintf "(%s + %s)" a b
  let mul  a b  = Printf.sprintf "(%s * %s)" a b
  let leq  a b  = Printf.sprintf "(%s <= %s)" a b
  let if_ c t e = Printf.sprintf "(if %s then %s else %s)" c t e
end

let program (type a) (module E : EXPR with type 'x repr = 'x a) =
  let open E in
  if_ (leq (add (int 3) (int 4)) (mul (int 2) (int 5)))
      (int 42) (int 0)

Rust (idiomatic — GAT-based tagless final)

pub trait Expr {
    type Repr<T>;
    fn int(n: i64) -> Self::Repr<i64>;
    fn bool_val(b: bool) -> Self::Repr<bool>;
    fn add(a: Self::Repr<i64>, b: Self::Repr<i64>) -> Self::Repr<i64>;
    fn mul(a: Self::Repr<i64>, b: Self::Repr<i64>) -> Self::Repr<i64>;
    fn leq(a: Self::Repr<i64>, b: Self::Repr<i64>) -> Self::Repr<bool>;
    fn if_<T>(c: Self::Repr<bool>, t: Self::Repr<T>, e: Self::Repr<T>) -> Self::Repr<T>;
}

pub struct Eval;
impl Expr for Eval {
    type Repr<T> = T;
    fn int(n: i64) -> i64 { n }
    fn bool_val(b: bool) -> bool { b }
    fn add(a: i64, b: i64) -> i64 { a + b }
    fn mul(a: i64, b: i64) -> i64 { a * b }
    fn leq(a: i64, b: i64) -> bool { a <= b }
    fn if_<T>(c: bool, t: T, e: T) -> T { if c { t } else { e } }
}

pub struct Pretty;
impl Expr for Pretty {
    type Repr<T> = String;
    fn int(n: i64) -> String { n.to_string() }
    fn bool_val(b: bool) -> String { b.to_string() }
    fn add(a: String, b: String) -> String { format!("({a} + {b})") }
    fn mul(a: String, b: String) -> String { format!("({a} * {b})") }
    fn leq(a: String, b: String) -> String { format!("({a} <= {b})") }
    fn if_<T>(c: String, t: String, e: String) -> String {
        format!("(if {c} then {t} else {e})")
    }
}

pub fn program<E: Expr>() -> E::Repr<i64> {
    E::if_(
        E::leq(E::add(E::int(3), E::int(4)), E::mul(E::int(2), E::int(5))),
        E::int(42),
        E::int(0),
    )
}

Rust (initial encoding — explicit AST for contrast)

pub enum Ast {
    Int(i64),
    Bool(bool),
    Add(Box<Ast>, Box<Ast>),
    Mul(Box<Ast>, Box<Ast>),
    Leq(Box<Ast>, Box<Ast>),
    If(Box<Ast>, Box<Ast>, Box<Ast>),
}

pub fn eval_ast(ast: &Ast) -> Value {
    match ast {
        Ast::Int(n) => Value::Int(*n),
        Ast::Add(a, b) => match (eval_ast(a), eval_ast(b)) {
            (Value::Int(x), Value::Int(y)) => Value::Int(x + y),
            _ => panic!("type error"),
        },
        // ... and so on for every node type
    }
}

Type Signatures

Concept	OCaml	Rust
DSL interface	`module type EXPR`	`trait Expr`
Type constructor	`type 'a repr`	`type Repr<T>` (GAT)
Identity interpreter	`type 'a repr = 'a`	`type Repr<T> = T`
Constant interpreter	`type 'a repr = string`	`type Repr<T> = String`
Polymorphic program	`(module E : EXPR with type 'x repr = 'x a)`	`fn program<E: Expr>()`
Dispatch	First-class module	Monomorphisation

Key Insights

GATs are the critical enabler. Before Rust 1.65, tagless final required workarounds (wrapper structs, PhantomData). The type Repr<T> GAT directly mirrors OCaml's type 'a repr with no ceremony.

Monomorphisation replaces first-class modules. OCaml passes the interpreter as a runtime module value. Rust bakes the choice into the type at compile time via <E: Expr> — zero overhead, no boxing.

**Repr<T> = T is the identity type function.** For Eval, the "representation" of an i64 is literally an i64. This is the same trick OCaml uses with type 'a repr = 'a, and Rust expresses it identically.

**Repr<T> = String ignores the phantom type.** Pretty always returns String regardless of what T is. This is the "constant functor" pattern — T is phantom, present only to satisfy the trait interface and preserve type-level information for callers.

Initial vs. final encoding trade-off. The initial encoding (AST enum) centralises interpretation in one eval_ast function — easy to add new expression types, hard to add new interpreters without touching the match arms. The final encoding (tagless trait) distributes interpretation — easy to add new interpreters as impl blocks, but extending the DSL with new operations requires updating every existing interpreter.

When to Use Each Style

Use tagless final (trait-based) when: you want multiple independent interpreters (evaluate, pretty-print, type-check, compile) that must not depend on each other, or when you're building an extensible embedded DSL where new backends are added by library consumers.

Use initial encoding (AST enum) when: you need to inspect, transform, or optimise the expression tree itself (e.g., constant folding, serialisation, pattern matching over the structure), or when adding new expression forms is the primary axis of extension.

Exercises

Add a new Console interpreter for the tagless-final algebra that prints each expression to stdout instead of evaluating it, demonstrating the open extension property.

Implement a Pretty interpreter that renders arithmetic expressions back to a human-readable string, reusing the same algebra trait without modifying existing code.

Define a larger algebra that includes both arithmetic and boolean operations, combine the two interpreters using trait composition, and implement a short-circuit evaluator that skips the right operand of And when the left is false.

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust