没有合适的资源?快使用搜索试试~ 我知道了~
理论计算机科学电子札记127(2005)21-41www.elsevier.com/locate/entcs循环高阶项图的重写演算C. Bertolissia,P. Baldanb,H. Cirsteaa,C. 基什内尔aaLORIA INRIA INPL NANCY II54506Vandoeuvre-l`es-NanncyBP23 9CedexFranncebDipartimenodInormatino din ormati noti摘要重写演算(Rewriting Calculus,简称ρ-calculus)是在90年代末提出的一种将项重写和λ-演算完全结合起来的重写规则,作为详细的抽象,其应用和获得的结构化结果是微积分的第一类对象。在各种理论中,评价机制,推广β-归约,强烈依赖于术语在本文中,我们提出了一个扩展的ρ-演算,处理图形的结构,而不是简单的条款。转换是通过将重写规则作为第一类实体显式应用来执行的。表达共享和循环的可能性允许人们表示和计算规则的无限实体。项上的演算可以通过在标准的ρ演算匹配约束之外使用统一化约束来自然地推广因此,这为我们提供了显式替换演算到项图的自然扩展的基础几个例子说明了所介绍的概念。关键词:重写演算,循环lambda演算,项图,匹配和统一约束。介绍术语重写的主要兴趣来自于基于函数和重写的语言以及定理证明。特别地,我们可以通过分析相关项重写系统的一些特性来描述函数式或基于重写的程序的行为。在这个框架中,术语通常被视为树,但为了提高这些语言实现的效率,将术语视为图[7]是一个根本的兴趣。在这种情况下,共享子项的可能性允许节省1571-0661 © 2005 Elsevier B.V. 在CC BY-NC-ND许可下开放访问。doi:10.1016/j.entcs.2005.01.03422C. Bertolissi等人/理论计算机科学电子笔记127(2005)21Cc你好,、、、−→+x,svszyJCc1Jc(a) 使用图重写规则的(b) 在无限的列表中,Fig. 1.术语图空间(通过使用指向同一子项的多个指针而不是复制子项)和节省时间(出现在共享子项中的redex将最多减少一次,并且当共享最大时,可以在恒定时间内完成相等性测试我们可以以重写系统R ={x≠ 0 → 0,x<$s(y)→(x<$y)+x}。 如果我们代表如果使用图形,我们将通过复制对x的引用而不是复制x本身来编写第二条规则(参见图1)。图重写是优化函数式和声明式语言实现的有用技术[21]。此外,定义循环的可能性增加了表达能力,使人们能够轻松地表示例如,循环列表ones= 1:ones,其中循环项图重写已经被广泛研究,无论是从操作[7,2]还是从分类/逻辑的角度[10](参见[22]关于项图重写的调查在此背景下,Z.M. Ariola和J. W. Klop [3].他们的方法由一个方程框架组成,该框架模型扩展了显式递归的λ演算。λ-图被视为一个包含λ-项的递归方程组,重写被描述为一系列方程变换。这项工作允许图形结构与λ演算的高阶能力相结合最后一个重要的成分仍然缺失:模式匹配。使用模式匹配进行区分的可能性可以被编码,特别是在λ演算中,但是它更有吸引力的是直接区分和使用重写。程序变得非常紧凑,不再需要对数据类型结构进行编码。重写演算(简称ρ演算)是在90年代后期作为项重写和λ演算的自然推广而引入的。].它已经被证明是一个非常有表现力的框架,例如表达对象演算[12],并且它已经配备了强大的类型系统[5]。:,s,sxsJ,zy、、,,、C. Bertolissi等人/理论计算机科学电子笔记127(2005)2123ρ-演算的一个重要组成部分是由β-约简的推广生成的匹配约束,称为ρ-约简。通过使这个匹配步骤显式化,并且匹配的约束是演算的第一类对象,我们可以允许显式处理约束而不是替换[9]。本文的第一个贡献包括一个新的系统,称为ρg-演算,它推广了循环λ-演算,因为标准ρ-演算推广了经典λ-演算。ρg-演算处理具有约束变量的循环项,并且可以通过一系列递归方程来表示垂直共享和水平共享。在ρg演算中,与匹配相关的计算是显式的,并在对象级执行然后我们证明ρg-演算可以模拟普通的ρ-演算。为了做到这一点,我们证明了匹配在ρg-演算中表现良好w。R. t. ρ-演算的匹配算法,以及对任何ρ-约化,ρg-演算都存在相应的约化.通过证明循环λ-项可以转化为ρg-演算以及循环λ-约简可以在我们的系统中模拟,我们还证明了ρg-演算是循环λ-演算的自然推广因此,我们得到了循环λ-演算和ρ-演算的共同推广,提供了一个框架,其中匹配,图形结构和高阶能力是原始的。本文的结构如下。在第一节中,我们简要回顾了启发我们新微积分的两个系统:标准ρ-微积分[?[1]和循环λ-演算[3]。第二节和第三节分别描述了ρg演算的语法和小步语义,给出了系统中的一些项和项约简的例子。在第4节中,我们证明ρg-演算是ρ-演算的推广,并证明循环λ-约简如何在ρg-演算中模拟。最后,我们在第5节提出了未来工作的一些观点。1重写演算和循环lambda演算本文简要介绍了启发本文所介绍的微积分的两种形式。1.1重写演算引入ρ演算是为了使重写显式对象的所有基本成分,特别是规则抽象(D)、规则应用和结果集(;)的概念。在ρ-演算中,通常的λ-抽象λx.t24C. Bertolissi等人/理论计算机科学电子笔记127(2005)21(ρ)( T1DT2) T3→ρ[T1T3]T2(σ)[T1T3]T2›→σσ ( T1T3 ) ( T2 )(δ)(T1; T2)T3→δT1T3; T2T3图二. ρ-演算的小步语义用一个规则抽象T1DT2代替,其中T1和T2是两个任意项,T1的自由变量在T2中有界.ρ项的集合定义如下:T::= X| K| TDT|[TT] T| T T| T; T符号T,U,L,R,. 在项的集合T上的范围,符号x,y,z,. 在变量集合X上的范围,符号a,b,c,. ,f,g,h的范围在常数集合K上。小步长归约语义由图2中给出的评估规则定义。将重写规则(抽象)应用于一个术语,通过规则(ρ)评估将相应的约束应用于重写规则的右侧。这种构造称为延迟匹配约束。约束项的主体将根据相应匹配问题的结果进行评估或延迟。如果存在解,则延迟匹配约束的值为σ(T2),其中σ是T1和T3之间匹配的解。 的匹配能力ρ演算可以用任意的理论来调节。这里我们考虑空理论下的ρ-演算(i. e.语法匹配),其是可判定的并且具有唯一解。从这些顶层规则开始,我们定义,通常,上下文闭包表示为→ρσδ。多步求值→ρσδ被定义为→ ρσδ的自反传递闭包。1.2循环lambda演算Ariola和Klop提出的循环λ-演算包含了一个用循环重写项图的方程框架。 它通过增加一个letrec结构扩展了λ-演算,在某种程度上,称为λ-图的新项被表示为标准λ -项上的(可能嵌套的)递归方程组。如果系统在没有规则限制的情况下使用,则会失去连贯性。作者通过控制递归方程的运算来恢复它。由此产生的演算,称为λφ[3],足够强大,可以合并经典的λ-演算[4]和λμ-演算[20],C. Bertolissi等人/理论计算机科学电子笔记127(2005)2125JJJ(β)(λx. t1)t2→β 第1章|x= t2(外部子)Ctx{y}|y = t,E→es Ctx{t}|y = t,E(acyclic sub) |y=Ctx{x},x=t 2,E→ac 第1章|y=Ctx{t 2},x= t 2,E=如果y > x(黑洞)Ctx{x}|x= x,E→· {·}|x= x,E阿勒特|y=Ctx{x},x= Ctx x,E= Ctx→·|y=Ctx{·},x= Ctx x,E= Ctx如果y > x(garbage collect)(垃圾收集)|E,E→gc 阿勒特|E如果E f=g和E(E,t)阿勒特|g→ gc t图三.λφ 0-演算的求值规则[1]中的λσ-演算分别以水平分担和垂直分担进行了推广。λφ的语法如下:t::= x|f(t1,. t n)|t0t1|λx.t|最大值0| x1= t1,.,x n= t nλφ-项的集合由普通λ-项(i. e.变量、固定元函数、应用程序、抽象)和使用letrec结构构建的新术语:|x1= t1,.,xn= t nn n,其中我们假设递归变量x i,i = 1,.,n,全部不同。我们用E表示一个无序的方程序列x1= t1,.,xn=t n,并且通过n = 0,得到空序列。术语由符号t、s、. . 变量由符号x、y、z、. 常数用符号a,b,c,.、f、g、h。上下文Ctx{}是在子项的位置具有单个孔Q的项用项t填充上下文Ctx{Q}产生项Ctx{t}。变量要么被lambda抽象绑定,要么被递归方程绑定。我们表示为≤递归变量的最小前序,使得x≥y,如果x=Ctx{y},对于某些上下文Ctx{ }。我们写x > y,如果x≥y和x/y,其中是由前序i诱导的等价。e.如果x ≥ y ≥ x,则x ≠ y(变量x和y出现在一个循环中)。记E∈(EJ,t),如果E的递归有界变量不与EJ和t的自由变量集相交,则E与一列方程EJ和一项t正交。符号x= x1,.x是递归方程序列x=x1,.的缩写,xn= x。图3给出了基本λφ0-演算的归约规则。这组基本规则的一些扩展可以考虑[3],分布规则(λφ1)或盒合并和消除规则(λφ2)。在下文中,我们将把注意力集中在图3的基本系统上。在β规则中,由λ约束的变量x变为由递归方程约束减少后。 这两个替换规则用于复制与递归变量相关联的图。对命令的限制26C. Bertolissi等人/理论计算机科学电子笔记127(2005)21递归变量被引入以确保在lambda赎回的循环配置的情况下的一致性无环子和黑洞规则中的条件y > x是必要的,以确保系统的连续性。规则垃圾收集规则中的条件EJ/=1避免了琐碎的非终止性约简。我们用<$→λφ表示由图3的规则集导出的重写关系,用→λφ表示它的自反和传递闭包。2ρg-演算的语法图4中给出的ρg-演算的语法扩展了标准ρ-演算和ρx-演算的语法[9],即:e. ρ-演算及其显式匹配和替换应用。项G1DG2表示重写规则(即,e. 抽象),其中术语G1被称为模式。有两种不同的应用操作符:函数应用操作符简单地用连接表示(在图形表示中用@表示),约束应用操作符用“[ ]”操作符表示。项可以被分组到使用运算符“;“构建的结构中,并且根据该运算符背后的理论,我们可以获得例如多集合(对于结合交换运算符)或集合(对于结合交换幂等运算符)。该运算符用于表示一组重写规则的(非确定性)应用从这个角度出发,项重写系统(和底层策略)可以在ρ-演算中编码[14],我们猜想这种编码可以扩展到ρg-演算中的项图重写系统。和ρx-演算一样,ρg-演算明确地处理形式为G G的匹配约束,但它也引入了一种新的约束,即递归方程。一个递归方程是一个形式为X=G的约束,可以看作是一个延迟的替换,或者是一个与一个项相关联的环境。在ρg演算中,约束是匹配方程和递归方程的合取(使用运算符“,”空约束用表示。假设运算符我们假设应用程序操作符关联到左侧,而其他操作符关联到右侧。为了简化语法,运算符具有不同的优先级。以下是优先级从高到低排序的运算符:application“ “ 、 “ d “ 、 “ ; “ 、 “ [] ” 、 “ “ 、 “ = “ 和“ , “ 。符号G,H,…在项x,y,z,.的集合G上的范围。在变量集合X上的范围(X <$G),a,b,c,.,f,g,h在一组常数K上的范围C. Bertolissi等人/理论计算机科学电子笔记127(2005)2127方面G::= X(变量)| K(常数)| G DG(抽象)| G G(功能应用)| G; G(结构)| G [C](限制应用)约束C::=空(空约束)|X = G(递归方程)| GG(匹配方程)| C、C(约束条件的结合)见图4。 ρ g-演算的推广(K G).符号E、F、. 在约束的集合C上的范围。我们把形式为(fG1)G2)的项称为代数项。. )G n,其中f ∈ K,我们通常用f(G1,G2,. ,G n)。我们用·(黑洞)来表示一个常数,这个常数已经由Ariola和Klop [2]使用方程方法引入,也由Corradini [15]使用范畴方法引入,以给对应于表达式x [ x = x ](自循环)的“未定义”项命名记法x= x1x也是序列x=x1,.的缩写。,xn= x。我们将符号Ctx{Q}用于恰好具有一个孔Q的上下文。 我们说一 个 ρg- 项 是 非 循 环 的 , 如 果 它 不 包 含 Ctx0{x0}Ctx1{x1} ,Ctx2{x1}Ctx3{x2},.,Ctxm{xn}Ctxm+1{x0},其中m∈N且∈{=,}. 这两个序列中的k称为一个周期。ρg-项的自由变量和约束变量的概念考虑了微积分的三个结合:抽象、递归和匹配。特别地,为了简化定义,我们还引入了约束C的域,记为DV(C),作为由它包含的递归和匹配方程定义的变量集(潜在地)集合DV(C)包括,对于C中的任何递归方程x=G,变量x,并且对于C中的任何匹配G1G2,集合G1的自由变量定义2.1[自由变量、约束变量和定义变量]给定ρg-项G,其自由变量表示为FV(G),其约束变量表示为BVar(G),28C. Bertolissi等人/理论计算机科学电子笔记127(2005)21递归定义如下:GBV(G)FV(G)X∅{x}K∅∅G1G 2BV(G1) BV(G2)FV(G1) FV(G2)G1; G2BV(G1) BV(G2)FV(G1) FV(G2)G1DG 2FV(G1) BV(G1) BV(G2)FV(G2)\ FV(G1)G0[C]BV(G0) BV(C)(FV(G0) → FV(C))\DV(C)对于给定的约束C,自由变量表示为FV(C),约束变量表示为BVar(C),定义变量表示为DV(C),定义如下:CBV(C)FV(C)DV(C)G∅∅∅x=G0xBV(G0)FV(G0){x}G1G 2 FV(G1) BV(G1) BV(G2)FV(G2)FV(G1)C1, C2BV(C1) BV(C2)FV(C1) FV(C2)DV(C1) DV(C2)在λ-演算中使用的α-转换概念可以自然地推广到处理ρg-演算的项在循环λ-演算中,我们定义了递归变量的顺序,即,由递归和匹配方程约束的变量:我们用≤递归变量上的最小前序表示,使得x ≥y,如果x = Ctx{y},对于某些上下文Ctx{ }。由预序导出的等价性记为x,我们说x和y是循环等价的(x<$y),如果x≥y≥x(它们在一个公共循环上)。 我们写x> y,如果x ≥ y和x/y。正如我们在后面将要看到的,这个顺序给了我们只允许向上替换的可能性为了支持这种直觉,下面我们有时给出不包括匹配约束的ρg-项的图形表示。这种对应关系仅在论文中非正式地使用,但它可以被精确地使用,例如,沿着[6]中的工作路线,对于具有粘合剂的循环项图。粗略地说,任何没有约束的项都表示为一个非循环图,显然,约束G [x1= G1,.,xn= G n]被读作letrec构造letrecx1= G1,.,xn= G n在G中并且通过循环表示结构在这里,规则右侧的变量与其在模式中的绑定事件之间的对应关系是通过保留变量名(而不是使用后指针)来表示的。这种对应关系并不直接延伸到一般的ρg项,可能包括匹配约束,其合适的图形表示仍在研究中。C. Bertolissi等人/理论计算机科学电子笔记127(2005)2129X0Dcons,f、、. . . .、、cc,,sc,,z+,。S.头,,z,s科奥伦斯ccJc、、、,zzgzCcc2Jcvzzf,oJXJ(i)(ii)(三)图五. 一些ρ g-项例2.2[一些ρg-项]有关这些项的图形表示,请参见图5。(i) 在规则(2<$f(x))D((y+y)[y=f(x)])中,当该规则应用于ρg-项时,右侧的共享避免了复制实例化f(x)的对象(ii) ρg项cons(head(x),x)[x=cons(0,x)]表示无穷多个零。请注意,递归变量x绑定x在约束的右侧cons(0,x)中的出现,以及约束所应用的术语cons(head(x),x)中的出现(iii) ρg-项f(x,y)[x=g(y),y=g(x)]是扭曲共享的一个例子,可以使用letrec构造来表示。我们有x≥y和y≥x,因此x≠y。通常,我们进行模α转换(使得不同的约束变量具有不同的名称),并且我们使用Barendregt的“互逆e.自由变量和绑定变量有不同的名称[4]。指出约束应用G[E]的子项G中的约束变量集是E的域加上G的约束变量。 例如,项x [xa,xb]等价于项y [y a,y b]的模α转换。 还请注意,递归变量的可见性仅限于出现在定义递归变量的约束列表中的ρg项以及应用此列表的ρg项。例如,在项f(x,y)[x=g(y)[y=a]]中,递归方程中定义的变量y限制了它在g(y)中的出现,但不在f(x,y)中。事实上,这个项并不满足命名条件,因为y既有这种命名约定允许我们忽略一些术语(参见下面的示例),从而非常直接地应用替换(如图6中的评估规则),因为不可能捕获变量。除了命名约定之外,ρg-项还需要一些结构属性才能是良构的。G30C. Bertolissi等人/理论计算机科学电子笔记127(2005)21定义2.3[良构项]ρg-项是良构的,如果• 每个变量最多出现一次作为递归方程的左侧;• 抽象和匹配方程的左侧是非循环的,并且它们所有不包含约束的子项都是代数的。例如,ρg-term(f(y)[y=g(y)]Da)不是良构的,因为抽象具有循环的左手边。除非另有说明,否则在下文中考虑的所有ρg项都例2.4[自由变量和绑定变量不应该同名]减少ρg项z[z=xDY,y=x+x](通过实例化变量y)可以导致变量捕获。 然而这个项不遵守我们的命名约定:如果我们考虑α -转换后得到的合法ρg-项z [z = x1DY,y = x + x],则变量捕获不再可能。 为了使变量x出现在第二个约束中,并以箭头为界,我们应该使用一个嵌套约束,如ρg项z [z = xD(y [y = x + x])]。例2.5[不同的绑定变量应该有不同的名字]直觉上,根据自由变量和绑定变量的概念,在一个项中,重写规则的左侧和ρg项的其余部分之间不可能有任何共享。换句话说,重写规则的左侧是自包含的。左手边的共享是允许的。右侧没有任何限制例如,在ρg-项f(y,ydg(y))[y=x]中,y的第一次出现是由递归变量约束的,而抽象D中y的作用域被限制在抽象本身的右侧。ρg项实际上应写成f(y,zdg(z))[y=x](通过α变换)3ρg-演算的小步长语义在经典的ρ-演算中,当把约束的应用约化为项时,i. 例如,延迟匹配约束,解决相应的匹配问题,并在演算的元级应用所得到的替换。在ρx-演算中,这种约简被分解为两个步骤,一个是计算替换,另一个是描述这些替换的应用。匹配计算导致从约束到subjunctions和应用程序的替代明确分开,并明确。在ρg-演算中,求解匹配约束的替换计算是显式执行的,如果计算成功,则结果是添加到项的约束列表中的递归方程C. Bertolissi等人/理论计算机科学电子笔记127(2005)2131GCB组规则:(ρ)(G1DG 2)G 3→ρG 2[G 1G 3](G1DG 2)[E]G 3→ρG 2[G 1G 3,E](δ)(G1;G 2)G 3→δG 1G 3;G 2G 3(G1;G 2)[E]G 3→δ(G 1G 3;G 2G 3)[E]匹配规则:(propagate)G1(G 2 [E 2])→p G1G2、 E2J J J J(分解)K(G1,.,Gn)K(G1,. ..,Gn),E→dkG1G1,...,GnGn,En≥0(solved)xG,E→s x=G,Eifx∈/DV(E)G规则:(外部子)Ctx{y}[y = G,E]→es Ctx{G}[y=G,E](非循环子) G[G0Ctx{y},y=G 1,E] →ac G[G0Ctx{G1},y=G 1,E]若x > y,则x∈ FV(G0)其中∈{=,}(垃圾)G[E,x=GJ] →G[E]如果x∈ FV(E)< $FV(G)G[g] →gcG(黑洞)Ctx{x}[x= x,E]→bh Ctx{·}[x=x,E]G[y=Ctx{x},x=Ctx,E] →bhG[y=Ctx{·},x= Ctx,E]如果y > x见图6。评估规则这意味着替代不是立即应用于术语,而是保留在环境中以备可能的延迟应用。图6中给出的ρg演算的求值规则可以分为三类:• 描述抽象和结构在ρ项上的应用的规则• 描述匹配方程求解的规则。• 处理替换和垃圾收集的规则。前两个规则ρ和δ来自ρ-演算。规则δ处理应用程序在使用“;”运算符构建的结构上的分布性,通过将适当的约束应用于规则的右侧来获得ρg项。对于这些规则中的每一个,考虑到可能的约束的存在,添加额外的一个。没有这些规则,抽象ρg-项的应用,如x[x=f(y)Dxf(y)]f(a)(可以像例3.4那样编码递归应用)就不能减少。或者,适当的分配规则可以引入,但这种方法是不考虑在本文中。匹配规则,特别是规则分解是强的,32C. Bertolissi等人/理论计算机科学电子笔记127(2005)21与我们要计算匹配解的模理论有关。在ρg-演算的第一个版本中,我们选择用一个空理论来表示ρg-演算,这个空理论已知是可判定的和唯一的,但是扩展到更复杂的理论是可能的。由于重写规则左侧的限制,我们只需要分解代数项。这组规则的目标是产生形式为x1= G1,.的约束。,xn= Gn。当匹配方程的左右两边都是代数方程时,这是可能的,但是一旦满足以下条件,就可能需要进行一些替换(如G-1规则所定义的):这些条款包含一些共享。包含约束的匹配方程(通过传播规则)被简化为包含相同匹配方程而没有约束的约束,该约束被传播到顶层。由于匹配等式的左侧是非循环的,因此不需要从匹配等式的左侧传播约束的评估规则;可以使用替换和垃圾收集规则在项中下推匹配的这一侧上的可能约束。对代数项进行分解,消除了繁琐的方程组. 匹配约束xg1是如果不存在其他约束,则在递归方程x=G1中变换形式x=G2或x G2。 例如,Con-不能减小应变xa,xb,这表明原始(非线性)匹配问题没有解。G-规则继承自Ariola和Klop的循环λ-演算前两个规则将与递归变量关联的ρg-项复制到相应约束范围内的项中。这是很重要的,当一个redex应该是明确的(e。G. 在x a[x=aDb]中)或当匹配方程应该被求解时(e.G.在a[a x,x=a]中)。 如前所述,ρg-项的变量的顺序只允许我们向上复制。如果没有这个条件,连续性就被破坏了:ρg项z1[z1=XDZ2s(x),z2= YDZ1s(y)]减少了到 z1[z1=xDz1s ( s ( x ) ) ] 或 到 z1[z1=xDz2s ( x ) , z2=yDz2s ( s(y))](see[3]完整的反例。正如结论中所提到的,我们猜想,正如循环λ-演算所发生的那样,在重写规则的形状上有一些限制,这也是ρg-演算连续性的关键因素之一。垃圾规则消除了表示ρg项的非连接部分的递归方程。匹配约束不被消除,从而保持在一个不成功的约简匹配失败的痕迹。黑洞规则用常数·代替未定义的ρg项。C. Bertolissi等人/理论计算机科学电子笔记127(2005)2133通常,我们定义一步关系式<$→M和→ρg以及多步关系式→M和→ρgw。R. t. M个匹配规则的子集和图6的整个规则集。这将是有趣的,研究适当的策略,延迟的应用程序的替代规则外部子和非循环子,以保持尽可能长的共享信息接下来的两个例子中的一个想法是,只有在需要为基本规则或匹配规则生成新的兑换时才应用替换规则此外,替换规则被用来例3.1[一个简单的共享约简]图形表示见图7(a)。(f(x,x)[x=a]Da)(f(y,y)[y=a])→ρa[f(x,x)[x=a]f(y,y)[y=a]]→esa[f(a,a)[x=a]f(y,y)[y=a]]=a[f(a,a)[x=a,n]f(y,y)[y=a]]›→gca[f(a,a)[]f(y,y)[y=a]]›→gca[f(a,a)f(y,y)[y=a]]›→pa[f(a,a)f(y,y), y=a]›→dka [a]y,y = a](通过幂等性)›→aca [a]a,y = a]›→dka[y=a]=a[y=a,]›→gca›→GCA例3.2[乘法]如果我们对常数“”使用一个整数表示法结果如图7(b)所示。34C. Bertolissi等人/理论计算机科学电子笔记127(2005)21CCΔ,→ρga,→ρg+D,s、、、ZZ得双曲余切值.R、、CcccJc、、,,vzFvzsJCccsJc、、,zszfa aza,s1,,(a)(b)第(1)款见图7。减少的例子(x<$s(y)D(x<$y+x))(z<$s(z)[z= 1])→ρ x<$y+x[x<$s(y)](zs(z)[z= 1])›→px<$y+x[x<$s(y)]zs(z),z= 1]→dkxy + x[xz,yz,z = 1]→sxy+x[x=z,y=z,z=1]→es(z<$z+z)[x=z,y=z,z=1]→gc(z<$z+z)[z=1]例3.3[非线性]涉及非线性模式的匹配可以导致一个范式,它要么是一个仅由递归方程组成的约束(表示成功的匹配),要么是一个包含一些匹配方程的约束(表示匹配失败)。f(y,y)f(a,a)›→dkya(幂等性)›→sy=af(y,y)f(a,b)›→ dkya,yB例3.4考虑项重写规则RY=Y x→x(Y x),它表示λ演算的不动点组合子Y的行为。给定a项t,我们有无限重写序列Y t→RYt(Y t)→RYt(t(Y t))→RY .在某种意义上,它可以被形式化(见[17,15]),收敛到无限项t(t(...))。. ))).我们可以把ρg-演算中的Y-组合子表示为下列项:Y=x0[x0= xDx(x0x)]。,sz1,,so、C. Bertolissi等人/理论计算机科学电子笔记127(2005)2135、SS、Δ@D得双曲余切值.G、、、,z@,,得双曲余切值.@,,,、、、,z,c@得双曲余切值.G、G、、、. z. .、Y,,zxXJ(a)(b)(c)见图8。减少的例子如果我们表示R=xDx(x0x),我们有以下约简:Y G›→es(xDx(x0x))[x0=R]G→ρx(x0x)[xG,x0= R]›→sx(x0x)[x=G,x0=R]→esG(x0G)[x=G,x0=R]›→gcG(x0G)[x0=R]→ρgG(G. (x0G))[x0=R]→ ρg.继续减少,这将我们可以使用Turner [23]介绍的方法更有效地实现相同的项约简,该方法通过图8(b)中描述的循环项对规则RY进行建模。这在ρg-演算中给出了ρg-项YT=xD(z[z=xz])在这种情况下的减少如下:YT G→ρz [z=x z] [xG]›→sz[z=x z] [x=G]›→esz[z=G z] [x=G]→gcz[z=G z]图8(c)中描述了所得的ρg项。如果我们这种约简捕捉到这样一个事实,即循环ρg-项上的有限重写序列可以对应于无限项约简序列。@,c、36C. Bertolissi等人/理论计算机科学电子笔记127(2005)214ρg-演算与ρ-演算和循环λ-演算ρ-演算的项集是ρg-演算的项集的严格子集(模某些语法约定)。ρ-项的主要区别是约束列表限制为一个必须具有以下形式的单一约束(延迟匹配约束)。在证明ρ-演算在ρg-演算中被模拟之前,我们需要证明ρg-演算的M匹配规则相对于限于模式的ρ-演算匹配算法是良好的[13]。引理4.1设T是代数ρ-项,其中FV(T)={x1,.,xn},设TU是匹配问题,其解σ ={x1/U1,.,xn/Un},即σ(T)= U。那么我们有TU→Mx1=U1,. x n= U n。证据我们通过对T项的结构归纳证明了存在约化TU→Mx1U1,.,xn 其中x i都 是 不 同 的 , 因 此 论 文 如 下 。• 基本情况:项T是变量或常数。当T=x是微不足道的。如果T=a,则σ={}且U=a。 在ρg-演算中,我们有a <$→e<$这个性质显然成立• 诱导情况:T = f(T1,. ,Tm),其中m> 0。由于替换σ存在并且匹配是句法的,我们有U = f(V1,. ,Vm)和σ(f( T1,. ,Tm ))= f(σ( T1),. ,σ(Tm )),其中σ(Ti)= Vi,i = 1. M.通过归纳假设,对于任何i,如果FV(Ti)={xi,.,x i}<$FV(T),则T iV i→Mx iσ(xi),.,xiσ(xi).1ki1 1kiki加入各种减少,我们有f(T1,. ,T m)f(V1,. ,V m)›→dkT1V1,.,TmV m→Mx1σ(x1),.,xnσ(xn).要理解最后一步,请注意,在列表X1σ(x1),.,X1σ(x1),.,xmσ(x1),.,xmσ(x m)11k1k11mkmkm具有相同左侧变量的约束具有相同的右侧。因此,通过幂等性,这样的列表与x1σ(x1),...,xnσ(xn).Q我们现在可以证明,ρ演算的约化可以在下式中模拟: ρg演算引理4.2设T和TJ是ρ-项。如果在ρ-演算中存在约化T→ρσδTJ,那么在ρ g -演算中也存在相应的约化T→ρgTJ。证据 我们证明,对于ρ - 演算 中的 每个约化步骤, 我们都 有一个C. Bertolissi等人/理论计算机科学电子笔记127(2005)2137在ρg-演算中的相应的归约步骤序列• 如果在ρ-演算中T→ρTJ或T→δTJ,则我们在ρg-演算中使用相应的规则平凡地得到相同的约简。• 若T = [T1T3] T2→σσ(T2)= TJ,其中T1是ρ-演算模式,置换σ ={U1/x1,.,Um/xm}是匹配的解,那么在ρg-演算中相应的约简如下:T=T2[T1T3]→MT2[x1= U1,.,x m= U m],通过引理4.1-es{U1/x1,.,U m/x m}T2[x1= U1,.,x m= U m]→gc{U1/x1,.,U m/x m}T2[]›→gc{U1/x1,.,U m/x m}T2= T J其中,我们用{U1/x1,. ,U n/xn}T2项T2,其中变量x i的每次出现都被项U i代替,对于所有i = 1. M.Q在匹配失败的情况下,这两个演算处理错误的方式略有不同,即使在这两种情况下,匹配冲突没有减少,并保持为约束应用失败。特别地,我们可以在ρg-演算中比在ρ-演算中更深入地分解匹配问题,因此可能发生的是,在ρg-演算中,标准形式的ρ例4.3[ρ-演算和ρg-演算中的匹配失败]在这两种演算中,不成功的约简导致项的约束列表中的不可解匹配方程。(f(a)Db)f(c)→ρσδ[f(a)f(c)]b(f(a)Db)f(c)→ρb[f(a)f(c)]›→dkb [a]c]注意,在ρ演算中,由于匹配算法不能计算求解匹配方程f(a)f(c)的替换,因此不能应用(σ)规则,因此约简被卡住。另一方面,在ρg-演算中,M匹配规则可以部分地分解匹配方程,直到达到冲突acλφ0的项可以很容易地转化为ρg-演算的项。 λφ0的主要差别是w。R. t.ρg-演算是一个限制列表,递归方程列表的约束。不需要延迟匹配约束,因为在λ演算中匹配总是平凡地满足的。38C. Bertolissi等人/理论计算机科学电子笔记127(2005)21ΔΔΔΔΔ定义4.4[翻译]将λφ0项t翻译为ρg项,记为t,归纳定义如下:Xλx.t=x=xDtf(t1,. ,t n)最大值0|x1= t1,.,xn= t n=f(t1,. ,t n)=t0[x1= t1,.,x n= t n]t0t1=t0t1我们可以把ρg-演算的求值规则看作是λφ0-演算的一个例子。β-规则可以用ρg-演算的B-规则来模拟。其余的规则可以使用ρg-演算的子集G规则接下来我们证明,λφ0-演算的约化可以在ρg-微积分。引理4.5设t1和t2是两个 λφ0-项。如果t1<$→λφt2,λ-演算,则ρg-演算存在约化t1→ρgt2.证据 我们继续分析λφ0的每个约化公理。• β规则:t1=(λx.s1)s2→βs1|x = s2<$= t2在ρg-演算中,我们有:t1=(xDs1)s2→ρs1[xs2]›→ss1[x=s2]= t2• 外部子规则:trivial。• 2016年02月01日02:00:00在这种情况下,总是表示。• 黑洞法则:微不足道。• 垃圾收集规则:但书E(EJ,t)等价于使用ρg演算中自由变量的定义所表达的但书。条件-因为我们消除了一个递归,所以在ρ演算中,G时间的方程式因此,λφ 0中的垃圾收集规则的单个步骤可以对应于ρ g-演算中相应垃圾规则的多个步骤:|E,EJ→gct|则t [E,EJ] →gct [E]。Q5结论和今后的工作本文提出了ρg-演算,它是ρ-演算的一个推广,能够处理子项和圈C. Bertolissi等人/理论计算机科学电子笔记127(2005)2139(其可用于表示规则无限数据结构)可以被表示。ρg-演算已经被证明是循环λ-演算和标准ρ-演算的推广。这项工作仍处于初步阶段,未来的研究有几个有趣的方向。从循环λ-演算[3]和ρ-演算[5]的类似工作中得到启发,理解在哪些限制下ρg-演算可以连续是很有趣的。我们推测,如果我们考虑一个句法匹配,它可能会限制到重写规则和匹配问题,其中左手边尊重适应我们句法的所谓这个条件实际上对应于我们在第2节中已经对模式施加的限制。同时,一个吸引人的问题是推广ρg-演算来处理不同的、非句法的匹配理论。例如,在涉及循环图的匹配的情况下,即使匹配问题的解实际上存在,匹配约束的减少也例如,项g(x,x)(g(f(z),f(f(y)[y=f(y),z=f(z)]可以简化为:[xf(z),xf(f(y)),y=f(y),z=f(z)]但它停留在这一点。为了从这种失败中恢复过来,我们应该能够比较两个匹配方程的右侧,并确定它们的“解开”是否换句话说,我们应该能够处理一般的循环匹配。我们应该注意到,这并不简单,因为在ρg-演算中,匹配是内在化的,而不是在元层面上进行的此外,在本文中,我们只是非正式地讨论了定义与ρg-演算的项相关联的(循环项)图的问题。虽然对于没有匹配约束的ρg-演算的片段,一些明确的建议可以来自[6,16]中关于具有绑定器的循环项图的现有工作,但对完整演算的推广将需要进一步的研究。在使这种对应形式化之后,一个非常有趣的问题出现了,我们是否可以将项图重写编码到ρg-演算中,就像项重写系统(及其底层策略)可以编码到ρ-演算中一样。此外,ρg-演算的一个项,可能有共享和循环,可以被看作是一个一方面,定义一个无穷版本的ρ-演算是很有趣的,可以得到启发,例如,从无穷λ-演算[19]和无穷重写[17,15]的工作。另一方面,为了加强ρg-演算作为项的有效实现的观点,40C. Bertolissi等人/理论计算机科学电子笔记127(2005)21在无穷ρ演算中重写,应该有[18,8]风格的充分性结果。确认我们感谢Andrea Corradini和Fabio Gadducci对本文早期版本进行了富有成效的讨论,并感谢匿名评审员提出了富有洞察力的建议。引用[1] M. 阿 巴 迪 湖 Cardelli , P. L. Curien 和 J. - J· 利 维 显 式 替 换 。 Journal of FunctionalProgramming,4(1):375[2] Z. M. Ariola和J. W.克洛普方程项图重写。Foundamenta Informaticae,26(3-4):207
下载后可阅读完整内容,剩余1页未读,立即下载
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![txt](https://img-home.csdnimg.cn/images/20210720083642.png)
![application/msword](https://img-home.csdnimg.cn/images/20210720083327.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://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)