DEV Community πŸ‘©β€πŸ’»πŸ‘¨β€πŸ’»

DEV Community πŸ‘©β€πŸ’»πŸ‘¨β€πŸ’» is a community of 966,904 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

Create account Log in
Yufan Lou
Yufan Lou

Posted on

(Not) Finally Tagless in Rust

Tagless Final is a style of programming derived first by Oleg Kiselyov to be used in ML for embedding domain specific languages (DSL), but from ML point of view every API is a DSL so really it is a style to write APIs ergonomically.

The name "Tagless Final" is probably foreign to most programmers. "Tagless" means without tag, which is usually an allocation to store the abstract syntax tree of the language. Without this allocation means less overhead. To do so, instead of constructors, which is theorized by the "initial" algebra of the Ξ»-calculus, this style uses functions, which is theorized by the coalgebra of the Ξ»-calculus, and thus named "final". No, I do not understand what I just wrote.

What is fun with this style is that it achieves the best separation of specification and implementation bar none. In Rust each part of the specification is a trait, like so:

trait Prim {
    fn int(v: i64) -> Self;
    fn bool(v: bool) -> Self;
}
trait AddOp {
    fn add(x: Self, y: Self) -> Self;
}
trait IfOp {
    fn leq(x: Self, y: Self) -> Self;
    fn if_<'a>(cond: Self, x: Box<dyn Fn() -> Self>, y: Box<dyn Fn() -> Self>) -> Self;
}

The program is then written only in terms of the traits:

fn prog<S>() -> S
where
    S: Prim + AddOp + IfOp
{
    S::if_(
        S::leq(S::int(5), S::int(9)),
        Box::new(|| S::add(S::int(3), S::int(8))),
        Box::new(|| S::int(7)),
    )
}

When executing the program, you just supply the implementation as the type parameter:

fn main() {
    println!("{:?}", prog::<P>());
    println!("{:?}", prog::<R>());
}

Here I implemented P as a pretty printer and R as a simple evaluator. The printed results are:

P("if 5 <= 9 { 3 + 8 } else { 7 }")
Int(11)

This style also is claimed to have solved "the Expression Problem", a dilemma created by module boundaries and orphan rules which have forced us to trade-off between a closed set of operators for stricter checks or an open set of operators for easier extensions. With this style, sets of operators and interpreters can be defined at will, while the set of operators is closed by the trait bounds attached to the program. Best of both worlds! Hopefully.

Unfortunately when used in Rust, this style cannot reach its full potential. In an ML with higher kinded type (HKT), Tagless Final can do the following things that in Rust I have not found a way to do:

  • Enforce the types of the operators
  • Enforce the parametricity of the operators
  • No tags for primitive types in the implementation

If you are curious, the code is in the gist below.

Top comments (0)

All DEV content is created by the community!

Hey, if you're landing here for the first time, you should know that this website is a global community of folks who blog about their experiences to help folks like you out.

Sign up now if you're curious. It's free!