第六章 Prolog语言一章 下一章  返回人工智能教学主页

 本章学习重点

无论是问题和系统的任务描述或是知识经验的表示以至推理决策,都离不开智能语言。因此,研究和使用智能语言是人工智能的中心任务之一。对于同一问题的编程可以 使用多种不同的语言、有多种不同的方法实现。Prolog语言是人工智能中使用最普遍的语言,本章将对其进行介绍。

6.1 PROLOG语言概述
6.2 PROLOG语言的结构
6.3 PROLOG的内部谓词
6.4 PROLOG语言的搜索策略
6.5 谓词!的讨论
6.6
PROLOG程序设计
6.7 PROLOG语言与C语言的连接
6.8 Visual Prolog的程序结构

工 具:Prolog Z 1.0Amzi! Prolog 6.1Prolog 2.0Visual Prolog 5.2 
Clips 6.0Lisp works 4.1
写字版绘图板DOS状态

6.1 PROLOG语言概述 下一节

6.1.1 PROLOG语言的发展

PROLOG(programming in Logic)语言是、种以逻辑推理为基础的逻辑型程序设计语言。它是陈述性语言而不是过程性语言。它的思想最早(20世纪70年代初)在英国爱丁堡大学由R. Kowalski首先提出,并由  M.Van Emden作了模型示范。1972年,Alain Colmeraner及其研究小组在法国马塞大学研制成功了第一个PROLOG系统。1977年,英国爱丁堡大学的D Warren开发了 DEC-10 PROLOG语言,使之进一步完善。

  虽然一直想把PROLOG语言移植到个人计算机,但无论哪个个人计算机版的PROLOG语言都离真正的PROLOG语言相差太大,而丘执行速度相当慢。

  然而, 1986年美国的 Borland International公司向个人计算机软件市场推出了TURBO PROLOG软件,形势急转,受到了个人计算机用户的欢迎。

  随后,TURBO PROLOG语言相配套的 TURBO PROLOG Toolbox也开发出来了。它使TURBO PROLOG用起来更便利。现在,PROLOG语言已广泛应用于符号计算的许多应用场合,其中包括关系数据库、专家系统、数理逻辑、抽象问题求解、定理证明和语义学、自然语言理解、结构设计、位置规划和逻辑学、符号方程解决、编译程序编制、生物化学结构、生理学分析和药物设计,涉及了许多人工智能领域。

6.1.2 PROLOG语言的特点

  作为一种程序设计语言,PROLOG语言无论是它描述求解问题的方式,还是其语言本身都与一般的程序设计语言有很大的差别。

  大家都很熟悉,用一般的程序设计语言, FORTRAN、C甚至 VB、C++等来解问题时需要指明算法,即对一给定的问题要规定一系列计算机执行的计算步骤,告诉计算机"如何做"。而PROLOG语言求解问题时,要求程序员描述所解问题中的对象和反映它们之间关系的某些已知事实,描述和定义各对象和它们之间关系的某些规则。它强调描述对象(和事实)之间的逻辑关系,程序员一般不必要告诉计算机运算执行的先后次序。因此,从只须描述问题本身,而不必描述求解问题的详细计算步骤这一点上来说,PROLOG语言是更高级的语言。

  PROLOG语言是一种不寻常但又非常简单的语言。刚学习PROLOG语言的人会发现编

PROLOO程序的方式与用一般的程序语言说明一个算法不同。使用PROLOG语言的程序员对要解决的问题将考虑两个方面:在问题中会出现什么形式的事实和关系?与回答有关的哪些关系为真?

  PROLOG语言所用的方法是规定与问题有关的已知事实和关系,并无必要把问题的解看成是一步接着一步的指令序列。实际上,当在计算机上采用PROLOG语言编写程序时,计算机如何进行计算,从某种程度上取决于PROLOG语句中所固有的逻辑关系和从给定的事实中可以推论出来的新事实,以及由使用者提供的直接的控制信息。

  PROLOG语言提供一种统一的被称为“项”的数据结构。不但所有的数据,而且PROLOG程序都是由项构成的。PROLOG程序由一组子句组成,其子句或者表示关于给定信息的事实,或者表示规则。规则说明问题的解与给定事实如何相关,或者说明如何从给定事实中推论出解。因此,可以把使用PROLOG语言看成是朝着按逻辑编写程序的最终目标前进的第一步。

  PROLOG语言有下面的特点:

(1)PROLOG语刍是一种描述语言,用 PROIDC语言求解问题时,只须程序员描述待解问题中的对象及它们之间关系的一些已知事实和规则。它强调描述对象之问的逻辑关系,而不必告诉计算机运算执行的先后次序,即告诉计算机“做什么”,而不是像普通程序设计语言那样告诉计算机“如何做”。

(2)PROLOG语言的数据和程序结构统一,PROLOG语言提供了一种统一的数据结构,称为‘“项”。所有的程序和数据均由项构成,并且都是树型结构。

(3)PROLOG语言能够自动实现模式匹配和回溯。这些是人工智能系统中常用的基本操作、用户在PROI0C语言这一级上不必考虑这个问题。

(4)递归是PROLOG语言的重要特点之一。由于这一特点,一个大的数据结构常常能由一小的程序来处理。

(5)语法简明。PROlOG语言仅有下种句型,语法规则比较简单。

返回本节开头 返回本章开头

6.2 PROLOG语言的结构 上一节 下一节 

6.2.1 数据结构

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

1.常量

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

  在PROLOG语言中,合法的常量有:

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

(2)原子,分为两种:

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

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

(3)字符集AB…Z
        ab...z
        0123456789
        ?”#$≠&’()=_~^\}[],{-@+;*<>

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中,无论是程序还是数据,都是由项构成。

  项的定义为

<项>::=<常量>|<变量>|<结构>|“(”<项>“)”

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

6.2.2 程序结构

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

1.事实

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

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

 likes(john,mary).

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

  下面是一些事实的例子:

female(jane).           jane是女性。

play(jane,mary,chess).    jane和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系统将根据数据库或知识库中的事实和规则进行推演来回答用户的问题。

返回本节开头 返回本章开头

6.3 PROLOG语言的内部谓词 上一节 下一节

内部谓词是由PROLOG系统预先提供的,而不是由编程者自定义的谓词。它们提供了无法靠程序来定义的功能,为用户提供常用的谓词。编程时可不加定义地直接利用这些谓词,因而为程序设计提供了便利。此外,内部谓词由系统实现,因此它们有很高的执行效率。

  PROLOG语言有着较为丰富的系统内部谓词,由于篇幅所限只是粗略地按类介绍。文中所提到例化是指一个变量去代表某个确定的客体。

6.3.1 比较类

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

        X=Y    等于

        X\=Y   不等于

        X<Y    小于

        X>Y    大于

        X<=Y   小于等于

        X>=Y   大于等于

        X==Y   强等于

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

6.3.2 表达式类

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

        X is Y

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

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

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

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

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

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

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

6.3.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)tab(X)。输出X个空格符到当前输出流(X必须例化)。

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

    (9)display(X)。与write(X)相似,只是它忽略运算符说明,以结构形式输出项。

    (10)op(X,Y,Z)。说明名为Z的运算符,其优先级为X,结合规则为Y。

6.3.4 文件操作类

  PROLOG语言提供的改变当前输入流、输出流的谓词如下:

    (l)see(X)。打开目标文件X,并以文件X为当前输入流。如X为变量或以X为名的文件不存在,则出错。

    (2)seeing(X)。如X为变量,X被例化为当前输入流;X已例化,X与当前输入流匹配时,目标成功。

    (3)seen。关闭当前输入流;置当前输入流为键盘。

    (4)tell(X)。把X定义为当前输出流,打开文件X。如X未例化,则出错。

    (5)telling(X)。如 X为变量, X被例化为当前输出流; X已例化, X与当前输出流匹配时,目标成功。

    (6)told。关闭当前输出流,并在文件尾加上结束标志;置当前输出流为显示器。

