What is the 'expression problem'?

I have a rough idea about what this is but if someone has an explanation of the 'expression problem' that they think is succinct and intuitive I would love to hear it.

Watch this lecture.

The idea is that your program is a combination of a datatype and operations over it. The problem asks for an implementation that allows to add new cases of the type and new operations without the need for recompilation of the old modules and keeping static type safety(no casts or runtime type checks).

It's interesting to notice that in functional programming languages 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. This is one of the big conceptual differences between the two programming paradigms.

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).

There is also this article about solving the problem with Clojure, however the problem is presented in Java so it should make sense even if you don't know Clojure, especially with the help of the little charts.

which says: >Philip Wadler of Bell Labs coined the term Expression Problem in an unpublished paper that he circulated by email in 1998. As he put it, "The Expression Problem is a new name for an old problem. The goal is to define a datatype by cases, where one can add new cases to the datatype and new functions over the datatype, without recompiling existing code, and while retaining static type safety (e.g., no casts)."