OPS: Automata

Материал из Вики ИТ мехмата ЮФУ
Перейти к: навигация, поиск

Содержание

Введение

Автоматное программирование (Automata-based Programming, или программирование от состояний) основано на использовании конечных автоматов, описывающих поведение программ.

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

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

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

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

Критерий применимости автоматного подхода лучше всего выражается через понятие «сложное поведение»[1]. Неформально можно сказать, что сущность (объект, подсистема) обладает сложным поведением, если в качестве реакции на некоторое входное воздействие она может осуществить одно из нескольких выходных воздействий. При этом существенно, что выбор конкретного выходного воздействия может зависеть не только от входного воздействия, но и от предыстории. В программных и программно-аппаратных вычислительных системах сущности со сложным поведением встречаются очень часто. Таким свойством обладают устройства управления, сетевые протоколы, диалоговые окна, персонажи компьютерных игр и многие другие объекты и системы. Таким образом, речь идет не только и не столько об использовании конечных автоматов в программировании, сколько о методе создания программ в целом, поведение которых описывается автоматами.

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

Данная работа «Разработка программного модуля автоматизации формирования программного кода на языке C по графу переходов конечного автомата» (далее OPS: Automata) предназначена для автоматизации этапов проектирования, разработки и, быть может, верификации программного обеспечения.

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

Задача OPS: Automata предназначена для автоматизации некоторых этапов (этапов проектирования, разработки и, быть может, тестирования) жизненного цикла программного обеспечения (ПО), разрабатываемого с применением автоматного подхода.

Цель решения задачи: генерация кода программ на языке C с явным выделением состояний.

Выходная информация:

  • код программы на языке C.

Входная информация:

  • граф переходов автомата (возможно, диаграмма состояний).

Требования

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

Обзор программ-аналогов

dia2fsm, fsmgen

  • сайт.
  • GNU GPL;
  • написано на C++;
  • для рисования графов конечных автоматов (КА) используется редактор диаграм Dia (версии 0.96.1);
  • Dia распространяется под лицензией GNU;
  • есть возможность организации библиотек автоматов;
  • текущая версия генератора работает под Win32;
  • планируется создание версии для Linux.

Возможности

  • генерирует код на C, C++;
  • производится проверка на непротиворечивость переходов — из одного cостояния не может выходить два и больше переходов по одному и тому же событию, с одним и тем же условием guard.
  • Производится проверка переходов по умолчанию (default transitions) со значением guard '*'. При наличии нескольких переходов генерируется ошибка, при отсутствии хотя бы родного — выдается пердупреждение.
  • Производится проверка безусловных переходов (не задано guard condition), при наличии нескольких безусловных переходов по одному событию генерируется ошибка.

EiffelState

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

FSME

Редактор FSME (Finite State Machine Editor) состоит из трех компонент:

  • FSME (Finite State Machine Editor). Используется для создания и редактиования графов переходов автоматов. Полученный с его помощью граф переходов может быть сохранен в формате XML;
  • FSMC (Finite State Machine Compiler). Конвертер графов переходов, сохраненных в XML-формате в языки C++ и Python;
  • FSMD (Finite State Machine Debugger/Tracer). Компонента для визуальной отладки графов переходов. [14]

Достоинства

  • совмещение функций редактирования и преобразования графов переходов в одной программе;
  • возможность отладки графов переходов. [14]

Недостатки

  • несоответствие дизайна получаемых графов переходов общепринятому;
  • не предусмотрена возможность дополнительного оформления графов переходов;
  • возможность генерации кода лишь на двух языках (C++ и Python) и отсутсвие возможности настройки получаемого кода;
  • для реализации GUI использует Qt3, причем после попытки автоматически привести к Qt4 (qt3to4) возникают неустраняемые (я не могу устранить) ошибки компиляции.

MetaAuto

Проектная документация представлена в источнике [14]. Разработчик: Канжелев Сергей Юрьевич, магистрант СПбГУ ИТМО, один из авторов [4].

  • официальный сайт;
  • использует xslt-обработку данных, представленных в XML-формате;
  • в качестве средства построения диаграмм используется MS Visio.

Возможности

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

QFSM

Возможности

  • Drawing, editing and printing of diagrams;
  • Binary, ASCII and "free text" condition codes;
  • Multiple windows;
  • Integrity check;
  • Interactive simulation;
  • HDL export in the file formats: AHDL, VHDL, Verilog HDL, KISS;
  • Diagram export in the formats: EPS and SVG;
  • State table export in Latex, HTML and plain text format;
  • Ragel file export (used for C/C++, Java or Ruby code generation).

