没有合适的资源?快使用搜索试试~ 我知道了~
多态和递归类型的句法逻辑关系
理论计算机科学电子笔记172(2007)259-299www.elsevier.com/locate/entcs多态和递归类型的句法逻辑关系罗伯特·哈珀2卡内基梅隆大学计算机科学系匹兹堡,宾夕法尼亚州15213摘要逻辑关系方法为类型分配一个关系解释,该类型表示一个类型的所有项所满足的操作不变式。该方法广泛用于类型化语言的研究,例如建立术语的上下文等价。使用逻辑关系的主要困难是建立一个合适的关系解释的存在。我们扩展工作的皮茨和Birkedal和哈珀构建关系的解释类型的多态性和递归类型,并将其应用于建立参数和表示独立性属性在一个纯粹的操作设置。我们认为,一旦建立了关系解释的存在,就可以直接使用它来建立利益属性。关键词:操作语义,类型结构,程序逻辑,lambda演算和相关系统,数据抽象,多态性。1引言这是一个愉快的贡献这篇论文在荣誉戈登D。普洛特金在他六十岁生日的时候。Plotkin对编程语言的数学基础的研究是独特的,为后来的许多工作提供了基础,并为被忽视或不理解的问题建立了新的方法。有几个主题与本文所述的工作有直接关系一个重要的主题是使用操作语义来定义和分析编程语言。 Plotkin的结构化操作语义学[25,24]特别具有启发性。执行被建模为一个过渡系统,其状态是程序。转换关系由反映程序结构的推理规则集合归纳定义。转换规则指定1电子邮件:crary@cs.cmu.edu2电子邮件:rwh@cs.cmu.edu1571-0661 © 2007 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi:10.1016/j.entcs.2007.02.010260K. 克拉里河Harper/Electronic Notes in Theoretical Computer Science 172(2007)259各个执行步骤和这些步骤的执行顺序。程序的执行行为的性质,例如类型安全,可以通过转换规则的归纳来证明。Plotkin工作的另一个主题应用莱布尼茨的不可分割的同一性原理,两个程序片段在观察上是等价的,即它们产生相同的可观察结果,但是它们可以用于完整的程序中。作为粗一致同余,可以用余归纳法证明两个分片在观测上是等价的.但在实践中,这样的直接证明很少是有效的,需要一个更容易处理的特征。Plotkin在他对PCF的开创性研究中[22],考虑了指称方法,结果证明这些方法为观察等效提供了充分但非必要的条件。这需要证明相对于PCF的操作语义的指称语义的计算充分性,Plotkin使用逻辑关系的方法证明了这一点[32]。皮茨指出,逻辑关系也可以用来获得观测等价性的有用特征[18]。与每个类型相关联的是一个等价关系,称为逻辑等价,它是通过为每个类型构造函数分配关系上的操作来定义的 关系作用被这样定义,即逻辑等价是一个相容的同余,因此它是观察等价的充分(而且在许多情况下是必要)条件。对于简单的类型系统,逻辑等价性是通过类型结构上的归纳来定义的,这导致了一种优雅的证明方法来建立观测等价性。但在更丰富的类型系统中,需要复杂的方法一个复杂的因素是非断言多态性,如Girard和Reynolds所介绍的[7,8,28]。关系参数性的概念[29]将对数等价推广到多态类型。在简单的情况下,参数性可以用来描述多态语言的观测等价性通过Mitchell和Plotkin这可以看作是Hoare证明抽象类型实现正确性的方法[ 10 ]的推广递归类型为逻辑关系方法带来了进一步的复杂性在这里,我们再次遇到中心主题Plotkin的研究,即解决递归型方程,并发展理论的parametricity存在的递归类型。基于Scott的特别是,他与Smyth的工作[31]开创了递归类型的范畴理论研究,导致Freyd将Abadi和Plotkin研究了在指称设置中存在递归类型的关系参数化,提出了部分等价关系解释[1],并在此设置中开发了参数化逻辑[26]。普洛特金的所有这些研究主题都融入了本作品。我们认为,sider一个调用值的业务解释的吉拉德-雷诺兹多态K. 克拉里河Harper/Electronic Notes in Theoretical Computer Science 172(2007)259261类型λ-演算[7,28]扩展了一般递归类型。我们的主要结果是观察等价的一个完整的表征,其中我们观察到的终端在单位类型的逻辑等价方面然后,我们使用逻辑等价的状态和证明参数属性的语言。特别是,我们重新制作了Sumii和Pierce [33]的一个例子,以与他们的互模拟技术进行比较主要的技术挑战是为这样一个丰富的类型系统定义逻辑等价我们希望提供一个关于观测等价性的合理而完整的定义,它允许我们导出多态类型的参数性性质为了说明递归类型,我们在一个完整的可接受关系格上工作,这些关系格是指向的,尊重观察等价性,并支持通过固定点归纳进行推理(精确定义见第2我们为每个类型构造函数分配一个在这个关系空间上的容许作用,确保逻辑等价是一个同余,因此包含在观察等价中。由于容许关系尊重观测等价性,所需的完整表征如下。关键的问题是为语言的每个类型构造函数定义一个可接受的关系动作。函数类型的关系操作将函数关联起来,将相关参数映射到相关结果。为了将关系操作分配给多态类型,我们使用Girard方法的一个变体如果对应的实例对于这些实例类型之间的可容许关系的每个选择是相关的,则该动作关联两个多态在Pitts [19]之后,与一般递归类型相关的关系动作依赖于Freyd对类型方程的解的最小不变量表征的操作版本Birkedal和Harper [4]利用ciu等价[14]对具有单一递归类型的简单类型语言证明了这个性质,称为句法最小不变性在这里,我们给出了一个新的,流线型的证明基于应用等价[12]。 逻辑等价,然后构造利用语法最小不变性处理递归类型,和Girard的 多 态 类 型 的 方法 。逻辑等价特别便于证明语言的参数性和表示独立性。认为基于逻辑关系的方法推导这些属性过于复杂,Sumii和Pierce [33]开发了一种基于新形式的双模拟的新方法。相反,我们认为,主要的复杂性在于证明逻辑等价的定义,这可以一劳永逸地完成。我们在第6节中展示了使用逻辑等价推导表示独立性质是直接的。例如,我们展示了如何利用关系参数性获得Sumii和Pierce的结果。证明减少到选择一个合适的可接受的关系,并证明这个关系是由抽象类型的操作保持。262K. 克拉里河Harper/Electronic Notes in Theoretical Computer Science 172(2007)259τ12类型τ::= α|1 |τ1→τ2|α.τ|μ α.τ项e::= x| ∗ |λx:τ.e|e1e2|Λ α.e|e [τ]|单位:μα.τe|输出E值v::= x| ∗ |λx:τ.e|Λ α.e|单位:μα.τv|类型Γ::=|Γ,α|r,x:τFig. 1. 语法2预赛2.1语言该语言的语法如图1所示。静态语义如图2所示,操作语义如图3所示。操作语义由闭合项之间的小步、按值调用的转换关系组成,写作e<$→eJ。我们将类型集和类型索引的表达式集族定义为:如下所示:类型def={τ|τ型}E xpd=ef{e|e:τ}我们将E对EJ中X的捕获避免替换记为EJ[E/X]。像往常一样,我们识别仅在绑定变量的名称中不同的表达式。该语言享有通常的类型安全属性,如下面的引理所表示的,我们在整个过程中使用这些引理而没有明确引用。引理2.1(类型保持)如果εe:τ且e<$→eJ,则εeJ:τ。引理2.2(进展)如果εe:τ且e不是一个值,则(对某个eJ)e <$→ eJ。引理2.3(唯一类型)如果Γ e:τ且Γ e:τ J,则τ = τ J。我们将使用图4中的缩写。由于类型的唯一性,我们有时会省略这些缩写中的类型下标,因为它们在上下文中很清楚。动态语义的这些基本属性将在后续中使用:⊥τ ›→2 ⊥τfixτ→τ F<$→3λy:τ1.F(fixF)y (对于值F)i+1τ1→τ2F›→ λy:τ1.F(fixiF)y(对于值F)菲克斯K. 克拉里河Harper/Electronic Notes in Theoretical Computer Science 172(2007)25926311► 语境► Γ context Γ<$τ型x/∈Dom(Γ)► Γ,x:τ上下文► Γ contextα/∈Dom(Γ)► Γ,α上下文► Γ context FV(τ)<$Dom(Γ)Γ<$τ型► Γ context Γ(x)=τΓx:τ► Γ contextΓ上下文:1τ,x:τ1τe:τ2τ1.e:τ1→τ2Γe1:τ1→τ2Γe2:τ1Γ,αε:τΓ Λα.e:α.τΓe:τα.τJΓτ型Γe[τ]:τJ[τ/α]τe:τ[μα. τ/α]以μα.τe为单位的ττe:μα.ττ[μα]。τ/α]图二. 静态语义e1›→eJe1e2›→eJe2e›→eJve<$→v eJ(λx:τ.e)v<$→e[v/x]e›→ eJe[τ]›→eJ[τ](Λα.e)[τ]›→e[τ/α]e›→ eJinμα.τe<$→inμα.τeJe›→eJoute<$→outeJout(inμα.τv)<$→v图三. 结构化操作语义2.2适用等同性264K. 克拉里河Harper/Electronic Notes in Theoretical Computer Science 172(2007)259类型的关系解释将在取模应用等价的项的等价类上定义[11],这是操作等价的一种方便形式。K. 克拉里河Harper/Electronic Notes in Theoretical Computer Science 172(2007)259265defτ1→τ2idτd=efλx:τ. Xdefλ τ=(λx:T. (out x)x)(inT(λx:T. (out x)x))(其中T = μα。α → τ)fixτ1→τ20τ1→τ2=(out(inTJv))(inTJv)(其中v = λx:T J. λf:T → T。λ y:τ1.f((out x)xf)yT=τ1→τ2T J= μα。 α →(T → T)→ T)d=efλf:((τ1→τ2)→τ1→τ2). λy:τ1。⊥τi+1τ1→τ2fixωdef=λf:((τ1d=effix→τ2)→τ1→τ2)。λy:τ1.f(F)yτ1→τ2τ1 →τ2见图4。缩写等价性(在第5节中,我们证明了应用等价与上下文等价一致,即表达式上的粗一致等价关系。)开放项的应用等价性是通过考虑其封闭替换实例来定义的。为了这个目的和其他目的,我们需要替换的概念。类型化上下文中的变量。定义2.4我们将替换定义为从类型变量到类型以及从项变量到项的映射。如果:• 上下文,以及• Dom(σ)= Dom(r),以及• 对所有的α∈Γ,<$σ(α)型,且• 对所有x:τ∈Γ,有<$σ(x):σ(τ).应用近似被共归纳地定义为满足每种类型的消元规则所确定的条件的最大前序。我们区分近似的计算,这可能不会终止,从值,这是充分评估。定义2.5(i) 应用近似定义为最大关系式εe1≤e2:τ在封闭的条件下,例如:• 仅当εe1,e2:τ,且e1 <$$> →εv1意味着对某些情况,e2 <$→εv2v2,使得|v1≤valv2:τ,其中• nv1≤valv2:τ当且仅当 nv1,v2:τ,且菲克斯2菲克斯266K. 克拉里河Harper/Electronic Notes in Theoretical Computer Science 172(2007)259我· τ=1,或· τ=τ1→τ2且(对于所有满足τv:τ1的v)τv1v≤v2v:τ2,或· τ=α.τJ且(对于所有τJJ,使得τJJ类型)v1[τJJ]≤v2[τJJ]:τJ[τJJ/α],或· τ=μα。τJ和τoutv1≤outv2:τJ[τ/α]。(ii) 我们将应用逼近推广到开项如下:若Γ <$e1,e2:τ,且(对所有σ使得<$σ:Γ)<$σ(e1)≤σ(e2):σ(τ).(iii) 两个项e1和e2在上下文Γ中的类型τ处应用等价(写为如果Γ e1≤e2:τ且Γ e2≤e1:τ,则为Γ e1 e2:τ)。(iv) 如果εe1,e2:τ,那么我们写e1≤e2来表示εe1≤e2:τ。如果Γe1,e2:τ,则我们写Γe1≤e2表示Γe1≤e2:τ。(v) 类似地,如果e1,e2:τ,那么我们写e1 <$e2表示e1<$e2:τ。如果那么我们写Γ e 1 <$e2来表示Γ e1<$e2:τ。请注意,应用近似的“仅当”条件变成了“当且仅当”,从定义中可以很容易地得出下列基本性质提案2.6• 应用近似和等价是自反的(在适当类型的术语上)和传递的。• 应用等价是对称的。• 如果e1是良型的,且e1<$→e2,则e1<$e2。引理2.7(替换性和同余)应用近似是替换性和同余,在以下意义上:• 若Γ,x:τ,ΓJ<$e1≤EJ且Γ <$e2≤EJ:τ,则Γ,ΓJ<$e1[e2/x]≤EJ[EJ/x].1 2 1 2• 适用近似值根据以下规则关闭Γ,x:τ∈≤eJΓe1≤eJΓe2≤eJΓλx:τ.e≤λx:τ.eJ1 2Γe1e2≤eJeJ1 2Γ,α∈e≤eJΓΛα.e≤Λα.eJΓe≤eJre[τ]≤eJ[τ]Γe≤eJτe≤inμ α.τeJΓe≤eJr_oute≤outeJ证据通过一个简单的应用豪的方法[ 11 ]。Q推论2.8对于所有良型类型τ1和τ2,如果i≤j,则τ1→τ2≤jτ1→τ2≤fix τ1→τ2。菲克斯菲克斯266K. 克拉里河Harper/Electronic Notes in Theoretical Computer Science 172(2007)2591 21 2Val12Val12ValVal通过展示满足定义2.5的要求的关系来建立应用等价。引理2.9(适用近似的共归纳)假设R是一个类型索引关系,使得对于所有的τ ∈Type,R τ是Expτ上的二元关系。进一步假设:(i) 如果e RτeJ和e停止,则eJ停止,并且(ii) 若eRτ→τEJ且v ∈ Expτ 则ev RτeJv,并且(iii) 如果e R<$α.τeJ和τJ∈Type,则e[τJ]Rτ[τJ/α]eJ[τJ],并且(iv) 如果eRμα.τeJ,则oute Rτ[μα.τ /α]outeJ。则eRτeJ蕴涵e≤eJ。证据 设RJ和RJ关系定义如下:•Rje2:τ当且仅当Rje1,e2:τ且存在EJ,EJ使得e1eJREJ1 22.• RJv2:τ当且仅当v1,v2:τ,且· τ= 1,或· τ=τ1→τ2且(对于所有v,使得τv:τ1) τv1v RJv2v:τ2,或· τ=τα.τJ和(对于所有τJJ,使得ττJJ类型) τv1[τJJ]RJv2[τJJ]:τJ[τJJ/α],或· τ= μα.τJ和τ outv1RJoutv2:τJ[τ/α]。我们主张,如果e1RJe2和e1<$→v1,则对于某个v2,e2<$→v2,使得JValv2. 通过共归纳得出,e1RJe2意味着e1≤e2,因为Rj而≤是符合其规范的最大关系结果然后是反射性。设e1<$EJRej<$e2和e1<$→ev1。 那么eJ↓,根据条件1,eJ↓,所以1 2 1 2e2↓。因此,令e2<$→v2。注意,v1≠eJ,v2≠eJ。它仍然表明,v2:τ,其中τ是v1和v2的类型。我们按τ上的情形继续下去。设τ=τ1→τ2。设τv:τ1是任意的。通过条件2,eJv R eJv. 因此,使用同余,v1veJv R eJvv2v。因此1 2 1 2v1v RJv2v,因此v1RJv2。 其他情况都是类似的或微不足道的。Q2.3紧凑性不动点归纳法的运算模拟依赖于紧性,紧性表明在终止计算中,结果只需要递归函数的有限次“展开”。然而,在存在更高类型的情况下,精确语句必须考虑结果中递归函数的剩余出现我们可以优雅地管理这样的剩余事件,通过表示应用近似的展开,而不是相等。这种方法很有帮助,因为我们可以观察到,一个有剩余出现的项支配着一个没有剩余出现的项,从而忽略了这些剩余出现。这种对应用近似的关注使我们证明了一个更强的最小上界定理(定理2.11从这个定理中,我们可以得到一个简洁的-v1RK. 克拉里河Harper/Electronic Notes in Theoretical Computer Science 172(2007)2592672作为一个简单的推论。然而,我们将发现,许多后来的结果更方便地获得直接使用最小上界定理。不,不,不让我们一起来见证这一点吧。f[i]定义为[fixif/w]。我也不知道。8和一致性,如果i≤j,则ef[i]≤ef[j]≤ef[ω](预先定义了已关闭和已删除的资源)。引理2.10(模拟)假设p是一个值,并且p是f[ω]→p(当f[ω]是封闭的并且是线性的)。 其中x为tj,vJ为v=vJf[ω],k≥j时ef[k]≥vJf[k−j]。我的律师。 L etef[ω]›→Lv. 该方法是一种非线性的方法,其特征在于它不依赖于E的结构。如果e是一个值,则结果可以简单地通过令vJ=e得出。我们通过e的非值形式的情况来进行。案例1:Suppos e e=w. Tenef[ω]=fixf. Sincef[ω]是一个简单的函数,fm具有一个函数类型,所以设fm:τ1→ τ2. 则v = λy:τ1.f(fix f)y。 设vJ= λy:τ1.fw y,且letj=1. 其中v=vJf[ω]。 Suppos e k≥1。你好,ef[k]=fixkf›→+λy:τ1.f(fixk−1f)y(因为k>0)=vJf[k−1]Henc e ef[k]≥vJf[k−j]。例2:假设e=e1e2。然后又道:ef[ω]=ef[ω]1 2›→mv1ef[ω](对于一些m l)›→nv1v2(对于某个n l)›→+v通过归纳,,vJ,i,vJ使得(对于p=1,2)v=vJf[ω]和1122 pp所有k≥i ,ef[k] ≥vJf[k−ip]。 因此,我们可以从mλx:τ的角度来研究这一问题。eJ。Letp pp 1 1eJ=eJ[vJ/x]。然后又道:1 2ef[ω]›→ωv1v2=(λx:τ. eJf [ω])vJf [ω]1 2›→ eJf[ω][vJf[ω]/x]1 2=eJf[ω]›→ov(for someo l)268K. 克拉里河Harper/Electronic Notes in Theoretical Computer Science 172(2007)2591111通过引入,则x为i,vJ满足v=vJf[ω ],并且对于所有k≥i,eJf[k]≥vJf[k−i]。设j = i + i1+i2,且k≥j. 然后又道:ef[k]=ef[k]1 2≥vJf[k−i1]vJf[k−i2](通过congruence)1 2≥vJf[k−i1−i2]vJf[k−i1−i2](通过congruence)1 2=(λx:τ. eJf[k−i1−i2])vJf[k−i1−i2]1 2›→eJf[k−i1−i2][vJf[k−i1−i2]/x]1 2=(eJ[vJ/x])f[k−i1−i2]1 2=eJf[k−i1−i2]≥vJf[(k−i1−i2)−i](sincek−i1−i2≥i)=vJf[k−j]Henc e ef[k]≥vJf[k−j]。例3:Suppose e=μa。τe1. 这是一个新的版本。τv1,当f[ω]→τv1时。通过内归纳,存在j,vJsuchthatv1=vJf[ω]并且对于所有k≥j,ef[k] ≥vJf[k−j]。 LetvJ=inμ a。τvJ. 如果k≥j,则ef[k]=1 11单位为μα。τef[k]≥inμα。τvJf[k−j]= vJf[k−j],通过计算。1 1另外两个案例也是类似的。Q假设2.11(最大边界)暂停。 3如果是,ef[j]≤eJ,则ef [ω] ≤ eJ。证据 由于f是停顿的,我们可以通过同余而不失一般性地假定f是一个值。设R和Rval是如下定义的关系:• 如果等式1,等式2:τ,并且等式1具有等式Jf[ω],其中,等式j。eJf[j]≤1 1e2。• Rvalv2:τ当且仅当Rvalv2:τ,且· τ= 1,或· τ=τ1→τ2且(对于所有满足τv:τ1的v) τv1v R v2v:τ2,或· τ=τα.τJ和(对于所有τJJ,使得ττJJ类型) τv1[τJJ]R v2[τJJ]:τJ[τJJ/α],或· τ= μα.τJ和τ outv1Routv2:τJ[τ/α]。我们主张,如果e1Re2和e1<$→v1,则对于某个v2,e2<$→v2,使得v1Rval v2.从这个主张通过共归纳得出结果,因为R因此适合≤的规定,而≤是适合其规定的最大关系在此之前,向上p〇 se e1Re2ande1›→p 〇v1。 f[ω]>1. ByLe mma2.10,特征为tj,vJ,满足v1=vJf[ω]和dk≥j。 vJf[k−j]≤eJf[k]。在一个简单的过程中,1 1 1 1K. 克拉里河Harper/Electronic Notes in Theoretical Computer Science 172(2007)259269[3]如果f不停止,引理也很容易成立,因为(对所有k)fixf。270K. 克拉里河Harper/Electronic Notes in Theoretical Computer Science 172(2007)259111111nn1transi ti tity , 以 及 variabes ( letingi=k−j ) 的a c h a n g e e,ni 。 vJf[i]≤e2.Therefore2→briv2andd(sinceevaluationisdeterministic)brief. vJf[i]≤v alv2。 我想让你看看v1值v2。我们继续讨论v1类型的情况:案例一:假设是1:1。 然后v1Rval v2.案例2:Suppose?v1:τ1→τ2和Supo s e?v:τ1。 其中v1v=(vJv)f[ω]。但对于yi,(vJv)f[i]=(vJf[i])v≤v2vbyycongrue. 这是一个非常好的例子,1 1v 1 Rval v 2.案例3:Suppos e pouvv1:Poula。我和我的朋友们在一起。 Thenv1[τJ]=(vJ[τJ])f[ω]。对于任意i,(vJ[τJ])f[i]=(vJf[i])[τJ]≤v2[τJ],通过比较,证明了这一点。Thusv1[τJ]Rv2[τJ]11因此v1Rval v2。Ca se4: Sup ppos e pouvv1:μα. τ。输出v1=(输出vJ)f[ω]。对于yi,(outvJ)f[i]=out t(vJf[i])≤outv2。 这是输出v1R输出v2和输入v1R输出v2。Q1 1Corollary2.12(Ccompactness)Supposefhalts. 如果 [ω]停止 ( 并 关 闭 和 关闭),则该索引将导致[j]停止。我的律师。补充说明,对于CONTRADICTION, 4THATEF[ω ] ↓ , 对 于所有J,EF[J]↑。对于所有j,ef[j]≤πτ。 在L emma2.11中,ef[ω]≤τ,eef[ω]↑,但这不符合上述假设。Q2.4可受理性和不确定性我们将把注意力限制在容许关系类上,它是由指称语义学中链完备性条件的表达式类向量和关系的类型元组索引集定义如下:ECVτ,.,τdefτ τ1n=(Expτ1/1)×···×(Expτn/n)Relτ,.. . ,τd=efP(ECVτ,. . ,τ)定义2.13关系R ∈ Rel τ1,.,τn是可容许的,如果它满足以下两个条件:• (Pointedness)(尖锐性),<$τn)∈R• (完备性)假设(对于k = 1,. ,n)τJ,τJJ∈Type和w:τJ→ τJJ∈k:k k k kτ k和f k:(τJ→τJJ)→τJ→τJJ。如果对所有i,存在j≥i,使得k k k k(ef1[j], . . ,efn[j])∈R,thehen(ef1[ω], . . ,efn[ω])∈R.1n1n定义2.14关系R∈Relτ1,.,τn是严格的,如果每当(e1,.,e n)∈ R对某些i,e i↓,则对所有i,e i↓。4 如果愿意,也可以直接从引理2.10导出一个构造性证明。[5]为了简单起见,在不考虑构造性的情况下,以这种方式陈述指向性条件。本文中的定理如果用(构造性更强的)来代替,则可以构造地实现命题((proposal)) ei↓)n(e1,. ......、en)∈ R)<$(e1,. ,en)∈R. 这些条件在经典环境中是等价的K. 克拉里河Harper/Electronic Notes in Theoretical Computer Science 172(2007)259271我KK关系类的格属性对于递归类型的解释是必要引理2.15对于任意τ1,.,τ n∈Type,Rel τ 1,.中的严格可容许关系的集合,τn形成一个完整的格,其中底元素{(e1,. ,e n)∈ ECV τ1,...,τn |e1↑ n···e n↑ },顶元素{(e1,.,e n) ∈ ECVτ1,.,τn| (2002年)e i↓) ⇒ (2002年)e i↓)},由交点计算的相交,以及由所有上交点计算的连接界限。引理2.16(不动点归纳法)假设R∈Relτ1→τJ,.,τn→τ J是AD-1N允许的,F1,. ,Fnhalt,且(对于1≤i≤ n)<$Fi:(τi→τJ)→τ i→ τ J。如果(λx:τ1. 你好,...,λx:τ n. J)∈R 并且,在本发明中,为所有(f1,.(f n)∈R,i1n(λx:τ1. F1F1X,...,λx:τ n. F n f n x)∈R,则(fixF1,.,fixFn)∈ R.证据注意w:τ k→τj w:τ k→ τJ。我们通过归纳证明,对于所有i,(w F1[i],.,wFn[i])∈R.根据第一个假设,(W F1[0],...,wFn[0])=(fix0F1,.,fix0F n) (λx:τ1. 你好,...,λx:τ n. τJ)∈R.假设,对于归纳法,1N则(w F1[i],.,w Fn[i])=(fixiF1,.,fixiFn)∈R.然后(w F1[i+1],.,w Fn[i+1])=(fixi+1F1,.,fixi+1F n)<$(λx:τ1.F1(fixiF1)x,.,λx:τ n. Fn(fixiFn)x)∈R第二个假设。因此,对于所有i,存在j≥i(即i本身),使得t(wF1[j], . . ,wFn[j])∈R. 通过对R,(fixF1, . . ,fixFn)=(w F1[ω],.,wFn[ω])∈ R.Q记法我们将fixg(x:τ1):τ2.e记为FIX(λg:τ1→τ2。λx:τ1.e)。当f是形式fixg(x:τ1):τ2.e,我们写f i为平均值fixi(λg:τ1→ τ2。λx:τ1.e)。推论2.17(不动点归纳法)设R∈Relτ1→τJ,τ2→τJ 是admis-1 2sible和(i = 1,2)g:(τ i→τJ),x:τ i∈ i:τ J. 如果(λx:τ1. τJ,λx:τ2。<$τJ)∈i i1 2R且对于al(f1,f2) ∈R, (λx:τ1. e1[f1/g],λx:τ2. e2[f2/g])∈R,theNn(fixg(x:τ1):τ j.e1,fixg(x:τ2):τ j.e2)∈ R.1 23句法最小不变性在整环上,一类混合方差递归整环方程的解可以统一地表示为一类整环上的双函子F及其对函子F的最小变元ti:F(D,D)n=D[6]. i的极小性确保D的每个元素都是其有限投影的极限;这相当于要求与方程相关联的某个递归定义的函数是恒等式。Pitts [19]证明了最小不变量的存在对于递归域上的关系的构造是足够的,并使用它来证明使用逻辑关系参数的指称语义的充分性。继Birkedal和Harper [4]之后,我们证明了最小不变性条件的一个操作模拟,称为句法最小不变性。关键的观察是,上面提到的有限投影在语言中是可以定义的,就像它们的极限一样,这是一个递归定义的函数。 然后,我们表明,这272K. 克拉里河Harper/Electronic Notes in Theoretical Computer Science 172(2007)259一限制是应用等价的身份。我们在这里给出的论证是对下面给出的句法最小不变性证明的扩展和改进:K. 克拉里河Harper/Electronic Notes in Theoretical Computer Science 172(2007)259273παd=efpαπτ→τdef121τ τ1 2 =λf:(τπdef→τ)。λx:τ.π2(f(π1x))α.τ =λf:(λα.τ)。Λ α。(π τ[id α/p α])(f [α])π μα。τd=effixf(x:μα. τ):μα。τ。单位为μα。τ(π τ[μα. τ,f/α,pα])(outx)defπ1= λx:1。∗图五. 句法投射函数伯克达尔和哈珀。扩展包括考虑一般的递归和多态类型,而不是单一的固定递归类型。这需要更多的机器,但基本上沿着与以前相同的路线进行。技术上的改进是,通过考虑一系列可能的带有句法投射的术语“装饰”,使论证变得流线化,这是一个更强的归纳假设的前提首先,我们定义每种类型τ的句法投射函数πτ:τ→τ,如图5所示。注意,对于类型变量,语法投影函数遵从形式为pα的已标识项变量。一个适当的投影函数稍后被替换为pα-在多态变量的情况下是恒等式,在递归类型变量的情况下是投影本身。引理3.1如果β1,.,β nπ τ型则β1,.,β n,p β1:β1→β1,.,p βn:β n→β n→π τ:τ→τ。引理3.2项π τ[τ J,π τJ/α,p α]和π τ[τJ/α]在 语 法 上是相同的。3.1投影近似恒等式证明投影πτ适用于逼近τ型恒等函数是比较直接的。论证通过τ的结构上的外归纳进行,在递归类型的情况下是内不动点归纳。引理3.3假设β1,. ,β n<$τ型,且对所有1 ≤i≤n,<$vi≤idτi:τ i. 当πτ[→τ ,→v/β→,pβ→]≤idτ[→τ/β→]:τ[→τ/β→]→τ[→τ/β→]时,我的律师。 我不知道。 Letσ=[→τ,→v/β→,pβ→]。情形1:假设τ=βi。则πτ σ=pβiσ=vi.假设vi≤idτi。情形2:假设τ= 1。则π τσ = λx:1。1.情形3:SupposeT=τ1→τ2,且τJ→τJ=(τ1→τ2)[→τ/β→]。Tenπτσ=1 2λf:(τ J→ τ J)。λx:τ J。(π τσ)(f((π τσ)x))。设τv:τJ→τJ。我们希望展示1212 112即λx:τJ。(πτ σ)(v((πτ σ)x))≤valv.设τvJ:τJ。那么它表明,12 11274K. 克拉里河Harper/Electronic Notes in Theoretical Computer Science 172(2007)25911111(πτ σ)(v((πτ σ)vJ))≤v vJ。通过归纳法,πτ σ≤idτJ,所以(πτ σ)vJ≤vJ。通过2 1 111同余,v((πτ σ)VJ)≤VVJ. 通过归纳,πτ σ≤idτJ,所以(πτ σ)(v((πτσ)vJ))≤v((πτ11σ)vJ)≤vvJ。222 1例4: Suppose τ=α。τ1并且tτJ=τ1[τ→/β→]。Tenπτσ=λf:(λα.τ J)。Λ α。(π τσ [id α/p α])(f [α])。设τv:τα.τJ.我们希望展示111J这是。(πτ1σ[idα/pα])(v[α])≤v. 假设是πτ型。那么它表明,(π τσ [τJ,idτJ/α,p α])(v [τJ])≤v [τJ]。当然idτJ ≤idτJ,所以通过归纳,πτ σ[τJ,idτJ/α,pα]≤idτJ[τJ/α],结果如下。11例5:Suppose τ=μ a。τ1和τJ=τ1[→τ/β→]。Def ineπ=πτσanddntethatπ一个fix值我们通过归纳证明了对所有i,πi≤idμα.τJ.结果如下最小上界引理Least Upper Bound Lemma基本情况是微不足道的。 对于归纳情形,假设π i≤ id μα.τ J。副作用τv:μα,τJ.我们希望证明在μα.τJ((π τσ [μα.τJ,π i/α,p α])(outv))≤1111v.由于πi≤idμα.τJ,通过外归纳,πτ σ[μα.τJ,πi/α,pα]≤111idτJ[μα.τJ/α]。 因此(πτ σ[μα.τJ,πi/α,pα])(outv)≤ outv。通过一致性,1 111inμα.τJ((πτ σ[μα.τJ,πi/α,pα])(outv))≤inμα.τJ(outv).但是,v必须具有以下形式:1111inμα.τ JvJso inμα.τ J(out v)›→ inμα.τJvJ= v. 因此,在μα中,τ J(out v)≤ v。Q1 1 13.2投影主宰身份要证明投射在应用上支配恒等式,需要一个稍微复杂一些的论证。直觉上,πτ e的求值可能导致一个项在该项中的任意位置包含许多进一步的投影出现。我们把每一个都称为通过一定数量的投影对基本项的修饰,注意πτ e就是这样一个修饰。 我们表明,一个表达式是由它的所有装饰,从直接遵循的结果,适用性占主导地位。术语的修饰由其类型决定。为了在类型检查中解释替换,我们必须考虑一个项的类型可能作为另一个项的替换实例出现的所有可能方式,我们称之为因式分解。此外,为了归纳,我们必须考虑基于因式分解的投影的所有可能的合成。这导致了以下定义。定义3.4• 当τ是一个类型,σ是一个类型上的替换时,我们说(τ,σ)是一个因子分解若τσ = τ j,则为τ J(记为τ JD(τ,σ))。• 若π=(τ,[→τ/α→])是一个因子,且τ[ → τ /α → ]是一个β →的可解,则ππα定义为πτ[→τ,id→τ,idβ→/α→,pα→,pβ→]:τ[→τ/α→]→τ[→τ/α→].• 我们写τ D 1,. 对于每一个1 ≤ i ≤ n,我们记为π1,. n [e]表示πK. 克拉里河Harper/Electronic Notes in Theoretical Computer Science 172(2007)259275命题3.5如果π因子化τ,则对任何类型的置换σ,存在τσ的因子化πJ使得π π σ=π πJ。276K. 克拉里河Harper/Electronic Notes in Theoretical Computer Science 172(2007)259ϕ→ϕ→术语的可能修饰由语法指导的规则集合确定定义3.6• 装饰关系ΓeDeJ:τ定义如下:ΓxDπ[x]:τ(Γ(x)=τandτD→)ΓDπ[x]:1(1D→)r,x:τ1eD e<$:τ2 rτ1typ erτ2typerλx:τ1. eDπθ→[λx:τ1. e<$]:τ1→τ2(x/∈Dom(Γ)和τ1→τ2 D→)Γe1De<$1:τ1→τ2Γe2De<$2:τ1Γe1e2Dπ→[e<$1e<$2]:τ2(τ2D→)Γ,αeDe<$:τ是的。eD ππ→[Λα. e<$]:α.τ (α/∈Dom(Γ)andnd<$α. τD→)Γ►eD e¯:∀α. τrτJtypeτe[τJ]Dπ→[e<$[τJ]]:τ[τJ/α](τ[τJ/α]D→)eD e<$:τ[μα. τ/α]Γ►i nμα. τeD π→[以μα计。τe<$]:μα。τ(μα。τD →)eD e
下载后可阅读完整内容,剩余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直接复制
信息提交成功