The expression problem is a 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). The statement of the problem exposes deficiencies in programming paradigms and programming languages. Philip Wadler, one of the co-authors of Haskell, has originated the term.
interfaceIEvalExp
{
intEval();
}
classLit:IEvalExp
{
internalLit(intn)
{
N=n;
}
internalintN{get;}
publicintEval()
{
returnN;
}
}
classAdd:IEvalExp
{
internalAdd(IEvalExpleft,IEvalExpright)
{
Left=left;
Right=right;
}
internalIEvalExpLeft{get;}
internalIEvalExpRight{get;}
publicintEval()
{
returnLeft.Eval()+Right.Eval();
}
}
staticclassExampleOne
{
staticIEvalExpAddOneAndTwo()=>newAdd(newLit(1),newLit(2));
staticintEvaluateTheSumOfOneAndTwo()=>AddOneAndTwo().Eval();
}
Using this library we can express the arithmetic expression .Eval(). Now imagine that we wish to extend this library, adding a new type is easy because we are working with an Object-oriented programming language. For example, we might create the following class:
IEvalExp interface and then create sub-types for Mult classes, but the expression returned in ExampleTwo.AddOneToTwo() using the "},"parts":[{"template":{"target":{"wt":"code","href":"./Template:Code"},"params":{"1":{"wt":"ExpAlgebra<T>"}},"i":0}}]}'>ExpAlgebra<T> interface instead of directly from the types. We can now add a function by extending the "},"parts":[{"template":{"target":{"wt":"code","href":"./Template:Code"},"params":{"1":{"wt":"ExpAlgebra<T>"}},"i":0}}]}'>ExpAlgebra<T> interface, we will add functionality to print the expression:
\n{\n public IPrintExp Add(IPrintExp left, IPrintExp right)\n {\n return new PrintableAdd(left, right);\n }\n\n public new IPrintExp Lit(int n)\n {\n return new PrintableLit(n);\n }\n}\n\nstatic class ExampleThree\n{\n internal static int Evaluate() => ExampleTwo<IPrintExp>.AddOneToTwo(new PrintFactory()).Eval();\n internal static string Print() => ExampleTwo<IPrintExp>.AddOneToTwo(new PrintFactory()).Print();\n}\n"}}'>interfaceIPrintExp:IEvalExp
{
stringPrint();
}
classPrintableLit:Lit,IPrintExp
{
internalPrintableLit(intn):base(n)
{
N=n;
}
internalintN{get;}
publicstringPrint()
{
returnN.ToString();
}
}
classPrintableAdd:Add,IPrintExp
{
internalPrintableAdd(IPrintExpleft,IPrintExpright):base(left,right)
{
Left=left;
Right=right;
}
internalnewIPrintExpLeft{get;}
internalnewIPrintExpRight{get;}
publicstringPrint()
{
returnLeft.Print()+" + "+Right.Print();
}
}
classPrintFactory:ExpFactory,ExpAlgebra<IPrintExp>
{
publicIPrintExpAdd(IPrintExpleft,IPrintExpright)
{
returnnewPrintableAdd(left,right);
}
publicnewIPrintExpLit(intn)
{
returnnewPrintableLit(n);
}
}
staticclassExampleThree
{
internalstaticintEvaluate()=>ExampleTwo<IPrintExp>.AddOneToTwo(newPrintFactory()).Eval();
internalstaticstringPrint()=>ExampleTwo<IPrintExp>.AddOneToTwo(newPrintFactory()).Print();
}
Notice that in PrintFactory() with the .Print() method does not exist in that context.
Cook, William (1990).
"Object-Oriented Programming versus Abstract Data Types". In Bakker, J.W. de; Roever, W.P. de; Rozenberg, G. (eds.).
Foundations of Object-Oriented Languages (FOOL), REX School/Workshop. Lecture Notes in Computer Science. Vol.
489. Noordwijkerhout, The Netherlands: Springer Berlin Heidelberg. pp.
151–178.
doi:
10.1007/BFb0019443.
ISBN 978-3-540-46450-1.
↑
Cook, William (1989). A Denotational Semantics of Inheritance (PDF) (PhD). Brown University.
↑
Smaragdakis, Yannis; Don Batory (1998). Implementing Reusable Object-Oriented Components. Lecture Notes in Computer Science. Vol. 1445.
↑
Chambers, Craig; Leavens, Gary T. (November 1995). "Type Checking and Modules for Multi-Methods". ACM Transactions on Programming Languages and Systems. 17 (6): 805–843. doi:10.1145/218570.218571.
↑ Wehr, Stefan; Thiemann, Peter (July 2011). "JavaGI: The Interaction of Type Classes with Interfaces and Inheritance". ACM Transactions on Programming Languages and Systems. 33 (4): 1–83. doi:10.1145/1985342.1985343. S2CID 13174506.
↑