逻辑编程语言Prolog基础

什么是Prolog?

我们先给出一个例子.

man(jack). 
man(dylan).
happy(jack). 
playGuitar(jack) :- happy(jack).

运行:

?- man(jack).

Prolog回答:

yes

再运行:

?- playGuitar(jack).

Prolog回答同样是:

yes

上面的例子展示的就是Prolog程序和它的运行以及运行结果. 第一个运行结果的含义是: Jack是男性. 第二个运行结果的含义是: Jack在弹吉他.

Prolog是一种基于模式匹配,树型结构和自动回溯等机制的面向目标的编程语言。这几个机制构成了灵活而强大的编程框架. Prolog尤其适用于包含结构化对象以及这些对象之间的关系的问题. 例如,Prolog可以依据空间关系和一般规则进行推理. 所以,对于人工智能和非数值编程,Prolog是一种强大的语言。字面上看,Prolog意思是以逻辑(logic)编程. 此观念来自于20世纪70年代初期。早期开发者有Robert Kowalski, Maarten Van Emden 和Alain Colmeraner.

在低级编程语言中,程序员往往指定计算机如何做一件事(How型语言). 在高级编程语言中,程序员给计算机指定需要做什么. 编程语言是从低级向高级演化的. Fortran, C, Lisp,Python,Java等几乎所有语言都属于How型语言. 相反地,Prolog舍弃了“指定计算机如何做事”这样的传统. 它鼓励程序员描述问题,而不是描述解决问题的详尽的方式. Prolog为我们提供了另外一种编程的方式. 它背后的科学是人工智能. 我们可以从中学习到一些解决问题的观念,比如问题化简,回溯链,各种搜索技术等. Prolog可以让我们将抽象概念具体化. 编程者只需要指定什么是已知的,什么问题需要解决,即编程人员更关注事实而不是算法.

Prolog语法

Prolog程序由语句(clauses)构成. 语句又由对象和关系构成. 例如,上例中的

man(jack).

man就是一种关系,它可以指明对象的性别; jack就是该关系中的对象. 运行Prolog程序的方式很简单: 向程序提问. 语法如下:

?- 关系表达式.

其中, ?- 是提示符. 后面有个结束符(.). 例如:

?- happy(jack).

写语句时,常需要用到符号”:-”.

:- 表示”如果”,或“蕴含于”. 例如:

playGuitar(jack) :- happy(jack)

上面代码的意思是:如果Jack高兴,那么Jack就要弹吉他. :- 的右边叫主体; :- 的左边叫规则头.

下面我们通过一个例子来看Prolog的机制,从中可见多个重要的概念. 例如, 甲(a)是乙(b)的父母,可写为:

parent(a,b).

parent是关系名称; a,b 是该关系的参量.

Prolog举例

下面我们以中国近代著名的家庭义宁陈宝箴家的家谱为例,来看看Prolog的运行机制. 家谱如下:


在以下代码中,我们将人名用其拼音首字母的小写代替. 人名和拼音首字母的对应如下: 在以下代码中,我们将人名用其拼音首字母的小写代替. 人名和拼音首字母的对应如下:

陈宝箴 cbz
黄淑贞 hsz
陈三立 csl  
陈三畏 csw
陈师曾 csz 
陈寅恪 cyk
陈封怀 cfh

整个家谱由下列Prolog程序给出: 整个家谱由下列Prolog程序给出:

parent(cbz,csl).
parent(hsz,csl).
parent(hsz,csw).
parent(csl,cyk).
parent(csl,csz).
parent(csz,cfh).

此程序包含6个语句. 每个语句声明了一个parent关系. 当此程序与Prolog系统交互时,Prolog就parent这一关系提问. 例如,陈三立是陈寅恪的父母吗?实现代码如下:

?- parent(csl,cyk).

当prolog发现这是一个已经声明的事实,因此Prolog会给出答案:

yes

我们也可问程序:“陈三畏是陈师曾的父母吗?”

?- parent(csw,csz).

prolog回答:

