Scientific journal
Fundamental research
ISSN 1812-7339
"Перечень" ВАК
ИФ РИНЦ = 1,674

ALGORITHMS FOR HORIZONTAL TRANSFORMATION OF MODELS IN METALANGUAGE SYSTEM

Sukhov A.O. 1
1 National Research University Higher School of Economics
In the process of information systems creation and maintaining the model-based approach to the software development, which allows to shift the focus from code writing on general purpose language to models creation and automatic generation of the system source code on the basis of the created models, is increasingly used. However at usage of this approach there is a need of conversion of models constructed at various stages of system development by various categories of users with usage of different modeling languages. In paper the algorithms for horizontal transformation of models, which are described with usage of one domain-specific modeling language, to models, which are constructed in other graphical (textual) notation is considered. The component of MetaLanguage system, which implements these algorithms, allows to fulfill the transformations of visual models of the type «model-text» and «model-model».
model transformation
graph grammars
visual modeling languages
meta-modeling
1. Zamyatina E.B., Lyadova L.N., Sukhov A.O. O podkhode k integratsii sistem modelirovaniya i informatsionnykh sistem na osnove DSM-platformy MetaLanguage / Informatization and Communication, 2013, no. 5, pp. 11‑14.
2. Zamyatina E.B., Lyadova L.N., Sukhov A.O. Metody transformatsii vizualnykh modeley. Proc. of the 4th International Conference “Information Systems Development Technologies”. Gelendzhik, 2013, pp. 61‑70.
3. Sukhov A.O. The Language Workbench for Visual Domain-Specific Modeling Languages Creation / Fundamental research, 2013, no. 4 (Part 4), pp. 848‑852.
4. Sukhov A.O. Metody transformatsii vizualnykh modeley. Proc. of the 3th International Conference «Information Systems Development Technologies». Gelendzhik, 2012, pp. 120‑124.
5. Sukhov A.O. Teoreticheskiye osnovy razrabotki DSL-instrumentariya s ispol’zovaniyem grafovykh grammatik / Informatization and Communication, 2011, no. 3, pp. 35‑37.
6. Sukhov A.O. Formalnoye opisaniye metayazyka sistemy MetaLanguage. Proc. of the All-Russian Scientific Conference «Modern problems of mathematics and its applications». Perm, 2010, pp. 154‑159.
7. Algebraic Approaches to Graph Transformation. Part II: Single Pushout Approach and Comparison with Double Pushout Approach // H. Ehrig, R. Heckel, M. Korff [et al.]/ Handbook of Graph Grammars and Computing by Graph transformation, 1997, Vol. 1, pp. 247‑312.

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

Существуют реализации модельно-ориентированного подхода, которые применяют языки моделирования общего назначения для построения моделей ИС. Так, язык моделирования UML вместе со стандартом MOF (Meta-Object Facility) формирует основу для концепции MDA (Model-Driven Architecture). Другие реализации модельно-ориентированного подхода применяют для построения моделей визуальные предметно-ориентированные языки (Domain-Specific Language, DSL), предназначенные для решения определенного класса задач в конкретной предметной области. В отличие от языков моделирования общего назначения DSL более выразительны, просты в применении и понятны различным категориям специалистов, поскольку они оперируют привычными для них терминами предметной области. Для поддержки процесса разработки и сопровождения DSL используется специальный вид программного обеспечения – языковой инструментарий.

В процессе создания и эксплуатации ИС принимают участие различные категории специалистов (программисты, бизнес-аналитики, эксперты в предметной области и др.), поэтому достаточно часто появляется потребность изменения описания языка моделирования, его настройки на возможности конкретного пользователя, а также необходимость преобразования моделей, построенных различными специалистами на разных этапах создания ИС с использованием различных DSL. Для реализации этих возможностей необходимо, чтобы языковой инструментарий позволял строить целую иерархию моделей: модель, метамодель, мета-метамодель и т.д., где модель – это абстрактное описание на некотором формальном языке характеристик системы (процесса), важных с точки зрения цели моделирования, метамодель – модель языка, используемого для создания моделей, а мета-метамодель – язык, на котором описываются метамодели. Кроме того, языковой инструментарий должен содержать средства трансформации, позволяющие выполнять преобразование визуальных моделей как между различными уровнями иерархии (вертикальные трансформации), так и внутри одного уровня (горизонтальные трансформации).

Система MetaLanguage – это языковой инструментарий, предназначенный для создания визуальных динамически настраиваемых предметно-ориентированных языков моделирования [1]. Архитектура данной системы описана в работе [3].

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

Анализ наиболее развитых на сегодняшний день языков и инструментальных средств трансформации моделей, приведенный в работе [4], показал, что наиболее подходящим для реализации в системе MetaLanguage является алгебраический подход с одинарным выталкиванием [7], основанный на графовых грамматиках.

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

