没有合适的资源?快使用搜索试试~ 我知道了~
JavaScript的静态类型检查
理论计算机科学电子笔记138(2005)37-58www.elsevier.com/locate/entcsJavaScript的类型检查克里斯托弗·安德森1,3英国帝国理工学院计算机系地址:Paola Giannini保拉·贾尼尼1,2,4DipartimenodiInforrmatica,Universesita`delPiemonteOrientalele,SpaltoMarengo33,阿莱西亚,意大利.摘要JavaScript是一种功能强大的命令式基于对象的语言,由于在网页中的使用而变得流行。它通过允许动态地向对象添加成员来支持灵活的程序开发。 代码是动态类型的:运行时访问不存在的成员会导致错误。我们建议为JavaScript设计一个静态类型系统,它可以检测到这样的类型错误。因此,程序员可以从JavaScript提供的灵活编程风格和静态类型系统提供的安全性中受益。我们用JavaScript的形式来演示我们的类型系统,JS 0。我们的类型是结构性的。对象类型的成员分为定义的和潜在的。一个潜在的成员在分配时成为确定的。我们概述了一个证明,我们的类型系统是健全的。保留字:JavaScript,脚本语言,结构递归类型,类型检查1介绍JavaScript(参见[12])是一种强大的基于命令式对象的语言,由于在网页中的使用而JavaScript通过允许向对象动态添加成员来支持灵活的程序1部分由DART支持的工作,欧盟委员会研究理事会,IST-01- 6-1A2 MURST Co finn3电子邮件地址:cla97@doc.ic.ac.uk4电子邮件:giannini@mfn.unipmn.it1571-0661 © 2005 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi:10.1016/j.entcs.2005.09.01038C. 安德森,P。Giannini/Electronic Notes in Theoretical Computer Science 138(2005)370JavaScript代码直接嵌入到网页中,并在页面加载时进行解释。代码是动态类型的,如果在运行时访问了不存在的字段或调用了不存在的方法,则会生成运行时类型错误。当发生此类错误时,通常会向用户显示错误消息。我们建议为JavaScript提供一个静态类型系统,它可以检测到当前只在运行时检测到的类型因此,程序员可以从JavaScript提供的灵活编程风格和静态类型系统提供的安全性中我们用JavaScript,JS0的形式来演示我们的类型系统.JS0支持标准的JavaScript可扩展特性,例如创建对象的函数,以及字段和方法的动态我们的类型系统解决了JS0的可扩展特性带来的以下挑战:• JS0对象结构是由成员赋值决定的• JS0对象可以在创建后添加成员• JS0方法是通过将函数分配给成员来创建的,• JS0方法可以在对象之间共享,• JS0函数可以有三个不同的角色:创建对象,对象的方法和全局函数。我们使用JS0的显式类型版本JST来解决这些问题。 JST使用0 0结构形式为:t=μα。 <>列出对象的成员。活页夹μα用于允许通过α引用在TI里面的整个T 在JST对象类型的成员可以是注解为?表示它们尚未被分配。 我们称这样的成员为潜在的,而成员没有注释?他们被称为定义。函数类型的形状为:t = μα。((μ α. M,t1)→t2),其中μ α. M是函数可以作为方法的对象的类型(接收者),t1是参数的类型,t2是结果的类型。同样,对于函数类型,绑定器μ a允许引用M内的类型t,t1和t2。功能然后可以用作任何类型为μ α子类型的对象的方法。M.在函数对它的接收没有任何要求的情况下,则M=<<>>,则它可以被用作一个g函数。对于对象类型,我们在宽度上有一个子类型,因为要使类型t成为类型tJ的子类型,t必须至少声明tJ中定义的成员,同样的类型。此外,如果一个成员在tJ中有定义,那么它也必须在t.我们的意图是定义一个类型系统,它足够丰富,允许键入JavaScript程序的重要子集,同时防止运行时错误,例如访问对象的不存在成员。我们会的C. 安德森,P。Giannini/Electronic Notes in Theoretical Computer Science 138(2005)37390然后,开发一个类型推断来自动将JavaScript代码转换为类型化变体,以进行类型检查。这将是一个工具的基础,用户可以用它来检查他的JavaScript程序是否符合这种类型规则。本文的组织结构如下。在第2节中,我们给出了一个介绍JS0和JST特性的例子。在第3节中,我们定义了JS0的语法及其操作语义,在第4节中,我们给出了一个类型化的版本的JS0,JST.JST的可靠性证明在第5节中概述。最后在0 0第六部分,我们比较了我们的工作与其他人,并概述了我们未来的发展方向。2例如我们从一个示例开始,演示JavaScript中在图1中,我们给出了一个描述人 和 他 们 的 工 作 的 场 景 。 我 们 定 义 函 数 Person , moneyTrans ,employPerson。前面有注释//Main的代码是程序的入口点。图1显示:123456789101112131415161718Fig. 1. 无类型JS 0人示例• 使用函数创建对象(第16和17行),• 通过赋值在对象中隐式创建成员(第2行和第3行),• 通过将函数分配给成员来获取方法(第3行),• paul.payMe(10)方法调用,当moneyTrans被执行(第18行),• 在对象创建后添加成员,employPerson添加成员boss(第12行),以及function Person(x){this.money =x;this.payMe =moneyTrans; this}public void run(x){this.money =this.money + x;}public void run(x,y){ x.}//Mainnew Person(0); newPerson(0);paul = employPerson(paul,john); paul.payMe(10); paul.boss40C. 安德森,P。Giannini/Electronic Notes in Theoretical Computer Science 138(2005)3700• 全局函数调用,调用employPerson(paul,john)而不带接收器(第18行)。现在我们在类型化版本的JavaScript上下文中查看同一个示例。在这个例子中,我们使用了一个比JST的语法稍微宽松的语法,允许函数有多个参数和变量声明。图2给出了图1的类型化版本,其中:• t1是(money:Int>>,Int)→Int,andd•t2是μα。莫<<妮:是吗?,payMe:t1?,boss:α?>>,and•t3是μα。 <<钱:Int,payMe:t1,boss:t2?>>,and•t4是μα。moneyy:Int,payMe:t1,boss:α>>首先注意到,与函数的JavaScript不同,形式参数和返回类型有类型注释(第1、8和13行)。 元变量this的类型(函数可能是其方法)在每个函数的开头(第2、9和14行)给出。虽然不是JST语法的一部分,但出于演示目的,我们对变量paul和john和类型(第22和23行)。第二,观察对象类型是结构化的,包括一个对象列表,每个对象都有自己的考虑函数Person的返回类型t3,它是一个对象的类型,其中fieldsmoney的类型为Int,payMe的类型为t1(我们稍后会看到这是一个方法),boss的类型为t2。类型t2也是一个对象类型,但使用绑定变量α来引用自身。这捕获了要求一个人的老板也是一个人。类型中的成员可以用?指示类型t2中的潜在值,例如money、payMe和boss。当使用Person函数创建对象时,它们被赋予类型t3。因为成员boss是潜在的,这允许它在对象创建后添加。因此,物体可以以受控的方式进化。当一个潜在的成员被分配给时,它就变得有定义了,失去了它的?。为了保持类型系统的可管理性,我们只跟踪函数范围内变量(形参和this)的赋值要使变量赋值的结果在函数外部可见,必须使用适当的类型从函数返回变量例如,在函数employPerson中,赋值x.boss = y使boss在类型中有定义养木 返回类型为μa。moneyy:Int,payMe:t1,boss:α>>in哪个老板把批注弄丢了?函数被赋予形状为(t1,t2)→t3的类型,其中t1是元变量this的类型,t2是参数的类型,t3是C. 安德森,P。Giannini/Electronic Notes in Theoretical Computer Science 138(2005)3741函数的返回值。例如,moneyTrans的类型为t1:(moneyy:Int>>,Int)→Int当他遇到一个变量<<时,这是一个参数:Int>>,参数类型为Int,返回类型为Int。当一个函数在调用时被用作对象的方法时,我们检查接收者是否是函数中this声明类型的子类型 例如,与保罗一起,payMe(10)在21行中具有μa。 <<钱:Int,payMe:t1,boss:t2? 这是<<一个很大的钱:我不。对于对象类型,子类型是基于所涉及的类型的结构。要使类型t成为类型tJ的子类型,t必须至少声明tJ中定义的具有相同类型的成员。 如果一个成员在tJ中定义,那么它也必须在t中定义。我们在类型μ α中看到了这一点。<>,ofavariabablepaulbeingasubtypeoff<< 钱:我不>>,这种类型的这是declard在钱transs。 这意味着函数moneyTrans可以用作任何对象的方法,其声明的类型包含Int类型的成员money。考虑函数moneyTrans1返回自身:function moneyTrans1(x:Int):μ α. (Int,Int)→α{this.money.comthis.money =this.money +x;moneyTrans1;}与对象类型一样,绑定器μ a允许函数类型引用自身。1function Person(x:Int):t3{2this:t2;3this.money = x;4this.payMe = moneyTrans;5这6}78function moneyTrans(x:Int):Int{9this:money:Int>>;10this.money = this.money + x11}1213functionalnemployPerson(x:t3,y:t3):t4{14this:<>>;15x.boss = y; x16}1718//Main192021t3 public void run(100);t3paul = new Person(0)paul=employPerson(paul,john);paul.payMe(10);paul.boss图二. 类型化JS 0 Person示例42C. 安德森,P。Giannini/Electronic Notes in Theoretical Computer Science 138(2005)373JS0我们开发了JS0,它是JavaScript的一个子集,包括以下功能:(i) 用于创建对象的函数,(ii) 函数可以被别名化并用作对象的成员,(iii) 可以动态地将成员添加到对象我们选择这些特性是因为:(i)代表了在JavaScript中创建对象的方式,(ii)是对象获取方法的一种方式,(iii)为程序提供了灵活性。JS0不包括以下JavaScript特性:函数库、本机调用、全局this(通过全局对象)、动态变量创建、函数作为对象、动态删除成员、委托和原型设计我们省略了这些特性,因为前三个不是范式的核心,而其他的则太难在静态类型语言中支持。我们可以在JS0中编写[10]中的介绍性示例,假设函数库,以及预定义的类型,如JavaScript,字符串等。JS0的语法如图3所示。一个程序就是一系列函数的声明.在JS0中,函数只能有一个形参。对多参数函数的扩展是微不足道的。对于程序P,P(f)定义如下. 函数f(x){e} if P = F函数f(x){e} FjP(f)=Udf否则3.1操作语义我们有一个JS 0的结构化操作语义,它将表达式、堆和栈的元组重写为程序代码中的值、堆和栈的元组。重新编写报告的性质是:计算:Programexp×Heap×Stack(ValDev)×Heap×StackC. 安德森,P。Giannini/Electronic Notes in Theoretical Computer Science 138(2005)3743?:P∈Program::=FF∈FuncDecl::=function f(x){ e}e∈ Exp::=varlocalf函数标识符新 f( e)对象创建 e; e序列e. m( e)成员呼叫e. m成员选择f( e)全局调用lhs= e赋值e e e1 23条件零零n个整数var∈ EnvVars::=this|Xlhs∈ LeftSide::=x|e. M身份证f∈ FuncID::=f |f ′| .. .m∈用户ID::=m|m′|. . . ...这是什么?图三. JS 0的最大值其中:H∈Heap=Addr→finObjS∈Stack={this,x}<$Val使得S(this)∈Addrv∈Val={null}FuncIDAddrIntDV ∈Dev={nullPntrExc,stuckErr}o∈Obj=用户ID→finVal堆将地址映射到对象,其中地址Addr为10,. 恩...我们用→finn表示一个有限映射。 用H [i→v]表示更新将堆H中的地址i的值转换为v。堆栈将其映射到地址,将x映射到值,其中值Val是函数标识符(表示函数),地址(表示对象),null或整数。最后,对象是成员标识符和值之间的有限映射。[1][m1:v1.] mn:vn]]我们表示对象映射mi到vi,其中i∈1···n。对于栈和对象,我们使用之前定义的堆的更新表示法。为了让操作语义的味道,我们展示了规则(mem-call)。 一44C. 安德森,P。Giannini/Electronic Notes in Theoretical Computer Science 138(2005)370012规则的详细说明见附录A。e1,H,S1,H1,S1e2,H1,S1vJ,H2,SJH2(i)(m)=ff(x){e,J}eJ,H2,{this<$→i,x<$→vJ}v,HJ,SJJe. m(e),H,Sv,HJ,SJ(mem-call)在rule(mem-call)中,我们首先评估接收器,然后是方法的实际参数。我们通过在P5中查找接收器中成员m的值(通过对e求值获得)来获得函数定义(对应于该方法)。 我们用一个堆栈执行主体,调用的接收方,x为实际参数的值最后,我们在实际参数求值后返回堆栈,并在方法体执行后返回堆,因此this和x在方法体求值前绑定到它们的值,但堆具有方法体求值的结果返回到图1中的示例,在存在空堆H0的情况下执行函数Main的主体,其中堆栈S0将john和paul映射到null将产生堆H1和堆栈S1,使得john和paul分别映射到10和11,并且H1(ι0)=[[money:100,payMe:moneyTrans]]H1(ι1)=[[money:10,payMe:moneyTrans,boss:ι0]]请注意,成员payMe别名函数moneyTrans,该函数在paul.payMe(10)执行时被调用。4JS0的类型系统在本节中,我们将介绍JS0的一个完全类型化版本:JST。4.1类型图4显示了JS T与JS 0不同的部分以及类型的定义。我们提出以下意见:• 函数的返回类型前面有冒号,• 函数形式参数被给定类型,[5]为了表述清楚,我们从归约规则中省略了P。C. 安德森,P。Giannini/Electronic Notes in Theoretical Computer Science 138(2005)3745• 函数体首先声明接收器的类型,this。类型t1,...,tn,包括对象类型、函数类型或Int(整数类型)。 对象类型(μ a. M和M)列出对象中存在的方法和字段我们使用μ-binder来允许类型引用自身。所以是μ α。当M=<>时,是一个不与m个节点连接的类型m1,..., 类型t1的mn,...,n,分别。 在μ α。M[m›→t]我们表示将成员m更新为M中的类型t。 在图5中,我们定义M(m),它选择M中成员m的注释类型(如果它被定义),以及T(M,m),它选择M中成员m的类型(没有注释)。函数类型(μ α. (t1,t2)→t3和(t1,t2)→t3)列出了接收器的类型t1,它必须是对象类型μ αJ。M、参数类型t2和函数返回值类型t3。 至于对象类型μ绑定器允许引用整个类型。类型的自由变量的定义是标准的:FV(<>)=i∈1. nFV(ti),FV((t1,t2)→t3)=i∈1. 3FV(ti),FV(μ α. t)=FV(t)−{α},FV(α)={α},FV(Int)= α。我们假设t是一个weil形式的difitisclose d(FV (t)=f),并且,如果type是一个对象类型,那么它包含唯一的成员定义。如果m的类型是α,或M,或μ α。M或Int成员代表一个域。在α的情况下,类型具有封闭类型(μ α)的结构。M)。如果m 的类型是μ α。(t1,t2)→t3,或(t1,t2)→t3,则m表示方法。程序P中函数f的类型可以通过下面的查找函数L.(t,tJ)→ tJJ如果P(f)=函数f(x:tJ):tJJ{this:t; e}L(P,f)=Udf否则对象类型的某些成员使用?进行注释。这表明一个潜在的成员,m:t?,可以被分配给以后,因此,允许对象进化。在一个类型良好的程序中,潜在的成员只有在被赋值后才能被访问。4.1.1同余和子类型类型之间的全等性在图6中定义。用t1[α/t2]表示α在t1中的自由出现被t2替换。对象类型直到α-转换、其成员的置换和绑定变量的展开都是全等的,函数类型直到α-转换都是全等的,46C. 安德森,P。Giannini/Electronic Notes in Theoretical Computer Science 138(2005)37阿勒⎨如果M=· · ·m:t· · ·>>00语法P∈Program::=FF∈ FuncDecl::=functionf (x:tJ):tJJ{this:t;e}类型t∈ Type::=μ α。M |α|I n t |Intμ α。(μ α。M,t)→t|(μ α。M,t)→t M∈MemberTypes::= <<(m:t[?])联系我们α∈ ObjVar::=α|αJ|αJJ|......这是什么?见图4。 关于JSTM(m)=t?ifM=<<· · ·m:t?· · ·>>否则,.t如果M(m)= t或M(m)= t?T(M,m)=如果M(m)=Udf,则Udf图五. 成员类型的选择和展开绑定变量。子类型判断t“t j,在图7中定义,意味着只要需要类型t j,就对于对象类型,我们有宽度的子类型首先,Mj的所有定义成员必须存在,并且与M中的那些定义成员全等(μ α规则的第一行)。M“Μ ΑJ。图7中的MJ)。为了确保类型是封闭的,我们用绑定变量的出现次数按其封闭类型。图7中定义的第二个条件(μ α规则的第二行)。M“Μ Α J。MJ)是指MJ中的潜在成员。特别地,它指出MJ的所有潜在成员必须作为M的具有全等类型的潜在或定义成员存在。这个条件是必要的,以确保增加一个新的对象的成员不会破坏兼容性。例如,考虑以下程序片段(可以使用JST的语法给出类似的示例)C. 安德森,P。Giannini/Electronic Notes in Theoretical Computer Science 138(2005)3747我反旋展开α-转换αJFV(t)t tμ α。tt [α/μ α. t]μ α。tμ αJ. t[α/αJ]功能titJ{1, 2, 3}μ α。(t1,t2)→t3<$μ αJ. (tJ,tJ)→tJ123重新排序m:(M(m)= t ⇐⇒MJ(m)=tJ) ∧tJ≡tm:(M(m)= t? MJ(m)= tJ?)∧ tJ≡ tμ α。M μ αJ. MJ及物性t1t2 t2t3t1t3见图6。 类型的同余x:μα。 <>y:μα。<>z:μα。<>> >x =0;X. m1 = 5;.y =z;y. m1=零对象类型的许多合理子类型都包含μα 。 <>是μ α的子类型。 <<>>。 因此,假设z=x;是正确的。 如果我们的子类型不考虑潜在成员,我们也会有μα。 <<>>“μ α。 <>并且该信号my=z;将被校正。因此,前面的代码片段将是良好类型的。然而,在这段代码之后,x的字段m 1包含一个对象(null)而不是一个整数。对于函数类型,子类型与全等一致。在这项工作的未来版本中,我们可能会放宽这一限制,并允许接收器和参数类型的逆变和协方差的返回类型。给定类型48C. 安德森,P。Giannini/Electronic Notes in Theoretical Computer Science 138(2005)3711ttJtt1m:(MJ(m)=tJ= [α/μ α. M])m:(MJ(m)= tJ?=<$T(M,m)= t) <$tJ [αJ/μ αJ.[α/μ α. M])μ α。M“Μ Α J。MJ见图7。分型t和tJ,t“t j是否是可判定的4.2表达式的类型在程序P和环境Γ的上下文中键入表达式e具有以下形式:P,re:trJ环境,r ={this:μ a. M,x:t}将接收者this映射到格式良好的对象类型,将形式参数x映射到格式良好的类型。我们用Γ[var<$→t]表示var在Γ中更新为类型t键入判断右侧的环境反映了对类型在键入表达式时,接收器或参数的。唯一可能的改变是移除?从this或x的成员的类型。考虑图8的类型规则。规则(var)、(func)和(const)都很简单。注意null可以有任何对象类型。在规则(rule-acc)中,表达式e必须是对象类型,其中成员m是有定义的,即有定义的,没有注释?。 在类型,则所有出现的α都将被封闭类型替换,以返回封闭类型。在rule(meth−call)中,我们检查接收者的类型是一个对象类型,其中成员m具有函数类型,并且它是有定义的。此外,接收器的类型和实际参数必须是函数f的接收器和形式参数的声明类型的子类型。类型t1,TJ,和tJJ必须是封闭的,因为它们可能包含αJ的自由出现。在(call)中,我们考虑全局调用和构造函数,并要求函数中定义的接收器类型没有定义成员。这与操作语义是一致的,因为在全局调用和对象创建的情况下,我们从一个空的接收器对象开始。在rule(assign-add)中,我们修改了类型环境,从C. 安德森,P。Giannini/Electronic Notes in Theoretical Computer Science 138(2005)3749⎪⎪成员m的类型(this或形参的)注释?(if会员有?注释)。从这一点可以访问成员m。赋值的表达式类型必须是关闭后成员类型的子类型例 如 ,考虑表达式x。m2= x,其中,r(x)有y∈t=μα。 <>,(这个表达式可以正确地跟在x = null之后)。表达式在Γ中是良好类型的,我们有P,Γ x。m2=x:t<$rJ其中rJ将this映射到r(this),并且x映射到<< m1:Int,m2:μα。 <>(1),变量paul的类型为μα。钱:1,支付1,老板:t2? >>,afterheassignmentpaullhastype(1).我们现在给出类型赋值系统的一些性质。引理4.1设e是一个表达式,Γ是一个环境,使得Γ(x)和Γ(this)是良构的。如果P,r ∈e:t<$r J,则• rJ(x),rJ(this)和t是良构的,并且• r和r J是相容的。一个程序P是良构的,如果P中的所有函数声明都是良类型的,也就是说:如果f使得P(f)=functionf(x:tJ):tJJ{this:t;e}• 类型t、tJ和tJJ是良构的,t<$μ α。M、• P,{this:μ a. M,x:tJ},e:tJJJ,t jjj,tJJ。5类型系统在本节中,我们将概述类型系统是可靠的w.r.t.的证明。在3.1节中给出的操作语义。我们假设类型是-C. 安德森,P。Giannini/Electronic Notes in Theoretical Computer Science 138(2005)375110ΓΓΓ键入表达式P,Γthis:Γ(this)<$Γ(var)P,Γ<$x:Γ(x)<$ΓL(P,f)=tP,rf:tr(func)P,r为零:μ α。Mr(const)P,Γn:IntrP,Γ e:μ α。MJP,re:trJM( m)=t1P,ΓJ J JJ(−acc)第二章 :tr(seq)好吧m:t [α/μ α。[M][M]P,Γe;e:tJJJ1 2ΓP,r= 1:μ α。MJM(m)=μ αJ。(t1,tJ)→tJJP,r e:trJ1 1JJJJJ JJP,re2:trL(P,f)=μ α . (μ α。M,t1)→t1Jt11J{tJ Jμ α。M好吧m(e):tJJ[αJ/M(m)]JJ(meth−call)| M(m) = t }= ∅P,Γ<$newf(e):TJJ[αJ/L(P,f)]<$J(call)1 21Γ1ΓP,Γ<$f(e):TJJ[αJ/L(P,f)]<$JP , r ∈2 : t ∈rJrJ ( var ) =μα。MtJ=M[α/μ α。M]T(tJ,m)=tJJtΓJJ=ΓJ[var<$→tJ[m<$→tJJ]]P,r var. m=e2:trJJ(assign−add)P,r= 1:μ α。MJM( m)= tJP,rJe2:trJJt“tj[α/μα. M]P,r=1. m=e2:T(assign−upd)P,Γ ε1P,rJ e:IntrJ:tJJP,re:tJt2P,ΓJJJJJJJ J J► e3 :tr(续)Γ= Γ [x <$→Γ(x)*t](var−ass)你好e: e:tHtjJJHIJJJP,rx=e:tJJ1 2 3 Γ Γ见图8。 JS T中表达式的类型规则形成了我们首先定义一个值与给定类型兼容的概念。这个定义是通过共归纳给出的,首先定义了值和良构类型之间的任何一致关系应该具有的属性。定义5.1给定堆H和良构程序P,我们说:如果满足以下条件,则A(Val×Type)是一致关系• (null,t)∈A当且仅当t<$μ α。M表示一些形式良好的μ α。M、• (n,t)∈A当且仅当t=Int,52C. 安德森,P。Giannini/Electronic Notes in Theoretical Computer Science 138(2005)37• 若(f,t)∈A,则L(P,f)<$t,• 若(i,t)∈A,则t <$μ α. M和C. 安德森,P。Giannini/Electronic Notes in Theoretical Computer Science 138(2005)3753·H(i)=[[m1:v1. mp:vp]]· 对于所有的m和tJ,使得M(m)=tJ,我们有,m= mi对于某个i ∈ 1. p和(vi,tJ [α/t])∈ A· 对于所有的m和tJ,使得M(m)=tJ?如果m = mi对于某个i ∈ 1. p则(vi,tJ [α/t])∈ A如果A和AJ是一致关系,那么A <$AJ也是一致关系。因此,给定一个堆H和一个程序P,relations定义了值和类型之间的关系,也就是说,当一个值具有给定的类型时。定义5.2值v与H,P中的类型t相容,H<$v(t,如果对于H和P上的某种一致关系A,我们有(v,t)∈A请注意,一个地址可以与多种类型兼容。特别是,如果一个值与一个类型兼容,那么它与它的所有超类型都兼容。引理5.3如果t在下文中,我们定义栈S和堆H何时与环境Γ兼容。定义5.4如果P,H<$S(this)(Γ(this)andP,H<$),则P,Γ<$H,S<$成立S(x)(Γ(x)我们引入堆对之间的关系,堆栈说,一对堆,堆栈可以在表达式的评估期间从另一个获得。定义5.5给定堆H和HJ,堆S和SJ,PH,SDHJ,SJ如果:• S(this)= S J(this)。• 对于所有类型t,如果P,H <$S(x)(t成立,则P,H <$SJ(x)(t成立。• 对于所有地址i和类型t,如果P,H_i(t)成立,则P,H_i(t)也成立保持。我们现在可以陈述主要引理了。引理5.6对于良构程序P,环境Γ和表达式e,使得:P,re:trJIfe,H,Sv,HJ,SJ,anddP,ΓH,Sthen(i) P,HJv(t,54C. 安德森,P。Giannini/Electronic Notes in Theoretical Computer Science 138(2005)37(ii) P,rJ<$ HJ, SJ<$,和(iii) PH,SDHJ,SJ可靠性定理断言,如果一个表达式在类型环境Γ中是良好类型的也就是说,计算结果要么是正确类型的值,要么是nullPntrExc例外. 特别是,它不是stuckErr错误。定理5.7[类型可靠性]对于良构程序P,环境和表达式e,使得:P,re:trJIfP,IfH,If S和e,H,Sfw,HJ,SJ,then• 或者w= v,并且 P, HJ= v( t,• 或w = nullPntrExc。6比较和今后的工作本文定义了一个理想化版本的JavaScript的可扩展类型系统,并概述了它的可靠性。JavaScript是一种基于对象的语言,允许扩展对象和共享方法体。基于对象的语言的类型系统主要是在函数环境中开发的,参见[1]和[9]。在[6]中引入了一种命令式类型安全的面向对象语言TOIL。尽管该语言是基于类的,但其类型系统并不将类型与类标识。这使得类型的定义与我们的相似。但是,TOIL没有可扩展对象,因此不需要识别潜在的成员。可扩展对象在[8]中的函数设置中得到了考虑。Bono和Fisher在[5]中提出了可扩展对象的命令式演算。在Bono和Fisher类型系统中,对象有两种类型:可扩展的原型类型和不可扩展的对象类型。类型系统跟踪潜在的成员。我们的系统和Bono Fisher类型系统之间的主要区别是我们使用递归类型(而不是行类型加上泛量化和存在量化)。这使得我们有可能拥有一个可判定的类型推理算法,见本节的最后一段。请注意,Bono和Fisher的目标是在他们的对象演算中编码类,而不是获得类型推理算法。具有子类型的递归类型已经被各种研究人员与函数式编程语言一起研究,例如参见[3]。C. 安德森,P。Giannini/Electronic Notes in Theoretical Computer Science 138(2005)3755在[4]和[7]中使用了对象类型来跟踪对象的演化。特别是,在[7]中,潜在成员用于与本文件相同的目的。然而,这些类型与本文中使用的类型非常不同。它们是用对象的地址标识的单例类型在动态类型语言中确保类型安全的必要性已经得到了广泛的认可。[11]见《易经》,[12]见《易经》,[ 13 ]见《易经》,[14]见《易经》。在这些论文中,约束被定义为确保推断的约束可解的术语不会导致消息不理解错误。我们以不同的方式处理同一个问题,我们首先定义一个类型系统,它具有良好的特性,例如可靠性(良好类型的表达式不会导致消息无法理解的错误)和表达性(我们拥有的所有重要示例都可以被类型化)。我们的下一步将是定义一个类型推断算法,使得为一个术语推断的类型是该术语可导出的类型。特别是,我们希望实现一个主要的类型化,这是一个类型化的所有类型化的一个术语是派生的。主体性保证了我们可以用模块化的方式进行类型分析,也就是说,我们可以分别对两个表达式进行类型检查,然后只根据它们的类型信息对它们的组成进行类型检查。这对于[11]、[2]和[13]的系统是不可能的。确认我们要感谢Sophia Drossopoulou非常详细的评论和有用的建议,以及Mario Coppo的帮助和
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- 新皇冠假日酒店互动系统的的软件测试论文.docx
- 上海空中营业厅系统的软件测试论文.doc
- 网上选课系统的设计与实现论文.doc
- 师生互动网站设计与实现 ()论文.doc
- 学生档案管理系统论文_正文.doc
- 视频会议系统的设计与实现毕业论文.docx
- 基于web的职工电子档案管理系统的设计与实现毕业论文.docx
- 考试辅导网站的设计与实现论文.doc
- 论文 云端图书馆管理系统设计与实现.docx
- 计算机等级考试网上辅导系统的设计与实现论文.doc
- 基于web烘焙坊网站的设计与实现论文.doc
- 论文_基于J2EE的高校后勤采供管理系统开发.docx
- 老龄化社区服务及其系统应用论文.doc
- 论文-java基于SSM的大学生创新创业信息系统.docx
- 猎豹安全浏览器的软件测试论文.doc
- 基于Web的网上书店系统的设计与实现毕业论文.docx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功