融合逻辑和控制的程序转换组件定义及优化策略研究

理论计算机科学电子笔记57（2001）网址：http://www.elsevier.nl/locate/entcs/volume57.html19页融合逻辑和控制与局部变换：一个优化实例帕特里夏·约翰数学和计算机科学系，迪金森学院，卡莱尔，PA 17013，http://www.dickinson.edu/johannp，johannp@dickinson.edu埃尔科·维瑟乌得勒支大学信息与计算科学研究所Box 80089，3508 TB Utrecht，TheNetherlands http://www.cs.uu.nl/visser，visser@acm.org摘要抽象编程支持在程序构造中将逻辑关注点与控制问题分离。虽然这种关注点分离可以减少代码大小并提高代码的可重用性，但其主要缺点是会产生计算开销。融合技术可用于将抽象程序的可重用性与专用程序的高效性在本文中，我们说明了一些重写策略可以用来分离的程序转换规则的定义下，他们被应用的策略的方式。这样做支持程序转换组件的一般定义。然后，可以使用策略的融合技术来专门化这些通用组件。我们展示了如何通用的最里面的重写策略可以通过融合它的规则，它是适用于优化。优化和应用优化的程序都是用策略语言Rightgo指定的。优化是基于小的转换规则，在策略的控制下局部应用，使用有关应用规则的上下文的特殊知识。1介绍抽象编程技术支持算法功能的通用定义，通过将通用组件插入在一起可以获得不同的算法配置。因此，这些组件可以在许多情况下和许多不同的组合中重复使用。抽象编程的优点是减少了代码大小，c 2001年由Elsevier Science B出版。V.CC BY-NC-ND许可下的开放访问。约翰和维瑟2程序的可重用性。缺点是它支持的关注点分离可能会引入相当大的计算开销。相比之下，特定问题实例的代码可以有效地混合逻辑和控制，以达到比一般情况下更有效的实现。抽象编程的挑战是保持高层次的关注点分离，同时实现混合程序的高效性。融合技术通过自动地从程序的抽象复合版本中导出混合的有效版本来缓解模块化和有效性之间的紧张关系。例如，在函数程序的森林砍伐中，通过将函数组合融合在一起来消除中间数据结构[6，11，17]。融合还可以从类似于数值程序的数学规范的编程的代数风格转换为更新风格，其中函数参数被重写以重用分配给大型矩阵的内存[2，4]。Replego [15，16]是一种领域专用语言，用于基于重写策略范式的程序转换系统的规范。Allogo将基本转换规则的规范与应用这些规则的策略的规范分开。控制转换规则应用的策略可以使用一小组原始策略组合子进行编程。这些组合子支持非常通用的控制模式的定义，允许根据需要组合策略和规则以实现各种程序转换。这种抽象的编程风格导致程序转换系统的简洁和可重用的规范。然而，由于它们的通用性，一些策略没有足够的信息来有效地执行它们的任务，即使这些策略的专业化可以有效地实现。在本文中，我们开发了一个融合技术的Rendgo程序，spece- cializes通用的最内层约简策略，以特定的规则集。这种优化支持抽象编程，同时获得手写专门化的效率。优化是通过局部变换在Rocgo中实现的。局部变换是在策略的控制下应用于程序的选定部分的在传统的程序优化中，变换应用于整个程序.在优化命令式程序时，复杂的转换被应用于整个程序[12]。在编译风格的转换[3]|例如，在Glasgow Haskell公司[14]|在整个程序中应用大量小的、几乎微不足道的程序变换，以通过累积小的程序改变来实现大规模优化。我们在这篇文章中开发的优化风格是这些思想的组合：使用将它们应用到程序的特定部分以实现复杂转换效果的策略组合一些小的转换步骤。 因为变换是局部的，在应用点关于主题程序的特殊知识约翰和维瑟3模Peano签名排序Nat构造函数Zero： NatSucc： Nat -> Nat加：Nat *Nat->Nat规则A ：Plus（Zero，x）-> xB ：Plus（Succ（x），y）-> Succ（Plus（x，y））可以使用阳离子。这就允许适用原本不适用的规则。本文的其余部分组织如下。在第2节中，我们解释了基本的RISTOGO和介绍一般的RISTOGO规格的最内层约简。我们在第3节中提出了这个策略的优化版本。在第4节中，我们展示了如何从原始规范导出最内层的优化规范。第5节介绍了第4节中优化规则的JavaScript实现。第6节结束。2最内约简的一个一般性说明NodeGo是一种用于指定程序转换的语言。该语言的一个关键设计选择是逻辑和控制的分离。程序转换的逻辑由重写规则捕获，而重写策略控制这些规则的应用。在本节中，我们将描述与本文相关的Applogo元素我们用一个小的应用程序来说明它们，该应用程序使用最内层约简的通用规范来简化自然数的表达式。在[16]中给出了一个完整的描述，包括形式语义。在Replego中，要转换的程序被表示为一阶项。签名描述了术语的结构签名S上的项是来自S的空值构造器C或应用C（t1，...，tn）的n元构造函数C从S到S上的项ti. 例如，Zero、Succ（Zero）和Plus（Succ（Zero），Zero）是图1中签名上的项2.1重写规则重写规则表示项的基本转换重写规则具有L：l-> r的形式，其中L是规则的标签，并且项模式l和r分别是其左手侧和右手侧 术语模式是变量、空值构造函数C或应用程序C（p1，. ............................. ，pn）图1.一、一个带有签名和重写规则的例子约翰和维瑟4一个n元构造函数C到术语模式pi。例如，图1显示了简化自然数和的重写规则A和B。正如这里所建议的那样，Replugo提供了一个简单的模块结构，允许模块导入其他模块。当模式l与t匹配时，规则L：l-> r适用于（基础）项t，即，当L具有与T相同的顶层结构时。将L应用于t具有将t变换为通过用t的子项替换r中的变量而获得的项的效果。 例如，规则B将项Plus（Succ（Zero），Succ（Zero））变换为项Succ（Plus（Zero，Succ（Zero），其中x对应于Zero，y对应于Succ（Zero）。在项重写的正常解释中，通过将重写规则先验地应用于项及其子项直到不可能进一步应用为止来规范化项例如，术语Plus（ Succ（Zero），Zero）在规则A和B下标准化为术语Succ（Zero）。但是，由于规范化一个术语相对于规范中的所有规则并不总是可取的，并且由于重写系统不需要是并发的或终止的，因此通常需要更谨慎的控制一个常见的解决方案是在签名中引入额外的构造函数，然后使用它们通过额外的规则来编码控制，这些规则指定原始规则的应用位置和顺序。可编程重写策略提供了一种替代机制来实现这种控制，同时避免引入新的构造函数或规则。2.2将规则与策略相图2和图3说明了如何使用策略来控制重写。图2给出了在某些变换下最内层规范化概念的一般定义。最里面的策略可以用任何规则选择来实例化，以实现这些规则下的术语规范化。例如，在图3中，策略main被定义为使用规则A和B实例化的最内层策略来规范化Nat项。一般来说，变换规则和约简策略可以独立地定义，也可以以各种方式组合。可以对规则进行不同的选择，或者可以使用不同的策略来应用规则。并不是规范中的所有规则都需要参与规范规范化。通过这种方式，可以在Incidego中开发一个有效的转换规则库，并根据需要将其应用于各种转换。2.3重写策略重写策略是一个程序，它可以转换术语，也可以失败。在成功的情况下，结果是转换的项或原始项。 在失败的情况下，没有结果。重写规则只是将转换应用于根的策略约翰和维瑟5模块最内层策略最里面（s）=自底向 上 （ s ） = 红 色（s）=bottomup（red（s））recr（all（r）;s）recx（s）;bottomup（x）<+页：1约翰和维瑟6模块apply-peano导入最里面的peano策略主要 =最内层（A+ B）图二. 通用遍历策略。图三. 使用皮亚诺规则。的条款。策略可以被组合成更复杂的策略，通过Replego的策略运算符。 标识策略id总是成功，并且保持其主题项不变。 失败策略失败总是失败。策略s1和s2 rst的顺序组合s1; s2试图将s1应用于主题词。如果成功，则将s2应用于结果;否则失败。策略s1和s2的非确定性选择s1 + s2试图将s1或s2应用于主题词，但顺序不明。如果s1或s2成功，则成功，否则失败。策略s1和s2 rst的确定性选择s1< + s2试图将s1应用于主题词。如果s1失败，则尝试将s2应用于主题词。如果s1和s2都失败了，那么它也失败了。策略s的递归闭包rec x（s）试图将策略rec x（s）替换变量x在s中的每一次出现而获得的策略应用于主题项。策略定义f（x1，...，xn）=s引入了用策略x1，...，xn且具有主体s。 这些定义不能（直接或间接）引用所定义的操作符。相反，所有的递归都必须通过递归运算符rec显式表示。2.4Term遍历刚刚描述的策略组合器组合了将变换规则应用于其主题术语的根的策略为了在术语的内部站点应用规则（即，到子项），则有必要遍历该项。Replego定义了几个原始运算符，它们暴露了构造函数应用程序的直接子项。这些可以与上面描述的运算符相结合，以定义各种各样的完整项遍历。为了本文的目的，我们将遍历运算符的讨论限制在同余运算符和all运算符。同余运算符为Strat-ego中的项遍历提供了一种机制.对于每个构造函数C，都有一个对应的同余运算符约翰和维瑟7C.如果C是n元构造函数，则相应的同余算子定义策略C（s1，...，Sn），其仅适用于形式C（t1，...，tn）得到C（t1 '，...，Tn ′），如果每个SI成功地应用于ti，从而产生ti ′。例如，同余式Plus（s1，s2）只适用于Plus项，它的工作原理是将s1应用于第一个被加数，将s2应用于第二个被加数，产生Plus（t1 '，t2'）。如果对于 任 何 i ，si 到ti的应用 失 败， 则C（s1，...，Sn） 到C（t1，...，TN）也失败了。运算符all（s）将s应用于构造函数应用C（t1，.，tn）。当且仅当对直接子项的所有应用都成功时，它才成功。 结果项是构造器应用C（t1 '，.，其中ti'是通过将s应用于项ti而获得的结果。 注意，all（s）是常数的恒等式，即，没有孩子的申请人图2中的自底向上策略中有一个使用all的示例策略表达式recx（all（x）; s）指定策略首先递归地应用于项的所有直接子项，从而应用于其所有子项。如果成功，则将参数策略s应用于结果项。这种自底向上的定义捕获了术语上的后序遍历的一般概念图2中最内层的策略是使用自底向上定义的。strat- egyinner（s）对一个词执行自底向上的遍历在每个子项处，它将策略称为红色以减少该子项。这意味着在将red（s）应用于项之前，其所有子项都相对于s进行归一化。然后，策略red（s）将转换s应用于主题词。如果成功，则通过调用自底向上遍历进一步简化转换的结果，该遍历递归地调用每个子项的red（s）转换如果不是，那么这意味着主题词是正常形式的，所以red（s）后面跟着id。因此，最内层策略捕获了并行最内层约简的概念。然而，请注意，最内层的其他规范也是可能的，因为策略的递归表示通常不是唯一的。3最内约简的一个优化规范对图2中最内层策略的规范进行检查，发现它遍历项的上下方式导致了不一致性。困难的是，已经被归一化的子项可以被重新考虑多次进行归一化。例如，考虑图1中的规则B由于最内层的定义方式，在main的应用中，与B的左侧匹配的项的子项在应用该规则之前已经是标准形式特别地，匹配变量x和y的项是正规形式。然而，在构造了右侧的Succ（Plus（x，y））之后，由于在所谓的策略red中出现了自底向上，x和y项被完全重新归一化。重整化需要这些项被完全遍历，约翰和维瑟8模块应用-Peano策略主峰=自下而上（recr（（{x：？intx=0;！x}+{x，y：成功（r>加上（x，（y））}约翰和维瑟9？intx（x，y）;）<+id））见图4。 优化战略。规则在每个子项上都被尝试。因为这些项是正规形式的，所以当然没有进行实际的变换。在使用规则A和B进行最内层规范化的特殊情况下，图4中的定义更有效。这个定义完全避免了重正化|我们在第4节中介绍了它使用的Rightgo结构，|但是对于这样的优化存在（至少）两个问题。首先，手动优化策略可能非常困难。手工优化是容易出错的，特别是在任何合理大小的规格上执行第二，规则和策略倾向于混合在优化的程序中。这既抑制了规则与其他策略的重用，也抑制了规则与其他策略的组合的重用，而不是那些“硬连线”到优化策略中的组合由于这些原因，模块化规范到优化版本的自动转换是可取的。在下一节中，我们将通过展示如何从图2中自动导出图4中的优化规范来证明我们对最内层我们通过将其应用于特定程序inner（A+B）来演示该技术，但它同样很好地优化了应用于任何规则选择的inner4推导在本节中，我们将展示如何通过系统转换从策略最内层（A + B）导出图4的优化实现。在下一节中，我们将用XML形式化我们使用的转换规则，并将开发一种策略来以正确的顺序自动应用它们。推导的目的是融合出现在由最内层调用的策略red的定义中的自底向上的发生与规则A和B的右侧。这避免了重新规范化这些规则左侧的变量所绑定的项。因此我们首先对规则进行脱糖，然后内联（展开）定义，在一个单一的表达式包含完整的规格的最内层的战略。然后，自底向上策略可以分布在最内层应用的规则的右侧;在我们的运行示例中是A和B约翰和维瑟104.1去糖规则在Arabgo中，规则不是原语。 相反，它们是用匹配和构建术语的原语来表示的。战略？t将主题词与词模式t匹配。战略！t将主题术语替换为通过实例化术语模式t中的变量及其当前绑定而构造的术语。构造{xs：s}界定了策略 s 中变量的作用域。因此，规则 L ：l->r只是 L={x1，.，xn：？l;！r}，其中Xi是规则中出现的变量。因此，图1中的peano模块的示例规则简化为A ={x：？int x = 0;！x}B={x，y：？Plus（Succ（x），y）;！Succ（Plus（x，y））}4.2内联定义推导的第一步包括内联定义，即，用定义的主体来代替每个对策略的调用 。 如 果 f （ s1 ， ... ， sn ） =s 是 策 略 算 子 f 的 定 义， 则 调 用 f（s1，...，Sn）可以由s[s1/x1，...，Sn/Xn]，即，通过用实际参数替换f体的形式参数而获得的策略。对于图3中apply-peano模块中的主策略，内联给出了(1) 最内层（A+ B）、根据最深处的定义，(2) 自下而上（红色（A+ （B））根据红色的定义，这反过来又给出了(3) bottomup（rec r（（A+ B）; bottomup（r）<+id））最后，内联规则A和B的定义，(4) 自下而上（rec r（（{x：？int x = 0;！x}+ {x，y：？（x，y）;！Succ（Plus（x，y））}）; bottomup（r）<+id））4.3顺序组合优于选择在推导的下一步中，我们使用规则将自底向上策略右分配到非确定性选择策略（x+ y）; z->（x; z）+（y; z）此规则并非对所有策略表达式都有效。考虑一个项t，其中x和y都成功，（x;z）失败，（y;z）成功。然后（x+y）;如果尝试应用x，则z将失约翰和维瑟11败。相比之下，（x;z）+（y;z）总是约翰和维瑟12因为（y;z）成功。然而，只要z保证成功，规则就成立;在这种情况下，规则两边的成功或失败完全取决于x和y的成功或失败。因为id总是成功，所以递归策略（4）中的r也保证成功。因此，bottomup（r）保证成功，因此根据规则的bottomup（r）的正确分配是有效的。这给(5) 自下而上（rec r（（{x：？int x = 0;！}; bottomup（r）+ {x，y：？Plus（Succ（x），y）;！Succ（Plus（x，};bottomup（r））<+id））4.4作用域上的顺序组合接下来，为了将bottomup（r）应用于规则的右侧，我们需要通过应用转换将其置于规则的作用域之下{xs：s1}; s2 -> {xs：s1; s2}如果xs中的变量在s2中不是自由的，则此规则有效。其应用将（5）转化为(6) 自下而上（rec r（（{x：？int x = 0;！x; bottomup（r）}+ {x，y：？（x，y）;！Succ（Plus（x，y））; bottomup（r）}）<+id））4.5策略应用我们现在可以将bottomup（r）应用于每个规则右侧的项 用符号t来表示！t;s，即，为了表示将策略s应用于由当前绑定确定的t的实例，我们得到(7) 自下而上（rec r（（{x： ？（x，0）; bottomup（r）> x}+ {x，y：？（x，y）; bottomup（r）> Succ（Plus（x，y））}）<+id））4.6自下而上的分布将bottomup（r）应用于构造函数应用程序会导致以下推导：C（t1，.，（tn）【bottomup的定义约翰和维瑟13 C（t1，.，（tn）= {recursion} C（t1，.，（tn）约翰和维瑟14={顺序组合和所有的语义} C（t1，.，tn）【bottomup的定义 C（bottomup（r）> t1，.，& lt;bottomup（r）> tn）通过反复应用这个规则，bottomup（r）分布在右侧的术语结构上，直到遇到变量。这给(8) 自下而上（rec r（（{x：？（x，0）; bottomup（r）> x}+ {x，y：？int x（x，y）; Succ（r> Plus（bottomup（r）> x，bottomup（r）>y））}）<+id））4.7避免重正化最后，我们使用观察结果， v-> v如果v是一个起源于规则左边的变量。也就是说，如果vs包含所有在l中出现的变量，则v在vs中，并且{vs：？l;！r}是一个策略，那么<在r中bottomup（r）>v的出现可以被v本身替换。这个观察是有效的，因为匹配规则左侧变量的项已经是标准形式。虽然这种观察依赖于非局部信息，但它确实产生了一种局部的变换，因为它只在一个单一的策略，即，在策略的控制下应用于（本地）程序的选定部分。使用它，我们得到了所需的优化版本的inner（A+B）：(9) 自下而上（rec r（（{x：？int x = 0;！x}+ {x，y：？（x，y）;< r> Succ（ Plus（x，y））}）<+id））5执行在本节中，我们将展示如何在第4节中可以在马达加斯加实施。我们从定义JavaScript程序的抽象语法开始。然后，我们在规则中经常出现的抽象语法中添加覆盖到抽象的特定部分。接下来，我们将推导中使用的规则形式化为规则。最后，我们将这些规则组合成一个策略，优化出现的最内层的策略在Recho speci阳离子。 该优化适用于最内层（R1+.的形式的所约翰和维瑟15有策略。+Rn），具有任意规则Ri。约翰和维瑟165.1抽象语法图5定义了Ringgo中术语和策略表达式的抽象语法的签名。签名已被减少到那些结构是相关的优化最内层。术语(10) 作用域（[“x”]，Seq （ Match （ Op （ “Plus” ， [Op （ “Zero” ，[] ） ， Var （ “x” ） ] ） ） ， Build （ Var（“x”）在这个签名上是来自图1的规则A的主体在去糖之后的抽象语法表示，并且(11)作用域（[“x”，“y”]，Seq （ Match （ Op （ “Plus” ， [Op （ “Succ” ， [Var（“x”）]），Var（“y”）]），Build（Op（“Succ”，[Op（“Plus”，[Var（“x”），Var（“y”）]）是规则B的表示。正如这个签名所暗示的，Applugo支持内置的数据类型String。[t1，. [2019 - 10 - 15]还提供了。ID：Strat失败：StratSeq：斯特拉特 * 斯特拉特-> Strat选择：斯特拉特 * 斯特拉特-> StratLChoiceSVar：：斯特拉特 * 斯特拉特字符串->->StratSVarRec：String * Strat-> StratSDef：String * List（String）* Strat -> SDef呼叫：SVar* 列表（Strat）-> Strat约翰和维瑟17所有：Strat-> Strat匹配：Term-> Strat构建：Term-> Strat范围：List（String）* Strat-> Strat哪里：Strat-> Strat图五.简化了JavaScript程序的抽象语法。约翰和维瑟18模块策略-模式叠加Do（x）= Call（SVar（x），[]）最内层（s，im，r，y）=自底向上（im，Red（s，r，y））自底向上（r，s）= Rec（r，Seq（All（Do（r）），s））Red（s，x，y）= Rec（x，LChoice（Seq（s，Bottomup（y，Do（x），Id））图六、几种标准遍历策略的抽象语法模式5.2抽象模式我们希望优化策略表达式的某些特定模式。由于我们不想依赖于规范编写者为这些模式选择的名称，因此我们需要能够识别模式的结构。由于使用抽象语法表达式编码模式可能会导致大量难以管理的术语，因此我们使用了Replego覆盖机制来抽象它们。覆盖层为复杂的术语模式提供了一个名称（伪构造函数）。伪构造函数然后可以在匹配和构建术语中用作普通构造函数叠加层可以在其定义中使用其他叠加层，但不能递归。叠加可以被认为是术语宏。使用覆盖，我们可以编写涉及复杂术语模式的简洁转换规则。图6中的模块策略模式定义了与图2中的示例中的策略inherently、bottomup和red相对应的抽 象 语 法 模 式 的 覆 盖 。 因 此 ， 覆 盖 Do （ “f” ） 是 术 语 Call （ SVar（“f”），[]）的缩写。图6中的“extra”参数对应于图2中5.3转换规则图7定义了第4节推导中使用的规则的前六个规则是用于在其它操作者上顺序组合的分布规则确定性和非确定性选择的顺序组合的正确分配规则被参数化，策略决定要分配的策略表达式是否保证成功。AssociateR规则将合成关联到右侧。IntroduceApp 规 则 定 义 了 转 换 ！ t; s->< s>t 。 最 后 ， 规 则BottomupOverConstructor将Bottomup分布在构造函数应用上。该规则使用map策略操作符将自底向上的应用程序分布在构造函数的参数列表上。如图7所示，Replego规则可以具有使用关键字where引入的条件。条件规则仅在where子句中的条件成功时才适用此外，符号\r\将规则r转换为策略。因此，BottomupOverConstructor中map的参数是对应于局部规则的策略，该局部规则将项t转换为Bottomup到t的同一实例的应用。约翰和维瑟19模块fusion-rules导入stratego规则SeqOverChoiceL：Seq（x，Choice（y，z））-> Choice（Seq（x，y），Seq（x，z））SeqOverLChoiceL：Seq（x，L选择（y，z））-> L选择（Seq（x，y），Seq（x，z））SeqOverChoiceR（succ）：Seq（Choice（x，y），z）-> Choice（Seq（x，z），Seq（y，z））其中succ> zSeqOverLChoiceR（succ）：Seq（LChoice（x，y），z）-> LChoice（Seq（x，z），Seq（y，z））其中succ> zSeqOverScopeR：Seq（Scope（xs，s1），s2）-> Scope（xs，Seq（s1，s2））SeqOverScopeL：Seq（s1，Scope（xs，s2））-> Scope（xs，Seq（s1，s2））助理R：Seq（Seq（x，y），z）-> Seq（x，Seq（y，z））介绍应用程序：Seq（Build（t），s）-> Build（App（s，t））Bottomup OverConstructor： App（Bottomup（x，s），Op（c，ts））->App（s，Op（c，map（\t-> App（Bottomup（x，s），t）\）>ts））见图7。 分布和关联规则。5.4Strategy图8定义了将图7中的规则组合成用于优化最内层策略的出现的策略的策略融合。假设在应用融合之前已经进行了脱糖和内联。这些转换是由Replugo编译器自动处理的。融合策略对四个组成策略进行排序。首先，使用对应于Innermost约翰和维瑟20覆盖的同余算子来识别最内层策略的出现。 IntroduceMark规则将一个标记应用于在术语的最内部规范化中使用的规则的选择，然后propagate-mark策略将该标记传播到参数