Expression Problem and Object Algebras

Expression Problem (EP) is a classic programming problem of combining the incompatible.

The author of the task (Philip Wadler) formulates the following goals: to create such an abstraction that would allow the hierarchy to be expanded in two directions: adding new classes and adding new methods for processing the hierarchy, while maintaining strong static typing and without requiring changes to existing code [1].

In dynamically typed languages, we could add or override a method on the fly using a trick that has become known by the unsightly name monkey patching (although initially it was not about monkeys at all, but about partisans – guerrilla).

First, let's look at an example to see what the problem is.

Let us assume that we have a hierarchy of some widget components intended for rendering the screen:

abstract class Widget { 
  abstract void render(); 
}

class Text extends Widget {
  void render() { ... }
}

class Button extends Widget {
  void render() { ... }
}

Can we add a new class to the hierarchy? It seems there is nothing stopping us:

class BigRedButton extends Button {
  void render() { ... }
}

Now let's try to add a new method, for example dump()which dumps the screen state to a file:

abstract class Widget { 
  abstract void render();
  // добавили новый метод
  abstract void dump(OutputStream out);
}

class Text extends Widget {
  void render() { ... }
  void dump(OutputStream out) { ... }
}

class Button extends Widget {
  void render() { ... }
  void dump(OutputStream out) { ... }
}

But here's the problem – according to the task conditions, it is impossible to make changes to the existing code. After all, it is quite possible that the class Widget is a system/library one and we simply do not have access to its source code.

Approach number one – Visitor

A reader who is wise with experience and familiar with creativity Gangswill say don't reinvent the wheel – take the Visitor pattern.

interface Visitor {
  void visitText(Text t);
  void visitButton(Button b);
}

abstract class Widget { 
  abstract void accept(Visitor v);
}

class Text extends Widget {
  void accept(Visitor v) { v.visitText(this); }
}

class Button extends Widget {
  void accept(Visitor v) { v.visitButton(this); }
}

Now we can easily add new behavior by implementing different Visitors:

class RenderVisitor implements Visitor {
  void visitText(Text t) { /* render text */ }
  void visitButton(Button b) { /* render button */ }
}
class DumpVisitor implements Visitor {
  void visitText(Text t) { /* dump text */ }
  void visitButton(Button b) { /* dump button */ }
}

Hurray, victory! Or not? How do we now add a new class to the hierarchy, for example, Checkbox:

interface Visitor {
  void visitText(Text t);
  void visitButton(Button b);
  // Oops...
  void visitCheckbox(Checkbox c);
}

abstract class Widget { 
  abstract void accept(Visitor v);
}

class Text extends Widget {
  void accept(Visitor v) { v.visitText(this); }
}

class Button extends Widget {
  void accept(Visitor v) { v.visitButton(this); }
}

class Checkbox extends Widget {
  void accept(Visitor v) { v.visitCheckbox(this); }
}

It turns out that we need to make changes to the Visitor interface and, in addition, we will need to implement this method in all visitor implementations, but according to the task conditions, we do not make changes to the existing code.

It turns out that the problem was not solved, but rather “transposed” – now it’s not easy to add classes, but new methods.

Approach number two – modular Visitor

What if we lose some static typing, but gain more flexibility in return? 1) we can still inherit in the widget hierarchy; 2) we can extend the Visitor interface at the same time:

// 1) добавили новый класс в иерархию
class Checkbox extends Widget {
  void accept(Visitor v) {
    // хардкодим down cast в свое кастомное расширение
    if (v instanceof CheckboxAwareVisitor cv) cv.visitCheckbox(this);
    else throw new IllegalStateException("Require CheckboxAwareVisitor!");
  }
}

// 2) расширили Visitor
interface CheckboxAwareVisitor extends Visitor {
  void visitCheckbox(Checkbox c);
}

// 3) переиспользуем существующую имплементацию Visitor
class CheckboxAwareRender extends RenderVisitor implements CheckboxAwareVisitor {
  void visitCheckbox(Checkbox c) {
    // нужно дописать только этот метод, остальные наследуем
  }
}

If you look closely, in the method accept() a runtime check for a specific visitor type has appeared, otherwise the method will throw an exception, but the rest of the code remains unchanged, is available for reuse and does not even require recompilation.

