基于重写策略的编程语言解释器的设计和扩展（设计和扩展基于重写规则的编程语言解释器）

57网址：http://www.elsevier.nl/locate/entcs/volume65.html20页用重写策略Eelco Dolstra和Eelco Visser乌得勒支大学信息与计算科学研究所Box 80089，3508 TB Utrecht，TheNetherlands eelco@cs.uu.nl，visser@acm.org，http：//www.cs.uu.nl/people/feelco，visserg/摘要基于纯重写规则的编程语言语义源于重写引擎中实现的重写策略与预期的求值策略之间的本文展示了如何可编程重写策略可以用来实现基于重写规则的编程语言的解释器。这种方法的优点是，约简规则是第一类实体，可以在不同的策略中重用，甚至在其他类型的程序transformations，如优化器。该方法说明了几个解释器的lambda演算的基础上隐式和显式（并行）替代，不同的策略，包括规范化，渴望评估，懒惰的评估，并与更新懒惰的扩展模式匹配和选择表明，这样的解释器可以很容易地扩展。1介绍语言原型是设计和验证编程语言设计的活动。原型解释器对于语言设计的实验很有用语言原型方法应该支持语言定义的可执行性和定义的简单修改，以包括或排除语言结构，并使用不同的评估策略进行实验。支持语言原型的系统可以分为基于指称方法的系统和基于操作方法的系统。在指称方法中，程序表达式被转换成其计算值。支持这种方法的典型系统是动作语义、LPS和蒙太奇。在动作语义学[5]中，表达式被翻译成动作，动作表示其计算。 在LPS系统[11]一个表达式被映射到一元计算上[12]。 在蒙蒂奇程序被转换为抽象状态机[10]。 虽然外延c2002年由Elsevier Science B出版。V.CC BY-NC-ND许可下的开放访问。58虽然语义对于构建编译器非常有用，但它并没有提供在源代码级别对程序进行语法操作的理论，而这是构建源代码到源代码转换系统所需要的。在操作方法中，程序表达式直接由某种转换系统解释以产生其值。这提供了对语言的（抽象）语法结构的直接操作解释，可以用来构建解释器，但也可以用作实现其他程序转换的基础，例如优化器，重构引擎和软件更新工具。操作语义有不同的风格在CENTAUR系统[3]支持的自然语义[9]中，表达式与其值直接相关，可能通过使用求值关系的递归调用。 在重写语义方面，许多系统都支持，包括ASF+SDF[4]和ELAN [2]，表达式通过以下连续应用进行归一化：约简规则，它定义了一个表达式的修改，通常是小的。在句法理论[7]的方法中，例如由SL语言[17，18]支持，一组归约规则被扩展为评估上下文，该评估上下文限制了可以应用归约规则的位置。因此，评估上下文克服了纯粹的基于重写的语义的限制。穷尽地应用归约规则通常不能充分描述语言的语义。因此，评价策略和重写策略（由重写引擎提供）之间的差距通常通过显式指定评价函数而不是使用纯重写规则来弥补。在本文中，我们展示了如何可编程重写策略的范例可以用来实现解释器。在这种方法中，语义是通过“常量折叠”的减少规则，它描述了有效的程序表达式的转换。此外，用户定义的重写策略决定了在表达式中以什么顺序和在什么位置重写。应用规则，从而确定评估策略。这种方法是有吸引力的，因为语义规则是第一类实体，可重用，可以使用不同的策略相结合，很容易实验评估策略和语言配置。 这种配置不依赖于规格的模块结构|例如，在模块化动作语义的方法中[5];可以基于相同的规则集在相同的规范模块中定义不同的解释器。例如，在[6]中，基于Rhodego的懒惰和严格评估的解释器使用相同的规则集定义。此外，这组规则可以用于其他程序转换，而不是通过使用不同的策略来完全评估程序。实际上，这种方法源于使用重写策略实现优化器[16]。我们通过为lambda表达式定义一些解释器来说明这种方法。虽然lambda演算不是一种完全边缘化的编程语言，但它对于说明59定义符号解释器，即，变量绑定和替换的处理以及归约顺序。在第2节中，我们定义了一个lambda约简，其中包含一个替换元操作和通过约简规则显式定义的替换第3节中我们考虑了基于显式替换约简规则的评价策略的指定。策略包括穷举应用、渴望和懒惰评估、并行替换和懒惰评估更新。在第4节中，显式替换被动态重写规则的生成所取代。在第5节和第6节中，我们使用模式匹配、模式匹配失败和选择扩展了基本的lambda语言，从而为Rhodego语言的核心提供了一个解释器[6]。第7节讨论了这种方法的应用。所有的例子都是在Replego中指定的，Replego是一种基于重写策略范式的程序转换语言[14]。我们解释了所使用的martego结构，但不深入。[14]见《无量寿经2用显式替换在本节中，我们将探索使用显式替换为lambda表达式定义解释器的各种方法。Lambda表达式由变量、lambda表达式的应用程序和lambda表达式中变量的抽象组成为了描述表达式的结构，本文将使用上下文无关文法产生式之后的具体语法和构造器声明之后的抽象语法因此，lambda表达式由以下代数签名描述，注释中有具体的语法：签名排序Exp构造函数变量：String-> Exp// Id -> Exp应用程序：Exp * Exp-> Exp// Exp Exp -> ExpAbs： String * Exp-> Exp//“\\” Id“->”Exp-> Exp抽象语法术语的新转换的语法规范。然而，具体句法可以被看作是抽象句法表达式的句法糖[15].具体的语法术语将写在[[和]]。因此，[[（| x-> x）y ]]表示项App（Abs（“x”，Var（“x”）），Var（“y”））。我们将在规则中使用具体语法，但在遍历的定义中使用抽象语法。2.1β还原lambda表达式的含义可以通过将表达式归约为规范形式的归约规则来表达。规范形式表示60表达式的值。lambda表达式的约简由单beta约简规则表示贝塔：[[（\x-> e2]]->（[[x]]，[[e2]]，[[e1]]）其中右手侧表示在e1中xbye2的（无捕获）取代。 一个没有redices的表达式是标准形式，表示所有可以简化为它的表达式的值。当然，这种范式应该被认为是绑定变量的模重命名。lambda表达式的纯重写解释器会以任意顺序将Beta规则穷尽地应用于lambda表达式。这可以用reduce策略来表示，它被定义为：reduce（s）=repeat（rec x（some（x）+s））reduce策略选择规则，并反复尝试找到s成功的子项使用这种策略，lambda解释器可以定义如下：评价1=减少（Beta）在下一节中，我们将考虑更符合实际编程语言解释器的策略。2.2替代法在上述β归约的公式中，无捕获取代没有被定义为归约的一部分，而是被假设为元操作。除了这不能提供令人满意的减少定义的事实之外，这对解释算法的复杂性具有后果。替换操作的实现必须遍历项，而重写策略本身也遍历项，从而导致多次遍历。因此，最好将取代表示为还原过程本身的一部分。为了使替换显式，我们扩展了lambda表达式的签名，使用let绑定作为替换操作符。让绑定具有以下语法：签名构造器Let： String * Exp * Exp-> Exp//“let”Id“=”Exp“in”Exp -> Exp在e2中的let绑定let x = e1将表达式e1绑定到变量x。这个约束在表达式e2中成立，而在e1中不成立。同样，let结构的意义可以通过归约规则来表达。当Let体只是一个变量时，let绑定表达式61如果变量与绑定变量SubsVar相同，则将其替换为变量：[[ letx=e inx]]->[[e]]否则，消除绑定。SubsVar：[[letx= e in y ]] -> [[ y ]]where not（eq）>（x， y）Substitution通过应用程序SubsApp分发：[[letx= e in（e1 e2）]]->[[（letx= e in e1）（letx= e in e2）]]抽象下的替换需要小心处理，以避免在let绑定表达式中捕获自由变量。如果抽象变量与let绑定变量相同，则抽象隐藏了let绑定，因此可以消除let绑定。SubsAb：[[letx= e1 in\ x-> e2]]->[[\x-> e2]]如果变量不相同，则可以将替换应用于抽象的主体，但是在将抽象变量重命名为新名称之后。SubsAb：[[letx= e1 in\ y-> e2]]->[[\z->（let x= e1 inlet y= z in e2）]]其中不（eq）>（x， y）;new => z策略new生成一个新的唯一名称。该名称保证不会与当前使用的任何字符串一致给定这些归约规则，我们可以通过将抽象的应用转化为通过let绑定将实际参数替换为形式参数来重新定义beta归约：BetaES：[[（\x-> e1）e2]]->[[letx= e2 in e1]]现在可以通过相对于BetaES规则和Subs*规则进行约简来定义具有显式替换的Beta约简，而无需求助于元操作。通过给这个规则的选择命名（命名），它可以在以后被重用。eval2= reduce （ 减少）阿斯塔纳 为BetaES + SubsVar + SubsApp + SubsAbs623评价策略既然我们已经明确了替换，我们就转向还原顺序的问题。Reduce策略的任意归约顺序不是很有效，也没有描述程序语言解释器应该遵循的策略。首先，我们考虑效率问题。reduce策略从词根开始重复查找多个redice。一个更有效的策略是下面的最内层策略，它在考虑术语本身之前完全规范化子术语：最里面的为rec x（memo（all（x）; try（s; x）策略首先规范化子项（all（x）），然后才尝试应用其中一个规则。如果成功，它递归地减少应用规则的结果。否则，该术语为正常形式。为了避免重新规范化项，memo运算符记忆规范化结果。参见[8]，了解不依赖记忆的最内层策略的优化。重用同一组规则，我们现在可以基于最内层定义一个更有效的评估策略：eval3=最里面（最深处）3.1及早求值穷举地应用求值规则对于编程语言的解释器是不够的.例如，减少函数体通常只有在其参数已知后才有意义;它可以包含非终止的减少。为了改善程序的终止行为，解释器限制表达式的求值。这种限制可以通过调整应用评估规则的策略来表达急切（或严格）解释器在将let绑定表达式代入到let体之前对其求值，对函数的参数求值，但不对函数体求值。这基本上与完全归约相同，只是遍历应该受到限制，以便不在抽象下应用任何归约。这是由下面的求值策略表示的，它遵循最内层的算法，但限制了遍历：评价4 = 2016年10月25日，（Var（id）+App（e，e）+Abs（id，id）+Let（id，e，e））; try（Var_es; e））遍历是使用同余运算符来定义的，这些同余运算符指定了构造函数的遍历例如，App（e，e）策略指定e应该应用于App术语的两个直接子术语另一方面，Abs（id，id）指示应当将恒等变换应用于63Abs项的子项，即，Abs的子项不应该被评估。这个策略的一个更经济的定义是只指定应该遍历的构造函数，而不涉及任何其他构造函数：评价5 = 2016年10月25日，try（App（e，e）+Let（id，e，e））; try（appenda-es;e））3.2惰性计算惰性计算通过只减少需要其值的表达式来进一步改进终止行为。在lambda演算中，只有在执行beta归约时才需要值，因此应用程序和letbound表达式的参数不应该被评估;只有应用程序的函数位置应该被评估以暴露可能的redice。这在以下策略中表示，该策略进一步限制了遍历：评价6 = 2016年10月25日，try（App（e，id）+Let（id，id ， e ） ） ; try （ appenda-es;e））与急切求值策略的唯一区别是遍历的限制，所使用的求值规则保持不变。这个策略实现了延迟求值或按需调用，因为表达式只在需要时才被求值。通常，惰性赋值器也会在求值后记住表达式的值，这样它只被求值一次。这方面将在后面讨论。3.3并行替换上面定义的显式替换的公式，在表达式的构造函数上一次分配一个变量绑定。 通过将多个绑定组合成一组绑定，可以减少术语遍历的数量。为此，我们引入了并行let（letp）结构，其中包含一个绑定列表，而不是单个绑定。构造的语法签名构造器Letp： List（Bind）* Exp -> Exp//在”Exp -> ExpBind：String* Exp->Bind“中的“letp”{Bind“;"}*”//Id“=”Exp ->Bindletp的rst参数是表达式到变量的列表绑定。新的LETP结构要求重新制定评估规则。变量求值需要在绑定列表中查找值。如果没有64如果找到绑定（lookupb失败），则生成原始变量。PSubsVar：[[letp ds in x]]->[[e]]其中（lookupb>（x，ds）<+！[[ x ]]）=>e查找b =？（x，ds）; fetch（？[[x= e1]]）;！[[e1]] ds在应用程序上分发替换在一个步骤中分发所有绑定：PSubsApp：[[ letp ds in e1 e2 ]]->[[（letp ds in e1）（letp ds in e2）]]在抽象之上分发替换需要重命名绑定变量以避免捕获自由变量。PSubsAb：[[ letp ds in\ x-> e ]]->[[\y ->（letpds in letpx=y in e）]]其中new=>yBeta归约包括将参数绑定到形式参数：BetaPES：[[（\x-> e2]]->[[ letpy = e2 in letpx = y ine1]]其中new =>y为了实现并行替换的好处，可以组合两个相邻letp这需要将外部letp的 替 换 应 用 于 内 部 letp 的 let 绑 定 表 达 式 ; 这 对 应 于 替 换 引 理 。RuleLetOne是指两个字母与一个装订的组合：LetLetOne：[[letp x= e1 in（letp y= e2 in e3）]]->[[ letpy =（letpx = e1 in e2）;x = e1 ine3]]RuleLetLet将其推广到具有任意数量绑定的 letp：[[letpds1 in letpds2 ine1]]->[[letp ds4 in e1]]其中map（\[[x= e]]->[[ x= letpds1 in e ]]\）> ds2=>ds3;（ds3，ds1）=>ds4最后，我们给并行显式替换的归约规则集合命名：65PSubs-pes= BetaPES+ PSubsVar+ PSubsApp+ PSubsAbs+ LetLet使用这些规则，我们可以按照与以前相同的路线来定义评估策略。eagerevaluation策略评估函数参数和letp绑定：评价7 =rec e（try（App（e，（e）+ Letp（map（Bind（id，e）），id）; rec e （ try （ appenda-pes; rec y （ try （ App （ y ，y））; e）内部（y）递归只遍历应用程序节点，而不是letp绑定，以避免重新评估替换。延迟求值策略仅在函数位置中对表达式求值：评价8 = 2016年10月25日，try（App（e，id））; try（appenda-pes; e））请注意，不再需要计算letp表达式的主体，因为替换规则将把letp推到rst内部。3.4共享绑定上面的显式替换方法的问题是替换通过规则（P）SubsApp分布在项上。在急切求值的情况下，这是没有问题的，因为在替换中绑定的表达式首先被求值。然而，在惰性求值策略（eval6，eval8）中，let绑定表达式不被求值。这保证了表达式只在需要的时候被求值，但是替换函数的重复一个好的惰性计算器会在变量被计算一次后立即更新变量的绑定。这需要在替换后维护绑定为了形式化更新的概念，我们使用为并行替换引入的绑定集作为一个全局堆，在该全局堆上收集变量绑定。在计算开始时，LetLift规则引入了一个空堆：LetLift：[[e]]->[[letp in e]]变量替换与前面相同，但是应该保持绑定，并且应该仅在变量存在时减少，以避免非终止性USubsVar：[[ letp ds in x ]] -> [[ letp ds in e ]]其中lookupb>（x，ds）=>e应用程序的功能位置的评估不能再使用简单的同余运算符来表示，因为它需要分发替换环境并在之后恢复环境：66LetAppL（评估）：[[ letp ds1 in e1 e2 ]] -> [[ letp ds2 in e3 e2]]其中eval>[[letp ds1in e1]]=>[[letp ds2in e3]]在LetLetRen规则中，重命名内部Let中绑定的变量对应于在堆上为这些绑定分配空间LetLetRen：[[ letpds1 in letpds2 ine1]]->[[ letpds4 ine2]]其中重命名> [[ letpds2in e1]] =>[[ letp ds3in e2]];（ds3，ds1）=>ds4有了这些规则，我们可以定义一个惰性求值策略，它线程化求值环境，但还不更新任何绑定。每次变量被替换时，绑定到它的表达式都会重新计算。评价9 =intn=nums（nums，nums）;try（（USubsVar+ Letp（id，BetaPES）+ LetLetRen）; e））这个策略可以扩展为使用附加规则Update更新变量绑定，该规则将评估策略作为参数更新（评估）：[[letp ds1 in x]]->[[letp x= e; ds2 in e]]其中eval>[[ letp ds1in x]]=>[[ letp ds2in e]]评估策略e用于评估变量，从而产生值v.该值作为结果生成，并绑定到环境中的变量x。变量x的后续计算将直接产生值。更新规则可用于将策略eval9调整为更新策略：评价10 =LetLift; rec e（try（LetAppL（e））;try（Update（USubsVar;e））+ （Letp（id，BetaPES）+LetLetRen）; e））传递给Updaterst的策略执行替换，然后循环计算结果表达式。因此，我们已经指定了一个完整的操作帐户的懒惰lambda评估。该方案可以扩展为操作概念，如垃圾收集和黑洞，以检测nite循环[6]。674使用动态规则的在前面的章节中讨论的显式替换解释器提供了lambda演算计算的操作概念的完整说明。然而，作为术语结构的一部分的替换操作需要簿记和管道，并且偏离了评估遍历的基本方案。这可以通过从用于通过App节点的表达式遍历的简单同余操作符到环境线程规则LetAppL的更改来证明。这种情况可以通过注意替换可以被视为重写规则来改善，该重写规则将变量重写为应该替换它的表达式。然而，不能使用普通的重写规则，因为绑定集在计算期间动态扩展。在本节中，我们用一组动态重写规则来替换显式替换环境。动态重写规则[13]是在运行时生成的重写规则，可以从其生成上下文继承（Meta）变量绑定。4.1及早求值一个抽象的应用产生了一个替代。使用动态规则，这是通过将应用程序重写为抽象的主体并生成将抽象变量重写为应用程序的参数的规则EvalVar来EvalApp：[[（\x -> e2 ]] -> [[ e3]]哪里[[\ x -> e1]]=>[[\ y -> e3]];rules（EvalVar：[[y]]->[[e2]]）由于抽象是由转换规则打开的，因此绑定变量需要重命名以防止与自由变量冲突。构造规则（EvalVar：[[y]]->[[e2]]）生成规则EvalVar，该规则将上下文中绑定到y和e2的项的变量y的出现重写为e2，在这种情况下是EvalApp规则的左侧如果在此生成之前，另一个EvalVar规则已经为与y的相同绑定生成，则新规则将覆盖旧规则。 为了调整这种覆盖，动态规则机制提供了一个范围构造，它可以用来确定动态规则应该保持有效多长时间。然而，在我们正在定义的求值策略中，这是不需要的;通过在生成动态规则之前重命名抽象，我们可以保证y是一个新的变量，并且不会与任何早期的绑定冲突如果let绑定不用于表示替换，那么它们可以像抽象的应用程序一样进行计算。68EvalLet：[[letx= e1 in e2]]->[[（\x-> e2）e1]]基于这些规则的急切求值策略类似于具有显式替换的急切求值策略，即，以受限的方式遍历表达式，之后应用求值规则。动态规则EvalVar就像普通的静态规则一样被调用。eval11=rece（ try （ App（e，e））;try（EvalVar + （EvalApp + EvalLet）; e））请注意，在这种策略中，应用程序的参数在与抽象变量相关联之前进行评估，这确保了只有值才能替换变量。因此，应用EvalVar的结果不应该递归地评估。如果计算的结果不是一阶值，而是包含函数，则这些函数可能包含自由变量，这些自由变量具有由动态规则分配的值。由于评估不在抽象中进行，因此这些自由变量不会被它们的值替换。因此，评估策略评估11之后需要有一个子项目阶段来处理这一问题。Subs11=substitute（EvalVar）替代策略使用动态规则EvalVar来替换自由变量，同时重命名绑定变量以避免变量捕获。4.2更新的惰性评估与显式替换样式的情况一样，将急切求值策略转换为惰性求值策略是一个调整遍历方案的问题。eval12=rece（ try （ App（e，id）;try（（share（e）+（EvalApp+ EvalLet））; e））在评估变量之后，其绑定被更新，使得变量的后续评估不再被评估。共享策略替代变量，即，应用动态规则EvalVar，然后计算表达式，最后更新动态规则，以便在下次计算变量时生成此值。份额：[[x]]->[[e]]其中EvalVar; s> [[ x ]]=>[[ e]]; rules（EvalVar：[[x]]->[[e]]）695模式匹配在前面的部分中，我们已经探索了使用重写策略来定义纯lambda表达式解释器的几种风格。一旦选择了某种风格，扩展解释器以支持新的语言特性就变得非常容易。在这一节和下一节中，我们考虑使用模式匹配和失败来扩展lambda表达式。我们建立在动态规则风格的评估，存储绑定在动态生成的规则。5.1规则首先，我们用代数数据类型构造器扩展表达式语言。术语Con（n）是一个名为n的数据构造函数，它可以应用于使用普通应用运算符App的许多表达式。因此，构造函数应用程序的一个示例术语是App（App（Con（“Plus”），Con（“Zero”）），App （ Con （ “Succ” ） ，Con（“Zero”））或具体语法加零（成功零）从构造函数构建的值可以通过模式匹配规则进行拆分。规则类似于抽象，但它不是抽象变量，而是抽象构造器应用程序模式。一个规则由左边的一个表示术语模式的表达式和右边的一个表示规则值的一个示例规则是加上 零x->x或抽象语法Rule（App（App（Con（“Plus”），Con（“Zero”）），Var（“x”）），Var（“x”））lambda表达式的语言是用Con和Rule构造函数扩展的：签名构造器Con：String-> Exp//Id -> Exp规则：Exp * Exp-> Exp// Exp“->”Exp-> Exp5.2模式匹配缩减将规则应用于术语时，规则的左侧将与术语匹配。 如果成功，则生成右侧的实例化。这可以通过同时分解模式和主题词的归约规则来表示。如果模式是一个简单变量，它匹配任何参数项，70使用新的动态规则将参数绑定到变量：VarMatch：[[（x -> e1）e2 ]] -> e1where rules（EvalVar： [[x]]->[[e2]]）一个简单的构造函数只匹配同一个构造函数：ConMatch：[[（c-> e）c ]]->[[ e]]复杂的术语和模式是使用应用程序操作符组成的。如果子项匹配，则应用程序模式匹配应用程序值。这是通过将模式和值应用程序分解为curried规则和应用程序来实现的：AppMatch：[[（p1 p2 -> e3）（e1 e2）]] -> [[（p1 -> p2 -> e3）e1 e2]]请注意，此应用程序模式匹配不需要应用程序主干底部的构造函数;模式可以是x y的形式，即，可以在函数位置使用变量，从而一般地分解构造器应用。这个特性是在Rhodego [6]中引入的，以支持通用术语遍历。注意，该定义对非线性模式有一个后果，即，一个变量出现不止一次。例如，规则（Plus xx）-> e3左侧的模式包含变量x的两次出现。将此模式与Plus e1 e2匹配，最终重写为（x ->（x -> e3））e1 e2换句话说，内部的x将遮蔽外部的x。虽然这与通常的解释不同，在通常的解释中，与这些变量匹配的参数必须相等，但这是一个合理的解决方案;在这种情况下，不清楚范围规则是什么最后，let绑定可以被认为是规则应用程序的语法糖，LetRule：[[ letx = e1 ine2]]->[[（x-> e2）e1]]和抽象是一个简单规则绝对规则：[[\x-> e ]]->[[ x-> e ]]5.3评价战略基于这些规则，我们可以为lambda演算定义一个带有let和模式的惰性求值策略，如下所示：rules13= VarMatch+ ConMatch+ AppMatch+ LetRule+ AbsRule71评价13 = 2016年10月25日，try（App（e，id）; try（App（Rule（not（Var（id）），id），e））+ Rule（Var（id）;rename）; try（rules13; e+share（e）））这个策略有几个有趣的特点。在惰性计算中，不应该计算规则应用程序的参数，除非参数与不可变模式匹配。这是通过仅在函数简化为不可变规则时才计算参数来实现的。参数的求值是通过递归调用求值策略来完成的。主要的策略是将表达式简化为头范式，因为应用程序的参数不被评估。此外，规则中绑定变量的重命名是在策略中而不是在规则中完成的6失败与选择由于模式匹配的定义不包括模式匹配失败，因此在前一节中介绍的模式匹配扩展的价值有限。一个有用的模式匹配语言必须捕获失败，并提供一种选择替代执行的机制。函数式语言提供了case构造，它随后尝试许多规则，直到其中一个成功。在Rhodego中，case构造被分解为单个模式匹配规则和一个选择运算符。这样，规则就成了可以随意与其他规则结合在一起的头等公民。模式匹配失败本身也成为rst类。传统的格结构可以很容易地根据规则和选择来定义。在本节中，我们将进一步扩展我们的语言与失败和选择。6.1模式匹配失败首先，我们扩展了语言，明确了失败的概念。这是模式匹配失败的特殊标志。签名构造器失败：Exp //“失败”-> Exp当应用程序参数分别不是相应的构造函数或应用程序时，上一节中的ConMatch和AppMatch规则将无法应用。这通过以下将这些情况归为失败的负归约规则来表示。ConMatchN：[[（c -> e1）e2 ]] -> [[未通过]]哪里不（？[[ c ]]）> [[ e2]]72AppMatchN：[[（p1 p2 -> e1）e2 ]] -> [[fail]]where not（？[[ e3 e4]]）> e2注意，这些否定规则只有在参数已经被求值的情况下才有意义。6.2故障传播与选择当模式匹配失败变得明确时，就有可能处理它。我们添加了一个左偏选择运算符e1 + e2（LChoice），其中rst尝试其rst参数，如果这导致失败，则返回到其第二个参数。这个运算符使得在规则之间进行选择成为可能，也使得在可能导致失败的更复杂的计算签名构造器L选择：Exp * Exp-> Exp// Exp“+”Exp-> Exp选择运算符由以下归约规则定义如果左手边失败了，选择就减少到右手边。否则，如果左手边没有失败（并且不是规则（的选择）），则它减少到左手边。RightChoice：[[ fail<+e]]->[[e]]左选：[[e1+e2]]->[[e1]]哪里<不（？[[ fail]]+ ？[[ e3 -> e4 ]]+ ？[[ e5 + e6]]）> e1同样，这些规则只有在选择的左边被简化为一个值时才有意义。一个选择的左手边是一条规则，但不被认为是成功的。选择被认为是由规则的应用结果决定的。这通过以下分布规则来表示，该规则将应用程序分布在一个选项上：分发：[[（e1<+ e2）e3 ]] -> [[（e1 x）<+（e2 x）]]其中new => x; rules（EvalVar：[[x]]->[[e3]]）为了共享与参数表达式相关的计算，它被绑定到一个变量。故障通过应用程序传播73PropFunc：[[ faile]]->[[ fail ]]PropArg：[[efail]]->[[fail]]PropArg规则只适用于急切策略。在惰性策略中，应用程序参数的值被忽略，除非它被匹配。一个懒惰的评估策略，包括模式匹配失败，失败传播和选择，是eval13的直接扩展，增加了遍历，LChoice的销售和其他缩减规则：评价14 = 2016年10月25日，try（App（e，id）; try（App（Rule（not（Var（id）），id），e））+ LChoice（e，id）+ Rule（Var（id）;rename）; try（rules14; e+share（e）））规则14 =VarMatch + ConMatch + ConMatchN + AppMatch + AppMatchN+ 左选+ RightChoice PropFunc+Distrib+ LetRule + AbsRule通过总是评估函数参数并添加参数失败传播，可以从懒惰策略中派生出一个渴望策略。这种策略为具有rst类规则和泛型遍历的语言提供了一个解释器。这是罗托鲁戈语的基础[6]。RhoS- tratego增加了两个扩展。针对失败的匹配在惰性评估设置中很有用，可以强制评估。一个cut操作符，它可以用来进行回溯操作，以提交一个选择，并防止Distrib规则的进一步应用6.3案例：Sugar for ChoiceML和Haskell等函数式编程语言的传统案例构造可以通过规则和选择来实现。它可以被添加到上面定义的语言中，作为程序员的方便，通过引入case构造，它使用了一个替代列表签名构造器Case： Exp *List（Alt）-> Exp//“case”Exp“of”“{”{Alt“;"}*“}”-> ExpAlt：Exp*Exp->Alt//Exp“->”Exp这种语法糖可以被脱糖，变成一种选择的应用，呈现为规则，对案件被监票人：74案例脱糖：[[e1 of { as } ]] -> [[ e2 e1 ]]其中[[e1 + e2]]\，\[[p-> e]A]->[[p-> e]]\）> as=>e2注意，foldr（s1，s2，s3）是fold和map的组合，即， 简化列表[t1，...，tn]到（t1，（...，& lt;s2>（tn，）。匿名规则\[[p -> e ]A] ->[[p -> e]]\将case alternative转换为规则。左手边的A注释用于消除术语的歧义。7总结发言本文中的技术已应用于几个实际的解释器，包括Tiger，Rhodego的解释器，以及一个针对Rhodego规范的解释器-。Tiger语言的解释器规范[1]是Tiger-in-Answergo项目1的一部分，该项目探索了程序转换技术在编译中的应用。该语言包括命令式功能，如循环，赋值，可更新的记录和数组。使用动态规则可以优雅地表达这些特征。Rhodego [6]是一种函数式编程语言，具有用于策略重写的内置功能。该语言以模式匹配规则、第5节和第6节的选择和失败构成了该语言的核心。解释器的完整规范可以在[6]中找到，其源代码可以在线获得2。此外，我们已经试验了命令式程序的优化器的指定（例如，常数和复制传播、死代码消除）;由重写策略引导的一组优化规则，该重写策略使用动态规则来传送上下文敏感（数据流）信息。来自解释器的许多“常量折叠”规则可以在这样的优化器中重用。虽然很明显，优化器可以实现作为程序的部分评估，解释器和优化器之间的关系需要进一步研究。确认在2000年春季访问INRIA Roquencourt期间，Dick Kieburtz首次探索了lambda演算评估策略。 2001年1月，在访问IN-RIA/Lorraine期间，提出了使用Aneggo来指定口译员的想法，1 http://www.stratego-language.org/Hpc/TigerInStratego2 http://www.stratego-language.org/Stratego/RhoStratego75rho 演 算 的 解 释 者 是 Christophe Ringeissen 和 Pierre-Etienne Moreau 。Karina Olmos实现了许多命令式优化策略。LDTA的裁判员对论文提出了建设性的意见。引用[1] A. W.阿佩尔在ML中实现的现代编译器。剑桥大学出版社，1998年。18[2] P. Bor ovans ky，C. Kir c hner，H. Kir c hner，P. E. Moreau和M. 维特克Elan：基于计算系统的逻辑框架。在J. Meseguer，编辑，理论计算机科学电子笔记，第4卷。Elsevier Science Publishers，1996.1996年第一届重写逻辑与应用研讨会论文集2[3] P. Borra，D.Clement，T.Despeyroux，J. Incerpi，G.卡恩湾郎诉帕斯卡Centaur：系统。技术报告777，INRIA，SophiaAntipolis，1987年。2[4] A. van Deursen，J. Heering，and P. Klint，editors.语言原型。一种代数规范方法，AMAST计算系列第5卷。World Scienti c，Singapore，September 1996. 2[5] K.- G.杜和P. D.苔藓通过组合动作语义模块来组合编程语言。语言描述、工具和应用研讨会（LDTA'2001），意大利热那亚，2001年4月。一、二[6] E.多尔斯特拉程序转换语言的第一类规则和类属遍历。硕士论文，乌得勒支大学，乌得勒支，荷兰，2001年8月二、三、十、十四、十七、十八[7] M. Felleisen和R. Hieb.时序控制与状态的句法理论修订报告。TheoreticalComputer Science，103（2）：235{271，1992. 2[8] P. Johann和E.维瑟融合逻辑和控制与局部转换：一个例子优化。芽孢杆菌中Gramlich和S. Lucas，编者，Workshop on Reduction Strategies in Rewritingand Programming （ WRS'01 ） ， 第 57 卷 ， Electronic Notes in TheoreticalComputer Science，Utrecht，The Netherlands，2001年5月。Elsevier SciencePublishers.......................................................6[9] G.卡恩自然语义学在计算机科学理论方面的研讨会论文集，帕绍