Skip to content

Instantly share code, notes, and snippets.

@Sgeo
Forked from mstewartgallus/gadts.rs
Last active September 10, 2024 19:24
Show Gist options
  • Save Sgeo/b707a941e2460b25d59b to your computer and use it in GitHub Desktop.
Save Sgeo/b707a941e2460b25d59b 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
#[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);
}
}
@eddyb
Copy link

eddyb commented Jan 27, 2018

Is needs to use *mut instead of *const otherwise you can write this:

fn transmute_lifetime<'a, 'b, T: 'a + 'b>(r: &'a T) -> &'b T {
    is().ltor(r)
}

@Sgeo
Copy link
Author

Sgeo commented Feb 17, 2018

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