理论计算机科学电子笔记116（2005）157-170www.elsevier.com/locate/entcs一种基于静态分析FrancescoLogozzoSTIX-E'colePolytechniqueF-91128 Palaiseau，France摘要在主流的面向对象语言中，子类关系是根据子类型来定义的，也就是说，如果A的类型是B的子类型，则A类是B的子类。 在本文中，这一概念被扩展到考虑任意类的模块化静态分析类获得的属性。 在这样的设置中，子类关系归结为用于分析类的抽象域上的顺序关系。此外，我们展示了这种方法如何产生更多的语义表征的类层次结构，以及它如何可以用于一个有效的模块化分析的多态代码。关键词：抽象解释，继承，面向对象语言，语义，专用应用语言，静态分析1介绍子类化是面向对象语言的主要特征之一。它允许某种形式的增量编程和代码重用。此外，它允许在层次结构中构建代码，以便组成程序（或库）的类子类关系的传统定义是，如果类A的类型是a，则类A是类B的子类B. 换句话说，这意味着属于toA可以在任何需要B对象的上下文中使用，而不会在运行时导致类型错误。然而，子类型关系不足以确保，例如，A的对象不会导致被零除1电子邮件：Francesco.Logoz zo @Po ly tec hn iq ue. fr1571-0661 © 2004 Elsevier B. V.根据CC BY-NC-ND许可证开放访问。doi：10.1016/j.entcs.2004.02.074158F. Logozzo/Electronic Notes in Theoretical Computer Science 116（2005）157O如果B行为子类型试图克服这个问题[7，10]。粗略地说，行为子类型关系保证子类型对象替换父类型对象时不会发生意外行为。基本思想是用合适的正式语言。 这样的属性被称为类的行为类型[7]。然后，行为子类型关系被定义为：属性含义：A是B的子类，如果它的行为类型意味着芽孢这个蕴涵的检查可以通过几种方式完成：手工证明[7]，定理证明器[6]甚至在运行时[10]。但大多数在这个时代，类语义和手工提供的行为类型之间的形式对应被忽视了。在本文中，我们提出了一种基于模块化静态分析的行为子类型化方法[8，9]。其主要思想是在一个合适的抽象域上分析一个类，以推断出一个类不变式以及方法的前置条件和后置条件。我们把A的分析结果一、（一）. Observable是类语义的合理近似，因此它是一种行为型A。A的语义之间的对应关系而O（A）直接由静态分析的可靠性给出该behavioralsubtypinggrelationboilsdownstootheorder±àabstractdomain：给定两个类A和B，nO（A）±NO（B）表示A保留B的行为。换句话说，A是B的行为子类型。我们的行为子类型化方法有几个优点。首先，由于它基于静态分析，因此不需要任何人为干预来注释源代码。 此外，可观察的是确保是一个健全的近似类的语义，它节省了程序员时间一般来说，由于顺序关系是可判定的，因此它可以自动地查过了因此，不需要使用定理证明器或依赖不可靠的方法作为运行时断言监视[10]。此外，抽象解释框架中的行为子类型的定义允许使用标准技术，例如域细化[4]，以系统地提高可观察量的精度。1.1激励实例作为一个例子，让我们考虑图1中的类。他们实施不同种类的袋子。它们有一个向容器添加元素的方法add（e）和addSq（e），以及从容器中提取元素的方法remove（）。但是，它们在处理元素方面有所不同：Queue的remove（）方法返回元素以相同的顺序插入，而Stack，PosStack和SqStack以相反的顺序返回它们PosStackF. Logozzo/Electronic Notes in Theoretical Computer Science 116（2005）157159类 Stack 是s：listofint;init（）：s=[]add（e）：s=e：：sremove（）：lets=e：：lsin s=ls;回路e(a) 堆叠classQueueiss：listofint;init（）：s=[];add（e）：s=s：：eremove（）：lets=e：：lsin s=ls;回路e(b) 队列类PosStack是s：listofint;init（）：s=[]add（e）：s = |e|：：sremove（）：lets=e：：lsin s=ls;回路e(c) PosStack类SqStack是s：listofint;init（）：s=[]add（e）：s = |e|：：saddSq（e）：s=（ee）：：sremove（）：lets=e：：lsins=ls;returne(d) SqStackFig. 1. 论文运行实例和SqStack只包含正整数，并且SqStack有一个进一步的方法，可以插入其参数的平方。为了简单起见，我们不考虑这样的错误，如从空容器中删除元素。1.1.1类层次结构。很明显，这四个阶层有不同的行为。然而，这三者并非完全无关，那么它们之间的关系是什么呢？哪些是可接受的类层次结构？换句话说，什么时候用Queue的对象q替换Stack的对象s是安全的？ 答案取决“安全”的含义。 在类型论中，160F. Logozzo/Electronic Notes in Theoretical Computer Science 116（2005）157×√如果s没有导致运行时类型错误，则s的位置不会导致运行时类型错误。因此，在该示例中，类Stack、PosStack和Queue具有相同的类型，使得例如Stack可以是Queue的子类型，反之亦然。由于addSq方法，只有SqStack必须是Stack、PosStack或Queue的子类型。这是对可能的类层次结构的唯一约束。另一方面，如果上下文要求从包中提取的值与插入值的顺序相反，那么用q替换s就不再 因此，包是一种不同于类型的属性，它导致不同的子类化关系特别是，从这个角度来看，Stack和SqStack表现出相同的属性，因此Stack可以被定义为SqStack的子类。因此，可接受的类层次结构不同于子类型关系。1.1.2系统地细化阶级层次结构。类型和元素顺序都是类的属性，对合适的抽象域s、sayT和S进行了重新分析分别这两个域可以用简化的公式P <$=T<$合并在一起S'[4]。 因此，使用P¯中的更精确的方法，可以推断出更精确的类属性。在本例中，SqStack只能是Stack或PosStack的子类。然而，它仍然可以允许PosStack的Stack子类，反之亦然。这基本上是一个骗局--序列（sequenceofthefacttthatP？）不捕获s中元素的符号。因此，P<$n可以与S<$n抽象域[3]合并，以捕获Su ch的一个特性是：R<$=P<$×S i<$g n。此后，我们在g中得到，Stack永远不能是PosStack的子类，因为它不保留s中的所有元素都是正整数的属性。只有四个类层次结构提供了由R¯提供的适当的结构：在这个类中存在一些琐事关系是身份和图中列出的三二、1.1.3模块化验证。我们工作的最初动机是将行为子类型应用例如，考虑以下引用PosStack类型对象的函数：sqrt（PosStack p）：returnp. remove（）.我们想证明sqrt对于PosStack未来所有可能的子类都是正确的，因为所有这些子类都可以作为参数传递。如果子类不违反PosStack属性，即元素总是F. Logozzo/Electronic Notes in Theoretical Computer Science 116（2005）157161（Ⅲ）⟨⟩Sta，ck，队列是的，队列. . .. .. . . . .、、 、、位置t，a，ck.PosStackSqStack（一）（b）第（1）款StackQueuePosSt，a，ckSqStack（c）第（1）款图 二、AdmissibleclasshierarchiesusinggR？肯定的：第很明显，基于子类型的子类关系太弱，无法确保此属性。然而，如果仅将关系表示为基于R中的prop epertieeencode，如果允许，则PosStack的所有子类都保留所需的不变量。这减少了sqrt从不执行负数的平方根的证明，以PosStack作为参数来证明它。2抽象语义一个类A可以看作是一个三元组F，init，M，其中init是类的构造函数，F是一组字段，M是一组方法。为了一般性，我们假设非类型化的字段和方法。一个类A的具体语义A可以作为一个树的集合给出。粗略地说，每棵树都是A的一个实例的语义，它代表了上下文和对象之间所有可能的交互。对于类语义的正式定义，我们引用读者[8]。给定一个类A，A的静态分析是它的具体语义的近似。在抽象解释框架[3]中，这可以被形式化通过一个抽象的电磁函数A定义在一个抽象的域D′，±A′上。D的元素是对概念的计算表评估SqStack162F. Logozzo/Electronic Notes in Theoretical Computer Science 116（2005）157根据抽象领域Dsabstracttcould-第三部分为逻辑蕴涵。具体域和抽象域之间的对应由伽罗瓦连接<$α，γ<$给出。 具体化-F. Logozzo/Electronic Notes in Theoretical Computer Science 116（2005）157163（Ⅲ）（Ⅲ）（2）O±OI=m）（I）m∈M.我我我0- -我抽象语义的概念，γ（¯A）表示抽象信息关于A的具体语义。它应该是具体语义的一个合理的近似，即Aγ（<$A）。类A的行为类型是A的语义的一个属性。在本文中，我们考虑作为A的静态分析的结果的行为类型，并且我们将它们定义为类的可观察量：O（A）=<$A。将类的行为类型定义为对其源代码的静态分析的结果的优点是，它可以被自动推断。此外，给定两个类A和B，检查是否（A）<$（B）以便验证它们是否处于行为子类型关系中在下文中，我们定义adecidablee关系。2.1一个类的静态分析GivenaclasA=A，F，M，anabstractdomain，P<$，≤P<$，anabs牵引如果方法d ssemantics <$·）∈[M→P<$→P<$]，则其是可通用的分析A以推断类不变式以及方法前提条件和后置条件[9，8]。实际上，让我们考虑以下方程组：I=IH<$.我I0=<$init）它可以使用标准定点迭代技术解决[3]。然后可以证明I是一个类不变式，而Ii是方法的后置条件[9]。通过倒推分析，从后置条件开始：P=<$可判定，则± <$可判定。2.3通过Observables进行现在可以正式地将子类化定义为抽象域元素之间的包含关系：定义2.3LetAandBbettwo-classes，a/o/ 则A是B的子类，A B，相对于OiO（A）±<$O（B）。2我们对同名的方法使用相同的索引例如，P1和Q1是用于h〇1和h〇2的h〇dm〇n的概念的预编码。F. Logozzo/Electronic Notes in Theoretical Computer Science 116（2005）157165⟨ ±⟩ObservethattwhenO'， 与类型抽象域相关联[2]那么上面定义的关系与传统的基于子类型的子类化定义一致[1]。Def. 2.3可以通过下图可视化语义静态分析B，，B（乙）静态O（B）±¯语义分析J（A）O（A）这个图基本上显示了子类化的概念是如何与类的语义联系在一起的。 当A和B的抽象语义比较，A的值意味着B的值。这意味着A精炼Bw.r.t.该过程由ABS跟踪域O？进行编码。这是一个CCORD继承的一般理解是子类是祖先的特化。此外，我们对具体语义的抽象也不作任何假设。特别是，我们不区分历史属性和状态属性，不像[7]，两者只是具体语义的不同抽象。事实上，历史属性对应于跟踪抽象，状态属性对应于状态抽象。2.3.1行为子类型的静态检查我们的方法的主要优点是，子类化关系可以自动检查的编译器：类可观的推导是自动的，它们的包含是可判定的。因此，编译器只能接受保留父行为的子类。例如，这符合Ei Ejel子类化机制的精神[10]。然而，Eiel的规范要求在运行时检查祖先不变量的保存。一个有趣的未来的工作可以是我们的工作的子类化到Ei el语言的扩展。2.3.2模块化验证。拥有拒绝子类定义的编译器的一个主要优点，不保留父属性，是它使多态函数的模分析形式成为可能。考虑下面的多态函数f，它引用类型B的对象：f（B b） ：...... B. m（v）.. ..166F. Logozzo/Electronic Notes in Theoretical Computer Science 116（2005）157∈（Ⅲ）（Ⅲ）⟨≤⟩现在，请给我解释一下，ab stra ctdomain.如果使用B执行分析，则调用b.m（v）解析为对B的方法m B的调用。有了B的一个可观测量，mB的前置条件Q和后置条件J就可以用于分析，从而使方法你不需要再分析一遍。Thus，if'vP′是f的平均值，变量v所取的具体值，<$v≤<$Q=<$<$mB（<$v）≤<$J。这种分析的结果对所有调用f（a）都是有效的，其中a是类A的实例。这可以如下所示如果A≠B，则O（A）±O（B）. 通过对A的mA的序关系的定义，mA：P→I，其中Q≤P且I≤J。所以：<$v≤<$Q≤<$P=<$<$mA（<$v）≤ <$II≤<$J。因此J是方法mA的语义的可靠近似。 事实上，我们已经证明了以下定理：定理2.4设A和B是两个类，使得A <$B. 设mB是B的一个方法，mA是属于A的同名方法.设mB：Q→J，mA：P→I。然后v∈P<$。<$v≤<$Q=<$mA）（<$v）≤<$J。因此，使用超类对多态代码的分析足以说明结果对所有子类都有效。因此，没有必要为B的每个子类重新分析代码。2.3.3域名优化。在抽象解释框架中形式化行为子类型的另一个优点是，可以应用众所周知的抽象域精化技术[4，5]来提高可观察量的精度。因此有更多的细粒度类层次结构。特别是，使用约简乘积对于细化所捕获的属性的精度是实用的。一个可观察的抽象域至少必须封装抽象域T<$的类型。在其他方面，我们有一个更进一步的规则，abstractdomain需要捕获非类型属性，例如符号场的价值观。 那么可观测的领域就可以建立在从而得出两个方程的乘积：P<$=T<$×D<$。Asacon sequence，fromma抽象解释中的众所周知的结果（CFR.日 10.1.0.2），因此，P是一个比类型更重要的领域，因此，检索关系比子类型关系更精确。F. Logozzo/Electronic Notes in Theoretical Computer Science 116（2005）157167、、....... . T<$，T<$，，. . .. .. . . .直、、、、、、、、反向. . . .. . .. .POS 、、、、、、、、、、、、neg空⊥¯(a) ThebstractdomainS⊥¯(b) 抽象域Si<$gn图三. 表示元素顺序及其符号的、、、、，，、、、、，，直的，，，，、、、、位置，，，，，，，，，，，阴性，，，、、，倒过来、、，，，，，，，，，，，，，，，，，，直线，位置直型，阴性反向，位置反向，负向，，，，，，、，，，，，，空⊥¯图 四、BstractdomainH<$=S<$×Si<$gn3实施例的应用在本节中，我们将说明上一节的定义如何适用于1.1节的例子。首先，我们展示了当用类型实例化下划线抽象域时，如何将抽象域的定义简化为传统的基于子类型的定义。众所周知，类型可以被看作是一种抽象的解释[2]。我们callT<$对应的抽象域3.然后，如果我们实例化def。3.实际上，在所引用的论文中，作者考虑了与每个系统项目相对应的几个抽象域。TThwesider中最常见的是Church/Curry monotypes。.、、、168F. Logozzo/Electronic Notes in Theoretical Computer Science 116（2005）157O¯Ð2.3利用abs域T′，我们得到：时间复杂度：O（Stack）=O（Queue）=O（PosStack）={ints：listof ints，{init：void→void;add：int→void;remove：void →int}}，O（SqStack）={ints：listof intn，{init：void→void;add，addSq：int→void;remove：void→int}}因此，对子类关系定义的唯一限制是，SqStack不能是其他三个关系中任何一个的祖先。这是因为O（SqStack）是O（Stack）[1]的子类型。使用图3（a）中的抽象域可以获得不同的子类化关系，其直观含义是考虑列表的元素是插入在头部还是尾部位置。值得注意的是，这个元素是一个历史性的过程。在这种情况下，他使用S are获得的值：O（Stack）=O（PosStack）={\displaystyle\mathbb{reverse\mathbb}}，{init：→empty;add：reverse→reverse;remove：reverse→reverse}}，O（SqStack）={ints：reverse}，{intt：i}→empty;add，addSq：reverse→reverse;remove：reverse→reverse}}，O（Queue）={{s：strai ght}，{init：str}→empty;add：straight→straight;删除：直→直}}。在最后一个例子中，例如队列和堆栈可能永远不会在O（Queue）±<$O（Stack）n或O（Stack）±<$（Queue）之间建立关系。 然而，没有什么可以避免使用StackPosStack，因为S不捕获s中元素的符号，而只是它们被插入的顺序。使用图1的域S n，可以重新定义Reforeit it。3（b）款。我不认为我们能在他的地盘上图 4、这是减少根据这两个字的形式：H<$=S<$×S i<$gn。这两个方面的结果都很好，F. Logozzo/Electronic Notes in Theoretical Computer Science 116（2005）157169类是：O（Stack）={s：reverse，{init：i}→empty;add：reverse→reverse;remove：reverse→reverse}}，O（PosStack）={s：revererse，pos，{init：→empty;add：reverse，pos→reverse，pos;remove：reverse，pos→reverse，pos}}.检查堆栈PosStack是例行程序。最终，子类rela-这给图中的类层次结构带来了麻烦 2是在考虑了由一个bstractdomainR<$=T<$×H<$=T<$×S<$×S i<$g n所引起的特性的情况下得到的。4结论和今后的工作在这项工作中，我们提出了一种方法的行为子类型的基础上模块化的静态分析类的来源特别地，我们已经展示了如何根据底层抽象域上的顺序来定义子类化关系与传统的子类型和行为子类型相比，我们的方法有几个优点：类行为类型是自动推断的，子类型是可判定的，它更具语义特征，并且它是在抽象解释框架中制定的，因此可以使用关于抽象域的组合和细化的众所周知的技术。此外，在这种情况下，分析并验证多态代码的问题要简单得多。事实上，由于每个子类扩展都保留了祖先不变量，因此一旦定义了新的子类，就不需要重新分析代码然而，一个开放的问题是用于推断的可观测值的抽象域的选择对于一般目的的面向对象语言来说，很难预先确定子类希望保留的属性。类型已经被证明是有效的，因此一个抽象的可观察域必须至少包括它们。考虑到其他运行时错误，可以考虑继续朝这个方向例如被零除、超空指针或空指针解引用，使得给定类，确保其所有子类不会引入运行时错误。另一方面，我们相信，我们的方法可以有效的设计和特定问题的面向对象语言的发展作为一个例子，让我们考虑一种智能卡编程语言。在这种情况下，安全性是很重要的，因此希望的属性是，如果子类不泄露秘密，那么子类也不泄露秘密。在这种情况下，我们可以使用170F. Logozzo/Electronic Notes in Theoretical Computer Science 116（2005）157能够捕获安全性和信息流特性的可观察域。嵌入式系统是另一个可以利用更受约束的子类关系的领域。事实上，在这样一个领域，我们可以立即看到拥有一种语言的好处，这种语言可以确保子类不会违反超类的空间和时间约束。在未来，我们计划扩展目前的工作，以应付多重继承和Java接口，太。第一个扩展是非常直接的。接口的情况更加困难：接口本质上是一种类型规范，尽管大多数时候这种规范表达不够。以Java线程为例，它可以使用Runnable接口或Thread类来定义。在这两种情况下的类实现一个线程需要定义一个方法运行。那么什么是实现Runnable或扩展Thread的类之间的区别？直觉是，在这两种情况下，类的行为类型是相同的，我们计划定义一种规范语言，以处理非类型属性，从而能够表达接口所施加的属性。然后我们将使用它来证明一个类正确地实现了一个接口。致谢我们要感谢A。Cortesi，J. Feret，C. Hymans，A. Simon和E.厄普顿引用[1] L.卡德利 多重继承的语义。 在《数据类型的语义学》中，LNCS，第51-67页。 Springer-Verlag，1984.[2] P. Cousot。类型作为抽象的解释，邀请文件。在POPLACM Press，January 1997.[3] P. Cousot和R.库索抽象解释：一种统一的格模型，用于通过构造或近似定点来静态分析程序。在POPLACM Press，January 1977.[4] P. Cousot和R.库索程序分析框架的系统设计。在POPLACM Press，January 1979.[5] R. Giacobazzi，F. Ranzato和F.斯科扎里 完成抽象的解释。 Journal of the ACM，47（2）：361[6] G. T. Leavens和K. K. 达拉 概念 的 行为 分型 和 一 草图 扩展到基于组件的系统。在基于代理的系统的基础中，第6章，第113-135页。剑桥大学出版社，2000年。[7] B. H. Liskov和J.M.翼子类型的行为概念。TOPLAS，16（6）：1811F. Logozzo/Electronic Notes in Theoretical Computer Science 116（2005）157171[8] F.洛格佐面向对象语言的类级模块化分析。 在SASSpringer-Verlag，2003年6月[9] F.洛格佐类不变量的自动推理。在VMCAISpringer-Verlag，2004年1月。[10] B.迈耶Ei Eel：语言。普伦蒂斯·霍尔1992年
我的内容管理
展开