6.3.5 控制谓词类

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

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

    (3)repeat。repeat提供了通过回溯来得到多个解的一种方法。它可用PROLOG语言来定义如下:

          repeat.

          repeat:-repeat

    repeat在回溯中总使目标成功,它和fail连用可产生循环。

    例goal:-repeat,write('a'),fail。

        ?-goal.

    执行这个目标的结果是输出aaaa…。这是因为遇到repeat时目标成功,向下执行write(‘a')遇到fail,失败引起回溯。回溯到repeat时又使目标成功,从而产生无限循环的结果。

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

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

  截断谓词!的副作用是改变了以后的回溯线路。这样,对于那些程序员能预先知道的、无助于解决问题的目标,就不须再浪费时间去满足它,从而使程序运行速度加快。同时,由于不须为下次检查记录回溯点,也节约了内存空间。

见实例Visual Prolog实例ch04e07.proch04e08.pro

6.3.6 复杂目标类

(1)call(X)。X被例化为一个定义为目标的项,如果X成功,call(X)成功;如果X失败,call(X)失败。

    使用call可以在编制程序时,调用还未知的目标函子。

(2)not(X)。将X看做一个目标,X失败,not(X)失败。

    谓词not(X)可用!fail来定义:

        not(X):-call(X),!,fail.

        not(X).

见实例Visual Prolog实例ch04e10.pro,ch04e11.pro

(3)X,Y。谓词中,”是“并且”的意义。设X,Y均为目标,X和Y都成功,则谓词X,Y才成功;X成功,Y失败,则回溯,试图重新满足X,X又失败,则整个目标谓词X,Y失败。

(4)X;Y。谓词中;”是“或”的意义。设X,Y均为目标,X或Y成功,则谓词X,Y成功;X和Y均失败时,谓词X;Y才失败。

6.3.7 项 类

(1)var(X)。当X为一未例化的变量,var(X)为True。

(2)nonvar(X)。当X不是未例化变量时,nonvar(X)为False。

(3)atom(X)。当X为原子时,目标atom(X)成功。

(4)integer(X)。当X代表一个整数,则目标成功。

(5)atomic(X)。当X为一个原子或一个整数时,则目标成功。

6.3.8 结构分五类

(1)functor(T,F,N)。该谓词表示T是一个以F为函子、有N个分量的结构。

    例:?-functor([a,b,c],F,N).

        f=., n=2

        注:.表示表运算。

      ②?-functor(T,likes,2).

        T=likes(_23,_24)

        注:已建立了一个有关likes的一般结构; _23和_24表示变量的号码。

(2)arg(N,T,A)。如果T的第N个分量是A,则目标成功。使用时,N和T必须为已例化变量。

   例:?-arg(2,likes(mary,mother(jane)),X).

        X=mother(jane)

      ②?-arg(3,[a,b,c],X).

        no

(3)X=..L。该谓词表示L是由结构X的函子及分量构成的表。

   例:?-[a,b,c,d]=..L.

        L=[".",a,[b,c,d]]

      ②?-X=..[likes,mary,john].

        X=likes(mary,john)

(4)name(A,L)。该谓同表示L由组成A的字符(ASCll码表示)构成。

    例如,?-name(abc,X).

        X=[97,98,99]

    其中97,98,99是字符a,b,c的ASCll码值。

    又如,?-name(X,[97,98,99]).

            X=abc

        ?-name(abc,"abc").

            Yes

6.3.9 项维护类

(1)consult(X)。把文件X中的所有项加到数据库的末尾。要求X必须是一基本字串--原子,它表示一个文件名。

(2)reconsult(X)。reconsult(X)把从文件X上读入的项取代原来数据库中具有相同谓词名的项,可用以修正程序的错误。同样地,X必须是一原子,它表示一文件名。

(3)asserta(X)。asserta(X)把子句X加入到数据库中,放在与X具有相同谓词和变量数的项之前。X必须例化为一个项。

(4)assertz(X)。assertz(X)与asserta(X)基本相同,所不同的是把加入的项放在与X具有相同谓词和变量数的项之后。同样地,X也必须例化为一个项。

(5)retract(X)。retract(X)删除数据库中第一个与X匹配的项。为了确定被删除的项,X须充分例化。当试图重新满足该目标时,则从被删除项处开始继续寻找下一个与X匹配的项,如找到,则删除;如无匹配的项,则目标失败。

(6)retractall(X)。retractall(X)是删除数据库中所有与X匹配(头匹配)的项。利用retract(X)可将retractall(X)定义为

retractall(X):-retract(X),fail.         仅删除事实

retractall(X):-etract((X:-Y)),fail.   可删除规则

(7)listing(A)。A例化为一原子。该目标满足时,将数据库中所有以该原子为谓词的项输出到当前输出流。

(8)clause(X,Y)。满足目标clause(X,Y)即使得X和Y分别与数据库中一规则的头和体

匹配。使用时,X必须已例化及已知规则的主要谓词,如无该谓词的规则,则目标失败;如不止一个规则满足,则首先匹配第一个规则,当重新满足该目标时,再继续与下面的规则依次匹配。

    下面是一个说明。 clause(X,Y)应用的例子。

        member(X,[X|_]).

        member(X,[_|Y]):-member(X,Y).

        ?clause(member(A,B),C).

        A=_23,B=[_23|-],C=true      与事实匹配时,Y为 true

        A=_23,B=[_|_24],C=member(_23,_24)

6.3.10表处理

  表是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]来表示一个表,其中HT都是变量,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]   X=a,Y=b,Z=c
[[a,Y]|Z] [[X,b],[c]] X=a,Y=b,Z=[[C]]

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

  但竖杠的前面的变量可以多于一个。例如写法[X,Y|Z]是允许的。

  这样,这个表同[a,b,c]匹配合一后,

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

  另外,竖杠的前面和后面也可以是常量,例如[a|Y][X|b]都是允许的,但注意,后一个表称为无尾表,如果它同表[a|Y]匹配,则有

X=a,Y=b(而不是Y=[b])

如果无竖杠"|",则不能分离出表尾。例如,[X,Y,Z][a,b,c]合一后得X=a,Y=b,Z=c。其中变量Z并非等于[c]

  下面给出关于表的两个最常用的程序。

设计一个能判断对象X是表L的成员的程序。

我们可以这样设想:

(1)如果X与表L中的第一个元素(即表头)是同一个对象,X就是L的成员;

(2)如果XL的尾部的成员,X也就是L的成员。

根据这种逻辑关系.于是有下面的PROLOG程序:

member(X,[X|Tail]).

member(X,[Head|Tail]):-member(X,Tail).

其中第一个子句的语义就是上面的第一句话,第二个子句的语义就是上面的第二句话。可以看出,这个程序中使用了递归技术,因为谓词member的定义中又含有它自身。利用这个程序我们就可以判定任意给定的一个对象和一个表之间是否具有member(成员)关系。例如,我们取表L[a,b,c,d),Xa,对上面的程序提出如下询问:

goal:-member(a,[a,b,c,d]).

则有回答:yes

同样对于询间:

goal:-member(b,[a,b,c,d]).

goal:-member(c,[a,b,c,d]).

goal:-member(d,[a,b,c,d]).

都有回答:yes

但若询问

goal:-member(e,[a,b,c,d]).

则回答:no

如果我们这样询问

goal:-member(X,[a,b,c,d]).

意思是要证明存在这样的X,它是该表的成员,这时系统返回X的值,

X=a

如果需要的话,系统还会给出X的其他所有值。

表的拼接程序,即把两个表连接成一个表。

append([ ],L,L).

append([H|T],L2,[H|Tn]):-append(T,L2,Tn).

程序中第一个子句的意思是空表同任一表L拼接的结果仍为表L;M个子句的意思是说,一个非空的表L1与另一个表L2拼接的结果L3是这样一个表,它的头是L1的头,它的尾是由L1的尾TL2拼接的结果Tn。这个程序刻划了两个表与它们的拼接表之间的逻辑关系。

  可以看出,谓词append是递归定义的,子句append([ ],L,L).为终结条件,即递归出口。

  对于这个程序,如果我们询问

goal:-append([1,2,3],[4,5],L).

则系统便三次递归调用程序中的第二个子句,最后从第一个子句终止,然后反向依次求出每次的拼接表,最后输出

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

当然,对于这个程序也可以给出其他各种询问,:

Geal:-append([1,2,3],[4,5],[1,2,3,4,5]).

系统回答:yes

goal:-append([1,2,3],[4,5],[1,2,3,4,5,6]).

系统回答:no

goal:-append([1,2,3],Y,[1,2,3,4,5]).

系统回答:Y=[4,5]

goal:-append(X,[4,5],[1,2,3,4,5]).

系统回答:X=[l,2,3]

goal:-append(X,Y,[1,2,3,4,5]).

系统回答:

X=[],Y=[1,2,3,4,5]

X=[1],Y=[2,3,4,5]

X=[1,2],Y=[3,4,5]

X=[l,2,3],Y=[4,5]

等等(如果需要所有解的话)

  从上例可以看出,PROLOG具有递归机制。递归技术在表处理中特别有用,几乎所有的表处理程序都要用到递归。但在一般程序中,使用速归却要谨慎,或者应尽量不用递归,而用迭代循环。因为递归很容易导致堆栈溢出。

表的输出。

print([]).

print([H|T]):-write(H),print(T).

表的倒置,即求一个表的逆序表。

reverse([],[]).

reverse([H|T],L):-reverse(T,L1),append(L1,[H],L).

这里,reverse的第一个项是输入,即原表,第二个项是输出,即原表的倒置。

返回本节开头

6.4 PROLOG语言的搜索策略 上一节 下一节

  在6.1节已介绍 PROLOG语言是一种描述性的语言。用 PROLOG语言进行程序设计时,程序员只须描述待解问题中的有关事物及它们之间关系的已知事实和规则,也就是只须告诉计算机"做什么",而不须指出"如何做"。这是因为PROLOG系统具有模式匹配、回溯等自动搜索功能。因此,当用户建立了数据库或知识库后,就可以直接向PROLOG系统询间有关问题。PROLOG系统靠自身的模式匹配和回溯等功能来自动搜索目标,从而来回答用户的问题。本节将介绍PROLOG的自动搜索功能。

6.4.1 例化与匹配

  在讨论PROLOG语言的搜索方法之前,先来了解例化、解脱、匹配等几个重要的概念。下面通过例子来描述这些概念。

  设有知识库

      play(mary,swim).

      play(mary,tennis).

      play(john,tennis).

      play(john,football).

  询间?-play(mary,swim).

  PROLOG系统将询问作为一个目标,检查是否有知识能满足目标。PROLOG系统将搜索知识库,寻找与问题目标相匹配的项。

  所谓匹配的含义是:

    (1)一个未例化变量可与任何客体匹配。例化结果是该变量代表可匹配的客体。

    (2)一个常量只能与自己匹配。

    (3)如两个函子一致,且分量个数相等,当对应分量均相匹配时,则这两个结构可匹配。

    (4)两事实匹配是它们的谓词相同且对应自变量相匹配。

    (5)与规则匹配实际上只是与规则的头匹配,而规则头的匹配则与事实匹配相同。

其中例化的含义是:一个变量已例化,表示该变量已代表了某个确定的客体;而一个变量未例化,则表示该变量在某一时刻尚未代表某个确定的客体。

  开始使用子句项时,所有的变量都是未例化的。

  上面例的?-play(mary,swim)询问问题中不含变量。对该询问,PROLOG系统为满足该目标,从知识库的第一项开始搜索。根据匹配原则能与第一个事实 play(mary,swim)相匹配,因此,该问题得到满足,于是PROLOG系统便回答yes。

  若询问问题?-play(john,X),此时X是一个未例化的变量。对此,PROLOG系统同样搜索知识库。问题首先与第三个事实play(john,tennis)匹配,则目标满足,于是X被例化为tennis,PROLOG系统便可回答X=tennis,并在知识库的此处做一标记。用户输入有";"表示继续求解,这时PROLOG系统从知识库标记处再继续向下搜索(同时应将X解脱--使X恢复成未例化的变量)。问题又与第四个事实play(john,football)匹配,此时目标再一次满足,X又被例化为football,标记则被移到此处,PROLOG系统便可回答X=football。假如再输入";"继续求解,PROLOG系统又从标记处开始搜索。可以看出此时已没有可匹配的事实,因此,PROLOG系统就回答no。

