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

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

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

Например, фирма General Electrics создала средство State Logic [41].

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

Для описания поведения реактивных систем Д. Харелом в работе [7], как было отмечено выше, предложено использовать диаграммы Statechart, являющихся расширением графа переходов. Эти диаграммы были использованы в качестве языка спецификации поведения реактивных систем в инструментальном средстве Statemate компании I-Logix [8, 20]. Эта компания также использует указанные диаграммы в составе более современного пакета для разработки встроенных систем на базе моделей Rhapsody [42]. Компания I-Logix вошла в состав компании Telelogic, которая, в свою очередь, входит в состав корпорации IBM.

Для моделирования реактивных систем фирмой Mathworks создано средство Stateflow [43], которое тесно интегрировано с такими известными пакетами, как MATLAB и Simulink.

Кроме подхода для построения реактивных систем, предложенного Д.

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

программирования микроконтроллеров [45]. Так, например, фирмой IAR Systems создано средство visualSTATE [24].

В работе [46] описана методология, названная Co-Deisgn. Она ориентирована на совместное проектирование аппаратной и программной частей встраиваемой системы с использованием конечных автоматов. Для верификации построенной системы используется библиотека VIS [47].

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

В классических алгоритмах автоматы используются крайне редко. Так в книге [50], среди многих алгоритмов приведен только один (поиск подстрок), в котором используются автоматы. Существуют и другие алгоритмы, в которых целесообразно применять автоматы, например, обход деревьев [51].

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

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

При переходе к объектно-ориентированному программированию исследовались различные подходы к совместному использованию автоматов и объектов [52]. Так, в частности, одним из подходов к реализации автоматов, является создание библиотек, реализующих набор базовых классов. Наследуясь от этих классов, программист пишет программу в «автоматном» стиле. К таким библиотекам можно отнести, например, Werken Blissed [53] и boost::fsm [54], первая из которых предназначена для создания программ на языке Java, а вторая – на языке С++. Особенность применения таких библиотек состоит в том, что описание структуры автомата выполняется на целевом языке программирования.

возможность описывать автомат в текстовом конфигурационном файле, который затем преобразуется в код на целевом языке программирования. К таким библиотеками относятся, например, Ninni FSM Generator [55], Finite State Machine generating software [56], FSM [57], The State Machine Compiler [58], CHSM [59].

Форматы текстового описания варьируются: от таблицы переходов автомата Мура [55, 56, 58] до XML-описания смешанного автомата [57].

The State Machine Compiler [58] по текстовому описанию графа переходов генерирует код на языках Java, C++, C#, VB.Net, реализующий паттерн State [27]. Проверку корректности заданного автомата данная библиотека не производит. Библиотека имеет возможность генерировать графическое представление автомата по заданному описанию, но данную функциональность нельзя считать обоснованной, так как при моделировании поведения системы графическое представление автомата должно является первичным.

При использовании библиотеки [56] на первом этапе текстовое описание автомата преобразуется в бинарное представление, а затем оно передается интерпретатору. В работе [59] предлагается описывать граф переходов автомата непосредственно в коде программы на языке С/C++, используя специальные макросы.

При создании приложений с графическим интерфейсом пользователя в последнее время все шире используется паттерн Model-View-Controller [27].

Его основная идея заключается в разделении приложения на модель данных, контроллер и представление данных. Модель данных уведомляет контроллер об изменении данных. При этом контроллер обновляет представление данных. В этом случае оказывается удобным реализовывать контроллер с помощью конечного автомата, так как контроллер выполняет обновление представления данных на основе их текущего состояния – анализируя, например, какое окно в данный момент открыто. На сайте [60] приведен список программных продуктов, реализующих описанный подход. Среди них выделим ViewControl [22] компании StateSoft. Этот продукт ориентирован на разработку Интернет-приложений на основе платформы J2EE [62] и позволяет создавать графы переходов, используя UML-нотацию диаграммы состояний и собственный графический редактор.

В заключение раздела отметим, что в начале 90-х годов в Мичиганском университете Ю. Гуревичем [63] разработана теория машин абстрактных состояний (ASM –

Abstract

State Machine). В дальнейшем под его руководством в компании Microsoft на основе этой теории был разработан язык исполняемых спецификаций AsmL (Abstract State Machine Language) [64], который в настоящее время используется только для верификации.

1.6. Программные продукты для графического моделирования Функцию переходов конечного автомата можно задавать различными способами. Наиболее популярными являются табличное представление и представление в виде графа переходов [65].

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

Более наглядным и удобным является описание переходов конечного автомата в виде графа переходов. Существует множество нотаций для представления графа переходов автомата. Наиболее популярной сегодня является нотация, используемая в UML-диаграмме состояний, которая является модифицированной версией Statechart [7].

На сайте [67] приведен список компаний и их продуктов, предназначенных для создания моделей на языке UML. Кроме продуктов, указанных на этом сайте, следует отметить также UML-редактор Real [68].

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

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

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

поведенческих UML-диаграмм с помощью генерации кода для них или с помощью их интерпретации привело к появлению нового направления, реализующих идеи этого направления отметим инструмент Nucleus UML Suite [69] компании Accelerated Technology и инструмент iUML [90] компании Kennedy Carter.

Кроме вопросов построения кода по модели или непосредственного ее исполнения, также актуальным является автоматическая проверка формальной корректности модели. Спецификация UML [70] содержит описание ограничений, которым должна удовлетворять корректная модель.