Горизонтальные трансформации моделей в системе MetaLanguage

Базовым понятием при описании трансформации графов в соответствии с алгебраическим подходом является продукционное правило, которое имеет вид p: L → R, где p – имя правила, L – левая часть правила, которая называется паттерном, а R – правая часть правила, которая называется графом замены.

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

Графовая грамматика – это пара GG = (P, G0), где P – набор продукционных правил; G0 – начальный граф грамматики.

Пусть дан исходный граф G, а также графы L и R, которые представляют собой левую и правую части продукционного правила p: L → R, причем граф L является подграфом графа G. Тогда применением правила p к исходному графу G называется замена в графе G подграфа L на граф R, результатом замены является граф H, причем граф R – подграф графа H.

Графовая трансформация – это последовательное применение к исходному помеченному графу G0 конечного набора правил

P = (p1, p1, …, pn): syhov01.wmf,

где Gn – результат выполнения трансформации.

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

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

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

Существуют различные алгоритмы поиска графа, изоморфного заданному паттерну, наиболее распространенными на практике являются: алгоритм Ульмана, алгоритм Шмидта и Дрюфелла, алгоритм Венто и Фоггиа, Nauty-алгоритм и др. Отличием предлагаемого подхода от решения классической задачи сопоставления графов является то, что в данном случае требуется провести сопоставление графов, принадлежащих различным уровням иерархии моделей, при этом необходимо учитывать типы вершин и дуг графа.

Реализованный в системе MetaLanguage алгоритм поиска паттерна в графе модели является разновидностью алгоритма перебора с возвратом, который имеет экспоненциальную сложность. Алгоритм состоит из трех этапов. При выполнении первого этапа алгоритма будут найдены все экземпляры некоторого произвольного отношения из графа-паттерна, т.е. осуществляется поиск дуги, с которой начнется выполнение второго этапа алгоритма. На втором этапе требуется найти одно из возможных вхождений экземпляров всех отношений графа-паттерна GP в граф исходной модели GS. На третьем этапе в результирующий граф GT необходимо добавить те вершины графа GS, прообразы которых принадлежат графу GP. Далее следует выполнить замену левой части правила на правую. Если исходный граф GS содержит еще несколько вхождений экземпляров всех отношений графа-паттерна GP, то для каждого такого вхождения необходимо выполнить данный алгоритм, начиная со второго этапа. Рассмотрим этапы алгоритма поиска паттерна в исходном графе более подробно.

Первый этап – процедура FindPattern:

1.1. Очистить множество вершин исходного графа, просмотренных в ходе поиска, – VisitedEntities.

1.2. Выбрать в графе-паттерне GP одно из отношений, обозначим его rel. Если таких отношений не оказалось, то перейти к выполнению процедуры AddNodes добавления вершин в граф GT .

1.3. Найти все экземпляры отношения rel в исходном графе модели GS. Множество всех этих отношений обозначим FoundRelations.

1.4. Для каждого экземпляра отношения relI из множества FoundRelations выполнить процедуру FindSubGraph для поиска подграфа GT в графе исходной модели GS, соответствующего паттерну и содержащего этот экземпляр отношения.

Второй этап – процедура поиска подграфа, содержащего указанный экземпляр отношения, FindSubGraph состоит из следующих шагов:

2.1. Добавить в множество дуг результирующего графа GT дугу relI.

2.2. Если после добавления дуги оказалось, что количество дуг графа GT совпадает с количеством дуг графа-паттерна GP, то следует перейти к выполнению процедуры добавления вершин в граф GT (AddNodes), а затем вернуться, удалить из графа GT дугу relI и перейти к шагу 1.4, т.к. в исходном графе могут существовать и другие экземпляры отношений того же типа. Иначе перейти к шагу 2.3.

2.3. Приступить к рассмотрению первой вершины entI1, инцидентной ребру relI, если она ранее не была рассмотрена:

a. Добавить вершину entI1 в множество VisitedEntities.

b. Рассмотреть все входящие в entI1 дуги графа GS, если прообраз некоторой из них syhov02.wmf принадлежит графу-паттерну GP и он ранее не рассматривался, то следует произвести поиск подграфа, содержащего экземпляр отношения syhov03.wmf, начиная со второго этапа описываемого алгоритма.

c. Рассмотреть все исходящие из entI1 дуги графа GS, если прообраз некоторой из них syhov04.wmf принадлежит графу-паттерну GP и он ранее не рассматривался, то следует произвести поиск подграфа, содержащего экземпляр отношения syhov05.wmf, начиная со второго этапа данного алгоритма.

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

