loading...

(Ok) Tagless Final in Rust

louy2 profile image Yufan Lou ・2 min read

Rust nightly has Higher-Kinded Type! 🔥

OMG I still don't know what use this has but damn it felt magical.

Props to whoever in the compiler team working on this.

You actually have to mark the output type correctly as L::Repr<bool>!

If you pass a L::int(1) to L::add it's a compile time error and the compiler tells you that i64 doesn't match bool!

Gosh. Awesome. Amazing.

Now let's hope this won't tank the compilation time too much. 😛

#![allow(dead_code)]
#![allow(non_snake_case)]
#![allow(incomplete_features)]

#![feature(generic_associated_types)]

/*
let b (bv:bool) env = bv
let int (iv:int) env = iv
let and b1 b2 env = b1 & b2
*/

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

trait Lang {
    type Repr<T>;
    fn b(bv: bool) -> Self::Repr<bool>;
    fn int(iv: i64) -> Self::Repr<i64>;
    fn and(b1: Self::Repr<bool>, b2: Self::Repr<bool>) -> Self::Repr<bool>;
}

use core::marker::PhantomData;
struct B<P>(PhantomData<P>);
impl<P: 'static + Copy> Lang for B<P> {
    type Repr<T> = Func<P, T>;
    fn b(bv: bool) -> Self::Repr<bool> {
        Box::new(move |_env| bv)
    }
    fn int(iv: i64) -> Self::Repr<i64> {
        Box::new(move |_env| iv)
    }
    fn and(b1: Func<P, bool>, b2: Func<P, bool>) -> Func<P, bool> {
        Box::new(move |env| b1(env) & b2(env))
    }
}

struct P;
impl Lang for P {
    type Repr<T> = String;
    fn b(bv: bool) -> String {
        bv.to_string()
    }
    fn int(iv: i64) -> Self::Repr<i64> {
        iv.to_string()
    }
    fn and(b1: String, b2: String) -> String {
        format!("{} & {}", b1, b2)
    }
}

fn prog1<L>() -> L::Repr<bool>
where 
    L: Lang,
{
    L::and(L::b(false), L::b(true))
}

// fn prog_with_error<L>() -> L::Repr<bool>
// where
//     L: Lang,
// {
//     L::and(L::int(3), L::b(true))
// }

fn main() {
    let test1_p = prog1::<P>();
    println!("{:?}", test1_p);
    let test1_b = prog1::<B<()>>()(());
    println!("{:?}", test1_b);
}

// TODO: De Brujin Indices

Discussion

pic
Editor guide