远程属性文法：字段动态依赖评估和静态调度的实现

9网址：http://www.elsevier.nl/locate/entcs/volume65.html21页远程属性文法John Tang Bo yland1;2威斯康星大学密尔沃基分校电气工程与计算机科学系关闭WI，USA摘要远程属性文法使用具有单独定义的字段的对象来引入属性文法中的直接非局部依赖性。对象的字段可以从创建它的地方远程读取，特殊的早期的工作表明，远程属性语法可以静态调度的基础上，本文展示了如何可以实现增量。静态调度用于确保对象的字段在被读取之前被定义，并且我们不会在每个编辑周期中动态依赖关系用于在字段更改时将远程使用站点标记为受影响其结果是一个有效和实用的增量评估。1 介绍远程属性文法的定义和动机在早期的论文[2]中，图1取自该论文。与经典的属性语法一样，远程属性语法具有合成属性（由它们所连接的节点计算）和嵌入属性（由它们所连接的节点的父节点计算）。例如（第7行），树中的每个表达式节点都有一个由上下文指定的作用域和一个形状，即它的类型。对于经典的属性语法，我们添加了全局集合和对象，它们可以具有正常（局部分配）字段和集合字段。集合被赋予一个初始值和一个组合函数来组合所有发生的赋值例如图1宣布[1]这项工作部分由美国国家科学基金会（CCR-9984681）和国防高级研究计划局以及美国空军空军装备司令部罗马实验室根据合同F30602-99-2-0522提供支持。本文中包含的观点和结论是作者的观点和结论，不应被解释为必然代表国家科学基金会、国防高级研究计划局、罗马实验室或美国政府的官方政策或认可（无论是明示还是暗示）。2电子邮件：boyland@cs.uwm.educ 2002年由Elsevier Science B出版诉 在CC BY-NC-ND许可下开放访问。101全局消息w{}with（[）23block，decls，decl，stmts，stmt4吸气示波器5类型6同步波形7expr8吸气示波器9同步波形1011程序！ 块12block.scope = ROOT_SCOPE1314挡！“begin”decls stmts“end”15本地范围=16{coldeclsw{}with（[），17enclosures = block.scope}18decls.scope = scope19scope = scope2021decls！2223decls！ decls decl24decls1.scope = decls0.scope25decl.scope = decls0.scope2627decl！ id“：“type“;”28本地d =29{ shape = type.shape，30col usedw false with（or）}31decl.scope.declsw {id，d>}32如果不使用d，则33msgsw {id ++“未使用”}34endif3536类型！“整数”37type.shape = INTSHAPE38类型！“字符串”39type.shape = STRSHAPE4041stmts！4243stmts！ stmt44stmts1.scope = stmts0.scope45stmt.scope = stmts0.scope4647stmt！ block“;”48block.scope = stmt.scope4950stmt！ “：=”expr“;”51expr1.scope = stmt.scope52expr2.scope = stmt.scope53如果expr1.shape/= expr 2.shape54then msgsw {“type mismatch”}55endif5657expr！中间常数58expr.shape = INTSHAPE59expr！斯特朗常数60表达式形状= STRSHAPE6162expr！ ID63本地decl64decl = lookup（id，expr.scope）65expr.shape = decl.shape66如果decl = NOT_FOUND，则67msgsw {id ++“未声明”}68其他69decl.usedw true70endif71函数查找（id，s）72如果s = ROOT_SCOPE，则73结果= NOT_FOUND74其他75local d = fetch（id，s.decls）76如果d = NOT_FOUND，则77result = lookup（id，s.enclosing）78其他79结果= d80endif81endifFig. 1.使用远程属性语法进行名称解析消息的全局集合（第1行），初始值为空集，组合函数为并集。每个块节点创建一个具有两个字段的作用域对象（第15行）：decl的集合是从其他地方收集的，但是封闭的作用域在这里设置。我们看到（第31行）每个声明都向作用域的decl添加了一对name和object该对象有一个局部形状集和一个布尔集合，该集合指示该对象是否在任何位置使用如果它没有被使用，我们就在全局集合msgs中添加一条消息（第33行）。当表达式是以标识符的形式出现时（第64行），我们在作用域中查找这个标识符，检查是否找到了一个实际的声明，然后将声明标记为已使用。集合字段和全局集合可以有多个定义站点;所有11使用组合函数将（部分）定义组合成单个值。与Johnson和Fischer [9]以及Vorthman的DR线程[18]的非本地依赖性读取集合字段或全局集合时获得的值是最终值;中间值不会公开。特别地，诸如iwi + 1的规则是循环依赖性，而不是强制更新。远程属性文法与高阶属性文法相关，因为两者都允许复合对象通过树进行传输，但在我们的例子中，对象与身份和属性一起传输。从语义上讲，对象的每个字段都有一组独立的依赖项;将值打包到一起不会导致字段的任何使用依赖于对象的所有其他字段。相反，在高阶情况下，子树是引用透明的;树的任何使用都传递地依赖于用于构造树的任何东西。子树不携带属性值;它们在使用时被属性化。在高阶属性文法中，集合字段显然没有类似物.不像GorelHedin调度是通过生成控制属性来实现的，这些属性不携带任何值，但确保正确的顺序，特别是在使用之前（完全）定义字段。例如，当调度图1中的远程属性语法时，系统生成decl的合成属性，其指示该点以下的声明已经被添加到轮廓，并且生成stmts的继承属性，其指示范围对象被声明完全填充。然后，系统将这两个生成的属性连接到块的生产中。换句话说，我们使用（远程）属性语法的声明性语义来约束调度，而不是像Kastens和Waite在属性语法[11]中使用命令式符号表那样依赖于手动添加控制属性然而，即使远程属性语法是声明性的，基于控制属性的 因此，一种前进的方法是识别一些要传输的真实值，然后使用标准的增量技术，也许扩展高阶属性语法。这种方法的问题是受影响的属性的规模O（jAFECTEDj）要大得多，如2.4节中进一步详细描述的。另一种方法是保留命令式实现，并使用其他方式来传播更改。本文展示了如何远程属性语法调度使用自动生成的控制属性，但可以通过使用选定的动态依赖关系增量。这些方法与Hoover和Teitelbaum [8]使用的骨料处理技术有关;在论述过程中指出了相似之处和不同之处Johnson和Fischer通过静态地确定子树的优先级顺序来增量地处理远程依赖关系[9]，有时没有一致的顺序可以12Hoover [7]通过“近似”拓扑顺序处理所有非循环属性文法，有时导致属性重新评估。从理论上讲，重新评估的数量可能是指数级的，但在实践中，重新评估的数 量从未超过所有评估的一半Vorthmann [18]使用声明引用（DR）线程对树中的所有属性进行动态调度，该线程允许属性从声明流向引用。目前尚不清楚如果DR线程在评估过程中更新，该算法如何工作。本文中的调度算法（如Johnson和Fischer的算法）是静态的，并且只接受属性文法的一个子类（有序远程属性文法）。LIGA [10]是Eli编译器构造系统[5]的一部分，它有一个可以减少复制规则数量的符号胡佛已经展示了如何动态地绕过复制规则[7]。这两种技术大多与远程属性文法的扩展及其调度正交。一个重叠是对象的使用减少了所需的“并行”复制规则的数量在下面的部分中，我们将描述如何实现一个静态调度的远程属性语法，首先不使用增量，然后使用增量。下一节将介绍实现平台。第四部分是论文的结论。2增量访视序列评价器我们建立在Maddox [12]提出和实施的增量访问序列评估技术的基础上，Maddox [14]改进了Reps [14]的早期工作。处理多个子树替换（或等效地，多个编辑站点）的结果基本上类似于Swierstra和Vogt的技术[17]。我们将在本节中介绍2.1访视序列评价员访问序列计算器对每个非终结符使用属性的协议属性集对的序列hI1;S1i;：; hIn; Sn i。给定任何`-有序属性语法，可以为每个非终结符找到单个协议，使得每个属性可以仅依赖于在由将协议扁平化为单个序列而产生的总顺序中前面提到的属性。访问序列评估器可以为任何非循环属性语法定义;这里我们将自己限制在简单的`-有序情况下。评价树的工程通过使用递归访问的程序.对于非终结符X的产生式p，我们对X的协议中的每一对都有一个访问过程。p和对hIi; Si i的访问过程接受内点的值I中的合成属性，并计算Si中的合成属性。每次访视程序包含一系列针对此生产的属性评估，并要求访问孩子们的程序13由于每个节点都是从一个只知道它的非终结符（而不是它的产生式）的上下文中调用的，所以这种技术很好地映射到一个面向对象的语言上，每个非终结符都有抽象类，每个产生式都有具体类。具体来说，对于一个协议为hI1;S1i;：;hIn;Sn i的非终结符X，我们有以下类（这里T（a）表示属性a的类型）：抽象类X extends Node {抽象元组 visit_i（T（a）a j a 2 Ii）;j1我 n}对于形式为X0的产品p！X1：X m，我们有以下具体类：p类 extendsX0{Xi _i;j1我nT（a） a;j a 2 A（X0）（X 0的所有属性）T（l）l;j l 2 Lp（p的局部属性）p（Xic_ij1i n）{ _i=c_i;j 1i n}元组 visit_i（T（a）_a j a 2 Ii）{a= _ a; j a 2 Ii访问机构程序一return（a）;}j1I n}在本文中，我们假设所有属性都存储在树中存储属性使增量更容易。2.2Maddox使用Maddox从本质上讲，我们memoize访问过程中的树的状态，如果树是不变的，继承的属性是相同的，遍历结果可以从树作为缓存。这棵树可能以两种不同的方式改变。最明显的是，它可能在上次访问后被编辑过另一种更微妙的方式是，它可能在以前的访问中收到了新的这种直觉在Saraiva、Swierstra和Kuiper [15，16]的“访问树”递增技术中得到了形式化马多克斯为了检测树的变化，他在每个节点上添加一个位，称为中的节点或属性时，14它就变了当节点的最后一次访问完成时，该位被清除。我们避免在节点中设置已经设置的位，但这种变化不会影响平衡树中的渐近复杂度：类节点{boolean SUBTREE_MODIFIED = true;.public void run（）{SUBTREE_MODIFIED）{return true;如果（父！= public void println（）;}}}由此产生的访问程序采取以下形式：元组T（a）j a 2 Si> visit_i（T（a）_a j a 2 Ii）{如果（子树_修改||一 ！= _aii）{a= _ a; j a 2 Ii访问机构程序一Subtree_MODIFIED =i 6= n;}return（a）;}j1我 n修 改 后 更 新 属 性 的 时 间 复 杂 度 为 O （ jAFFECTEDj + j EDITANCESTORSj），其中AFFECTED是需要重新评估的所有属性值的集合，EDIT ANCESTORS是从编辑更改到根的路径上的所有节点的集合。后一项可以大到O（n），其中n是树中节点的总数，但Maddox观察到，如果（增量）解析器使用序列的平衡表示，并且如果我们假设由于齿轮的原因，程序员将不会生成深度嵌套的结构，例如：f1（f2（f3（...（fn（）那么jEDIT ANCESTORSj将具有O（klogn）的实际限制，其中k是编辑站点的数量，n是树的大小。2.3远程属性语法的访问过程在本节中，我们假设我们有一个远程属性语法，它是在（自动生成的）控制属性的帮助下调度的，并且结果是在属性语法的`- ordered类不失一般性，我们假设所有的字段都是集合字段;稍后我们将展示如何更简单地处理局部赋值字段的情况首先，我们研究一个非增量实现15访问程序。在以下部分中，我们将讨论增量实现。除了当地人，我们也有物品除了常规的属性如-BLOG，我们还有对象的读和写。为了简单起见，我们假设每个对象都是AGObject类型，每个f2F都有一个字段，以及一个getter和一个（部分）setter。我们还提供了一个collection函数，它在所有部分集合之后和任何gets之前被调用class AGObject { AGObject（Node owner）{.}T（f）f=f的默认值;j f 2 FT（f）get_f（）{return f;} j f 2 Fvoid partial_set_f（T（f）partial）{.}j f 2 Fpublicvoid onDestination（）{}j f 2 F}(In在原型中，对象是类型化的，每个对象类型都有一个单独的类远程属性语法指定在树中的何处创建对象。对对象的引用与本地属性一样存储在节点中：p类 extendsX0 {.AGObjecto = new AGObject（this）;j o 2 Bp（objects forp）}一个对象字段写v。f ww实现为v.partial_set_ f（ w）;在调度程序说字段已经接收到所有部分写入并准备好读取的时候，我们添加一行：v.collect_ f（）;如果部分setter保持值为最新，则该函数不需要做任何事情，但当我们转向增量实现时，它有一个重要的用途。一个物体场读作v=w。f被实现为int n= nums. nums（）;除此之外，一切都与经典属性语法相同这基本上是我们在早期工作中报告的结果[2]。2.4纯增量实现接下来我们转向增量视图。在本节中，我们将研究（并拒绝）一种纯功能性的实现方法。在我们早期的工作[2]中，控制属性的动机是“假装”它们携带在其基本属性中传输的对象字段的实际值。因此，实现远程属性语法的一种方法是将16将控件属性转换为承载值的属性。然后可以使用上一节中的技术来调度属性语法。缺点是这种转换增加了承载值的属性的数量我们还需要函数来比较转换后的控件属性的新旧值，每个控件属性都可以表示无限数量的对象字段。散列consing允许比较是常数时间，但代价是减慢对象构造。此外，相等性检查经常会失败。例如，如果我们改变了一个全局函数的参数类型，那么在环境中生成的携带实体类型的属性将在树中的几乎每个节点上都有即使我们得到了O（j AFECTED j）递增的同样的问题也发生在使用纯递增的高阶属性文法中。Saraiva、Swierstra和Kuiper给出了一种属性语法编写者可以用来改善这种情况的技术：在块的入口处，符号表被“投影”到块内使用的标识符集合。那么对块内未使用的全局变量的更改就不会传播到块中。这种技术并不直接适用于远程属性语法，因为控制属性是自动生成和调度的。但是，投影变换可以自动进行，这使用高阶属性文法技术提出了一个更严重的问题。将所有信息放在一个聚合值中会大大增加（虚假）依赖性的数量，可能导致有序远程属性语法在被视为高阶属性语法时出现循环。事实上，如果一个人试图在这样一个系统中表达收藏品，就会发生这种情况。远程属性语法和高阶属性语法之间的差异是由于处理对象的方式。对于高阶属性文法，树是纯值;它们可以实现为有向无环图（DAG），并且从不包含循环。对于远程属性语法，对象的字段在创建后分配，从而允许循环结构。考虑全局函数的形式参数类型的情况。在系统的高阶属性语法视图中，程序中某点的作用域是一个单一的值，它包括作用域中可见的所有信息，包括形参的类型。在远程属性语法视图中，作用域是一个带有字段的对象，该字段引用另一个对象，该对象表示带有包含形参类型的字段的函数在前一个系统中，改变形式的类型意味着我们已经创建了一个新的作用域值，因此有大量的受影响的在后一种情况下，没有观察到这样的变化;作用域对象不会因为参数类型的变化而改变。对象的这种处理方法大大减少了直接受影响的属性的数量。然而，仍然必须更新通过作用域对象访问形式类型的属性下一节将描述我们的技术来做到这一点。17远程读取远程写入修改的子树评估顺序图二、对一个对象字段进行一次修改的树的增量计算中的三个阶段，其中该字段在两个地方使用。182.5强制性增量实施受Hoover和Teitelbaum关于聚合的工作的启发图2给出了如何完成此操作的示例，并将在以下讨论中参考。基本思想是保持指针从树中写入字段的位置（在我们的示例树的最左边）到树中创建写入对象的位置（树中间附近的三角形我们还保留了从对象创建位置到树中读取字段的位置的指针（在我们的示例中有两个，树右侧的三角形）。与经典属性语法的增量技术一样，通过将所有祖先标记为根来管理编辑站点在这个例子中，这是通过从编辑位置（只有一个，在树的最左边的节点上）变暗的树边缘来增量计算的工作方式与以前一样，只访问树中树发生更改或继承的属性值发生更改的部分。在我们的示例图中，为了简化表示，我们假设继承的属性没有更改。在示例的上半部分，我们看到求值一直向下到左下角的三角形。如果我们发现一个远程字段写入被添加、删除或更改，我们通过调用markSubtreeModified（）将对象这在中间的图片中显示：中间的三角形被标记为编辑站点（边缘变暗）。此操作将导致增量计算访问此树（否则将跳过此树）。属性的总顺序确保我们永远不会标记已经跳过的对象（或者更准确地说，在总顺序中不会在后面访问的对象）。在收集对象的字段的时间表中，我们检查对象的字段值是否如果是，则将具有此对象的远程字段读取的所有节点因此，我们使用控制属性只是为了确保在字段写入之后和字段读取之前访问对象全排序防止了朴素更改传播的指数性;我们在每个编辑周期中不会对属性重新求值超过一次此外，该系统从不复制对象：保持身份，因此我们不会遭受直接在树中存储属性的分层属性语法系统的问题[3]。我们的方法不同于胡佛和Teitelbaum我们的对象引用保持不变，即使字段发生变化，并且到目前为止，在更改后受影响的属性很少。我们现在研究一下有助于动态跟踪对象字段的结构。首先，集合字段的每个部分定义将存储在适当的容器中。然后，这些部分定义将被放置在为集合字段本身创建的集合对象中。我们将根据集合字段的类型（包括其19初始值及其组合函数）。类型T的集合对象具有以下形式：classT {.集合_T（节点所有者）{... 个文件夹voidinsertPartial （ Partial_Tp ） {.}voidremovePartial （ Partial_Tp ） {.publicvoid run（）{ 个文件夹boolean hasChanged（）{. 个文件夹}集合对象接受该对象所属的节点，以便在分部集合更改时可以标记该对象。如果分部当前在集合中，则插入函数不执行任何操作。否则，如果分部已经在不同的集合中，则首先从那里删除它getValue方法返回完全组合的值，如果自上次调用hasChanged以来此值已更改，则hasChanged一般来说，集合对象将维护部分定义的无序堆（线性化的完全平衡二叉树），并通过对组合函数的O（logp）次调用（其中p是部分定义的数量）递增地维护集合值。类型T的分部定义类具有以下形式：class Partial_T{T部分;收藏_T收藏;.public void setValue（）{if（p == partial）return;partial = p;}public int findDuplicate（）{intfindDuplicate（）{if（集合！return.removePartial（）;}}部分定义对象也直接由集合对象修改，设置集合字段和其他（未指定）字段，指示其在集合中的位置和部分组合值。部分定义在改变其值之前删除它自己，从而简化了集合对象的工作，集合对象只需要在插入或删除部分定义之后更新组合值。20接下来，我们转向远程字段读取的动态依赖关系当一个对象的一个每个字段都可以在多个地方使用，因此我们为每个字段保留了一个动态依赖关系（使用节点）的双向链接列表。名单从哨兵开始。此结构允许在常量时间内从依赖项列表中添加或删除使用class Use {使用prev=this，next=this;节点use_site;Use（Node use）{ use_site = use;}void insertAfter（Use n）{.publicvoid onDestinyNode（）{ 个文件夹void noteChange（）{ //调用sentinel while（next！=这）{int n = numer. numerous（）;int n = numerous（）;}}}sentinel中的noteChange方法删除了列表中的所有其他use节点，但是如果再次执行远程读取，它们将重新插入自己。我们将partial_set和get函数分别改为接受部分定义对象和使用对象。更改收集功能以通知用户任何更改：class ABOUT {收集_T（f） f;intn = new int n（null）;void set_partial_f（Partial_T（f）partial）{insert_partial（partial）;}public voidrun（）{if（f.hasChanged（））uses_f.noteChange（）;}T（f）get_f（Use u）{ uses_ f.insertAfter（u）; returnf.getValue（）;}j f2Fpublic void run（）{f= new Collection_ T（f）（所有者）;j f 2 F}}当集合对象注意到部分值集合中的更改时，21修改所有者，以确保评估将进行到此点。当计算到达对象字段的集合点时收集的字段可能更改多次，但每次重新评估会话最多发生一次通知我们为每个远程字段写入生成部分定义对象，并为产生式规则中发生的每个远程字段读取生成使用对象：p类 extendsX0 {.Partial_fp_r= new Partial_f（）;j r =（v.f w w）2 Rp使用u_r= new使用（this）;j r =（v=w.f）2 Rp.}当规则r = v。f w w被调度，我们生成以下内容：intn.setValue（n）;v.set_partial（p_ r）;这将设置分部定义回想一下，如果分部中的值没有更改，并且分部已经在集合中，那么这两个操作都不会有任何效果。类似地，当调度r = v = w时。f，我们生成以下代码：int v= w.get_ f（ u）;如果使用已经在不同的使用列表中，则在插入新列表之前，将首先从该列表中删除该使用。与大多数增量属性语法算法不同，我们需要访问在增量解析过程中删除的子树，以便我们可以删除来自删除的子树的部分定义。我们还删除了使用，尽管这一步对于正确性来说不是必需的。类节点{.void remove（）{} //当这个子树被移除}那么对于形式为X0的每个生产p！X1：X m，我们重写这个方法：p类 extendsX0 {.public void run（）{_i.remove（）;j 1 i np_r.removeSelf（）;j r =（v. fw w）2 Rpu_r.removeSelf（）; j r =（v = w. f）2 Rp}}22其余增量访视程序的实施与第2.2节中先前在下一节中，我们将研究避免动态依赖的方法2.6分析与改进使用Maddox算法的这些修改的更新的时间复杂度是O（j_AFECTED_j_logM + j_AFECTED_ANCESTORS_j），其中M是完全评估的树中的任何字段的部分定义的最大数量，并且AFECTED_ANCESTORS是从属性必须被重新评估的地方到根的路径上的对数项来自部分定义的平衡树中的插入和移除。例如，假设每个节点都有一个规则，该规则写入同一对象的同一字段。然后在没有下游属性的单个节点上更新将需要计算大小为n的平衡树上的组合值。对于许多组合函数，可以做得比这更好。例如，如果组合函数是逻辑析取，那么我们可以只保留“真”的部分，并在任何变化之后在恒定时间内重新计算结果。另一个例子是加法，它有一个逆运算;人们可以通过减法来实现去除。如果组合函数是袋联合，我们可以将部分袋链接在一起进入结果。如果我们允许行外函数访问对象字段（如我们的示例或动态属性语法[13]），则最坏情况会任意增加，因为使用次数可能是无限的（如果使用“过程”，甚至是部分定义在图1中，lookup函数检查传递给它的作用域对象的decl和封闭字段。此外，具体化动态依赖具有空间成本以及时间成本。因此，对于一些频繁使用（或频繁定义）的字段，维护动态依赖关系可能是昂贵的。人们可能愿意在生成环境时承受额外的复杂性，但是在使用环境时，非局部依赖的运行时成本必须保持较低。在这里，我们将简要介绍一些可以进行的改进。对于那些只在本地分配的字段，我们可以安排定义作为本地属性，而不需要部分定义的机制。虽然这种改进只有一个常数因子的效果，我们希望它是广泛适用的：大多数对象字段可能是在对象被创建时分配的在我们运行的示例中，decl的类型在创建时就可用可以对仅本地分配的字段的子集进行进一步的改进，这些字段的定义可以在创建对象的同一访问中进行调度，而无需对子树进行任何干预访问。对于这样的字段，我们可以假设对象的创建依赖于它们。特别地，如果字段不同，对象将获得新的标识;我们称以这种方式处理的字段为严格的23领域的将字段视为严格字段会使依赖性信息变得粗糙，从而使我们能够避免记录字段的动态依赖性。这种转移在两种情况下都有改进：（1）场很少改变，如果有的话;（2）当场改变时，对象中的所有其他信息也容易改变。例如，只有当子树移动到不同作用域中的位置时，“封闭”作用域字段才会更改。这样的更改会从根本上改变子树中的名称查找，因此假设所有查找都需要重做也没什么损失。Hoover和Teitelbaum [8]描述了在经典属性语法的增量实现中使用聚集门的两个主要弱点：（1）大型结构通过无数的复制规则传递，所有复制规则都必须在更改时更新;（2）大型聚集中的单个更改会导致依赖于聚集中任何内容的字段的使用改善了这两个问题：（1）更改字段（例如声明的类型）通常并不意味着对象本身已经更改，（2）每个字段都有自己的依赖项集。因此，由于我们的属性语法可以使用带有字段的对象来表示集合，并且各个对象可以参与细粒度的依赖关系，我们已经解决了Hoover和Teitelbaum提出的两个主要问题。但是，虽然我们可以有效地使用对象来将符号表构造成各种轮廓，但我们在图1中的示例仍然使用聚合来表示局部绑定集。因此，如果在decl集中添加或删除任何声明，则必须重新执行此作用域上的每个名称查找。我们通过使用一个预定义的Table数据类型来解决这个问题，该数据类型的实现以一种特殊的方式处理增量。我们修改了at- tribute语法，为每个声明收集一个条目表：decl.scope.tablew Table（id，{d}）查找函数更改如下：function lookup（id，s）如果s = ROOT_SCOPE则结果= NOT_FOUNDelsecase get（s.table，id）of//如果有一个或多个，则任意选择{x，.} =>结果= x|{}=> result = lookup（id，s.enclosing）endcaseendif除了get的特殊行为之外，这将具有与原始属性gram- mar相同的增量性能。读取表格时，Use节点将附加到表格字段通常，只要整个表发生更改，就会激活此Use节点，但get操作会将Use节点移动到表的更深处，使其留在表中专用于保存给定标识符的条目的部分。因此，使用节点将仅被激活（并且查找24如果表的该部分发生变化，则会导致再次发生）。如果表之前没有标识符的条目，则使用空的声明集创建一个条目。这种“漏洞”（如Maddox和其他人所使用的）会导致在将条目添加到先前传递的范围时重新执行查找。假设封闭被定义为一个严格字段，那么只有这些动态依赖关系必须被添加。Hoover和Teitelbaum的实现利用了三个额外的数据结构：复制旁路树、应用程序树和“始终传播”列表。应用程序树类似于我们的Use列表。（我们的Partial树没有类比，因为经典的属性语法不允许集合。“总是传播”列表和复制旁路树用于避免更新复制规则的成本，特别是那些将聚合复制到树中多个位置的规则。当使用对象实现聚合时，只有当严格字段更改或对象本身是新的时，对象引用才会更改。因此，复制规则不太可能过时。我们在下一节中的实验表明，其余的复制规则几乎没有成本。3执行这些想法已经在APS [1]到Java编译器的原型子集中实现，该编译器在经典属性语法之上处理条件和远程功能它可以用来生成本文中描述的增量求值器。 作为一种比较方式，它还可以生成单独使用静态信息而不是选定的动态依赖项的增量实现。本质上，“纤维”属性被转换为承载价值的属性。出于效率的原因，这些额外的属性本身不携带字段值，而只是它们所表示的值的哈希码的总和。这种实现是不安全的（一个字段可能会改变，而哈希码的总和不会改变）;我们只将其我们的研究结果表明，使用动态依赖比一个纯粹的静态实现，通过比较这个基准。在原型中，指定哪些字段被收集，对于那些没有被收集的字段，它们是否应该被认为是严格的。在这个例子中，只收集decls和used字段，并且我们将封闭字段指定为strict。该实现使用了一种高效的技术来增量地构建声明和消息包;在恒定时间内完成一个小的插入或删除。我们在一个人工测试用例上运行求值器：一个外部块有1000个声明，100个内部块，每个内部块有10个内部声明和10个赋值语句。变量名称是从一组超过350个单词中随机选择的。表1描述了所测量的操作。我们从新创建的树开始测量树的初始属性下一个操作显示了如果我们在标记某个固定的节点集（任意选择）后重新运行求值器会发生什么，就好像它们被编辑过一样。换句话说，我们有一个空的受影响集，尽管系统认为所有属性都来自编辑25表1基准操作操作编辑尺寸（不平衡）编辑大小（平衡）初始1050413200NOP编辑60445变更类型50314新的全球60358表2人工测试用例的增量结果（不平衡）。列表表格静态动态静态动态访问时间访问时间访问时间访问时间初始14605932146058581460540814605298NOP编辑2667721116226675511162变更类型900670711075900615611073新的全球90086865306715900815511543网站受到影响。第三个操作是将1000个声明列表中间的某个声明从integer类型更改为string类型。最后一个操作是在这个列表的中间插入一个新的声明。我们在两种不同的情况下运行求值器：当树不平衡时不平衡树的高度超过1000个节点，而平衡树的高度只有19个节点。表1给出了这两种情况下的编辑大小（根据编辑站点和根之间的节点数，包括）。表2给出了四个不同评估器使用两种度量的运行时间。对于每个评估器，我们给出访问次数和执行增量更新的时间（以毫秒为单位）。这些时间是在装有JDK 1.4.0的轻载Sun Ultra 10上获得的，是忽略两次运行后十次运行的平均值对于每一次运行，我们创建一个新的树，然后测量所有四个操作。在左边，我们有使用原始属性语法的结果（当每个轮廓都有对象列表时）。在右边，我们使用修改后的属性语法，使用表抽象，允许动态依赖关系附加到表中对应于正在查找的标识符的绑定集。在每种情况下，我们将纯静态实现（表3重复所有26表3人工测试用例的增量结果（平衡）。列表表格静态动态静态动态访问时间访问时间访问时间访问 时间初始19099847190997731909943519099302NOP编辑312171670312122670变更类型1121371973211213153730新的全球112176525042658112171505416这些平衡树的实验对于纯静态情况和使用选定的动态依赖关系的情况，初始评估具有相同的访问次数我们是否使用列表或表格也不会影响访问次数。(The在平衡的情况下，由于节点的数量增加，访问的数量增加。然而，纯静态的实现速度较慢，因为有额外的值承载属性.在动态情况下，生成的属性仅对计划有影响表实现也比列表实现快，因为1000个项目的哈希表比相同大小的列表允许更快的访问。在NOP编辑案例中，由于脊柱标记，我们在不平衡案例中仍然有大量的访问。我们还看到动态依赖允许我们避免重做工作。这些好处在平衡的情况下尤其明显，因为访问次数大大减少即使在不平衡的情况下，当使用动态依赖关系时重做的访问也更便宜。第三种情况是更改其中一个全局变量的类型，再次显示了动态依赖关系的好处。在纯静态的情况下，增量更新失去精度;它只确定一个或多个全局变量具有新类型。几乎所有的树都必须重新评估。另一方面，动态依赖性提供了所需的精度;只有使用更改后的全局需要重新访问。平衡或不平衡，使用列表或表格，评估器需要5毫秒或更少。由于计时的分辨率为毫秒，因此差异可能并不显著。最后一种情况，添加一个新的全局变量，显示了表抽象如何使这些依赖关系更加精确。没有表的帮助，依赖关系太粗糙，不会比纯静态情况更好。这些数字使人们可以得出一些初步的结论。使用动态依赖允许更高的精度，因此更好地执行递增，特别是当与表的特殊实现相结合。有趣的是，虽然平衡树给出了一个渐进更好的性能，甚至27一个超过10000个节点的树不够大，不能显示出很大的好处。基本上这是因为额外的访问是非常便宜的，而不可避免的访问执行不平凡的任务。访问次数不能很好地代表评价时间。这项工作只是初步的和调查性的。在未来的工作中，我想尝试更多种类的变化和更大的语言描述。我还对将原型与具有细粒度版本控制的软件环境（如Fluid项目）集成感兴趣[4]。4结论本文展示了如何通过两种技术之间的合作来逐步实现远程属性语法：静态调度确保字段在使用之前被完全定义;动态依赖关系确保远程使用更改的字段被标记为编辑站点。如果没有静态时间表，通过动态依赖关系确定的编辑站点可能会被标记为“太晚”，也就是说，在评估已经完成之后。如果没有动态依赖项，静态调度初步结果表明，这种合作允许编辑，如添加一个全局变量或变量的类型的变化，以通过一个大型程序精确跟踪。在具有10000个节点的示例中，精度使增量评估的速度提高了50倍。确认我感谢威廉·雷特尔特、乔·萨拉四世和匿名的评论者提供了有益的意见。引用[1] Boyland，J.T.，“化学成分的描述性组成”，博士论文，加州大学伯克利分校（1996年），技术报告UCB//CSD- 96-916。[2] Boyland，J.T.，分析属性语法，在：K. Koskimies，editor，Quancher Construction：7th International Conference，CC31比49[3] Carle，A.和L. Pollock，关于层次属性语法，ACM编程语言和系统交易18（1996），pp.16比2928[4] Chan ， E. C. 的 方 法 ， J. T. Bo