2.5. Перейти к выполнению процедуры добавления вершин в граф GT.

Третий этап – процедура добавления вершин AddNodes – состоит из трех шагов:

3.1. Рассмотреть все дуги графа GT. Если прообраз какой-либо инцидентной дуге вершины принадлежит графу-паттерну GP, то ее следует добавить в множество вершин графа GT.

3.2. Найти в графе GS множество вершин, прообразы которых в графе GP являются изолированными, и добавить их в граф GT.

3.3. Вызвать процедуру замены левой части правила на правую LHSReplacement. Она определяется видом правила трансформации.

Алгоритмы замены левой части правила на правую

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

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

Описание шаблона производится на целевом языке. Для выделения динамической части используются специальные метасимволы: «<<» (двойные открывающиеся угловые скобки) – для обозначения начала динамической части; «>>» (двойные зарывающиеся угловые скобки) – для обозначения окончания динамической части. Поскольку имена некоторых сущностей и отношений могут совпадать, то для обозначения сущности перед ее именем указываются префикс «С.», а для обозначения отношения – префикс «О.».

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

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

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

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

Трансформацию вида «модель-модель» можно декомпозировать на следующие элементарные преобразования: «сущность → сущность», «отношение → отношение», «сущность → отношение», «отношение → сущность».

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

При выполнении преобразования «сущность → сущность» ee: EntL → EntR необходимо для каждого вхождения в исходную модель экземпляра сущности левой части правила EntIL создать в целевой модели новый экземпляр сущности правой части правила EntIR и выполнить заданные правила преобразования атрибутов. При этом созданный экземпляр сущности будет иметь то же имя, что и найденный по паттерну экземпляр сущности.

Для выполнения преобразования «отношение → отношение» rr: RelL → RelR сначала необходимо в исходной модели найти все экземпляры сущностей RelIL.SEI и RelIL.TEI, которые соединяет экземпляр отношения RelIL, далее для каждого вхождения таких пар экземпляров сущностей следует найти их образы в целевой модели fe(RelIL.SEI), fe(RelIL.TEI) и провести между ними экземпляр отношения из правой части правила RelIR. После этого следует выполнить правила преобразования атрибутов.

При выполнении преобразования «сущность → отношение» er: EntL → RelR для каждого вхождения в исходную модель экземпляра сущности левой части правила EntIL необходимо найти в этой модели вершины EntIS, EntIT, смежные с этим экземпляром сущности. Обозначим через Source и Target образы этих вершин в целевой модели. Для каждой пары вершин Source, Target в целевой модели необходимо провести экземпляр отношения RelIR. Далее следует выполнить заданные правила преобразования атрибутов.

Трансформация «отношение → сущность» re: RelL → EntR преобразует найденный в исходной модели экземпляр отношения паттерна RelIL в экземпляр сущности целевой модели EntIR. При выполнении преобразования для каждого вхождения экземпляра отношения левой части правила в исходную модель необходимо в целевой модели создать экземпляр сущности EntIR, выполнить заданные правила преобразования атрибутов. Имя экземпляра сущности EntIR будет совпадать с именем экземпляра отношения RelIL. На следующем шаге следует для каждого вхождения в исходную модель экземпляра отношения левой части правила найти в этой модели экземпляры сущностей RelIL.SEI, RelIL.TEI, соединяемые этим экземпляром отношения. Далее необходимо создать экземпляры отношений, соединяющие экземпляр сущности EntIR с вершинами Source и Target, которые являются образами вершин RelIL.SEI и RelIL.TEI в целевом графе, с сохранением направления экземпляра отношения RelIL.

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

Заключение

Рассмотренные в статье алгоритмы трансформации визуальных моделей, реализованные в системе MetaLanguage, позволяют выполнять горизонтальные преобразования моделей, описанных с использованием одного визуального языка моделирования в иную текстовую/графическую нотацию. Трансформатор предоставляет возможность не только генерировать код на целевом языке программирования на основе моделей, созданных пользователем с использованием предметно-ориентированных языков, но и выполнять преобразование этих моделей в стандартные нотации с целью их экспорта в сторонние системы для дальнейшей обработки, например, для проведения имитационного моделирования. В работе [2] приведен пример описания и выполнения трансформаций моделей систем массового обслуживания, выполненных с помощью предметно-ориентированного языка имитационного моделирования, в код на языке GPSS.

Работа подготовлена при финансовой поддержке РФФИ (проекты № 12-07-00763-а, № 14-07-31330-мол_а).

Рецензенты:

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

Румянцев А.Н., д.ф.-м.н., профессор, генеральный директор ООО «Информационные бизнес-системы Пермь», г. Пермь.

Работа поступила в редакцию 27.01.2014.