没有合适的资源?快使用搜索试试~ 我知道了~
理论计算机科学电子笔记158(2006)261-287www.elsevier.com/locate/entcs全局搜索的单子和伴随保罗·布莱恩·利维1英国伯明翰大学计算机科学学院伯明翰B15 2TT摘要在本文中,我们看看两个分类帐户的计算效应(强monad作为一元语言的模型,adjunction作为一个模型的调用推值与堆栈),我们适应他们纳入全球异常。 在每种情况下,我们扩展了微积分的结构,由于本顿和肯尼迪,融合异常处理与排序。这立即给了我们一个方程理论,只是通过调整方程的顺序。我们研究了两个等式理论的范畴语义。在单子元语言的情况下,我们看到支持例外的单子是某个共单子的余代数。我们进一步表明,使用贝克在堆栈的按推值调用(CBPV)的情况下,我们推广了CBPV附加的概念,以便等待值的堆栈可以处理返回的值和引发的异常。 我们看到了如何从CBPV附加函数中获得异常模型,反之亦然,通过限制那些在异常引发方面是同态的堆栈。关键词:异常处理,单子,附加,余单子,余代数,推值调用,贝克定理1介绍1.1Monads for在一篇开创性的论文[19]中,莫吉汇集了一系列被称为计算效应的命令式行为,包括发散、非确定性、存储和异常。本文是一项研究1电子邮件地址:pbl@cs.bham.ac.uk1571-0661 © 2006由Elsevier B. V.出版,CC BY-NC-ND许可下开放获取。doi:10.1016/j.entcs.2006.04.014262P.B. Levy/Electronic Notes in Theoretical Computer Science 158(2006)261s∈S有一个态射。的t0Ci∈Io最后一个例子。为了精确起见,让我们区分例外效应的一些• 有些语言,如Java,区分错误和异常。前者不能被捕获:当引发错误时,执行立即终止。相反,异常可以被捕获(也就是处理)。• 一些语言,如ML,允许动态生成新的异常名称,这在[8]中使用游戏进行建模。但在本文中,我们只研究全球例外。在对效果的研究中,研究了各种演算,包括计算λ演算[18],一元语言[19],细粒度按值调用[12],按推值调用(CBPV)[11],带堆栈的CBPV [14]。作为这些演算的模型,人们研究了各种各样的范畴结构,包括强单子[19]、Freyd范畴[16]、κ-范畴[16]、CBPV范畴[14]。上述演算都不包含特定对象的构造;必须将这些范畴结构也是如此。以强单子为例。文[21]对各种结果的分析,使C上的强单子T应具有的加法结构2• 为了模拟双随机不确定性,T应具有满足交换性、结合性和幂等性方程的态射1或T• 为地面存储单元建模,其中S是可数元素集可以被存储,T应该配备一个态射1查找T1和S∈S1T1是一个等价于Sgivenin[21]的方程;类似地更新几个细胞。• 为打印建模,其中A是可被打印,T应该配备一个态射<$c∈A1打印T1。• 为了对错误的产生进行建模,其中E是错误的可数集,T应该1错误e∈E• 为了对I/O建模,其中O是请求输入的消息的可数集,并且消息o∈O请求来自可数集Io的输入,monadT应该配备一个态射输入电压1,每个o∈ O。(这是前面两个例子的总结。如果Io是单例的,那么o就是一个打印字符。如果Io为空,则o为错误消息。)[2]我们假设范畴有一个合适类型的可数余积。下面(定义式2.1)我们精确地陈述这个假设。1P.B. Levy/Electronic Notes in Theoretical Computer Science 158(2006)261263−−→所有这些结果都是在[21,22]中发展的一般理论的实例。这个理论涉及到代数运算的概念,也就是关于项的运算θ,使得θ{Mi}i∈I到x。N = θ{Mi到x。 N}i∈I其中,I是θ的(可数)数,to表示排序。相反,正如[22]中所解释的,异常处理不是代数运算。那么,我们如何在一元元语言中添加例外呢?应该强加什么样的等式,以及由此产生的范畴结构是什么这些问题将在本文的第一部分(第2我们将看到范畴结构实际上是某个余单子的余代数一个用于异常的单子的大类由单子Transformer给出,它将单子T转换为T(+E)[4]。令人惊讶的是,我们将证明每个例外单子(在一个有均衡器的范畴上)都是这种形式。1.2添加剂用于CBPV是一个细粒度的演算,包括按值调用和按名称调用作为片段[11,13]。在[14]中表明,当我们用堆栈判断(又名评估上下文)扩展CBPV时,其范畴语义由一个附加项给出。作为一个例子,定义一个E-集合为一个集合X,它配备了一个函数EX.然后,集合范畴与E-集合范畴的结合给出了一个错误模型栈表示第二类的态射,在这个例子中是E-集同态.直觉,一个评估上下文,应用于一个引发错误的术语,给出一个引发错误的术语正如[14]中所指出的,这个理论不能解释异常处理。涉及处理程序的堆栈可能以非同态方式处理错误。这里的问题比1.1节中的更严重,因为异常处理实际上使CBPV的一些等式定律与堆栈失效。(在[9]中也注意到了类似的现象:异常处理使一些延续的标准法则失效。那么什么是适当的等式理论,以及由此产生的范畴结构是什么?这些问题将在本文件第二部分(第二节)中回答61.3将处理与排序相我们的两个问题都依赖于找到一组合理的方程来提出和处理异常。使用常规语法进行处理,264P.B. Levy/Electronic Notes in Theoretical Computer Science 158(2006)261B一►/∈看起来有点困难。但在[2]中,为句柄排序引入了一种新的语法:M {\displaystyle X}。N,抓住X。 NJ}这意味着:首先评估M。如果它返回一个值,则将x绑定到该值并计算N。另一方面,如果它引发异常,则将x绑定到该异常并计算NJ。在[2]中讨论了这种语法的许多优点-在存在sum类型的情况下,它与传统语法是等价的。但对我们有用的是,它与普通测序非常相似。所以我们需要做的就是把标准的排序方程,用它们来适应这个结构。这给出了我们正在考虑的两种演算的一个优雅的理论:一元元语言和带堆栈的CBPV。1.4理论与范畴结构在本文的过程中,我们提出了各种方程理论和各种范畴结构。我们将这些与主张理论和结构之间的“对应”的结果联系起来。这就断言了理论范畴(其中一个理论由一个签名和由签名生成的同余组成)与结构范畴看到例如,[14]在CBPV豁免的特定情况下,对于这种等效性的精确陈述;这种陈述很容易适用于其他情况。正如那里所解释的,A和B中的态射都需要保持鼻子上的结构;这是一个在范畴语义学中普遍存在的规则,其纠正留给未来的工作。2一元语言一元元语言,有有限的产品和总和类型,如图所示。1,以及引发异常的语法在这里,pm表示“模式匹配”,我们使用to进行排序。因为1的规则类似于×的规则,所以我们省略它们。在整个论文中,所有涉及测序的结构和方程都被标记为“0”,因为它们是当我们在语言中加入双排序时,需要进行调整方程理论如图2所示。我们省略了使每个方程类型良好所必需的假设。 给定一个项ΓM:B,我们写xM对于上下文中的弱化项,其中A是某个合适的类型.这意味着x不在Γ中,因为上下文中的标识符必须是不同的。因此,我们证明了对传统xFV(M)条件的需要。P.B. Levy/Electronic Notes in Theoretical Computer Science 158(2006)261265Σ类型A:: =i∈IAi|1 |A×A| A ~A(无限)Γ<$x:A(x:A)∈ΓM:A返回M:TAΓ►M:AˆıΓ,M:i∈IAirM:ArMJ:AJΓM,Mj:A×AJΓ,x:AM:TBΓλx.M:A ~ BrM:TAr,x:AN:TBrM到x。N:结核病Γ<$M:i∈IAiΓ,x:Ai<$Ni:B(<$i∈I)Γ<$pmMas{<$i,x<$.Ni}i∈IrM:A×AJr,x:A,y:AJ<$N:BrpmMasx,y。N:BrM:A ~BrN:ArMN:TBFig. 1. 一元语言与异常引发排序法则(return M)到x。 N = N [M/x]M = M到x。returnxM到X。N)到y。P = M到x。(N到Y。β定律pm,Mas{i,x.Ni}i∈I=N[M/x]pm<$M,MJ<$as<$x,y<$.N=N[M/x,M J/y](λx.M)N=M[N/x]xP)η-定律N [M/z] =pmMas{\displaystyle\pi,x\pi}。xN[i,x/z]}i∈IN [M/z] =pmMasx,y。xyN[x,yx/z]M= λx。(xMx)图二.一元语言ˆı∈I♣266P.B. Levy/Electronic Notes in Theoretical Computer Science 158(2006)261C我我我为了解释和类型,我们从[3,5]中改编了以下内容定义2.1设是一个范畴,即一个有区别的终端对象和区别的二元产品的范畴。(i) C-对象族{Ai}i∈I的分配余积是余锥(V,{Ai在i V}i∈I),使得对于每个C-对象X,cocone(X×V,{X × A X×iniX× V} ∈)是余积。(ii) 分配(Resp.)可数分配的)范畴是一个有分配余积的范畴,对于每个有限元(分别为),它都有一个分配可数的)对象的族(iii) 设T是C上的强单子。• T有Kleisli指数,当它对每对C-对象A,B,都有一个函子C(−×A,TB)的表示对象:opC −→设置。• T具有可数的Kleisli指数积,当它被装备时,对每一个可数族的C-对象对{(Ai,Bi)}i∈I,op表示函子i∈IC(−×Ai,TBi)的对象:C−→ Set。(This显然意味着T有Kleisli指数。)命题2.2存在理论/模型的对应关系(见第二节)。1.4)between• 一元语言• 一个分配范畴,连同一个强单子与Kleisli指数。注释2.3元语言的无穷变体可以通过将可数和类型以及函数类型和可数乘积类型的融合以[15]的风格包含到微积分中来形成然后,在• 无限一元语言理论• 一个可数分配范畴,以及一个强单子与可数产品的克莱斯利指数。3例外3.1提高效率我们首先处理异常的引发,这需要一个额外的类型exn,如图3.1所示。在[20]的意义上,异常引发是一种代数现象,因此它的语义非常简单--不像P.B. Levy/Electronic Notes in Theoretical Computer Science 158(2006)261267Σ类型有A::=i∈IAi|1 |A×A| A~A |exn(I finite)异常引发提高是代数联系我们升BM:TB(将M提升)为x。N =升高M图三. 一元语言异常处理实际上,raise的语义是由计算x:exn的语义确定的,因为raiseBV=(raise0x)[V/x]toy。赖斯湾这是一个一般结果的实例[22]:代数运算对应于泛型元素。我们相应地定义一个语义结构:定义3.1设C是分配范畴,E是C的对象。支持E-提升的强单子是C上的强单子T和从E到T0的CThe “monad constructor for exceptions” [定义3.2设C是分配范畴,有一个对象E。设T是C上的强单子。我们把TE定义为强单子T(−+E)。注意,如果T具有Kleisli指数(分别为Kleisli指数的可数乘积),则TE也是如此。命题3.3在以下两点之间存在理论-模型对应关系(1.4节):• 一元语言例外提升理论• 一个分配范畴C,具有区别对象E和C上的强单子,具有Kleisli指数,支持E-提升。3.2异常处理图4显示了获得一元元语言所需的变化。我们定义268P.B. Levy/Electronic Notes in Theoretical Computer Science 158(2006)261♣H.S.C.H.S.raisexparABMtoox. NtobeM去吧。N我抓到x了。N为M到x返回xcatch x. N然后,我们可以证明所有标记的方程(不再需要作为公理),以及一些分类的方程:((M为W。 举起V)抓住x. (N到Y。( 6)我们还可以证明:M{\displaystyle X}。N,到X。NJ}=(M为W。返回inlw)catch y返回inry)到z。pm z为{inlx. N,inrx. NJ}这表明,与普通的处理和排序相比,双排序并没有更多的表达性(在存在和类型的情况下)。这仅仅是句法上的方便。为异常处理提供分类语义需要更复杂的机制,我们现在正在开发这种机制。但就目前而言,请注意,TE总是给出一个模型。4代数上的余代数在这一节中,我们回顾并发展了余代数的一些抽象理论命题4.1设F是一个具有单位η和可数的附加函数,,,- 是的写L为诱导的comonad(FG,F ηG)。(i) 存在从L的分解(A,F,G,η)到co-Eilenberg-Moore分解(到L-余代数范畴中)的唯一比较K。它将一个A-对象X映射到(FX,FηX),并将一个态射XfXJ映射到Ff。(raise V)catch x. M=M[V/x](一)(return V)catch x. M=返回V(二)M=我抓到x了。提高x(三P.B. Levy/Electronic Notes in Theoretical Computer Science 158(2006)261269M=⎩⎭EH.S.C.H.S.Nj到xN{到y。xP,catch y. xPJ}M下面的结构和方程取代了图中标记为“1”1rM:TAr,x:AN:TBr,x:exnNJ:TBrM{to x. N,抓住X。NJ}:TB(returnnM)到xNN=N[M/x](raiseM)到xNn=NJ[M/x]Mcatchx. Nj去吧。 returnn返回catch x. 提高x(M 到xN⎫⎬)⎧⎨ 到Y。P⎫⎬=H.S.C.H.S. 我是一个很好的人。Pj抓住X。 NJ{to y. xP,catch y. xPJ}见图4。 一元语言(ii) 假设A有所有的均衡器,F保持它们。则K有一个右伴随Q(不一定是比较),且K Q的可数是同构。证据这在[1]中得到了证明。K的右伴随将L-余代数(Y,φ)映射到A中的均衡器Gφ公司简介ηGYQ现在假设(T,η,μ)是范畴M上的单子。我们组成了⎨270P.B. Levy/Electronic Notes in Theoretical Computer Science 158(2006)261,T,......XTX以下两个警告:M,艾伦贝格-穆尔、、 、、、K(T),,,,,,,,,z,M,,.J,,(MT)L(T),,t,这分三步进行共-艾伦伯格-穆尔第一步是形成T的Eilenberg-Moore分辨率(MT,GT,FT,NT)。这在MT上诱导出一个共单子,我们称之为L(T)。解释:• 它将一个对象(X,θ)映射到(TX,μX)• 它将态射(X,θ)f(Y,θJ)映射到(TX,μX)Tf(TY,μY)• 在(X,θ)处的单元是s(TX,μX)θ(X,θ)TηX2• 在(X,θ)处的余乘为(TX,μX)(TX,μTX)。第二步是形成这个comonad的co-Eilenberg-Moore分解解释:• L(T)的余代数是(X,θ,φ),其中(X,θ)是T-代数,(X,θ)φ (TX,μX)是T-代数同态,使得φ、、Xφ TX通勤id,θφTφzJJJXTXTηXT2X• 从(X,θ,φ)到(Y,θJ,φJ)的余代数同态是T-代数同态(X,θ)f(Y,θJ),使得XfY 通勤φ φJ JLXLf LY• 遗忘函子(左伴随)将对象(X,θ,φ)映射到(X,θ)和态射(X,θ,φ)f(Y,θJ,φJ)到f• 自由函子(右伴随)将对象(X,θ)映射到(TX,μX,TηX)和态射P.B. Levy/Electronic Notes in Theoretical Computer Science 158(2006)261271(X,θ)f(Y,θJ)到Tf272P.B. Levy/Electronic Notes in Theoretical Computer Science 158(2006)261不TACCCC、EC、E• (X,θ,φ)的单位是φ。第三步是从我们的第一个分辨率L(T)到co-Eilenberg-Moore分辨率的唯一比较,这是终端。它是从M到余代数范畴的函子,映射• 一个物体X到(TX,μX,TηX)• 一个态射XfY到Tf。 我们称这种比较为K(T)。命题4.2设(T,η,μ)是范畴M上的单子。假设M有所有的均衡器,T保持它们。则K(T)有一个右伴随Q,且K ∈ Q的余是一个同构.证据由于保持均衡器,自由代数函子FT也必须这样做。 然后,我们应用Prop。4.1㈡.Q5Monad模型5.1一般单子设C是一个分配范畴,E是它的一个对象,我们定义MC是C上的强单子范畴。我们首先回顾[7]中提到的以下结果。命题5.1设T是C上的强单子。 那么TE是下式的余积TinlA,ET和−+E。在A处由T(A+E)给出注入TTE。η(A+E)注入离子−+ETE在A处由A+ET(A+E)给出。现在,一般地,如果E是范畴M的对象,使得每个M-对象U都有与E的余积,则U<$→U+E给出M上的单子。特别地,我们得到一个单子TC,E,它把T映射到TE。它在T处的单位将X映射到TXTin IT(X+E)。在T处的乘法将X映射为T[id,inr]T((X+E)+E)T(X+E)此外,让我们写Mkl(resp.Mωkl)的全子范畴MC由具有Kleisli指数的强单子组成(分别为Kleisli指数的可数乘积然后TC,E限制到Mkl上的单子(resp.在Mωkl上),虽然强单子−+EC可能缺少克莱斯利指数我们称之为限制单子Tkl (分别)Tωkl)。我们现在可以给出我们的主要定义。P.B. Levy/Electronic Notes in Theoretical Computer Science 158(2006)261273C、ECCC+E定义5.2·支持C上的E-例外的强单子是L(TC,E)的一个组合代数。• 一个强单子与Kleisli指数(分别)。 是L(Tkl)的余代数(分别) L(Tωkl))。让我们解开这个定义。C、E首先,TC,E单子的代数恰好是一个强单子T,具有从−+E到T的强单子态射,这样的强单子态射对应于C-态射E提升T0(根据代数运算的一般理论[22])。因此,一个代数是支持E-提升的强单子.代数结构θ在X处由下式给出:T(X + E)T[ηX,(raise;T[])] T2XμXTX诱导余单子的余代数由一个强单子T和一个态射TXeXT(X+E)组成,T支持E -提升,T是强单子同态的,T是X中的自然态射X,,CccηXcccccccCcCTXeX、、、X,E中的η、、,zzT(X+E)T2Xe2XT(T(X+E)+E)T([id,ηinrX,E])μXT2(XJ)的方式μ(X+E)JT(XJ)TXeX+ETX×Y(eX)×YT(X+E)×YtX+E,YJtX,YJT(X×Y)(eX×T((X+E)×Y)JT(X×Y+E)、Y)的274P.B. Levy/Electronic Notes in Theoretical Computer Science 158(2006)261是TC,E-代数同态T(X+E)eX+ET((X+E)+E)(七)θXT[id,inrX+E,E]JT(XJ)TXex+E并且是余代数的TXeX T(X+E)、、,θXid,,zJTXTXeXT(X+E)eX e(X+E)J JT(X + E)TinlX+E,E T((X+E)+E)命题5.3条件(7)在所有其他方程存在的情况下等价于条件E,提高T0、、ηinr,e00,E z JT(0 +E)5.2元的单子语义上面的结构正是我们解释处理所需要的。对于给定的项T,M:TA和T,x:A,N:TB和T,x:exn,N,J:TB,项M{tox. N,抓住X。NJ}表示复合物[[r]]id,[[M][[r]]×T[[A]][[r]]×e[[A]][[r]]×T([[A]]+E)tT([[r]]×([[A]]+E)e)T [N]],[[N]]JT[[B]]然后很容易看出,图2中的所有方程定律都是有效的。反过来,我们也可以用handling的语法构造这样一个余代数. 我们定义eA为项的同余类,x:TA = x{to y. 回来,抓住你。 return inr y}:T(A + E)P.B. Levy/Electronic Notes in Theoretical Computer Science 158(2006)261275C、EC、EJ并且所有所需的交换性图都遵循定律。这两个方向使我们能够证明:命题5.4理论/模型对应(1.4节)• 有例外的一元语言理论• 一个分配范畴C,一个杰出的对象E,和一个强大的单子,克莱斯利指数,支持E-例外。5.3比较函数现在让我们解包在第二节中定义的比较函子K(TC,E)四、它将C上的一个强单子T映射到单子TE,因此它正是例外单子Transformer。命题5.5设E是分配范畴C的对象。假设C有均衡器。 则函子K(T C,E)和K(Tkl和K(Tωkl),有一个右伴随,并且在每一种情况下,该伴随的可数是同构。证据 我们必须检查道具的条件。4.2满意了给定一个强单子αTTβ逐点计算均衡器SγTKleisli指数只是T和TJ的Kleisli指数的均衡器,对于Kleisli指数的可数乘积也是如此。 TC,E的保存是微不足道的。Q推论5.6设T是C上支持E-例外的强单子. 如果C有e个量化器,则T=TEJ 对于C上的某个长单子TJ,指数(分别为Kleisli指数的可数乘积),如果T具有他们我们注意到,TJ可能不是唯一的同构。例如,设C为Set,设E为1,设TJ为单子(−→0)→0,设TJJ为单位单子(将每个都映射到1)。ThenTEJJ(它们是单位单子),但TJ0≠TJ0。和TEJ是同构的我们现在已经描述了Set上所有的单子,它们对异常进行建模并验证了Fig.1的定律二、接下来我们来看一些非实例。下面是Set上的两个monad,支持E-raising,但一般不支持E(i)[6]单子映射X到S→((S×X)+E),其中S是某个集合276P.B. Levy/Electronic Notes in Theoretical Computer Science 158(2006)261Σ∈(ii) 单子映射X到(S×((S×X)→R))→R,其中R是某个集合,S是E→R。第二个例子是由Andrzej Filinski和Hayo Thielecke [个人交流]独立提供的,作为NJ-SML提供的捕获和逃逸在每种情况下,都有一个候选的解释用于测序。分别用T,x:A,N,TB和T,x:exn,N,J:TB表示。然后,我们定义[[[M]为x。N,抓住X。NJ}]]来映射ρ∈ [[Γ]]到(i) 函数映射s∈S到• ([[N]](ρ,x<$→b))sJ如果([[M]]ρ)s=inl(sJ,b)• ([[NJ]](ρ,x<$→e))s如果([[M]]ρ)s=inre.(ii) 函数映射s∈S和k∈(S×[[B]])→R到([[M]] ρ)((λe. (([[NJ]] p)(s,k),(λ(sJ,b). (([[N]]ρ)(sJ,k)推论5.6表明,这些解释(一般来说)并不能证实图4中的方程。这可以直接检查:(i)打破方程(5),以及(ii)打破(3)。 Filinski还证明了[个人交流],(3)作为一种观察等价,被捕获和逃逸打破。可以得出两个备选结论• 这些monad不适合建模异常,它们所建模的构造(如catch和escape)也不自然• 图中的定律四是要求过高,一般例外6使用堆栈的按推值有例外的一元元语言模型仍然是一元元语言模型,尽管有额外的结构。相比之下,在我们现在转向的带有堆栈的CBPV的情况下,添加异常需要一个真正不同的结构。我们首先审查CBPV。我们的账户是针对有限CBPV的;对于有限版本,将“可数”替换CBPV有两类不相交的术语:值和计算。它同样有两个不相交的类型类:值有一个值类型,而计算有一个计算类型。为了清楚起见,我们在计算类型下面加了下划线。类型由下式给出:值类型A::=U B|iIAi|1 |A× A计算类型B::= FA|i∈IBi | A → BP.B. Levy/Electronic Notes in Theoretical Computer Science 158(2006)261277►►►CC|►路上了 U和F遵循Eilenberg-Moore附加,而表示乘积代数和指数代数。i∈I,且其中,我可以是任何可数集(finite,in finitary CBPV)。F和U的含义如下。FA类型的计算产生A类型的值。类型UB的值是类型B的计算的形实转换器,即,计算被冻结成一个值,以便它可以被传递。当以后需要时,可以强制执行,即。处决了被作为一个例子模型,假设我们有一个单子T上的一个carbohydrate封闭范畴C与可数的余积和产品。然后每个值类型表示一个C对象,每个计算类型表示一个T代数,与按值调用一样,CBPV中的标识符只能绑定到一个值,因此它必须具有值类型。因此,我们将上下文Γ定义为序列x0:A0,.,xn−1:An−1具有相关值类型的不同标识符。我们写ΓvV:A表示V是类型A的值,我们写ΓcM:B表示M 是B型计算。在单子语义中,值ΓvV:A表示从[[Γ]]到[[A]]]的C-态射,并且计算Γ M:B表示从[[Γ]]到[[[B]的载体的-态射。CBPV的各项如图所示五、符号第三个判断是ΓBkK:C。这来自[14]的CK机器,并且意味着K是C类型的堆栈或求值上下文,具有B类型的孔。本文不讨论CK-机,而是给出栈的类型规则。对于单子语义,给定C上的强单子T,我们定义C-对象X上T-代数(Y,θ)到T-代数(Z,φ)的同态为C-态射X×YfZ满足X×TYt(X,Y)T(X×Y) TfTZX×θφJJX×YfZ一个堆栈|BkK:C则表示[[Γ]]上从[[[B]]到[[C]]的同态。复值是实现理论/模型对应所需的纯CBPV的扩展,尽管它们使操作语义复杂化。在[10]中证明了这种扩张在计算上是保守的。278P.B. Levy/Electronic Notes in Theoretical Computer Science 158(2006)261Σ∈Σ►►当{i,x<$.Mi}i∈I:B时,类型值类型A::=U B|iIAi|1 |A× A计算类型B::=FA|i∈IBi | A → B值和计算r,x:A,rJvx:AV:A返回V:FAT-100M:BΓ ►vthunkM:UBV:AΓ,x:AcM:B令V为x。M:BrcM:FAr,x:AcN:BrcM到x。N:BV:UB力V:BvV:A Σˆı∈IIvV:i∈IAiΓ,x:Ai<$cMi:B(<$i∈I)ΓvV:AΓvVJ:AJΓvV,Vj:A×AJrvV:A×AJr,x:A,y:AJcM:BV作为X,Y,M:BΓcMi:Bi(i∈I)i∈IΓcM:i∈II'msorry.I'mB我ˆı∈Iˆır,x:AcM:BΓcλx.M:A→B堆叠Γ|Cknil:CΓ |K:CΓ|i∈IBik::K:CV:AΓcM:A→BVr,x:AcM:Br |BkK:CΓ|法蒂玛 到x M::K:CV:A |BkK:CΓ |A→BkV::K:C图五. 带烟囱Γ►v⟨ˆı,V⟩:i∈IA我Γ<$cλ{i.Mi}i∈I:B我P.B. Levy/Electronic Notes in Theoretical Computer Science 158(2006)261279OXXXJXXX选项。我们可以类似地添加复杂的堆栈,如[14]中所解释的。复杂值和复杂堆栈的语法如图所示六、给定一个计算ΓcM:B和一个堆栈Γ |BkK:C,我们通过在C上拆解K,得到一个计算ΓcM·K:C,这是用K上的归纳法以明显的方式定义的。给定一个堆栈Γ |Bk K:C和Γ |CkL:D,我们可以连接K和Ltogive ver|B=kK++L:D,通过对K的逆归纳来定义。CBPV的方程理论如图所示7、同样的道理,如图2所示),以及图8中的异常引发的附加法则。 这里有一些后果:M·K = M到x。((return x)·xK)M = M到x。return x(M到X。N)·K = M至X。(N·K)(M到X。N)到y。P = M到x。(N到Y。P)λ{i. (M到X。Ni)}i∈I= Mto x. λ{i.Ni}i∈Iλy。(M到X。N)= M到X。λy.N(raiseV)·K =raiseV λ{i. raiseV}i∈I=raiseVλx。升高V=升高V定义6.1设D是一个范畴。右D-模是函子O:D −→集解释一下,• 它为每个A提供了一个“态射”集合A,其中的一个元素被写为G一、• 我们可以创作G 一与H B混合w获得g;hA• 这种组合满足结合性和右恒等律。定义6.2设C是范畴。局部C-索引范畴是严格C-索引范畴D,其中所有这些纤维具有一个对象对象s(obopD),并且所有的重索引函子都是对象上的同一性;等价地,一个[C,Set]丰富范畴。设D是局部C-指标范畴. 一个右D-模由• 对于每个X∈obC和Y∈obD,一个小集合OXY,其中的一个元素,我们调用X到Y上的O-态射,并写为g Y• 对于eachXJkX和gY是Omorphismkg的一个索引Y• 为每个GY和YhYJ 复合O态射g;h YJ280P.B. Levy/Electronic Notes in Theoretical Computer Science 158(2006)261复数值rvV:Ar,x:AvW:B令V为x。W:BΓvV:<$AiΓ,x:Ai<$vWi:B(<$i∈I)i∈I当{i,x.Wi}i∈I:B时,rvV:A×AJr,x:A,y:AjvW:BV为V,V为V,V为V,V为V,W:B复杂堆栈V:A,x.A|BkK:CΓ|设V为x。K:CrvV:Air,x:Ai|BkKi:C(i∈ I)i∈IΓ |BkpmVas{i,x.Ki}i∈I:CΓvV:A × AJΓ,x:A,y:AJ|BkK:CΓ |BkpmVasx,y.K:CΓ |CkK:B |BkL:DΓ |CkK,其中nil是L:DΓ |CkKi:Bi (i ∈ I)Γ |BikL:Di∈IΓ |Ck{Ki其中i::nil}i∈I是L:Dr,x:A|CkK:B |A→BkL:DΓ|其中x::nil是L:D见图6。 复杂值和堆栈
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- 保险服务门店新年工作计划PPT.pptx
- 车辆安全工作计划PPT.pptx
- ipqc工作总结PPT.pptx
- 车间员工上半年工作总结PPT.pptx
- 保险公司员工的工作总结PPT.pptx
- 报价工作总结PPT.pptx
- 冲压车间实习工作总结PPT.pptx
- ktv周工作总结PPT.pptx
- 保育院总务工作计划PPT.pptx
- xx年度现代教育技术工作总结PPT.pptx
- 出纳的年终总结PPT.pptx
- 贝贝班班级工作计划PPT.pptx
- 变电值班员技术个人工作总结PPT.pptx
- 大学生读书活动策划书PPT.pptx
- 财务出纳月工作总结PPT.pptx
- 大学生“三支一扶”服务期满工作总结(2)PPT.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功