Checkbox c = new Checkbox(...);

// OK
c.accept(new CheckboxAwareRender());

// успешно скомпилируется, 
// но упадет в runtime с ошибкой "Require CheckboxAwareVisitor!"
c.accept(new RenderVisitor());

By analogy, we can add other extensions:

interface SelectboxAwareVisitor extends Visitor {
  void visitSelectbox(Selectbox s);
}

class Selectbox extends Widget {
  void accept(Visitor v) {
    // хардкодим down cast в свое кастомное расширение
    if (v instanceof SelectboxAwareVisitor sv) sv.visitSelectbox(this);
    else throw new IllegalStateException("Require SelectboxAwareVisitor!");
  }
}

class SelectboxAwareRender extends RenderVisitor implements SelectboxAwareVisitor {
  void visitSelectbox(Selectbox s) {
    // render select box
  }
}

Now, for convenience, let's collect all custom implementations into a composite, which will delegate to the corresponding implementation:

class CustomCompositeRender extends RenderVisitor implements CheckboxAwareVisitor, SelectboxAwareVisitor {
    CheckboxAwareVisitor checkboxVisitor;
    SelectboxAwareVisitor selectboxVisitor;

    void visitCheckbox(Checkbox c) { checkboxVisitor.visitCheckbox(c); }
    void visitSelectbox(Selectbox s) { selectboxVisitor.visitSelectbox(s); }
}

Subtotals

In classical object-oriented languages, it is easy to extend the hierarchy with new classes, but difficult to add new behavior to them. If you apply the visitor pattern, the problem is transposed – it will be easy to add new behavior (due to different implementations of visitors), but it will be difficult to extend the hierarchy with new classes.

This limitation can be bypassed by sacrificing the purity of the code and some compile-time checks. To do this, you need to extend the visitor interface, and in a new class in the hierarchy, override the accept() method to cast visitor to your extension.

Object Algebra

Let's go back to the beginning and look at the problem from a different angle. What is the main obstacle to solving the Expression problem? It is that you can't just add an arbitrary method to a class. But you can extend interfaces without consequences.

It would be good to abandon the class hierarchy in its explicit form and replace them with interfaces. And such a method really exists – let's imagine the hierarchy as a factory interface, where methods are constructors of the corresponding variants:

interface WidgetAlg<E> {
    E panel(List<E> children);
    E textbox(String title, String input);
    E button(String title);
}

An interface of this kind (operating with one or more abstract generic types) is called an algebraic signature [2]. We will call a class that implements a signature an object algebra.

Different implementations of the interface will be responsible for different aspects of the objects' behavior.

class WidgetToString implements WidgetAlg<String> {
  public String panel(List<String> children) {
    return String.format("panel(children=[%s])", String.join(", ", children));
  }

  public String textbox(String title, String input) {
    return String.format("textbox(title=%s, input=%s)", title, input);
  }

  public String button(String title) {
    return String.format("button(title=%s)", title);
  }
}

If we want to add a new data structure variant to the hierarchy, then, similar to the Modular Visitor pattern, we should extend the signature interface:

interface SelectboxWidgetAlg<E> extends WidgetAlg<E> {
  E selectbox(String title, List<String> options);
}

class SelectboxWidgetToString extends WidgetToString implements SelectboxWidgetAlg<String> {
  // реализуем кастомное расширение, остальные методы наследуются
  public String selectbox(String title, List<String> options) {
    return String.format("selectbox(title=%s, options=[%s])", title, String.join(", ", options));
  }
}

Unlike Visitor, there is no dynamic cast required here and there are no interface/implementation mismatch errors – such code simply won't compile.

Other examples

A.Biboudis & co. in their work Streams a la carte [3] offer a flexible and extensible interface for streams (since most of the Java 8 Streams functionality is hardcoded in the standard library and cannot be overridden).

J.Richard-Foy developed and slightly told about the implementation details of the library for describing client-server interaction [4].

In general, object algebras are often used in eDSL development, often in conjunction with similar-spirited Tagless-Final style, it's a pity that Java itself has modest expressive capabilities, apparently because of this, Scala is more often chosen to solve such problems.

Sources

1. The Expression Problem

2. Extensibility for the Masses

3. Streams a la carte

4. Modular Remote Communication Protocol Interpreters