6.4.2 回溯控制

  回溯是PROLOG语言的一个很重要的基本操作。PROLOG系统重复地试图满足和重新满足询问问题及其派生的目标就是回溯。PROLOG系统能自动地完成回溯功能,下面仍通过例子来理解PROLOG语言的回溯控制。

  设有知识库

        play(mary,swim).             ①

        play(mary,tennis).           ②

        play(john,tennis).           ③

        play(john,football).         ④

  询问?-play(mary,X),play(john,X).

  这是一个带有连接同","的询问。前面已说过,","""合取的意思,因此要满足整个目标,必须分别满足play(mary,X)和play(john,X)这两个子目标。

  下面给出PROLOG系统搜索的过程,注意回溯步骤。

(1)试图满足子目标play(mary,X),X是未例化变量。PROLOG系统搜索知识库,与子句①匹配,于是,该子目标成功,X被例化为swim,同时在子句①处做标记。做标记的目的是当需重新满足该目标时,PROLOG系统将控制从此标记处开始搜索。

(2)由于X已例化为swim,因此第二个子目标为play(john,swim)。现试图满足该子目标。PROLOG系统搜索知识库,不存在与此目标相匹配的子句,因此此目标失败。

(3)当后一个目标失败后,必须重新试图满足前一个目标。由于对play(john,swim)失败,于是PROLOG系统试图重新满足前一个目标play(mary,X)。系统可控制从标记处—子句①开始搜索,同时X被解脱,重新成为未例化变量,这就是回溯。

(4)PROLOG系统从子句①以后搜索。目标play(mary,X)与事实play(mary,tennis)匹

,于是目标又成功,X被例化成tennis,同时在子句②处做标记以便回溯时使用。

(5)PROLOG系统又转向第二个目标进行搜索。由于X被例化为tennis,只需满足目标play(john,tennis)。注意,这里PROLOG系统并不是重新满足,而是再次进入第二个目标(在询问中是从左到右的,而回溯则是从右到左)。因此,搜索从知识库的第一行开始。这次找到了匹配的事实--子句③,目标成功。由于第二个目标满足了,PROLOG系统也在子句③处做一标记。注意,子句②和子句③两处的标记是不同的,因为PROLOG系统要在可与任何一个(子)目标满足的子句(事实和规则)处做一标记。

(6)两个子目标都满足,则整个目标play(mary,X)∧play(johnJ)也就被满足了,X被例化为tennis。

  这样PROLOG系统为询问找到一个解:X=tennis。

  如果此时用户键入分号";"要求继续求解,结果会是怎样呢?

  ";"将引起回溯,试图重新满足第二个子目标play(john,tennis)。该子目标中没有其他无例化的变量(X是由第一个子目标例化的,不能在此解脱)。PROLOG系统将从子句③以后开始搜索,可以发现,再无匹配的事实,于是该目标失败,由此又引起回溯。PROLOG系统试图再重新满足第一个子目标play(mary,X)(PROLOG系统应在此解脱X),并从第一目标的标记(子句②)后开始搜索。可看出,不能找到匹配的事实,于是第一子目标也失败,因而整个目标也就失败。由于PROLOG系统找不到更多的解,因此系统只有回答no。

  整个PROLOG系统的搜索过程可见图6.1

6.1 PROLOG搜索过程示意

6.4.3 搜索策略

  搜索策略是PROLOG系统的核心。下面从图5.1的PROLOG搜索过程示意出发来讨论PROLOG语言的搜索策略。

  PROLOG系统对一个目标进行处理的步骤为:

(1)从左到右依次满足连接中的各子目标。

(2)对任何一个子目标,第一次搜索时,总是从知识库的顶即第一行子句开始。

    l)如直接可与事实匹配,则这一子目标成功,并完成在知识库中的可匹配事实处设置标记(回溯时用)及例化相应的变量。

    如与某规则的头可匹配,则设置标记并再从左到右设法满足该规则的体所描述的各子目标。

    2)没有任何事实或规则与之匹配,则该子目标失败。如有左邻,则试图重新满足左邻目标,即回溯;否则,系统便可结束搜索。

    3)回溯时,需恢复例化的变量即解脱,并从相应的标志以后开始搜索。

  下面仍通过例子来进一步解释PROLOG系统的搜索策略。

  例6.1 该例是上一节的例子的扩充。

        play(mary,swim).

        play(mary,tennis).

        play(john,tennis).

        play(john,football).

        diff(mary,john).

        likes(X,Y):-play(X,Z),play(Y,Z),diff(X,Y).

  询问:?- likes(mary,X).

  按照PROLOG系统的搜索策略,本例的处理步骤为:

(1)目标问题只能与仅有的规则的头likes匹配,因此规则中的X被倒化为mary。注意问题中的X和规则中的Y均未例化,这时,可称这两个变量为共享,因为这两个变量处于同一位置上。共享的含义是:一旦其中的一个变量被例化为某个明确的客体,则另一个也被例化为这一客体。

(2)当满足这一规则时,则可认为原来的目标被分解为规则的体即三个子目标。于是,应依次满足这三个子目标。

  首先需满足子目标play(mary,Z)。PROLOG系统从头开始搜索知识库,与第一个事实匹配,则该子目标成功,并做标记在第一个事实的子句上,Z被例化为swim。

(3)下一个子目标即是play(Y,swim)。同样地,从知识库的顶开始搜索,也与第一个事

实匹配,则该子目标被满足,并做标记,Y被例化为mary。

(4)再下一个子目标是diff(mary,mary)。该子目标失败;便引起回溯。系统试图重新满足前一个子目标play (Y,swim),Y被恢复成未例化变量。

(5)这次从知识库标记处开始搜索。在知识库中,找不到与之匹配的事实,因此子目标

play(,swim)失败,于是又引起回溯。系统试图重新满足第一个子目标play(mary,Z),Z被恢复成未例化变量。

(6)从知识库标记处开始搜索,该子目标可与第二个事实匹配,则该子目标又一次成功,并做标记,Z被例化为tennis。

(7)进入下一个子目标play(Y,tennis)(注意这是从左到右地搜索匹配,而不是回溯),从知识库的顶开始搜索。发现子目标与第三个事实匹配,则成功,Y被例化为john。

(8)再进入下一个子目标diff(mary,john),很明显,子目标满足。

(9)规则体的所有子目标均已成功,那么本规则即成功。因为问题中的X和规则中的Y共享,因此,X也被例化为john。最后,PROLOG系统给出答案X=john。

返回本节开头 返回本章开头

6.5 谓词!的讨论 上一节 下一节 

6.3.5节中介绍的一个控制谓词是截断谓词!。它是PROLOG语言控制搜索过程的一个非常重要的内部谓词,它能改变回溯的次序。利用它,将能使PROLOG系统的搜索朝着预想的方向进行。它是如此的重要,下面对谓词!作详细的讨论。

6.5.1 谓词!的作用

  在介绍!之前,先严格地归纳目标成功和失败的情况。

  一个目标成功,3种情况:

    (1)与一个事实匹配;

    (2)与一个规则的头匹配且该规则的体的所有子目标成功;

    (3)系统的内部谓词!执行成功。

  一个目标的失败,4种情况:

    (1)无子句可以匹配;

    (2)与一个规则的头匹配,但该规则的体执行失败;

    (3)系统的内部谓词执行失败;

    (4)一度执行成功,但而后在执行中发生回溯,又没有别的选择分枝。

  谓词!是一种能影响PROLOG回溯方式的专门机构。用户可以利用!来告诉PROLOG系统:当要回溯前面一串已满足的目标时,就不必再考虑那些目标的其他可选择分枝。因为用户能事先知道这种不必要的回溯对求解毫无意义。因此,PROLOG程序中合理地使用!具有两个优点:

    (1)PROLOG程序可以运行得更快,因为它将不会浪费时间去试图满足那些能事先知道不可能导致解答的目标;

    (2)程序可以占有较少的计算机存储空间,因为PROLOG系统不必为它以后的搜索去记录那些对求解毫无帮助的回溯点的信息。

  从语法上讲,在一规则中谓词!就好像是一个目标,它是没有变元的谓词。作为一个目标,它将立即成功,但不能被重新满足,其副作用是改变这以后的回溯方式。所谓不能被重新满足,是指当回溯到达这一目标时,不可能再找另一个满足目标的成功解。换句话说,企图再满足它时能引起立即失败。在给出具体例子说明谓词!的使用之前,先从直观的与或/树中来解释谓词!的作用。现假设有一棵与/或树,如图6.2所示。

  设在匹配子句1时,子目标g1匹配子句c1时成功,子目标g2匹配子句c4成功,谓词!也成功,但在满足子目标g4时失败。按照PROLOG的正常搜索方法,当子目标g4失败后,将引起回溯。如不存在谓词!,则首先要求子目标g2寻找另一个可能匹配成功的子句c5。如果g2失败,PROLOG回溯到子目标g1,对子句c2,c3进行匹配检验。现在因为有了谓词!,它表示相关目标不可重新被满足且立即失败,因此改变了回溯工作方式。PROLOG系统将不对c5,c3,c2作进一步的匹配检验,这就好像把虚线部分的枝条都已剪除了。由此产生从父目标(匹配子句1)到子目标g2之间的所有目标都不可重新满足。

 

6.2 PROLOG搜索的与/或树

  谓词!的作用主要有3个方面:

(1)确定某规则的使用

    例如r1:-a,b,!.

        r2:-:c.

