PLS Lab

The Expression Problem

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.

Solutions

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.

References

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}
}