Стейт машина что это
Конечный автомат (он же машина состояний) на чистом С
Почти каждый микроконтроллерщик сталкивался с громадными switch-case и мучительно их отлаживал.
И много кто, начиная писать реализацию какого-либо протокола, задумывался как написать её красиво, изящно, так чтобы через месяц было понятно что ты имел в виду, чтобы она не отжирала всю память и вообще какала бабочками.
И вот тут на помощь приходят машины состояний, они же конечные автоматы (те самые которые используются в регулярных выражениях).
Собственно через регулярные выражения я к ним и пришёл.
Недавно мне потребовалось реализовать несложную функциональность устройства с 4-мя кнопками — выделение в потенциально хаотичных нажатиях кнопок двух кодовых последовательностей и выполнение определённых действий, когда последовательность найдена.
Поясню на примере: есть 4 кнопки — A, B, C, D и кодовая последовательность ACDA. Тогда при последовательном нажатии B, C, A, D, A, C, D, A, B, устройство должно зажечь лампочку после 8-го (предпоследнего) нажатия. С точки зрения регулярных выражений задача проста — ищем во входной строке подстроку «ACDA». Как только нашли — зажигаем лампочку. Но тащить в микроконтроллер какую-нибудь библиотеку по работе с regexp не хотелось. Я чувствовал что всё можно сделать самому и проще. Тогда я решил попробовать самостоятельно реализовать конечный автомат соответствующий поиску данной подпоследовательности.
А теперь — немного теории и практики:
Основная черта конечных автоматов — они описываются набором возможных состояний, набором сигналов (событий) и таблицей переходов. Таблица переходов — это сопоставление паре из текущего состояния и пришедшего сигнала нового состояния.
Представим, что у нас есть автомат с 3 состояниями и 3 сигналами, которые нужно обрабатывать. По приходу каждого сигнала автомат совершает переходит в новое состояние.
Очевидно что данный код не очень удобочитаем и будет катастрофически разрастаться с увеличением количества состояний и сигналов.
Кроме того, если мы захотим в каждый переход добавить какое-либо однотипное действие (например логирование — что-то вроде ), то это породит кучу изменений в коде. При редактировании таких изменений почти наверняка будет допущена какая-нибудь ошибка и отладка превратится в ад.
Заметим, что суть двух вложенных switch — это выбор из таблицы (по колонке и по столбцу) и вспомним что формально конечные автоматы удобно записывать в виде таблицы переходов где каждая строка соответствует сигналу, каждый столбец — состоянию, а на пересечении записано состояние в которое переходит автомат.
Попробуем упростить имеющийся код, задав таблицу переходов, извините за тафтологию, таблицей.
Продемонстрированый вид инициализации даннных известен как designated inits и был введён в С99.
теперь надо полученную структуру данных обработать — пишем функцию doFSM_table:
Чтобы сделать получившийся автомат ещё более универсальным и придать ему возможность совершать какие-то действия кроме перехода по состояниям добавим в таблицу указатели на функции-обработчики, соответствующие переходам:
Вообще улучшать данный механизм можно долго, но данная статья ставит своей целью не разработать универсальную библиотеку для реализации конечных автоматов, а продемонстрировать как некоторые задачи могут быть решены значительно проще и компактнее чем «в лоб», при этом не прибегая ни к каким замысловатым библиотекам или языкам.
В заключение приведу таблицу, получившуюся для задача поиска подпоследовательности, с которой я начинал:
Самые простые конечные автоматы или стейт-машины в три шага
Привет, Хабр!
Перейдем сразу к делу, но небольшая предыистория все таки нужна: полтора года назад возникла необходимость реализовать простую стейт — машину (конечный автомат), владея теорией с университета, я был уверен в тривиальности данной задачи (все мы оптимисты).
Время, проведенное с google, прошло без результатов, так как существующие решения не только имели фатальный недостаток, но и ряд других серьезных недочетов, таких как сложная структура и отсутствие документации.
Вскоре я наткнулся на эту статью, которая подтвердила отсутствие удобных решений.
Что сделал тогда?
Так как задачу требовалось решить быстро (ну как обычно), то мой конечный автомат был реализован с помощью словарей, то есть:
Таким образом, в нужном месте функция «издает сигнал» и, в зависимости от текущего состояния и сигнала, происходит переход (устанавливается следующее состояние)
Но что дальше?
Это был третий курс обучения в университете по специальности «Программная инженерия» и было уже пора определиться с темой диплома. Посовещавшись с предполагаемым научным руководителем, возникла идея того, что хорошо бы не только написать библиотеку для реализации конечных автоматов, но и как-то визуально их представлять.
Решение: библиотека и графический редактор.
Подробнее о реализации каждого из них расскажу в следующих статьях, а пока что покажу что получилось.
Спустя год разработки.
Графический редактор
Реализован на wpf с использованием ReactiveUI.
Тут у нас структура конечного автомата в виде графа и в виде таблицы переходов.
Накидываем узлы, соединяем их и сохраняем в xml файл.
В целом я постарался сделать удобно и стильно, а как бонус — куча горячих клавиш поддерживается. Ссылку на репозиторий с документацией в виде gif прикреплю в конце.
Возможности
Две темы
Два представления конечного автомата:
Валидация
Добавление узлов и соединений
Отмена действий
Сворачивание и перемещение узлов
Масштабирование
Выделение элементов
Наименования для состояний и переходов
Перемещение переходов
Удаление переходов
Импорт/Экспорт из/в xml
Сохранение схемы в PNG/JPEG
Библиотека
Реализуем конечный автомат в три шага:
Отмечу, что необязательно использовать редактор, ведь конечный автомат можно описать в коде и, если понадобиться, сделать export схемы, которую потом уже открыть в редакторе.
А что с переходами?
Для перехода внутри функции, которая обрабатывает Entry/Exit в состояние, вызываем:
Переход не произойдет сразу же, просто указанный переход будет помечен как следующий, то есть сначала отработают все события состояния, а потом уже будет вызван переход.
Что есть ещё?
Полный список фич и подробную документацию можно найти в репозитории, ссылку тоже оставлю.
Возможности:
Будущее проекта
Диплом был защищен на отлично, но забрасывать проект не хотелось бы.
Поэтому буду рад помощи с реализацией нижеописанных пунктов.
Также, если Вы нашли ошибки или у вас есть другие идеи — пишите, буду очень рад!
Библиотека. Возможные улучшения:
Последний пункт распишу подробнее. Сейчас пользователю необходимо помнить, какие имя у переходов и состояний описаны внутри файла.
И работа с ними происходит так:
Сразу скажу, что dynamic не подойдет так как все равно нужно помнить название.
Тут наверное нужна какая-то кодо-генерация, но решение пока что не нашел.
Графический редактор. Возможные улучшения:
Выводы
Ссылки
Графический редактор, исходники на GitHub: SimpleStateMachineNodeEditor
Библиотека, исходники на GitHub: SimpleStateMachineLibrary
Теория вычислений. Введение в конечные автоматы
Это до предела упрощенная модель компьютера имеющая конечное число состояний, которая жертвует всеми особенностями компьютеров такие как ОЗУ, постоянная память, устройства ввода-вывода и процессорными ядрами в обмен на простоту понимания, удобство рассуждения и легкость программной или аппаратной реализации.
С помощью КА можно реализовать такие вещи как, регулярные выражения, лексический анализатор, ИИ в играх и тд.
У конечных автоматов имеется таблица переходов, текущее состояние автомата, стартовое состояние и заключительное состояние.
Таблица переходов — В ней хранятся переходы для текущего состояния и входного символа. Простейшая реализация может быть как двумерный массив.
Здесь видно, что из состояния 0 в состояние 1 можно попасть только, если у нас будет входной символ ‘a’, из состояния 1 в состояние 2, если символ ‘b’.
Текущее состояние — множество состояний в котором автомат может находиться в данный момент времени.
Стартовое состояние — состояние откуда КА начинает свою работу.
Заключительное состояние — множество состояний в которых автомат принимает определенную цепочку символов, в ином случае отвергает.
Детерминированные конечные автоматы (deterministic finite automaton)
Простейший КА, в котором может быть одно состояние в текущий момент времени, обладает детерминированностью.
Детерминированность — для всех состояний имеется максимум и минимум одно правило для любого возможного входного символа, то есть например, для состояния 1 не может быть два перехода с одним и тем же входным символом.
Недетерминированные конечные автоматы (nondeterministic finite automaton)
НКА не является каким-то существенным улучшением ДКА, просто в нем добавлен так сказать синтаксический сахар, в виде свободных переходов, недетерминированности и множеств состояний. Реализовать можно как массив состоящий из структур в которой хранится состояние, входной символ и следующее состояние.
Свободные переходы (эпсилон переходы) — переходы, которые можно совершать без чтения входного символа.
Недетерминированность — ноль и более переходов для одного символа в каких-либо состояниях.
Множества состояний — в один момент времени НКА может находится в нескольких состояниях.
Заключительное состояние обозначается двойным кругом.
В стартовом состоянии у нас текущим состоянием является <1>, при входном символе ‘b’ у нас появляется возможность, пойти в состояние 1 и в состояние 2, то есть после входного символа ‘b’ текущим состоянием является множество <1, 2>.
Свободным переходом обозначается пунктирной линией.
Здесь видно два свободных перехода из стартового состояния, то есть без чтения входного символа мы сразу находимся в множестве состоянии <2, 4>.
Для преобразования НКА в ДКА используется алгоритм Томпсона.
При преобразовании НКА в ДКА может получиться не совсем минимальный ДКА и для его минимизации можно применить алгоритм Бржозовского.
Конечные автоматы с магазинной памятью (pushdown automaton)
Это тот же КА, но с дополнительной памятью в виде стека. Теперь для совершения перехода нужно учитывать еще несколько факторов, символ который нужно удалить из стека и символы которые нужно добавить в стек.
КАМП можно применять в таких местах, где может быть неограниченное количество вложений, например при разборе языков программирование или подсчету вложенных скобок в математических выражениях. Реализовать с помощью КА невозможно, ведь количество возможных состояний конечно в отличие от стека (я понимаю, что память тоже конечна).
Удаление символа из стека — при любом переходе решается какой символ вытолкнуть, если на вершине стека не оказалось такого символа, то он и не выталкивается. Так же если символ нужно оставить в стеке, то он добавляется вместе с добавляемыми символами.
Добавление символов в стек — при любом переходе решает какие символы добавить в стек.
Этот КАМП подсчитывает вложенность скобок, за счет добавления и удаления символов из стека.
ДАМП не равен НАМП, поэтому невозможно одно преобразовать в другое, следовательно НАМП обладает преимуществом перед ДАМП.
Машина Тьюринга (Turing machine)
Самая мощная машина из существующих, его преимущество перед другими в ленте с которой он может работать как хочет. В нем нет свободных переходов. Умеет интерпретировать другие автоматы такие как КА, КАМП.
Лента — это одномерный массив в который могут записываться данные за счет головки над ячейкой, который можно заранее заполнить входными данными.
Шаблон: считаный_символ_с_головки/записаный_символ; сторона_смещения_головки. края ленты обозначаются ‘_’.
Эта МТ выполняет инкремент двоичного числа, головка стоит слева, там где начинается лента.
ДМТ эквивалентен НМТ, так, что они тоже не различаются.
Универсальная машина Тьюринга (universal Turing machine)
Машина которая может порождать другие машины Тьюринга, получая на входную ленту данные машины.
Стейт-машина в Angular: учимся использовать правильно
Для начала давайте проясним, что же такое стейт-менеджеры. Если вы оказались здесь, следовательно, знаете о них хотя бы в общих чертах. Примерное описание звучит следующим образом:
Паттерн State Machine предназначен для создания объектов, поведение которых варьируется в зависимости от состояния. При этом для клиента создается впечатление, что изменился класс объекта. Таким образом, назначение предлагаемого шаблона совпадает с таковым для паттерна State, однако область применимости и степень гибкости последнего уже.
Главная идея заключается в том, что объект находится в одном из нескольких сменяемых состояний и может по-разному реагировать на одни и те же события, которые с ним происходят. Набор этих состояний и переходов между ними предопределён и конечен.
Больше материала по теме читайте тут. Это старая статья, но, кроме интересного паттерна в ней прилагается список литературы о конечных автоматах и управлению состояниями в инженерном деле и математике.
Как используют стейт-машины
Сфера применения стейт-машин специфична — это переключатели, реализующие смену состояний, например, в играх, или управляющие переключением различных механизмов программ, например коннект или дисконнект соединения с сетью. Кроме этого, стейт-менеджеры используют, например, для управления состоянием сети блокчейн.
На фронтенде их регулярно используют в качестве хранилища данных с CRUD’ом и шиной событий для относительно безопасного общения частей приложения между собой, для хранения токена или данных пользователя с доступом к ним во всём приложении, или всевозможных списков (страны, языки, валюты и прочее). Это не всегда соответствует области применения стейт машин и в таких случаях целесообразнее использовать более подходящие инструменты.
Плюсы и минусы
Итак, давайте рассмотрим преимущества и недостатки использования стейт-машин в контексте фронтенд-приложений.
Какие мы получаем преимущества:
Теперь давайте посмотрим на проблемы, которые мы приобретаем взамен:
Ну хорошо. Так как же правильно использовать стейт-менеджер?
В первую очередь нужно уяснить, что механизм управления состояниями становится ядром вашего приложения. Не программа его использует, а наоборот — он пускает корни в приложение и паразитирует на его ресурсах. Из этого следует вывод — вы связаны архитектурой, которую навязывает стейт-машина, подходит она для вашей бизнес-логики или нет. Критически важно определить степень ее необходимости в проекте еще на начальном этапе, иначе впоследствии вы будете страдать на сопровождении или удалять ее из уже готового кода, как сорняк, что дорого и тяжело, вплоть до переписывания всего проекта целиком.
Далее перед тем, как писать код, проанализируйте требования к проекту, взвесьте все за и против, определите действительно ли вашему проекту требуется именно управление состояниями. Важно так же учитывать целесообразность — область применения менеджеров состояний довольно специфична и не широка, как это можно понять из описания в начале статьи. Чаще, требуется только Store или Event Bus, альтернатив которым полно в сети или которые можно легко написать самостоятельно, и они не будут диктовать условия вашей архитектуре, но гармонично в неё впишутся.
Теперь рассмотрим случаи использования стейт-машин, в которых они действительно будут кстати. Это уместно, например, в знаменитом пасьянсе «Косынка», где состояние изменяется и фиксируется каждый раз, когда карта перекладывается на новое место. Или в игре в кости, где у кубика 6 граней, а с программной точки зрения 6 состояний. Так же стейт-машина полезна в случаях, когда предполагается большое количество состояний и множество триггеров, чтобы эти состояния менять. Здесь без стейт-машины сложно управлять изменениями и сохранять их чистыми.
Если не требуется управлять состояниями, использование стейт-менеджера усложнит ваше приложение, не давая ничего, что нельзя получить другими способами.
Перенесемся на момент в мир векторной иллюстрации. На картинке изображены два практически одинаковых шара, но с одним большим «НО» — оба шара созданы разными способами.
Простые стейт-машины на службе у разработчика
Представьте на минутку обычного программиста. Допустим, его зовут Вася и ему нужно сделать анимированную менюшку на сайт/десктоп приложение/мобильный апп. Знаете, которые выезжают сверху вниз, как меню у окна Windows или меню с яблочком у OS X. Вот такое.
Начинает он с одного выпадающего окошка, тестирует анимацию, выставляет ease out 100% и наслаждается полученным результатом. Но вскоре он понимает, что для того, чтобы управлять менюшкой, хорошо бы знать закрыто оно сейчас или нет. Мы-то с вами тут программисты опытные, все понимаем, что нужно добавить флаг. Не вопрос, флаг есть.
Вроде, работает. Но, если быстро кликать по кнопке, меню начинает моргать, открываясь и закрываясь не успев доанимироваться в конечное состояние. Вася добавляет флаг animating. Теперь код у нас такой:
Через какое-то время Васе говорят, что меню может быть полностью выключено и неактивно. Не вопрос! Мы-то с вами тут программисты опытные, все понимаем, что… нужно добавить ЕЩЕ ОДИН ФЛАГ! И, всего-то через пару дней разработки, код меню уже пестрит двустрочными IF-ами типа вот такого:
Вася начинает задаваться вопросами: как вообще может быть, что animating == true и enabled == false; почему у него время от времени все глючит; как тут вообще поймешь в каком состоянии находится меню. Ага! Состояния. О них дальше и пойдет речь.
Знакомьтесь, это Вася.
Состояние
Вася уже начинает понимать, что многие комбинации флагов не имеют смысла, а остальные можно легко описать парой слов, например: Disabled, Idle, Animating, Opened. Все мы тут программисты опытные, сразу вспоминаем про state machines. Но, для Васи придется рассказать что это и зачем. Простым языком, без всяких математических терминов.
У нас есть объект, например, вышеупомянутая менюшка. Объект всегда находится в каком-то одном состоянии и реагируя на различные события может между этими состояниями переходить. Обычно состояния, события и переходы удобно описывать вот такими схемами (кружочками обозначены начальное и конечные состояния):
Из схемы понятно, что из состояния Inactive в Active можно попасть только по событию Begin, а из состояния Paused можно попасть как и в Active, так и в Inactive. Такую простую концепцию почему-то называют «Конечный Автомат» или «Finite State Machine», что очень пугает обычных людей.
По завету ООП, состояния должны быть скрыты внутри объекта и просто так снаружи не доступны. Например, у объекта во время работы может быть 20 разных состояний, но внешнее API на вопрос «чо как дела?» отвечает «ничо так» на 19 из них и только на 1 ругается матом, что проср*ли все полимеры.
Следуя концепции стейт машин, очень легко структурировать код так, что всегда будет ясно что и как делает тот или иной объект. Всегда будет понятно, что что-то пошло не так, если система вдруг попыталась перейти в недоступное из данного состояния состояние. А события, которые вдруг посмели прийти в неправильное время, можно смело игнорировать и не бояться, что что-нибудь сломается.
Самая простая в мире стейт машина
Допустим, теперь Вася делает проект на C# и ему нужна простая стейт машина для одного типа объектов. Он пишет что-то типа такого:
А вот так обрабатывает события в зависимости от текущего состояния:
Но, мы-то с вами тут программисты опытные, все понимаем, что метод setState в итоге разрастется на пару десятков страниц, что (как написано в учебниках) не есть хорошо.
State Pattern
Погуглив пару часов, Вася решает, что State Pattern идеально подходит в данной ситуации. Тем более, что старшие программисты все время соревнуются кто больше паттернов запихнет в свой апп, так что, решает Вася, паттерны это дело важное.
Например, для State Pattern можно сделать интерфейс IState:
И по отдельному классу для каждого состояния, которые этот интерфейс имплементят. В теории выглядит красиво и 100% по учебнику.
Но, во-первых, для каждой несчастной мелкой стейт машины нужно городить уйму классов, что само по себе небыстро. Во-вторых, рано или поздно начнутся проблемы с доступом к общим данным. Где их хранить? В основном классе? А как классы-состояния получат к ним доступ? А как мне тут за 15 минут перед дедлайном впилить быстро мелкий хак в обход правил? И подобные проблемы взаимодействия, которые будут сильно тормозить разработку.
Реализация на основе особенностей языка
Некоторые языки программирования облегчают решение тех или иных задач. В Ruby, например, так вообще есть целый DSL (и не один) для создания конечных автоматов. А в C# конечный автомат можно упростить через Reflection. Вот как-то так:
Реализовав систему описанную выше, Вася понимает, что у нее тоже больше минусов, чем плюсов:
Фреймворк
А тем временем, Вася уже вовсю стал вникать в теорию стейт машин и решил, что хорошо бы иметь возможность формально их описывать через API или (о Боже) через XML, что в теории звучит круто. Мы-то с вами тут программисты опытные, все понимаем, что нужно писать свой фреймворк. Потому что другие не подходят, так как у всех у них есть один фатальный недостаток.
Вася решил, что с помощью его фреймворка можно будет быстро и легко создать стейт машину без необходимости писать много ненужного кода. Фреймворк не будет накладывать никаких ограничений на разработчика. Все вокруг будут веселы и жизнерадостны.
Я попробовал множество фреймворков на разных языках, несколько подобных написал сам. И всегда для описания конечного автомата средствами фреймворка требовалось больше кода, чем в простом примере. Все они накладывают те или иные ограничения, а многие пытаются делать сразу столько всего, что для того, чтобы разобраться, как же тут все-таки создать несложную стейт машину, приходится продолжительное время рыться в документации.
Вот, например, описание конечного автомата фреймворком stateless:
Но, пробившись через создание стейт машины, можно воспользоваться полезными функциями, которые предоставляет фреймворк. В основном это: проверка правильности переходов, синхронизация зависимых стейт машин и суб-стейт машин и всяческая защита от дурака.
XML — это отдельное зло. Кто-то когда-то придумал использовать его для написания конфигов. Стадо леммингов java разработчиков длительное время молилось на него. А теперь никто уже и не знает зачем все используют XML, но продолжают бить всех, кто пытается от него избавиться.
Вася тоже загорелся идеей, что можно все сконфигурировать в XML и НЕ ПИСАТЬ НИ СТРОЧКИ КОДА! В итоге в его фреймворке отдельно лежат XML файлы примерно такого содержания:
Класс! И никакого программирования. Но, мы-то с вами тут программисты опытные, все понимаем, что программирование никуда не ушло. Вася заменил кусок императивного кода на кусок декларативного кода, добавив при этом во фреймворк интерпретатор XML, который все еще в пару раз усложнил. А потом попробуй это отдебажить, когда код на разных языках и разбросан по проекту.
Соглашение
И тут Васе все это надоело и он вернулся обратно к самому простому в мире конечному автомату. Он его немного переделал и придумал правила как писать в нем код.
UPDATE: спасибо за комментарии. Здесь действительно не хватало небольшого объяснения.
У нас есть несколько состояний. Переход между ними — это транзакция из атомарных операций, то есть они все происходят всегда вместе, в правильном порядке и между ними не может вклиниться еще какой-то код. При смене состояния с A на B происходит следующее: выполняется код выхода из состояния A, состояние меняется с A на B, выполняется код входа в состояние B.
Для перехода на состояние A нужно вызвать метод stateA, который выполнит нужную логику и вызовет setState(A). Самому вызывать setState(A) крайне не рекомендуется.
UPDATE: В setState() пишется уникальная логика выхода из состояния, а в stateB() возможна специфическая логика выхода из состояния A при переходе в B. Но очень редко используется.
Простое соглашение для написания стейт машин. Оно достаточно гибкое и имеет следующие плюсы:
Как и во всех соглашениях, какой-то код может сперва находиться в одном месте, но потом у него появится другой смысл, или окажется, что он где-то дублируется. Тогда мы можем его перенести в другое место. Никто нам не запрещает. Все-таки код не вытесан из камня, это всего лишь текст, который (о ужас!) можно и нужно менять с развитием проекта.
UPDATE: а setState() вполне можно заменить одним сеттером для наглядности.
Заключение
На этом заканчивается увлекательное приключение Васи в мире стейт машин. А ведь впереди еще столько всего интересного. Отдельного топика бы только заслужили параллельные и зависимые стейт машины.
Я надеюсь, что, если вы еще не используете стейт машины повсеместно, эта статья перетянет вас на сторону добра; если вы пишите свой уберфреймворк для работы со стейт машинами, она поможет свежим взглядом посмотреть на то, что у вас получается.
Я надеюсь, что эта статья поможет разработчикам задуматься где и когда стоит использовать паттерны и фреймворки, и что описанное соглашение по оформлению стейт машин окажется кому-то полезным.