Solving the expression problem in Rust

help
1

Hi,

I'm implementing a parser in Rust, and I'm having trouble figuring out a good representation for expressions.

The naïve solution seems to be:

enum Expr {
    ConstantExpr(f64),
    AddExpr(Box<Expr>, Box<Expr>),
    MulExpr(Box<Expr>, Box<Expr>),
}

impl Expr {
    fn evaluate(&self) -> f64 {
        use Expr::*;

        match self {
            ConstantExpr(v) => *v,
            AddExpr(expr1, expr2) => expr1.evaluate() + expr2.evaluate(),
            MulExpr(expr1, expr2) => expr1.evaluate() * expr2.evaluate(),
        }
    }
}

[full source]

This runs into the expression problem. It's simple to add additional operations—I can just create another function under impl Expr. But to add additional expressions (e.g. DivExpr), I need to update the match statement under all existing operations to support the additional expression (violating the open-closed principle).

It seems like the expression problem can be solved using traits—for example, I can define ConstantExpr as a struct, and implement the trait Eval:

trait Eval {
    fn eval(&self) -> f64;
}

struct ConstantExpr {
    v: f64
}

impl Eval for ConstantExpr {
    fn eval(&self) -> f64 {
        self.v
    }
}

This seems a lot better. I can add new operations by creating a new trait and implementing it for existing expressions. And I can add new expressions by creating a new struct an implementing existing traits for it. In both cases, no prior code needs to be modified.

But I'm not sure how to express the recursive structure of AddExpr and MultExpr, e.g.:

struct AddExpr {
    l: ... /* can be ConstantExpr, AddExpr, or MultExpr */,
    r: ... /* can be ConstantExpr, AddExpr, or MultExpr */,
}

This seems to suggest encapsulating ConstantExpr, AddExpr, MultExpr in a parent enum, e.g.:

enum Expr {
    Constant(ConstantExpr),
    Add(AddExpr),
    Mul(MulExpr),
}

trait Eval {
    fn eval(&self) -> f64;
}

struct ConstantExpr {
    v: f64,
}

impl Eval for ConstantExpr {
    fn eval(&self) -> f64 {
        self.v
    }
}

struct AddExpr {
    l: Box<Expr>,
    r: Box<Expr>,
}

impl Eval for AddExpr {
    fn eval(&self) -> f64 {
        use Expr::*;
        let lval = match &*self.l {
            Constant(expr) => expr.eval(),
            Add(expr) => expr.eval(),
            Mul(expr) => expr.eval(),
        };
        let rval = match &*self.r {
            Constant(expr) => expr.eval(),
            Add(expr) => expr.eval(),
            Mul(expr) => expr.eval(),
        };

        lval + rval
    }
}

/* MulExpr implementation */

fn interpret(expr: Expr) -> f64 {
    use Expr::*;
    match expr {
        Constant(expr) => expr.eval(),
        Add(expr) => expr.eval(),
        Mul(expr) => expr.eval(),
    }
}

[full source]

The resulting code is a lot more verbose, and I'm back to the original problem. Each eval trait implementation needs to match on the Expr enum, so implementing an additional expression means updating the match statement in every eval definition.

Ideally, I could just define some sort of sum type (e.g. Expr = ConstantExpr | AddExpr | MulExpr), but this doesn't seem to be possible in Rust.

Is there a clean solution to this problem?

2

This is exactly a definition of Rust enum, AFAIK.

3

You can store Box<dyn Eval> or Box<dyn Expression> where trait Expression: Eval.

Playground.

2 Likes
4

Oh, this is perfect! I didn't know traits could be used to abstract structs that implement other traits.

Thanks for the help.

5

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.