图形转换语言的提高性能和可用性的方法及其比较

理论计算机科学电子笔记152（2006）207-222www.elsevier.com/locate/entcs提高图形转换语言的可用性Attila Vizhanyo1，Sandeep Neema，Feng Shi，Daniel Balasubramanian，Gabor Karsai范德比尔特大学软件集成系统美国田纳西州纳什维尔，邮编37235摘要使用图转换技术实现的模型转换工具通常被期望提供高性能。出于这个原因，在图形重写和转换（GReAT）语言中，我们支持两种技术：预先绑定选定的模式变量和显式排序的转换步骤，以提高转换引擎的性能。当应用于实际情况时，我们认识到我们的方法有三个缺点：（1）没有支持 为了在另一个远距离步骤中方便地重用一个重写步骤的结果，（2）缺乏用于对模式匹配的结果进行排序的排序能力，以及（3）缺乏对多个模式匹配的结果的区分合并。在本文中，我们简要地突出了GReAT的相关功能，描述了三个激励性的例子来说明问题，介绍了我们的解决方案：对语言的新扩展，并将这些方法与其他语言进行了比较。保留字：模型转换、图形转换、可用性1引言模型转换工具应该可靠地工作并提供高性能。当模型转换用于工具集成时（如[1]），或者当它用于交互式工具中以帮助建模者时，我们希望转换能够快速执行。另一方面，模型转换的开发者（“程序员”）也期望高性能的模型转换1viza{，sandeep，fengshi，daniel，gabor}@isis. vanderbilt. e度1571-0661 © 2006 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2005.10.026208A. Vizhanyo等人/理论计算机科学电子笔记152（2006）207来自语言的要求：他们希望以简洁但可理解的形式来表达复杂的转换，而不必处理低级实现细节，也不必依赖于转换语言的构造在第一代GReAT（图重写和变换）语言中，我们提供了许多功能来解决第一个问题，而牺牲了第二个问题。性能的改进是使用以下技术：1。为了减少在宿主图中找到匹配子图的搜索，我们支持将选定的图形模式元素预先绑定到宿主图中的已知节点。这些预先绑定的元素将搜索变为局部图搜索问题。此外，由重写规则创建的预绑定元素和新元素也可以在后续重写规则中重用二、为了消除在执行时对规则激活的搜索，我们显式地对重写规则进行排序。通过将上面讨论的绑定主机图元素从一个规则传递到另一个规则来指定排序。特殊的规则，称为3.第三章。为了进一步提高性能，我们用标准编译器编译的过程语言（C++）生成可执行代码[3]。技术1和2将在以下部分中描述，其详细描述GReAT语言的语义虽然这些技术为我们提供了一种语言，在这种语言中，我们可以实现具有可接受性能的转换，但我们在实践中发现了许多缺点本文将介绍三个激励性的例子，说明问题是什么，以及我们对语言所做的改进，以解决这些问题和语言改进的实现这之后是与相关工作进行了简短的比较，并进行了总结和结论。2 GReATGReAT适用于模型转换的形式化规范，其中UML类图用于表示转换的输入和输出模型的抽象语法模型的抽象语法定义了它的建模概念、它们的关系和它们的完整性约束[8]。我们把UML类看作类型图的节点[9]，把这些类之间的各种关联看作图的边本文只解释了必要的语言结构，[4]描述了完整的方法和支持工具。GReAT的操作语义在[5]中正式定义讨论了图变换技术在模型变换中的适用性。A. Vizhanyo等人/理论计算机科学电子笔记152（2006）207209信息问题可以通过将模型看作顶点和边标记的多图来理解，其中标签引用类型图中的如果我们用图表示模型，那么图可以被认为是对象网络，其“模式”使用UML类图表示。UML类图可以扮演一个图形语法的角色，因为它们可以描述所有可以用域构造的因此，将模型转换问题表述为图转换问题是合理的GReAT中的模型转换表示为显式排序的基本重写操作，称为产生式或规则。产生式包含由模式顶点和边组成的模式图。GReAT使用UML类图符号来指定模式的顶点和边。GReAT规则中的每个模式元素都可以扮演以下三种角色之一：绑定、删除或重新创建。角色指定在转换过程中如何使用元素。规则的执行包括匹配每个标记为Bind或Delete的模式对象模式匹配器将返回在宿主图中找到的给定模式的所有可能匹配的然后根据可选的保护条件评估匹配，并且丢弃保护评估为假的匹配然后，对于每个满足保护条件的匹配，从图中删除标记为Delete的图对象最后，图形对象的属性可以通过可选的AttributeMapping（AM）规范进行操作属性映射通过定义良好的C++API使用对图形对象的编程访问考 虑 图 1 所 示 的 简 单 规 则 。 “Container” 具 有 Bind 角 色 ， “LP” 和“Container/LP”组合具有Delete角色，而“Inport”和“Container/Inport”组合具有Bind New角色。此规则的语义是：查找所有接下来，评估警戒条件。假设这个条件是“Container.name == LP.name”。因此，只有“LocalPort”的名称与Container的名称相同的匹配才会通过守卫，其余的匹配将通过守卫。被丢弃最后，如引言中所述，GReAT支持将选定的图形模式元素预绑定到主机图形中的已知节点这为规则提供了其模式的初始部分匹配，这大大减少了搜索空间。在形成转换的输入接口的输入端口的帮助下，210A. Vizhanyo等人/理论计算机科学电子笔记152（2006）207图1.一、GReAT中的一个简单规则步类似地，输出端口可用于将匹配的或新创建的对象传递给后续规则。对于要应用于宿主图的转换规则，必须将图对象提供给规则的每个输入端口;如果没有对象提供给规则在指定涉及多个域（即多个不相关的类型图）的转换时，通常需要将不同域的对象相互关联。 GReAT通过允许用户指定交叉图来支持属于不同域的UML类之间的关联的指定。然后可以创建和操纵这种跨域的关联（在GReAT中称为“交叉链接在执行转换时，就像普通的关联一样。为了说明端口和交叉链接的使用，请考虑图2所示的规则。(Here，我们假 设 UML 类 “LocalPort” 和 “Transmitter” 属 于 不 同 的 域 。 ） In1 用 于 为“LocalPort”提供初始绑定，In2用于为“Actor”提供初始绑定。换句话说，当规则触发时，所选择的然后，该规则查找“Actor”中包含的所有最后，匹配的GReAT中的数据流还暗示了规则的执行顺序，如下所示。如果RuleA的输出端口连接到RuleB的输入端口，则RuleA必须在RuleB之前执行。每个规则可以有任意数量的端口，每个端口都提供有来自（可能是各种）源的图形对象。如果一个源规则为目标规则的输入端口提供对象，则它必须为目标的所有输入端口提供对象。为了管理转换的复杂性，GReAT提供了A. Vizhanyo等人/理论计算机科学电子笔记152（2006）207211图二. 输入端口和交叉链路用户可以使用更高级别的结构，如分层规则和控制结构。高级规则可以通过组合一系列原始规则来创建。GReAT中有两种高级规则这两者的区别在于，Block将所有输入传递给第一个包含的规则，由第一个规则创建的输出传递给第二个规则，依此类推。ForBlock将一个输入一直传递到其包含的规则，然后传递下一个数据包，依此类推。3全球集装箱如上所述，GReAT的控制流语言指定了初等变换步骤的执行顺序。转换步骤总是从初始上下文开始模式匹配。通过上下文，我们意味着一些模式变量到主机图顶点的预绑定。这一背景（即初始绑定）在转换期间经由端口从一个规则传递到另一个规则，类似于过程语言中的参数传递这种方法的主要缺点是，程序员需要通过几个规则指定上下文，即使上下文实际上只在一个远程的、不相邻的步骤中使用。为了简化开发，我们引入了全局容器的概念转换的输入和输出驻留在容器中，这些容器保存输入和输出图的对象和链接这些容器是在转换开始时选择的，每个生产都匹配/删除/创建其中的对象这些隐式容器。我们将全局容器定义为一个对象网络，其“根”对象（包含容器中的全局容器由临时的、非持久的212A. Vizhanyo等人/理论计算机科学电子笔记152（2006）207只在执行转换期间存在的对象。程序员的任务是通过绘制UML类图来定义容器的类型图（type-graph）程序员可以指定任意数量的全局容器的语法，GReAT将管理这些实例（即容器）。可以为全局容器创建任意类型系统，包括定义具有属性，关联等的新类每个容器中唯一的全局可访问对象是根类型的单例实例，称为全局根对象或全局对象。从这个全局对象，可以通过模式匹配到达其他模型对象，其类型可以是新类型，也可以是为转换定义的任何类型图的一部分（包括输入和输出域）。全局容器在大型转换中最有用，因为它们可以消除大部分上下文传递或重复的复杂模式匹配。一个例子是从模型生成代码，其中组件用于对系统的功能分解进行建模。假设转换由几个规则组成，最左边和最右边的规则如图3所示。此外，假设模型包含数百个组件，并且其中一些组件在代码生成时被错误命名（例如，他们的名字以数字开头 我们需要在不同的转换步骤中对这些命名错误的组件集执行多个操作。与组件的总数相比，这些组件的数量可以忽略不计，因此重用模式匹配结果以减少搜索时间是有意义的。然而，指定上下文传递所有几十个规则也是不方便的，特别是当上下文仅在最后一个规则中使用为了避免程序员做过多的工作，可以使用全局容器特性图3中左边的规则，（1）将具有无效名称的组件正确的规则（可能很远，在转换程序的远距离部分）重命名这些选定的组件，以符合目标语言命名约定。请注意，模式匹配通过从“NSRootObject”开始的“NSRootObject-Component”关联查找组件全局容器特性的缺点是，它仍然使用模式匹配来查找以前找到的结果，尽管搜索时间相当短（如我们的示例）。相比之下，上下文传递不需要模式匹配，但它需要内存空间来存储结果。A. Vizhanyo等人/理论计算机科学电子笔记152（2006）207213(a)（b）第（1）款图三. 使用全局容器使用全局容器的主要优点是通过支持在远程步骤中方便地重用一个重写步骤的结果全局容器还有助于从转换中删除超级复杂的细节，以获得更清晰的程序结构。4分选GReAT建立在图形模式指定语言和模式匹配的基础上。模式匹配是确定性的，因为它返回给定模式的所有有效匹配的集合，并且该匹配集合对于给定模式和主机图总是相同的模式匹配是不确定的，因为集合中元素（匹配）的顺序可能在不同的执行之间变化这种非确定性在某些模型转换中是不可接受的，其中某些元素需要以固定的顺序处理回想一下，规则对匹配集执行操作的顺序与模式匹配发现它们的顺序相同。当匹配的确定性顺序是强制性的时，一个示例是解释分层并发状态机，例如MatlabStateFlow的操作语义规定并行（AND）状态从左到右和从上到下进行评估和执行。换句话说，每个并发（AND分解）复合状态具有多个活动子状态，并且负责在执行状态机步骤期间以该特定顺序执行其所有子状态在我们以前的一个作品中，我们已经实现了一个StateFlow到C代码214A. Vizhanyo等人/理论计算机科学电子笔记152（2006）207见图4。 创建国家执行功能GReAT中的生成器[7]。代码生成器本质上为每个StateFlow状态生成一个C对于并发复合状态，生成的C函数负责调用表示子状态的函数例如，假设并发状态“Parent”从左到右、从上到下包含三个那么生成的状态执行函数应该是这样的：void ParentExec（）{ChildA（）; ChildB（）; ChildC（）;}注意，第一个在我们的实现中，我们创建了一个元模型，它捕获了C语言的一个风格化子集的抽象语法然后，在转换步骤中，我们创建代表C代码段的模型元素然后，在后处理步骤中将生成的模型打印成C文本格式图4显示了我们最初的并发状态代码生成解决方案指定的模式找到“ParentState”的所有子项然后，通过评估保护条件来丢弃具有顺序（非并发）复合状态的那些匹配最后，在最后一步中创建状态执行函数定义和引用函数定义的函数调用程序这种模式规范的问题在于，函数调用者是以随机顺序创建的，因此没有任何东西会强制并行状态的正确执行顺序在前面的例子中，如果模式匹配器返回set：{（Parent，ChildB，Prg，ParFunc），（Parent，ChildA，Prg，ParFunc），（Parent，A. Vizhanyo等人/理论计算机科学电子笔记152（2006）207215(a)（b）第（1）款图五. 创建有序状态执行函数ChildC，Prg，ParFunc）}，则生成的代码如下所示：void ParentExec（）{ChildB（）; ChildA（）; ChildC（）;}显然，我们需要根据“ChildState”-s的“Order”属性指定并行状态的顺序。换句话说，我们希望使用一些排序标准对匹配集进行重新排序，例如，根据“ChildState”-s的“Order”属性对匹配进行排序。这个排序步骤应该在模式匹配之后进行，甚至在向量之后进行，这样新创建的对象也可以重新排序。这意味着排序后的匹配只能在后续的转换步骤中使用。排序步骤是离开规则之前执行的最后一个操作。GReAT 程 序 员 可 以 通 过 在 规 则 中 设 置 输 出 端 口 的 属 性 “Com-communication function”来指定排序在图5中，比较函数“StateOrder”用于对并行状态进行排序。compare函数是用过程语言（这里是C++）编写的，它的两个参数是要比较的两个对象。一个比较函数的例子如图6所示.程序员只需要指定函数名和函数体，函数签名就会自动生成。如果需要排序，则对模式匹配产生的匹配进行重新排序和排序，使得由比较函数指定的排序关系在 元 素 之 间 保 持 在 我 们 的 示 例 中 ， { （ Parent ， ChildB ， Prg ，ParFunc ） ， （ Parent ， ChildA ， Prg ， ParFunc ） ， （ Parent ，ChildC，Prg，ParFunc）}被重新排序，产生{（Parent，ChildA，Prg，ParFunc ） ， （ Parent ， ChildB ， Prg ， ParFunc ） ， （ Parent ，ChildC，Prg，ParFunc）}。这些匹配然后在216A. Vizhanyo等人/理论计算机科学电子笔记152（2006）207模板类T>public void run（constT）{&返回lhs.Order（）

下载后可阅读完整内容，剩余1页未读，立即下载