没有合适的资源?快使用搜索试试~ 我知道了~
惰性求值的两种操作语义研究及其抽象模型
理论计算机科学电子笔记104(2004)235-251www.elsevier.com/locate/entcs懒惰逻辑语义Luca Paolini和Simona Ronchi Della Rocca1Universit`adiTorinoDipartimento diInformaticapaolini,ronchi@di.unito.it摘要研究了λ演算在按名调用和按值调用两种情况下的惰性求值从这类演算的两个拓扑模型的逻辑描述出发,定义了一个按类型分层的项的前序关系,它准确地把握了我们要建模的两个操作语义。这样的关系可以用于构建两个完全抽象的模型。关键词:惰性求值,λ-演算,完全抽象。1介绍Plotkin在[13]中引入了λ-演算的惰性求值,在call-by-name和call-by-value设置中,用于捕获函数式语言的特性,其中函数仅在提供参数时才被评估。在λ-演算设置中,这意味着程序的评估(即,封闭项)在达到抽象项时停止。懒惰的按名称调用求值是通过标准的λβ演算来建模的,按值调用是使用λβv演算来建模的,这是在[13]中引入在这两种情况下,惰性求值都是通过在每一步选择不在λ-抽象范围内的最外层redex(分别是β-redex和βv-redex)来由这种评估策略引起的惰性操作语义可以按照Plotkin定义1篇论文部分得到MURST-Co finn '01 COMETA项目、IST-2001-33477 DART项目、MIUR-Co finn' 02 PROTOCOLLO项目的支持1571-0661 © 2004 Elsevier B. V.根据CC BY-NC-ND许可证开放访问。doi:10.1016/j.entcs.2004.10.003236L. Paolini,S. Ronchi Della Rocca /理论计算中的电子注释。Sci. 104(2004)235-251MMM[13],作为λ -项之间的前序关系,说M在操作上小于N当且仅当,对于所有上下文C [。]使得C[M],C[N]是闭的,C[M]归约为抽象暗示C[N]归约为抽象。λ演算的惰性指称语义首先由Abramsky和Ong [2]在按名称调用设置中研究,并由Egidi,Honsell和Ronchi Della Rocca [8]在按值调用设置中研究。这两个模型都建立在拓扑空间的范畴内,并基于域上的提升运算。即cbn模型,对于点名的情况,是域方程X=[X → X]其中[。→。[1]是Scott连续函数的提升空间在按值调用的情况下,模型Mcbv是域的初始解X = [X → <$X]其中[。→。[1]是Scott严格连续函数的提升空间这两个模型都被证明是正确的,但在它们想要建模的操作语义方面并不完整。 让我们回想一下,当指称语义蕴涵操作语义时,模型是正确的,如果逆蕴涵成立,则模型是完备的。此外,一个模型对于操作语义是完全抽象的当且仅当它对于操作语义是正确的和完备的。在[8]和[2]中分别证明了,在按值调用和按名称调用的情况下,不存在对于惰性操作语义是完全抽象的拓扑模型。这两个证明都是对文[10]中证明的不完全性结果的启发。在[8]通过对cbv的崩溃,基于项上的应用互模拟的概念,已经建立了一个完全抽象的模型。这种技术不能应用于cbn模型,因为它要求在构建模型时使用的投影是λ可定义的,在这种情况下这是不正确的。基于稳定函数的懒惰按名称调用模型类的进一步不完备性结果已在[4]中得到证明。在本文中,我们考虑一个逻辑描述的两个先前召回的模型,基于一个交集类型分配系统,我们定义了一个前序关系之间的封闭的条款,分层的类型,当专门的类型系统描述一个或另一个两个模型,原来是等价的操作语义模型描述。因此,这个预序关系用于以完全统一的方式构建两个完全抽象的模型,分别用于按名称调用和按值调用的情况。首先,关于项的前序被扩展到关于作为L. Paolini,S. Ronchi Della Rocca /理论计算中的电子注释。Sci. 104(2004)235-251237||∈⊆闭项,然后通过折叠属于同一等价类的所有过滤器,相对于由给定的前序诱导的在[7]中建立了一个基于游戏语义变体的懒惰按名称调用操作语义的在[5]中可以找到在不同设置中对按名称调用的懒惰λ本文的结构如下。在第2节中,我们将介绍参数λ演算,这将允许我们以统一的方式谈论λ演算的按名称调用和按值调用版本。在第3节中,介绍了两种惰性操作语义。 在第4节和第5节中,分别回顾了模型和滤波器模型的基本概念。 第6节包含了关于术语的两个前序,以及它们准确把握操作语义的证明。在第6节中,我们将简要介绍如何使用这种前序来构建一个完全抽象的模型。2参数化语言为了统一处理两个不同的结石,我们将使用[12]第一个定义是参数演算的概念。λ演算是一种语言Λ,它配备了一组输入值,满足某些闭包条件。非正式地,输入值表示部分评估的术语,可以作为参数传递。定义2.1设i) λ -演算的项集Λ由以下文法归纳定义:M::= x λx.M MM其中x是一个可数的变量集合。ii) 约简(→λ)是以下规则的上下文闭包:(λx.M)N→M[N/x]当且仅当N∈λ。(λx.M)N称为λ-redex(或简称redex)。iii) →E和=E分别是→E的自反闭包和传递闭包以及→ E的对称闭包、自反闭包和传递闭包。iv) 当满足以下条件时,集合Λ是输入值的集合:• Var闭包;• P,Q∈R,P[Q/x]∈ R,对每个x∈Var(替换闭包);• M∈ N和M→N都蕴含N ∈ N(约化闭包).238L. Paolini,S. Ronchi Della Rocca /理论计算中的电子注释。Sci. 104(2004)235-251{|∈}1Lv) 如果一个项不具有正-赎回,则它是正-正规形式定理2.2 [12]对于输入值集合的每一个选择,λ λ演算都具有Church-Rosser性质。在本文中,我们将研究输入值的两个特定实例,即λ = Λ和λ = Γ,其中Γ = V ar λx。MMA. 很容易检查Λ和Γ都是输入值的集合。特别地,λΛ-演算是通常的λβ-演算,λΓ-演算是λβv-演算,由Plotkin [13]定义。对于每一个λ Λ,λ0表示λ λ对闭项的限制。M表示项M1,..., Mn,对于n ≥ 0(如果n = 0,则序列为空)。M3操作语义下面定义的两个操作语义分别在按名称调用和按值调用设置中表征了简化为抽象的封闭项集。设W∈Λ是λ-抽象的集合。定义3.1i)RML是证明形状其中M∈Λ0且N∈W0。 它包括以下规则:(懒惰)P [Q/x] M1.. . M mLNλx.MLλx.M(λx.P)QM.. .M(头)中国ML表示存在判断MLN的证明,对于某些N,而ML表示没有这样的证明。ii) 懒惰操作语义L被定义为以下前序:M≤LN当且仅当,对于所有上下文C [. [1],则C[M],C[N] ∈Λ0,C [M] L蕴涵C [N] L。严格的前序将被表示为RSL。iii) M<$LN当且仅当M≤LN且N≤LM。前面描述的形式系统对应于Plotkin [13]引入的惰性按名称调用求值机。定理3.2设M∈ Λ 0.i) M<$LN蕴涵N是抽象作用且M→<$ΛN;ii) ML当且仅当M Λ-约化为抽象。在下一个定义中,给出了懒惰的按值调用操作语义ML. Paolini,S. Ronchi Della Rocca /理论计算中的电子注释。Sci. 104(2004)235-251239M1MV定义3.3i)BIV是证明形状判断的形式系统其中M∈Λ0且N∈W0。 它包括以下规则:(懒惰)QVQJP [QJ/x] M1.. . M mVNλx.M<$Vλx.M(λx.P)QM.. . MN(头)MV表示存在判断MVN的证明,对于某些N,而MV表示没有这样的证明。ii) M≤VN当且仅当,对于所有上下文C [. [1],则C[M],C[N]∈ Λ0,C [M] V蕴含C [N] V。iii) M<$VN当且仅当M≤VN且N≤VM。前面描述的形式系统对应于Plotkin [13]引入的惰性按值调用求值机。定理3.4设M∈ Λ 0.i) M<$VN蕴涵N是抽象作用且M→<$rN;ii) MV当且仅当M Γ-约化为抽象。4λ-模型在这一节中,我们回顾了λ-模型的定义以及正确性和完备性的概念定义4.1 λ λ-模型是一个四元组,其中:D是一个集合,D是D中D2的映射,I是D中D的映射. 此外,如果E是从Var到I的函数(环境)的集合,范围为ρ,ρJ,.。,则解释函数[[. ]]:Λ× E→D满足以下条件:(i)[x]n=n(n);(ii)[MN]]ρ=[[M]]ρ[[N]]ρ;(iii) [λx.M]]ρ<$d=[[M]]ρ[d/x],若d∈I;(iv) 若[M]]ρ[d/x]=[[MJ]ρJ[d/y],其中eachd∈I,则then[[λx.M]]ρ=[[λy.MJ]]ρJ;(v) M∈ φ蕴涵φρ。[[M]]ρ∈ I.其中ρ [d/x](y)=如果 y=x,则 delseρ(y).I是输入值集合的语义对应物;假设I = D,则前面的定义等价于[9]中给出的λ模型的经典定义 Aλ-模型 在定义的术语之间引入等价关系 如:M<$MNifando <$if [M]]Mρ =[[N]]Mρ,f或所有envi n entsρ。240L. Paolini,S. Ronchi Della Rocca /理论计算中的电子注释。Sci. 104(2004)235-251≤≤≤≤≤∇►∈设O是由操作语义O导出的项之间的等价关系。指称等价<$M相对于运算等价<$O是正确的,如果M<$MN对所有M和N蕴涵M<$ON,而它是完备的,如果M<$ON对所有M和N蕴涵M<$M N。 M是完全抽象的,如果它既正确又完备。5滤波器模型在本节中,我们将介绍过滤器模型的概念,这是一类基于交叉类型和交叉类型分配系统的λ-模型。在[6],[3],[1]中已经广泛地研究了使用交集型赋值系统来进行域的逻辑描述。定义5.1i)设C是一个非空的可数类型常数集,至少包含常数ω(全称类型)。 类型集合T(C)归纳定义如下:σ::= α|(σ→σ)|(σ<$σ),其中α∈ C.ii) 交集关系是T(C)上的一个前序关系,在以下规则下闭合:σ≤ω(一)σ≤σ∧σ(b)第(1)款σ∧τ≤σ(c)第(1)款σ∧τ≤τ(cJ)(σ→τ)<$(σ→π)≤σ→(τ<$π)(d)其他事项σ σJ,τ τJ(五)στ≤σJτJσJσ,τ τJ(f)(g)(r)σ≤ρ,ρ≤τ(t)σ→τ ≤σJ →τJσ→ω≤ω→ωσ≤σσ≤ρiii) 设≤是T(C)上的一个交关系≤诱导一个类型理论:στ当且仅当σ≤τ且τ≤σ。iv) 一个类型系统是一个三元组C,≤I,I(C)>,其中C是一组类型常数,≤I是T(C)上的一个交集关系,I(C)是关于≤I的一组输入类型,即它不是空的,并且在以下条件下是封闭的:<• σ∈I(C)和σ∈τ表示τ∈I(C);• σ∈I(C)和τ/∈I(C)意味着σ≤<$τ。v) 给定一个类型系统,相应的类型赋值系统是一个形式系统,证明了以下形式的陈述:BM:σ其中M是项,σ T(C)和B是基,即,一个从Var到I(C). B[σ/x]表示基,使得:B [σ/x](y)=如果 y=x,则 σelse B(y).L. Paolini,S. Ronchi Della Rocca /理论计算中的电子注释。Sci. 104(2004)235-251241→类型分配系统由以下规则组成:B[σ/x]x:σB[σ/x] σ/M:τ(var)BM:ωσ∈I(C)BM:σ→τBN:σ(ω)B λx.M:σ→τ(→I)B MN:τ(→E)BM:σBM:τBM:σ σ≤τB M:στ(一)B M:τ(≤100)BM:στBM:στB M:σ(1)B M:τ(英)注意,规则(El)和(Er)是冗余的,因为规则(≤)。I(C)是可以分配给输入值的类型的集合。 这是由I(C)(而不是整个T(C))是基的余域,并且规则((E)要求应用程序的参数具有 属于I(C)的类型。设I是类型系统。若π∈I(C)且σ≤ππ,则σ∈I(C)。若σ∈I(C),则对所有的τ∈T(C),σ∈τ∈I(C).若π/∈I(C)且π≤<$σ,则σ/∈I(C).为了减少类型中括号的数量,我们将在连接词之间使用以下优先规则 : 绑 定 比 → 强 , 而 且 → 向 右 关 联 。 我 们 将 使 用 σ<$τ<$ρ 来 表 示σ<$(τ<$ρ)和σ<$(τ<$ρ)。在下一个定义中给出的合法类型理论的概念是一个关键的概念,因为我们将证明合法是类型理论导出λ-模型的必要条件。定义5.2设I是类型系统。当且仅当对所有的σ∈I(C)和τ/<$ω:(σ1→τ1)τ... <$(σn→τn)≤<$σ →τ(1≤n)意味着{i1,.,i k}{1,.,n} s. t.(σ i1... <$σ ik)≥<$σ且(τ i1<$... τik)≤设I(C)是一个类型系统。i) f上的滤波器f是任何包含ω且在ω且≤ω下闭的集合,即:·μ,ν∈f蕴涵μπν∈f;242L. Paolini,S. Ronchi Della Rocca /理论计算中的电子注释。Sci. 104(2004)235-251FF·μ∈f和μ≤μτ意味着τ∈f。设F(f)是f上所有滤波器的集合,设I(f)是滤波器的集合含有至少一种属于I(C)的类型ii) 设S是一组类型;↑S是从S通过关闭它而获得的过滤器,且≤S,即包含S的最小滤波器。iii) 设f(f)是F(f)上定义的二元运算,如下所示:f1f2= ↑ {ω}{τ|σ→τ∈f1和σ∈f2和σ∈ I(C)}.注意f∈I(C)和σ/∈I(C)通过输入类型集合上的条件暗示σ∈f解释功能将每个术语与所有可以分配给它的类型相关联设I=C,≤I,I(C)>.<[啊。]]F(λ):Λ×(Var→ I(λ))→ F(λ)是解释功能,定义如下:[[M]] Fρ(σ)={σ∈T(C)|B其中B<$ρ表示<$z∈VarB(z)∈ρ(z)。定理5.4设I=C,≤I,I(C)>是一个律型系统,M∈<对于所有的环境ρ,[[M]] ρ∈ I(π).然后是一个λ λ-模型。我的律师。 这是一个假设:对于所有的t[M]]Fρ(ρ)是一个滤波器。可以通过验证定义4.1的条件来执行该程序。Q由滤波器λλ模型引起的项之间的偏序定义如下:M±FNifandoifρ,[[M]]Fρ<$[[N]]Fρ也就是说,{σ| <$B<$ρ使得B<$<$M:σ}<${σ| B<$ρ使得B<$N:σ}。MиFN将表示适当的包含。我们可以通过考虑前序关系而不是等价关系来细化模型关于给定操作语义的正确性和完整性的概念。定义5.5设F是一个滤波器模型。F关于O-运算语义是正确的当且仅当M±FN蕴涵M≤ON,对所有M,N∈Λ。F关于O-操作语义是完备的当且仅当逆蕴涵成立.而且对于O是完全抽象的,如果它对于O是正确的和完全的。L. Paolini,S. Ronchi Della Rocca /理论计算中的电子注释。Sci. 104(2004)235-251243L≤→V6两个懒惰的模型我们提出了两个过滤器模型,这是正确的,但不完全的L-操作语义和V-操作语义,分别。定义6.1设C={ω}。是类型系统,其中≤是定义5.1.ii)和I(C)=T(C)的最小交集关系。 设L为滤波器模型.同构于作为域方程的初始解获得的拓扑λX=[X → X]其中[。→。[2]是Scott连续函数的提升空间定理6.2 i)[2]关于L-运算语义,L是正确的.ii)[2]关于L-操作语义,L是不完备的。现在让我们定义下一个模型。定义6.3是类型系统,其中C={ω},I(C)={σ0... σ n|<$k ≤ n <$σ,τ ∈ T(C<$)σ k<$σ →τ}和x2是通过添加到定义5.1.ii)规则而(ω→ω)→τ≤<$ω→τV是λ Γ-模型.(五)很容易检验σ∈I(C<$)当且仅当σ/<$ω。可以证明过滤器Γ-模型V与[8]中定义的类型同构,其中类型从一个常数ν开始构建,该常数ν扮演类型ω ω的角色。 所以它同构于拓扑λ-模型作为域方程的初始解获得X = [X → <$X]其中[。→。[1]是Scott严格连续函数的提升空间定理6.4 i)[8] V在V-操作语义上是正确的.ii)[8]关于V-操作语义,V是不完备的。这两个模型的特征收敛项的类型ω→ω。性质6.5设M∈ Λ 0.244L. Paolini,S. Ronchi Della Rocca /理论计算中的电子注释。Sci. 104(2004)235-251σωτσ►≡σ∧τ►στni) BM:ω→ω当且仅当ML。ii) BM:ω→ω当且仅当M <$V。类型的一些结构属性将是有用的。性质6.6设∈ {,}.i) 如果σ/<$ω那么σ<$σ 0<$. n,其中, n是n,σ iτ i→. →τ i→ω→ω,对n,mi∈ N.1百万iii) σω当且仅当σω` -是的.你... (n≥1).iii) (ω→ω)→τ<$ω→τ,对所有的τ∈T(C<$).7适用的操作前序在闭λ-项上定义了两个预序关系,分别用T(C)和T(C)类型分层.这些关系将分别对应于两个运算前序≤L和≤V。设m是一组输入值:一个项M是m-有价值的,当且仅当它m-约化为m中的一个项显然,Λ-有值项的概念是没有意义的。定义7.1令(λ= Λ且λ= λ)或(λ =Γ且λ=λ)。i) Λ 0是Λ0上的一个关系,定义如下:• MN是真的;∆σ→τ∆σ→τ• M其中τω,当且仅当对所有基B,B<$NM:ω→ω蕴含B<$N:ω→ω;其中τ/ω,当且仅当P是闭的,且是P-值的,BP:σ蕴涵MPNP;N当且仅当MN和MN;ii) MN当且仅当MN,对所有σ。下一个属性将有助于更好地理解前面的性质7.2对于每个类型σ和基B,i) 存在一个闭项P,使得B∈P:σ;ii) 存在一个闭项P使得B ≠ P:σ。证据很容易证明,对于每个σ,有n使得B∈:λx1. x n.DD:σ和B:λx1. xn.DD:σ,其中D λx. 这两个证明都可以通过对σQ的• M• ML. Paolini,S. Ronchi Della Rocca /理论计算中的电子注释。Sci. 104(2004)235-251245σων≤≤ω→ωωνÐ∆公司简介τ注意,虽然λx.DD/D.事实上,0ω→ωΛω →ω →ω每个P∈Λ,B<$$> P:ω,因此(λx.DD)P<$ω→ω(DD)P为真,的定义。 因此,M<$ΛN和σ≤ <$τ并不意味着M<$ΛN。σ τ性质7.3设M,N∈ Λ 0.i) 爱情是一种回忆。ii) 是传递性的。证据这 两点都可以通过对σ的简单归纳来证明。Q性质7.4设M,N∈ Λ 0.i) M±LN蕴涵M<$ΛN;ii) M ± VN表示M<$r N。证据i) 我们将证明M/<$ΛN蕴涵M/±LN。通过定义M/<$ΛN意味着存在σ使得M/<$ΛN。证明是通过归纳σ。显然是σ/ω,因为根据定义M<$ΛN为真。如果σμ→ν,当νω时,BM:ω→ω和B/N:ω→ω都是由Λ的定义,所以证明是直接的。若σ∈μ→ν,其中ν/εω,则存在P∈Λ0,ΛNP,通过定义Λ。 因此,通过归纳,MP/±LNP,所以M/±LN。如果σν,则通过归纳得出证明ii) 类似于前一点。Q现在我们将证明,对于闭项,前序L和V分别与<$Λ和<$Γ重合。给我7块钱。5L∈M,N∈Λ0,设(Λ=Λ和Λ=Λ)或(Λ=Γ和()。 MN当且仅当M PN P,对于每个序列P有价值的条款。证据 我们将证明,M/N意味着存在一个序列,闭项-有价值项P,使得MP/NNP。根据假设,∆ω→ω一个类型σ使得M/<$σN,所以证明是通过σ上的归纳来完成的。Ifσωthenσω`。-是的.你... nωx(n≥1);but,sinceMN乘n定义,这是不可能的。故设σ/ω。如果σµ→ν,其中νω,那么证明是空洞的。若σεμ→ν,其中ν/εω,则有P∈ε0这样MP NP,所以通过归纳证明。如果是这样,那么证明就遵循归纳法。我们将证明,如果存在一个闭的p-值P序列,τ/ω型,使得MP/ω NP然后M/N N,通过诱导246L. Paolini,S. Ronchi Della Rocca /理论计算中的电子注释。Sci. 104(2004)235-251►ω→ω≡≡⇓►→≡∈P的长度。如果P= 0,则证明是平凡的,所以令P≥1,PQQJ.• B<$QJ:ωby rule(ω)impliesMQ证明遵循归纳法。Λω→τ “恩,恩。• BQJ:ω→ω,由于QJ是Γ-值的,则蕴涵MQ”“是的,是的。引理7.6设M,N∈ Λ 0.Γ(ω→ω)→τNQ通过QM≤LN当且仅当MP<$ΛNP,对于每个闭项序列P。证据 记住,对于每一项Q,L当且仅当B<$Q:ω ω,由性质6.5. i.设P是闭项序列,B是基。如果M≤LN,则MP <$L蕴涵N P <$L;因此,根据性质6.5. i,B <$<$M P:ω → ω蕴涵B <$N P:ω → ω。因此,通过定义ω→ω,证明就完成了。设MP<$ω→ωNP,对每个闭项序列P.我们将证明,如果C [M],C [N] ∈ Λ0且C [M]<$L,则C [N]<$L,对所有上下文C [. ]. 证明是通过归纳证明C[M]L的推导的大小来完成的。如果最后应用的规则是(lazy),则C [. ][啊。]或C [. ]λx.C0 [. ],所以证据是直接的。如果最后应用的规则是(头),那么根据C [的可能形状,有两种情况。].• C [. [. ] C1 [. [……C m [. ](m∈N).如果m= 0,则ML蕴涵BM:ω→ω,所以通过定义ω→ω,BN:ω→ω,证明遵循性质6.5. i。现在让m≥1。 定义D [. [. [……C m [. ],所以D[M]<$C[M]。如果M(λz.M0)M则D [. [λz.M0] MC1 [. [……C m [. ](m∈N).如果M = 0,则令D [。]M0 [C1 [. ]/z] C2 [. [……C m [. ],否则令D [.[M1/z] RC1 [. [……C m [. ]其中M=M1R.在所有情况下,D[M]L和通过归纳D[N]L,所以D[N]L通过规则(头)。但是MC1 [N]. C m [N] Limplies BMC1 [N].C m [N]:ω → ω,因此假设BNC1 [N]. Cm [N]:ω→ω。因此,NC1 [N]. C m[N]通过属性6.5. i.• C[. ](λy.C0 [. ])C1 [. [……C m [. ](mN)。m= 0的情况是不可能的,否则证明通过推导的归纳来进行,证明C0[M][C1 [M]/y] C2 [M]. C m [M] μL。Q定理7.7对任意M,N∈ Λ 0,M<$ΛN当且仅当M≤LN。证据 引理7.5和7.6。QL. Paolini,S. Ronchi Della Rocca /理论计算中的电子注释。Sci. 104(2004)235-251247⇐∈≤⟨⟩∈0对应于7.6的性质的蕴涵的证明,对于λr演算不能通过推导的大小的归纳来完成。我们需要定义一个更精细的归纳测度,它已经在[11]中引入,用于V-操作语义的推理。定义7.8权值Λ0−→N是偏函数,定义如下:• λx.MJ• λ(λx.M0)M1.. .M m = 1 + M1 +M0 [M1/x] M2. .M m性质7.9设M∈ Λ 0.i) 定义M当且仅当MV;ii) LetM→N. 如果定义了N,且M≥N,则定义了M。非正式地,Γ-有价值项M的权重是两个约简序列的长度的上界,从M开始并到达抽象,一个在每一步执行最外面的Γ-redex,另一个在每一步执行不在抽象范围内的最里面的Λ-redex以下属性保持不变。引理7.10令M,N~ 0。 MVN当且仅当MP<$ω→ωNP,对每个闭Γ-值项序列P.证据 设Q是闭的Γ-值项. 则QV当且仅当BQ:ω→ω,通过性质6.5。设P是闭的Γ-值项序列。 如果M≤VN,则 MP<$V蕴涵NP<$V;因此,根据性质6.5. ii,B<$MP:ω→ω蕴涵B<$NP:ω→ω因此,通过定义ω→ω,证明就完成了。设MP<$ω→ωNP,对每个闭的Γ-值项序列P.我们将证明,如果对于所有上下文C [ M ],C [M]defined蕴涵C [N]defined。]故C[M],C[N]~。然后,结果由性质7.9. i得出。证明将由C[M]上的归纳法给出。 根据C [的可能形状,有两种情况。].• C [. [. ] C1 [. [……C m [. ](m∈N).如果m=0,则定义为MM,MV,所以BM:ω→ω。但BN:ω→ω通过定义ω→ω和证明遵循性质7.9.一.设m≥ 1且M∈(λx.M0)M1. M p.姿势D [. [. [……C m [. ],所以D[M]C[M]。·如果p> 0,则D [. ]M0 [M1/x] M2. M p C1 [. [……C m [. ],所以D[M]和M1“既然如此,既然如此。· 否则D [. ]M0 [C1 [. ]/x] C2 [. [……C m [. ],因此,D[M]和C1[M]是248L. Paolini,S. Ronchi Della Rocca /理论计算中的电子注释。Sci. 104(2004)235-251∈√∈ F“既然如此,既然如此。在这两种情况下,都是由归纳法来定义的。因此,D [N] V,因此,BMC1[N].. C m [N]:ω → ω,因此根据假设B NC1 [N]. Cm [N]:ω→ω。所以NC1 [N]... C m [N] V由性质6.5.ii证明如下。• C [. ] λy.C0 [. ])C1 [. [……C m [. ](m∈N).m= 0的情况是平凡的,否则证明遵循C0 [M][C1 [M]/y] C2 [M].的权重的归纳。Cm [M]和C1 [M]。Q定理7.11对任意M,N∈ Λ 0,M<$rN当且仅当M≤VN。证据 引理7.5和7.10。Q8两个完全抽象的模型通过使用上一节的结果,我们可以分别针对L和V操作语义构建两个完全抽象的模型。由于这两种情况下的构造是完全一致的,我们将只画出V的情形。在F0(F)上,FΓ诱导一个预序,F(F)的一组滤波器,封闭式术语的解释。定义8.1设f,g0(n),设ρ为环境。f∈gifando∈ fifM,NΛ0满足[M]]Fρ(π)=f和[N]]Fρ(π)=g隐含MrN。此外,fg当且仅当f<$rg和g<$rf.注意,如果M是封闭的,则n[M]]Vρ=[[M]]VρJ,f或所有ρ,ρJ;moreover,ifM,N当n[M]]Vρ=[[N]]VρJ闭合时,由P函数表示M∈N和N∈M7.4.二.注意,r是重载的,因为它既表示Λ 0上的关系,也表示F0()上的关系。现在我们可以定义新的λr模型。定义8.2设f,g∈F0(f).i) [f]是f关于等价关系,而F0是由导出的等价类的集合在F0(?)0 00F(F)此外,让我{[f]∈F| ∃M ∈ ΓS.T. [M]]ρ=f}。ii) F:F0×F0→F0定义为[f]<$[g] = [f<$g],对所有的[f],[g] ∈F0.iii) 解释功能[。]] VV:Λ ×(Var → I0)→F0 定义为:VVF(V)[[M]]=[[M]]ρ],其中ρ使得对于所有x∈Var,ρ(x)∈(x)iv) 设VV为四元组:。L. Paolini,S. Ronchi Della Rocca /理论计算中的电子注释。Sci. 104(2004)235-251249∈ζζ√ρ[d/x]ρ[d/x]请注意,解释也被定义为开放术语性质8.3令M,N,P,Q~ 0.如果M <$rN和P <$rQ,则MP <$rN Q。证据 定理7.11。Q◦通过使用前面的描述,可以定义。当然,这很容易[f] ∈I0和FJ∈[f]意味着FJ∈I()。引理8.4VV是一个λ r-模型。证据 我们检查VV是否满足定义4.1的条件。若ρ∈(Var→I0),则令ρ使得对所有x∈Var,ρ(x)∈ρ(x).(i)[x]]VV=[[x]]ρF(F)]=[ρ(x)]=F(x).(ii)[MN]]VV=[[MN]]Fρ()]=[[M]]Fρ()[[N]]ρF()]=[[M]]ρF()][[M]] V<$V<$[[N]] V<$V.[N]]ρF(N)]=()(iii) [λx.M]]V<$V<$[d]=[[λx.M]]ρF]<$ [d]=[[λx.M]]Fρ(λ)d]=[[M]]F(λ)]=[[M]]V<$[V[d]/x],f或所有d∈I0().(iv) Let[M]]V[V[d]/x]√=[N]]VJV[[dJ]/xJ],其中d,dJ∈ I0(n);因此[M]]F(n)]=[[[N]]F()],因此[[λx.M]]]=[[λxJ.N]] J]因此[λx.M]] VV=[[λxJ.N]] VV。ρ[dJ/xJ](v) 小事一桩。ρ ρζζJQ由于πΓ是F0(π)上的一个预序,那么它诱导出F0上的一个偏序.定义8.5设tM±VVN表示e[M]]V<$V<$r[[N]]V<$V,f或所有的<$∈(Var→I0).此外,令M<$VVN表示M±VVN和N±VVM。因此,模型VV在项的解释上引入了偏序(不仅是封闭项)。引理8.6设M,N∈ Λ 0. M±VVN当且仅当M<$r N。证据 设φ ∈(Var → I0),ρ使得对所有x ∈ Var,ρ(x)∈ φ(x).VV ΓVVF(π)ΓF(F)M±VVN当且仅当[M]<$$>[[N]<$ 当且仅当[[M]]ρ<$[N]]ρ]如果和oif[M]]ρF()<$r[[N]]ρF()if和oifM<$rN.Q正确性很容易。定理8.7 VV在V-操作语义上是正确的.250L. Paolini,S. Ronchi Della Rocca /理论计算中的电子注释。Sci. 104(2004)235-251VVVV证据我们将通过正确性的定义证明M±VVN蕴涵M≤VNM±VVN意味着C[M]±VVC[N],对于每个闭合上下文C [. ].因此C [M]<$r C[N],根据引理8.6;因此C[M]<$rC[N],因此BC[M]:ω→ω蕴涵Bω→ωC[N]:ω→ω,对所有基B. 那么,性质6.5.ii,C[M]<$V蕴涵C[N]<$V,因此M≤VN。Q下面的定理意味着关于V-操作语义的完全抽象定理8.8 VV在V-操作语义上是完备的.我的律师。 我们将提供/±VV意味着/≤V。M/±VVN表示s[M]]V<$VΓ[[N]]V<$V,对于some<$∈(Var→I0). 因为他如果FV(M)≠ FV(N)={x1,., xm}则有Pi ∈ Γ 0F(F)故[[x]=[[x]]。 因此,令s(xi)=Pi(1≤i≤m),hences(M),s(N)∈Λ0. Thus[s(M)]]VJV特别是s(M)/±VVs(N)。Γ[[s(N)]]V<$ JV,f或所有<$ J∈(Var→I0),根据引理8.6,s(M)/nΓs(N),则存在一个闭Γ-值序列项Q使得s(M)QΓω→ω s(N)Q,定理7.5。令C [. ][]] (λx1. x条纹鲈[啊。)s(x1). s(xm)Q; 显然C [M],C [N] ∈Λ0和C[M]≠V和C[N]≠V,SoM/≤VN。Q所以我们可以陈述下面的定理。定理8.9该模型对于按值调用的操作语义是完全抽象的。L-运算语义的完全抽象模型的构造与此类似,但更为简单.引用[1] Abramsky S., 1比77[2] Abramsky S.,王立成,“Full abstraction in the Lazy Lambda Calculus”, I 159-267.[3] Alessi F.“Strutture[4] 巴斯托内罗·O古伊十世, 247-277[5] 巴斯托内罗·O Pravato A.,Ronchi Della Rocca S.,“Structures for Lazy Semantics”,[6] Coppo M.,Dezani-Ciancaglini M.,Honsell F.Longo G., 241-262.L. Paolini,S. Ronchi Della Rocca /理论计算中的电子注释。Sci. 104(2004)235-251251[7] Digianantonio Pietro,[8] 埃 吉 迪 湖 , Honsell F. Ronchi Della Rocca S. , “Operational, Denotational and LogicalDescription: a case study”, 149比170[9] 欣德利河,Longo G.,“Lambda演算模型和可拓性”,Z.数学,逻辑格。数学,26,1980,pp.289-310.[10] Honsell F. Ronchi Della Rocca S. , “An Approximation Theorem for Topological LambdaModels and the Topological Incompleteness of Lambda Calculus”,[11] 保利尼湖,Ronchi Della Rocca S.,“Call By Value Solvability”,[12] 保利尼湖,Ronchi Della Rocca S.,“The Parametric Parameter Passing[13] G. Plotkin,”Call by value, call by name and the 125-159
下载后可阅读完整内容,剩余1页未读,立即下载
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![.zip](https://img-home.csdnimg.cn/images/20210720083646.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)
会员权益专享
最新资源
- 电力电子系统建模与控制入门
- SQL数据库基础入门:发展历程与关键概念
- DC/DC变换器动态建模与控制方法解析
- 市***专有云IaaS服务:云主机与数据库解决方案
- 紫鸟数据魔方:跨境电商选品神器,助力爆款打造
- 电力电子技术:DC-DC变换器动态模型与控制
- 视觉与实用并重:跨境电商产品开发的六重价值策略
- VB.NET三层架构下的数据库应用程序开发
- 跨境电商产品开发:关键词策略与用户痛点挖掘
- VC-MFC数据库编程技巧与实现
- 亚马逊新品开发策略:选品与市场研究
- 数据库基础知识:从数据到Visual FoxPro应用
- 计算机专业实习经验与项目总结
- Sparkle家族轻量级加密与哈希:提升IoT设备数据安全性
- SQL数据库期末考试精选题与答案解析
- H3C规模数据融合:技术探讨与应用案例解析
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![](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)