Prolog语言基础知识

Prolog语言基础知识

一.数据结构

PROLOG语言与其他任何一种计算机高级语言一样，有其定义的数据结构。下面将介绍PROLOG语言的基本数据结构。

1.常量

常量是数据结构的基本组成部分，用来对特定对象及关系的命名。

在PROLOG语言中，合法的常量有：

(1)整数,一个纯数字串，例 182 000，581 202。

(2)原子，分为两种：

1)标识符：以小写字母开头的，包含字母、数字、下划线的串，例 aBC12，is_。

2)符号：PROLOG语言规定的符号集的非空序列，例?、-、=。若原子用 单引号厂(‘ ’)括住，则可含有任何字符。

(3)字符集ab...z

2.变量

变量是用来表示还无法知道且需要PROLOG程序来确定的客体。变量用变量名表示,变量名与标识符相似,所不同的是以大写字母或下划线开头。例Variable，_ansure。

PROLOG语言中有一个特殊的变量,不需要知道它是什么以及具体名字,只是表示留出一位置,称为匿名变量。用单一的下划线(_)来表示。比如只想知道是否有人喜欢跳舞,但不需知道这个人的名字,这时就可以用匿名变量。

3.结构

结构是PROLOG语言中的第三类数据结构;用于构造PROLOG数据对象。一个结构是一个单一的客体,它由一个函子和一个或多个称为分量的项的序列组成。其书写形式为

函子(分量1,分量2,…,分量n)

其中的分量也可以是结构。

例如可用结构描述事实"Mary住zhongshan路120号":

person(mary,address(zhongshan,120)).

此例中address是一个具有两个分量即路名和门牌号的结构。该结构是作为事实的一个分量出现,它将作为关系中的一个客体来对待。

当然,结构中的分量也可以是结构,如上例可写成:

person(name(mary),address(street(zhongshan),number(120))).

其中name,address,street,number均为结构。这样,该事实的表示更一目了然了。

在PROLOG语言中,常用的结构形式有:

(1)函子(分量1,分量2,...,分量n)。如上例Mary的住所。(2)表。表是PROLOG语言中最常用的数据结构,它由一些有序分量组成,其长度可任

意。有序即表示表中的分量次序是有意义的。同样,表的分量可以是原子、结构等,当然也可以是表。

例如含有3个分量a,b,c的表可写成[a,b,c]。如用函数的方式可写成.(a.(b.(c[])))。其中符号"."是表的函子,也就是说,表是以"."为函子的特殊结构。

(3)表达式。PROLOG语言提供了各种运算,如算术运算、比较运算等。PROLOG语言中的运算可以是中缀形式,简明直观,符合人们的习惯。

算术表达式X+Y&Z中,"+"、"&"便是运算符,该表达式如用函数结构形式来表示就是+(X&(YZ))。所以,表达式也是一种结构。

PROLOG语言提供了统一的数据结构--项(term)。在PROLOG中,无论是程序还是数据,都是由项构成。

项的定义为

::=|||“(”“)”

每一个项书写为一个字符串。

二.程序结构

PROLOG语言的程序结构非常简单,由三部分组成,即事实、规则和询问。

1.事实

事实用来说明有关客体及客体之间的相互关系。事实和规则都是逻辑推理的前提。

例如 John喜欢 Mary(John Like。Mary)。这是一个事实,它包含了两个客体 John和Mary及一个关系likes。用PROLOG语言的标准形式描写即为

likes(john,mary).

事实中的关系(如 likes)称为谓词,客体称为自变量。事实的语义是表示该语句恒为真。在PROLOG语言的标准形式中,谓词和确定的客体(常量)必须以小写字母开头,而变量客体用大写字母开头,客体间用逗号","分开,用一对圆括号括住,最后用“.”终结。

下面是一些事实的例子:

female(jane).ane是女性。

play(jane,mary,chess).ane和mary下棋。

关系中自变量的个数是任意的,而语句意义的解释由程序员所确定。如likes(john,mary),可解释成John喜欢Mary,也可解释成Mary喜欢John。因此解释一个谓词含义是完全由程序设计者决定的,但一经确定,就必须在整个程序中遵守。

事实的语法与结构相似。事实中的谓词对应于结构的函子,而事实中的自变量则对应于结构的分量。

2.规则

规则是关于客体及其关系的一般陈述,表明某些关系的成立要依赖于其他一些关系的成立。规则可以是事实的一种紧凑的表现形式。

自然语言中,用"如果"一词来说明规则。在PROLOG语言中,规则由规则头和规则体组成,其间用符号":-"连接。符号":-"表示"如果"。规则用"."结尾。例如"如果某人是学生,则john就喜欢该人"。用PROLOG语言书写应为

likes(john, X):-student(X).

表示如果student(X)成立,则likes(john)就成立。

PROLOG语言的规则的一般形式为

p:-p1,p2,p3,…,pn..

其中p1,…pn均为命题。在此,逗号","是合取(∧或并且)的意思。因此,规则的语义是:如果“p1∧p2∧…∧pn”为真,则p就为真,即规则头部就为真。

值得注意的是:在一条规则中,所有相同的变量代表了相同的客体,而在规则的不同次使用时,变量可以代表不同的客体。但规则的同一次使用中,对一变量的解释必须完全一致。

一个谓词可用一些事实和规则的组合来定义,称为谓词的子句。

可以把PROLOG程序看做是事实和规则的一个库,称为数据库或知识库。PROLOG系统的任务就是依据知识库中的知识(事实和规则的集合)来回答用户的问题。编写PROLOG程序,实际上就是提供所需要的事实和规则,PROLOG系统能使计算机去利用事实和规则及自身所带有的推理方法,从一些事实推理出另一些事实。

3.询问

