Конечный автомат и его реализация на 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.
По мотивом раскритикованной статьи.

ссылка на оригинал статьи http://habrahabr.ru/post/274401/


Комментарии

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *