Solutions to the Expression Problem Using Object Algebras

This page documents solutions to the Expression Problem using object algebras. These solutions are meant to illustrate the use of object algebras in various programming languages. Object algebras and a solution to the Expression Problem in Java were presented in the paper:

Extensibility for the Masses: Practical Extensibility with Object Algebras

Bruno C. d. S. Oliveira and William R. Cook

The source code for the paper can be found here.

Reading the paper is recommended for understanding the code in the solutions as this web page only contains very limited information.

If you have a solution for the expression problem in your favourite language, and that language is not listed here, please consider sending it to us. We will publish it here together with the information about the author responsible for it.

Background: The Expression Problem

The expression problem (EP) [1] is a classical problem in programming languages. It refers to the difficulty of writing data abstractions that can be easily extended with both new operations and new data variants. Traditionally the kinds of data abstraction found in functional languages can be extended with new operations, but adding new data variants is difficult. The traditional object-oriented approach to data abstraction facilitates adding new data variants (classes), while adding new operations is more difficult. The Visitor Pattern [2] is often used to allow operations to be added to object-oriented data abstractions, but the common approach to visitors prevents adding new classes.

The problem

The expression problem is about implementing a language for arithmetic expressions (for example: 1 + 2, 4 * 5, (8 + 3) * 4). The expression problem is meant to be a canonical problem illustrating the difficulties that arize when software evolves. So, there is an initial set of features comprised by the initial types of expressions and operations over those expressions.

Initial set of features

Types of expressions: Integer literals, addition.
Operations: Evaluation of expressions.

Evolution 1

Add a new type of expressions. For example, subtraction.

Evolution 2

Add a new operation. For example pretty printing.

Note that there is a lot more that can be done in terms of evolution, but those two basic evolutions serve to illustrate the essence of the problem.

Requirements for a solution

Without further constraints, the expression problem is trivial to solve. However, the point of the expression problem is to be able to do software evolution in a modular way, without modifying or recompiling code that has been written previously. The requirements of the expression problem are stated more precisely next:

Extensibility in both dimensions: A solution must allow the addition of new types of expressions and new operations and support extending existing operations.
Strong static type safety: A solution must prevent applying an operation to an expression which it cannot handle using static checks.
No modification or duplication: Existing code must not be modified nor duplicated.
Separate compilation and type-checking: Safety checks or compilation steps must not be deferred until link or runtime.
(Optional requirement) Independent extensibility: It should be possible to combine independently developed extensions so that they can be used jointly.

The last requirement, independent extensibility, tends to need some additional sophistication from the programming language or code, so we'll consider it optional for a basic solution to the expression problem.

Solutions using Object Algebras

A general solution for the problem that works in basically any language with interfaces and a simple form of generics can be achieved with object algebras (see the paper for details). The code for solutions in various languages is shown next:

Java (authors: Bruno Oliveira and William Cook)
F# (authors: Matthew Parkinson and Gavin Bierman)
Scala (author: Bruno Oliveira)
Haskell (author: Bruno Oliveira)
C# (author: Ralph Moritz)
C++ (author: Weixin Zhang)

References

[1] Philip Wadler, The Expression Problem, Email (Nov 1998), discussion on the Java Genericity mailing list
[2] Eric Gamma, Richard Helm, Ralph Johnson and John Vlissides. Design Patterns: Elements of Reusable Object-Oriented Software. Addisson-Wesley professional computing series, Addisson-Wesley (1994)