Для того чтобы лучше разобраться в основных концепциях автоматного программирования, рассмотрим сначала один из абстрактных вычислителей, широко применяемых в теории формальных языков, — машину Тьюринга Эта абстрактная машина была предложена А. Тьюрингом в 1936 г. в качестве формального определения понятия «алгоритм». Тезис Черча—Тьюринга гласит, что все, что можно «вычислить», «запрограммировать» или «распознать» в любом смысле (из формально определенных в настоящее время), можно вычислить, запрограммировать или распознать с помощью подходящей машины Тьюринга. Машина Тьюринга состоит из двух частей: устройства управления и запоминающего устройства — ленты (рис. 1.5). Лента содержит бесконечное число ячеек, в которых могут быть записаны символы некоторого конечного алфавита. В каждый момент времени на одной из ячеек ленты установлена головка чтения-записи, позволяющая устройству управления считывать или записывать символ в этой ячейке.
Устройство управления представляет собой конечный автомат. У него имеется единственное входное воздействие: символ, считанный с ленты, и два выходных воздействия: символ, записываемый на ленту, и указание головке сдвинуться на одну ячейку в ту или иную сторону либо остаться на месте. Тезис Черча—Тьюринга означает, что в терминах операций машины Тьюринга можно записать все те же программы, что и на любом существующем языке программирования. Как же программировать на машине Тьюринга? Пусть, например, необходимо реализовать функцию инкремент (увеличение целого числа на единицу). Пусть исходное число записано на ленте в двоичном виде слева направо, во всех остальных ячейках находится пустой символ (‘blank’) и головка указывает на самый старший разряд числа. Тогда для увеличения числа на единицу можно предложить следующий алгоритм: Двигаться вправо, пока не встретится пустой символ.1.Сдвинуться на одну ячейку влево.2.Пока в текущей ячейке находится символ 3. ‘1’, изменять его на ‘0’ и двигаться влево. Если в текущей ячейке находится 4. ‘0’ или ‘blank’, записать в ячейку ‘1’ и завершить работу. Этот алгоритм необходимо «ввести» («закодировать») в устройство управления машины Тьюринга. Другими словами, необходимо задать состояния, а также функции переходов и выходов ее управляющего автомата. Удобный и наглядный способ сделать это предоставляют графы переходов автоматов, иначе называемые диаграммами переходов. Подробнее язык графов переходов будет обсуждаться в параграфе 2.2, а пока достаточно знать, что вершины в этом графе соответствуют состояниям автомата, а дуги — переходам между состояниями. Каждая дуга помечается условием перехода (значениями входных воздействий, которые инициируют этот переход) и действием на переходе (значениями выходных воздействий).На рис. 1.6 представлен граф переходов управляющего автомата машины Тьюринга, реализующей функцию инкремент. Здесь символ ‘b’ — сокращение от blank, символ ‘*’ на месте записываемого символа означает «Записать тот же самый символ, который был считан». Команды головке обозначаются стрелками (стрелка вниз означает «Остаться на месте»). В метке перехода над чертой записывается его условие, а под чертой — действие. Отметим, что в графе переходов обозначены имена состояний управляющего автомата. Эти имена отражают смысл состояния и являются кратким описанием поведения машины в этом состоянии. Итак, управляющий автомат машины Тьюринга, реализующей функцию инкремент, имеет три состояния. Сколько же состояний у этой машины в целом? Ее действия в каждый момент времени полностью определяются совокупностью состояния управляющего автомата, строки на ленте и положения головки. Отметим, что символы на ленте для устройства управления представляют собой входные воздействия, однако относительно машины в целом они не являются входными (внешними), а формируют часть внутреннего состояния вычислителя. Всевозможных строк на ленте, как и положений головки, бесконечно много, поэтому и у машины Тьюринга бесконечное число состояний. Однако если задуматься, состояния управляющего устройства и состояния ленты имеют принципиально различные значения. В приведенном примере оказалось, что для того чтобы задать алгоритм для машины Тьюринга, достаточно описать ее поведение в каждом из трех состояний управляющего автомата (см. рис. 1.6). Нам не потребовалось задавать реакцию машины для каждой из бесконечного числа возможных входных строк. Неформально можно сказать, что состояния управляющего автомата определяют действия машины, а состояние ленты — лишь результат этих действий.
Здесь уместна аналогия из объектно-ориентированного программирования. Вызывая компонент (метод) некоторого класса, клиент указывает имя компонента и, если требуется, его фактические аргументы. Различных компонентов в классе обычно всего несколько, в то время как различных аргументов может быть необозримо много. При этом имя компонента определяет действие (алгоритм вычислений), а значения аргументов — только результат действия (результат вычислений).Теперь очевидно, что состояния устройства управления и состояния ленты — совершенно разные понятия с точки зрения программирования на машине Тьюринга, и смешивать их не стоит. Первые следует явно перечислять, отображать на графе переходов, описывать алгоритм поведения в каждом из них. Вторые в программе в явном виде не участвуют, построить граф переходов между ними невозможно, а если бы это и удалось, то для понимания программы такой граф был бы бесполезен. Первые можно назвать качественными состояниями машины, а вторые — количественными. В автоматном программировании для этих двух классов состояний приняты термины, заимствованные из теории управления. Состояния автомата называются управляющими, а состояния ленты — вычислительными *1.
Понятие «состояние», так же как и деление на управляющие и вычислительные состояния, не является «чужеродным» для программирования. Традиционно под состоянием программы подразумевают множество текущих значений всех используемых в ней переменных И хотя число переменных, равно как и число потенциальных значений каждой переменной, можно считать конечным, получающееся пространство состояний оказывается необозримо большим.
Однако не все исследователи трактуют понятие состояния программы столь прямолинейно. Так, А. Дж. Перлис в 1966 г. [16] предложил в описания языка, среды и правил вычислений включать состояния, которые могут подвергаться мониторингу во время исполнения, позволяя диагностировать программы, не нарушая их целостности. В этом же году Э. Дейкстра предложил ввести так называемые переменные состояния, с помощью которых можно описывать состояния системы в любой момент времени (Дейкстра использовал для этих целей целочисленные переменные). При этом им были поставлены вопросы о том, какие состояния должны вводиться, как много значений должны иметь переменные состояния и что эти значения должны означать. Он предложил сначала определять набор подходящих состояний, а лишь затем строить программу. По мнению Э. Дейкстры, диаграммы переходов между состояниями могут оказаться мощным средством для проверки программ. Это обеспечивает поддержку его идеи о том, что программы должны быть с самого начала составлены правильно, а не отлаживаться до тех пор, пока они не станут правильными. Понятия управляющих и вычислительных состояний применимы не только к машине Тьюринга, но и к любой сущности со сложным поведением. Однако если в машине Тьюринга отличить управляющие состояния от вычислительных не составляет труда (поскольку она по определению состоит из устройства управления и ленты), то для произвольной сущности явное выделение управляющих состояний — сложная задача. Об этом уже упоминалось в параграфе 1.1. Причина сложности состоит в том, что различия между управляющими и вычислительными состояниями в общем случае трудно формализовать. Неформально основные различия сформулированы в табл. 1.1.*1 В автоматном программировании (и, в частности, в этой книге), говоря без уточнения о состоянии некоторой автоматной модели, сущности или системы со сложным поведением, подразумевают управляющее состояние. Если речь идет о вычислительном состоянии, это оговаривается особо. Представьте себе, что в машине Тьюринга не было бы управляющего автомата. Алгоритм ее работы может быть закодирован на ленте в виде последовательности команд. Машина точно так же продолжала бы вести себя по-разному на разных этапах алгоритма, однако из ее описания это было бы уже неясно. Логика ее поведения была бы потеряна среди не столь существенных деталей, а управляющие состояния смешались бы с вычислительными. Программировать на такой машине и разбираться в уже существующих программах стало бы практически невозможно. Переход от ленты, головки и простейших команд к языкам высокого уровня, конечно, упрощает программирование, но при реализации сущностей со сложным поведением полностью проблемы не решает. Вспомните электронные часы из параграфа 1.1. Точно так же как в нашей «воображаемой» машине, состоящей только из ленты, в листинге 1.1 логика затеряна среди деталей. Опыт рассмотрения машины Тьюринга подсказывает, что для того чтобы сделать программу простой и понятной, необходимо явно выделить управляющие состояния (идентифицировать их, дать им имена) и описать поведение сущности в каждом из них. Например, при реализации электронных часов с будильником можно выделить три управляющих состояния: «Будильник выключен», «Установка времени будильника» и «Будильник включен». В каждом из этих состояний реакция будильника на нажатие любой кнопки будет однозначной и специфической. Как отмечено выше, в случае с машиной Тьюринга выделение управляющих состояний тривиально, так как логика в ней априори вынесена в отдельное устройство — управляющий автомат. Подобная идея используется при построении систем автоматизации, в которых всегда выделяют управляющие устройства и управляемые объекты. Следуя этой концепции, сущность со сложным поведением естественно разделить на две части: управляющую часть, ответственную за логику поведения, — выбор выполyyняемых действий, зависящий от текущего состояния и входного воздействия, а также за переход в новое состояние; управляемую часть, ответственную за выполнение действий, выбранных для выyyполнения управляющей частью, и, возможно, за формирование некоторых компонентов входных воздействий для управляющей части — обратных связей. В соответствии с традицией теории управления, управляемая часть здесь и далее называется объектом управления, а управляющая часть — системой управления. Поскольку для реализации управляющей части используются автоматы, то она часто называется управляющим автоматом или просто автоматом. После разделения сущности со сложным поведением на объект управления и автомат реализовать ее уже несложно, а главное, ее реализация становится понятной и удобной для модификации. Вся логика поведения сущности сосредоточена в управляющем автомате. Объект управления, в свою очередь, обладает простым поведением (а следовательно, может быть легко реализован традиционными «неавтоматными» методами). Он не обрабатывает непосредственно входные воздействия от внешней среды, а только получает от автомата команды совершить те или иные действия. При этом каждая команда всегда вызывает одно и то же действие (это и есть определение простого поведения).Таким образом, в соответствии с автоматным подходом, сущности со сложным поведением следует представлять в виде автоматизированных объектов управления — так в теории управления называют объект управления, интегрированный с системой управления в одно устройство. парадигма автоматного программирования состоит в представлении сущностей со сложным поведением в виде автоматизированных объектов управления