9: Автоматное программирование: анализ задачи

Привет, Вы узнаете о том , что такое автоматное программирование, Разберем основные их виды и особенности использования. Еще будет много подробных примеров и описаний. Для того чтобы лучше понимать что такое автоматное программирование , настоятельно рекомендую прочитать все из категории Стили и методы программирования.

Автоматные задачи

Многие программистские задачи удобно решать с помощью методов, формализацией которых могут служить таблицы состояний и переходов (напр., их собрание см. в [32] и на сайте http://is.ifmo.ru).

Пример 9.1.1. Модель изменяющейся системы.

Пусть мы моделируем динамическую либо экологическую систему, у которой в различных областях принципиально разное поведение. Вместо того, чтобы совмещать внутри одного и того же программного модуля анализ, какой области принадлежит точка, и вычислениеследующего состояния системы, мы можем написать несколько простых модулей моделирования поведения системы в каждой из областей (единственная проверка, которая при этом может понадобиться, вышли мы при очередном шаге моделирования за границы области или нет). Как отдельный модуль строится глобальная управляющая программа, которая проверяет, в каком состоянии находится система, и вызывает соответствующий вычислительный модуль.

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

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

Теоретически автомат Мура представляется как матрица переходов, строками которой служат состояния автомата, а столбцами - входные символы¹ . В качестве входных символов на практике можно рассматривать результаты проверки некоторых условий. Неявное в теории, но важнейшее на практике содержимое каждого состояния автомата - процедура, приводящая к глобальному изменению состояниявычислительной системы. Такие процедуры назовем действиями.

Таблицы автоматов часто также представляются в виде графов, что особенно удобно, когда не все возможные переходы междусостояниями реализуемы. См., напр., рис. 9.1, где представлены и таблица, и граф.

Рис. 9.1. Таблица состояний. Граф переходов.

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

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

Имеется вариация понятия автоматов, порождающая другой метод автоматного программирования. В теории автомат Мили отличается тем, что результат, записываемый на выходную ленту автомата, может зависеть от выбранного перехода. На практике действия в таблице состояний и переходов могут ассоциироваться либо с состояниями (с вершинами графа, автомат Мура ), либо с переходами (с дугами графа, автомат Мили ). Ниже Вы увидите примеры, когда при программировании естественно возникают оба этих варианта². Модель вычислений автомата Мили лучше использовать, если проверки в каждом состоянии по существу различны, а модель автоматов Мура - если проверки по существу однородны, как в примере 9.1.1.Метод программирования, когда действия сопоставляются переходам, назовемпреобразованиями на переходах (сокращенно просто "на переходах "), метод, когда действия производятся в состояниях, назовемпреобразованиями в состояниях (сокращенно просто "в состояниях ").

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

Внимание!

В данном случае мы видим один из неистощимых источников ошибок в программах, который впервые заметил Д. Грис. Если по сути задачи нам все равно, какое из действий будет выполнено, а язык (как те стандартные языки, на которых обычно работают) заставляет детерминировать переходы, либо ранжировав их по порядку, либо принудительно сделав их условия логически противоречивыми, то при изменении программы часто возникают трудности. Они связаны с тем, что после изменения детерминировать-то надо было по-другому, но уже нельзя различить, какие из условий существенны, а какие вставлены лишь для детерминации.

Как было показано в нашем примере, таблицы переходов и состояний являются естественным способом программирования для модуля, имеющего дело с глобальными операциями над некоторой средой (эти глобальные операции сами, как правило, программируются в другом стиле). Для автоматного программирования характерно go to, и здесь оно на месте.

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

Основные структуры автоматного программирования

Информационное пространство всех блоков и процедур при автоматном программировании в первом приближении одно и то же: состояния системы, моделируемой совокупностью программных действий. Но на самом деле многие блоки либо процедуры работают с подсистемами. Подсистемы, ввиду их автономности, могут иметь характеристики, прямо недоступные для общей системы, и ограниченный доступ к общему системному пространству данных. Более того, подсистемы могут общаться прямо, в обход иерархически вышестоящей системы (см.рис. 9.2). Таким образом, структура информационного пространства при автоматном программировании в общих чертах соответствует той, которая навязывается современными системами с развитой модульностью³. В системах модульности есть понятия, предоставляемые для пользования другими модулями, есть модули, которые автоматически получают доступ ко всем понятиям дружественного модуля, и есть интерфейсы между модулями.

Рис. 9.2. Информационное пространство систем

Светло-серые области - традиционный общий контекст системы и подсистемы. Темно-серые иллюстрируют, что доступность может быть односторонней, и не только по иерархии. Одна из систем может влиять на часть информационного пространства другой, а та может лишь пассивно следить, что натворил коллега. Области, связанные двусторонними стрелками, иллюстрируют прямое общение в обход иерархии.

Исторически первой моделью автоматного программирования, использованной как на практике, так и для теоретических исследований, было представление программы в виде блок-схемы (см., напр., рис. 9.3), узлы которой являлись состояниями. Узлы блок-схемы делятся на пять типов:

• начальная вершина, в которую нет входов и где производится инициализация переменных либо состояния вычислительной системы;
• действия, при которых исполняется вызов процедуры либо оператор и после которых автомат однозначно переходит в следующеесостояние ;
• распознаватели, проверяющие значение переменной либо предиката и затем передающие управление по разным адресам;
• соединения, в которые имеется несколько входов и один выход;
• выход, попав в который, программа заканчивает работу.

Рис. 9.3. Блок-схема

Представление программ в виде блок-схем было целесообразно для многих классов программ, писавшихся в машинных кодах без средств автоматизации программирования. Блок-схемы тогда были основным средством планирования разработки программ и их документирования. Традиционные блок-схемы - предмет изучения, в частности, теоретического программирования (см. книги Котова [16], [17]).

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

Действия в автоматном программировании глобальны, а условия локальны. Проверка условия не изменяет состояния всей системы (ни одного из ее параметров или характеристик), она лишь переводит саму программу в то или иное состояние.

Это подтверждает и анализ практических систем, для моделирования которых удобно применять автоматное программирование. Об этом говорит сайт https://intellect.icu . Например, открытие или закрытие одного вентиля в трубопроводной системе изменяет все потоки в системе, а проверка - открыт ли вентиль - локальная операция. Изменение температуры рабочего вещества в системе опять-таки влияет на все ее характеристики, а измерить эту температуру можно, сняв показания всего одного датчика.

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

Необходимость одновременного и согласованного рассмотрения внешних и внутренних характеристик приводит к тому, что, когда внутренние характеристики раздробляются и детализируются (например, при соединении стиля автоматного программирования с присваиваниями), программист начинает путаться, согласованность понятий исчезает и возникают ошибки.

Внимание!

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

Граф состояний и переходов, называемый также таблицей переходов — нагруженный ориентированный граф G. Каждой вершине графа G сопоставлено наименование состояния, а каждой дуге — условие.

Условие AB, сопоставленное дуге, ведущей из a в b, содержательно интерпретируется следующим образом. При выполнении AB всостоянии a управление передается состоянию b (или же в другом смысле осуществляется переход по данной дуге).

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

Программные представления графа состояний

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

1. Состояния и таблица переходов жестко заданы постановкой задачи (например, такова задача синтаксического анализа). В этом случае лучшее программное представление переходов между состояниями - go to, независимо от размера таблицы.
2. Состояния и таблица переходов пересматриваются, но фиксированы между двумя модификациями задачи. При небольших размерах таблицы по-прежнему предпочтительней всего реализация через переходы, а при достаточно больших - необходима ее декомпозиция, в связи с чем часто целесообразно представление состояний объектами.
3. Состояния и таблица переходов динамически порождаются перед выполнением данного модуля и фиксированы в момент его выполнения. Лучший способ реализации - задание таблицы переходов в виде структуры данных и написание интерпретирующей программы для таких таблиц.
4. "Живая таблица": модифицируется в ходе исполнения. Пока что дать методологические советы для таких таблиц мы не можем, хотя очевидно, что, несмотря на внешнюю рискованность, такой путь чрезвычайно выигрышен для многих систем адаптивного реагирования. Заранее нужно обговорить, что модули, перестраивающие таблицу, и модули, исполняющие ее, должны быть как можно более жестко разделены.

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

В данном разделе начинается детальный показ двух методов автоматного программирования, основанных на модели Мура и Мили. Методика работы в них почти одна и та же, но, как чаще всего бывает, маленькое и вроде бы техническое различие (чему сопоставляются действия:состояниям или переходам?) порождает два несовместимых метода. Их несовместимость не столь грубая, как во многих других случаях (два таких случая - несовместимость между автоматами и присваиваниями и между циклами и рекурсиями - рассмотрены ниже). Если это и противоречие, то противоречие технологическое. Произвольно перемешивая эти два метода, мы в дальнейшем затрудняем модификацию программы, а в настоящем вынуждены множить число подпорок.

Человек даже грубые противоречия игнорирует или обходит ⁴. Для применения правила важно знать не только его, но и когда можно его нарушать. Общеметодологический принцип здесь такой: если уж нарушать, то на полную катушку (проехав перекресток на красный свет, глупо останавливаться сразу за ним)! Второй принцип: если нельзя, но очень нужно, то надо! А. А. Шалыто указал, что в теории ⁵ есть и такое смешанное понятие, как автоматы Мили-Мура. Одной из моделей таких автоматов является автомат с двумя выходными лентами: на одну пишется результат в состояниях, на другую - на переходах. Программной интерпретацией такой теоретической модели является, например, модуль, который в состояниях ведет диалог с окружающей средой, в результате чего получает данные для определения очередного перехода, а на переходах производит внутренние вычисления.

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

Постановка задачи и первичный анализ

Пусть требуется решить следующую задачу. Словом называется любая непустая последовательность букв латинского алфавита (для простоты - только строчных букв). Перепечатать из входной последовательности символов все максимальные входящие в нее слова в следующем виде:

<слово> - <длина слова><конец строки печати>

Ввод заканчивается пустой строкой.

Например, по строкам

попугай бегемот
1мот2крот1мот

нужно выдать что-либо вроде

попугай 7
бегемот 7
мот 3
крот 4
мот 3

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

Построение графа состояний

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

Вот полный перечень вариантов реакций:

1. Символ буква: инициализировать обработку слова (счетчику длины слова присвоить единицу).
2. Символ буква: продолжить обработку слова (счетчик длины слова увеличить на единицу).
3. Символ не буква: закончить обработку слова (напечатать длину прочитанного слова).
4. Символ не буква: пропустить символ.
5. Символ конец строки: закончить обработку слова (напечатать длину прочитанного слова).
6. Символ конец строки: пропустить символ.
7. Символ конец строки: завершить процесс.

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

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

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

Для рассматриваемого случая в начальном состоянии ( St1 ), возможны переходы:

1. с переходом в другое состояние - St2 (поскольку следующая буква требует другой реакции),

4. с сохранением состояния и

6. отработка первого перевода строки.

Рис. 9.4. Начало построения графа состояний по Муру

Результат только что проведенного анализа можно представить в виде графа, изображенного на рис. 9.4. С каждой дугой графа связано условие перехода. С каждым состоянием может быть связано действие. В состояниях St1 и St3 действием является пропуск очередного символа и чтение следующего, но соединить их сейчас нельзя, поскольку в первом из них переход на завершение работы невозможен, так что перевод строки анализируется по-разному. Это позволяет предположить, что в данной задаче действия стоит ассоциировать спереходами, а не с состояниями. Правильный выбор того, с чем ассоциировать действия, может сильно оптимизировать программу. Для показа двух возможных вариантов, которые в данном случае почти эквивалентны по сложности, мы будем действовать как на переходах, так и в состояниях. В частности, предварительный анализ состояний при методе преобразований на переходах дан на рис. 9.5.

Рис. 9.5. Начало построения графа состояний при использовании метода на переходах

Внимание!

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

На схемах вход и выход обозначаются черными прямоугольными блоками. При желании их можно считать специальными состояниями, с которыми ассоциированы действия инициализации и завершения процесса. Состояние St2 изображено штриховой линией, поскольку анализего еще не проведен. Для каждого из еще не проанализированных состояний (в данном случае для St2 ) следует определить условияперехода (и соответствующие им действия, если выбрали работу на переходах ).

В рассматриваем случае в состоянии St2 возможны переходы:

2. с сохранением состояния ;

3. окончание слова и отработка вывода слова, поскольку следующий символ не буква, с переходом в другое состояние, которому дается временное имя St4 ;

5. отработка окончания слова и перевода строки, ему можно дать временное имя St5.

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

Для решаемой задачи легко выяснить, что состояние St3 требует тех же действий и переходов, что и St5, а St4 изоморфно St1. Следовательно, возможна склейка этих двух состояний со старыми и построение графа завершается, так как новых состояний нет (см. рис. 9.6). С тем, чтобы не дублировать действия <Завершить процесс>, можно определить еще одно, заключительное состояние, с выходом из которого будет ассоциировано это действие (один раз!).

Рис. 9.6. Полученный граф состояний при действиях на переходах

Аналогично можно поступить и когда мы работаем в состояниях. Здесь процесс удлиняется на один шаг, поскольку необходимо выделить завершение обработки слова в отдельное действие (причем в двух вариантах: после перевода строки и после других небуквенных символов). Полученный результат показан на рис. 9.7.

Рис. 9.7. Полученный граф состояний при действиях в состояниях

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