多元控制部分评价: 灵活的逻辑程序专用化方法，搜索空间修剪技术的研究

理论计算机科学电子笔记177（2007）137-151www.elsevier.com/locate/entcs多元控制部分评价克劳迪奥·奥乔·阿和格扎维埃·普埃布拉马德里技术大学计算机科学学院西班牙马德里{claudio，german}@ fi.upm.es摘要多元控制部分求值（PCPE）是最近提出的一种灵活的逻辑程序专用化方法。 它考虑了全局控制和局部控制规则的全部内容，而不是单一的、预定的组合。因此，可以将不同的全局和局部控制规则分配给不同的呼叫模式，从而获得混合的结果，在某种意义上，它们不能像传统的部分评估那样使用控制规则的单个组合来获得。PCPE可以实现为基于搜索的算法，产生候选专用程序集（其中许多是混合的），而不是单个程序。这些程序中的每一个的质量通过使用不同的适应性函数来评估，该函数可以是资源感知的，考虑多个因素，例如运行时间、内存消耗和专用程序的代码大小等。虽然PCPE是一种有吸引力的方法，但当作为基于搜索的算法实现时，它会导致搜索空间的固有爆炸。 因此，在本发明中，为了在实践中使用，并处理现实的程序，我们必须能够修剪它的搜索空间，而不丢失感兴趣的解决方案。这项工作的贡献是双重的。一方面，我们进行了实验研究的异质性的解决方案，通过基于搜索的PCPE，显示的解决方案提供的行为非常不同，当使用拟合函数进行比较。请注意，这一点很重要，因为否则产生大量候选专门化的成本将不会被正义化。这项工作的第二个贡献是引入了一种技术，用于修剪这种方法的搜索空间。 所提出的技术很容易应用，并产生了相当大的减少搜索空间的大小，允许PCPE处理合理数量的基准程序。虽然修剪是以启发式的方式进行的，但我们的实验结果表明，我们的启发式在实践中表现良好，因为使用修剪获得的解决方案的拟合值与未应用修剪时获得的解决方案关键词：部分评估，控制策略，资源感知，程序优化，剪枝技术1介绍部分评估的目的是使一个项目的专业化。其输入的一部分，称为静态数据[11]。 生成的代码的质量通过部分评估，很大程度上取决于所使用的控制策略。不幸的是，存在复杂的控制规则，表现（几乎）最佳的所有程序仍然是远离现实。多控制部分评估[15]（PCPE）试图通过采用一组全局和局部控制来解决这个问题。1571-0661 © 2007 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2007.01.008138C. 奥乔亚湾Puebla/Electronic Notes in Theoretical Computer Science 177（2007）137规则而不是预定的组合（如在传统的部分评估算法中所做的）。这允许对不同的调用模式（原子）使用不同的全局和局部控制规则。因此，PCPE可以产生专门的程序，这是无法实现的传统的部分评估使用任何考虑的局部和全局控制规则的隔离。在[15]中，介绍了实现PCPE的两种算法。其中之一使用一个称为挑选的函数来决定先验的（全局和局部）控制策略将被应用于每个原子。第二种方法将一些预先选择的控制规则应用于每个原子，生成几个候选专业化，并通过使用拟合函数经验比较最终配置（候选专业化）来确定后验哪个专业化是最好的，可能会考虑到诸如专业化程序的大小以及这种专业化程序的时间和内存效率等因素。由于选择一个好的Pick函数可能是一项非常困难的任务，并且需要对PCPE的概念进行证明，我们实现了第二个算法（将第一个算法留给将来的工作），尽管该算法在搜索空间的大小方面效率较低。在PCPE的主要优点中，我们可以提到：它可以获得比传统PE更好的解决方案：在[15]中，初步实验表明，对于许多不同的资源感知函数，PCPE产生的混合解决方案比传统PE可实现的任何解决方案都具有更好的适应性值。混合的解决方案是无法实现的传统的部分评估，因为不同的全局和局部控制规则适用于不同的呼叫模式。它是一种资源感知的方法：在传统的PE中，现有的控制规则集中在时间效率，试图减少在剩余程序中执行的解析步骤其他因素，如编译的专用程序的大小，以及运行剩余程序所需的内存通常被忽略-一些相关的例外是[4]，[3]-。除了潜在地生成更大的程序之外，众所周知，部分评估可以由于诸如子句索引、缓存大小等较低级别的问题而减慢程序。另一方面，PCPE利用资源感知适应性函数从一组候选解决方案中选择最佳解决方案它是更用户友好的：现有的部分求值器通常提供几个全局和局部控制策略，以及许多其他参数（全局树，计算规则等）。直接检验所得溶液的质量。对于新手用户来说，很难找到正确的参数组合以达到预期的结果（减少编译代码的大小，减少执行时间等）。即使对于有经验的用户，预测部分评估的行为也是相当困难的，特别是在空间效率（剩余程序的大小）方面。PCPE允许用户同时experi- ment与不同的参数组合，以实现具有所需特性的专业程序。它执行在线部分评估：与其他方法（例如，C. 奥乔亚湾Puebla/Electronic Notes in Theoretical Computer Science 177（2007）137139[3]），PCPE执行在线部分评估，因此它可以利用大量的工作可用于逻辑程序的在线部分评估不幸的是，PCPE不是万能药，它有许多缺点。这种方法的主要缺点是，当实现为基于搜索的算法时，其搜索空间会出现固有的指数爆破，因为给定配置，后继的数量可以与所考虑的局部和全局控制规则的组合的数量一样高。作为一个直接的结果，PCPE的专业化时间高于其PE同行。在第一次熟悉了多元控制部分求值的基本思想之后，我们的脑海中可能会立即出现两个问题(i) PCPE是否提供广泛的解决方案？也就是说，所获得的解的集合是否足够异构以使我们有一个广泛的候选解集合可供选择？(ii) PCPE在实践中是否可行？也就是说， 因为有一个指数爆炸，搜索空间，是否有可能执行一些修剪，以处理现实的程序，而不会失去有趣的解决方案？在这项工作中，我们解决了这两个问题，提供了一些实验结果，以帮助我们证明我们的指控。2背景我们假设对逻辑编程的术语有一些基本的了解详情参见示例[12]简单地说，原子A是形式p（t1，.，tn），其中p/n，其中n≥ 0，是谓词符号，并且t1，.，n是项。应用于原子A的函数pred，即， pred（A），返回A的谓词符号p/n。一个子句的形式是H←B，其中它的头部H是一个原子，它的主体B是一个原子的连接。一个定义的程序是一组有限的子句。一个目标（或查询）是一个原子的连接。两个项t和tJ是变体，记为t<$tJ，如果存在重命名ρ使得tρ = tJ。我们用{X1<$→t1，.， Xn <$→tn}，其中σ（ Xi ）=ti，i=1， . . ， n（w it h Xif=Xjifi=fj）和dσ（X）=X，其中ti是项。一个简单表达式的有限集合S的单位元是一个代换θ，如果Sθ是一个单例。一个单位元θ称为S的最一般单位元（mgu），如果对于S的每个单位元σ，存在一个替换γ使得σ=θγ。2.1 LP中的部分求值基础LP的部分求值传统上是根据SLD语义来给出的。我们简要回顾一下这里的术语。计算规则的概念用于选择目标中的原子进行计算。定义2.1计算规则是从目标到原子的函数R设G是一个形式为←A1，...，AR，.，Ak，k≥ 1。如果R（G）=AR，我们说AR是140C. 奥乔亚湾Puebla/Electronic Notes in Theoretical Computer Science 177（2007）137G中的选定原子。定义程序的操作语义是基于派生的[12]。定义2.2 [推导步骤]设G为←A1，.，AR，.，Ak.设R是一个计算规则，R（G）=AR.设C = H←B1，.，B可以是P中的一个重命名的分隔子句。则如果以下条件成立，则GJ是通过R从G和C导出的θ = mgu（AR，H）GJ是目标←θ（A1，.，AR−1，B1，.、Bm、AR+1、...、Ak）按照惯例，给定一个程序P和一个目标G，P∈ {G}的SLD推导由一个可能无限的序列G=G0，G1，G2，. 目标序列C1，C2，. P的适当重命名的分离子句的集合，以及一个序列θ1，θ2，. 使得每个Gi+1都是使用θ i +1从Gi和Ci+1导出的。当AR与P中的几个子句统一时，推导步骤可以是非确定性的，从而为给定目标产生几个可能的SLD推导。这样的SLD推导可以被组织在SLD树中。有限导子G = G0，G1，G2，.，如果Gn为空，则称Gn成功。在这种情况下θ = θ1θ2...θn称为目标G的计算答案。 如果不可能用Gn执行推导步骤，则这样的推导被称为失败。在部分求值中，SLD语义被扩展，以便也允许不完全导子，它们是形式G = G0，G1，G2，.的有限导子。，Gn，并且其中在Gn中没有原子被选择用于进一步解析。这是必要的，以避免专门化过程的（局部）不终止。另外，代入θ = θ1θ2...θn称为目标G的计算答案替换。不完整的SLD树可能包含不完整的派生。为了计算部分求值（PE）[11]，给定一个输入程序和一组原子（目标），第一步是应用展开规则为这些原子计算有限个不完整的SLD树。然后，从SLD树中系统地提取一组结果或剩余规则。定义2.3 [展开规则]给定一个原子A，展开规则计算一组有限的SLD导子D1，.，Dn（即，可能不完整的SLD树）的形式Di= A，.，Gi，其中i = 1，.，n，其相关结式为θi（A）←Gi。因此，该步骤返回结果集，即，一个程序，与这些树的根到叶的派生相关联。计算的SLD树的结果集称为初始目标（查询）的部分评估。对一组目标的部分评价被定义为对该组中每个目标的部分评价的并集。我们参考[8]了解详细信息。为了确保PE算法的局部终止，同时产生有用的专门化，展开规则必须包含一些非平凡的机制，以停止SLD树的构造。如今，良基序（wfo）[2，13]和良拟序（wqo）[16，9]被广泛地用于C. 奥乔亚湾Puebla/Electronic Notes in Theoretical Computer Science 177（2007）137141我我我我在线部分评估技术（参见，例如，[6、10、16]）。除了局部终止之外，还应用抽象运算符来将结式右侧的原子适当地添加到要部分评估的原子集合这个抽象操作符执行全局控制，并负责保证生成的原子数量保持有限。这是通过用更一般的原子代替原子来实现的，即，通过失去精确度来保证终止。抽象阶段产生一组新的原子，其中一些可能又需要进一步评估，因此，在引入新原子的3多元控制部分评价传统的逻辑程序部分求值算法是参数化的. 全局控制和局部控制规则1. 在这些算法中，一旦选择了专门化策略，就将其应用于剩余程序中的所有调用模式。然而，众所周知，存在几种控制策略，它们在不同的情况下可能会感兴趣。找到一种在所有环境下都表现良好的专业化战略确实是一项相当困难的努力。因此，至少在原则上，人们可能对将不同的专门化策略应用于不同的原子（调用模式）感兴趣，而不是考虑单一的专门化策略不幸的是，这是现有的算法PE不迎合。多元控制部分评估（PCPE）[15]通过允许使用一组专业化策略而不是预定的策略来填补这一空白。3.1一种基于搜索的多元控制部分求值算法算法1示出了基于搜索的多控制部分评估算法。在该算法中，配置Confi是一对{Si，Hi}。Si是尚未由算法处理的原子的集合，Hi是已经由算法处理的原子的集合事实上，在Hi中，我们不仅存储原子Ai，而且还存储对这些原子应用全局控制的结果AJ和展开规则Unfold，用于展开Ai，即，H i的成员是形式为Ai，AJ，Unfold的元组。我们存储Unfold是为了在代码生成阶段使用这样的展开规则。算法的正确性要求每个AJ是Ai的抽象，即，Ai=AJθ。算法1采用两个辅助数据结构。一个是Confs，它包含了目前正在探索的配置。另一个是Sols，它存储算法当前找到的解决方案集。众所周知，对Confs使用不同的数据结构提供了对搜索空间的不同遍历。在我们在CiaoPP[7]中实现该算法时，我们使用了堆栈和队列，以深度优先和breadth-first fashion，分别。给定一组描述对程序的潜在查询的原子S，初始配置的形式为：在算法的每次迭代中，从现在开始，我们将全局和局部控制规则的任何组合称为专门化策略。142C. 奥乔亚湾Puebla/Electronic Notes in Theoretical Computer Science 177（2007）137我我一个j从Confs弹出一个配置<$Si，Hi<$（第6行），并从Si中选择一个原子Ai（第7行）。然后，分别应用全局控制（Abstract∈ G）和局部控制（Unfold∈ U）规则的几种组合（第11行和第12行）。每个应用程序使用相应的展开规则Unfold为AJ构建SLD树，A j是Abstract确定的Ai的推广。一旦计算了SLD树τi剩余代码中的原子J 由函数leaves收集（第14行）。 叶中的原子（τi），不是在算法的先前迭代中处理的原子的变体，被添加到要考虑的原子集合（Si+1）并推送到Confs上。 我们使用B→A表示B和A是变体，即，它们是相等的模变量重命名。 当要处理的配置堆栈为空，即所有最终配置都已达到。专业课程核心-响应<$A，AJ，展开<$∈Hnresultants（AJ，Unfold），其中函数resultants是参数w.r.t. 展开规则。注意，在这个算法中，一旦一个原子Ai被抽象成AJ，我我将被生成，它将不会被进一步抽象，无论其他原子在算法的稍后迭代中被处理。因此，不能保证为其生成代码的原子集是独立的。当两个原子没有共同实例时，它们然而，H中的对唯一地确定在每个程序点使用的版本。由于代码生成为H中的每个条目生成一个新的谓词名称，因此独立性得到保证，因此专用程序不会产生比原始程序更多的解决方案如[15]中所述，可以考虑类似的算法，该算法先验地决定要应用于每个原子的控制策略。该算法将更类似于传统的PE算法，对不同的原子采用可能不同的控制规则不幸的是，不清楚如何做出该决定，因此算法1生成几个候选部分评估，然后决定一个正的部分评估。teriori哪个专门的程序来使用。 显然，生成所有可能的候选人专门的程序比只计算一个程序更昂贵。然而，选择最佳候选人的后验允许作出更明智的决定比选择它的先验。3.2搜索空间的指数爆破鉴于算法1允许不同的专业化策略组合，给定一个配置，有几个后继配置。 这可以解释为，给定G ={A1，. ，Aj}，并且U ={U1，. ，Ui}，存在一组trans-i-i形成算子TA1，.、TA1、.，T. 在最坏的情况下，U1UiUi展开规则U ={展开1，.，展开i}，以及一组抽象函数G={摘要1，. ，摘要j}，存在i × j个可能的组合。如已经如前所述，这表示搜索空间大小的固有指数爆炸，并且它使得算法对于处理现实程序不切实际。当然，为了处理这个问题，可以对上面所示的基本算法进行若干优化第一个明显的优化是消除搜索树中相同节点的后代的等价配置一C. 奥乔亚湾Puebla/Electronic Notes in Theoretical Computer Science 177（2007）137143我我我算法1基于搜索的多元控制部分求值算法输入：程序P输入：感兴趣的原子集合S输入：展开规则集U输入：泛化函数G输出：部分求值集一曰： H0=0第二章： S0=S第三章： create（Confs）;Confs=push（confs0，confs0，Confs 0）第四章： Sols=05：重复6：Si，Hi=pop（Confs）7：Ai=Select（Si）8：候选人={摘要，展开|抽象∈ G，展开∈ U}9：重复10：候选人=候选人− {Abstract，Unfold}11：AJ=抽象（Hi，Ai）12：τi=展开（P，AJ）13：Hi+1=Hi<${<$Ai，AJ，展开<$}14：Si+1=（Si− {Ai}）<${A∈leaves（τi）|Hi+1. B/A}15：如果Si+1= 0，则16：Sols=Sols{Hi+1}17：其他18：push（push，Hi+1，Confs）19：如果结束20：直到候选人=10021：i=i+1二十二： 直到空堆栈（Confs）也就是说，通常情况下，给定一个配置Conf，存在多个TAAJJj A AJU和TUJ 其中（A，U）/=（A，U）s. t. TU（Conf）=TUJ（Conf）。 这种优化是易于实现，执行成本不高，并显著减少了搜索空间。然而，即使进行了这种优化，一个简单的实验也显示了这个问题的严重性。让我们考虑清单1（a）中的程序，它实现了一个简单的反向算法。在这个实验中，让我们选择全局控制规则集G={dynamic，hom emb}。homemb全局控制规则基于同胚嵌入[8，9]，当原子在全局控制级别同胚嵌入任何先前访问的原子时，将原子标记为潜在危险（因此是广义的）动态是最抽象的全局控制规则，它抽象出原子的所有参数的值，并用不同的变量替换它们。 此外，让我们选择局部控制规则集U={one step，df hom emb as}。一步规则是最简单的展开规则，144C. 奥乔亚湾Puebla/Electronic Notes in Theoretical Computer Science 177（2007）137：-module（_，[rev/2]，[]）。：-entryrev（[_，_|L]、R）。rev（[]，[]）。转速（[H| L]，R）：-rev（L，Tmp），app（Tmp，[H]，R）。ap p（[]，L，L）.app（[X|Xs]， Y，[X|Zs]）：-ap（Xs， Y，Zs）.（一）输入查询#解决方案转速（左、右）6rev（|L]、R）48rev（[，|L]、R）117rev（[，，|L]、R）186rev（[，|L]、R）255rev（[1 |L]、R）129rev（[1，2 |L]、R）480（b）第（1）款图1.一、nrev示例和PCPE生成的解的个数总是对任何原子执行一个展开步骤最后，df hom emb as是一种基于同胚嵌入的展开规则。关于这个展开规则的更多细节可以在[14]中找到。它可以安全地处理外部谓词，只要展开是安全的（参见[1]）和局部的（参见[14]），它就可以执行非最左边的展开。在CiaoPP[7]中，初始查询的描述（即，算法1中的感兴趣的原子集合S）通过考虑由模块导出的谓词集合来获得，在这种情况下是rev/2，可能通过条目声明来限定例如，清单1（a）中的条目声明用于专门化至少包含两个元素的列表的图1的表（b）显示了算法1（消除搜索树中的等价配置）为几个条目声明生成的候选解决方案的数量。如在表中可以观察到的，随着作为条目提供的列表的长度增长，计算的候选解的数量快速增长。此外，如果输入列表的元素是静态的，那么候选数的增长甚至更快，如表1中的最后两行所示，其中我们提供了列表的第一个元素。从这个小例子中，很明显，为了能够处理现实的Prolog程序，必须减少搜索空间。在第5节中，我们提出了一种这样做的技术4PCPE混合解决方案的异质性如前所述，算法1产生一组候选解。其中，它们中的一些是纯的，在某种意义上说，它们可以通过传统的PE（即，它们对剩余程序中的所有原子应用相同的控制策略），其余的是混合的，在这个意义上，它们对不同的原子应用不同的专门化策略。在本节中，我们试图确定PCPE获得的不同解的拟合值的异质性4.1选择适当的全局和局部控制规则集问题的解决方案得到的PCPE是异质w.r.t.它们的适合性值在很大程度上取决于所使用的专门化策略的特定选择，以及控制规则集G和U的多样性。我们可以预期，通过选择足够不同的控制规则，C. 奥乔亚湾Puebla/Electronic Notes in Theoretical Computer Science 177（2007）137145解决方案也将非常不同，反之亦然。为了看到这一点，考虑一下我们选择U={det，lookahead}，其中det和lookahead都是完全确定的[6，5]-即，它们选择与单个子句头匹配的原子，不同之处在于lookahead使用有限数量的计算步骤的考虑到这两个规则都是基于确定性展开的，并且这被认为是一种非常保守的技术，这种局部控制规则的特定选择很可能不会有助于找到异构解决方案。一个更好的主意是选择一个保守的展开规则，另一个是激进的。 主动局部控制规则的示例将是执行非最左侧展开的规则。在选择全局控制规则时可以进行相同的推理，我们可以选择一个非常精确的规则-同时保证终止-和一个非常不精确的全局控制规则。4.2PCPE解一旦我们为PCPE选择了一组合适的控制规则，我们需要确定我们获得的解决方案的适合性是否是异质的。为此，我们在一组基准和不同的拟合函数上进行了一些实验，以收集统计事实，如标准差和直径，可以帮助我们确定所获得的解决方案有多不同在我们的实验中，如第3节所述，我们使用了一组全局控制规则G={dynamic，homemb}和一组局部控制规则U={one step，df hom emb as}。此外，我们还使用了在[15]中已经引入的不同拟合函数。由于空间的原因，我们将展示使用以下拟合函数时获得的一些结果speedup根据程序的时间效率比较程序，测量运行时的加速比w.r.t.原始程序。当使用这个适应性函数时，用户需要提供一组运行时查询，以便对程序的执行进行计时。这样的查询应该代表程序2的实际执行。该拟合函数计算为：加速比=Torig/Tspec，其中Tspec是专用程序运行给定运行时查询所花费的执行时间，Torig是原始程序所花费的时间reduction根据程序的空间效率来比较程序，衡量编译后字节码大小的减少。原始程序。它被计算为约简=（Sorig-Sempty）/（Sspec-Sempty），其中Sspec是专用程序的编译字节码的大小，Sorig是原始程序的编译字节码的大小，并且Sempty是空程序的编译字节码的大小。在表1中，我们可以观察到，对于一些基准测试，当使用加速[15]作为拟合函数时收集的统计数据。如前所述，数字[2]虽然寻找代表性的运行时查询本身就是一个有趣的研究课题，但自动化这一过程超出了本文的范围146C. 奥乔亚湾Puebla/Electronic Notes in Theoretical Computer Science 177（2007）137基准输入查询加速比Vers健身是说标准差直径实施例PCPEmain（，，2，）271.560.870.210.99置换permute（[1，2，3，4，5，6]，L）701.311.150.481.16尼雷夫rev（[，|L]、R）2551.090.660.150.51顾问今天要做什么（，，）141.681.310.670.97相对relative（john，X）6118.013.454.8416.37苏普利ssupply（，，）315.151.841.824.72转置transpose（[，，]，，]，）1542.620.870.302.13整体87.44.491.451.213.83表1不同基准上的PCPE统计（加速）获得的版本的数量与几个因素密切相关，例如所使用的控制规则的数量和种类，以及用于专门化每个程序的初始输入查询对于这个特定的实验，PCPE为每个基准生成了平均87个候选解决方案。在大多数情况下，我们可以观察到最佳解的拟合度和平均拟合度都超过1，这意味着在比较所获得的解时实现了加速。原始程序。在某些情况下，平均加速比低于1，这表明许多解决方案都很糟糕，并且相对于相对速度会变慢。原始程序。让我们以转置为例。在这个特定的基准测试中，我们可以看到154个最终解决方案中的大多数都比原始程序慢，这意味着很容易用不同的控制策略来专门化这个程序，并获得比原始程序运行更慢的解决方案。然而，请注意，PCPE获得的最佳解决方案比原始程序快2.62。为了回答我们最初的问题，即，无论PCPE是否提供广泛的解决方案，我们感兴趣的列是St Dev和Diameter。St Dev代表标准差，并测量数据集中的值分布情况。直径测量（任何）最佳解决方案与（任何）最差解决方案相比的拟合度差异。 注意PCPE找到的许多解可以具有相同的拟合值。在St Dev中接近0的值表示大多数解是相似的，并且它们的拟合度值与平均拟合度值相似然而，平均St Dev为1.21，表明一般情况下解决方案是分散的，即，它们在相互比较时是不同的，即使向PCPE算法提供了非常少的静态信息（如表1的输入查询列所示）。当我们用图形的方式来观察不同解的适合性时，图2我们可以观察到，对于清单1（a）中定义的nrev基准，所有解的拟合度如何分布在平均值上 我们之所以选择这个基准，是因为它具有最低的标准差值，并且获得的版本数最多。此外，我们可以看到，许多解决方案共享相同的拟合值，并且在某种程度上它们被分组在一起，这表明应该可以找到将这些解决方案折叠成一个的方法，以这种方式修剪搜索空间。 关于直径列，我们可以观察到平均直径为3.83，这表明C. 奥乔亚湾Puebla/Electronic Notes in Theoretical Computer Science 177（2007）137147最坏和最好的解决方案。1.110.90.80.70.60.50.40 50 100 150 200 250 300图二. PCPE解决方案nrev这些初步结果是令人鼓舞的，表明PCPE是能够获得几个异构的解决方案，其中大部分是无法实现的传统的部分评估。对于其他拟合函数也得到了类似的结果（由于空间不足，此处未显示虽然很明显，我们需要修剪搜索空间，以使这种方法实用，我们应该小心，为了不修剪好的解决方案。5修剪搜索空间：SPRS启发式尽管有可能消除冗余的配置和没有希望的分支，但在实践中值得探索使用具有更多限制能力的多控制部分演绎，以减少探索搜索空间的成本。例如，我们可以将自己限制在这样的配置中，即总是对对应于同一谓词的所有原子使用相同的专门化策略，而不是允许配置中不同原子的专门化策略的所有可能组合。这种限制通常会显著减少我们算法的分支因子，因为一旦我们之前考虑了任何配置中相同谓词的原子，即搜索空间中当前谓词的祖先，则对原子Ai的处理将变得确定性必须使用与以前完全相同的专门化策略。 我们称这种方法为SPSR，代表相同的谓词，相同的规则。我们将把满足这一限制的配置称为一致的，与那些没有的不一致。虽然这种简化乍一看可能看起来过于限制，但实际上通常存在一种专门化策略，该策略对于对应于同一谓词的所有原子都表现良好，溶液0.64148C. 奥乔亚湾Puebla/Electronic Notes in Theoretical Computer Science 177（2007）137基准Heur版本健身是说标准差直径PCPECSPE实施例PCPEorig271.56HD1.370.870.210.99SPSR271.600.860.231.11置换orig701.31HD1.060.910.481.16SPSR91.291.021.011.01尼雷夫orig2551.03HD1.030.640.150.51SPSR91.060.710.190.55顾问orig141.68HD1.551.210.670.97SPSR81.661.490.861.06相对orig6118.01HD15.303.454.8416.37SPSR1117.968.009.3616.95苏普利orig315.15HD5.151.521.824.72SPSR315.131.531.824.51转置orig1542.62HD2.600.870.302.13SPSR62.541.080.571.60整体orig87.44.494.011.351.213.83SPSR14.44.442.092.013.82表2搜索-修剪替代方案的比较（加速）在给定的程序中。我们将以这样一种方式修改算法1，即只进一步处理一致的配置为此，我们需要为每个配置中的每个原子存储用于泛化这样的原子的全局控制规则。我们现在提供一个关于一致性配置的正式定义。SPSR启发式算法定义5.1[相容配置]给定一个配置Conf=S，H<$，我们说Conf是相容的i <$S<$A1，AJ，G1，U1<$∈H，<$A2，AJ，G2，U2<$∈1 2H，pred（A1）=pred（A2）<$（G1=G2<$U1=U2）请注意，一致配置的定义可以应用于中间配置（而不仅仅是最终配置）。因此，如果给定的配置Conf不一致，则它将被修剪，即，它不会在Confs上被推。 通过这样做，我们不仅修剪了这个配置，而且修剪了所有后继配置这意味着早期修剪将显著减少搜索空间。6实验结果由于SPSR启发式以盲方式修剪搜索空间，即，在不对被修剪的候选进行任何评估的情况下，有可能修剪最优解。为了确定是否是这种情况，我们扩展了第二节中所示的实验。4.将SPSR启发式应用于实例程序时得到的结果相加。在表2中，我们显示了通过PCPE获得的版本的数量，通过PCPE获得的最优解和通过C. 奥乔亚湾Puebla/Electronic Notes in Theoretical Computer Science 177（2007）137149基准Heur版本溶胶健身是说标准差直径PCPECSPE实施例PCPEorig2711.22HD1.150.820.190.82SPSR2711.220.820.190.82置换orig7061.15做0.980.610.271.15SPSR911.150.630.341.15尼雷夫orig25530.98做0.980.320.150.79SPSR910.980.550.250.71顾问orig1411.69HD1.681.030.341.41SPSR811.690.940.381.41相对orig6121.17做0.980.670.251.04SPSR1111.170.800.281.04苏普利orig31111.26HD11.261.611.7910.32SPSR31111.261.611.7910.32转置orig15450.98做0.980.390.190.75SPSR610.980.630.260.70整体orig87.42.712.632.570.770.452.32SPSR14.41.002.630.850.492.30表3搜索-修剪备选方案的比较（约简）传统的PE（连同用于获得这样的值3的控制策略CS）、所有解的平均值、它们的标准偏差和它们的直径，当使用加速比作为拟合函数时。 我们比较在所有情况下，由原来的PCPE方法（行orig下列Heur）与PCPE获得的值修剪时，其搜索空间的SPSR算法（行spsr）的装置。如表中所示，当应用SPSR时，搜索空间显著减小，并且平均版本数从87个候选解决方案减少到仅14个。然而，有一些基准没有实现搜索空间的修剪，例如pcpe和ssupply的情况。这是因为这些程序在其候选特化中包含很少的原子，并且所有这些配置都是一致的，满足SPSR限制。在我们的实验中，当修剪完成时，St Dev增长，表明我们正在修剪共享相同拟合值的解决方案通过查看拟合值，我们可以假设最佳解决方案被保留，尽管执行了盲修剪（orig和spsr的拟合值之间的轻微差异可能是由于测量时间时的噪声）。请注意，在大多数情况下，PCPE优于传统PE。有趣的是，很明显，对于这些基准，因为PE是HD。我们还可以观察到，当修剪是这可能表明坏的解决方案被修剪掉了。在表3中，我们显示了与上述相同的信息，但对于约简拟合函数。我们还添加了一个额外的列Sols，显示PCPE找到的最佳解决方案的数量（请注意，当测量时间效率时，该列没有任何意义，因为该测量受到噪声的影响通过3我们 使用的 以下符号 为指示 对 控制规则：ho={ hom emb，one step}，hd={ hom emb，dfhom emb as}，do={ dynamic，one step}，dd={ dynamic，df hom emb as}150C. 奥乔亚湾Puebla/Electronic Notes in Theoretical Computer Science 177（2007）137查看拟合值，我们可以看到，尽管执行了盲修剪，但最佳解决方案被保留。但根据Sols专栏，我们正在修剪掉多余的最佳解决方案，只留下其中一个。显然，SPSR修剪的版本数量并不取决于所使用的拟合函数，因为拟合函数是在生成所有解之后使用的，以便确定哪些候选者是最好的。关于拟合值，有趣的是注意到该策略确实如此，即，动态作为全局控制，一步作为局部控制，产生与原始程序非常相似的程序（可能具有一些变量和谓词重命名）。这意味着在原始程序几乎没有谓词的情况下，很难获得比原始程序更小的剩余程序。这在基准测试permute、nrev、relative和转置，其中最佳控制策略是do，并且拟合值接近1。然而，请注意，PCPE在置换和相对而言，显然是通过混合解决方案。还有趣的是，直径在大多数情况下保持不变，这表明最佳和最差的解决方案都得到了保留。然而，在nrev和transpose中，直径减小了一点，并且由于最佳解决方案被保留，这意味着我们在这些情况下修剪了最差的解决方案总之，SPSR似乎是一种非常有趣的修剪技术，因为它显著减少了PCPE的搜索空间，它似乎保留了最佳解决方案（至少对于测试的基准），并且可以允许我们使用PCPE来攻击更有趣的基准，并为算法提供更多的静态它仍然是作为未来的工作，开发其他技术修剪搜索空间PCPE，可以确保最佳的解决方案被保存。致谢。这项工作的部分资金来自欧盟委员会的信息社会技术计划，IST- 15905MOBIUS项目下的未来和新兴技术，西班牙教育部的TIN-2005-09207MERIT项目，马德里地区政府根据S-0505/TIC/0407PROMESAS项目引用[1] E. Albert，G.普埃布拉和J·加拉格尔不纯谓词逻辑程序部分求值的非最左展开。第14届基于逻辑的程序合成与转换国际研讨会（LOPSTRSpringer-Verlag，2006年4月。[2] M. Bruynooghe ， D. De Schreye ， 和 B. 马 滕 斯 在 部 分 演 绎 中 避 免 无 限 展 开 的 一 般 准 则 。 NewGeneration Computing，1（11）：47[3] 史蒂芬-约翰·克雷格和迈克尔·卢舍尔。Prolog的自调优资源感知专业化。 PPDPPress.[4] 索米亚湾德布雷资源有限的部分求值。在PEPM'97的会议录192. ACM Press，1997.C. 奥乔亚湾Puebla/Electronic Notes in Theoretical Computer Science 177（2007）137151[5] J. Gallagher和M.布鲁努格程序特化算法的推导。New Generation Computing，9（1991）：305[6] J·P·加拉格逻辑程序的专门化。在PEPM'93的会议录ACM Press，1993.[7] 我是V。 Her rm ene gil do，Germ'anPuebla，Franc is coBueno，andPedroL'opez-Garc'sala.使用抽象解释（和Ciao系统预处理器）的程序优化，验证和优化。Science of Computer Programming，58（1[8] M. Leuschel和M.布鲁努格通过部分演绎的逻辑程序专业化：控制问题。Theory and Practice of LogicProgramming，2（4 5）：461[9] 迈克尔·鲁舍尔关于同胚嵌入的在线终止幂。在Giorgio Levi，编辑，静态分析。Proceedings of SAS史普林格出版社[10] Michael Leuschel，Ber