QFSM 3 года назад

  • Инструмент для синтаксического анализа.
  • Позволяет проводить интерактивную симуляцию.
  • Генерации кода нет.
  • Условия перехода — регулярные выражения.
  • Предназначен для создания сканеров, а не ПО общего вида.
  • Интерфейс удобный.
  • Применение: применим для построения распознавателей, преобразователей и прочих языковых инструментов.
  • ОС: Unix.
  • Исходные коды: C++.
  • Графический интерфейс.
  • Способ графического представления графа: граф переходов.
  • Автомат сохраняется на диске в .xml-файле.
  • Есть возможность производить исполнение (отладку) построенного автомата средствами, предоставляемыми самим инструментом.
  • Удобный интерфейс.

Ragel

Note: parts of Ragel output are copied from Ragel source covered by the GNU GPL. As a special exception to the GPL, you may use the parts of Ragel output copied from Ragel source without restriction. The remainder of Ragel output is derived from the input and inherits the copyright status of the input file. Use of Ragel makes no requirements about the license of generated code.
  • написано на C++.

Возможности

  • Ragel is a finite state machine compiler with output support for C, C++, Objective-C, D, Java and Ruby source code;
  • Construct finite state machines using:
    • regular language operators;
    • state chart operators;
    • a scanner operator;
    • some mix of the above.
  • Embed actions into machines in arbitrary places.
  • Control non-determinism using guarded operators.
  • Minimize state machines using Hopcroft's algorithm.
  • Visualize output with Graphviz.
  • Use byte, double byte or word-sized alphabets.
  • Generate C, C++, Objective-C, D, Java or Ruby code with no dependencies.
  • Choose from table or control flow driven state machines.

Ragel глазами очевидца

Zed Shaw, автор HTTP-сервера Mongrel для платформы Ruby On Rails и SMTP-сервера Lamson для создания расширяемых почтовых систем на языке Python, рассказывает в своем блоге рассказывает об опыте использования Ragel. Под заголовком «Why Ragel Is Cool», он пишет: «This isn’t anything new as there’s been many software packages that do this, but what makes Ragel different is you can:

  1. inject actions at any point in the machine’s transitions
  2. use code to alter the machine’s state on the fly
  3. flexibly mix between regex specification and state chart specifications
  4. produce a variety of machine styles like table, flat, or goto machines
  5. get varying degrees of control over the state minimization
  6. easily mesh it with whatever IO or character access code you have
  7. and it’s fast as hell»

[выделение авторское]

Ragel он использовал в разработке Mongrel: «Ragel is the software behind Mongrel’s speed and correct HTTP processing. With very little effort I was able to use Ragel to create a full HTTP processor that can process the protocol at insane speeds. From a developer point of view Ragel let me crank out a fully functioning web server in about a week. (...) Specifying the protocol with a clear state machine also made Mongrel more secure than other servers».

Utu — это еще одна разработка Zed Shaw. Сам он называет Utu экспериментом в написании клиент-серверных приложений. Автор отмечает выразительность средств представления КА: «A single state machine diagram and a Ragel specification works much better than pages and pages of RFC documentation» и использует их как спецификацию сервера Utu.

Когда дело доходит до тестирования, Zed не забывает и упомянуть о «some interesting testing properties»: «First we can actually unit test the logic for the hub without connecting it to any other part of the system until we’re ready. Second we can actually fuzz the machine to see how it reacts to invalid inputs. Finally, testing the Hub involves feeding it varying streams of events, so we can try out different usage scenarios really easily».

Ragel 3 года назад

  • Консольное приложение.
  • Распознаватель текста по регулярным выражениям.
  • Редактора нет.
  • Визуализатора нет.
  • Применение: применим для построения распознавателей, преобразователей и прочих языковых инструментов.
  • ОС: Unix/Win.
  • Исходные коды: C++.
  • Интерфейс командной строки.
  • Автомат хранится на диске в текстовом файле, его описание подобно описанию грамматики для Yacc.
  • Язык генерации кода: C/C++.
  • Невозможно производить исполнение (отладку) построенного автомата средствами, предоставляемыми самим инструментом.
  • Документация хорошая.

SMC

SMC (The State Machine Compiler, The State Map Compiler) — Java приложение.

