动态重写规则：解决程序转换中重写规则控制和性质问题的方法

网址：http://www.elsevier.nl/locate/entcs/volume59.html作用域动态重写规则埃尔科·维瑟乌得勒支大学信息与计算科学研究所Box 80089，3508 TB Utrecht，TheNetherlands http：//www.cs.uu.nl/people/visser，visser@acm.org摘要术语重写对程序转换的适用性受到缺乏对规则应用的控制以及重写规则的上下文无关性质的RST问题通过支持用户可定义重写策略的语言来解决。本文解决了第二个问题，通过扩展重写策略与范围的动态重写规则。动态规则是在运行时生成的，并且可以从其定义上下文访问可用的变量。 在规则范围内生成的规则在该范围结束时自动收回。该技术是通过几个程序转换：绑定变量重命名，函数内联，死函数消除。1介绍重写规则为表达程序转换提供了一种很好的形式。重写规则定义了从程序的代数等式导出的局部变换。有两个问题与标准项重写技术的应用程序转换：需要intermersing规则和策略，以控制重写规则的应用和上下文无关的重写规则的性质1.1规则的详尽适用穷尽应用程序的整个抽象语法树的所有规则是不足以解决大多数转换问题。表示基本转换的重写规则系统通常是不连续的和/或非终止的。经常使用的一种特别解决方案是通过引入额外的功能符号将对规则应用的控制编码到规则本身中。规则和策略的这种交织模糊了底层的程序等式，以定义遍历抽象语法树的规则的形式引起编程惩罚，并且禁止在不同变换中重用规则。c 2001年由Elsevier Science B出版。V.CC BY-NC-ND许可下的开放访问。2可编程重写策略的范例解决了在保持规则和策略分离的同时控制规则应用的问题。策略是一个小程序，它从可用的规则中进行选择，并定义应用规则在树中的顺序和位置。因此，规则保持纯粹，不与策略纠缠在一起，并且可以在多个转换中重用。对策略的支持由许多不同形式的转换系统提供。在TAMPR [4]中，变换被组织为一系列标准形式。对于每个规范形式，树相对于规范中的规则子集进行规范化。ELAN [3]提供了非确定性顺序策略。Replego [17，15]提供了通用的原语遍历操作符，可用于组成通用的树遍历模式。参见[16]，了解程序转换中的策略。1.2重写规则重写的第二个问题是重写规则的上下文无关性。规则只知道它正在转换的构造。然而，转换问题通常是上下文敏感的。例如，当在调用站点内联函数时，调用被函数体替换，其中实际参数已替换为形式参数。这要求函数的形参和函数体在调用点是已知的，但这些形参和函数体只在语法树的较高位置可用在程序转换中有许多类似的问题，包括绑定变量重命名、类型检查、常量和复制传播以及死代码消除。虽然这些应用中的基本转换都可以通过重写规则来表示，但它们需要上下文信息。这个问题的通常解决方案是在树上扩展遍历（无论是手写的还是通用的），这样它就可以分发转换规则所需的数据。例如，ASF+SDF [5]中的遍历函数可以声明为具有一个可以收集数据的累积参数。语言独立的操作定义，如在Reyngo中的绑定变量重命名[15]，捕获了一个通用的树遍历模式，它负责通过树分布环境。 这些解决方案的缺点是遍历策略变得数据繁重，而不仅仅是处理控制流。也就是说，所有的遍历函数都被携带上下文信息的附加参数所感染。当需要多个环境时，通用解决方案就会崩溃，例如，处理多个名称空间。另一个解决方案是使用上下文规则[2，17]。上下文规则通过使用本地遍历将上下文和本地转换组合在一个规则中，该本地遍历应用重用来自上下文的信息的规则。这种方法的问题在于，它对3抽象语法树，导致在上下文规则作为上下文访问的同一树上的遍历的一部分而应用的情况下的二次复杂性。1.3动态规则本文介绍了动态规则作用域重写策略的扩展。动态规则是在运行时生成的正常重写规则，可以从其生成上下文访问信息。例如，为了定义内联器，可以在声明函数的点处生成内联特定函数的函数调用的规则，并在函数的调用点处使用该规则。动态规则是最高级的。它们的应用受正常策略的控制。因此，动态规则可以作为全局树遍历的一部分来应用。规则可以推翻先前生成的规则的定义。 为了将动态规则的应用限制在树的某个部分，可以通过规则范围来确定规则的活动范围（第3节）。在作用域中暂时被否决的规则在该作用域的末尾再次可见。为了隐藏在外部作用域中生成的规则，可以对规则进行Under（第4节）。来自外部作用域的规则也可以被永久覆盖（第5节）。本文所描述的动态规则机制反映了在www.tago.com上发布的tago0.6.2版本中动态规则的实现。stratego-language.org.1.4纲要第二节回顾了在西班牙语中重写策略的基础知识部分3通过Tiger程序上的一系列转换引入了动态规则：绑定变量重命名（第3节），函数内联（第4节）和死函数消除（第5节）。这些例子中的每一个都激发和说明了动态规则的一个方面。第6节讨论了其他应用、相关工作和未来工作。第7节结束2重写策略这一节回顾了本文所需的重写策略的基础知识。参见[17]了解语言下的操作语义的细节。本文以Appel [1]的编译器构造教材中的示例语言Tiger为例，说明动态规则的应用。2.1程序表示在Replego中，要转换的程序被表示为一阶项。签名描述了术语的结构。签名S上的项是4让函数ifnfact（10）<事实（n1然后：1个int）else：int=（n*事实（n-（1））在端设（FunctionDec（[FunDec（“fact”，[FArg（“n”，Tid（“int”））]，Some（Tid（“int”）），如果（RelOp（LT，Var（“n”），Int（“1”）），Int（“1”），BinOp（MUL，Var（“n”），Call（Var（“fact”），[BinOp（MINUS，Var（“n”），Int（“1”）]，[Call（Var（“fact”），[Int（“10”）]）]）图1.一、一个小的Tiger程序的具体和抽象语法从S或应用程序C（t1，...，tn）的n元构造函数C从S到S上的项ti.列表符号[t1，.，tn]是用构造函数Cons和Nil构造的术语的缩写。图2显示了Tiger程序抽象语法的签名Tiger是一种命令式的、具有嵌套函数的一阶语言 数据是由数组和记录组成的，它们来自整数和字符串。使用if-then-else、while和for确定控制owTiger签名上的术语的 示 例 是 Var （ “x” ） （ 变 量 x ） 、 Call （ Var （ “f” ） ， [Var（“x”）]）（调用带有参数x的函数f）和Let（[VarDec（“x”，None，Int（“1”））]，[Var（“x”）]）（局部变量x的声明被初始化为整数常量1）。图1给出了一个小的示例程序和相应的抽象语法表示。2.2重写规则重写规则表示项的基本转换重写规则具有L：l-> r的形式，其中L是规则的标签，并且项模式l和r分别是其左手侧和右手侧 术语模式是变量、空值构造函数C或应用程序C（p1，.，pn）的n元构造函数C到项模式pi。例如，在一个示例中，倍数：BinOp（PLUS，e，Int（“0”））->e5是Tiger表达式的简单常量折叠规则。当模式l匹配t时，规则L：l->r应用于项t，即，当L具有与T相同的顶层结构时。将L应用于t具有将t变换为通过用t的子项替换r中的变量而获得的项的效果。 实际上，底层规则下的基本操作是JavaScript中的rst类操作。手术？t表示针对术语模式t的匹配，并且！t表示建立一个实例，6模块Tiger-Core签名排序Exp LValue InitField Tdec Dec FundDec FArg Type Field TypeId构造函数Var： String -> VarFieldVar： LValue * String -> LValue下标：LValue * Exp -> LValueInt：String-> ExpString： String -> ExpNilExp： Exp调用：Var * List（Exp）-> Exp记录：TypeId *List（InitField）->ExpInitField：String* Exp ->InitField数组：TypeId * Exp * Exp -> Exp BinOp：BinOp * Exp * Exp -> Exp RelOp： RelOp *Exp * Exp -> Exp序号：列表（Exp）-> Exp赋值：L值 * Exp -> Exp如果：Exp * Exp * Exp -> Exp如果：Exp * Exp-> ExpWhile： Exp * Exp -> Exp对于：变量 * Exp * Exp * Exp-> Exp断裂：失效令：List（Dec）* List（Exp）-> ExpTdec： String * Type -> TdecTypeDec： List（Tdec）-> DecVarDec：String * Option（TypeId）* Exp -> Dec函数Dec：List（FunDec）-> DecFArg： String * TypeId -> FArgFunDec： String * List（FArg）*选项（TypeId）*Exp-> FunDec名称Ty：类型Id->类型记录Ty ：列表（字段）->类型字段：String * TypeId ->字段ArrayTy： TypeId ->类型Tid： String -> TypeId图二. Tiger抽象语法的签名7术语模式T的定义。因此，规则L：l->r只是L = {x1，.，xn：？l;！r}，其中{x1，...，xn：s}定义了模式变量 x1，...，xn。构造{s}隐式地使s中的所有自由变量成为局部变量。2.3重写策略可编程重写策略提供了一种机制，用于实现对重写规则应用的控制，同时避免引入新的构造函数或规则。重写策略是一个程序，它可以转换术语，也可以失败。在成功的情况下，结果是一个转换的术语。 在失败的情况下，没有结果。重写规则只是将转换应用于项的根的策略策略可以被组合成更复杂的策略，通过Replego的策略运算符。标识策略id总是成功，并且保持其主题项不变。失败策略失败总是失败。策略s1和s2rst的顺序组合s1; s2试图将s1应用于主题词。如果成功，则将s2应用于结果;否则失败。策略s1和s2的非确定性选择s1 + s2试图将s1或s2应用于主题词，但顺序不明。如果s1或s2成功，则成功，否则失败。策略s1和s2rst的确定性选择s1 + s2试图将s1应用于主题词。<只有当s1失败时，它才会尝试将s2应用于主题词。如果s1和s2都失败，则选择也失败。策略s的递归闭包rec x（s）试图将策略rec x（s）替换变量x在s中的每一次出现而获得的策略应用于主题项。策略定义f（x1，...，xn）=s引入了新的策略操作，用策略x1，...，xn应用body s。2.4通用术语Traffic刚刚描述的策略组合器组合了将变换规则应用于其主题术语的根的策略为了在术语的内部站点应用规则（即，到子项），则有必要遍历该项。Replego定义了几个原始运算符，它们暴露了构造函数应用程序的直接子项。这些可以与上面描述的运算符相结合，以定义各种各样的完整项遍历。为了本文的目的，我们将遍历运算符的讨论限制在同余运算符和all运算符。同余运算符为Strat-ego中的项遍历提供了一种机制如果C是n元构造函数，则同余C（s1，...，Sn）是仅适用于形式C（t1，...，tn），并且通过将策略si应用于项ti来工作。例如，同余式Let（s1，s2）将形式为Let（t1，t2）的项变换为Let（t1 '，t2'），其中t1'是将s1应用于t1的结果，对于t2'也是类似的。 如果8设（[VarDec（“i”，None，Int（“1”））]，[BinOp（PLUS，Let（[VarDec（“i”，None，BinOp（PLUS，Var（“i”），Int（“2”）]，[Var（“i”）]），Var（“i”）]）对于任何i， si到ti的应用失败，则 C（s1，...，Sn）到C（t1，...，TN）也失败了。运 算 符 all （ s ） 将 s 应 用 于 构 造 函 数 应 用 C （ t1 ， . ，tn）。 当且仅当对直接子项的所有应用都成功时，它才成功。所得到的项是构造器应用C（t1 ′，...，其中ti'是通过将s应用于项ti而获得的结果。 注意，all（s）是常数的恒等式，即，没有子元素的构造函数应用程序使用all的一个例子是自顶向下策略，定义为topdown（s）=rec x（s; all（x））策略表达式recx（s; all（x））指定首先将参数变换s应用于当前主题项的根。如果成功，则将该策略递归地应用于该术语的所有直接子项，从而应用于其所有子项。这种自顶向下的定义捕获了术语上的前序遍历的一般概念。3绑定变量重命名绑定变量重命名是将绑定变量及其对应的实例替换为新的唯一名称的转换。作为转换的结果，一个名称最多被一个绑定使用。当在绑定下替换表达式时（例如在执行函数内联时），为了防止捕获自由变量，这种转换是必要的下面的转换演示了Tiger程序中变量声明的重命名。）请注意，第二个声明的初始化中使用的i是由外部声明绑定的，并且内部let之后使用的i也引用外部声明。但是，内部let中的i引用内部声明。这些问题在右边的重命名版本中得到了澄清左边表达式的抽象语法表示是术语：让在端vari（let以端*=1瓦尔岛+（一）：=（i）+（二）让在vara_0：=1end+a_0）：=（a_0+（二）9exprename（Let（ [VarDec （ x ，t ， e1 ） ] ， Let（ [VarDec （ y ，t ，exprename（e1，wherenew=> yexprename （ Var（ x ）， rn ）=Var（lookup （ x ，rn））e2），rn）=rn））]，exprename（e2，（x，y）：rn））exprename（BinOp（op，e1，e2），rn）=BinOp（op，exprename（e1，rn），exprename（e2，rn））图三.重命名函数的定义。第一个盒子包含基本规则。第二个框显示了定义所包含的其他规则的示例。3.1重命名的功能定义绑定变量重命名的传统实现定义了一个函数exprename，该函数递归地访问抽象语法树的所有节点，携带重命名表rn，该重命名表在绑定位置处扩展并在变量出现时查询（图3）。注意，为了重命名声明的初始化式，使用了未扩展的重命名环境。new函数生成一个新的字符串，该字符串是唯一的，因为它不会出现在当前语法树中的任何位置。这种实现的缺点是函数必须扩展访问所有树节点，即使是那些不是变量或不绑定变量的节点（如BinOp）。因此，重命名函数的定义对于遵循模式exprename（C（e1，.，en），rn）=C（exprename（e1，rn），.，exprename（en，rn））要完整定义Tiger程序的重命名，需要6条基本重命名规则和17条附加规则。对于真正的语言，基本规则与附加规则的比例可能会降低。3.2使用重写规则泛型遍历可以避免定义当前转换中不涉及的构造的遍历的开销上面的递归重命名函数本质上可以用自顶向下的遍历来表示扩展名=topdown（try（RenameVarDec+ RenameVar））10该策略遍历抽象语法树，并在每个子树尝试应用规则RenameVarDec或RenameVar之一。运算符try被定义为try（s）=s<+id，即，它尝试应用变换s，但如果失败，则返回原始项。只需要提供实际更改的构造的规则rst规则在变量声明中通过生成新名称来重命名绑定变量：11RenameVarDec：令（[VarDec（x，t，e1）]，e2）->令（[VarDec（y，t，e1）]，e2），其中new=> y第二条规则将Var（x）的出现重命名为Var（y）：RenameVar：Var（x）-> Var（y）但这里有一个问题：在规则RenameVar中，目的不是将任何变量重命名为任何其他变量，而是将绑定变量的出现重命名为在其绑定位置生成的新名称，即，在规则RenameVarDec中。3.3正在生成重命名规则因此，重命名变量的规则取决于相应绑定构造的重命名。这种依赖关系可以使用动态规则来表示。RenameVarDec可以重新公式化，以便为声明构造绑定的变量RenameVarDec：令（[VarDec（x，t，e1）]，e2）->令（[VarDec（y，t，e1）]，e2），其中new=> y;rules（RenameVar：Var（x）-> Var（y））在RenameVarDec条件下的动态规则声明规则（RenameVar：Var（x）-> Var（y））生成RenameVar规则的实例，该实例继承其上下文中的元变量x和y的值。作为该动态规则生成操作的示例，考虑将RenameVarDec应用于术语设（[VarDec（“i”，None，Int（“1”））]，. ）的方式当将规则的左侧与这个项进行匹配时，变量x被绑定到字符串“i”。随后，new生成一个新的唯一字符串，比如“a_0”，并将其绑定到变量y。在这些绑定的上下文中，创建了动态规则RenameVar，从而生成规则：RenameVar： Var（“i”）-> Var（“a_0”）最后，生成重命名的变量声明：Let（[VarDec（“a_0”，None，Int（“1”））]，... ）的方式当进一步遍历树时，Var（“i”）的每个出现都将被遍历。应用的动态生成的规则RenameVar被Var（“a_0”）替换，而其他（自由）变量不被考虑。123.4限制生成的规则自顶向下的重命名策略使用RenameVarDec和 RenameVar作为de-上面的ned还不太对。 如果我们把它应用到我们的示例表达式中，我们得到：）为i的内部声明生成的重命名规则覆盖了外部声明的规则这对于i在内部let中的出现是正确的，但是该规则在内部let之后也仍然适用。这个问题表明，应该可以在生成的规则的有效范围结束后收回这正是规则范围{|实验室：s|}实现。在执行% s时生成的标签为lab的规则将在范围结束时自动删除因此，任何被范围内生成的规则重写的规则在范围之后再次可见回想一下，exprename被定义为exprename = topdown（try（RenameVarDec + RenameVar））其中topdown的定义是：topdown（s）=rec x（s; all（x））通 过 将 重 命 名 策 略 重 新 定 义 为exprename =rec r（{|RenameVar：try（重命名VarDec+ return（r）;|}）由变量声明生成的RenameVar规则在退出作用域后自动有必要内联自顶向下的定义，因为生成的重命名规则的范围应该包括使用all（r）遍历子项。考虑新策略对示例的影响，注意内部let之后的i）然而，重命名仍然是不正确的，因为初始化器中的i没有被正确地重命名。让在端vari（let以端*=1瓦尔岛+（一）：=（i）+（二）让在vara_0：=1end+b_0）：=（b_0+（二）让在端vari（let以端*=1瓦尔岛+（一）：=（i）+（二）让在端vara_0：=1end+a_0）：=（b_0+（二）13为了正确处理变量声明的初始化器，应该调整遍历，以便在生成新的重命名规则之前重命名初始化器中的变量这就是下面的策略所实现的。同余式Let（[VarDec（id，id，r）]，id）访问变量声明的初始化器，而同余式Let（[VarDec（id，id，id）]，r）只访问Let的主体：扩展名 为rec r（try（Let（[VarDec（id，id，r）]，id））;{|RenameVar：try （ RenameVarDec +RenameVar ） ;（Let（[VarDec（id，id，id）]，r）+all（r））|}）choice（Let（[VarDec（id，id，id）]，r）<+all（r））仅针对变量声明的情况调整泛型遍历。3.5基于规则生成的由于Tiger中有几个绑定变量的结构，因此重复为每个绑定结构生成重命名规则的代码是这可以通过创建将名称转换为新名称的规则并同时生成重命名规则来避免。图4为Tiger程序定义了一个全面的重命名策略，它覆盖了所有绑定构造，也重命名了类型标识符，因此同时处理了两个命名空间。用于绑定的重命名规则构造调用规则NewVar以生成新名称和对应的变量重命名规则。规则定义如下：NewVar： x -> y其中new=> y; rules（RenameVar： Var（x）-> Var（y））使用此规则定义的重命名器重命名所有变量，即使变量名已经是唯一的。对于某些应用程序，重命名尽可能少的变量是有用的，例如，当结果应该由程序员可读时。一种方法是只重命名那些与外部绑定冲突的变量。 在我们运行的示例中，这种方法具有以下效果：）这可以通过只为已经存在于外部作用域中的变量生成新名称来实现下面的规则尝试将RenameVar应用于变量x。如果成功，则变量已经在外部作用域中声明在这种情况下，会生成一个新的变量否则，原始变量名让在端vari（let以端*=1瓦尔岛+（一）：=（i）+（二）让在端vari（let以端*=1vara_0+（一）：=（i）+（二）14模块Tiger-Tiger导入Tiger动态规则库策略exprename =rec r（try（Let（[VarDec（id，id，r）]，id））;|RenameVar、RenameTid：try（重命名声明 +重命名Args+ 重命名为+ Rolling（[Rolling（id，id，id）]，r）+all（r））|}）重命名声明 为Let（[RenameVarDec+FunctionDec（map（RenameFun））+ TypeDec（map（RenameTdec））]，id）RenameVarDec：VarDec（x，t，e）-> VarDec（y，t，e）其中x=> yRenameFun：FunDec（f，xs，t，e）-> FunDec（g，xs，t，e）其中f=>g重命名Args：FunDec（f，xs，t，e）-> FunDec（f，ys，t，e）其中map（FArg（NewVar，id））> xs=> ys重命名为：对于（Var（x），e1，e2，e3）->对于（Var（y），e1，e2，e3），其中x=> y重命名Tdec：Tdec（x，t）-> Tdec（y，t），其中x=> y图四、绑定变量和类型名称的重命名采用了NewVar： x -> ywherein（ Var（x）; new<+！x）=> y;rules（RenameVar：Var（x）-> Var（y））153.6总结在本节中，我们已经看到了如何使用规则（...）使用上下文中的信息构建16他们所定的后续生成的规则将覆盖以前生成的规则。一个规则范围{|实验室：s|}将由s生成的规则的有效范围限制在作用域内。多个命名空间的动态规则（例如，变量和类型），可以同时生成动态规则可以像静态规则一样在树结构的一般遍历中使用因此，只有相关的树节点被显式访问，其他节点被隐式遍历4函数内联函数内联是一种将函数调用替换为函数体的转换，其中实际参数已替换为形式参数。例如，考虑下面的简单示例，其中对sqr函数的调用被其函数体替换）请注意，替换引入了局部变量来将实际参数绑定到（重命名的）形参。这是必要的，因为Tiger是一种命令式语言。简单地用实际参数代替形式参数可能会导致工作重复，甚至会因为干预分配而导致错误进一步的优化，如常量和复制传播，可以在可能的情况下摆脱局部声明。函数内联转换由定义如下的InlineFunInlineFun：Call（Var（f），es）-> Let（ds，e）其中exprename-all> fdec=> FunDec（_，xs，t，e）;（xs，es）=>ds函数调用被替换为一个let表达式，该表达式以函数声明e的主体作为其主体。此外，let还引入了一个列表对应于函数声明的形式参数xs的变量声明（重命名声明后）。通过将形式变量和实际变量的列表压缩在一起并使用规则BindVar构建变量声明，将局部变量xs绑定到实际参数es：BindVar：（FArg（x，t），e）-> VarDec（x，Some（t），e）规则中的变量fdec应该绑定到f的原始函数声明。 此信息通常在函数的调用站点不可用。通过在遇到let function sqr（x：int）=（x* x）inlet var a_0：int：=（3+y）in（a_0 * a_0）结束结让 函数sqsqr（（3+y））：int）=在17UnDeclareVars 为（？VarDec（x，_，_）+ 什么？对于（Var（x），_））;UnDeclareFun =？int x = 0（x，x，x，x）;rules（InlineFun：Call（Var（x），_）->BindVar：（FArg（x，t），e）-> VarDec（x，DeclareFun为？fdec@FunDec（f，_）;可内联;规则（InlineFun：Call（Var（f），es）-> Let（ds，e）其中exprename-all> fdec => FunDec（_，xs，t，e）; zip（BindVar）>（xs，es）=> ds十月=Let（[FunctionDec（map（DeclareFun<+UnDeclareFun））+ UnDeclareVars]，id）模块Tiger-Inline引进虎扑战略inline（s1，s2）为rec x（s1; try（Let（[VarDec（id，id，x）]，id））;| InlineFun：（Decimal; Let（[VarDec（id，id，id）]+ x，id）; Decimal; Let（id，x）<+ all（x））; s2图五. 简单内联策略函数声明的必要信息可以传递给InlineFun。在图5中，策略DeclareFun为函数声明生成一个内联规则，如果它是可 内联的。图5定义了一个简单的内联策略，它使用两个转换策略s1和s2进行参数化。这些是在树的下行路径（s1）和上行路径（s2）上应用的转换。示例实例化可以是18inline（repeat（InlineFun+），repeat（重复））其在向下的过程中内联函数并简化表达式（例如，恒定的折叠）。 该战略基本上归结为以下几点：inline（s1，s2）为public int findDuplicate（{|InlineFun：try（December）;all（x）; s2|}）也就是说，首先应用s1变换。然后，在输入InlineFun规则的作用域之后，Decoder会为任何局部函数声明生成内联规则。随后递归地访问所有子树。然后进行S2变换。图5中的策略处理变量声明的作用域规则，并在优化内联规则的主体之后重新生成内联规则，以便只内联已经优化的函数4.1Unde ning Rules生成InlineFun规则的StrategyDeclareFun仅在函数声明被视为可内联时才这样做。 可内联的确切定义在这里并不重要;它可以使用基于静态或动态程序分析的各种方法来定义。重要的是，对于不可内联的函数，不会生成InlineFun规则。如果存在两个同名的函数，一个隐藏另一个，并且外部函数可以内联，而内部函数不能，这可能会导致用错误的函数体替换调用。因此，有必要防止内联规则从外部范围蔓延到槽。动 态 规 则 可 以 声 明 为 under ned 。 策 略 UnDeclareFun 生 成 一 个InlineFun规则，该规则被定义为：UnDeclareFun 为？Fdec（x，_）;rules（InlineFun：Call（Var（x），_）-> Undefined）此规则在调用时总是失败。这样做的目的是为了隐藏相同函数名的变量声明和循环计数器变量也是如此，因为它们可能会隐藏函数定义。另一种方法是在生成的InlineFun规则的where子句中计算可内联的然而，这是昂贵的，因为每次调用规则时都需要重新计算条件5失效功能消除死代码消除的目的是从程序中删除在运行时从不使用的代码片段死函数消除是死代码消除的一种特殊情况，在这种情况下，19被定义的函数永远不会被调用。下面的转换是dead函数elimination的一个例子，它从上一节中获取内联的结果，并删除现在未使用的sqr函数：）消除死函数需要遍历程序，以确定是否有任何对函数的调用。图6给出了使用动态规则消除死函数的定义。策略是默认声明每个函数都是死的。策略DeclareDead定义了一个函数的IsDead规则，一旦它的声明在作用域中。在遍历语法树的过程中，当遇到对函数的调用时，IsDead规则受NotDead规则的约束。在退出的过程中，IsDead规则仍然成功的所有函数都会被策略Eliminate删除，该策略会筛选出所有应该被删除的函数。请注意，为了消除死（相互）递归函数，应该重新使用5.1覆盖规则这种策略需要引入一种新的动态规则。考虑使用常规动态规则来定义NotDead不死=？int n（n）;rules（IsDead： FunDec（f，_）-> Undefined）这将需要为在该位置调用的函数添加新规则IsDead。但是，一旦转换退出周围的作用域，这个新规则就会被删除，而函数声明仍然会被删除。然而，这并不是我们想要的，因为NotDead的意图是改变在函数声明的作用域中定义的原始规则，而不是为了局部目的而使用IsDead这是通过将动态规则声明为覆盖规则来实现的。只有在相同左侧存在动态规则的先验定义时，重写动态规则的生成才成功6讨论6.1其他应用动态规则已经成功地应用于许多转换中。let function sqr（x：int）=（x* x）inlet var a_0：int：=（3+y）in（a_0 * a_0）端端让 vara_0：=（三）+y）20RmEmptyLet：令（[FunctionDec（[]）]，RmEmptyLet：令（[]，e）-消除=Let（[FunctionDec（filter（not不死=？int n（n）;重写规则（IsDead：FunDec（f，_）-> Undefined）DeclareDead为？fdec@FunDec（f，_）;rules（IsDead：FunDec（f，_）->DeclareDead为Let（[FunctionDec（map模块Tiger-ElimDead引进虎扑战略去死函数为rec x（try（Let（[VarDec（id，id，x）]，id））;| IsDead：尝试（DeclareDead）;（Let（[VarDec（id，id，id）]+ x，x）+all（x））; try（NotDead + Eliminate; try（RmEmptyLet））见图6。 消除死功能在Tiger的抽象解释风格类型检查器中，使用动态规则因此，不需要沿着遍历线程化类型环境，并且类型规则可以直接表示为重写规则。在Tiger的解释器中，动态规则用于表示从变量到堆栈或堆上的值的映射。变量绑定使用类似于重命名器的作用域遍历来处理。全局可见堆对象由一个无作用域的动态规则表示，该规则将引用值（指针）映射到值。单个结构的评估使用常数折叠规则表示。Tiger程序的几个优化，包括常量传播、复制传播和死代码消除，都可以使用动态规则优雅地表达出来在前向转换问题中，动态规则重写