Автоматное программирование: состояние как явная величина

Откройте любой сервис, который прожил три года, и найдите там сущность «Заказ». С высокой вероятностью в ней будет что-то подобное:

class Order:
    is_submitted: bool
    is_paid: bool
    is_shipped: bool
    is_cancelled: bool
    payment_failed: bool
    refund_requested: bool

Шесть булевых полей — это 2^6 = 64 комбинации. Легальных среди них штук восемь. Остальные пятьдесят шесть — это баги, которые ещё не случились: заказ одновременно отменённый и отгруженный, оплаченный с payment_failed = true, возврат по неоплаченному. Ни один тип, ни один тест и ни одно код-ревью не запрещают им возникнуть, потому что запрет негде записать: он существует только в голове человека, который писал первую версию и уже уволился.

Автоматное программирование — это парадигма, отвечающая на этот класс проблем ровно одним ограничением: состояние системы — это одно значение из конечного перечислимого множества, а всё поведение — тотальная функция от пары «состояние, событие». Вы теряете право писать if (order.is_paid && !order.is_cancelled) где угодно в коде. Взамен получаете гарантию, которую невозможно получить дисциплиной: несуществующее состояние нельзя выразить, а необработанное сочетание нельзя не заметить.

Это та же сделка, что в обзорной статье трека — свобода в обмен на гарантию. Просто предмет сделки здесь самый дорогой из всех: контроль над состоянием, который в императивной парадигме размазан по всей программе.

Что именно отнимает и что даёт автоматная парадигма

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

Немного истории: почему это старше и живее, чем кажется

Три факта из этой истории стоит держать в голове.

Первый: самые надёжные протоколы, которыми вы пользуетесь каждую секунду, специфицированы как автоматы. TCP в RFC 793 описан диаграммой состояний (LISTEN, SYN-RECEIVED, ESTABLISHED, FIN-WAIT-1 и так далее), TLS 1.3 в RFC 8446 — тоже. Причина не в любви к формализму: между двумя машинами нет общей памяти и общего стека, договориться можно только о состояниях и переходах.

Второй: statecharts Харела (оригинальная статья 1987 года) появились не из академического интереса, а из авионики: плоский автомат истребителя разрастался до сотен состояний, и Харел добавил три вещи — вложенность, параллельные регионы и историю. Это единственное известное лекарство от комбинаторного взрыва переходов, и оно работает до сих пор.

Третий: в русскоязычной инженерной школе это направление известно как автоматное программирование (SWITCH-технология А. А. Шалыто, сайт проекта) — там же лежит большая коллекция разборов промышленных задач в этом стиле.

Модель: тотальная функция переходов

Формально автомат — это пятёрка (S, E, s0, δ, F): множество состояний, множество событий, начальное состояние, функция переходов и множество финальных состояний. Практически важна только δ, и важно в ней одно слово: тотальная.

δ : S × E → S × Effects

Тотальная означает, что для каждой из |S| × |E| пар определён результат. Не «мы обработали интересные случаи», а все. Для заказа с восемью состояниями и восемью событиями это 64 клетки. Из них реально осмысленных — 14. Остальные 50 — это ответ на вопрос «что делать, если пришла оплата по уже отменённому заказу», и ответ должен быть записан явно: игнорировать, вернуть ошибку, положить в очередь разбора, инициировать возврат. Именно эти 50 клеток и есть та часть системы, которая в обычном коде существует в виде «ну, такого не бывает».

Две классические модели различаются местом эффекта:

• Автомат Мили — эффект привязан к переходу: «при событии payment_ok в состоянии awaiting_payment — списать резерв и отправить письмо».
• Автомат Мура — эффект привязан к состоянию: «войдя в paid, отправить письмо».

На практике почти всегда удобнее Мили: реакция обычно зависит и от того, откуда пришли. Но у Мура есть важное преимущество в распределённом мире — эффекты «при входе в состояние» проще делать идемпотентными, потому что их можно переисполнить при восстановлении, зная только текущее состояние.

Вот минимальная модель жизненного цикла заказа. Обратите внимание, что каждая стрелка подписана событием, а не намерением: submit, а не «пользователь захотел».

Диаграмма читается за минуту, и в этом её главная ценность: она одинаково понятна разработчику, тестировщику, аналитику и поддержке. Тот же смысл, записанный вложенными if, не понятен никому, включая автора через полгода.

Таблица переходов как данные

