Switch-технология

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


Содержание

Назначение

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

Стили программирования

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

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

Наличие состояний придает "устойчивость" рассматриваемым процессам.

Вычислительные устройства и языки программирования

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

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

Возражения против Switch-технологии

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

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

Все эти утверждения безусловно верны. Однако ни одно из них не препятствует применению автоматного программирования при создании систем со сложным поведением в различных предметных областях.

Основные положения

Автоматы и программирование

Справедливо соотношение: "Управляющие состояния + входные воздействия = конечный (детерминированный) автомат без выхода".

Справедливо также: "Автомат без выхода + выходные воздействия = автомат".

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

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

Стиль программирования, основанный на явном выделении состояний и применении автоматов для описания поведения программ, назван "автоматное программирование", а соответствующий стиль проектирования программ - "автоматное проектирование программ".

Состояния

Состояния делятся на два типа: управляющие (автоматные) и вычислительные (неавтоматные).

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

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

Вычислительные состояния могут быть не только дискретными, но и непрерывными, что приводит к понятию "гибридный автомат".

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

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

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

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

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

Кодирование состояний

Традиционно в программировании под термином "кодирование" понимается собственно процесс написания текста. В Switch-технологии, так же как и в теории автоматов, предлагается использовать термин "кодирование состояний".

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

Возможность слежения за состояниями автомата по значениям одной многозначной переменной позволяет ввести в программирование (по аналогии с теорией управления) понятие "наблюдаемость".

Схема связей

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

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

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

Графы переходов

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

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

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

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

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

Структура автоматных программ

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

Четырехуровневая схема программ (дешифратор состояний - выходные воздействия - дешифратор входных воздействий - формирование следующих состояний) реализует автоматы Мура.

Четырехуровневая схема программ (дешифратор состояний - дешифратор входных воздействий - выходные воздействия - формирование следующих состояний) реализует автоматы Мили.

Пятиуровневая схема программ (дешифратор состояний - выходные воздействия - дешифратор входных воздействий - выходные воздействия - формирование следующих состояний) реализует смешанные автоматы.

Схемы программ с указанной структурой названы автоматными.

При таком построении граф переходов, автоматная схема программ и конструкция switch изоморфны.

Взаимодействие автоматов

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

Вложенность может рассматриваться как вызываемость с любым событием. Число автоматов, вложенных в состояние, не ограничено. Глубина вложенности также не ограничена.

Взаимодействие автоматов отражается на "схеме взаимодействия автоматов", которая может совмещаться со "схемой связей".

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

Реализация и инструментальные средства

Реализация графов переходов

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

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

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

Инструментальные средства для поддержки автоматного программирования

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

Инструментальное средство Visio2Switch [2] позволяет по графу переходов, построенному в определенной нотации и изображенному с помощью редактора Visio, автоматически реализовать его в виде программы на языке С.

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

Недостаток инструментальных средств этого класса - не решен вопрос о проектировании и реализации программ в целом.

Инструментальное средство UniMod [4] предназначено для поддержки автоматного программирования и построения и реализации не только автоматов, но и программ в целом.

Это средство характеризуется формулой: "UniMod = UML + SWITCH-технология + Eclipse + Java + Sourceforge". Оно является открытым и использует только два типа диаграмм UML - диаграммы классов в форме схем связей и диаграммы состояний. Указанное инструментальное средство позволяет создавать программы, поддерживая концепции "Исполняемый UML" (Executable UML) и "Разработка на базе моделей" (Model Driven Architecture).

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

Автоматы и параллельные программы

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

Проверка программ

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

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

Такая проверка более корректна, чем традиционная проверка "вход-выход".

Отладка автоматных программ выполняется в автоматных терминах, что резко ее упрощает.

Автоматные программы приспособлены для верификации с помощью метода Model checking [5], так как для них отсутствует необходимость строить модели поведения.

Верификация программ

Программы, создаваемые на основе Switch-технологии, приспособлены к верификации по построению. Это объясняется тем, что при верификации поведения с использованием метода Model Checking для программ, написанных традиционно, должны строиться модели, например, в виде системы переходов, а при автоматном программировании модели в виде графов переходов задаются при спецификации программ.

Структура автоматных программ, в которых функции входных и выходных воздействий практически полностью отделены от логики программ, делает практичным верификацию этих функций на основе формальных доказательств с использованием пред- и постусловий [6, 7]

