第4期 高伟，等：G6del语言控制机制的研究与实现 ·349· 句对应的分枝将被剪除.如果没有这个“1”，那么3 DELAY延迟机制既能够发挥剪枝的有效性，又保证 条语句将被一起尝试执行，这将浪费大量的时间.由 了程序的完备性. 这个例子可以看出，剪枝操作在保证程序正确性的 剪枝运算在编写风格良好的Godel程序中较少 基础上，极大地提高了执行效率. 使用，代之以否定或f-then-else等说明性结构，这主 已经知道，条形剪枝是commit剪枝的特例，它 要是为了保证程序具有清晰的说明性语义，尽管剪 可以转换为commit剪枝.转换方法如下：将“|”左边 枝操作可能影响程序的说明性语义，但合理的剪枝 的子目标作为commit剪枝的条件（对于事实子句， 可以使程序执行速度和问题求解的效率大大提高， 此时条件为Tue),并附加剪枝号.例如，可以将上 有着优越的过程性语义，在逻辑程序设计语言中仍 面的条形剪枝语句转换为如下commit剪枝语句： 有重要的意义 Partition([],_,]])True1, Partition([x I xs],y,[x I ls],bs) 4 Godel语言控制机制的算法设计与 ←{x≤y}_1∧Partition(xs,y, 实现 Is,bs), Partition([xI xs],y,ls,[x I bs]) 由上面所述知，Gdel语言中通过引人新的控 x>y1 Partition(xs,y,ls,bs). 制成分DELAY延迟机制和剪枝操作，完善了逻辑 Tue为系统关键字，即剪枝条件永远为真.因 程序设计语言的控制机构，可有效地提高系统的效 此，对于第1条子句只要合一成功即可剪除第2条 率.然而，由于实现难度较大，迄今为止，即使是语言 子句和第3条子句对应的搜索分枝， 的设计者们，也仅实现了一个旨在验证语言功能的 3.2 DELAY说明和剪枝的应用 原型系统，一些新的语言成分并没有实现.下面，对 如同Prolog中的cut一样，剪枝操作也有可能 Gdel语言控制机制的实现算法进行讨论，希望能 会剪去有效答案，但是，在Godel程序中可以通过设 够为该语言的完全实现建立一些方法和技术基础. 计一个好的DELAY说明来控制剪枝.一个重要的 Gdel语言的控制机制可概括为 启发就是DELAY说明应足够强，从而避免由于过 1)从左到右选取子目标进行判定.如子目标有 早地剪去一个不合适的树枝而导致无法预料的错 DELAY声明，先判断DELAY条件是否满足再决定 误.下面的Godel程序G3通过改进程序G1中的对 是否执行，若不满足，则先取下一个子目标； Delete的延迟声明有效地说明了这一点. 2)采用深度优先的方法对搜索树进行搜索、匹 PREDICATE Delete:a List(a )List(a ) 配和判定； DELAY Delete (x,[y I _],_UNTIL NONVAR 3)按程序中子句的顺序选取目标的可匹配项 (x)A NONVAR(y ) 进行匹配尝试和处理，当一个子目标匹配成功时，若 Delete (x,[xI y],y)+True2. 有剪枝操作，则不对与其剪枝号相同的其他可匹配 Delete(x,[ylz],[ylw])←-{x≠yi2 ADelete 项进行匹配尝试，即剪掉搜索树的部分分枝， (x,z,0)· Godel语言中的控制机制是Godel语言实现的 假设Delete的DELAY说明被删除了，现在来 关键部分之一.原理上，控制机制只是实现带有延迟 考察目标： 和剪枝的从左到右、深度优先、从上到下的匹配算 ←-Delete(x,[1,2,3],y)∧x=2 法，较为简单.但是，在实现一个真正实用的系统时， 目标中的第1个原子与Delete定义里的第1条 还得考虑各种因素，实现起来比较复杂s].G6del 语句的头部相匹配，因此，系统求得x=1并将剪掉 语言中的控制机制作为编译系统实现的一部分，其 其他的匹配语句，然而接下来调用1=2会导致目标 实现在技术上是将程序运行时的各种信息分为多栈 产生不可预料的错误. 存储（运行栈、环境栈、解除栈和延迟栈），以此来简 现在假设Delete调用已经根据程序中的Delete 化运行栈的控制，从而使控制机制获得较高的效率。 的延迟说明进行了延迟，从而先执行x=2,然后唤 借助前面实例分析的流程获得的思想，下面给出 醒x上的延迟调用Delete(2,[1,2,3],y),那么，目 Gdel语言控制机制的算法流程图（图1）」 标就能返回预期的结果.由此可见，Gdel语言中的