(Maybe) Tagless Final in Rust

louy2 profile image Yufan Lou ・1 min read

Why the biggest take away from Tagless Final has been the type class abstraction, I am kinda confused now. Anyway.

I thought I couldn't enforce types in the operators. That is wrong. I just cannot enforce types in the operators as confined in a trait. That's where the Higher-Kinded Type is useful.


let varZ env = fst env
let varS vp env = vp (snd env)
let b (bv:bool) env = bv
let lam e env = fun x -> e (x,env)
let app e1 e2 env = (e1 env) (e2 env)

type Func<T, O> = Box<dyn FnOnce(T) -> O>;

fn varZ<A, B>() -> Func<(A, B), A> {
    Box::new(|env| env.0)

fn varS<A, T1: 'static, T2: 'static>(vp: Func<T1, T2>) -> Func<(A, T1), T2> {
    Box::new(move |env| vp(env.1))

fn b<P>(bv: bool) -> Func<P, bool> {
    Box::new(move |_env| bv)

fn lam<A: 'static, B: 'static, T: 'static>(e: Func<(A, B), T>) -> Func<B, Func<A, T>> {
    Box::new(|env| Box::new(|x| e((x, env))))

fn app<T1: 'static + Copy, T2: 'static, T3: 'static>(
    e1: Func<T1, Func<T2, T3>>,
    e2: Func<T1, T2>,
) -> Func<T1, T3> {
    Box::new(|env| e1(env)(e2(env)))

fn main() {
    let testf1 = app(lam(varZ()), b(true));
    println!("{}", testf1(()));
    let testf3 = app(lam(varS(varZ())), b(true));
    println!("{}", testf3((1, (2))));


Editor guide