Самая частая реализация автомата — switch внутри метода. Она работает, но теряет главное преимущество парадигмы: модель перестаёт быть данными. Правильнее хранить переходы в структуре, которую можно обойти программно. Это частный случай приёма «правила как данные» — подробный разбор в статье Правила как данные.

from dataclasses import dataclass, replace
from enum import Enum
from typing import Callable

class State(str, Enum):
    DRAFT = "draft"
    AWAITING_PAYMENT = "awaiting_payment"
    PAID = "paid"
    SHIPPED = "shipped"
    DELIVERED = "delivered"
    REFUNDING = "refunding"
    REFUNDED = "refunded"
    CANCELLED = "cancelled"

class Event(str, Enum):
    SUBMIT = "submit"
    PAYMENT_OK = "payment_ok"
    PAYMENT_FAILED = "payment_failed"
    SHIP = "ship"
    DELIVER = "deliver"
    CANCEL = "cancel"
    REFUND_OK = "refund_ok"
    TIMEOUT = "timeout"

@dataclass(frozen=True)
class Order:
    """Данные автомата. Неизменяемые: переход возвращает НОВОЕ значение."""
    state: State
    attempts: int = 0
    amount: int = 0          # в копейках, чтобы не связываться с float

@dataclass(frozen=True)
class Effect:
    """Намерение, а не действие. Исполняется снаружи, в оболочке."""
    kind: str
    payload: dict

Transition = Callable[[Order, dict], tuple[Order, list[Effect]]]
TABLE: dict[tuple[State, Event], Transition] = {}

def on(state: State, event: Event):
    """Регистрация клетки таблицы. Дубликат — ошибка на импорте модуля."""
    def deco(fn: Transition) -> Transition:
        key = (state, event)
        if key in TABLE:
            raise AssertionError(f"переход {state}/{event} уже определён")
        TABLE[key] = fn
        return fn
    return deco

@on(State.DRAFT, Event.SUBMIT)
def _(order: Order, data: dict):
    return (replace(order, state=State.AWAITING_PAYMENT),
            [Effect("reserve_stock", {"amount": order.amount}),
             Effect("charge", {"amount": order.amount})])

@on(State.AWAITING_PAYMENT, Event.PAYMENT_OK)
def _(order: Order, data: dict):
    return replace(order, state=State.PAID), [Effect("capture", {})]

@on(State.AWAITING_PAYMENT, Event.PAYMENT_FAILED)
def _(order: Order, data: dict):
    # Условный переход — единственное место, где сравниваются счётчики.
    if order.attempts + 1 < 3:
        return replace(order, attempts=order.attempts + 1), [Effect("retry_charge", {})]
    return replace(order, state=State.CANCELLED), [Effect("release_stock", {})]

@on(State.PAID, Event.SHIP)
def _(order: Order, data: dict):
    return replace(order, state=State.SHIPPED), [Effect("notify_customer", {})]

class IllegalTransition(Exception):
    pass

def step(order: Order, event: Event, data: dict | None = None) -> tuple[Order, list[Effect]]:
    """Чистая функция: ни базы, ни времени, ни сети. O(1) по времени."""
    fn = TABLE.get((order.state, event))
    if fn is None:
        raise IllegalTransition(f"{event} недопустимо в состоянии {order.state}")
    return fn(order, data or {})

Сложность перехода — O(1) по времени (поиск в словаре) и O(|S| * |E|) по памяти для таблицы в худшем случае, что для восьми состояний и восьми событий означает 64 записи, то есть ничто. Ради полноты картины: даже автомат в тысячу состояний и сотню событий — это сто тысяч возможных клеток, а реально заполненных обычно на два порядка меньше, потому что таблица разрежена.

Теперь то, ради чего всё затевалось, — тест на полноту. Он не проверяет логику, он проверяет, что вы подумали обо всех клетках:

import itertools

# Явный реестр «известно-недопустимых» пар: не забыли, а решили отвергать.
FORBIDDEN = {
    (State.DELIVERED, Event.CANCEL),
    (State.CANCELLED, Event.PAYMENT_OK),   # оплата пришла после отмены -> см. политику ниже
    # ... остальные 48 пар
}

def test_transition_table_is_total():
    missing = []
    for s, e in itertools.product(State, Event):
        if (s, e) not in TABLE and (s, e) not in FORBIDDEN:
            missing.append((s.value, e.value))
    assert not missing, f"клетки без решения: {missing}"

Этот тест падает каждый раз, когда кто-то добавляет новое состояние или новое событие — и это его работа. В обычном коде добавление статуса не ломает ничего до продакшена; здесь оно ломает сборку и требует явно проговорить, что делать с каждым событием в новом состоянии.