PROLOG语言是一种可会话式语言。执行一个PROLOG程序实际上就是进行人机对话,在将事实和规则存人数据库或知识库中后,就可以向系统询问一些有关的问题,而问题就是系统求解的目标。

例如设有数据库:

likes(mary,wine).

likes(john,meat).

likes(john,X):-likes(mary,X).

就可以询问:"Mary喜欢葡萄酒吗?"或"John喜欢什么?"

PROLOC语言的询问的一般形式为

?- p1,p2,…,pn..

其中"?-"是PROLOG语言询问的特殊符号,p1,p,…pn的意义与规则中的意义相同。询问的语义是:“p1∧p2∧…∧pn”是为真吗?"。

因此,上面的"Mary喜欢葡萄酒吗?"或"John喜欢什么?"询问可分别写为:

?-likes(mar,wine).

?-ikes(john,X).

于是,PROLOG系统将根据数据库或知识库中的事实和规则进行推演来回答用户的问题。

三. PROLOG语言的内部谓词

内部谓词是由PROLOG系统预先提供的,而不是由编程者自定义的谓词。它们提供了无法靠程序来定义的功能,为用户提供常用的谓词。编程时可不加定义地直接利用这些谓词,因而为程序设计提供了便利。此外,内部谓词由系统实现,因此它们有很高的执行效率。PROLOG语言有着较为丰富的系统内部谓词,由于篇幅所限只是粗略地按类介绍。文中所提到例化是指一个变量去代表某个确定的客体。

1 比较类

比较谓词类是具有两个自变量中缀形式的内部谓词,结果为True或False。比较谓词有:

X=Y等于

X\=Y不等于

X

X>Y大于

X<=Y小于等于

X>=Y大于等于

X==Y强等于

这些谓词的自变量可以是被例化为整数的变量,也可以是以常量形式出现的整数。其中=、\=和==不仅是对整数而言,其自变量也可以是任何结构。

2 表达式类

PROLOG语言提供的表达式求值和建立表达式的内部谓词如下:

X is Y

(Y可被例化为表达式。该谓词首先对Y求值,得出一整数。如X未例化,则X例化为这一结果,且目标成功;否则,如X已例化,则"is"退化为"="来判断成功与否。)

X+Y加法运算。求值时自变量必须例化。

X-Y减法运算。求值时自变量必须例化。

X*Y乘法运算。求值时自变量必须例化。

X/Y整除法运算。求值时自变量必须例化。

X mod Y取模运算。求值时自变量必须例化。

可进行整数或实数求值。运算的优先级是:+、-(正负号),mod(取模),*、/(乘除),+、-(加减)。

3 输入输出类

PROLOG语言的输入输出类(I/O)谓词是系统从输入流输入一个项、一个字符或一个文件,或把一个项、一个字符或一个文件输出到输出流。它们仅仅是功能性的,即仅完成一项动作。

(l)geto(X)。如 X与输入流中的下一个字符匹配,则目标成功。

(2)get(X)。如 X与输入流中的下一个打印字符匹配,则目标成功。

(3)skip(X)。读入并跳过当前输入流中的字符,直到找到一个可与X匹配的字符。

(4)read(X)。读入当前输入流的下一个项,并使之与X匹配。

(5)put(X)。把整数X输出到当前输出流(X必须例化)。(6)nl。对当前输出流输出控制符"回车换行"。

(7)write(X)。把项X输出到当前输出流。

(8) writeq(X)。与write(X)相似。

4 控制谓词类

(1)true。该目标永远成功。

(2)fail。该目标永远失败。使用fail可以强制回溯,从而得到问题的所有解。

(3)!(cut)。截断谓词!是PROLOG语言控制搜索过程的一个非常重要的内部谓词,它允许程序员告诉PROLOG系统,当对已满足的目标的链进行回溯时,前面的那些选择不需要重新考虑。

截断谓词! 的含义是:作为一个目标,它直接成功,但当回溯到它时,不能重新被满足,并使其双亲目标(触发含有!的子句的目标)立即失败。即穿过"“!”的回溯是不可能的。

5表处理

表是PROLOG中一种非常有用的数据结构。表的表述能力很强,数字中的序列、集合,通常语言中的数组、记录等均可用表来表示、表的最大特点是其长度不固定,在程序的运行过程中可动态地变化。具体来讲,就是在程序运行时,可对表施行一些操作,如给表中添加一个元素,或从中删除一个元素,或者将两个表合并为一个表等等。用表还可以方便地构造堆栈、队列、链表、树等动态数据结构。

表还有一个重要特点,就是它可分为头和尾两部分。表头是表中第一个元素,而表尾是表中除第一个元素外的其余元素按原来顺序组成的表。例如下面的例子:

表 表头 表尾

[1,2,3,4,5] 1 [2,3,4,5]

[apple,orange,banana] apple [orange,banana]

[[a,b],[c],[d,e]] [a,b] [[c],[d,e]]

[“PROLOG”] “PROLOG” [ ]

[ ] 无定义 无定义

在程序中是用竖线"|"来区分表头和表尾的,而且还可以使用变量。例如一般地用[H|T]来表示一个表,其中H、T都是变量,H为表头,T为表尾。注意,此处H是一个元素(表中第一个元素),而T则是一个表(除第一个元素外的表中其余元素按原来顺序组成的表)。表的这种表示法很有用,它为表的操作提供了极大的方便。下面我们就给出用这种表示法通过匹配合一提取表头和表尾的例子。

表1 表2 合一后的变量值

[X|Y] [a,b,c] X=a,Y=[b,c]

[X|Y] [a] X=a,y=[]

[a|Y] [X,b] [a,b] X=a,Y=[b]

还需说明的是,表中的竖杠"|"后面只能有一个变量。例如写法[X|Y,Z]就是错误的。