Теория вычислений. Введение в конечные автоматы
Это до предела упрощенная модель компьютера имеющая конечное число состояний, которая жертвует всеми особенностями компьютеров такие как ОЗУ, постоянная память, устройства ввода-вывода и процессорными ядрами в обмен на простоту понимания, удобство рассуждения и легкость программной или аппаратной реализации.
С помощью КА можно реализовать такие вещи как, регулярные выражения, лексический анализатор, ИИ в играх и тд.
У конечных автоматов имеется таблица переходов, текущее состояние автомата, стартовое состояние и заключительное состояние.
Таблица переходов — В ней хранятся переходы для текущего состояния и входного символа. Простейшая реализация может быть как двумерный массив.
Здесь видно, что из состояния 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)
Машина которая может порождать другие машины Тьюринга, получая на входную ленту данные машины.
Создаем Конечный Автомат на PHP
Что такое Конечный Автомат?
Я объясню на примере. Предположим, что я хочу купить молоко, тогда такая задача будет иметь примерно следующие состояния:
Произведение оплаты за молоко
Поездка обратно домой
Везде. В большинстве (если не во всех) бизнес-процессах, требующих как минимум двух «состояний». Например: службы доставки, операции купли-продажи, процесс найма и т.д.
Внимание! если вы новичок или опыт с ООП мал тогда не воспринимайте статью как руководство к действию. Конечные Автоматы не популярны коммерческой разработке и могут быть полезны в проектах, которые направлены на транзакции, например платёжные шлюзы. Задумываются о них лишь когда запутанность транзакций превышает все мыслимые пределы.
Зачем мне нужен Конечный Автомат?
Вернемся назад к примеру с молоком. Зачем мне нужно создавать конечный автомат, в котором процесс идет от А до Я?. Загвоздка в том что всегда что-то случается, могут возникнуть ошибки, недоразумения или проблемы.
Таким образом состояния для нас теперь следующие:
Произведение оплаты за молоко
Поездка обратно домой
Можно даже добавить больше состояний, но для нашего исследования тут хватит основных. Также возможно сжатие состояний и использование меньшего их количества, например «состояние отмены поездки» и «состояние отмены покупки молока» можно объединить просто в «Отмена».
Как автоматизировать процесс?
milk = 0 нет молока, milk = 1 у меня есть молоко
money = кол-во денег в кармане
price = цена молока
stock_milk = количество молока в магазине
store_open = 0 магазин закрыт, = 1 открыт
gas = бензин моей машины
Так мы можем сформировать состояния и переходы:
Состояние после перехода
Когда возможен переход?
Поездка за молоком
Когда milk = 0 и gas > 0
Отмена поездки (это конец процесса)
store_open = 1 и stock_milk > 0
store_open = 0 или stock_milk = 0
Произведение оплаты за молоко
(это также увеличивает milk +1)
неверно, а money (видим пробелы) правильно.
Пятая, и, наконец, мы объединим все это вместе.
Тестирование с использованием пользовательского интерфейса
Если конфигурация верна, то на странице должен отображаться новый экран.
Теперь давайте создадим новую задачу. Давайте начнем с начальными значениями: milk = 0, money = 999 и gas = 10 и нажмем на кнопку «Create a new job«. Теперь задача была создана и перешла из состояния «Вождение автомобиля»(1) в состояние » Купить молоко»(2).
Давайте установим следующие значения, store_open=1 и stock_milk=1 и нажмем на кнопку Set field values (она установит новые значения и проверит все условия).
Замечания и предложения
Основы теории вычислительных систем: машина с конечным числом состояний
Теория вычислительных систем — это то, что позволяет нам программировать. Однако, можно писать программы и без представления о концепциях, скрывающихся за вычислительными процессами. Не то, чтобы это было плохо — когда мы программируем, то работаем на намного более высоком уровне абстракции. В конце концов, когда мы ведём машину, то концентрируемся только на двух или трёх педалях, переключателе передач и руле. Для повседневной неспешной езды этого более чем достаточно. Однако, если мы хотим управлять автомобилем на пределе его возможностей, то тут нужно знать гораздо больше, чем просто три педали, КПП и руль.
Такой подход справедлив и в программировании. Большая часть повседневной мирской работы может быть выполнена при минимальном знании теории вычислительных систем или даже вообще без него. Не нужно понимать теорию категорий, чтобы накидать форму «Контакты» в PHP. Тем не менее, если вы планируете писать код, требующий серьёзных вычислений, то тут уж придётся разобраться с тем, что у этих самых вычислений под капотом.
Цель этой статьи — представить некоторые фундаментальные основы вычислений. Если это окажется интересным, то в дальнейшем я могу написать более продвинутый топик на эту тему, но прямо сейчас я хочу просто рассмотреть логику простейшего абстрактного вычислительного устройства — машины с конечным числом состояний (finite state machine).
Машина с конечным числом состояний
Машина с конечным числом состояний (finite state machine, FSM), или конечный автомат (finite automaton) — это математическая абстракция, используемая при проектировании алгоритмов. Говоря простым языком, машина с конечным числом состояний умеет считывать последовательности входных данных. Когда она считывает входной сигнал, то переключается в новое состояние. Куда именно переключится, получив данный сигнал, — заложено в её текущем состоянии. Звучит запутанно, но на самом деле всё очень просто.
Представим устройство, которое читает длинную бумажную ленту. На каждом дюйме этой ленты напечатана буква — a или b.
Как только устройство считывает букву, оно меняет своё состояние. Вот очень простой граф переходов для такой машины:
Кружки — это состояния, в которых машина может быть. Стрелочки — переходы между ними. Так что, если вы находитесь в состоянии s и считываете a, то вам необходимо перейти в состояние q. А если b, то просто остаётесь на месте.
Итак, если изначально мы находимся в состоянии s и начинаем читать ленту из первого рисунка слева направо, то сначала будет прочитана a, и мы переместимся в состояние q, затем b — вернёмся обратно в s. Следующая b оставит нас на месте, а a вновь переместит в q. Элементарно, но какой в этом смысл?
Оказывается, если пропустить ленту с буквами через FSM, то по её итоговому состоянию можно сделать некоторые выводы о последовательности букв. Для приведённго выше простого конечного автомата финальное состояние s означает, что лента закончилась буквой b. Если же мы закончили в состоянии q, то последней на ленте была буква a.
Это может показаться бессмысленным, но существует масса задач, которые можно решить с помощью такого подхода. Простейший пример: определить, содержит ли HTML-страница следующие теги в заданном порядке:
Также конечный автомат может использоваться для представления механизмов парковочного счётчика, автомата с газировкой, автоматизированного газового насоса и тому подобных штук.
Детерминированная машина с конечным числом состояний (Deterministic Finite State Machine)
Машины с конечным числом состояний, которые мы рассматривали выше, являются детерминированными. У них из любого состояния существует только один переход для любого разрешённого входного сигнала. Другими словами, не существует двух различных путей из данного состояния, когда вы считываете, допустим, букву a. На первый взгляд такое ограничение кажется глупым.
Недетерминированная машина с конечным числом состояний (Nondeterministic Finite State Machine)
Итак, надо распознать букву a с последующим нулём или более одинаковых букв b или c и с замыкающей следующей буквой алфавита. Самый простой способ отобразить этот алгоритм с помощью машины с конечным числом состояний представлен ниже. Финальное состояние t означает, что строка была принята целиком и соответствует шаблону.
На этом принципе основан алгоритм большинства шахматных программ. Они просматривают все возможности всех возможных ходов на данном этапе и выбирают ту стратегию, которая в данный момент даёт максимальное преимущество над противником.
Регулярные выражения
Если вы когда-нибудь занимались любым видом программирования, то вы почти наверняка сталкивались с регулярными выражениями (regular expressions). Регулярные выражения и машины с конечным числом состояний функционально эквивалентны. Всё, что можно допустить для (или связать с) регулярным выражением, можно допустить для (или связать с) конечным автоматом. Например, шаблон, который мы разбирали выше, можно связать с
Это положение известно как лемма о накачке для регулярных языков. Её основная мысль: если ваш шаблон имеет блок, который может быть повторён более, чем один раз, то этот шаблон не является регулярным. Другими словами, ни регулярные выражения, ни машины с конечным числом состояний не могут быть сконструированы так, чтобы распознавать все строки, которые можно связать с шаблоном.
Машина Тьюринга
Так как же нам распознавать нерегулярные шаблоны? Существует теоретическое устройство, подобное конечному автомату и называемое машиной Тьюринга (Turing Machine). Как и у машины с конечным числом состояний, у него имеется бумажная лента, с которой оно считывает информацию. Однако, машина Тьюринга также способна записывать и стирать данные на ленте. Полное объяснение принципов этого устройства займёт больше места, чем у нас здесь имеется, поэтому я обозначу лишь несколько важных моментов, относящихся к нашей дискуссии о машинах с конечным числом состояний и регулярных выражениях.
Машина Тьюринга вычислительно полна, и всё, что в принципе может быть вычислено, может быть вычислено с помощью машины Тьюринга. А благодаря способности записывать данные на ленту с такой же лёгкостью, как и считывать их с ленты, она не ограничена конечным числом состояний. Бумажную ленту можно представить, как имеющую бесконечную длину. Очевидно, что современные компьютеры не обладают бесконечным количеством памяти, однако, они имеют её достаточно, чтобы вы не вышли за предел для тех типов задач, которые они способны обработать.
Машина Тьюринга предоставляет нам воображаемое механическое устройство, позволяющее визуализировать и понять, как работает вычислительный процесс. Это особенно полезно для понимания пределов вычислений. Если это интересно, то в будущем я могу написать отдельную статью о машине Тьюринга.
Почему это имеет значение?
Понимание, что машины с конечным числом состояний и регулярные выражения функционально эквивалентны, открывает невероятно интересные способы применения движков регэкспов. Особенно, когда дело доходит до создания бизнес-правил, которые могут быть изменены без перекомпиляции всей системы.
Знание основ теории вычислительных систем позволяет вам брать проблему X, которую вы понятия не имеете как решать, и применять к ней подход: «Я не знаю, как решить X, но я знаю, как решить Y и как привести решение для Y к решению для X. Вот почему теперь я знаю, как решить X».
Конечный автомат (он же машина состояний) на чистом С
Почти каждый микроконтроллерщик сталкивался с громадными 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:
Чтобы сделать получившийся автомат ещё более универсальным и придать ему возможность совершать какие-то действия кроме перехода по состояниям добавим в таблицу указатели на функции-обработчики, соответствующие переходам:
Вообще улучшать данный механизм можно долго, но данная статья ставит своей целью не разработать универсальную библиотеку для реализации конечных автоматов, а продемонстрировать как некоторые задачи могут быть решены значительно проще и компактнее чем «в лоб», при этом не прибегая ни к каким замысловатым библиотекам или языкам.
В заключение приведу таблицу, получившуюся для задача поиска подпоследовательности, с которой я начинал:
Машины состояний и разработка веб-приложений
Настал 2018-й год, найдено множество замечательных способов создания приложений, но бесчисленные армии фронтенд-разработчиков всё ещё ведут борьбу за простоту и гибкость веб-проектов. Месяц за месяцем они проводят в попытках достигнуть заветной цели: найти программную архитектуру, свободную от ошибок, и помогающую им делать их работу быстро и качественно. Я — один из этих разработчиков. Мне удалось найти кое-что интересное, способное дать нам шанс на победу.
Знакомство с машинами состояний
Машина состояний — это математическая модель вычислений. Это — абстрактная концепция, в соответствии с которой машина может иметь различные состояния, но, в некий момент времени, пребывать лишь в одном из них. Полагаю, самая известная машина состояний — это машина Тьюринга. Это — машина с неограниченным числом состояний, что означает, что состояний у неё может быть бесконечное количество. Машина Тьюринга не очень хорошо соответствует нуждам современной разработки интерфейсов, так как в большинстве случаев у нас имеется конечное число состояний. Именно поэтому нам лучше подходят машины с ограниченным числом состояний, или, как их часто называют, конечные автоматы. Это — автомат Мили и автомат Мура.
Разница между ними заключается в том, что автомат Мура меняет состояние, основываясь только на своём предыдущем состоянии. Однако, у нас имеется множество внешних факторов, таких, как действия пользователя и процессы, происходящие в сети, что означает, что и автомат Мура нам не подойдёт. То, что мы ищем, очень похоже на автомат Мили. У этого конечного автомата имеется начальное состояние, после чего он переходит в новые состояния, основываясь на входных данных и на его текущем состоянии.
Один из самых простых способов проиллюстрировать работу машины состояний заключается в рассмотрении её через аналогию с турникетом. У него имеется ограниченный набор состояний: он может быть либо закрыт, либо открыт. Наш турникет преграждает вход в некую область. Пусть у него будет барабан с тремя планками и механизм для приёма денег. Пройти через закрытый турникет можно, опустив монету в монетоприёмник, что переводит устройство в открытое состояние, и толкнув планку для того, чтобы пройти через турникет. После того, как через турникет прошли, он снова закрывается. Вот простая схема, которая показывает нам эти состояния, а также возможные входные сигналы и переходы между состояниями.
Исходное состояние турникета — «закрыто» (locked). Неважно, сколько раз мы толкнём его планку, он останется закрытым. Однако, если мы опустим в него монетку, турникет перейдёт в состояние «открыто» (un-locked). В этот момент ещё одна монетка ничего не изменит, так как турникет всё ещё будет в открытом состоянии. С другой стороны, теперь толчок планки турникета имеет смысл, и мы сможем через него пройти. Это действие, кроме того, переведёт наш конечный автомат в исходное состояние «закрыто».
Если нужно реализовать единственную функцию, которая контролирует турникет, нам, вероятно, стоит остановиться на двух аргументах: это — текущее состояние и действие. Если вы используете Redux, возможно, вам это знакомо. Это похоже на широко известные функции-редьюсеры, где мы получаем текущее состояние, и, основываясь на полезной нагрузке действия, решаем, каким будет следующее состояние. Редьюсер — это переход в контексте машины состояний. На самом деле, любое приложение, имеющее состояние, которое мы можем как-то менять, может называться машиной состояний. Дело просто в том, что всё это, снова и снова, реализуется вручную.
Каковы сильные стороны машин состояний?
На работе мы используем Redux и он нас вполне устраивает. Однако я начал замечать кое-какие вещи, которые мне не нравятся. То, что мне что-то «не нравятся», не значит, что это не работает. Речь больше идёт о том, что всё это добавляет проекту сложности и принуждает меня писать больше кода. Как-то я занялся сторонним проектом, где у меня был простор для экспериментов, и я решил переосмыслить наши подходы к разработке на React и Redux. Я начал делать заметки о том, что меня беспокоит, и понял, что абстракция машины состояний, вероятнее всего, сможет решить некоторые из этих проблем. Примемся за дело и посмотрим, как реализовать машину состояний на JavaScript.
Мы будем решать простую задачу. Нам нужно получать данные из серверного API и показывать их пользователю. Самый первый шаг заключается в том, что понять, как, при осмыслении задачи, думать в терминах состояний, а не переходов. Прежде чем мы перейдём к машине состояний, хочу рассказать о том, как, на высоком уровне, выглядит то, что мы хотим создать:
Сейчас, анализируя задачу, мы мыслим линейно, и, собственно говоря, пытаемся охватить все возможные пути к итоговому результату. Один шаг ведёт к другому, следующий ведёт ещё к одному, и так далее. В коде это может выражаться в виде операторов ветвления. Проведём мысленный эксперимент с программой, которая построена на основе действий пользователя и системы.
Происходит так из-за того, что мы мыслим переходами. Мы сосредоточены на том, как именно происходят изменения в программе, и на том, в каком порядке они происходят. Если, вместо этого, сосредоточиться на различных состояниях приложения, всё значительно упростится. Сколько состояний у нас есть? Каковы их входные данные? Используем тот же пример:
Это означает, что нам придётся покрыть меньше кода при тестирования. Кроме того, некоторые типы тестирования, такие, как интеграционное тестирование, могут быть автоматизированы. Подумайте о том, что при таком подходе у нас было бы по-настоящему чёткое понимание того, что делает наше приложение, и мы могли бы создать скрипт, который проходится по предопределённым состояниями и переходам и генерирует утверждения. Эти утверждения могут доказать, что мы достигли каждого из возможных состояний или осуществили конкретную последовательность переходов.
На самом деле, выписать все возможные состояния легче, чем выписать все возможные переходы, так как нам известно, какие состояния нам нужны, или какие состояния у нас есть. Между прочим, в большинстве случаев, состояния описывали бы логику функционирования нашего приложения. А вот если говорить о переходах, их смысл очень часто в начале работы неизвестен. Ошибки в программах являются результатам того, что действия выполнены тогда, когда приложение находится в состоянии, не рассчитанном на эти действия. Кроме того, даже если приложение находится в подходящем состоянии, действие может быть выполнено в неподходящее время. Подобные действия приводят наше приложение в состояние, о котором мы не знаем, и это выводит программу из строя или приводит к тому, что она ведёт себя неправильно. Конечно, нам это ни к чему. Машины состояний — это хорошие средства защиты от подобных проблем. Они защищают нас от достижения неизвестных состояний, так как мы устанавливаем границы для того, что и когда может случиться, не указывая явно — как это может случиться. Концепция машины состояний отлично сочетается с однонаправленным потоком данных. Вместе они уменьшают сложность кода и дают чёткие ответы на вопросы о том, как система попала в то или иное состояние.
Создание машины состояний средствами JavaScript
Хватит разговоров — пришло время программировать. Использовать будем тот же самый пример. Основываясь на вышеприведённом списке, начнём со следующего кода:
Состояния представлены объектами, возможные входные сигналы состояний — методами объектов. Однако исходного состояния тут нет. Изменим вышеприведённый код, приведя его к следующему виду:
После того, как мы определили все состояния, имеющие смысл, мы готовы отправлять им входные сигналы и менять состояние системы. Делать это будем, используя два следующих вспомогательных метода:
Пока всё идёт как надо. Далее нам нужно реализовать действия success и failure и описать входные данные состояния fetching :
Полный пример работающей машины состояний можно найти в моём CodePen-проекте.
Управление машинами состояний с помощью библиотеки
Шаблон конечного автомата работает вне зависимости от того, используем ли мы React, Vue или Angular. Как мы видели в предыдущем разделе, реализовать машину состояний на чистом JS можно без особых сложностей. Однако, если доверить это специализированной библиотеке, это способно добавить проекту больше гибкости. Среди примеров хороших библиотек для реализации машин состояний можно отметить Machina.js и XState. В этой статье, однако, мы поговорим о Stent — моей Redux-подобной библиотеке, в которой реализована концепция конечных автоматов.
Stent — это реализация контейнера машин состояний. Эта библиотека следует некоторым идеям проектов Redux и Redux-Saga, но даёт, по моему мнению, более простые в использовании и менее скованные шаблонами возможности. Она разработана с использованием подхода, основанного на том, что сначала пишут документацию к проекту, а потом — код. Следуя этому подходу, я потратил недели только на проектирование API. Так как я самостоятельно писал библиотеку, у меня был шанс исправить проблемы, с которыми я столкнулся, используя архитектуры Redux и Flux.
Создание машин состояний в Stent
В большинстве случаев приложение выполняет множество функций. В результате лишь одной машиной нам не обойтись. Поэтому Stent позволяет создавать столько машин, сколько нужно:
Позже мы можем получить доступ к этим машинам, используя метод Machine.get :
Подключение машин к логике рендеринга
Рендеринг в моём случае выполняется средствами React, но мы можем использовать любую другую библиотеку. Всё это сводится к вызову коллбэка, в котором мы инициируем рендеринг. Одной из первых возможностей библиотеки, которую я создал, была функция connect :
Для удобства вспомогательные функции экспортированы в расчёте на интеграцию с React. Это очень сильно похоже на конструкцию connect(mapStateToProps) Redux.
Stent выполняет коллбэк и ожидает получить объект. А именно — объект, который отправлен как props компоненту React.
Что такое состояние в контексте Stent?
Мой опыт работы со Stent показывает, что если объект состояния становится слишком большим, то нам, возможно, нужна ещё одна машина состояний, которая могла бы обрабатывать эти дополнительные свойства. Идентификация различных состояний занимает некоторое время, но я полагаю, что это — большой шаг вперёд в деле написания приложений, которыми легче управлять. Это нечто вроде попытки заблаговременного планирования поведения системы и подготовки пространства для будущих действий.
Работа с машиной состояний
Практически так же, как в примере, приведённом в начале материала, нам, при работе со Stent, нужно задать возможные (конечные) состояния машины и описать возможные входные сигналы:
Входные данные и обработчики действий
Возможно, самое важное в этом примере — обработчики действий. Это — место, где мы пишем большую часть логики приложения, так как здесь описывается реакция системы на входные данные и на изменённые состояния. Порой мне кажется, что самые удачные архитектурные решения, принятые при проектировании Redux — это иммутабельность и простота функций-редьюсеров. В сущности, обработчики действий Stent — это то же самое. Обработчик получает текущее состояние и данные, связанные с действием, после чего он должен вернуть новое состояние. Если обработчик не возвращает ничего ( undefined ), тогда состояние машины остаётся неизменным.
Мы уже видели функцию-обработчик, и последний вариант обработчика действия — это функция-генератор. Идейным вдохновителем этого механизма стал проект Redux-Saga, выглядит это так:
Если у вас нет опыта работы с генераторами, вышеприведённый фрагмент кода может выглядеть немного таинственно. Однако, генераторы в JavaScript — это мощный инструмент. С их помощью можно приостановить обработчик действия, изменять состояние несколько раз и обрабатывать асинхронные механизмы.
Эксперименты с генераторами
Когда я впервые познакомился с Redux-Saga, я решил, что там представлен чрезмерно усложнённый способ поддержки асинхронных операций. На самом же деле это — весьма остроумная реализация шаблона command (команда). Главное преимущество этого шаблона заключается в том, что он разделяет вызов некоего механизма и его реальную реализацию.
Другими словами — мы сообщаем системе о том, чего мы хотим, но не говорим о том, как это должно произойти. В этом всём мне помогла разобраться серия материалов Мэтта Хикса, рекомендую с ней ознакомиться. Те же самые идеи я принёс и в Stent. Мы передаём системе управление, сообщая ей о том, что нам нужно, но на самом деле этого не делая. Как только действие выполняется, мы получаем управление обратно.
Вот что можно передавать системе в настоящий момент:
Этот код выглядит как синхронный, но, на самом деле, таковым он не является. Здесь мы видим, как Stent выполняет рутинные операции по ожиданию разрешения промиса и по работе с другим генератором.
Проблемы Redux и их решение с помощью Stent
▍Избавление от чрезмерного количества шаблонного кода
Архитектура Redux (как и Flux) основана на действиях, которые циркулируют в системе. По мере роста приложения, как правило, в нём появляется множество констант и создателей действий. Эти сущности обычно оказываются в разных папках, в результате анализ кода при его выполнении иногда требует дополнительного времени. Кроме того, при добавлении в приложение новой возможности, всегда приходится иметь дело с полным набором действий, что означает определение большего количества имён действий и создателей действий.
В Stent нет имён действий. Библиотека генерирует создателей действий автоматически:
▍Устранение непредсказуемых изменений состояния
В целом, Redux замечательно реализует иммутабельный подход к управлению состоянием приложения. Проблема заключается не в самом Redux, а в том, что разработчику позволено диспетчеризировать любое действие в любое время. Если предположить, что у нас есть действие, которое включает свет, нормально ли будет выполнить это действие два раза подряд? Если нет — тогда как решить эту проблему средствами Redux? Например, мы, возможно, поместим какой-то код в редьюсер. Этот код будет защищать логику приложения, проверяя при попытке включения света, не включен ли он ранее. Вероятно, это будет что-то вроде условного оператора, который проверяет текущее состояние.
Теперь вопрос заключается в том, не находится ли это действие за пределами сферы ответственности редьюсера? Следует ли редьюсеру знать о подобных пограничных случаях?
Чего мне не хватает в Redux, так этот способа остановки диспетчеризации действия, основанного на текущем состоянии приложения без загрязнения редьюсера условной логикой. И мне совершенно не хочется принимать подобное решение в том слое, где был вызван создатель действия. С помощью Stent фильтрация бессмысленных действий происходит автоматически, так как машина не реагирует на действия, которые не объявлены в текущем состоянии. Например:
Факт того, что машина принимает лишь специфические входные данные в конкретное время защищает нас от странных ошибок и делает наше приложение более предсказуемым.
Состояния как основа архитектуры приложений
Redux, как и Flux, заставляют нас мыслить в терминах переходов. Модель мышления, характерная для Redux-разработки, в основном, базируется на действиях, и на том, как эти действия трансформируют состояние в редьюсерах. Это не так уж и плохо, но я обнаружил, что гораздо выгоднее, во всех смыслах, оперировать не переходами между состояниями, а самими состояниями. При таком подходе разработчика будут занимать вопросы о том, какими могут быть состояния приложения, и о том, как эти состояния представляют требования логики функционирования проекта.
Итоги
Концепция машин состояний в программировании, особенно — в разработке пользовательских интерфейсов, стала для меня настоящим открытием. Я начал видеть машины состояний повсюду, у меня появилось желание везде, где это возможно, ими пользоваться. Я чётко вижу преимущества наличия в проекте строго определённых состояний и переходов между ними. Мне, в ходе работы, всегда хочется сделать мои приложения как можно более простыми, а их код — как можно более понятным. Я уверен, что машины состояний — это шаг в правильном направлении. Это — простая, и в то же время — мощная концепция. Её практическое использование вполне способно помочь сделать веб-приложения стабильнее и устранить множество ошибок, характерных для других подходов к разработке.
Уважаемые читатели! Пользуетесь ли вы машинами состояний при работе над своими проектами?