Кстати, про клетку (CANCELLED, PAYMENT_OK): она бывает в проде постоянно. Платёжный провайдер подтверждает списание через минуту после того, как ваш таймаут отменил заказ. Правильный ответ — не «игнорировать», а «перейти в Refunding». Без матрицы такие клетки обнаруживаются только в чате поддержки.

Эффекты наружу: почему переход должен быть чистым

Соблазн написать send_email() прямо внутри перехода огромен. Но как только вы это сделали, автомат перестал быть тестируемым без моков, перестал быть воспроизводимым и стал непригоден для повторного проигрывания истории.

Дисциплина ровно такая же, как в схеме «функциональное ядро, императивная оболочка» из статьи про ФП: решение отдельно, действие отдельно.

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

Состояние в типе: автомат, который проверяет компилятор

Таблица переходов ловит ошибки в рантайме. Систему типов можно заставить ловить их на компиляции: если поля, доступные в состоянии Paid, физически отсутствуют в Draft, то order.payment_id в черновике просто не скомпилируется.

// Размеченное объединение: у каждого состояния — СВОИ поля.
type Order =
  | { status: "draft"; items: Item[] }
  | { status: "awaitingPayment"; items: Item[]; invoiceId: string; attempts: number }
  | { status: "paid"; items: Item[]; paymentId: string }
  | { status: "shipped"; items: Item[]; paymentId: string; trackingId: string }
  | { status: "cancelled"; reason: string };

// Функция принимает не «Order», а конкретное состояние.
// Вызвать ship() для черновика невозможно: не тот тип.
function ship(order: Extract<Order, { status: "paid" }>, trackingId: string): Order {
  return { status: "shipped", items: order.items, paymentId: order.paymentId, trackingId };
}

// Проверка полноты: при добавлении нового варианта компилятор ткнёт сюда.
function describe(order: Order): string {
  switch (order.status) {
    case "draft": return "черновик";
    case "awaitingPayment": return `ждём оплату, попытка ${order.attempts}`;
    case "paid": return `оплачен ${order.paymentId}`;
    case "shipped": return `в пути ${order.trackingId}`;
    case "cancelled": return `отменён: ${order.reason}`;
    default: {
      const _exhaustive: never = order;   // ошибка компиляции при новом статусе
      return _exhaustive;
    }
  }
}

В языках с линейными типами это доводится до предела — паттерн typestate, когда состояние закодировано в параметре типа, а переход потребляет старое значение:

use std::marker::PhantomData;

struct Draft;
struct Paid;
struct Shipped;

struct Order<S> {
    id: u64,
    _state: PhantomData<S>,
}

impl Order<Draft> {
    // self по значению: старый Order<Draft> после вызова недоступен.
    fn pay(self, _payment_id: &str) -> Order<Paid> {
        Order { id: self.id, _state: PhantomData }
    }
}

impl Order<Paid> {
    fn ship(self, _tracking: &str) -> Order<Shipped> {
        Order { id: self.id, _state: PhantomData }
    }
}

// order.ship() для Order<Draft> — не «ошибка в рантайме», а «нет такого метода».

Цена типизированного автомата честная и её надо знать. Во-первых, состояние в типе не переживает границу процесса: загрузив заказ из базы, вы получаете Order в неизвестном состоянии и обязаны сузить его разбором (match) — типы работают внутри одного вычисления, а не между рестартами. Во-вторых, число вариантов кода растёт: каждое состояние — свой тип, свои конструкторы, своя сериализация. Практическое правило: типизируйте автомат там, где переходы происходят в памяти в рамках одной операции (протокол соединения, сборка запроса, конечный автомат парсера), и используйте таблицу с проверками в рантайме там, где экземпляр живёт неделями в базе. Подробнее о технике «сделать некорректные состояния невыразимыми» — в статьях Типы вместо паттернов и Моделирование типами.

Statecharts: лекарство от взрыва переходов

Плоский автомат ломается на масштабе. Добавьте в устройство глобальное событие «выключить питание», и вам придётся нарисовать стрелку из каждого из сорока состояний. Добавьте второе такое событие — восемьдесят стрелок. Это и есть комбинаторный взрыв, из-за которого автоматы имели репутацию «академической игрушки» до 1987 года.

Харел добавил три конструкции, и все три есть в UML, XState и SCXML.

Иерархия (вложенные состояния). Переход, нарисованный на родителе, действует для всех детей. «Выключить питание» рисуется один раз.