no

因为程序并未提及陈三畏是否为陈师曾父母.

当然我们也可问:“黄淑贞是Alice的父母吗?”

?- parent(hsz,alice).

Prolog不会判断Alice是中国人名还是外国人名. Prolog仅仅从程序中的关系来做判断. 因为并未听过”ALice”这个人,因此它果断给出结果:

no

但是,如果我们问“谁是陈三畏的父母?”这样的问题时,Prolog确实可以给出我们一个值,而不仅仅是yes或no.

?- parent(X,csw).

Prolog给出的回答是

X = hsz

同理,我们可以问:”谁是陈三立的子女?“

?- parent(csl,X).

输出结果为:

X = csz

这里,我们只得到一个回答. 可是,从家谱中给我们可以发现看到陈三立的子女不止一个,所以我们期待能看到所有的结果的操作. 这时,我们输入一个分号,那么Prolog就会给出其余的答案:

X = cyk

由于上图中没有给出陈三立更多子女的信息,所以,如果我们试图知道更多答案,Prolog会回答“no”.

考虑一个更复杂的情形. 我们可以问诸如”谁是谁的父母?”这样的问题. 提炼一下该问题,它就变为:找出X,Y,使得X是Y的父母. 用Prolog表示为:

?- parent(X,Y).

Prolog会找出所有的”父母-子女“对.  Prolog一次只显示一个解,直到所有的解被找出. 结果如下:

X = cbz
Y = csl;

X = hsz
Y = csl;

X = hsz
Y = csw;

X = csl
Y = csz;

...

我们还可以问更加复杂的问题. 比如,”谁是陈封怀的祖父母?“ 这个关系我们命名为grandparent. 显然,我们的程序中没有grandparent这一关系. 虽如此,我们可以将这一问题的解决划分为两步. 第一步,谁是陈封怀的父母?设为Y. 第二步,谁是Y的父母?设为X. Prolog将这一复合问题写出两个简单语句序列:

?- parent(Y,cfh), parent(X,Y).

答案为:

X = csl
Y = csz

复合语句可以理解为:找出X,Y,使得这两个条件成立:parent(Y,cfh) 和parent(X,Y). 这两个条件的顺序并不重要, 所以这个复合问题也可以写成

?- parent(X,Y), parent(X,cfh).

而结果不会改变.

我们再举最后一例. 陈寅恪和陈师曾有共同的父母吗? 同样,我们可以由两步得出: 第一步,谁是陈寅恪的父母,设为X. 第二步,X是陈师曾的父母吗? 代码如下:

?- parent(X,cyk), parent(X,csz).

结果如下:

X = csl

从上面的例子中,我们看出了Prolog程序的一些特征。我们将它们分别列下:

  1. 在Prolog中定义关系非常简单. 关系往往用n-元组可以实现.
  2. 用户可以向Prolog程序中已经定义的关系提问.
  3. 每一个Prolog程序由从句构成. 每个语句由圆点(.)结束.
  4. 传入到关系里面的参量可以是具体对象,比如,csl, cyk等,也可以是X,Y这些抽象的对象. 具体对象在前者称为原子,而一般的抽象对象则称为变量.
  5. 向Prolog的提问可以包括一个或多个目标(在Prolog中,目标即问题),如 “parent(X,cyk), parent(X,csz)”表示两个目标的连接,其意思是: X是cyk的父母,X也是csz的父母.
  6. Prolog对一个问题的回答可正可负,这要看问题是否得到满足. 若回答为正,则称响应的目标是可满足的(satisfiable),反之,则称该问题是不可满足的.
  7. 如果有多个答案同时满足目标,Prolog会按用户的意愿显示出答案.

参考文献:

Richard O’Keefe, The craft of prolog.

lisp介绍: http://www.gigamonkeys.com/book/introduction-why-lisp.html

David Gries, The science of programming.

Edsger W. Dijkstra, A discipline of programming.

“逻辑编程语言Prolog基础”的一个回复

发表评论

电子邮件地址不会被公开。