r1,r2是同一谓词的两个子句,其中只有一个子句被选用。谓词!表示系统已为一特定的目标找到了合适的正确规则。在此谓词!的作用是让PROLOG在搜索时选取确定的规则。

(2)和谓词fail连用

    例如 al:-a,!,fail.

         r2:-b,!, fail.

         r3:c.

r1,r2,r3是同一谓词的三个子句,谓词!fail连用的含义是“对于给定的目标不用再求其他的解,目标肯定是失败了。”

  下面通过一些例子,来说明谓词!的使用方法。

6.5.2 用法及举例

  谓词!的第一种用法称为分情况选择,这种用法较为普遍。它是针对下列情况使用的:

        当情况1®做动作1

        当情况2®做动作2

        当情况n®做动作n

        否则®做动作 n+1

  样本写法将是:

        sample(case1,X,...):-!,action1(X,...).

        sample(case2,X,...):-!,action2(X,...).

        sample(casen,X,...):-!, actionn(X,...).

        sample(others, X,...):-catch_all_actionnl(X,...).

  这里谓词!确定了仅在分支情况中选择-种,不可能再有第二种。

  例6.2 这是一个求级数和的例子。定义谓词sum_to,使得目标sum_to(N,X)在N为一整数值时,X将被实例化为从1到N的和。如:

        ?-sum_to(5,X).

        X=15;注意这里打分号

        no

  因为1+2+3+4+5=15,所以X为15。显然这是递归程序。终结情况为N=1,否则先求出1到N-1之和,再加N。于是sum_to的程序为

        sum_to(1,1):-!.

        sum_to(N,Res):- N1 is N-1,sum_to(N1,Res1),Res is Res1+N.

  终结条件是N=l,此时答案也是l。第二个子句引入了另一个sum_to目标,这个新目标的第一个变元的值比原来小于1。如此递归下去,直至到达终结条件。注意,不能用sum to(N-l,Res1)来代替 N1 is N-1,sum_to(N1,Res1)。

  须说明这个例子为什么在第1个子句中用谓词!,这是因为,在对表的处理中,容易区分空表和非空表这两种情况。因此,在定义有关表运算的谓词时,只须提供空表和非空表两种不同模式的规则的头来分别处理就可以了。某对象能匹配空表就不会匹配非空表,反之亦然(即它们的交集为空)。但是对于数来说,并不容易区分。因为不可能指明一个子句,它只匹配不等于1的整数。于是这个求级数和的例子所采用的方法是:再提供一个含谓词!的子句来针对整数1的情况,而用变量来匹配其他情况。从PROLOG的搜索方式知道,对任一目标,系统首先试图匹配该目标谓词的第一个子句(这里是检查N=1?),如第一子句失败,则再试图匹配第二个子句等。对本例子的第二子句应只匹配不等于1的数。但问题在于第二子句也能匹配数值1。如果第一子句中不用谓词!,即写成:

        sum_to(1,1).

        sum_to(N,Res):-N1 is N-l,sum_to(N1,Res1), Res s Res1+N.

  当用户询问?-sum_to(1,X)时,第一次得到正确的解是X=1。但如果键入";"和回车换行后,PROLOG进行回溯重新选择子句匹配时,将找到第二子句,这就产生了错误。实际上这将引起无限运行,直到存储空间用完为止。在第一子句中有了谓词!,则对目标sum_to(1,X)只能成功一次,PROLOG系统决不会测试第二行的规则。

  这个例子说明,当程序员不能够通过指明规则头的不同模式来区别所有可能的情况时(交集不为空),则可以利用谓词!,PROLOG在搜索时选取确定的规则。这是谓词!的一种用法,称为确认一规则的选择。但上面sum_to谓词实际上是不完善的,因为对sum_to(M,S),M≥1时程序是可行的,而当M为小于1的整数时,也会出现无限运行的情况。为避免出现这种情况,可把sum_to改写成:

        sum_to(N,1):-(N<1;N=1),!.

        sum_to(N,R):-N1 is N-1,sum_to(N1,R1),R is R1+N.

  此时,如提供的N小于等于1,则选择第一子句。虽然对小于1的N会给出了不合理的结果,但系统不会出现无限运行的情况。

  谓词!的第二种用法是常与另一个内部谓词fail合用。谓词fail像内部谓词!一样没有变元。谓词fail作为一个目标总是失败并引起回溯。当谓词fal的前面是谓词!时,则由于谓同!的作用将改变正常的回溯方式,使匹配含该谓词!的规则的父目标立刻失败(因为从父目标到谓词!之间的所有目标均不可重新满足)。谓词!和谓词fail的组合使用,在实际应用中是很有用的。

  例6.3要描述一个人是很健壮的,其条件是:如他没有心脏病、没有肺病、又不是近视眼等等。也许程序员开始写出如下事实和规则:

heart_disease(wan_lin).
tuberculosis(wan_lin).
nearsight(wan_lin).

strong(X):-heart_disease(X),fail.
strong(X):-tuberculosis(X),fail.
strong(X):-nearsight(X),fail.
strons(X).

  第一规则试图说明,如果X是有心脏病的人,则匹配它的目标失败。同样地,第二、三规则说的是,X有肺病或近视眼,则他不是强壮的。而第四行的子句则企图说明,X没有诸疾病,则他是强壮的。很遗憾,上述程序是不正确的。假如询问:

?-strong(wan_lin).

且假设已存在一事实heart_disease(wan_lin),则本来希望询问中的目标匹配了第一规则后得到回答no。但由于匹配第一规则时,目标heart_disease(X)成功后接着遇到目标fail(它总是失败),于是引起回溯。这样造成PROLOG系统去匹配第二、三、四子句而最后因匹配了第四子句而告成功。肯定地,这是PROLOG系统的回溯功能所引起的结果。为了使PROLOG系统能停止这种不必要的回溯,可以用谓词!放在谓词fail之前来完成。于是本例的程序改写为:

        strong(X):-heart_disease(X),!,fail.

        strong(X):-tubeculosis(X),!,fail.

        strong(X):-nearsight(X),!,fail.

        strons(X).

  现在如询间?-strong(wan_lin),则该目标匹配第一规则后,因为谓词fail马上使之失败。又因为谓词!使得从父目标strong(wan_lin)到谓词!之间的所有目标都是不可重新满足的,因此PROLOG系统回答no。由此可见,因为谓同!和谓词fail的作用,改变了正常的回溯方式,提高了搜索速度。最后一条规则是匹配任何一个strong(X)目标,该目标已经过了它前面各种情况的排除后,才与最后一规则匹配,所以此人一定是健康的。这个例子中谓同!的用法也称做cut-fail组合用法或谓词!的排除型选择用法。

  谓词!的第三种用法是把谓词!放在产生器和测试器的后面。典型的模式是

        example(X):-generate(X),test(X),!

  产生器generate(X)不断地产生一些值,每产生一个值,测试器就立即测试该值是否满足条件。如不满足,则回溯到产生器,由产生器产生下一个值再测试,直至找到一个满足条件的解。此时执行到达谓词!,它指明已找到惟一需要的解,没有必要或不可能再找其他的解。

  例6.4利用加法和乘法来编写整数除程序。

is_integer(0).
is_integer(X):-is_integer(Y),X is Y+1.
divide(N1,N2,Result):- is_integer(Result),P1 is Result*N2,P2 is (Result+1)*N2,P1=< N1,P2>N1,!.

  这条规则利用谓词is_integer来不断产生整数,直到产生的数是N1整除N2的结果,所以is_integer用做产生器,而其他的目标则起着测试器作用。由于最后用了谓同!,因此对给定值N1和N2,divide(N1,N2,Result)只能对一个可能的值成功。虽然is_integer能够无限地产生许多候选的整数,不过一旦成功地找到解,谓词!就终结了任何可能的回溯。

  如询问:

        ?-divide(32,5,X).

          X=6;

          no

  因为6*5<= 32<7*5,这里谓词!的作用就是把父目标 divide(32,5,X)到谓词!之间的所有目标(包括is_integer(Result)、P1 is Result*N2、P2 is (Result+1)*N2、P1=<N1及P2>N1)的标志指针都去掉,使得它们不能被重新满足。因此,这种谓词!告诉PROLOG系统,已经找到惟一的正确的解,应当立即停止寻找另一解的任何企图,或者说终结一个产生和测试的序列。

  上面三个例子说明了谓词!的用法。谓词!的意义和作用在这三个例子中都是一样的,它使从谓词!到父目标之间的所有子目标都成为不可重新满足。

  谓词!主要用于3个地方:

 (1)要告诉PROLOG系统,它对一特定的目标已经找到了正确的规则。这是例62的情况,称为分情况选择。

 (2)要告诉PROLOG系统,应立即使一特定的目标失败,不必再试其他可能的选择。这是利用谓词!和谓词fail的组合来实现的。例6.3就属于这种的情况,称之为排除性选择。

 (3)要终结一个须通过回溯产生其他可选择的解。这时谓词!指明已找到惟一需要的解,没有必要或不可能再找其他的解。这就是例6.4的情况,称为单解性选择。

返回本节开头 返回本章开头

6.6 PROLOG程序设计 上一节 下一节

为了开拓视野,本节列出一些PROI刀G语言的应用举例。以这些例子为基础,能设计出具有实用价值的应用系统

6.6.1 数学函数

1.最大公约数

  谓词gcd是求两个正整数的最大公约数。如两个正指数X,Y的最大公约数是Z,则目标gcd(X,Y,Z)成功。

  算法1:每次从大的数中减去小的数,再求小的数与差的最大公约数,直到小的数为0。

gcd(0,X,X):-!.
gcd(X,0,X):-!.
gcd(X,Y,Z):-X>Y,U is X-Y,gcd(U,Y,Z),!.
gcd(X,Y,Z):-gcd(Y,X,Z).

算法2:辗转相除法。

        gcd(X,0,X):-!.

        gcd(X,Y,Z):-N is X mod Y,gcd(Y,N,Z).

