第2期 昌杰，等：逻辑程序设计语言Godel与Pobg的比较 ·165· 类问题.其中cut最重要的作用是，丢掉在它所出现 其执行唤醒，对Reverse(T,[2,4])进行操作.如此 的规则中从头部开始直到“！”之间所有子目标由于成 循环操作直到所有合一操作结束，将得Y值为[3 功而在数据库中作出的标记.使这些目标的再满足无 4.21. 法进行，从而防止回溯.它可以解决一些由于Poog 从例子可以看出，延迟不仅解决了因Poog控 最左文字优先规则而引起的的无限循环，例如： 制机制带来的无限制循环问题，而且还引入了并发 例3设有Probg程序片段 执行，可提高系统执行的效率 1)member(X,XlTJ)←4 Godelf的剪枝操作comm it类似于Probg中的 2)member(X.(Y T])--member(X.T). cut机制，但它是建立在并发语言的comm it机制之 m em ber(XY)谓词判断X是否为列表Y中的 上，具有更好的说明性语义.然而，Goàel的剪枝操 元素.在没有加“！”之前，执行目标子句member(X,作也会带来和pobg中cut一样的问题，如剪去了 1,2,3)时，X将在分别输出1,2,3后陷入死循环. 有效答案所在的分支等，但Godel语言通过增强对 引入“！”以后，X将在输出1以后停止执行.但是， 谓词的D可AY说明就能够很好地解决这个问题 若要求输出所有解，“！”在任何位置的引入都无法 对于上述程序，若没有对其增加D日AY说明， 解决此问题，即使改变子句和子目标的次序也无济 当执行目标语句member(X,[1,2,3])∧X=2 于事，同时该方法缺乏通用性」 时，第1个子目标在与子句1合一后得到X=1结 针对Polg语言控制机制存在的问题，Godeli语 束回溯，这个结果与子目标2相矛盾，从而无法得出 言对其控制机制进行了改进，引入DEAY延迟控 正确的结果.当对其增加如下说明： 制剪枝操作.程序员可以通过适当的DEAY延迟 DELAY member(X,/Y ]UNTL NON- 保证一个调用在被足够实例化后再推进，这样就避 VAR(X)ANONVAR(Y). 免了无法预料的失败，同时有助于程序员控制程序 对该目标子句，第1个子目标由于不满足条件 运行2) 而被挂起，直到第2个子目标执行将X实例化为2， 例4对应于同样的问题，Godeli语言采用的源 立即将子目标1唤醒.得到判断结果TRUE,表示X 程序如下： 是列表中元素. PRED CATE Reverse:List(a)*List(a ) 尽管剪枝会破坏程序的可读性和正确性，但合 DELAY Reverse(X.Y)UNTL 理的剪枝可以大大提高程序执行的效率，因此，剪枝 NONVAR(X)VNONVAR(Y). 在逻辑程序设计语言中仍具有重要意义.在Godel 1)Reverse([]]) 语言中，如果配合以强DHAY说明，更将大大减少 2)Reverse([HI TJ,Rev)+Reverse T.TR) 剪枝带来的负面作用，从而得到更加广泛的应用 AAppend(TR,[H J.Rev). 3模块化程序设计的作用 其中，DHAY延迟的语法形式为DELAY A tom UNTL Cond,.Aom为原子，Cond为条件集.这里， 模块化程序设计是大型软件系统开发的有效方 Cond为NONVAR(X)ANONVAR(Y).程序表示 法和技术之一.Po0g的设计没有引入模块化的设 在操作中只有当Reverse()内X、Y中任意一项被实 计方案，语言本身过于简单也使得它并不适用于大 例化，才能对Reverse()所对应的子句进行处理，否 型软件的设计与开发.随着计算机应用领域的不断 则，延迟将挂起对谓词Reverse()的调用，直到条件 深化，对软件的效率、可靠性、易维护的要求越来越 被满足 高，非模块化设计功能的Pobg很明显不符合现代 所以，当例2中同样的目标子句Reverse(Y, 软件工程的基本要求」 [2,4,3])被执行时，首先，目标子句满足D日AY条 Godeli语言的定位考虑了大型智能软件的开 件，在与子句1匹配失败后，与子句二合一，生成2发，引入了模块系统.每个模块相当于一个构件，程 个子目标Reverse(I,TR)和Append(TR,[HI,序员将各个不同的构件进行组装设计可形成更大的 Rv).由于子目标1不满足延迟条件被挂起，子目程序，而每个构件尽量保持各自的独立性.模块的执 标2被执行，Append()谓词将TR和H分别实例化 行细节封装在模块内部，对其他构件保持透明 为[2,4和3此时，子日标1延迟条件满足，立刻将 这样的设计使Godeli语言融合了现代软件工程的思 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net类问题. 其中 cut最重要的作用是 ,丢掉在它所出现 的规则中从头部开始直到“!”之间所有子目标由于成 功而在数据库中作出的标记. 使这些目标的再满足无 法进行 ,从而防止回溯. 它可以解决一些由于 Prolog 最左文字优先规则而引起的的无限循环. 例如 : 例 3 设有 Prolog程序片段 1) member( X, [X | T ]) ← !. 2) member( X, [ Y | T ] ) ← member( X, T) . member( X, Y) 谓词判断 X 是否为列表 Y中的 元素. 在没有加“! ”之前 ,执行目标子句 member( X, [1, 2, 3 ]) 时 , X将在分别输出 1, 2, 3后陷入死循环. 引入“! ”以后 , X 将在输出 1以后停止执行. 但是 , 若要求输出所有解 ,“! ”在任何位置的引入都无法 解决此问题 ,即使改变子句和子目标的次序也无济 于事 ,同时该方法缺乏通用性. 针对 Prolog语言控制机制存在的问题 , Go¨del语 言对其控制机制进行了改进 ,引入 DELAY延迟控 制剪枝操作. 程序员可以通过适当的 DELAY延迟 保证一个调用在被足够实例化后再推进 ,这样就避 免了无法预料的失败 ,同时有助于程序员控制程序 运行 [ 2 ] . 例 4 对应于同样的问题 , Go¨del语言采用的源 程序如下 : PRED ICATE Reverse: List( a ) 3 L ist( a ). DELAY Reverse ( X, Y ) UNTIL NONVAR ( X ) ∨NONVAR ( Y ). 1) Reverse ( [ ], [ ]). 2) Reverse ( [ H | T ], R ev ) ← Reverse ( T, TR ) ∧Append ( TR, [H ], R ev ). 其中 , DELAY延迟的语法形式为 DELAY A tom UNTIL Cond, A tom 为原子 , Cond为条件集. 这里 , Cond为 NONVAR ( X ) ∧NONVAR ( Y ). 程序表示 在操作中只有当 Reverse ( )内 X、Y中任意一项被实 例化 ,才能对 Reverse ( )所对应的子句进行处理 ,否 则 ,延迟将挂起对谓词 Reverse ( )的调用 ,直到条件 被满足. 所以 ,当例 2中同样的目标子句 Reverse ( Y , [ 2, 4, 3 ])被执行时 ,首先 ,目标子句满足 DELAY条 件 ,在与子句 1匹配失败后 ,与子句二合一 ,生成 2 个子目标 Reverse ( T, TR ) 和 Append ( TR, [H ], Rev). 由于子目标 1不满足延迟条件被挂起 ,子目 标 2被执行 , Append ( )谓词将 TR 和 H分别实例化 为 [ 2, 4 ]和 3. 此时 ,子目标 1延迟条件满足 ,立刻将 其执行唤醒 ,对 Reverse ( T , [ 2, 4 ])进行操作. 如此 循环操作直到所有合一操作结束 ,将得 Y值为 [ 3, 4, 2 ]. 从例子可以看出 ,延迟不仅解决了因 Prolog控 制机制带来的无限制循环问题 ,而且还引入了并发 执行 ,可提高系统执行的效率. Go¨del的剪枝操作 comm it类似于 Prolog中的 cut机制 ,但它是建立在并发语言的 comm it机制之 上 ,具有更好的说明性语义. 然而 , Go¨del的剪枝操 作也会带来和 p rolog中 cut一样的问题 ,如剪去了 有效答案所在的分支等 ,但 Go¨del语言通过增强对 谓词的 DELAY说明就能够很好地解决这个问题. 对于上述程序 ,若没有对其增加 DELAY说明 , 当执行目标语句 member ( X , [ 1, 2, 3 ]) ∧ X = 2 时 ,第 1个子目标在与子句 1合一后得到 X = 1结 束回溯. 这个结果与子目标 2相矛盾 ,从而无法得出 正确的结果. 当对其增加如下说明 : DELAY member ( X, [ Y | _ ]) UNTIL NON2 VAR ( X ) ∧NONVAR ( Y ). 对该目标子句 ,第 1个子目标由于不满足条件 而被挂起 ,直到第 2个子目标执行将 X实例化为 2, 立即将子目标 1唤醒. 得到判断结果 TRUE,表示 X 是列表中元素. 尽管剪枝会破坏程序的可读性和正确性 ,但合 理的剪枝可以大大提高程序执行的效率 ,因此 ,剪枝 在逻辑程序设计语言中仍具有重要意义. 在 Go¨del 语言中 ,如果配合以强 DELAY说明 ,更将大大减少 剪枝带来的负面作用 ,从而得到更加广泛的应用. 3 模块化程序设计的作用 模块化程序设计是大型软件系统开发的有效方 法和技术之一. Prolog的设计没有引入模块化的设 计方案 ,语言本身过于简单也使得它并不适用于大 型软件的设计与开发. 随着计算机应用领域的不断 深化 ,对软件的效率、可靠性、易维护的要求越来越 高 ,非模块化设计功能的 Prolog很明显不符合现代 软件工程的基本要求. Go¨del语言的定位考虑了大型智能软件的开 发 ,引入了模块系统. 每个模块相当于一个构件 ,程 序员将各个不同的构件进行组装设计可形成更大的 程序 ,而每个构件尽量保持各自的独立性. 模块的执 行细节封装在模块内部 ,对其他构件保持透明 [ 4 ] . 这样的设计使 Go¨del语言融合了现代软件工程的思 第 2期 昌 杰 ,等 :逻辑程序设计语言 Go¨del与 Prolog的比较 ·165·