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


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

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

    Подробнее
    Реклама
    Комментарии 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.

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