Возможности

  • генерирует код на C, C++, C#, Groovy, Java, Lua, Objective-C, Perl, PHP, Python, Ruby, Scala, Tcl и VB.net.

UniMod

Представляет собой плагин к среде разработки Eclipse. А.А. Шалыто говорит об UniMod, как о единственном средстве генерации программ по автоматам в своем роде [1]. См. также [7, 8, 12, 13].

  • официальный сайт;
  • Open Source, LGPL;
  • написано на Java;
  • сопровождается;
  • ведутся работы по доработке [3].

Возможности

  • Создание и редактирование схем связей и графы переходов управляющих автоматов, которые создаются на основе диаграмм классов и состояний языка UML.
  • Выполнение валидации автоматов: проверяет достижимость состояний, полноту и непротиворечивость условий переходов.
  • Поддержка отладки программ в терминах автоматов, когда при пошаговом выполнении на диаграмме состояний подсвечивается текущее состояние, переход, выходная переменная и т. п.
  • Позволяет производить проверку корректности построенных с его помощью программ на основе метода Model Checking.
  • Может осуществлять как компиляцию диаграмм в код на различных языках программирования (Java и, по некоторым источникам ([1]), C++), так и непосредственную интерпретацию с промежуточным преобразованием диаграмм в описание на языке XML.

Процесс разработки с использованием UniMod

Процесс разработки системы со сложным поведением с помощью этого инструментального средства состоит в следующем [1]:

  1. На основе анализа предметной области производится объектная декомпозиция системы, определяются сущности и отношения между ними.
  2. В отличие от традиционных для объектно-ориентированного программирования подходов, из числа сущностей выделяются источники событий, объекты управления и автоматы. Источники событий активны – они по собственной инициативе воздействуют на автомат. Объекты управления пассивны и выполняют действия по команде от автомата. Они также формируют значения входных переменных для автомата. Автомат активируется источниками событий и на основании значений входных переменных и текущего состояния воздействует на объекты управления и переходит в новое состояние.
  3. С использованием нотации диаграммы классов, строится схема связей автомата, которая задает его интерфейс. На этой схеме слева отображаются источники событий, в центре – автоматы, а справа – объекты управления. Источники событий с помощью UML-ассоциаций связываются с автоматами, которым они поставляют события. Автоматы связываются с объектами, которыми они управляют.
  4. Каждый объект управления содержит два типа компонентов, реализующих входные и выходные переменные.
  5. Для каждого автомата с помощью нотации диаграммы состояний строится граф переходов, в котором дуги могут быть помечены событием, булевой формулой из входных переменных и выходным воздействием на переходе. В вершинах могут быть указаны выходные воздействия в состояниях и имена вложенных автоматов. Каждый автомат имеет одно начальное и произвольное число завершающих состояний.
  6. Состояния на графе переходов могут быть простыми и составными (суперсостояния). Если в состояние вложено другое состояние, то оно является составным. В противном случае состояние простое. Основной особенностью составных состояний является то, что дуга, исходящая из такого состояния, заменяет однотипные дуги из каждого вложенного состояния.
  7. Компоненты объекта управления, соответствующие входным и выходным переменным, реализуются вручную на целевом языке программирования.

Реализация

  • «Компилятивеый подход» к использованию графов переходов. Данный подход реализует логику работы автомата не в процессе исполнения программы, а сгенерировав предварительно исходный код автоматного класса. «Компилируемый подход» был использан при создании приложений для мобильных телефонов. Необходимость его применения была связана с тем, что UniMod Runtime Engine (ядро UniMod, реализующее логику работы автомата при «интерпретируемом подходе») требует наличие библиотеки JDK 1.4 и, поэтому его невозможно применять при разработке приложений для мобильных телефонов.
  • Схема генерации кода. Граф переходов (Design Model) экспортируется в XML (Runtime Model), который трансформируется в Java-код (Java-Code). Трансформация XML-модели в Java-код осуществляется с использованием Velocity-шаблонов. [14]

