prolog(programming in logic)语言与传统程序设计语言有着本质的差别。传统程序设计语言是基于冯.诺依曼式的计算机体系结构,是以赋值/数据处理。prolog语言是典型的逻辑程序设计语言,它是建立在horn子句基础上的。horn子句或者是一个断言(命题),或者是一个逻辑蕴涵式(推理规则)。对于提供的问题,prolog系统实现目标的过程是一种特殊的线性输入消解过程。prolog的主要机制是模式匹配和回溯,搜索策略是从上到下,从左到右,严格执行深度优先。软件测试[2,3]是提高软件可靠性的重要手段,也是软件工程中最活跃的研究领域之一。笔者经过多年使用prolog语言发现,规则之间的矛盾在prolog程序中经常出现,且程序员不易发现这种错误。因此,我们提出了一种检测prolog程序中规则之间矛盾的算法,已用c语言实现了该算法。对turbo-prolog系统盘进行了剖析,该算法作为一种prolog检测工具已被合并到turbo-prolog系统盘中。
1prolog检测工具研究现状
1965年robinson提出的归结原理是在机器定理证明方面的一个重要突破。在1972年,为了将计算机应用于机器定理证明,konwalski和colmerauer等人在法国马赛大学设计出了prolog。
出于prolog程序的执行是不确定的,规则的输入输出关系不像传统软件中的过程那样精确,激活规则的方式太多,不能使用路径覆盖工具。目前国内外在prolog检测工具方面的研究进展很小,主要成果有:
1)lawrence提出了描述prolog程序控制流程的框模型。
2)重庆大学提出了一种检测prolog程序中无限循环的算法。
3)shapiro提出了算法调度方法。
4)pereira提出了关系调试方法等。
2矛盾检测算法
2.1数据结构
为了对矛盾进行检测,需要对源程序进行静态测试,其基础是将源程序转变为内部结构的数据结构。
turbo prolog程序由若干程序段构成,每段用一个关键字标识,包括:1)领域段;2)数据库谓词说明;3)谓词说明;4)事实;5)目标。
我们设计的各程序段的数据结构如下:
1)领域段数据结构如下(图1)
图1领域段数据结构图 其中在d1中,type可为整数、字数、字符、串、符号类型;next域用于链接下一类型的说明;perior域为指向此类型的变量名。在d2中,name域为此类型的变量名;next域将同一类型说明的变量连在一起。 2)谓词说明段数据结构如下(图2) |
图2谓词说明段数据结构图 3)事实规则域数据结构如下(图3) |
图3事实规则域数据结构图 2.2矛盾检测算法的实现原理 在prolog程序中经常会出现2个规则之间矛盾的现象。推理过程中出现矛盾,这对于知识库来说是不完备的,而且它直接影响到知识库的可靠性。 矛盾的定义: 如果2组规则在相同条件下得出相反的结论,或者在2组相互矛盾的条件下得出了相同的结论,我们则说这2组规则是矛盾的,多条规则的情况同理。 一般地,设在规则r1,r2,…,rn中有2个规则ri,ri+1头部相同: ri,a:——α1,α2,…,αn ri+1,a:——β1,β2,…,βn 如果α1,β1不为循环谓词,我们将其“代换”,直到都为确定状态为止。“代换”后的规则ri,ri+1的子目标集合分别为: ri,(γ1,γ2,…,γn,θ1,θ2,…,θm) ri+1,(δ1,δ2,…,δn,θ1,θ2,…,θm) 将相同的子目标除去不再考虑,只对两者有相同的子目标加以比较。若从形式上ri有子目标b,ri+1有子目标b,则两集合有矛盾存在,即ri,ri+1出现矛盾。否则,列出两规则子目标中不同的子目标,通过人机对话方式询问用户,从谓词语义上确定是否有矛盾谓词存在。 3turbo prolog系统盘的剖析与改进 为了把矛盾检测算法做为一种工具合并到turbo prolog系统盘中,需做以下工作: (1)在turbo prolog系统菜单上增加一个菜单选项(debug)。 (2)修改turbo prolog系统中的文件prolog.exe使其能接收选择,执行检测工具。 (3)找到turbo prolog系统中存储程序的内存地址,以便使检测程序对源程序进行操作。 通过跟踪分析prolog.exe文件,找到一段程序如下: 1636cmpwordptr[bp+06h],+00 163ajnz163f 163cjmp16be 163fpush[bp+06] 它的流程图如下: |
图4turbo prolog系统盘流程图 笔者将上段程序改为: 1636cmpwordptr[bp+06],+44 163ajnz163f 163cint60 163enop 163fpush[bp+06] 通过对prolog.exe的动态跟踪分析,得到了存储源程序的地址:当前数据段ds内,偏移地址00d5处,内容55bf为当前存储prolog源程序的段地址;当前数据段ds,偏移地址00d3处,内容0097为当前存储prolog源程序的偏移地址。 4结束语 用c语言实现的矛盾检测算法(工具)已被合并到turbo prolog的系统盘中,为用户的实际使用提供了方便。将一个检测工具合并到prolog系统盘上一般有2种方法:第一,将需增加的程序加入exe文件中;第二,将需增加的程序以常住内存的方式,由源程序调用。对于第一种方式,由于exe文件的头参数需要修改,还涉及到压栈、保护现场、返回等问题,对源文件过多的修改增加了不可靠性;第二种方法修改的信息比较少,而且中断调用是系统所设置的,比较可靠。 |