Gadts in Rust

gadts.rs

/// This type is only every inhabited when S is nominally equivalent to T
#[derive(Debug)]
pub struct Is<S, T>(::std::marker::PhantomData<(*const S, *const T)>);

// Construct a proof of the fact that a type is nominally equivalent
// to itself.
pub fn is<T>() -> Is<T, T> { Is(::std::marker::PhantomData) }

// std::mem::transmute does not accept unsubstituted type parameters
// manual transmute as suggested by manual
unsafe fn transmute<S, T>(s: S) -> T {
    use std::ptr;
    use std::mem;
    
    let result = ptr::read(&s as *const _ as *const T);
    mem::forget(s);
    result
}

impl<S, T> Is<S, T> {
    // What we really need here is a type class so we can have the
    // following two methods:
    //
    // fn ltor <F> (&self, F <T>) -> F <S>;
    // fn rtol <F> (&self, F <S>) -> F <T>;
    //
    // Note that under our hypothesized future interface f
    // (caster.ltor (x)) would not always equal f (x) because of side
    // effects, and so this proposed future interface would still be
    // slightly broken. At the very least, the problem would leak out
    // in timing the differing performance of the values.

    /// These are safe because the Is type is always guaranteed to only be
    /// inhabited by Is <T, T> types.
    pub fn ltor (&self, value : S) -> T { unsafe { transmute (value) } }
    pub fn rtol (&self, value : T) -> S { unsafe { transmute (value) } }
}


// Tadaa! A GADT!
#[derive(Debug)]
enum Expression<T> {
    Number (Is<T, usize>, usize),
    Add (Is<T, usize>, Box<Expression<usize>>, Box<Expression<usize>>)
}

impl<T> Expression<T> {
    fn evaluate(self) -> T {
        match self {
            Expression::Number(caster, number) => caster.rtol(number),
            Expression::Add(caster, lhs, rhs) => caster.rtol (
                lhs.evaluate() + rhs.evaluate())
        }
    }
}

fn number(value: usize) -> Expression<usize> { Expression::Number (is(), value) }

use std::ops::Add;
impl Add<Expression<usize>> for Expression<usize> {
    type Output = Expression<usize>;
    fn add(self, rhs: Expression <usize>) -> Expression<usize> {
        let lhs = self;
        Expression::Add (is(), Box::new(lhs), Box::new(rhs))
    }
}

#[test]
fn test_expression_tree () {
    let (x, y) = (4, 6);
    let expected_result = x + y;

    let expression : Expression<usize> = number(x) + number(y);
    let result = expression.evaluate();

    if result != expected_result {
        panic!("The expression evaluated to {:?}, and not the expected result {:?}", result, expected_result);
    }
}