Expression Problem и Объектные алгебры
Expression Problem (EP) — это классическая задача в программировании на совмещение несовместимого.
Автор задачи (Philip Wadler) формулирует следующие цели: создать такую абстракцию, что позволяла бы расширять иерархию в двух направлениях: добавлять новые классы и добавлять новые методы для обработки иерархии, сохраняя при этом строгую статическую типизацию и не требуя изменений существующего кода [1].
В динамически типизируемых языках мы бы могли добавить или переопределить метод на лету с помощью трюка, ставшего известным под неказистым названием monkey patching (хоть первоначально речь шла совсем не про обезьян, а про партизан — guerrilla).
Для начала разберемся на примере в чем заключается проблема.
Hidden text
Примеры будем описывать на упрощенной Java. При необходимости код можно адаптировать под любой другой ОО-язык.
Пусть на дана иерархия неких компонентов-виджетов, предназначенных для отрисовки экрана:
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 panel(List children);
E textbox(String title, String input);
E button(String title);
} Интерфейс такого вида (оперирующий одним или несколькими абстрактными generic-типами) назовем алгебраической сигнатурой [2]. Объектной алгеброй назовем класс, имплементирующий сигнатуру.
Разные имплементации интерфейса будут отвечать за разные аспекты поведения объектов.
class WidgetToString implements WidgetAlg {
public String panel(List 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 extends WidgetAlg {
E selectbox(String title, List options);
}
class SelectboxWidgetToString extends WidgetToString implements SelectboxWidgetAlg {
// реализуем кастомное расширение, остальные методы наследуются
public String selectbox(String title, List 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.
Источники
The Expression Problem
Extensibility for the Masses
Streams a la carte
Modular Remote Communication Protocol Interpreters