Недостатки

  • Не генерирует исходный код на C.
  • Концепция «автоматы и объекты управления как классы» нарушает стройность объектно-ориентированной структуры системы и приводит к появлению в ней нового типа сущностей – автоматов. Это ограничивает модульность (поскольку автоматы в действительности не являются самостоятельными сущностями) и усложняет выделение уровней абстракции.
  • Как следствие предыдущего пункта, требуется не только объектная, но и автоматная декомпозиция, что еще больше усложняет структуру системы.
  • В графической нотации описания поведения смешиваются элементы из различных языков: используются как составные состояния, так и вложенные автоматы.
  • Модули системы не являются в достаточной степени самостоятельными и не предназначены для повторного использования. Например, имена компонентов объектов управления совпадают с краткими идентификаторами входных и выходных переменных автомата. Это довольно странно, если допустить, что класс объекта управления мог разрабатываться отдельно от управляющего автомата и может быть повторно использован в другой системе. Кроме того, для автоматов множество их клиентов ограничивается заранее заданными поставщиками событий, что препятствует использованию разработанных автоматов в другом контексте.
  • В инструменте UniMod используется довольно странная автоматная модель [1]. С одной стороны, все автоматы являются пассивными: совершают переходы только при возникновении события. Кроме того, работа системы начинается с запуска источников событий. Однако все автоматы снабжены завершающими состояниями, и окончание работы системы происходит по инициативе автомата. Такая модель находится где-то между пониманием автомата как главной программы (унаследованного из процедурного программирования с явным выделением состояний) и как сущности, предоставляющей набор сервисов. В доказательство наличия пережитков процедурного подхода, в большинстве проектов, созданных с помощью инструмента UniMod, существует единственный главный автомат, в который вложены все остальные; [1]
  • Ограниченность в оформлении графов переходов — не предусмотрено возможности добавления комментариев или картинок;
  • Возможность применения только в проектах, создаваемых на языке Java и только на платформе Eclipse;
  • Невозможность генерации исходного кода программы. [14]

Конвертер Visio2Switch

Конвертер представляет собой встраиваемый модуль (add-in) к графическому редактору MS Visio. Это исполняемый файл, имеющий самостоятельный пользовательский интерфейс, но требующий для работы наличие запущенной программы MS Visio.

  • для графического представления графов используется MS Visio.

Возможности

  • генерирует код на C.

Недостатки

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

Описание существующих технологий решения задачи OPS: Automata

Генерация кода

Генерация исходного кода программ является одним из вопросов порождающего программирования [15]. На данный момент разработано множество способов генерации кода. Среди них можно выделить следующие виды:

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

Подстановки

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

Подстановки c исполнением кода

Этот вид генерации отличается от предыдущего возможностью использовать в шаблоне не только подстановки, но также вставки исполняемого кода, оперирующего переданными в шаблон данными. Исполняемый код чаще всего использует язык, специально созданный для конкретного типа шаблонов и включающий основные конструкции (простое ветвление, циклы, обращение к данным из внешних источников, включение других файлов шаблонов и текстовых файлов, синтаксический разбор файлов шаблона, локальные переменные). Примером такого подхода является технология Jakarta Velocity, в которой используется специальный язык, называемый ее создателями "язык шаблонов", с синтаксисом, похожим на используемый в Perl. Однако, есть технологии, которые используют языки с более широкими возможностями, например, ASP и JSP используют Basic и Java соответственно.

Пример

Способ генерации кода с использованием технологии ASP.

Шаблон: 

<%@ language=jscript %><% // test.cpp.asp %>
<%
    var greeting = Request.QueryString("greeting");
    if( greeting.length == 0 ) greeting = "Hello, World.";
%>
// test.cpp

<% if( Request.QueryString("iostream").length != 0 ) { %>
#include <iostream>
using namespace std;
<% } else { %>
#include <stdio.h>
<% } %>[/code]

int main()
{
<% if( Request.QueryString("iostream").length != 0 ) { %>
    cout << "<%= greeting %>" << endl;
<% } else { %>
    printf("<%= greeting %>\n");
<% } %>
    return 0;
}

в зависимости от переданных данных (в частности, в зависимости от переменной <mono>iostream</mono>, содержащейся в строке запроса), создает один из приведенных кодов: 

// test.cpp

#include <iostream>
using namespace std;

int main()
{
    cout << "Hello, World!" << endl;
    return 0;
}
 
// test.cpp

#include <stdio.h>

int main()
{
    printf("Hello, World!\n");
    return 0;
}

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

Обработчики данных регулярной структуры

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

Разработка GUI

GUI (Graphical user interface — графический интерфейс пользователя) может быть разработан с использованием:

  • библиотеки Qt4;
  • .net;
  • java.

[Способы создания GUI с использованием C++].

Проектирование

Преобразование графа переходов в исходный код

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

Описанный подход обладает следующими недостатками:

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


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

Декомпозиция

Из приведенной схемы задача OPS: Automata может быть разделена на следующие модули:

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

