·348 智能系统学报 第4卷 说明即可避免Append过程被低效地执行，也可使 声明剪枝条件，无需了解归结的控制过程.这既减轻 其避免无限循环. 了程序员的负担，又增强了程序说明性语义与过程 2)下面通过对Gdel程序G1的实例运行可更 性语义的一致性， 有效地说明Godel程序中DELAY延迟机制的合理 3.1 commit剪枝 使用可以促进子目标的协同执行，从而增强程序的 Godel语言的剪枝(commit)机制是对Prolog中 有效性 cut的改进，它建立在并发语言的commit机制之上， 设程序目标为←-Slowsort([6,1,5,2,4,3],x). 具有更好的说明性语义，可用于对搜索树进行剪枝， 第1个调用Sorted(x),发现x为列表变量，不 进而影响搜索的完全性，以提高问题求解的效率， 满足Sorted的DELAY说明，调用被延迟并在变量x Godel语言剪枝算子是commit,.一般形式为{…}n 上做标记.然后，调用Slowsort的第2个子目标Per- (n代表整数标号)，有2个特殊形式：一解剪枝 mutation([6,1,5,2,4,3],x）,满足Permutation的 （one-solution commit)和条形剪枝(bar commit).一 延迟说明，调用成功，x被实例化为[611]，但还是 解剪枝形式为{….，当它找到{}所包含的公式的 不满足Sorted的DELAY说明，故继续执行Permuta- 一个解之后返回，其他可能的解将被剪除.条形剪枝 tion的调用.当x被实例化为[6,1|2]时，满足Sor- 形式为“”，其含义相当于合取，其作用范围是语句 ted的DELAY说明，此时立即唤醒x上的延迟调用， 体内出现在其左边的公式，只求出其辖域内公式的 重新执行Sorted(x)调用.由于x的前2个元素[6， 一个解，而搜索树中其他谓词定义中包含“”的语 1]不是有序的，程序放弃排列结果[6,112]，Sor 句的相关分支均被剪除.Gdel语言中剪枝操作的2 ted(x)将重新延迟.Permutation调用回溯，重新产 种特殊形式经过处理，在计算机内部它们都可用一 生排列；当x被实例化为[1,612]时又满足Sorted 般形式{…}-n来表示.一个剪枝操作{Formula{-_n 的DELAY说明，并立即唤醒x上的延迟调用，重新 的括号{.·}指明了该剪枝在语句体中的作用范 执行Sorted(x)调用.这时，由于x的前2个元素 围，而标记n是剪枝号（标签），用于标识某一剪枝. [1,6]是有序的，Sorted进行递归调用.依此循环处 当公式Formula成功时，这个定义语句中的所有其 理，程序将很快得到[6,1,5,2,4,3]的排序结果[1， 他包含相同标记n的语句所对应的树枝将被剪掉. 2,3,4,5,6] 条形剪枝操作记为“1”，每条Godel程序语句最多 如果没有采用上面基于Sorted上的DELAY说 只能含有一个“1”.“1”的作用范围就是在语句体 明，那么程序运行时每次都要完整地算出列表x上 内出现在“”左边的那个公式.如果一个程序中某 的每个元素，而长度为n的列表的排列个数为n!,所 语句含有“1”，那么该程序将在求出“1”辖域中公 以，计算时间复杂度为O(n!).然而，如果采用DE 式的一个解后，剪除由同一谓词定义的语句中包含 LAY说明后执行这样的目标所花的时间将大大减 了“”的语句所产生的搜索树中的所有其他分支 少，时间复杂度为O(n).可见DELAY延迟计算促 举例如下，设某程序中有3条语句如下所示： 进了子目标的协同执行，从而产生的惰性计算的效 Partition([],,][])1, 果，使得Godel程序的排序比对应的Prolog程序的 Partition([xlxs],y,[x|s],bs)←-x≤yl 排序效率更高。 Partition (xs,y,ls,bs), Godel语言中的剪枝操作 Partition ([x I xs],y,ls,[xI bs])+x>yl Partition (xs,y,ls,bs). 在Godel语言的控制机制中，除了DELAY延迟 上述语句定义了快速排序程序中的分割函数， 机制外，还有一个重要的控制机制，即剪枝操作.有 即当第1个参数列表不为空时，根据表中元素y(列 点类似于Prolog中的cut机制，Godel语言也提供了 表元素)的值把该列表分为比y大的部分和比y小 对反驳一消解树进行不完全搜索的方法，即剪枝操 的部分，分别存在第4个和第3个参数列表中.3条 作.但剪枝操作与cut不同，剪枝操作有效地解决了 语句中都含有“1”，它的目的是保证这3条语句互 Prolog中cut带来的诸如程序的逻辑部分界定的不 斥.即当列表为空时第1条语句被执行，而第2和第 准确性、存在否定时Cut造成求解结果不可靠等问 3条语句对应的分枝被剪除，因为此时第2和第3 题.剪枝与cut机制最本质的区别在于cut机制需要 条语句根本没有必要执行；而当列表不空时第2和 程序员了解程序的归结过程，而剪枝只需要程序员 第3条语句中的某一句将被执行，另外2条程序语