Конечно-автоматная технология программирования

В архиве лежит упакованная версия статьи (8 кб)

Технология - это “совокупность производственных методов и процессов в определенной отрасли производства, а также научное описание способов производства” (Ожегов С.И. Словарь русского языка).

Можно ли назвать представленное в [1, 2] технологией? Использование методов, базирующихся на единой модели структурного конечного автомата (КА), дает нам основание говорить об их объединении в совокупность, называемую далее конечно-автоматной технологией (КА-технология) разработки программ. Покажем, что это так, рассмотрев основные этапы создания программных проектов: проектирование, кодирование, тестирование, эксплуатацию и сопровождение программ.

Проектирование.

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

Формальная модель конечного автомата (КА) и сеть из множества КА предоставляют разработчику гибкие структурные средства для отображения параллельного взаимодействия как на уровне отдельных компонентов, так и на уровне их множества. Технологии разработки программ “сверху вниз”, “снизу вверх”, структурный подход таких возможностей или не имеют, или они ограничены. Даже в технологии объектно-ориентированного программирования (ООП) вопросы параллельной работы объектов вынесены за ее рамки. Использование других технологий, базирующихся на известных параллельных моделях, сопряжено с трудностями, связанными если не с ограничениями области их применения (в первую очередь это относится к самой формальной модели - основы технологии), то с проблемами последующей реализации (той же модели) на программном и/или аппаратном уровнях.

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

Таким образом, в рамках КА-технологии можно легко и наглядно представлять структуру задачи любой сложности в параллельном виде. Пример из [2] это демонстрирует. Более сложные примеры применения конечных автоматов можно найти в [3] или [4].

Кодирование

После описания структуры системы и алгоритмов работы ее составных частей в терминах формальной модели наступает момент ее описания/реализации на языке программирования. Сейчас это сводится к реализации алгоритмов, представленных блок-схемами программ. И даже если блок-схемы и не присутствуют в явном виде, то суть дела от этого не меняется. В КА-технологии алгоритмы представлены той или иной формой КА-описания.

Пути реализации блок-схем известны. А как реализовать автоматы? Во-первых, как уже упоминалось, существуют формальные методы перехода от модели КА к эквивалентной блок-схеме, например, методы проектирования микропрограммных автоматов [5]. Во-вторых, известны и программные методы реализации автоматов, наиболее удобный из которых т.н. интерпретационный. Современные программные средства позволяют реализовать этот метод в виде, который наиболее приближен к исходному описанию автоматов. В [1] показано, как это осуществить в рамках КА-технологии. Там же имеется ссылка на DLL-библиотеку, реализующую автоматную модель, для Microsoft Visual C++ версии 5.0.

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

Итак, кодирование/программирование автоматов в рамках КА-технологии основано на следующих принципах:

1. введено понятие динамичного объекта, который может быть наделен алгоритмом поведения во времени;
2. алгоритм поведения объекта задается моделью конечного автомата;
3. язык описания автомата основан на базе табличной формы представления автоматов;
4. логика поведения объекта (таблица переходов автомата) отделена от методов автоматного объекта (предикатов и действий), связанных с реализацией его поведения во времени;
5. любые динамичные объекты могут выполняться параллельно.

Тестирование

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

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

В рамках КА-технологии применимы приемы тестирования и отладки, которые зачастую невозможны при других подходах. Отделение множества операторов от структуры КА-программы позволяет проводить их независимый анализ. Можно легко строить и модифицировать логику работы программы на множестве ее операторов, т.е. экспериментировать с логикой самой программы. Или, что очень удобно, использовать одну и ту же проверенную и отлаженную логику (управление) в разных программах/объектах, т.е. наследовать алгоритм по аналогии с наследованием методов или данных объектов в ООП.

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

Хорошо и то, что общность модели позволяет использовать зарекомендовавшие себя формальные математические методы и другие эффективные методы тестирования из области проектирования аппаратных средств.

Эксплуатация и сопровождение

Удачно разработанные проекты “живут” достаточно долго. При этом приходится их модифицировать или проводить определенные доработки, т.е. сопровождать.

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

Самым точным источником информации о программе является листинг. Но не зря есть мнение, что проще написать новую программу, чем “корпеть” над листингом старой, а уж тем более чужой. С листингом КА-программ работать очень легко, т.к. отделение логики программы (управления) от ее операторов делает ее “самодокументируемой”. Это свойство позволяет быстро и точно восстановить алгоритм работы программы/объекта. Например, по табличному описанию построить более наглядную графическую форму в виде автоматного графа. Тот, кто хоть раз пытался построить по листингу программы ее блок-схему, знает о сложности такой процедуры.

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

Примеры применения

Автоматная модель и ее параллельный вариант - это универсальная алгоритмическая модель, пригодная для применения в любой прикладной области. На текущий момент она реализована в форме DLL библиотеки (см. также [1]). Микроядро или, другими словами, виртуальная КА-машина выполняет функции интерпретации модели КА, реализует параллельную работу компонент, управляя их запуском, синхронизацией и т.п. Разработанные на языке С++ средства описания автоматов и библиотека расширяют объектные возможности языка, реализуя динамическую работу классов.

Прикладные области, где проходила “обкатку” данная технология, достаточно разнообразны. Это и простые в алгоритмическом плане бухгалтерские программы типа расчета заработной платы или учета квартирной платы. Есть и проект системы управления технологическим процессом выращивания кристаллов с множеством динамически порождаемых параллельно функционирующих объектов реализующих процессы съема данных с датчиков, выдачу управляющих воздействий на объект, автоматные алгоритмы работы драйверов с разнообразной аппаратурой, процессы отображения и расчета.

