.346. 智能系统学报 第4卷 表，如此下去系统将进入无限循环4们 1 Prolog语言中的控制问题 在Prolog语言中，为解决此问题而引人了附加 为便于理解和分析，还需要先来回顾Prolog语 的控制机制cuts),如可在上例中Append的第I条 言控制机制存在的问题。 定义子句后增加cut原语(！)，改写为 例1设有Prolog程序P和目标子句G:← Append([],X,X)←-！. B1AB2A·AB,则Prolog程序的运行机制可概 虽然这样做可以避免上述的无限循环，但不能 括为 提高系统效率，而且影响了程序的可读性，甚至会影 1)从左到右，即逐个解决子目标B,B2,…,B。； 响一些调用的正确性，另外，Prolog语言编译系统中 2)深度优先，即在子目标B1完全解决之前不去 有时也可采用重新调整定义子句和子目标的次序等 处理B2,…,B,; 方法来解决一些控制问题.例如，当Append3用于 3)从上到下，即解决B,时先试用程序中它的第 表的分解时，可改变定义中的Append的子句顺序， 1条定义子句C,若成功转入C的体，直到后面解题 以提高效率.但这一方法缺乏通用性，对一些问题无 遇到困难或要求更多的解时才会回到原处去试用后 济于事.例如.目标： 面的定义子句（回溯）31， +-Append3(X,Y,Z,[1,2,3]). 上述过程体现了Prolog程序执行时基本的控制 对Prolog系统来说，无论如何重新安排子目标 机制.Prolog系统由于严格按照从左到右、深度优 与子句，或是使用cut,程序在输出列表[1,2,3]的 先、从上到下的匹配控制机制，而缺乏其他有效的控 所有可能的划分后都将陷入无限循环.因此，需要一 制机制，这样，在许多情况下将导致系统执行的低效 种既能提高效率又能避免死循环的控制机制，而且， 率且可能引起无限循环，也可能破坏系统的完备性 还应能较好地体现程序的说明性语义， 例2考虑下面的Prolog程序P1: 2 Godel语言中的DELAY延迟机制 1)Append([]X,X). 2)Append([HI T],Y,[H])Append (T, 针对Prolog语言控制机制存在的问题，Godel语 Y,Z). 言对Prolog语言的控制机制进行了改进，引入了 3)Append3 (X,Y,Z,U) DELAY延迟机制和剪枝操作.虽然Godel程序的执 +Append (X,Y,W)Append (W,Z,U). 行和Prolog程序一样都是采用最左深度优先搜索策 Append(X,Y,Z)是表的联结操作，表示将表 略的反驳一消解方法；但其推理过程在从左到右、深 X放在表Y前面构成一个大表Z;Append3.(X,Y, 度优先的控制基础上，合理使用延迟计算和灵活运 Z,U)表示将表X、Y、Z按顺序联结成一个大表U. 用剪枝操作，可以解决上述死循环的问题， 如果目标为←-Append3([1,2],[3],[4],X). 下面是个典型的Gdel语言计算排序问题的 Prolog程序会将3个表合并在一起得到X=[1,2, 程序实例G1. 3,4];但是，如果把Append3定义用于表的分解就 MODULE Slowsort. 会出现问题.例如，如果目标为：←Append3(X, PREDICATE Slowsort:List(a)*List(a); [3],[4],[1,2,3,4]),根据Append3的定义，第1 Permutation:List(a)*List(a); 个调用Append(X,[3],W),将与Append的第1 Sorted:List(a); 个定义子句相匹配，X实例化为[]，Append的第2 Delete a List(a)*List(a). 个调用失败产生回溯.第1个调用重新匹配后，X实 DELAY Slowsort(x,y）UNTIL 例化为长度为1的表，第2个调用再次失败产生回 NONVAR(x)VNONVAR (y); 湖.第1个调用再重新匹配，X实例化为长度为2的 Sorted([]UNTIL TRUE; 表，这时，第2个调用Append成功，X=[1,2].由 Sorted([_I x ]UNTIL NONVAR(x); 此可见这个计算的时间开销数量级为X长度的平 Delete(_,y,)UNTIL 方，而不是理想的与X长度成正比的数量级.进一 NONVAR(y)V NONVAR(2). 步考虑回溯的情况.不难看出，回溯使第1个调用将 Slowsort(z,y)-Sorted(y)Permutation(,y). X实例化为长度为3的表，第2个调用当然失败.此 Sorted([])←{Tue_1. 时，再次回溯到第1个调用，X实例化为长度为4的 Sorted([])+True1