Programing: the Expression Problem

By Xah Lee. Date: . Last updated: .

In programing language design, you have something called the “Expression Problem”.

The “expression problem” isn't really a problem in computer science. It is a problem as in: “Houston, we have a problem.”

Wikipedia Expression problem has a excellent description, quote:

The Expression Problem is a term used in discussing strengths and weaknesses of various programming paradigms and programming languages.

the “Expression Problem” is best explained here: but, better is to understand it as the general case of “Cross Cutting Concerns”, explained here:

In FunctionalProgramming, you would describe a data type such as:

 type Shape = Square of side
            | Circle of radius

Then you would define a single area function:

 define area = fun x -> case x of
    Square of side => (side * side)
  | Circle of radius => (3.14 *  radius * radius)

In ObjectOrientedProgramming, you would describe the data type such as:

 class Shape <: Object
   virtual fun area : () -> double

 class Square <: Shape
   side : double
   area() =  side * side

 class Circle <: Shape
   radius : double
   area() = 3.14 * radius * radius

The 'ExpressionProblem' manifests when you wish to 'extend' the set of objects or functions.

    If you want to add a 'triangle' shape:
        the ObjectOrientedProgramming approach makes it easy (because you can simply create a new class)
        but FunctionalProgramming makes it difficult (because you'll need to edit every function that accepts a 'Shape' parameter, including 'area')
    OTOH, if you want add a 'perimeter' function:
        FunctionalProgramming makes it easy (simply add a new function 'perimeter')
        while ObjectOrientedProgramming makes it difficult (because you'll need to edit every class to add 'perimeter()' to the interface).

And that is the heart of the ExpressionProblem.

The ExpressionProblem is a specific example of a larger class of problems known generally as CrossCuttingConcerns - in this particular case the relevant 'concerns' being 'the set of shapes' and 'the features of shapes'. Many languages include designs to help solve the ExpressionProblem. Open functions (functions that can be extended with new pattern-matches), open data-types (data types that can be extended with new patterns), and MultiMethods ('open' specialized polymorphic functions with 'open' set of classes), and PredicateDispatching, are all viable approaches.

More general solutions to SeparationOfConcerns will also apply (e.g. IBM's HyperSpaces motivating example specifically targets this problem).

in functional programming language, it's easy to add new operations, but hard to add cases to the datatype. While in an OO language it's the other way round.

and even more generally, it's a problem of multi-hierachy or multi-organization. The problem is that, one fixed structure (or focus/aspect) of code that assumes situation X, cannot deal well with situation Y without refactored or rewritten.

So, the specific case of “Expression Problem” is really not a problem in programing in any math or concrete sense. (That is, for example, sorting, concurrency, efficiency, are real problems that can be formalized as formal logic.) It's like saying, i want white shoes and i also want black shoes

The idea behind the problem is that text is 1 dimensional. Even if you have lines and columns, you generally read it, word by word, line by line. So does the compiler.

And you try to represent some kind of 2 or more dimensional data in it. For example a table in row-mayor order looks like this:

((A, B, C), (D, E, F), (G, H, I))

In this representation, it's quite easy to add a new row at the end, without touching the rest:

((A, B, C), (D, E, F), (G, H, I), (J, K, L))

But adding columns is problematic a bit, you need to touch it 4 different places:

((A, B, C, M), (D, E, F, N), (G, H, I, O), (J, K, L, P))

You generally run into this problem in practice, when dealing with abstract classes: it's quite easy to add a new subtype as a new module, but when you add a new abstract method, you'll need to touch all the modules and add it; you need to do the same thing in many places. Normally you make abstractions to protect against these repetitive things.

There is no solution to this problem as long as you use 1D representation.

The solution to this problem would be an editor that can let you edit these table like things like a real table and not like text (in an Excel like view, where you can conveniently add new columns and rows).
share|improve this answer

answered Mar 4 at 18:55

If you have a question, put $5 at patreon and message me.