逻辑程序的高效实现

9.4.3 逻辑程序的高效实现

Prolog程序的执行有两种模式；解释执行和编译执行。解释本质上相当于将程序当作知识库来运行图9.6的FOL-BC-ASK算法。我们说“本质上”，因为Prolog解释器包含各种为了最大化速度而设计的改进方法。我们在此只考虑其中的两种。

首先，在继续下一个子目标之前，Prolog翻译器生成一个答案和一个“承诺”，在对当前答案进行完全地探索后再生成其它的答案，而不是构造每个子目标所有可能的答案列表。该承诺称为选择点。当深度优先搜索完成对当前答案带来的所有可能解的探索之后，返回选择点，并对选择点进行扩展以生成子目标的新答案和新的选择点。该方案不仅节省了时间，还节省了空间。它还为调试提供了一个非常简单的接口，因为在任何时候都只考虑一条单一的解路径。

其次，我们简单实现的FOL-BC-ASK在生成和组合置换上花费了大量的时间。Prolog使用可以记住其当前绑定的逻辑变量来实现置换。在任何一个时间点，程序中的每个变量或者绑定了某个值或者没有。这些变量和值一起隐含地定义了当前证明分支的置换。扩展路径只能增加新的变量绑定，因为试图对一个已经绑定值的变量增加不同的绑定会导致合一的失败。当一条搜索路径失败时，Prolog将返回前一个选择点，然后会解除部分变量的绑定值。这可以通过在一个被称为踪迹栈的栈中记录已经被绑定的变量来完成。一旦每个新变量由UNIFY-VAR绑定，变量就被推入踪迹栈。当目标失败需要返回前一个选择点时，每个变量都将在从踪迹栈中删除的时候解除绑定。

由于索引的查找、合一和建立递归调用栈的开销，即使效率最高的Prolog解释器在执行每步推理时都需要上千条机器指令。事实上，解释器总是表现得如同以前从来就没见到过该程序；例如，它需要查找能和目标匹配的子句。另一方面，编译过的Prolog程序是一个针对特定的子句集的推理过程，因此，它知道哪些子句匹配目标。Prolog基本上为每个不同的谓词生成一个小型定理证明机，从而削减大部分解释开销。它同时还可能对每个不同调用的合一程序进行开放编码，从而避免对于项结构的显式分析。（关于开放编码的合一的详细内容参见Warren等人（1977）的文章。）

如今的计算机指令集与Prolog语义的匹配非常差，因此大部分Prolog编译器把Prolog程序编译成中间语言，而不是直接编译成机器语言。最流行的中间语言是Warren抽象机（Warren Abstract Machine， WAM），以纪念David H. D. Warren，第一代Prolog编译器的实现者之一。WAM是一个适合于Prolog的抽象指令集，可以解释或者翻译成机器语言。其它编译器将Prolog翻译成高级语言如Lisp或者C，然后就可以利用这些语言的编译器翻译成机器语言。例如，谓词 Append 的定义可以编译成如图 9.8所示的代码。在此有几点值得一提：

图9.8 表示谓词Append的编译结果的伪代码。函数NEW-VARIABLE返回一个新的变量，它不同于目前使用的所有其它变量。过程CALL(continuation)根据指定延续继续执行

• 胜过必须在知识库中搜索 Append 子句，编译器把子句转换成一个过程，只需简单地调用该过程就可以进行推理。

• 如同前面所描述的，当前变量绑定保存在踪迹栈中。过程的第一步就是保存踪迹栈的当前状态，所以如果第一个子句失败就可以利用RESET-TRAIL还原踪迹栈。这将取消任何由第一次调用UNIFY生成的绑定。

• 最有技巧性的是利用延续实现选择点。你可以将延续视为一个过程和参数列表的封装，它们共同规定了无论何时当前目标成功后下一步将进行什么工作。由于它可能有多种成功途径，而且每条途径都需要探索，因此它在目标成功时将不只是从一个类似 APPEND的过程返回。延续参数解决了这个问题，因为它可以在每次目标成功时调用。在APPEND编码中，如果第一个参数为空，则谓词APPEND就已经成功。然后，我们以踪迹栈中适当的绑定来调用（CALL）延续，以完成下一步应该要做的事情。例如，如果对APPEND的调用在顶层，延续会打印变量的绑定。

在Warren对Prolog中推理的编译进行研究之前，逻辑程序设计太慢而不通用。Warren和其他人设计的编译器提高了Prolog程序的速度，使得它在各种标准测试程序上可以与C语言相匹敌（Van Roy， 1990）。当然，几十行Prolog程序就可以编写一个规划器或者自然语言分析器的事实也令它比C语言更适用于大多数小规模AI研究项目的原型开发。

并行化也能切实地提高速度。有两个主要的并行性来源。第一个称为或-平行，源于某个目标可以与知识库中许多不同子句进行合一的可能性。每个合一都会引出一个搜索空间的独立分支，这些分支指向某个潜在的解，并且都可以并行求解。第二个称为与-并行，源于并行求解蕴涵体内的每个合取子句的可能性。与-并行更难达到，因为整个合取式的解要求对所有变量的一致绑定。每个合取分支必须和其它的分支交流以确保获得全局解。