Диссертация (Методы и средства разработки графических предметно-ориентированных языков), страница 7

Динамические языки, в свою очередь, характеризуются формализмом,используемым для определения их семантики, поскольку для них применимособственно понятие «вычисление». Наиболее типично применение формализма,являющегося вариантом сетей Петри (граф, по которому могут перемещатьсятокены исполнения, подробный обзор сетей Петри можно найти в [55]), либо7Entity-Relationship34диаграмм состояний (наиболее известный вариант которых — диаграммы Харела [25], используемые в языке UML).Языки, использующие формализмы, сводящиеся к сетям Петри, имеют двеважные с практической точки зрения подкатегории.

Первая подкатегория языковв качестве токенов использует данные, которые обрабатываются программой.Каждый узел языка исполняется, когда имеет на всех своих входах данные,нужные ему для работы, и результатом его исполнения является набор данных,которые рассылаются на выходы блока. Блоки, одновременно имеющие все данные, могут исполняться параллельно. Такие языки мы будем называть языками спроцессом вычислений, ориентированным на поток данных. Они широко распространены среди инженеров и математиков, примерами сред, реализующих такойподход, являются среда математических расчётов Matlab/Simulink [88] и средамоделирования физических приборов LabVIEW [56].

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

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

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

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

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

Графовые языки обычно имеют выделенную логическуюмодель, неграфовые языки имеют тенденцию быть существенно графическими,однако бывают исключения. Например, автором данной работы был реализованязык описания конечного автомата, распознающего жесты рукой для системыкомпьютерного стереозрения. Там состояния было удобно связывать с физическим расположением руки в пространстве, и от геометрического расположенияна диаграмме элементов языка зависела генерация правил перехода. Язык былграфовым (узлами были состояния автомата, связями — переходы), но при этомсущественно графическим.Отметим, что языки с выделенной логической моделью позволяют использовать один и тот же элемент логической модели на разных диаграммах илив разных местах одной диаграммы. Если редактор для этого языка позволяет,можно редактировать логические свойства элемента у любого из его графических«образов», и все остальные «образы» получат эти изменения автоматически.1.6.

Способы формализации визуальных языковЧасто визуальные языки создаются с целью применения каких-либо формальных методов анализа или трансформации создаваемых с их помощью диаграмм, поэтому оказывается полезным их формальное математическое описание.36Такая формализация позволяет использовать готовые теоретические результатыи инструменты, созданные для выбранного формализма, кроме того, позволяетуточнить описание языка и проверить его на наличие скрытых ошибок.Выбор математического формализма для описания языка зависит от целейформализации, но можно выделить общую схему, применяемую для визуальныхязыков [21, 27]:• формально описывается синтаксис языка;• выбирается математический формализм, описывающий семантику языка;• строится отображение из синтаксиса в семантику.Вопросы формального описания семантики хорошо освещены в литературе.Классическим примером языка с формальной операционной семантикой являются уже упоминавшиеся здесь сети Петри [55], этот пример интересен тем,что формализация семантики позволила получить нетривиальные и практическизначимые результаты с использованием методов линейной алгебры и теорииграфов ( [9, 17, 38, 101]).

Общий подход к определению операционной семантикивизуального языка описывается в [14], также распространён подход, при которомоперационная семантика описывается с помощью текстовых языков программирования [71].Рассмотрим подробнее вопрос формализации синтаксиса языка. Наиболеераспространены графовые визуальные языки, в частности потому, что онипозволяют использовать средства и методы теории графов. Подробный обзорразличных формализмов теории графов, пригодных для формализации синтаксиса языка, приводится в приложении А работы [137].

В качестве альтернативыследует упомянуть работу [18], где в качестве базы для визуальных языковпредлагается использовать формализм теории категорий. Кратко опишем математическую модель графовых визуальных языков, следуя [137], которая будетприменяться в данной работе.Графом называется пара (V, E) из конечного множества вершин V и бинарногоотношения E ⊆ V × V . Пара (v, w) ∈ E называется дугой графа, v — началом,w — концом дуги. Накладывая различные ограничения на E, можно получитьразные виды графов, например, в случае, если отношение E симметрично (то37есть (v, w) ∈ E ⇒ (w, v) ∈ E), граф называется неориентированным.

В случае,если E не обязательно симметрично, граф называется ориентированным, то естьнеориентированный граф — это ориентированный граф, у которого отношениеE симметрично. Часто полезно сопоставить вершинам и дугам некоторую дополнительную информацию, поэтому вводится помеченный граф, как шестёрка(V, E, LV , MV , LE , ME ), где V и E — вершины и дуги графа соответственно,LV и LE — конечные множества меток вершин и меток дуг соответственно,MV : V → LV — функция разметки вершин, ME : V × V → LE — функцияразметки дуг.Появление меток на дугах позволяет отличать дуги друг от друга не толькопо началу и концу, поэтому оказывается полезным модифицировать определениеграфа так, чтобы две вершины могли связывать несколько дуг.

Ориентированныммультиграфом называется четвёрка (V, A, s, t), где V — это конечное множествовершин, а A — конечное множество дуг, s : A → V и t : A → V — функции,сопоставляющие дугам из A вершину-начало и вершину-конец соответственно.Над мультиграфами также может быть определена разметка: помеченный ориентированный мультиграф — это восьмёрка (V, A, s, t, LV , MV , LA , MA ), где V ,A, s, t определяются так же, как в ориентированном мультиграфе, LV и LA —конечные множества меток вершин и дуг соответственно, MV : V → LV иMA : A → LA — функции разметки, ставящие вершинам и дугам в соответствиеих метки.Ещё одним важным обобщением понятия «граф» являются гиперграфы, гдерёбра могут связывать не две вершины, а любое подмножество множествавершин, что удобно для представления n-арных связей в визуальных языках.Гиперграф — это пара (V, E), где V — конечное множество вершин, E ⊆2V — множество гиперрёбер.

В некотором смысле парными к гиперграфамявляются метаграфы — обобщение графов, в котором ребро может связыватьдва подмножества множества вершин (то есть обобщается не понятие ребра, какв гиперграфе, а вершины). Метаграф — это пара (V, E), где V — конечноемножество вершин, E ⊆ 2V × 2V : ∀(Vi , Vj ) ∈ E Vi ∩ Vj = ∅ — множестворёбер.Наконец, ещё одним интересным обобщением понятия «граф» являются hiграфы, предложенные Д.