神刀安全网

The Expression Problem and its solutions

A motivating example

As is my wont, my example comes from the world of compilers and interpreters. To my defense, this is also the example used in some of the seminal historic sources on the expression problem, as the historical perspective section below details.

Imagine we’re designing a simple expression evaluator. Following the standard interpreter design pattern , we have a tree structure consisting of expressions, with some operations we can do on such trees. In C++ we’d have an interface every node in the expression tree would have to implement:

class Expr { public:   virtual std::string ToString() const = 0;   virtual double Eval() const = 0; };

This interface shows that we currently have two operations we can do on expression trees – evaluate them and query for their string representations. A typical leaf node expression:

class Constant : public Expr { public:   Constant(double value) : value_(value) {}    std::string ToString() const {     std::ostringstream ss;     ss << value_;     return ss.str();   }    double Eval() const {     return value_;   }  private:   double value_; };

And a typical composite expression:

class BinaryPlus : public Expr { public:   BinaryPlus(const Expr& lhs, const Expr& rhs) : lhs_(lhs), rhs_(rhs) {}    std::string ToString() const {     return lhs_.ToString() + " + " + rhs_.ToString();   }    double Eval() const {     return lhs_.Eval() + rhs_.Eval();   }  private:   const Expr& lhs_;   const Expr& rhs_; };

Until now, it’s all fairly basic stuff. How extensible is this design? Let’s see… if we want to add new expression types ("variable reference", "function call" etc.), that’s pretty easy. We just define additional classes inheriting from Expr and implement the Expr interface ( ToString and Eval ).

However, what happens if we want to add new operations that can be applied to expression trees? Right now we have Eval and ToString , but we may want additional operations like "type check" or "serialize" or "compile to machine code" or whatever.

It turns out that adding new operations isn’t as easy as adding new types. We’d have to change the Expr interface, and consequently change every existing expression type to support the new method(s). If we don’t control the original code or it’s hard to change it for other reasons, we’re in trouble.

In other words, we’d have to violate the venerable open-closed principle , one of the main principles of object-oriented design , defined as:

software entities (classes, modules, functions, etc.) should be open for extension, but closed for modification

The problem we’re hitting here is called the expression problem , and the example above shows how it applies to object-oriented programming.

Interestingly, the expression problem bites functional programming languages as well. Let’s see how.

转载本站任何文章请注明:转载至神刀安全网,谢谢神刀安全网 » The Expression Problem and its solutions

分享到:更多 ()

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址