Expression problem: Difference between revisions

Revision as of 21:43, 4 June 2025

Latest revision as of 16:27, 27 July 2025

(5 intermediate revisions by 3 users not shown)

Line 1:

{{Short description|Data abstraction problem in programming languages}}

The '''expression problem''' is a challenging problem in [[programming language]]s that concerns the extensibility and modularity of statically typed data abstractions. The goal is to define a data abstraction that is extensible both in its representations and its behaviors, where one can add new representations and new behaviors to the data abstraction, without recompiling existing code, and while retaining static type safety (e.g., no casts). The statement of the problem exposes deficiencies in [[programming paradigm]]s and [[programming language]]s,. andPhilip {{as of|2023|lc=y}} is still considered unsolvedWadler,{{citation needed|date=Octoberone 2023}}of althoughthe there are many proposed solutions.{{citation needed|reason=feels misleading as if there is some buzzco-authors of research interest or activityHaskell, whereashas in fact most oforiginated the references are from 30 years ago|date=October 2023}}term.

== History ==

Line 75:

Some follow-up work used the expression problem to showcase the power of programming language designs.<ref name="Scala0">

{{cite journalbook

| titlechapter=Extensible Algebraic Datatypes with Defaults

| first1=Matthias | last1=Zenger

| first2=Martin | last2=Odersky

| title=Proceedings of the sixth ACM SIGPLAN international conference on Functional programming | pages=241–252

| pages=241–252

| citeseerx=10.1.1.28.6778

| year=2001

| doi=10.1145/507635.507665

| isbn=1-58113-415-0 }}</ref><ref name="Scala">

{{cite webbook

| titlechapter=Independently extensible solutions to the expression problem

| chapter-url=https://homepages.inf.ed.ac.uk/wadler/fool/program/final/10/10_Paper.pdf

| first1=Matthias | last1=Zenger

| first2=Martin | last2=Odersky

| title=FOOL 2005

| series=Foundations of Object-Oriented Languages (FOOL)

| publisher=ACM SIGPLAN

| citeseerx=10.1.1.107.4449

| year=2005

Line 98 ⟶ 100:

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.

* [[Multiple dispatch]]<ref name="Chambers & Leavens, Multi-Methods">{{cite journal|last1=Chambers|first1=Craig|last2=Leavens|first2=Gary T.|title=Type Checking and Modules for Multi-Methods|journal= ACM Trans.Transactions on Programming Program.Languages Lang.and Syst.Systems|date=November 1995|volume=17 |issue=6|pages=805–843|doi=10.1145/218570.218571 |url=http://lib.dr.iastate.edu/cgi/viewcontent.cgi?article=1036&context=cs_techreports|doi-access=free}}</ref>

* {{section link|Ruby syntax|Open classes}}<ref name="Clifton et. al., MultiJava Open Classes">{{cite book|last1=Clifton|first1=Curtis|last2=Leavens|first2=Gary T.|last3=Chambers|first3=Craig|last4=Millstein|first4=Todd|chapter=MultiJava: Modular open classes and symmetric multiple dispatch for Java |title=Proceedings of the 15th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications |journalchapter=OopslaMultiJava: Modular open classes and symmetric multiple dispatch for Java '00|date=2000|pages=130–145 |doi=10.1145/353171.353181 |isbn=978-1-58113-200-7 |s2cid=7879645 |chapter-url=http://people.csail.mit.edu/dnj/teaching/6898/papers/multijava.pdf}}</ref>

* [[Coproduct]]s of [[functor]]s<ref>{{cite journal

|author = Wouter Swierstra

Line 111 ⟶ 113:

|publisher = Cambridge University Press

|doi = 10.1017/S0956796808006758

|doi-broken-date = 4 June 2025

|s2cid = 21038598

|doi-access = free

}}</ref>

* [[Type class]]es<ref name="Wehr & Thiemann, JavaGI Type Classes">{{cite journal|last1=Wehr|first1=Stefan|last2=Thiemann|first2=Peter|title= JavaGI: The Interaction of Type Classes with Interfaces and Inheritance|journal= ACM Trans.Transactions Program.on Lang.Programming Syst.Languages and Systems|date=July 2011|volume=33 |issue=4|pages=12:1–12:83 1–83|doi=10.1145/1985342.1985343 |s2cid=13174506 |url=http://www.stefanwehr.de/publications/WehrThiemann2011TOPLAS.html|doi-access=free}}</ref>

* Tagless-final<ref name="Carette et al.,

Finally tagless, partially evaluated: Tagless staged interpreters for simpler typed languages">{{cite journal|last1=Carette|first1=Jacques|last2=Kiselyov|first2=Oleg|last3=Chung-chieh|first3=Shan|title=Finally Tagless, Partially Evaluated: Tagless Staged Interpreters for Simpler Typed Languages|journal=J. Funct. Program.|date=2009|volume=19 |issue=5 |pages=509–543 |doi=10.1017/S0956796809007205 |s2cid=6054319 |url=http://okmij.org/ftp/tagless-final/JFP.pdf}}</ref> / Object algebras<ref name="Oliveira & Cook, Object Algebras">{{cite journal|last1=Oliveira|first1=Bruno C. d. S.|last2=Cook|first2=William R.|title=Extensibility for the Masses: Practical Extensibility with Object Algebras|journal=Ecoop '12|date=2012|url=http://www.cs.utexas.edu/~wcook/Drafts/2012/ecoop2012.pdf}}</ref>

* Polymorphic Variants<ref name="Code Reuse Through Polymorphic Variants">{{cite journalbook|last1=Garrigue|first1=Jacques|titlechapter=Code Reuse Through Polymorphic Variants|chapter-url=https://www.math.nagoya-u.ac.jp/~garrigue/papers/variant-reuse.pdf|title=Workshop on Foundations of Software Engineering. Sasaguri, Japan, November 2000 |citeseerx=10.1.1.128.7169|year=2000}}</ref>

== Example ==

Line 193 ⟶ 194:

</syntaxhighlight>

However, if we wish to add a new function over the type (a new method in C# terminology), for example to pretty print an expression, we have to change the {{code|IEvalExp}} interface and then modify all the classes that implement the interface. Another possibility is to create a new interface that extends the {{code|IEvalExp}} interface and then create sub-types for {{code|Lit}}, {{code|Add}} and {{code|Mult}} classes, but the expression returned in {{code|ExampleOne.AddOneAndTwo()}} has already been compiled so we will not be able to use the new function over the old type. The problem is reversed in functional programming languages like [[F Sharp (programming language)|F#]] where it is easy to add a function over a given type, but extending or adding types is difficult.

=== Problem solution using object algebra ===