没有合适的资源?快使用搜索试试~ 我知道了~
162理论计算机科学电子笔记45(2001)网址:http://www.elsevier.nl/locate/entcs/volume45.html12页关于静态语义的提取约翰·汉南宾夕法尼亚州立大学计算机科学与工程系University Park,PA 16802,USA摘要我们研究的问题,自动提取一个静态语义从语言的语义定义。 传统的方法需要手动构建静态和动态语义,然后证明两者是一致的。随着语言变得越来越复杂,静态分析也变得越来越复杂,一致性证明通常具有挑战性。 我们需要找到自动构建可证明正确的静态分析的技术。1介绍编程语言设计和实现的常见方法是识别语言的静态(编译时)和动态(运行时)操作或属性,然后构建静态语义和动态语义。即使正式的语言定义不包含这样的显式阶段,这些语言的编译器几乎总是做这样的区分,在生成代码之前执行语义分析。一个简单的编译器设计原则可以概括为以下几个阶段:(i) 词法分析(ii) 语义分析(iii) 代码生成或者,上面提到的语言设计方法可以总结为:(i) 静态语义(ii) 动态语义1这项工作得到了NSF奖#CCR-9900918的部分支持2电子邮件地址:hannan@cse.psu.edu2000年1月,出版社dbyElsevierScienceB。 V. 在CC BY-NC-ND许可下开放访问。汉南163这两个阶段对应于编译器的后两个阶段。正如代码生成使用由语义分析提供的信息一样,动态语义可以使用由静态语义提供的信息或属性在强类型语言中,此信息由良好类型的结果组成,该结果允许动态语义避免任何类型检查。由于类型在大多数静态分析中扮演着重要的角色,因此语言定义的静态阶段通常被称为类型系统。类型表征表达式的含义。为了确保静态语义向动态语义提供有效信息,需要某种该结果表明表达式更一般地说,我们可以想象描述程序属性而不是类型。这些属性可能包括安全性、资源使用或其他属性。我们描述这些属性的目的可能是提供编译时分析,以确保程序的某些运行时行为满足这些属性。例如,我们可以描述一个涉及优先级和安全信息访问级别静态分析应该告诉我们,在运行时,不会发生安全违规同样,我们必须提供一个一致性结果来证明静态分析的正确性:静态分析所做的断言在动态语义中被验证/接受。随着性质变得越来越复杂,分析变得越来越复杂,证明这种一致性越来越困难。将语义和编译器分为两个阶段提供了两个优点:效率和可预测性。通过在编译时执行一次测试和操作,我们可以避免在运行时执行它们强类型语言的静态类型检查就是一个很好的例子。通过在编译时建立程序的属性,我们对程序在运行时的行为有一些同样,静态类型检查可以确保程序不会生成任何运行时类型错误。一般来说,这些优点超过了必须构建两个不同阶段并证明它们正确的缺点。然而,随着我们定义具有更复杂特征的语言,并试图通过静态分析提供更多信息,定义这些分析并证明它们与动态语义一致的难度将会增加。另一种方法是定义一个包含静态和动态检查的语义。 这通常比定义两个语义更容易,部分原因是属性的检查可以在属性明显时完成。例如,我们不提供静态类型检查,而是使用动态类型检查。然后我们可能只检查值是否具有适当的类型。当然,这可能导致不同的语义。观察这种组合语义的一种方法是,它操纵语法对象(编译时可用)和语义对象(汉南164运行时间)。从这样的语义开始,我们想考虑将这种语义分成两部分的任务:传统的静态和动态语义,这样我们就可以保证两者之间的一致性。2分段语义从语义规范构造类型检查器的想法并不新鲜,尽管在这方面做的工作很少。1991年,尼尔·琼斯(Neil Jones)考虑了这个问题[4]。他专注于类型系统,而不是更一般的静态属性问题。但是由于类型是当今使用的最重要的静态属性,因此从它们开始是明智的。由于从语义构造类型检查器的问题是引入计算阶段的问题之一-编译时和运行时-很自然地考虑传统的阶段转换[5],特别是部分求值,作为分离语义的静态和动态部分的技术。为此,Jones回顾了一些讨论部分求值的标准技术。首先,我们应该确切地了解问题是什么给定一个操作语法对象和语义对象的操作语义,我们希望(自动)分离编译时操作和运行时操作。我们特别关注错误检查。让L成为一种编程语言。则[p]]Lv是运行L- 在输入v上编程p。一个S语言的解释器int的编写在L中有以下性质:[[int]]L(source,input)=[source]]SinputS程序中的错误是通过int中的检错码来实现的。给定此设置,我们可以描述静态语义:静态语义是一种机制,用于检测给定的S程序是否可以导致int在某些输入上执行静态错误的概念很有趣。我们是否将静态语义学作为静态错误的定义?或者,是否存在某种静态错误的其他定义,从这个定义中我们可以证明静态语义的定义是合理和完整的?进一步考虑这一点,我们看到,我们确实必须解决两个一般问题:(i) 确定语义的静态属性(ii) 构造一个捕获这些属性的静态语义静态语义是否定义静态错误的问题类似于现有的类型系统观点(i) 规定性(教会):类型是预先定义的条件,以确保意义;(ii) 描述性(Curry):类型描述程序操作的值汉南165迟到了我们不关心这些观点的分歧相反,我们将考虑包含类型的描述性使用的语义,并尝试构建使用规定性视图的语义特别是,我们希望从给定的语义构造一个类型检查器更一般地说,我们希望在语言的定义(语义)中,类型检查阶段发生在评估阶段之前按照Jones [4],我们可以使用称为部分求值的程序专门化概念来使静态错误的概念更加假设我们有一个部分求值器混合。回想一下,部分求值器接受程序p和程序输入s的一部分mix(p,s)(d)=p(s,d)部分求值将计算分为两部分,通常描述为静态部分(计算混合(p,s))和动态部分(剩余程序对d的应用)。我们感兴趣的是,当程序是一个定义解释器时在这种情况下,静态输入是要解释的源程序(动态输入是源程序的输入),并且上述等式可以重写为:intsort=[sort]]L(int,sort)如果解释器包含错误检查(包括类型检查),那么我们可能希望部分求值执行这些测试,并且剩余程序ps=mix(p,s)不包含这样的错误检查。在这种情况下,我们已经解决了分级类型检查的问题,尽管没有构造一个显式类型系统不幸的是,这个想法除以零),从任何时候都发生在程序中。这种方法出现的问题是,我们无法区分静态和动态误差。另一个问题是,这种方法一次处理一个程序我们不能保证以这种方式处理的每个源程序都会产生不包含错误检查的残留程序我们无法确定我们的语言是否是强类型的(这里的意思是所有的静态错误测试都可以通过部分求值来为了解决区分静态错误和动态错误的问题,Jones观察到静态错误应该是只能由部分求值器(对int进行操作)执行的错误,并且它的代码永远不会在剩余程序中生成。这种性质可以通过结合时间分析(BTA)来检测。BTA将每个基本函数调用或数据构造函数划分为两个类之一:可以在程序专门化时计算的类汉南166⇒以及那些必须在运行时执行的(由专用程序ps)[4]。因此,当我们将源程序视为静态输入时,识别解释器中的静态错误的问题就简化为Jones演示了如何将BTA与部分求值相结合,用于识别静态属性(类型检查),并将它们与程序的求值分开执行。3另一种方法使用部分求值来指定静态语义的一个基本限制是,我们没有显式地构造类型系统或静态操作的其他相反,一般的部分求值器隐式地执行这些操作。部分求值的另一种替代方法是另一种称为通道分离的分级转换[5]。回想一下,分段转换通常是一种基于数据可用性分离计算阶段的方法,最常见的应用程序是从解释器开发编译器。部分求值可能是最广为人知和使用的分段转换,但也存在其他转换,包括传统的编译器优化(例如,恒定折叠)和通过分离。考虑通过分段转换解决的一般问题:给定一个具有两个输入x,y的程序p,将p(x,y)执行的计算分段为两个连续的阶段:• 一个以x为输入• 一个以y作为输入部分求值通过单个程序混合来实现,使得如果mix(p,x)=px,则对于所有输入x和y,p(x,y)=px(y)。在上面的例子中,p是一个解释器,x是要解释的源程序,y是程序的输入遍数分离需要一种技术来构造两个新程序,p1和p2,使得对于所有输入x和y,p(x,y)=p2(p1(x),y)。在这种情况下,如果p是一个解释器,x是一个源程序,那么我们可能会期望p1是一个编译器,p2是编译器目标语言的求值器通道分离的缺点是,我们没有一个通用的方法来采取一个任意的程序p,并构造所需的新程序p1和p2,使p1执行一些非平凡的计算。(我们总是可以让p1是恒等函数,让p2=p。任意函数太一般化了,而且可能划分成两个函数的数量太多,以至于无法支持执行通道分离的简单方法在以前的工作中,我们通过考虑解释器的受限形式来解决这个问题,即抽象机器[2]。在这项工作中,一个抽象的机器是由一组重写规则的s和sJ表示的机器状态。通常,机器状态由程序和数据组成机器的每个规则指定给定程序状态如何操作数据,汉南167(e1e2);C,(ρ;L,S)λe; C,(ρ; L,S)α-β-C,(L,{ρ,λ e};S)C,((ρ; v); L,S)C,(L,v;S)(e + 1); C,((ρ; v); L,S)环戊烯; C,(ρ;L,S)ap;C,(L,v;{ρ,λ e};S)图1.一、CLS机器产生新的程序状态。在这个系统中重写是特别简单的,因为我们只允许在顶层重写,即,整个学期。这种简单的计算形式是富有表现力的,但也非常便于推理,因为我们只需要考虑一种计算形式(机器状态重写)作为一个例子,我们研究了CLS机[3],它是Landin的SECD机[6]的一个变体这是一台在lambda演算上执行按值调用归约的机器机器状态由三重C,L,S组成,代码- 要计算的表达式序列L- 环境序列S- 中间值的堆栈该语言的术语由以下语法给出e::= 1 |e +1 |λe|ee|AP代码或程序是由一系列术语给出的。环境是一系列价值观。值只是由一个术语和一个环境组成的闭包堆栈也是一个值列表机器的规则如图1所示。我们的通道分离技术背后的想法是考虑抽象的MA。有形式规则的脊s,d其中s和SJ表示静态(编译时)组件,d和DJ表示动态(运行时)组件。对于CLS机,我们把C分量作为静态部分,把对(L,S)作为动态部分。然后,我们将每个规则分解为两个部分:一个只对静态部分进行操作,另一个对动态部分进行操作例如,以下形式的规则s,d会被分解成一对规则s,Y项s1和s2的构造是为了确保重写在锁中进行汉南168ev(e1e2);Cpush;ev(e1);ev(e2);ap;Cev(λ e);Clam(ev(e);nil);Cev(1);Cev(e+ 1);Csnd;ev(e);C推;C,ρ;L,S(lamCJ);C,ρ;L,Sfst;C,(v,ρ);L,Ssnd;C,(v,ρ);L,Sap;C,L,v;(ρ,lamCJ); S图二.分离的机器与原始系统同步应用这个简单的转换会产生两组重写规则(抽象机器):• 编译器(引入一种新的机器语言)• 新语言的口译员这些新规则的构建是在原有规则的基础上进行的因为规则有如此简单的结构,我们可以识别出一些不同的情况,这些情况会产生元规则-关于如何构建新规则的规则这些元规则基于s、d、sJ和dJ之间的依赖关系。特别地,我们考虑如何从s和d构造项SJ和DJ。将这些元规则应用于CLS机器,我们得到图2中给出新的机器语言由指令push、lam、fst和snd组成。这些指令是由元规则生成的,而赋予它们意义的规则为这种新的抽象机器语言提供了定义由此产生的机器可以证明是正确的关于原来的有趣的是,这个新机器本质上是分类自动机[1]。编译器将lambda术语的结构分解为更简单的组件(新的机器语言),因此我们看到原始术语结构的遍历和术语的实际评估之间存在分离4静态语义传递分离可以用来分离抽象机器中固有的静态语义我们探讨这个想法,考虑所涉及的问题,并给出一个例子,通过一些逆向工程。必须立即考虑三个问题:• 我们能否识别操作语义的适当形式?甚至汉南169虽然我们把自己限制在抽象机器上,但我们仍然希望理解最好的形式,使我们能够分离出静态语义。• 我们能识别静态错误吗?一个更普遍的问题是简单地识别语义的静态属性。这类似于定义什么是静态误差。• 我们能否确定一组分解静态和动态属性的元规则?我们之前使用通道分离的工作确定了一小部分元规则,用于构建新的重写规则。这些元规则通过正确性证明得到了证明。我们想为当前的问题找到一个通用的集合我们对这些问题不作任何明确的回答相反,我们将通过一个例子来证明传递分离的思想可以应用于分离静态语义的问题。我们首先修改为我们的语言提供语义的抽象机器CLS机器是无类型的机器:机器中不进行类型检查;术语没有关联的类型。为了提供尽可能多的信息,我们最初假设术语是显式类型化的:每个术语(和子术语)都显式地标记了其类型(写为上标)。虽然这可能是不现实的(因为它假设一些预先存在的类型系统插入这些类型),但这个假设是一个有用的起点,允许我们看到如何分离静态和动态操作。我们修改CLS机器来处理这些显式类型的术语,并包括某些类型检查。特别地,机器检查函数调用中的实参的值是否与绑定到它的形参具有相同的类型机器还检查变量的值(在环境中找到)与变量的类型相同图3给出了改进后的机器环境δ将变量(de Bruijn索引)映射到类型化值(即,值及其类型)。我们可以通过做一些简单的语法修改来重组这台机器具体来说,我们将δ分解为一对环境:Γ(将变量映射到类型)和ρ(将变量映射到值)。图4中给出了最终的机器我们假定我们要提取的静态属性是表达式和类型的关联。自动识别此属性并以使此属性明显的方式构造机器是一个具有挑战性的但是一旦我们有了图4中的机器,我们就可以考虑如何实现我们的目标。最终,我们的目标不是简单地产生静态语义,而是提供一些静态检查,当满足时指示不存在某些类型的运行时错误。因为我们的目标是避免抽象机器中的错误状态,所以我们将尝试识别永远不会导致错误状态的状态。幸运的是,我们在机器中有明确的错误状态描述我们如何知道一个特定的机器状态是否会导致错误状态?正向推理汉南170⇒(m n)τ;C,(δ;L,S)λ(λ m)τ1→τ2; C,(δ; L,S)δ-C,(L,{δ,λ m}τ1→τ2;S)1τ; C,((δ; vτ); L,S)α-β-C,(L,v;S)τ1τ;C,((δ;vτ J) ;L,S)当τ1=τJ时,n(m + 1)τ; C,((δ; v); L,S)mτ; C,(δ;L,S)C,(L,vτ2;{δ,λ m}τ2→τ; S)λmτ; C,((δ;vτ2);L,S)ap;C,(L,v;{δ,λ m};S)否则为图3.第三章。Explicit Typed Machine<$[r,(m n)]τ;C,ρ;L,S<$[r,m]τ2→τ;[r,n]τ2;ap;C,ρ;ρ;L,S<$λ [r,λ m] τ1→τ2; C,ρ; L,S C,L,{ρ,[Γ,λ m] τ1→τ2}; S<$[(r;τ),1]τ;C,(ρ;v)L,S<$C,L,v;S<$τ[(r;τJ),1]τ;C,(ρ;v)L,S当τj=τJ时,R或Ri<$[(r;τJ),(m+ 1)]τ;C,(ρ;v)L,S<$[r,m]τ;C,ρ L,S<$ap;C,L,vτ2;{ρ,[Γ,λ m]τ2→τ};SC,L,v;{ρ,Γ,λ m};否则S误差见图4。重组的机器在这里似乎没有多大帮助,但反向推理却有帮助。如果一台机器处于安全状态,那么它之前的状态会导致该安全状态。我们可以给安全状态下一个归纳的定义(i) 任何一个最终的状态都是安全的状态;(ii) 如果s是一个安全状态,并且sJs是机器中某个规则的instance,那么sJ也是一个安全状态。注意,条件ii要求机器是确定性的:从状态sJ到状态s的唯一可能步骤必须是。这种条件是必须发展的正式理论的一部分,以正式证明我们所采取的步骤。汉南171⇒[r,m]τ2→τ[r,n]τ2[Γ,(m n)]τ[Γ,λm]τ1→τ2[Γ,λ m]τ1→τ2[(Γ;τ),1]τ[Γ,m]τ[(r;τJ),(m+1)]τ[(Γ;τ2),m]τ[Γ,λ m]τ1→τ2图五、静态类型检查的推理规则用来构建静态语义的方法现在我们有了确定安全状态的一般策略,我们想提取静态属性。由于我们希望避免的类型错误是基于与表达式相关联的类型的属性,因此我们可以将错误状态理解为不正确的类型与表达式相关联的状态。这一观察使我们得到了一个简单的元规则,用于为静态语义构建推理规则:对于机器中的每个重写规则s sJ,令A和AJ分别是s和sJ中出现的静态属性的集合如果A不是单例集,则方法失败;否则构造推理规则AJA如果我们将这个元规则应用于图4中的规则,那么我们得到图5中的推理规则第二条规则没有提供任何信息,因此可以将其删除。剩下的规则是检查lambda演算类型的传统规则虽然我们已经非正式地证明了这些规则的构造,认为原始重写规则提供了足够的信息来提取推理规则,但我们还没有提供正式的证据来证明推理系统提供了防止运行时类型错误发生的安全性。我们也没有-汉南172抽象机器的一般形式,这种技术适用。尽管如此,我们还是希望这个例子能对从操作语义中提取静态语义的问题有所启发。5进一步的工作和结论上一节中的类型是从哪里来的?我们假设术语已经附加了它们的类型,并且语义使用这些类型来执行检查。这些假设对我们有利,帮助我们实现了构建类型系统的目标作为第一步,我们认为这是公平的,为我们提供尽可能多的信息有人可能会说,我们的例子实际上是证明类型可靠性的一部分,告诉我们可以在运行时擦除类型但是这些类型首先是从哪里来的呢?一个更现实的起点,我们的工作将是原来的CLS机。它不包含类型。错误条件是隐式的:如果机器状态与某个规则的左侧不匹配,则发生错误(除非机器处于最终状态)。一个更熟悉的起点可能是像Scheme这样的Scheme没有表达式的静态类型,但它有值的动态类型检查。例如,给定一个应用程序(e1e2),Scheme只要求e1的值是一个函数(有一个参数)。没有检查e2的值的类型是否匹配此函数的参数的类型。假设我们的目标是从Scheme这样的语言开始,然后添加静态检查以确保某些类型的运行时错误不会发生。从本质上讲,我们如何从Scheme这样的语言(具有动态类型的值)到ML这样的语言(具有静态类型的表达式)?我们认为,类似于上一节中提出的技术可能会起作用。我们从Scheme使用的非常简单的类型概念开始然后,我们这将比上一个例子中的更复杂。同样,我们必须使用重写规则向后工作,认为安全状态来自安全状态。我们认为这种方法值得研究,因为它可能会导致一些有趣的结果。总之,Neil Jones对类型系统和静态分析的研究为研究提取静态语义的问题提供了一个起点关键问题的识别,包括静态错误的定义,有助于为当前和未来的工作铺平道路。引用[1] Eschineau,G.,P. - L. Curien和M. Mauny,分类抽象机,编程科学8(1987),pp. 173-202.[2] Hannan,J.,抽象机器的阶段转换,在:P. Hudak和汉南173N. Jones,editors,Proceedings of the ACM SIGPLAN Symposium on PartialEvaluation and Semantics Based Program Manipulation(1991),pp.130-141。[3] Hannan, J. 和 D. Miller , From operational semantics to abstract machines ,Mathematical Structures in Computer Science2(1992). 415-459,出现在1990年ACMLisp和函数式编程会议的特刊中。[4] 琼斯,N.,静态语义,类型和绑定时间分析,理论计算机科学90(1991),pp。95-118,也出现在图像编程,编辑。D. Bjørner和V. Kotov,北荷兰。[5] 约林大学和W. Scherlis,编译器和阶段转换,在:第十三届ACM程序设计语言原理研讨会,1986年,pp。86比96[6] 兰丁,P.J.,表达式的机械求值,计算机杂志6(1964),pp. 308-320
下载后可阅读完整内容,剩余1页未读,立即下载
![pptx](https://img-home.csdnimg.cn/images/20210720083543.png)
![application/octet-stream](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://profile-avatar.csdnimg.cn/default.jpg!1)
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
我的内容管理 收起
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
会员权益专享
最新资源
- 藏经阁-应用多活技术白皮书-40.pdf
- 藏经阁-阿里云计算巢加速器:让优秀的软件生于云、长于云-90.pdf
- 藏经阁-玩转AIGC与应用部署-92.pdf
- 藏经阁-程序员面试宝典-193.pdf
- 藏经阁-Hologres 一站式实时数仓客户案例集-223.pdf
- 藏经阁-一站式结构化数据存储Tablestore实战手册-206.pdf
- 藏经阁-阿里云产品九月刊-223.pdf
- 藏经阁-2023云原生实战案例集-179.pdf
- 藏经阁-Nacos架构&原理-326.pdf
- ZTE电联中频一张网配置指导书
- 企业级数据治理之数据安全追溯
- MISRA-C 2012-中文翻译版.pdf
- 藏经阁-《多媒体行业质量成本优化及容灾方案白皮书》-37.pdf
- 藏经阁-浅谈阿里云通用产品线Serverless的小小演化史-23.pdf
- 藏经阁-冬季实战营第一期:从零到一上手玩转云服务器-44.pdf
- 藏经阁-云上自动化运维宝典-248.pdf
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)