Expression problem: Difference between revisions

Revision as of 04:49, 22 July 2022

Revision as of 13:59, 26 September 2022

Line 1:

The '''expression problem''' is a challenge problem in [[programming languages]] 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). It exposed deficiencies in [[programming paradigms]] and [[programming languages]], and it is still not definitively solved, although there are many proposed solutions.

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

It exposed deficiencies in [[programming paradigms]] and [[programming languages]], and it is still not definitively solved, although there are many proposed solutions.

== History ==

Line 21 ⟶ 19:

| url= https://www.cs.tufts.edu/~nr/cs257/archive/john-reynolds/procedural-data-structures.pdf

}}

</ref> Reynolds discussed two forms of Data Abstraction: User-defined Types, which are now known as [[Abstract data types|Abstract Data Types]] (ADTs) (not to be confused with [[Algebraic data types|Algebraic Data Types]]), and Procedural Data Structures, which are now understood as a primitive form of Objects with only one method. He argued that they are complementary, in that User-defined Types could be extended with new behaviors, and Procedural Data Structures could be extended with new representations. He also discussed related work going back to 1967. However, Reynold's conclusions based on this early analysis turned out to be completely wrong: he wrote that adding a second method to an object "is more a tour de force than a specimen of clear programming," which completely missed the Object-Oriented paradigm and its great success. He also believed the two forms of data abstraction "are inherently distinct and complementary."

he wrote that adding a second method to an object "is more a tour de force than a specimen of

clear programming," which completely missed the Object-Oriented paradigm and its

great success. He also believed

the two forms of data abstraction "are inherently distinct and complementary."

Fifteen years later in 1990, [[William Cook (computer scientist)|William Cook]]<ref name="CookOOPvsADT">

Line 75 ⟶ 69:

| isbn= 978-0897919791

| s2cid= 5815257

}}</ref> 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".

"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<ref name="K">

Line 101 ⟶ 94:

}}</ref>

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 Programprogram Cubescubes#Applications|FOSD Program Cubes]].{{Citation needed|date=January 2016}}

== Solutions ==

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.

Line 292 ⟶ 285:

Notice that in {{code|ExampleThree.Print()}} we are printing an expression that was already compiled in {{code|ExampleTwo}}, we did not need to modify any existing code. Notice also that this is still strongly typed, we do not need reflection or casting. If we would replace the {{code|PrintFactory()}} with the {{code|ExpFactory()}} in the {{code|ExampleThree.Print()}} we would get a compilation error since the {{code|.Print()}} method does not exist in that context.

== See also ==

* [[FOSD Programprogram Cubescubes#Applications|Applications of FOSD Programprogram Cubescubes]]

* [[Generic programming]]

* [[POPLmark challenge]]

== References ==

{{Reflist|2}}

== External links ==

*[http://homepages.inf.ed.ac.uk/wadler/papers/expression/expression.txt The Expression Problem] by [[Philip Wadler]].

*[http://www.uni-koblenz.de/~laemmel/paradigms1011/resources/xproblem.html Lecture: The Expression Problem] by [[Ralf Lämmell]].

*[http://channel9.msdn.com/Shows/Going+Deep/C9-Lectures-Dr-Ralf-Laemmel-Advanced-Functional-Programming-The-Expression-Problem C9 Lectures: Dr. Ralf Lämmel - Advanced Functional Programming - The Expression Problem] at [[Channel 9 (discussion forum)|Channel 9]],.{{dead link|date=September 2022}}

*[http://lampwww.epfl.ch/~odersky/papers/ExpressionProblem.html Independently Extensible Solutions to the Expression Problem, Matthias Zenger and Martin Odersky, EPFL Lausanne].

[[Category:Programming language design]]