«РАЗРАБОТКА МЕТОДОВ ПРОЕКТИРОВАНИЯ И РЕАЛИЗАЦИИ ПОВЕДЕНИЯ ПРОГРАММНЫХ СИСТЕМ НА ОСНОВЕ АВТОМАТНОГО ПОДХОДА ...»

Санкт-Петербургский государственный

университет информационных технологий, механики и оптики

На правах рукописи

Шамгунов Никита Назимович

РАЗРАБОТКА МЕТОДОВ ПРОЕКТИРОВАНИЯ И

РЕАЛИЗАЦИИ ПОВЕДЕНИЯ ПРОГРАММНЫХ

СИСТЕМ НА ОСНОВЕ АВТОМАТНОГО ПОДХОДА

Специальность 05.13.13 — Телекоммуникационные системы и компьютерные сети Диссертация на соискание ученой степени кандидата технических наук

Научный руководитель — доктор технических наук, профессор Шалыто А.А.

Санкт-Петербург –

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ

ГЛАВА 1. ОБЗОР МЕТОДОВ, ПАТТЕРНОВ И ЯЗЫКОВ,

ПРИМЕНЯЮЩИХСЯ ДЛЯ ОПИСАНИЯ ПОВЕДЕНИЯ

ПРОГРАММ В ТЕЛЕКОММУНИКАЦИОННЫХ СИСТЕМАХ........ 1.1. Методы преобразования процедурных программ в автоматные

1.2. Паттерны проектирования. Паттерн State

1.3. Графический язык описаний и спецификаций SDL

1.4. Унифицированный язык моделирования UML

1.5. Язык ASML

1.6. SWITCH-технология

Выводы

ГЛАВА 2. ПРИМЕНЕНИЕ КОНЕЧНЫХ АВТОМАТОВ ДЛЯ

РЕАЛИЗАЦИИ ВЫЧИСЛИТЕЛЬНЫХ АЛГОРИТМОВ................. 2.1. Задача о Ханойских башнях

2.1.1. Классическое рекурсивное решение задачи

2.1.2. Обход дерева действий

2.1.3. Непосредственное перекладывание дисков

2.2. Задача о ходе коня

2.2.1. Методы оптимизации

2.2.2. Определение клеток, обход из которых невозможен

2.2.3. Выявление заблокированных клеток

2.2.4. Применение правила Варнсдорфа

2.2.5. Использование различных массивов ходов коня

2.2.6. Итеративная программа

2.2.7. Рекурсивная программа

2.2.8. Автоматная программа

2.3. Обход деревьев

2.3.1. Постановка задачи обхода двоичного дерева

2.3.2. Описание структур данных для представления двоичных деревьев

2.3.3. Ввод деревьев

2.3.4. Обход двоичного дерева без использования стека

2.3.5. Обход двоичного дерева с использованием стека

2.3.6. Обход k-ичного дерева без использования стека

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

2.4.1. Введение

2.4.2. Изложение метода

2.4.3. Факториал

2.4.4. Числа Фибоначчи

2.4.5. Задача о ханойских башнях

2.4.6. Задача о ранце

Выводы

ГЛАВА 3. ПАТТЕРН ПРОЕКТИРОВАНИЯ STATE MACHINE...... 3.1. Описание паттерна

3.1.1. Назначение

3.1.2. Мотивация

3.1.3. Применимость

3.1.4. Структура

3.1.5. Участники

3.1.6. Отношения

3.1.7. Результаты

3.1.8. Реализация

3.1.9. Пример кода

3.2. Повторное использование классов состояний

3.2.1. Расширение интерфейса автомата

3.2.2. Расширение логики введением новых состояний

Выводы

ГЛАВА 4. ЯЗЫК ПРОГРАММИРОВАНИЯ STATE MACHINE..... 4.1. Особенности языка State Machine

4.2. Пример использования языка State Machine

4.2.1. Описание примера

4.2.2. Описание состояний

4.2.3. Описание автомата

4.2.4. Компиляция примера

4.3. Грамматика описания автоматов и состояний

4.3.1. Грамматика описания состояния

4.3.2. Грамматика описания автомата

4.4. Повторное использование

4.4.1. Допустимые способы повторного использования

4.4.2. Описание примеров

4.4.3. Наследование состояний

4.4.4. Использование одного состояния в различных автоматах

4.5. Реализация препроцессора

4.5.1. Генерация Java-классов по описанию состояний

4.5.2. Генерация Java-классов по описанию автоматов

Выводы

ГЛАВА 5. ВНЕДРЕНИЕ РЕЗУЛЬТАТОВ РАБОТЫ

5.1. Область внедрения

5.1.1. Система Navi Harbour

5.1.2. База данных СУДС

5.2. Постановка задачи

5.3. Применение паттерна State Machine для проектирования класса ThreadFactory................. 5.3.1. Формализация постановки задачи

5.3.2. Проектирование автомата ThreadFactory

5.3.3. Диаграмма классов реализации автомата ThreadFactory

5.3.4. Реализация контекста автомата ThreadFactory

5.3.5. Пример реализации класса состояния автомата ThreadFactory

5.4. Приложение, визуализирующее работу класса ThreadFactory

5.5. Сравнение реализации класса ThreadFactory на основе паттерна State Machine и традиционного подхода

5.6. Сравнение реализации класса ThreadFactory на основе паттерна State Machine и SWITCHтехнологии

Выводы

ЗАКЛЮЧЕНИЕ

ЛИТЕРАТУРА

Введение Актуальность проблемы. При разработке телекоммуникационных систем и компьютерных сетей весьма актуальной является задача формализации описаний их поведения. При этом наиболее известным является графический язык описаний и спецификаций 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 ITUT, 2000). Однако из изложенного выше следует, что применительно к описанию поведения, даже совместное применение указанных выше языков не делает диаграммы менее громоздкими.

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

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

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

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

вычислительные алгоритмы (в основном рекурсивные) и задачи управления.

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

Основные задачи

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

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

изменяющимся в зависимости от состояния поведением, в котором устранены недостатки известного паттерна State [5].

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

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

результаты, которые выносятся на защиту.

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

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

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

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

Результаты диссертации были получены в ходе выполнения научноисследовательских работ «Разработка технологии программного обеспечения систем управления на основе автоматного подхода», выполненной по заказу Министерства образования РФ в 2001 – 2004 гг., и «Разработка технологии автоматного программирования», выполненной по гранту Российского фонда фундаментальных исследований по проекту № 02-07-90114 в 2002 – 2003 гг.