2.最小公倍数

  谓词lcm是求两个正整数的最小公倍数。如两个正整数X,Y的最小公倍数是Z,则目标lcm(X,Y,Z)成功。

  算法:两个正整数的最小公倍数,是将两数相乘,再除以两数的最大公约数。

lcm(X,Y,Z):-gcd(X,Y,N),Z is X*Y/N.
gcd(X,0,X):-!.
gcd(X,Y,Z):-N is X mod Y,gcd(Y,N,Z).
 

3.Fibonacci(菲伯纳奇)数列

  Fibonacci数列为1,1,2,3,5,8,…。

  定义谓词fib,X为第N项Fibonacci数时,目标fib(N,X)成功。

  算法:仍采用递归定义。

        fib(0,1):-!.

        fib(1,1):-!.

        fib(N,X):-N1 is N-1,N2 is N-2,fib(N1,Z1),

                    fib(N2,Z2),X is Z1+Z2.

4.素数

  谓词prime是判断一给定的整数是否为素数。如给定整数N为素数,则目标prime(N)成功。

  算法1:逐个试验N(设为奇数)能否被3,5,7,,N-2整除,如不能被整除,N为素

数。可使用生成测试模式来测试N--逐个产生3,5,N,测试N能否被产生的整数整除。

        prime(2):-!.

        prime(N):-N<2,!,fail.

        prime(N):-is_prime(N,I).

        is_prime(N,I):-I is N mod 2,I=0,!,fail.

                        /* n为偶数,则跳过 */

        is-prime(N,I):-test(N,I),I=N.

      /* test(N,I)完成生成和测试。如N能被某个奇数整除且这个整数为它自己(即I=N),则表示N为素数(N为素数时,最终总能被它自己整除);I<>N,则表示N能被<N的奇数整除,那么N就不是素数 */

        test(N,I):-generate(I),M is N mod I,M=0,!.

                        /* 表示N能被I整除 */

        generate(3).

        generate(X):-generate(Y),X is Y+2.

                      /* 产生奇数列:3,5,7,... */

  实际上,将检查的条件定为N/2就足够了,不必检查到N-2(修改第五行)。

  算法2:1-N间的所有素数可采用Eratosthenes(埃莱斯托森斯)筛选法。即筛去2的倍数、筛去3的倍数... ...、所有的倍数都被去掉,则余下的数字就是素数。具体工作方式如下。

    (1)把2-N所有数值放人筛中;

    (2)选择并去掉筛中最小的数;

    (3)将该数加到素数集中;

    (4)把筛中所有该数的倍数筛去;

    (5)筛不空时,重复(2)-(5)步。

        primes(Limit,Ps):-integers(2,Limit,Is),sift(Is,Ps).

                      /* 谓词primes即把所有素数放人表 Ps中 */

      Integers(Low,High,[Low,Rest]):-

                  Low=<High,!,M is Low+1,integers(M,High,Rest).

        integers(-,-,[ ])./* 生成一个从2-N的整数表 */

        sift([ ],[ ]).

        sift([I|Is],[I|Ps]):-remove(I,Is,New),sift(New,Ps).

                      /* 谓词sift依次把筛中当前最小素数放人素数集中 */

        remove(P,[ ],[ ]).

remove(P,[I|Is],[I|Nis]):-not(0 is I mod p),!,remove(P,Is,Nis).

remove(P,[I|Is], Nis):- 0 is I mod P, !,
 remove(P, Is, Nis).

 /* 谓词remove把筛中当前最小的倍数去掉构成新表,以便对新的筛中内容进行同样的处理 */

6.6.2 八皇后问题

  八皇后问题可描述为如何在8X8的国际象棋棋盘上安放8个皇后,使得没有任何两个皇后占据棋盘上的同一行、同一列,或者同一对角线(有两个方向的对角线)。

  先考虑不能为同一行和同一列的限制。因为任意两皇后既不能同行,也不能同列,这样,每列只能放一个皇后,各列的皇后所在的行号分别为1-8。因此可将棋盘上皇后的布局用L表示:

        L=[X1,X2,…,X8]

  其中X值表示第几列的皇后,X1-X8分别与行号l-8一一对应,也就是说L是行号l-8的一个排列[(Xi,i)表示一个格子]。这种排列已排除了两个皇后的同行同列的可能,因此,下面只要考虑两皇后不在同一对角线上。

如图6.3,我们定义从左下方到右上方的对角线称为上向对角线,而从左上方到右下方的为下向对角线。

6.3 八皇后棋盘

    已知每个格子用其行列表示即为(Xi,i),则在同一上向对角线上有Xi+i=Xj+J;

同一下向对角线上有 Xi-i=Xj-J。这样,|Xi-Xj|=|i-j|,就处于同一对角线上。

因此,只须保证行号差的绝对值不等于列号差的绝对值,也即|Xi-Xj|<>|i-j|,就可保证 L表示的布局能满足问题所需的解。

  算法:全部生成--逐个测试法。产生L的整个排列,然后检查它是否符合解的要求。保留符合者。

      nqueens(Col,L):-permutation(L,Col),safe(L).

                    /* 谓词nqueens完成最终目标,求出解 */

      permutation([ ],[ ])。

      permutation([X|L],Col):-member(X,Col),

                            delete(COL,X,C1),

                            permutation(L,C1).

                    /* 谓词 permutation生成 l-8的排列 */

      safe(L):-member(X,L),delete(L,X,L1),

               takes(X,L1,1),!,fail.

      safe(L)./* 谓词 Safe测试所生成的排列是否符合条件 */

      member(X,[X|_]).

      member(X,[_|L]):-member(X,L).

      delete([X|L],X,L).

      delete([Y|L],X,L):-delete(L,X,L1).

                 /* 谓词 delete删除表 L中的元素 X */

      takes(X,[Y|L],I):-X>Y,J is X-Y,I=J.

takes(X,[Y|L],I):-Y>X,JisY-X,I=J.

     takes(X,[Y|L],I):- I1 is I+1,takes(X,L,I1).

                      /* 谓词 takes判断是否在同一对角线上 */

当询问?-nqueens([l,2,3,4,5,6,7,8],L),write(L),fail.

系统将输出92个解。

