Конечные автоматы в ДраконТех
ДраконТех генерирует программный код конечных автоматов на языках JavaScript и Lua.
Для чего нужны конечные автоматы
Конечные автоматы — прекрасный инструмент разработки алгоритмов управления.
Алгоритмы можно разделить на две большие группы: вычислительные алгоритмы и алгоритмы управления. Пример вычислительного алгоритма — расчёт корней квадратного уравнения. Общее свойство вычислительных алгоритмов — у них есть конец. Если в таком алгоритме нет ошибок, он всегда завершается.
Вторая группа — алгоритмы управления. Они характерны тем, что имеют дело с процессами, которые растянуты во времени. У многих алгоритмов управления нет конца. Пример: алгоритм управления биением сердца.
Проблема создания понятных и надёжных алгоритмов управления стоит остро. От этого зависит вся наша техносфера. Кроме того, сложные вычислительные алгоритмы тоже являются процессами. Сложными вычислениями тоже надо управлять. Управлять надо даже простыми программными объектами, такими как элементы пользовательского интерфейса. Всё это делает алгоритмы управления чрезвычайно важными и широко распространёнными.
Что такое конечный автомат
Конечный автомат — это объект, который может переключаться между несколькими состояниями. Количество таких состояний конечно, отсюда название: «конечный автомат». Автомат принимает конечное количество типов сообщений. Реакция автомата на сообщения зависит от того, в каком из состояний он находится.
Представьте себе класс, который имеет несколько методов. Отличие конечного автомата от класса заключается в том, что методы автомата работают по-разному в зависимости от того, в каком из состояний он находится. Например, лифт может ехать вверх, ехать вниз или стоять на месте. В зависимости от состояния автомата управления лифтом лифт будет по-разному откликаться на нажатия кнопок. Если двери лифта открыты, нажатие кнопки не приведёт к началу движения.
Оказалось, что конечные автоматы — удобная вещь для моделирования алгоритмов управления. Конечный автомат хорош тем, что помогает свести сложное поведение к нескольким сценариям. Эти сценарии легко выявить и протестировать.
Как изобразить конечный автомат в ДраконТех
Основная трудность при создании конечных автоматов — их наглядная визуализация. Существующие диаграммы конечных автоматов имеют недостатки. Один из недостатков — отсутствие логики переключения между состояниями. Другой недостаток — хаотическое расположение состояний на диаграмме.
ДРАКОН предлагает схему отображения конечных автоматов, лишённую этих недостатков. ДРАКОН позволяет поместить всю существенную информацию о конечном автомате на одной визуальной сцене. Эта информация включает логику выбора следующего состояния. Кроме того, конечные автоматы предстают на дракон-схеме в упорядоченном, единообразном стиле.
Предлагается следующая схема.
- Каждому состоянию конечного автомата соответствует одна ветка силуэта.
- На ветке помещается икона «Выбор» с ключевым словом receive. Иконы «Вариант» под этой иконой «Выбор» означают типы сообщений, которые автомат обрабатывает в данном состоянии.
- Ниже следует логика, которая содержит действия, которые автомат осуществляет при обработке данного сообщения, а также выбор следующего состояния.
- Выбор следующего состояния делается при помощи иконы «Адрес». «Адрес» указывает на следующее состояние автомата.
Для каждой ветки силуэта икон «Адрес» может быть несколько. То есть в зависимости от ситуации при получении некоего сообщения автомат может выбрать, в какое состояние перейти.
Для каждой иконы «Вариант» на всех ветках силуэта ДраконТех создаст метод-обработчик. Сигнатура обработчика (его название и принимаемые аргументы) берётся из иконы «Вариант». Автомат может ожидать одно и то же сообщение в одном или нескольких состояниях. При этом сигнатура сообщения должна совпадать для всех состояний.
Для случаев, когда в каком-то состоянии автомат ожидает только один вид сообщений, можно применять икону «Простой ввод». В иконе «Простой ввод» указывается сигнатура метода-обработчика сообщения в том же формате, что и в иконах «Выбор».
Иконы "Простой ввод" и "Выбор" с receive — это точки, где алгоритм автомата останавливается и ожидает входящие сообщения.
Вот пример конечного автомата из демонстрационного приложения "Лифт". Этот автомат управляет кабиной лифта.
Пример конечного автомата на языке ДРАКОН
Автомат CabinMachine имеет несколько состояний:
- ClosedStill. В этом состоянии автомат ожидает одно сообщение onCommand.
- Opening. Ожидаемые сообщения: update, onDoor.
- Open. Ожидаемое сообщение: onTimeout.
- Closing. Ожидаемые сообщения: update, onCommand, onDoor.
- Moving. Ожидаемые сообщения: update, onArrived, onCommand.
Выражения в иконах "Вариант" и "Простой ввод" выглядят как вызовы функций: onTimeout(), onDoor(). Но это объявления методов-обработчикаов. Старужи их можно вызвать так: cabin.onDoor().
В данном автомате обработчики не принимают аргументов. Аргументы можно добавить, и тогда метод-обработчик будет принимать эти аргументы. Аргументы обработчика доступны в автомате до следующей иконы "Простой ввод" или "Выбор" с receive.
Пример: если мы поместим в икону "Вариант" код onDoor(info), аргумент info будет добавлен методу-обработчику. Значение аргумента info будет доступно до следующей точки ожидания.
Объект автомата доступен в автоматной дракон-схеме под именем me. Этим можно пользоваться для доступа к полям объекта автомата.
Ещё одно применение объекта me — получение метода-обрабочика конкретного события как делегата. Паттерн использования этой возможности такой: сначала передаём делегат как callback в какую-то функцию, потом ожидаем события.
Пример такого паттерна в автомате CabinMachine: в ветке Open мы сначала передаём обработчик события onTimeout: setTimeout(me.onTimeout, doorTimeout). Потом мы ожидаем наступления события onTimeout: onTimeout().
Преимущества представления конечных автоматов при помощи дракон-схем силуэт
При беглом взгляде на диаграмму становится сразу понятно, какие состояния возможны для данного конечного автомата. Для этого достаточно увидеть заголовки веток. Так как заголовки веток силуэта расположены на одной горизонтальной линии в самом верху диаграммы, не нужно сканировать всю диаграмму, чтобы их найти.
Для каждого состояния легко определить, какие типы сообщений автомат ожидает в данном состоянии. Для этого нужно просмотреть иконы «Выбор». Иконы «Выбор» тоже выстроены по горизонтальной линии.
Ниже икон «Выбор» следуют деревья принятия решений о действиях автомата и переходе в следующее состояние. Переходы указаны в иконах «Адрес», которые также расположены на одной горизонтали. Поэтому одного взгляда на ветку силуэта достаточно, чтобы увидеть, в какие следующие состояния автомат может перейти из текущего состояния.
Принудительная остановка автомата
Преимуществом таких конечных автоматов является возможность остановить их принудительно при помощи метода stop(). То есть клиентский код может выключить конечный автомат. Если при этом автомат ожидает каких-то внешних событий, например событий сети или действий пользователя, то, когда эти события поступят, автомат их проигнорирует. Такое «мягкое» выключение автоматов исключает ошибки, которые возникают, когда приходят события, которых программа уже не ожидает. Выключенный автомат игнорирует любые события и не бросает исключений.
Автоматы как асинхронные функции
Чтобы запустить конечный автомат, сгенерированный на языке JavaScript, нужно вызвать его метод run().
Метод run() возвращает объект типа Promise. Благодаря этому можно ожидать окончания работы автомата при помощи ключевого слова await. То есть метод run() — это асинхронная функция.
В автоматной дракон-схеме можно применить ключевое слово return с некоторым значением. Это значение можно получить в клиентском коде при помощи await так же, как для асинхронных функций.
В итоге получается удобная конструкция. С одной стороны, она обладает свойствами конечного автомата. С другой — позволяет вызывающему коду дожидаться окончания работы автомата при помощи await. При этом алгоритм конечного автомата должен иметь конец.
ДраконТех генерирует конечные автоматы и для алгоритмов без выхода, но ожидание окончания работы такого автомата в операторе await зависнет навсегда.
Таким образом, для JavaScript ДраконТех генерирует асинхронные функции на стероидах, которые реагируют на внешние события. Кроме того, такие асинхронные функции можно остановить извне.
Генерация кода для автоматов на JavaScript
ДраконТех поддерживает генерацию кода конечных автоматов для языков JavaScript и Lua.
Для того чтобы указать генератору кода, что данная дракон-схема описывает конечный автомат, нужно вставить хотя бы одну икону «Выбор» с ключевым словом receive или икону «Простой ввод». В конечный автомат можно превратить как свободную функцию, так и метод класса.
Для автоматной дракон-схемы ДраконТех генерирует фабричную функцию, которая создаёт объект автомата. Объект автомата имеет метод run(), который запускает автомат, и метод stop(), который принудительно останавливает его во время работы.
Методы run() и stop() нельзя вызывать изнутри автомата. Метод run() можно вызвать только один раз.
Существуют два способа использовать автомат в JavaScript:
- Явное создание объекта автомата и вызов run().
- Неявное создание объекта автомата и ожидание результата автоматного алгоритма через await.
Явное создание. Чтобы создать экземпляр автомата, нужно вызвать фабричную функцию, которая имеет имя ИмяАвтомата_create. Потом нужно вызвать метов run().
machine = SomeMachine_create(x, y) machine.run() machine.someMethod(z)
Неявное создание. Автоматная функция вызывается как обычная асинхронная функция:
result = await SomeMachine(x, y)
Генерация кода для автоматов на Lua
Автоматы ДраконТех на языке Lua поддерживают только явное создание объектов автомата:
machine = SomeMachine(x, y) machine.run() machine.someMethod(z)
Обратите внимание, что имя автомата не нужно дополнять строкой _Create.
Типичная ошибка программирования автоматов: повторный вход
При программировании конечных автоматов нужно избегать ситуации, когда происходит повторный вход в логику автомата, когда он ещё не закончил обрабатывать предыдущее событие.
Конечные автоматы, сгенерированные ДраконТех, вызывают ошибку при попытке повторного входа в логику автомата. Эта неприятная ситуация будет немедленно обнаружена, что поможет найти и устранить ошибку.
Чтобы избежать повторного входа в алгоритм автомата, нужно продумать архитектуру так, чтобы автомат не вызывал код, который вызовет методы автомата, включая stop().
Если логика программы такова, что этого нельзя избежать, методы автомата следует вызывать отложенным способом. То есть надо перенести вызов методов в следующий шаг работы программы. В JavaScript это делается при помощи функции setTimeout(): setTimeout(() => machine.method(), 0). ДраконТех может обернуть вызов метода автомата в setTimeout() автоматически. Для этого надо поместить вызов метода в икону «Простой вывод».
Многие задачи решаются при помощи нескольких автоматов. Чтобы избежать повторного входа в обработчики, нужно организовать автоматы в иерархию. Иными словами, нужно построить дерево автоматов. Далее следует ввести правила, по которым автоматы в дереве будут передавать сообщения друг другу.
Правила передачи сообщений между автоматами
- Только родительский автомат вызывает методы дочерних автоматов напрямую.
- Во всех остальных случаях автоматы вызывают методы других автоматов отложенным способом. Примеры: вызов методов родительского автомата, вызов методов автоматов-братьев.
- Автомат никогда не вызывает свои собственные методы.
Силуэт показывает автомат как единое целое
Конечные автоматы можно программировать при помощи дракон-схем и без помощи силуэта и икон «Выбор» с ключевым словом receive. Например, можно создавать наглядные конечные автоматы при помощи деревьев принятия решений. Дракон-схемы типа «примитив» отлично подходят для изображения принятия решений.
Проблема здесь заключается в том, что деревья принятия решений и другие стандартные методы реализации конечных автоматов разрывают логику автомата. Предлагаемый в ДраконТех метод, напротив, помогает увидеть конечный автомат как единое целое. При помощи дракон-схемы «силуэт» можно увидеть конечный автомат как единый поток управления, который циркулирует между состояниями.
Заключение
Конечные автоматы — не новая технология. Они существуют десятилетиями и доказали свою эффективность во множестве областей: от пользовательских интерфейсов до промышленных систем управления. Проблема обычно заключается не в самих автоматах, а в том, что по мере роста сложности их становится трудно понимать и сопровождать.
Подход, реализованный в ДраконТех, направлен именно на решение этой проблемы. Он позволяет увидеть состояния, сообщения, действия и переходы на одной визуальной сцене и воспринимать автомат как единое целое, а не как набор разрозненных обработчиков событий.
Ссылки
Автоматное программирование на языке ДРАКОН. С. Б. Митькин