Your browser does not support JavaScript! Программирование с явным выделением состояний

Интеллектуальные решения для кораблей и судов

Акционерное Общество Концерн НПО Аврора
Интеллектуальные решения для кораблей и судов.Наша специализация — системы и комплексы управления техническими средствами кораблей и судов. Мы автоматизируем ядерные, дизельные, паротурбинные и иные энергетические установки, разрабатываем судовую и корабельную автоматику, тренажеры, мостиковые системы, выполняем гарантийное и послегарантийное обслуживание, поставляем ЗИП
194021
Российская Федерация
Санкт-Петербург
ул. Карбышева 15
, ,
7802463197

7 конференция молодых специалистов Корабельные системы управления и обработки информации

5-6 октября 2017 года в АО "Концерн "НПО "Аврора" состоится традиционная научно-техническая конференция молодых специалистов "Корабельные системы управления и обработки информации"
Подробная информация. Форма заявки.

Программирование с явным выделением состояний
Автор: Шалыто А.А., д.т.н., профессор, Туккель Н.И.
Место размещения: "Мир ПК" - 2001, № 8, № 9.


Вне зависимости от методов разработки любая программа обладает состояниями, которые в каждый момент времени определяются значениями всех ее данных. Как пишет Гради Буч, "внутри большой прикладной программы могут существовать сотни и даже тысячи переменных и несколько потоков управления. Полный набор этих переменных описывает состояние прикладной программы в каждый момент времени" [1].

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

Возможно, что разработчик предусмотрит реакции программы на все комбинации значений управляющих переменных (2n комбинаций в рассматриваемом случае). Однако более вероятно, что сколько-то (вплоть до 2n-n) комбинаций он не учтет, и тогда при неожиданном сочетании входных воздействий программа способна перейти в непредусмотренное, или, по терминологии Фредерика Брукса, "невизуализируемое", состояние: "Сложность служит причиной трудности перечисления, а тем более понимания всех возможных состояний программы, а отсюда возникает ее ненадежность... Сложность структуры является источником невизуализируемых состояний, в которых нарушается система защиты" [2].

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

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

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

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

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

SWITCH-технология: общие сведения

Идея описывать с помощью многозначных переменных состояния как развитие сюжета игры, так и взаимодействие игрока с персонажами, управляемыми компьютером, напрашивается сама собой. В играх компании BioWare (например, Baldur’s Gate 2) эти переменные используются для описания последовательностной логики развития сюжета игры. Предложение применять автоматы для описания поведения в играх можно найти, например, в [3]. Но этот подход, конечно, был известен и ранее [4].

Технология, основанная на многозначных переменных состояния, получившая название "SWITCH-технология", была предложена в 1991 г. А.А. Шалыто для алгоритмизации и программирования задач логического управления [5]. Именно в ней был впервые введен этап кодирования состояний, отсутствующий в традиционных технологиях программирования. Позднее автор развивал SWITCH- технологию применительно к событийным ("реактивным") системам [6, 7].

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

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

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

Графическая нотация

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

Алгоритм произвольной иерархии

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

Иллюстрация метода

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

Традиционный подход

При использовании традиционного событийного подхода для выполнения заданных функций необходимо реализовать обработку следующих событий:

  • нажатие правой кнопки мыши;
  • отпускание правой кнопки мыши;
  • перемещение мыши с нажатой правой кнопкой;
  • выход курсора мыши за границу панели.

Листинг 2 содержит модуль, состоящий из обработчиков перечисленных событий, для ОС QNX и графической оболочки Photon.

На первый взгляд эти обработчики кажутся независимыми. Так обычно считается и в литературе по программированию. Однако в действительности обработчики связаны друг с другом уже в силу того, что предназначены для управления одним и тем же объектом (панелью). Oни также содержат общую управляющую переменную menu. Как следует из текста программы, логика ее работы распределена по обработчикам событий, а значит, поведение модуля априори непредсказуемо.

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

Аналогичный эффект возникает и тогда, когда самодокументирующимся делают визуальный формализм. Примером могут служить диаграммы состояний (Statecharts), используемые в языке UML [8]: запись сложных логических выражений, а также большого числа выходных воздействий и их особенностей становится практически необозримой. То же происходит при работе с SDL- диаграммами, широко применяемыми при программной реализации протоколов в телефонии [7].

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

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

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

