Я много и часто говорю о том, что есть принципиальное различие между конечным автоматом и полем «state» в базе данных. Я даже уже отчасти писал про это, но акценты в том тексте были на другом, поэтому я решил посвятить целые полчаса собственной жизни кристаллизации тезисов о правильных конечных автоматах и их реализации в CS.
Так повелось, что математики ограничились применением конечных автоматов к алфавитам, а прикладники тем временем увидели знакомое слово «состояние» и со свойственным всем нам верхоглядством решили, что набор «состояний» и «переходов» — это и есть конечный автомат. Всем, наверное, доводилось видеть такой код:
void transition(state, event) {
switch(state) {
case IDLE:
this.state = WORKING;
doWork(event);
this.state = DONE;
break;
case DONE:
doReset();
this.state = IDLE;
break;
default:
terminate();
}
}Не «Рождение Венеры» Ботичелли, конечно, но функцию свою выполняет. Выполняет ведь? А кто может указать на одну архитектурную и одну критическую ошибку, которая завтра испортит тот объект, который этот автомат обслуживает?
Один переход — одно состояние
Архитектурная ошибка понятна: чтобы оказаться в состоянии DONE (как и в любом другом) — нужен переход, инициированный ивентом, а не вот это вот. В принципе, хотя такой подход, как в коде выше, и противоречит математическому определению конечного автомата, его, вроде бы, можно стерпеть.
На самом деле нет. Представьте себе, что рядом с вами работает умный ленивый человек, который решил втайне от вас сохранять состояние в базу. Естественно, он не станет лезть в ваш код и высылать вам на ревью PR с +18000-12000. Он прикрутит аспект на изменение состояния. Который обновит в базе state каждый раз, когда он устанавливается в новое значение в коде.
Если однажды doWork упадёт, то в базе останется значение состояния «WORKING», и код выше для данного объекта теперь всегда будет выходить в terminate. Если вы считаете, что от таких досадных недоразумений должен защищаться программист — мне вас жаль. Переложите такие задачи на компилятор — и у вас высвободится вагон свободного времени, чтобы собственноручно писать код, а не делегировать это развлечение LLM-ке.
Вообще говоря, рассчитывать на то, что правильный работоспособный код будет получаться стараниями разработчика — глупость, граничащая с преступлением. Вон даже создатели раста это понимают.
Гонка
Как бы мы ни стремились замедлить прогресс созданием однопоточного кода, мир отвоёвывает своё. Когда я вкатывался в профессию, понятие thread-safe в прикладном программировании было известно нескольким фрикам, и то — понаслышке. Когда я стал писать более-менее внятный код, все без исключения сторонние библиотеки тщательно оговаривались в README: «вот тут thread-safe, тут — не thread-safe, а тут — рыбу заворачивали». Сегодня писать не thread-safe код — фактически саботаж.
Код выше, будучи вызван в конкурентной среде, может передать управление другому потоку между строками 4 и 5. Вот тут:
this.state = WORKING;
// что-то я устал, перекур, давайте пока без меня
doWork(event);А другой поток — может запросто инициировать переход на этом же объекте. Хоба! — и второй поток проник в switch, состояние (установленное первым потоком) — WORKING, — и вот второй поток уже вызывает terminate. Тут город засыпает, и просыпается маф^W первый поток. Хоба! И мы вызываем doWork на терминированном объекте. Буквально на ровном месте, причем.
У этого кода есть и третий, чуть менее явный огрех.
Состояние может изменяться только переходами
Ух, и не сосчитать, сколько раз мне доводилось видеть в чужом коде заплатки (потому что бизнес не ждет, а правильно делать — долго) наподобие внезапной переустановки состояния вопреки любой мыслимой и немыслимой логике, где-нибудь через двести строк от определения функции transition:
void prepareReport() {
State state = this.state;
// «буквально на секундочку сделаем эту дорогу двусторонней», —
// как говорил мой дядька, сворачивая под кирпич
this.state = WORKING; // чтобы правильно посчитались суммы
… // do a report
this.state = state;
}Хоба! И наша сущность на час (это небыстрый отчет) переходит во временное состояние WORKING.
Я утрирую, конечно. Общеизвестно, что мы, разработчики, крайне ответственно относимся к контрактам, добавляем код только корректным, правильным образом — и вообще никогда не допускаем ошибок. Поэтому мы выставим мьютексы, будем определять состояния только переходами, никогда не станем менять внутренний стейт ad-hoc, и понапишем корректных тестов на любой случай, предусмотрев все возможные и невозможные сценарии.
Из последнего анекдота, кстати, родился популярный среди недалеких людей тезис о «комбинаторном взрыве» при проектировании логики на конечных автоматах. Количество возможных переходов невозможно элегантно ограничить, если в качестве состояния использовать просто поле в структуре.
Как всего этого избежать?
Мне неизвестен способ изящнее, чем запускать легковесный процесс (гринтред, корутину, горутину) на каждый экземпляр конечного автомата и обрабатывать входящие запросы — как сообщения в акторной модели. Этого можно добиться и вне акторной модели: тогда на функции/методе transition просто должен висеть мьютекс (наподобие synchronised в джаве). Это, правда, не спасет от непреднамеренного саботажа — от установки поля вручную в обход синхронизированного метода. В акторной модели — вам не придется об этом даже думать. Процесс не может обрабатывать больше одного сообщения одновременно. Там очередь. А внутреннее состояние процесса невозможно изменить извне. Поэтому гарантии консистентности вы получаете просто из коробки.
Вообще говоря, на этом подарки, которые мог бы преподнести разработчику компилятор, — не заканчиваются. Можно было бы проверять такие мелочи, как наличие начального состояния, обязательного для конечного автомата, хотя бы одного конечного, отсутствие сирот… Можно было бы сообщить обо всех циклических «путях», о кратчайших путях достижения конечного состояния, а еще можно было бы нарисовать mermaid-диаграмму и прицепить её к документации. И это всё вполне может сделать компилятор. Я уже рассказывал про свою библиотеку Finitomata, в которой все эти плюшки реализованы. Сейчас я просто на пальцах покажу, как добиться всех тех же гарантий можно на чистых процессах.
Процесс в эрланге — готовый конечный автомат
Директива use GenServer превращает код модуля в процесс, который умеет отвечать на синхронные и асинхронные сообщения — для этого всего лишь надо реализовать соответствующие колбэки. Вот пример (упрощенный) для турникета.
```
defmodule Turnstile do
use GenServer
@impl GenServer
def init(_), do: {:ok, {:closed, 0}}
@impl GenServer
def handle_cast(:coin, {_, coins}),
do: {:noreply, {:open, coins + 1}}
def handle_cast(:walk, {:open, 1}),
do: {:noreply, {:closed, 0}}
def handle_cast(:walk, {:open, coins}),
do: {:noreply, {:open, coins - 1}}
def handle_cast(action, {state, coins}) do
require Logger
Logger.error("Prohibited action ‹#{action}› in state ‹#{state}›")
{:noreply, {state, coins}}
end
endВсё. Паттерн-матчинг в трёх clauses одной и той же функции разруливает любые действия. Тут немного кода, попробуйте сами проверить, не напортачил ли я с логикой.
Вот так это выглядит в iex (REPL):
iex|?|2 ▶ {:ok, pid} = GenServer.start_link(Turnstile, :ok)
{:ok, #PID<0.115.0>}
iex|?|3 ▶ GenServer.cast(pid, :walk)
16:59:10.631 [error] Prohibited action ‹walk› in state ‹closed›
iex|?|4 ▶ GenServer.cast(pid, :coin)
iex|?|5 ▶ GenServer.cast(pid, :walk)
iex|?|6 ▶ GenServer.cast(pid, :coin)
iex|?|7 ▶ GenServer.cast(pid, :coin)
iex|?|8 ▶ GenServer.cast(pid, :coin)
iex|?|9 ▶ :sys.get_state(pid)
{:open, 3}Один у вас процесс, или их миллион — ничего не изменится. Обработка сообщений из mailbox — будет производиться последовательно, одно за другим. Состояние всегда будет консистентным.
Но что будет, если процесс упадёт? Его перезапустит его супервизор, с начальным состоянием, что нормально для 99% случаев. Но если он упадёт сразу после того, как щедрый Вася отгрузил в монетоприёмник 10 жетонов, Вася может расстроиться. Есть три распространенных варианта решения этой проблемы: ① использовать мою библиотеку peeper, ② хранить состояние в ETS с правильно установленным heir (здесь это немного выходит за рамки темы текста, в библиотеке выше есть реализация), или ③ писать в базу.
Последний вариант — скорее всего необходим для жетонов стоимостью с крыло боинга каждый, но в случае метро — обычно лучше обойтись одним из первых двух.
Удачного конечного автоматизирования!
Комментарии (52)
kmatveev
20.05.2025 18:56Мне кажется, что есть ещё третья ошибка, возникающая при программировании конечных автоматов, от которой спасают акторы. Я называю её "object reentrancy". Суть вот в чём: функция или метод, принимающая событие, должна сделать две вещи: поменять состояние, и выполнить всякие side effect-ы. Представим, что она это делает в таком порядке: сначала выполняет сайд-эффекты, а потом меняет состояние. Если side effect - это синхронный вызов, то в его процессе может породиться новое событие, и в том же потоке выполнения снова вызовется метод, принимающий событие. Но состояние-то осталось старым! Потом эта цепочка начнёт раскручиваться, и состояния начнут обновляться задом наперёд. Mutex-ы не спасут, они обычно позволяют себя повторно захватить потоку, который ими и так уже владеет.
В ООП есть понятие "class invariant". Это нормально, что внутри метода этот инвариант временно ломается, пока это не наблюдаемо извне. Но если метод временно передаёт управление, например в какой-нибудь callback, пока инвариант сломан, то возможна неожиданная жопа. Я с таким сталкивался, когда у меня несколько стейт-машин общались друг с другом.
Поэтому для конечных автоматов есть два варианта: или дисциплина "сначала меняем состояние, потом выполняем остальные действия", или все события только через очередь. Мне больше нравится первый вариант, очень люблю сквозную отладку.
Dhwtj
20.05.2025 18:56сначала меняем состояние, потом выполняем остальные действия
3 способа есть
Просто синхронно вызвать (state → side-effect в том же стеке, lock для атомарности)
Outbox (state и «что отправить» коммитятся вместе)
Saga / In-Progress
state=InProgress; call remote; on OK → state=Done; on Fail → Rollback|Retry.
Нужна логика повтора/компенсации, зато нет общей БД.
«Сначала state, потом эффекты» это верно, но способы доставки/исполнения эффектов дают три варианта (стек, outbox, saga).
cupraer Автор
20.05.2025 18:56логика повтора/компенсации
В конечном автомате? Вы там на тяжелых наркотиках, что ли?
Dhwtj
20.05.2025 18:56А... Понял
В терминах Сага (императивно) это Retry/Rollback
В терминах конечного автомата (декларативно) это переход в состояние need retry / need rollback
cupraer Автор
20.05.2025 18:56А кто толкнет дальше из need состояния?
Dhwtj
20.05.2025 18:56сервис подписчик
cupraer Автор
20.05.2025 18:56Какой еще сервис? Уже и сервис нарисовался? А хотели ведь мирно без гостей посидеть.
Dhwtj
20.05.2025 18:56В акторной можно всё в одном
В ФП кто-то должен толкнуть
В ООП всё плохо когда его дёргают из нескольких потоков управления. Своего потока управления в ООП нет и начинается хаос. А в акторной модели свой поток управления за счёт очереди и может ещё чего то.
cupraer Автор
20.05.2025 18:56Да, просто за счет очереди и изолированного пространства. Инкапсуляция по-взрослому: не существует способа её нарушить.
Это реализуемо, конечно, и в ФП, и в ООП, но за счет дополнительных «сервисов» (что и ладно бы) — но вдобавок оно не страхует от ошибок разработчика, а вот это уже — труба для прикладного языка.
Dhwtj
20.05.2025 18:56Намекаете, что конечный автомат декларативен до мозга костей и императивные действия не царское его дело?
cupraer Автор
20.05.2025 18:56сначала меняем состояние, потом выполняем остальные действия
А если «остальное действие» не выполнилось? Просто не смогло по независящим от нас причинам? Выбросило исключение?
Siemargl
20.05.2025 18:56Первый вариант некорректен, в процессе перехода могут возникнуть проблемы, что переход произойдёт не туда.
Реентрабельный КА не представляю, это ересь)
cupraer Автор
20.05.2025 18:56Что значит реентрабельный?
Siemargl
20.05.2025 18:56Стандартное определение
cupraer Автор
20.05.2025 18:56Стандартное определение — синоним потокобезопасности. У меня в тексте есть полноценный пример потокобезопасного конечного автомата, который можно запустить и попробовать поломать.
Siemargl
20.05.2025 18:56Вообще то потокобезопасность необходимое, но недостаточное свойство для реентерабельности. В Википедии, которую Вы за источник не уважаете, тем не менее это описано.
Похоже, у Вас больше склонность к теоретическим знаниям, что было отмечено комментаторами и в прошлой статье.
КА кстати является лучшим примером, моего 1го высказывания выше.
cupraer Автор
20.05.2025 18:56Больше, чем что? Вы не могли бы использовать конвенционный русский язык, чтобы не приходилось переспрашивать по два раза?
Не знаю, о каких комментаторах идёт речь. Или говорите прямо, или кокетничайте где-нибудь в другом месте.
Siemargl
20.05.2025 18:56Видимо, у нас достаточно разная образовательная база. Что даже дважды прочитанная Вами википедия не даёт нужного понимания.
Разговора не получится, слишком много разжевывать, извините.
cupraer Автор
20.05.2025 18:56Почитал википедию, мой пример демонстрирует полную реентрабельность и в викийном определении.
Refridgerator
20.05.2025 18:56А вы говорите, зачем нужно ООП. Чтобы State снаружи нельзя было изменять, вот зачем. Я конечные автоматы тоже предпочитаю делать в отдельном потоке, а управление через методы типа
bool Stop() {must_stop=true;}, где must_stop - это приватный флаг и будет обработан там, где надо.Dhwtj
20.05.2025 18:56Варианты:
• Автомат живёт дольше процесса, влияет на деньги/внешний мир → фиксируем каждый event или хотя бы снапшот в durable storage.
• Автомат ограничен одним вызовом функции/потоком, можно легко пересчитать → держим state в ОЗУ (переменная, стек, closure). Необходимости /дополнительного удобства в ООП не возникает, но если это ООП язык, то его использование здесь естественно.
Граница проходит по требованиям к надёжности и времени жизни.
А... Понял
польза ООП перевешивает когда:
• состояние уходит за пределы одной функции (передаём, кешируем, шарим между потоками);
• нужно запретить нелегальные переходы (метод next() проверяет allowed-таблицу);
• автомат эволюционирует, его будут трогать другие разработчики.
cupraer Автор
20.05.2025 18:56А если нерадивый коллега вызовет
Stopв недозволенном месте?Ну и да, чтобы запретить менять что-то снаружи — ООП не требуется.
Refridgerator
20.05.2025 18:56Тут разница в том, что в одном случае нерадивый коллега дёргает стоп-кран, а в другом случае - вежливо просит машиниста поезда остановиться. А машинист поезда может его так же вежливо послать ждать следующей остановки.
cupraer Автор
20.05.2025 18:56Если честно, я не очень понимаю, как это должно работать. Можете маленький кусочек кода показать?
Dhwtj
20.05.2025 18:56Он про инкапсуляцию, которая защищает от некорректных изменений мутабельного состояния
cupraer Автор
20.05.2025 18:56Это с каких пор инкапсуляция защищает от некорректных изменений мутабельного состояния?
Dhwtj
20.05.2025 18:56Это одно из главных назначений инкапсуляции: защитить мутабельное состояние объекта от некорректных внешних изменений.
Может, не всегда получается, но ЭТО ДРУГОЕ, ВЫ НЕ ПОНИМАЕТЕ! (С) лолВ конкурентной среде для ООП все плохо. Несколько потоков пытаются переписать один объект и нет единой точки правды. В акторной модели актор сам - точка правды.
Dhwtj
20.05.2025 18:56а... да... и еще
поток (Control Flow) для ООП является внешним, обьект в ООП пассивен и когда к нему обращаются из нескольких потоков управления то поучается хаос
актор имеет свой поток управления
я всегда воспринимал поток как OS thread а тут вон оно как)
cupraer Автор
20.05.2025 18:56А в каком языке вы чувствуете себя наиболее комфортно? Давайте я найду годную реализацию акторной модели для него, и тогда сможем предметно поговорить.
Dhwtj
20.05.2025 18:56C#
но стараюсь быть полиглотом
Я в курсе, что есть Akka.net но не пробовал
cupraer Автор
20.05.2025 18:56стараюсь быть полиглотом
Это понятно, все нормальные разработчики стараются. Но обсуждать новое эффективнее в той области, где не возникает базовых вопросов.
У Akka.NET же крутейшая документация. Примеры, правда, так себе, наподобие «как нарисовать сову» — но вот этот, вроде, не переусложнен нерелевантными деталями.
Refridgerator
20.05.2025 18:56Маленький не получится, для этого придётся какой-то игрушечный пример придумывать.
Ну вот например у меня есть объект для вывода звука одновременно на несколько устройств, и у него есть такие состояния, которые должны проходить последовательно:
STOPPED,
ENUMERATE_RUNTIME_MODULES,
INIT_DEVICES,
START_DEVICES,
WAIT_FOR_BUFFERS,
STOP_DEVICES,
FREE_DEVICESЗапросы на изменение состояния обрабатывается в начале каждого. И если запрос на остановку приходит при переходе с INIT_DEVICES на START_DEVICES - то состояния WAIT_FOR_BUFFERS и STOP_DEVICES можно пропустить и переходить сразу на FREE_DEVICES. А в состояниях STOPPED, STOP_DEVICES и FREE_DEVICES его отслеживать не имеет смысла.
Соответственно запрос на старт имеет смысл обрабатывать только в состоянии STOPPED, а объект в состоянии STOPPED висит на блокирующем событии, чтобы не расходовать зря процессорное время, поэтому об этом нужно дополнительно просигнализировать объекту межпоточной синхронизации, прямой доступ к которому давать снаружи тоже не самая лучшая идея.
vadimr
20.05.2025 18:56а объект в состоянии STOPPED висит на блокирующем событии, чтобы не расходовать зря процессорное время, поэтому об этом нужно дополнительно просигнализировать объекту межпоточной синхронизации, прямой доступ к которому давать снаружи тоже не самая лучшая идея.
Это всё, что угодно, но не конечный автомат.
Refridgerator
20.05.2025 18:56Ну назовите это как "асинхронный конечный автомат", суть от этого не меняется. Состояния явно прописаны, их количество конечно, в один момент времени существует только одно детерминированное состояние.
vadimr
20.05.2025 18:56Этак вы любую программу назовёте конечным автоматом (кстати, встречал на Хабре и такое мнение).
cupraer Автор
20.05.2025 18:56Технически, любую программу можно описать конечным автоматом.
vadimr
20.05.2025 18:56Нет, в силу неразрешимости проблемы останова.
cupraer Автор
20.05.2025 18:56А кто сказал, что переходы конечного автомата должны выполняться за фиксированное время?
Это теософская дискуссия. Идрис умеет доказывать тотальность функций, поэтому я критичные места реализую сначала на нём.
vadimr
20.05.2025 18:56Программа, для которой истинно, но недоказуемо утверждение, что она выполняется за бесконечное число шагов - будет порождать автомат с бесконечным количеством состояний, то есть актуально бесконечный.
Если только о тотальных функциях говорить, тогда, конечно, формально да.
cupraer Автор
20.05.2025 18:56Не, количество состояний ограничено сверху мощностью множества состояний, выразимых грамматикой (AST), которое счётно :)
cupraer Автор
20.05.2025 18:56Это поле «state», про которое я в самом первом предложении написал, что воюю с непониманием, чем оно отличается от конечного автомата.
dzmitry_sidarau
И как всегда ни слова о реактивном программировании с вытеснящим полиморфизмом. Аудитория негодует!