I am going to have a look at the Expression Problem starting from a simple floral code. Once the problem is faced, I’ll state it formally, and then I’ll have a look at the functional side of things.

I’ll finish with solutions that appear in the literature, and see if any is easy to implement in Java.

1. OOP Flowers

I enjoy flowers, and I want to break from the usual examples given in code (Java here).

So, let’s first define what a flower is, and its properties.

public interface Flower {
  String name();
}

Now, let’s define some flowers, such as a rose and a tulip for example:

public class Rose implements Flower {
  @Override public String name() {
    return "Rose";
  }
}

public class Tulip implements Flower {
  @Override public String name() {
    return "Tulip";
  }
}

That’s fairly straight-forward.

Here is the graph corresponding to that code:

Initial UML Diagram

1.1. Adding a new flower

Let’s add a new flower to our families, such as a Daisy:

public class Daisy implements Flower {
  @Override public String name() {
    return "Daisy";
  }
}

1.2. Adding a new action

Our name function is an action that we can perform on a Flower. What about adding a new one, such as `floralFormula`[1]?

public interface Flower {
  String name();
  String floraFormula();
}

public class Rose implements Flower {
  @Override public String name() {
    return "Rose";
  }

  @Override public String floralFormula() {
    return "K(5)C5A∝G(1-5)";
  }
}

public class Tulip implements Flower {
  @Override public String name() {
    return "Tulip";
  }

  @Override public String floralFormula() {
    return "P(3+3)A(3+3)G(3)";
  }
}

public class Daisy implements Flower {
  @Override public String name() {
    return "Daisy";
  }

  @Override public String floralFormula() {
    return "Ca(5)Co(5)A(5)G(2)";
  }
}

That was a bit longer, as modifying the interface led to having to update all existing flowers.

Initial UML Diagram after adding an action

1.3. OOP Sum-up

The way we modelled our flowers in OOP, it was easy to add a new flower without having to touch existing code, but adding a new action forced us to modify all known flowers.

What does that mean?

On the one hand, if the interface is provided to you by a library, then you know you will be limited to what can be added and where. Ever thought about adding a new function inside the String class for example? You cannot.

The following matrix sums up what is easy and what is not in OOP:

OOP Matrix showing that adding objects is easy

Now, let’s have a look at how the same thing would be implemented in a functional language.

2. FP Flowers

I’ll use F#:

type flower = Rose | Tulip

let name flower =
    match flower with
        | Rose -> "Rose"
        | Tulip -> "Tulip"

2.1. Adding a new flower

Again, let’s add a Daisy:

type flower = Rose | Tulip | Daisy

let name flower =
    match flower with
        | Rose -> "Rose"
        | Tulip -> "Tulip"
        | Daisy -> "Daisy"

In this case, we already had to update the flower type as well as the name function.

2.2. Adding a new action

Again, let’s add flowerFormula:

let flowerFormula flower =
    match flower with
        | Rose -> "K(5)C5A∝G(1-5)"
        | Tulip -> "P(3+3)A(3+3)G(3)"
        | Daisy -> "Ca(5)Co(5)A(5)G(2)"

This time we didn’t have to modify any existing flowers!

2.3. FP Sum-up

The way we modelled our flowers in FP, it was easy to add a new action without having to touch existing code, but adding a new flower forced us to modify all known actions.

It clearly feels like what is easy in FP isn’t in OOP, and vice versa.

The following matrix sums up what is easy and what is not in FP:

FP Matrix showing that adding actions is easy

3. The Expression Problem

The limitations we encountered in both cases is The Expression Problem. With our matrix, the question becomes: is it possible to model this in a such a way that adding either a flower type or an action does not lead us to modify existing code?

Expression Problem Matrix: how to could we make adding either an action or an object easy?

This sounds like the Single Responsibility Principle.

Matrix

More formally, the expression problem adds a few conditions to a solution[2]:

  • Extensibility in both dimensions: A solution must allow the addition of new data variants and new operations and support extending existing operations.

  • Strong static type safety: A solution must prevent applying an operation to a data variant 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.

  • Independent extensibility: it should be possible to combine independently developed extensions so that they can be used jointly.

4. "From OOP to FP": the Visitor Pattern

Before diving into solutions to this problem, let’s see how the Visitor Pattern in OOP allows one to make the OOP matrix become the FP matrix.

The idea of the visitor pattern comes from the following observation: the root cause forcing us to modifying existing flowers whenever we add a new action is the fact that flowers have knowledge of their own action (aka., they are defined in the interface that all flowers implement).

Therefore, if a flower can only accept actions that will be passed to them, the problem is circumvented.

public interface Flower {
  Object accept(final Action action);
}

public class Rose implements Flower {
  @Override public Object accept(final Action action) {
    return action.execute(this);
  }
}

