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 и отсутствуют ошибки несоответствия интерфейса и реализации — такой код просто не скомпилируется:

static <T> T exampleAlg(SelectboxWidgetAlg<T> f) {
  List<String> options = List.of("...", "...");
  return f.panel(List.of(
    f.selectbox("Choose one", options),
    f.button("Next")
  ));
}

// Ok
exampleAlg(new SelectboxWidgetToString());
// Error - базовый класс не имплементирует наше расширение SelectboxWidgetAlg
exampleAlg(new WidgetToString());

Upd. Разберемся на чем базируется данный подход.

Church encoding

На заре computer science в процессе работы над лямбда-исчислением перед Алонзо Чёрчем встала задача каким-то образом представить произвольные структуры данных. Известно, что лямбда-исчисление это крайне простая система, состоящая только из переменных и функций. Как в таких стесненных условиях моделировать структуры данных? Выбор у нас небольшой — будем применять функции высшего порядка.

Допустим, мы хотим представить алгебраический тип данных для формул.

data Exp = Lit Int       -- числовой литерал, константа
         | Neg Exp       -- изменение знака x → -x
         | Add Exp Exp   -- сложение x + y

Каждый конструктор варианта представлен отдельной функцией:

Lit :: Int → Exp -- конструктор для литерала. принимаем один параметр Int, возвращаем созданное выражение
Neg :: Exp → Exp -- конструктор для negate. принимаем выражение, возвращаем инвертированное выражение
Add :: Exp × Exp → Exp -- принимаем пару параметров, возвращаем сумму

Соберем итоговый тип структуры:

type ChurchEncodedExp = ∀Exp.(Int → Exp) → (Exp → Exp) → (Exp × Exp → Exp) → Exp

Итого, получилась функция трех аргументов: первый — конструктор Lit, второй — конструктор Neg, третий — конструктор Add. Преобразование структуры данных в подобную функцию называется кодированием Чёрча (Church encoding).

Теперь реализуем функции - "фабрики" для каждого варианта:

lit x = \onlit onneg onadd -> onlit x
neg e = \onlit onneg onadd -> onneg (e onlit onneg onadd)
add e1 e2 = \onlit onneg onadd -> onadd (e1 onlit onneg onadd) (e2 onlit onneg onadd)

-- пример выражения
example_exp = add (lit 8) (neg (add (lit 1) (lit 2)))

Как видим в такой записи много дублированного кода. Хотелось бы семантически связанные вещи объединить. Например, билдеры onlit, onneg, onadd:

signature ExpSig e {
  onlit :: Int → e
  onneg :: e → e
  onadd :: e × e → e
}

Эта запись подозрительно напоминает интерфейс в Java:

interface ExpSig<E> {
  E lit(int x);
  E neg(E x);
  E add(E x, E y);
}

Подставляя разные реализации интерфейса ExpSig мы будем получать разные интерпретации выражений:

lit x = \sig -> onlit x
neg e = \sig -> onneg (e sig)
add e1 e2 = \sig -> onadd (e1 sig) (e2 sig)

eval_signature = ExpSig {
  onlit = \x -> x
  onneg = \x -> -x
  onadd = \x y -> x + y
}

to_string_signature = ExpSig {
  onlit = \x -> "$x"        -- интерполяция строки
  onneg = \x -> "(- ($x))"
  onadd = \x y -> "$x + $y"
}

-- пример выражения
example_exp = add (lit 8) (neg (add (lit 1) (lit 2)))

-- применим eval_signature
example_exp(eval_signature) == 5

-- применим to_string_signature
example_exp(to_string_signature) == "8 + (- (1 + 2))"

Теперь если присмотреться к ExpSig то можно заметить, что это набор методов, которые оперируют алгебраическим типом Exp, т. е. по определению это интерфейс объектной алгебры (или сигнатура объектной алгебры).

Подытожим, что мы сделали.

1) Алгебраический тип данных E = T1 | T2 ... | Tn (он же тип-сумма, он же discriminated union) кодируется как функция вида (T1 → E) → (T2 → E) → ... → (Tn → E) → E

2) Для удобства именуем каждую функцию-конструктор и «транспонируем» строку в столбец, таким образом описываем сигнатуру алгебры:

signature E {
  cons1 :: T1 -> E
  cons2 :: T2 -> E
  ....
  consN :: Tn -> E
}

3) В языках типа Java, C# сигнатура будет представлена интерфейсом

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

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

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