Ортогональные регионы. Система находится в нескольких состояниях одновременно, но по разным осям: соединение — отдельная ось, запись — отдельная. Вместо произведения 4 × 3 = 12 состояний вы описываете 4 + 3 = 7.

История. Возврат в составное состояние восстанавливает подсостояние, в котором вышли, — без ручного хранения «где я был».

Внутри Online два независимых региона: канал (Idle/Streaming) и запись (NotRecording/Recording). Событие link_lost описано один раз на границе составного состояния и работает для любой комбинации внутри. Плоский эквивалент потребовал бы четырёх состояний и четырёх стрелок наружу.

Практическое ограничение: ортогональные регионы соблазняют размножать оси. Если у вас их пять — вы, скорее всего, моделируете не автомат, а набор независимых сущностей, и их лучше разнести физически. Хорошая эвристика — не больше двух-трёх регионов на составное состояние.

Время как событие

Автомат ничего не знает о часах — и это его сила. Таймаут в автоматной парадигме моделируется не «спящим потоком», а обычным событием timeout, которое кто-то снаружи планирует и доставляет.

Следствия сугубо практические:

• Детерминизм тестов. Прогон «сутки бездействия» — это одна строка step(order, Event.TIMEOUT), а не sleep. Виртуальное время бесплатно.
• Единая точка политики. Таймер ставится тем же исполнителем эффектов, что и письма: переход возвращает Effect("schedule", {"event": "timeout", "after_s": 900}).
• Отмена по построению. Устаревший таймер, доставленный после перехода, попадёт в клетку, где он не описан, и будет отвергнут — вместо того чтобы «сработать не вовремя».

Это тот же приём, который в конкурентной парадигме называется «вынести источник недетерминизма на границу»; подробнее — в статье про конкурентные модели.

Долгоживущие автоматы: персистентность, идемпотентность, версии

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

Четыре правила, без которых долгоживущий автомат в проде не выживает:

1. Одно место хранения истины. Состояние живёт в базе, а не в памяти обработчика. Если оно продублировано в кеше — вы получите два автомата, которые разъедутся.
2. Дедупликация по идентификатору события. Доставка «хотя бы один раз» — норма для брокеров и вебхуков; см. идемпотентность и доставку.
3. Версионирование модели. В момент выката в системе есть тысячи экземпляров «в полёте». Новое состояние добавлять безопасно, удалять — нет: сначала выкатывается код, умеющий читать старые состояния, потом мигрируются экземпляры. Хранить версию автомата рядом с состоянием — дешёвая страховка.
4. Явное состояние компенсации. Отмена оплаченного заказа — это не «вернуться в Draft», а отдельная ветка Refunding → Refunded. Автоматная модель делает это требование видимым; ветку компенсаций забывают ровно тогда, когда её негде нарисовать.

На этой же идее построены движки долговременного исполнения (Temporal, Cadence, AWS Step Functions, Camunda): вы описываете процесс, движок хранит состояние и гарантирует, что после падения выполнение продолжится с того же места. Обратная сторона медали — ваш процесс становится куском чужого рантайма со своими правилами детерминизма. Родственная тема — саги и распределённые транзакции, разобранные в архитектурных паттернах и в BPMN.

Проверяемость: главный бонус парадигмы

Поскольку модель — это граф, к ней применимы алгоритмы на графах. Это редкая ситуация, когда «проверить программу» означает буквально «обойти структуру данных».

Первые три проверки пишутся за час и стоят копейки — их надо иметь в каждом проекте, где есть автомат. Генерация тестов обходом графа даёт «бесплатный» набор сценариев: находите все простые пути от начального состояния до финальных и превращаете каждый в тест. Формальная верификация нужна редко, но когда нужна — работает: разбор практики TLA+ в Amazon есть в статье про тестирование распределённых систем, а теоретическая база автоматов и языков — в треке по математике.

Отдельный приём, который стоит знать: проверка эквивалентности двух автоматов. Если вы переписываете легаси, старую и новую модель можно прогнать на одинаковых последовательностях событий и сравнить траектории. Это не тест «поведения» в общем смысле — это доказательство на конкретном множестве путей, и получить его дёшево можно только потому, что поведение выражено данными.

Где это работает в проде

