42理论计算机科学电子笔记76（2002）网址：http://www.elsevier.nl/locate/entcs/volume76.html10页重写和缩小Sergio Antoy1计算机科学系波特兰州立大学，波特兰OR 97207，美国萨尔瓦多·卢卡斯2DSIC圣保罗理工大学摘要重写和缩窄策略的传统研究旨在建立策略的基本属性，如可靠性、完备性和/或最优性在这项工作中，我们分析和比较重写和缩小战略的角度来看，考虑到的信息的策略来计算一个步骤。需求的概念为提出和比较著名的战略提供了一个合适的框架 我们发现存在一个几乎线性的策略序列，考虑到越来越多的信息。 我们的例子表明，随着我们在这个序列上的进展，一个策略变得更加集中，并避免了一些无用的步骤计算的战略之前，它在这个序列。我们的工作仍在进行中，它澄清了类似或相关策略的行为，并有望简化某些结果从一个策略到另一个策略的转移。它还表明，需求的概念是原子和战略研究的基础。关键词：声明式编程，缩小，重写，策略。1介绍现代的函数逻辑程序，在大多数情况下，建模的编译器，tor为基础的长期重写系统，并通过缩小执行缩小1由美国国家科学基金会在INT-9981317、CCR-0110496和CCR-2000资助下部分支持。0218224。 电子邮件：antoy@cs.pdx.edu，WWW：http://www.cs.pdx.edu/antoy2部分由CICYT TIC 2001 -2705-C 03 -01，Acciones Integradas HI2000-0161、HA 2001-0059、HU 2001-0019和Generalitat Valenciana GV 01 - 424。电子邮件：slucas@dsic.upv.es网站，网址：http://www.dsic.upv.es/users/elp/slucas.html2002年由ElsevierScienceB. V. 操作访问根据C CB Y-NC-N D许可证进行。安东尼和卢卡斯43是重写的一种推广，它允许对可能包含不完整信息的表达式求值，这些信息由未实例化的变量表示。执行函数逻辑程序的一个基本组成部分是缩小策略，即，一种策略或算法，用于确定首先应计算表达式的哪个子表达式以及未实例化变量的绑定（如果有的话）。多年来，提出了许多战略。其中一些可以概括为缩小众所周知的函数计算行为，如按值调用或按需调用。其中一些策略相当复杂。其他策略提出了一种更简单的方法，即通过替换映射（replacement map）来优先计算函数调用的某些参数，这些映射通常由程序员定义。例如，映射可以建立函数调用的哪些参数应该总是（或从不）在调用之前被评估函数式编程和函数式逻辑编程之间的显著区别在于，在某些情况下，后者由更大类的重写系统建模，特别是支持非确定性计算的重写系统。非确定性源于对重写规则的选择有了这种规则，缩小策略变得更加复杂。按值调用和按需调用的经典概念不再适用或有意义，并且所提出的策略的属性不太容易理解。不可忽略的战略数量可以非正式地归类为需求驱动。一些需求驱动的策略适用于重写系统的类别，这些重写系统比典型函数式语言中的一阶计算建模大得多。需求驱动战略的非正式特征如下。如果可能的话，在顶部评估（减少或缩小）项t。否则，如果t的根的某些参数可能会促进重写规则在顶部的应用，换句话说，如果规则“要求”这些参数的评估，则（递归地）评估这种“需求性”的概念在不同的战略中各不相同，稍后将专门讨论，它很简单，往往也很实用，但在某些情况下并不完善。规则要求对某些参数求值的事实，既不意味着对这些参数的求值保证了规则的应用，也不意味着规则的应用在某种直观意义上对t的（完全）求值是必要的。一般来说，这些问题是不可判定的. 在最坏的情况下，需求驱动的策略可能无法终止计算，即使终止是可能的（不完整性）。在其他情况下，策略可能只是执行更聪明的策略会避免的步骤（浪费或非最优性）。最后，需求驱动的策略可能会终止计算，但不会产生范式（不正确）。在本文中，我们回顾了几种重写或缩小策略，我们从前面讨论的“需求”的角度对它们进行了描述和分析安东尼和卢卡斯44→→|→踏出一步。我们调查的主要结果是，一个策略关注的信息越多，该策略的重点就越突出。更确切地说，查看更多信息的策略能够执行更少的计算步骤一个结果。这一结论并不令人惊讶。然而，我们的新方法允许我们在同一框架内研究简单的策略，如上下文敏感的重写策略[12]，以及更复杂的策略，如需要缩小[7]。我们的方法使它更容易理解孤立的每一个策略和策略之间的一些关系。这简化了选择哪种策略更适合用于某些应用程序或某些上下文。第二节简要回顾了一些策略，并从需求的角度提出了这些策略.第三节对我们的结论进行了总结。2战略直观地说，需求驱动的战略工作原理如下。给定一个要评估的项t，该策略的目标是在t的根处应用每一个可能的重写规则。让我成为一个规则。在一些情况下，当t和l统一时，l r立即适用。在其他情况下，例如，当L的前导符号和T的根不同时，可以立即排除该规则。有趣的情况是，不能立即断定某项规则最终是否适用。 这发生在，例如，当t和l的根相同时，l在某个位置p的子项和相应的子项t|t的p不统一。由于我们考虑基于构造函数的项重写系统，位置p处l的子项是构造根的;如果位置t的p也是以构造函数为根的，那么我们可以立即排除规则。 如果位置p处的t的子项是操作根的，需要在规则l→r可以应用于t的根（的后代）之前对其进行评估。不严格地说，在这种情况下，t p的求值是由lR. 迪埃杰伦特需求驱动的策略以不同的方式选择p例如，考虑以下列表上的熟悉操作。该符号采用Curry [9]的语法，在这种情况下与Haskell [18]相同，除了我们用Peano符号表示自然数。这种选择既简化了代码，又保持了程序和重写系统之间的更紧密的对应关系。append[] ys = ysappend（x：xs）ys = x：appendxs ys drop 0 xs = xsdrop（Succ-）[] =[]drop（Succ n）（-：xs）= drop nxs（一）给定项t=（drop（n+m）（append p q）），一些需求驱动策略将评估（n+m）或（append p q）或两者，希望一旦安东尼和卢卡斯45对这些子项进行评估，某些丢弃规则可能变得适用于所得项。此示例提示了几个注意事项。(C1)drop的论点并不都一样。如果不看右边，似乎更倾向于计算（n+m）而不是（append p q）。原因在于，在（n+m）的值上，可能不需要（append p q）的求值。更准确地说，如果（n+m）不求值为构造函数根项，则t本身不能求值为构造函数根项。因为在函数（逻辑）语言中，范式只有在它们是构造器项时才有意义，在这个例子中，（append p q）的求值将是无用的。许多需求驱动策略并不那么复杂，但是对于需求驱动策略所针对的某些重写系统类别，这种复杂可能是不可能的，例如，参见Display（2）中的操作插入定义。(C2)某些需求驱动策略使用单独的规则来选择要评估的项。在某些情况下，这种情况会导致次优计算。(C3)需求驱动的战略是自上而下的。这意味着，需求驱动策略通过遍历项t来选择要评估的项t的哪个子项。从根到叶。这种自上而下的遍历有两个相互关联且有些微妙的后果：（C3a）需求驱动策略在函数的参数优选为不被评估，但是在仅执行不可避免的步骤的意义上，该策略不是完全懒惰的，参见（1），以及（C3b）在优选地不缩小术语的内部叙述的意义上，需求驱动策略主要是最外面的，但是在仅缩小最外面的叙述的意义上，该策略不是完全最外面的，参见（2）。下面的例子定义了一个操作，该操作将一个元素插入列表中的某个非确定性选择的位置。通常使用该操作，例如，用于计算列表的置换或用于从列表中提取某些元素。插入x y = x：yinsert x（y：ys）= y：insert xys（二）表达式（insert 0 [1，2]）产生[0，1，2]、[1，0，2]或[1，2，0]中的任何一个。现在，考虑t=（insert 0（append p q））的求值。在t的计算中，一个计算（附加p q），但另一个不计算。 对于涉及这种操作的计算，没有普遍接受的必要步骤的概念，并且计算（append p q）的计算不是最外层的。在本节的其余部分，我们回顾了一些策略，并从需求的角度提出上下文敏感的重写策略[12]上下文敏感重写（CSR）使用替换映射来定义函数（调用）参数的索引来评估[13]。任何评价安东尼和卢卡斯46--禁止其他参数。地图的定义是程序员的责任。根据经验，要求值的函数调用的参数是那些对应于某些重写规则左侧的不可变项的参数。用这种方法得到的映射称为正则映射。正则替换映射确保了左线性重写系统的头范式可以被计算[13]。例如，在（1）中定义的操作append的规范映射原因是除非append的第一个参数被求值，否则append的规则不能被触发。append的第二个参数的值不影响任何一条规则的应用。规范替换映射的定义类似于需求性的概念（通过术语重写系统的规则），参见[13]的5.1节在（1）中定义的操作drop的正则映射包含位置1和2。该策略单独查看每个重写规则的每个参数。因此，该策略无法根据第一个参数的值确定是否不需要对drop懒惰重写策略[8，15]延迟重写（LR）使用类似于CSR的替换映射。这张图旨在定义一个“纯粹的”渴望行为（因为“懒惰的”或要求的行为是以不同的方式实现的）。同样，LR的替换映射可以由程序员定义。作为经验法则，给定一个定义函数f，映射包含f的参数，这些参数在所有定义3f的规则中都是不可变的子项（例如，µ（drop）=1（1）降为（1）。 对这些子项的评估旨在在评估其他子项之前进行。然后，如果函数调用的（其他）操作根的子项都对应于定义被调用函数的重写规则R左侧的不可变项，并且从该位置到规则根的路径中出现的符号在R中重合，则对它们进行评估。此外，要求术语的已求值部分与规则左侧的相应部分匹配。这样评估的子项在[8，15]的术语中被称为因此，这样的子项的激活和最后，我们注意到，具有正则映射的LR与CSR一致[15]。具体地，t=（drop（n+m）（append p q））的求值通过求值（n+m）来进行。如果（n+m）不等于0，则LR激活t在位置2的子项注意，不需要对结果项的第二个参数进行求值，即（drop 0（append p q））因此，LR比CSR执行得更好，因为它会查看候选参数的某些上下文[3]清晰度信息也可以用于定义替换地图。安东尼和卢卡斯47进行评估。但请注意，最近激活的子项的活跃部分可以在整个项中自动变为活跃部分。因此，即使没有任何规则的要求，也可以自由地评估它们。因此，懒惰的重写毕竟不是那么懒惰。按需重写策略[14]按需重写（ODR）对签名的每个符号使用两个替换映射：µ和µD地图µ与CSR中相同。mapµD放宽了禁止对不在mapµ中的参数求值的要求。对于这些参数，根据规则的左侧，允许“按需”进行评估地图的定义是程序员的责任。作为经验法则，选择LR的第一个替换映射，以及第二个替换映射的规范替换映射将确保为基于左线性构造器的重写系统计算头范式[14]，并与LR进行更准确的比较。需求驱动的重写和缩小[1，2，11，16]文献中出现了几种战略，统称为需求驱动。 这些策略的一个共同特点是使用所需位置集而不是替换地图。一组必需的位置定义了函数（调用）的哪些参数要求值。原则上，这类似于替换映射，但同一函数的不同出现可能具有不同的所需位置集合。从直觉上讲，函数调用的参数可能会或可能不会根据其他参数的值进行评估。这种策略的一个变体[2]，在逻辑编程中为非确定性函数计算提出，使用定义树，因此仅限于基于构造器的重写系统。[11]将这种策略推广到缩小计算，但将其限制在条件弱正交重写系统中。例如，调用（1）中定义的函数drop的第二个参数仅在第一个参数是Succ-rooted时才被计算。在第一个参数为0的调用中不计算它。在某些情况下，DDR比CSR、ODR和LR更复杂，并且不会给程序员带来定义替换映射的负担。[2]应用于由（2）中定义的操作insert根的项，非确定性地应用第一个规则而不评估任何参数，或者评估第二个参数，如果它不是构造函数根的，则尝试应用第二个规则。需要重写和缩小[4，7，10]（强烈）需要重写（NR）同时查看定义操作的所有规则的左侧。不严格地说，函数调用的参数只有在所有可以应用于该调用的规则都要求它时才被计算。换句话说，有些论点安东尼和卢卡斯48受欢迎程度高于其他人，并且策略根据该受欢迎程度顺序来评估位置。在强序列系统中，求值的顺序由匹配自动机确定[10]。在归纳顺序中，评估的顺序由定义树确定[3]。此策略将按需调用计算的行为扩展到收缩。[4]将此策略扩展到重写具有特定类型重叠规则的系统。所有这些策略都是相当准确的，因为它们只计算必要的步骤-[4]模非确定性选择。这种准确性的缺点是这些策略适用于的重写系统的种类的限制。这些策略已被证明是完整的和最佳的域，他们打算。例如，这些策略都不适用于（2）中定义的操作插入应用于在（1）中定义的操作drop，这些策略首先评估第一个参数，然后评估第二个参数，如果第一个参数是Succ-rooted。有趣的是，这些策略并没有明确定义需求或替代地图，但与之前的策略密切相关（详细比较见[12]）。人们可以为每个定义操作的规则获得一个单独的规范映射。CSR获得操作的规范映射作为所有这些单独映射的并集。NR将所需位置作为适用于函数调用的所有单个映射的交集。[19]WNR类似于NR，同时查看单个操作的所有规则。通过继续为NR引入的类比，WNR类似于CSR，获得操作的规范映射作为每个规则的所有个体映射的并集。然而，与CSR相反，WNR评估所有可能适用于函数调用的规则的所有要求位置。WNR是一种相对简单的重写策略[19]。对于窄化，情况变得复杂得多，因为不同位置处的步骤可能需要不兼容的替换，因此不能像重写那样并行执行。在[6]中提出了保守扩展[19]的缩小策略。对于基于构造函数的弱正交重写系统，这两种策略都是完备的。然而，对于后者，前者的最优性结果尚未得到完全证明。这些策略适用于弱正交重写系统。在这些术语中，存在没有必要位置的术语。当某些重写规则重叠时，可能会发生这种情况，如以下众所周知的parallel-or操作：或True- = True或-True = True或False False = False（三）安东尼和卢卡斯49为了完整起见，我们还提到了一些重要的策略，这些策略不是基于需求的。并行最外层和最外层公平策略[17]仅针对重写进行了研究。他们从根本上不同于以前的人，因为他们不看具体的重写规则。相反，他们看的是最外层的赎回权。它们对于WNR完备的同一类是完备的。从简单的例子中很容易看出，这些策略可能比WNR评估更多的赎回。另一种不直接基于需求的策略在[5]中定义。这个策略很重要，因为它是第一个完整的收缩策略，适用于整个基于条件构造函数的重写系统。该策略通过允许应用[4]的转换来隐式定义。3结论本文回顾了一些基本的重写和缩小策略。所有的策略都是从需求的角度提出的，这是一种新的和不寻常的呈现。这种观点更容易理解一个策略执行另一个策略不执行的步骤的条件。我们的工作仍在进行中。因此，这一结论与其说是所取得成果的尾声，不如说是未来工作的序幕。我们计划精确地制定一个概念，对于定义的操作，重写规则要求的参数。上下文敏感重写、惰性重写和按需重写的规范替换映射都可以使用这个概念来表达。在很大程度上，更高级的策略，如需求驱动，需要和弱需要重写也可以用这个概念来表达这些考虑表明重写规则所要求的参数的概念对于策略的研究来说是原子的和基本的。通过比较不同的策略如何使用这一基本概念，我们期望对策略的行为以及相关策略之间的差异和相似性有新的见解。引用[1] M. 阿尔蓬特湾Falaschi，P.Julian和G.维达尔惰性函数逻辑程序的专门化。在PEPM'97的Proc.ACM，1997年。[2] S.安托伊 逻辑程序设计中的非确定性和惰性求值。在T. P. Clement和K.- K. Lau，编辑，逻辑编程综合和转换（LOPSTR史普林格出版社安东尼和卢卡斯50[3] S. 安 托 伊 定 义 树 在 第 四 届 国 际 会 议 上 ， Conf. on Algebrahem and LogicProgramming，pages 143-157. Springer LNCS 632，1992年。[4] S. 安托伊最佳非确定性函数逻辑计算。第六届国际代数和逻辑编程会议（ALPSpringer LNCS 1298，1997年。[5] S. 安托伊基于构造函数的条件收缩。在Proc. of the 3rd InternationalConference on Principles and Practice of Declarative Programming（PPDP2001年ACM。[6] S.安图瓦河Echahed和M.哈纳斯函数逻辑语言的并行求值策略。第14届国际逻辑编程会议（ICLPMIT Press，1997.[7] S. 安图瓦河Echahed和M.哈纳斯一个必要的缩小战略。Journal of the ACM，47（4）：776-822，July 2000.[8] W. Fokkink，J. Kamperman，and P. Walters.懒惰地重写急切的机器。ACM Transactions on Programming Languages and Systems，22（1）：45[9] M.Hanus （ ed. ） .Curry ： 一 种 集 成 函 数 逻 辑 语 言 。 见http://www.informatik.uni-kiel.de/~curry，2000年。[10] G.Huet和J. - J.我也是。 正交项重写系统中的计算。在J. - L. Lassez和G.Plotkin，编辑，计算逻辑：纪念Alan Robinson的论文，第395-443页。麻省理工学院出版社，马萨诸塞州剑桥，1991年。[11] R. L oogen，F. L'opezFraguas和M. R odr'ıguezArtalejo.一个需求驱动的懒惰 缩 小 计 算 策 略 。 在 Proc.5th International Symposium on ProgrammingLanguage Implementation and Logic Programming （ PLILPSpringer LNCS714，1993年。[12] S. 卢卡斯上下文敏感的重写策略。信息与计算出现。[13] S. 卢卡斯函数和函数逻辑程序中的上下文相关计算Journal of Functional andLogic Programming，1998（1）：1[14] S.卢卡斯按需重写的终止和OBJ程序的终止。 第三届原则与实践国际会议论文集，PPDP'01，第82-93页。ACM Press，2001.[15] S.卢卡斯惰性重写和上下文敏感重写。In M. Hanus，编辑，电子笔记在理论计 算 机 科 学 ， 第 64 卷 。 Elsevier Science Publishers ， 2002. 见http://www.elsevier.nl/locate/entcs/volume64.html。[16] J.J.Moreno-Navarro和M.R odr'ıguez-Artalejo.用函数和谓词进行逻辑编程Journal of Logic Programming，12：191安东尼和卢卡斯51[17] M. J·奥唐纳用方程描述的系统中的计算。Springer LNCS 58，1977年。[18] S. 佩顿·琼斯和J.Hughes（ed.）. Haskell 98：一种非严格的纯函数式语言。可在www.example.com上获得http://www.haskell.org/onlinereport/。[19] R. C. 我和塞卡诉拉马克里什南 方程式逻辑中的程序设计：超越强顺序性。信息与计算，104（1）：78
我的内容管理
展开
