The Expression Problem

The craft of programming is almost universally concerned with different types of data and operations/algorithms that act on this data.

Overview

  • Given a set of data types and a set of operations that act these types
  • Sometimes we want to add more operations and make sure they work properly on all types
  • Sometimes we want to add more types and make sure all operations work properly on them
    • But sometimes we need to add both and that is where the problem lies
    • Most mainstream languages do not provide good enough tools to add both new types and new operations to an existing system without having to modify the existing code
    • This is called the expression problem
    • This problem gives great insight into the fundamental differences between OOP, FP and concepts like interfaces and multiple dispatch

Example in OOP

class Example {
    interface Expr {
        String toString();
        double eval();
    }

    static class Constant implements Expr {
        double val;
        Constant(double val) {
            this.val = val;
        }
        public String toString() {
            return String.valueOf(val);
        }
        public double eval() {
            return val;
        }
    }

    static class BinaryPlus implements Expr {
        Expr lhs;
        Expr rhs;
        public BinaryPlus(Expr lhs, Expr rhs) {
            this.lhs = lhs;
            this.rhs = rhs;
        }
        public String toString() {
            return lhs + " + " + rhs;
        }
        public double eval() {
            return lhs.eval() + rhs.eval();
        }
    }
}
  • With this design we can:
    • Easily add new expression types (like Variable, FuncCall, …) by defining new classes that implement Expr
    • But what happens if we want to add new operations on expression trees
      • In addition to eval and toString we might to add typeCheck, compile, …
      • Here adding new operations is not as easy as adding new types because we would have to change the Expr interface
      • And as a consequence, we would have to change every existing expression type to implement the new operations

Example in FP

  • This problem also applies to functional programming
  • OOP collects functionality in objects (types)
  • In FP, we prefer types to be data containers and functionality (operations) are collected in functions that act on these types
  • Functional languages do not escape the expression problem; it just shows differently
type expr = Constant of float
          | BinaryPlus of expr * expr

let rec toString = function
  | Constant c -> string_of_float c
  | BinaryPlus (lhs, rhs) -> toString lhs ^ " + " ^ toString rhs

let rec eval = function
  | Constant value -> value
  | BinaryPlus (lhs, rhs) -> eval lhs +. eval rhs
  • With this design we can:
    • Easily add new operations like typecheck because we can just define a function typecheck that pattern matches on expr
    • But if we would like to add new expression types like FuncCall we have to modify all existing functions to handle this type in the pattern matching
  • So we hit the exact same problem as above but from a different angle

TODO: Solutions

References