没有合适的资源?快使用搜索试试~ 我知道了~
可在www.sciencedirect.com在线获取理论计算机科学电子笔记322(2016)19-34www.elsevier.com/locate/entcs使用名称多态性的增量重新绑定1大卫安科纳a,2保拉贾尼尼b,3埃琳娜祖卡a,4aDIBRIS,意大利Universit`adiGenovabCSInstitute,DISIT,Universit`adelPiemonteOrientale,Alessandria,Italy摘要我们提出了一个扩展名变量的演算增量重新绑定的代码在以前的工作中介绍。名称可以是常量或变量,用作带有自由变量的代码片段的接口。开放代码可以通过应用重新绑定(rebinding)来动态反弹,重新绑定是从名称到术语的关联。 重新绑定是增量的,因为重新绑定也可以包含自由变量,可以由操作员操作,例如重写和重命名。通过使用名称变量,以编写在其名义接口和/或其适应方式中是参数化的术语,从而极大地增强了表达能力。类型系统相应地扩展了受约束的名称多态类型,其中简单的不等式约束防止参数名称接口之间的冲突保留字:开放代码,增量重绑定,名称多态,元编程1引言我们以前的工作[1,2]顺利地集成了简单类型的类演算的静态绑定与代码的动态和增量重新绑定机制要动态反弹的开放代码片段是值。重新绑定是在名义基础上进行的,也就是说,开放代码中的自由变量与不服从α等价的名称此外,重新绑定是增量的,因为重新绑定是名称和术语之间的关联,可以反过来包含要重新绑定的自由变量。重新绑定是第一个类值,可以通过诸如重写和重命名之类的操作符在本文中,我们提出了一个扩展以前的工作,支持,除了名称常量,名称变量,使它能够写在他们的名义接口参数和/或它是适应的方式比如说,1这项工作得到了部分资助2010LHT4KM”。2电子邮件:davide. unige.it3电子邮件:giannini@di.unipmn.it4电子邮件:elena. unige.ithttp://dx.doi.org/10.1016/j.entcs.2016.03.0031571-0661/© 2016作者。出版社:Elsevier B.V.这是一篇基于CC BY-NC-ND许可证的开放获取文章(http://creativecommons.org/licenses/by-nc-nd/4.0/)。20D. Ancona等人/理论计算机科学电子笔记322(2016)19⟨›→›→|⟩⟨›→›→|⟩⟨ ›→|›→›→ ⟩联系 我们|›→›→ ⟩有可能写出对应于模块的我们在下面总结一下语言的特点。• 不受约束的术语,形状为x1X1,., x mX m|t是表示“开放代码”。 也就是说,t可以包含变量x1,...,x m到 通过全局名义接口X1,..., X条纹鲈是使用时,开放代码应与重新绑定X1相结合t1,...,Xmt m。• 重绑定应用是增量式的,即一个未绑定项可以部分重绑定,一个重绑定项可以依次打开。 例如,项x X,y Y x+y可以与重新绑定y Y X y,Z y组合,得到y Y,yJY yJ+y。这使得代码专门化成为可能,类似于部分应用程序为位置绑定实现的功能。• 重新绑定也是第一类值,可以通过诸如重写和重命名之类的操作符进行操作。• 名称X可以是名称常量N或名称变量α,并且名称抽象Λα.t和名称应用t X可以类似于lambda抽象和应用来定义和实例化名称参数项。[2]中的类型系统,支持开放(非精确)和封闭(精确)类型的重新绑定,相应地扩展到处理名称变量。值得注意的是,类型是用形状为α:c.T的受约束的名称多态类型扩展的,其中c是一组名字之间的不等式约束X Y。这种约束是必要的以保证对于α的每个可能的实例化,我们都得到格式良好的项和类型。例如,项Λα:α=N。N:int 0,α:int 1是一个重绑定参数,以其两个组件之一的名称命名,但必须与另一个组件的常量名称N不同。在本文的其余部分,我们首先提供了微积分的非类型化版本的形式定义(第2节),然后是一些展示其表达能力的例子(第3节)。然后,我们定义了一个类型化的微积分(第4节),并给出了一个可靠性结果。我们在第5节中展示了打字示例,最后在结论中我们讨论了相关的和未来的工作。2无类型演算图1给出了无类型演算的语法和归约规则,其中我们留下了原始类型(如整数)的未指定结构,我们将在示例中使用这些结构。我们假设变量x、名称常数N和名称变量α的有限个集合。我们使用X,Y来定义名字的范围,这些名字要么是名字常量,要么是名字变量。我们使用各种序列来表示有限映射:从变量到名称的解绑定映射u,从名称到项的重绑定映射r,从名称到名称的重命名σ,以及从变量到项的替换s我们假设,在这样的序列中,顺序和重复是无关紧要的。此外,在一个术语中,它是一个很好的形式,写得很好,它们实际上表示地图,例如,在X1→›t1,...,如果Xi =Xj则ti= tj。因此,我们可以使用以下符号:dom和rng分别表示定义域和值域,u1<$u2表示地图合成,假设rng(u2)<$dom(u1),(u1,u2)表示两个不相交地图的并D. Ancona等人/理论计算机科学电子笔记322(2016)1921>>> >u12211域,和u1[u2]的地图符合u2无论后者被定义,与u1在其他地方。t::=. |x项|xterm| t1 t2application| t Xname application| t1 t2rebinding operator|! 跑不| t1t2覆盖| σ1t uσ2renaming operatoru::=x1→›r::=X1X1,...,xm→›t 1,...,XmXm解绑映射tm重联图σ::= X1<$→Y1,.,X m›→ Y m重命名X,Y::= N |α名字v::=. |拉乌|t|拉乌|r| Λα.t值|Λ α.tvalueE::= [ ]|......这是什么?|vE| EX| E| E不|vE|!E|评价语境| vE|σ1E uσ2s::=x1t1,...,xm ›→ tm代换(CTX)t−→tJE[t]−→E[tJ](A页) (λx.t)v−→t{x<$→v}(NAME-APP)(Λα.t)N−→t{α<$→N}<$t{α<$→N}(R EB-A PP)|r>u,u |t − → u,u |t {x ≠ → r(u(x))|x ∈dom(u)}<$rng(u2)<$dom(r)=<$(RUN)(OvER)!⟨ |t −→ tu1|r1u2|r2− →u1,u2|r1 [r2](R)σ1αu|r<$σ2−→ <$σ1<$u|rσ2图1:无类型演算:语法和归约规则22D. Ancona等人/理论计算机科学电子笔记322(2016)19⟨|⟩⟨|⟩除了基本类型的抽象和值之外,演算中还出现了三种新的值:未绑定项ut,重绑定项ur和名称抽象Λα.t。D. Ancona等人/理论计算机科学电子笔记322(2016)1923⟨›→|⟩>∅- -∩∅⟨ |⟩联系我们⟨›→|⟩约化为ny<$→N2,yJN2|(y +2)+yJ= 0.非约束项,例如, X Nx+1,表示不直接使用,但,而不是“盒装”,如括号所示。这个装箱的代码可能是开放的,并且可以通过名义接口动态地反弹相反,重新绑定表示可用于动态重新绑定开放代码的代码 重新绑定也可以是未绑定的,也就是说,它的代码可以是开放的,inN→N |N10,N21 +x0. 根据序列表示法,具有空解绑定映射的项被简单地写为t,并且类似地对于重新绑定。名称抽象可用于编写参数化w.r.t.标称接口,例如,Λ α。x α x+1是上述未绑定项的参数版本。注意,与例如,[11],我们采取了一种分层的方法,其中名称不是术语,以保持传统语言的分离,为了简单起见,这里是微积分,从元级别结构,其语义原则上是独立的。因此,我们有专门的名称抽象和名称应用结构除了值和变量之外,术语还包括由以下运算符构造的复合术语它们与图1中给出的归约规则一起说明。Rule(CTX)是通常的上下文闭包。规则(APP)是标准的。对一个项t s的替换的应用是以标准的方式定义的。请注意,在解绑定映射的域中出现的变量的行为类似于λ绑定器。因此,dom(u)中的变量在dom(u)中不是自由的。|不受限制,不受替代。在名称应用程序t X中,t和X被期望分别简化为名称名称抽象应用于名称常量,如规则(N AME-A PP)所建模的。 名称替换,t α N,即用名称常量替换名称变量,以标准方式定义。特别地,唯一引入绑定的构造是名称抽象,而名称替换必须也传播到解绑定映射、重绑定映射和重命名。 请注意,通过名称替换,我们可以获得病态的术语,例如,⟨ |α<$→ 0,N<$→ 1 <${α <$→N}给出| ⟨ |N›→ 0,N›→1个单位。在这种情况下,该规则不能被应用,如由侧条件t {α <$→ N}正式表示的。在t1t2项中,期望重绑定算子t1和t2的自变量分别减少到重绑定项和未绑定项 当重新绑定应用于未绑定项rule(R EB-A PP)时,与重新绑定提供的名称相关联的所有变量(附带条件rng(u2)dom(r)=)都被相应的项替换,因此从未绑定项的未绑定映射中删除。然而,所得到的未绑定项的未绑定映射被重新绑定项的未绑定映射扩充。 条件dom(u)=dom(u2)=,隐含地要求u,u 2的良构性,总是可以通过对两项之一应用适当的α-重命名来满足。我们还默认该规则仅适用于当r(u1(x))对所有x∈dom(u1)有定义时,即rng(u1)∈dom(r)。比如说,N2→N2|N1<$→y +2,N3y> N x <$<$→ N1,y <$→ N2|x +y轴一个学期内!t,则run运算符的参数预计将减少为24D. Ancona等人/理论计算机科学电子笔记322(2016)19⟨|⟩∩∅>预计将采用具有通用形状的重新绑定x r|α1<$→t1,α2t2,.. . 适应,适应未绑定的术语,没有要反弹的名称,可以取消装箱,rule(RUN)。比如,!0+ 1简化为0+ 1,然后可以对其进行评估。未绑定的项可以被“取消装箱”,并且只有在它们的开放代码已经通过一个或多个重新绑定应用程序完成之后才可以通过run操作符执行,这样它们就不包含未绑定的变量;例如,未绑定的项x →N|x+1马达加斯加与重新绑定的服务器一起独立完成|N → 0,N J1 π。在t1t2项中,重写操作符的参数预计将减少到两个重新绑定。规则(OvER)允许合并两个重新绑定,在冲突的情况下优先考虑右边的一个。解绑定映射u1和u2简单地正如规则(R EB-A PP)所发生的那样,隐式条件dom(u1)dom(u2)=总是可以通过应用 一个合适的α-重命名为两项之一比如说,N→N1|N2x 1,N31 mmN→N1|N3<$→ 2,N4<$→x 2约简为→N1,xJ→N1|N2x 1,N3<$$> → 2,N4<$$> →xJ2 <$.在一项σ1tuσ2中,期望重绑定算子的辐角约化为重绑定算子u|当σ 2和σ 1分别是恒等重命名时,我们使用更精确的符号σ1t和tuσ2。 重命名操作符用于分别适应解绑定和重绑定映射u和r的标称接口,规则(R)。使用重命名σ1可以合并名称,而使用σ2可以复制和删除术语;例如(N1→N1,y→N2|N1<$→0,N3<$→1u(N1<$→N1,N2<$→N1)简化为:x →N2,y→N2|N10,N2<$→0 <$。 至于规则(R EB-A PP),我们tac-假定规则(R)仅在rng(u)∈dom(σ1)时适用,且rng(σ)和dom(r2)分别成立。重命名对于适应未绑定术语和重新绑定是必不可少的;重命名和名称抽象有利于动态软件适应和重用。例如,术语t=Λα1。Λα2.λxr. (xru(N1→→α2))>nx1→N1,x2N2|x1x2mm通过重命名它,然后将其应用于未绑定项→ N1,x2→ N2|x1x2mm;例如,t N3N4N|N3λx.x+1,N4<$→ 1 <$在某些步骤中减少到2。3名称抽象在以前的工作[2]中,我们已经分析了构建未绑定项和重新绑定、重新绑定的重写和重命名以及重新绑定应用程序到未绑定项的构造的表达能力这样的结构支持几个编程概念,如动态范围,重新绑定,元编程和基于组件的编程。例如,如果我们假设用let rec构造来扩展calculus来定义递归函数,那么下面的声明定义了一个通过生成式编程支持程序专门化的函数pow:让rec辅助电源=λ; λ如果n >0然后<|y>D. Ancona等人/理论计算机科学电子笔记322(2016)1925Lambda X. !(一)< |X›→ X>>f)>>>>s让权力=λ; λ设f=< | Y›→第1章>> (辅助电源)n)在例如,pow 3的计算结果为把一个x。 !(一)<|X› →x>)。因 此 , pow32 重 写 为 ! ( 一 ) <|X<$→2>),重写为! <|2*2*2*1>,重写为2*2*2*1,最后重写为8。在这里,我们将重点关注新引入的名称操作构造的表达能力,并展示它们如何支持泛型和元编程。模块/组件选择重绑定术语直接支持模块/组件的概念。我们已经展示了[2]如何对封闭(即所有依赖都已解析)模块/组件的成员选择进行编码。例如,下面的项编码了一个操作符,它选择了由重新绑定表示的(封闭)模块的Yts= lambdaX. !(x个< y›→ Y | y>)例如,术语t<|X<$→0,Y <$→42>计算为42。然而,通过这种方式,选择只能被编码为一个固定的名称常量(在这种特定情况下是Y)。通过新引入的名称抽象构造,选择运算符的一般定义可以由微积分的单个项提供t′=λaα。 把一个x。 !(x个这样,相同的项t)可用于选择与以下项相任意的名字 例如,如果t= <|F<$→ λn.n+1,N<$→41>,则(t′sFt)(t′sN t)评价42在主流的面向对象语言中,这种元编程工具要么由特定的库来支持,要么由更灵活的结构来支持,如JavaScript括号表示法。在所有情况下,都不会执行静态检查,以确保所选名称始终在运行时定义例如,使用JavaScript5中的括号表示法,可以定义以下函数:功能select(name,object){ return object[name]}符号e1[e2]允许程序员访问由e1表示的对象的属性,该对象的名称由任意表达式e2定义。因此,select(“val”,{val:42})返回42,而select(“foo”,{val:42})是unfined。正如我们将在第5节中看到的,tetermt′s=λα。 lambdax. !(x)可以静态类型化,以确保只选择已定义的成员。5这里介绍的所有示例都符合ECMAScript 5语法,尽管其中一些示例可以通过使用最近发布的ECMAScript6规范中引入的新功能和简写以稍微简洁的方式编写。26D. Ancona等人/理论计算机科学电子笔记322(2016)19mixins的动态适应Mixin类[3]和mixin模块[4]是泛型编程中常用的概念,用于支持软件重用。在静态类型的主流面向对象编程语言中,mixin仅由C++支持,带有模板,参见[14]。下面的类模板定义了在其基类中是参数化的类Mixin,由模板参数B表示。模板<类B>publicclassB{ public:public intfindDuplicate(intfindDuplicate){ if(intfindDuplicate){returnB:: op(value);扔std:: logic_error(“非法“);}};mixin添加了静态方法checked_op,并且可以使用定义op(int)和in_bounds(int)的类来实例化,如以下代码片段所示:public class Sqrt{静态intint(int)值)的{返回return(value);}staticbool in_bounds(intvalue){ returnvalue>= 0;}};class_sqrt:公共公司简介{}; public voidrun(){send(联系我们::检查操作(4)==2);assert(int_sqrt::op(-4)!= 2) ;assert(Checked_sqrt::checked_op(-4)!= 2);// 我的天 逻辑错误}多亏了由MykedMixin定义的泛型代码,在应用静态方法op之前,类Sqrt用静态方法checked_op扩展,检查参数是否为非负,然后应用静态方法op,反过来,应用库函数6sqrt。使用C++类模板实现的mixin的主要限制是它们无法适应其方法与mixin所施加的名称约定不匹配的类;在AnchokedMixin的情况下,参数基类必须提供静态方法op(int)和in_bounds(int)。此外,C++模板的类型检查不是组合的,因此每次模板实例化时都会检查此类约束。动态语言,如JavaScript [9],允许mixin的动态适应。在这种情况下,mixin由一个函数7定义,它有三个参数,这些参数应该包含字符串:op表示必须检查的操作的名称,in_bounds表示执行检查的操作的名称,new_op表示与op的检查版本相对应的新添加操作的名称。function(x) { this[new_op]= function(x){6函数sqrt不执行任何检查,除非math_errhandling具有常量MATH_ERREXCEPT集7我们记得JavaScript是一种基于原型的语言,对象是通过函数动态创建的,尽管最近ECMAScript 6中引入了一种等效的基于类的表示法。D. Ancona等人/理论计算机科学电子笔记322(2016)1927>如果(!this[in_bounds](x))throw“非法参数“return this[op](x)}}多亏了方括号符号,程序员可以将适当的字符串传递给AnchokedMixin函数,以适应AnchokedMixin的实例。sqrt ={//一个新的对象, 两 属性sqrt:数学.sqrt,check_arg:function( x){returnx>=0}}Mixin. prototype =sqrt//所有mixedmixin的实例都将 有 sqrt 作为 prototype chk_sqrt = newmixedMixin(“sqrt”,”check_arg“,”checked_sqrt“)chk_sqrt.sqrt(-4)//评估到NaNchk_sqrt.checked_sqrt(四)//评估到2 chk_sqrt.checked_sqrt(-4)//抛出“非法参数“同样的函数mixedmixin可以用来扩展一个对象,log函数log ={//一个新对象与 两 属性日志:数学.log10,check_arg:function( x){returnx>=0}}Mixin. prototype =log//mixin的所有实例 将 有 日志 作为 prototype chk_log = newmikedMixin(“log”,”check_arg“,”safe_log“)chk_log. log(-10)//计算为NaNchk_log. safe_log(10)//评估至1chk_log. safe_log(-10)//抛出“非法论点“由于对名称操作的支持,mixin适配和应用可以在我们的演算中表达;此外,如第4节所 示,组 合类型 检查确 保了 mixin 适配 和应用 的类型 正确性 上面 给出的JavaScript示例可以在我们的演算中改写为8:t m= λαop. b中的λαLambdaαnop. 拉姆达河 letn op =!(r )in rQ<|αn op›→n op>与前面的例子一样,mixin有三个名字αop、αinb和αnop,分别对应于必须检查的操作的名字、执行检查的操作的名字和新添加的操作的名字,新添加的操作是操作αop的检查版本。然后它取一个重新绑定r,它被期望为运算αop和b中的α提供一个定义,并被应用于一个未绑定项,该未绑定项根据重新绑定提供的运算αop和b中的α来定义新的运算。重新绑定的应用程序的结果被运行,以获得与新操作对应的值,最后,重新绑定(扮演模块的角色)通过重写操作符与新组件8由于演算不支持异常,如果边界没有被验证,函数简单地返回常规值-1。28D. Ancona等人/理论计算机科学电子笔记322(2016)19|►⟨|⟩⟨|⟩不urσ::=.. | Λ α:c. t| X|不|t不|t> t|t > t|! 不|不1 21212 1 2::=x1:T1<$→X1, . ,xm:Tm›→XmQt| σ t uσ::=X1:T1→<$t1, . ,Xm:Tm→›tmX,Y::= N|α::=X1→<$ Y1, . ,Xm→› YmT::=. . . |T1→T2|α:c。不|⟨Δ|T|⟨Δ1|Δ2⟩νCΔνΣAΓ::=X1=/ Y1. . .Xm/=Ym::=X1:T1, . ,Xm:Tm* =A;c; r::= α1. αn::=x1:T1, . . . ,xm:Tm::=|+的term取消绑定映射重新绑定映射重命名名称类型约束名称上下文(变化)注释类型上下文名称变量变量上下文(WF-箭头型)A; c |= T OK A; c |= T ′OKA; c| = T→T′ OK(WF-NAME-ARROW -TYPE)A{α}; c,c′|= TOKA; c|=α:c′.T OK?(WF-NAME-cTX)A; c |= T kOK(1 ≤ k ≤ m)A X k(1 ≤ k ≤ m)c |= X i= X j<$T i= T j(1 ≤i,j ≤ m)A; c|=X1:T1, . ,Xn:TmOK(WF-UNB-TYPE )A; c| = Δ OKA; c| = T OKA; c |= Δ|T OK(WF-REB型)A; c| = Δ ′OKA; c| = Δ OKA; c|= Δ′|好的C|= Xi = Xj<$ti= tj(1≤i,j≤m)(WF-REB-MAP )C| = X1<$→t1,.,X m›→t mOKA<$X k(1 ≤ k ≤ m)A <$Y k(1 ≤ k ≤ m)c |= X i= X j<$Y i= Y j(1≤ i,j ≤ m)(WF-人)A; c|=X1→<$Y1, . ,Xm›→YmOK??4类型演算图2显示了类型化演算的语法,它通过用类型注释变量和名称以及用约束命名变量进行了扩展,下面将详细解释。图2:类型化演算:语法约束的形状为X/=Y。 一组约束c在名称变量A下是一致的,写作Ac,如果在c中出现的变量属于A,并且此外,X=/ X/∈c,对于所有X。 我们认为X成本等于Y成本,|=X=?Y,如果X/=Y/∈c.类型包括函数类型、约束名称多态类型、未绑定类型ΔT和重新绑定类型 Δ1Δ2ν。 为了简单起见,我们省略了基本类型的原始值,如整数或布尔值。在下面的解释中,我们更详细地说明了由受约束的名称多态类型表示的类型系统的新特性。读者可以参考我们以前的工作,以获得更多关于未绑定类型和开放/封闭重新绑定类型的解释和示例。如果判断A;c=TOK可由图3的规则导出,则类型T在名称变量A和约束c的集合下是良构的。如果X是一个名称变量,我们写A X来表示X属于A图3:格式良好的类型、重绑定映射和重命名函数类型对应于lambda抽象,其中变量现在D. Ancona等人/理论计算机科学电子笔记322(2016)1929≤ ≤联系 我们|›→›→ ⟩⟨|⟩◦≤≤νH H用一个类型标注。受约束的名称多态类型对应于名称抽象,其中name变量现在使用约束进行注释。约束是必要的,以保证对于α的每个可能的实例化,我们都得到格式良好的项和类型。例如,项Λ α:α=N。N:int 0,α:int 1是一个重绑定参数,以其两个组件之一的名称命名,但必须与另一个组件的常量名称N不同。未绑定类型Δ T对应于开放码:Δ是序列X1:T1,.,X m:T m称为名称上下文。 类型指定开放代码需要将名称X i重新绑定到类型T i(1im)的项,以便正确地产生类型T的项。 只有当序列中出现的类型是格式良好的,序列中出现的名称变量属于A,并且在c下可能相等的名称被映射到相同的类型中时,未绑定类型在名称变量A和约束c下才是格式良好的,如图3中的规则(WF-UNB-TYPE)和(WF-NAME-c TX)所示。再装订类型<$Δ1|Δ 2对应于重新绑定;名称上下文Δ 1指定重新绑定所依赖的名称,而名称上下文Δ 2=X1:T1,.,X m:T m指定重绑定映射将每个名称X i与T i(1im)类型的项相关联。如果类型被标注为v=+,那么我们说类型是开放的(或非精确的),并且重绑定映射允许包含比名称上下文中指定的更多的关联。 注释ν =用于封闭(或精确)类型,以强制重绑定映射的域与Δ2的域完全重合。在类型规则中,我们将在注释上使用二元运算符,定义为ν = ν=ν和++ =+。一个重绑定类型在名称变量A和约束c下是良构的,只有当序列Δ 1和Δ 2中出现的类型是良构的,序列中出现的名称变量属于A,并且在c下可能相等的名称被映射到相同的类型中,类似于未绑定项所需的,如图3中的规则(WF-REB-TYPE)和(WF-NAME-c TX)所建模的。重命名以及值、求值上下文、替换和名称子定义为无类型语言。图3还定义了约束c下重绑定映射的良构性,以及名称变量A和约束c下重命名的良构性。(无类型化)重绑定映射是良构的,如果在c下可以相等的名称被映射在相同的项中,如规则(WF-REB-MAP)所建模的。请注意,类型注释的格式良好性由规则(WF-NAME-cTX)单独检查。重命名的格式良好要求名称变量属于A,并且在c下可能相等的名称被映射到相同的名称中,如由规则(WF-REN)建模的。子类型关系在图4中定义。函数类型之间的子类型是标准的。一个受约束的多态类型可以通过添加更多的约束或使实例化获得的类型更具体来变得更具体。未绑定类型之间的子类型遵循与函数类型相似的规则:关系在名称上下文中是逆变的,在重新绑定后返回的类型中是协变的名称上下文之间的子类型由记录子类型的通常规则定义:宽度和深度子类型都允许。宽度和深度30D. Ancona等人/理论计算机科学电子笔记322(2016)19⟨|⟩►◦⟨|⟩⟨|⟩(SUB-E)T1′≤T1T2≤T2′T1→T2≤ T1′→T2′(SUB-NAME-)c′c T ≤T′α:c.T≤(SUB-UNB)Δ′≤ ΔT≤T′⟨Δ |T≤ Δ ′|T ′(SUB-OPEN-REB)Δ ′1≤ Δ 1 Δ2≤Δ′2⟨Δ| Δ ⟩ ≤ ⟨ν产品介绍1 2Δ| Δ ⟩1 2(SUB-CLOSED-REB)Δ′1≤ Δ1Ti≤Ti′(1≤i≤n)⟨ Δ 1|X1:T1, . ,Xn:Tnε≤ε Δ ′1|X1:T1′, . ,Xn:Tn′端(SUB-NAME-cTX)<$i(1≤i≤n)<$j(1≤j≤m)Xi′=Xj<$Tj≤Ti′X1:T1, . ,Xm:Tm≤X1′:T1′, . ,Xn′:Tn′A; c| = TOKA; c| = T′OKT≤ T′(S ub-cONSTR)A; c| = T≤T ′图4:类型化演算:子类型规则在重新绑定类型之间也允许子类型化,如果关系中的右手侧(简称RHS)类型是开放的,因为封闭类型总是可以被认为是开放类型,而不是相反。这是因为封闭类型在重新绑定映射上表达了更严格的约束。 比如说,ν再装订机|X:T Xt x,Y:T Y<$→t y对于任何Δ,类型为Δ|X:T X,Y:TY对于ν= +和ν=,它有类型ΔX:TXν,而只有对于ν= +,它才有类型Δ X:T X ν;还要注意,这个项最精确的类型是X:TX,Y:TY<$。当子类型关系中的rhs类型是一个封闭的重绑定类型时,那么lhs类型也必须是封闭的,因此,它必须定义相同的名称集;在这种情况下,只允许深度子类型。最后,rule(S ub-cONSTR)在名称变量和约束下对子类型进行建模.类型判断具有形状A;c; r t:T,这意味着术语t具有 在变量A、约束c和上下文Γ下的类型T为自由变量提供类型。图5中给出了类型规则。类型系统支持包容,规则(T-SUB)。请注意,第二个前提意味着两种类型都是良构的。lambda抽象的规则(T-ABS)是标准的。在规则(T-NAME-ABS)中,如果引入的约束条件cJ在当前名变量被α增广的情况下是一致的,则项Λα:cJ.t是良类型的,并且t取约束条件的并集是良类型的在规则(T-U NB)中,术语“T-U”|如果通过辅助函数名ctx从u中提取的名称上下文,例如,X1:T1,...,X m:T m,在当前名称变量和约束下是格式良好的,也就是说,如果X i是名称变量,则X i属于A,并且,如果X i可以等于c下的X j,则它们被映射为相同的类型。结果类型T通过在由辅助函数ctx从u提取的内容更新的上下文中键入t来获得。这两个辅助函数在图5的底部定义。在规则(T-REB)中,如果从u和r提取的名称上下文在当前名称变量和约束下是格式良好的,则术语u r此外,在当前约束下,r必须是良构的,也就是说,可能相等的名称映射在同一项中。最后,对于r的定义域中的每个名称,用类型标注,比如T,相关术语必须在上下文中具有类型T,该上下文由辅助函数ctx从u中提取的类型更新。注意D. Ancona等人/理论计算机科学电子笔记322(2016)1931⎧/1∀1212(T-S UB)A; c;Γt:T A; c| = T≤T ′A;c;T′(T-ABS)A;c|=T1OKA;c;Γ[x:T1]t:T2A; c; Γλx:T1. t:T1→T2(T-NAME-ABS)A<${α}<$c′A<${α};c,c′;Γ<$t:TA;c;Γε Λα:c′.t:εα:c′.T(T-U注)A; c| = ΔOKA;c; Γ[Γ′]t:TA; c; r|t:Δ|Tname ctx(u)= Δctx(u)= Γ′C|= X1t1,...,XmtmOKname ctx(u)= ΔA; c| = Δ1|Δ 2-1000OK A;c; Γ[Γ′]ti:Ti(1≤i≤m)1(T-REB)A; c; r|X1:T1›→t1,.,Xm:Tmtm:Δ1| Δ2⟩◦ctx(u)= Γ′Δ 2=X1:T1, . ,Xm:Tm(T-V(AR)A;c;rx:TΓ(x)=T(T-A PP)时间1:T1→T2第二节:T1时间t1t2:T2(T-NAME-APP)A<$c′{α<$→X}A;c;Γ<$t:<$α:c′.T A<$XA;c; r→t X:T{α<$→X}A; c| = Δ 1,Δ 2正常A; c; rt1:Δ|Δ 1,Δ ′ν1A; c; rt2:Δ|Δ 2ν2(Δ=或ν 1 2 =),(T-OvER)A;c;ΓtQt:Δ|Δ,Δν1 Hν2dom(Δ′)dom(Δ)(T-REB-APP)(T-R UN)t:|T你好!t:TA; c| = Δ 1,Δ 2正常A; c; rt1:Δ′,Δ 1|Δ,Δ 2ΔvA; c; r Δt2:Δ,Δ 1|T(Δ1 =λ或ν=λ),A; c; r t1> t2:Δ′,Δ 1|Tdom(Δ1)dom(Δ2)=domA; c| = σ1OK A; c| = σ2正常 A; c| = σ1<$Δ 1OK A; c; rt:Δ1|Δ 2⟩ν(T-R)A; c;Γ <$σ1t uσ2:<$σ1<$Δ 1|Δ 2◦ σ2⟩◦ctx(x1:T1 X1, . ,xm:Tm→Xm)=x1:T1, . ,xm:Tm名称ctx(x1:T1X1, . ,xm:Tm→Xm)=X1:T1, . ,Xm:TmσΔ =Δσ=Δ′ifdom(Δ)dom(σ)其中X:T∈Δ′i ∈σ Y Y:T∈Δσ(Y)=X,否则定义为Δ′ifrng(σ)dom(Δ)其中X:T∈Δ′ i <$X∈dom(σ)<$T= Δ(σ(X)),否则定义图5:类型化演算:类型化规则总是可以推导出一个精确的类型规则(T-VAR)和(T-APP)是标准的。在规则(T-NAME-APP)中,项t X是良类型的,如果X属于A,如果它是一个名称变量,t有一个受约束的多态类型α:cJ.T,并且通过在约束cJ中用X替换α,我们不会得到形状Y=Y的不等式。在这种情况下,结果类型是通过将T中的α替换为X而获得的。在约束和类型中用名称替换名称变量的明显定义被省略了。在规则(T-OvER)中,只有当t1和t2具有重新绑定类型时,重写t1t2才是良好类型的;t1类型的名称上下文被确定性地分成两部分。部分ΔJ1对应于也在t2中定义的名称,如边条件dom(ΔJ1)dom(Δ2)所表示的,因此被覆盖,而1⎪⎩⎧⎪⎨⎪⎨⎪⎩232D. Ancona等人/理论计算机科学电子笔记322(2016)19部分Δ1对应于未在t2中定义的名称。如果Δ1 =π,则t1完全为D. Ancona等人/理论计算机科学电子笔记322(2016)1933>重写,因此结果的名称上下文是t2的上下文;在这种特定情况允许t2的类型是开放的,而如果Δ1是开放的,则t2需要具有封闭型,否则无法正确识别Δ1。前面定义的操作符H组合了两个注释ν1和ν2,使得结果类型是封闭的,当且仅当两个类型t1和t2都是封闭的。请注意,由于存在名称变量,除了必须覆盖的名称之外,还有一些名称可以在某些实例化中被覆盖例如,在项Λ α中:α/= N1。⟨ |N1:T1t1,N2:T2<$→t2<$⟨ |α:int›→ 1 π,名称N1永远不会被覆盖,而名称N2可以被覆盖,α=N2。赋给覆盖项的名称context对应于无覆盖的情况,即在这种情况下为N1:T1,N2:T2,α:int然而,由于这个名称上下文在约束α/=N1下必须是良构的,因此类型N2必须是int,因此即使对于实例化α=N2,我们也会得到良构的类型。规则(T-RUN)指出,只有当其名称上下文为空时,未绑定类型的术语才可以安全运行,也就是说,所有变量都已经在代码中正确绑定。重新绑定应用程序t1t2的类型规则(T-REB-APP)类似于重写的类型规则:为了正确识别t1中不需要绑定的名称(用Δ1表示),该规则需要t2的精确类型,除非 Δ1 =(也就是说,所有名称都是绑定的),也允许开放类型。这是因为t1的绑定名称必须与t2中的对应名称具有相同的类型,而t2中未在t2的开放类型中指定的其他名称可能会用于将t1的名称与不兼容的类型绑定。请注意,通过应用包容,总是可以将名称与其类型是预期类型的子类型最后,在用于重命名的规则(T-R)中,两个重命名必须在当前名称变量和约束下格式良好,即新引入的名称必须存在,并且可能相等的名称被映射到相同的名称中。结果类型的名称上下文是通过辅助操作符σΔ和Δσ从原始类型传播而来的,这两个操作符都是部分的,定义在图5的底部。注意,如果两个名字X和Y被σ1映射成两个可能相等的名字,那么X和Y必须具有相同的类型,形式上表示为要求名字上下文的良构性σ1<$Δ 1。字体系统的可靠性w.r.t.操作语义学声明良好类型的术语不会卡住。 这是从下面的主题缩减和进度属性派生的。定理4.1(主语归约)设t是这样的,对于某个T和T,我们有:如果t−→tJ,则tJ= T。定理4.2(进步)设t是这样的,对于某个T,我们有:那么,要么t是一个值,要么对于某个tJ,我们有t−→t J。5打字示例在本节中,我们考虑第3节中示例的类型化版本。34D. Ancona等人/理
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 5
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- 彩虹rain bow point鼠标指针压缩包使用指南
- C#开发的C++作业自动批改系统
- Java实战项目:城市公交查询系统及部署教程
- 深入掌握Spring Boot基础技巧与实践
- 基于SSM+Mysql的校园通讯录信息管理系统毕业设计源码
- 精选简历模板分享:简约大气,适用于应届生与在校生
- 个性化Windows桌面:自制图标大全指南
- 51单片机超声波测距项目源码解析
- 掌握SpringBoot实战:深度学习笔记解析
- 掌握Java基础语法的关键知识点
- SSM+mysql邮件管理系统毕业设计源码免费下载
- wkhtmltox下载困难?找到正确的安装包攻略
- Python全栈开发项目资源包 - 功能复刻与开发支持
- 即时消息分发系统架构设计:以tio为基础
- 基于SSM框架和MySQL的在线书城项目源码
- 认知OFDM技术在802.11标准中的项目实践
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功