Разработка программы начинается с того, что по словесному описанию поведения модуля составляется перечень его входных и выходных воздействий, отражаемый на схеме связей автомата. На схеме для каждого воздействия указывается его источник (приемник), полное название (на языке разработчика) и идентификатор в виде буквы латинского алфавита с номером. Для автомата идентификатор предлагается начинать с буквы 'A', для события — с 'e', для входной переменной — с 'x', для переменной состояния автомата — с 'y', а для выходного воздействия — с 'z'.

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

Дополнительные состояния

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

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

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

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

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

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

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

Теперь добавим в виде "заглушек" функции входных (если они имеются) и выходных воздействий (соответственно 'x' и 'z'), содержащие только вызовы функций протоколирования, и уже на ранней стадии программной реализации мы получим действующий макет разрабатываемого модуля, что соответствует принципу пошаговой нисходящей разработки [2].

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

Структура программы

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

Заключение

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

Предлагаемая в настоящей статье технология является новой попыткой введения такой дисциплины и основана на априорном задании требуемых состояний и их визуализации. Опыт ее применения вполне подтверждает высказывание: "то, что не специфицировано формально, не может быть проверено, а то, что не может быть проверено, не может быть безошибочным" [10]. Поэтому авторы надеются (особенно учитывая мнение о работе [5], высказанное в [11]), что их подход, по крайней мере для систем логического управления и событийных систем, в части создания качественных программ является приближением к тому, что Ф.Брукс называет "серебряной пулей" [2]. Заметим, что Брукс благосклонно отзывается только о подходе Дэвида Харела [8], также основанном на применении автоматов; достоинства SWITCH-технологии по сравнению с подходом Харела показаны в [7].

Автоматный подход начинает применяться все шире. Так, например, создатель операционной системы UNIX Кен Томпсон на вопрос о текущей работе ответил: "Мы создали язык генерации машин с конечным числом состояний, так как реальный селекторный телефонный разговор — это группа взаимодействующих машин с конечным числом состояний. Этот язык применяется в Bell Labs по прямому назначению — для создания указанных машин, а вдобавок с его помощью стали разрабатывать драйверы" [12].

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

По мнению авторов, SWITCH-технология позволяет, в соответствии с принципом Оккама, "не размножать сущности без необходимости" (как происходит, например, в UML) и обладает "минимализмом" [13], необходимым для обеспечения понимания программ.

В настоящее время наблюдается возрастание интереса к парадигме автоматного программирования [14—15]. Для большей ее популяризации на сайте www.softcraft.ru создан раздел "Автоматные модели".

Литература

1. Буч Г. Объектно-ориентированный анализ и проектирование с примерами приложений на С++. М.: Бином, СПб: Невский диалект, 1998. 560 с.
2. Брукс Ф. Мифический человеко-месяц, или Как создаются программные системы. СПб.: Символ, 2000. 304 с.
3. Секреты программирования игр /А. Ла Мот, Д. Ратклифф, М. Семинаторе и др. СПб.: Питер, 1995. 278 с.
4. Дейкстра Э. Взаимодействие последовательных процессов // Языки программирования. М.: Мир, 1972, с.9—86.
5. Шалыто А.А. SWITCH-технология. Алгоритмизация и программирование задач логического управления. СПб.: Наука, 1998. 628 с.
6. Шалыто А.А., Туккель Н.И. SWITCH-технология — автоматный подход к созданию программного обеспечения "реактивных" систем
// Промышленные АСУ и контроллеры, 2000, №10, с.44—48.
7. Шалыто А.А. Алгоритмизация и программирование для систем логического управления и "реактивных" систем // Автоматика и телемеханика,
2001, №1, c.3—39.
8. Буч Г., Рамбо Д., Джекобсон А. Язык UML. Руководство пользователя. М.: ДМК, 2000. 432 с.
9. Черняк Л. Создание программ как инженерная дисциплина // Computerworld Россия, 2000, №37, c.18—20.
10. Зайцев С.С. Описание и реализация протоколов сетей ЭВМ. М.:Наука, 1989. 112 с.
11. Герр Р. Новый поворот // PC Magazine / Russian Edition, 1998,№10, с.88—90.
12. Кук Д., Урбан Д., Хамилтон С. Unix и не только: Интервью с Кеном Томпсоном // Открытые системы, 1999, №4, с.35—47.
13. Герр Р. Отладка человечества // PC Magazine / Russian Edition, 2000, №5, с.90—91.
14. Любченко В.С. Мы выбираем, нас выбирают... (к проблеме выбора алгоритмической модели) // Мир ПК, 1999, №3.
15. Кузнецов Б.П. Психология автоматного программирования // BYTE / Россия, 2000, №11.

Статья: Программирование с явным выделением состояний



Назад в раздел