6.6.3 专家系统示意

  这里举一个稍复杂一些的例子。利用PROLOG系统建造一个小型的动物分类专家系统(简单示意)。该专家系统采用问答方式来辨别出用户意想中的七种动物之一。下面是一段同专家系统的会话:

        has it hair/* 你意想中的动物有毛发吗 */

        yes/* 有 */

        does it eat meat/* 该动物是食肉动物吗 */

        yes/* 是 */

        has it a towny-color/* 该动物是淡黄褐色的吗 */

        yes/* 是 */

        has it black spots/* 该动物有黑色斑点吗、/

        yes/* 有 */

        you animal may be a(n)cheetahg

          /* 你意想中的动物可能是豹 */

  PROLOG系统的考察事实和规则的能力为程序设计提供了与专家系统类似的推理能力。

  下面就是动物分类专家系统程序:

    database

          xposltlve(symbol,symbol).

          xnegatlve(symbol,symbol).

    predicates

          run.

          anlimal_Is(symbo).

          it_is(sysbol).

          positive(symbol,symbol).

          negative(symbol,symbol).

          clear_facts.

          remember(symbol,symbol,symbol).

          ask(symbol,symbol).

                        /* 为向数据库/知识库添加有关某谓词的事实,则需先在程序顶部的数据库/知识库说明段中说明该谓词。一旦说明,则关于该谓词的子句只允许为事实而不能为规则。有关数据库/知识库谓词的详细讨论可参见有关资料 */

          clauses

          run:-animal_is(X),!,

          write("\nYour animal may be a(n)",X),

                    nl,nl,clear_facts.

        run:-write("\nUnalbe to determine what"),

            write("your animal is \n\n'),clear_facts.

      positive(X,Y):-xpositive(X,Y),!.

/* 如果在数据库中存在着一个有关数据库/知识库谓词 xpositive的事实,则普通谓词 xpositive成功 */

    positive(X,Y):-not(xnegative(X,Y)and ask(X,Y).

    negative(X,Y):-xnegative(X,Y),!.

    negative(X,Y):-not(xpositive(X,Y)and ask(X,Y).

                  /* 如果不知道什么事实反驳一给定事实,则询问用户 */

    ask(X,Y):-write(X,"it",Y,"\n”),

              readln(Reply),

              remember(X,Y,Reply).

           /*谓词 ask向用户询问,并记住用户的回答 */

    remember(X,Y,yes):-assertz(xpositive(X,Y)).

    remember(X,Y;no):-assertz(xnegative(X,Y)),fail.

              /* 如用户回答yes,则借助标准谓词assertz将此肯定事实加入数据库*/

    clear_fact:-retract(xpositive(-,-)),fail.

    clear_fact:-retract(xnegative(-,-)),fail.

    clear_facts:-write("\n\nPlease press the space bar to Exit"),readchar(-).

                  /* 为了在同一程序中,后续目标不与在实现前一目标期间所加入的信息发生混淆,应该去掉先前加入到数据库中的事实。清除后,提示                  用户按空格键以回到PROLOG系统 */

                  /* 下面为推理系统提供知识 */

    animal_is(cheetah):-it_is(mammal) and

                       it_is(carnivore) and

                       positive(has,tawny_color) and

                       positive(has,black_spots).

                /* 如果:动物是哺乳动物、食肉动物、黄褐色的,而且有黑色斑点那么:该动物是豹 */

    animal_is(tiger):-it is(mammal)and

                    it_is(carnivore)and

                    positive(has,tawny_color)and

                    positive(has,black_stripes).

              /* 如果动物是哺乳动物、食肉动物、黄褐色的,而且有黑条纹,那么该动物是虎 */

    animal_is(giraffe):-it_is(ungulate)and

                    positive(has,long_neck)and

                    positive(has,long_legs)and

                    positive(has,dark_spots).

              /* 如果动物是有蹄类动物、有长脖子、有长腿,而且有黑斑点,那么该动物是长颈鹿 */

    animal_is(zebra):-it_is(ungulate)and

                  positive(has,black_stripes).

              /* 如果动物是有蹄类动物,而且有黑条纹,那么该动物是斑马 */

    animal_is(ostrich):一计_is(bird)and

                      negative(does,ly)and

                      positive(has,long neck)and

                      positive(has,long-legs)and

                      positive(has,hi。k-and-white-color).

                /* 如果动物是鸟、不会飞、有长脖子、有长腿,而且是黑白色的,那么该动物是鸵鸟 */

        animal-Is(吓nguin):-it_is(bird)and

                      negative(does,fly)and

                      positive(does;swim)and

                      positive(bhas,black_and_wbite_color)

                /* 如果动物是鸟、不会飞、会游泳,而且是黑白色的,那么该动物是企鹅 */

        nimal_is(albatross):-it_is(bird) and positive(does,fly_well).

                    /* 如果动物是鸟已善飞,那么该动物是信天翁 */

        it_is(mammal):positive(has,hair)

                    /* 如果动物有毛发,那么波动物是哺乳动物 */

        it_Is(mammal):-positive(does,give_milk).

                      /* 如果动物有奶,那么该动物是哺乳动物、/

        it_is(bird):-positive(has,feathers).

                  /* 如果动物有羽毛,那么该动物是鸟 */

        it_is(bird):-positive(does,fly)and positive(does,layeggs).

                  /* 如果动物会飞且会下蛋,那么波动物是鸟 */

        it_iss(carnivore):-positive(does,eat_meat).

                      /* 如果该动物吃肉,那么该动物是食肉动物 */

        it_is(carnivore):positive(has,pointed_teeth)and

                    positive(has,claws)and

                    positive(has,forwardeyes).

                /* 如果该动物有犬齿且有爪且眼盯着前方,那么该动物是食肉动物 */

        it_is(ungulate):-it_Is(mammal) and positive(has,hooves).

                    /* 如果该动物是哺乳动物且有蹄,那么该动物是有蹄类动物 */

        it_is(ungulate):-it_is(mammal)and positive(does,chew_cud)

                    /* 如果该动物是哺乳动物且嚼食动物,那么该动物是有蹄类动物 */

  至此,程序员可询问诸如"动物有毛发吗?"之类的问题了。

  如想使系统能推理出新结论,则须向PROLOG数据库/知识库加入相应的事实和规则。

  本例中出现的":-"就是"if”。实际上,PROLOG语言还有许多过程性的一面。如像fail或!等内部谓词就是用来控制程序流的。利用PROLOG语言可编制出"if then else""case""do while"结构的程序。如需要更多地了解,可参见有关资料。

返回本节开头 返回本章开头

6.7 PROLOG语言与C语言的连接 上一节  下一节

  没有一种计算机语言,可以完成所有的工作,PROLOG语言也不例外。PROLOG语言是一种很适合于人工智能应用和数据库管理的语言。但对于与实际应用相关的一些过程性工作却并不很适合。当然,可将PROLOG语言与其他语言连接起来使用。如一个财务系统,可采用PROLOG语言编写自然语言的"前端",而对过程性的工作处理仍使用C语言来实现。

  除了专家系统和某些数据库管理程序之外,与人工智能有关的子系统,通常可与已有的应用系统相结合,以进一步提高其功能。大多数人工智能语言在处理过程性的工作时常有些不方便,所以可将两种或多种语言结合起来使用,以便各取所长。

6.7.1 语言条件

  PROLOG语言可直接与C,PASCAL,FORTRAN和汇编语言编写的程序连接起来。需注意的是,并不是和其中一种语言连接起来,就能完全工作的。在与其他语言的代码连接之前,还要有二个条件:

    (1)这些代码必须编译(或汇编)成标准的OBJ文件;

    (2)这些代码要使用32位指针,即必须完全支持80X86系列的大存储器模式;

    (3)如果在两种语言之间存在着参数的传递,则其代码的传递方式必须与这两种语言所支持的方式相一致。

  除此之外,对实数,PROLOG语言采用的是IEEE浮点格式。并不是所有的编译程序都支持这种格式,因此,如果想用浮点方式来编写外部子程序,那就应该保证与IEEE格式一致。

6.7.2 外部谓词说明

  当采用能与PROLOG语言连接的其他语言来编写程序时,必须在PROLOG程序的global predicales(全局谓词)段说明此程序为外部谓词。外部谓词的一般格式,除了要明确告诉PROLOG语言此外部子程序所使用的是什么语言外,还有类似于一般全局谓词的说明方式等其他方面。下面是说明用C语言写的mul外部子程序;

        global predicates

        mul(integer,inleger,integer)-(i,i,o),(I,i,i) language C

这里(i,i,o)和(i,I,i)是表示合法的流模式。i表示输入;调用时已约束,O表示输出,调用时无约束(自由)。

  当建立外部过程(PROLOG语言调用这个过程),准备结合这个子程序名时。要记住所采用的过程名和特定的流模式序号。例如,mul的第一个流模式名为mul;第二个流模式为mul_1 。所以,外部子程序要用这样的名字。它总是在一谓词后跟一下划线,然后是流模式的序号。

  还有一点要注意的是,所有的谓词都假设是成功的。只要PROLOG程序调用,外部子程序不能失败而产生回溯。

6.7.3 参数传递

  一般所写的外部子程序,常用来传递参数,或是接受信息,或是返回给主程序信息。当传递参数时,应注意以下几点。

  用户在用80X86系列的处理器,可选择各种存储器模式,但是PROLOG语言要求使用大模式,即对外部过程的调用和从外部过程的返回必须是FAR,并且只能用32位指针,PROLOG语言对于16位指针是不能工作的。

  PROLOG语言与外部过程是用堆栈来传递参数的。对汇编语言、PASCAL和FORTRAN语言,其自变量是按它们出现的顺序存放在堆栈中的,而大多数C编译程序产生的子程序希望按相反的顺序找到它们的自变量,所以对C语言的参数传递是按相反的顺序压进堆栈的(也有少数C编译程序是按其他方式传递参数的,因此,若选用C语言,则应确认编译程序究竟是按什么顺序传递参数的)。

6.1 PROLOG语言的内部数据类型

  型

  示

integer

2字节

red

8字节(IEEE格式)

character

1字节(压栈时为2宇节)

symbol

4字节指针(指向null结束的宇符串)

string

4字书指针(指向null结束的字符串

compund

4字节指针(指向记录)

  PROLOG语言中的每种数据类型,在存储器中是以某种具体形式表示出来的。表 6.1给出了各种数据类型及其存储方式。当字符、整数或实数型参数从PROLOG语言传递到子程序时,实际上压人堆栈的是其数值;而对符号、字符串或复合型的参数,则是其地址被压进堆栈。由此须注意的是:当外部子程序存在着返回参数给PROLOG语言,则必须在输出参数指向的地址处,PROLOG语言装人一数值。

  每当PROLOG语言调用外部过程时,传递参数的压栈顺序是:任何自变量都被压进堆栈,接着BP寄存器的当前值压进堆栈,然后返回地址压进堆栈。这样的信息排列,称为激活记录。使用者应知道每段信息位于何处,以便对自变量能正确存取。返回地址在堆栈中总要占4个字节;BP寄存器的当前状态需要2个字节表示;而对输入参数,其字节大小将取表6.1所列的数值;对输出参数则是取4个字节。

6.7.4 外部C语言子程

  假设对C语言编程较熟悉,并会使用C语言的指针。

  从表6.1可看出,字符、整数和实数型是直接将输入参数的值传递到堆栈,而字符串、符号和复合型是将其地址压进堆栈。这意味着字符、整数或实数型的传递参数将作为C语言的int、float和char的数据类型来处理;而对字符串、符号和复合型的传递参数,则要用C语言的char * 数据类型--指针(或是指向复合结构的指针)来处理,因为只有地址(指针)能传递到C语言子程序。所有的返回参数必须使用相应的指针类型。如下面的函数是将两实数相乘,并以第三个参数返回结果。

        mul(,b,c)

           float a,b;

           float *c;

{*c=a*b;}

  所用的C编译程序必须使用32位指针(有些编译程序可能将此条件看成"大存储器模式选择"),许多C编译程序允许在16位和32位指针之间选择,因此要确认选择是正确的。如果编译程序不能以32位指针方式工作,它就不能与PROLOG语言相连接。

  下面的命令行是连接C模块与PROLOG模块:

  LINK INIT+P+C+P.SYM,PROGRAME,PROLOG + CLIB

其中P表示PROLOG代码,C表示C代码。一般C语言库函数被包括在库函数清单里,大多数C编译程序将调用函数库CLIB。

6.7.5 两个限制

  当用字符串或符号作为输出参数时,必须注意两条特定的重要限制。

  (l)PROLOG语言仅当字符串变量被约束之后,才对其分配存储空间。因此,下列代码段将不能正确操作,并且可能会使你的计算机"Down"机。

    C语言代码段:

        global predicates

        strcpy(string,string)-(l,o)language C

    PROLOG语言代码段:

            clauses

                start:-

                  A="this is test",

                  strcpy(A,B),

                  write(B).

  strcpy是C语言的标准字符串拷贝函数(strcpy函数仅将字符串A的内容拷贝到变量B里去)。之所以这个代码段不能完成拷贝,是因为变量B在调用时没有被约束为任何值,因此系统对它没有分配存储空间,即它的指针无所指。因此,strcpy准备拷贝字符串A的内容到变量B时,strcpy将会把它们放到内存的某一随机点上--这很可能会导致程序死去。克服这一问题的惟一办法是在调用前,系统先将一哑值约束到变量B中。这样系统就会分配存储空间给变量B,以使字符串拷贝函数能正常上作。当然,将变量B约束为一值,就意味着strcpy的说明必须改为两个输入参数。这种方法看起来似乎奇怪,但是,这是对这种类型操作的惟一途径。修改后的代码如下所示。

    C语言代码段:

        global predicates

        strcpy(string,string)(i,i)language C

    PROLOG语言代码段:

          clauses

           start:

             A="this is a test.",

             B="this is a nonsense string.”,

             strcpy(A,B),

             wtite(B).

  要注意的是必须保证哑字符串足够长,以便使外部子程序能将需要的内容放进去。无论用什么语言实现外部子程序,这个问题都有普遍性意义。

  (2)一般规定不能直接使用符号来返回输出参数,因为所有的符号是存放在系统的符号表中。如改变了该符号的内容并且所占字节长度变大,则可能会重叠地写到另外的符号上,偶尔还会破坏整个符号表。

  当然,这些限制是由C语言指针变量的特点引起的。如对C语言比较熟悉的话,那这两个限制就不成问题了。

返回本节开头

6.8 Visual Prolog的程序结构 上一节

 Visual Prolog的语法可用来表达关于属性和关系的知识。为了理解它的基本原理,在第2章已经介绍了子句(事实和规则)、谓词、变量和目标。

  与Prolog其他版本不同,Visual Prolog有一个强类型的Prolog编译器,声明每一个谓词要应用的对象的类型。这个类型声明使Visual Prolog程序直接被编译成本地机器代码,给出执行速度类似于编译的C和Pascal的代码。

在此,我们讨论Visual Prolog程序的四个基本段:声明并定义谓词和谓词参数型的谓词段、声明并定义参数论域的论域段、定义规则的字句段和规定程序目标的目标段。然后,简要介绍Visual Prolog程序的其他段,包括事实段、常量段、各种全局段,以及编译命令。

6.8.1 基本程序段

  一般来说,一个Visual Prolog程序包括四个段,即子句 (clauses)段、谓词(Predicates)段、论域(domains)段和目标(goal)段。

  .子句段是VisuProlog程序的核心。其中放置事实和规则,Visual Prolos程序对其进行操作以试图满足程序的目标。

  .谓词段用来声明谓词及其参数的论域(类型)、(不必声明Visual Prolog的内部谓词。)

  .论域段用来声明正在使用的任何论域,而这些论域不是Visual Prolog的标准论域。(不必声明Visual Prolog的标准论域。)

  .目标段用来放置Visual Prolog程序的开始目标。

6.8.1.1子

  子句段放置组成程序的所有事实和规则。如果要理解事实和规则,并且知道如何在Visual Prolog中写出它们,就必须知道子句如何起作用、给定谓词的子句必须统一被放在子句段、定义谓词的一个子句序列被称为过程。

  当要试图满足一个目标时,Visual Prolog将从子句段的顶部开始寻找匹配目标的每一个事实和规则。Visual Prolog经由子句段继续往下进行,将为每一个匹配当前了目标的子句设置内部指针。如果该子句不是进行求解的逻辑通路的一部分, Visual Prolog返回到前向设置的指针并继续寻找其他匹配子句(这就是回溯)。

6.8.1.2谓词段

  如果想要在Visual Prolog程序的子句段定义自己的谓词,就必须在谓词段进行声明,否则Visual Prolog将不能理解。当你声明了一个谓词,就告诉了Visual Prolog该谓词的参数属于哪个论域。

  Visual Prolog带有大量内建谓词。在程序中使用内建谓词不需要进行声明。Visual Prolog在线帮助给出内建谓同的完整解释。

  事实和规则定义谓词。程序的谓词段简单列出每一个谓词及其参数的类型(论域)。尽管子句段是程序的核心,通过声明事实和规则所涉及的对象(参数)类型,Visual Prolog将变得更具效率。

  如何声明自定义谓词

  谓词声明以谓词名开始,紧跟一个(左)圆括号,接着是零个或多个谓词参数。

  predicateName(argument_type1,argument_type2,...argument_typeN)

  参数之间以逗号分隔,最后的参数后跟随一个(右)圆括号。注意,与子句段不同,谓词声明不需要加句号。参数类型可以是标准论域或是已经在论域段声明过的论域。

  谓词名

  谓词名必须以字母开始,接着是一系列的字母、数字和下划线。谓词名中字母的大小写没有要求。但是,我们明确推荐谓词名的第一个字母为小写字母。(其他Prolog版本不允许谓词名以大写字母或下划线开始,Visual Prolog将来的版本也可能同样不允许。)谓词名不能超过250字符。

  谓词名中不能使用空格、减号、星号、斜线或其他非字母和数字的字符。Visual Prolog中有效的字符如下:

  .大写字母:A,B,...,Z。

  .小写字母:a,b,...,z。

  .数字:0,l,..,9。

  .下划线:_。

  只要遵循谓词名和参数名的命名规则,所有的谓词名和参数可以由这些字符的组合组成。

  谓词参数

  谓词参数必须属于已知的Visual Prolog论域。可以是标准论域,者是在论域段中声明的自定义论域。

  举例

  l)如果在谓词段声明谓词my_predicate(symbol,integer)。如:

PREDICATES
my_predicate(symbol,integer)

  因为Symbol和integer是标准论域,所以不必在论域段声明谓词参数的论域。但是,如果在谓词段声明my_predicate(name,number),像这样:

PREDICATES
my_predicate(name,number)

则必须为name和number声明合适的论域。假定想使它们分别表示。symbol和integer,则论域声明应该这样:

DOMAINS
  name=symbol
  number=integer
FREDICATES

  my_predicate(name,number)

2)下面的程序片段显示更多的谓词和论域的声明:

DOMAINS
  person,activity=symbol
  car,make,color=symbol
  mileage,years_on_road,cost=integer
PREDICATES
  like(person,activity)
  parent(person,person)
  can_buy(person,car)
  car(make,mileage,years_on_road,cilor,cost)
  green(symbol)
  ranking(symbol,integer)

  这段摘录详细指定了下列关于谓词及其参数的信息:

  .谓词like。带有两个参数(person和activity),它们都属于symbol论域(这意味着它们的值只能是名字而不能是数字)。

  .谓词parent带有两个person参数,它们都属于symbol域。

  .谓词can_buy带有两个参数(person和car),它们也都属于symbol论域。

  .谓词car带有5个参数:make和color是symbol论域,mileage、years_on_road、cilor、cost是整数integer论域。

  .谓词green带有一个symbol参数,因为它属于标准论域symbol,所以不必声明参数的类型。

  .谓词ranking带有两个参数,它们都属于标准论域(symbol和integer),因此不必声明参数类型。

6.8.1.3论域段

  传统的Prolog只有一种类型:项(term)。Visual Prolog中同样也有,不过我们声明谓词的参数到底属于什么论域。

  论域使你可以给看起来相似的不同类型的数据起一个有特色的名字。在Visual Prolog程序中,关系的对象(谓词的参数)属于论域,这些论域可以是事先定义的论域,也可以是指定的特殊论域。

  论域段提供两个非常有益的用途。首先,可以给论域赋予有意义的名字,尽管它们可能是内部已经存在的并且相同的论域。其次,特殊的论域声明用来声明标准论域中未定义的数据结构。

  声明一个论域有时对阐明部分谓词段是有益的。声明自己的论域,给参数的类型起一个有用的名字,有助于定义谓词的文档化。

举例

  l)下面这个例子说明怎样通过声明论域来帮助文档化谓词:

  Frank是45岁的男子。

  用预定义的论域声明谓同如下:

  person(symbol,symbol,integer)

  这个声明在很多情况下是很好的。但是如果想把代码完成后维持数月仍能很好地理解,前面的调词声明不会有大的帮助。相反,下面的声明将会有助于理解谓词中的参数所代表的含义。

DOMAINS
  name,sex=symbol
  age=integer

PREDICATES
  person(name,sex,age)

  这样声明的主要优点之一是Visual Prolog可以捕捉类型错误,例如像下面这样明显的错误:

same_sex(X,Y):-
  person(X,sex,_),person(sex,Y,_).

  尽管name和sex都被定义为symbol类型,但它们并不等同。这使Visual Prolog能够检测到你偶然交换它们的错误。当程序较大而复杂时,这个特征就非常有用了。

既然特殊声明的论域表示参数的意思有如此多的好处,你一定疑惑为什么不对所有的参数给出特殊声明。答案就是,一旦一个参数被声明为特殊论域,它就不能与其他的论域混合,甚至相同的论域也不行!所以,尽管name和sex是相同的论域(symbol),但它们不能混合。不过,所有自定义的论域可以与预定义论域匹配。

  2)下面的例子程序运行时将产生一个类型错误:

DOMAINS
  product,sum=integer
PREDICATES
  add_em_up(sum,sum,sum)
  multiply_em(product,product,product)
CLAUSES
  add_em_up(X,Y,Sum):-
  Sum=X+Y.
  multiply_em(X,Y,Product):
  Product=X+Y.

  这个程序做两件事:加法和乘法。加入目标

GOAL
  add_em_up(32,54,SUM)

Visual Polog(Test Goal)将给出结果:

  Sum=86
  1 Solution

这就是你给出的两个整数的和。

  另一方面,程序也可以用multiply_em谓词进行乘法运算。现在检验这个程序。如果你想算出31和13的乘积,可以加入目标:

  multiply_em(31,13,Productt).

Visual Prolog (Test Goal)将回答正确答案:

  Product=403

  1 Solution

但是如果你想算42和17之和,目标是

  add_em_up (42,17,Sum).

  现在你要得到31和17之和的双倍,加入目标:

  multiply_em(31,17 Sum),add_em_up(Sum,Sum.Answer).

你可能期望Visual Prolog(Test Goal)返回

  Sum=527,Answer=1054

  1 Solution

但是相反,你却得到一个类型错误。原因是你试图把multiply_em(论域product)的结果值赋给add_em_up的第一和第二个参数,而它们都是sum论域。这样造成的类型错误是因为product和sum是不同的论域。尽管两十论域实际上是同一个整数integer类型,但它们是不同的论域,要不同对待。

  因此,如果一个变量在一个子句中被用在不只一个谓词里面.这个变量必须在每个谓词中声明相同的论域。确信你完全理解在这里给出的类型错误背后的概念,并已更好地理解编译程序错误信息。在本章的后面,我们将叙述Visual Prolog提供的各种自动的和显式的类型转换。

  3)为了进一步理解怎样利用论域声明来捕捉类型错误,考察下面的程序例子:

