Expression Problem (EP) - это классическая задача в программировании на совмещение несовместимого.

Автор задачи (Philip Wadler) формулирует следующие цели: создать такую абстракцию, что позволяла бы расширять иерархию в двух направлениях: добавлять новые классы и добавлять новые методы для обработки иерархии, сохраняя при этом строгую статическую типизацию и не требуя изменений существующего кода [1].

В динамически типизируемых языках мы бы могли добавить или переопределить метод на лету с помощью трюка, ставшего известным под неказистым названием monkey patching (хоть первоначально речь шла совсем не про обезьян, а про партизан - guerrilla).

Для начала разберемся на примере в чем заключается проблема.

Пусть на дана иерархия неких компонентов-виджетов, предназначенных для отрисовки экрана:

abstract class Widget { 
  abstract void render(); 
}

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

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

Можем ли мы добавить новый класс в иерархию? Кажется ничто нас не останавливает:

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

Теперь попробуем добавить новый метод, например dump(), выгружающий состояние экрана в файл:

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) { ... }
}

А вот тут проблема - по условию задачи вносить изменения в существующий код нельзя. Ведь вполне вероятно, что класс Widget является системным / библиотечным и доступа к его исходникам у нас просто нет.

Подход номер раз - Visitor

Читатель, умудренный опытом и знакомый с творчеством Банды, скажет не придумывайте велосипед - возьмите паттерн Visitor.

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); }
}

Теперь мы легко сможем добавить новое поведение с помощью реализации разных Visitor-ов:

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 */ }
}

Ура, победа! Или нет? Как же теперь добавить новый класс в иерархию, например, 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); }
}

Получается нужно внести изменения в интерфейс Visitor и к тому же потребуется реализовать этот метод во всех имплементациях визитера, но по условию задачи изменения в существующий код не вносим.

Получается проблему не решили, а "транспонировали" - теперь не классы легко добавлять, а новые методы.

Подход номер два - модульный Visitor

А что если мы потеряем немного статической типизации, но взамен приобретем больше гибкости? 1) мы все еще можем наследоваться в иерархии виджетов; 2) мы можем одновременно с этим расширять интерфейс Visitor:

// 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) {
    // нужно дописать только этот метод, остальные наследуем
  }
}

Если присмотреться, в методе accept() появилась runtime-проверка на конкретный тип визитера, в противном случае метод выкинет исключение, но зато весь остальной код остается без изменений, доступен для повторного использования и это даже не требует перекомпиляции.

Checkbox c = new Checkbox(...);

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

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

По аналогии можем добавлять другие расширения:

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
  }
}

А теперь для удобства соберем все кастомные реализации в композит, который будет делегировать в соответствующую имплементацию:

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); }
}

Промежуточные итоги

В классических объектно-ориентированных языках легко расширять иерархию новыми классами, но трудно добавить к ним новое поведение. Если применить паттерн visitor, то проблема транспонируется - станет легко добавлять новое поведение (за счет разных реализаций визитеров), но будет сложно расширить иерархию новыми классами.

Это ограничение можно обойти пожертвовав чистотой кода и частью compile-time проверок. Для этого необходимо расширить интерфейс визитера, а в новом классе в иерархии переопределить метод accept(), чтобы кастить visitor в свое расширение.

Object Algebra

Откатимся к началу и посмотрим на проблему под другим углом. В чем заключается основное препятствие при решении Expression problem? В том, что нельзя просто так добавить в класс произвольный метод. Зато можно без последствий расширять интерфейсы.

Вот было бы хорошо отказаться от иерархии классов в явном виде и заменить их на интерфейсы. И такой способ действительно существует - представим иерархию в виде интерфейса-фабрики, где методы это конструкторы соответствующих вариантов:

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

Интерфейс такого вида (оперирующий одним или несколькими абстрактными generic-типами) назовем алгебраической сигнатурой [2]. Объектной алгеброй назовем класс, имплементирующий сигнатуру.

Разные имплементации интерфейса будут отвечать за разные аспекты поведения объектов.

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);
  }
}

Если мы хотим добавить новый вариант структуры данных в иерархию, то по аналогии с шаблоном Modular Visitor следует расширить интерфейс сигнатуры:

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));
  }
}

В отличие от Visitor здесь не требуется dynamic cast и отсутствуют ошибки несоответствия интерфейса и реализации - такой код просто не скомпилируется.

Другие примеры

A.Biboudis & co. в своей работе Streams a la carte [3] предлагают гибкий и расширяемый интерфейс для стримов (т.к. большая часть функционала Java 8 Streams захардкожена в стандартной библиотеке и не может быть переопределена).

J.Richard-Foy разработал и немного рассказал о деталях реализации библиотеки для описания клиент-серверного взаимодействия [4].

Вообще, объектные алгебры часто применяют при разработке eDSL, часто совместно с близким по духу Tagless-Final стилем, жаль что в самой java скромные выразительные возможности, видимо из-за этого для решения подобных задач чаще выбирают scala.

Источники

1. The Expression Problem

2. Extensibility for the Masses

3. Streams a la carte

4. Modular Remote Communication Protocol Interpreters