Toy Expression Interpreter

Question

I've just started learning Rust (coming from Haskell) and decided to test a toy expression interpreter.

Code:

use std::rc::Rc;

pub type RAST<T> = Rc<AST<T>>;

#[derive(Debug)]
pub enum AST<T> {
    ConstInt(isize, Rc<T>),
    Add(RAST<T>, RAST<T>, Rc<T>),
}

pub fn eval<T>(x: &RAST<T>) -> RAST<T> {
    match &**x {
        AST::Add::<T>(l, r, t) => {
            let el = eval(&l);
            let er = eval(&r);
            match (&*el, &*er) {
                (AST::ConstInt::<T>(li,_q),
                 AST::ConstInt::<T>(ri,_r)) =>
                    Rc::new(AST::ConstInt::<T>(li+ri, Rc::clone(t))),
                _ => mk_add(&el, &er, &t),
            }
        },
        _ => Rc::clone(x),
    }
}

pub fn mk_int<T>(i: isize, t: &Rc<T>) -> RAST<T> {
    Rc::new(AST::ConstInt::<T>(i, Rc::clone(t)))
}

pub fn mk_add<T>(l: &RAST<T>, r: &RAST<T>, t: &Rc<T>) -> RAST<T> {
    Rc::new(AST::Add::<T>(Rc::clone(l), Rc::clone(r), Rc::clone(t)))
}

pub fn main() {
    let a = Rc::new(());

    let x = mk_int(3, &a);
    let y = mk_int(6, &a);
    let z = mk_add(&x, &y, &a);
    let c = mk_add(&x, &z, &a);

    let r = eval(&c);
    println!("Raw: {:?}", c);
    println!("Evaluated: {:?}", r);
}

With this output:

Raw: Add(ConstInt(3, ()), Add(ConstInt(3, ()), ConstInt(6, ()), ()), ())
Evaluated: ConstInt(12, ())

I'd really appreciate any feedback on:

1. Am I using the "right" type for the Add subnodes (i.e. Rc)?
2. Is it possible to create eval as an AST method instead of a function? I kept fighting the borrow checking if x in eval was self : &AST<T> (within the impl block, of course)
3. Is there any way to make this program more concise/cleaner? I think I understand why all the additional wrapping and sprinkling of Rc::clone/new and lots of reference taking is needed, but was wondering if I was perhaps missing something that might make this code cleaner to read. Any other feedback/helpful pointers would also be appreciated. Thank you!

Answer 1

Am I using the "right" type for the Add subnodes (i.e. Rc)?

No. You probably don't want to do that. Just use AST. Good Rust code rarely actually needs Rc. Instead of using Rc<> in the definition of AST, use Box.

#[derive(Debug)]
pub enum AST<T> {
    ConstInt(isize, Rc<T>),
    Add(Box<AST<T>>, Box<AST<T>>, Rc<T>),
}

Now Rc does give you the ability to reuse branches of the AST. For example, you use x twice. However, I've not seen a real case of ASTs where that needs to happen. As it stands you are paying the costs of RC (both in programmer effort, execution time, and memory overahead) for no good reason.

You should also get rid of the Rc<> for the T. Just store a T. In cases where you need to be able to copy the T for some reason (which is probably never), take a <T: Clone> so you can call the clone method. The client code can then put in Rc<> in place if it wants, or if the data is trivial just allow it to be copied.

I would also question the usefulness of a generic type here at all. Are you really going to annotate the same AST with different additional data in different places? I rather doubt it.

Is it possible to create eval as an AST method instead of a function? I kept fighting the borrow checking if x in eval was self : &AST (within the impl block, of course)

You'll find that if you don't try to pass ASTs in Rc<> that this will work much better. The problem is that you can't take self to be an Rc<>, so you don't get access to the reference counter itself which makes it difficult to do anything useful.

Even if you use RC, you can define a static method in the impl (just don't have a self parameter. Then you can use syntax like AST::eval(ast).

pub fn eval<T>(x: &RAST<T>) -> RAST<T> {

This function is pretty strange. Why does an evaluation function return an AST. Shouldn't it return a value? If instead this function were to return isize it would be a much simpler function.

However, the logic of the function makes more sense if it is a optimization function. That is, it seeks to produce a more optimized version of the AST rather than evaluate the AST. But if that's the idea, your function takes the wrong type. It might make sense for the optimization function to take ownership of the AST, consuming the old AST reusing peices of it for the new AST. Or it might make sense to take a mutable reference to the AST, modifying the AST to make a more optimized version.

Is there any way to make this program more concise/cleaner? I think I understand why all the additional wrapping and sprinkling of Rc::clone/new and lots of reference taking is needed, but was wondering if I was perhaps missing something that might make this code cleaner to read.

Yes, if you follow my advice aboev you'll find the code a lot more concise and cleaner.