Упражнение 30: Конечные автоматы состояний

Исходник: Exercise 30: Finite State Machines

Переводчик: Феликс Чернов

Лицензия: CC BY-NC-SA 4.0

Официально использует Google Translate

Каждый раз, когда вы читаете книгу по парсингу, есть один ужасный раздел, посвящённый конечному автомату состояний (КАС). Они подробно анализируют "ребра" и "узлы", каждый возможный набор "автомата" преобразуется в другой автомат, и честно говоря, это немного много. КАС имеет более простое объяснение, которое делает его практичным и понятным, не нарушая теоретическую версию того же самого предмета. Конечно, вы не будете отправлять статью в ACM, потому что вы не знаете всей математики, лежащей за КАС, но если вам просто нужно использовать их в приложении, то они достаточно просты.КАС — это способ организации событий, происходящих на последовательности состояний. Другой метод определения событий — это "триггер входа", аналогичный булевому выражению в if-выражении, но обычно менее сложный. Событие может быть нажатием кнопки, получением символа из потока данных, изменением даты или времени, а также почти любым другим способом заявления события. Состояние — это любая "позиция", где ваш КАС останавливается, пока он ждет новых событий; каждое определённое состояние позволяет определённые события (входы). События часто являются временными, а состояния обычно постоянными, и оба могут быть представлены как данные. Наконец, вы можете привязать код к событиям или состояниям, а также решить, следует ли запускать код при входе в состояние, внутри него или при выходе из него.КАС — всего лишь один из методов, который используется для выполнения различных событий в разных местах, с использованием белого списка для указания возможного кода, который можно выполнить. В КАС, когда вы получаете неожиданное событие, происходит отказ, поскольку вам нужно явно указывать, какие события (или условия) допустимы для каждого состояния. if-выражения также могут обрабатывать возможные ветвления, но это черный список для всех возможностей. Если вы забудете else-ветку, то любое условие if-elif, которое не покрыто, вернётся к значению по умолчанию.

Давайте разберём это: + Вы имеете состояние, которое является индикатором текущего положения машины состояний (МСС). Состояние может быть "начало", "нажата клавиша", "остановка" или аналогично описывает возможное местоположение МСС в процессе выполнения. Каждое состояние указывает на то, что система ожидает какого-то события перед тем, как принять решение о следующем действии.+ Вы также имеете события, которые могут перемещать МСС из одного состояния в другое. Эти события могут быть "нажата клавиша", "соединение сокета завершилось ошибкой", "файл сохранён" и так далее; они представляют собой внешние стимулы, которые заставляют МСС принимать решения относительно того, что делать дальше и какое следующее состояние выбрать. Одно событие даже может вернуться в то же самое состояние, что позволяет создавать циклические переходы.+ В зависимости от события, МСС переходит из одного состояния в другое, и это происходит строго благодаря определённому событию, связанному со состоянием (хотя одно из этих событий может быть определено как "любое событие"). Они никогда не "случайно" переходят в новое состояние; вы можете точно отследить их переходы между состояниями, просматривая события и доступные состояния. Это делает их очень удобными для отладки.

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

• Иногда "отсутствие события" само по себе является событием. Это хорошо и мощно, поскольку означает, что даже если ничего не произошло, вы всё равно можете перейти МСС в новое состояние. Однако на практике "отсутствие события" часто является скрытым событием "повторите попытку" или "просыпайтесь". В других случаях это состояние может означать "неопределенно, возможно следующее событие сообщит мне, какое состояние это".Пожалуйста, обратите внимание, что в этом переводе были использованы специальные термины и понятия, характерные для области программирования и теории автоматов. Сила конечного автомата (КА) заключается в возможности четко описать каждый событие, где события представляют собой данные, принимаемые системой. Это делает КА очень удобными для отладки, тестирования и правильной реализации, так как вы точно знаете все возможные состояния и то, что может произойти при каждом событии в каждом состоянии. В этом упражнении вам предстоит изучить библиотеку КА и пример использования КА, чтобы понять принцип их работы.## Упражнение

Я создал модуль CA, который обрабатывает простые события для управления соединениями веб-сервера. Это вымышленный пример CA, который демонстрирует быстрое написание CA на Python. Он представляет базовый шаблон для обработки соединений, чтения и записи данных через сокеты, но он недостаточен для полной реализации, это всего лишь небольшой пример.

def START():
    return LISTENING

def LISTENING(event):
    if event == "connect":
        return CONNECTED
    elif event == "error":
        return LISTENING
    else:
        return ERROR

def CONNECTED(event):
    if event == "accept":
        return ACCEPTED
    elif event == "close":
        return CLOSED
    else:
        return ERROR

def ACCEPTED(event):
    if event == "close":
        return CLOSED
    elif event == "read":
        return READING(event)
    elif event == "write":
        return WRITING(event)
    else:
        return ERROR

def READING(event):
    if event == "read":
        return READING
    elif event == "write":
        return WRITING(event)
    elif event == "close":
        return CLOSED
    else:
        return ERROR

def WRITING(event):
    if event == "read":
        return READING(event)
    elif event == "write":
        return WRITING
    elif event == "close":
        return CLOSED
    else:
        return ERROR

def CLOSED(event):
    return LISTENING(event)

def ERROR(event):
    return ERROR

Также есть небольшой тест, показывающий, как запустить этот CA:

import fsm

def test_basic_connection():
    state = fsm.START()
    script = ["connect", "accept", "read", "read", "write", "close", "connect"]
```    for event in script:
        print(event, ">>>", state)
        state = state(event)

```Ваша задача в этом упражнении — преобразовать этот пример модуля в более мощный и универсальный класс FSM на Python. Вы должны использовать его как набор подсказок для понимания того, как обрабатывать входящие события, как состояние может представляться как Python-функция, а также как осуществляются неявные переходы. Обратите внимание, что иногда я возвращаю функцию для следующего состояния, но в других случаях вызываю функцию состояния? Попробуйте понять, почему я делаю это, так как это очень важно для работы с FSM. Для завершения этого вызова вам потребуется изучить модуль Python inspect, чтобы понять, что вы можете делать с объектами и классами Python. Есть специальные переменные, такие как __dict__, а также функции в inspect, которые помогут вам исследовать классы или объекты и найти функции.```Вы также можете перевернуть это проектирование. Вы можете использовать события как методы в подклассах и проверять текущее состояние `self.state` внутри этих событийных функций, чтобы определить следующий шаг. Это полностью зависит от того, что вы обрабатываете, имеете ли вы больше событий или состояний, и что имеет смысл в данный момент.

Наконец, вы можете использовать дизайн, где есть класс `FSMRunner`, который знает только, как запускать такие модули. Это имеет некоторые преимущества перед одним классом, знающим, как запускать свои собственные экземпляры, но также имеет свои недостатки. Например, как `FSMRunner` будет отслеживать текущее состояние? Будет ли это находиться в модуле или в экземпляре `FSMRunner`?

## Исследовательское обучение

+ Улучшите ваши тесты, сделав их более универсальными, и создайте FMS для совершенно другой области, знакомой вам.
+ Добавьте возможность логировать события, запущенные в вашей реализации. Одним из крупнейших преимуществ использования FMS для обработки событий является то, что можно хранить и записывать все события и состояния, получаемые FMS. Это позволяет вам отлаживать, почему система достигает нежелательного состояния.

## Глубокое изучение

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