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