САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
Математико-механический факультет
Кафедра системного программирования
ГЕНЕРАЦИЯ КОДА ПО ДИАГРАММЕ АКТИВНОСТЕЙ
Дипломная работа студентки 545 группы
Ивановой Оксаны Олеговны
Научный руководитель
|
………………
/ подпись /
|
д.ф.-м.н., проф. Терехов А.Н.
|
Рецензент
|
………………
/ подпись /
|
ст. преп. каф. сист. прог. Литвинов Ю.В.
|
“Допустить к защите”
заведующий кафедрой,
|
………………
/ подпись /
|
д.ф.-м.н., проф. Терехов А.Н.
|
Санкт-Петербург
SAINT PETERSBURG STATE UNIVERSITY
Mathematics & Mechanics Faculty
Software Engineering Chair
CODE GENERATION FROM ACTIVITY DIAGRAM
by
Oksana Ivanova
Master’s thesis
Supervisor
|
………………
|
Professor A.N. Terekhov
|
Reviewer
|
………………
|
Senior lect. Y.V. Litvinov
|
“Approved by”
Head of Department
|
………………
|
Professor A.N. Terekhov
|
Saint Petersburg
Оглавление
Введение 4
Глава 1. Контекст исследования.
8
1.1. Диаграмма активностей. 8
1.2. Обзор существующих CASE-средств.
9
1.3. QReal. 10
Глава 3. Результаты. 12
3.1. Требования к генератору. Диаграмма активностей. 12
3.2. Пример неструктурированной диаграммы. 19
3.3. Описание алгоритма. 22
Заключение 29
Список литературы: 31
Введение
По мере развития индустрии информационных технологий сложность программного обеспечения постоянно растет. Появляются продукты с все более значительным объемом исходного кода, количеством связей между компонентами и т.д. Их разработка и поддержка становится более затратной по времени и используемым ресурсам. Вместе с тем, решающим фактором при разработке программного обеспечения является время создания продукта. Продукт, вышедший на рынок первым, обладает несомненным преимуществом перед конкурентными разработками. Таким образом, в IT-индустрии возникла проблема упрощения и ускорения разработки программного обеспечения.
Решение вышепоставленной проблемы происходило и происходит в основном в трех направлениях:
-
развитие организации процесса разработки ПО (к примеру, появление методологий управления проектами, в том числе аgile software development);
-
совершенствование средств разработки ПО (к ним можно отнести такие среды разработки, как Microsoft Visual Studio, Eclipse, а также системы контроля версий);
-
применяются языки программирования с все большим уровнем абстракции.
В качестве продолжения последнего подхода следует отдельно выделить графические языки моделирования.
Графические языки моделирования используются довольно продолжительное время, однако среди разработчиков не существует единого мнения об их роли. Обычно их используют на этапе проектирования, так как языки программирования не всегда обеспечивают нужный для этого уровень абстракции. Однако графические языки можно применять также для рисования эскизов (чтобы облегчить обмен информацией между разработчиками, подчеркнуть самые важные аспекты системы) и непосредственно в качестве языка программирования (по компонентам графического языка (диаграммам) генерируется исполняемый код и, таким образом, сам язык моделирования становится исполняемым кодом). Именно этот аспект их применения мы будем рассматривать в данной работе.
В настоящий момент основным стандартом в области визуализации программного обепечения является язык UML (сокр. от англ. Unified Modeling Language – унифицированный язык моделирования). UML – открытый стандарт, находящийся под управлением группы OMG (Object Management Group). Его появление явилось результатом слияния множества объектно-ориентированных языков графического моделирования, процветавщих в конце 80-х и начале 90-х.
В стандарт UML входят 13 типов диаграмм (рис. 1). Описание программы при помощи всех этих диаграмм является избыточным, по причине того, что сами диаграммы взаимосвязаны, хотя эта связь не всегда включена в стандарт UML. Поэтому для нужд кодогенерации обычно используется лишь некоторое подмножество (срез) языка UML.
Рис. 1. Виды диаграмм UML.1
Вследствие популярности графических языков моделирования возникает необходимость автоматизации работы с ними. На рынке программного обеспечения представлено множество так называемых CASE-средств (сокр. от англ. computer-aided software enginering), которые решают множество задач, покрывающих весь жизненный цикл программного обеспечения, от простого анализа и документирования до полномасштабной автоматизации.
На данный момент задача кодогенерации из диаграмм UML представляет большой интерес для широкого круга разработчиков. Любой достаточно большой проект в процессе своей разработки включает стадию проектирования. При этом на этапе реализации довольно удобно использовать диаграммы, созданные на этапе проектирования. Генерация кода из диаграмм существенно упрощает написание программ, хотя бы потому, что диаграммы являются более наглядным описанием системы по сравнению с кодом.
Все диаграммы UML взаимосвязаны между собой, и описание системы при помощи совокупности всех диаграмм является избыточным. По этой причине для генерации кода осуществляется выборка диаграмм, по которым производится генерация. Чаще всего тела функций определяют при помощи конечных автоматов, однако их выразительная сила невысока. Известный эксперт в области визуального моделирования Мартин Фаулер отметил, что диаграммы активностей лучше подходят для целей описания семантики произвольных процессов и ”в наибольшей степени их мощь может проявиться в случае применения UML как языка программирования”.[1] Одно из важных применений диаграммы активностей в UML – это описание процедурного и параллельного программирования.
На данный момент лишь немногие CASE-средства способны генерировать код по диаграмме активностей. В то же время большинство из них являются платными и охватывают диаграмму активностей не полностью. При попытках генерации кода из данной диаграммы может возникнуть нетривиальная проблема ее неструктурированности. Под неструктурированными мы понимаем диаграммы, не отображающиеся напрямую на структурные конструкции текстовых языков программирования. Таким образом, моя задача состоит в разработке алгоритма генерации кода по неструктурированной диаграмме активностей.
Генерация кода по неструктурированной диаграмме активностей похожа на задачу элиминации оператора goto в компиляторах. Однако есть и дополнительная трудность – сохранение максимальной схожести полученного кода с исходным. Такая проблема решалась в задачах реинжиниринга устаревших программ [10].
Глава 1. Контекст исследования.
1.1. Диаграмма активностей.
Диаграмма активностей – это одна из поведенческих диаграмм UML. Она позволяет хорошо описывать логику процедур, бизнес-процессы и потоки работ.
Диаграмма активностей позволяет моделировать поведение системы естественным образом, в соответствие с шагами выполняемых процессов. С помощью диаграмм активностей можно описывать сложный жизненный цикл объекта с переходами из одной деятельности в другую. Но этот вид диаграмм может быть использован и для описания динамики совокупности объектов. Они применимы и для детализации некоторой конкретной операции, причем предоставляют для этого больше возможностей, чем "классическая" блок-схема.
Кроме генерации кода по диаграмме активностей возможна генерация кода по диаграмме конечных автоматов. Генерации из диаграммы конечных автоматов посвящено множество работ, и многие CASE-средства ее поддерживают. Но для использования этой диаграммы необходимо проектировать задачу, используя по совместительству объектные и автоматные парадигмы программирования. При этом такой стиль программирования был назван объектно-ориентированным с явным выделением состояний [12], [13]. Поскольку наша задача состоит в генерации чисто объектно-ориентированного кода, диаграмма активности остается для нас предпочтительнее диаграммы конечных автоматов.
Одна из наиболее часто используемых диаграмм UML – это диаграмма прецедентов, она же 0 «use case» диаграмма. Данная диаграмма показывает то, как пользователи взаимодействуют с системой. Диаграмма «use case» предназначена для отображения списка операций, которые должна выполнять описываемая система, иначе говоря, – это требования к системе. По этой причине при кодогенерации диаграмму «use case» чаще всего используют для генерации требований к системе.
Отметим, что к поведенческим диаграммам относятся четыре диаграммы взаимодействия. Они показывают взаимодействие между объектами, с различными акцентами (время, связь, последовательность).
Диаграмма активностей имеет свои преимущества с точки зрения генерации по ней кода, хотя на данный момент времени она незаслуженно обделена вниманием многих CASE-средств, позволяющих прямую генерацию кода.
1.2. Обзор существующих CASE-средств.
В разряд CASE-средств попадают как относительно дешевые системы для персональных компьютеров с весьма ограниченными возможностями, так и дорогостоящие системы для неоднородных вычислительных платформ и операционных сред. Так, современный рынок программных средств насчитывает более 300 различных CASE-средств, наиболее мощные из которых так или иначе используются практически всеми ведущими западными фирмами. [14]
В ходе исследования аналогов основной целью являлось нахождение средств, генерирующих поведение с учетом диаграмм активностей. Несмотря на то, в документации к некоторым рассмотренным средствам была указана возможность генерации кода по диаграмме активностей, при ознакомлении с ними было выявлено обратное. [4],[5],[8],[9],[15]. Однако, CASE-средство Enterprise Architect генерирует код из диаграммы активностей, но мало того, что он накладывает на нее существенные ограничения, он еще является и платным. [16]
В случае, если не накладывать ограничения на структурность диаграммы, то становится очевидным, что невозможно поддерживать полное соответствие кода диаграмме. При попытке сгенерировать что-либо из кода, с большой вероятностью диаграмма будет отличаться от исходной.
Несмотря на то, что CASE-средства еще не в полной мере поддерживают генерацию кода из диаграммы активностей, существует множество научных статей, посвященных данному вопросу [17], [18].
1.3. QReal.
С 1984 г. на математико-механическом факультете ЛГУ проводятся исследования и разработки в области CASE-технологий. С 1995 года началась разработка системы реального времени REAL. REAL является технологией разработки информационных систем и систем реального времени, она представляет собой набор взаимосвязанных графических редакторов диаграмм UML 1.4 и SDL-92. На его основе был создан набор технологических решений, таких как REAL-IT для автоматической генерации по моделям информационных систем.
В 2006 году было принято решение о создании нового кроссплатформенного CASE-пакета QReal , а также поддержке спецификации UML 2.1. Мотивацией к этому послужило то, что набор визуальных редакторов UML, поддерживаемых REAL, устарел, а задание нового редактора требовало от пользователя написания не только кода на C++ (что уже является неудобным), но и знания всего CASE-пакета в целом. Отметим, что использование устаревшей библиотеки MFC (сокр. с англ. Microsoft Foundation Classes) усложняло процесс переноса системы на другие платформы и сопровождение. Подробнее об этом можно почитать в [11].
В настоящее время продолжается разработка и поддержка решения студентами и аспирантами кафедры системного программирования СПбГУ.
Мой практический опыт работы с данной технологией заключался в описании для нее некоторых диаграмм языка UML 2.0 и языка BPEL на специальном, основанном на XML, языке описания редакторов в рамках курсовой работы на 3 курсе. Это дало мне опыт работы c CASE-средствами.
Глава 3. Результаты.
3.1. Требования к генератору. Диаграмма активностей.
В процессе моделирование не должно накладываться особых ограничений на вид диаграммы и расположение элементов, поэтому пользователь может создать диаграмму любой сложности. Это усложняет генерацию кода по таким диаграммам и такие случаи надо разбирать отдельно. При создании диаграмм пользователь работает в терминах диаграмм, а не в терминах кода, который по ним получается. Поэтому пользователь может не следовать правилам структурного программирования при рисовании диаграмм.
Вследствие того, что мы не будем ограничиваться только структурными диаграммами, при генерации кода могут возникнуть некоторые трудности. Рассмотрим, какие могут получиться диаграммы и какой код будет сопоставляться им.
Рис. 2. Простая диаграмма с while.
Рис. 3. Диаграмма со структурным ветвлением.
По такой диаграмме, изображенной на рис. 1, понятно, что за код должен получиться. Его генерация также не является интересной задачей. Единственное, что стоит отметить, в таком простом случае и сгенерированный код должен получаться простым и понятным.
Так, рисунку 3 должен соответствовать следующий код:
if (a>b){
action1();
}
else{
action2();
}
Рис. 4. Диаграмма с неструктурным ветвлением.
Рассмотрим диаграммы с неструктурными циклами на примере диаграммы, изображенной на рис. 4. С одной стороны такие диаграммы, становятся более сложными для кодогенерации. С другой стороны, они визуально более ясны и более понятны информативно. Однако, для генерации кода они представляют некоторую сложность. В первую очередь, код становится совсем не однозначным. Сложность заключается в том, что разработчику не избежать расскопирования кода или использования констуркции goto. На мой взгляд, раскопирование в данном случае является более удачной идеей.
По такой диаграмме ожидается следующий код:
if (a>b){
action1();
if (d>e){
action3();
}
else{
action2();
}
}
else if (b>c){
action3();
}
Рис. 5. Диаграмма с неструктурными циклами.
Максимальный интерес представляет кодогенерация из диаграмм с неструктурными циклами. Пример такой диаграммы изображен на рис. 5. Диаграммы этого типа легки для понимания, однако возникает сложность в генерации по ним кода. Причиной тому является ее неструктурированность. В cпецификации UML диаграммы такого типа разрешены, но тем не менее, многие CASE-средства не обладают возможностью генерации по ним кода.
Ожидаемый код по диаграмме, изображенной на рис. 5, должен выглядеть следующим образом:
while (true){
if (a>b){
action1();
if(d>e){
}
else{
action2();
break;
}
else if (b>c){
action3();
break;
}
}
3.2. Пример неструктурированной диаграммы.
Рассмотрим наглядный пример неструктурированной диаграммы активностей. Представление в виде блок-схемы практически любого нетривиального математического алгоритма дает неструктурированную диаграмму. Рассмотрим знакомый любому студенту математико-механического факультета алгоритм решения системы линейных уравнений по методу Гаусса.
Изложим сам алгоритм.
Итак, пусть – вещественная n-мерная матрица, – вектор. Требуется найти такой , что .
Метод Гаусса заключается в привидении матрицы с помощью последовательности т.н. элементарных преобразований к верхне-треугольному виду, с соответствующим преобразованием , после чего решение находится тривиальным образом. Напомним, что под элементарным преобразованием подразумевается преобразование матрицы одного из трех типов:
-
вычитание из i-ой строки j-ой строки;
-
деление i-ой строки на число;
-
перестановка i-ой и j-ой строк.
Каждое преобразование соответствует умножению слева матрицы на некоторую обратимую матрицу.
Преобразования (ii) и (i) используются в методе для присвоения диагональным элементам 1 (i-ая строка делится на ) и обнуления поддиагональных элементов (для всякого j > i, из j-ой строки вычитается i-ая, умноженная на ). При этом, когда точность вычислений существенна, при реализации алгоритма не рекомендуется делить строки на слишком маленькие диагональные элементы. Так что каждый диагональный элемент сравнивается с некоторым фиксированным e>0 и, если диагональный элемент меньше e, производится выбор максимального элемента в соответствующей подматрице и перестановка его с диагональным. Перестановка осуществляется с помощью преобразований вида (iii).
Рассмотрим запись реализации в виде диаграммы (рис. 3.2.):
Рис. 3.2. Неструктурная диаграмма.
findMaxInSubMatrix(...), transform1,2(...), transpose(...) – методы, осуществляющие поиск максимального элемента в подматрице, и различные элементарные преобразования (одновременно с матрицей A и c вектором b), их реализация опущена. Непосредственный вывод решения в диаграмме также опущен. Как видим, диаграмма даже такого простого алгоритма со значительными упрощениями уже оказывается неструктурной.
3.3. Описание алгоритма.
Для задания структуры системы традиционно используется диаграмма классов, а для задания логики поведения системы диаграмма активностей. Будем с каждым методом ассоциировать диаграммы активностей, которая будет показывать логику поведения системы внутри данного метода.
Диаграмма классов.
Диаграмма классов показывает из себя статическое представление системы. Оно определяет структуру моделируемой системы в терминах классов, интерфейсов, наследования и реализации, полей и свойствах классов. По такому представлению можно сгенерировать код с методами-заглушками.
Диаграмма активностей.
Для генерации логики из диаграммы активности было решено создать отдельную структуру. Сначала граф диаграммы преобразуется в граф, который более удобен для вывода, за тем происходит сам вывод. При построение нужной модели была обнаружена сложность с вычленением условных конструкция и циклов, которая была успешно преодолена. Ниже описано ее решение при предположении, что в диаграмме активностей отсутствуют вершины кроме action, final, merge, initial, decision, а графы активностей изображены схематично.
Вычленение условных конструкций и циклов для диаграммы активностей.
Напомним, что диаграмма активности есть ориентированный граф (X,Г) (где Х – множество вершин, Г – множество ребер) с некоторой дополнительной структурой. А именно, каждая вершина имеет тип, некоторые ребра могут иметь "пометку". В задаче будут встречаться вершины следующих типов (со следующими свойствами):
-
обычная (action) – содержит некоторое строковое описание кода; ее входящая и исходящая степени равны 1;
-
разделяющая (decision) – каждое исходящее ребро содержит условия перехода;
-
объединяющая (merge) – исходящая степень равна 1;
-
конечная (final) – исходящая степень равна 0.
Грубо говоря, вершина типа action может соответствовать вызову процедуры, объявлению переменных, операциям над ними и т.д., разделяющие вершины (далее – DN2) соответствуют объявлениям условных операторов и циклов (конструкции if(..){}, while(..){} и т.д.), объединяющие вершины (MN3) служат для "закрытия" условных операторов, а конечная вершина (FN4) обозначает завершение функции.
Будем ожидать, естественно, что диаграмма удовлетворяет всем естественным свойствам (граф связный и т.д.). Так же предположим, что каждой DN соответствует некоторая MN. Наконец, что важнее всего, мы ограничимся пока генерацией кода без циклов (типа while) - хотя простейший случай с циклами и не представляет сложностей, но общий случай требует некоторых разъяснений. Итак, мы считаем, что входящая степень DN равна 1, а сам граф не содержит ориентированных циклов. Пример диаграммы с ориентированным циклом изображен на рис. 6.
Рис.6. Диаграмма с ориентированным циклом.
Решение.
Решение задачи в случае простых диаграмм без пересекающихся условных операторов не представляет большой сложности. Пример такой диаграммы изображен на рис. 7. Диаграмма с пересекающимися условными операторами, приведенная на рис. 8, требует некоторой дополнительной работы.
Рис.7. Диаграмма без пересекающихся условных операторов.
Содержательная часть заключается в работе c пересекающимися условными оператора. Для каждой DN требуется найти соответствующую MN или FN, а также построить дополнительную структуру, по которой построение кода не будет представлять особой сложности.
Рис. 8. Диаграмма с пересекающимися условными операторами.
Итак, рассмотрим некоторый цикл внутри описанной диаграммы.
Рассмотрим случай, когда цикл не содержит вложенных DN. Таким образом, часть рассматриваемой диаграммы содержит единственную DN, а все выходящие из нее пути сходятся в одну вершину MN или FN.
Пусть из DN выходит N ребер. Для каждого i-го ребра рассмотрим упорядоченное множество вершин Mi и пошагово наполним их вершинами. На первой итерации в Mi поместим вершину, в которую входит i-ое ребро. Кроме того, нам понадобится флаг для каждого множества. Будем считать, что каждое Mi может быть "открытым" или "закрытым". На первом шаге все Mi положим открытыми.
Итак, наполним вершины следующим образом: на n+1 шаге будем идти по всем открытым Mi по порядку. Для открытого Mi добавим в него следующую за последней вершину из Mi . Очевидно, что в предположении отсутствия других DN, “следующая” вершина для Mi определяется однозначно. Произведем проверку, пересекается ли Mi с каким-либо Mj, если да, Mi объявляем закрытым. Таким образом, после каждого прохода все открытые множества не будут пересекаться. Процесс продолжается до тех пор, пока не останется всего одно открытое множество:
int open = N;
while(open!=1){
for(int i=1; i<=N; i++){
if(Mi.isOpen()){
Mi.addNext();
for(int j=1; j<=N; j++){
if(j!=i && Mi.intersects(Mj)){
Mj.close();
open--;
}
}
}
}
}
По оставшемуся в конце открытому множеству легко находится последняя MN, а по Mi восстанавливается искомое разбиение цикла на пути. Алгоритм незначительно усложняется, если учитывать наличие конечных вершин. В этом сучае будем считать, что все конечные вершины являются одной вершиной типа MN без исходящих ребер.
В общем случае, когда в графе много DN, алгоритм обобщается рекурсивно. Вместо множества вершин Mi, наша структура превращается в список Si,элементы которого являются либо вершинами, либо набором списков S. Отметим, что в момент столкновения с вложенной DN, будем добавлять не следующую вершину, а набор таких же множеств Mi, полученных в результате работы алгоритма с графом, начиная с встретившейся DN.
Графы с циклом while.
Алгоритм незначительно усложнится в случае появления в графе структурных циклов (рис. 6). Множество будет называться закрытым не только в случае столкновения с другим множеством, что рассматривалось ранее, но и в случае прихода в одну из ранее пройденных DN.
Кроме того, в структуру необходимо добавить поле, отвечающее за соответствие ветви циклу while или условному переходу.
В случае наличия в графа неструктурированных циклов while (рис. 9), в структуру необходимо добавить тип, отвечающий за смешанные ветви, то есть когда вложенные ветви могут соответствовать конструкциям как while, так и if. Множество Mi будет объявляться «закрытым» в случае, если “ребенок” последней вершины является вершиной из полученного списка DN, что было описано ранее. Множество Mi будет «запоминать», какая именно вершина в списке «заставила» ее остановиться. Кроме того, необходимо хранить для каждой ветки if-типа, находящейся в ветви смешанного типа, степень ее вложенности, что нужно для осуществления выхода из нужного while при генерации кода.
Рис. 9. Пример неструктурированного цикла while.
Следует различать все приведенные выше случаи. В зависимости от того, какие конструкции содержит диаграмма, следует генерировать различный код. Код, полученный в последних двух случаях, будет явно менее понятен, чем диаграмма. Для остальных случаев не стоит использовать такой же алгоритм вывода, как для последних.
Заключение
В процессе работы было выявлено, что на данный момент лишь немногие CASE-средства способны генерировать код по диаграмме активностей. В то же время при попытках генерации кода из данной диаграммы может возникать существенная проблема – ее неструктурированность. То есть диаграмма, не отображающаяся напрямую на структурные конструкции текстовых языков программирования, представляет сложность для генерации кода, она требует разработки специального алгоритма, обрабатывающего нетривиальные ситуации. Таким образом, моей основной задачей стала разработка алгоритма генерации кода по неструктурированной диаграмме активностей.
Результатами работы являются:
-
выбор диаграммы активностей UML для описания поведенческого аспекта системы;
-
разработан и реализован алгоритм генерации исходного кода для языка C#;
-
алгоритм интегрирован в среду визуального моделирования QReal.
Разработанный алгоритм применим во многих областях, в которых возможно задание поведения системы при помощи неструктурированной диаграммы активностей. В работе рассмотрен наглядный пример неструктурированной диаграммы, применимой в области решения математических задач. Таким образом, реализованный алгоритм генерации исходного кода имеет широкое практическое применение.
Список литературы:
1. M. Fowler. UML Distilled: A Brief Guide to the Standard Object Modeling Language. Addison-Wesley Professional. – 192p. – 2003.
2. UML. URL: http://uml.org/.
3. Microsoft Developer Network. URL: http://msdn.microsoft.com/.
4. ArgoUML. URL: http://argouml.tigris.org/.
5. UModel. URL: http://www.altova.com/products/umodel/uml_tool.html.
6. QReal URL: http://unreal.tepkom.ru/.
7. Qt4 URL:http://doc.qt.nokia.com/.
8. Visual Paradigm URL: http://visual-paradigm.com/.
9. Umbrello URL: http://uml.sourceforge.net/.
10. А.Н. Терехов, А.А.Терехов. Автоматизированный реинжиниринг программ. – СПбГУ – 330c. – 2000.
11. Брыксин Т.А. Дипломная работа «Model/View архитектура Case-пакета Real/MV». – 2007.
12. А.А. Шалыто. Автоматное программирование. – СПБГУИТМО – 44с. –2009.
13. С. Канжелов, А.А.Шалыто. Автоматическая генерация кода программ с явным выделением состояний. – 10 с. – 2006.
14. А. М. Вендеров. CASE-технологии. Современные методы и средства проектирования информационных систем. – 176с. – М. – 2004.
15. BOUML. URL: http://bouml.free.fr/
16. Enterprise Architect. URL: http://www.sparxsystems.com.au
17. W. Zhao, R. Hauser, K. Bhattacharya, R. Bryant. Compiling business processes: untangling unstructured loops in irreducible flow graphs. – 24 с. – 2006.
18. A.K. Bhattacharjee1, R.K. Shyamasundar. Validated Code Generation for Activity Diagrams. – 14с. – 2005.
|