DOMAINS
  brand,color=symbol
  age=byte
  price.mileage=ulong
PREDICATES
  car(brand,mileage,age,color,price)
CLAUSES
  car(chrstyler,130000.3,red,12000).
  car(ford,90000,4,gray,25000).
  car(datsun,8000,1,black,30000).

其中,在谓间段中声明的car谓词带有5个参数。一个属于age域,是byte类型。对80x86系列CPU来说,一个byte是一个8位无符号整数,可以表示0-255之间的值,包括0和255。类似地,论域mileage。和price是ulong类型,是一个32位的无符号整数。论域brand和color是symbol类型。

  我们将简要地讨论内建论域的大部分细节、下面把程序装人TestGoal项且,依次尝试下列目标:

  car(renault,13,40000,red,12000).
  car(ford,90000,grey,4,25000).
  car(1,red,30000,80000,datsun).

  每一个目标产生一个论域错误。第一种情况是因为age必须是byte型的。所以,如果mileage和age对象被交换了,Visual Prolog很容易检测到。第二种情况是age和color对象被交换了、第三种情况你自己可以找到哪里被混淆了。

6.8.1.4目标段

  从本质上讲,目标段与规则体是相同的:它只简单地列出子目标。目标段和规则之间有两点不同:

  l)目标goal关键词后不跟符号”:-”。

  2)当程序运行时,Visual Prolog自动执行目标。

  这就像Visual Prolog调用一个目标,程序运行,试图满足目标规则体。如果目标段的子目标全部成功,那么程序成功终止。反之,程序运行时,如果目标段中有一个子目标失败,则我们说程序失败。(尽管从外部看来程序没有任何不同,仅仅是程序结束。)

