Expression problem

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

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

Philip Wadler coined the term[1] in response to a discussion with Rice University's Programming Languages Team (PLT):

The expression problem is a new name for an old problem.[2][3] 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).


The problem was first observed by John Reynolds in 1975.[2]

At ECOOP '98, Krishnamurthi et al.[4] presented a design pattern solution to the problem of simultaneously extending an expression-oriented programming language and its tool-set. They dubbed it the "expressivity problem" because they thought programming language designers could use the problem to demonstrate the expressive power of their creations. For PLT, the problem had shown up in the construction of DrScheme, now DrRacket, and they solved it[5] via a rediscovery of mixins.[6] To avoid using a programming language problem in a paper about programming languages, Krishnamurthi et al. used an old geometry programming problem to explain their pattern-oriented solution. In conversations with Felleisen and Krishnamurthi after the ECOOP presentation, Wadler understood the PL-centric nature of the problem and he pointed out that Krishnamurthi's solution used a cast to circumvent Java's type system. The discussion continued on the types mailing list, where Corky Cartwright (Rice) and Kim Bruce (Williams) showed how type systems for OO languages might eliminate this cast. In response Wadler formulated his essay and stated the challenge, "whether a language can solve the expression problem is a salient indicator of its capacity for expression." The label "expression problem" puns on expression = "how much can your language express" and expression = "the terms you are trying to represent are language expressions".

Others co-discovered variants of the expression problem around the same time as Rice University's PLT, in particular Thomas Kühne[7] in his dissertation, and Smaragdakis and Batory[8] in a parallel ECOOP 98 article.

Some follow-up work used the expression problem to showcase the power of programming language designs.[9][10]

The expression problem is also a fundamental problem in multi-dimensional Software Product Line design and in particular as an application or special case of FOSD Program Cubes.[citation needed]


There are various solutions to the expression problem. Each solution varies in the amount of code a user must write to implement them, and the language features they require.

See also[edit]


  1. ^ "The Expression Problem".
  2. ^ a b Reynolds, John C. (1975). "User-defined types and procedural data as complementary approaches to data abstraction.". New Directions in Algorithmic Languages. IFIP Working Group 2.1 on Algol. pp. 157–168.
  3. ^ "Object-Oriented Programming versus Abstract Data Types" (PDF).
  4. ^ "Synthesizing Object-Oriented and Functional Design to Promote Re-Use".
  5. ^ "Modular object-oriented programming with units and mixins".
  6. ^ Flatt, Matthew; Krishnamurthi, Shriram; Felleisen, Matthias (1998). "Classes and Mixins". Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on Principles of programming languages - POPL '98. pp. 171–183. doi:10.1145/268946.268961. ISBN 978-0897919791.
  7. ^ Kühne, Thomas (1999). A Functional Pattern System for Object-Oriented Design. Darmstadt: Verlag Dr. Kovac. ISBN 978-3-86064-770-7.
  8. ^ Smaragdakis, Yannis; Don Batory (1998). "Implementing Reusable Object-Oriented Components". Lecture Notes in Computer Science. 1445.
  9. ^ "Extensible Algebraic Datatypes with Defaults". 2001: 241–252. CiteSeerX Cite journal requires |journal= (help)
  10. ^ "Independently extensible solutions to the expression problem". 2005. CiteSeerX Cite journal requires |journal= (help)
  11. ^ Chambers, Craig; Leavens, Gary T. (November 1995). "Type Checking and Modules for Multi-Methods". ACM Trans. Program. Lang. Syst. (17): 805–843.
  12. ^ Clifton, Curtis; Leavens, Gary T.; Chambers, Craig; Millstein, Todd (2000). "MultiJava: Modular Open Classes and Symmetric Multiple Dispatch for Java" (PDF). Oopsla '00.
  13. ^ Wouter Swierstra (2008). "Data Types à La Carte". Journal of Functional Programming. 18 (4). Cambridge University Press. pp. 423–436. doi:10.1017/S0956796808006758. ISSN 0956-7968.
  14. ^ Wehr, Stefan; Thiemann, Peter (July 2011). "JavaGI: The Interaction of Type Classes with Interfaces and Inheritance". ACM Trans. Program. Lang. Syst. (33).
  15. ^ Carette, Jacques; Kiselyov, Oleg; Chung-chieh, Shan (2009). "Finally Tagless, Partially Evaluated: Tagless Staged Interpreters for Simpler Typed Languages" (PDF). J. Funct. Program.
  16. ^ Oliveira, Bruno C. d. S.; Cook, William R. (2012). "Extensibility for the Masses: Practical Extensibility with Object Algebras" (PDF). Ecoop '12.
  17. ^ Garrigue, Jacques (2000). "Code Reuse Through Polymorphic Variants". CiteSeerX Cite journal requires |journal= (help)

External links[edit]