Expression problem

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.

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. At ECOOP '98, Shriram Krishnamurthi et al. 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 via a rediscovery of mixins. 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 in his dissertation, and Smaragdakis and Batory in a parallel ECOOP 98 article. Some follow-up work used the expression problem to showcase the power of programming language designs. 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. interface IEvalExp { int Eval(); } class Lit : IEvalExp { internal Lit(int n) { N = n; } internal int N { get; } public int Eval() { return N; } } class Add : IEvalExp { internal Add(IEvalExp left, IEvalExp right) { Left = left; Right = right; } internal IEvalExp Left { get; } internal IEvalExp Right { get; } public int Eval() { return Left.Eval() + Right.Eval(); } } static class ExampleOne { static IEvalExp AddOneAndTwo() => new Add(new Lit(1), new Lit(2)); static int EvaluateTheSumOfOneAndTwo() => AddOneAndTwo().Eval(); } Using this library we can express the arithmetic expression as we did in and can evaluate the expression by calling . 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: class Mult : IEvalExp { internal Mult(IEvalExp left, IEvalExp right) { Left = left; Right = right; } internal IEvalExp Left { get; } internal IEvalExp Right { get; } public int Eval() { return Left.Eval() * Right.Eval(); } } 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 interface and then modify all the classes that implement the interface. Another possibility is to create a new interface that extends the interface and then create sub-types for , and classes, but the expression returned in 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# where it is easy to add a function over a given type, but extending or adding types is difficult. interface ExpAlgebra { T Lit(int n); T Add(T left, T right); } class ExpFactory : ExpAlgebra { public IEvalExp Lit(int n) { return new Lit(n); } public IEvalExp Add(IEvalExp left, IEvalExp right) { return new Add(left, right); } } static class ExampleTwo { public static T AddOneToTwo(ExpAlgebra ae) => ae.Add(ae.Lit(1), ae.Lit(2)); } We use the same implementation as in the first code example but now add a new interface containing the functions over the type as well as a factory for the algebra. Notice that we now generate the expression in using the interface instead of directly from the types. We can now add a function by extending the interface, we will add functionality to print the expression: interface IPrintExp : IEvalExp { string Print(); } class PrintableLit : Lit, IPrintExp { internal PrintableLit(int n) : base(n) { N = n; } internal int N { get; } public string Print() { return N.ToString(); } } class PrintableAdd : Add, IPrintExp { internal PrintableAdd(IPrintExp left, IPrintExp right) : base(left, right) { Left = left; Right = right; } internal new IPrintExp Left { get; } internal new IPrintExp Right { get; } public string Print() { return Left.Print() + " + " + Right.Print(); } } class PrintFactory : ExpFactory, ExpAlgebra { public IPrintExp Add(IPrintExp left, IPrintExp right) { return new PrintableAdd(left, right); } public new IPrintExp Lit(int n) { return new PrintableLit(n); } } static class ExampleThree { internal static int Evaluate() => ExampleTwo .AddOneToTwo(new PrintFactory()).Eval(); internal static string Print() => ExampleTwo .AddOneToTwo(new PrintFactory()).Print(); } Notice that in we are printing an expression that was already compiled in , 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 with the in the we would get a compilation error since the method does not exist in that context.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1371816574 under CC BY-SA 4.0; modifications have been made.