6.8.2 其他程序段

  到目前为止,假定你已经熟悉了Visua1 Prolog程序的子句段、谓词段、论域段和目标段,下面我们再学习一下其他通用程序段:事实(facts)段,常量(constants)段,以及各种全局(global)段。这些都仅仅是初步,像学习其他部分一样,要学会这些段,懂得怎样在程序中使用它们。

6.8.2.1事实段

  一个Visual Prolog程序是事实和规则的一个聚集。有时候,当程序运行时,可能想要更新(改变、删除或增加)一些程序对之进行操作的事实。在这种情况下,事实组成了动态的或内部的事实数据库,当程序运行时,可以改变它。Visual Prolog包含一个在程序中声明事实的特殊段,它是动态(或可变)的事实数据库的一部分,这就是事实段。

  关键字facts声明事实段。在这里所声明的事实被包含在动态事实段。Visual Prolog含有许多内建谓词,允许很容易地使用动态事实段。关键字facts与过去使用的关键词database是同义的。

6.8.2.2常量段

  在Visual Prolog程序中可以声明和使用符号常量。常量声明段用关键字constants指示,后面跟着声明本身,采用下列语法:

  <Id>=<Macro definition>

  <Id>是符号常量的名字,<Macro definition>是赋给常量的值。每一个<Macro definition>以一个新行字符结束,所以每行只能有一个常量声明。稍后的程序中将涉及以这种力式声明的常量。

  考察下面这段程序:

CONSTANTS
  zero=0
  one=1
  two=2
  hundred=(10*(10-1)+10)
  pi=3.141592653
  ega=3
  slash_fill=4
  red=4

  在编译程序之前,Visual Prolog将用与每一个常量相对应的实际串值替换它们。例如:

  A=hundred*34,delay(A),
  setfillstyle(slash_fill,red).
  Circumf=pi*Diam.
  ...

将被编译器以完全相同的方式处理为:

  ...
  A=(10*(10-1)+10)*34,delay(A),
  setfillstyle(4,4),
  Circumf=3.141592653*Diam,
  ...

  使用符号常量有下面一些限制:

  .常量定义不能引用自身。例如:

  my_number=2*my_number/2   /* Is not allowed */

将产生一个常量递归定义错误信息。

  .在常量声明中,系统不区分大小写字母。因此,程序的子句段中使用常量标识符时,第一个字母必须小写,以避免混淆常量与变量。所以,下面的例子是有效的构造:

  CNSTANTS
    Two=2
  Goal
    A=two,write(A).

  .程序中可以有几个常量声明段,但是常量必须在使用前被声明。

  .被声明的常量从声明点到该源文件结束以及在任何文件中包含该声明之后是有效的。常量标识符只能被声明一次。同一个常量标识符的多次声明将导致错误信息:这个常量已经被定义。

6.8.2.3全局段

  Visual Prolog允许在程序中声明论域、谓词和子句为全局(gohal)的(而不是局部的)。global domains段、global Predicates段和global facts段可以分开放在程序顶部进行声明。

6.8.2.4 编译程序命令

  Visual Prolog提供几种编译程序命令,可以把它们加入程序中,告诉编译器在编译时以特殊方法处理代码、通过Visual Prolog系统的菜单项Option|Project|Compiler Options也可以设置大多数编译程序命令。在此,我们仅简介怎样使用其中几个基本的编译程序命令。

  include命令

  随着对使用Visual Prolog越来越熟悉,可能会发现在程序中总要反复地使用某一段过程。使用包含(include)命令可以把你从反复键入这些过程的工作中解放出来。

  下面是如何使用包含命令的例子:

  l)创建一个文件(例如MYSTUFF.PRO),在其中声明那些频繁使用的谓词(使用论域和谓词段),并且在子句段中给出定义那些谓词的过程。

  2)编写程序源文本将要使用这些过程。

  3)在源文本中的一个自然边界处,写下这行:

  include “mystaff.pro”

  一个自然边界是指在程序中放置论域段、事实段、谓词段、子句段和目标段的任何地方。

  4)在编译源文件时,Visual Prolog将会把文件MYSTUFF.PRO中的内容适当地加入到最终编译的源文件中。

  你可以使用包含命令把几乎任何经常使用的文本引入到源文件中,并且一个包含文件还可以包含另一个文件(但是一个给定文件在程序中只能被包含一次)。包含命令可以出现在源文本中任何自然边界处。然而,当在源文本中包含一个文件时,一定要注意程序结构的限制。

6.8.3 Visual Prolog结构小结

  下面是本节介绍的主要概念。

  l)一个Visual Prolog程序的基本结构如下:

DOMAINS
/*  domain declarations
   ... */

PREDICATES
/*  predicate declarations
  ...  */

CLAUSES
  /*.  clauses(rules and facts)
  ... */

GOAL
/*  subgoal_1,
    subgoal_2,
    etc. */

  2)子句(clauses)段用来放置Visual Prolog试图满足程序目标时使用的事实和规则。

  3)谓词(predicates)段用来声明谓词及其参数的论域(类型)。谓词名必须以字母开始(最好是小写字母),后跟一串字母、数字和下划线,最多可长达250个字符。谓词名中不能使用空格、减号、星号和斜线等。谓词声明形式是

predicateName(argument_type1,argument_type2,...argument_typeN)

  argument_type1,argument_type2,...argument_typeN或者是标准论域,或者是在论域段已经声明的论域、声明参数的论域和定义参数类型是一回事。

  4)论域(domain)段用来声明谓词参数的非标准论域。Prolog中的论域相当于其他语言中的类型。Visual Prolog的标准论域是char、byte、short、ushort、word、integer、unsigned、long、ulong、dword、real、string和symbol。基本论域声明的形式是

DOMAINS
argument_type1,argument_type2,...argument_typeN=<standardDomain>

复合论域的声明是

argument_type1,argument_type2,...argument_typeN=<compoundDomain_1>;<compoundDomain_2>;<...>;<compoundDomain_M>;

  复合论域今后讨论。

  5)目标(goal)段用来放置程序的目标(在PDC Prolog中,这里使用术语“内部目标”),允许程序进行编译、建立且作为与可视化开发环境VDE无关的、单独的可执行文件运行。单独执行时,Visual Prolog仅仅寻找程序目标的第一个解,目标变量被绑定的值并不显示。

  一些Prolog环境(例如,旧的PDC Prolog环境)支持所谓的外部目标(与术语内部目标相对应)。当PDC Prolog环境运行一个不包括内部目标的程序时,环境将会显示一个特殊对话框,在运行时间可以在对话框中键入一个外部目标。对于外部目标,Prolog将会搜索目标的所有解,并显示目标变量被绑定的值。Visual Prolog的可视化开发环境VDE不支持外部目标。然而,对于简单的程序(这本语言教程中的大多数例子),可以使用VDE专门的实用程序Test Goal。这个Test Goal目标的所有解,并显示目标变量所绑定的值。

  6)谓词的元(arity)是指谓词所带参数的个数。两个谓词可以有相同的名字但是含有不同个数的参数。在谓词和子句段,必须把不同参数个数的谓词版本聚集在一起,但是参数个数不同的谓词被认为是完全不同的谓词。

  7)规则的形式是

  Head :-<Sungoal1>,<Sungoal2>,...,<Sungoal1N>.

  为了使一个规则成功,Prolog必须满足所有的子目标,创建一致的绑定变量的集合。如果一个子目标失败,则Prolog将退回且寻找较早于目标的替代方案,然后以不同的变量值继续向前进行。这就是回溯。

  8)Prolog中的“:-”(“if”)不要与其他语言中用的if混淆。一个Prolog规则是一个then/if形式的条件式,而其他语言中的IF语句则是if/then形式的条件式。

返回本节开头 返回本章开头
本章结束 返回本章开头 一章 下一章 返回人工智能教学主页