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(),
}
}
}
```

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(),
}
}
```

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?