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

Актуальность проблемы. При разработке телекоммуникационных систем и компьютерных сетей весьма актуальной является задача формализации описаний их поведения. При этом наиболее известным является графический< язык описаний и спецификаций SDL [1] (Specification and Description Language), разработанный Международным союзом электросвязи (ITU-T). Этот язык входит в Рекомендации ITU-T серии Z.100.

Диаграммы, являющиеся основой этого языка, в отличие от схем алгоритмов, содержат состояния в явном виде. Поэтому язык SDL является автоматным. Однако SDL-диаграммы обладают рядом недостатков, к которым можно отнести, например, громоздкость. С другой стороны, при разработке систем рассматриваемого класса все шире используется объектно-ориентированное программы, для проектирования которых применяется' унифицированный язык моделирования [2] (UML —Unified Modeling Language). В этом языке для описания поведения также используется автоматная модель — диаграммы состояний Statecharts [3], предложенные Д. Харелом. Эти диаграммы из-за использования словесных обозначений также являются весьма громоздкими.

Поэтому в последние годы были выполнены исследования, направленные на объединение языков SDL и UML (Рекомендации Z.109 ITU-Т, 2000). Однако из изложенного выше следует, что применительно к описанию поведения, даже совместное применение указанных выше языков не делает диаграммы менее громоздкими.

Для устранения этого недостатка с 1991 года в России разрабатывается б’Ж/ГСЯ-технология [4], предназначенная для алгоритмизации и программирования систем со сложным поведением. Эта технология была названа также автоматным программированием. Графы переходов, используемые для описания поведения в рамках предлагаемого подхода, достаточно компактны, так как они применяются совместно со схемами связей, подробно описывающими интерфейс автоматов.

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

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

Целью диссертационной работы является разработка методов проектирования и реализации поведения программных систем на основе автоматного подхода.

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

Основные задачи исследования состоят в следующем.

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

2. Разработка образца проектирования (паттерна) объектов, с изменяющимся в зависимости от состояния поведением, в котором устранены недостатки известного паттерна State [5].

3. Разработка языка автоматного программирования, основанного на непосредственной поддержке предложенного паттерна.

Методы исследования. В работе использованы методы дискретной математики, построения и анализа алгоритмов, теории автоматов, построения компиляторов, паттерны проектирования объектно-ориентированных программ.

Научная новизна. В работе получены следующие научные результаты, которые выносятся на защиту.

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

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

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

4. На базе предложенного паттерна, за счет введения дополнительных синтаксических конструкций в язык Java [6], разработан автоматный язык State Machine, позволяющий писать программы непосредственно в терминах автоматного программирования.

Результаты диссертации были получены в ходе выполнения научно-исследовательских работ «Разработка технологии программного обеспечения систем управления на основе автоматного подхода», выполненной по заказу Министерства образования РФ в 2001 — 2004 гг., и «Разработка технологии автоматного программирования», выполненной по гранту Российского фонда фундаментальных исследований по проекту № 02−07−90 114 в 2002 — 2003 гг. (http://is.ifmo.ru, раздел «Наука»).

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

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

Реализация результатов работы. Результаты, полученные в диссертации, используются на практике.

1. В компании eVelopers [7] (Санкт-Петербург) при создании системы автозавершения ввода в пакете автоматно-ориентированного программирования Unimod [8].

2. В компании Транзас [9] (Санкт-Петербург) при создании телекоммуникационной системы управления движением судов Navi Harbour.

3. В учебном процессе на кафедре «Компьютерные технологии» СПбГУ ИТМО при чтении лекций по курсам «Теория автоматов в программировании» и «Программирование на языке Java».

Апробация диссертации. Основные положения диссертационной работы докладывались на XXXIII конференции профессорско-преподавательского состава СПбГУ ИТМО (Санкт-Петербург, 2004), научно-методических конференциях «Телематика-2002», «Телематика-2004» (Санкт-Петербург) и на конференции Microsoft Research Academic Days 2004 (Санкт-Петербург).

Публикации. По теме диссертации опубликовано 9 печатных работ, в том числе в журналах «Информационно-управляющие системы», «Программист», «Компьютерные инструменты в образовании», «Телекоммуникации и информатизация образования» и «Мир ПК».

Структура диссертации. Диссертация изложена на 193 страницах и состоит из введения, пяти глав и заключения.

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

содержит.

Все основные результаты, полученные в диссертации, опубликованы. Кроме работ автора, на которые даны ссылки в тексте диссертации, им опубликованы также и работы [69−74]. Приведем информацию о личном вкладе автора.

В работах [69, 70] автором предложена идея метода преобразования рекурсивных программ в автоматные. Выполнена реализация ряда примеров на основе этого метода.

В работе [71] автор предложил один из методов оптимизации алгоритмов обхода доски. Он также выполнил ряд реализаций этого алгоритма.

В работах [52, 72] автором предложен язык автоматного программирования и его реализация.

В работах [73, 74] автором предложен обход двоичных деревьев на основе автоматного подхода. Окончательная версия этого обхода и обобщение на случай обхода Личных деревьев была произведена в соавторстве.

В работе [48] при разработке паттерна State Machine автором был предложен ряд реализаций, устраняющих недостатки паттерна State. Автором продемонстрирована эффективность этого паттерна по сравнению другими объектно-ориентированными реализациями.

Заключение

.

В диссертации получены следующие научные результаты.

1. Обоснована целесообразность разделения множества состояний на два класса: управляющие и вычислительные на примерах таких классических алгоритмов как, например, «Ханойские башни», «Обход шахматной доски ходом коня», «Обход деревьев». Показано, что, как и в машине Тьюринга, небольшое число состояний первого типа может управлять огромных числом состояний второго типа.

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

3. Разработан паттерн проектирования State Machine, устраняющий такие недостатки известного паттерна State как сложность повторного использования классов состояний, децентрализованная логика переходов и сильная связность классов состояний друг от друга.

4. Для непосредственной поддержки паттерна State Machine предложен одноименный язык программирования. Этот язык является расширением языка Java за счет введения в него синтаксических конструкций automaton, state, events. Реализован препроцессор, преобразующий код, написанный на этом языке, в код на языке Java.