没有合适的资源?快使用搜索试试~ 我知道了~
理论计算机科学电子笔记130(2005)3-21www.elsevier.com/locate/entcs对象模型的抽象等价概念Rohit Gheyi1,2蒂亚戈·马索尼3保罗·博尔巴4伯南布哥联邦大学巴西累西腓摘要对象模型的等价性概念通常过于具体,因为它们假设所比较的模型由具有相同名称的元件形成。这在几种情况下是不够的:在模型重构期间,当使用辅助模型元素时,或者当比较的模型包含不同但对应的元素时。因此,在本文中,我们提出了一个更抽象和语言无关的对象模型的等价概念。当比较模型时,它支持根据需要从名称和元素中抽象出来。我们使用PVS系统来指定和证明我们的概念的属性。它是通过比较简单的模型在合金,一个正式的面向对象的建模语言,但也被应用于推导出一套全面的代数法合金。保留字:等价概念,定理证明,对象模型1介绍在软件开发过程中比较可交付成果是非常重要的。 事实上,有几种方法可以比较 的程序。例如,在维护期间,当我们1 我 们 要 感 谢 Augusto Sampaio 、 Daniel Jackson 和 MIT 软 件 设 计 组 的 成 员 CarlosPombo,以及UFPE软件生产力组的成员,感谢他们的重要评论。这项工作得到了CNPq和CAPES(巴西研究机构)的支持2电子邮件:rg@cin.ufpe.br3电子邮件:tlm@cin.ufpe.br4电子邮件:phmb@cin.ufpe.br1571-0661 © 2005由Elsevier B. V.出版,CC BY-NC-ND许可下开放获取。doi:10.1016/j.entcs.2005.03.0024R. Gheyi等人理论计算机科学电子笔记130(2005)3可能希望用行为上等效的、结构更好的组件来替换给定的组件。 比较设计模型也同样有用,设计模型可以用对象建模语言来表达,比如Alloy [13]或UML类图[1]。然而,目前的对象模型的等价概念通常过于具体。它们假设比较的模型由具有相同名称的元素组成。这在若干情况下是不够的。例如,模型重构改变了模型的结构,但仍然保持了以前的语义。然而,很难验证所得到的模型是否保留了语义,特别是当模型元素被替换为替代结构时。此外,可能会使用辅助模型元素,在计算等值时应忽略这些元素。此外,当相容性模型包含不同但对应的元素时,我们可以很容易地找到直观上等价的模型,但不能基于大多数等价概念来证明。在本文中,我们提出了一个更抽象的等价概念的对象模型。当比较模型时,它支持根据需要从名称和元素中抽象出来。通过依赖于一组选定的相关元素-字母表,以及从相关元素到相应模型(视图)中的等效对应物的映射。此外,这种等价概念适用于任何对象建模语言,因为我们认为对象模型是对象结构和相互关系的抽象描述。我们用原型验证系统(PVS)[18]规范语言对其进行编码,并通过使用PVS证明器[19]正式推导出几个属性这些证明表明了概念相对于对象建模语言的底层语义的独立性在这里,我们通过比较简单的模型来说明我们的等价概念,但它也被应用于推导合金[10]的一组全面的代数定律。它对于其他语义保持模型转换的应用也很有用例如,我们将其用于原子化过程[5],该过程转换Alloy模型以提高Alloy Analyzer工具的分析性能[14]。 我们证明了原子化变换通过应用代数定律和这里提出的等价概念保持了模型的语义[10]。此外,这个概念可以用于正式地导出模型重构,这对于将设计模式[7]引入模型非常有用此外,一个灵活的等价概念可能是有用的,例如,当我们有兴趣验证部分模型是否是等价的。这个概念对于比较组件的规格也很有价值。如果它们是等同的,则一个组件可以被另一个组件替换,R. Gheyi等人理论计算机科学电子笔记130(2005)35在其他地方描述的方法[24]。本文的其余部分组织如下。第二节通过一个例子说明了我们的等价概念背后的主要概念和直觉。第3节概述了PVS系统,在这里使用的形式化和证明有关我们的等价概念的属性。第4节然后形式化等价概念,第5节,其中显示了它的一些属性。下一节讨论相关工作。最后,第7节对本文进行了总结。2激励的例子在本节中,我们使用一个例子来介绍等价概念背后的主要概念和直觉,等价概念在第四、图1描述了银行系统的两个对象模型[15]。 对象模型中的每个框表示一组对象。箭头是关系,指示一个集合中的对象如何与其他集合中的对象相关。例如,标有accounts的箭头指定Bank中的每个对象都与一组Account对象相关。多重性符号的定义如下:!(1)?(零或一)、*(零或多)和+(一或多)。多重符号可以出现在箭头的两端。如果省略多重性符号,则假定为 *Fig. 1. 简化银行系统图1(a)显示了一个模型,说明每个银行与一组帐户直接相关,而图1(b)中的模型建立了每个银行与一个集合相关,集合与一组帐户直接相关。在这里,我们感兴趣的是验证它们是否具有相同的语义,因此,等价的替代设计。通常,考虑到对象模型的语义是一组有效的(满足所有建模约束的)对其集合和关系的赋值(解释),验证一个模型的任何有效解释是否对另一个模型也有效就足够了,反之亦然。6R. Gheyi等人理论计算机科学电子笔记130(2005)3例如,图2(a)显示了图1(a)模型的有效解释。这种解释表示包含两个银行(b1,b2)和两个账户(c1,c2)的银行系统。银行b1与账户c1和c2相关。图2(b)显示了图1(b)模型的有效解释。它具有与图2(a)解释相同的银行和账户,但是银行b1与向量v1相关,向量v1与账户c1和c2相关。图二. 解释这种比较两个模型是否具有相同语义的通用等价概念是有用的,但不够灵活,无法比较具有辅助元素(如Vector)的等价模型,或表示相同概念的不同形式(如图1(a)中的帐户)图1中的模型在直观上是等效的,考虑到银行和账户之间的关系,无论是否存在中间收款,都要保持这种关系然而,这些模型在这个等价概念下是不等价的;例如,图2(a)中对图1(a)中的模型的解释具有分配给帐户的值,与图2(b)中对图1(b)中的模型的解释形成对比,其中帐户没有出现。为了在这种情况下比较模型,我们提出了一个灵活的等价概念。我们的方法比较了两个对象模型的语义只为一些相关的模型元素(集和关系),抽象的值分配给别人。相关元素的集合被称为alpha- bet(alpha-bet)。不在字母表中的名字被认为是辅助的,或者与比较无关。例如,假设该字段只包含Bank和Account名称。如果两个模型对这些名称有相同的解释,那么在这个等价概念下它们被认为是等价的。其他名称,如col,Vector和elems,被视为辅助,因此在相应模型中搜索等效解释时不考虑因此,我们现在可以比较图1中描述的模型,因为两个模型都具有字母表中的所有元素R. Gheyi等人理论计算机科学电子笔记130(2005)37→→然而,有时我们可能会有模型元素,虽然相关,但不能比较,因为它们不是两个模型的一部分。例如,假设我们将帐户包括到。在这种情况下,我们无法比较图1中的模型,因为帐户不是图1(b)中模型的一部分。此外,在重构活动中,某些结构可能已被其他元素替换,即使生成的模型保持原始语义并表达相同的概念。例如,在图1(b)中,accounts不是模型的一部分,但实际上可以表示为col和elems的组合。在这些情况下,我们的等价概念可以考虑一个映射,称为视图(v),建立如何使用另一个模型的元素来解释一个模型的元素视图由一组项组成,例如n exp,其中n是元素请注意,虽然辅助名称的值不进行比较,但它们可以用于为相关名称生成另一种含义在本例中,我们可以选择一个包含以下项的视图:accounts col.elems,其中点运算符表示关系组合。现在我们可以推断这两种模型是等价的。请注意,accounts是根据属于图1(b)中模型的两个名称定义的使用这个项目,我们可以用帐户的值扩展图2(b)的解释视图允许使用其他元素的等效组合来表示相关元素的策略。图三. 口译扩展值得一提的是,两个模型在以下方面可以是等效的:8R. Gheyi等人理论计算机科学电子笔记130(2005)3→一个字母表和一个视图,选择不同的字母表或视图产生不同的概念。例如,如果我们取相同的(Bank,Account,accounts)和v,其中包含以下项:accounts(Bank->Account),其中在这种情况下,这些模型是不等价的,因为它们在某些解释中可能具有不同的帐户值。现在,假设我们取来包含Bank、Account、accounts和col名称。在这种情况下,这些模型不能进行比较,因为在图1(a)所示的模型中不可能提供col的视图表示。我们基于字母表和视图的等价概念更加灵活,因为它在比较模型时支持对名称和元素的抽象通过根据需要选择特定的字母表和视图,开发人员可以为给定的情况选择适当的抽象级别事实上,通常的(具体的)等价概念是我们的概念的一个特定实例,当我们简单地接受一个空视图和一个包含模型中所有名称的字母表时3PVS概述为了指定我们的等价概念,在第4节中描述的,我们需要一种形式化的规范语言,除了允许递归函数之外,至少还允许一阶逻辑此外,额外的功能,例如相对强大的定理证明器功能,以避免容易出错的手动证明,对于实现正确性非常有益。我们选择原型验证系统(PVS),但我们可以用任何其他具有前面提到的功能的规范语言来PVS为正式规范和验证提供了机械化支持[18]。PVS系统由一个规范语言、一个证明器、规范库和几个浏览工具组成。该语言基于简单类型的高阶逻辑。 每个规范都包含一个集合 的理论。每个理论都可以引入类型、变量、常数,也可以引入与理论相关的公理、定义和定理。规范是强类型的,这意味着每个表达式都有一个关联的类型.假设我们想在PVS中对银行系统的一部分进行建模,其中每个银行都包含一组帐户,每个帐户都有一个所有者和一个余额。接下来,我们声明一个名为BankingSystem的理论,它声明了两个未解释的类型(Bank和Person),表示银行和个人的集合,以及表示帐户的记录类型。未解释的类型不对规范的实现强加任何假设,这与诸如int之类的解释类型形成对比,它强加了整数的所有公理。R. Gheyi等人理论计算机科学电子笔记130(2005)39记录类型,如Account,强制假设如果其任何组件类型为空,则它为空,因为结果类型由其组成部分的Carnival乘积给出。所有者和余额是账户的字段,分别表示账户的所有者银行系统:理论开始银行:类型人:类型帐户:类型=[#所有者:人,余额:int#]每个理论都可以使用IMPORTING子句导入其他理论。默认情况下,所有理论都导入Prelude库,该库提供了布尔运算符,集合,等式,实数,有理数,整数和自然数类型及其相关属性[18]。在PVS中,我们也可以声明函数类型。接下来,我们声明两个函数类型(分别是数学关系和函数)。在PVS中有多种形式来声明函数。其中之一是声明其名称、参数和结果类型,例如第一个函数建立每个银行与一组帐户相关。另一种方法是定义相关的映射,如第二个函数,它表示撤回操作。accounts:[Bank -> set[Account]]withdraw(acc:Account,amount:int):Account= accWITH[balance:=(balance(acc)-amount)]balance(acc)表达式表示acc帐户的余额。WITH关键字表示重写运算符。在withdraw函数中,包含WITH操作符的表达式表示具有相同acc所有者的帐户,但余额减去了amount。类似地,我们可以声明一个表示credit操作的函数除了声明类型和函数,PVS规范还可以声明公理、引理和定理。例如,接下来我们声明一个定理,该定理说明当在相同金额的贷记操作之后withdrawCreditTheorem:FORALL定理(根据:Account,amount:int):balance(withdraw(credit(acc,amount),amount))= balance(acc)ENDBankingSystemFORALL关键字表示通用量化器。先前的量化是指一个账户和一个要存入然后取出的金额PVS证明检查器提供了一系列强大的证明命令,可以使用定义和引理进行命题,等式和算术推理。例如,前面的定理可以通过两次应用扩展规则来证明,这在取款和存款函数中扩展了定义这些证明命令可以组合起来形成证明策略[19]。例如,我们可以通过应用grind策略来证明前面的定理,该策略安装了重写和连续重写。10R. Gheyi等人理论计算机科学电子笔记130(2005)3简化。4等值概念在本节中,我们将形式化对象模型的抽象等价概念如第2节所述,我们认为两个模型在字母表和视图方面是等价的。一个字母表包含一组元素名称,一个视图包含一组映射,每个映射将一个名称与一个表达式相关联,如图4中的元模型所述,它可以直接转换为PVS规范。表达式类型表示来自对象建模语言的表达式。见图4。 字母和视图通过对字母和视图的描述,建立了模型间等价的条件。我们认为,两个模型是等价的,如果他们有相同的一套有效的解释,在字母表中的所有名称。如果一个模型不包含相关的名称,它的解释将由当前模型中的有效表达式产生,由视图条目定义。因此,两个模型在字母表和视图方面是等价的,只要视图对两个模型都有效。等价性被简单地定义为相互细化,模视图和字母表,如下所述。等效(m1,m2:模型,a:字母表,v:{ vi:视图|valid(vi,{m1,m2},a)}):boolean = refines(m1,m2,a,v)∧refines(m2,m1,a,v)在下文中,我们使用一些数学符号而不是PVS关键字和函数,以提高可读性。Model类型表示对象建模语言的模型,它服从等价概念。在我们的例子中,它定义了一个Alloy模型。在PVS中,我们可以声明依赖类型[18],例如前面函数中v参数的类型。它确立了该关系仅适用于对于两个模型都是有效视图的v的参数。因此,当所考虑的视图无效时,不比较模型。在下面的章节中,我们解释了模型的有效视图和精化的概念。R. Gheyi等人理论计算机科学电子笔记130(2005)311→→→→4.1有效视图如前所述,视图必须满足某些属性,才能对给定的模型和字母表有效。一个有效的视图必须以明确的形式指出,字母表中不属于所考虑的模型的元素如何用该模型中的替代元素来表达。我们通过使用图5中的示例来解释这一点,该示例说明了图1中描述的两个银行系统的扩展版本之间的等价性。除了每个银行与一组账户相关之外,每个银行还与一组客户相关。此外,每个账户都属于一个客户,有两种账户:支票账户和储蓄账户。图五、扩展银行系统的等价性概念在此示例中,具有闭合头部形式的箭头(例如从ChAcc到Account的箭头)表示子集关系。在这种情况下,ChAcc是Account的子集。 由于这两个子集共享一个箭头,因此它们是不相交的。 如果箭头被填充,则子集耗尽超集,因此超集的成员不存在不是子集之一的成员。在表示银行系统的两个对象模型中,子集形成了一个分区:超集的每个成员都只属于一个子集。有效视图的第一个属性是它不能是递归的。因此,视图的每个项(源目标)不能在目标表达式中引用其源例如,我们不允许在ChAcc AccountChAcc这样的视图中使用项,其中"这种限制是由于视图项必须表示字母表中元素的明确映射,这对于递归项是不可能的,它试图将元素映射到自身。 它 值得一提的是,我们允许包含以下项目的视图:ChAcc Account和AccountChAcc。我们的概念确保每个名称的值必须由单个映射产生,避免相互递归。另一个属性是有效视图只包含映射字母表中名称的项。假设图5中的代理由Bank、Account12R. Gheyi等人理论计算机科学电子笔记130(2005)3−→→−→客户、业主、客户和账户名称。我们不允许ChAcc的映射,因为它不在字母表中,因为它的值不用于比较模型。例如,包含ChAcc Account SavAcc映射的视图(其中"“运算符表示集合差异)在考虑到先前的差异时将无效。请注意,前面描述的有效视图的前两个属性是与模型无关的。hasOnlyItemsForAlphabet(a:Alphabet,v:视图):boolean =附件:项目㈤| source(it)∈ names(a)最后,最后一个属性确定,如下面的PVS函数所述,不在模型中的字母表名称必须由视图映射。因此,我们将能够在模型中产生它们的值。但是,视图必须为该名称和所考虑的模型恰好具有一个有效项,以避免不一致问题。例如,图5中银行系统的右侧模型不包含accounts关系,尽管它存在于前面示例中的字母 表中。考虑一个 具有两个映射的 视图:accounts col.elems 和accounts custs。* *注意,这两个映射都可以用来表示帐户因此,这两个表达式在模型中必须在语义上等价,以保持帐户为了避免这种额外的复杂性,我们确定,对于字母表中所有不在模型中的名称,视图必须只有一个项目可以表达其值。hasMappingsForAlphabet(m:Model,a:Alphabet,v:View):boolean =中文:姓名(a)|n∈/names(m)oneValidItem(n,m,v)我们定义一个项目对于模型是有效的,如果项目的表达式只包含模型中的名称,并且它在模型中必须是良好类型的。观察一个有效视图的这三个属性只包括语法条件;因此自动检查一个视图对于一个模型是否有效是很简单的4.2细化如前所述,当两个模型在一组重要的名称和映射方面相互细化时,它们是等价的然后,我们将我们的精炼概念形式化。给定两个模型m1和m2,我们说m2精化m1,如果对于字母表中的所有名字,对于满足m1语义的每个解释因此,我们认为这些解释对于字母表和视图是等效的,可能抽象名称和元素,如图所示。R. Gheyi等人理论计算机科学电子笔记130(2005)313∈P∀∃下一个refines(m1,m2:Model,a:Alphabet,v:{vi:View |valid(vi,{m1,m2},a)}):boolean=i1:语义(m1)| i2:语义(m2)|equivalentMappings(m1,m2,i1,i2,a,v)每个解释都有一个映射关系,它将名称映射到值,如下面的PVS片段所示。值由Value类型建模。解释:类型=[#map:[名称->设置值] #]语义函数产生模型的所有有效解释,根据使用的对象建模符号定义。此后,满足所有模型约束的解释被认为对该模型有效。如前所述,在refines函数中,两个模型的有效解释仅针对字母表中的名称进行比较。也就是说,两种解释都应该为字母表中的每个名称分配相同的值,如以下函数所示equivalentMappings(m1,m2:Model,i1,i2:Interpretation,a:Alphabet,v:{ vi:View |valid(vi,{m1,m2},a)}):boolean =中文:姓名(a)|mappings(m1,a,n,i1,v)= mappings(m2,a,n,i2,v)但是,当这样一个名称不在其中一个模型中时,它肯定不会被相应的解释映射在这些情况下,我们首先将适当的视图项应用于解释,以获得该名称的间接赋值(扩展解释)。然后,这些值应该与其他解释分配给该名称的值相同,否则它们不被视为等效。这是由mappings函数形式化的,这将在下面描述,并为i解释产生m中的n名称的值。它计算i中n的值,无论它是否属于所考虑的模型。在后一种情况下,该函数在生成n的值之前应用视图。mappings(m:Model,a:Alphabet,n:名称,i:解释,v:{vi:视图|valid(vi,{m},a)}):Value =if(nnames(m))then map(i)(n)elsemap(applyView(i,getViewItem(n,m,v)(n)applyView函数接受一个解释和一个视图项,并产生作为参数接收的相同解释,但具有作为参数接收的项的名称及其值的额外映射它实际上以这样一种方式扩展了一种解释,即它可以直接与另一种解释进行比较。applyView(i:Interpretation,v:ViewItem):Interpretation=iWITH [map:= map(i)WITH [source(v)|-> evalExpression(target(v),i)]]14R. Gheyi等人理论计算机科学电子笔记130(2005)3→→视图的应用程序总是有效的,因为我们假设它对每个模型都有效。因此,对于不属于所考虑模型5等价概念首先,我们使用PVS证明我们的概念是一个等价关系对于固定的字母表和视图(它是自反的,对称的和传递的)。需要强调的是,以下属性与任何对象建模符号无关。为了展示用于证明此性质的定理的实例,以下陈述我们的等价关系是对称的。 为了提高本节定理的可读性,所有泛量化的观点必须对所有涉及的模型都有效。例如,在下一个定理中,v是m1和m2模型的有效视图。equivalentSymmetry: 定理(m1,m2:模型,a:字母表,v:视图)|equivalent(m1,m2,a,v)等价(m2,m1,a,v)在证明了这些基本性质之后,我们利用PVS证明了其他一般性质。这些属性在应用序列时特别有用语义保持模型转换[10],这导致了一系列等效模型。这可能是必要的,例如,将设计模式[7]引入模型。在这些情况下,有时我们可能会重构模型,并且只在一段时间后才注意到我们没有选择适当的字母表和视图。例如,我们可能需要视图中的一个额外项。这个问题的一个解决方案可能是从头开始重构,考虑正确的字母表和视图。然而,这是非常耗时的,因为它涉及到计算每个模型的语义或重新应用几个转换。本节中介绍的属性构成了更合适的方法。这些属性是关于我们的等价概念的一般规律,建立了我们如何在保持等价的同时操作视图和字母表。在下面的部分中,我们展示了关于我们的概念的一些规律。5.1减少视图图6显示了第2节中描述的银行系统模型。假设顶部的两个模型是等价的,考虑到视图v1只包含映射accounts col.elems和Account ChAcc+SavAcc(假设我们没有选择适当的视图,因为在等价性中没有使用Account→ChAcc+SavAccR. Gheyi等人理论计算机科学电子笔记130(2005)315在这些模型中,最好从v1中删除此项目见图6。 更改视图为了确保这两个模型在简化视图下也是等价的,我们需要检查新视图v2对这两个模型仍然有效 每一种模式都能完善另一种模式。为了使v2有效,它不能是递归的.由于M1和M2在v1和v 2中是等价的,所以v1必须是两个模型的有效视图;因此所有映射都不是递归的。所以,v2不是递归的,因为它的映射都在v1中.有效视图的第二个属性确保视图只映射字母表中的元素。由于v1是一个有效视图,它只映射字母表中的映射。移除视图项时保留此属性。有效视图的第三个属性确保字母表中不属于模型的每个名称都只有一个有效项。由于v1是M1和M2的有效视图,因此它已经具有字母表中的M1和M2。因此,我们必须保证,如果由它映射的名称(即要删除的项)不包含在其中一个模型中,例如M1,则由该名称映射的表达式不能在M1中求值,其中至少包含一个不属于M1的名称。因此,该项对M1无效。这个约束确保在比较解释时不使用它,因此保留了这样一个属性,即对于模型中的每个名称,视图只有一个有效项现在我们必须检查关于v2的精化关系是否也成立,这样我们就可以证明模型在θ和v2下仍然是等价的。注意,细化关系只是比较16R. Gheyi等人理论计算机科学电子笔记130(2005)3¬⇒∀∧字母.由于前面的约束确保了被移除的项不会被比较使用,我们保证了细化关系也适用于v2这是在PVS中证明的相应定理递减视图:定理(m1,m2:模型,a:字母表,v:视图,it:视图项)|当量(m1,m2,a,v)validItem(it,{m1,m2})equivalent(m1,m2,a,vWITH mappings:= mappings(v)-{it})5.2增加视图同样,我们证明了一个增加视图的定理。我们只需要检查减少视图的相同属性,以及其他两个约束,以验证新项不能递归并映射字母表的元素。注意,这些约束意味着我们只能引入一个不用于比较相应模型的项,如以下定理所述。increasingView:THEOREM(m1,m2:Model,a:Alphabet,v:View,it:ViewItem)|等价(m1,m2,a,v)source(it)∈/names(target(it))source(it)∈names(a)<$validItem(it,{m1,m2})<$equivalent(m1,m2,a,vWITHmappings:= mappings(v)<${ it})注意,它们具有可以通过以下方式轻松自动化的语法条件: 减少或增加视图时的工具。此外,这些约束只涉及要删除或添加的项5.3减少字母表图7用相同的视图和字母表显示了前面描述的相同的银行系统模型。现在假设我们不想考虑字母表中的银行(={Account,accounts})。 当减少字母表时,v仍然必须在字母表中关联映射。由于我们没有改变先前有效的观点,并且两个模型在更大的字母表中是等价的,因此直观上它们在其中的一个子集中仍然是等价的;模型越抽象,就越容易比较它们是否等价。递减字母:定理(m1,m2:模型,a1,a2:字母表,v:视图)|equivalent(m1,m2,a1,v)等价名称(a2)姓名(a1)∧hasOnlyItemsForAlphabet(a2,v)当量(m1、m2、a2、v)考虑到前面提到的视图和字母表,两种模型仍然是但是,如果我们选择从字母表中删除Account,我们就不能删除它,因为视图中包含了一个它的项在这种情况下我们R. Gheyi等人理论计算机科学电子笔记130(2005)317见图7。 更改字母表首先,我们必须应用这个法则来减少视图,删除视图中的项目;然后,我们可以应用这个法则来减少字母表。 重要的是要观察减少视图的条件也是句法的。为了增加字母表,我们需要一些语义条件,因为我们必须确保两个模型对于字母表中添加的名称具有相同的值这些属性在重构等价模型链时很重要,因为不需要在链中我们只需检查所涉及的视图和字母表中的一些句法条件作为未来的工作,我们打算证明等价概念的其他性质,如组合性。6相关工作相关的工作[17]已经进行,为字母关系演算(ARC)提供了形式化的语义和定律,它增加了一个理论,[22]第二十二话每个ARC规范都包含一个相关的字母表,相当于我们的字母表概念。 他们使用等价概念来比较定律中的模型,指出如果两个ARC模型具有规范中所有名称的值,则它们是等价的它们的等价概念可以用来比较具有不同名称的ARC模型。为了做到这一点,他们给任何可能的值,而不是在每个模型中的名称;事实上,他们只比较两个模型的共同值。我们的概念与他们的相似,只是我们可以用它来18R. Gheyi等人理论计算机科学电子笔记130(2005)3比较具有不同元素名称的模型类似的方法[3]提出并形式化了Z规范的简化等价概念[21]。它们展示了如何通过一个具有属性的模型来细化一个具有关联的模型,其中两个模型具有相同的名称。他们使用Z/EVES定理证明器证明了这个改进[20]。我们相信,我们的等价概念也可以被看作是Z规范的传统然而,我们的精化关系必须是对称的,不同于他们提出的[3]。UML图[1]的细化概念在其他地方提出[16]。他们提出的改进不仅考虑软件的结构视图,作为我们的工作,而且还考虑行为视图。 他们说,一个模型完善了另一个模型。 如果前者比后者具有更可预测的行为。由于我们的等价概念只处理结构模型,因此我们根据它们的元素名称来比较模型,而不管它们的行为。转换规则[11]已经为UML类图[1]提出。它们说明了两个类图何时是等价的。 区别于 我们的工作是我们的等价概念必然是对称的。此外,一些规则比较具有不同名称的模型然而,它们并没有定义一个一般的等价概念,说明两个类图何时是等价的。这个概念是基于一个非正式的UML语义。 因此,在某些情况下,一些转换规则可能不保留语义,如前所述[9]。这里提出的等价概念的先前版本被描述用于比较可能具有不同元素的合金模型[9]然而,这种使用隐式字母表的概念是有限的,因为它实际上只比较属于两个Alloy模型的元素。此外,这里提出的概念是为任何对象建模符号定义的,与本节中提到的相关方法一个类似的工作提出了Refinement面向对象语言(ROOL)的编程法则[2],这是一种类似于Java的语言[12]。这个相关的工作是类似于我们的意义上,他们提出了一个等价的概念的程序。他们指出,两个程序是等价的,如果每个程序完善另一个。此外,这种细化关系基于主命令的最弱前提语义[4]。我们的等价概念处理抽象对象模型,而不是程序。另一项工作提出了Java程序的重构[6]每一次重构都会改变软件的内部结构,使其更容易理解,修改成本更低,而不会影响软件的可观察行为[6]。 作者保证,如果两个程序在一个测试套件中没有失败,那么它们我们的等价概念涉及R. Gheyi等人理论计算机科学电子笔记130(2005)319模型而不是代码。此外,我们的概念可以用来比较模型的相关结构,类似的作者提出的比较软件的可观察行为7结论在本文中,我们提出了一个抽象的等价概念的对象模型。 在比较模型时,它支持从名称和元素中抽象出来。此外,它还可以用于比较模型的各个部分。我们的等价概念只比较了字母表中模型元素的语义解释,并且来自该字母表的元素不需要在所考虑的模型中,因为它们是由视图根据其他模型元素来表达的。我们还展示了一些有用的属性,证明了PVS证明,它可以语法检查是否以前的等价模型仍然是等价的,当字母和视图发生变化。之前,我们提出了Alloy中描述的等价概念,首先仅适用于Alloy模型[8]。由于Alloy Analyzer [14]是一种用于分析Alloy模型的工具,它不是一个定理证明器,因此我们手动证明了我们的概念实际上是一个等价关系。然而,使用Alloy作为指定任何建模语言的框架可能特别有趣,因为我们能够在证明属性之前使用该工具。我们在逻辑断言中指定等价概念的每个属性,然后要求工具验证断言是否对预定义的范围有效。该工具生成的反例有助于我们理解等价概念。只有在工具没有给出任何反例之后,我们才开始手动证明,后来使用PVS。这种等价概念在几种情况下都很有用,例如Alloy分析中原子化过程的形式化虽然我们的等价概念最初是根据Alloy建模语言定义的,允许Alloy [10]的建模定律的证明,但这个概念足够抽象,可以应用于其他对象建模语言,例如UML [1]。事实上,PVS中的证明显示了概念相对于建模语言语义考虑到未来的工作,我们打算推导和证明这个等价概念的一些额外的属性,以确保我们的概念是广泛适用的,并使证明过程更直观的建模。例如,需要证明等价概念的组合性质。此外,我们的目标是将这种等价概念与20R. Gheyi等人理论计算机科学电子笔记130(2005)3经典的数据精炼概念,如其他地方所采用的[23]。引用[1] Booch,G.,雅各布森岛,Rumbaugh,J.(1999). 统一建模语言用户指南。艾迪森-韦斯利[2] 博尔巴山口Sampaio,A., 和Cor n'elio,M. (2003年)的报告。一个面向对象编程的改进算法第17届欧洲面向对象编程会议,ECOOP[3] 博尔赫斯河 (2004年)。 我不相信UML,我也不相信它。伯南布哥联邦大学技术研究所信息学中心。[4] Cavalcanti,A.和Naumann,D.(2000年)的第10/2000号决议。面向对象程序细化的最弱前提语义。IEEE Transactions on Software Engineering,26(8):713[5] Edwards,J.,Jackson,D.,Torlak,E.,Yeung,V.(2004).使用子类型加快约束求解。2004年ACM SIGSOFT软件测试与分析国际研讨会(ISSTA)论文集,第232-242页。Press.[6] 福勒,M。(1999年)。重构:改进现有代码的设计。艾迪森-韦斯利[7] 伽马,E.,赫尔姆河,约翰逊河,Vlissides,J.(1994). 设计模式:可重用面向对象软件的元素。艾迪森-韦斯利[8] 盖伊河(2004年)。对象建模的基本规律。硕士论文,伯南布哥联邦大学。[9] 盖伊河Borba,P.(2004).重构合金规格。在Cavalcanti,A. 和Machado,P.,编辑,ElectronicNotes in Theoretical Computer Science , Proceedings of the Brazilian Workshop on FormalMethods,第95卷,第227-243页。爱思唯尔[10] Gheyi河,Massoni,T.,Borba,P.(2004).对象建模的基本规律。在第三次规范化和基于验证的系统(SAVCBS)中,与ACM SIGSOFT 2004/FSE-12,第18[11] Gogolla,M. Richters,M.(1998年)。UML类图的等价规则。在统一建模语言,UML'98 -超越符号。第一次国际讲习班,法国米卢斯,第87-96页。[12] Gosling,J.,乔伊,B.,Steele,G.(1996年)。Java语言规范。艾迪森-韦斯利[13] 杰 克 逊 , D 。 ( 2004 年 ) 。 合 金 3.0 参 考 手 册 。 在 http://alloy.mit.edu/beta/reference-manual.pdf。[14] Jackson,D., 谢克特岛 和Shlyahter,H. (2000年)的第10/2000号决议。 Alcoa:合金约束分析仪。 第22届国际软件工程会议(ICSE)论文集,第730-733页。Press.[15] 利斯科夫湾和Guttag,J.(2001年)的第10页。Java中的程序开发艾迪森-韦斯利[16] 刘志, Jifeng,H., 和Li,X。 (2004年)。 基于UML的开发的严格方法。在第七届巴西形式方法研讨会(SBMF),第48-57页,累西腓,巴西。[17] Nuka,G. Woodcock,J.(2004).机械化的字母关系演算。在Cavalcanti,A.和Machado,P.,编 辑 , Electronic Notes in Theoretical Computer Science , Proceedings of the BrazilianWorkshop on Formal Methods,第95卷,第209爱思唯尔[18] Owre,S.,Rushby,J.,Shankar,N.,和Stringer-Calvert,D.(2001年a)。PVS语言参考。请访问http://pvs.csl.sri.com。[19] Owre,S.,Rushby,J.,Shankar,N.,和Stringer-Calvert,D.(2001年b)。PVS证明器指南。请访问http://pvs.csl.sri.com。R. Gheyi等人理论计算机科学电子笔记130(2005)321[20] Saaltink,M.(1997年)。Z/EVES系统。在Bowen,J.,Hinchey,M.,和Till,D.,编辑,ZUM史普林格出版社[21] Spivey,J.(1989年)。Z符号:参考手册。C. A. R. 《霍雷系列》编辑普伦蒂斯·霍尔[22] Tarski,A.(1941年出版)。 关于关系的演算。 Journal of Symbolic Logic,6(3):73[23] Woodcock,J. and Davies,J.(199
下载后可阅读完整内容,剩余1页未读,立即下载
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://profile-avatar.csdnimg.cn/default.jpg!1)
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
我的内容管理 收起
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
会员权益专享
最新资源
- 京瓷TASKalfa系列维修手册:安全与操作指南
- 小波变换在视频压缩中的应用
- Microsoft OfficeXP详解:WordXP、ExcelXP和PowerPointXP
- 雀巢在线媒介投放策划:门户网站与广告效果分析
- 用友NC-V56供应链功能升级详解(84页)
- 计算机病毒与防御策略探索
- 企业网NAT技术实践:2022年部署互联网出口策略
- 软件测试面试必备:概念、原则与常见问题解析
- 2022年Windows IIS服务器内外网配置详解与Serv-U FTP服务器安装
- 中国联通:企业级ICT转型与创新实践
- C#图形图像编程深入解析:GDI+与多媒体应用
- Xilinx AXI Interconnect v2.1用户指南
- DIY编程电缆全攻略:接口类型与自制指南
- 电脑维护与硬盘数据恢复指南
- 计算机网络技术专业剖析:人才培养与改革
- 量化多因子指数增强策略:微观视角的实证分析
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)