理论计算机科学电子笔记190（2007）67-83www.elsevier.com/locate/entcsJava字节码E. 阿尔伯特1P. 阿里纳斯1S. Genaim2 G. 普埃布拉2D。Zanardini21DSIC，马德里康普顿斯大学，{elvira，puri}@ sip.ucm.es2马德里技术大学，{german，samir，damiano}@ clip.dia.fi.upm.es摘要最近，我们提出了一个通用的框架，Java字节码的成本分析，可用于衡量资源的使用。这种分析在编译时生成成本关系，将程序的成本定义为输入数据大小的函数。 本文的目的是评估这种成本分析的实用性，通过实验评估的原型分析仪在Ciao实现。 有了这个目标，我们近似的计算复杂性的一组选定的基准，包括已被用来评估现有的成本分析在其他编程范式，和其他基准，说明面向对象的功能的知名算法。在我们的评估中，我们首先研究可 以 自动 求 解 生 成的 成 本 关 系。 我 们 的 实验 表 明 ， 在 某些 情 况 下 ， 推断 的 成 本 关系 可 以 自 动解 决 使 用Mathematica系统，而在其他情况下，一些事先的操作是需要的方程是可解的。此外，我们通过实验评估了分析过程的不同阶段的运行时间。总的来说，我们相信我们的实验表明，我们的成本分析的效率是可以接受的，并且所获得的成本关系在实践中是有用的，因为至少在我们的实验中，有可能得到封闭形式的解决方案。关键词：成本分析，Java字节码，成本关系，递归方程，复杂性。1动机拥有关于一段代码的执行成本的信息[17，11]是非常有用的;在许多情况下，这方面对于在相同规范的不同实现中进行选择至关重要。此外，这可以允许证明应用程序的执行满足指定的资源消耗约束[10]。成本分析在移动代码的环境中也非常有用，因为资源非常有限，我们可能希望根据代码的成本来接受或拒绝代码。在极限情况下，接受没有成本保证的移动代码[6，12]可能是拒绝服务攻击的来源，因为执行可能非常（或无限）昂贵。重要的是要注意，在上述情况下不太可能访问源代码;相反，我们只能直接处理编译后的1571-0661 © 2007 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2007.02.06168E. Albert等人理论计算机科学电子笔记190（2007）67代码. Java字节码[14]正在成为最流行的移动代码格式之一。因此，需要对Java字节码进行精确的成本分析总的来说，成本分析远非微不足道;程序员需要大量的专业知识才能直觉地知道哪些实现技术可能会导致更有效的程序。当我们处理低级的、面向对象的语言（如Java字节码）时，这一点尤其困难。从某种意义上说，Java字节码的自动化成本分析并不总是能够成功地给出有意义的结果，特别是对于非常复杂的代码。因此，关于我们最近提出的成本分析框架的主要问题之一[5]，我们在目前的工作中进行了评估，生成的成本关系可以自动简化为封闭形式的解决方案，当考虑传统上用于复杂性分析的简单成本模型时，它会计算执行步骤（字节码指令）的数量为了找到封闭形式的解决方案，我们使用最先进的递归方程求解器Mathematica系统[1]。我们研究，一系列的代表性的基准，是否可以通过使用提供的RSolve查询生成的成本关系解决。当这是不直接可能的，我们提出的转换，使生成的方程可解。至于输入语言，和[5]一样，我们考虑Java字节码的一个子集，它不包括动态类加载、反射或浮点运算等特性。 实际上，这个子集基本上对应于CLDC，它是Java的一个变体，用于嵌入式行业，介于JavaCard和Java标准版之间。我们相信CLDC是一个很好的选择，因为它具有真正语言的所有特征：真正的内存管理、面向对象等，同时从分析的角度来看，它比Java标准版更易于管理。此外，CLDC被业界广泛接受为可下载代码的运行时环境：移动电话（MIDP），机顶盒（JSR 242）和智能卡终端设备（STIP）。通过规模推断进行成本分析的工作主要在逻辑[11]和函数[16]编程中进行。德布雷和林函数语言[15，21]中的一些最近的工作涉及使用类型系统来研究大小关系和推断成本方程。 在这两种情况下，没有深入讨论获得成本关系的封闭形式的问题，也没有提供解决方案的例子（尽管给出了基本数学理论的参考）。在[8]中，提出了一种静态分析方法，用于过度近似源Java类面向对象程序分配的内存量。这里，对象大小被表示为符号表达式。这种方法不涉及成本方程本文其余部分的结构如下。 秒 2概述 我们的Java字节码成本分析框架[5]。然后，我们研究了三种基准。节中3，我们分析了一些著名的递归过程，由于它们的结构，引起的成本关系，可以很容易地处理E. Albert等人理论计算机科学电子笔记190（2007）6769输入Java字节码中间递归表示第0章：加载0J Jfiba（n）← BC（Block 0），（fib 1（n，s 0）; fib 2（n，s0））。Jfib 1（n，s 0）← guard（ifeq（s 0）），BC（Block 1），fib 5（n）.fib2（n，s 0）←guard（ifne（s 0）），BC（Block 2），（fib 3（nJ，sJ，sJ）; fib 4（nJ，sJ，sJ））。0101Jfib 3（n，s 0，s 1）← guard（if icmpeq（s 0，s 1）），BC（Block 3），fib 5（n）.fib4（n，s 0，s 1）←guard（if icmpne（s 0，s 1）），BC（Block 4），fibb（nJ），fibc（ nJJ）. fib5（n）← BC（Block5）.一曰：IFEQ 9第四章：加载0第五章：iconst 1第六章：如果ICMPNE 11第九章：iconst 110：irereturn11：iload 012：iconst 1尺寸关系fiba（n）›→fib1（nJ，s 0），{nJ=n，s 0=n}J Jfib0（n）›→fib 2（n，s 0），{n=n，s 0=n}J Jfib1（n，s 0）›→fib 5（n），{s 0=0，n=n}JJJfib2（n，s 0）›→fib 3（n，s0，s1），J J J{s0/=0，s0=n，s1=1，n=n}JJJ J J J Jfib2（n，s0）›→fib4（n0，s0，s1），{s0=/0，s0=n，s1=1，n=n}J Jfib3（n，s 0，s 1）›→fib 5（n），{s 0=s 1，n=n}fib4（n，s 0，s 1）›→fibb（nJ），{s 0/=s 1，nJ=n−1}fib4（n，s 0，s 1）›→fibc（nJ），{s 0/=s 1，nJ=n−2}13：isub14：invokestatic #2;//方法fib：（I）I17：iload 0第18章：我的天19：isub20：invokestatic #2;//方法fib：（I）I23：iadd第24章：我的天产出成本关系Cfib（n）=（TBlock0+CC0（n））C1（n）CC0（n）=C2（n）C1（ n）= T块1+C5（ n）C5（n）=TBlock5C2（n）=（T块k2+CC2（n））C3（n）CC2（n）=C4（n）C3（ n）= TBlock3+C5（ n）C4（n）=TBlock4+Cfib（n−1）+Cfib（n−2）n=0n=/0⟩n=1100/=1Fig. 1. 成本分析阶段数学。秒4处理使用数组的程序，有简单的和嵌套的循环，并且需要一些简单的变换来求解方程。节中5、对具有面向对象特性的程序，如对象、动态调度等进行了评价，得到的代价关系式只需经过一定的变换就可以用Mathematica处理。最后，SEC。6给出了我们的分析所需时间的实验结果，并总结了论文。70E. Albert等人理论计算机科学电子笔记190（2007）672Java字节码通过一个例子，我们简要回顾了我们最近提出的成本分析的不同阶段[5]。运行示例如图所示1;它对应于著名的斐波那契数列的简单递归实现给定一个自然数n，调用fib（n）计算斐波那契级数中的第n项。成本分析的输入字节码可以在图的左上角看到。输入变量n在字节码级别存储在具有index0的情况。 将此局部变量与常量0和1（E. Albert等人理论计算机科学电子笔记190（2007）6771块1保护（ifeq）块5第00：iload_01：ifeq 9块2guard（ifne）4：iload_05：图标_16：if_icmpne 119：图标_110：irereturn块3块4图二. 控制流程图斐波那契数列）在第1和第6行。如果任何一个比较成功，执行跳转到字节码指令9，其中常量1被压入堆栈并作为方法的结果否则，即，当两个比较都失败时，控制转到字节码指令11，其中该方法被递归地调用两次（第14行和第20行），分别具有值n-1和n-2。将获得的值相加，从而给出方法的返回值我们的成本分析从该输入字节码开始，并执行以下小节所述的五个主要分析步骤2.1控制流图首先，与方法相关的字节码通过使用编译器理论[2，3]中已建立的思想转换为控制流图（CFG），该思想已应用于Java字节码分析[18]。这有助于将字节码的非结构化控制流转换为递归。考虑图2中的CFG。每个块包含一个标识符（块i），一个可选的保护，和一个（可能是空的）连续的字节码指令序列块0是初始块。CFG中的边缘显示不同的执行路径。由异常、条件跳转或动态分派引起的分支由guard（C）形式的guard控制，guard（C）表示执行块的条件。例如，块1和块2分别包含guard（ifeq）和guard（ifne）：如果在执行字节码指令1（ifeq 9）时位于堆栈顶部的元素等于0，则执行移动到块1，而如果这样的顶部元素不同于0，则执行移动到块2。我们指出，警卫不考虑在计算成本的程序，因为他们不是原始程序的一部分，然而，他们提供的信息是非常相关的准确的递归成本方程的生成。保护（if_icmpeq）guard（if_icmpne）11：iload_012：图标_113：isub14：调用（静态，Fib，fib（I）I）17：iload_018：图标_219：isub20：调用（静态，Fib，fib72E. Albert等人理论计算机科学电子笔记190（2007）672.2递归表示从CFG我们得到了一个递归表示的方法，其中迭代转化为递归。在这种表示中，图中的每个块被表示为规则。此外，操作数堆栈通过将其内容转换为一系列附加的局部变量来进行扩展。注意，这是可能的，因为在每个有效的字节码程序中，每个程序点处的局部堆栈的高度可以静态计算。fib方法的递归表示（的简化版本）显示在图1的右上角。由于fib确实是一种递归方法，因此这种表示的相关性在这种情况下并不明显（然而，参见，例如，[5]的例子fibi（x）← Bim表示输入变量x中的blockBlock的执行执行由B i中包含的动作组成。保护和块调用是显式表示的，但为了简单起见，字节码的其余部分被写为sBC（Blocki）。对于不连续的term，“;“操作表示只有一个项（对应于CFG上的对于局部变量的值的每个组合 主要规则是用于fiba的规则;仅用于对listingu进行排序的补充规则对出现在同一规则主体中的主要规则进行了大量的排序，就像fib 4规则的情况一样，它包含对fibb和fibc的调用。在这个例子中，除了参数n之外，还需要考虑另外两个变量：堆栈上的元素s0和s1 规则fib2（n，s0）模拟块2的行为，如果满足以下条件，则遍历块2栈顶不为0（如guard（ifne（s0））所述），并且在执行BC（块2）之后可以是块3或块4（这通过（fib3（nJ，sJ0，sJ1） ;fib4（nJ，sJ0，s1J））使其可见），其在两个块的开始处的保护中的对应部分中被区分。2.3尺寸分析接下来的步骤包括推断不同程序点处的状态之间的大小关系。具体地说，我们推断规则头部的输入变量与块或方法调用中的输入变量之间的大小关系在它的身体里这是通过执行自底向上定点计算来完成的。一般来说，可以使用各种度量来确定输入项的大小，可能会影响结果的精度。在最常用的大小度量中，我们的系统能够处理（i）数字变量的整数值（即，x的大小是它的值）;以及（ii）指针的路径长度[19]（即，x的大小是从x开始的最长指针链的长度）。正如我们稍后将看到的，变量的大小是一条信息，它在估计项目成本时是必不可少的[13]。在运行的示例中，使用整数值作为大小度量，并且推断的大小关系在图1的中心部分示出。为例第三个大小关系是从递归表示的第二条规则中推导出来的：关系{s0=0，n=nJ}意味着当进入块1时，s0是0，正如防护所要求的那样，并且n在块内不被修改E. Albert等人理论计算机科学电子笔记190（2007）6773至于路径长度分析，我们的分析器还不支持任意程序的分析;特别是，程序应该满足一些正确性条件[19]：（1）数据结构不是循环的;（2）每当引用传递给方法时，保证相应的结构（在堆上）不会被该方法更新。为了克服这些限制，我们应该通过共享和循环组件来丰富我们的分析器[19]。这是正在进行的工作的主题。2.4相关变量通过前面的分析步骤获得的信息将用于估计方案的成本。解决成本方程的问题是，在一般情况下，非常困难的，和现有的工具，我们用来实验我们的方法表示几个限制，至于类的问题，可以处理。因此，我们的目的是通过对迄今为止得到的结果应用额外的变换来使事情变得更简单。作为第一步，我们注意到，在许多情况下，堆栈仅用于加载包含在非堆栈变量中的一段数据并执行比较;之后，堆栈位置被清空，而不对加载的数据进行任何修改在这种情况下，堆栈变量仅用作临时数据保存者，并且其使用在比较之后立即结束;检测这种情况通常是可能的，并且导致将非堆栈变量与堆栈变量统一起来，以便从关系中消除后者[5]。在示例的第1行，在将n加载到堆栈上之后立即执行与0的比较。因此，很明显，递归中的变量s0表示可以在保护中被n替换，从而导致保护（ifeq（n））。在fib中，这种优化允许在所有关系中摆脱s0和s1;n成为唯一需要考虑的变量此外，重要的是要确定与成本有关的一组变量，即，其值可能会影响程序的执行时间。例如，for类循环的索引通常是相关的，因为它会影响迭代次数;另一方面，用于存储部分结果的变量在成本中没有影响，除非其值参与执行时间不固定的计算。相关变量是那些涉及到保护或方法调用的变量，因为（i）保护会影响程序的控制流程，因此会影响程序的执行时间;（ii）执行外部方法的成本显然与总成本相关。这种分析的目的类似于程序切片[20];它是通过向后传播被发现相关的控制流程图变量来执行的。最后，当到达固定点时，每个块都被标记为输入和输出相关变量的集合，这些变量将用于产生成本关系。在fib中使用切片不会导致从关系中消除任何变量，因为在上述优化之后，只有一个变量n，它显然与成本相关。然而，在其他例子中（见3.1节），几个变量可以被删除，从而导致一个更简单的形式的成本关系，否则不能解决74E. Albert等人理论计算机科学电子笔记190（2007）672.5成本关系根据递归表示、大小关系和相关变量，我们自动产生Cost关系作为输出，该关系定义了通过对costequations的处理的成本。 Intively，for eachrulep（nx）←G，B，（q1;. ;qn），其中G是保护，B是字节码指令，我们生成：• 一个成本方程，它将p的成本定义为B中报表的成本加上其延续的成本，记为p;• 另一个成本方程将p的成本定义为q1的成本（如果其保护满足），。. . 或者说，如果它的保护是满足的，那么它的成本就是qn因此，递归表示中的每个规则至少与一个成本方程相关联（当不存在析取时）。例如，定义fib a的规则被用来定义Cfib。 如果纤维连续体在其内部是连续的，则产生连续。这个延续CC0具有与析取中的调用一样多的备选项，即， 两个. 每一个都有相应的警卫标记，这决定了它的适用性。因此，等式C1（resp.C2）仅在n等于0时才适用（分别为与0不同）。注意，等式中的保护是从递归表示中的规则中的保护中提取的。在每一个不对应于延续的成本方程中也考虑到规模关系。例如，与规则fib4相关联的等式C4利用了图1中的最后两个大小关系，它们分别将fib4与fibb和fibc相这种尺寸关系的应用允许生成对于Cfib（n−1）和Cfib（n−2）的计算结果，则是正确的。成本关系不是参数关系。成本模型（在图中，我们使用Tb表示字节码块b的成本）。3递归过程在这一节中，我们推导出两个经典递归过程的代价在这两种情况下，一般来说，对于其基本情况取决于常数值的递归过程，通过我们的分析获得的成本关系可以直接通过Mathematica求解。为了简单起见，在下文中，所有字节码指令的成本被假设为1;使用将不同成本分配给不同字节码的更精细的成本模型为了可读性，我们只提供原始的Java代码，而不是字节码。3.1经典的河内塔第一个例子对应于河内塔的经典算法，如下表所示;调用hanoi（7，1，2，3）使用辅助塔2将7个磁盘从塔1移动到塔3。由分析器获得的递归方程在同一表中描述。等式hanoi[n]对应于调用hanoi的总成本，其中n是该方法的第一个参数。的E. Albert等人理论计算机科学电子笔记190（2007）6775Hanoi的代价关系和Mathematica解public int findDuplicate（int [] nums，int[] nums，int [] nums）{如果（n> 0）{hanoi（n-1，s，t，a）;System.out.println（n+"：“+s+"→"+t）;hanoi（n-1，a，t，s）;8>河内[n]== m0[n]，>m0[n]== 2 + m3[n]，<河内E=>m3[0]== 1，>m3[n]== m4[n]，：m4[n]== 15 + hanoi[n-1]+ hanoi[n-1]Mathematica查询： RSolve[{Ehanoi}，{hanoi[n]，m0[n]，m3[n]，m4[n]}，n]2+nMathematica答案（复杂度）： hanoi[n]→（-17）+ 52图三. 河内问题其它方程对应于控制流程图中不同块的成本;它们直接从相应的递归表示中获得。例如，等式m0[n]对应于验证条件n>0;这里，2是比较中使用的相应字节码的成本。公式m3[0]对应于基本情况（当n≤0时），m3[n]对应于执行then分支;常数15是相应字节码的成本，hanoi[n-1]的两次出现是递归调用的成本。 在递归调用中n减1的事实是通过字节码程序的大小分析检测到的。请注意，局部变量和堆栈元素没有出现在方程中，它们被切片算法（2.4节）删除了，因为它们出现在方程中。不考虑基本情况;因此，它们与成本无关。一旦生成了方程，我们就可以在Mathematica中通过调用它来求解它们。 所述queryRS olv e[{eqns}，{a[n]， . . ，z[y]}，{n，. . . ，y}]求解针对a[n]， . . . ，z[y]，wheren， . . . ，y是唯一的变量，通过给出a，.，z为纯函数。完整的Mathematica查询如表所示。我们能够在没有任何预处理的情况下求解上述方程，并且正如预期的那样，所获得的答案预测了hanoi[n]的指数复杂度。3.2递归斐波那契数列下一个例子（图4）是斐波那契数列的递归实现，已经在第二节中研究过了。二、由分析器获得的递归方程在同一表中描述。等式fib[n]对应于调用的总成本fib（n）。其他方程对应于控制流程图中的不同块。例如，m4[0]和m4[n]分别对应于条件n==0的成功和失败。 类似地，m6[1]和m6[n]对应于n==1。公式m7[n]对应于递归调用及其相应字节码的成本;调用中的1和2的减少通过字节码的大小分析来检测此外，通过切片的方式，从方程在Mathematica中求解上述方程会得到预期的指数复杂度。76E. Albert等人理论计算机科学电子笔记190（2007）67Fibonacci的代价关系及其Mathematica解法public int findDuplicate（int []nums）{如果（（n==0）||（n==1））return 1; else return（fib（n-1）+fib（n-2））;}8>fib [n]== m0[n]，>>m0[n]== 2 + m4[n]，>> m4[0]== 2，>m4[n]==m5[n]，Efib=>m5[n]== 3 + m6[n]，>>m6[1]== 2，>>m6[n] == m7[n]，>：m7[n] == 10 + fib [n-1] + fib [n-2]Mathematica查询：RSolve[{Efb}，{fb [n]，m0[n]，m4[n]，m6[n]，m7[n]}，n]Mathematica答案（复杂度）： fib [n]→-（2（152- 19（1 -15）+53−n1+n（1 -15）n- 19（1 +15）n-5（1 +15）n））/（（-1 +15）2（1 +15）2）见图4。 斐波那契问题阵列恢复代价关系及Mathematica求解public int findDuplicate（int[ ] nums）{int nums= nums;int[ ] nums = new nums [];for（int i=la; i> 0;i--） r[la-i]=a[i-1]; return r;}反向[a] == m0[a]，m0[a]== 8 + m1[a]，m1[i]== 2 + m2[i]，m2[0]== 2，m2[i]== m4[i]，m4[i]== 12 + m1[i-1]Mathematica查询： RSolve[{rev[a] == m0[a]，m0[a] == 8 + m1[a-1]，m1[a]== 2 + m2[a]，m2[0]== 2，m2[a]== m4[a]，m4[a]== 12 + m1[a-1]}，{rev[a]，m0[a]，m1[a]，m2[a]，m4[a]}]Mathematica答案： reverse[a]−> 12（1 + 2 a）图五. 阵列恢复4使用数组和（嵌套）循环分析程序在本节中，我们将评估几个处理数组和循环的过程的成本分析的实用性。我们从一个数组反转的例子开始，它的代价关系在Mathematica中是可解的。然后，我们研究了数组连接，这需要对成本关系进行一些变换，以使其可解。最后，我们分析了一种多循环嵌套的矩阵乘法算法，它可以通过对每个循环的不同查询来解决4.1数组的反转我们想推断一个简单的反转方法的成本，该方法反转数组的元素。在我们的系统中，reverse的递归表示形式为reverse（a，i，r），其中a表示输入数组，i是局部变量，r是结果数组。基本上，执行时间取决于循环迭代的次数;因此，相关变量是那些出现在m2递归关系的保护中的变量（表示循环的终止条件）。只有a和i出现在我们的系统产生的成本关系中，而r被删除。大小分析将数组a抽象为它的长度，并推断变量i在每次迭代中减少一个单位。为了在Mathematica中求解递归方程，我们需要使用E. Albert等人理论计算机科学电子笔记190（2007）6777阵列级联代价关系及Mathematica求解public int findDuplicate（int [] nums）{int l1 =a.length; int l2= b.length;int i = 0; int[ ] nums =nums; int[] nums =nums对于（i=0;i l1;i++）r[i]=a[i];for（i=l1;i l1+l2;i++）r[i]=b[i];return r;}8concat[a，b]== m0[a，b]，m0[a，b] == 15 + m1[a，b，0]，m1[a，b，i] == 3 + m2[a，b，i]，m2[a，b，i]== m3[a，b，i]，i≥ am2[a，b，i]== m4[a，b，i]，i aRSolve[{m1[i]== 3 + m2[i]，m2[a]== 2 + k，m2[i]== m4[i]，RSolve[{m5[i]== 5 + m7[i]，m7[a+b]== 2，m7[i]== m8[i]，：m8[i] == 8 + m5[i+1]}，{m5[i]，m7[i]，m8[i]}，i]Mathematica答案： m1[i]-> 5 + 11 a - 11 i + k（ k-> m5[b]）m5[i]-> 7 + 13 a +13 b-13 i答案（答案的构成）：concat[a，b]-> 15 + m1[0]<$15+ 5 + 11 a + m5[b]<$27+ 24 a见图6。 数组连接所有方程中的变量名称相同，即，我们不能同时拥有a和i。这是因为，否则，Mathematica要求从初始方程开始传递所有变量（另请参见第二节）。4.2）。请注意，这种重命名可以很容易地以自动的方式完成（结果可以在RSolve查询中看到4.2两个数组考虑图6中的方法concat：它连接两个输入数组a和b，并在c中返回结果。等式concat[a，b]对应于成本使用两个长度为a和b的数组调用concat，m0[a，b]对应于局部变量的初始化。 回路分别对应于等式：（1）m1[a，b，i]、m2[a，b，i]和m4[a，b，i];以及（2）m3[a，b，i]、m5[a，b，i]、m7[a，b，i]和m8[a，b，i]。大小分析能够推断出循环计数器及其相应初始值的增加我们在Mathematica中发现的主要限制是：1) 在递推方程中不可能包括保护;2) 变量不能在方程头中重复;3) 所有方程必须至少有一个变量参数;4) 方程头中的变量必须出现在方程体中。关于限制1），我们可以注意到在m2的方程中，递归在i=a时结束。因此，我们可以将m2的两个方程写为：m2[a，b，a]==m3[a，b，a]，m2[a，b，i]==m3[a，b，i]。相同的过程可以应用于针对m7的方程，其可以被变换为m7[a，b，a+b] =2，m7[a，b，i] ==m8[a，b，i]。这种重新表述仍然不能被Mathemat接受-78E. Albert等人理论计算机科学电子笔记190（2007）67ICA，因为在规则的头部有重复的变量（第2点）。然而，我们观察到关系的前两个参数，a和b（即，数组长度）通过该关系保持恒定。因此，我们可以安全地（自动地）将它们从所有方程中删除。然而，这种转变带来了问题3)和4）。问题3出现是因为前两个方程不再有变量;这阻止了我们将它们包含在Mathematica查询中（相反，我们只能在最后使用它们，以组成最终解）。此外，当i被初始化为等式m3中的数组b的长度时，即，我们有m3[i] ==m5[b]，问题4）发生。为了克服问题4）（它确实会经常出现），我们将m5[b]视为常数（表中使用k）并在所有方程中替换它。这涉及到在Mathematica中执行两个不同的查询，正如上面所看到的：一个针对m1[i]，一个针对m5[i]。最终复杂度是通过将结果（考虑到k=m5[b]）与没有变量的初始方程组合而获得的。我 们 想 指 出 的 是 ， 虽 然 上 述 转 换 可 以 自 动 完 成 （ 我 们 可 以 产 生 直 接 在Mathematica中可解的递归关系），但我们还没有在我们的系统中实现它们，因为我们仍在研究哪个求解器更适合我们的需求。的确，Mathematica 是一个相当复杂的软件，它比求解递归方程所需的要复杂得多;因此，我们可能想用一个更简单的软件来处理我们系统的输出，比如PURRS [7]，它确实是专门用于求解递归方程的。4.3矩阵乘法考虑图7中的方法mult，它实现了两个矩阵（的子集）的乘法。前两个参数是要相乘的矩阵，r和c是要考虑的行数和列数。作为一个新特性，mult提供了嵌套循环。这需要对CFG进行特殊处理（更多细节请参见[4]），以检测和提取循环。等式m0[r，c，i]、m1[r，c，i]和m2[r，c，i]对应于最外环;m3[r，c，j]、m4[r，c，j]和m5[r，c，j]对应于中间环;并且m6[r，c，k]、m7[r，c，k]和m8[r，c，k]对应于最内环。请注意，大小分析能够推断出循环计数器的增加推导出的递推方程不能用Mathematica求解。我们基本上需要应用在节中解释的相同的转换4.2使方程可解（并克服前面提到的限制）。非常简单，我们首先通过将它们应用于方程头来简化所有的守卫。然后，我们从方程中删除参数f和c，因为它们在所有方程中都是常数。最后，我们向Mathematica输入三个独立的查询，每个循环一个。最后，三个循环得到的结果被组合在初始方程中（我们不能在查询中包含它，因为它没有参数）。E. Albert等人理论计算机科学电子笔记190（2007）6779矩阵乘法代价关系及Mathematica解法static int[ ][ ] multit（int[ ][ ] a，int[ ][ ] b，int i =0;inti=0; int i=0RSolve[{m0[i]== 3 + m1[i]，m1[r]== 0，m1[i]== m2[i]，>>m2[i]== 4 + k + m0[i+1]}，{m0[i]，m1[i]，m2[i]}，i]>>RS〇lve[{m3[j]==3+m4[j]，m4[c]==0，m4[j]==m5[j]，Mathematica查询：>m5[j]== 4 + z + m3[j+1]}，{m3[j]，m4[j]，m5[j]}，j]>>RSolve[{m6[k]== 3 + m7[k]，m7[c]== 0，m7[k]== m8[k]，>>：m8[k]==24+m6[k+1]}{m6[k]，m7[k]，m8[k]}，k]8>m1[i]->3-7i-ik+7r+kr（k=m3[0]）矩阵形式为：>：m3[j]->3+7c-7j+cz-jz（z=m6[0]）m6[k] ->3（1 + 9 c - 9 k）2溶液：mul->16+m1[0]<$19 +7r+rm3[0]<$19 +7r+r（3+7c+cm6[0]）<$19+10r+10rc+27c r见图7。 矩阵乘法5处理面向对象的特性在本节中，我们将研究几个面向对象的特性。首先，我们来看看如何在成本分析的背景下处理动态调度。然后，我们分析了将一个列表实现为一个具有field属性的类的成本。最后，我们推导出一个线性搜索算法在列表上的成本。据我们所知，这些例子说明了新的面向对象的功能，没有在现有的成本分析研究其他语言和范式。5.1动态调度图8中的Incr示例取自[5]，展示了有趣的面向对象特性，例如使用对象和调用具有动态调度的方法。特别是，由于在编译时不知道三个方法（A.inc，B.inc或C.inc）中的哪一个将被执行，我们需要考虑每个情况下获得的因此，确定将执行哪个方法的对象o成为成本关系中的守卫的一部分从m4的等式中可以看出，根据对象o属于A类、B类还是C类，我们有不同的成本。我们可以应用第4节中讨论的所有变换，以使方程在Mathematica中可解（即，对i应用保护，从所有方程中消除变量n，等等）。然而，我们不能将区分对象类型的保护应用于方程头。我们的建议包括80E. Albert等人理论计算机科学电子笔记190（2007）678见图8。INCR方案生成三组不同的递归方程（一组对应于每个方法调用）。我们现在可以去掉所有方程组中的变量o了。这将导致在表中写入三个Mathematica查询。我们将每一个的结果命名为addX，其中X是计算成本的对象类型。由于Mathematica的答案对于加B和加C是相当大的，我们没有在表中写入常数部分。然后，根据人们是否对计算成本的上限或下限感兴趣，我们计算三个解决方案的最大值或最小值：显然，添加A提供了计算成本的上限，添加C提供了计算成本的下限。5.2列表处理算法类List（图9）包含一个过程，它计算一个列表的逆，该列表被实现为一个具有两个字段的类：next，指向列表中的下一个元素，以及data，包含存储在列表中的信息。表中描述了分析仪推导出的方程。回想一下，在递归方程中，x代表从x可到达的路径的长度，如第2.3节所解释的。大小分析能够推断出x的路径长度在循环的每两次连续访问中减少1，并且切片能够删除所有不符合循环条件的变量。输出递归方程可以直接在Mathematica中求解。我们得到了线性复杂度，如图所示动态调度费用关系及Mathematica求解class A{int i +1;}};class B extends A{int i +2;}};class C extends B{int i +1;}};class Incr{public int findDuplicate（intnums）{int i =0;int i=0;while（i =n）{i = 0.incr（i）;}}};add[n，o]== m0[n，o]，m0[n，o]== 4 + m1[n，o，0]，m1[n，o，i] == 3 + m2[n，o，i]，m2[n，o，i] == 2，i> nm2[n，o，i]== m3[n，o，i]，i≤ nm3[n，o，i] == 7 + m4[n，o，i]，m4[n，o，i] == A：incr[i] + m5[n，o，i+1]，o ∈Am4[n，o，i] == B：incr[i] + m5[n，o，i+2]，o∈ Bm4[n，o，i] == C：incr[i] + m5[n，o，i+3]，o ∈Cm5[n，o，i] == 2 + m1[n，o，i]，A：incr[i] == 3，B：incr[i]== 3，C：incr[i]== 3，>RSolve[{m1[i]== 3 + m2[i]，m2[n]== 2，m2[i]== m3[i]，m3[i]== 7 +m4[i]，>>m4[i]== A + m5[i+1]，m5[i]== 2 + m1[i]，A[i]== 3}，>>{m1[i]，m2[i]，m3[i]，m4[i]，m5[i]，A[i]}，i]>