Выбор и обоснование средств программной реализации задачи OPS: Automata

Генерация кода

Из перечисленных методов порождающего программирования подходящим является только использование XMLT-шаблонов. Если в качестве промежуточного формата хранения автомата был выбран XML, то для преобразования его в код на любом языке программирования требуется всего лишь написать XSLT-шаблон.

Пользовательский интерфейс

Было принято решение не использовать существующие средства создания UML-диаграмм. Одно из самых распространенных средств (MS Visio) является коммерческим, некоторые свободные программы либо идут как плагины к средам разработки (Eclipse, NetBeans), либо не являются достаточно удобными для пользователя (Rational Rose), другие не соответствуют общепринятым стандартам UML (PSUML, MS Visio) [5]. Кроме того, применение даже наиболее удачных средств построения UML диаграмм (BOUML) может мешать дальнейшему расширению возможностей разрабатываемого программного модуля.

Список используемых источников

  1. Поликарпова Н.И., Шалыто А.А. Автоматное программирование. — 1-е изд. — СПб.: Питер, 2009. — 176 с.
  2. Сайт по автоматному программированию
  3. SYRCoSE 2008. A. Khoroshilov, V. Mutilin, V. Shcherbina, O. Strikov, S. Vinogradov, and V. Zakharov. How to Cook an Automated System for Linux Driver Verification. Volume 2, pp. 11-14., Presentation
  4. Канжелев С.Ю., Шалыто А.А. Автоматическая генерация кода программ с явным выделением состояний. Статья в рамках «Software Engineering Conference (Russia) – 2006», презентация.
  5. UML. В поисках инструментов. Обсуждение на нашем форуме.
  6. Верификация автоматных программ
  7. UniMod. Публикации
  8. UniMod. Проекты
  9. Визуальное конструирование программ
  10. Реализация систем, управляемых событиями
  11. Static Finite State Machine. Кодогенерация времени компиляции Compiler-time code generation
  12. UniMod. Публикации (англ.)
  13. UniMod. Проекты (англ.)
  14. Преобразование графов переходов, представленных в формате MS Visio, в исходные коды программ для различных языков программирования (инструментальное средство MetaAuto)
  15. Чарнецки К., Айзенекер У. Порождающее программирование: методы, инструменты, применение. Для профессионалов
  16. Школы Концорциума W3C. XML Bible (второе издание), Глава 17: XSL-преобразования. http://xml.nsu.ru
  17. Технология автоматного программирования: применение и инструментальные средства. В отчете представлены сравнительная таблица инструментов создания программ и обзор некоторых из них. К сожалению, сведения устаревшие (14.10.06) и не соответствуют реальности.
  18. UML. Инструменты

Текущее состояние проекта

22.07.09

В настоящий момент ищу/смотрю/пробую на вкус существующие ПП. Их очень много (возможно, настолько много, что в создании еще одного нет необходимости). Все-таки, не смотря на многообразие, пока не вижу того, который удовлетворил бы всем предъявляемым требованиям. Однако, некоторые (UniMod) очень хороши и я решила, что разработка будет вестись, с оглядкой на них, в частности мне безумно (плохое слово) понравились возможности UniMod по отладке программ и я бы очень хотела повторить это, тем более, что другие ПП не предоставляют средств отладки вообще (это заключение сделано после беглого осмотра), что является не только отсутствием большого плюса, но и наличием большого минуса, поскольку одним из важнейших свойств автоматного подхода является существование средств проверки правильности. Я же не вижу препятствий по диаграмме состояний (или графу переходов, это зависит от реализации) проверять достижимость состояний (в любое состояние автомата должен вести путь из начального состояния, составленный из переходов), непротиворечивость (не должно существовать такого входного воздействия, при котором условия нескольких переходов из некоторого состояния автомата будут одновременно истинными) и полноту (для любого входного воздействия должен существовать хотя бы один переход из множества переходов из данного состояния автомата, условие которого будет истинным) множества переходов, хотя это и весьма трудоемко и, возможно, вскоре я откажусь от своих слов. Так же UniMod позволяет производить корректность на основе метода Model Checking (проверка модели). Я еще не вникала что это, но на сайте [1] представлено много работ [6], посвященных верификации, это заставляет верить в лучшее. Правда, некоторые из возможностей UniMod я реализовать технически не в состоянии, например, делать точками останова элементы графа переходов (для этого требуется связь со средой).

