The Expression Problem and its Solutions Published: May 12, 2016 Tags: C & C++, Clojure, Multiple dispatch, Haskell --- Overview The expression problem addresses a fundamental challenge in software design: how to extend a program with new data types and new operations without modifying existing code. Most mainstream languages make it easy to add either new types or new operations, but not both simultaneously, leading to maintenance and extensibility issues. --- The Problem We have a set of data types and operations. Adding new types is easy in object-oriented languages. Adding new operations requires modifying existing code. Functional languages usually support easy extension of operations but struggle with adding new types. The problem shows fundamental differences between object-oriented programming (OOP) and functional programming (FP) and involves concepts like interfaces and multiple dispatch. --- Motivating Example: Expression Evaluator Object-Oriented Approach (C++) Base interface Expr defines operations: ToString() and Eval(). Concrete types like Constant and BinaryPlus inherit from Expr. Adding new types (e.g., variable reference, function call) is straightforward by subclassing Expr. Adding new operations (e.g., type check, serialization) requires modifying Expr and all subclasses, violating the open-closed principle. Functional Approach (Haskell) Algebraic data type Expr with constructors: Constant, BinaryPlus. Operations like stringify and evaluate are functions using pattern matching. Adding new operations is straightforward by defining new functions. Adding new types requires modifying all functions handling expressions; existing functions must be updated. --- Expression Problem Matrix | | Operation 1 | Operation 2 | ... | |----------|-------------|-------------|-----| | Type 1 | ✓ | ✓ | | | Type 2 | ✓ | ✓ | | | ... | | | | In OOP, rows (types) are easy to add; columns (operations) are hard. In FP, columns (operations) are easy to add; rows (types) are hard. --- Historical Perspective The term "Expression Problem" was coined by Philip Wadler in the 1990s. The problem has existed since early programming language design. Early works like Krishnamurthi, Felleisen, and Friedman's paper (1999) extensively discuss solutions. --- Visitor Pattern: Flipping the Matrix in OOP Visitor pattern allows adding new operations easily by defining new visitors. Expression classes accept visitors instead of implementing operations directly. Adding new types, however, means changing the visitor interface and all visitors. Thus, the problem flips: easier to add operations, harder to add types. --- Extending Visitor Pattern (C++) Uses multiple inheritance and virtual inheritance to extend visitor interfaces without changing existing visitors. Adding a new type like FunctionCall requires: Extending ExprVisitor to ExprVisitorWithFunctionCall. New expression class FunctionCall overrides Accept() method. New visitor EvaluatorWithFunctionCall handles the new type. Drawbacks: Requires dynamic_cast and complex C++ features. Existing visitors unaware of new types don’t work properly. Difficult to maintain when many types are added over time. --- Solving the Problem in Clojure Using Multimethods Types defined as records (e.g. Constant, BinaryPlus). Operations defined as multimethods dispatching on the type: evaluate stringify Adding new types: Define new record (e.g. FunctionCall) and new multimethod implementations. Adding new operations: Define new multimethod without modifying existing types. Benefits: No need to modify existing code. Supports independent extension of types and operations.