There is something in Rust that can help, though. You can define multiple impls for different bounds.

Supposing we started off with a trait for expression nodes:

  pub trait ExprNode { fn eval(&self, ctx: &Context) -> Value; }

Now, this library has gone out into the wild and been implemented, so we can't add new methods to ExprNode (ignoring default implementations, which don't help solve the problem). However, we can define a new trait:

  pub trait CanValidate { fn validate(&self) -> Result<(), ValidationError>; }

And now we get to what is (somewhat) unique to Rust: you can define different method sets based upon different generic bounds. Suppose we have a parent Expr struct which encapsulates the root node and the context:

  pub struct Expr<N> { root: N, ctx: Context }

We would probably already have this impl:

  impl<N: ExprNode> Expr<N> {
    pub fn eval(&self) -> Value { self.root.eval(&self.ctx) }
  }

Now we just need to add this impl:

  impl<N: CanValidate + ExprNode> Expr<N> {
    pub fn validate(&self) -> Result<(), ValidationError> { self.root.validate() }
  }

Of course, this is a trivial example (and doesn't even require the intersection bound), but it does illustrate how the expression problem can be solved. The problem this strategy creates, though, is combinatorial explosion. When we just have two traits, it's not a big deal. When we have several traits, and useful operations start to require various combinations of them (other than just Original + New), the number of impls and test cases starts to grow rapidly.