没有合适的资源?快使用搜索试试~ 我知道了~
理论计算机科学电子笔记155(2006)191-217www.elsevier.com/locate/entcs多态的参数域理论模型直观/线性Lambda演算放大图片作者:Rasmus E. Rasmus L. Petersen彼得森1,2丹麦哥本哈根IT大学理论计算机科学系摘要我们提出了一个形式化的版本阿巴迪和Plotkin的逻辑参数的多态对偶直觉/线性类型理论与固定点,并显示,以下Plotkin的建议,它可以用来定义广泛的类型,包括解决方案递归域方程。我们进一步定义了一个参数的LAPL结构的概念,并证明它提供了一个健全的和完整的一类模型的逻辑,并得出结论,这样的模型有一个广泛的一类递归域方程的解决方案。最后,我们提出了一个具体的参数的LAPL结构的基础上适当的类别的部分等价关系的通用模型的无类型的lambda演算。保留字:参数多态,范畴语义,域理论1介绍在本文中,我们展示了如何定义多态直觉/线性lambda演算的参数域理论模型。这项工作的动机是两个不同的观察,由于雷诺兹和普洛特金。1983年,Reynolds认为二阶lambda演算的参数模型对于编程中的数据抽象建模非常有用[24](参见[18]最近的教科书描述)。对于真正的编程,1这项工作得到了丹麦技术研究委员会的部分支持,资助号:56-00-03092 电子邮件地址:birkedal@itu.dk、mogel@itu.dk、rusmus@itu.dk1571-0661 © 2006 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi:10.1016/j.entcs.2005.11.057192L. Birkedal等人理论计算机科学电子笔记155(2006)191当然,他不仅对诸如二阶lambda演算这样的强终止演算感兴趣,而且对具有完全递归的语言也感兴趣。因此,在LOC。前引书Reynolds还要求一个多态性的参数域理论模型[24]。非正式地说,这意味着[25]是一个模型的扩展,他的polymorphicla mbacalculus[2 3,9],与poly morphic不动点算子Y:α。(α→α)→α,使得(i) 类型被建模为域,没有多态性的子语言以标准方式建模,Yσ是域σ的最小固定点运算符;(ii) 逻辑关系定理(也称为抽象定理)在逻辑关系是可接受的时被满足,即,严格的、封闭的锁链限制;(iii) 域中表示某种多态类型的每个值都是参数的,因为它满足逻辑关系定理(即使它不是该类型的任何表达式的解释)。当然,这种非正式的描述为问题的不同形式化留下了空间即便如此,这也被证明是一个不小的问题。Plotkin [21]的未发表的工作指出了解决问题模型的一种方法-理论上通过在无类型lambda演算的域模型上使用严格的、可容许的部分等价关系,但是,据我们所知,这种关系参数模型的细节以前还没有详细研究过。(We在这里这样做)。In loc.前引书Plotkin还建议,人们不仅应该考虑多态lambda演算的参数域理论模型,而且应该考虑多态直觉/线性lambda演算的参数域理论模型,因为这将提供一种在演算中区分严格和可能非严格连续函数的方法,并且因为一些类型构造,例如,余积,不应该在一个有固定点的carnival闭范畴中建模[10]。事实上,Plotkin认为,这样的演算可以作为域理论的一种非常强大的元语言,其中也可以使用参数化来编码递归类型。为了证明参数性的这些结果,Plotkin建议使用阿巴迪和Plotkin的参数性逻辑的变体因此,多态直觉/线性lambda演算的参数域理论模型从编程语言的角度(用于建模数据抽象)和从纯域理论的角度来看都是重要的。最近,Pitts及其同事[19,2]提出了一种句法方法来应对ReynoldsL. Birkedal等人理论计算机科学电子笔记155(2006)191193Lence来自一种名为Lily的语言的操作语义,它本质上是多态直觉主义/线性lambda演算,具有操作语义。与这里提出的工作并行,Rosolini和Simpson [27]已经展示了如何使用直觉集合论中的合成域理论来构建参数域理论模型。此外,他们已经展示了如何给莉莉一个计算上足够的指称语义在本文中,我们对直觉/线性lambda演算的参数域理论模型的研究做出了以下贡献:• 本文给出了不动点线性Abadi-Plotkin逻辑(LAPL)的一种形式化。术语语言,被称为PILLY,用于多态直觉/线性逻辑(Y代表固定点组合子),是Barber和Plotkin的演算的一个简单扩展,用于具有多态性和固定点的对偶直觉/线性lambda演算(DILL),该逻辑是Abadi-Plotkin的参数逻辑的扩展,具有形成可容许关系的规则。该逻辑允许对PILLY项进行直观推理;即,这些项可以是线性的,但是关于项的推理总是直观地进行。在LAPL中,我们可以给出参数性后果的详细证明,包括递归域方程的解;这些结果和证明在以前的文献中没有正式提出过由于篇幅原因,我们在此省略了它们;它们可在所附的技术报告中找到。• 我们给出了参数LAPL结构的定义,这是LAPL参数模型的一个基本概念,并给出了相关的可靠性和完备性定理。• 我们基于无类型lambda演算的通用模型上的部分等价关系的适当类别,提出了一个具体的参数化LAPL结构的定义,从而证实了民间传说的想法,即人们应该能够在无类型lambda演算的通用模型上使用部分等价关系我们注意到,可以看到我们的参数的LAPL结构的概念作为一个合适的范畴公理化的一个良好的范畴域。在Axiomatic Domain Theory中,早期的许多工作都集中在公理化predomains和连续函数的范畴与predomains和部分连续函数的范畴之间的连接[5,第7页]。– here we axiomatize the adjunction between the category of domains andstrict functions and the category of domains and all continuous functions andextend it with parametric polymorphism, which then suffices to model alsorecursive194L. Birkedal等人理论计算机科学电子笔记155(2006)191在技术发展中,我们使用了可容许关系的概念,我们将其公理化,因为可容许关系在不同的模型中可能意味着不同的东西。我们相信,我们的公理化是合理的,因为它涵盖了几种不同类型的模型,如这里描述的经典模型和基于合成域理论的模型[16]。这里提出的工作建立在我们以前关于参数化Abadi-Plotkin逻辑的范畴模型的工作上阅读本文不必熟悉[3]的细节(除了[3]的附录A,它包含了一些关于可组合振动的定义和理论),但是,对于不熟悉参数性的读者来说,从[3]开始可能会有所帮助,因为这里给出的参数性结果的证明比[3]中的证明稍微复杂一些,因为使用了线性。在随后的论文中,我们打算展示如何定义一个计算上足够的Lily模型,以及如何从Rosolini和Simpson作为一个推论,人们可以得出[ 27 ]和[ 2 ]中提到的递归类型的编码确实有效(这些属性没有在loc中正式证明。前引书).我们还将扩展[3]的参数完成过程,以在给定多态直觉/线性lambda演算模型的情况下产生参数化的LAPL结构,参见[15]。由于篇幅的原因,本文省略了许多证明。更多细节可参见随附的技术报告[4],其中包括所有的财产证明在此陈述31.1概述本文的其余部分组织如下。在第2节中,我们提出了LAPL,用于在多态直觉/线性lambda演算(PILLY)上推理参数性的逻辑。在第3节中,我们陈述了参数性的一些主要结果(详细证明见[4]在第4节中,我们给出了LAPL结构的定义,并证明了它的可靠性和完备性。在第5节中,我们提出了参数的定义3读者可以在以下网址找到技术报告的在线副本:www.itu.dk/people/birkedal/papers网站。L. Birkedal等人理论计算机科学电子笔记155(2006)191195J结构,并证明了在这种结构中可以求解递归域方程在第6节中,我们提出了一个具体的参数的LAPL结构的基础上部分等价关系的通用域模型。为了使模型更容易理解,我们首先提出了一个PILLY的模型(没有参数),然后展示了如何将其转化为参数化的LAPL结构。此外,作为如何在模型中计算的一个例子,我们描述了可定义的自然数对象。2线性Abadi-Plotkin逻辑在本节中,我们定义了一个逻辑,用于推理具有固定点的多态直觉线性Lambda演算(PILLY)的参数性。该逻辑基于阿巴迪和普洛特金的参数性的逻辑基本上是PILLY上的高阶逻辑。逻辑的表达式是PILLY的变量和PILLY类型之间关系的上下文中的公式。首先,我们来定义一下药丸Y。2.1Y药丸PILLY本质上是Barber和PlotkinPILLY中的格式良好的类型表达式是以下形式的表达式α1:类型,. ,α n:类型<$σ:类型其中,σ使用以下语法σ::= α|我|σ⊗τ|στ |!σ|α。σ,σ的所有自由类型变量都出现在旋转栅门的左侧。α的列表我们在类型系统中包含了IPILLY的条款形式如下:Ξ |x1:σ1,.,xn:σ n; XJ:σJ,.,xJ :σJ► t:τ1 1m m其中σi、σJ和τ是类上下文中的良构类型。名单x被称为直觉类型上下文,通常表示为Γ,而列表196L. Birkedal等人理论计算机科学电子笔记155(2006)191xJ被称为线性类型上下文,通常表示为Δ。变量不重复名字在任何上下文中都是允许的,但是类似于交换规则的置换是允许的。由于形成规则的性质,除了线性上下文之外,所有上下文都可以导出弱化和收缩。术语的语法是:t::= x |** |Y |λx:σ.t |TT|特什特|!不|Λ α:t型|t(σ)|设x:σ_y:τ是t中的t|让!x:σ be t in t|让 * 在测试中测试我们使用λ来表示线性函数抽象,λ在图形上与λ有一些相似之处我们用S,T,U……在条款上进行调整。给出的形成规则是DILL [1]的标准规则,扩展到具有类型变量的上下文,加上类型抽象和类型应用的标准规则以及公理Ξ |Γ; − γ Y:α。!(!αα)α。Ξ |如果对于所有出现在Γ和Δ中的类型σ,Γ; Δ被认为是良构的,则Γ; Δ是良构的类型构造。如果出现在Δ中的变量集合与出现在ΔJ中的变量集合不相交,则Δ和ΔJ被认为是不相交的。我们用−来表示一个空的上下文。由于let结构和函数抽象中的变量类型通常从上下文中显而易见,因此这些通常会被省略。PILLY项上的外部等价关系是DILL [1]中的规则所给出的最小等价关系,对Y项推广了一个明显的规则,对多态类型推广了β-和η我们以通常的方式通过定义σ→τ=对普通的lambda抽象进行编码!στ和λx:σ。t =λ◦y: ! σ。让!x是t中的y,其中y是新变量。使用这种符号,常数Y以更熟悉的类型Y出现:α。 (α → α)→ α。2.2逻辑如上所述,LAPL的表达式存在于PILLY的变量和PILLY类型之间的关系的上下文中。上下文如下所示:Ξ |Γ |R1:Rel(τ1,τJ),.,Rn:Rel(τ n,τJ),1NS1:AdmRel(ω1,ωJ),. ,Sm:AdmRel(ω m,ωJ)1m其中,|Γ; −是PILL Y的上下文,τ i,τJ,ω i,ωJ是良构类型我我在上下文中,对于所有i.R和S的列表并且通常表示为Θ。至于其他上下文,我们允许置换,但不允许重复变量。L. Birkedal等人理论计算机科学电子笔记155(2006)191197可容许关系的概念取自Domain理论。直觉可容许关系是关联的,且在链的最小上界下是封闭的.重要的是要注意,在上下文中没有线性分量Δ- 关键在于,该逻辑仅允许关于PILLY的项的直觉推理,而PILLY项可以线性地表现。逻辑中的命题由语法给出φ::=(t = σu)|ρ(t,u)|φ⊃ψ| ⊥ |不|φ∧ψ|φ∨ψ|α:φ型|x:σ。φ |Rel(σ,τ).φ|图5:AdmRel(σ,τ).φ|α:φ型|x:σ。 φ |Rel(σ,τ).φ|图5:AdmRel(σ,τ).φ其中ρ是一个可定义的关系(将在下面定义2.2.1可定义关系可定义的关系,范围为ρ,由下面的规则定义。可定义的关系总是有一个域和一个共域,就像术语总是有类型一样。可定义关系的基本形成规则是:Ξ |Γ |Θ,R:Rel(σ,τ)R:Rel(σ,τ)Ξ |r,x:σ,y:τ|Θ θφ:PropΞ |Γ |θ(x:σ,y:τ).φ:Rel(σ,τ)|Γ |θ ρ:AdmRel(σ,τ)Ξ |Γ |Θ θρ:Rel(σ,τ)注意,在第二个规则中,我们只能抽象直觉变量来获得可定义的关系。在最后一个规则中,ρ:AdmRel(σ,τ)是一个容许关系,下面将讨论。该规则说,可容许关系构成可定义关系的子集一个可定义关系的例子是函数的图关系f=(x:σ,y:τ).fx = τy,其中f:σ τ. 等式关系eqσ被定义为恒等映射的图。如果ρ:Rel(σ,τ)是一个可定义的关系,并且我们被赋予了正确类型的项,那么我们可以形成这样的命题,即这两个项通过可定义的关系相关联:Ξ |Γ |Θ θρ:Rel(σ,τ)θ |Γ; − τt:σ,s:τΞ |Γ |θ ρ(t,s)(一)198L. Birkedal等人理论计算机科学电子笔记155(2006)191我们也将ρ(t,s)写成tρs我们介绍了一些简化符号的关系重新索引对于f:σJσ,g:τJτ和ρ:Rel(σ,τ),我们将可定义关系记为(f,g)<$ρ(x:σJ,y:τJ)。ρ(f x,g y).2.2.2可定义关系在本小节中,我们提出了一些关于可定义关系的构造,这些构造将用于给出PILLY类型的关系解释。我们定义,,!,并以这样的方式对关系进行处理,- 第4节中介绍的一类关系-变成线性范畴,即,PILLY的模型。如果ρ:Rel(σ,τ)和ρJ:Rel(σJ,τJ),则我们可以构造一个可定义关系(ρ ρJ):Rel((σ σJ),(τ τJ)),定义为ρρJ=(f:σσJ,g:τ τJ)。x:σ。y:τ。ρ(x,y)<$ρJ(fx,gy).如果α,β|Γ |Θ,R:AdmRel(α,β)θρ:Rel(σ,τ)格式良好,|Γ |Θ是格式良好的,θ,α<$σ:类型,β<$τ:类型我们可以定义Ξ |Γ |Θ =(α,β,R:AdmRel(α,β)).ρ:Rel((α. σ),(β.τ))作为(t: α:类型。σ,u:β:τ型)。 α,β:类型。 AdmRel(α,β)。ρ(tα,uβ)。对于ρ:Rel(σ,τ),我们试图定义一个关系!ρ:Rel(!σ,!τ)。首先,我们对任何类型σ定义关于σ的命题(−)↓为x↓f:σI. f(x)= I*。这一定义是由于[27]。 这里的直觉是,既然我们已经固定了点,我们可以把类型看作域,所以x↓被认为是x。我们进一步定义了地图:!σ σ作为λx:!σ。让!在y = λx:σ中y是x。X.我们现在可以定义L. Birkedal等人理论计算机科学电子笔记155(2006)191199!ρ=(x:!σ,y:!τ).x ↓ <$$>y ↓ <$(x ↓ <$ρ(<$x,<$y))。200L. Birkedal等人理论计算机科学电子笔记155(2006)191按照场域的直觉,!被认为是提升,并且提升单元提供元素的未提升版本。这个公式表示要么x和y都是X,要么它们都是提升元素,它们的未提升版本是相关的。接下来,我们将定义ρ和ρJ的张量积ρ<$ρJ:Rel((σ<$σJ),(τ<$τJ)),对于ρ:Rel(σ,τ)和ρJ:Rel(σJ,τJ)。定义的基本要求在第4节中引入的关系LinAdmRelations的范畴中,为了给出一个满足这一要求的具体定义,我们走了一条稍长的路线。我们首先介绍地图f:σ τα。(στα)α定义为f x =令xJ∈xJJ:στ是Λ α中的x。λh:σ τα。hxJxJJ。然后我们定义ρ<$ρJ=(f,f)<$(α,β,R:AdmRel(α,β)). (ρρJ右)R),或者,如果我们把它写出来,(x:σ<$σJ,y:τ<$τJ)。α,β,R:AdmRel(α,β)。时间:στα,tJ:σJτJβ。(ρρJR)(t,tJ)<$R(令xJ<$xJJ为x in t xJxJJ,令yJ<$yJJ为y intJyJyJJ)。这一令人印象深刻的明确定义的基础是我们将在以后提出的,利用参数性,σ τ同构于α。(στα)α,以及我们已经对后者有了一个关系解释。了用 这一定义是由亚历克斯·辛普森提出的。类似地,为了定义关系IRel:AdmRel(I,I),我们定义映射f:Iα。αα作为λx:I. 设 * 为id中的x,其中id = Λ α。λx:α。x和定义IRel=(f,f)((α,β,R:AdmRel(α,β)).R R),如果我们把它写出来(x:I,y:I)。AdmRel(α,β,R:AdmRelL. Birkedal等人理论计算机科学电子笔记155(2006)191201(α,β))。 z:α,w:β。zRw<$(let * be x inz)R(let * be y in w).202L. Birkedal等人理论计算机科学电子笔记155(2006)1912.2.3容许关系关系参数性的雷诺定义[24]中使用的关键概念是类型的关系解释。具有n个自由变量的类型的关系解释是一个接受n个关系并返回a的函数。新的关系。 然而,我们不要求这个函数定义在所有关系向量上,而只要求它定义在“可容许关系”的向量上另一方面,这个函数也应该返回可接受的关系。由于可容许关系的公理如图1所示。在最后一条规则中,ρ<$ρJ是<$x,y的简写。ρ(x,y)ρJ(x,y).命题2.1容许关系包含所有的图,并且在2.2.2节的构造下是封闭的。现在,最后,我们可以给出可定义关系的最后一个形成规则:α1,...αn<$σ(α):类型Ξ |Γ |θ πρ1:AdmRel(τ1,τ′),.,ρn:AdmRel(τn,τ′)1NΞ|Γ |Θ <$σ [ρ]:AdmRel(σ(τ),σ(τ ′))我们称σ[ρ]为类型σ的关系解释。注2.2注意到σ [ρ]是一个句法结构,不像[ 3 ]那样是通过替换得到的。还是σ [ρ1/α1,.,ρ n/α n]可能是一个更完整的符号,但这很快就变得过于冗长。在[22]中,σ[ρ]在某种程度上是根据σ的结构归纳定义的,但在我们的情况下不是这样的。足够了,因为我们需要为类型常量形成σ[ρ](当使用LAPL模型的内部语言时)。我们在公理中捕捉归纳定义。2.2.4公理和法则在指定了LAPL语言之后,是时候指定公理和推理规则了。我们有谓词逻辑的所有常用公理和规则,以及下面指定的公理和规则。对于变量、关系变量和类型变量的术语、可定义关系和类型的替换有明显的规则。对类型、项和关系进行泛量化和存在量化的规则是标准的。通常,外部相等意味着内部相等,并且有明显的规则表示内部相等是等价关系。直觉上可容许的关系应该与x和x有关,我们需要一个公理L. Birkedal等人理论计算机科学电子笔记155(2006)191203JJΞ|Γ |Θ,R:AdmRel(σ,τ)R:AdmRel(σ,τ)Ξ |Γ |θ eqσ:AdmRel(σ,σ)Ξ|Γ|θρ:AdmRel(σ,τ)|Γ;− τt:σσ,u:ττx,y∈/ΓJ J JJΞ |Γ |Θ =(x:σ,y:τ)。ρ(t x,u y):AdmRel(σ,τ)JΞ|Γ|θρ,ρ:AdmRel(σ,τ)x,y∈/ΓJΞ|Γ |Θ =(x:σ,y:τ)。 ρ(x,y)<$ρ(x,y):AdmRel(σ,τ)Ξ|Γ|θρ:AdmRel(σ,τ)x,y∈/ΓΞ|Γ |Θ=(y:τ,x:σ)。 ρ(x,y):AdmRel(τ,σ)|Γ |θ ρ:AdmRel(σ,τ)Ξ|Γ|你好!ρ:AdmRel(!σ,!τ)x,y∈/ΓΞ|Γ |Θ =(x:σ,y:τ)。 T:AdmRel(σ,τ)Ξ|Γ|θρ:AdmRel(σ,τ)|Γ|Θθφ:Propx,y∈/ΓΞ|Γ |θ(x:σ,y:τ).φ ρ(x,y):AdmRel(σ,τ)α |Γ|θρ:AdmRel(σ,τ)|Γ|θσ:Typeθτ:Typex,y∈/ΓΞ|Γ |Θ =(x:σ,y:τ)。α:类型。 ρ(x,y):AdmRel(σ,τ)|r, z:ω|θρ:AdmRel(σ,τ)x,y∈/ΓΞ|Γ |Θ =(x:σ,y:τ)。 ωz:ω。ρ(x,y):AdmRel(σ,τ)JΞ|Γ|Θ, R:AdmRel(ω,ω)θρ:AdmRel(σ,τ)x,y∈/ΓJΞ|Γ |Θ =(x:σ,y:τ)。 AdmRel(ω,ω)。 ρ(x,y):AdmRel(σ,τ)JΞ|Γ|Θ, R:Re 1(ω,ω)θρ:AdmRe1(σ,τ)x,y∈/ΓJΞ|Γ |Θ =(x:σ,y:τ)。 Rel(ω,ω). ρ(x,y):AdmRel(σ,τ)J JΞ|Γ |θ ρ:AdmRel(σ,τ),ρ:Rel(σ,τ) |Γ|Θ|联系我们JΞ |Γ |θ ρ:AdmRel(σ,τ)Fig. 1. 可容许关系说明这一点。 一般来说,我们将使用(−)↓作为x的检验。Ξ|Γ|Θθρ:R el(!σ,!τ),ρJ:AdmRel(!σ,!τ)x,y∈/ΓΞ |Γ |Θ |x:σ,y:τ。ρ(!x,!y)ρJ(!x,!y)艾利克斯:204L. Birkedal等人理论计算机科学电子笔记155(2006)191!σ,y:!τ。 x ↓ <$$> y ↓ <$(ρ(x,y)<$ρJ(x,y))(二)L. Birkedal等人理论计算机科学电子笔记155(2006)191205我们有关于将类型解释为关系的规则αα i:型|Γ |Θ πρ:AdmRel(τ,τ J)Ξ |Γ |Θ |Tα i [ρ] ρ iα►σσJ:类型|Γ |Θ πρ:AdmRel(τ,τJ)π |Γ |Θ |T <$(σ σJ)[ρ]<$(σ [ρ] σJ [ρ])α<$σ<$σJ:类型<$|Γ |Θ πρ:AdmRel(τ,τ J)Ξ |Γ |Θ |T <$(σ<$σJ)[ρ]<$(σ [ρ]<$σJ[ρ])<$|Γ |Θ πρ:AdmRel(τ,τ J)Ξ |Γ |Θ |TI [ρ] I Relα►β。σ(α,β):类型|Γ |Θ πρ:AdmRel(τ,τ J)Ξ |Γ |T(β。σ(α,β))[ρ] π(β,βJ,R:AdmRel(β,βJ)).σ [ρ,R])α!σ:型号 :|Γ |Θ πρ:AdmRel(τ,τ J)Ξ |Γ |Θ |T(!σ)[ρ]!(σ[ρ])这里ρ<$ρJ是x,y的简写。xρy xρJy.如果可定义关系ρ具有(x:σ,y:τ)的形式。φ(x,y),则ρ(t,u)应该等价于φ,其中x,y被t,u替代:Ξ |r,x:σ,y:τ|Θθφ:Prop | Γ; − τt:σ,u:τΞ|Γ |Θ |T ∈((x:σ,y:τ). φ)(t,u)φ [t,u/x,y]最后,我们需要一个公理来说明不动点组合子的参数性:Ξ |Γ; −|Θ <$Y( α. (α→α)→α)Y2.2.5可拓性与同一性扩展模式以下两种模式称为扩展性模式:(x:σ)。t x = τu x)t = στu(τα:t α = τu α型)τ t = Qα:τu型。引理2.3在逻辑中可以证明:σf,g:σ → τ。(x:σ)。f(!x)=τg(!(x))x:!σ。f(x)=τg(x).特别是,外延性意味着206L. Birkedal等人理论计算机科学电子笔记155(2006)191σf,g:σ → τ。(x:σ)。f(!x)=τg(!x))τf=σ→τgL. Birkedal等人理论计算机科学电子笔记155(2006)191207JJF架构− | − |−α:类型。σ [eqα]eqσ(α)被称为身份扩展架构。这里σ的范围涵盖所有类型的实例。对于任何类型的β,α1,.,α n<$σ(β,α),我们可以形成参数性图式:− | − |−:(β. σ)。 β,β。 AdmRel(β,β)。 (uβ)σ [R,eqα](u βJ),其中,为了可读性,我们省略了:β,βJ和eq α后的类型是eqα1, . 的 简 短符 号 。 . ,eqαn.这是因为如何有一个明确的扩展模式意味着参数化模式。3LAPL中的证明在LAPL中,人们可以对广泛的类型集合的可定义性进行形式证明,包括递归类型,如Plotkin [21]所建议的那样我们已经详细地写出了所有的证明,但这里没有空间把它们包括在内。可参见随附的技术报告[4]。主要结果是定理3.1设α <$σ(α):型是纯PILL Y中的型。存在一个封闭型rec α。σ和一对项f:rec α。σσ(rec α.σ),g:σ(rec α.σ)rec α。σ,使得恒等扩张模式蕴含f∈g=σ ( rec α.σ ) σ ( rec α.σ )idσ ( rec α.σ )和g∈f=rec α.σ recα.σidrec α.σ.4LAPL结构在本节中,我们介绍了一个LAPL结构的概念。LAPL结构是LAPL的模型.然而,首先,我们要记住什么是PILL的模型(PILL是没有术语Y的PILLY),以及PILL在这样的模型中是如何解释的(对于PILL模型的完整描述和这些模型中的解释,参见例如[17,13,1,12])。PILL的一个模型是一个固定的对称monoidal adjunctionLinType,,ype,Gp,sssssss,z,scs善良,208L. Birkedal等人理论计算机科学电子笔记155(2006)191我我我zK_ind使得LinType是有界对称monoidal闭的;Type中的张量是有界Carnival积;Type等价于自由余代数的有限积范畴;Kind是Carnival;p有一个类属对象和关于忽略Ω的投影的简单积,其中Ω是类属对象的p。[13]这是一个非常详细的解释。回想一下,PILL在这样的模型中被解释如下。类型σ被解释为对象[σ]]∈LinType,我们解释项α|x:σ; xJ:σJ<$t:τ作为态射![[σ1]]... 快![[σ n]][[σJ]]. [[σJ]][[τ]]1m在LinType中,在哪里!=FG。当然,[!σ]] =![[σ]。注意,我们将LinType中的态射表示为。进一步回想一下,微积分的直觉部分,即微积分中没有自由线性变量的项,可以用类型来解释。假设我们有这样一个术语,|x:σ; − τt:τ。那么这个术语在LinType中的解释是[[|x:σ; − t:τ]]:i![[|σ i]][[|τ]]。Since![[|σ]]=F(G([[|σ]]))(Fcanbeprovedtobetrong)and!= FG,我们有,使用附加词FEG,这样的一项对应于[[|x:σ;− t]]Type:iG([[σi]])→G([[τ]])在类型。最后,PILLY的模型是PILL的模型,其对不动点算子进行建模Y:α。(α→α)→α定义4.1前LAPL结构是(i) 范畴和函子道具,tLinType、、你好啊,你好, 、RJCtx......,qp ,,zJ使得、L. Birkedal等人理论计算机科学电子笔记155(2006)191209F• 图LinType,,ype,Gp,sssssss,z,s cs种是Y药丸的模型。• q是一个具有纤维有限积的纤维化• (r,q)是一个指数化的一阶逻辑纤维化,它具有关于Kind中的投影<$x Ω → <$x的乘积和上积[3],其中Ω是p应用于p的类属对象。见下文备注4.2• I是一个忠实的保积映射。(ii) 一个纤维化的逆变态射:LinType×Kind LinTypeUCtx、、、、,,z_ 得双曲余切值.种(iii) 双射族H_mCtx_n(n,U(σ,τ))→O_b_j(Prop_n×I(G(σ)×G(τ)对于LinType中的σ和τ以及Ctx中的τ,• 在域变量中是自然的• 在σ,τ• 与重索引函子交换;也就是说,如果ρ:J→是Kind中的态射,u:→U(σ,τ)是Ctx中的态射,则ΨΞJ(ρ∗(u))=(ρ¯)∗(ΨΞ(u))其中reρ是ρ的笛卡尔升力。请注意,仅在垂直态射上定义了x1。注4.2我们要求对(r,q)是一个索引一阶逻辑纤维化。这意味着,对于每一个以Kind表示的对象来说,r对f上的纤维的限制我们进一步要求(r,q)有简单的乘积和余乘积,这意味着逻辑模型在类型上的量化。进一步注意,实际上,U是由对结构其余部分的要求唯一定义的,因此我们通常将前LAPL结构简单地称为第1项中的所谓纤维函子U的逆变,我们是指U在每个纤维中都逆变。、、、、210L. Birkedal等人理论计算机科学电子笔记155(2006)191J我们现在解释如何在pre-LAPL结构中解释LAPL的子集。我们在这个阶段考虑的LAPL子集是没有可容许关系和没有类型的关系解释的我们解释的LAPL的范畴Ctx的子集的全部上下文如下。上下文Ξ |x1:σ1,. x n:σ n|R1:Rel(τ1,τJ),.,R m:Rel(τ m,τJ)被解释为我 IG([[σi]])×j1mU([[τj]],[[τJ]]),其中,类型的解释是LinType →Kind。为了便于记法,我们将[1]写成|Γ|对于t在Ct x中的解释,tha t是对于I([[t])的解释,|Γ;− t:τ]]Type)π(不是ete下标类型),其中π是投影π:[[|Γ |θ]] → [[θ |Γ|在Ctx中。逻辑中的命题在Prop中以范畴逻辑的标准方式解释。上下文中定义域σ和余域τ的可定义关系|Γ |[001 pdf 1st-31files][001 pdf1st-31files][001 pdf 1st-31files]|Γ |[1],[2],[3],[4],[5]。可定义关系|Γ|Θ,R:Rel(σ,τ)R:Rel(σ,τ)被解释为投影,并且[[|Γ |θ(x:σ,y:τ).φ:Rel(σ,τ)]]−1([[|r,x:σ,y:τ|θφ]])。我们现在定义ρ(t,s)的解释,对于一个可定义的关系ρ和项t,s的正确类型。 首先,对于|Γ |θ ρ:Rel(σ,τ),我们定义[[|r,x:σ,y:τ|θ ρ(x,y)]]= θ([θ |Γ |Θ θρ:Rel(σ,τ)]])。接下来,如果|[001 pdf 1st-31files]r:σ,s:τ,则[[001 pdf 1st-31files] |Γ |Θ <$ρ(t,s)]]等于⟨⟨π,⟨[[Ξ|Γ |θ t]],[[|Γ |θ s]],πJ [[|r,x:σ,y:τ |θρ(x,y)]],其中,π,πJ是投影π:[[π]]|Γ |θ]] → [[θ |[]]和πJ:[[π]]|Γ |Θ]] →[[| − |θ]]。为了解释可容许关系,我们将假设我们被给予U的子函子V,即,一个定义域和上定义域为U的逆变函子V和一个分量都是单态的自然变换V<$U。因此,对于所有σ,τ,我们可以认为V(σ,τ)是U(σ,τ)的子对象我们认为V(σ,τ)是所有可容许关系的子集(因为同构允许我们认为U(σ,τ)是所有可定义关系的集合)。
下载后可阅读完整内容,剩余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直接复制
信息提交成功