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

в 16:35, , рубрики: 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.
По мотивом раскритикованной статьи.

Автор: ekubyshin

Источник

Поделиться новостью

* - обязательные к заполнению поля