2 декабря 2011 в 13:26

Шаблоны проектирования в автоматном программировании


Из теории алгоритмов и автоматов известно понятие конечного автомата, которое описывает поведение некоторой абстрактной модели в терминах конечного набора состояний и событий, инициализирующих переходы между этими состояниями. На основании этой теории была развита достаточно распространенная сейчас парадигма автоматного программирования, при использовании которой задача решается в терминах конечных автоматов — т.е. в терминах состояний и событий. В явном виде, данная парадигма широко применяется в языках программирования, при построении лексеров. Однако, можно найти огромное количество примеров программных систем, в некотором смысле реализованных на основе данной парадигмы.

В статье рассматриваются особенности применения шаблонов 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. Там же можно найти примеры на другие паттерны, о которых уже было написано несколько статей на Хабрахабре.
Костюков Владимир @spiff
карма
244,0
рейтинг 0,0
Пользователь
Самое читаемое Разработка

Комментарии (12)

  • +12
    Шалыто в массы?
    • –3
      Ну зачем сразу в массы то :) Так для развития. Статья на самом деле очень поверхностно касается того, чем занимался Шалыто. Это больше похоже на Event-driven Finite State Machine на ООП.
      • +2
        От Шалыто можно дождаться многого…
        • –3
          Да кто спорит. Может я не корректно выразился. У Шалыто — научная работа на 600 страниц и куча публикаций. А тут — автомагнитола на шаблоне «Посетитель» :)
        • +5
          вы случайно все не из итмо?
          • +2
            кто бы мог подумать :)
          • –1
            Из ИТМО, но к Шалыто отношения не имею :)
  • +1
    Уже года 2 использую для рисования автоматов cmaptools.

    На основании полученного файла генерирую код переходов и подключаю к классу, в котором объявлены функции y0, y1,...yn и z0, z1,...zn для обработки соответственно состояний и действий при переходах.

    Таким образом код переходов и обработка переходов в разных местах и я в любой момент могу внести изменения через cmaptools. Естественно нужно поправить затронутый изменениями код обработки, но в целом получается железобетонная система, с помощью которой можно быстро и надёжно решить практически любую достаточно сложную задачу.

    Плюс всегда остаётся подробнейшая документация к коду, в которой можно без труда разобраться и через дцать лет.
  • +3
    Не могли бы вы объяснить, чем вызвано такое написание циклов:
    for (;!pool.isEmpty() || started;) {
                for (;!pool.isEmpty();) {
                    GramophoneEvent event = pool.poll();
                    event.apply(handler);
                }
    

    ? Довольно странная конструкция, на мой взгляд. Почему не while?
    • –1
      Если вопрос заключается в том «почему не while», то отвечу просто — я так привык писать и в итоге все странслируется в один и тотже код (что и был бы с while).

      Два волженных цикла нужны для «зависания» потока обработки. Там ниже, в первом есть секция synchronized, на которой поток подвисает, жо тех пор пока его не разбуит вновь поступившее событие в очередь. (см код dispatch())

      И я сделал так, что поток работает до тех пор, пока не выгребет все события из очереди, даже если его остановили раньше (методом disable())
      • 0
        Чего только не встретишь. :)
        Вопрос заключался именно в «почему не while». У меня просто немного голова заболела, когда я прочел
        «для (ничего; пока очередь не пуста; ничего не делать) { //тело цикла }»;
        вместо
        «пока (очередь не пуста) { //тело цикла }» в случае с while(!pool.isEmpty()) {}

        :)
  • 0
    У такого подхода есть слабая сторона — система закрыта для расширений пространства событий — т.к. при добавлении нового придется переписывать интерфейс GramophoneHandler, а также его наследники RadioHandler и CDHandler.

Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

Интересные публикации