megakorre/rust-poly.md

## rust-poly.md

      
    Raw
  

              rust-poly.md
            
          
    EDIT! full code can be found here gist
So I played around with rust a bit now.
And I thought I might share some random stuff.
So say you wanted to represent a expression tree with plus and minus nodes and a
node for values. One way to do this would be to use rust's enum's.
In rust enums are like haskell's union types so you can specify the different values
to be constructors carrying data.
     enum expr {
        val(int),
        plus(&expr, &expr),
        minus(&expr, &expr)
    }
Any recursive constructor needs to use a reference type to expr.
In this case I use the borrowed pointer type.
so to make a function that evals this expression you just
make use of some pattern matching and recursion
fn eval(e: &expr) -> int {
    alt *e {
      val(i) => i,
      plus(a,b) => eval(a) + eval(b),
      minus(a,b) => eval(a) - eval(b)
    }
}
So I can now build any tree of these constructors and eval it
fn run() {
   let x = eval(
     &minus(&val(5),
       &plus(&val(3), &val(1))));
        
    io::println(#fmt("val: %i", x)); // => prints 1
}
putting a & in front of a expression allocates it on the stack
and gives you a reference to it. so the lifetime of this tree is
to the end of the run function.
Now this is a awesome and a relay terse solution,
but we off course have to bring out the big polymorphism guns
to get a open tree where any evaluable expression can participate.
So we start by defining a trait
trait Expr {
    fn eval() -> int;
}
So there's now a trait that can be evaluated to a int
so let's create the 3 node types
enum plus = (int,int);
enum minus = (int,int);
I use enum's here so I don’t have to name the arguments with a struct..
I don’t create a wrapper for val this time beaus I’m going to use the int
type directly.
impl of Expr for plus {
    fn eval() -> int {
        alt self { plus((ref a,ref b)) => a.eval() + b.eval() }
    }
}

impl of Expr for minus {
    fn eval() -> int {
        alt self { minus((ref a,ref b)) => a.eval() - b.eval() }
    }
}

impl of Expr for int {
    fn eval() -> int { self }
}
So now we can build a tree with using these enums
and use virtual dispatch to evaluate the tree.
fn main() {
    let v = minus((5 as Expr, 
                  plus((
                      3 as Expr, 
                      1 as Expr)) as Expr));
    
    io::println(#fmt("%i", v.eval())); // => prints 1
}
The "as Expr" makes a kind of virtual object that can be passed in to
the structure.
Note the v.eval() don’t use virtual dispatch here because the compiler knows the exact
type of v;
We can make this even more general if we want using generics.
enum plus<T:Expr,T2:Expr> = (T,T2);
enum minus<T:Expr,T2:Expr> = (T,T2);
We can write the enum types with generics so that we don’t need to use the as Expr
case when building the tree. And when we know the type at compile time we don’t need
to use virtual dispatch.
The trait impl needs to be made generic to
impl plus_expr<T:Expr,T2:Expr> of Expr for plus<T,T2> {
    fn eval() -> int {
        alt self {
          plus((ref a, ref b)) => a.eval() + b.eval()
        }
    }
}

impl minus_expr<T:Expr,T2:Expr> of Expr for minus<T,T2> {
    fn eval() -> int {
        alt self {
          minus((ref a, ref b)) => a.eval() - b.eval()
        }
    }
}
Now I can change the tree construction to
fn main() {
    let v = minus((5, plus((3, 1))));
    io::println(#fmt("%i", v.eval()));
}
The type of v in this code is minus<int, plus<int, int>>
witch is pretty cool. I can now use these to build any mix
of virtual Expr objects and typed Expr implementers I want.
This is really awesome but the first implementation is probably
good enough for most situation.
I have barely started to to play around with rust so if you have
some other better way of doing expression tree's please comment
I would love to read it.