Gadts in Rust (I tried to see if I could hack in trait-based generics for each variant. Nope. :-()

gadts.rs

use std::marker::PhantomData;
use std::ptr;
use std::mem;
use std::ops::Add;

/// This type is only every inhabited when S is nominally equivalent to T
#[derive(Debug)]
pub struct Is<S, T>(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(PhantomData)
}

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

impl<S, T> Is<S, T> {
    pub fn expr(&self, expr: Box<Expr<T>>) -> S {
        self.value(expr.eval())
    }

    pub fn value(&self, value: T) -> S {
        unsafe { transmute(value) }
    }
}

#[derive(Debug)]
pub struct Addable<S, T>(Is<S, T>);

pub fn addable<T>() -> Addable<T, T>
    where T: Add<Output = T>,
          Box<Expr<T>>: Add<Output = T>
{
    Addable(is())
}

// Tadaa! A GADT!
#[derive(Debug)]
pub enum Expr<T> {
    Bool(Is<T, bool>, bool),
    Int(Is<T, i64>, i64),
    Float(Is<T, f64>, f64),
    Add(Addable<T, T>, Box<Expr<T>>, Box<Expr<T>>),
    If(Box<Expr<bool>>, Box<Expr<T>>, Box<Expr<T>>),
    Greater(Is<T, bool>, Box<Expr<i64>>, Box<Expr<i64>>),
}

impl<T> Expr<T> {
    fn eval(self) -> T {
        match self {
            Expr::Bool(is_a, bool) => is_a.value(bool),
            Expr::Int(is_a, int) => is_a.value(int),
            Expr::Float(is_a, float) => is_a.value(float),
            Expr::Add(addable, lhs, rhs) => addable.0.value(lhs + rhs),
            Expr::If(cond, then, else_) => {
                if cond.eval() {
                    then.eval()
                } else {
                    else_.eval()
                }
            }
            Expr::Greater(is_a, is_greater, is_lesser) => {
                is_a.value(is_greater.eval() > is_lesser.eval())
            }
        }
    }

    fn if_(cond: Box<Expr<bool>>, then: Box<Expr<T>>, else_: Box<Expr<T>>) -> Box<Self> {
        Box::new(Expr::If(cond, then, else_))
    }

    fn add(a: Box<Expr<T>>, b: Box<Expr<T>>) -> Box<Self>
        where T: Add<Output = T>,
              Box<Expr<T>>: Add<Output = T>
    {
        Box::new(Expr::Add(addable(), a, b))
    }
}

impl Expr<i64> {
    fn number(value: i64) -> Box<Self> {
        Box::new(Expr::Int(is(), value))
    }
}

impl Expr<bool> {
    fn bool(value: bool) -> Box<Self> {
        Box::new(Expr::Bool(is(), value))
    }

    fn greater(is_greater: Box<Expr<i64>>, is_lesser: Box<Expr<i64>>) -> Box<Self> {
        Box::new(Expr::Greater(is(), is_greater, is_lesser))
    }
}

// Returning Exprs from these makes it far too easy to create a surprise
// infinite loop of evals.
/*impl Add<Expr<usize>> for Expr<usize> {
    type Output = usize;
    fn add(self, rhs: Expr<usize>) -> Self::Output {
        let lhs = self;
        lhs.eval() + rhs.eval()
        //Expr::Add(is(), Box::new(lhs), Box::new(rhs))
    }
}*/
/*impl Add<Box<Expr<usize>>> for Box<Expr<usize>> {
    type Output = usize;
    fn add(self, rhs: Box<Expr<usize>>) -> Self::Output {
        let lhs = self;
        lhs.eval() + rhs.eval()
    }
}*/

impl<T> Add<Box<Expr<T>>> for Box<Expr<T>>
    where T: Add<Output = T>
{
    type Output = T;

    fn add(self, rhs: Box<Expr<T>>) -> T {
        self.eval() + rhs.eval()
    }
}

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

    //let expr: Expr<usize> = Expr::number(x) + Expr::number(y);
    let expr = Expr::add(Expr::number(4), Expr::number(6));
    let result = expr.eval();

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