Такие ограничения описаны и для диаграммы состояний.

В указанной выше спецификации ограничения описываются с помощью языка объектных ограничений (Object Constraint Language).

Предполагается, что UML-редакторы должны проверять правильность построения диаграмм с учетом этих ограничений. Существует ряд программных продуктов, ориентированных на проверку OCL ограничений [70, 72]. Однако в работе [73] показано, что некоторые из ограничений, описанных в спецификации на язык, противоречат друг другу. В этой работе также показано на примере популярных UML-редакторов, что очень мало ограничений реально проверяется. Отметим, что спецификация UML допускает присутствие в диаграммах состояний противоречивых переходов и неполноту множества исходящих из состояния переходов.

формального описания операционной семантики для диаграмм состояний – правил их исполнения. Устранению данного недостатка посвящены такие работы как [74–76] и стандарт ITU-T Recommendation Z.109 [77]. В работе [74] предлагается объединить язык UML c языком SDL [78], так как для последнего формально определена операционная семантика.

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

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

Говоря в дальнейшем о явном выделении состояний будем иметь ввиду выделение именно управляющих состояний.

В работе [79] в рамках SWITCH-технологии предложен метод проектирования событийных объектно-ориентированных программ с явным выделением состояний. Особенность этого подхода состоит в том, что поведение объектов описывается с помощью конечных автоматов, представляемых в форме графов переходов с нотацией, предложенной в работе [44]. SWITCH-технология, как она описана в работе [40], несмотря на то, что она не содержит визуальных средств моделирования и библиотек, предлагает методологию перехода от поведенческой модели к коду на целевом языке.

Инструментальным средством для поддержки SWITCH-технологии является программа Visio2Switch [80], которая позволяет преобразовывать графы переходов, созданные в Microsoft Visio, в код на языке C.

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

Редактор Finite State Machine Editor [81] использует ряд идей из SWITCH-технологии и реализует редактор для графа переходов конечного автомата. Граф переходов может быть преобразован в код на языках C++ или Python.

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

• использование собственной нотации для представления графа • использование только компилятивного подхода;

• отсутствие возможности создания вложенных состояний или • отсутствие вложенных автоматов;

• отсутствие автоматической проверки корректности графа В среде разработки Флора [82] было предложено строить объектноориентированные программы путем «размещения» объектов из предварительно построенных библиотек на дереве. При этом вручную писалась только та часть программы, которая реализовала ее логику. После знакомства с автоматным программированием [40], в это средство была добавлена возможность описания логики с помощью графов переходов автоматов, которые автоматически исполняются.

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

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

Инструментальное средство XJTek AnyState [21] содержит редактор графов переходов и редактор исходного Java-кода. При изменении графа переходов выполняется его синхронизация с исходным кодом.

К особенностям данного продукта можно отнести:

• использование UML нотации диаграммы состояний;

• сохранение графической информации о диаграмме состояний (координаты состояний, цвета, тип шрифтов) прямо в исходном коде в виде комментариев;

• проверка выполнения некоторых ограничений. Информация о найденных ошибках записывается непосредственно в код;

Недостатком является неудобный графический редактор.

Инструмент IAR Systems visualSTATE [24] предназначен для создания приложений для микроконтроллеров. Этот продукт реализует:

• редактор графа переходов автомата в виде UML-диаграммы помощью собственного алгоритма;

интегрированного эмулятора различных микроконтроллеров;

• генерацию программного кода;

• автоматическое создание некоторой документации.

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

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

Инструментальное средство Telelogic Tau2 [83] является редактором диаграмм, поддерживающим стандарт UML версии 2 [84]. Средство позволяет проверять корректность построенной модели и запускать ее. При запуске существует возможность использовать встроенный отладчик.

описывать действия, выполняемые на переходах и в состояниях с помощью программирования, в которые входят C, C++ и Java.

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

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

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

Пакет Borland Together Architect [85] является одним из самых популярных и удобных инструментов для создания UML-моделей. В нем существует возможность генерации кода по диаграмме классов для языков Java, C++ и С# и обратная генерация – создание диаграммы классов по коду.

Обе эти возможности вместе называются round-trip [86], и в указанном инструменте они работают синхронно – при изменении кода сразу изменяется модель, а при изменении модели – код.

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

Недостатком Borland Together Architect является его ориентация, в первую очередь, на создание кода, а не на создание модели. Возможность синхронизации кода и диаграммы классов позиционируется создателями инструмента как удобное средство для рефакторинга [87] – улучшения существующего кода.

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

Одним из принципиально новых подходов, развивающихся в настоящее время, как отмечалось выше, является исполняемый UML [15, 16], который объединяет статические и динамические диаграммы. Одним из вариантов к реализации этого подхода является разработка виртуальной машины UML [88–90].

В проекте [89] модель программной системы предлагается строить следующим образом: структура программы моделируется с помощью UMLдиаграммы классов, а поведение – с помощью описания каждого метода каждого класса в виде UML-диаграммы последовательностей. Такой подход при сложной логике приложения крайне неудобен, так как приводит к очень громоздким моделям.

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

реализована в проекте Telelogic TAU2 [83]. Однако так как этот проект является закрытым, то весьма трудно выполнить анализ решений, принятых при его создании. Также закрытыми являются и инструментальные средства IBM Rational Rose и Borland Together.

