|
PROLOG(Programming in Logic)语言与传统程序设计语言有着本质的差别。传统程序设计语言是基于冯.诺依曼式的计算机体系结构，是以赋值/数据处理。PROLOG语言是典型的逻辑程序设计语言，它是建立在Horn子句基础上的。Horn子句或者是一个断言(命题)，或者是一个逻辑蕴涵式(推理规则)。对于提供的问题，PROLOG系统实现目标的过程是一种特殊的线性输入消解过程。PROLOG的主要机制是模式匹配和回溯，搜索策略是从上到下，从左到右，严格执行深度优先。软件测试［2，3］是提高软件可靠性的重要手段，也是软件工程中最活跃的研究领域之一。笔者经过多年使用PROLOG语言发现，规则之间的矛盾在PROLOG程序中经常出现，且程序员不易发现这种错误。因此，我们提出了一种检测PROLOG程序中规则之间矛盾的算法，已用C语言实现了该算法。对Turbo-PROLOG系统盘进行了剖析，该算法作为一种PROLOG检测工具已被合并到Turbo-PROLOG系统盘中。 1 PROLOG检测工具研究现状 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出现矛盾。否则，列出两规则子目标中不同的子目标，通过人机对话方式询问用户，从谓词语义上确定是否有矛盾谓词存在。 3 Turbo PROLOG系统盘的剖析与改进 为了把矛盾检测算法做为一种工具合并到Turbo PROLOG系统盘中，需做以下工作：
(1)在Turbo PROLOG系统菜单上增加一个菜单选项(Debug)。
(2)修改Turbo PROLOG系统中的文件prolog.exe使其能接收选择，执行检测工具。
(3)找到Turbo PROLOG系统中存储程序的内存地址，以便使检测程序对源程序进行操作。
通过跟踪分析prolog.exe文件，找到一段程序如下：
1636 CMP WORD PTR［BP+06H］，+00
163A JNZ 163F
163C JMP 16BE
163F PUSH ［BP+06］
它的流程图如下： 
图4 Turbo PROLOG系统盘流程图 笔者将上段程序改为：
1636 CMP WORD PTR［BP+06］，+44
163A JNZ 163F
163C INT 60
163E NOP
163F PUSH ［BP+06］
通过对prolog.exe的动态跟踪分析，得到了存储源程序的地址：当前数据段DS内，偏移地址00D5处，内容55BF为当前存储PROLOG源程序的段地址；当前数据段DS，偏移地址00D3处，内容0097为当前存储PROLOG源程序的偏移地址。 4 结束语 用C语言实现的矛盾检测算法(工具)已被合并到Turbo PROLOG的系统盘中，为用户的实际使用提供了方便。将一个检测工具合并到PROLOG系统盘上一般有2种方法：第一，将需增加的程序加入EXE文件中；第二，将需增加的程序以常住内存的方式，由源程序调用。对于第一种方式，由于EXE文件的头参数需要修改，还涉及到压栈、保护现场、返回等问题，对源文件过多的修改增加了不可靠性；第二种方法修改的信息比较少，而且中断调用是系统所设置的，比较可靠。 | 
