没有合适的资源?快使用搜索试试~ 我知道了~
理论计算机科学电子笔记91(2004)116-133www.elsevier.com/locate/entcs用于构件检索的大卫·赫默1昆士兰大学信息技术与电气工程学院摘要在本文中,我们描述了一个高阶联想交换模式匹配算法。我们的动机是需要开发工具支持,以匹配用户需求和库组件接口,两者都使用正式语言指定。在开发这种工具支持时,我们的目标是最大程度的召回,同时保持合理的自动化和效率水平。为了支持库组件的自适应,我们假设库组件可能包含高阶参数(表示类型,功能和关系)-组件通过实例化参数来适应用户的要求。然而,有了这个假设,通常的规范匹配技术,基于使用基于一阶逻辑的定理证明器证明等价性,一般来说不再有用。因此,我们建议建立基于模式匹配的工具支持,并通过提供(部分)支持匹配的表达式,可以证明是等效的应用法律的结合性和交换性,以增加召回。关键词:关联交换匹配,特征匹配,成分检索1介绍1.1动机基于组件的软件工程(CBSE)最初由McIl- roy在1969年提出[11],是一种开发范式,其中软件通过将许多软件构建块(称为组件)拼凑在一起来构建。的1电子邮件:hemer@itee.uq.edu.au1571-0661 © 2004 Elsevier B. V.根据CC BY-NC-ND许可证开放访问。doi:10.1016/j.entcs.2003.12.008D. Hemer / Electronic Notes in Theoretical Computer Science 91(2004)116-117本发明的构思类似于在电子工程环境中从多个较小、较简单、公知的组件工程师浏览组件描述的目录,寻找合适的组件,这些组件可以拼凑在一起构建其设备。对基于组件的软件工程的研究在最近得到了重申,特别关注CBSE的形式化方法[17,6,1,20,19]。特别是已经有一个正式的组件接口的重点,并使用这种额外的表现力和精确性,以开发支持适应和检索组件,以满足用户的需求。支持组件自适应的最常用的基于形式的机制是在逻辑组件中使用(形式的)高阶参数。这样的组件可以通过将高阶参数实例化为类型、项或谓词来适应,以满足用户需求。正如我们将在下面解释的那样,高阶参数的使用对可以开发的检索支持类型有影响在检索方面,一种有前途的方法是正式指定库组件的属性和用户需求,并使用称为规范匹配的技术[22]来检索满足用户需求的库组件规范匹配涉及检查库组件是否满足用户需求;库组件和用户需求都使用组件语言正式指定。1.2构件检索的形式化方法规范匹配基于匹配两个组件规范,代表组件库规范(模式)和用户需求(查询)。为了本文的目的,我们将在两大类中考虑规范匹配技术:句法匹配和语义匹配。句法匹配技术[16,5]基于模式匹配或统一。这些技术的优点是它们通常非常有效,并且可以完全自动化。此外,统一化和模式匹配可以应用于高阶逻辑,因此与我们通过使用高阶参数来支持组件自适应的目标是兼容的。基于统一的方法的主要缺点是与纯语法匹配相关的召回水平很差。语义匹配技术[22,9,15,18]基于证明逻辑组件满足用户需求。基于语义的匹配技术的主要优点事实上,基于语义的规范匹配可以扩展到包括宽松的匹配技术。例如,基于语义的技术可以用于匹配118D. Hemer / Electronic Notes in Theoretical Computer Science 91(2004)116-对具有较弱前置条件和较强后置条件的库组件进行查询。然而,语义匹配技术需要推理支持(通常以交互式定理证明器的形式),这可能成为检索过程中的主要开销,无论是在效率还是自动化水平方面。此外,目前的规范匹配方法都是基于一阶逻辑的,因此这些技术与我们通过使用高阶参数来支持自适应的目标不一致。1.3本文本文的目的是提出一种解决方案,以解决介于上述两类匹配技术之间的规格匹配问题。我们描述了一个高阶模式匹配为基础的技术,这是知识为基础的意义上,它可以应用关联性和交换性规则,以增加召回的水平。在第2节中,我们总结了高阶逻辑的模式匹配和统一的现有方法,包括一阶逻辑的结合交换匹配的现有方法在第4节中,我们定义了表达式语言,给出了参数实例化的描述,并描述了表达式语言的纯语法模式匹配算法。在第5节中,我们给出了关联交换匹配的一个规范。在第6节中,我们定义了高阶表达式的(不完全)关联交换模式匹配算法。在第7节中,我们将讨论如何使用这种匹配技术来支持组件检索。2相关工作Prolog语言包含一阶(无类型)元变量。Prolog中的演绎是基于这些Meta变量的所谓标准(一阶)统一通过用新的子项替换项中的一个或多个变量来获得项的集合,例如f(a,b)是f(x,b)的实例,其中子项a替换元变量X。如果两个术语有一个共同的实例,其中两个术语共同的变量被一致地替换,则称它们是统一的在高阶逻辑(即参数范围在函数或关系上的逻辑)的情况下,标准统一不再适用。Huet [8]首先提出了一种算法,用于统一类型微积分中的高阶项。从那时起,Huet算法的许多实现已经开发出来。已经确定,一般来说,高阶统一性是不可判定的(即给定任意项,并不总是可能D. Hemer / Electronic Notes in Theoretical Computer Science 91(2004)116-119当他们决定的时候然而,某些类别的高阶项的统一特别是对于米勒发现的一类被称为“模式”的术语类似地,三阶匹配已被证明是可判定的[2],并且存在某些类别的高阶项,其中匹配是可判定的[21]。高阶统一最常应用于自动推理。HOL定理证明器[4]与高阶逻辑“硬连线”,并为高阶统一提供内置支持。另一方面,Isabelle定理证明器[14]是一个通用的定理证明器,设计用于各种形式理论的推理。然而,它确实提供了对高阶逻辑的支持,具有用于高阶统一的内置算法请注意,它的(懒惰)算法并不保证会终止,因为它的元语言中的术语的“最一般单位”集合高阶统一也被用于编程语言。作为一个例子,Prolog 扩展了标准的Prolog,允许参数在函数和关系上变化。因此,Lambda- Prolog中的推理依赖于高阶统一而不是标准统一。最后,我们注意到,结合交换匹配和合一已经在一阶逻辑中得到了很好的研究。特别是,我们从Lincoln和Christian [10]开发的算法中获得灵感。3例如我们从一个激励性的例子开始,这个例子虽然简单,但不能用标准的模式匹配或基于语义的匹配技术来处理。假设用户需要一个向列表添加元素的函数,使得列表在添加元素之前和之后不包含重复,并且列表永远不会超过50个元素。这种要求可以用以下具体说明来表示:addelem(ine:E, ins:List, outr:List)前非重复样本数≤50postran(r)= ran(s){e} len(r)≤ 50 isNonRep(r)。这个问题可以通过对e是否是列表s的成员进行案例分析来解决。这可以通过使用案例分析列表组件来实现。这个库组件中顶级函数的具体说明如下所示,其中P和Q是参数。案例(inx:X, iny:Y, outz:Z)前P(y)120D. Hemer / Electronic Notes in Theoretical Computer Science 91(2004)116-postP(z)<$Q(x,y,z).因此,为了解决这个问题,我们需要找到addelem和cases之间的匹配。使用签名匹配,我们可以轻松地将查询和库规范的输入/输出参数的名称和库规格可适于给出:case(ine:E, ins:List, outr:List)前P(s)后P(r)→Q(e,s,r)。然而,简单的模式匹配不会返回匹配,因为库规范的后置条件中的本文描述的AC匹配算法确实返回了这个问题的匹配,实例化P<$→λx·isNonRep(x)<$len(x)≤50,Q<$→λx,y,z· ran(z)= ran(y)<${x}。4高阶项4.1抽象语法我们首先定义本文中使用的数学表达式语言集合Var、FunctionName和FunctionParam分别表示变量、函数名和函数参数的名称集合。在本文中,变量将由小写标识符u,v,w,x,y和z表示。函数名由小写标识符f、g和h表示,用于1元及以上的函数,标识符c、d和e表示常量。函数参数由大写标识符F、G和H表示。[Var,FunctionName,FunctionParam]术语可以是占位符、变量、(非参数)函数应用或参数函数应用。占位符用于定义函数参数的实例化,它们抽象地表示为自然数。 例如,给定一个参数F的实例化为fnapplic(g,n(2),ph(1)n),意味着F的应用(必须至少有两个参数)被应用于F的第二个和第一个参数的函数g所取代。函数将多个值(参数)映射为单个值;函数的应用程序由函数名和一系列项表示。通过包含一个参数函数应用程序,术语可以在函数上参数化;抽象地由函数参数和D. Hemer / Electronic Notes in Theoretical Computer Science 91(2004)116-121术语的顺序术语::=ph值N1|瓦尔吉尔瓦尔吉尔|fnapplic⟨⟨FunctionName×seq Term⟩⟩|termparam⟨⟨FunctionParam×seq Term⟩⟩例4.1抽象术语fnApplic(f,n varx,termParam(G,nfnApplic(c,nvar)n)n)(1)具有具体表示f(x,G(c)).(二)4.2实例化参数通过用其他非参数表达式替换参数的出现来实例化表达式在表达式中的所有参数都被替换的情况下,该表达式被称为已经完全实例化,否则该表达式被称为部分实例化。为了描述表达式中的参数如何被替换,给出了形式参数实例实例化被定义为从参数到包含占位符的项的有限部分映射占位符引用实例化中参数的参数Inst==FunctionParam→›Term映射是有限的,因为只有无限多的参数要实例化。映射是部分的,表明并非所有参数都需要实例化。参数F到项t的实例化由符号F~t表示。平凡实例化(TrivInst)被定义为在应用后保持所有表达式不变的唯一实例化它被表示为空函数。参数实例化通常使用占位符来定义实例F~ph(1)+ph(2)表明F至少有两个自变量的应用被+应用于F的第一个和第二个自变量所取代。更具体地说,F(x,y)将使用此实例化被x+y替换。函数instantiate将实例化应用于表达式以产生新表达式。instantiate:Term×Inst→Term122D. Hemer / Electronic Notes in Theoretical Computer Science 91(2004)116-对于项,通过分别考虑占位符和变量、非参数函数应用和参数函数应用来定义实例化函数instantiate函数的非正式定义如下:• 占位符2和未绑定变量保持不变;• 通过实例化所述变元列表来实例化非参数函数应用;• 设F~e是实例化映射的一部分,则构造形式为F(a1,. .,am)的实例化是通过首先用e替换函数application,然后替换任何出现的占位符ph(j),其中j ∈ 1.。e中的m由实例化aj所产生的项来表示。例4.2假设F,G,H是参数,上述参数的实例i定义为:i=={F~f(ph(2),g(ph(1),ph(2),G~h(ph(1)),H~ph(2)}(3)则项t1==G(H(c,x+y))由i实例化如下:instantiate(t1,i)=instantiate(G(H(c,x+y)),i)(4)=h(instantiate(H(c,x+y),i))(5)=h(x+y)(6)项t2==F(H(d,x),G(x))由i实例化如下:instantiate(t2,i)=instantiate(F(H(d,x),G(x)),i)(7)=f(n =2,g(n =1, n =2))(8)其中,R1是实例化调用F的第一个参数的结果,并且F2是实例化调用F的第二个参数的结果,即:n=instantiate(H(d,x),i)=x(9)因此,由i实例化项t2的结果是:instantiate(t2,i)= f(h(x),g(x,h(x).(十一)2通常,要实例化的术语不包含占位符;然而,为了完整性,包括了这种情况,稍后会有用。D. Hemer / Electronic Notes in Theoretical Computer Science 91(2004)116-1234.3匹配项两个数学表达式p和q被称为匹配,如果存在实例i使得用i实例化p产生q。我们将可能包含参数的表达式p称为模式,而q称为查询。术语匹配的顶级指定由下式给出:匹配:P(术语×术语×Inst)n(p,q,i)∈match·instantiate(p,i)=q现在,我们给出一个非正式的描述算法匹配数学表达式的结构归纳的模式。匹配术语的算法遵循4.1节中给出的术语抽象语法的结构。请注意,虽然占位符只出现在实例化中使用的表达式中,但为了完整起见,这里考虑占位符。情况1:p= varx,其中x是变量。p仅匹配具有平凡实例化的项x情况2:p=ph(j),其中j是>0的自然数。p匹配查询q=ph(j)与平凡的实例化。情况3:p = f(a1,. .,其中f是非参数函数。p匹配形式为f(b1,. .,bm),其中对于每个j,aj匹配bj。匹配集合可以通过合并(在可能的情况下)通过针对每个j将aj与bj匹配而形成的实例化集合来形成。情况4:p= F(a1,. 、.中,其中F是参数函数。p与任意项e的匹配集是通过考虑e的所有不相交的子树集而形成的,其中集合中的每个子树esub匹配aj,其中j∈ 1。M.通过将不相交集合中的每个esub与对应的aj匹配而形成的实例化集合被合并以形成实例化集合。然后将这些与实例化{F~eJ}合并,其中eJ是通过将每个子树替换为相应的占位符来形成的。124D. Hemer / Electronic Notes in Theoretical Computer Science 91(2004)116-完整的实例集是通过对所有不相交的子树集取实例集的并集,并最终过滤掉任何包含自由变量的实例而形成的。例4.3给定一个模式p=F(G(x,y),H(x,y)),其中F,G和H都是参数,以及一个查询q=(x+y)<$(y-x)。使p与q匹配的两种(多种)可能的方式是:{F~ph(1)-ph(2),G~ph(1)+ph(2),H~ph(2)-ph(1)}(12){F~ph(2)-ph(1),G~ph(2)-ph(1),H~ph(1)+ph(2)}(13)第一个匹配是通过考虑以下不相交的子树生成的:问:{x+y,y−x}(14)第一个子树x+y与函数应用F的第一个参数G(x,y)匹配,第二个子树y−x与函数应用F的第二个参数G(x,y)匹配。H(x,y)。分别用占位符ph(1)和ph(2)替换子树x+y和y-x,得到实例化F~ph(1)ph(2)。通过遵循相同的过程,可以示出G(x,y)将x+y与实例化G~ph(1)+ph(2)匹配。类似地,H(x,y)用实例化H~ph(2)−ph(1)匹配y−x。上面列出的第二个匹配可以以大致相同的方式生成。与第一次匹配一样,考虑子树x+y和y-x,但这一次第一个子树与F的第二个参数匹配,第二个子树与F的第一个参数匹配。Q5联想交换匹配在本节中,我们描述一种宽松形式的匹配,称为关联交换匹配或AC匹配,它使用关联交换算子的属性来实现更多的匹配。5.1结合交换算子结合算子和交换算子是一类特殊的算子,定义如下:定义5.1称一个算子f是结合的,如果对所有的u,v,w f(f(u,v),w)=f(u,(f(v,w))D. Hemer / Electronic Notes in Theoretical Computer Science 91(2004)116-125例5.2结合运算符包括整数集合上的函数+、和−。二元连接词“”、“”、“”和“惠”也是联想词。定义5.3一个算子f称为交换的,如果对所有的u,v f(u,v)= f(v,u)。例5.4函数+和,以及二元连接词、和惠都是可交换的。 函数−和二元连接符是结合但非交换的算子的例子。定义5.5两个表达式e1和e2被称为AC等价的,记为e1=ACe2i,这两个表达式可以仅使用以下定律来证明相等:两个表达式中任何AC运算的结合性和交换性,以及绑定变量的重命名。这是直接表明关系=AC是一个等价关系。示例5.6假设 运算符f是AC,那么表达式f(f(a,g(b)),c)和f(f(g(b),c),a)是AC等价的。这是可以证明的使用结合性和交换性的性质如下:f(f(a,g(b)),c)=ACf(f(g(b),a),c)交换性(十五)=AC f(g(b),f(a,c))关联性(十六)=AC f(g(b),f(c,a))交换性(十七)=AC f(f(g(b),c),a)关联性(十八)5.2扁平化的表达对于给定的AC运算符,表达式可以通过修改抽象语法以允许该运算符下面的语法树中有两个或更多分支来扁平化例如,假设+是AC,项((a+b)+c)可以相对于+被省略,以给出a+b+c。函数flatten采用AC函数和项,并将项相对于AC函数展开。flatten:FunctionName×Term→seqTerm请注意,如果最外层的项不是所讨论的AC算子,则不会进行任何附加处理。例如,g((a+b)+c)项在相对于+被省略时将保持不变。126D. Hemer / Electronic Notes in Theoretical Computer Science 91(2004)116-5.3交流匹配规范模式p被称为匹配查询q直到AC等价,如果存在实例化i,使得在i下实例化p的结果AC等价于q,即:匹配AC:P(术语×术语×仪器)p,q:Term;i:Inst·matchesAC(p,q,i)惠实例化(p,i)=ACq例5.7假设f是AC算子,G是参数函数。然后是模式,p==f(f(G(x,y),z),h(c))(19)相当于查询q==f(f(x,h(c)),f(z,y))(20)在实例化i={G~f(ph(1),ph(2))}(21)为了证明这是真的,我们首先相对于i实例化p,然后使用结合性和交换性定律将实例化的模式转换为查询,即:instantiate(p,i)=f(f(f(x,y),z),h(c))(22)=ACf(f(x,y),f(z,h(c)(23)=ACf(f(x,y),f(h(c),z))(24)=ACf(f(x,f(y,h(c)),z))(25)=ACf(f(x,f(h(c),y),z))(26)=ACf(f(x,h(c)),f(y,z))(27)=ACf(f(x,h(c)),f(z,y))(28)6一种交流匹配匹配算法可以通过考虑AC算子进行扩展,并匹配到AC-等价。匹配AC功能扩展了AC功能的匹配匹配AC:Term×Term→FInstD. Hemer / Electronic Notes in Theoretical Computer Science 91(2004)116-127对于术语,函数matchAC以类似的方式实现,匹配(见第4.3节),但考虑两种额外情况6.1匹配非参数AC函数我们首先通过考虑模式和查询都是相同关联交换函数的非参数函数应用(模式可以在其子项中包括参数)的情况来扩展匹配算法。一个例子是匹配模式(G(x,y)+z)+h(c)和查询(x+h(c))+(z+y)。一个可能的匹配可以通过实例化G~ph(1)+ph(2)来实现。在描述算法之后,我们描述了这种匹配是如何生成的。我们假设模式p具有形式p = f( a1,.,am)和查询q具有形式q = f(b1,.,bn),其中f是非参数AC函数。在这种情况下,用于将p与q匹配的算法如下进行第一步:将函数flatten应用于参数序列a1,. ,Am和B1,. ,bn的模式和查询分别,以获得序列aJ,.,aJ和1JbJ,.,BJ,其中j≥m,k≥ n;1K第二步:从这些序列中删除任何重复项,即在两个序列中出现的任何相同项,以分别给出序列α和β;第三步:将序列β i的分区的集合生成为袋的序列Φ,使得:(a)#Φ =#α产品编号Φ(b)第(1)款k=1计数Φ(k)=#β(c) 对于每一个k∈ 1.. #α如果α(k)是参数函数应用,则α≥1计数Φ(k)=01否则(d) 对于每一个k∈ 1.. #β存在j∈ 1.. #Φ使得Φ(j)中的β(k128D. Hemer / Electronic Notes in Theoretical Computer Science 91(2004)116-(e) 每个元素在袋序列Φ中出现的次数与它在序列β第四步:对于上一步中生成的每个分区序列Φ,通过将每个袋子映射到项来形成项序列γ,如下所示:(a) 对于具有[u]形式的单个元素的袋子,返回术语u(b) 对于袋[u1,.,uv]与多个元素一起返回项f(u1,. ,uv)第五步:应用函数matchAC(α,γ)来获得步骤4中生成的每个项序列γ的匹配集例6.1给定模式p=(G(x,y)+z)+h(c),其中+是AC-函数,G是参数函数,查询q=(x+h(c))+(z+y)来自Ex.五点七然后,用于生成p和q的匹配的算法如下进行(i) 将p和q相对于AC-运算符+进行赋值,以给出序列:G(x,y),z,h(c)x,h(c),z,y(ii) 删除出现在两个序列中的元素以给出序列:α=<$G(x,y)<$β=x,y(iii) 分割β以给出袋序列<$[[x,y]]<$(iv) 形成项序列γ=<$x+y<$(v) 生成matchAC(G(x,y),x + y)的匹配集。结果由单个实例化G~ph(1)+ph(2)组成。6.2针对AC查询匹配高阶函数我们考虑的第二个扩展是针对形式g(b1,. 、.中, bm),其中g是AC函数,以及形式F(as)的模式,其中F是参数,as是形式a1,. .,an,并且至少一个自变量是涉及AC函数g的函数应用。D. Hemer / Electronic Notes in Theoretical Computer Science 91(2004)116-129一个简单的例子是模式G(x+z,y)匹配查询y+x+z。这可以通过实例化G~ph(1)+ph(2)来实现。一个更复杂的例子是模式G(x+y,y+x)与查询x+y+y+x匹配。这可以在以下实例中实现:G~ph(1)+ph(1)(29)G~ph(1)+ph(2)(30)G~ph(2)+ph(2)(31)注意,我们没有包括实例化G~ph(2)+ph(1),因为这等价于上面列出的第二个实例化。在给出算法的草图之前,我们定义一个关于函数f的项的权重的概念。定义6.2项t相对于函数f的权重定义如下:.#flatten(t,f)如果f是AC函数weight(t,f)=1例其他情况(三十二)例6.3对于AC函数+,x+(G(y)+f(c))的权重为3,x的权重为1,f(x+y,x+z)的权重为1,G(x+z)的权重为1。对于形式g(b1,. .,bm),其中g是AC函数(假定查询已经相对于g被忽略),以及形式F(as)的模式,其中F是参数,as是形式a1,. .,an,算法如下进行:第一步:生成具有k个元素的多重集的集合,其形式为[u1,. .,uk]],其中每个ui是自然数。每个多重集应满足以下条件:(i) 每个ui表示模式的参数的索引(自然数,N),使得对于每个i∈ 1.k,ui∈ 1.. n(ii) 包是非空的,使得对应的模式参数相对于g的权重之和130D. Hemer / Electronic Notes in Theoretical Computer Science 91(2004)116-的参数,即,克1≤j=1weight(as(uj),g)≤ m.第二步:对于每个袋子,通过分别考虑具有单个元素的袋子和具有多个元素的袋子来生成匹配集,如下所示:(i) 对于形式为[u]的袋子,生成表达式as(u)和查询g(b1,. .,bm),并将每个结果与实例化F~ph(u)合并。(ii) 对于形式为[U1,. 、.中, 其中k> 1,生成表达式g(as(u1),. 、.中,as(uk))和查询g(b1,. 、.中,bm),将每个结果与实例化F~g(ph(u1),. .,ph(uk))。例6.4为了说明该算法,我们考虑匹配模式G(x+y,x+z,y,z),其中G是参数,针对查询x+y+z,这里我们假设+是一个AC运算符。 我们首先注意到,查询已经针对+进行了处理。 第一步是生成 满足上述步骤1中的条件的多集合的集合。我们注意到,模式的第一个和第二个参数关于+的权重是2,而其他两个参数的权重是1。因此,可能的多重集的集合是:{[[1]],[[2]],[[3]],[[4]],[[1,3]],[[1, 4]],[[2,3]],[[2,4]],[[3,3]],[[3,4]],[[4,4]],[[3,3,3]],[[3,3,4]],[[3,4, 4]],[[4,4, 4]]}(三十三)对于这些多重集合中的每一个,我们形成一个新的项,如算法的步骤2所述。例如,对于多集[1,3]],形成了项(x+y)+y,由模式的第一个参数的一个实例和第三个参数的一个实例组成。对于每一个多重集合,参数G的实例化也被创建;对于多重集合[[1, 3]],实例化G~ph(1)+ph(3)被形成。然后,每个新的术语与查询进行匹配,并且表示成功匹配的任何实例化与对应的新创建的G的实例化合并。在这个例子中,有两个成功的匹配G~ph(1)+ph(4)和G~ph(2)+ph(3),分别来自多集[[1, 4]]和[2, 3]在第一种情况下,创建了项(x+y)+z,它将查询与平凡实例化相匹配这与实例化G~ph(1)+ph(4)D. Hemer / Electronic Notes in Theoretical Computer Science 91(2004)116-131给出第一个答案。在第二种情况下,创建了项(x+z)+y,它再次将查询与平凡匹配。7讨论7.1不完整本文中描述的算法绝不是完整的,因为对于某些查询和模式,有满足指定的实例(除了在某种意义上等同于返回的实例之外)没有返回。事实上,给出一个满足算法不返回的规范的例子很简单。例7.1考虑模式F(x+c,y,u,v),其中F是参数,查询x+(u<$v)+y+c。通过实例化F~ph(1)+ph(2)+(ph(3)ph(4))我们得到项x+c+y+(uv),可以很容易地看出它是AC等价于查询。然而,这个实例化不是由我们的算法生成的。算法的不完整性可能不会吸引纯粹主义者,但必须记住,我们的目标是提高与匹配相关的召回水平,同时不会对效率和自动化水平产生不利影响。在这个意义上,我们的算法实现了既定的目标。高阶AC匹配似乎没有任何已发布的可判定性或复杂性结果,但一阶AC匹配已经发布了几个结果[7,3]。这些论文证明了一阶AC匹配是可判定的,但是存在需要指数时间来计算的病理情况。Eker [3]表明,对于只有单个AC函数的情况,可以在多项式时间内计算解7.2建筑物检索工具支持本文中描述的算法已被用作CARE图书馆检索工具的一部分[5]。该算法(与检索工具的其他部分一样)已在Prolog中实现。由于Prolog是一种高级语言,所以实现的算法与本文所描述的算法非常相似。该算法使用回溯来计算所有解。检索工具基于匹配片段规范,对应于用户需求(查询)和库组件(模式)。片段指定使用前置和后置条件表示,匹配通过匹配相应的前置和后置条件来完成,然后合并得到的实例化(如果有的话)。132D. Hemer / Electronic Notes in Theoretical Computer Science 91(2004)116-这代表了细粒度的匹配,然而CARE中的库组件因此,匹配被进一步扩展,以包括针对列表模板匹配多个用户需求。匹配各个片段(如上所述),然后合并产生的实例化以给出完整的匹配。可以对检索工具进行的进一步增强是将基于定理证明器的匹配与我们现有的基于模式的匹配相结合。这可以通过两种方式实现。第一种方法是实现单独的匹配算法,即,基于定理证明器的和基于模式匹配的,然后根据模式和查询的形式决定使用哪一个。另一种方法是使用支持高阶逻辑的定理证明器[14,4]。这样的证明器提供了对高阶统一的支持,但是它们可以通过添加对关联交换匹配的支持来增强,如本文所述。8结论本文描述了一种高阶联想交换模式匹配算法。虽然该算法并不完整(因为它不会返回满足规范的所有解决方案),但它确实满足了我们要求的目标,即增加基于语法的模式匹配的召回率,同时不会过度牺牲效率,并保持自动化。我们已经简要地描述了如何使用该算法作为组件检索工具的一部分,并讨论了如何进一步增强可以实现AC匹配与基于语义的匹配技术相结合,或者它可能会提高基于高阶逻辑的定理证明的能力确认这项工作由澳大利亚研究委员会发现资助DP0208046,规范汇编。引用[1] Abrial,J-R.,B书:从程序到意义。 剑桥大学出版社,1996年。[2] Dowek,G.,三阶匹配是可判定的。Annals of Pure and Applied Logic,69:135-155,1994.[3] Eker,S. M.,提高交流匹配和统一的效率。技术报告RR-2104,INRIA洛林,1993年。D. Hemer / Electronic Notes in Theoretical Computer Science 91(2004)116-133[4] 戈登,M。J. C.和T. F.梅勒姆编辑们HOL简介:高阶逻辑的定理证明环境。剑桥大学出版社,1993年。[5] 赫默,D.和P.琳赛支持基于组件重用在在乎在Michael Oudshoorn,编辑,Proceedings of the Twenty-Fifth Australasian Computer Science Conference , 第 4 卷Conferences in Research and Practice in Information Technology,第95-104页。澳大利亚计算机协会,2002年1[6] Hemer,D.和p. A. Lindsay,C是从正式规范开发验证程序的工具集。号手术Frieder和J.Wigglesworth,编辑,第四届软件工具评估国际研讨会论文集,第24-35页。IEEE ComputerSociety Press,May 1996.SVRC TR 95-52。[7] Hermann,M.和p. G. Kolaitis,同时基本匹配问题的计算复杂性。Journal of AutomatedReasoning,23:107[8] Huet,G. P.,类型λ-演算的一个统一算法理论计算机科学,1:27[9] Jeng,J-J.和B.H. C Cheng,Specification Matching for Software Reuse:A Foundation。在ACM软件重用研讨会论文集,第97[10] Lincoln , P. and J. Christian, Adventures in associative-commutative unification. 见 ClaudeKirchner,editor,Unification,pages 393中国科学院出版社,1990年.[11] McIlroy,M. D、大规模生产的软件组件。软件工程概念和技术,第88-98页[12] Miller,D.,将简单类型的可编程项统一为逻辑程序设计。 在P.K. Furukawa,编辑,Proc.1991Joint Int. Conf. Logic Programming,第253-281页。MIT Press,1991.[13] Nipkow,T.,高阶模式的功能统一。在Proceedings of the 8 th IEEE Symposium Logic inComputer Science中,第64-74页。IEEE计算机协会出版社,1993年6月。[14] 保尔森湖C.的方法,伊莎贝尔:接下来的700个定理证明者。在P. Odifreddi,编辑,逻辑和计算机科学,第361-386页。中国科学院出版社,1990年.[15] Perry,D. E.和S. S. Popovich,Inquire:基于同品种器械的使用和重用。 第八届基于知识的软件工程会议集,第144-151页,1993年9月。[16] 罗林斯 E. J.和J. M. 阿荣,规范作为软件库的搜索关键字。在K. Furukawa,editor,Eighth International Conference on Logic Programming,pages 173-187. MIT Press,1991.[17] Schmidt,H. W. 和W. Zimmermann,A Complexity Calculus for Object-Oriented Programs。Journal of Object-Oriented Systems,1(2):117[18] 舒曼,约翰M.,软件工程中的自动定理证明。Springer Verlag,2001年。[19] Stickel,M.,R. Waldinger,M.劳瑞,T。普雷斯伯格和我。 安德伍德,从子程序库中演绎天文软件的组成。在Proceedings 12 th International Conference on Automated Deduction,第341-355页[20] 威廉姆森,K。和M.希利,通过范畴理论- 使用specware的案例研究。自动化软件工程,8:7[21] Wolfram,D.一、高阶匹配的可判定性。In Jorg Siekmann Franz Baader and Wayne Snyder,editors,Proceedings of the Sixth International Workshop on Unification,UNIF[22] Zaremski,A.Moormann和J.M. Wing,软件组件的规范匹配在第三届ACM SIGSOFT软件工程基础研讨会,1996年。
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- zigbee-cluster-library-specification
- JSBSim Reference Manual
- c++校园超市商品信息管理系统课程设计说明书(含源代码) (2).pdf
- 建筑供配电系统相关课件.pptx
- 企业管理规章制度及管理模式.doc
- vb打开摄像头.doc
- 云计算-可信计算中认证协议改进方案.pdf
- [详细完整版]单片机编程4.ppt
- c语言常用算法.pdf
- c++经典程序代码大全.pdf
- 单片机数字时钟资料.doc
- 11项目管理前沿1.0.pptx
- 基于ssm的“魅力”繁峙宣传网站的设计与实现论文.doc
- 智慧交通综合解决方案.pptx
- 建筑防潮设计-PowerPointPresentati.pptx
- SPC统计过程控制程序.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功