The craft of programming is almost universally concerned with different types of data and operations/algorithms that act on this data . Therefore, it's hardly surprising that designing abstractions for data types and operations has been on the mind of software engineers and programming-language designers since... forever.
Yet I've only recently encountered a name for a software design problem which I ran into multiple times in my career. It's a problem so fundamental that I was quite surprised that I haven't seen it named before. Here is a quick problem statement.
Imagine that we have a set of data types and a set of operations that act on these types. Sometimes we need to add more operations and make sure they work properly on all types; sometimes we need to add more types and make sure all operations work properly on them. Sometimes, however, we need to add both - and herein lies the problem. Most of the mainstream programming languages don't provide good tools to add both new types and new operations to an existing system without having to change existing code. This is called the "expression problem". Studying the problem and its possible solutions gives great insight into the fundamental differences between object-oriented and functional programming and well as concepts like interfaces and multiple dispatch.
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 in functional programming Update 2018-02-05: a new post discusses the problem and its solutions in Haskell in more depth. Object-oriented approaches tend to collect functionality in objects (types). Functional languages cut the cake from a different angle, usually preferring types as thin data containers, collecting most functionality in functions (operations) that act upon them. Functional languages don't escape the expression problem - it just manifests there in a different way. To demonstrate this, let's see how the expression evaluator / stringifier looks in Haskell. Haskell is a good poster child for functional programming since its pattern matching on types makes such code especially succinct: module Expressions where data Expr = Constant Double | BinaryPlus Expr Expr stringify :: Expr -> String stringify ( Constant c ) = show c stringify ( BinaryPlus lhs rhs ) = stringify lhs ++ " + " ++ stringify rhs evaluate :: Expr -> Double evaluate ( Constant c ) = c evaluate ( BinaryPlus lhs rhs ) = evaluate lhs + evaluate rhs Now let's say we want to add a new operation - type checking. We simply have to add a new function typecheck and define how it behaves for all known kinds of expressions. No need to modify existing code. On the other hand, if we want to add a new type (like "function call"), we get into trouble. We now have to modify all existing functions to handle this new type. So we hit exactly the same problem, albeit from a different angle.
The expression problem matrix A visual representation of the expression problem can be helpful to appreciate how it applies to OOP and FP in different ways, and how a potential solution would look. The following 2-D table (a "matrix") has types in its rows and operations in its columns. A matrix cell row, col is checked when the operation col is implemented for type row : In object-oriented languages, it's easy to add new types but difficult to add new operations: Whereas in functional languages, it's easy to add new operations but difficult to add new types:
A historical perspective The expression problem isn't new, and has likely been with us since the early days; it pops its head as soon as programs reach some not-too-high level of complexity. It's fairly certain that the name expression problem comes from an email sent by Philip Wadler to a mailing list deailing with adding generics to Java (this was back in the 1990s). In that email, Wadler points to the paper "Synthesizing Object-Oriented and Functional Design to Promote Re-Use" by Krishnamurthi, Felleisen and Friedman as an earlier work describing the problem and proposed solutions. This is a great paper and I highly recommend reading it. Krishnamurthi et.al., in their references, point to papers from as early as 1975 describing variations of the problem in Algol.
Flipping the matrix with the visitor pattern So far the article has focused on the expression problem, and I hope it's clear by now. However, the title also has the word solution in it, so let's turn to that. It's possible to kinda solve (read on to understand why I say "kinda") the expression problem in object-oriented languages; first, we have to look at how we can flip the problem on its side using the visitor pattern. The visitor pattern is very common for this kind of problems, and for a good reason. It lets us reformulate our code in a way that makes it easier to change in some dimensions (though harder in others). For the C++ sample shown above, rewriting it using the visitor pattern means adding a new "visitor" interface: class ExprVisitor { public : virtual void VisitConstant ( const Constant & c ) = 0 ; virtual void VisitBinaryPlus ( const BinaryPlus & bp ) = 0 ; }; And changing the Expr interface to be: class Expr { public : virtual void Accept ( ExprVisitor * visitor ) const = 0 ; }; Now expression types defer the actual computation to the visitor, as follows: class Constant : public Expr { public : Constant ( double value ) : value_ ( value ) {} void Accept ( ExprVisitor * visitor ) const { visitor -> VisitConstant ( * this ); } double GetValue () const { return value_ ; } private : double value_ ; }; // ... similarly, BinaryPlus would have // // void Accept(ExprVisitor* visitor) const { // visitor->VisitBinaryPlus(*this); // } // // ... etc. A sample visitor for evaluation would be : class Evaluator : public ExprVisitor { public : double GetValueForExpr ( const Expr & e ) { return value_map_ [ & e ]; } void VisitConstant ( const Constant & c ) { value_map_ [ & c ] = c . GetValue (); } void VisitBinaryPlus ( const BinaryPlus & bp ) { bp . GetLhs (). Accept ( this ); bp . GetRhs (). Accept ( this ); value_map_ [ & bp ] = value_map_ [ & ( bp . GetLhs ())] + value_map_ [ & ( bp . GetRhs ())]; } private : std :: map < const Expr * , double > value_map_ ; }; It should be obvious that for a given set of data types, adding new visitors is easy and doesn't require modifying any other code. On the other hand, adding new types is problematic since it means we have to update the ExprVisitor interface with a new abstract method, and consequently update all the visitors to implement it. So it seems that we've just turned the expression problem on its side: we're using an OOP language, but now it's hard to add types and easy to add ops, just like in the functional approach. I find it extremely interesting that we can do this. In my eyes this highlights the power of different abstractions and paradigms, and how they enable us to rethink a problem in a completely different light. So we haven't solved anything yet; we've just changed the nature of the problem we're facing. Worry not - this is just a stepping stone to an actual solution.
Extending the visitor pattern The following is code excerpts from a C++ solution that follows the extended visitor pattern proposed by Krishnamurthi et. al. in their paper; I strongly suggest reading the paper (particularly section 3) if you want to understand this code on a deep level. A complete code sample in C++ that compiles and runs is available here. Adding new visitors (ops) with the visitor pattern is easy. Our challenge is to add a new type without upheaving too much existing code. Let's see how it's done. One small design change that we should make to the original visitor pattern is use virtual inheritance for Evaluator , for reasons that will soon become obvious: class Evaluator : virtual public ExprVisitor { // .. the rest is the same }; Now we're going to add a new type - FunctionCall : // This is the new ("extended") expression we're adding. class FunctionCall : public Expr { public : FunctionCall ( const std :: string & name , const Expr & argument ) : name_ ( name ), argument_ ( argument ) {} void Accept ( ExprVisitor * visitor ) const { ExprVisitorWithFunctionCall * v = dynamic_cast < ExprVisitorWithFunctionCall *> ( visitor ); if ( v == nullptr ) { std :: cerr << "Fatal: visitor is not ExprVisitorWithFunctionCall
" ; exit ( 1 ); } v -> VisitFunctionCall ( * this ); } private : std :: string name_ ; const Expr & argument_ ; }; Since we don't want to modify the existing visitors, we create a new one, extending Evaluator for function calls. But first, we need to extend the ExprVisitor interface to support the new type: class ExprVisitorWithFunctionCall : virtual public ExprVisitor { public : virtual void VisitFunctionCall ( const FunctionCall & fc ) = 0 ; }; Finally, we write the new evaluator, which extends Evaluator and supports the new type: class EvaluatorWithFunctionCall : public ExprVisitorWithFunctionCall , public Evaluator { public : void VisitFunctionCall ( const FunctionCall & fc ) { std :: cout << "Visiting FunctionCall!!
... continue reading