Конечные автоматы (FSM)
Конечные автоматы (Finite State Machines, FSM) - это математическая модель, которая описывает поведение системы, которая может находиться только в одном из конечного числа состояний в каждый момент времени.
Основные компоненты конечного автомата
- Состояния - конечный набор возможных состояний системы.
- События - действия, которые могут вызвать переход из одного состояния в другое.
- Переходы - функции, определяющие новое состояние на основе текущего состояния и события.
- Начальное состояние - состояние, в котором система находится до начала работы.
Визуализация конечного автомата
Конечные автоматы часто представляют в виде диаграмм состояний, где:
- Состояния изображаются как круги или прямоугольники
- Переходы изображаются как стрелки между состояниями
- Стрелки помечаются событиями, которые вызывают переход
Пример диаграммы простого автомата:
+-------+ TOGGLE +-------+
| |------------>| |
| ВЫКЛ | | ВКЛ |
| |<------------| |
+-------+ TOGGLE +-------+Преимущества использования конечных автоматов
1. Предсказуемость и строгая структура
FSM делает поведение системы предсказуемым и ясным. В каждый момент времени система находится в определенном состоянии, и переходы между состояниями чётко определены.
2. Управление сложностью
FSM позволяет разделить сложную логику на понятные дискретные состояния и правила перехода между ними.
3. Отладка и тестирование
Модель FSM упрощает отладку и тестирование, потому что:
- Состояния можно перечислить и проверить
- Переходы предсказуемы и детерминированы
- Легко понять, как система перешла в текущее состояние
4. Документирование поведения
Диаграммы состояний FSM могут служить наглядной документацией того, как должна работать система.
Применение конечных автоматов
Конечные автоматы широко используются в различных областях:
- UI компоненты: для управления состояниями интерфейса (открыт/закрыт, активен/неактивен)
- Бизнес-процессы: для моделирования рабочих процессов (новый, в работе, проверка, завершено)
- Протоколы связи: для управления соединениями (подключение, подключено, отключение)
- Игровые механики: для управления состояниями игровых объектов (простой, перемещение, атака)
- Парсеры и компиляторы: для разбора и анализа текста
Основные модели реакции на события
При проектировании конечных автоматов важно определить, как система будет реагировать на события. В теории автоматов выделяют две фундаментальные модели:
Автомат Мура
Выходные значения связаны с состояниями, а не с переходами. В концепции statecharts эта модель используется для действий, которые должны выполняться при входе в состояние или пока система находится в определенном состоянии. В lite-fsm эта концепция реализуется через эффекты, привязанные к состояниям:
const lightMachine = createMachine({
config: {
OFF: {
TOGGLE: "ON",
},
ON: {
TOGGLE: "OFF",
},
},
initialState: "OFF",
initialContext: { brightness: 0 },
effects: {
// Эффект, привязанный к состоянию ON (автомат Мура)
ON: ({ services }) => services.light.turnOn(),
},
});Автомат Мили
Выходные значения связаны с переходами, а не с состояниями. В statecharts это отражается в действиях, которые выполняются во время перехода между состояниями. Такой подход удобен, когда важно реагировать именно на изменение состояния или когда одинаковые события должны вызывать разные действия в зависимости от текущего состояния. В lite-fsm это реализуется через reducer, обрабатывающий конкретные события:
const counterMachine = createMachine({
config: {
IDLE: {
INCREMENT: "COUNTING",
},
COUNTING: {
INCREMENT: null,
},
},
initialState: "IDLE",
initialContext: { count: 0 },
reducer: (state, action) => {
// Эффект, привязанный к событию INCREMENT (автомат Мили)
if (action.type === "INCREMENT") {
state.context.count += 1;
return state;
}
return state;
},
});Ограничения базовых конечных автоматов
Простые конечные автоматы отлично подходят для моделирования несложных процессов, но при разработке реальных масштабных приложений они быстро сталкиваются с серьезными ограничениями:
Проблема взрыва состояний
Традиционные FSM имеют одну фундаментальную проблему - “взрыв состояний”. С ростом сложности приложения количество возможных комбинаций состояний растет экспоненциально. Например, в приложении с 5 независимыми булевыми флагами потребуется 2^5 = 32 отдельных состояния для описания всех возможных комбинаций. А если флагов 10, то уже понадобится 1024 состояния.
Нарастающая сложность переходов
В крупных приложениях очень быстро растет не только количество состояний, но и число возможных переходов между ними. Определение и поддержка всех этих переходов становится практически невозможной задачей.
Отсутствие повторного использования логики
В классических FSM сложно выделить повторяющиеся паттерны и переиспользовать их в различных частях приложения, что приводит к дублированию кода и увеличению шансов на ошибки.
Statecharts (Расширенные диаграммы состояний)
Расширенная модель statecharts (диаграммы состояний), предложенная Дэвидом Харелом, решает проблемы простых FSM, добавляя несколько ключевых концепций:
Примечание: Оригинальная статья Дэвида Харела “Statecharts: A Visual Formalism for Complex Systems” (1987) является фундаментальной работой, определившей концепцию statecharts. Для ознакомления также доступна свободная версия статьи в PDF .
Ключевые концепции Statecharts
1. Иерархия и вложенные состояния
Вложенные (иерархические) состояния позволяют группировать связанные состояния внутри родительских. Это критически важно для:
- Уменьшения сложности: Вместо линейного списка из сотен состояний - иерархическая структура, которую легче понять
- Наследования поведения: Дочерние состояния могут наследовать обработку событий от родительских состояний
- Модульности: Логика разных функциональных модулей может быть изолирована и разработана независимо
2. Параллельные состояния
Параллельные состояния позволяют моделировать независимые процессы, которые происходят одновременно:
- Независимые аспекты: Форма может одновременно находиться в состояниях “валидная” и “отправляется”
- Декомпозиция сложных систем: Разные части UI (панели, диалоги) могут иметь собственные жизненные циклы
- Предотвращение комбинаторного взрыва: Вместо создания отдельных состояний для каждой комбинации, можно моделировать независимые процессы отдельно
3. Контекст и данные
Расширенная модель включает хранение данных (контекста), что позволяет:
- Уменьшить количество состояний: Вместо создания отдельных состояний для каждого значения данных, можно хранить их в контексте
- Сохранять историю: Можно отслеживать предыдущие действия и принимать решения на их основе
- Принимать условные решения: Переходы могут зависеть от данных в контексте
4. Истории и самопереходы
- Истории позволяют вернуться к предыдущему активному состоянию после выхода и повторного входа
- Самопереходы дают возможность обрабатывать события без изменения состояния, но с обновлением контекста
Практические преимущества Statecharts
Применение statecharts и связанных концепций в крупных приложениях дает значительные преимущества:
- Лучшая масштабируемость: Возможность моделировать сложные системы без экспоненциального роста состояний
- Понятные границы ответственности: Четкое разделение между различными компонентами и их состояниями
- Устранение невозможных состояний: Структурные ограничения предотвращают попадание системы в “невозможные” состояния
- Прогнозируемое поведение: Легче отследить, как система перешла в определенное состояние
- Упрощение тестирования: Возможность тестировать отдельные компоненты системы независимо
- Документирование системы: Диаграмма statechart сама по себе является наглядной документацией поведения системы
Создание базового автомата
import { createMachine, MachineManager } from "lite-fsm";
// Определение автомата
const playerMachine = createMachine({
config: {
IDLE: {
WALK: "WALKING",
RUN: "RUNNING",
},
WALKING: {
STOP: "IDLE",
SPEED_UP: "RUNNING",
},
RUNNING: {
STOP: "IDLE",
SLOW_DOWN: "WALKING",
},
},
initialState: "IDLE",
initialContext: {
speed: 0,
direction: null,
},
});
// Создание менеджера
const manager = MachineManager({ player: playerMachine });
// Вызов перехода
manager.transition({ type: "WALK", payload: { direction: "north", speed: 3 } });Расширенные возможности и паттерны
Иерархические состояния через композицию
В lite-fsm иерархические состояния моделируются с помощью композиции автоматов:
// Вложенный автомат для состояний редактирования
const editingMachine = createMachine({
config: {
TEXT: {
SWITCH_MODE: "VISUAL",
SAVE: null,
},
VISUAL: {
SWITCH_MODE: "TEXT",
SAVE: null,
},
},
initialState: "TEXT",
initialContext: { content: "" },
});
// Основной автомат, который управляет текущим режимом работы
const documentMachine = createMachine({
config: {
VIEWING: {
EDIT: "EDITING",
},
EDITING: {
SAVE: "VIEWING",
CANCEL: "VIEWING",
},
},
initialState: "VIEWING",
initialContext: {},
});
// Объединение автоматов через менеджер
const manager = MachineManager({
document: documentMachine,
editor: editingMachine,
});Родительские состояния
Пример родительского состояния с дочерними:
// Автомат для общего состояния прогулки
const walkMachine = createMachine({
config: {
WAITING: {
LEAVE_HOME: "ON_WALK",
},
ON_WALK: {
ARRIVE_HOME: "WALK_COMPLETE",
},
WALK_COMPLETE: {
// Финальное состояние
},
},
initialState: "WAITING",
initialContext: {},
});
// Автомат для активности собаки во время прогулки (вложенное состояние)
const dogActivityMachine = createMachine({
config: {
INACTIVE: {
LEAVE_HOME: "WALKING", // Реагирует на событие родительского автомата
},
WALKING: {
SPEED_UP: "RUNNING",
ARRIVE_HOME: "INACTIVE", // Реагирует на событие родительского автомата
},
RUNNING: {
SLOW_DOWN: "WALKING",
ARRIVE_HOME: "INACTIVE", // Реагирует на событие родительского автомата
},
},
initialState: "INACTIVE",
initialContext: { speed: 0 },
reducer: (state, action) => {
switch (action.type) {
case "SPEED_UP":
state.context.speed += 2;
return state;
case "SLOW_DOWN":
state.context.speed = Math.max(1, state.context.speed - 1);
return state;
default:
return state;
}
},
});
// Объединяем автоматы в систему
const manager = MachineManager({
dogWalk: walkMachine,
dogActivity: dogActivityMachine,
});
// Начинаем прогулку - это событие обрабатывают оба автомата
manager.transition({ type: "LEAVE_HOME" });Параллельные состояния
Параллельные состояния реализуются через независимые автоматы:
// Автомат, отвечающий за воспроизведение
const playbackMachine = createMachine({
config: {
PLAYING: {
PAUSE: "PAUSED",
},
PAUSED: {
PLAY: "PLAYING",
},
},
initialState: "PAUSED",
});
// Автомат, отвечающий за параметры звука
const audioMachine = createMachine({
config: {
MUTED: {
UNMUTE: "UNMUTED",
},
UNMUTED: {
MUTE: "MUTED",
VOLUME_CHANGE: null,
},
},
initialState: "UNMUTED",
initialContext: { volume: 50 },
});
// Объединение параллельных автоматов через менеджер
const manager = MachineManager({
playback: playbackMachine,
audio: audioMachine,
});Самопереходы
Самопереходы позволяют обрабатывать события без изменения состояния:
// Автомат выпрашивания лакомства собакой
const dogBeggingMachine = createMachine({
config: {
BEGGING: {
GETS_TREAT: null, // Самопереход - собака остается в состоянии BEGGING
GO_AWAY: "IDLE",
},
IDLE: {
SEE_FOOD: "BEGGING",
},
},
initialState: "IDLE",
initialContext: { treatsReceived: 0 },
reducer: (state, action) => {
// Обработка события GETS_TREAT увеличивает счетчик полученных лакомств
if (action.type === "GETS_TREAT") {
state.context.treatsReceived += 1;
return state;
}
return state;
},
});Финальные состояния
Финальные состояния моделируются как состояния без исходящих переходов:
const processMachine = createMachine({
config: {
IDLE: {
START: "PROCESSING",
},
PROCESSING: {
COMPLETE: "COMPLETED",
ERROR: "FAILED",
},
COMPLETED: {
// Финальное состояние - нет исходящих переходов
},
FAILED: {
RETRY: "PROCESSING",
},
},
initialState: "IDLE",
});Условные переходы
Условные переходы реализуются с помощью reducer:
const authMachine = createMachine({
config: {
CHECKING: {
AUTH_SUCCESS: "AUTHENTICATED",
AUTH_FAILURE: "ERROR",
},
AUTHENTICATED: {
LOGOUT: "LOGGED_OUT",
},
ERROR: {
RETRY: "CHECKING",
},
LOGGED_OUT: {
LOGIN: "CHECKING",
},
},
initialState: "CHECKING",
reducer: (state, action) => {
// Условная логика переходов на основе данных в payload
if (action.type === "AUTH_SUCCESS" && action.payload?.role === "admin") {
return {
state: "AUTHENTICATED",
context: {
...state.context,
isAdmin: true,
user: action.payload.user,
},
};
}
return state;
},
});Заключение
Моделирование поведения с помощью конечных автоматов и statecharts предоставляет мощные инструменты для создания надежных и предсказуемых приложений. Каждый из этих подходов имеет свои преимущества и может быть выбран в зависимости от сложности задачи.
Хотя lite-fsm не предоставляет прямую поддержку всех возможностей statecharts в одном автомате (таких как вложенные состояния в рамках одного автомата), библиотека предлагает гибкий и легковесный способ моделирования сложного поведения через композицию автоматов, разделение ответственности и систему эффектов.