没有合适的资源?快使用搜索试试~ 我知道了~
按需调用Lambda演算中的互模拟关系
理论计算机科学电子札记128(2005)81-101www.elsevier.com/locate/entcs非确定系统中互模拟的相合性按需调用Lambda演算马蒂亚斯·曼1InstitutfurInformatik,JohannWolfganggGoethe-Universitüat,Frannkfurt,Germany摘要我们提出了一个按需调用的λ-演算λND,其中包含一个不稳定的非确定性算子pick和一个非递归let。给出了互模拟的定义,它必须基于一个进一步的计算公式,因为互模拟是一个简单的概念,定义是不可用的。 其主要原因是λ的互模拟是一个同余,与语境对等一致。该证明是Howe方法的非平凡扩展。这可能是朝着定义有用的互模拟关系并证明它们是扩展λ ND -演算的演算中的同余关系迈出的一步。关键词:互模拟,同余,上下文等价,非确定性,按需调用Lambda演算1介绍平等在程序的推理中起着重要的作用。因此,特别是对于λ-演算,当两个项应该被认为相等时,存在一定范围的概念。首先,有可转换性的概念,即如果两个项可以根据微积分的转换规则相互转换,则它们是等价的通常,转换允许在任意上下文中进行,即。程序片段,因此可转换性是一致的。对于确定性微积分,有大量合理的方程,例如,有用的程序变换,既不能被证明,也不能被证明。1电子邮件地址:mann@cs.uni-frankfurt.de1571-0661 © 2005 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi:10.1016/j.entcs.2004.09.04182M. Mann/Electronic Notes in Theoretical Computer Science 128(2005)81与可兑换性相矛盾。因此,有一个严重的兴趣在λ-理论(参见。[5,PartIV]),即λ-演算在导子下闭的相容扩张由于[23]的上下文等价,它通过术语在所有上下文中的行为来区分术语,属于这一类。通常,观察到终止(参见[19])。因此,当C表示终止时,程序上下文,上下文等价c可以表示为sct(C:C[s]C[t])这显然建立了一致性,因为它是基于对某些行为的观察,它通常被称为观察一致性。我们认为语境等价性比可转换性更重要,原因有几首先,上下文等价并不直接依赖于微积分的归约规则第二,语境对等比可转换性验证更有意义的等式 , 后 者 可 能 , 例 如 , 在 某 些 情 况 下 , 仅 涉 及 相 同 渐 近 复 杂 度 的 项(cf.[29])。另一方面,在非确定性环境中,可兑换性一般会导致不一致的理论。因此,当然,有一些可转换的术语不是上下文等价的。但在许多情况下,微积分的确定性部分可以被证明是可靠的。语境对等因此,上下文等价在正确的程序转换的重要领域中具有很大的意义,无论是确定性的还是非确定性的演算。然而,上下文等价的证明可能是不平凡的,因为必须考虑所有的上下文。因此,通过上下文引理来减少上下文的数量是常见的(参见。[19]),例如在[20]中,特定机器配置的对象是足够的,而[21,14,13,31]使用评估上下文。毫无疑问,这是一个非常有用的方法,对于许多任务来说是足够的。但它并没有在原则上解决这个问题,因为仍然有有限数量的背景需要考虑。互模拟的起源可以追溯到Park [25]和Milner [18]的工作,提供了一种更逐步的方法来证明方程,因此互模拟技术从那时起就经常应用于函数编程(例如[2,27,8,9在这个领域中,有一些不同的关系,但一般来说,双相似性的定义涉及一些单调算子的最大不动点。正因为如此,互模拟证明可以非常简洁,而相应的上下文等价证明是微妙的,如示例4.9所示。因此,它本身是一个强大的证明工具,但为了使用它来证明程序转换的正确性,必须确保M. Mann/Electronic Notes in Theoretical Computer Science 128(2005)8183这是一个一致性。例如,Groote和Vaandrager在[10]的介绍中强调证明互模拟是一个同余是至关重要的。 但正如[2,11,12]中的结论所示,这通常不是一项微不足道的任务。此外,我们在例3.3中证明,在非确定性与共享相结合的范围内,互模拟必须仔细设计。现在这项工作的目的是为非确定性按需调用λ演算建立一个合理的互模拟定义第二部分,在介绍了几种具有非确定性和/或共享性的λ-演算之后,讨论了互模拟为同余的主要证明方法。第三节将介绍我们所研究的λND我们特意选择了一个非常基本的微积分作为进一步研究的起点。由于几个原因,我们将在那里解释,直接与let环境一起工作的λND中的互模拟定义是有问题的,我们在第4节中开发了一种方法,在任意有限深度的环境中进行评估。我们通过调整简化规则来实现这一点,以便互模拟可以基于简化为纯抽象,而无需周围的let环境,同时记录原始环境的每一个可能的结果这使我们能够定义互模拟,并最终在定理5.2通过[11,12]中Howe方法的扩展所谓的“预一致候选”在本节最后给出了它的主要结果,即在λλ中,互模拟匹配语境等价。在第六节中,建立了λND-演算和λ-演算之间的联系。定理6.3的实现是λλ-演算的上下文等价与λND-演算的上下文等价一致它的证明主要依赖于图的方法,例如[14,13]使用它。由于空间的限制,我们目前草图的最重要的证明,并将参考[16]提供完整的证据。2相关工作当然,在扩展λ-演算上已经有很多研究,在如何证明互模拟是这一领域的一个同余上也有相当多的研究。由于似乎不可能考虑到关于这个问题的所有出版物,我们将简要地讨论只有一些相关的工作。84M. Mann/Electronic Notes in Theoretical Computer Science 128(2005)81∗2.1λ-演算中的不确定性与共享性当将非确定性构造引入编程语言或λ演算时,必须澄清一些问题。除了非决定论的分类,例如,在[32]中,我们考虑了一个主要问题,即决定什么样的术语应该被允许复制。没有共享的语言中的非决定论,即那些保留复制(β)规则的语言,例如[24,7,30],与我们的工作完全不同,因为它将区分λx。(x + x),从λx。(2x)。[6]的情况也是如此,因为在显式替换演算中也是如此(参见[10])。[1]),子任务分布在应用程序上,因此是重复的。[4,3,17]的确定性按需调用演算使用let构造(或特殊语法实体,如[3]中的情况)实现显式共享,并将复制限制为抽象。然而,他们的平等理论是基于可转换性,而不是上下文对等。因此,[21,14,13,31]中的演算都提供了非确定性选择,共享和上下文等价,大致代表了我们的研究方向。虽然有一些分歧。由于这些论文没有讨论互模拟,因此在相当初级的微积分中进行我们的研究似乎是明智的,因为这也应该增加可读性因此,像[14,13]的工作一样,λND-演算只有一个非递归let,而[21,31]中的演算提供递归绑定。此外,与[14,13]类似,但与[21,31]相反,λND-演算既没有case也没有data构造器。2.2证明双相似性为同余如前所述,对于结合共享的非确定性λ演算,关于上下文等价的互模拟的研究还不多[2]的lazy lambda演算是一个确定性的,实际上是按名称调用的λ演算。这种指称方法与皮茨的操作技术有关,但[26]不包含非决定论。在纯操作方法中,[28]的规则格式是确定性的,而Howe [11,12]的方法原则上允许非确定性评估。在[10]中,互模拟也显示了一个同余,但是他们的规则格式太受限,无法表示我们的演算。正如Howe已经指出的,[10]中的预同余候选的定义太弱,不能证明在替换下是稳定的[12,引理3.2]。像他早期的工作[11]一样,豪的技术假设每个术语都可以复制,因此必须为了适应分享。尽管没有处理共享,Sands在[27]中展示了M. Mann/Electronic Notes in Theoretical Computer Science 128(2005)8185yxCPHowe的方法的扩展性因此,将我们的工作建立在[11]的基础上的决定看起来最有希望。3λND- 一个λND-演算与[14]的演算非常相似,不同之处在于非确定性选择是由句法结构pick而不是常数建模在图1的文法中,设V表示非E::= V| (英、英) |(设x = E in E)|(pick E E)|(pick E E)Fig. 1. 在语言中的表达式中使用变量的终端因此,语言的术语,称为Λ ND,是变量或由应用程序以及运算符λ,let和pick形成。 由于符号=是let-结构的一部分,我们使用numb来实现语法相等,直到绑定变量的重命名。此外,我们写s[t/x],用t替换s中x的每个自由出现,并采用不同的变量约定,即假设所有绑定变量彼此不同,自由变量也不同。我们隐含地假设这个约定在每个约简步骤之后取有效,因此例如在下面的(cp)-规则的指定中,项λy.r的双重出现不会造成问题。letx=(lety=tint)ins−l−l→etlety=tyin(letx=txins)(llet)Lapp(letx=txins)t−−→letx=txin(s t)(lapp)(λx.s)t−lb−e→ta 设x=tins(lbeta)pickst−n−→dlpickst−n−d→r国家发展银行s(荷兰)t(ndr)NDR−→= −−→−−→(nd)letx=λy.rinD[x]−→letx=λy.rinD[λy.(cp)图二. λND-演算的约化规则86M. Mann/Electronic Notes in Theoretical Computer Science 128(2005)81像往常一样,上下文是一个有一个洞的项,我们用C[s]表示用项s填充上下文C的洞。注意,distinct变量M. Mann/Electronic Notes in Theoretical Computer Science 128(2005)8187俄.西∈ R→−∗约定不适用于在上下文的洞中绑定的变量。λND-演算将配备一个基于小步归约关系的操作语义。我们将从图2中对这些规则进行简要说明。(llet)和(lapp)的目的主要是为了支持--rangelet-用于后续缩减的绑定。普通的(β)-规则被(lbeta)所取代,它只是创建了一个let-绑定。规则(ndl)和(ndr)实现了非确定性选择,并被合并到(nd)中。使用(cp),绑定到抽象的变量的一次出现可以被这个抽象的副本替换。注意,与第4节的λ-演算不同,规则(cp)每次只将抽象复制到一个位置。这不仅与早期的按需调用λ演算(call-by-needλ-calculi)的工作一致(参见:[4,3,17]),但也比同步替换更接近于懒惰函数式语言的实现。AL::=[]eAL::=[]|AL[AL]LR::=letx=ein[]LR::=[]|LR[LR]R::=L<$R[A<$L]|L<$R[letx=A<$LinR[x]]S::=[ ] |eS|设x = e在S中|let x = e in S|设x = S,在e中|pickS e|picke S图三. ΛND的主要上下文类为了获得按需要调用的评估,后面定义的正常阶归约将始终发生在归约上下文中。这些不会在应用程序的论证中引入漏洞,也不会在let的绑定中引入漏洞,也不会在λ项中引入漏洞。 在图3中,和减少和表面处理,文本分别由符号R和S表示。 表面上下文在抽象下没有漏洞,并且将变得更加重要第4节。注意,每个约简上下文也是一个表面上下文。设a∈ {llet,lapp,lbeta,ndl,ndr,cp}是图2中的任何归约规则。我们不知道h−R−,→a是规则(a)在一个约简上下文R中的应用,并写出约简的自反传递闭包。关系。以下定义的正序约简唯一地标识了正序Redex,并且除了非确定性规则之外,也是唯一的。定义3.1 A约化sR,at被称为正常顺序,并由下式表示:n,a−−→s−−→t,如果它是下列之一88M. Mann/Electronic Notes in Theoretical Computer Science 128(2005)81−−−→R−−−→R(i) IfsLR[AL[r]]和规则(lapp)、(lbeta)、(nd l)或(nd r)适用于。(ii) 如果s∈L∈R[letx=A∈L[r]inR[x]],则具有相同的约简系数,该约简系数表示R,使得规则(lapp)、(lbeta)、(ndl)或(ndr)适用于r。(iii) Ifs<$L<$[letx=λy.rinR[x]]n,cpL<$[letx=λy.rinR[λy. [r]]通过规则(cp)对于某个约简上下文R。(iv) 如果规则(llet)应用如下:sLR[letx=(lety=tyn,llet在R[x]中LR[lety=tyin(letx=txinR[x])]t以上定义符合[13],与[4]略有不同,如[13,p.42]中所讨论的。直观地说,它可以描述如下。在(nd)、(lapp)或(lbeta)适用之前,将其描述为形式LR和随后的形式AL的上下文中,情况(i)。如果在此过程中遇到变量只要可能,对所讨论的变量执行(cp)或(llet),即(三)、(四)分别。 否则,在情况(ii)中,如果这些变量基于应用程序,详细说明到A类-约束条件,可以应用(ND)、(LAPP)或(LBeta)。然后,收敛的概念由L∈R[λx]的正规阶约简序列定义。t],即, a w eakheadnormalform,WHNFforsshort. 所以我 们 写st如果和 o如果 s→−nt和t是 一个WHNF,s如果存在这样的t和s/如果没有。显然,正规阶约化既不是连续的,也不是终止的,即,一项可以简化为多个弱头正常形式或根本没有。由于确定正规序redex的过程相当复杂,因此如何直接用结构化操作语义表示正规序约简并不明显。 例如,[12]的结构化评估系统,除了适合大步骤操作语义之外,似乎不能够做到这一点。这是因为正规阶可约项和弱头正规形都可以用let算子形成3.1语境对等收敛,如前一节所定义的,展示了所谓的“必须趋同”的概念即所有以s开始的正规阶约简序列都导致WHNF,这对于非确定性演算也是有意义的(参见。[21、13、31])。然而,为了简单起见,以下定义仅考虑M. Mann/Electronic Notes in Theoretical Computer Science 128(2005)8189R定义3.2上下文近似4ΛND,c定义为:s4ΛND,ctC:C[s]=C[t]和语境对等ΛND,c乘sΛND,ct乘s4ΛND,c t乘s 4 Λ ND,ct乘s4ΛND,cs.目标是定义互模拟,使其符合上下文等价性。 下面的例子清楚地表明,不可能使用通常的例3.3令组合子K(λ z. z z)(λ z. z z)照常。则 sletv= pickK K2inλw.vand t<$λw. pickK K2 可 以 通 过 上 下 文Cletf= [] in((fK)(fK)K)以如下方式区分:关于t,我们可以构造一个正规阶约简序列C[t]→−nL[K],其中由于v是共享的,因此对于C [ s ],不存在正规阶约简序列。显然,项s和t是弱首范式,如果应用于任意(哑元)参数,两者都可能产生K或K2。因此,s和t不能通过应用于论证来区分。前面的例子还揭示了在λND-演算中变换λy。设x = s in t ~设x = sin λy.t,即在λ上移位let,通常对于w.r.t.语境对等之所以如此,是因为项let v = pick K K2 in λw.v变成了λw。设v=在v中选择K,这一转变的反向应用。人们可以简单地通过这两个术语的例子,或者,论证后者是上下文等价的(参见。[13,规则(UCP)])到示例中的项T这个例子表明,由于let环境,弱中心范式不携带足够的信息,以便仅通过应用于论点来区分。可能有几种方法可以调整互模拟,以便上述类型的例子工作,但不清楚哪一个将真正产生互模拟的合适定义。我们消除环境的方法还有一个额外的好处,那就是证明预同余候选在规则(llet)下是稳定的,这对于我们尝试过的定义的其他变体来说似乎是不可行的。因此,在我们介绍通过收集所有可能的结果来消除let-环境的特殊演算λND之前,我们通过一个例子来说明在λND-演算中,规则(llet)通常是找到WHNF所必需的90M. Mann/Electronic Notes in Theoretical Computer Science 128(2005)81≡n,cpSλ≈例3.4考虑项sletx=(lety=tyinλz.t)inx通过以下正规阶约简,其显然具有WHNF:设x=(设y=tyinλz.t)inxn,llet−→lety=tyin(letx=λz.tinx)−→lety=tyin(letx=λz.tinλz. t)的范围内显然,(llet)的效果不能通过(cp)规则的不同范围或目标来实现。显然,复制整个环境让y=tyinλz.t通常也是没有选择的,因为例如,为一个形式为letf=(lety=pickK K2inλx.x y)的项在f(f<$)中,会改变它的价值上下文近似4λND-演算的λλ-如图4所示,一个特殊的常量被添加到语言中,现在用Λ表示。图5中λ演算的归约规则演变为E::= V|◎| (λx.E)| (E E)| (let x = E in E)| (pick E E)见图4。 在语言中的表达式在λND中,如下所示。首先,通过规则(停止),可以减少每一个非确定性的条款,以确定性,进一步的非决定性的水平被引入。由于没有关于简化的规则,因此这限定了简化,即,评估被修剪下面。随着微积分的现有非确定性,我们将利用规则(停止)来表示每个项,可以说,一组已经评估到不同深度的项。由于我们的目标是消除顶级环境,因此很自然地完全复制无法进一步减少的术语,即重复和抽象,并并行地垃圾收集它们与规则(cpa)的绑定。所以我们可以在第6节中表明,原来的(cp)规则已经过时。此外,所有这些约简将允许在任意表面上下文内进行,这些表面上下文如前所述由符号因此,也不需要规则(llet),因为我们可以在使用(cpa)折叠let环境之前,首先在let我们将给予更多在第6节中,我们详细介绍了这一过程,在λND和λπ中重合。如上所述,λ演算的约化可以发生在surfacecontexts;hence-S-,→a表示规则(a)在side中的应用M. Mann/Electronic Notes in Theoretical Computer Science 128(2005)8191λ≈λ≈λ≈◎◎CPAλ≈−−−→Lapp(letx=txins)t−−→λletx=txin(st)(lapp)(λx.s)t−lb−e→ta letx=tins(lbeta)pickst−n−→dls(ndl)pickst−n−d→rt(ndr)letx=sint−−→λ<$t[s/x](cpa)其中s<$λz.q或s<$λ停止s−−→λ<$ifs/<$(stop)图五. λ-演算的约化规则任何表面上下文S∈ S。由于在使用规则(stop)切割o之前,可以计算任意深度,因此我们称之为近似约简,如果否,则省略本节剩余部分的下标λ。混乱出现了。然后定义了λ-bys<$λx.t<$$>s−→S <$λx。t,即如果存在一种不对称还原,一个抽象的序列。4.1归约序列在互模拟证明的预期中,可以证明规则(cpa)和(lbeta)的应用永远不会对近似约简序列造成任何损害。在前者的情况下,这仅对w.r.t.有效在任意上下文中的一些(停止)-约简C,停i,C,停定义4.1−→-reduction被称为内部,由−→定义,如果C ∈ C是一个C_n_t,而C_h不是一个表面C_n_t,则C ∈ C是一个C_n_t.C ∈/S。这些内部(停止)归约可以总是移动到近似归约序列的末尾。引理4.2设s,λx.t∈Λ与s(s)成项i,停止)λx.t. 然后∗≈−→λ≈∪−−∗−→这是一个关于S−→S的推论λx.tJ使得λx.tJi,停止λ≈λx.t成立。内部(停止)-减少可能成为必要的清理分叉情况如下。考虑一个普通的(停止)归约应用于一个绑定到let表达式中的变量的抽象的情况如果规则(CPA)92M. Mann/Electronic Notes in Theoretical Computer Science 128(2005)81−−−→J−−−→−→λλ≈−−−−→−→当且仅当t−→λ≈是后来用于这个let表达式,前面介绍的术语可以在抽象中找到。因此,上述(停止)-和(cpa)-减少的简单交换不能达到相同的效果。因此,我们可以证明,对于每一个收敛的近似约简序列,优先约简的规则(cpa)导致一些内部(停止)约简延迟的抽象。Lemma4. 3Lets,sJ,λx. tbe项sothatsS,cpasJ和s−→Sλx.t保持不变。则SJ具有抽象λx.tλ≈其中,从λx.t只通过内部(停止)-减少,即λx.tJi,停止<$λx. t。对于规则(lbeta)的约简,适用更强的陈述。也就是说,如果(lbeta)适用于表面上下文,则是否首先执行不同的约简并不重要。引理4.4设s,t是使得S,l βt保持。 对于所有的AB-我们有sS<$λz.q−→−→Sλz.q成立。引理4.3和4.4的证明使用了完全分叉集的技术,在引理4.2的情况下,使用了交换图(参见图1)。[13、31])。更多详情见[16,第2.3.1节]。另一个重要的结果是重新排序收敛近似约简序列,使约简首先发生在let绑定内部。定理4.5对于每一个约化,设x=sintS≈以下形式的近似约简序列:λz.q也有一个letx=sint−l−et−−x−=−S−i−n→t令x=sJint[ ],cpat[sJ/x]Sλ≈ λz.q其中SJ表示抽象或抽象。证据 关于近似约简序列长度的归纳 Q4.2相似性由于规则(stop)和(cpa),我们现在有可能为抽象提供关于其let环境的信息,直到任意深度。这一事实将通过非决定论加以利用,即通过考虑所有可能的近似约简到抽象。我们想强调的一点是,我们正在寻找一种方法来证明λND-演算中的上下文等价性。 因此,我们对λND本身的相似性的通常概念不感兴趣-例3.3已经λ≈M. Mann/Electronic Notes in Theoretical Computer Science 128(2005)8193≈≈·⊆ ⇒⊆≈不同意语境近似-而是在一个表征的语境对等,表现出更多的操作风格。因此,像Abramsky [2]和Pitts [26]一样,我们使用熟悉的术语“互模拟”和“双相似性”。然而,我们随后将发展的关系将被拉森和皮彻[15]归类为定义4.6操作[·]次数:Λ0×Λ0 →Λ0 ×Λ0关于关系封闭式术语的定义如下:≈ ≈ ≈ ≈sJ[η]<$tj<$$>λx.s:(sJ<$λx.s=<$r:r∈ Λ0,称为实验。一个关系式η<$Λ0× Λ0=<$(λx.s)r η(λy.t)r))是一个模拟,如果η<$[η]<$。它是单调的,即,η1η2=[η1]η 2[η2]η,存在最大的固定点定义4.7定义相似性4b为[·]的创建固定点,I.E. 4b=gfp([·]),并且双相似性是4bt4bs.因此,两个项s和t被认为是双相似的,只要它们的近似约简导致抽象的集合,使得如果应用于任意参数,则每个集合中都有双相似的元素。下一个例子强调,这正是我们需要获得与上下文相同的区分术语的能力。例4.8众所周知,两项s∈v=pickK K2inλw.v和t <$λw. 例3.3的pickK K2可以通过上下文来区分现在我们可以证明tb s也不成立。 既然t已经是抽象,因此我们考虑导致抽象的s设v=[ ]inλw.v,ndls−−→设v=K在λw.v设v=[ ]inλw.v,ndr[ ],注册会计师−→ λ w。K[ ],注册会计师s−−−−−−−−−−−−→letv=K2inλw.v−−−→λ w. K2由于非确定性选择已经固定,这些抽象都没有暴露必要的行为。特别地,当应用于自变量序列λ,λ,K和λ,K,λ时,t可以收敛。对于前者,K不收敛,λw也不收敛。K2为后者。下面是一个证明的例子,它对相似性很直接,但似乎涉及到使用上下文近似的定义。94M. Mann/Electronic Notes in Theoretical Computer Science 128(2005)81≈⇓ ⇓⇓∈≈≈例4.9设r,s,t∈Λ0任意封闭的条件。 然后我们有r4bts4bt=选择r s4bt即,如果T表现得 假设选择r sλy.p,则rλy.p或sλy.p. 因为通过这个前提我们有r4bt和s4bt,所以这个命题被证明了.现在我们将相似性扩展到开放项。这样做的动机是双重的。首先,当处理封闭项时,全等的概念意义不大。 例如,在一个示例中, 对于闭s,从s<$bt推断λx.s<$bλx.t,t不会得到太多,因为x只是一个虚拟变量。 第二,证据方法与4b的扩展密切交互以打开术语。所以我们必须记住哪些项可以在λ演算中复制。由于这仅适用于抽象和抽象,因此使用所有关闭替换的技术并不适用,如以下示例所证实的。例4.10考虑xx中的开放项ff和letx=f,它们在λND演算中是上下文等价的,因为允许复制变量[13]中规则(LCV)的正确性但是要求每一个闭代换的项都是双相似的是不可能的:(ff)[pickKK2/f]可以产生K K2,按照例3.3的思路,如果连续应用于参数,和K,则K K2收敛,而(令x=finx x)[pickK K2/f]显然不是。因此,我们需要的是一个限制的替代,使自由变量只映射到封闭或封闭的抽象。定义4.11设s,tΛ(可能是开放的)。然后我们写s4bot当且仅当σ(s)4bσ(t)对所有闭置换σ成立,range rng(σ)满足rng(σ)<${p∈Λ0|p<$$>p<$λz.q}。在[16,4.7节]中,我们证明了一个等价的概念可以通过考虑所有闭let环境来定义。4.3预全等候选人在这一节中,让τ 代表 Λ- 语言的任何运算符(即, λ、let、pick或application),并且i表示其操作数序列。我们用a iη b i表示a iη b i对每个i成立的条件。一个关系η ηΛ η× Λ η称为算子相关的,或相容的,当且仅当a iη b i意味着τ(ai)η τ(bi)。预同余是相容的预序。M. Mann/Electronic Notes in Theoretical Computer Science 128(2005)8195^^^^^ ^您的位置:^^ ^您的位置:我我我≈下面定义了一个关系,它在定义上是相容的,但不一定是传递的。目的是表明它与4bo相一致,本节将为4 b o制定标准定义4.12设η=Λ0× Λ0成为一个preorder。 然后定义它的预聚体,≈ ≈encecandidate4^bΛ×Λby• x4bb,如果x∈V是一个变量,且x4bob.• τ(ai)4^bbi,如果存在aJ,则存在ha tai4^baJ和τ(A J)4bob。Howe [11,p. 201]恰当地给出了一个非正式的解释,即a4bb如果b可以通过一个自下而上的过程从a得到,用在4bo下更大的项替换子项。 如前所述,在λ演算中,只有抽象和抽象可以被复制。因此,以下两个引理反映了我们的[11,引理1]和[12,引理3.2]分别对应。引理a4.13Letb,bJ∈Λbe项. 则b4^bbJ蕴含b[<$/x]4^bbJ[<$/x]。引理4.14对所有b,bJ∈Λ0和闭抽象λz.r,λz.rJ∈ Λ0b4^bbJλz.r4^bλz. RJ蕴涵b[λ z]。r/x]4^bbJ[λz. rJ/x]。的这两个引理都是通过对预一致性的定义进行归纳来证明的。我们利用4bo定义的优势。令下面的η0代表前序η<$Λ×Λ的限制对于闭项,即η0=ηι Λ0× Λ0,那么从上面我们可以表明:≈ ≈定理m4.15r(4^b)0<$4b成立,当且仅当4^b<$4b,当O且仅当 4 bo是一个预同余。我们将建立第一个集合包含(4b)04b,通过共归纳,从(4b)0[(4b)0]开始,ce4b中的s是[·]的固定顶点,包含所有模拟。为了对收敛近似约简序列的长度使用归纳法,我们必须证明(4b)0在每个单步约简下都是保持的。5相似是预同余的在每一步约化下保持(4 b)0等于s(4b)0ts−→SλsJ隐含ssJ(4b)0ti,其中s,sJ, t都是闭项。请注意,只有封闭的表面上下文,即那些开放项可以是封闭的,涉及某处的LR上下文。可以证明,对于每个收敛的近似约简,也存在相同抽象的近似约简序列,其中96M. Mann/Electronic Notes in Theoretical Computer Science 128(2005)81≈≈联系我们在闭合表面环境中不发生近似简化。因此,在下文中,在封闭的条件下审查最高级别的削减是足够的。引理5.1设r,s∈Λ0[ ],abeee d e e et e eete er−−→λns保持不变。然后对于每一个dt∈Λ0,我们有:r(4^b)0t蕴涵s(4^b)0t。证据 在ndl,ndr的情况下,停止 这种说法是显而易见的。 剩余的归约规则是通过归纳法定义的预同余候选,其中对于(lapp)和(lbeta)相容性为4bw.r.t.应用形式([ ]e)的上下文。该规则的证明(cpa)是在分别利用引理4.13和4.14的情况下,区分了抽象和Q值得注意的是,凭借豪的方法,我们得到了一个模块化的证明。如果新的归约规则被添加到演算中,证明将很容易扩展,因为它可以为每个规则单独完成此外,使用(cpa)而不是(cp)极大地简化了问题,因为通过集成垃圾收集,不需要在let环境中跟踪复制到其绑定的目标位置的术语定理5.2相似4b0是一个预同余.证据 利用引理5.1,定理4.15的前提得到满足。Q由于语言Λ包含严格比ΛND更多的上下文,由于常数λ,我们单独定义λ的我们将在第6节中展示这些上下文不会增加任何计算能力。定义5.3λλ的上下文近似4Λε,c定义为:s4Λ,ctC:C[s]=C[t]和语境对等Λ,cbysΛ,cts4Λ,ctt4Λ,cs.根据定理5.2,它变得几乎直接地表明相似性4bo与λ演算中的上下文近似一致。定理5.4设s,t∈ Λ ε是项。 则s4botis4Λct保持。6λND与λ<$中相等的对应由于我们的目的是证明λND-演算中的上下文等价性ΛND,c,我们有义务证明这确实是相同的M. Mann/Electronic Notes in Theoretical Computer Science 128(2005)8197∈λλND作为λ-演算中的上下文等价关系Λε,c。因此,我们首先回顾一下上下文近似是如何定义的:s4ct(C:C[s]=C[t])很明显,4ΛND,c和4ΛN,c的对应需要以下性质:对于每一项t∈ΛN,存在到弱头标准形的标准阶约化当且仅当t有近似约化为抽象概念因此,我们理解λND中的正规阶约化的概念以明显的方式扩展到从Λ开始的项,即把Λ看作一个没有正规阶约化的常数。此外,可以证明,对于每个区分两个项s,t的ΛND-上下文C,也存在ΛND -上下文Cj,使得CJ[s]收敛,但CJ[t]不收敛,反之亦然。为此目的,我们可以从C得到CJ,只需将所有出现的替换为,其正规阶约化不终止。因此,ΛND和ΛN的上下文在区分项上是同样有力的,并且我们还从上述讨论中得到了一个充分的条件财产也就是说,我们可以在下面集中注意两个演算之间的收敛归约序列的变换。6.1变换−→S-intoo→−n-red sequenc ess构造WHNF的正规阶约简的过程是通过对收敛近似约简的长度进行归纳。由于(cpa)和(nd)是在一个步骤中达到抽象的唯一近似约简,因此归纳基础应该是清楚的。对于归纳步骤,它是然后表明,每个近似reduc- tion可以移动到正常秩序的减少序列的末尾。对于在不是约简上下文的表面上下文内执行的近似约简,这是一个明显的任务,因为相应的上下文是不相交的。因此,只有在约简上下文中的规则约简(cpa)才是特别感兴趣的。对于这些,在[16,第5.1节]一套完整的通勤图w.r.t.建立了正规阶约简。不重复−R−,−c−p→a-r导出和hence的图形可以通过归纳得出以下结果。Lemma6. 1Letr,λx. s∈Λbetermssuchthatr−→Sλx.s成立。然后nλ当r为WHNF时,r也是正规的或正规的推论r →-λ ND。证据使用上面讨论的参数,将近似约简序列的长度归纳为抽象。Q98M. Mann/Electronic Notes in Theoretical Computer Science 128(2005)81λλNDND6.2变换→−n-into−→S-red sequenc es因为每个约简上下文也是一个表面上下文,所以唯一不是近似约简的正规阶约简是由规则(cp)和(llet)得到的。因为对于(cpa),前者在λ-演算中有对应物其治疗并不困难。但是为了使后者超连续,必须调整约简策略,使得对于R[x]中的letx=(lety=tyintx)这样的项,近似约简首先在lety=tyintx内进行,直到约简得到一个抽象,可以使用(cpa)将其复制到R[x]中。由于定理4.5,这个过程总是可能的,并且也可以递归地应用于上面场景的tx中的子项lety=ty引理6.2设r,s∈Λ最好是mssuchthats是WHNF且r→−ns公司简介保持。然后还有一个近似约简r抽象−→Sλλx.ttosome证据 关于正规阶约化序列长度的归纳法。 Q把所有这些部分放在一起,我们实现了相似性与上下文近似的对应,无论是在λND-演算还是在λπ-演算中。定理6.3设s,t∈ Λ ε是任意λε-项. 则s4bt成立,当且仅当s4<$ND,ct成立,当且仅当s4<$ND,ct成立。我们在λND-演算中证明上下文等价的主要目标现在变成了一个简单的推论。推论6.4对所有项s,t∈Λ ND,我们有s∈boti ∈sΛ,ct保持不变。7结论和今后的工作据我们所知,第一次为非确定性按需调用演算定义了一个合理的互模拟互模拟是一个同余的证明扩展了豪首先,我们已经看到,通过将项简化为弱头范式并将这些WHNF应用于任意参数来测试项是不合适的。相反,要测试的术语必须具备关于哪些选择必须被共享,哪些选择可以被复制的所有信息。我们通过在每个任意深度的表面上下文内执行评估来实现这一点,其中let环境中的选择也可以M. Mann/Electronic Notes in Theoretical Computer Science 128(2005)8199强求由于我们非确定性地收集所有这些可能的结果,因此我们有足够的潜力来区分术语。另一个方面涉及可以被复制的术语的种类。正如我们所看到的,前一致候选,或者严格地说,双相似性到开放项的扩展必须被调整,使得只有双一致和双相似项才是开放项。抽象的考虑。 这可能会为证明基本替换引理的基本替换引理的在这些解释的基础上,我们确信本文所展示的技术对于处理一种用case和data构造器扩展λND这也可能是值得的,应用本文的结果的设计和结构操作语义学的一般和纯句法系统的定义,例如,像[12]的结构化评估系统,但适合于非决定论与分享相结合。如前所述,语境对等既不考虑必然趋同,也不考虑与之同等的发散。就像[21,13,31]的工作所建议的那样,在非确定性演算中将可能视为有限个约简序列是非常合理的因此,作为λND-演算的进一步扩展,可以合并不同的行为所以,如果s有一个非-终止正常秩序的减少,一个可能的-和明智的-定义的上下文等价可能会给出sct((C:C[s]C[t])(C:C[s]C[t]))使用上下文近似,可以以若干方式建立上述上下文等同。
下载后可阅读完整内容,剩余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直接复制
信息提交成功