• Сетевые протоколы. TCP, TLS, HTTP/2, WebSocket — все специфицированы как автоматы, и реализации следуют спецификации буквально.
• Платежи и заказы. Любая система с деньгами имеет автомат в ядре, признаёт она это или нет. Разница только в том, нарисован он или размазан по if.
• CI/CD и оркестраторы задач. Джоба: queued → running → succeeded / failed / cancelled, с ретраями и таймаутами.
• Встраиваемые системы. В RTOS автомат — основной способ писать обработчики без динамической памяти: таблица переходов помещается во flash, состояние — в один байт.
• UI. XState принёс statecharts во фронтенд именно ради борьбы с флагами isLoading/isError; связанный разбор — в статье про управление состоянием.
• Игровой ИИ. Поведение NPC — классический иерархический автомат (сейчас чаще behaviour tree, но идея та же: поведение как данные).

Автоматы среди других парадигм трека

Автоматная парадигма редко бывает единственной — она встраивается в другие как дисциплина работы с состоянием.

Разница с реконсиляцией стоит отдельного абзаца, потому что её постоянно путают. Автомат отвечает на вопрос «какие переходы разрешены», контроллер — на вопрос «как прийти к цели из любого состояния». Если у вас есть требования вида «нельзя отгрузить неоплаченный заказ», нужен автомат. Если требование звучит как «в конце концов должно быть три реплики», нужна реконсиляция.

Типичные ошибки

1. Флаги вместо состояний. Первый и главный симптом: булево поле, которое имеет смысл только вместе с другим булевым полем.
2. Эффекты внутри перехода. Убивает тестируемость и делает повторное проигрывание невозможным.
3. Необъявленные переходы «по-тихому». except KeyError: pass в обработчике — это гарантированный молчаливый пропуск оплаты в проде.
4. Состояние в двух местах. В базе paid, в кеше awaiting_payment. Дальше всё зависит от того, кого спросили.
5. Плоский автомат на сорок состояний. Симптом отсутствия иерархии; лечится вложенными состояниями, а не увеличением монитора.
6. Переход, зависящий от внешнего вызова. if payment_service.check(): ... внутри step() — переход перестал быть чистым и воспроизводимым. Сначала получите факт снаружи, потом подайте его событием.
7. Отсутствие ветки компенсации. «Отменить оплаченный» — это не обратная стрелка, это отдельный путь с деньгами.
8. Автомат ради автомата. Для сущности с двумя состояниями (active/archived) вся эта машинерия — оверинжиниринг. Порог окупаемости — примерно от четырёх состояний либо от первого случая, когда легальность перехода зависит от истории.

Мини-итог

1. Автоматная парадигма меняет свободу писать произвольные условия по флагам на гарантию, что невалидное состояние невыразимо, а необработанное сочетание видно.
2. Функция переходов должна быть тотальной: не «интересные случаи», а все |S| × |E| клеток, включая «оплата пришла после отмены».
3. Переход — чистая функция, возвращающая новое состояние и описание эффектов. Эффекты исполняет оболочка, атомарно с сохранением состояния.
4. Модель — это данные: её можно нарисовать, обойти графом, проверить на достижимость и превратить в тесты. Именно это отличает автомат от switch.
5. Против взрыва переходов работают три конструкции Харела: иерархия, ортогональные регионы, история.
6. Для короткоживущих автоматов сильнее типы (typestate, размеченные объединения); для долгоживущих — таблица плюс дедупликация, версии и явные компенсации.
7. Автомат почти всегда живёт внутри другой парадигмы: как дисциплина состояния внутри актора, как интерпретатор потока событий, как ядро саги.

Источники

• David Harel. Statecharts: A Visual Formalism for Complex Systems, 1987 — первоисточник иерархических автоматов.
• RFC 793 (TCP) и RFC 8446 (TLS 1.3) — промышленные спецификации протоколов как автоматов.
• А. А. Шалыто. Автоматное программирование и SWITCH-технология — материалы и разборы промышленных задач.
• XState / Stately — statecharts в JS/TS, визуальный редактор и генерация тестов по модели.
• W3C SCXML — стандартная XML-нотация автоматов, реализованная в Qt, Apache Commons SCXML и других.
• Temporal и AWS Step Functions — долговременное исполнение процессов.
• Richard Feldman. Making Impossible States Impossible — доклад про моделирование состояния типами.
• Robert Virding, Joe Armstrong et al. OTP gen_statem — автомат как стандартный примитив рантайма BEAM.

Что дальше

Автомат делает явным состояние. Следующая статья делает явным то, что через это состояние течёт: Программирование, ориентированное на данные — почему «отделить данные от кода» и «разложить данные под кэш» оказались одной идеей, и что из этого следует для обычного бэкенда.