В работе [40] был предложен метод проектирования программ с явным выделением состояний, названный «SWITCH-технология»

(http://ru.wikipedia.org/wiki/Switch-технология) или «автоматное программирование» (http://ru.wikipedia.org/wiki/Автоматное программирование). В дальнейшем этот метод был развит для событийных систем [44], а потом и для объектно-ориентированных [79].

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

SWITCH-технология определяет для каждого автомата два типа диаграмм (схема связей и граф переходов) и их операционную семантику.

При наличии нескольких автоматов предложено также строить схему их взаимодействия. Для каждого типа диаграмм предложена соответствующая нотация (http://is.ifmo.ru/?i0=science&i1=minvuz2).

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

2. Указанный недостаток устранен в SWITCH-технологии, которая вводит в процесс проектирования диаграмму связей автомата, для описания его интерфейса – входных и выходных воздействий. В UML-нотации такую диаграмму удобно представлять в виде диаграммы классов.

сформулировать задачи, решение которых актуально в настоящее время:

• разработка методологии моделирования поведения программных систем на основе совместного применения SWITCH-технологии и • разработка инструментального средства для поддержки SWITCHтехнологии с использованием нотации UML;

• обоснование выбора средств разработки, с помощью которых должны быть созданы инструментальные средства;

интерпретируемых исполняемых моделей поведения;

• реализация методов верификации создаваемых моделей;

• разработка средств отладки моделей в терминах автоматов.

ГЛАВА 2. РАЗРАБОТКА МЕТОДА ПОСТРОЕНИЯ

ОБЪЕКТНО-ОРИЕНТИРОВАННЫХ ПРОГРАММ С

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

Для проектирования программ с использованием этого языка предлагается следующий метод:

1. На основе анализа предметной области в виде UML-диаграммы классов разрабатывается концептуальная модель системы, определяющая сущности и отношения между ними.

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

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

4. Схема связей, кроме задания интерфейсов автоматов, выполняет функцию, характерную для диаграммы классов – задает объектно-ориентированную структуру программы.

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

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

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

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

9. Каждый автомат имеет одно начальное и произвольное число конечных состояний.

10. Состояния на графе переходов могут быть простыми и сложными. Если в состояние вложено другое состояние, то оно называется сложным. В противном случае состояние простое.

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

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

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

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

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

Опишем синтаксис и операционную семантику предлагаемого графического языка.

Синтаксис созданного графического языка основан на UML-нотации.

Для текстовых языков программирования синтаксис обычно описывают с помощью формальных грамматик. UML является графическим языком и использует другой подход: описывается мета-модель, задающая множество правильных моделей, а затем определяются графические примитивы, соответствующие элементам мета-модели. Диаграммы строятся из указанных примитивов. Сама мета-модель UML описана с помощью высокоуровнего средства задания мета-моделей – MetaObject Facility (MOF) [92].

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

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

«EventProvider» – источник событий, «StateMachine» – автомат и «ControlledObject» – объект управления. Между такими классами возможно наличие направленных ассоциаций (дуга со стрелкой определенного вида) трех типов: от источника событий к автомату, от автомата к объекту управления и от автомата к автомату. Ассоциации должны быть помечены метками – идентификаторами.

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

Диаграмма состояний содержит следующие типы элементов:

начальное, нормальное и конечное состояния и переходы между ними.

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

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

Каждая диаграмма состояний содержит одно головное – сложное состояние, содержащее все остальные состояния.

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

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

e1[o1.x1 && o2.x3 > 10]/o1.z1, o2.z2, A2.e Здесь e1 – название события; o1, o2 – идентификаторы, помечающие ассоциации, которые ведут к первому и второму объектам управления; x1, x3 – методы объектов управления, возвращающие значение типа boolean или int; z1, z2 – методы объектов управления; A2 – идентификатор, помечающий ассоциацию, которая ведет к вызываемому автомату; e2 – событие, посылаемое вызываемому автомату A2. В квадратных скобках задается условие срабатывания перехода (охранное условие) – логическая формула.

В качестве события на переходе может быть использовано либо событие, определенное в одном из источников событий, связанных с данным автоматом, либо специальное событие «*», означающее любое событие.

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

Далее приведена LL(1) [48] грамматика для охранного условия:

целочисленной константе, терминал bool – булевской константе, а терминал rel – бинарному отношению (‘>’, ‘=’, ‘true] transitions [1. Вставьте карту#2. Ввод pin кода#e6#true] actions [o1.z2] states [(/AClient:9. Запрос денег/AServer) - (Чтение запроса);

(/AClient:5. Запрос Баланса/AServer) - (Авторизация); (/AClient:3. Авторизация/AServer) - (Чтение запроса); (/AClient) - (2. Ввод pin кода)] ] fsaState [T0_init] Model [ step [3] event [e4] guards [true->true] transitions [2. Ввод pin кода#3.

Авторизация#e4#true] actions [o2.z3] states [(/AClient:9. Запрос денег/AServer) - (Чтение запроса); (/AClient:5. Запрос Баланса/AServer) - (Авторизация); (/AClient:3. Авторизация/AServer) - (Чтение запроса); (/AClient) - (3. Авторизация)] ] fsaState [T0_init] Model [ step [4] event [e10] guards [true->true] transitions [3. Авторизация#4. Главное меню#e10#true] actions [o1.z4] states [(/AClient:9. Запрос денег/AServer) - (Чтение запроса);

(/AClient:5. Запрос Баланса/AServer) - (Авторизация); (/AClient:3. Авторизация/AServer) - (Чтение запроса); (/AClient) - (4. Главное меню)] ] fsaState [T0_init] Model [ step [5] event [e4] guards [true->true] transitions [4. Главное меню#8. Ввод суммы#e4#true] actions [o1.z8] states [(/AClient:9. Запрос денег/AServer) - (Чтение запроса);

(/AClient:5. Запрос Баланса/AServer) - (Авторизация); (/AClient:3. Авторизация/AServer) - (Чтение запроса); (/AClient) - (8. Ввод суммы)] ] fsaState [T0_init] Model [ step [6] event [e4] guards [true->true] transitions [8. Ввод суммы#9. Запрос денег#e4#true] actions [o2.z9] states [(/AClient:9. Запрос денег/AServer) - (Чтение запроса);

(/AClient:5. Запрос Баланса/AServer) - (Авторизация); (/AClient:3. Авторизация/AServer) - (Чтение запроса); (/AClient) - (9. Запрос денег)] ] fsaState [T0_init] Model [ step [7] event [e13] guards [true->true] transitions [9. Запрос денег#10. Выдача денег#e13#true] actions [o1.z10 states [(/AClient:9. Запрос денег/AServer) - (Чтение запроса);

(/AClient:5. Запрос Баланса/AServer) - (Авторизация); (/AClient:3. Авторизация/AServer) - (Чтение запроса); (/AClient) - (10. Выдача денег)] ] fsaState [bad$accept_all] Как видно, на седьмом шаге выполнилось действие o1.z10, хотя за всю историю не происходило события e23. Посмотрим, что привело к выдаче денег. На шаге 6 автомат AClient попал в состояние «9. Запрос денег», в которое вложен автомат AServer. При этом выполнилось действие o2.z3, которое, как изображено на рис. 12, означает «Запрос снятия денег».

Далее произошло событие e13, которое означает «Снятие денег прошло удачно». Возникает вопрос, каким образом произошел запрос снятия денег, если не происходило события e23. На самом деле, объект управления o (ServerQuery) предназначен для того, чтобы создавать события генератора событий p4 (ClientEventProvider). Объект управления o2 реализован так, что при вызове действия o2.z3 («Запрос снятия денег») генерируется событие e23 («Запрос снятия денег»).

Верификатор не учитывает логику внутри методов объектов управления. Поэтому он «не знает», что если выполнилось событие o2.z3, то обязательно произойдет событие e23. Для того чтобы все же верифицировать рассматриваемое свойство банкомата, добавим необходимую логику прямо в верифицируемое свойство, в следующем виде:

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

Итак, интересующая в данный момент логика объекта управления o заключается в том, что если было выполнено действие o2.z3, то будет сгенерировано событие e23. Запишем это в LTL-логике:

где X – LTL-оператор Next. Добавим теперь полученное условие в верифицируемую формулу, используя оператор следования, как было предложено выше:

Теперь запишем эту формулу на языке BIR:

LTL.temporalProperty ( Property.createObservableDictionary ( Property.createObservableKey(«server_request_money», AutomataModel.wasAction(model, «o2.z3»)), Property.createObservableKey(«money_requested», AutomataModel.wasEvent(model, «e23»)), Property.createObservableKey(«give_money», AutomataModel.wasAction(model, «o1.z10»)) LTL.negation(LTL.prop(«give_money»)), Верификация данной формулы оказывается удачной, что означает, что управляющая система банкомата действительно выполняет выдачу денег лишь после того, как она запросила наличие денег у сервера.

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

G ([произошла ошибка] F [карта будет возвращена]), где G – темпоральный оператор Globally, а F – темпоральный оператор Future. Событие «Ошибка при работе с сервером» кодируется в банкомате как e15, а возвращение карты – это действие o1.z13. Тогда формула принимает следующий вид:

На языке BIR формула выглядит следующим образом:

LTL.temporalProperty ( Property.createObservableDictionary ( Property.createObservableKey(«error», AutomataModel.wasEvent(model, «e15»)), Property.createObservableKey(«card_returned», AutomataModel.wasAction(model, «o1.z13»)) LTL.always (LTL.implication ( LTL.eventually (LTL.prop («card_returned»)) Верификация данной формулы успешна.

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

G F [пользователь получает деньги] Деньги выдаются при выполнении действия o1.z10, так что формула в этом случае примет следующий вид:

На языке BIR, соответственно, это записывается как LTL.temporalProperty ( Property.createObservableDictionary ( Property.createObservableKey(«give_money», LTL.always (LTL.eventually (LTL.prop В результате верификации этой формулы верификатор выдает следующий контрпример:

Model [ step [0] event [null] guards [null] transitions [null] actions [null] states [null] ] fsaState [T0_init] Model [ step [0] event [] guards [] transitions [] actions [] states [(/AClient:9. Запрос денег/AServer) - (Top); (/AClient:5. Запрос Баланса/AServer) - (Top); (/AClient:3.

Авторизация/AServer) - (Top); (/AClient) - (Top)] ] fsaState [T0_init] Model [ step [1] event [*] guards [] transitions [s1#1. Вставьте карту#*#true] actions [o1.z1] states [(/AClient:9. Запрос денег/AServer) - (Top); (/AClient:5. Запрос Баланса/AServer) - (Top);

(/AClient:3. Авторизация/AServer) - (Top); (/AClient) - (1. Вставьте карту)] ] fsaState [T0_init] Model [ step [2] event [e0] guards [true->true] transitions [1. Вставьте карту#s2#e0#true] actions [o1.z0] states [(/AClient:9. Запрос денег/AServer) - (Top); (/AClient:5. Запрос Баланса/AServer) - (Top); (/AClient:3. Авторизация/AServer) - (Top); (/AClient) - (s2)] ] fsaState [T0_init] Model [ step [2] event [e0] guards [true->true] transitions [1. Вставьте карту#s2#e0#true] actions [o1.z0] states [(/AClient:9. Запрос денег/AServer) - (Top); (/AClient:5. Запрос Баланса/AServer) - (Top); (/AClient:3. Авторизация/AServer) - (Top); (/AClient) - (s2)] ] fsaState [bad$accept_S2] Model [ step [2] event [e0] guards [true->true] transitions [1. Вставьте карту#s2#e0#true] actions [o1.z0] states [(/AClient:9. Запрос денег/AServer) - (Top); (/AClient:5. Запрос Баланса/AServer) - (Top); (/AClient:3. Авторизация/AServer) - (Top); (/AClient) - (s2)] ] fsaState [bad$accept_S2] В этом контрпримере автоматная система совершает лишь два шага:

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

Заметим, что в контрпримере строка с шагом «2» повторяется три раза. Это связано с тем, что после совершения второго шага автоматная система перестает работать, и шаги совершает лишь автомат Бюхи: из состояния T0_init в состояние bad$accept_S2.

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

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

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

ГЛАВА 4. ИНСТРУМЕНТАЛЬНОЕ СРЕДСТВО ДЛЯ

ПОДДЕРЖКИ АВТОМАТНОГО ПРОГРАММИРОВАНИЯ

UNIMOD

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

Рассматриваемое инструментальное средство поддерживает два основных типа обработки построенных диаграмм – интерпретацию и компиляцию.

Интерпретационный подход реализует виртуальную машину UML. На рис. 15 приведена структурная схема для интерпретационного подхода.

XML-описание UMLJava-byte code Интерпретатор XMLавтоматов Рис. 15. Структурная схема интерпретационного подхода интерпретационного подхода исходным кодом являются UML-модель (схемы связей и диаграммы состояний по SWITCH-технологии) и Java-код источников событий и объектов управления.

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

На рис. 16. приведена структурная схема для компилятивного подхода.

Шаблоны для языка Рис. 16. Структурная схема компилятивного подхода непосредственно преобразуется в код на целевом языке программирования, который впоследствии компилируется и запускается. Для преобразования в код применяются Velocity-шаблоны [101]. Это позволяет адаптировать компилятивный подход для языков программирования, отличных от языка Java, например для C++.

Указанный подход целесообразно применять для устройств с «классической» SWITCH-технологии.

4.3. Реализация редактора диаграмм на платформе Eclipse Редактор для создания указанных диаграмм является встраиваемым модулем (plug-in) для платформы Eclipse (http://www.eclipse.org). Эта платформа обладает рядом преимуществ перед такими продуктами, как, например, IntelliJ IDEA или Borland JBuilder, так как:

• является бесплатным продуктом с открытым исходным кодом;

редакторов – Graphical Editing Framework;

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

Для обеспечения процесса активной разработки программ на текстовых языках в перечисленных выше средствах разработки реализованы:

• подсветка семантических и синтаксических ошибок;

• завершение ввода и исправление ошибок ввода;

• форматирование и рефакторинг [87] кода;

• исполнение и отладка программы внутри среды разработки.

В английском языке эти возможности называются «code assist». При создании модуля для платформы Eclipse указанные возможности были реализованы для редактирования диаграмм.

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

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

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

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

Рис. 17. Предлагаемые варианты исправления ошибки на диаграмме Форматирование кода облегчает его чтение. Многие текстовые редакторы позволяют автоматически форматировать код.

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

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

• текст программы компилируется в код, исполняемый операционной системой (Pascal, C++);

• текст программы компилируется в код, исполняемый виртуальной машиной (Java, C#);

• текст программы непосредственно исполняется интерпретатором (JavaScript, Perl).

Подобные решения применяются и для предлагаемого графического языка. Основными вариантами исполнения являются второй и третий.

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

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

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

На рис. 18 показана архитектура графического отладчика.

При запуске модели в режиме отладки, внутри платформы Eclipse должен создаваться компонент UniMod Server-side Debugger, а в целевой виртуальной Java машине (JVM) должен создаваться компонент UniMod Client-side Debugger. Эти компоненты взаимодействуют, используя протокол UniMod Debugger Protocol. Для поддержки возможности отладки текстового Java кода объектов управления между платформой Eclipse и целевой JVM также устанавливается соединения посредством стандартного протокола Java Debug Wire Protocol [103].

регламент взаимодействия между указанными выше компонентами:

1. При старте компонента UniMod Client-side Debugger приостанавливает исполнение модели, создает серверный сокет [104] и ожидает присоединения к нему компонента UniMod 2. После установления соединения эта компонента ожидает получения списка точек останова, возможно пустого.

3. После получения списка точек останова компонента UniMod Client-side Debugger регистрирует их и возобновляет исполнение модели.

4. Каждый шаг исполнения модели контролируется и при достижении точки останова компонент UniMod Clientside Debugger приостанавливает исполнение модели, а также информирует об этом событии компонент UniMod Server-side Debugger.

получении события о достижении точки останова, графически выделяет соответствующий элемент на диаграмме состояний и ожидает команды от пользователя. При этом пользователь имеет возможность, как возобновить исполнение модели до следующей точки останова, так и выполнить только один шаг исполнения модели. О выбранном пользователем действии извещается UniMod Client-side Debugger.

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

7. Также в процессе отладочной сессии пользователь может устанавливать новые точки останова и удалять существующие.

Об этих действиях извещается компонент UniMod Clientside Debugger.

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

Отметим, что так как серверный сокет создает компонент UniMod Client-side Debugger, то с точки зрения архитектуры клиент-сервер, он и будет являться сервером данной системы, а компонент UniMod Server-side Debugger – клиентом.

При этом компонент UniMod Server-side Debugger должен посылать команды, описанные в табл. 1.

Таблица 1. Команды, посылаемые компонентом UniMod Server-side Debugger событиях, описанных в табл. 2.

Таблица 2. События, формируемые компонентом UniMod Clientside Debugger SUSPENDED_ON_BREAKPOINT Исполнение модели приостановлено CANT_UPDATE_MODEL Невозможно обновить модель Ниже приведены возможные типы точек останова:

• достижение состояния на диаграмме состояний;

• выполнение перехода между состояниями;

• получение значения входной переменной при вычислении охранного условия на переходе;

• вызов выходного воздействия на переходе;

• вызов выходного воздействия по входу в состояние;

• вызов вложенного автомата.

На рис. 19 показана статическая модель отладчика. Классы слева описывают структуру компонента UniMod Client-side Debugger, а классы справа – UniMod Server-side Debugger.

Классы app.AppConnector и debugger.DebuggerConnector реализуют сетевое взаимодействие.

Классы app.BreakpointManager и debugger.BreakpointManager управляют точками останова.

Класс app.ThreadManager приостанавливает и возобновляет поток выполнения в отлаживаемой модели.

Класс app.EvetProcessorEventProvider следит за процессом обработки событий в отлаживаемой модели.

Класс app.ModelManager сохраняет новую версию модели до того момента, когда на ее можно будет заменить старую версию.

пользователем системы.

Классы app.AppDebugger и debugger.Debugger композируют остальные классы системы и их поведение далее будет описано и реализовано в виде системы взаимодействующих автоматов.

На рис. 20 показана модель сообщений, которыми обмениваются клиент и сервер. Класс EventMessage представляет сообщения, которые Debugger. Внутри этих классов показаны константы, Server-side которые соответствуют типам сообщений, определенным в таблицах 1 и 2.

Класс Position определяет точку останова в отлаживаемой модели.

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

Класс CommandMessage также имеет ассоциацию с классом Model для пересылки в отлаживаемую модель новой версии модели.

Интерфейс MessageCoder определяет методы для кодирования сообщения в массив байт для пересылке по протоколу TCP и для декодирования сообщения из массива байт.

Динамическая модель отладчика декомпозирована на две модели – серверную (реализует поведение компонента UniMod Client-side Debugger) и клиентскую (реализует поведение компонента UniMod Server-side Debugger).

На рис. 21 представлена схема связей автоматов серверной части системы. При этом классу статической модели app.AppDebugger соответствуют три автомата app, A2 и A3.

Класс app.AppConnеctor на рис. 21 играет роль и источника событий и объекта управления. Это вызвано тем, что при получении сообщения от клиента app.AppConnеctor извещает об этом автомат с помощью посылки события. При необходимости отправки сообщения клиенту автомат вызывает методы объекта управления app.AppConnеctor.

На рис. 22 представлена диаграмма переходов автомата app. Этот автомат реализует поведение серверной части системы в целом.

На рис. 23 представлена диаграмма переходов автомата A2, отвечающего за управление точками останова.

На рис. 24 представлена диаграмма переходов автомата A3, управляющего потоками выполнения.

Рис. 21. Схема связей автоматов серверной части системы Рис. 22 Диаграмма переходов автомата app Рис.24. Диаграмма переходов автомата A На рис. 25 представлена схема связей автоматов клиентской части системы. Классу статической модели debugger.Debugger соответствуют три автомата debugger, A2 и A3.

Класс debugger.DebuggerConnеctor на рис. 25, также как класс app.AppConnector, играет роль и источника событий и объекта управления.

Класс debugger.UManager также является и источником событий и объектом управления, так как он, с одной стороны, поставляет автомату события от пользователя, а с другой – позволяет автомату управлять пользовательским интерфейсом отладчика.

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

На рис. 26 представлена диаграмма переходов автомата debugger.

Этот автомат реализует поведение клиентской части системы в целом.

На рис. 27 представлена диаграмма переходов автомата A2, отвечающего за управление точками останова.

На рис. 28 представлена диаграмма переходов автомата A3, управляющего потоками выполнения.

Рис. 25. Схема связей автоматов клиентской части системы Рис. 26. Диаграмма переходов автомата debugger Рис. 27. Диаграмма переходов автомата A Рис. 28. Диаграмма переходов автомата A По автоматной модели системы сгенерировано ее XML-описание, которое исполняется интерпретатором. Источники событий и объекты управления реализованы вручную.

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

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

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

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

РАБОТЫ В ПРАКТИКУ ПРОЕКТИРОВАНИЯ

• при разработке этого средства;

• в учебном процессе при выполнении студенческих курсовых проектов на кафедре «Компьютерных технологий» в СПбГУ ИТМО (http://is.ifmo.ru в разделе UniMod-проекты);

• в компании eVelopers (http://www.evelopers.com) для разработки интернет-приложений и мобильных приложений;

• в компании JetBrains (http://www.jetbrains.com) при разработке системы мета-программирования Meta Programming System 5.1. Создание системы автоматического завершения ввода В рамках создания очередной версии пакета UniMod встала задача реализации системы автоматического завершения ввода при редактировании условий на переходах на UML-диаграмме состояний.

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

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

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

Если поданная на вход строка является префиксом возвращать множество строк C ( ) = { i }i =1..n, любая из которых 2. Если поданная на вход строка не является префиксом символами или с помощью удаления лишних символов трансформировать строку в правильный префикс предложения языка. Число дополнений и удалений должно быть как можно 5.1.1. Описание предлагаемой технологии Если исходный язык L задан формальной порождающей грамматикой, то для построения такой системы необходимо использовать методы проектирования компиляторов [48]. Известны инструменты для автоматического создания компиляторов по заданной грамматике (http://www.kulichki.net/kit/tools/java.html).

На рис. 30 приведена обобщенная структура компилятора.

В проекте UniMod трансляция выражений на переходах выполняется с помощью, так называемого, «компилятора компиляторов» ANTRL [95]. Он по заданной LL(k)-грамматике строит код на языке Java, реализующий лексический анализатор и рекурсивный нисходящий синтаксический использован и как распознаватель принадлежности выражения заданному синтаксическое дерево. Данный анализатор не может быть использован для построения системы автоматического завершения ввода, так как в случае подачи ему на вход префикса для выражения на заданном языке вместо законченного выражения, он выдает ошибку.

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

Таблица разбора представляет собой двумерный массив M [A, a], где A – нетерминал, а a – терминал (лексема) или символ конца потока $. В ячейках таблицы записываются правила грамматики, с помощью которых заменяются нетерминалы на вершине стека, а пустые ячейки таблицы соответствуют ошибкам. Подробно работа такого анализатора описана в работе [48].

При подаче на вход описанному выше анализатору незавершенной строки без символа конца потока, анализатор остановится, имея какой-то нетерминал на вершине стека. В этом случае множество терминалов C ( ), ожидаемых вслед за обработанной строкой, может быть определено как { : M [T, ] }, где T – нетерминал на вершине стека после остановки анализатора.

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

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

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

Технология основывается на том, чтобы для заданной LL(1)грамматики построить конечный автомат типа Мили, который будет являться синтаксическим анализатором. Автомат должен реагировать на события, которые поставляет ему лексический анализатор. Каждому событию соответствует терминал. В работах [48, 106] приведено описание подхода для создания нисходящего синтаксического анализатора на основе диаграмм переходов. При этом предлагается записывать по одной диаграмме для каждого правила вывода грамматики. Описываемая в настоящей работе технология предлагает сворачивать все диаграммы в одну, при необходимости удаляя рекурсию с помощью метода, описанного в работе [107]. Такой подход позволяет избавиться от упоминания нетерминалов на диаграммах переходов и, следовательно, разорвать семантическую связь с исходной грамматикой. Такой разрыв позволит описывать язык только с помощью диаграммы переходов и автоматически получать реализацию распознавателя для данного языка.

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

5.1.2. Построение диаграммы переходов синтаксического Пусть LL(1)-грамматика для нашего примера задана следующим множеством правил вывода:

целочисленной константе, терминал bool – булевской константе, а терминал rel – бинарному отношению (‘>’, ‘=’, ‘HandleL(CAutoAnswererModelEngine::E23));

iModelEngine->HandleL(CAutoAnswererModelEngine::E24);

Для объектов управления методы, реализующие входные и выходные переменные, программируются вручную. Так для объекта управления CMessageList выходная переменная z3 имеет вид:

void CMessageList::Z3L(TStateMachineContext& aContext) if (aContext.iMessageFileIndex >= 0 && aContext.iMessageFileIndex < iList->Count()) StringLoader::Load(fileName, R_AUTOANSWERING_MSG_DIR_PATH);

fileName.Append(iList->At(aContext.iMessageFileIndex).iName);

BaflUtils::DeleteFile(iFs, fileName);

iList->Delete(aContext.iMessageFileIndex);

CreateDefaultNameL();

Входная переменная x1 для того же объекта управления реализована следующим образом:

TBool CMessageList::X1L(TStateMachineContext& aContext) TInt numberMessages(iList->Count());

for (TInt i = 0; i < numberMessages; i++) const TMessage& message = iList->At(i);

if(message.iName.Compare(*aContext.iFileName) == 0) return ETrue;

Код, сгенерированный для метода TransiteOnEventL автомата A2, реализующий переход из текущего активного состояния, в зависимости от события и значений входных переменных:

TA2::EState TA2::TransiteOnEventL(CAutoAnswererModelEngine::EEvent aEvent, TStateMachineContext& aContext) TA2::EState targetState = UNKNOWN_STATE;

for (TA2::EState sourceState = iState; targetState == UNKNOWN_STATE && sourceState != TOP;

sourceState = GetSuperstate(sourceState)) switch (sourceState) case CAutoAnswererModelEngine::EEvent::E21:

case CAutoAnswererModelEngine::EEvent::E4:

case CAutoAnswererModelEngine::EEvent::E20:

case CAutoAnswererModelEngine::EEvent::E4:

case ENTERING_FILE_NAME:

case CAutoAnswererModelEngine::EEvent::E12:

case CAutoAnswererModelEngine::EEvent::E13:

case CAutoAnswererModelEngine::EEvent::E12:

// Look for default transition for (TA2::EState sourceState = iState; targetState == UNKNOWN_STATE && sourceState != TOP;

sourceState = GetSuperstate(sourceState)) switch (sourceState) case ENTERING_FILE_NAME:

// If no transition was found stay in current state return targetState != UNKNOWN_STATE ? targetState : iState;

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

iMessageList = CMessageList::NewL(Document().Fs());

iContactEngine = CPbkContactEngine::NewL();

iActiveView = CAutoAnsweringViewActive::NewL();

AddViewL(iActiveView); // Transfer ownership to base class iMainView = CAutoAnsweringViewMain::NewL();

AddViewL(iMainView); // Transfer ownership to base class iRecordView = CAutoAnsweringViewRecord::NewL();

AddViewL(iRecordView); // Transfer ownership to base class iSelectMsgView = CAutoAnsweringViewSelectMsg::NewL(*iMessageList);

AddViewL(iSelectMsgView); // Transfer ownership to base class iSelectUserView = CAutoAnsweringViewSelectUser::NewL(*iContactEngine);

AddViewL(iSelectUserView); // Transfer ownership to base class iViewView = CAutoAnsweringViewView::NewL(Document().ContactMessageMap(), *iContactEngine);

AddViewL(iViewView); // Transfer ownership to base class iCallWatcher = CCallWatcher::NewL(*iLogger);

iMessageRecorder = CMessageRecorder::NewL(Document().Fs());

iMessagePlayer = CMessagePlayer::NewL(Document().Fs(), iCallWatcher->Phone(), *iLogger);

iMessagePlayer->SetUseLoudSpeaker(ETrue);

iLineMessagePlayer = CMessagePlayer::NewL(Document().Fs(), iCallWatcher->Phone(), *iLogger);

iLineMessagePlayer->SetUseLoudSpeaker(EFalse);

iCurrentCaller = CCurrentCaller::NewL(*iContactEngine);

iModelEngine = CAutoAnswererModelEngine::NewL( this, iMessageList, iMessagePlayer, iMessageRecorder, iCallWatcher, iCurrentCaller);

iMessagePlayer->SetModelEngine(iModelEngine);

iMessageRecorder->SetModelEngine(iModelEngine);

iCallWatcher->SetModelEngine(iModelEngine);

// ToDo find out what should do LineMessagePlayer iLineMessagePlayer->SetModelEngine(iModelEngine);

iCurrentCaller->SetModelEngine(iModelEngine);

Программа, построенная на основе изложенного подхода, может быть загружена с сайта http://www.evelopers.com.

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

Для расширения функциональных возможностей инструментального средства UniMod был разработан прототип текстового языка автоматного программирования с помощью системы метапрограммирования JetBrains Meta Programming System (MPS) [110, 111], которая позволяет быстро создавать проблемно-ориентированные языки (Domain Specific Language — DSL) [111, 112]. Для задания языка в системе MPS требуется разработать:

• структуру абстрактного синтаксического дерева (АСД) [48] для разрабатываемого языка. Узлам АСД могут соответствовать такие понятия как «объявление класса», «вызов метода», «операция • модель текстового редактора для каждого типа узла АСД. Задание синтаксиса для этого узла. При этом, если для традиционных текстовых языков программирования создание удобного редактора – отдельная сложная задача, то для языков, созданных с помощью средства MPS, редакторы являются частью языка. Эти редакторы поддерживают автоматическое завершение ввода текста и проверку корректности программы;

• модель ограничений на экземпляры АСД;

• модель системы типов [113] для языка;

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

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

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

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

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

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

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

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

На рис. 59 слева показан пример текстовой автоматной программы на разработанном языке программирования первого типа, распознающей цепочки символов вида a*b*c*. Автоматически построенная диаграмма состояний изображена на рис.59 справа.

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

1. При разработки системы автоматического завершения ввода в использовано само это средство – применен так называемый «метод раскрутки».

2. Разработанные методы и инструментальное средство успешно «Автоматное программирование» на кафедре «Компьютерных технологий» СПбГУ ИТМО.

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

4. Разработан прототип текстового языка автоматного программирования в среде быстрой разработки языков MPS. В рамках работ по созданию следующей версии инструментального средства UniMod2 в него будет включена реализация этого языка.

ЗАКЛЮЧЕНИЕ

Он позволяет:

• сократить объем ручного программирования;

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

• использовать диаграммы классов и графы переходов в составе • формально и наглядно описывать логику поведения программы и модифицировать ее, изменяя только графы переходов;

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

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

http://unimod.sourceforge.net. За все время существования проекта было произведено более 45000 скачиваний.

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

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

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

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

ИСТОЧНИКИ

М.: Вильямс, 2004.

примерами приложений на С++. СПб.: Невский диалект, 2001.

Ларман К. Применение UML и шаблонов проектирования. М.: Вильямс, Коуд П., Норт Д., Мейфилд М. Объектные модели. Стратегии, шаблоны и приложения. М.: Лори, 1999.