一个简单的公式解释器

Question

为了理解 Rust，我正在尝试实现一个小公式解释器。表达式只能是整数、求和、变量 (Term) 或赋值 (Set)。然后我们可以评估一个表达式。由于没有关联值的符号可以出现在表达式中，因此它的计算会产生另一个表达式（不一定是整数）。

可以在散列中找到变量的值（如果有的话）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,
        }
    }
}

以上代码无法编译。每个match好像都借用了一个变量。此外，我认为我们不应该使用 String 类型，但我不明白为什么。

编译错误：

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

这个问题有点主观，但这里有一些我看到的问题：

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)
}

在这里，您不能取消引用 a_ev 和 b_ev，因为 *a_ev 属于持有它的 Rc 容器。您可以通过等到您真正需要将值放入 Rc 容器中来创建它们来修复此错误：

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()

在这里，变量 a 的类型是 &String，所以写成 &a 是没有意义的——它就像对引用的引用。这可以通过将 &a 更改为 a 来解决。此外，env.get(a).unwrap() 是对 HashMap 所拥有的 Expr 的引用，因此您不能 dereference/move 它。此问题的一种解决方案是使用 HashMap<String, Rc<Expr>> 而不是 HashMap<String, Expr>。另一种方法是简单地克隆值：

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

为了能够克隆该值，您必须使用 "derive" 编译器指令来表明 Expr 实现了该特征：

#[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
    },
    // ...

在这里，您将 *b_ev 移动到 HashMap 中，然后通过 return 尝试再次 dereference/move 它。另外，像上面一样，你有一个额外的 &。这两个问题都可以按照上面的方法解决：

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)); // ...

此处，您将 **a 移动到 otherwise 中，而它仍由 Rc 容器拥有。由于您不使用 otherwise，因此可以通过将其替换为 _:

轻松解决问题

_ => { // ...

otherwise => otherwise

您不能获取其他东西拥有的值（*self 被其他东西拥有）并且 return 它的值。但是，您可以克隆它：

_ => self.clone()

总的来说，您的代码存在的问题是它试图在一些地方复制数据。正如我上面所说，我可以想到两种修复它的方法：使用 Rc<Expr> everywhere 而不是 Expr，或者使用 clone .这是编译和使用 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]

Answer 2

这是我按照 Adrian 的建议将所有 ExprNode 替换为 Rc<ExprNode> 的第二个版本。唯一的克隆变量是 Rc 指针，所以我猜这只是增加了一个引用计数。我唯一的遗憾是我们丢失了方法语法，但我认为这可以通过使用 struct 而不是类型别名定义 Expr 来修复。

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));
}

一个简单的公式解释器

A simple formula interpreter

rust