Конечный автомат (FSM) - важная концепция вычислений. Мы можем найти много вариантов поведения FSM в нашей реальной жизни, таких как торговые автоматы, лифты, светофоры и т. Д.

Программирование на основе конечных автоматов также является мощным инструментом для моделирования сложных переходов между состояниями, оно может значительно упростить нашу программу.

Что такое конечный автомат

Конечный автомат (FSM) или просто конечный автомат - это математическая модель вычислений. Это абстрактная машина, которая в любой момент времени может находиться ровно в одном из конечного числа состояний. Автомат может переходить из одного состояния в другое в ответ на некоторые входные данные; переход из одного состояния в другое называется переходом.

- Википедия

Автомат состоит из трех ключевых элементов: начального состояния, списка всех возможных состояний, входов, запускающих переход между состояниями.

Рассмотрим турникет в качестве простого примера моделирования конечных автоматов.

Как и другие конечные автоматы, конечный автомат турникета состоит из трех элементов:

  • Его исходное состояние - «Заблокировано».
  • У него есть два возможных состояния: «Заблокировано» и «Разблокировано».
  • Два входа вызовут изменение состояния: «Толчок» и «Монета».

Создайте программу на основе FSM на Голанге

Затем я создам программу из командной строки, которая имитирует поведение турникета.

Когда программа запускается, она предлагает пользователю ввести некоторые команды, после чего она изменит свое состояние в соответствии с введенной командой.

Версия 1, реализация FSM в простой форме

Во-первых, мы определили два состояния (Locked & Unlocked) и две допустимые команды (CmdCoin & CmdPush).

В функции main мы устанавливаем начальное состояние в Locked, выводим информацию об использовании пользователю.

Затем мы запускаем основной цикл, считываем командную строку из stdin, обрабатываем команду на основе текущего состояния.

Вы можете заметить, что нам нужно обрабатывать неизвестные команды для каждого состояния, это можно улучшить с помощью небольшого рефакторинга.

Кроме того, если выделить логику перехода состояния в функцию, программа будет более выразительной.

Версия 2, рефакторинг, чтобы сделать код более понятным

На практике конечный автомат часто представляется в виде Таблицы переходов между состояниями, для нашего примера с турникетом таблица выглядит так:

Мы можем реализовать автомат с таблицей перехода состояний.

Версия 3, представляет Таблицу переходов между состояниями

При таком подходе все возможные переходы перечислены в таблице. Его легко поддерживать и понимать. Если требуется новый переход, просто добавьте запись в таблицу.

Поскольку конечный автомат является абстрактной машиной, мы можем пойти еще дальше и реализовать его объектно-ориентированным способом.

Версия 4, смоделируйте автомат с классом

Представлен новый класс Turnstile, и у него есть свойствоState, метод с именем ExecuteCmd.

Единственный способ вызвать переход состояния - вызвать метод ExecuteCmd.

Отношение можно выразить с помощью орграфа ниже:

Сложите все вместе, вот полный исходный код:

Беги вверх

Давайте попробуем эту программу:

$ go run main.go
current state is [Locked], please input command [coin|push]
foo
unknown command, try again please
push
not allowed, unlock first
coin
unlocked, ready for pass through
coin
well, don't waste your coin
push
pass through, shift back to locked
push
not allowed, unlock first
^Csignal: interrupt
$

После запуска программы появится подсказка.

Если мы введем недопустимую команду «foo», мы получим ответ, что программа не знает эту команду.

Поскольку исходное состояние заблокировано, если мы попытаемся его «толкнуть», турникет не откроется. Разблокировать его может только команда «монета».

Но команда «монета» не действует на разблокированный турникет. Если в этой ситуации «нажать», турникет вернется в заблокированное состояние.

Пример выше демонстрирует все типичные переходы турникета.

Заключение

В этом рассказе мы представили концепцию конечного автомата и построили программу на основе конечного автомата.

Мы предоставляем четыре версии программы.

  • v1, реализуйте автомат в простой форме.
  • v2, сделайте некоторый рефакторинг, чтобы уменьшить дублирование кода
  • v3, представьте таблицу перехода состояний
  • v4, рефакторинг с ООП

Надеюсь, после этого путешествия вы почувствуете то же, что и я: FSM - это простой, но мощный инструмент, и мы должны добавить его в наш набор инструментов для программирования. Не правда ли?