В любом случае начать надо с малого. Малое — это максимум аскетичности, но чтобы работало, так что пока о верификации и каких бы то ни было наворотах речи вестись не будет.

22.07.09

Ну вот. Нашла таки нечто, предоставляющее какие-то средства по верификации. На этом поиски программ-аналогов закончены.

23.07.09

Хотела остановить поиск новых программ-аналогов, но не смогла...

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

Почерпнула очень много. В частности, родилась идея генерировать код не только на C, но и на «априори заданном языке программирования», как это происходит у Канжелева С. Ю. . Двумя другими важными мыслями стали: читать автомат не в какой-нибудь текстовый файл, структура которого и значение данных в каждой строчке будут известны, понятны и очевидны мне одной, а в .xml-файл, как это сделано у большинства людей, и, возможно, отказаться от создания визуальной среды построения диаграмм, по крайней мере, на начальном этапе. Последнее решение вызвано тем, что, во-первых, хочется соответствия дизайна графов общепринятому (добиться чего не то чтобы трудно, но долго и рутинно), во-вторых, прежде чем заняться этим, надо разобраться с существующими средами создания UML-диаграмм, в частности, наверное, не стоит изобретать свой формат хранения графа переходов автомата, а использовать существующий (или один из). Таким образом, пока что в моей задаче входным будет .xml-файл, структуру которого предполагается уточнить.

Встал и очень интересный вопрос. Мне страшно говорить о нем вслух. Прикинув, что я хочу сделать и что у меня получится, прихожу к мысли, что изобрету MetaAuto (а оно мне надо?). Нет, мне не сложно, конечно, но зачем? Пока я не могу утверждать, что пройду по стопам Сергея Юрьевича, поскольку еще не определилась до конца, что лучше использовать, но его подход мне, как минимум нравится. Единственный минус, который я вижу в его творении — это активное использование платной Visio (с вытекающими отсюда причиндалами). Но потом с диаграммой в xml'e он творит, что хочет! Использует разные интересные интеерсные штуки... ням-ням... как бы я хотела это повторить! Но на деле мне остается только написать конвертер из формата, получаемого построением диаграммы состояний (графа переходов) в бесплатном приложении, в xml, а остальное предоставить делу техники MetaAuto? На сегодняшний день вопрос остается открытым.

Последним „открытием“ несколько подавлена.

23.07.09 (утро)

Ну вот. Убежденность, в том, что использование XMLT+XML является удачным решением засела глубже. Это было одно из принципиальных мест, где мои пути с MetaAuto могли разойтись. Так нет же.

Начинает создаваться впечатление, что сижу без дела. Оно и понятно: раньше я делом считала программирование, соответственно, то, что делаю сейчас — не дело (потому что не программирование).

Не представляю что делать.

24.07.09 (ночь)

Разочаровалась во всех имевшихся ссылках по генерации кода. Сейчас читаю Гамма. В запасе диссертация Чарнецки. Возлагаю надежды на них.

Но мысли пришли в порядок.

24.07.09 (утро)

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

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

Разбиралась с существующими средствами создания UML-диаграмм. Это понадобится в будущем, когда буду пытаться преобразовать диаграмму состояний в код: надо будет решить из какого формата генерировать промежуточный файл. Требуется, чтобы средство создания uml-диаграмм поддерживало такие вещи, как вызов автомата на ребре, например. Читала Буча, Рамбо, Джекобсона. Конечно, средства UML поражают. Я была с ними шапочно знакома и всегда думала, что они гораздо скуднее. Кроме того, узнала, что по автомату код генерируют не только упомянутые мною программы, но и те, которые строят эти самые автоматы (точнее, диаграммы состояний). Усугубляет все и тот факт, что код генерировать, на мой взгляд, гораздо удобнее в такой полноценной штуке: там и диаграммы классов и многое другое, что позволяет кодогенератору "увидеть" разрабатываемую систему куда лучше, чем такой вот однобокий генератор, как (будет) у меня. С другой стороны, я не знаю как пользуются эти кодогенераторы хорошим зрением — может, и не пользуются.

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

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

Только сейчас понимаю, что обратить внимание на инструментарий по UML надо было с самого начала, но я всегда его считала Paint'ом с разными фигурами (+некоторые фичи), а ожидать от Paint'а генерации кода, увольте. Предубеждение.

05.08.09

Разбиралась с Ragel.

26.08.09

Happy end.

Источник — «http://it.mmcs.sfedu.ru/_wiki/index.php?title=OPS:_Automata&oldid=3052»