Gadts in Rust

gadts.rs

/// This type is only every inhabited when S is nominally equivalent to T
pub type Is <S, T> = Is_ <S, T>;

priv struct Is_ <S, T>;

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

pub 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.
    fn ltor (&self, value : S) -> T { unsafe { cast::transmute (value) } }
    fn rtol (&self, value : S) -> S { unsafe { cast::transmute (value) } }
}


// Tadaa! A GADT!
enum Expression <T> {
    Number (Is <T, uint>, uint),
    Add (Is <T, uint>, @Expression <uint>, @Expression <uint>)
}

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

fn number (value : uint) -> Expression <uint> { Number (Is (), value) }

impl Add <Expression <uint>, Expression <uint>> for Expression <uint> {
    fn add (&self, &rhs : &Expression <uint>) -> Expression <uint> {
        let &lhs = self;
        Add (Is (), @lhs, @rhs)
    }
}

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

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

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

This is for an old version of Rust. I modernized it in my fork.