public class Tulip implements Flower{
  @Override public Object accept(final Action action) {
    return action.execute(this);
  }
}

public class Daisy implements Flower {
  @Override public Object accept(final Action action) {
    return action.execute(this);
  }
}

This allows us to define what an Action is:

public interface Action {
  Object execute(final Rose flower);
  Object execute(final Tulip flower);
  Object execute(final Daisy flower);
}

And we can now re-create our actions, such as Name:

public class Name implements Action {
  @Override public Object execute(final Rose flower) {
    return "Rose";
  }

  @Override public Object execute(final Tulip flower) {
    return "Tulip";
  }

  @Override public Object execute(final Daisy flower) {
    return "Daisy";
  }
}

This last piece of code clearly shows that we could add that action without having to touch any existing flowers!

However, adding new flowers still forces us to modifying Action, and therefore all actions as well.

If you’re wondering how to use such a code, here is an example:

public class Main {
  public static void main(String[] args) {
    final Rose rose = new Rose();
    final Action action = new Name();
    System.out.println("Hello " + action.execute(rose));
  }
}

Graphically, this gives:

OOP: Visitor Pattern

5. Solutions to the Expression Problem

The Expression Problem is named as such, because it can be used to determine the expression power of a given language. Indeed, the easier it is to solve the Expression Problem, the more freedom of expression you get from a language.

Consequently, there exist multiple ways to solve this, depending on what your language capabilities:

  • In the 90s we saw Open Classes arrive;

  • In the same decade, we also saw Multimethods;

  • In the 2000s, Generalized Algebraic Data Types (GADTs) were shown also be a viable solution;

  • In the 2010s, Object Algebras / Tagless Interpreters converged;

  • etc.

Unfortunately, Java does not allow to use either Open Classes nor Multimethods, and GADTs are way too verbose in Java to be useful.

Fortunately, Object Algebras are easy to implement in Java as no special feature is needed.

Fun story: Object Algebras are the result of research starting from a OOP language to a solution, while Tagless Interpreters are the result of research starting from a FP language, yet they are equivalent.

6. Object Algebras

We the visitor pattern, we saw that if we decouple actions from the flowers hierarchy, we gain the freedom to add new actions without having to touch existing flowers.

However, our hierarchy of actions knew about all flowers, thus adding a new flower forced us to update all actions.

Object Algebras aim at decoupling both flowers and actions hierarchies by using what Java calls generics.

First, we have to define what a flower is, and it must not be aware of any action whatsoever:

public interface Flower {
}

We can thus define our flowers:

public class Rose implements Flower {
}

public class Tulip implements Flower {
}

Then, we need a way to define an action that knows the least amount possible information about flowers, yet is linked to flowers:

public interface Action<T extends Flower> {
}

This allows us to define our actions contracts, in particular Name:

public interface Name<T extends Flower> extends Action<T> {
  String name(T flower);
}

We can see that we force the action to work on types part of the Flower hierarchy by asking for an object that extends the Flower interface. This ensures actions don’t have to know all the hierarchy to be able to work.

However, this is only the contract of the Name action, we now need to implement it for each flower:

public class RoseName implements Name<Rose> {
  @Override
  public String name(Rose flower) {
    return "Rose";
  }
}

public class TulipName implements Name<Tulip> {
  @Override
  public String name(Tulip flower) {
    return "Tulip";
  }
}

That’s it!

Now, adding a new flower, such as Daisy, is totally independent from the existing code: 1 new class implementing Flower, and 1 new class per Action so that existing actions are properly defined for a Daisy. Same with adding a new action: 1 new interface defining that new Action, and 1 new class per pre-existing Flower to implement this new action.

Give it a try, and first add a Daisy, and then add a FloralFormula!

If you’re wondering how to use this code, here is how it looks like:

public class Main {
  public static void main(String[] args) {
    System.out.println("First Usage: " + new RoseName().name(new Rose()));
    System.out.println("Second Usage: " + new TulipName().name(new Tulip()));
  }
}

Graphically, it becomes clearer that we decoupled the hierarchies:

Object Algebra Graph

7. Conclusion

We’ve seen how the expression problem manifests itself in Java, and a possible solution with Object Algebras that can be understood as an extension of the Visitor Pattern.

As with anything, there are pros and cons to this approach in Java. Playing with it will allow you to figure some of them, so I strongly encourage you that you do.

It also highlights that using a different language might provide you with features to express things in a simpler manner.

1. A flower formula is a formula whose purpose is to capture the architecture of a flower in a dense way. If you want to know more: https://en.wikipedia.org/wiki/Floral_formula
2. B. C. d. S. Oliveira & W. R. Cook, 2012 "Extensibility for the Masses"