The expression problem refers to a challenge in programming languages. As described by Philip Wadler,
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). For the concrete example, we take expressions as the data type, begin with one case (constants) and one function (evaluators), then add one more construct (plus) and one more function (conversion to a string).
The expression problem is central in the design and implementation of DSLs.
One way of solving the expression problem in a purely functional language with kinds, and type classes (in other words, Haskell) is the data types à la carte technique.
Reynolds, John C. 1978. ‘User-Defined Types and Procedural Data Structures as Complementary Approaches to Data Abstraction’. In Programming Methodology, edited by David Gries, 309–17. New York, NY: Springer New York. https://doi.org/10.1007/978-1-4612-6315-9_22.
@incollection{reynolds_1978,
address = {New York, NY},
title = {User-{Defined} {Types} and {Procedural} {Data} {Structures} as {Complementary} {Approaches} to {Data} {Abstraction}},
booktitle = {Programming {Methodology}},
publisher = {Springer New York},
author = {Reynolds, John C.},
editor = {Gries, David},
year = {1978},
doi = {10.1007/978-1-4612-6315-9_22},
pages = {309--317}
}
It was first referred to as the expression problem in an email by Philip Wadler.
There is a reasonably rich Wikipedia page.