Рассмотрев два типа автоматов: абстрактные, применяемые в теории формальных языков, и структурные, которые используются в логическом управлении, — попытаемся обобщить полученные сведения, указать сходства и различия автоматных моделей и выделить те их черты, которые важны при применении автоматов в программировании. Цель этого раздела — построить модель автоматизированного объекта управления (для краткости называемого просто автоматизированным объектом, АО). Это понятие уже было введено неформально в параграфе 1.3 как совокупность управляющего автомата и объекта управления. Предпосылкой для создания этой концепции была необходимость проектирования и реализации систем со сложным поведением. Теперь попробуем прийти к понятию автоматизированного объекта управления с другой стороны — путем обобщения традиционных автоматных моделей.
Вспомним абстрактные модели автоматов, рассмотренные в разделе 1.4.1. Как отмечалось выше, все они имеют похожую структуру: состоят из устройства управления представляющего собой ДКА с выходом) и хранилища данных того или иного вида (лента, магазин). Для теории формальных языков вид хранилища и набор элементарных операций с данными имеют решающее значение: они определяют вычислительную мощность машины. При моделировании и высокоуровневой программной реализации сущностей со сложным поведением удобнее заменить конкретное хранилище данных объектом управления (ОУ), множество вычислительных состояний которого может быть любым и определяется спецификой решаемой задачи (рис. 1.20).Вместо ограниченного набора элементарных операций с данными будем использовать произвольные запросы и команды1. В соответствии с традицией теории формальных языков такой вычислитель можно было бы назвать автоматом с произвольной памятью. Важная черта устройства управления всех абстрактных машин — его конечность. Управляющий автомат не только имеет конечное число состояний, но, кроме того, реализуемые им функции переходов и выходов оперируют исключительно конечными множествами. Именно это свойство позволяет описывать логику поведения машины явно: в виде таблицы или графа переходов. Поэтому свойство конечности устройства управления необходимо сохранить при построении модели автоматизированного объекта. Более того, это свойство целесообразно усилить следующим неформальным требованием: число управляющих состояний, входных и выходных воздействий должно быть небольшим, обозримым. Управляющий автомат с тысячей состояний, безусловно, является конечным, однако изобразить его граф переходов практически невозможно, что сводит на нет преимущества явного выделения управляющих состояний. Напротив, число вычислительных состояний может быть сколь угодно большим (при переходе от модели к программной реализации оно с необходимостью станет конечным, однако может остаться необозримым). В процессе работы управляющему автомату требуется получать информацию о вычислительном состоянии и изменять его. Однако в силу свойства конечности автомат не может напрямую считывать и записывать вычислительное состояние. Для этого и требуются операции объекта управления. Небольшое число запросов, возвращающих конечно значные результаты, позволяет автомату получать информацию о вычислительных состояниях, которую он способен обработать. Небольшое число команд используется для «косвенного» изменения вычислительных состояний. Операции с памятью в традиционных абстрактных вычислителях также можно считать командами и запросами. Рассмотрим, например, автомат с магазинной *1 В объектно-ориентированном программировании запросами (или чистыми функциями) называются компоненты класса, возвращающие значение и не имеющие побочных эффектов. Такие компоненты не изменяют вычислительные состояния объекта, но позволяют получить некоторую информацию об этих состояниях. Другой тип компонентов класса (команды), напротив, предназначен для изменения состояний объектов. памятью. Его множество вычислительных состояний бесконечно: это множество всех возможных конфигураций стека. Для управления стеком автомат использует один запрос top, возвращающий символ на вершине стека, и две команды pop и push, первая из которых снимает символ со стека, а вторая заталкивает символ в стек *1.В вопросах, связанных с программированием, важна не только структура АО, но и особенности процесса его работы. Работа всех рассмотренных автоматных моделей разбита на такты. За такт модель успевает считать входное воздействие, вычислить функции переходов и выходов и обновить значения выходных и внутренних переменных. Некоторые из рассмотренных моделей (например, ДКА и детерминированный МП-автомат) начинают следующий такт работы только в том случае, если получают на вход очередной символ. Их работа всегда заканчивается при достижении конца входной строки. Обобщая такое поведение, введем понятие пассивной автоматной модели: каждый такт ее работы инициируется внешней средой, а по окончании такта управление передается обратно этой среде. У таких автоматных моделей, как машина Тьюринга и структурные автоматы, напротив, после окончания текущего такта немедленно начинается следующий. Процесс работы продолжается до тех пор, пока автомат способен совершить очередной переход2. Такие автоматные модели можно назвать активными, поскольку будучи однажды запущенными, они не нуждаются в дальнейших «стимулах» для продолжения работы. На самом деле при аппаратной реализации синхронных структурных автоматных моделей начало нового такта инициируется тактовым генератором. Однако предполагается, что он является «внутренним» для автомата по сравнению с внешней средой, подающей входные воздействия. Поэтому с точки зрения среды такой автомат является активным. Если активная автоматная модель в качестве входного воздействия считывает вычислительное состояние внешней среды, то для пассивной характерно событийное взаимодействие: среда сама (асинхронно) сигнализирует о своем изменении, вызывая автоматную модель с некоторым событием. В программировании целесообразно использовать как активные, так и пассивные автоматные модели в зависимости от решаемой задачи. В пассивной модели, в общем случае, лишь некоторые компоненты входного воздействия являются событиями, а остальные представляют собой «традиционные» входные перемен 1 Push можно считать как одной командой, аргументом которой является заталкиваемый символ, так и набором команд без аргументов — по одной для каждого символа магазинного алфавита. Это не имеет значения, поскольку магазинный алфавит конечен.2 Такой критерий завершения работы используется при описании машин Тьюринга. При спецификации поведения программных систем в целях наглядности удобно выделять на графах переходов специальные конечные, или завершающие, состояния. Переход в любое из таких состояний приводит к немедленному завершению работы автоматные: их значения опрашиваются самим автоматом, а их изменения не инициируют начало такта. Вернемся к абстрактным вычислителям. Заметим, что в некоторых из них (таких, как ДКА) автомат взаимодействует только с внешней средой, получая от нее входные символы. В других (например, в машине Тьюринга) — автомат общается лишь со своим объектом управления, или, в терминах теории абстрактных автоматов, со своей дополнительной памятью. В третьих (таких, как МП-автомат) — устройство управления взаимодействует и с внешней средой, и с объектом управления, причем от среды оно получает лишь входные воздействия, тогда как взаимодействие с объектом управления имеет двунаправленный характер. При построении модели автоматизированного объекта целесообразно использовать третий вариант как наиболее общий (рис. 1.21).На этом рисунке сплошными стрелками обозначены традиционные и наиболее типичные для программных реализаций виды взаимодействия между автоматом, объектом управления и внешней средой. Автомат получает входные воздействия как со стороны среды, так и от объекта управления. В событийных системах часть или все компоненты входного воздействия со стороны среды могут быть событиями (множество событий обозначено на рисунке буквой E). Входное воздействие со стороны объекта управления формирует в модели обратную связь (от управляемого объекта к управляющему). Это воздействие может отсутствовать, тогда модель является разомкнутой — так в теории управления называются системы управления без обратной связи В противном случае модель называется замкнутой. Автомат, в свою очередь, воздействует на объект управления. Пунктирными стрелками обозначены менее распространенные, хотя и возможные варианты взаимодействия. Так, автомат может оказывать выходное воздействие и на внешнюю среду. Однако таких связей можно избежать, включив все управляемые автоматом сущности в состав его объекта управления. Отметим, что в программировании различие между объектом управления и внешней средой носит скорее концептуальный, а не формальный характер. Создавая модель системы со сложным поведением, разработчик производит ее декомпозицию на автоматизированные объекты, определяя тем самым объект управления каждого автомата. В целях минимизации связей между модулями программной системы целесообразно проводить декомпозицию таким образом, чтобы автомат оказывал выходные воздействия только на собственный объект управления. Кроме того, объект управления может взаимодействовать с внешней средой напрямую. Напомним, что в абстрактных автоматных моделях входные и выходные воздействия обычно представляют собой символы некоторого конечного алфавита или цепочки таких символов, а в структурных моделях — битовые строки заданной длины. В программировании на вид входных и выходных воздействий нет ограничений: это могут быть символы, числа, строки, множества, последовательности, произвольные объекты — все зависит от специфики поставленной задачи и инструментов, используемых для ее решения. Кроме того, могут различаться способы передачи входных воздействий автомату и интерпретации выходных воздействий в объекте управления.Если по назначению сущность близка к традиционной системе управления, то представление входных и выходных воздействий битовыми строками будет удобным по тем же причинам, что и для структурных автоматных моделей. Однако интерпретация этого представления может быть различной. В примере со счетным триггером (см. раздел 1.4.2) каждое из двух значений выходной переменной соответствовало определенному вычислительному состоянию: включенной или выключенной лампочке. В программировании чаще используется другая интерпретация: каждой выходной переменной сопоставляется определенное изменение вычислительного состояния (действие, команда). При этом единица обозначает наличие действия, а нуль — его отсутствие. В этом случае вектору из нулей соответствует отсутствие каких-либо команд. Такой вид выходного воздействия может привести к недетерминизму в том случае, если результат зависит от последовательности выполнения команд. Поэтому в качестве выходного воздействия вместо множества команд часто используется последовательность команд. При рассмотрении всевозможных деталей использования автоматных моделей в программировании становится ясно, что выбрать одну конкретную модель, подходящую для всех задач, невозможно. При программной реализации сущностей со сложным поведением применение могут найти активные и пассивные, разомкнутые и замкнутые модели, различные формы представления и интерпретации входных и выходных воздействий. Модель автоматизированного объекта управления должна быть применима для любой сущности со сложным поведением и поэтому целесообразно сформулировать ее довольно абстрактно. Примеры программной реализации сущностей со сложным поведением, которые будут приведены в последующих главах, являются конкретными воплощениями этой модели. Итак, приведем формальное определение автоматизированного объекта управления. Пара AO,, состоящая из управляющего автомата и объекта управления, называется автоматизированным объектом управления. Управляющий автомат представляет собой шестерку XYZ,,,,,0, где X =XE XO — конечное множество входных воздействий, причем каждое входное воздействие x состоит из компоненты xE, порождаемой внешней средой, и компоненты xO, порождаемой объектом управления; Y — конечное множество управляющих состояний; Z — конечное множество выходных воздействий; y0 Y — начальное состояние; — функция выходов (выходных воздействий), состоящая обычно из двух компонент: функции выходных воздействий в состояниях Y > Z и функции выходных воздействий на переходах X Y > Z; X Y > Y — функция переходов. Объект управления — это тройка Vffqc,,, где V — потенциально бесконечное множество вычислительных состояний (или значений), fq : V > XO — функция, сопоставляющая входное воздействие вычислительному состоянию, fc : Z V > V — функция, изменяющая вычислительное состояние в зависимости от выходного воздействия. Функции fq и fc являются математическими эквивалентами набора запросов и набора команд соответственно. Графическое представление описанной модели приведено на рис. 1.22.Таким образом, с позиций теории формальных языков автоматизированный объект — это автомат с произвольной памятью. По вычислительной мощности он, в общем случае, эквивалентен машине Тьюринга. Формально для обеспечения эквивалентности необходимо потребовать, чтобы запросы и команды объекта управления являлись вычислимыми функциями (их можно было вычислить с помощью машины Тьюринга). В определении это свойство подразумевается. В разомкнутой модели автоматизированного объекта входные воздействия поступают только от внешней среды (X = XE), а запросы объекта управления отсутствуют (рис. 1.23). Такой автоматизированный объект по вычислительной мощности эквивалентен ДКА: его объект управления уже не является дополнительной памятью, а скорее представляет собой разновидность выходной ленты. В терминах теории логического управления автоматизированный объект — это, как правило, замкнутая система, управляемая автоматом первого рода с выходным преобразователем, в качестве которого может использоваться автомат Мура, Мили или смешанный автомат. Как было упомянуто выше, автоматизированный объект эквивалентен по вычислительной мощности машине Тьюринга. Иначе говоря, для любого АО можно построить машину Тьюринга, которая решает ту же задачу, и наоборот. С одной стороны, из этого свойства следует важное достоинство автоматного подхода: с помощью автоматизированного объекта можно описать любой алгоритм, любую программу, которая только может быть выполнена компьютером. С другой стороны, возникает вопрос: зачем было изобретать автоматизированный объект вместо того, чтобы выбрать на роль модели сущности со сложным поведением более простую и столь же мощную машину Тьюринга Ответ приходит сам собой, если вспомнить пример с машиной Тьюринга, реализующей функцию инкремент (см. параграф 1.3). Для вычисления простейшей функции понадобился управляющий автомат из трех состояний. Автомат машины Тьюринга, выполняющей умножение двух чисел (преобразование строки «0n10m1» в строку «0nm»), содержит уже 12 состояний! Такая модель не только не упрощает описание сложного поведения, но и значительно усложняет описание простого. Программирование на машине Тьюринга (или тьюрингово программирование) чрезвычайно сложно и непрактично по той причине, что набор элементарных операций этой машины с дополнительной памятью очень ограничен. Поэтому автомату приходится не только управлять, но и выполнять не свойственную ему функцию вычисления. Переход к модели автоматизированного объекта управления позволяет использовать в качестве элементарных операций произвольные запросы и команды. При этом на управляющий автомат ложится лишь часть ответственности по реализации алгоритма: та, что связана с логикой (управлением), для чего автоматы, собственно, и предназначены. Можно сказать, что при программировании на машине Тьюринга любое поведение (кроме алгоритма, состоящего из единственного шага, на котором необходимо записать символ и сдвинуть головку) является сложным. В автоматном программировании грань между простым и сложным поведением определяется разработчиком. Умножение двух чисел может быть сложным, если вы собираетесь эмулировать и визуализировать счеты. Построение самобалансирующегося дерева [26] может оказаться элементарной операцией, если в вашем распоряжении есть соответствующая библиотека, предоставляющая готовую функцию. Таким образом, переход от тьюрингова программирования к автоматному состоит в повышении уровня абстракции операций с памятью, причем этот уровень при автоматном подходе не фиксирован, а зависит от решаемой задачи. Более того, низкоуровневый автоматизированный объект может быть инкапсулирован в объекте управления, существующем на более высоком уровне абстракции. Благодаря такому вложению автоматизированных объектов автоматное программирование поддерживает концепцию выделения уровней абстракции, распространенную в современной методологии разработки ПО. Выбор уровня абстракции элементарных операций при моделировании сущности со сложным поведением определяет разделение поведения на логику и семантику, а состояний — на управляющие и вычислительные. Это и есть наиболее творческий и нетривиальный шаг в автоматном подходе к разработке ПО. Выбор чересчур простых элементарных операций приводит к разрастанию и усложнению автомата, логика становится менее понятной и перегруженной деталями, которые эффективнее было бы реализовать в объекте управления. Машина Тьюринга — крайний случай такого «злоупотребления логикой». Напротив, выбор слишком абстрактных запросов и команд ведет к усложнению их реализации, перегруженности флагами и условными конструкциями. Вырожденный случай такого «злоупотребления семантикой» — использование традиционных (неавтоматных) стилей программирования, где любое поведение считается простым (рис. 1.24).Защитники традиционных парадигм программирования могут возразить, что борьба со сложностью программ осуществляется там путем декомпозиции: функциональной (в процедурном программировании) или объектной (при объектно-ориентированном подходе). При наличии сложной логики декомпозиция лишь распределяет ее по различным компонентам системы, но не делает ее явной и, конечно же, не устраняет ее. Таким образом, декомпозиция отчасти выполняет одну функцию автоматного подхода — упрощение операций, однако совершенно не справляется с другой — формированием у разработчика целостной картины поведения сущности. С другой стороны, борьба со сложностью автоматов оставалась (и отчасти остается до сих пор) одной из главных задач автоматного программирования. Эта задача по-разному решается в процедурной и объектно-ориентированной разновидностях парадигмы. Два различных решения подробно обсуждаются в главах 2 и 3 этой книги. Пока отметим лишь то, что объектно-ориентированный подход поддерживает понятие автоматизированного объекта управления более непосредственно. Поэтому борьба со сложностью как автомата, так и объекта управления осуществляется при этом подходе гораздо проще и эффективнее.
2. Процедурное программирование с явным выделением состояний