blog: rust pollymorpism

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.

megakorre/rust-poly.md

megakorre commented Aug 10, 2012