Применение Switch-технологии

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

Для поддержки автоматного программирования создан сайт [8].

Впервые технология применительно к логическому управлению изложена в книге Шалыто А.А. Switch-технология. Алгоритмизация и программирование задач логического управления. [9]

Программирование с явным выделением состояний для системы, реагирующей на события, впервые было использовано при автоматизации судовых дизель-генераторов [10].

Объектно-ориентированное программирование с явным выделением состояний впервые было использовано в игре Robocode [11].

Автоматный подход эффективен для реализации визуализаторов алгоритмов дискретной математики [12] и при реализации некоторых из таких алгоритмов (например, обход дерева и поиск подстрок).

Автоматное программирование начинает все шире использоваться в рамках такого научного направления, как "искусственный интеллект" [13, 14].

Автоматы являются удобным средством для описания параллельных процессов [15].

Проект "Технология автоматного программирования: применение и инструментальные средства"

В 2005 году по результатам конкурса, проводимого в рамках Федеральной целевой научно-технической программы "Исследования и разработки по приоритетным направлениям развития науки и техники" на 2002-2006 годы, проект "Технология автоматного программирования: применение и инструментальные средства" был поддержан Федеральным агентством по науке и инновациям.

Проект вошел в список 15 наиболее перспективных и социально значимых проектов, выполняемых в рамках указанной программы (проект 2005-ИТ-13.4/004 [16], а также статья в приложении к газете КоммерсантЪ [17]).

Указанные выше работы в области Switch-технологии находятся в русле работ по обеспечению высокого качества программного обеспечения, проводимых в Западной Европе при создании синхронного программирования [18] и в NASA при создании программного обеспечения для беспилотных космических аппаратов [19].

Движение за открытую проектную документацию

Организовано "Движение за открытую проектную документацию", которое дополняет движения за открытые и свободные исходные коды, в рамках которого выполнятся работы по совершенствованию Switch-технологии.

Ссылки

1. Finite state machine. http://en.wikipedia.org/wiki/Finite_state_machines (англ.)
2. Конвертор Visio2Switch. http://is.ifmo.ru/progeny/visio2switch/
3. Инструментальное средство MetaAuto. http://is.ifmo.ru/projects/metaauto/
4. Инструментальное средство UniMod. http://unimod.sourceforge.net/ (англ.)
5. Кларк Э., Грамберт О., Пелед Д. Верификация моделей программ: Model Checking. М.: МЦНМО. 2002.
6. Дейкстра Э. Заметки по структурному программированию / Дал У., Дейкстра Э., Хоор К. Структурное программирование. М.: Мир, 1975.
7. Мейер Б. Объектно-ориентированное конструирование программных систем. М.: Русская редакция. 2005.
8. Сайт кафедры "Технологии программирования" СПбГУ ИТМО, http://is.ifmo.ru
9. Шалыто А.А. Switch-технология. Алгоритмизация и программирование задач логического управления. СПб.: Наука. 1998, 628 c. http://is.ifmo.ru/books/switch/1
10. Проект "Система управления дизель-генератором". http://is.ifmo.ru/projects/dg/
11. Проект "Система управления танком для игры Robocode". http://is.ifmo.ru/projects/tanks/
12. Сайт кафедры "Технологии программирования" СПбГУ ИТМО, раздел "Визуализаторы". http://is.ifmo.ru/vis/
13. Сайт кафедры "Технологии программирования" СПбГУ ИТМО, раздел "Проекты". http://is.ifmo.ru/projects/
14. Сайт кафедры "Технологии программирования" СПбГУ ИТМО, раздел "Внедрение". http://is.ifmo.ru/application/
15. FSM. http://itc.ua/article.phtml?ID=19921&IDw=19
16. Выбраны лучшие инновационные проекты России //Информационная система "Наука и Инновации", http://www.rsci.ru/company/innov/more.html?MessageID=965
17. Волшебный сундучок Роснауки //Приложение к газете КоммерсантЪ, 16.11.2005. http://www.kommersant.ru/application.html?DocID=625381
18. The Synchronous Languages 12 Years Later. http://www-sop.inria.fr/aoste/benveniste2003synchronous.pdf (англ.)
19. Риган П., Хемилтон С. NASA: миссия надежна //Открытые системы, 2004. №3. http://www.osp.ru/text/302/184060.html

 
Начальная страница  » 
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Э Ю Я
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 Home