(http://is.ifmo.ru, раздел «Наука»).

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

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

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

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

телекоммуникационной системы управления движением судов Navi В учебном процессе на кафедре «Компьютерные технологии»

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

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

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

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

Работа иллюстрирована 46 рисунками и содержит две таблицы.

Глава 1. Обзор методов, паттернов и языков, применяющихся для описания поведения программ в телекоммуникационных системах 1.1. Методы преобразования процедурных программ в автоматные Известна работа [10], в которой предложено преобразовывать итеративные программы в автоматные, например, с целью их визуализации.

В этой работе не описывается способ преобразования рекурсивных программ в автоматные.

1.2. Паттерны проектирования. Паттерн State Паттерны (образцы) проектирования представляют собой примеры наиболее удачных проектных решений в области объектноориентированного программирования. Применительно к теме данной работы наибольший интерес представляет паттерн State [5].

Паттерн State является наиболее известной реализацией объекта, изменяющего поведение в зависимости от состояния. В указанной работе данный паттерн недостаточно полно специфицирован, поэтому в разных источниках, например в работах [11, 12], он реализуется по-разному (в частности, громоздко и малопонятно). Поэтому многие программисты считают, что этот паттерн не предназначен для реализации автоматов.

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

1.3. Графический язык описаний и спецификаций SDL Для построения телекоммуникационных систем используется графический язык SDL [1], разработанный Международным институтом электросвязи (ITU-T). Отличительная особенность языка SDL состоит в том, что он не предусматривает никакой разницы между спецификацией и описанием. Основу этого языка составляет концепция взаимодействия конечных автоматов и связей между ними, называемых процессами, описываемых SDL-диаграммами. Для построения этих диаграмм разработан набор графических символов. На рис. 1 приведен пример [1] описания одного из процессов на языке SDL.

Отметим, что диаграммы в языке SDL весьма громоздки и соответствуют только одному классу автоматов — автоматам Мили [4].

1.4. Унифицированный язык моделирования UML Унифицированный язык моделирования (Unified Modeling Language, UML) [2] является графическим языком для визуализации, спецификации, конструирования и документирования систем, в которых большая роль принадлежит программному обеспечению. С помощью UML можно разработать детальный план создаваемой системы, отображающий не только ее концептуальные элементы, такие как системные функции и бизнеспроцессы, но и конкретные особенности реализации.

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

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

выразительными моделями.

Предоставляет механизмы расширения и специализации.

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

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

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

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

Диаграммы активности являются развитием схем алгоритмов в части реализации параллельных процессов.

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

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

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

1.5. Язык ASML В настоящее время в компании Microsoft развивается язык AsmL (

Abstract

State Machine Language), предложенный Ю. Гуревичем [13]. Этот язык применим в ситуациях, когда необходимо точно специфицировать компьютерную систему в части ее функциональности. Менеджеры, разработчики и тестеры могут использовать язык AsmL для спецификации задач.

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

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

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

1.6. SWITCH-технология С 1991 года в России развивается SWITCH-технология, которая предназначена для проектирования программ на основе конечных автоматов.

Качество программ, построенных с ее использованием достигается за счет выразительных средств графов переходов и изоморфного перехода от графов к программам. Эта технология успешно зарекомендовала себя при создании систем логического управления. С применением этой технологии студентами и аспирантами СПбГУ ИТМО было создано более пятидесяти проектов [14] в самых разных областях разработки программного обеспечения. Это проанализировать ее сильные и слабые стороны.

Для SWITCH-технологии разработана графическая нотация для описания конечных автоматов. Для автоматизации построения диаграмм в этой нотации разработан инструмент проектирования Unimod [7], подключаемый к среде разработки Eclipse [15].

Отметим, что SWITCH-технология обладает рядом недостатков.

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

Выводы Из изложенного выше следует.

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

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

Глава 2. Применение конечных автоматов для реализации вычислительных алгоритмов 2.1. Задача о Ханойских башнях Одной из наиболее известных рекурсивных задач является задача о ханойских башнях [16], которая формулируется следующим образом.

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

Покажем, что применение автоматов [17] позволяет формально переходить к итеративным алгоритмам решения этой задачи, либо строить такие алгоритмы непосредственно. В работах [18, 19] приведены примеры преобразований рекурсивных программ в итеративные, однако подходы, обеспечивающие такие преобразования, не формализованы. Настоящая работа призвана устранить этот пробел.

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

2.1.1. Классическое рекурсивное решение задачи Известны рекурсивные алгоритмы для решения рассматриваемой задачи [16, 20]. Приведем один из таких алгоритмов, построенный по методу «разделяй и властвуй». Задача о перекладывании N дисков с i-го на j-ый стержень может быть декомпозирована следующим образом.

Переложить N–1 диск со стержня с номером i на стержень с Переложить диск со стержня с номером i на стержень с номером j.

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

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

Рис. 3. Дерево декомпозиции для задачи о ханойских башнях при N = В этом дереве вершины, обозначенные прямоугольниками, соответствуют подзадачам, решаемым при каждом вызове рекурсивной функции. Эти вершины помечаются номерами стержня, с которого перекладывается диск, стержня, на который перекладывается диск, и числом перекладываемых дисков. При этом для вершины с пометкой (i,j,k) левая вершина поддерева будет помечена (i,6–i–j,k–1), средняя — (i,j,1), а правая — (6–i–j,j,k–1).

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

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

printf( "\nХаной с %d дисками:\n", input ) ;

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

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

Это дерево обладает следующим свойством: для вершины с пометкой (i,j) вершина левого поддерева имеет пометку (i,6–i–j), а вершина правого поддерева — (6–i–j,j).

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

Построим итеративный алгоритм обхода этого дерева. Не храня его в памяти, будем осуществлять двоичный поиск каждой вершины, начиная с корневой, так как для нее известны номера стержней и способ определения их номеров для корневых вершин левого и правого поддеревьев. Например, для вершины с номером 5, на первом шаге алгоритма осуществляется переход от вершины 4 к ее правому поддереву — вершине 6, так как пять больше четырех. На втором шаге осуществляется переход от вершины 6 к ее левому поддереву — искомой вершине 5, так как пять меньше шести. Таким образом, несмотря на то, что обход дерева осуществляется слева направо, алгоритм работает сверху вниз.

Итеративная программа обхода дерева действий:

int max_nodes = (1 r и node->p соответственно.

2.3.3. Ввод деревьев Ввод деревьев в примерах будем производить в следующем виде. В первое строке записано число N (количество вершин в дереве). Последующие N строк содержат описания вершин дерева. Для i-ой вершины в строке с номером i+2 (вершины нумеруются с нуля) указываются номера корней левого и правого поддеревьев. В случае отсутствия поддерева вместо номера корня записывается число -1. Для рассматриваемого примера исходные данные имеют следующий вид:

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

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

Таким образом, автомат имеет следующие состояния:

0. — Start — начальное (конечное) состояние.

2. — Right — движение вправо.

3. — Parent — движение вверх.

Автомат оперирует переменной node (имеющей тип Node*), являющейся указателем на текущий узел дерева.

Поясним, как строится граф переходов, описывающий поведение автомата. Переходы между состояниями определяются условиями, которыми помечаются соответствующие дуги графа переходов. Условия node->l, node->r и node->p обозначают наличие у текущего узла левого потомка, правого потомка и родителя соответственно. Отрицание будем обозначать восклицательным знаком (!). Например, переход из состояния Parent в состояние Start осуществляется при условии, что у вершины нет родителя.

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

Например, переход из состояния Right в состояние Left производится при условии, что у вершины есть правое поддерево. При этом на указанном переходе выполняется действие — изменяется переменная node, в которой хранится указатель на текущую вершину.

Кроме действий на переходах в автомате также выполняются действия в состояниях, например, в состоянии Left производится вывод номера текущей вершины на экран.

Граф переходом для реализации нерекурсивного обхода двоичного дерева без использования стека приведен на (рис. 9).

Отметим, что в случае безусловного перехода из одного состояния в другое дуга помечается символом 1 (переход из нулевой вершины в первую).

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

Отметим, что если в работах [31, 33] рассмотрено три типа обходов и для каждого из них предложен свой алгоритм, то предлагаемый подход позволяет, используя один и тот же граф переходов автомата, осуществлять все три обхода, за счет вывода номера текущей вершины только в одном из состояний: Left, Right, Parent. При этом в зависимости от выбранного состояния получим три стандартных обхода [31, 33]:

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

void traverseWithoutStack(Node const* node, int show) { if (show & SHOW_RIGHT) cout data r) { if (show & SHOW_PARENT) cout data p) { } while(state != START);

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

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

На этом рисунке используются следующие обозначения: push(node) — помещение текущего узла в стек, top() — узел в вершине стека, pop() — функция удаления узла из стека, возвращающая удаленную вершину, empty() — проверка стека на пустоту.

Заметим, что при всех обходах дерева в стек помещается одна и та же информация. Таким образом, один стек может быть использован для реализации всех трех обходов, что позволяет экономить память.

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

Приведем реализацию этого автомата при помощи конструкции switch, построенную по графу переходов формально и изоморфно.

void traverseWithStack(Node const* node, int show) { Граф переходов позволяет легко понять поведение программы, а также является тестом для ее проверки. Это объясняется тем, что состояния декомпозируют входные воздействия на группы, каждая из которых содержит условия, определяющая переходы только из этого состояния.

2.3.6. Обход k-ичного дерева без использования стека Изложенный подход может быть обобщен на случай k-ичных деревьев [33].

В программе дерево будем представлять в следующем виде:

где k — константа, c — массив, хранящий указатели на детей. Метод, предложенный для обхода двоичных деревьев без использования стека, можно обобщить для обхода k-ичных деревьев (рис. 11).

node = node->c[0] node->c[1] node = node->c[2] node->c[k-1] node = node->c[k-1] Рис. 11. Граф переходов автомата для реализации обхода Отметим, что у построенного автомата k+3 состояний. Таким образом, число состояний автомата зависит от k.

Приведем реализацию этого автомата при помощи конструкции switch, построенную по графу переходов формально и изоморфно.

switch ( state ) case Start :

case Child1 :

case Child2 :

case Child3 :

case Parent :

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

Предложим универсальное решение. Из графа переходов следует, что условия перехода и действия в состояниях с первого по k-ое очень похожи.

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

node = * child_ptr;child_ptr = node -> c Рис. 12. Редуцированный граф переходов автомата для реализации обхода Приведем реализацию этого автомата при помощи конструкции switch, построенную по графу переходов формально и изоморфно.

KNode * * child_ptr;

KNode * * next_ptr;

switch ( state ) case Start :

case Child:

2.4. Реализация рекурсивных алгоритмов на основе автоматного подхода 2.4.1. Введение В работе [35] предложен метод преобразования произвольных итеративных программ в автоматные программы, что позволяет реализовать произвольный итеративный алгоритм структурированной программой, содержащей один оператор do-while, телом которого является один оператор switch.

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

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

2.4.2. Изложение метода Идея метода состоит в моделировании работы рекурсивной программы автоматной программой, явно (также как и в работах [18, 19]) использующей стек. Отметим, что явное выделение стека по сравнению со "скрытым" его применением в рекурсии, позволяет программно задавать его размер, следить за его содержимым и добавлять отладочный код в функции, реализующие операции над стеком.

Перейдем к изложению метода.

Каждый рекурсивный вызов в программе выделяется как отдельный оператор. По преобразованной рекурсивной программе строится ее схема, в которой применяются символьные обозначения условий переходов (x), действий (z) и рекурсивных вызовов (R). Схема строится таким образом, чтобы каждому рекурсивному вызову соответствовала отдельная операторная вершина. Отметим, что здесь и далее под термином «схема программы» понимается схема ее рекурсивной функции.

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

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

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

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

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

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

6.2. Безусловный переход на дуге, направленной из вершины с номером 2 в вершину с номером 0, заменяется условием 6.3. К вершине с номером 2 добавляются дуги, направленные в вершины, в которые до преобразования графа входили дуги с рекурсией. На каждой из введеных дуг выполняется операция pop, извлекающая из стека верхний элемент.

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

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

printf( "{%d} ", stack[i].n ) ;

printf( "\n" ) ;

void fact( int n ) push {4,1,2,2}: {4,1,2,2} {3,1,3,3} push {2,1,2,2}: {2,1,2,2} {3,1,3,3} push {4,1,3,3}: {4,1,3,3} push {2,1,3,3}: {2,1,3,3} push {3,2,3,2}: {3,2,3,2} {2,1,3,3} push {4,2,3,2}: {4,2,3,2} {2,1,3,3} push {2,2,3,2}: {2,2,3,2} {2,1,3,3} 2.4.6. Задача о ранце Задача о ранце может быть сформулирована следующим образом.

Имеется N типов предметов, для каждого из которых известны его объем и цена, причем количество предметов каждого типа не ограничено.

Необходимо уложить предметы в ранец объема M таким образом, чтобы стоимость его содержимого была максимальна.

непосредственное рекурсивное решение этой задачи является крайне неэффективным из-за повторного решения одних и тех же подзадач [16].

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

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

int N = sizeof(items)/sizeof(item_t) ;// Количество типов item_t itemKnown[knap_cap+1];

maxKnown[cap] = max ; itemKnown[cap] = items[maxi];

knap_ret = max;

void show_knap( int cap, int value ) int total_size = 0 ;

printf( "\nВиды предметов {объем, цена} (%d):\n", N );

printf("{%d,%d} ", items[i].size, items[i].val);

printf("\n\nОбъем ранца: %d.\n", cap);

printf("Содержимое ранца:\n");

while(i > 0 && i - itemKnown[i].size >= 0) printf( "{%d,%d} ", itemKnown[i].size, total_size += itemKnown[i].size;

i -= itemKnown[i].size;

printf( "\nЗанятый объем: %d. Ценность: %d\n", show_knap( knap_cap, knap_ret ) ;

В приведенной программе массив maxKnown используется для запоминания результатов решения подзадач, а массив itemKnown применяется в функции show_knap() для определения содержимого ранца, полученного в результате решения задачи.

Построим схему этой программы (рис. 25).

Рис. 25. Схема программы решения задачи о ранце По схеме программы построим граф переходов автомата Мили (рис. 26).

Преобразуем этот граф переходов для моделирования работы рекурсивной программы. При этом дуга 4—5 направляется в вершину с номером 1, а выполняемый при переходе по этой дуге рекурсивный вызов заменяется на операцию push и действие (cap = space), выполняемое над параметром рекурсивной функции при ее вызове. Безусловный переход на дуге 2—0 заменяется на условие «стек пуст». Добавляется дуга 2—5, при переходе по которой выполняется действие pop (рис. 27).

Упростим этот граф за счет исключения неустойчивой вершины с номером 5 (рис. 28).

Приведем автоматную программу, построенную по графу переходов автомата Мили с семью состояниями.

stack_t stack[200] ;

push( int cap, int i, int space, int max, int maxi, int t stack[top].maxi = maxi ;

stack[top].t = t ;

printf( "push {%d,%d,%d,%d,%d,%d}: ", cap, i, show_stack() ;

pop( int *cap, int *i, int *space, int *max, int *maxi, printf( "pop {%d,%d,%d,%d,%d,%d}: ", stack[top].cap, stack[top].space, stack[top].max, stack[top].maxi, stack[top].t ) ;

*cap = stack[top].cap ;

*i = stack[top].i ;

*space = stack[top].space ;

*max = stack[top].max ;

*maxi = stack[top].maxi ;

*t = stack[top].t ;

show_stack() ;

int stack_empty() { return top < 0 ; } void show_stack() printf( "{%d,%d,%d,%d,%d,%d} ", stack[i].cap, stack[i].space, stack[i].max, stack[i].maxi, printf( "\n" ) ;

typedef struct int size, val ;

} item_t ;

item_t items[] = { 3,4, 4,5, 7,10, 8,11, 9,13 } ;

int N = sizeof(items)/sizeof(item_t) ;

int maxKnown[knap_cap+1] ;

item_t itemKnown[knap_cap+1] ;

void knap( int cap ) int i, space, max, maxi = 0, t ;

break ;

case 2:

else pop( &cap, &i, &space, &max, &maxi, &t ) ;

t = knap_ret + items[i].val ; y=6;

break ;

case 3:

{ space = cap - items[i].size ; y=4;} else maxKnown[cap] = max ;

itemKnown[cap] = items[maxi] ;

break ;

case 4:

if( space >= 0 ) push( cap, i, space, max, maxi, t ) ;

else break ;

case 6:

if( y_old != y ) printf( "Переход в состояние %d\n", void show_knap( int cap, int value ) int total_size = 0 ;

printf( "\nВиды предметов {объем, цена} (%d):\n", N ) ;

printf( "{%d,%d} ", items[i].size, items[i].val ) ;

printf( "\n\nОбъем ранца: %d.\n", cap ) ;

printf( "Содержимое ранца:\n" ) ;

while( i > 0 && i - itemKnown[i].size >= 0 ) printf( "{%d,%d} ", itemKnown[i].size, printf( "\nЗанятый объем: %d. Ценность: %d\n", show_knap( knap_cap, knap_ret ) ;

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

Виды предметов {объем, цена} (5):

{3,4} {4,5} {7,10} {8,11} {9,13} Содержимое ранца:

{3,4} {7,10} {7,10} Занятый объем: 17. Ценность: Выводы Показано, что использование автоматного подхода позволило получить наглядные и, в отличие от классических, универсальные алгоритмы решения задач обхода деревьев, которые весьма экономны по памяти.

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

В работе [36] было отмечено, что итеративные алгоритмы по вычислительной мощности эквивалентны рекурсивным. Однако, в известной авторам литературе, формальный метод преобразования рекурсивных алгоритмов в итеративные отсутствует. Как отмечалось во введении, в работах [18, 19] приведены примеры такого преобразования, которые, однако, не являются формализованными. Настоящая работа устраняет указанный пробел. При этом развивается основанный на использовании конечных автоматов подход, предложенный в работе [10].

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

Глава 3. Паттерн проектирования State Machine Наиболее известной реализацией объекта, изменяющего поведение в зависимости от состояния, является паттерн State [5]. В указанной работе данный паттерн недостаточно полно специфицирован, поэтому в разных источниках, например в работах [11, 12], он реализуется по-разному (в частности, громоздко и малопонятно). Поэтому многие программисты считают, что этот паттерн не предназначен для реализации автоматов.

Другой недостаток паттерна State состоит в том, что разделение реализации состояний по различным классам приводит и к распределению логики переходов по ним, что усложняет понимание программы. При этом не обеспечивается независимость классов, реализующих состояния, друг от друга. Таким образом, создание иерархии классов состояний и их повторное использование затруднено. Несмотря на эти недостатки, паттерн State достаточно широко применяется в программировании, например, при реализации синхронизации с источником данных в библиотеке Java Data Objects (JDO) [37].

Заметим, что проблемы с паттерном State возникают не только при его описании, но даже в определении, в том числе, из-за неправильного перевода. Так в работе [38] приведено следующее определение: «шаблон State — состояние объекта контролирует его поведение», в то время как более правильным было бы следующее: «шаблон State — состояния объекта управляют его поведением». Эти определения имеют разный смысл, так как в английском языке слово control переводится как управление, а в русском языке управление — это действие на объект, а контроль — мониторинг и проверка выполняемых действий на соответствие заданному поведению. Не случайно часто говорят «система управления и контроля».

Кроме работы [5], паттерн State, как отмечалось выше, описывается в работах [11, 12]. В них авторы рассматривают реализацию графов переходов автоматов с помощью этого паттерна. В работе [11] код реализации графа переходов с двумя вершинами занимает более десяти страниц текста. Такая же странная ситуация и в работе [12]. Автор этой книги легко справился с описанием и примерами к сорока шести паттернам, и только для паттерна State ему понадобилась помощь рецензента, который предоставил ему пример. Однако приведенный в этом примере граф переходов с четырьмя вершинами реализован таким образом, будто бы автор недостаточно разобрался в паттерне.

В настоящей работе, предлагается новый паттерн, объединяющий достоинства реализации автоматов в SWITCH-технологии [4] (централизация логики переходов) и паттерна State (локализация кода, зависящего от состояния в отдельных классах).

Новый паттерн назван State Machine. Обратим внимание, что в работе [39] уже был предложен паттерн с аналогичным названием, предназначенный для программирования параллельных систем реального времени на языке Ada 95. Тем не менее, авторы выбрали именно это название, как наиболее точно отражающее суть предлагаемого паттерна.

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

Более двадцати методов реализации объектов, изменяющих поведение в зависимости от состояния, рассмотрены в работе [40]. Паттерн State Machine мог бы продолжить этот список. Наиболее близким к новому паттерну является объединение паттернов State и Observer, рассмотренное в работе [41]. Однако, предложенный в этой работе подход достаточно сложен, так как добавляет новый уровень абстракции — класс ChangeManager. В паттерне State Machine используется более простая модель событий, не привлекающая относительно тяжелую реализацию паттерна Observer. В работе [42] предложена реализация паттерна State, позволяющая создавать иерархии классов состояний. Зависимость между классами состояний снижается за счет того, что переход в новое состояние осуществляется по его имени. Такая реализация, тем не менее, не снимает семантической зависимости между классами состояний.

3.1. Описание паттерна В названиях разделов будем придерживаться соглашений, введенных в работе [5].

3.1.1. Назначение Паттерн State Machine предназначен для создания объектов, поведение которых варьируется в зависимости от состояния. При этом для клиента создается впечатление, что изменился класс объекта. Таким образом, назначение предлагаемого паттерна фактически совпадает с таковым для паттерна State [5], однако, как будет показано ниже, область применимости последнего уже.

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

3.1.2. Мотивация Предположим, что требуется спроектировать класс Connection, представляющий сетевое соединение. Простейшее сетевое соединение имеет два управляющих состояния: соединено и разъединено. Переход между этими состояниями происходит или при возникновении ошибки или посредством вызовов методов установить соединение (connect) и разорвать соединение (disconnect). В состоянии соединено может производиться получение (метод receive) и отправка (метод send) данных по соединению. В случае возникновения ошибки при передаче данных генерируется исключительная ситуация (IOException) и сетевое соединение разъединяется. В состоянии разъединено прием и отправка данных невозможна. При попытке осуществить передачу данных в этом состоянии объект также генерирует исключительную ситуацию.

Таким образом, интерфейс, который необходимо реализовать в классе Connection, должен выглядеть следующим образом (здесь и далее примеры приводятся на языке Java):

package connection;

import java.io.IOException;

public interface IConnection { public void connect() throws IOException;

public void disconnect() throws IOException;

public int receive() throws IOException;

public void send(int value) throws IOException;

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

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

реализующим состояния, не требуется «знать» друг о друге, так как выбор состояния, в которое производится переход, осуществляется контекстом в зависимости от текущего состояния и события.

Отметим, что графы переходов, применяемые для описания логики переходов при проектировании с использованием паттерна State Machine, отличаются от графов переходов, рассмотренных в работах [3, 4, 43].

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

Граф переходов для описания поведения класса Connection приведен на рис. 29. В нем классы, реализующие состояния соединено и установление связи, DISCONNECT — обрыв связи, а ERROR — ошибку передачи данных.

Рис. 29. Граф переходов для класса Connection Рассмотрим в качестве примера обработку разрыва соединения при ошибке передачи данных. При реализации с использованием паттерна State состояние ConnectedState укажет контексту, что следует перейти в состояние DisconnectedState. В случае же паттерна State Machine контекст будет уведомлен о наступлении события ERROR, а тот осуществит переход в состояние DisconnectedState. Таким образом, классы ConnectedState и DisconnectedState не знают о существовании друг друга.

3.1.3. Применимость Паттерн State Machine может быть использован в следующих случаях.

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

Рефакторинг кода [44], зависящего от состояния объекта.

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

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

Эмуляции абстрактных и структурных автоматов.

Таким образом, область применимости паттерна State Machine шире, чем у паттерна State.

3.1.4. Структура На рис. 30 изображена структура паттерна State Machine.

Здесь IAutomatonInterface — интерфейс, реализуемого объекта, а operation1, operation2, … — его методы. Этот интерфейс реализуется основным классом Context и классами состояний ConcreteState1, ConcreteState2, …. Для смены состояния объекта используются события event1_1, event2_1, …, event2_1, event2_2, …, являющиеся объектами класса Event. Класс Context содержит ссылки на все состояния объекта (ConcreteState1 и ConcreteState2), а также на текущее состояние (state). В свою очередь, классы состояний содержат ссылку на модель данных (dataModel) и интерфейс уведомления о событиях (eventSink). Для того чтобы не загромождать рисунок, на нем не отражены связи классов состояний и класса Event.

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

3.1.5. Участники Паттерн State Machine состоит из следующих частей.

Интерфейс автомата (IAutomatonInterface) — реализуется контекстом и является единственным способом взаимодействия клиента с автоматом. Этот же интерфейс реализуется классами Контекст (Context) — класс, в котором инкапсулирована логика переходов. Он реализует интерфейс автомата, хранит экземпляры модели данных и текущего состояния.

Классы состояний (ConcreteState1, ConcreteState2, …) — состояниями и передаются контексту, который осуществляет переход в соответствии с текущим состоянием и событием.

Интерфейс уведомления о событиях (IEventSink) — реализуется контекстом и является единственный способом взаимодействия объектов состояний с контекстом.

Модель данных (DataModel) — класс предназначен для хранения и обмена данными между состояниями.

Отметим, что в предлагаемом паттерне, интерфейс автомата реализуется как контекстом, так и классами состояний. Это позволяет добиться проверки целостности еще на этапе компиляции. В паттерне State такая проверка невозможна из-за различия интерфейсов контекста и классов состояний.

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

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

Решение о смене состояния принимает контекст на основе события, пришедшего от конкретного объекта состояния.

3.1.7. Результаты Сформулируем результаты, получаемые при использовании паттерна State Machine.

Также как и в паттерне State, поведение, зависящее от состояния, локализовано в отдельных классах состояний.

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

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

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

Паттерн State Machine предоставляет «чистый» (без лишних методов) интерфейс для пользователя. Для того чтобы клиенты не имели доступа к интерфейсу IEventSink, реализуемого классом контекста, следует использовать или закрытое (private) наследование (например, в языке C++) или определить закрытый конструктор и статический метод, создающий экземпляр контекста, возвращающий интерфейс автомата. Соответствующий фрагмент кода имеет вид:

class Automaton implements IAutomatonInterface { В отличие от паттерна State паттерн State Machine не содержит дублирующих интерфейсов для контекста и классов состояний.

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

Более того, при реализации наследования в паттерне State также затруднено и расширение интерфейса автомата. Скорее всего, именно по этим причинам в работе [5] не описано наследование В работе [45] рассматривается задача реализации объектов, часть методов которых не зависит от состояния, для решения которой предложен паттерн Three Level FSM. Данная задача может быть также решена и при помощи паттерна State Machine. Для этого следует разделить интерфейс реализуемого объекта и интерфейс соответствии с описываемым паттерном. Для реализации полного интерфейса объекта создается наследник контекста, в котором определяются методы, не зависящие от состояния (рис. 31).

Рис. 31. Реализация методов, не зависящих от состояния 3.1.8. Реализация Рассмотрим возможные модификации паттерна State Machine.

Хранение модели данных. Контекст можно реализовать таким образом, чтобы он включал в себя модель данных, как предлагается в паттерне State. Тогда в конструктор объекта состояния передается только один параметр. Однако при таком подходе зависимость реализации состояний от контекста увеличивается, что усложняет повторное использование классов состояний.

Stateless и stateful классы состояний. В паттерне State Machine контекст и классы состояний реализуют интерфейс автомата. Это достигается за счет того, что указанные классы содержат ссылки на модель данных и интерфейс уведомления о событиях. Таким предыстории). Такой подход не всегда приемлем, поскольку в некоторых ситуациях критичен расход памяти. Паттерн State Machine можно видоизменить так, чтобы состояния были stateless (не зависят от предыстории). При этом для классов состояний интерфейса автомата тем, что в каждый метод добавлены параметры, через которые передаются ссылки на модель данных и интерфейс уведомления о событиях. Это приводит к фактическому дублированию интерфейсов, что затрудняет модификацию кода и его повторное использование, но экономит память.

Задание переходов. Переходы между состояниями задаются в контексте. Это можно сделать, например, при помощи конструкции switch, как предлагается в SWITCH-технологии [4]. Переходы также можно задать таблицей, отображающей пару в. Инфраструктуру для реализации табличного подхода можно реализовать в базовом для всех контекстов классе.

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

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

3.1.9. Пример кода Коды всех примеров, описанных в статье, доступны по адресу [46].

В следующем примере приведен код на языке Java, реализующий класс Соединение, описанный в разд. 3.1.2. Это упрощенная модель произвольного удаленного соединения, через которое можно передавать данные.

Прежде всего, опишем интерфейсы и базовые классы, которые используются в данном примере. Эти классы вынесены в пакет ru.ifmo.is.sm (sm — сокращение от State Machine). Диаграмма классов этого пакета приведена на рис. 32.

Рис. 32. Диаграмма классов пакета ru.ifmo.is.sm Опишем классы и интерфейсы, входящие в него.

IEventSink — интерфейс уведомления о событии:

Event — класс события. Используется для уведомления контекста из классов состояний:

StateBase — базовый класс для состояний. Для проверки типов во время компиляции применяются параметры типа (generic, template), появившееся в Java 5.0. В конструкторе запоминается интерфейс для приема событий:

public abstract class StateBase {

protected final IEventSink eventSink;

public StateBase(AI automaton, IEventSink AutomatonBase — базовый класс для всех автоматов. Он предоставляет возможность наследнику регистрировать переходы, используя метод addEdge. Дополнительно класс AutomatonBase реализует интерфейс уведомления о событии:

import java.util.IdentityHashMap;

public abstract class AutomatonBase

Классы, созданные в соответствии с паттерном State Machine, образуют пакет сonnection. Диаграмма классов этого пакета приведена на рис. 33.

Рис. 33. Диаграмма классов пакета connection В качестве модели данных автомата используется класс Socket, в рассматриваемом случае реализующий интерфейс IConnection.

После определения интерфейса для клиента и модели данных необходимо перейти к определению управляющих состояний автомата. Для DisconnectedState. В состоянии ConnectedState могут произойти события ERROR и DISCONECT, а в состоянии DisconnectedState — события CONNECT и ERROR (рис. 29).

Обратим внимание, что на рис. 29 присутствуют дуги, помеченные одинаковыми событиями. В данном примере объекты событий создаются в классе состояния, из которого исходит переход. Например, событие ERROR DisconnectedState не совпадает с аналогичным событием на петле из состояния DisconnectedState. При другой реализации для события ERROR мог бы быть создан только один объект.

Приведем код классов состояний.

Класс ConnectedState:

package connection;

import ru.ifmo.is.sm.*;

import java.io.IOException;

public class ConnectedState extends StateBase implements IConnection { public static final Event DISCONNECT = new public static final Event ERROR = new Event("ERROR");

protected final Socket socket;

public ConnectedState(AI automaton, IEventSink super(automaton, eventSink);

public void connect() throws IOException { public void disconnect() throws IOException { eventSink.castEvent(DISCONNECT);

public int receive() throws IOException { public void send(int value) throws IOException { специализирует параметр типа класса StateBase. При расширении специализируют этот тип. Окончательная специализация указывается при создании класса состояния в конструкторе автомата. Это обеспечивает возможность последующего расширения интерфейса автомата и классов состояний.

Класс DisconnectedState:

package connection;

import java.io.IOException;

import ru.ifmo.is.sm.*;

public class DisconnectedState extends StateBase implements IConnection { public static final Event CONNECT = new public static final Event ERROR = new Event("ERROR");

protected final Socket socket;

public DisconnectedState(AI automaton, IEventSink super(automaton, eventSink);

this.socket = socket;

public void connect() throws IOException { } catch (IOException e) { eventSink.castEvent(ERROR);

eventSink.castEvent(CONNECT);

public void disconnect() throws IOException { public int receive() throws IOException { throw new IOException("Connection is closed public void send(int value) throws IOException { throw new IOException("Connection is closed (send)");

Остается описать класс Connection — контекст. В этом классе реализована логика переходов, в соответствии с графом переходов на рис. 29.

Заметим, что последние четыре метода этого класса — делегирование интерфейса текущему состоянию:

package connection;

import java.io.IOException;

import ru.ifmo.is.sm.AutomatonBase;

public class Connection extends addEdge(connected, ConnectedState.DISCONNECT, addEdge(connected, ConnectedState.ERROR, addEdge(disconnected, DisconnectedState.CONNECT, addEdge(disconnected, DisconnectedState.ERROR, // Создание экземпляра автомата public static IConnection createAutomaton() { // Делегирование методов интерфейса public void connect() throws IOException { public void disconnect() throws IOException { public int receive() throws IOException { return public void send(int value) throws IOException { Обратим внимание, что в классах состояний определена только логика генерации событий, а логика переходов сконцентрирована в классе контекста.

3.2. Повторное использование классов состояний Рассмотрим два расширения класса Connection. Первое расширение будет демонстрировать возможность добавления методов в интерфейс класса, а второе — изменение поведения за счет введения новых состояний.

3.2.1. Расширение интерфейса автомата Проиллюстрируем возможность расширения интерфейса автомата на примере добавления возможности возврата данных в объект соединения для их последующего считывания. Введем интерфейс IPushBackConnection, расширяющий интерфейс IConnection методом pushBack. Таким образом, расширенный интерфейс выглядит следующим образом:

package push_back_connection;

import connection.IConnection;

import java.io.IOException;

public interface IPushBackConnection extends IConnection void pushBack(int value) throws IOException;

push_back_connection, диаграмма классов которого представлена на рис. 34.

Рис. 34. Диаграмма классов пакета push_back_connection При вызове метода pushBack(int value) значение, переданное в параметре этого метода, заносится в стек. При последующем вызове метода receive возвращается элемент из вершины стека, а если стек пуст, то значение извлекается из объекта socket.

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

Приведем реализацию класса PushBackConnectedState (класс PushBackDisconnectedState реализуется аналогично). При этом класс наследуя его логику:

package push_back_connection;

import connection.*;

import ru.ifmo.is.sm.IEventSink;

import java.util.Stack;

import java.io.IOException;

public class PushBackConnectedState extends ConnectedState implements public PushBackConnectedState(AI automaton, IEventSink super(automaton, eventSink, socket);

public int receive() throws IOException { public void pushBack(int value) { stack.push(new Integer(value));

Отметим, что в классе PushBackConnectedState параметр типа специализируется еще более чем в классе ConnectedState. Это требуется для того, чтобы поле automaton, определенное в классе StateBase имело правильный тип — IPushBackConnection. Таким образом, интерфейс автомата “протягивается” сквозь всю иерархию классов состояний через параметр типа.

Созданные классы состояний используются для реализации класса контекста PushBackConnection:

package push_back_connection;

import connection.Socket;

import ru.ifmo.is.sm.AutomatonBase;

import java.io.IOException;

public class PushBackConnection extends private PushBackConnection() { IPushBackConnection connected = new PushBackConnectedState(this, IPushBackConnection disconnected = new PushBackDisconnectedState(thi // Логика переходов addEdge(connected, PushBackConnectedState.DISCONNECT, disconnected);

addEdge(connected, PushBackConnectedState.ERROR, disconnected);

addEdge(disconnected, PushBackDisconnectedState.CONNECT, connected);

// Начальное состояние state = disconnected;

// Создание экземпляра автомата public static IPushBackConnection createAutomaton() { return new PushBackConnection();

// Делегирование методов интерфейса public void connect() throws IOException { state.connect(); } public void disconnect() throws IOException { state.disconnect(); } public int receive() throws IOException { return state.receive(); } public void send(int value) throws IOException { state.send(value); } public void pushBack(int value) throws IOException { state.pushBack(value); } Приведенный пример иллюстрирует, что классы состояний могут использоваться повторно в случае расширения интерфейса автомата.

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

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

ResumableConnection.

реализовать класс ErrorState, определяющий поведение в состоянии ошибка. Для состояний соединено и разъединено используются классы ConnectedState и DisconnectedState, уже разработанные в разд.

3.1.9. Граф переходов для класса ResumableConnection изображен на рис. 35.

Рис. 35. Граф переходов класса ResumableConnection Класс ErrorState реализуется следующим образом:

package resumable_connection;

import connection.*;

import ru.ifmo.is.sm.*;

import java.io.IOException;

public class ErrorState extends StateBase implements IConnection { public static final Event CONNECT = new public static final Event DISCONNECT = new Event("DISCONNECT");

protected final Socket socket;

public ErrorState(AI automata, IEventSink eventSink, super(automata, eventSink);

this.socket = socket;

public void connect() throws IOException { socket.connect();

castEvent(CONNECT);

public void disconnect() throws IOException { castEvent(DISCONNECT);

public int receive() throws IOException { return automaton.receive();

public void send(int value) throws IOException { automaton.send(value);

Класс ResumableConnection реализуется следующим образом:

package resumable_connection;

import connection.*;

import ru.ifmo.is.sm.AutomatonBase;

import java.io.IOException;

public class ResumableConnection extends implements IConnection { private ResumableConnection() { Socket socket = new Socket();

// Создание объектов состояний IConnection connected = new ConnectedState(this, this, IConnection disconnected = new DisconnectedState(this, IConnection error = new ErrorState(this, this, // Логика переходов addEdge(connected, ConnectedState.DISCONNECT, disconnected);

addEdge(connected, ConnectedState.ERROR, error);

addEdge(disconnected, DisconnectedState.CONNECT, addEdge(disconnected, DisconnectedState.ERROR, addEdge(error, ErrorState.CONNECT, connected);

addEdge(error, ErrorState.DISCONNECT, disconnected);

// Начальное состояние state = disconnected;

// Создание экземпляра автомата public static IConnection createAutomaton() { return new ResumableConnection();

// Делегирование методов интерфейса public void connect() throws IOException { state.connect(); } public void disconnect() throws IOException { public int receive() throws IOException { return public void send(int value) throws IOException { Из приведенного примера видно, что классы состояний могут быть использованы повторно при реализации других автоматов.

Выводы Паттерн State Machine является усовершенствованием паттерна State.

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

Новый паттерн устраняет ряд недостатков, присущих паттерну State.

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

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

В паттерне State логика переходов распределена по классам сложность восприятия логики переходов в целом. В паттерне State Machine логика переходов реализуется в контексте. Это позволяет разделить логику переходов и поведение в конкретном состоянии.

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

Автоматическая генерация кода обычно используется в CASE-средствах.

Второй подход можно реализовать, например, на языке Self [47], в котором описанное выше делегирование можно выполнить при помощи динамического наследования. Это обеспечивается тем, что язык позволяет непосредственно изменять класс объекта во время выполнения, а объекты в этом языке могут делегировать операции другим объектам.

Глава 4. Язык программирования State Machine В программировании часто возникает потребность в объектах, изменяющих свое поведение в зависимости от состояния. Обычно поведение таких объектов описывается при помощи конечных автоматов. Существуют различные паттерны проектирования для реализации указанных объектов, приведенные, например, в работах [5, 40]. В большинстве из этих паттернов или автоматы реализуются неэффективно, или сильно затруднено повторное использование компонентов автомата. Эти недостатки устранены в предложенном авторами паттерне State Machine [48].

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

Одним из способов создания предметно-ориентированных языков является расширение существующих, например, за счет введения в них автоматных конструкций [50, 51].

В работе [52] был предложен язык State (расширяющий язык C# [53]), который предназначен для реализации объектов с изменяющимся поведением. Однако, конструкции, вводимые в этом языке, невозможно реализовать эффективно, поскольку в нем вызов метода объекта влечет за собой вычисление набора предикатов.

программирования является встраивание в них поддержки паттернов проектирования. Например, в язык C# встроен паттерн Observer [5], широко используемый, например, для реализации графического интерфейса пользователя.

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

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

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

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

Отметим, что если в паттерне State [5] следующее состояние указывается текущим, то в паттерне State Machine это выполняется путем уведомления класса контекста о наступлении события.

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

По сравнению с языком Java в язык State Machine введены дополнительные конструкции, позволяющие описывать объекты с варьирующимся поведением в терминах автоматного программирования, определенных в работе [48]: автоматов, состояний и событий. Для описания автоматов и состояний в язык введены ключевые слова automaton и state соответственно, а для событий — ключевое слово events.

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

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

Также как в паттерне State Machine, в предлагаемом языке состояние может делегировать дальнейшее выполнение действия автомату. При этом для ссылки на автомат используется ключевое слово automaton (также как и при описании автоматов).

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

Описание автоматов и состояний на языке State Machine помещаются в файлы с расширением Авторами разработан препроцессор, преобразующий код, написанный на предлагаемом языке, в код на языке Java (в файлы с расширением.java). При этом новые синтаксические конструкции преобразуются в соответствии с паттерном State Machine.

Препроцессор генерирует код, содержащий параметры типа (generics) [57], что позволяет осуществлять проверку типов во время компиляции.

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

4.2. Пример использования языка State Machine В данном разделе особенности новых синтаксических конструкций языка State Machine рассматриваются на примере проектирования и реализации класса Connection, описанного в работе [48]. Приведем его краткое описание.

4.2.1. Описание примера Требуется спроектировать класс Connection, представляющий сетевое соединение, имеющее два управляющих состояния: соединено и разъединено. Переход между ними происходит или при возникновении ошибки или посредством вызовов методов установить соединение (connect) и разорвать соединение (disconnect). В состоянии соединено может производиться получение (метод receive) и отправка (метод send) данных. В случае возникновения ошибки при передаче данных генерируется исключительная ситуация (IOException) и сетевое соединение переходит в состояние разъединено, в котором прием и отправка данных невозможны.

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

Интерфейс, который требуется реализовать в классе Connection, выглядит следующим образом.

package connection;

import java.io.IOException;

public interface IConnection { public void connect() throws IOException;

public void disconnect() throws IOException;

public int receive() throws IOException;

public void send(int value) throws IOException;

В работе [48] для реализации состояний соединено и разъединено, DisconnectedState соответственно. Состояния уведомляют контекст о событиях: класс ConnectedState — о событиях DISCONNECT и ERROR, а класс DisconctedState — о событиях CONNECT и ERROR.

Граф переходов для рассматриваемого примера представлен на рис. 29.

4.2.2. Описание состояний Для описания состояния используется ключевое слово state.

Приведем код состояния ConnectedState на языке State Machine:

package connection;

import java.io.IOException;

public state ConnectedState implements IConnection events DISCONNECT, ERROR { protected final Socket socket;

public ConnectedState(Socket socket) { this.socket = socket;

public void connect() throws IOException { public void disconnect() throws IOException { socket.disconnect();

castEvent(DISCONNECT);

public int receive() throws IOException { return socket.receive();

} catch (IOException e) { castEvent(ERROR);

public void send(int value) throws IOException { socket.send(value);

} catch (IOException e) { При описании состояния указан интерфейс автомата (IConnection) и список событий, которые это состояние может сгенерировать (ERROR, DISCONNECT). Также как в паттерне State Machine, контекст уведомляется о наступлении события вызовом метода castEvent. За исключением этого, состояния описываются аналогично классу на языке Java.

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

Для реализации автомата Connection, необходимо также описать состояние DisconnectedState:

package connection;

import java.io.IOException;

public state DisconnectedState implements IConnection protected final Socket socket;

public DisconnectedState(Socket socket) { public void connect() throws IOException { public void disconnect() throws IOException { public int receive() throws IOException { throw new IOException("Connection is closed");

public void send(int value) throws IOException { throw new IOException("Connection is closed");

4.2.3. Описание автомата В языке State Machine автомат предназначен для определения набора состояний и переходов.

Для описания автомата применяется ключевое слово automaton.

Приведем код на предлагаемом языке для автомата Connection, реализующий граф переходов (рис. 29):

package connection;

public automaton Connection implements IConnection { state DisconnectedState disconnected(CONNECT -> state ConnectedState connected(ERROR -> public Connection(Socket socket) { disconnected @= new DisconnectedState(socket);

connected @= new ConnectedState(socket);

Обратим внимание, что класс автомата должен реализовывать ровно один интерфейс, который и считается интерфейсом автомата. В данном примере — это интерфейс IConnection.

ConnectedState и DisconnectedState соответственно) описываются при помощи ключевого слова state. Первое из состояний, описанных в автомате, является стартовым. В данном примере это состояние disconnected.

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

Например, для состояния connected переходами являются DISCONNECT означает, что при поступлении события DISCONNECT в состоянии connected автомат переходит в состояние disconnected.

производится создание объектов состояний. Отметим, что состояния, Инициализация объектов состояний производится при помощи нового оператора @=, специально введенного для этой цели в язык State Machine.

ConnectedState(socket) connected новым объектом класса ConnectedState.

За исключением этого, автомат описывается аналогично классу на языке Java.

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

4.2.4. Компиляция примера Для генерации Java-кода из файлов с расширением.sm необходимо event_mapping Отметим, что интерфейс автомата должен совпадать у автомата и всех состояний, которые он использует. Это семантическое правило, поэтому оно не может быть выражено грамматикой.

Для инициализации состояний в конструкторе автомата применяется оператор @=. Слева от него указывается имя состояния, а справа — объект, реализующий это состояние. Тип указанного объекта должен в точности совпадать с типом, указанным при описании автомата.

проинициализированы. При этом каждое — не более одного раза (как если бы они были обыкновенными переменными, описанными с модификатором final).

Использование оператора @= вне конструктора является ошибкой.

4.4. Повторное использование Одним из преимуществ объектно-ориентированного программирования является возможность повторного использования кода. Эта возможность также поддерживается и в предлагаемом языке.

4.4.1. Допустимые способы повторного использования В Java объектно-ориентированном программировании интерфейс объекта представляет собой некоторый контракт [59]. При этом возможно наследование класса, основываясь только на его контракте. Наследование от автомата как класса допустимо, но для расширения его поведения в наследнике необходимо изменять набор состояний и функцию переходов.

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

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

Наследование состояний.

Использование классов состояний в нескольких автоматах.

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

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

4.4.2. Описание примеров Connection.

Автомат PushBackConnection предоставляет возможность возврата данных в объект соединения и их последующего считывания. Интерфейс IConnection:

package push_back_connection;

import connection.IConnection;

import java.io.IOException;

public interface IPushBackConnection extends IConnection void pushBack(int value) throws IOException;

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

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

Рис. 37. Граф переходов автомата ResumableConnection 4.4.3. Наследование состояний PushBackDisconnectedState, ConnectedState и DisconnectedState соответственно. Это позволяет обеспечить повторное использование кода состояний.

Приведем код состояния PushBackConnectedState:

package push_back_connection;

import connection.*;

import java.util.Stack;

import java.io.IOException;

public state PushBackConnectedState extends ConnectedState implements IPushBackConnection { public PushBackConnectedState(Socket socket) { public int receive() throws IOException { return stack.empty() ? super.receive() : stack.pop();

public void pushBack(int value) { Состояние PushBackDisconnectedState реализуется аналогично:

package push_back_connection;

import connection.*;

import java.io.IOException;

public state PushBackDisconnectedState extends DisconnectedState implements IPushBackConnection public PushBackDisconnectedState(Socket socket) { public void pushBack(int value) throws IOException { throw new IOException("Connection is closed Автомат PushBackConnection не наследует автомат Connection.

Повторное использование кода достигается за счет применения наследников состояний ConnectedState и DisconnectedState.

package push_back_connection;

import connection.Socket;

public automaton PushBackConnection implements IPushBackConnection PushBackConnectedState connected { PushBackDisconnectedState disconnected { public PushBackConnection(Socket socket) { connected @= new PushBackConnectedState(socket);

4.4.4. Использование одного состояния в различных автоматах Для реализации автомата ResumableConnection необходимо поведение в состоянии ошибка. В автомате также будут использованы состояния ConnectedState и DisconnectedState, разработанные для автомата Connection.

Приведем код состояния ErrorState:

package resumable_connection;

import connection.*;

import java.io.IOException;

public state ErrorState implements IConnection events

CONNECT, DISCONNECT {

protected final Socket socket;

public ErrorState(Socket socket) { public void connect() throws IOException { socket.connect();

castEvent(CONNECT);

public void disconnect() throws IOException { castEvent(DISCONNECT);

public int receive() throws IOException { return automaton.receive();

public void send(int value) throws IOException { automaton.send(value);

Теперь можно определить автомат ResumableConnection:

package resumable_connection;

import connection.*;

public automaton ResumableConnection implements state DisconnectedState disconnected(CONNECT -> state ConnectedState connected(DISCONNECT -> state ErrorState error(DISCONNECT -> disconnected, private ResumableConnection() { connected @= new ConnectedState(socket);

disconnected @= new DisconnectedState(socket);

Из приведенных примеров следует, что состояния могут быть использованы повторно.

4.5. Реализация препроцессора Для реализации препроцессора были использованы инструменты создания компиляторов JLex и Cup, описанные в работе [55], которые распространяются по лицензии open source license [60]. Первый из них предназначен для построения лексических анализаторов, а второй — синтаксических [43].

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

http://is.ifmo.ru, раздел Статьи. Для работы препроцессора необходимо также установить инструменты создания компиляторов JLex и Cup, доступные по адресу [61].

4.5.1. Генерация Java-классов по описанию состояний Каждое состояние, описанное на языке State Machine, преобразуется в одноименный класс на языке Java. При этом все методы и их реализация переходят в генерируемый класс.

В случае если одно состояние расширяет другое, то генерируемый класс будет расширять соответствующий ему Java-класс. В противном AutomatonBase.StateBase, ru.ifmo.is.sml.runtime.

Указанный класс является базовым для всех классов состояний. В нем определено поле automaton, позволяющее вызывать методы автомата, в котором содержится данный экземпляр состояния. Отметим, что в языке StateMachine automaton является ключевым словом. Таким образом, конфликтов с полями, определенными пользователем, не возникает.

В классе StateBase также реализован метод castEvent, который состояния вызывают для уведомления автомата о наступлении события. Для AutomatonBase.StateBase.Event.

Рассмотрим код, сгенерированный препроцессором для состояния ConnectedState.

сгенерированного кода и вставка комментариев выполнены вручную:

import java.io.IOException;

public class ConnectedState // Базовый класс, для всех состояний extends ru.ifmo.is.language.AutomatonBase.StateBase implements IConnection { // События преобразуются в набор статических переменных public final static Event DISCONNECT = new Event(ConnectedState.class, "DISCONNECT", 0);

public final static Event ERROR = new Event(ConnectedState.class, "ERROR", 1);

// В остальном -- без изменений protected final Socket socket;

public ConnectedState(Socket socket) { this.socket = socket;