Expression problem: Difference between revisions

Revision as of 06:30, 29 May 2021

Revision as of 03:25, 26 June 2021

Line 1:

The '''expression problem''' is achallenge term usedproblem in discussing[[programming strengthslanguages]] that concerns the extensibility and weaknessesmodularity of variousstatically [[programmingtyped paradigms]]data andabstractions. [[programming languages]].

}}</ref> The goal is to define a datatypedata byabstraction casesthat is extensible both in its representations and its behaviors, where one can add new cases to the datatyperepresentations and new functionsbehaviors overto the datatypedata abstraction, without recompiling existing code, and while retaining static type safety (e.g., no casts).</blockquote>

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

== History ==

[[Philip Wadler]] coinedformulated the termchallenge and named it "The Expression Problem"<ref name="WadlerPost">{{cite web

| title=The Expression Problem

| url=http://homepages.inf.ed.ac.uk/wadler/papers/expression/expression.txt

}}</ref> in response to a discussion with Rice University's [[Racket (programming language)#Development|''Programming Languages Team'' (PLT)]]:.

He also cited three sources that defined the context for his challenge:

<blockquote>The expression problem iswas afirst newobserved nameby for[[John anC. oldReynolds|John problemReynolds]] in 1975.<ref name="Reynolds">

{{cite book

| chapter= User-defined typesTypes and proceduralProcedural dataData Structures as complementary approaches to dataData abstractionAbstraction.

| title= New Directions in Algorithmic Languages

| year= 1975

Line 15 ⟶ 19:

| publisher= IFIP Working Group 2.1 on Algol

| pages= 157-168

| 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 (ADTS) (not to be confused with *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. His conclusions based on this early analysis turned out to be completely wrong:

</ref><ref name="Cook">

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

{{cite web

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

| title=Object-Oriented Programming versus Abstract Data Types

great success. He also believed

| url=http://www.cs.utexas.edu/users/wcook/papers/OOPvsADT/CookOOPvsADT90.pdf

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

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

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

== History ==

{{cite webbook

The problem was first observed by [[John C. Reynolds|John Reynolds]] in 1975.<ref name="Reynolds" />

| last= Cook |first= William

| author-link= William Cook (computer scientist)

| date= 1990

| editor-last1= Bakker | editor-first1= J.W. de

| editor-last2= Roever | editor-first2= W.P. de

| editor-last3= Rozenberg | editor-first3= G.

| title= Foundations of Object-Oriented Languages (FOOL), REX School/Workshop

| ___location= Noordwijkerhout, The Netherlands

| publisher= Springer Berlin Heidelberg |pages=151-178

| titlechapter= Object-Oriented Programming versus Abstract Data Types

| chapter-url= https://link.springer.com/chapter/10.1007/BFb0019443

| isbn= 978-3-540-46450-1}}

</ref>

applied Reynold's work in the context of Objects and Abstract Data Types, which had both grown extensively. Cook identified the matrix of representations and behaviors that are implicit in a Data Abstraction, and discussed how ADTs are based on the behavioral axis, while Objects are based on representations.

At ECOOP '98, Krishnamurthi et al.<ref name="Synth">

Line 33 ⟶ 52:

| title= Modular object-oriented programming with units and mixins

| url= http://dl.acm.org/citation.cfm?id=289432

}}</ref> via a rediscovery of [[Mixin|mixins]].<ref name="FKFMixins">{{cite thesis |type= PhD

| last= Cook | first= William | date= 1989

| title= A Denotational Semantics of Inheritance | publisher= Brown University

| url=http https://www.cs.utexas.edu/users/~wcook/papers/OOPvsADTthesis/CookOOPvsADT90cook89.pdf }}</ref><ref name="FKF">

{{cite book

| chapter= Classes and Mixins

Line 47 ⟶ 69:

| first3= Matthias

| isbn= 978-0897919791

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

Line 57 ⟶ 79:

{{cite journal

| title=Extensible Algebraic Datatypes with Defaults

| first1=Matthias | last1=Zenger

| first2=Martin | last2=Odersky

| pages=241–252

| citeseerx=10.1.1.28.6778

| year=2001

}}</ref><ref name="Scala">

{{cite journalweb

| title=Independently extensible solutions to the expression problem

| first1=Matthias | last1=Zenger

| first2=Martin | last2=Odersky

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

| publisher=ACM SIGPLAN

| citeseerx=10.1.1.107.4449

| year=2005