第4期 高伟，等：G6del语言控制机制的研究与实现 ·347· Sorted([x,ylz])←-{x≤y1 Sorted([ylz]). Append3(X,Y,Z,U)+-Append(X,Y,W)A Permutation([],]) +Append(W,Z,U). Permutation([xI y],[ul v]) 程序中的DELAY说明表示调用Append时第1 ←Delete(u,[xly],z）Permutation(z,v). 个参数和第3个参数必须至少有一个是非变量，如 Delete (x,[xI y],y)True2. 果满足不了该条件，则调用被延迟挂起.系统在引起 Delete (x,[yl z],[yl w])x y2 Delete(x,z,0). 延迟的变量上做标记，以示某过程调用等待此变量 模块Slowsort给出了实现排序的Gdel语言程 被实例化为非变量，一旦标记变量被实例化，所有其 序.程序中Slowsort(x,y)表示对列表x排序后得到 上等待的过程调用立即被唤醒，成为当前优先执行 列表y,其中，调用的谓词Permutation(x,y)表示列 的子目标.例如：←-Append(X,[2],[1,2])满足 表y是列表x的一个排列，而谓词Sorted(x)表示x DELAY说明，过程被成功调用.然而对于： 是一个有序列表.DELAY说明表示当x和y至少有 ←-Append(X,[2],Y),由于第1个参数和第3个参 一个已约束时，SlowSort才能计算；而Sorted(x)调 数同时为变量不满足DELAY说明，过程调用将被 用只有当列表x为空或者在前2个元素已知的情况 延迟，并在这些变量上做标记.一旦X、Y中任一变 下才可以执行，否则延迟计算.谓词Sorted有3个定 量被实例化为非变量，延迟的Append立即被唤醒 义子句并且都包含了剪枝号为1的剪枝，这表示如 重新调用执行. 果在匹配时有一个子句匹配成功，则不再尝试匹配 2.2 DELAY延迟机制的使用 其他2个含有相同剪枝符号1的子句.从这个例子 运用DELAY延迟机制能确保某些调用被充分 不难看出Godel语言引入的这些新机制使语言具有 实例化后才运行，从而增强程序的可终止性以避免 更强的说明性，同时语言的控制也变得更加灵 死循环.另外，DELAY延迟的使用可以实现子目标 活).下面来详细介绍DELAY延迟机制. 的协同执行，从而增强程序的有效性.下面通过例子 2.1 DELAY延迟说明的语法和语义 来说明这2点。 DELAY延迟说明的语法形式为 1)考察前面的Prolog程序P1中的目标：←-Ap DELAY Atom UNTIL Cond. pend3(X,[3],[4],[1,2,3,4]) 其中，Atom是原子.Cond语法规则如下： 在Gdel程序G2中的执行情况： Cond→Cond1 I Cond1{∧Cond1 I Cond1{V 第1个调用执行Append(X,[3],W),发现 Cond1, Append的第1、第3个参数同时为变量，不满足Ap Cond1-NONVAR Variable I GROUND pend的DELAY说明，调用被延迟，并在第l、第3个 Variable )I TRUE I Cond ) 变量上做标记.然后，调用Append3的第2个子目标 其中，Cond对原子中出现的变量延迟调用条件进行 Append(W,[4],[1,2,3,4]),它满足DELAY说 说明，Variable是出现在Atom中的变量，关键字 明，将W实例化为[1|T,],立即唤醒W上的延迟调 NONVAR表示延迟条件是变量，已实例化，关键字 用，重新执行第I个Append调用，Append(X, GROUND表示变量为基本项.程序通过DELAY说 [3],[1IT])满足DELAY说明，合一成功将X实 明限制谓词过程的调用，调用如果满足则进行处理， 例化为[i|T2],接着调用Append(T2,[3],T), 否则延迟挂起调用 调用被延迟；再选下一个子目标Append(Ti,[4], 将前面的Prolog程序PI改写为带DELAY延 [2,3,4])继续执行，如此往复执行直到目标合一成 迟说明的Godel程序G2如下： 功.从调用的执行过程可见，2个Append调用是并 PREDICATE Append:List(a)List(a)* 发执行的，它们的时间开销与X的长度成正比，要 List(a); 低于Prolog系统中的时间数量级(X长度的平方)， Append3:List a)*List a)* 因此，系统效率将得到很大提高.注意：Prolog程序 List(a)*List(a). P1调用目标←-Append3(X,Y,Z,[1,2,3]),将陷入 DELAY Append(X,_,Z)UNTIL 无限循环. NONVAR(X)V NONVAR(Z) 但是，在Godel程序G2中由于存在Append的 Append([]X,X). DELAY说明，该目标在输出所有可能的划分后正常 Append([HI T],Y,[HI Z ])+-Append (T,Y,Z). 结束（具体调用过程不再累述）.由此可见，DELAY