ФЕДЕРАЛЬНОЕ АГЕНСТВО ОБРАЗОВАНИЯ И НАУКИ  РФ

ЮГО-ЗАПАДНЫЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

КАФЕДРА ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ 
 
 
 
 

Реферат

на тему: «Парадигма автоматного программирования» 
 
 
 
 

Выполнил:                                                                          ст. гр. ПО-92

                                                                                             Хорошилов С.А.

Проверил:                                                                          проф.

                                                                                             Довгаль В.М. 
 
 
 

Курск 2011

Оглавление

 
 
 

 

Введение

 
 

     Автоматное  программирование, иначе называемое «программирование от состояний» или  «программирование с явным выделением состояний» — это метод разработки программного обеспечения, основанный на расширенной модели конечных автоматов и ориентированный на создание широкого класса приложений.

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

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

 

Автоматное  программирование как  парадигма программирования

 
 

     Очень многие системы, которые для внешнего наблюдателя ведут себя 
достаточно осмысленно, являются автоматизированными объектами управления.

     Автоматизированный объект управления представляет собой совокупность системы управления (СУ) и объекта управления (ОУ), охваченных обратными связями (рис. 1). 

Рис. 1.       Автоматизированный объект управления 

     Задача построения автоматизированных объектов управления рассматривается в любом курсе теории автоматического управления применительно к объектам различных типов.

     Удивительно, что это почти никак не коснулось практики программирования, несмотря на то, что в теории алгоритмов в качестве одной из основных моделей используется машина Тьюринга. Машина Тьюринга, по сути, является автоматизированным объектом управления , в котором система управления - конечный автомат, а объект управления – лента (ее ячейки памяти).

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

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

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

     Основная особенность автоматного программирования - программы предлагается создавать так же, как производится автоматизация технологических (и не только) процессов.

     При этом на основе анализа предметной области выделяются источники входных воздействий и автоматизированные объекты управления, каждый из которых содержит систему управления (систему взаимодействующих конечных автоматов) и объекты управления. Эти объекты реализуют выходные воздействия и формируют значения еще одной разновидности входных воздействий, которые по обратным связям передаются системе управления.

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

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

     Объекты управления могут быть реальными или виртуальными - 
реализованными программно. В первом случае их логика изменена быть не может, а во втором - она (при необходимости) практически вся может быть вынесена в автоматы.

      Парадигма автоматного программирования состоит в представлении и реализации программ как систем автоматизированных объектов управления.

 

Основные  положения автоматного  программирования

 
 

     Основным понятием в автоматном программировании является состояние.

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

     При этом справедливо соотношение: «Состояния + входные воздействия = конечный автомат без выхода». Справедливо также: «Автомат без выхода + выходные воздействия = автомат».

     Автоматы могут быть абстрактными (входные и выходные воздействия формируются последовательно) и структурными (входные и выходные воздействия формируются «параллельно»). В автоматном программировании, в отличие, например, от программирования компиляторов, обычно применяются структурные автоматы.

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

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

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

 

Достоинства автоматного программирования

 
 

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

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

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

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

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

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

     Для автоматных программ отсутствует семантический разрыв между требованиями к программе и к модели, так как он устраняется в ходе разработки графов переходов на этапе проектирования. Это позволяет считать автоматные программы приспособленными к верификации. Таким образом, при верификации программ имеет место ситуация, аналогичная с контролем схем со сложной логикой – эти схемы не удается проверить, если они не спроектированы специальным образом для обеспечения контролепригодности.

 

Список литературы