Конечный автомат и его реализация на Javascript

    Разрабатывая очередной интерфейс столкнулся с задачей, где требовалась реализация конечного автомата.
    Побродив по интернету и изучив этот вопрос, решил написать небольшую заметку.

    Хорошее и простое определение конечного автомата можно дать так:
    Конечный автомат — это компьютерная программа, которая состоит из:
    • Событий, на которые реагирует программа;
    • Состояний, в которых программа пребывает между событиями;
    • Переходов между состояниями при реагировании на события;
    • Действий, выполняемых в процессе переходов;
    • Переменных, которые содержат значения, необходимые для выполнения действий между событиями.

    Конечные автоматы обычно представляют в двух видах:
    1. Ориентированного графа, где точки это определенные состояния, а стрелки — направления переходов.
    2. Двумерной таблицей, столбцы — это события, а строки — состояния, а ячейки содержат действия и переходы.

    Автомат состоит из события, к которому привязаны соответствующие обработчики, и состояния, в котором находится автомат.

    Для лучшего понимания как работает программа с использованием конечного автомата бывает полезным нарисовать представление ориентированного графа с изображением всех состояний, событий и действий. В другом случаем, может быть полезным перевести автомат в таблицу. В любом случае, надо исходить из конкретной ситуации.

    Конечный автомат довольно хорошо применим в много шаговых интерфейсах, где следующий шаг зависит от того, какие параметры были выбраны на текущем (предыдущем) шаге. Например, анкета на оформление кредитной карты. Также, автомат, хорошо применим в интерфейсах, в которых есть логика прогнозирования отрисовки, основанная на выбранных параметрах. Т.е. там где моделируется поведение, при котором реакция на будущие события зависит от предыдущих событий (поэтому автомат хорошо изображается в виде графа).

    Machina.JS


    Machina.js — является одной из реализаций конечного автомата. Подробную документацию можно найти на сайте проекта.

    Что из себя представляет machina.js:
    • Работает в браузере и на nodejs
    • поддерживает amd-модули
    • зависит от undersore или lodash
    • написано Jim Cowart, автора postal.js и monologue.js

    Чтобы лучше понять, что такое конечный автомат, рассмотрим пример реализации автомата на machina.js (взял код с сайта проекта).

    Много кода
    var vehicleSignal = new machina.Fsm( {
    
        // the initialize method is called right after the FSM
        // instance is constructed, giving you a place for any
        // setup behavior, etc. It receives the same arguments
        // (options) as the constructor function.
        initialize: function( options ) {
            // your setup code goes here...
        },
    
        namespace: "vehicle-signal",
    
        // `initialState` tells machina what state to start the FSM in.
        // The default value is "uninitialized". Not providing
        // this value will throw an exception in v1.0+
        initialState: "uninitialized",
    
        // The states object's top level properties are the
        // states in which the FSM can exist. Each state object
        // contains input handlers for the different inputs
        // handled while in that state.
        states: {
            uninitialized: {
                // Input handlers are usually functions. They can
                // take arguments, too (even though this one doesn't)
                // The "*" handler is special (more on that in a bit)
                "*": function() {
                    this.deferUntilTransition();
                    // the `transition` method takes a target state (as a string)
                    // and transitions to it. You should NEVER directly assign the
                    // state property on an FSM. Also - while it's certainly OK to
                    // call `transition` externally, you usually end up with the
                    // cleanest approach if you endeavor to transition *internally*
                    // and just pass input to the FSM.
                    this.transition( "green" );
                }
            },
            green: {
                // _onEnter is a special handler that is invoked
                // immediately as the FSM transitions into the new state
                _onEnter: function() {
                    this.timer = setTimeout( function() {
                        this.handle( "timeout" );
                    }.bind( this ), 30000 );
                    this.emit( "vehicles", { status: GREEN } );
                },
                // If all you need to do is transition to a new state
                // inside an input handler, you can provide the string
                // name of the state in place of the input handler function.
                timeout: "green-interruptible",
                pedestrianWaiting: function() {
                    this.deferUntilTransition( "green-interruptible" );
                },
                // _onExit is a special handler that is invoked just before
                // the FSM leaves the current state and transitions to another
                _onExit: function() {
                    clearTimeout( this.timer );
                }
            },
            "green-interruptible": {
                pedestrianWaiting: "yellow"
            },
            yellow: {
                _onEnter: function() {
                    this.timer = setTimeout( function() {
                        this.handle( "timeout" );
                    }.bind( this ), 5000 );
                    // machina FSMs are event emitters. Here we're
                    // emitting a custom event and data, etc.
                    this.emit( "vehicles", { status: YELLOW } );
                },
                timeout: "red",
                _onExit: function() {
                    clearTimeout( this.timer );
                }
            },
            red: {
                _onEnter: function() {
                    this.timer = setTimeout( function() {
                        this.handle( "timeout" );
                    }.bind( this ), 1000 );
                    this.emit( "vehicles", { status: RED } );
                },
                _reset: "green",
                _onExit: function() {
                    clearTimeout(this.timer);
                }
            }
        }
    
        // While you can call the FSM's `handle` method externally, it doesn't
        // make for a terribly expressive API. As a general rule, you wrap calls
        // to `handle` with more semantically meaningful method calls like these:
        reset: function() {
            this.handle( "_reset" );
        },
    
        pedestrianWaiting: function() {
            this.handle( "pedestrianWaiting" );
        }
    } );
    
    // Now, to use it:
    // This call causes the FSM to transition from uninitialized -> green
    // & queues up pedestrianWaiting input, which replays after the timeout
    // causes a transition to green-interruptible....which immediately
    // transitions to yellow since we have a pedestrian waiting. After the
    // next timeout, we end up in "red".
    vehicleSignal.pedestrianWaiting();
    // Once the FSM is in the "red" state, we can reset it to "green" by calling:
    vehicleSignal.reset();
    

    Как видно по комментариям в коде, new machina.Fsm — создает экземпляр конечного автомата, в качестве аргумента принимает конфигурацию автомата со всеми его состояниями.

    В текущем примере задано 5 состояний автомата, причем автомат может находиться только в одном из этих состояний uninitialized, green, green-interruptible, yellow или red.

    Состояние представляет из себя объект, который содержит обработчики текущего состояния.

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

    Подробнее можно почитать на сайте проекта, а также посмотреть презентацию и видео.

    Можно посмотреть на примеры других реализаций конечного автомата:


    P.S.
    По мотивом раскритикованной статьи.
    Метки:
    • –1
    • 12,2k
    • 7
    Поделиться публикацией
    Похожие публикации
    Комментарии 7
    • +8
      Ни описания как работает, ни примеров использования в реальном мире. Может дополните до статьи?
      • 0
        Ммм… вам описание работы конечного автомата?

        Есть список состояний, каждое из которых задает правило перехода к следующему и т.д. и т.д.
      • 0
        Хоть бы написали, зачем такие автоматы нужны в программировании (считается, что практически не требуют отладки; визуализация алгоритма, что позволяет генерировать код практически без участия программиста) и какие есть особенности (сам по себе автомат — последовательное устройство, но умные и правильно растущие руки позволяют создать более эффективные и менее кодо- / металлоемкие параллельные системы)
        • 0
          Конечный автомат довольно хорошо применим в много шаговых интерфейсах, где следующий шаг зависит от того, какие параметры были выбраны на текущем (предыдущем) шаге. Например, анкета на оформление кредитной карты. Также, автомат, хорошо применим в интерфейсах, в которых есть логика прогнозирования отрисовки, основанная на выбранных параметрах. Т.е. там где моделируется поведение, при котором реакция на будущие события зависит от предыдущих событий (поэтому автомат хорошо изображается в виде графа).

          • 0
            Только увидел Ваш ответ.
            Это не автомат, а алгоритм. С таким же успехом автоматом можно назвать любое действие с контролем промежуточного состояния. Пример.
            1 Вы ели? Да/нет — Вымойте руки/Сходите в столовую.
            2 Руки чистые? Да/Нет — Идите работать / Вернитесь в туалет
            Если применительно к сетям Петри, то там автомат появляется в вырожденном случае — 1 вход и 1 выход. Ну и где здесь анализ?
        • 0
          Код не смотрел, но судя по принимаемому конструктором machina.Fsm аргументу, содержимое этого аргумента — и есть почти сто процентов кода КА. Не вполне понятно, что делает создаваемый объект, кроме того, что хранит конфиг и текущее состояние в придачу.
          • 0
            Подозреваю что вызывает хуки, хэндлит переходы, бойлерплейт уменьшает банально. Остается декларативное описание автомата и все.

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