Tagless-final encoding of a simple arithmetic language in Rust

tagless-final.rs

trait Interp {
    type Repr<T>;

    fn lit(i: i32) -> Self::Repr<i32>;
    fn add(a: Self::Repr<i32>, b: Self::Repr<i32>) -> Self::Repr<i32>;
}

struct Eval;

impl Interp for Eval {
    type Repr<T> = i32;

    fn lit(i: i32) -> Self::Repr<i32> {
        i
    }

    fn add(a: Self::Repr<i32>, b: Self::Repr<i32>) -> Self::Repr<i32> {
        a + b
    }
}

struct Print;

impl Interp for Print {
    type Repr<T> = String;

    fn lit(i: i32) -> Self::Repr<i32> {
        format!("{i}")
    }

    fn add(a: Self::Repr<i32>, b: Self::Repr<i32>) -> Self::Repr<i32> {
        format!("({a}) + ({b})")
    }
}

struct Neg<I>(std::marker::PhantomData<I>);

impl<I: Interp> Interp for Neg<I> {
    type Repr<T> = I::Repr<T>;

    fn lit(i: i32) -> Self::Repr<i32> {
        I::lit(-i)
    }

    fn add(a: Self::Repr<i32>, b: Self::Repr<i32>) -> Self::Repr<i32> {
        I::add(a, b)
    }
}

fn expr<I: Interp>() -> I::Repr<i32> {
    I::add(I::lit(42), I::add(I::lit(1), I::lit(2)))
}

fn main() {
    dbg!(expr::<Eval>()); // 45
    dbg!(expr::<Print>()); // "(42) + ((1) + (2))"
    dbg!(expr::<Neg<Eval>>()); // -45
    dbg!(expr::<Neg<Print>>()); // "(-42) + ((-1) + (-2))"
}

Borrowed from "Tagless-final primer" of Oleg Kiselyov.
Playground >>