目标语高阶框架中的策略构建

理论计算机科学电子笔记124（2005）149-170www.elsevier.com/locate/entcs目标语高阶框架中的策略构建Victor L.冬季1，2美国内布拉斯加大学奥马哈分校计算机科学系摘要当从策略的角度来看时，重写系统中的标记规则库可以被看作是策略表达的受限形式（例如，使用左偏选择组合子严格组成的规则集合）。本文描述了高阶机制能够动态地构建类似于规则库的策略表达式。这些策略表达式和规则库之间的一个显著区别是策略表达式可以使用任意二进制组合子（例如，左偏选择、右偏选择、顺序组合或用户定义）。此外，这些策略表达式中使用的数据可以通过术语遍历获得。描述了一个称为TL的高阶战略规划框架。在译入语中，我们可以动态地构建上一段中提到的那种策略表达。下面的演示展示了如何使用TL中可用的高阶结构来解决程序转换领域中常见的几个问题。关键词：程序转换，重写，策略编程，高阶重写，瞬态组合子，TL1介绍在术语结构中分布数据的概念是基于重写的计算的核心[11]。 在[14]中，这个问题被描述并提到1这项工作得到了美国能源部的部分支持，合同DE-AC 04 - 94 AL 85000。桑迪亚实验室（Sandia）是一个多项目实验室，由洛克希德·马丁公司下属的桑迪亚公司为美国能源部运营。Victor Winter也得到了NSF资助号CCR-0209187的部分支持2电子邮件地址：vwinter@mail.unomaha.edu1571-0661 © 2005 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2004.07.020150V.L. Winter/Electronic Notes in Theoretical Computer Science 124（2005）149分布式数据问题（DDP）当要分发的数据独立于输入时（即，对于所有输入项恒定），用于分布数据的简单策略通常可以静态地构造。例如，考虑构建一个策略，将项中的每个整数重写为整数2。这里的目标是通过重写遇到的每个整数来将整数2分布在整个期限结构中。 这是一个数据分布的例子，涉及独立于任何特定输入项的数据。相反，考虑构建一个策略，重写一个项中的每个整数，使所有整数都等于该项中的第一个整数。例如，对于给定的项t，如果t中的第一个整数是27，那么t中的所有整数都应该重写为27。这是一个数据分布的例子，涉及依赖于输入项的数据。在程序转换领域，整个术语中相关数据的分布通常比数据的独立分布更常见。例如，变量重命名、函数内联和常量传播都需要通过术语结构分布相关数据。战略/重写系统通常提供扩展，以增强其描述数据分布的能力。参数化是一种广泛用作数据分发机制的扩展。例如，ASF+SDF [1]已经扩展了一个固定的可参数化遍历函数集合[4]。另一个扩展是允许使用问题相关数据动态构建例如，在Replego [10]中，提供了一种机制，可以通过动态构造和销毁规则来在运行时在本文中，我们将研究战略规划的高阶扩展。具体来说，我们将描述如何使用称为TL的策略编程语言的高阶规则、策略和遍历来有效地在整个期限结构中分布（依赖）数据。 虽然TL目前是一个理论框架，但TL的一个受限方言已在HATS3系统中实现[6]，并且可以免费使用。所有本文提出的例子已经在HATS中实现。本文的其余部分组织如下。第2节概述了TL。第3节深入研究了TL中集合并的战略实现的内部工作原理。第4节介绍了程序转换领域中常见的两种操作。第5节讨论了一些相关的工作，第6节结束。3除了语法上的差异之外，主要的限制是HATS不支持用户定义策略V.L. Winter/Electronic Notes in Theoretical Computer Science 124（2005）149151≤ ≤ ∈∪++⇒skiplhs→rhsif条件lhs→sif条件nsn;sn12sn+sn1 2sn+> s21I（sn）修复（s1）瞬态（sn）永远不适用条件一阶策略n+1阶序贯复合的条件策略偏左选择一个一元组合子什么都不一阶策略S1限制sn2TL概述TL [14]是一个基于身份的高阶策略系统，用于重写解析树。我们使用基于身份的术语来表示重写系统，其中规则应用到一个术语的失败使该术语不变。我们使用基于故障的术语来表示系统，其中规则对术语的不成功应用会与TL相反，战略规划系统Escogo [11]和Elan [2]是基于失败的。在TL中，域（即，术语语言）使用扩展BNF定义，术语也称为解析表达式，使用特殊符号描述TL支持图1所示的结构、组合子和策略常量。Fig. 1. 目的语的基本结构除了图1所示的构造之外，TL还提供了许多单层通用遍历，从而提供了构造用户定义的遍历的能力。这些结构不是本文主题的核心，因此被省略。相反，我们只是简单地提出了一些通用的遍历，形成TL遍历库的一部分。2.1Term符号设G=（N，T，P，S）表示一个上下文无关文法，其中N是非终结符集，T是终结符集，P是产生式集，S是起始符号。给定一个任意符号B∈N和一串符号α= X1X2. 其中对于所有的1 i m：XiN T，我们说B导出α i ∈ T，P中的乘积可以用来将B展开为α。 传统上，表达B可用于表示B可在Zerorm类似地，可以写B α来表示由一个或多个展开步骤组成的推导。在TL中，我们写B[[αJ]]来表示导子B<$α的实例其结果值是以B作为其根符号的解析树 在TL，152V.L. Winter/Electronic Notes in Theoretical Computer Science 124（2005）149形式为B[[αJ]]的表达式称为解析表达式。在解析表达式B[[αJ]]中，字符串αJ是α的实例，因为αJ中的非终结符通过使用下标来约束。下标的非终结符被引用到模式变量或简单的变量，短. TL还考虑模式变量（例如，Bi）本身是一个解析表达式。在一个给定的范围内，所有出现的具有相同下标的模式变量在模式变量上放置下标的目的是使语法推导能够相对于一个或多个面向等式的约束而受到限制非终结符B和模式变量Bi之间的区别在于，B传统上被视为一个集合（或句法范畴），而Bi是一个在句法范畴B上量化的类型化变量。当解析表达式的主导符号和特定结构不重要时，解析表达式将由形式为t，t1，.的变量表示。不包含模式变量的解析表达式称为基础，包含一个或多个模式变量的解析表达式称为非基础。最后，在重写或策略编程的上下文中，这里描述的树可以并且通常被视为术语。当区别是一致的重要性时，我们将互换地提到树和术语。2.2规则TL支持以下形式的条件标记一阶重写规则：label：lhs→rhsifcondition其中LHS是项，RHS是其评估产生项的策略表达式，并且标签和条件部分是可选组件。高阶规则的形式为：label：lhs→snifcondition其中Sn是其评估产生（可能更高阶）规则的策略表达式。当解析高阶规则时，→关联到右侧。二阶无条件规则的一个抽象例子是：r：lhs1→lhs2→rhs2为了消除内部结构的歧义（例如，条件成分），可以将规则的右侧括在括号中。label：lhs→（sn）ifconditionV.L. Winter/Electronic Notes in Theoretical Computer Science 124（2005）149153∧ ∨ ¬→为了便于标记，没有条件的带标签高阶规则例如，规则的形式：r：x1→x2→x3→x4可以等价地写为：r x1：x2→x3→x4或者甚至是：2.2.1规则条件r x1x2：x3→x4规则的条件部分是由一个或多个匹配等式组成的匹配表达式。该符号改编自ρ-演算[5]，用于表示一阶匹配模空方程理论。让T2表示基树，且令T1表示可以包含一个或多个模式变量解析表达式方程t1t2是一个匹配方程。同样地，我们也可以写t2t1. 匹配方程是一个布尔值运算，它产生一个替代σ作为副产品。如果σ（t1）=t2，则将模式变量绑定到基础解析表达式的替换σ是t1t2的解，其中=表示语法相等的布尔值测试。匹配表达式是涉及一个或多个匹配等式的布尔表达式。匹配表达式可以使用标准布尔运算符构造：，，. 替换σ是匹配表达式miσ（m）的解，使用布尔运算符的标准语义计算为真2.2.2规则应用将条件重写规则r应用于树t表示为r（t），其中r是标签或匿名规则值，例如，LHSsn. 我们采用 一种ML风格的咖喱表示法，其中application是一个左关联隐式运算符，括号用于覆盖优先级，或者可以可选择地包括以增强可读性。例如，r t表示r对t的应用，并且具有与r（t）相同的含义2.3TL库中的一些一阶遍历TL支持用户定义的一阶遍历。TL还提供了一些标准的通用一阶遍历。泛型遍历有三个自由度：（1）是自底向上遍历术语还是自顶向下遍历术语，（2）是从左到右遍历术语的子项154V.L. Winter/Electronic Notes in Theoretical Computer Science 124（2005）1491⊕2M12n−1n −1n−1M还是从右到左，以及（3）是否使用标准的线程语义或广播语义来传播遍历中的策略（见2.6节）。图2给出了最常用的通用遍历的列表。第一个遍历是TDL。这种遍历将以自上而下、从左到右的方式遍历它所应用的术语。除了第2.6节中讨论的TD BR外，表中的其余条目具有类似的描述。最后两个遍历相对于给定的遍历方案执行固定点计算。遍历底向上顶向下left-to-right从右向左螺纹广播TDL√√√TDR√√√TD BR√√BUL√√√BUR√√√FIX TDL√√√FIX TDR√√√图二. 一般一阶遍历2.4高阶策略TL是一个受限的高阶战略规划框架。TL是受限制的，因为它只允许应用高阶策略的基础条款。例如，策略可能不适用于其他策略或规则，如ρ演算[5]所允许的那样在TL中，应用对于一个（基）项的n阶策略是n-1阶策略。从操作的角度来看，高阶遍历遍历一个术语，并对遇到的每个术语应用高阶策略sn因为应用的策略是n阶的，所以应用的结果将是n-1阶的策略。如果一个遍历访问m个项，则m个阶的策略将生成n-1。设s得双曲余切值.、、......得双曲余切值.表示由此产生这样的穿越。在TL中，各种二元策略组合子可以用于组合战略结果sn-1，sn-1，.，sn-1转换为战略1 2m表达式（即， 战略）。 设表示一个二进制组合子，如se-顺序组合，左偏选择，右偏选择，或用户定义的二元组合子。高阶遍历将这些策略组合成以下形式的策略表达式：sn−1sn−1. n−1V.L. Winter/Electronic Notes in Theoretical Computer Science 124（2005）14915512M遍历底向上顶向下left-to-right从右向左⊕τ第二tdl√√更多>>我第二个TDR√√更多>>我lcond tdl√√<+我第二TDR√√<+我第二次布尔√√更多>>我第二钻头√√更多>>我第二次膨胀√√<+我第二钻头√√<+我顺序tdl√√;我序列时间序列√√;我塞格布勒√√;我seq钻头√√;我图三. 一般高阶遍历有一个技术细节在上述解释中被省略了。除了使用二元组合子组合策略之外，高阶遍历还将一元组合子τ统一应用于每个结果策略。因此，产生的实际策略是：τ（sn−1）<$τ（sn−1）<$. τ（sn−1）在实践中，最有用的一元组合子是瞬态组合子，其中I组合子扮演默认的角色瞬态组合子在2.5节中描述。TL支持用户定义的高阶遍历。TL还提供了一些标准的通用高阶遍历。一般的高阶遍历有四个自由度：（1）项是自底向上遍历还是自顶向下遍历，（2）项的子项是从左到右遍历还是从右到左遍历，（3）应该使用哪个二元组合子来组成结果策略，以及（4）应该使用哪个一元组合子来包装每个结果策略。图3给出了最常用的通用遍历的列表。这个列表中的第一个遍历是rcondtdl。这个遍历将以自上而下、从左到右的方式遍历它所应用的术语。然后，结果策略将使用右偏选择组合子进行组合，最后每个结果策略将被包装在一元组合子I中。 表中的其余条目具有类似的描述。156V.L. Winter/Electronic Notes in Theoretical Computer Science 124（2005）1492.5瞬态组合器瞬态组合子是TL中一种非常特殊的组合子。这个combina- tor限制了一个策略，因此它最多只能应用一次。“最多一次”性质是瞬态组合子的特征，也是将skip引入TL框架的我们将跳跃定义为一种应用永远不会成功的策略。图4给出了两个抽象的策略常数δ和δ与组合子+和;之间的关系这些关系被认为是从一个失败为基础的框架，以及基于身份的框架的角度在基于故障的系统中，例如ELAN和ELAN，ELAN通常被称为id或identity，δ通常被称为fail。在TL的基于身份的框架中，被称为id，δ被称为skip。基于策略失败的语义t δttδtt<+ss<+<<ϵs<+sSϵs<+sSs;ss;δ;ss;δssδδsssS见图4。 id、skip和fail的语义TL定义了一个策略的形式瞬态（s）作为一个战略，减少如果已经观察到策略S的应用，则跳转到策略跳过。此外，只有最里面的（即，最近封闭的）瞬态可以观察策略的应用。这个限制是必要的，以防止级联序列的减少战略包含嵌套瞬态。瞬变现象为自我修正策略打开了大门当使用导线时-V.L. Winter/Electronic Notes in Theoretical Computer Science 124（2005）149157→为了将自修改策略应用于术语，不同的策略可以 应用于遍历过程中遇到的每个术语。例如，让int1int[[2]]表示将任意整数重写为值的规则2. 如果这样的规则是应用于一个自上而下的方式，所有的整数将被改写为2。现在考虑以下自修改瞬态策略：transmant（int1→int[[1]]）+transmant（int1→int[[2]]）+transmant（int1→int[[3]]）当以自上而下的方式应用于一个术语时，该策略会将遇到的第一个整数重写为1，第二个整数重写为2，第三个整数重写为3。所有其他整数将保持不变。2.6运输机制TL提供了两种类型的术语遍历：线程遍历和广播遍历。在线程遍历（例如，TDL、TDR、BUL、BUR），则按顺序访问术语，并且在术语之间传递单个策略。在图5中可以看到一个显示线程遍历行为的图表。在广播遍历（例如，TDL BR）一个应用程序产生的策略的不同副本将被给予一个学期的所有孩子。 例如，对策略表达式TDL BR（s）t的求值将首先将策略s应用于项t。回想一下，在最一般的情况下（即，当策略中存在瞬变时），这种应用将改变S和T。设sJ和tJ分别表示策略，从s到t的应用中产生的术语。由于TDL BR是广播遍历，因此sJ的不同副本将应用于tJ的每个子项。显示广播遍历行为的图表可以在图6.3基准：集合联合我们相信集合并具有与一些常见的转换活动相似的特征。例如，集合并的变体可以用作变量重命名、数据流分析、控制流分析、Java类文件中的符号解析[14]以及字段分布和158V.L. Winter/Electronic Notes in Theoretical Computer Science 124（2005）149S'|S1S7S2S4S5S3S6s0图五. 从策略应用角度看线程遍历TDL图Ss's'见图6。 从策略应用角度看广播穿越TDL BRJava类文件中的方法方法表构造[15]。因此，由于其广泛的适用性，我们认为集工会是一个基准问题的战略规划系统。在本节中，我们将研究如何在TL中解决联合基准。我们的方法是提升对数据的基本操作（例如，将一个元素插入集合等）到战略层面。例如，当实现union时，我们希望创建一个策略，仅当元素尚未出现在集合中时才将特定元素插入我们的union在TL中，这些类型的问题特定的一阶策略的构建可以通过高阶策略来完成。在图7中，给出了描述集合/序列表达式的语言的BNF语法。 语法的元符号是：：=、（）、>、“和“。符号（）用于表示域符号，域变量是V.L. Winter/Electronic Notes in Theoretical Computer Science 124（2005）149159联系我们setexpr：：= set set op set|set set： ：=“{“es“}“es：：= e es|（）下一页联系我们<|（<<“id > id >“）set op：：=保持E1添加e1：：工会S：使工会：es[[e1es2]]→es[[e1es2]]es[[]]→es[[e1]]es[[e1es1]]→transient（（keep e1）+（add e1））set expr[[set1union set2]]→T DL（lcond tdl union s set1）set2括在尖括号中，端子符号括在引号中。在图8中，keep和add是实现集合上的基本操作的策略，例如将元素添加到空集。策略并集s是高阶的，并且定义了单个计算步骤（例如，将一个元素“联合”成集合的策略）。最后，策略make union执行其相应的集合操作，首先针对集合1中的每个元素正确地实例化union s，然后将结果策略应用于集合2。见图7。一种描述集合/序列表达式的见图8。 术语二阶策略的实例化及其应用3.1翻译中联合的实现这里的策略主题是分解一个集合表达式{a1，a2，.， an}{e1，e2，...，em}分解为一系列增量策略，每个增量策略都可以用于评估以下形式的表达式： 高阶策略联盟S生成这样的增量策略。具体来说，当给定上下文es[[e1es1]]时，union s将提取元素e1并产生一个由条件复合keep（e1）+add（e1）组成的瞬态建立在union s上的是策略表达式（lcond tdl union s set1），它遍历set1，产生union s实例的条件组合; set 1中的每个元素对应一个实例。然后使用遍历TDL将所得到的策略应用于集合2。 记住这一点，让我们追踪表达式set 1的策略评估，其中set1={x1x2x3x4}，set2={y1x2x3y2}。（lcond tdl union s set1）的结果及其对第一项的应用 在图9至13中示出了组2中的每个单元。图9显示了初始策略160V.L. Winter/Electronic Notes in Theoretical Computer Science 124（2005）149瞬态（es[[x1es2]]→es[[x1es2]]+es[[]]→es[[x1]]）<+ transient（es[[x2es2]]→es[[x2es2]]+es[[]]→es[[x2]]）<+瞬态（es [[x 3 es 2]] → es [[x 3 es 2]]+ es [[]] → es [[x 3]]）<{y1x2x3y2}<+transient（es[[x4es2]]→es[[x4es2]]+es[[]]→es[[x4]]）{y<$1x2x3y2}见图9。具有TDL遍历的并集-+-t-ran-si-en-t（e-s[-[x2-e-s2-]]→--es-[[x-2-es-2]]-+--es-[[]-]→-e-s[-[x-2]]-）<+瞬态（es[[x3es2]]→es[[x3es2]]+es[[]]→es[[x3]]）<+ transient（es[[x4es2]]→es[[x4es2]]+es[[]]→es[[x4]]）{y1x2x3y2}见图10。与TDL遍历的并集-+-t-ran-si-en-t（e-s[-[x2-e-s2-]]→--es-[[x-2-es-2]]-+--es-[[]-]→-e-s[-[x-2]]-）-+-t-ran-si-en-t（e-s[-[x3-e-s2-]]→--es-[[x-3-es-2]]-+--es-[[]-]→-e-s[-[x-3]]-）<+ transient（es[[x4es2]]→es[[x4es2]]+es[[]]→es[[x4]]）{y1x2x3y2}见图11。与TDL遍历的并集-+-t-ran-si-en-t（e-s[-[x2-e-s2-]]→--es-[[x-2-es-2]]-+--es-[[]-]→-e-s[-[x-2]]-）-+-t-ran-si-en-t（e-s[-[x3-e-s2-]]→--es-[[x-3-es-2]]-+--es-[[]-]→-e-s[-[x-3]]-）<+transient（es[[x4es2]]→es[[x4es2]]+es[[]]→es[[x4]]）{y1x2x3y2}见图12。 与TDL遍历的联合{y1x 2x 3y2}--t-ra-ns-ien-t（-es-[[x-1e-s2-]]-→-es-[[x-1-es-2]-]-+-es-[[-]]→--es-[[x-1]-]）-+-t-ran-si-en-t（e-s[-[x2-e-s2-]]→--es-[[x-2-es-2]]-+--es-[[]-]→-e-s[-[x-2]]-）-+-t-ran-si-en-t（e-s[-[x3-e-s2-]]→--es-[[x-3-es-2]]-+--es-[[]-]→-e-s[-[x-3]]-）<+ transient（es[[x4es2]]→es[[x4es2]]+es[[]]→es[[x4]]）{y1x2x3y2x1}图十三. 使用TDL遍历的联合适用于Set2。 图10和图11分别显示了策略在遇到（应用于）元素x2和x3时的变化。 将策略应用于元素y2没有效果，如图所示12个。最后，在图13中，遍历到达集合2的末尾，此时添加元素x1注意，在这种情况下，策略和集合2都被应用程序更改以类似的方式，加上x4，{y1x2x3y2x1x4}作为最终项，跳过作为最终策略。4适应共同的转型目标在本节中，我们将研究TL解决方案，以解决在程序转换领域中出现的两个常见的转换对象。我们要提到的是，这些例子的灵感来自于类似的例子，V.L. Winter/Electronic Notes in Theoretical Computer Science 124（2005）149161|在[10]中。这两个例子都是关于图14中定义的语法片段来考虑的。 语法的元符号是：：=、（）、>、“、“、[和]。符号（）用于表示中间符号，域变量用尖括号括起来，终止符用引号括起来，而产生式的可选部分用方括号括起来4.1变量重命名在这个例子中，我们考虑一个小块结构化命令式语言的变量重命名问题。(Note图14给出的语法允许块被嵌套）。TL解决方案使用了一个函数new，该函数能够生成唯一的变量名。图15中的代码突出显示了在此设置中重命名变量时必须解决的一些问题首先，变量可以在嵌套块中重新声明。然而，假设变量不能在给定的声明列表中冗余地声明。其次，变量声明可以包括对初始表达式的赋值，该初始表达式可以包含先前声明的变量的出现。在处理带有初始化表达式的声明时，必须小心将变量与其正确的声明相关联。例如，在图15中，在内部块中的声明int x1 =x 1+1中，对初始化表达式x1 + 1中出现的变量x1的引用实际上是对外部块中x1的前一个声明的引用因此，将int x1 =x 1+1重命名为int new x1 =new x 1+ 1是不正确的。 相反，重命名的结果应该是int new x1 =x 1+ 1。这个例子中的另一个困难来自于语法定义的块的结构。具体地说，一个块被有意地定义为由一个声明列表和一个语句列表组成。请注意，重命名必须同时在声明列表和语句列表中进行图16给出了变量重命名的TL实现。我们对变量重命名问题的策略方法的概述如下。以由内而外的方式处理块（即，嵌套块第一）。当遇到一个块时，它的声明列表将以自顶向下的方式遍历，并且将构造一个能够重命名的策略表达式 块中的所有变量（声明列表和语句列表中出现的变量）。特别注意确保初始化表达式中出现的变量（即，声明中赋值右侧的表达式）不会不适当地162V.L. Winter/Electronic Notes in Theoretical Computer Science 124（2005）149prog块dec列表dec：：=：：=||类型：：=stmt list：：=stmt：：=assign：：=expr：：=cond：：=逻辑表达式：：= rel：：=||ETFid listexpr list实际idnum...：：=：：=：：=：：块“{“dec list stmtlist“}“dec“;”dec list|（ ）下一页类型idtype id“fun”id“（“idlist“）””=”expr“int”|“布尔”|......这是什么？stmt“;”stmt list|（）下一页分配|块|......这是什么？id“=”exprcond|逻辑表达式“if”expr“then”expr“else”exprrel|......这是什么？expr “=”E...E“+”T |E“-”T|不T * F |F“/”F |FID|num|（“expr“）|id“（“expr list“）”|......这是什么？id [“，”id list ]|（）下一页actual [“，”expr list|（）expr见图14。 一种小块结构的命令式语言V.L. Winter/Electronic Notes in Theoretical Computer Science 124（2005）149163限制id% 1id % 2：免费id1id 2dec[[type1id1=expr1]]→dec[[type1id2=expr1]]）：id1→id2生成重命名：如重命名var重命名dec1→transient（（restricted id 1id 2）+（free id 1id2））ID2 新干线（十二月一日dec [[type1id1]]下载dec1dec[[type1id1=expr1]]）：块1→TD BR（lcond tdl gen rename dec list1）块1如果块1块[[dec list1stmt list1]]=图15. 重命名变量时的注意事项：变量重命名图16.变量重命名策略{int x 1;int x 2;int x3 = x1 + x2;x1 = 5;x2 = x1 + 5;{int x1 = x1 + 1;int z1 = x1 + x2;int z2 = 4;x1 = x2 + z1 * z2;}的情况;x1 = x2 + x1;}{int n;int f5;int y6 = y4 + y5;y4 = 5y5 = y4 + 5;{int y1 = y4 + 1;int y2 = y1 + y5;int y3 = 4;y1 = y5 + y2 * y3;}的情况;y4 = y5 + y4;}164V.L. Winter/Electronic Notes in Theoretical Computer Science 124（2005）149在图16所示的TL实现中，策略restricted和free是curry形式的三阶策略，当给定变量名id1和相应的新变量名id2时，描述一种特定的重命名规则。 策略限制id% 1id %2描述了当遇到id1特别是，id1的声明应该重命名为id2，但初始化表达式应该保持不变。策略free id1id2描述了在所有其他情况下应该发生的重写。在受限和自由规则的基础上，是高阶策略生成重命名。当应用于声明时，gen rename将创建以下形式的瞬态：transient（（restricted id1id2）+（free id1id2））请注意，这种瞬态策略只能应用一次，并将执行限制或自由重命名。在自顶向下遍历的过程中，我们的想法是让这个瞬态应用于生成它的声明，之后它将减少到跳过该声明的所有子树。如果这可以实现，那么任何继续到初始化表达式的遍历都将保持声明变量的所有出现不变。除了这种行为，我们希望重命名在块的其余部分继续（例如，其余的声明和声明）。这正是TD BR可以实现的行为。当与瞬态结合使用时，理解TD BR的效果的一种方式是TD BR捕获关于树结构的“不在下面“的概念。“不低于”的概念 对于给定的树t和给定的叶x，设p表示从t的根到叶x的路径。让s表示一阶策略（不包含瞬态组合子）。 遍历TD BR瞬态t将在t中的每条路径上最多应用s一次。例如，如果s应用于路径中的特定点，则瞬态（s）将在此应用之后减少为跳过，因此将不应用于路径上的任何其他地方。考虑到TD BR和瞬态组合子之间的相互作用，让我们考虑解析表达式dec list[[ dec1; dec list1]]。当应用于此项时，策略TD BR s将首先将s应用于dec list[[ dec1; dec list1]]，从而产生策略sJ。战略的副本然后，将sJ广播到declist[[de c1;declist1]]的子帧的每个c h。 特别地，dec1和declist1都将接收它们自己的 SJ 副 本。更具体地说，让我们考虑当s是瞬态的（（restricted id1id2）时会发生什么。<+（freid1id2））。 在这种情况下，将s应用于declist[[de c1;declist1]]将使s保持不变（例如，s=SJ）。接下来，将向dec1和dec list1广播sj的副本。 如果dec1是负责生成V.L. Winter/Electronic Notes in Theoretical Computer Science 124（2005）149165则sj将适用于dec1但将不适用于dec 1以下的任何子项（例如，DEC1中的初始化表达式）。相反，在dec_list_1内，s_J将继续尝试将其自己的s_J的副本应用并广播到其子节点。这将使得瞬态sJ内的策略（free id1id2）能够将块内所有剩余的id1重命名为id2，这是所期望的。最后，在var rename策略中，遍历BUL会导致程序中的所有块以由内而外的方式重命名4.2NaïveFunumberingIn-lining当执行函数内联时，目标是用函数体的实例替换函数调用。这个主体实例是通过将与函数定义相关的形式参数替换为与调用相关的实际参数来获得的。图17中显示了内联的示例。在图18中，给出了一个用于执行简单函数内联的TL实现fun inline的策略是幼稚的，因为它没有考虑递归和相互递归函数定义可能导致的问题，也没有解决与实际参数对应的表达式重复所导致的效率问题策略fun inline使用匹配将块分割成声明列表和语句列表。声明列表然后由策略fun dec处理，它为每个函数声明创建一个内联策略，并将结果组合成一个策略表达式。这个策略表达式然后被应用到原始的声明列表中，以便内联声明列表中的所有函数调用。然后这个内联声明列表再次被策略fun dec处理。这一次，所得到的策略被应用于语句列表，该语句列表具有内联所有函数调用的效果。然后清理所得到的语句列表（例如，从表达式中删除多余的括号）。最后，结果语句列表替换原始块中的语句列表，就像内联声明列表一样战略fun dec通过战略inline的帮助实现其转型目标。这个策略的函数名为id1，形参列表id list1，函数体expr1为curry形式。 有了这些信息，内联策略就能够将函数调用F[[id1（expr list1）]]重写为适当内联的函数体F[[（expr2）]]。它在策略zip的帮助下实现了这一点。作为一个定义，策略zip只是一个宏，除了增强内联策略的条件部分的可读性之外，没有其他目的。在操作上，zip的主体将首先对id list执行遍历166V.L. Winter/Electronic Notes in Theoretical Computer Science 124（2005）149形式到实际：zipid list1expr list1：id1→瞬态（实际[[expr1]] →F[[id1]] →F[[（expr1）]]）lcond tdl（lcond tdlformal to actualid list1）expr list1inlineid1id list1expr1：如果FunDec：删除括号F[[id1（expr list1）]]→F[[（expr2）]]expr2T DL（zip id list1expr list1）expr1dec[[fun id1（id list1）=expr1]]→inline id1id list1expr1：......有趣的内：block[[dec list1stmt list1]]→block[[dec list1stmt list3]]ifdec list2T DL（lcond tdl fun dec dec list1）dec list1stmt list2T DL（lcond tdl fun dec dec list2）stmtlist1stmt list3T DL remove parens stmt list2=图17. 函数内联示例图 十八岁ATLimlementionofnévefunctinin-ling{intn =1;funf 1（x，y）=x+y;funf2（x，y，z）=x∈y+z; funf3（x）=f1（x，x）;z1 =f1（f1（20， 30），f1（40， 50））;z1 =f1（2， 3）+f2（22，33， 44）;}{intn =1;funf 1（x，y）=x+y;funf2（x，y，z）=x∈y+z; funf3（x）=f1（x，x）;z1 = 20 + 30 + 40 + 50;z1= 2 + 3 + 22< $33 + 44;z1 = 3 + 3 +3+4+ 4;}V.L. Winter/Electronic Notes in Theoretical Computer Science 124（2005）149167⊕⊕函数的形参列表 这种遍历将为id列表中的每个形参id创建一个瞬态策略。我们用s表示最终的策略表达式。接下来，用策略s遍历实际参数列表expr list。这将产生一个策略表达式，由形式为F [[id1]] → F [[（expr1）]]的规则集合组成，其中id1是形式参数，expr1是对应的实际参数。的需要前面提到的瞬态组合子来确保在形式和实际之间创建适当的当集体查看时，产生的规则能够将形式参数重写为函数体内的实际参数，从而产生该函数的内联实例。5相关工作TL规则的高阶性质可以理解为Currried重写规则的一种形式。在这种情况下，curry参数可以在高阶泛型遍历过程中绑定。在这种泛型遍历过程中产生的策略的组合与态射有关。具体来说，用于构造完整遍历的单层通用遍历组合子与函数式编程框架中的玫瑰树上的hylomorphism类似但不完全相同[8][9]。其他人也提出了类似的意见。例如，在策略术语中，可以将变形折叠b理解为对列表的结构执行自底向上的项遍历，其中二元函数可以用来实现类型保持重写功能或类型统一累积功能。在[7]中建立了蜕变和策略驱动的术语遍历之间的这种联系。ρ演算[5]是一个基于失败的重写框架，其中匹配模方程理论提供了项的语法比较机制。在ρ-演算中，规则和应用规则的项之间的区别是模糊的。规则和项都被认为是ρ-项。这种统一的处理让人想起λ-演算中函数和项之间的关系。而且，与λ-演算类似，在ρ-演算中，对于变量在一个项内出现没有限制。特别地，自由变量可以在规则的右侧引入。事实上，一条规则的右边可能本身就是一条规则，它为高阶策略打开了一扇无缝的大门。与ρ演算不同，TL是一种受限高阶语言。在TL中，高阶策略只适用于基本项（而不适用于其他策略）的限制回避了名称捕获问题。168V.L. Winter/Electronic