类型安全的Traffic函数：自动树遍历与应用

100网址：http://www.elsevier.nl/locate/entcs/volume70.html18页使用类型安全的Traffic函数范登布兰德KlintJ.J.VinjuCentrum voor Wiskunde enInformaticaKruislaan 413，NL-1098 SJ Amsterdam，荷兰摘要项重写是进行程序分析和程序转换的一种有吸引力的技术。树（术语）遍历经常使用，但不支持标准术语重写。 本文通过增加两种原始树遍历策略和三种类型的遍历来扩展多排序一阶项重写的自动树遍历。这些所谓的遍历函数可以是自顶向下的，也可以是自底向上的。它们可以是sort_mapping- ing、映射到单个排序或这两者的组合。Traffic函数设计简单，在一阶多排序集合中的应用是类型安全的，可以很好地实现。我们描述了遍历函数的操作语义，并讨论了应用。1引言程序分析和程序转换通常以程序的语法树为出发点。这个树上的操作可以用很多方式来表示，从命令式或面向对象的程序到属性语法和重写系统。人们遇到的一个常见问题是如何表示树的遍历：访问树的所有节点并从某些节点提取信息或对某些其他节点进行更改。可能出现在程序语法树中的节点类型由编写程序的语言的语法决定。通常，语法中的每个规则对应于语法树中的节点类别。现实生活中的语言是由包含几百到一千条语法规则的语法描述的。这立即揭示了编写树遍历的一个障碍：一个简单的递归遍历函数应该考虑许多节点类别，其定义的大小将相应地增长。如果我们意识到遍历函数只会做一些真正的工作（除了遍历）为非常少的节点类别。这个问题需要一种自动化的形式来处理树遍历本身，这样人类程序员就可以专注于少数几个2002年由ElsevierScienceB. V. 操作访问根据C CB Y-NC-N D许可证进行。1010000节点类别，其中真正的工作要做。换句话说，我们希望将树遍历作为程序员的内置功能，而不是负担根据以前的经验[3，5，6]，我们知道术语重写是一种方便的、可扩展的技术，用于表达单个程序和完整软件系统的分析、转换和因此，在本文中，我们解决的问题是如何树遍历可以添加到长期重写范式。一个重要的要求是有一个自动树遍历的类型化设计，这样术语总是格式良好的。另一个要求是设计和使用的简单性。特别是，我们更愿意留在一阶物种的领域内。在本介绍的其余部分，我们将简要概括术语重写，并讨论为什么遍历函数在术语重写中是必要的在第2节中，我们扩展了代数规格形式主义Asf+Sdf[1，9]与遍历功能，并在第3节中，我们给出了一些小的例子，使用这些遍历功能。遍历函数的操作语义在第4节中给出。第5节描述了遍历函数的经验，第6节给出了讨论，并讨论了相关的工作。术语重写算法1最内层重写的解释器。functinnermost（term;rules）（ fn;chillow ） ： =decompose（term）children：=nilforeachchild inchildren dochillow：=append（chillow;innermost（child;rules））odterm：=compose（fn;chillow）reduce：=reduce（term;rules）return ifreduce=fail thentermelsereduce 减少功能（术语;规则）foreachrule inrules do（ lhs;rhs ） ： =decompose（ rulee ） 绑 定 ： =match（term;lhs）如果绑定6=失败，则returninnermost（substitutee（rhs;bindings）;rules）od返回失败。项重写中的基本见解对于理解本文中描述的遍历函数是重要的因此，我们给一个简短的和非正式的重述最内项重写。[11]见《无量寿经》项是由常数组成的前x表达式（例如，A或12），变量（例如，X）或功能应用（例如，f（a，X，12））。为了简单起见，我们将常量视为空值函数。闭项是没有变量的项重写规则是一对项T1！ T2. T1和T2都可能含有10222假设T2中的每个变量也出现在T1中。如果一项在结构上等于变量1的模出现，则该项匹配另一项（例如，f（a，X）匹配f（a，b））并导致绑定（例如，X与b结合）。 由匹配产生的绑定可以用于替换，即，将术语中的变量替换为它们所绑定的值。给定一个封闭项T和一组重写规则，重写规则解释器的目的是找到一个可以减少的子项：所谓的redex。如果T的子项R与规则T1！T2，由该匹配产生的绑定可以在T2中被替换，从而产生T。R0然后在T中替换 T0 并且继续搜索新的Redex。重写停止时，没有新的redex可以找到，我们说，这项，然后在正常形式。选择Redex的不同方法可能会产生不同的结果。 在本文中，我们限制我们的注意力最左最里面的重写中的redex搜索从左到右，自下而上的方式。重写规则解释器的操作在A1中更详细地示出。函数match和substitute没有进一步定义，但具有刚才概述的含义。这些函数分解和组合了许多术语和规则，并在 一份名单请注意，基础术语表示可以是类型化的，也可以是非类型化的.match、substitute、decode和compose函数必须考虑到这一点。观察函数innersiderst如何在尝试减少项本身之前减少当前项的子项。这实现了对术语的自底向上遍历。还要注意，如果项的归约失败，它会返回自身作为结果.如果可能的话，函数reduce执行一个缩减步骤。它在所有规则中搜索匹配的左侧，如果找到，则将成功匹配产生的绑定替换到相应的右侧。然后，通过最内层重写进一步减少修改后的右侧。在第4节中，我们将扩展算法1以覆盖遍历函数。为什么要在项重写中遍历函数？重写规则非常方便地表达树上的转换，人们可能会想为什么需要遍历函数。我们将通过包含自然数的简单树来阐明这一点。图1显示了一个简单树语言的Sdf语法[10]。叶子是自然数，节点是用二进制构造函数f、g或h之一构造的。现在可以很容易地定义这些树上的变换。例如，如果我们想替换所有出现的1 如果一个特定的变量名在一个模式中出现不止一次，匹配算法就必须做一些额外的工作。通常，不同的出现被重命名为新的变量，并添加相等性检查。103f（Tree，Tree）-> Treeg（Tree，Tree）-> Tree h（Tree，Tree）-> Tree->树Nat模块树语法进口排序树上下文无关语法图1：简单树语言的Sdff乘h，则以下规则如下：[t1]f（T1，T2）=h（T1，T2）将这一规则应用于f（f（g（1，2），3），4）项，可以通过两个步骤（使用最内层约简）得到规范形式：f（f（g（1，2），3），4）->f（h（g（1，2），3），4）-> h（h（1，2），3），4）类似地，如果我们想用h（T1，h（T2，T3））替换所有f（g（T1，T2），T3）形式的子树，我们可以通过以下规则实现：[t2]f（g（T1，T2），T3）=h（T1，h（T2，T3））如果我们把这个规则应用到f（f（g（1，2），3），4）上，我们一步得到一个标准形f（f（g（1，2），3），4）->f（h（1，h（2，3）），4）注意，在这两种情况下，重写的标准（最内层）归约顺序是ing系统负责术语的完整遍历。然而，这种优雅的规范有三个严重的局限性。首 先，如果我们想得到规则[t1]和[t2]的组合效果，我们会得到不可预测的结果，因为这两个规则相互干扰：组合的重写系统被称为不一致。将上述两个规则应用于我们的样本项f（f（g（1，2），3），4）可以在两个步骤中得到h（h（g（1，2），3），4）或h（h（1，h（2，3）），4），这取决于在第一个约简步骤中是应用[t1]还是[t2]。第二个问题是重写规则不能访问任何上下文信息。换句话说，重写规则只有一个参数，即与左侧匹配的特别是对于程序转换，这是非常有限的。第三，在普通（类型化）项重写中，仅允许类型保持重写规则，即，重写规则左手侧的类型必须等于该规则右手侧的类型。子术语只能被相同类型的子术语替换，从而强制整个术语保持良好类型。以这种方式，不能表达非类型保持遍历，例如对项的（抽象）解释或分析。104=g（trafo2（T1），trafo2（T2））=h（trafo2（T1），trafo2[6] trafo2（g（T1，T2））[7] trafo2（h（T1，[五]《中国日报》trafo2（f（g（T1，T2），T3））=h（trafo2（T1），h（trafo2（T2），trafo2（T3）= N[4]trafo2（N）[1] trafo1（f（T1，T2））=h（trafo1（T1），trafo1（T2））[2] trafo 1（g（T1，T2））=g（trafo1（T1），trafo1（T2））= N->树->树模块Tree-trafo 12导入树语法导出上下文无关语法trafo1（TREE）trafo2（TREE）方程[0]trafo1（N）图2：trafo1和trafo2的定义。解决上述三个问题的一个常见方法是引入新的函数符号，消除规则之间的干扰。在我们的例子中，如果我们引入函数 trafo1 和trafo2，我们可以通过将trafo1和trafo2应用于初始项的顺序来显式地控制组合变换的结果。通过引入额外的函数sym-1，我们还获得了使用这些函数的额外参数传递数据的能力这会将数据流添加到规范中。最后，函数符号允许通过显式键入函数以接受一种类型并产生另一种类型来表达非类型保持转换。通过引入一阶函数，解决了重写规则的三个局限性。这种方法的主要缺点是，我们失去了内置的最内层重写功能，可以在没有显式程序员的一部分。需要额外的重写规则来定义trafo1和trafo2对输入项的遍历，如图2所示。 观察图中的方程[2]和[5]分别对应于原始方程[t1]和[t2]其他方程只需要定义树遍历。定义遍历规则需要语法中所有产生式的明确知识（在本例中是f、g和h的定义）。在本例中，每个函数的规则数量与图1所示语言的大小直接相关。对于大型文法，这显然是不可取的。本文提出的遍历函数解决了项遍历所需的额外规则问题，同时又不损失一阶函数携带数据的实际能力和具有非排序保持变换。1052Asf+Sdf中的函数我们希望在多排序的一阶项重写语言Asf+Sdf[1，9]中自动进行树遍历Asf+Sdf使用上下文无关的语法来定义术语的签名因此，术语可以用任意用户定义的符号来书写上下文无关语法在Sdf2中定义。术语在Asf3中定义的重写规则中使用。为了本文的目的，Asf的以下特性是相关的：多分类（类型化）术语。无条件和有条件的规则。条件有三种形式：项之间的相等、项之间的不等和引入新变量的所谓赋值条件。只有在所有其他规则都失败时才尝试的默认规则。项通过最左最内归约进行归一化。遍历函数的思想如下。程序员通过提供签名和指定重写规则来设计新的功能。遍历函数的签名也必须被定义。这是一个普通的声明，但是它被显式地标记为属性遍历。我们称这样一个带标签的函数为遍历函数，因为从用户的角度来看，它会自动遍历一个术语：术语遍历的重写规则不再需要指定，因为它们是由遍历属性自动提供的。规范编写者只需要为遍历函数实际访问的节点遍历属性提供的功能定义遍历行为，而用户提供的重写规则定义节点的访问行为如果在最内层重写期间，遍历函数作为redex的最外层函数符号出现，则该函数将在进一步的约简发生之前首先用于遍历redex。从概念上讲，遍历函数是一个可能很大的重写规则集的简写。对于每个遍历函数，可以计算一组重写规则，以实现某些子项的遍历和实际重写。这是定义遍历函数语义的好方法。更多的细节可以在[7]中找到。问题是在我们的全类型设置中我们可以提供什么样的遍历。我们允许三种类型的函数用于访问行为和两种类型的遍历策略，我们现在按顺序讨论。这种方法的优点和局限性将在第6节中讨论对于广泛的例子，我们请读者参考[7]。交通职能分为三种类型，定义如下：2 定义形式主义。3 代数规范形式主义。106Transformer：一个将遍历其rst参数的排序保持转换。可能的额外参数可 能 包 含 在 遍 历 期 间 可 以 使 用 （ 但 不 能 修 改 ） 的 附 加 数 据Transformer的声明如下：f（S1; ：;Sn）！S1 f遍历（trafo）g因为Transformer总是返回相同的排序，所以它是类型安全的。变换器是用来变换一棵树的.累加器：所有节点类型到单个类型的映射。它将遍历它的第一个参数，而第二个参数保留累积的值。累加器声明如下：f（S1;S2; ：;Sn）！S2f遍历（accu）g每次应用累加器后，累加的参数都是最新的.累加器的下一个应用程序（可能在术语中的其他地方）将使用累加参数的新值。换句话说，累加器在遍历期间充当全局可修改状态累加器函数从不改变树，只改变其累加的参数。此外，第二个参数的类型必须等于结果类型。累加器的最终结果是累加参数的值。通过这些限制，累加器对于每个实例也是类型安全的。累加器是用来从树中提取信息的。累积Transformer：一种排序保持转换，在遍历其rst参数时累积信息第二个参数保持累积值。累加转换器的返回值是一个由转换后的第一个参数和累加值组成的元组累加Transformer声明如下：f（S1;S2; ：;Sn）！S1#S2 f遍历（accu，trafo）g一个累积Transformer被用来同时从树中提取信息并对其进行变换。Transformers、transformers和accumulating transformers可能在它们的第一个参数中过载，以获得异构树的访问者。这意味着单个遍历函数可以在单个遍历中访问不同类型的节点。遍历函数的可选额外参数可以携带信息，其定义重写规则可以通过使用条件从其子对象中提取信息。因此，我们可以很容易地表示使用非局部信息的分析和转换有了这三种类型的穿越，就必须为它们提供穿越策略。遍历策略决定了遍历的顺序，“深度”的遍历。我们为每种类型的遍历提供了以下两种策略中的一种选择。自底向上：函数遍历节点的所有子树，而其重写规则用于以自底向上的方式访问节点。注释107模块Tree-sum importsTree-syntax exports上下文无关语法sum（TREE，NAT）->NATf遍历（accu）g方程[1]sum（N1，N2）= N1 + N2模块Tree-inc importsTree-syntax exports上下文无关语法inc（TREE）-> TREEf遍历（trafo）g方程[1]inc（N）= N +1在中国（F（g（f（1，2），3），出来F（（f（2，3），4），（g（4，5），6）））（g（5，6），7））图3：Transformerinc递增树中的每个数字在sum（f（g（f（1，2），3），g（g（4，5），6）），0个）出来21图4：累加器sum计算树中所有数字的和。108自底向上选择此行为。没有明确指示访问策略的遍历函数也使用自底向上策略。自上而下：函数以自上而下的方式遍历节点的子树，并在其重写规则之一适用的第一个节点处停止循环，并且不转到该节点的任何子树。注释自顶向下选择此行为。具有自底向上策略的Transformer类似于标准的最内层重写;它是排序保持和自底向上的。这就好像在一个Transformer函数的上下文中定义了一个小型重写系统。 不同之处在于，Transformer函数在一个节点上进行一次约简，而最内层约简则完全规范化一个节点。自顶向下策略相当强大，因为它会停止，允许用户在某些条件下继续遍历。请注意，水平顺序（从左到右或从右到左）也可能是一个参数。在这项工作中，我们专注于从左到右的遍历。3示例在对遍历函数进行了一般性的描述之后，是时候说明这些概念了。我们将给出一个非常简单的例子，说明刚才描述的每种类型的遍历函数。更真实的例子在第5节中给出。109模块Tree-pos导入Tree-syntax导出上下文无关语法pos（TREE，NAT）-> TREE #NATf遍历（accu，trafo） g方程[1]pos（N1，N2）= N1 * N2，N2 + 1>在f（g）（f（1，2），3），g（g（4，5），6）），0个）出来图5：累加Transformerpos将每个数字乘以其在树中的位置。增加树中的数字。 图3中的规范显示了TransformerInc.它的目的是增加树中出现的所有数字。将inc应用于样本树的结果也显示在图3中。把数字放在一棵树上。第二个例子展示了累加器的用法。我们要解决的问题是计算一棵树中所有数字的和。图4中的累加器和解决了这个问题。注意，在等式[1]中，变量N1表示当前节点（一个数字），而变量N2表示迄今为止已经累积的和（也是一个数字）。乘以树中的位置。最后一个示例显示了累加Transformer的用法。遍历函数是在树的自底向上遍历中确定每个数字的这是通过图5所示的累加Transformerpos一般的想法是在遍历过程中累积每个数字的位置，并将其用作乘数来转换数字节点。1104操作语义在本节中，我们展示了遍历函数的操作语义。读者可以参考[7]，了解不同风格的语义，即用正常的重写系统来表达遍历函数。本节中的语义更适合作为实现的参考我们从算法1中描述的正常最内层重写开始。在这个算法中，我们假设我们有一个类型化的术语表示，因为我们希望有类型安全的遍历函数。这意味着每个构造函数和每个函数符号都可以关联一个一阶类型。 例如，函数f可以具有类型1你好！R.如果n= 0，则f是r型常数。如果n >0，f要么是一个构造函数，要么是一个参数类型分别为1;：;n的函数。如果我们允许元组1110算法2一个扩展的解释器，用于最内层重写。functinnermost（term;rules）（fn;chillow）：=decompose（term）儿童：=零foreachchild inchildren dochillow '：=app end（chillow';innermost（child;rules））odterm：=compose（fn;chillow'）reduce：=switch function-type（ fn）case遍历：traverse（term;rules）casenormal：reduce（term;rules）;return ifreduce= fail thenterm else reduce术语，我们还应该定义元组的类型。元组类型简单地由（1）表示2）的情况。当然，match函数应该注意只匹配具有匹配类型的术语。我们的compose函数获得了一个额外的参数，指示它应该使用哪种类型的函数来构造一个术语。主要算法由正常的最内层约简策略组成，但当遇到遍历函数时，我们切换到不同的模式。算法2中的switch语句检测到一个遍历函数，并将控制权移交给一个名为transverse的函数，而不是调用reduce。该函数在算法3中示出它为每种遍历函数使用不同的参数启动遍历回想一下，输入项的形式为trf n（T1;T2;：;Tn）（n>=1），其中trfn是一个逆函数，T1是要被逆的项，T2是（可选的）累加器矩阵t，而T3;：;Tn是（可选的）剩余的参数。 实际的遍历是通过td-or-bu（“top-down orbottom-up”）完成的，根据trfn的遍历策略，td-or-bu使用自顶向下或自底向上。td-or-bu的变元由不同类型的遍历决定。我们通过重用最内层重写算法的reduce根据遍历策略（自底向上或自顶向下），它可以在遍历子对象之前或之后应用。为了是类型安全的，遍历函数的类型在遍历术语时改变。它的类型总是与当前访问的节点的类型相匹配。此行为由type-compose函数编码。对于保持类型的转换器，rst参数的类型和结果参数适应当前访问的节点的类型。类似地，对于累加器，只有第一个参数的类型被改变，而累加的参数的类型保持不变。最后，对于组合，rst参数的类型和结果元组类型被更新。在函数visit-children中遍历children时，考虑到累积值必须在每个child之间传递。请注意，在Transformer的情况下，通过始终传递值nil来忽略此累积值。112;在成功应用用户定义的规则之后，函数make-reduce根据遍历的类型决定如何处理reduce如果它是一个Transformer，则reduce替换redex。在累加器的情况如果它是一个累加的Transformer，元组的第一个元素替换redex，而第二个元素替换累加的参数。算法3遍历函数的解释器（1/2）。functtraverse（term;rules）（trfn;args）：=decompose（term）;term：=head（args）;args：=tail（args）开关类型（trfn）case\trafo“：（reduct;nil）：=td-or-bu（trfn;term;nilargs;rules）returnreducecase\accu“：（reduct;accu）：=td或bu（trfn;term;head（args）;tail（args）;rules）返回accucase\accu，trafo“：returntd-or-b u（trfn;term;head（arg s）;tail（args）;rule s）;. functtd-or-bu（trfn;term;accu;args;rules）返回切换策略（trfn）case\top-down“ ：top-d ow n（trfn;term;acc u;arg s;rules）case\bottom-up“ ：bottom-u p（trfn;term;acc u;args;rule s）;.functtop-down（trfn;term;accu;args;rules）reduce：=reduce（type-compose（trfn;term;accu;args）;rules）return ifreduce=fail thenvisit-childre n（trf n;term;acc u;args;rules）elsemake-reduc t（trfn;term;reduc t）.functbottom-up（trfn;term;accu;args;rules）（term;accu）：=visit-children（trfn;term;accu;args;rules）reduce：=reducee（type-compose（trfn;term;accu;args）;rules）returnifreduce=fail 然后（term;accu）elsemake-reduc t（trfn;term;reduc t）.functvisit-children（trfn;term;accu;args;rules）（fn;chillow）：=decompose（term）children'：=nilforeachchild inchildren do（reduct;accu）：=td-或-bu（trfn;child;accu;args;rules）chillop '：=app end（chillop';reduct）odreturn（com pos e（f n;chillow'）;accu）. 减少功能（trfn;term;reduct）返回开关类型（trfn）case\trafo“：（reduct;nil）case\accu“：（term;reduct）case\accu，trafo“：reduce;.113最后，当我们从遍历返回时，顶层函数遍历为每种类型的遍历函数返回不同的范式。在Transformer的情况下，简单地返回转换后的项。当它是一个acc.114算法3遍历函数的解释器（第2/2部分）functty pe-com pos e（fn;term;accu;arg s）t：=result-type-of（term）交换机类型（fn）情况\trafo“：1你好！1：=type-of（fn）type：=t你好！不case\accu“：12你好！2：=type-of（fn）type：=t2你好！2case\accu，trafo“：12n！（12）：=type-of（fn）type：=t2你好！（t2）、returncomppos e（fn;ty pe;[term;acc u;arg s]）.mulator，我们返回累积的参数。累加Transformer返回已变换项的元组和累加参数的最终值。5经验已经进行了各种实验，包括COB-OL上的转换、Sdf检查器、Sdf重构和Java重构。我们在这里更详细地讨论在软件改进小组（SIG）的一个联合项目中，Centrum voor Wiskundeen Informatica（CWI）和Vrije Universiteit（VU）遍历函数已被应用于COBOL程序的转换[18]。这是基于[15]中描述的早期工作。目的是将VSCOBOL II迁移到COBOL/390。一个现有的工具（IBM的CCCA）用于执行基本的、技术上必要的转换。然而，这使得许多结构保持不变，这些结构将在下一个COBOL标准中获得“archaic”或“ob-blog”的地位。此外，编译器专用的COBOL扩展保留在代码中，并且几个过时的运行时实用程序可以被标准COBOL功能所取代。这个源到源转换的集合被形式化为许多遍历函数。每个函数都执行一个微小的子任务。这样的子任务的示例是：添加END-IF关键字以关闭IF-语句。将嵌套的IF-语句替换为EXPLOATE-语句。用标准COBOL 语句替换过时的CALL实用程序。Reduce GO-TO语句：一种goto消除算法，它本身由20多个不同的转换规则组成，这些规则在一个xed点计算。这些子任务中的每一个（总共21个）仅由几个重写规则组成，115定义遍历函数在特定语句上的效果。有几种方法可以组合这些子任务来获得我们想要的COBOL转换工具。首先，子任务可以使用正常的Asf+Sdf规则使用功能应用程序进行组合。其次，每个子任务本身就是一个Asf+Sdf规范，可以在命令行上单独运行。结合生成的解析器和通用的漂亮打印机，这些工具可以使用简单的shell脚本构建完整的源代码到源代码转换工具。在一个实验中，转换工具被应用于一个测试库，582个COBOL程序，包含440，000行代码，以获得以下结果：添加了17，000个END-IF。4，000条线路被更改，以消除CALL-实用程序。1，000个GO-TO已被消除（约占所有GO-TO的65%）。使 用ASF解释器完成整个转换花费了两个半小时。遍历函数的编译版本在这个实验完成的时候还没有准备好，但是它会减少至少15倍的时间因此，估计的编译执行时间大约为10分钟。在这个翻新工厂中使用的COBOL语法中的产品数量是600，执行的转换数量是21，正如我们上面看到的。每个转换步骤只需要遍历一次树。我们可以得出结论，最大数量为4 需要重写的规则是21600=12：600！实际上，由于使用了遍历函数，重写的实际次数少于100次。在其他项目中，遍历函数的经验似乎也非常积极。引用[14]：在 撰 写 本 文 时 ， Sdf 转 换 框 架 （ FrameworkforSdfTransformations，FST）由24个遍历函数描述，每个函数只有几个重写规则。Sdf语法本身有大约100个相关的产品。 这是对遍历函数支持的有用性的显著指示。在最坏的情况下，我们将不得不处理大约2400个重写规则。“6讨论本文中概述的方法比手动编写显式遍历树的函数有很大的优势。4 在实践中，这个数字可以更小，因为手写的规范可以明确地避免访问某些子树。116无类型键入战略基元[第16话]ELAN [2]内置战略改造工厂[八]《中国日报》遍历功能图6：遍历方法的分类。与手工编写的遍历代码相比，该遍历函数方法更具有语言无关性、类型安全性和简洁性。由于遍历函数的实现独立于它们所应用的源语言，因此该方法是类型安全的，因为只有类型保持转换和有限的排序改变转换可以表示。它是简洁的，因为只需要为实际需要转换的节点类型（而不是只需要访问的节点在手写代码的情况下，程序员必须显式地遍历树中的所有节点，代码量将变得庞大。此外，这段代码依赖于被转换的源语言。类型安全依赖于用于表示树的数据结构。可以使用通用树数据类型和松散类型安全，或者可以为每个节点类型使用不同在后一种情况下，必须编写大量的接口和遍历代码。原则上，该代码适合于自动生成。对于JAVA，这种方法在[12]中描述。相关工作 我们在图6中区分了四种直接相关的方法并在下面讨论它们。关于相关工作的更广泛的覆盖范围，我们参考[7]。ELAN [2]是一种多排序、一阶重写规则的语言，扩展了一种策略语言，用于控制各个重写规则的应用。其策略原语（例如，不知道选择，不关心选择）允许制定非确定性计算。目前，ELAN不支持通用树遍历，因为它们不容易与ELAN的类型系统相结合。Replego [17]是一种无类型的术语重写语言，提供用户定义的策略。在它的策略原语中，重写规则和几个通用的遍历操作符允许以抽象的方式定义任何树的遍历，如自底向上和自顶向下因此，树遍历是可以与重写规则分开重用的第一类对象Replego提供了一个具有各种命名遍历策略的库，例如，自底向上（s），自顶向下（s）和最里面（s）。在[13]中，提出了一种类似于Nigrogo的语言，它允许类型化的泛型遍历，以实现类型保持和类型统一策略。转换工厂[8]是一种从语言定义中生成Asf+Sdf重写规则的方法。在生成阶段之后，117用户通过提供变换的名称并通过更新默认遍历行为来实例化实际变换。注意，生成的重写规则是良好类型的，但是非常不特定的类型被用于获得生成的重写规则的可重用性。转换工厂提供两种遍历：转换器和分析器。Transformer转换它访问的节点。分析器是遍历、组合函数和默认值的组合。生成的遍历函数将每个节点减少到默认值，除非用户覆盖它。组合函数以最内层的方式组合结果。对高阶行为的模拟又一次导致了不特定的类型。与Traffic函数的关系Traffic函数来自于我们在Asf+Sdf中为现实语言编写程序转换的经验。这两个企业和转型工厂也提供了解决方案，以弥补我们遇到的问题。Rupgo扩展了遍历策略组合子和用户定义策略的项重写，但我们更保守，只扩展了一阶项重写的遍历原语的固定集合。 遍历函数的一个贡献是，它们为一阶规范中的树遍历提供了一种简单的类型安全方法。结果很简单，可以以简单的方式进行静态类型检查，并且可以高效地实现。最近，在[13]中提出了另一种类型的树遍历系统。它是基于遍历组合子，如在Rollgo中找到的。虽然这个打字系统在很多方面都很吸引人，但对用户来说有点复杂。两个泛型类型被添加到一阶类型系统：类型保持和类型统一策略。为了在这些泛型类型和普通类型之间进行调解，需要一个额外的组合子，它组合了类型保护和类型提升操作符。在遍历函数的情况下，不需要扩展类型系统，因为树遍历与函数应用结合在单个遍历函数中。这允许解释器或编译器自动创建类型保护与遍历函数类似，在[13]中，遍历类型也被划分为类型保持对象和映射到单个类型。元组组合不被操作。与转换工厂（它最直接地启发了我们的遍历函数）相比，我们提供了一组稍微不同的遍历函数，并减少了符号开销。我们还消除了对高阶参数的需求在实现层面，我们不生成Asf+Sdf规则，但我们在Asf+Sdf的标准解释器和编译器中加入了遍历函数。因此，执行更高效，规范更可读，因为用户不会面对生成的重写规则或模拟的高阶参数。Traffic函数的编译我们扩展了Asf+Sdf118编译器[4]以非常简单的方式使用遍历函数。我们在这里只是简单地描述一下方法。对于遍历函数的每个定义重写规则和对遍历函数的每个调用，重载参数的类型和可选的结果类型被转换为单个通用类型。 中第一次近似，结果是一个大的类型不安全函数，可以使用现有的编译方案编译。类型安全的实现如下。如果重写规则的第一个参数被构造函数保护，这将自动强制类型安全。如果它没有被保护（即，参数是单个变量），我们向重写规则添加一个条件，该条件在运行时检查匹配树的类型。编译后的代码将是类型安全的。生成的编译代码通过调用一个小的运行时库进行扩展。它们负责实际遍历树，并在尝试应用编译后的遍历函数之前或之后传递累积的参数。结论我们已经描述了作为最内层项重写的扩展的遍历函数的项重写，并且我们已经展示了如何将其纳入Asf+Sdf。我们的方法的优点是：最常用的遍历顺序作为内置原语提供。这种方法是完全类型安全的，并且很容易进 行 类型检查。可以高效地实现业务功能。总而言之，遍历函数是简单性和表达能力之间的一个很好的折衷。对于实现问题和广泛的例子，我们参考[7]。我们的方法的主要缺点体现在处理内置原语不提供的遍历顺序时。有两种逃脱是可能的：这种遍历可以被模拟为一种内置策略的修改（通过添加条件或辅助函数），或者可以通过枚举语法的所有构造函数的遍历规则来返回到遍历的繁琐规范。扩展该方法以覆盖从左到右与从右到左遍历的可变性是可能的。确认我们收到了来自遍历函数用户的不可或缺的反馈。Steven Klusener（软件改进组）和Hans Zaadnoordijk（阿姆斯特丹大学）将它们用于COBOL转换，RalfLammel（CWI和阿姆斯特丹自由大学）和Guido Wachsmuth（大学（Rostock的）在Sdf重构中应用它们。119引用[1] J. A. Bergstra ， J. Heering ， and P. Klint ， editors. 代 数 规 范ACMPress/Addison-Wesley，1989.[2] P. Bor ovans ky，C. Kir c hner，H. Kir c hner，P. E. Moreau和C. 林盖森ELAN概述。在Claude Kirchner和Hel ene Kirchner编辑的重写逻辑及其应用国际研讨会上，第15卷理论计算机科学Elsevier，1998年。[3] M.G.J. van den Brand，A. van Deursen，P. Klint，S. Klusener和E.A.范德默伦。ASF+SDF的工业应用。In M. Wirsing和M. Nivat，编辑，AlgestheticsMethodology and Software Technology（AMAST '96），LNCS的第1101卷，第9页{18.Springer-Verlag，1996.[4] M.G.J. van den Brand、J. Heering、P. Klint和P.A.奥利维尔编译语言定义：ASF+SDF编译器。ACM Transactions on Programming Languages andSystems，2002。出现。[5] M.G.J. van den Brand、P. Klint和C.维尔霍夫系统改造的核心技术。在KG。Je ery，J. Kral，and M. Barto sek，编辑，SOFSEM'96：信息学的理论与实践，LNCS第1175卷，第235页。Springer-Verlag，1996.[6] M.G.J. van den Brand、P. Klint和C.维尔霍夫术语重写出售。In C.Kirchner 和 H. Kirchner ， editors ， Second International Workshop onRewriting Logic and its Applications，WRLA 98，1998.[7] M.G.J. van den Brand，P. Klint，and J.J. Vinju. 使用遍历函数重写术语。Technical Report SEN-R0121，Centrum voor Wiskun