Из теории алгоритмов и автоматов известно понятие конечного автомата, которое описывает поведение некоторой абстрактной модели в терминах конечного набора состояний и событий, инициализирующих переходы между этими состояниями. На основании этой теории была развита достаточно распространенная сейчас парадигма автоматного программирования, при использовании которой задача решается в терминах конечных автоматов — т.е. в терминах состояний и событий. В явном виде, данная парадигма широко применяется в языках программирования, при построении лексеров. Однако, можно найти огромное количество примеров программных систем, в некотором смысле реализованных на основе данной парадигмы.
В статье рассматриваются особенности применения шаблонов Visitor/Double Dispatch и State при реализации системы на основе конечного автомата. Кроме того, статью можно рассматривать как продолжение цикла публикаций о шаблонах проектирования на Хабрахабре.
Мотивация
Автоматное программирование — весьма удобный и гибкий инструмент, который позволяет решать поставленную задачу в терминах, близких понятиям предметной области. Например, задача о программировании поведения лифта в многоэтажном доме превращается в весьма формализованную модель автомата со следующим состояниями: “Лифт едет вверх”, “Лифт едет вниз”, “Лифт стоит на этаже N” и приходящими от жильцов дома событиями: “Нажата кнопка Вниз на N-ом этаже” и “Нажата кнопка Вверх на N-ом этаже”.
Однако на ряду с очевидными преимуществами такого подхода существует один небольшой недостаток — кодирование подобной системы представляет собой весьма неприятный процесс, сопровождаемый использованием большого количества ветвлений и переходов.
Для решения этой проблемы существует ООП и шаблоны Visitor и State.
Пример
Рассмотрим следующую задачу. Пусть требуется спроектировать и реализовать примитивную автомагнитолу, которая поддерживает два режима работы — “радио” и “CD-плеер”. Переключение между режимами осуществляется с помощью тумблера на панели управления (см. рисунок в начале статьи). Кроме того, магнитола поддерживает механизм переключения радиостанций или треков (кнопка “Next”), в зависимости от выставленного режима.
Отличный пример того как данная задача решается на основе вложенных ветвлений (switch) языка Си можно посмотреть в Википедии. Рассмотрим его наиболее значимый участок.
switch( state ) { case RADIO: switch(event) { case mode: /* Change the state */ state = CD; break; case next: /* Increase the station number */ stationNumber++; break; } break; case CD: switch(event) { case mode: /* Change the state */ state = RADIO; break; case next: /* Go to the next track */ trackNumber++; break; } break; }
Код из примера абсолютно не читаем и тяжело расширяем. Например, добавление нового состояния или события представляется весьма трудоемкой операцией, требующей модификацию большого количества кода. Кроме того, такой спагетти-код провоцирует разработчика дублировать некоторые участки (возможна ситуация, при которой в разных состояниях одно и тоже событие должно обрабатываться одинаково).
Шаблон Visitor и его частный случай Double Dispatch призван решить данную проблему, путем разделения понятий состояния и обработчика. При этом, конечная реализация алгоритма обработки события выбирается в процессе исполнения, на основе двух факторов: типа события и типа обработчика (отсюда название — “Двойная Диспетчеризация”).
Таким образом, для добавления нового типа события или обработчика в систему, достаточно лишь реализовать требуемый класс, наследника классов “Событие” или “Обработчик” соответственно.
Диаграмма классов
Основные сущности системы:
- Gramophone — магнитола, которая может включаться — enable(), выключаться — disable() и принимать события — dispatch(event);
- GramophoneEvent — интерфейс возможных событий с одним единственным методом — apply(handler) для “применения” обработчика к событию;
- GramophoneHandler — интерфейс обработчика, который содержит полиморфные методы (handle) обработки всех существующих в системе событий;
Наибольший интерес в рассмотренной диаграмме представляет интерфейс GramophoneHandler, который одновременно является частью конструкции Visitor (в качестве самого посетителя) и самодостаточной конструкцией State (в качестве состояния для Gramophone). Т.е. можно считать, что в рассмотренном примере используется своего рода композиция двух шаблонов.
Реализация
Один из вариантов использования системы будет выглядеть следующим образом:
public static void main(String args[]) { Gramophone gramophone = new Gramophone(); // it's CD by default gramophone.enable(); // start event loop gramophone.dispatch(new ToogleEvent()); // toogle to radio gramophone.dispatch(new NextEvent()); // next station gramophone.dispatch(new ToogleEvent()); // toogle to CD player gramophone.dispatch(new NextEvent()); // next CD track gramophone.disable(); // stop event loop }
Опишем возможные варианты внешних событий, приходящих системе.
/** * Events */ interface GramophoneEvent { void apply(GramophoneHandler handler); } class ToogleEvent implements GramophoneEvent { @Override public void apply(GramophoneHandler handler) { handler.handle(this); } } class NextEvent implements GramophoneEvent { @Override public void apply(GramophoneHandler handler) { handler.handle(this); } }
В рассмотренном коде, метод apply() имеет одинаковую реализацию во всех потомках. В этом заключается основная идея шаблона — полиморфное определение типа события в процессе исполнения кода. Т.е. у обработчика будет вызываться метод handle() в зависимости от типа самого события (типа ссылки this).
В языках, не поддерживающих полиморфизм (например в JavaScript), можно инкапсулировать информацию о типе обрабатываемого события в названии метода. Тогда в нашем случае методы буду выглядеть как handleNext(event) и handleToogle(event) а вызывающий код так:
var NextEvent = function() { this.apply = function(handler) { handler.handleNext(this); } }
Реализация возможных состояний системы представляет собой следующий код. В нашем случае состояние = обработчик.
/** * Visitor */ interface GramophoneHandler { void handle(ToogleEvent event); void handle(NextEvent event); } class RadioHandler implements GramophoneHandler { private Gramophone gramophone; public RadioHandler(Gramophone gramophone) { this.gramophone = gramophone; } @Override public void handle(ToogleEvent event) { gramophone.toogle(new CDHandler(gramophone)); } @Override public void handle(NextEvent event) { gramophone.nextStation(); } } class CDHandler implements GramophoneHandler { private Gramophone gramophone; public CDHandler(Gramophone gramophone) { this.gramophone = gramophone; } @Override public void handle(ToogleEvent event) { gramophone.toogle(new RadioHandler(gramophone)); } @Override public void handle(NextEvent event) { gramophone.nextTrack(); } }
Наконец расмотрим реализацию основного класса системы — магнитолы (Gramophone).
/** * FSM (Finit-State-Machine) implementation */ class Gramophone implements Runnable { private GramophoneHandler handler = new CDHandler(this); private Queue<GramophoneEvent> pool = new LinkedList<GramophoneEvent>(); private Thread self = new Thread(this); private int track = 0, station = 0; private boolean started = false; public void enable() { started = true; self.start(); } public void disable() { started = false; self.interrupt(); try { self.join(); } catch (InterruptedException ignored) { } } public synchronized void dispatch(GramophoneEvent event) { pool.offer(event); notify(); } @Override public void run() { for (;!pool.isEmpty() || started;) { for (;!pool.isEmpty();) { GramophoneEvent event = pool.poll(); event.apply(handler); } synchronized (this) { try { wait(); } catch (InterruptedException ignored) { } } } } void toogle(GramophoneHandler handler) { this.handler = handler; System.out.println("State changed: " + handler.getClass().getSimpleName()); } void nextTrack() { track++; System.out.println("Track changed: " + track); } void nextStation() { station++; System.out.println("Station changed: " + station); } }
В рассмотренной реализации методы toogle(), nextTrack() и nextStation() имеют область видимости только внутри пакета. Это сделано для того, чтобы обезопасить систему от прямых внешних вызовов. Более того, в реальных условиях рекомендуется дополнительно проверять природу вызывающего потока. Например в каждый из методов можно добавить следующий код проверки.
void nextTrack() { if (Thread.currentThread() != self) { throw new RuntimeException(“Illegal thread”); } track++; System.out.println("Track changed: " + track); }
Кроме того, следует обратить внимание на метод run(), который реализует идиому Event Loop. В данном случае, метод содержит два вложенных цикла, обеспечивающих засыпание потока при отсутствии событий в очереди. При этом, добавление каждого нового события в очередь (см. метод dispatch()) его пробуждает.
Заключение
Статья не является пропагандой использования ООП и шаблонов проектирования, а лишь раскрывает особенности использования перечисленных инструментов для решения конкретной задачи.
Код рассмотренного примера доступен на GitHub. Там же можно найти примеры на другие паттерны, о которых уже было написано несколько статей на Хабрахабре.
