Публикация в журнале "Открытые системы". 2001. N3. С.68-69. http://www.osp.ru/os/2001/03/179997/
|
Книга затрагивает не просто область конечных автоматов, а куда более важные вопросы единства математических основ аппаратуры и программного обеспечения |
В начале 70-х годов Дуглас Росс, автор известной методологии IDEF0, утверждал, что "80 или даже 90% информатики будет в будущем основываться на теории конечных автоматов". И хотя этого пока не наблюдается, все же можно сказать, что конечные автоматы с 60-х годов играют заметную роль в развитии компьютерных технологий.
Помимо теории формальных языков и основанных на ней методов построения компиляторов конечные автоматы активно используются в компьютерных играх, в реализации сетевых протоколов, системах сжатия информации, криптосистемах, в системах реального времени и встроенных системах. Иными словами, там, где требуется большая надежность и где логика поведения чересчур сложна, чтобы программист смог реализовать ее на одном лишь уровне здравого смысла.
С появлением структурного программирования стало очевидно, что из трех главных конструкций для управления: следования, цикла и ветвления последний является самым трудным в восприятии программиста, поскольку при множестве альтернатив превращает линеаризованную структуру алгоритма в древовидную. При этом сложность даже последовательных программ (не говоря уже о параллельных) растет стремительно и временами может превосходить дерево вариантов в столь непростой для автоматического анализа модели, как современные шахматы.
Разбиение программы на процессы и объекты с заменой многоступенчатого ветвления средствами обработки сообщений (событий) заменяет одну проблему на другую: вложенность уменьшается, зато количество взаимодействующих компонентов заметно возрастает. Логика "размывается" и в итоге мы получаем плохо контролируемую ситуацию, когда из-за хаотического "ручного" синтеза и невозможности построить исчерпывающий набор тестов нет никакой уверенности в корректности построенной системы. Ключ к решению состоит в применении формальных методов, в создании удобной абстракции, способной "выжать" из алгоритма квинтэссенцию логики его работы и дать возможность проводить весь необходимый анализ.
Одной из таких удобных абстракций могут служить конечные автоматы, среди разновидностей которых стоит выделить трансдюсеры (transducer), автоматы Мили и Мура. Близость к булевой алгебре и теории графов, наглядность графического представления и детерминированность поведения являются заметными достоинствами этой абстракции. Однако при этом надо четко себе представлять, в чем их недостатки, а для этого придется обратиться к истокам программирования, к идеям "механического" вычисления. Как известно, они воплотились в таких формальных моделях, как машины Тьюринга (1936), комбинаторные процессы Поста (1936), нормальные алгоритмы Маркова (1951).
Пытаясь найти точное определение понятия эффективной вычислимости, английский математик Алан Тьюринг выделил особый класс абстрактных машин, о которых высказал предположение, что они пригодны для осуществления любой "механической" вычислительной процедуры. Несмотря на всю громоздкость описания с их помощью алгоритмов они замечательны тем, что согласуются со знаменитым тезисом Черча - всякая механическая процедура, манипулирующая с символами, может быть выполнена той или иной машиной Тьюринга. Иными словами, эта абстрактная машина способна реализовать любой алгоритм. В таком контексте конечный автомат эквивалентен ограниченной машине Тьюринга, у которой есть только считывающая головка, способная перемещаться лишь в одну сторону - слева направо. Достаточно ли этих возможностей, ведь далеко не все алгоритмы могут быть представлены конечными автоматами?
Чтобы ответить на этот вопрос и определить место конечных автоматов среди других абстракций, рассмотрим сети Петри, занимающие промежуточное положение между машинами Тьюринга и конечными автоматами. Сети Петри работают в терминах условий и событий, где первым сопоставлены позиции (особые узлы - емкости для хранения фишек связаны ориентированными дугами с переходами), а последним - переходы (особые узлы-действия, перемещающие фишки и связанные ориентированными дугами с позициями). Конечные автоматы являются частным случаем сетей Петри и эквивалентны автоматным сетям Петри - сетям, в которых каждый переход может иметь точно одну входную и выходную позицию.
Сети Петри лучше всего подходят для описания любых асинхронных систем (асинхронное программирование), тогда как конечные автоматы - лишь для сугубо последовательных систем (автоматное программирование). (Система взаимосвязанных автоматов реализует параллельные системы - замечание Шалыто А.А.). Наглядность динамики и композиционные возможности сетей Петри выше (при различии понятий "позиция" и "состояние", что требует построения графа достижимых маркировок для определения функциональных возможностей сети Петри - замечание Шалыто А.А.), чем у конечных автоматов, но при этом компактность представления предпочтительнее у последних. Что касается отношения к машине Тьюринга, то достаточно расширить сеть Петри сдерживающими дугами (позволяющими определять отсутствие фишек в данной позиции), как она же становится эквивалентной машине Тьюринга. Очевидно, что чем "мощнее" абстракция, чем больше она позволяет синтезировать возможностей, тем хуже у нее дело обстоит с анализом. Иными словами, конечные автоматы анализировать гораздо проще, чем классические сети Петри и уж тем более чем машины Тьюринга.
В работе "Научные основы доказательного программирования" А.П.Ершов выделял три вида программирования: синтезирующее (автоматическое, автоматизированное или ручное манипулирование знанием о задаче с синтезом соответствующей программы), сборочное (построение программы из уже существующих и корректных фрагментов), конкретизирующее (построение специализированных программ из универсальных заготовок). Их отображение на распространенные ныне парадигмы и языки программирования имеет следующий вид.
Синтезирующее программирование:
Сборочное программирование:
Конкретизирующее программирование:
Автоматное и асинхронное программирование в значительной степени раскрываются через синтезирующее программирование, хотя затрагивает также сборочное и конкретизирующее.
Возрождение интереса к конечным автоматам связано с ростом сложности программных систем. Не последнюю роль в активизации работ в данной области играет то обстоятельство, что язык и методология UML, ставшие стандартом де-факто в области проектирования программного обеспечения, предусматривают при описании поведенческих свойств создаваемой системы использование конечных автоматов и сетей Петри. К сожалению, несмотря на достаточно сильные отечественные научные школы, наблюдается огромный дефицит литературы по этим направлениям.
Отрадно, что в некоторой степени этот пробел сможет восполнить вышедший в конце прошлого года в Санкт-Петербурге в издательстве "Наука" объемный труд "Логическое управление. Методы аппаратной и программной реализации алгоритмов". СПб.: Наука, 2000, 780 с. (www.techkniga.spb.ru). Автор этой книги, А.А.Шалыто, профессор Санкт-Петербургского государственного института точной механики и оптики (технического университета), около тридцати лет работает в НПО "Аврора", где применяет изложенные методы для создания программного и аппаратного обеспечения систем управления судами. Издание рекомендуется как учебное пособие, хотя оно больше походит на монографию.
Особенностью книги является изложение авторской концепции SWITCH-технологии (www.softcraft.ru), которая служит развитием подхода Д.Харела (statechart) и названа так из-за реализации автоматов через switch-операторы языка Си. Справедливости ради, стоит отметить, что подобные идеи в том или в ином виде уже нашли применение. В частности, Дж.Нобл в работе "Конечные автоматы в языке Форт" (Noble J.V. Finite State Machines in Forth. University of Virginia. Institute for Nuclear and Particle Phisics. 1995. (www.jfar.org/ article001.html) предложил метод однозначного отображения конечных автоматов на язык программирования без использования медленных вложенных операторов IF, а через операторы CASE языка Форт (Аналогичное предложение по использованию оператора switch языка Си и его аналогов в других языках программирования было сделано в работе Шалыто А.А. Программная реализация управляющих автоматов //Судостроит. пром-стью Сер. Автоматика и телемеханика. 1991. Вып.13 - замечание А.А.Шалыто). Если в этой связи упомянуть о чисто практических вещах, то из свободно распространяемых инструментов можно порекомендовать GSM Suite Эндрю Мангогна (www.slip.net/~andrewm/gsm/gsm_overview.html) - набор программ для автоматического генерирования текста, описывающего поведение конечного автомата, на языке Си++. Что касается онлайн- имитаторов, то стоит обратить внимание на Finite State Machine Simulator (www.engineering.union.edu/~hannayd/csc140/simulator/fsm. htm). Примером использования конечных автоматов может служить проект Xerox Finite State Compiler (www.xrce.xerox.com/research/ mltt/fst), результаты которого активно используются для обработки фраз естественного языка.
Книга Шалыто затрагивает на просто область конечных автоматов, а куда более важные вопросы единства математических основ аппаратуры и программного обеспечения, а также проблемы доказательного и автомати- ческого программирования, которое предусматривает автоматический синтез программ на основе формальной спецификации и базы знаний предметной области.