Skip to content

Instantly share code, notes, and snippets.

@mstewartgallus
Last active November 2, 2019 18:59
Show Gist options
  • Save mstewartgallus/5605948 to your computer and use it in GitHub Desktop.
Save mstewartgallus/5605948 to your computer and use it in GitHub Desktop.
Gadts in Rust
/// 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));
}
}
@Sgeo
Copy link

Sgeo commented Mar 26, 2016

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment