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

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

В статье рассматриваются особенности применения шаблонов 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. Там же можно найти примеры на другие паттерны, о которых уже было написано несколько статей на Хабрахабре.