A simple formula interpreter

Question

To understand Rust, I am trying to implement a little formula interpreter. An expression can only be an integer, a sum, a variable (Term) or an assignment (Set). We can then evaluate an expression. Since symbols with no associated values can appear in an expression, its evaluation yields another expression (and not necessarily an integer).

The values of the variables (if there are any) can be found in a hash table.

use std::rc::Rc;
use std::collections::HashMap;

enum Expr {
    Integer(i32),
    Term(String),
    Plus(Rc<Expr>, Rc<Expr>),
    Set(Rc<Expr>, Rc<Expr>),
}

impl Expr {
    fn evaluate(&self, env: &mut HashMap<String, Expr>) -> Expr {
        match *self {
            Expr::Plus(ref a, ref b) => {
                let a_ev = Rc::new(a.evaluate(env));
                let b_ev = Rc::new(b.evaluate(env));
                match (*a_ev, *b_ev) {
                    (Expr::Integer(x), Expr::Integer(y)) => Expr::Integer(x + y),
                    _ => Expr::Plus(a_ev, b_ev),
                }
            }
            Expr::Term(ref a) => *env.get(&a).unwrap(),
            Expr::Set(ref a, ref b) => {
                let b_ev = Rc::new(b.evaluate(env));
                match **a {
                    Expr::Term(x) => {
                        let x_value = env.get_mut(&x).unwrap();
                        *x_value = *b_ev;
                        *b_ev
                    }
                    otherwise => {
                        let a_ev = Rc::new(a.evaluate(env));
                        Expr::Set(a_ev, b_ev)
                    }
                }
            }
            otherwise => otherwise,
        }
    }
}

The above code does not compile. Each match seems to borrow a variable. Moreover, I think we should not use the String type, but I can't understand why.

The compilation error:

error[E0277]: the trait bound `std::string::String: std::borrow::Borrow<&std::string::String>` is not satisfied
  --> src/main.rs:22:39
   |
22 |             Expr::Term(ref a) => *env.get(&a).unwrap(),
   |                                       ^^^ the trait `std::borrow::Borrow<&std::string::String>` is not implemented for `std::string::String`
   |
   = help: the following implementations were found:
             <std::string::String as std::borrow::Borrow<str>>

Answer 1

This is a second version where I follow Adrian's suggestion to replace all ExprNode with Rc<ExprNode>. The only cloned variables are Rc pointers, so I guess this just increments a reference count. My only regret is that we lost the method syntax, but I think this can be repaired by defining Expr with a struct instead of a type alias.

use std::rc::Rc;
use std::collections::HashMap;

#[derive(Debug)]
enum ExprNode {
    Integer(i32),
    Term(String),
    Plus(Expr, Expr),
    Set(Expr, Expr),
}

type Expr = Rc<ExprNode>;

type Env = HashMap<String, Expr>;

fn evaluate(e: &Expr, env: &mut Env) -> Expr {
    match **e {
        ExprNode::Plus(ref a, ref b) => {
            let a_ev = evaluate(a, env);
            let b_ev = evaluate(b, env);
            match (&*a_ev, &*b_ev) {
                (&ExprNode::Integer(x), &ExprNode::Integer(y)) => Rc::new(ExprNode::Integer(x + y)),
                _ => Rc::new(ExprNode::Plus(a_ev, b_ev)),
            }
        }
        ExprNode::Term(ref a) => env.get(a).unwrap().clone(),
        ExprNode::Set(ref a, ref b) => {
            let b_ev = evaluate(b, env);
            match **a {
                ExprNode::Term(ref x) => {
                    let x_value = env.get_mut(x).unwrap();
                    *x_value = b_ev;
                    x_value.clone()
                }
                _ => Rc::new(ExprNode::Set(evaluate(a, env), b_ev)),
            }
        }
        _ => e.clone(),
    }
}

fn main() {
    let e = Rc::new(ExprNode::Plus(
        Rc::new(ExprNode::Integer(9)),
        Rc::new(ExprNode::Integer(4)),
    ));
    let mut env = HashMap::new();

    println!("{:?}", evaluate(&e, &mut env));
}

Answer 2

This question is somewhat subjective, but here are some problems I see:

---

