图转换语言中的设计模式与习惯用法的应用

理论计算机科学电子笔记127（2005）181-192www.elsevier.com/locate/entcs图转换语言中的可重用习惯用法和模式阿蒂拉·维占约2Zsolt卡尔马冯世Anantha NarayananGabor Karsai范德比尔特大学软件集成系统美国田纳西州纳什维尔，邮编37235摘要基于图转换技术的软件工程工具正在变得可用，但由于缺乏习惯用法和设计模式，它们的实用性有所降低。惯用法和设计模式为软件工程中反复出现的设计问题提供了原型解决方案，但它们的使用可以很容易地扩展到使用图转换系统的软件开发中。 本文简要介绍了一种简单的图形转换语言GReAT，展示了在模型转换的上下文中出现的典型设计问题是如何使用它的构造来解决的。 这些解决方案类似于软件设计模式，作为更完整的收藏的起点保留字：图形转换，设计模式。1介绍图重写和变换（GRT）[4]的实际应用一方面取决于数学上有充分依据但易于使用的工具的存在，另一方面取决于实际工程经验和有关技术使用的知识。随着模型驱动架构（MDA）[3]的到来，GRT即将成为一种可以在行业中广泛使用的技术虽然已经第1aditya@isis.vanderbilt.edu2viza@isis.vanderbilt.edu1571-0661 © 2005 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2004.12.035182A. Agrawal等理论计算机科学电子笔记127（2005）181虽然已经开发了大量GRT工具[13，14，17，18]，但在实际开发项目中使用的工具很少，而且关于这些工具的使用，积累和记录的在MDA的视野中，应用于软件设计过程中产生的工件的转换是软件设计过程中不可或缺的重要组成部分。符号过程。由于这些转换必须在设计模型（在最一般的意义上是类型化的多重图）上执行，因此GRT技术是适用的。一种用来编写图形转换程序（从而实现模型转换）的语言应该有一个定义良好但简单的语法和语义。然而，在模型转换中有一些常见的重复任务不应该直接由语言支持。相反，它们应该作为有良好文档记录的、可重用的习惯用法和设计模式提供，以解决反复出现的设计问题。两者之间的区别在于习惯用法仅限于应用程序领域，而设计模式是独立于领域的。在本文中，首先，我们描述GReAT，一个可视化的转换语言，支持显式顺序图转换和重写操作。接下来描述了两个独立于领域的设计模式，然后描述了一个重要的习惯用法。最后一节讨论了相关的和未来的工作。2伟大用 于 演 示 设 计 模 式 和 id-iom 的 转 换 语 言 是 图 形 重 写 和 转 换 语 言（GReAT）[7，9]。GReAT基于图文法和变换的理论工作[4，5，6]，属于实用图变换系统集，如AGG[14]，PROGRES[13]，FUJABA[17]和VIATRA[18]。GReAT可以是分为三个部分：（1）领域规范和异构转换，（2）图形转换语言，和（3）控制流程语言。在图转换程序中，节点和边是有类型的，这些类型形成了一个类型系统，我们称之为域。AGG中的PROGRES模式和类型图是用于指定图域的专有格式。我们选择UML [1]类图和对象约束语言（OCL）[2]来进行这样的规范，因为它是标准化的，并且至少与模式和类型图一样具有表达性。UML以前曾在FUJABA中用于领域规范，而类似MOF的模型图已在VIATRA中使用。在实际的图转换程序中，需要处理多个域以及横切域的关联图1（a）A. Agrawal等理论计算机科学电子笔记127（2005）181183(a)分层数据流（b）平面数据流Fig. 1. 元模型HDF和FDF图二.引入交叉链接的元模型显示了一个UML类图，表示层次数据流网络（HDF）的域，图1（b）表示一个非层次数据流语言（FDF）。HDF和FDF将在后面作为示例在本文中，图变换被定义为在同一域内操纵图的变换，而图重写被定义为两个不同域之间的映射。GReAT的一个设计挑战是为两者提供统一的语法和语义。通过允许用户通过定义临时顶点和边类型来组成源和目标元模型来解决这个问题，这些顶点和边类型可以跨越多个域，并且仅在转换期间使用。例如，图2显示了一个元模型，它定义了HDF和FDF之间的关联/边。通过使用临时交叉链接组成域，我们能够将不同的域连接在一起，以形成包含所有域和交叉引用的更大的异构域。这种方法类似于VIATRA中的参考节点和边[18]。GReAT的核心是图形转换语言。 它的灵感来自于许多以前的作品，如[4，5，6]。它定义了基本的转换实体：产生式/规则。产生式包含一个模式图，其中每个模式对象：一个顶点（或一条边）符合一个类型：来自元模型的一个类（或一个关联）。 每个模式对象都有一个属性来指定它在转换中扮演的角色：（1）绑定：对象仅用于匹配图中的对象。(2)delete：对象用于匹配对象，但是一旦计算出匹配，对象就会被删除。 (3)new：在计算匹配之后创建新对象。规则的执行包括匹配每个标记为bind或delete的模式对象。的184A. Agrawal等理论计算机科学电子笔记127（2005）181图三. 带有模式、防护和属性映射模式匹配器将返回给定模式图的所有可能匹配和主机图。然后，对于每个匹配，删除标记为删除的模式对象，然后创建标记为新保护是由OCL约束指定的先决条件（参见图3）。在应用动作之前，将在比赛中对后卫进行评估。“属性映射”（AM）是一个过程规范，用于为新创建的对象的属性提供值和/或修改现有对象的属性，并在应用转换后执行。在图3中，模式图中的每个对象都引用异构元模型中的一个类，并且应该与图对象相匹配，该图对象是元模型实体。新操作用一个勾号（NewChild）表示，删除用一个“叉”号表示。我们的动作规范类似于Groove [20]中的橡皮擦和创造者，或者类似于FUJABA [17]中标记为销毁和创建的图表元素。GReAT有一个建立在图形转换语言之上的高级控制流语言，具有以下结构：（1）旋转和（2）排序[8]。旋转是一种优化技术，它为一组模式对象提供到宿主图对象的初始绑定。这有效地将模式匹配的搜索空间限制为从初始绑定的上下文开始。在GReAT中，端口用于支持旋转（参见图3中的In和Out图标）。输入端口向模式匹配器提供初始匹配，而输出端口用于从规则中提取图形对象，它们可以被传递到下一个规则。因此，规则对数据包进行操作，数据包被定义为（端口，主机图对象）对的集合规则的显式排序和高级控制流程语言允许精确控制转换。控制流语言支持以下特征：（1）排序（规则以指定的顺序触发）（2）非确定性（“并行”规则的执行顺序A. Agrawal等理论计算机科学电子笔记127（2005）181185case（一个在控制队列路径之间进行选择的分支结构）。排序用于指定一组转换规则的执行顺序。例如，图5示出了规则的序列，故事图[19]在FUJABA有一个相似的测序结构图5中还显示了层次结构，其中上述规则都包含在称为“CollectPrimitives”的复合规则中。测试/用例构造用于在不同的执行路径之间进行选择。图10显示了一个名为“TestProxyExistence”的测试关于这些结构的详细讨论请参考[7]，关于语言的形式语义请参考[9]。3可重用图转换的模式和习惯用法每个转换模式/习惯用法都将以统一的方式描述，并具有以下结构：（1）动机：一个问题，在需要模式的地方出现。(2)适用性：模式适用的一般问题类别。（3）结构：模式的抽象具体化(4)优点：应用模式的优点。(5)已知用途：a已知要应用模式的一组转换。(6)限制：模式适用性的一组限制虽然这些设计模式适用于各种各样的转换，一个单一的激励性的例子来证明需要的模式：分层数据流（HDF）的分层数据流（FDF）表示。在图1（a）中，HDF的元模型已经被呈现为具有捕获数据流行为的原语和仅用于封装其他组件的复合物。目的是将HDF的树结构转换为FDF表示（参见图1（b）），同时保留数据流连接。一个简单的算法如下：（1）收集所有的原语节点并将它们复制到FDF，（2）跟踪从每个原语中的每个端口到相应的目标原语端口的数据流连接，（3）用FDF中的单个数据流关联来替换该跟踪3.1叶收集器模式动机：在HDF重定向算法的步骤1中，要求是收集层次结构中的所有叶节点例如，在图4中，给定根186A. Agrawal等理论计算机科学电子笔记127（2005）181见图4。 HDF模型图五. 在HDF我们需要找到所有的叶基元P121，P11，P21，P22。 图5显示了收集给定HDF层次结构中所有原语的规则。顶级规则“CollectPrimitives”，作为输入获取 等级制度它调用“HasComponents”来收集所有直接子元素，并在每 个 子 元 素 上 递 归 调 用 “CollectPrimitives” 。如 果 输 入如 果“CollectPrimitives”是一个原语，则“IsPrimitive”规则将成功，其输入将被传递到输出。在递归结束时，所有原语都将在顶层调用的输出中可用适用性：从一个起始对象开始，需要遍历特定类型的定向关联，直到到达叶子对象。叶对象被定义为不能进一步遍历关联的对象结构：此模式的参与者如图6所示。The “GetDirectNeighbors”“IsLeaf”规则识别输入对象是否是叶子。 这是通过模式基数等于零的模式（参见“IsLeaf”中的箭头）。模式边的基数为零意味着两个对象之间不应该存在这样的边。在其他转换语言中，这被称为负模式边缘。这个“IsLeaf”的实现优点：遍历方案和叶识别是独立的彼此的叶收集和叶处理也可以独立地变化A. Agrawal等理论计算机科学电子笔记127（2005）181187见图6。 Leaf Collector模式已知用途：（1）分层状态机到有限状态机的转换，以获得所有的叶状态，（2）Matlab从Simulink端口开始查找数据流连接链末端的所有端口。例如，在图4中，给定端口O121，它将找到O21和O221。(3)嵌入式系统建模语言（ESML）[15]到任务网络架构（TNA）的转换，以收集所有分层任务。限制：只能应用于没有循环的图形3.2传递闭包动机：在FDF中，需要执行数据依赖性分析。对于这样的分析，需要找到数据流连接的传递闭包[16]。图7显示了计算FDF上传递闭包的转换。该算法的第一步是找到那些没有任何传入关联（源）的FDF组件的所有邻居。这在“FindSource”中使用零基数关联模式实现。然后，下一个邻居 被 用 作“TransitiveClo-sureStep”的 初 始 值。 在 一 个“TransitiveClosureStep”中，给定一组组件，找到它们的所有下一个和前一个邻居。如果前一个邻居与下一个邻居之间没有关联，则在它们之间创建新的关联。The “TransitiveClosureStep” is called again with the set ofnext neighbors as适用性：当需要计算图的传递闭包结构：在一般情况下，关联的类型和顶点的类型可以改变以适应问题的要求已知用途：已用于在ESML模型[15]和其他分布式和并行系统上执行可达性分析。限制：只能应用于有向无环图（dag）。可以采取预处理步骤将任意图转换为dag，方法是188A. Agrawal等理论计算机科学电子笔记127（2005）181图7.第一次会议。寻找传递闭包的转换规则图8.第八条。通用分布式系统的UML类图将所有强连通分量简化为单个顶点。3.3代理生成器习惯用法本节将讨论代理生成器设计习惯用法，它也是可重用的，但仅限于特定的问题域。动机：图8显示了一个基于分布式服务的系统（DSBS）的模型。分布式系统（System）由多个处理器（Processor）组成，每个处理器承载不同的对象（Object），对象可以向其他对象请求服务（Request对象可以是本地处理器上的远程主对象（Master）的代理（Proxy），这种关系可以由两个对象之间的关联Distribute在这样的分布式系统中，为了减少网络传输，以及抽象的网络通信对象的相互作用，我们可以使用代理在每个处理器上代表远程组件本地。这种优化可以通过在对象网络上使用静态分析方法识别对代理的需求，然后自动生成它们来执行。图9显示了识别代理需求并创建它们的转换。对于每一个主机，客户端对，这样客户端需要在远程主机上发出请求，第一步是确定主机是否在客户端的处理器上有代理。这是在“TestProx- yExistence”中完成的。如果它成功地找到了一个代理，那么调用“AssociateWithProxy”，这将把对主服务器的请求替换为对本地代理的请求。否则，A. Agrawal等理论计算机科学电子笔记127（2005）181189图9.第九条。代理生成器习惯用法的转换规则见图10。测试代理存在(a)代理规则（b）关联代理规则见图11。 创建和关联代理在客户端的处理器上步骤1. 确定本地处理器上的代理是否存在：这是使用图10中描述的名为“TestProxyExistence”的测试来实现的。它有两种情况，如果否则调用190A. Agrawal等理论计算机科学电子笔记127（2005）181步骤2.创建代理（可选）：在如图11（a）所示的规则“代理代理”中，给定主服务器和客户端，在客户端的本地处理器上创建代理以及与主服务器的Distributeassociation。新创建的代理、其对应的主代理和客户端被传递到步骤3.迁移服务：在如图11（b）所示的规则“AssociateWithProxy”中，给定主服务器和相应的代理服务器，客户端对主服务器的请求被客户端对代理服务器的请求替换。适用性：在任何需要抽象和优化远程交互的分布式系统中。这些交互可以是服务/请求、事件源/接收器和数据流交互。该习惯用法可用于在分布式对象网络上执行静态分析以进行优化，也可在需要远程交互时在运行时使用结构：在一般情况下，成语有三个不同的任务。（1）给定一个主客户端对，测试代理是否存在（2）如果存在代理（3）如果代理不存在，首先创建一个代理并将其与主服务器链接，然后删除客户端-主服务器关联并创建客户端-代理关联。优点：该模式将代理识别、代理创建和代理关联步骤分开，这样每个步骤都可以独立修改已知用途：用于嵌入式系统建模语言[15]。局限性：代理生成器习惯用法需要客户机和主服务器对，两者之间有一个4相关工作软件设计模式自20世纪90年代初就被记录下来了[10]被认为是设计模式的开创性工作。图转换已被提出来自动化的应用程序软件设计模式。[11]描述了一种使用图查询和图重写规则来应用软件设计模式的方法。在[12]中，讨论了图重写系统（GRS）对设计静态方面的复杂转换的指定和执行的适用性。文中的例子说明了如何GRS可以用来实现MDA提出的这些方法试图自动化软件设计模式的应用。而本文试图发现的转换设计模式，是常见的转换问题的解决方案，可以用来设计图转换。A. Agrawal等理论计算机科学电子笔记127（2005）1811915结论我们已经展示了设计模式的思想如何应用于图转换程序的上下文中我们使用两个（独立于域的）设计模式和一个（依赖于域的）习惯用法来演示这个概念。我们相信，以这种方式记录设计模式对于图转换的实践者是有用的，我们呼吁社区为这一知识体系做出贡献在这一领域的进一步研究可能会导致设计模式和习惯用法的全面编译，这些设计模式和习惯用法可用于培训使用图转换技术的开发人员。6确认DARPA/IXO MOBIES计划（F30602-00-1-0580）和NSF ITR：“Foundations for Embedded and Hybrid Systems” has supported, in part, theactivities described in this引用[1] 朗博岛Jacobson和G. Booch，[2] 对象管理组，对象约束语言规范，OMG文档格式/01-9-77。2001年9月[3] http://www.omg.org/mda/“The[4] Grzegorz Rozenberg，Pte. 有限公司、一九九七年。[5] 布洛斯坦·D S chürrA.，“Computing with Graphs and Graph Rewriting”，TechnicalR e port AIB 97-8，Fachgruppe Informatik，RWTH Aachen，Germany。[6] H. Gottler，“Attributed graph grammars for graphics”，H. Ehrig，M. Nagl和G. Rosenberg，编辑，Graph Grammars and their Application lo Computer Science，LNCS 153，第130- 139页142，Springer-Verlag，1982.[7] Agrawal A. Karsai G.，史方：“Graph Transformations on Domain-Specific Models”, Technicalreport[8] Vizhanyo A.，Agrawal A.史方：[9] Karsai G.，Agrawal A.施F，洒J.：“On the Use of Graph Transformations for the FormalSpecification of Model Interpreters”, Journal of Universal Computer Science, Special issue[10] Erich Gamma、Richard Helm、Ralph Johnson和John Vlissides：设计模式：元素Addison-Wesley，1995年[11] Angsgar Radermacher通过图形转换工具支持设计模式。AGTIVE 1999：pp. 111-126192A. Agrawal等理论计算机科学电子笔记127（2005）181[12] Alexander Christoph：NetObjectDays，NODe 2002，Erdom，德国，2002年10月7-10日pp. 七十六至八十六岁[13] A. 很好。PROGRES：一种基于图形语法的VHL语言 InPr oc. 第四个I NT。图文法及其在计算机科学中的应用，LNCS第532期，第641-659页Springer-Verlag，1991.[14] Taentzer，G.：AGG：一个代数图变换的工具环境，工业相关图变换的应用程序，Kerkrade，荷兰，LNCS，Springer，2000年。[15] G. Karsai，S.尼马湾艾伯特，D。 点整打 “A Modeling Language and its Supporting Tools for[16] Kurt Mehlhorn，“Graph algorithms and NP-completeness”，Springer-Verlag New York，Inc.，美国纽约州纽约市，1984年。[17] 联合 Ni ckel和J. Niere和A. Zu？ndorf，“Toldemonstration：TheF UJABAe n vironmen t”，Proc.ICSE：The 22nd International Conference on Software Engineering，Limerick，Ireland，ACM Press，200.[18] D. V'o和G. V和A。Pataricza，《设计视觉语言的自动转换》，第44卷，Elsevier，第205-227页，计算机编程科学，2002年[19] T. Fis cher和J. Niere和L. 陈文辉，“一种基于UML和Java的图形转换语言”，《图形转换的理论与应用》，北京大学出版社，1998年[20] A. Rensink，Groove模拟器：状态空间生成工具，AGTIVE，计算机科学讲义，Springer，2003年。