Одна из сложных областей эффективного использования КА - разработка игровых программ. Другая предметная область такого же класса - системы управления и/или функционирования в реальном времени. В этих областях в полной мере присутствуют элементы, которые сложно реализовать при обычных подходах. Это - параллельный характер работы составных частей системы, их синхронизация в реальном времени. В таких областях обычно применяются специализированные системы проектирования. В их основу положена, примененная и в КА-технологии, концепция микроядра, которое реализует параллельные механизмы среды функционирования.

Подчеркнем, что КА-технология хорошо подходит для работы в реальном времени. Реализованный проект системы управления технологическим процессом в реальном времени, обеспечивает реакцию системы с точностью до 0.01 сек (можно обеспечить и лучшую) в среде Windows. Это не хуже, чем гарантируют специализированные системы такого типа.

Выводы

Чем сложнее проект, тем эффективнее применение конечно-автоматной модели. КА-технология решает проблемы структурного и алгоритмического проектирования систем. Она не влияет на особенности самой прикладной области и потому может быть легко внедрена всюду. Это аналогично распространению ООП на достаточно специализированные прикладные области и системы программирования.

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

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

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

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

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

Дополнение: сравнение SWITH-технологии и КА-технологии

Данный раздел написан на основании впечатлений от знакомства с технологией разработки программного обеспечения, описанной в [6]. Эта технология и кратко рассмотренная выше КА-технология имеют общую начальную точку отсчета: обе описывают алгоритм программы моделью конечного автомата. Но, чтобы провести их детальное сравнение, нужно уже на формальном уровне сравнить абстрактные модели, лежащие в их основе. В данном случае это несколько отличающиеся по своим функциональным возможностям автоматные модели. В SWITCH-технологии - модель взаимосвязанных графов переходов, в КА-технологии - введенная автором сетевая модель структурных автоматов.

У сравниваемых технологий очень близок подход к реализации модели, хотя при этом применяется и различная терминология. Как в КА-программе, так и SWITCH-программе (в первой явно, во второй не столь и допускается большая свобода) логика программы (управление программы) отделена от ее операторов. В данном случае понятия управление и операторы программы (прежде всего предикаты) соответствуют понятиям, вводимым в теории схем программ [7]. Только в первом случае логика представлена таблицей переходов, которая затем интерпретируется. Во втором случае она реализуется "шаблонами" на основе известной управляющей инструкции языка программирования SWITCH или ей аналогичной, где вызов операторов программы организован через вызовы соответствующих подпрограмм (см. для сравнения пример блок-схемной реализации логики RS-триггера в [2]).

Основное отличие рассматриваемых технологий в реализации логики автоматных программ. В SWITCH-технологии она реализуется переводом автоматного описания в программные инструкции языка программирования (типа SWITCH), в КА-технологии реализуется прямое исполнение автоматов путем интерпретации его исходного табличного представления. Это более короткий и наглядный путь реализации автоматов, хотя и более медленный, если рассматривать уровень отдельного компонентного автомата сети автоматов.

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

Подведя итог, можно сказать, что КА-технология по сравнению с SWITSH-технологией:

1. предлагает более короткий и удобный, хотя и более медленный, путь реализации автоматов;
2. параллелизм формальной модели в КА-технологии имеет более широкие возможности, чем у модели, положенной в основу SWITCH-технологии;
3. КА-технология, в отличие от SWITSH-технологии, не только в полной мере использует возможности объектной парадигмы, но и наделяет ее новыми возможностями.

Заключение

В заключение хочется выразить особую благодарность Шалыто А.А. за проявленный интерес к работе, высказанные замечания и за предоставленную возможность ознакомиться с материалами по SWICH-технологии проектирования программных систем. Именно это послужило стимулом к пересмотру и дополнению уже достаточно давно подготовленного материала. Данные технологии, безусловно, очень близкие "родственники". По меньшей мере, они имеют одного "предка" - автоматную модель, а также единые принципы, положенные в основу технологии, построенной на основе этой модели. Детальное их сравнение, конечно, должно быть не столь поверхностным, как это сделано выше и еще ждет нас впереди (о концепциях и более эмоциональном взгляде автора на проблему выбора модели программ, а соответственно и технологии их проектирования, см. [8, 9]).

Литература:

1. Любченко В.С. О бильярде с Microsoft C++ 5.0. “Мир ПК”, № 1/98, с.202-206.
2. Любченко В.С. Новые песни о главном (римейк для программистов). “Мир ПК”, № 6/98, с.114-119.
3. Буч Г. Объектно-ориентированное проектирование с примерами применения: Пер. с англ. - М.: Конкорд, 1992. -519с.
4. Шлеер С., Меллор С. Объектно-ориентированный анализ: моделирование мира в состояниях: Пер. с англ. - Киев: Диалектика, 1993. - 240 с.
5. Баранов С.И. Синтез микропрограммных автоматов. -Л.: Энергия, 1979. -232с.
6. Шалыто А.А., Туккель Н.И. SWITCH-технология: автоматный подход к созданию программного обеспечения "РЕАКТИВНЫХ" систем. Материал размещен на сайте www.softcraft.ru
7. Котов В.Е. Введение в теорию схем программ. Новосибирск: Наука, 1978. -258с.
8. Любченко В.С. Фантазия или программирование? “Мир ПК”, №10/97, с.116-119.
9. Любченко В.С. Мы выбираем нас выбирают… К проблеме выбора алгоритмической модели. “Мир ПК”, № 3/99.