没有合适的资源?快使用搜索试试~ 我知道了~
虚构的范畴语义的模态类型理论:扩展理论计算机科学的新方法
可在www.sciencedirect.com在线获取理论计算机科学电子笔记323(2016)143-161www.elsevier.com/locate/entcs纤维模态类型理论Valeria de Paiva瓦莱里娅·德·派瓦1,2自然语言和人工智能研究实验室NuanceCommunications,美国美国艾克·里特3英国伯明翰大学计算机科学学院摘要本文描述了一个虚构的范畴语义的模态必要性只有片段的建设性模态类型理论,无论是依赖类型和没有。构造类型理论通常不讨论逻辑模态,模态往往主要在经典逻辑中研究,而不是在类型理论中。但是模态在类型论中应该非常有用,因为它们在建模理论计算系统时非常有用。提供模态逻辑及其相关的Curry-Howard模态类型理论的构造性版本也是一个非常有成效的程序,例如在处理计算效应,阶段计算和功能反应类型时很有帮助。 似乎有新的兴趣在建设性模态类型理论的概念(和线性类型理论的概念),部分原因是同伦类型理论的兴趣。这里提出的模态类型理论使用依赖类型,以Ritter的构造演算的分类模型的风格。 为了建立这些,我们首先讨论的种类建构模态类型理论的最新研究成果。然后,我们提供了一个非依赖模态类型理论,在前面的工作中介绍,我们推广到依赖类型在下面的部分。依赖类型理论通常但并不总是被赋予关于纤维化的范畴语义。我们提供的非依赖和依赖类型系统的fibrations方面的语义讨论,并证明他们的声音和完整的,从而提供证据,类型理论是有意义的。这些虚构的模型也应该适用于同伦类型理论的设定。保留字:模态逻辑、纤维化、分类模型1介绍模态逻辑是一种形式逻辑系统,它扩展了命题(或谓词)逻辑,包括表达模态的运算符,主要是可能性和必要性的内涵概念,但也包括时间,道义,可证明性和其他类型的模态。1我们要感谢编辑Ma'rioBenevides和Re n'e Thiemann在排版问题上的耐心。2电子邮件:valeria. nuance.com3电子邮件:exr@cs.bham.ac.ukhttp://dx.doi.org/10.1016/j.entcs.2016.06.0101571-0661/© 2016作者。出版社:Elsevier B.V.这是CC BY许可下的开放获取文章(http://creativecommons.org/licenses/by/4.0/)。144诉de Paiva,E.Ritter/Electronic Notes in Theoretical Computer Science 323(2016)143模态逻辑,最初被认为是必要性和可能性的逻辑,已经发展成为一门自己的数学学科,处理(限制)描述语言来谈论各种关系结构。模态逻辑是计算机科学中使用最多的显式逻辑系统,但它的使用几乎都是基于经典模态逻辑,即在经典命题逻辑基础上的模态逻辑,而本文讨论的是构造性模态逻辑。构造模态逻辑从一个直觉命题基础开始,并在其上添加模态。这个过程就像任何一个逻辑系统的“构造化”过程一样,通常是一个一对多的过程,一个经典的概念产生了许多可能的构造版本,人们需要比较,对比和选择。各种数学、哲学和美学标准都可以用来选择你最喜欢的经典概念的建设性版本基本的一元(1位)模态算子通常写为Q,表示必然情况,表示可能情况。在经典模态逻辑中,这些运算符中的每一个都可以使用另一个使用否定来表示:QP参与Q<$P;QP参与-我是 在构造模态逻辑的情况下,这种算子的互定义性是不期望的,也是不需要的。这和我们在直觉主义中没有的方法一样逻辑普适和存在量化器之间的互定义性P(x)参与<$$>x<$P(x),<$x.P(x)Participate <$$> x <$P(x)就模态而言我们并不期望它。有时,逻辑学中不同的建构方法导致研究者得出相同的系统。特别是Fitch[18],Fisher-Servi [17],Ewald [15],Plotkin和Stirling,特别是Simpson [29]的工作,导致了最着名和最成功的直觉模态逻辑系统,基于系统IK。辛普森普拉维茨遵循一条非常不同的道路,在他的《自然演绎》(Natural Deduction)一书中,他也为系统S4和S5提供了直观的这项工作产生了一系列相关的工作,特别是关于S4的直觉主义版本,[8,7,16,2],其中指导直觉来自Curry-Howard对应。这些系统在这里被称为系统CS4,用于构造模态逻辑。对这些基于Prawitz式自然演绎的构造性模态系统的一些研究受到Girard的线性逻辑的启发我们以前在构造模态逻辑上的工作提供了一个DILL风格的对偶直觉模态演算(DIML)[19]。由于DIML的工作基本上是由使用分类组合子实现函数式语言的动机,DIML演算的主要工作是确保实现分类组合子所需的显式替换工作。但我们也介绍了仅必要性S4的构造性模态类型理论的基础,我们将在下一节中重现诉de Paiva,E.Ritter/Electronic Notes in Theoretical Computer Science 323(2016)143145本文的主要目标是显示这个建设性的模态类型理论的虚构的范畴语义我们已经知道这种虚构的范畴语义学有一段时间了,但它仍然停留在我们的“思考”思想文件夹中,因为我们没有令人信服的应用程序。现在似乎有新的兴趣在概念的建设性模态类型理论和线性类型理论,部分原因是在同伦类型理论的兴趣[30]。因此,写一个如何将S4中的box-only模态与依赖类型集成起来的好主意,使盒子依赖构造函数。2模态类型理论有些过时的调查[12]解释说,在文献中有几个关于构造模态逻辑和相关模态类型理论的建议它们来自不同的动机和直觉,来自逻辑、数学和计算机科学,来自作者不同的背景关于构造模态逻辑的开创性工作已经产生了最著名和最成功的直觉模态逻辑系统,基于Simpson的系统IK[29]。辛普森这些系统将与Prawitz的系统形成对比,Prawitz在他的自然演绎的开创性工作中也为系统S4和S5提供了直觉主义版本[26]。普拉维茨的工作产生了一个收藏相关的工作,特别是直觉版本的S4,[8,7,16],其中指导直觉来自库里-霍华德对应。这些系统被称为系统CS4,用于构造模态逻辑。与Simpson的系统不同Q(A<$B)→QA<$QB(1)Q→(2)我们所知道的模态类型理论的第一个版本是莫吉关于计算λ演算的开创性工作[ 24 ],由[ 7 ],[ 21 ]解释为一个相当退化的Borhuis的博士论文[9]在Barendregt立方体的基础上提出了一种经典的模态理论。 Borhuis使用了Fitch的自然演绎法的变体,它等价于一阶经典逻辑的Gentzen-Prawitz自然演绎法。但他认为模态类型理论是经典的,模态是可互定义的,如果目标是获得Curry-Howard对应,这就没有多大意义。还有Frank Pfenning及其合作者[25,11]在模态类型理论方面的重要工作,遵循Curry-Howard对应的S4和Martin-Léof区分判断和主张的方法这项工作,相反,[8,7]没有,总的来说,被关注,146诉de Paiva,E.Ritter/Electronic Notes in Theoretical Computer Science 323(2016)143范畴语义学在下一节中,我们将描述一个类似于[8]的系统,它起源于Prawitz的工作,并以[6]风格的Curry-Howard对应的范畴模型作为指导直觉。因此,我们认为模态系统与它们的直觉对应物是在同一水平上定义的。我们最初的动机是重新使用的机器处理减少简单类型的微积分。3对偶直觉模态逻辑我们回顾了在我们以前的工作[19]中介绍的称为对偶直觉模态逻辑(DIML)的构造性必然性证明系统,它基于Barber(和Plotkin原系统DILL设法保持还原系统的直觉命题和直觉线性逻辑,并排,通过使用直接“翻译”到逻辑的建议的模态系统DIML对直觉逻辑中的必然性模态做了同样的事情。请注意,尽管我们称之为逻辑,但该系统是一个与该逻辑相对应的柯里-霍华德类型论,也就是说,如果我们删除这些项,我们最终会得到该逻辑的一个自然演绎公式。我们回顾了类型理论的细节,因为将其推广到依赖类型是我们的主要目标。3.1DIML的类型判断DIML的类型有接地类型、功能类型A→B和盒型QA。变量被标记为xM或xI,以指示它们是模态的还是直觉的,DIML的原始表达式是t::= x M|X I|λx:A.t|TT| Qt|设t为t中的Qx其中x(变量上的标签有时会被省略,以增加可读性。我们确定α-等价项。上下文是一个序列的形式x1:A1,.,xn:An,其中x是不同的变量,A是类型。 DIML上下文由两个包含不相交的变量集的上下文Γ和Δ组成,并被写为Γ |Δ。 我们称Γ中的变量为模态变量,称Δ中的变量为直觉变量。DIML的类型判断具有形式Γ |Δ t:A和由图1中的推理规则生成。这些是简单类型lambda演算的规则加上Q模态的引入和消除规则。需要注意的是,引入一个必要的Q类型需要一个空的直觉语境,对应于我们可以说一个命题是必要的直觉想法,如果它所依赖的所有假设都是必要的,即。非必然模态假设的集合(它的直觉上下文)是空的。排除规则为诉de Paiva,E.Ritter/Electronic Notes in Theoretical Computer Science 323(2016)143147r,x:A,r J| A/DM:AΓ |Δ,x:A,Δ j xI:AΓ |Δ,x:A→t:B(→I) Γ |Δ Δt:A→BΓ |Δ u:AΓ |Δ λx:A.t:A→ BΓ |Δ Tu:B(→E)Γ| A(QI)Γ |Qt:QAΓ |Δ t i:QA iΓ,x:A|Δ u:BΓ|令t为u:B中的Qx(QE)Γ |Δ,x:AΔt:BΓ |Δ u:AΓ |Δ τ(λx:A.t)u = t[u/x]:BΓ |Δt:A → B(x/∈FV(t))Γ |Δ λx:A.tx = t:A→ BΓ| x:A| Δ,y:BCΓ|令Qt为Qx,u = u [t/x]:CΓ Δt:QA Γ |Δ,y:QAtJ:CΓ |Δ t令t为Qx,其中tJ [Q(x)/y]= tJ [t/y]Fig. 1. DIML(Dual Intuitionistic and Modal Logic)Q模态是常见的,遵循Schroeder-Heister的消除规则风格。由于这些变量的类型规则,这两种变量的弱化都是允许的。这两种变量的收缩都来自于上下文组合的加法方式。交换也是可以接受的。请注意,我们也可以有逻辑连接词和分离词的规则,但我们更倾向于集中在基本的连接词含义和情态上。DIML中更复杂的上下文性质导致了更微妙的Meta理论。正如变量类型有两条规则一样,根据被替换变量的性质,也有两个正如我们从线性代数学中所学到的,我们需要一个适当的双替换引理,以满足两种变量的需要,见下文。注意,忘记下面引理中的术语,我们得到了两种形式的切割规则,我们可以证明它们在DIML中是可接受的。引理3.1(替换)如果Γ |Δ Δt:A和Γ |x I:A,Δ εs:B,则为Γ |Δ Δs[t/xI]:B,其中re[t/xI]表示t-矩阵元级替换。 类似地,如果|−T:A和T,x M:A|Δ εs:B然后是Γ |Δ εs [t/x M]:B.我们可以将引入和消除规则视为彼此相反的,从而为每个类型构造函数导出β和η-相等判断。然后,这导致DIML的完全Curry-Howard对应,其可以是148诉de Paiva,E.Ritter/Electronic Notes in Theoretical Computer Science 323(2016)143证明了等价于[8]中的类型论,从而等价于Q-only S4的公理化定义,有时写作CS4。定理3.2存在一个公理化的仅Q直觉S4模态推导:有一个DIML项t和一个DIML判断|A.注意中的空模态上下文|Γt:A,模态变量总是可以移动到上下文的直觉部分,并将Q前缀给它们。这个证明是巴伯证明的一个简单的改编只有Q的构造性S4的可靠性和完备性定理,如在[8]可以通过DIML和CS4之间的转换和直接获得,如下。我们不扩展这些评论,而是直接转移到类型理论DIML中的3.2DIML的归约演算DIML中的约简仅由β-赎回组成,并且是包含基本约简(λx:A.t)ut[u/x]设Qu为Qy,单位为ss[u/y]两项t和u在方程理论中是等价的,DIML约简关系称为DIML等式nt,记为tn=u。主题缩减意味着通过缩减保留打字信息,我们只考虑那些还原是良好类型项的约简-通过主题约简,约简也是良好类型的。引理3.3(DIML主语归约)如果存在DIML类型判断Γ |A和a重写t <$tJ,则还有一个类型判断Γ |Δ Δ tJ:A.DIML约简的第二个关键属性是它包含在DIML的相等判断中。引理3.4如果Γ |Δ t:A和t u,则有一个相等判断Γ |Δ ►t = u:DIML中的A。定理3.5 DIML约化关系是强正规的和相容的.证据 强规范化证明了标准的reductionmethod,而consumption,然后遵循从本地consumption,这可能很容易被检查。Q3.3DIML语义刚刚给出的DIML的表示是基于类型和相等性判断的,以便尽可能平滑地与语义连接。我们的归约演算是为了模拟计算过程而设计的,因此仅限于诉de Paiva,E.Ritter/Electronic Notes in Theoretical Computer Science 323(2016)143149每个类型构造函数的β-redex,没有η转换。结果是一个行为良好的类型理论,如果需要,我们可以为它提供操作语义DIML的传统1-范畴语义也很容易陈述和证明合理和完备,就像类型论最初一样(在线性逻辑的情况下[4])。源自于此。定义3.6我们定义一个DIML范畴M为一对Carnival闭范畴(S,C),有两个对称的monoidal函子F:C→S和G:S→C,它们是伴随的,GEF。直觉是S对模态上下文和模态项进行建模,C对直觉上下文和直觉项进行建模。该附加函数用于对Q模态进行建模。定义一个解释[]:DIML→ M,它将DIML的类型和序列(在一个基本类型集上)带到一个模型M,如下所示:[[X]] =I(X)对于X,基类型[[A→B]] = [[A]] →[[B]][[QA]] =F G([[A]])我们将这种解释扩展到上下文(A1,. A n|B1,. B n)通过向模态假设添加框并定义[A1, . ,An|B1, . ,Bn]]=Q[[A1]]×···×Q[[A n]] × [[B1]] ×···× [[B n]]。 翻译需 要 一 个 小 时 |ΔΔt : A 到 箭 头 [[Γ|ΔΔt : A]] : [[Γ|[1][2][3][4][5][6][7][8][9][10][10][11][12][10][11][12][12][13][14][15][16]DIML类型理论可以在上面定义的DIML范畴中得到合理的解释定理3.7类型理论DIML具有由上面定义的结构M提供的可靠模型。换句话说,给定DIML类别M,使用上述解释,以下成立:• 假设Γ| Δ Δt:DIML中的A。然后,[]|A]]是S中的态射,其定义域为[[Γ| [A]和[A];• 假设r = s:A。 然后[[Γt:A]]= [[Γ s:A]]。我们也有DIML类别的完整性:定理3.8DIML模型在类型论DIML的适当意义下是完备的。这就是说,如果我们有平等的解释[[r]],t:A]]=[[Γs:A]](其中[[]]是上面定义的解释)在DIML范畴M中对于任何导出序列Γt:A和Γs:A,那么我们可以在类型论中导出DIMLΓt= s:A中的方程。这个证明是巴伯论文中的证明我们构建的长期模型,并表明,演算的基本规则映射到适当的态射使用的范畴结构。因此,我们手头上有一个相对简单的DIML模型,但在下一节中,我们将解释DIML的纤维化模型为什么?为什么?为什么我们要150诉de Paiva,E.Ritter/Electronic Notes in Theoretical Computer Science 323(2016)143用纤维化来模拟这种类型理论?原因是我们想对Martin-Léoff的 概念类型理论(DTT)的模态扩展幸运的是,我们中的一个人写了一篇关于依赖类型理论建模和有效实现的博士论文[28],所以大部分工作都已经到位,只需要适应necessity-modalconstructor的情况。4简单DIML Fibrational语义我们也可以通过纤维化而不是反射来模拟DIML类型理论。通常的纤维化建模框架是为具有依赖类型的理论开发的我们可以使用这个框架,通过施加强限制来建模没有依赖类型的理论,下面将讨论回想一下,使用Fibrations的依赖类型(乘积和和)的基本建模由于语法和语义之间的不匹配而变得有点复杂,因为语法中的替换是讨论在的n-实验室(http://ncatlab.org/nlab/show/categorical+model+of+依赖+类型)解释了几个几乎等价的公式的存在以及各自的优缺点Jacobs [20]提供了依赖类型理论及其分类建模的详细阐述。本文选择了一个基于索引范畴E:Bop→Cat的公式,它模拟了严格替换。为了在依赖设置中对必然性模态进行建模,我们遵循我们以前关于线性逻辑的工作的直觉,更具体地说,我们遵循对ILT建模的工作[23],一种直觉主义线性lambda演算,其中线性和直觉主义含义共存。主要的一点是,一个必要的Q模态,像线性逻辑砰!需要证明理论上的一种特殊形式的假设,这些必须是形式!A.类似地,为了引入模态类型QB,它的所有假设都必须具有形式QAi。我们首先回顾一下使用D-范畴对依赖类型的建模,然后我们将自己限制在非依赖类型上,但添加了必要性模态。4.1相关产品为了对简单依赖积(函数空间的一种推广)建模,我们使用了Ehrhard D-范畴的一个变体在这里,我们简单地回顾一下我们想要建模的依赖类型理论语法和我们所做的选择这些类型是接地类型和从属产品。原始表达式为A::= G|AB不* *= x| λx:A.t|TT诉de Paiva,E.Ritter/Electronic Notes in Theoretical Computer Science 323(2016)143151[]背景Γ ► 上下文ΓA类型Γ,x:一种新的语境Γ,xM:A/B型ΓxM:AB类型r,x:A,rJ<$x:AΓ,x:At:B(λI)Γλx:A.t:λx:ABt:r=0:B[u/x](英)r,x:At:Bru:AΓ(λx:A.t)u=t[u/x]:B[u/x]rt:rx:AB(x/∈FV(t))Γλx:A.tx=t:λx:AB图二. 依赖类型理论(Dependent Type Theory,DTT)其中x因为类型可能包含术语,所以我们需要对所有句法类别(即上下文、类型和术语)进行类型判断它们由图2中的推理规则生成。我们省略了上下文、类型和术语的一致性规则。对于基本依赖型理论,只有一个约化规则,即β-约化(λx:A.t)u<$t [u/x].因为类型之间存在非平凡的等式,证明依赖类型理论满足标准的元理论结果要困难得多。特别是,主题归约是一个非平凡定理。作为证明的一部分,我们必须证明两个相关乘积类型<$x:A′ B和<$x:A′ BJ相等,当且仅当A和AJ以及B和BJ相等。详情见[5]。引理4.1(DTT主语归约)如果在依赖类型论中有一个类型判断Γ t:A和一个重写ttJ,那么也有一个类型判断 A.主体归约也是表明依赖类型理论的归约包含在平等判断中引理4.2如果Γt:A且tu,则存在等式判断Γt =u:依赖类型理论中的A。为了模拟这种类型理论,我们有一个索引范畴E:Bop→Cat,其中基范畴B模拟通常的上下文Γ。物体Γ,E(Γ)模型上的纤维152诉de Paiva,E.Ritter/Electronic Notes in Theoretical Computer Science 323(2016)143其变量包含在由Γ建模的上下文中的术语。我们需要一个终端对象T在B中。每一个纤维都是一个carbohydrate闭范畴。我们还要求对于基B中的每个态射f,E(f)保持终端对象。这个索引范畴的关键构造是被称为“理解性质”的要求精确定义如下:定义4.3D-范畴是一个索引范畴E:Bop→Cat,使得(i) B有一个终端对象T;(ii) 函子I:B →Gr(E)定义为I(Γ)=(Γ,1)和I(f)=(f,Id)有一个右伴随G。记G((Γ,A))为Γ·A,G((f,h))为(Fst,Snd),G((f,h))为f·h(iii) 对于每对态射g:Γ·A→ Δ·B和f:Γ→ Δ使得Fst≠g=f<$Fst在E(Γ)存在唯一态射h:A→f<$B使得g =f·h;(iv) 对于E(Γ)中B和A的任意对象Γ,函子Fst ∈A:E(Γ)→E(Γ·A)有一个右伴随函子Fst ∈ A:E(Γ·A)→E(Γ).在续篇中,我们将写HomE(Γ·A)(Fst_A(B),C)与HomE(Γ)(B,Fst_A(C))之间的自然同构Cur,以及它的对偶App.(v) 严格 意义上满足映 射 Fst<$AE<$A 的 Be ck-Che valley 条 件 , 即 方 程f<$ ( CurA(h))= CurA((f·Id) <$(h))对任意f:Δ → Γ,A∈E(Γ),B∈E(Γ·A)和态射h:1·B在E(Γ·A)中成立.任何依赖类型理论都可以在D-范畴中得到合理的解释。这种解释是由归纳而不是推导来定义的。变量解释使用的理解和依赖产品使用的权利附加削弱。使用依赖类型理论的元理论结果表明,判断的解释是独立于其推导。定理4.4给定一个D-范畴E:Bop→Cat,在上述解释[[]]以下事实成立。(i) 假设上下文。 B中的一个对象;(ii) 假设Γ A型。 故[[r] A Type]是E([[r]])中的一个对象;(iii) 假设Γ M:A. 则[[Γ M:A]]是E([[Γ]])中从1到[[A]]的态射;(iv) 假设Δ r =Δ。 则[[Γ]]=[[Δ]];(v) 假设rA = B。 则[[ΓA型]] = [[ΓB型]];(vi) 假设rM = N:A。 然后[[ΓM:A]] = [[ΓN:A]]。D-范畴也是完备的,这可以通过通常的项模型构造来证明。诉de Paiva,E.Ritter/Electronic Notes in Theoretical Computer Science 323(2016)143153定理4.5如果[[ΓM:A]] = [[ΓN:A]],其中[[ ]]是上面定义的解释,对于每个D-范畴E:Bop→ Cat和对每一个导序列Γ <$M:A和Γ <$N:A,则我们可以在类型论中导出Γ <$M = N:A.这两个定理都是在[27]中为构造演算(这是依赖型理论的一个特例)所陈述和证明的。这个证明是模块化的,专门研究一般依赖类型理论的可靠性和完备性。此外,证明也专门用于非依赖类型论的情况,唯一的修改是坚持函子E(f)是B的对象上的恒等式。4.2添加必要性模态当我们想给依赖类型添加框模态时,我们可以使用D-范畴的基本思想,但是现在上下文有两个部分(模态上下文和直觉上下文),它们的行为非常不同。基本的直觉是 [23]中的建模,其中基本类别B将仅具有模态变量的术语建模为态射,并将模态上下文视为对象。物体上的纤维|具有直觉变量和模态变量的Δ模型项,其中模态变量包含在由Γ建模的模态上下文中。模态变量的替换通过应用函子E(f)来建模,模态上下文的上下文扩展通过理解来建模,该理解现在产生B中的态射f:Γ·A与由B中的态射f:Γ→ ΓJ和E(Γ)中的态射g:Δ→A组成的对之间的双射这使我们得出以下完整的定义:定义4.6固定DML范畴是索引范畴E:Bop→Cat,使得(i) B有一个终端对象T;(ii) 所有纤维都是Carnival闭范畴,并且E(f)对B中的每个态射f保持鼻上(iii) 每个函子E(f)是对象上的单位元(iv) 函子I:B →Gr(E)定义为I(Γ)=(Γ,1)和I(f)=(f,Id)有一个右伴随G。对于G((Γ,A)),我们记为Γ·A,对于这个伴随的余单位,记为(Fst,Snd)(v) F或B的 所有b ∈Γ,函子Fst∈A:E(Γ)→E(Γ·A)有一个与QA相 连 的 函 数. 若f:B→Fst<$AC是E(Γ·A)中的态射,则记νA(f)为E(Γ)中的态射,该态射是通过将f转置到附加函数上而得到的。(vi) 此外,在严格意义上,附加QAEFstA满足Beck-Chevalley条件,即:方程f<$$>QA=QA<$(f·Id)<$f <$(νA(g))=νA((f·Id)<$(g))对任意f:Δ → Γ,B∈ObE(Γ),C∈ObE(Γ),g∈ Hom E(Γ.A)(B,C)成立. 请注意,由于这个框架是为具有依赖类型的理论开发的154诉de Paiva,E.Ritter/Electronic Notes in Theoretical Computer Science 323(2016)143为了使用它来建模没有依赖类型的理论,我们施加了限制,即重新索引是对象的同一性,上面定义中的条件[(iii)]5依赖模态类型理论在为构造模态类型理论定义了一个虚构语义之后,其中所有的类型构造器都是简单类型,我们现在想要拥有模态,它们本身就是依赖产品系统上的依赖类型。这是本文的主要创新之处我们不知道有任何其他的工作描述依赖模态作为我们在这里描述的这些S4必要性模态依赖类型理论有一个混合的记录。一方面被一些人认为是在函数式编程本身中,依赖类型以两种非常不同的方式使用,正如[10]中所解释的那样:首先是作为构造性逻辑中定理证明的案例研究,如Coq,LEGO,Agda,Lean等,但也作为对现有和普通函数式语言的扩展,如Haskell和ML。在第一种情况下,不终止是被禁止的,因为它会使逻辑不一致;而在第二种情况下,人们寻求一种用于异构验证的语言,尽可能地表达,允许程序员将他们的“验证预算”投入这样的语言必须像任何函数式编程语言一样原生地支持一般递归,因此非终止性不是问题。在本文中,我们明确地处于第一个阵营,并想看看在依赖类型论域中允许模态的内涵概念(特别是必要性或Q-like S4模态)的类型系统的数学基础是什么。在这样的宇宙中,模态本身作为依赖类型构造函数更有意义类型论的形式发展与非依赖情形是平行的相关模态类型理论的原始表达式由下式给出:t::= x M|X I|λx:A.t |TT |Q(t,t)|设t是Q(x M,x I),在t中其中x(变量上的标签有时会被省略,以增加可读性。依赖模态类型理论的类型判断如图3所示。我们省略了上下文、类型和术语的一致性规则。需要注意的重要一点是,考虑到我们在双上下文方面对框模态的表述,将框推广到依赖构造函数成为一个简单的步骤,在语义上,有点让人想起如何处理传统Martin-Léofde p nty petheor y中的强和。注意,非依赖乘积,即通常的函数空间或逻辑隐式,诉de Paiva,E.Ritter/Electronic Notes in Theoretical Computer Science 323(2016)143155Γ上下文ΓA类型[]X上下文Γ,x:一个X上下文ΓA型ΓB型Γ,xM:A<$B型Γ,xM:A<$B型ΓA→B型ΓxM:AB类型ΓQxM:AB类型r,x:A,r J| Δ λ x M:AΓ |Δ,x I:A,Δ j x I:AΓ |Δ,x I:A Δ t:BΓ |Δ λx I:A.t:A →B(→I)Γ |Δ Δt:A→BΓ |Δ u:AΓ |Δ Tu:B(→E)r,x M:A|Δt:BΓ |Δ λx M:A.t:λ x:AB(I)Γ |Δ Δt:Δ x:AB Γ| 阿鲁:AΓ |Δ Tu:B [u/x M](英)Γ|:A |Δ εs:B [t/x M] Γ |ΔQ(t,s):QxM:AB(QI)Γ |Δ T:QxM:ABr,x:A| Δ,y:Bu:CΓ|令t为u:C中的Q(x,y)r,x:A| Δ Δt:B Γ| u:AΓ |Δ Δt:Δ x:AB(x/∈FV(t))Γ |Δ(λx:A.t)u = t [u/x]:B[u/x]Γ |Δ,x:A,t:B,r |Δ τu:Aτ |Δ τ(λx:A.t)u = t[u/x]:BΓ |Δ λx:A.tx = t:λ x:ABΓ |Δτt:A → B(x/∈ FV(t))Γ |Δ λx:A.tx = t:A→ BΓ| :A |Δ T:B [t/x M] r,x:A| Δ,y:BCΓ|设Q(t,s)为Q(x,y),u = u [t/x,s/y]:CΓ |Δ T:Qx:ABΓ |Δ,y:Qx:ABtJ:CΓ|令t为Q(x,a),其中tJ [Q(x,a)/y] = tJ [t/y]图三. 依赖DIML的类型判断(depDIML)是可派生的。 depDIML的约简规则如预期的那样(λxM:A.t)ut[u/xM]156诉de Paiva,E.Ritter/Electronic Notes in Theoretical Computer Science 323(2016)143(λxI:A.t)ut[u/xI]设Q(t,u)为Q(x,y),s∈s[t/x,u/y]诉de Paiva,E.Ritter/Electronic Notes in Theoretical Computer Science 323(2016)143157然而,依赖类型理论的元理论通常非常微妙。特别是主体归约成为一个重要的定理。幸运的是,我们可以使用相同的方法来证明标准依赖类型理论的这些定理。和前面一样,我们有两种替换引理:引理5.1(depDIML替换)如果Γ |Δ Δt:A和Γ |x I:A,Δ εs:B,则为Γ|ΔΔs[t/xI]:B,其中re[t/xI]表示t-矩阵元级替换。类似地,如果|−T:A和T,xM:A|Δ εs:B然后是Γ |Δ εs [t/x M]:B.引理5.2(depDIML主语归约)如果存在依赖DIML类型判断Γ |A和a重写t<$tJ,则还有一个类型判断Γ |Δ ΔtJ:A.定理5.3依赖DIML约化关系是强正规的和连续的。6依赖Fibrational语义开始时所做的艰苦工作现在有了回报。在第4节中给出的框架可以用来建模依赖DIML类型理论,只要去除重索引是对象的标识的限制定义6.1A 菲布雷德 依赖 DIML-范畴 是 一个 索引范畴E:Bop→Cat,(i) B有一个终端对象T;(ii) 所有纤维都是Carnival闭范畴,并且E(f)对B中的每个态射f保持鼻上(iii) 函子I:B →Gr(E)定义为I(Γ)=(Γ,1)和I(f)=(f,Id)有一个右伴随G。我们将G((Γ,A))写成Γ·A,(Fst,Snd)表示这个附加函数的余单位,(f,g)表示通过将(f,g)转置到这个附加函数上而得到的态射对(iv) 对于E(Γ)中B和A的任意对象Γ,函子FstA∈:E(Γ)→E(Γ·A)有一个右伴随函子Fst A:E(Γ·A)→E(Γ).在续篇中,我们将写HomE (Γ·A)(Fst_A(B),C)与HomE(Γ)(B,Fst_A(C))之间的自然同构Cur,以及它的对偶App.(v) 严格 意义上满足映 射 Fst<$AE<$A 的 Be ck-Che valley 条 件 , 即 方 程f<$ ( CurA(h))= CurA((f·Id) <$(h))对任意f:Δ → Γ,A∈E(Γ),B∈E(Γ·A)和态射h:1·B在E(Γ·A)中成立.(vi) 对于B的所有函子Γ,函子Fst∈A:E(Γ)→E(Γ·A)有一个与QA相连的函数。若f:B→Fst<$AC是E(Γ.A)中的态射,则记νA(f)为E(Γ)中的态射,该态射是通过将f转置到附加函数上而得到的。(vii) 此外,在严格意义上,附加QAEFstA满足Beck-Chevalley条件,即:方程f<$$>QA=QA<$(f·Id)<$f <$(νA(g))=νA((f·Id)<$(g))158诉de Paiva,E.Ritter/Electronic Notes in Theoretical Computer Science 323(2016)143一对任意f:Δ→ Γ,B∈ObE(Γ),C∈ObE(Γ),g∈HomE(Γ.A)(B,C)成立模态变量将通过理解变量和直觉变量在纤维中的适当投影来解释。 类型A→B解释为:在相应的纤维中的函数空间,以及由右伴随弱化的依赖乘积。Q-模态被解释为左伴随弱化。更确切地说,Q-模态的分句如下:[[r |A]]= f [[r |Δ ε s:B]]= g[[r |Δ <$Q(t,s)]]= pair(Id,f)<$(ν−1(Id)<$g)[[r |Δ τt:Qx:AB]]= f [[Γ,x:A| Δ,y:B[t:C]]=g[[r |Δ let t be Q(x,y)in s]]= ν−1(g)f,Id使用这个定义和与以前相同的证明方法,我们现在可以陈述我们的分类模型的可靠性和完备性可靠性证明使用替换引理。引理6.2(i)假设[[r |A]]= f. 然后我们有(i) 如果Γ,x:A,Γ J| Δ n上下文,则[[r,r J [s/x]| Δ[s/x]_Context]] =(_Id,f_.Id)n [[r,x:A,r]|[A].(ii) 如果Γ,x:A,Γ J| ΔB型,则[[Γ,Γ J [s/x]| Δ[s/x]<$B [s/x] Type]] =(f_Id,f_Id)<$[[Γ,x:A,Γ J| Δ λB型]]。(iii) 如果Γ,x:A,Γ J| Δt:B,则[[Γ,Γ J [s/x]| Δ[s/x] Δs [tx]:B [s/x] =(Δ Id,fλ·Id)n [[r,x:A,r]|Δ t:B]]。(ii) 假设[[Γ| Δε s:A]]= f. 我们有[]| ΔΔ t [s/y]:B]]=[[Γ| Δ,y:A[t:B]][t:B]]定理6.3给定一个依赖于DML-范畴E:Bop→Cat,在上述解释[[]]下,下列事实成立。(i) 假设Γ| A.背景。 然后,[]|[[]]是E([[Γ]])中的一个对象;(ii) 假设Γ A型。 故[[r] A Type]是E([[r]])中的一个对象;(iii) 假设Γ|Δ t:A. [2019 - 03 - 15 00:00:00][ 2 0 1 9 - 0 1 : 0 0 ] [ 2 0 1 9 -0 1 : 0 0 ]int n(n);(iv) 假设|Δ = ΓJ| ΔJ。 然后,[]| Δ]] =[[Γ J| ΔJ]];(v) 假设rA = B。 则[[ΓA型]] = [[ΓB型]];(vi) 假设Γ| Δt = s:A. 然后,[]| Δ Δt:A]] = [[Γ| Δ εs:A]]。证据使用替换引理6.2,通过对所有判断的推导进行同步归纳来进行证明。Q定理6.4如果[r|其中,[[ ]]是上面定义的解释,对于每个依赖DML-范畴E:Bop→Cat和对于每个导出序列Γ |Δ Δt:A和Γ|那么我们可以在类型论中推导出|Δt =s:A.诉de Paiva,E.Ritter/Electronic Notes in Theoretical Computer Science 323(2016)143159证据证明过程中,从一个依赖的DIML理论构建一个长期的模型。由于在句法模型中对这个依赖的DML理论的解释是恒等式,所以完整性紧随其后。Q这个框架也支持将外延恒等式类型作为对角线的左伴随。然而,相应的类型理论的精确表述是相当微妙的,将留给进一步的工作。最近由于同伦类型理论的单价基础计划[30],从更基础的角度重新对DT
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 5
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- 李兴华Java基础教程:从入门到精通
- U盘与硬盘启动安装教程:从菜鸟到专家
- C++面试宝典:动态内存管理与继承解析
- C++ STL源码深度解析:专家级剖析与关键技术
- C/C++调用DOS命令实战指南
- 神经网络补偿的多传感器航迹融合技术
- GIS中的大地坐标系与椭球体解析
- 海思Hi3515 H.264编解码处理器用户手册
- Oracle基础练习题与解答
- 谷歌地球3D建筑筛选新流程详解
- CFO与CIO携手:数据管理与企业增值的战略
- Eclipse IDE基础教程:从入门到精通
- Shell脚本专家宝典:全面学习与资源指南
- Tomcat安装指南:附带JDK配置步骤
- NA3003A电子水准仪数据格式解析与转换研究
- 自动化专业英语词汇精华:必备术语集锦
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功