let a_ev = Rc::new(a.evaluate(env));
let b_ev = Rc::new(b.evaluate(env));
match (*a_ev, *b_ev) {
    (Expr::Integer(x), Expr::Integer(y)) => Expr::Integer(x+y),
    _ => Expr::Plus(a_ev,b_ev)
}

Here, you can't dereference a_ev and b_ev because *a_ev is owned by the Rc container holding it. You can fix this error by waiting until you actually need the values to be put in Rc containers to create them:

match (a.evaluate(env), b.evaluate(env)) {
    (Expr::Integer(x), Expr::Integer(y)) => Expr::Integer(x + y),
    (a_ev, b_ev) => Expr::Plus(Rc::new(a_ev), Rc::new(b_ev))
}

---

Expr::Term(ref a) => *env.get(&a).unwrap()

Here, the variable a has type &String, and so writing &a makes no sense -- it would be like a reference to a reference. That can be fixed by changing &a to a. Also, env.get(a).unwrap() is a reference to a Expr that is owned by the HashMap, so you can't dereference/move it. One solution to this problem would be to use a HashMap<String, Rc<Expr>> instead of a HashMap<String, Expr>. Another would be to simply clone the value:

Expr::Term(ref a) => env.get(a).unwrap().clone(),

In order to be able to clone the value, you must use a "derive" compiler directive to say that Expr implements that trait:

#[derive(Clone)]
enum Expr {   // ...

---

let b_ev = Rc::new(b.evaluate(env));
match **a {
    Expr::Term(x) => {
        let x_value = env.get_mut(&x).unwrap();
         *x_value = *b_ev;
         *b_ev
    },
    // ...

Here, you move *b_ev into the HashMap and then try to dereference/move it again by returning it. Also, like above, you have an extra &. Both of these issues can be solved in the same way as above:

let b_ev = b.evaluate(env);
match **a {
    Expr::Term(ref x) => {
        let x_value = env.get_mut(x).unwrap();
        *x_value = b_ev.clone();
        b_ev
    },
    // ...

---

otherwise => { let a_ev = Rc::new(a.evaluate(env)); // ...

Here, you are moving **a into otherwise while it is still owned by an Rc container. Since you don't use otherwise, the problem is easily fixed by replacing it with _:

_ => { // ...

---

otherwise => otherwise

You can't take a value that is owned by something else (*self is owned by something else) and return it by value. You can, however, clone it:

_ => self.clone()

---

Overall, the problem with your code is that it tries to duplicate data in a few places. As I said above, there are two ways of fixing it that I can think of: using Rc<Expr> everywhere instead of Expr, or using clone. Here is a fixed version of your code that compiles and uses clone:

use std::rc::Rc;
use std::collections::HashMap;

#[derive(Clone, Debug)]
enum Expr {
    Integer(i32),
    Term(String),
    Plus(Rc<Expr>, Rc<Expr>),
    Set(Rc<Expr>, Rc<Expr>),
}

impl Expr {
    fn evaluate(&self, env: &mut HashMap<String, Expr>) -> Expr {
        match *self {
            Expr::Plus(ref a, ref b) => {
                match (a.evaluate(env), b.evaluate(env)) {
                    (Expr::Integer(x), Expr::Integer(y)) => Expr::Integer(x + y),
                    (a_ev, b_ev) => Expr::Plus(Rc::new(a_ev), Rc::new(b_ev))
                }
            },
            Expr::Term(ref a) => env.get(a).unwrap().clone(),
            Expr::Set(ref a, ref b) => {
                let b_ev = b.evaluate(env);
                match **a {
                    Expr::Term(ref x) => {
                        let x_value = env.get_mut(x).unwrap();
                        *x_value = b_ev.clone();
                        b_ev
                    },
                    _ => {
                        let a_ev = a.evaluate(env);
                        Expr::Set(Rc::new(a_ev), Rc::new(b_ev))
                    }
                }
            }
            _ => self.clone()
        }
    }
}

fn main() {
    let e = Expr::Plus(Rc::new(Expr::Integer(9)), Rc::new(Expr::Integer(34)));
    let mut env = HashMap::new();

    println!("{:?}", e.evaluate(&mut env));
}

[playpen]