人工智能程序設(shè)計(jì)語言-59

1、人工智能程序設(shè)計(jì)語言人工智能程序設(shè)計(jì)語言華北電力大學(xué)計(jì)算機(jī)系華北電力大學(xué)計(jì)算機(jī)系 2/20/20221內(nèi)容內(nèi)容 綜述 函數(shù)型程序設(shè)計(jì)語言LISP 邏輯性程序設(shè)計(jì)語言PROLOG PROLOG程序設(shè)計(jì)2/20/20222華北電力大學(xué)華北電力大學(xué)內(nèi)容內(nèi)容 綜述 函數(shù)型程序設(shè)計(jì)語言LISP 邏輯性程序設(shè)計(jì)語言PROLOG PROLOG程序設(shè)計(jì)2/20/20223華北電力大學(xué)華北電力大學(xué)綜述綜述 人工智能所解決的問題 并非一般的數(shù)值計(jì)算或數(shù)據(jù)處理問題 是要實(shí)現(xiàn)對腦功能的模擬和再現(xiàn) 人工智能程序 面向問題 面向邏輯 支持知識(shí)表示 能描述邏輯關(guān)系和抽象概念 處理對象更多的是知識(shí)，或者說是符號(hào) 常規(guī)程序設(shè)計(jì)

2、語言受限2/20/20224華北電力大學(xué)華北電力大學(xué)綜述綜述 人工智能程序設(shè)計(jì)語言 函數(shù)型語言 邏輯性語言 面向?qū)ο笳Z言 混合型語言2/20/20225華北電力大學(xué)華北電力大學(xué)綜述綜述-函數(shù)型語言函數(shù)型語言 函數(shù)型語言 LISP是一種函數(shù)型程序設(shè)計(jì)語言。LISP程序由一組函數(shù)組成，程序的執(zhí)行過程就是一系列的函數(shù)調(diào)用和求值過程。但LISP還不是純函數(shù)型語言，準(zhǔn)確地講，它是基于-函數(shù)的語言。除LISP外，20世紀(jì)70年代J.Backus還提出了一種稱為FP的所謂純函數(shù)型程序設(shè)計(jì)語言。但該語言現(xiàn)在還限于理論研究，實(shí)現(xiàn)上還存在一定困難。2/20/20226華北電力大學(xué)華北電力大學(xué)綜述綜述-邏輯型語言邏

3、輯型語言 邏輯型語言 邏輯型程序設(shè)計(jì)語言起源于PROLOG （PROgramming in LOGic）。 PROLOG語言首先由法國馬塞大學(xué)的Colmerauer和它的研究小組于1972年研制成功，后來在歐洲得到進(jìn)一步發(fā)展。特別是1981年日本宣布要以PROLOG作為他們正在研制的新一代計(jì)算機(jī)智能計(jì)算機(jī)的核心語言，更使PROLOG舉世矚目，迅速風(fēng)靡世界。2/20/20227華北電力大學(xué)華北電力大學(xué)綜述綜述-邏輯型語言邏輯型語言 現(xiàn)在PROLOG幾乎在人工智能的所有領(lǐng)域都獲得了應(yīng)用, 成為與LISP并駕齊驅(qū)的甚至更加流行的智能程序設(shè)計(jì)語言。 由于PROLOG語言是一種邏輯型程序設(shè)計(jì)語言, 因此

4、用它編寫的程序也就是邏輯程序,即在PROLOG程序中一般不需告訴計(jì)算機(jī)“怎么做”, 而只需告訴它“做什么”。因此,PROLOG亦屬陳述性語言。與通常的過程性程序設(shè)計(jì)語言相比, PROLOG是更高級的語言。2/20/20228華北電力大學(xué)華北電力大學(xué)綜述綜述-面向?qū)ο笳Z言面向?qū)ο笳Z言 面向?qū)ο笳Z言面向?qū)ο笳Z言 20世紀(jì)80年代以來，面向?qū)ο蟪绦蛟O(shè)計(jì)(ObjectOrientedProgramming，簡稱OOP)異軍突起，發(fā)展迅速。OOP以其信息隱蔽、封裝、繼承、多態(tài)、消息傳遞等一系列優(yōu)良機(jī)制，大大改善了軟件的復(fù)雜性、模塊性、重用性和可維護(hù)性，有望從根本上解決軟件的生產(chǎn)效率問題。另一方面，由于面

5、向?qū)ο蟪绦蛟O(shè)計(jì)的類、對象、繼承等概念，與人工智能特別是知識(shí)表示和知識(shí)庫產(chǎn)生了天然的聯(lián)系。 2/20/20229華北電力大學(xué)華北電力大學(xué)綜述綜述-混合型語言混合型語言 混合型語言混合型語言 1. 函數(shù)型與邏輯型相結(jié)合的語言函數(shù)型與邏輯型相結(jié)合的語言 函數(shù)型與邏輯型語言的結(jié)合方式有耦合型和統(tǒng)一型兩類。 統(tǒng)一型又可分為具有歸結(jié)語義的函數(shù)型語言和集成式語言兩個(gè)子類。 耦合型語言意為將具有歸約語義的函數(shù)型語言和具有歸結(jié)語義的邏輯型語言組合在一起, 并在二者之間提供一個(gè)接口而形成的一種混合型語言。 其典型代表有： 2/20/202210華北電力大學(xué)華北電力大學(xué)綜述綜述-混合型語言混合型語言 (1) LOG

6、LISP。該語言在LISP的基礎(chǔ)上增加了表達(dá)合一、 回溯等機(jī)制的系統(tǒng)函數(shù)，從而在保持LISP特色的同時(shí)又有了邏輯程序設(shè)計(jì)能力。 (2) FUNLOG。該語言在 PROLOG 之外又增加了函數(shù)定義機(jī)制, 系統(tǒng)以歸結(jié)語義執(zhí)行PROLOG程序, 以歸約語義求解函數(shù)。 (3) POPLOG。這是POP-11、PROLOG和LISP的混合型語言, 三種成分各有一個(gè)增量式編譯器。具有歸結(jié)語義的函數(shù)型語言又可分為N-語言、F-語言和R語言。2/20/202211華北電力大學(xué)華北電力大學(xué)綜述綜述-混合型語言混合型語言2. 函數(shù)型與面向?qū)ο笙嘟Y(jié)合的語言函數(shù)型與面向?qū)ο笙嘟Y(jié)合的語言 在LISP語言的基礎(chǔ)上再擴(kuò)充面

7、向?qū)ο髾C(jī)制而產(chǎn)生的語言, 稱為函數(shù)型的面向?qū)ο蟪绦蛟O(shè)計(jì)語言(亦稱為面向?qū)ο蟮腖ISP)。 這種語言現(xiàn)已成為一個(gè)家族, 其中比較著名的有： (1) Flavors 由 MIT 的 Lisp Machine 小組于 1979 年研制而成, 它的基語言是Symbolics Common LISP。 (2)LOOPS(Lisp-Object-OrientedProgramming System )。它是在InterLisp-D環(huán)境上實(shí)現(xiàn)的基于LISP的OOP語言, 由Xerox公司于1983年推出。 2/20/202212華北電力大學(xué)華北電力大學(xué)綜述綜述-混合型語言混合型語言 (3) CommonLo

8、ops。 它是基于CommonLisp的函數(shù)型OOP語言, 由Xerox公司于1985 年推出。 (4) CLOS (CommonLisp Objetc System)。它是Xerox公司于1986 年推出的一個(gè)CommonLoops與New Flavors的后繼產(chǎn)品。 (5) CommonObjects。它是由HP公司于19831985年實(shí)現(xiàn)的又一個(gè)基于CommonLisp 的OOP語言。 (6) OBJ2 也是一種面向?qū)ο蟮暮瘮?shù)型語言。 2/20/202213華北電力大學(xué)華北電力大學(xué)綜述綜述-混合型語言混合型語言3. 邏輯型與面向?qū)ο笙嘟Y(jié)合的語言邏輯型與面向?qū)ο笙嘟Y(jié)合的語言 這類語言著名的

9、有: (1) SPOOL。日本IBM分部于1985年推出的以面向?qū)ο笏枷霐U(kuò)充的PROLOG語言。 (2) Orient 84K。Keio大學(xué)于1984年發(fā)表的基于PROLOG和Smalltalk 的并行執(zhí)行語言。 (3) Vulan。 一種面向?qū)ο蟮倪壿嬓驼Z言。2/20/202214華北電力大學(xué)華北電力大學(xué)內(nèi)容內(nèi)容 綜述 函數(shù)型程序設(shè)計(jì)語言LISP 邏輯性程序設(shè)計(jì)語言PROLOG PROLOG程序設(shè)計(jì)2/20/202215華北電力大學(xué)華北電力大學(xué)函數(shù)型程序設(shè)計(jì)語言函數(shù)型程序設(shè)計(jì)語言LISP LISP是第一個(gè)人工智能程序設(shè)計(jì)語言 LISt Processing，表處理語言 1960年由MIT的麥

10、卡錫和他的研究小組設(shè)計(jì)，擅長表處理，即符號(hào)處理 許多人工智能系統(tǒng)用LISP語言編寫 LISP被譽(yù)為人工智能的數(shù)學(xué)，是人工智能研究和開發(fā)的主要工具2/20/202216華北電力大學(xué)華北電力大學(xué)函數(shù)型程序設(shè)計(jì)語言函數(shù)型程序設(shè)計(jì)語言LISP LISP語言的主要特點(diǎn)： LISP程序由一組函數(shù)組成，程序的執(zhí)行過程是函數(shù)的調(diào)用過程 程序和數(shù)據(jù)在形式上是相同的，即都是符號(hào)表達(dá)式，簡稱為S表達(dá)式 遞歸是LISP語言的主要控制結(jié)構(gòu) 程序以交互方式運(yùn)行2/20/202217華北電力大學(xué)華北電力大學(xué)LISP的程序結(jié)構(gòu)的程序結(jié)構(gòu)LISP的程序一般由函數(shù)的定義和函數(shù)的調(diào)用兩部分組成。其一般格式為： (DEFUN() (

11、) () () () ()“DEFUN”是定義函數(shù)的關(guān)鍵字“函數(shù)名”可以是系統(tǒng)的內(nèi)部函數(shù)(名), 也可以是用戶用DEFUN定義的函數(shù)(名)2/20/202218華北電力大學(xué)華北電力大學(xué)一個(gè)一個(gè)LISP程序程序(DEFUN HANOI (a b c n) (COND (= n 1) (MOVE-DISK a c) (T (HANOI a c b (- n 1) (MOVE-DISK a c) (HANOI b a c (- n 1) (DEFUN MOVE-DISK(from to) (TERPRI) (PRINC Move Disk From) (PRINC from) (PRINC To)

12、(PRINC to) (HANOI abc 3) 兩個(gè)函數(shù)前者調(diào)用后者函數(shù)調(diào)用部分只有一個(gè)函數(shù)調(diào)用2/20/202219華北電力大學(xué)華北電力大學(xué)LISP的基本函數(shù)的基本函數(shù) LISP的函數(shù)一律使用前綴表示方式,分為內(nèi)部函數(shù)(基本或系統(tǒng)函數(shù))和用戶自定義函數(shù)兩類 基本函數(shù)的種類有十多個(gè)，僅給出主要的幾類 表處理函數(shù) 算數(shù)函數(shù) 求值與賦值函數(shù) 謂詞函數(shù) 條件函數(shù)2/20/202220華北電力大學(xué)華北電力大學(xué)表處理函數(shù)表處理函數(shù) 表處理是LISP的主要特色，下面僅給出最常用的幾個(gè)：1) CAR函數(shù)功能取出表中的表頭。如CAR(LISP Language Program)返回值 LISP2) CDR函

13、數(shù) 功能 取出表中的表尾 如 (CDR(LISP Language Program) 返回值 (Language Program)2/20/202221華北電力大學(xué)華北電力大學(xué)表處理函數(shù)表處理函數(shù)3) CONS函數(shù) 功能 將S表達(dá)式作為表頭加到表中去 如 (CONSMy(LISP Language Program) 返回值 (My LISP Language Program)4) APPEND函數(shù)功能 將n個(gè)表中的元素合并成一個(gè)新表如(APPEND(TIGER LION)(DOG CAT)返回值 (TIGER LION DOG CAT)5) LIST函數(shù)功能把n個(gè)S表達(dá)式作為元素構(gòu)成一張新表如

14、(LISTYELLOWREDBLUE)返回值 (YELLOW RED BLUE) 2/20/202222華北電力大學(xué)華北電力大學(xué)算術(shù)函數(shù)算術(shù)函數(shù) LISP的算術(shù)表達(dá)式也是用函數(shù)表示的，稱為算術(shù)函數(shù) 舉例說明 (+2 5)表示2+5，返回值為7 (-(*4 8)(/10 5)表示48-10/5，返回值為302/20/202223華北電力大學(xué)華北電力大學(xué)求值與賦值函數(shù)求值與賦值函數(shù) 撇號(hào) 是禁止求值函數(shù)QUOTE的簡寫形式 賦值函數(shù)有多個(gè) SET函數(shù)是最基本的一個(gè)功能把S表達(dá)式賦給變量例如： (SETX8); X 得到值8 (SETY(a b c); Y 得到值(a b c) (SETZ(CDRY

15、); Z 得到值(b c)2/20/202224華北電力大學(xué)華北電力大學(xué)謂詞函數(shù)謂詞函數(shù) 返回值為邏輯值真或假的函數(shù)稱為謂詞函數(shù) 真和假分別用T和NIL表示 謂詞函數(shù)也有多個(gè)，僅給出常用的幾個(gè)：(1) 原子謂詞ATOM 功能檢測其參數(shù)是否為原子，是則T，否則NIL 例如： (ATOMa);返回T (ATOM(a b);返回NIL 2/20/202225華北電力大學(xué)華北電力大學(xué)謂詞函數(shù)謂詞函數(shù) (2) 相等謂詞EQUAL 功能判斷兩個(gè)參數(shù)是否邏輯相等 例如： (EQUALaa); 返回T (EQUAL(a b)(a c); 返回NIL (3)判空表函數(shù)NULL 功能判斷參數(shù)是否為空表，是則返回T

16、，否則返回NIL2/20/202226華北電力大學(xué)華北電力大學(xué)條件函數(shù)條件函數(shù) 條件函數(shù)類似于分支語句，其作用是控制程序的流程 格式 (COND(P1 e1) (P2 e2) (Pn en) 其中Pi(i=1,.,n)為謂詞，ei(i=1,.,n)為一個(gè)或多個(gè)S表達(dá)式 功能功能如果P1為真，則COND函數(shù)的值為e1。否則，判斷P2，直到某個(gè)Pi真為止，然后將對應(yīng)的ei作為函數(shù)值。若沒有一個(gè)Pi的值為非NIL，則COND的返回值為NIL。特別地，Pi也可以為邏輯常量T，這時(shí)則對其對應(yīng)的各表達(dá)式求值，并把最后一個(gè)表達(dá)式的值作為COND的返回值 2/20/202227華北電力大學(xué)華北電力大學(xué)條件函數(shù)

17、條件函數(shù)例如： (COND(NULL x)0) (ATOM x)1) (LISTP x)(LENGTH x) 其語義是，若x的值為NIL，則COND的返回值為0;若x為原子，則COND的返回值為1;若x的值為表，則COND的返回值為表的長度2/20/202228華北電力大學(xué)華北電力大學(xué)自定義函數(shù)自定義函數(shù) 自定義函數(shù)的格式為： (DEFUN() ) 其中函數(shù)體，又可能是用戶自定義的函數(shù)或LISP基本函數(shù)的某種組合2/20/202229華北電力大學(xué)華北電力大學(xué)例例 定義求定義求N!的的LISP函數(shù)函數(shù)階乘的公式是 n!n(n-1)! 1!1 0!1其LISP函數(shù)如下： (DEFUNN!(n) (

18、COND(=n 0)1) (=n 1)1) (T(* n(N!(- n 1)該函數(shù)的最后一行中又調(diào)用了它自己這個(gè)函數(shù)N!是遞歸定義的2/20/202230華北電力大學(xué)華北電力大學(xué)例例 HANOI（DEFUN HANOI（a b c n）當(dāng)只有一個(gè)盤子時(shí)，直接將a上的盤子移動(dòng)到c上（COND（n 1）（MOVEDISK a c）其他情況，通過遞歸，先將柱a上的n1個(gè)盤子通過柱c移到柱b上（T（HANOI a c b（ n 1）再將柱a上的一個(gè)盤子移動(dòng)到柱c上（MOVEDISK a c）最后再通過遞歸，將柱b上的n1個(gè)盤子通過柱a移動(dòng)到柱c上 （HANOI b a c（ n 1）函數(shù)MOVE-DI

19、SK起顯示的作用，表示從柱from到柱to移動(dòng)了一個(gè)盤子（DEFUN MOVEDISK（from to）TERPRI是回車換行函數(shù)，PRINC是顯示參數(shù)的函數(shù)（TERPRI）（PRINC”Move Disk From”）（PRINC from）（PRINC”To”）（PRINC to）2/20/202231華北電力大學(xué)華北電力大學(xué)內(nèi)容內(nèi)容 綜述 函數(shù)型程序設(shè)計(jì)語言LISP 邏輯性程序設(shè)計(jì)語言PROLOG PROLOG程序設(shè)計(jì)2/20/202232華北電力大學(xué)華北電力大學(xué)邏輯型程序設(shè)計(jì)語言邏輯型程序設(shè)計(jì)語言PROLOG 1972年，法國馬賽大學(xué)的Alain. Colmerauer提出了Prolo

20、g的雛型 1975年，Prolog被用于問題求解系統(tǒng)，此后在許多領(lǐng)域獲得了應(yīng)用，如關(guān)系數(shù)據(jù)庫、定理證明、智能問題求解、計(jì)算機(jī)輔助設(shè)計(jì)、規(guī)劃生成等領(lǐng)域 Prolog語言是以一階謂詞邏輯的Horn 子句集為語法，以Robinson的消解原理為工具，加上深度優(yōu)先的控制策略而形成的人工智能通用程序設(shè)計(jì)語言2/20/202233華北電力大學(xué)華北電力大學(xué)Horn邏輯邏輯 文字文字：原子公式(正文字)或原子公式的否定(負(fù)文字)P, Q, R 子句子句：若干文字的析取 PQR 在數(shù)理邏輯中，霍恩子句（Horn Clause）是帶有最多一個(gè)肯定文字的子句(文字的析取) Horn子句子句：子句L1L2 Ln中如果

21、至多只含一個(gè)正文字，那么該子句稱為Horn子句。Horn子句P Q1 Q2 Qn通常表示為：P Q1, Q2, , Qn2/20/202234華北電力大學(xué)華北電力大學(xué)Horn邏輯邏輯 Horn子句的類型：子句的類型： 過程：P Q1, Q2, , Qn 事實(shí)： P 目標(biāo)： Q1, Q2, , Qn 空子句： 2/20/202235華北電力大學(xué)華北電力大學(xué)Horn邏輯邏輯例例: 過程：AT(dog, x) AT(Zhang, x) 事實(shí)：AT(Zhang, train) 目標(biāo)： AT(dog, train) 首先目標(biāo)中過程調(diào)用AT(dog, train)與過程名AT(dog, x)匹配，合一為t

22、rain/x，調(diào)用過程AT(Zhang, x)，從而產(chǎn)生新目標(biāo) AT(Zhang, train)，與事實(shí)匹配，產(chǎn)生目標(biāo) 。因而調(diào)用成功，輸出“是”。2/20/202236華北電力大學(xué)華北電力大學(xué)Prolog的基本特點(diǎn)的基本特點(diǎn) Prolog既是一種邏輯程序設(shè)計(jì)語言，又是一個(gè)邏輯系統(tǒng) Prolog是一種描述性語言，是一種面向問題的語言，只需要告訴它要做什么，即給出問題的形式描述，而不需要知道應(yīng)該如何做 Prolog完全依靠匹配、回溯來進(jìn)行搜索 Prolog有很強(qiáng)的描述能力2/20/202237華北電力大學(xué)華北電力大學(xué)內(nèi)容內(nèi)容 綜述 函數(shù)型程序設(shè)計(jì)語言LISP 邏輯性程序設(shè)計(jì)語言PROLOG PR

23、OLOG程序設(shè)計(jì) PROLOG語句 PROLOG程序 PROLOG程序的運(yùn)行機(jī)理 其它2/20/202238華北電力大學(xué)華北電力大學(xué)PROLOG的語句的語句 PROLOG語言只有三種語句，分別為: 事實(shí)(fact) 規(guī)則(rule) 問題(question) 2/20/202239華北電力大學(xué)華北電力大學(xué)事實(shí)事實(shí)(fact)格式格式 (). 謂詞名是以小寫英文字母打頭的字母、數(shù)字、下劃線等組成的字符串 項(xiàng)表是以逗號(hào)隔開的項(xiàng)序列 例如：student(john). like( mary ,music).功能功能 一般表示對象的性質(zhì)或關(guān)系一般表示對象的性質(zhì)或關(guān)系 作為特殊情形，事實(shí)也可以只有謂詞名

24、而無參量 例如：abc. repeat.2/20/202240華北電力大學(xué)華北電力大學(xué)規(guī)則規(guī)則(rule)格式格式 ():-(),(). “:-”號(hào)表示“if” 左部的謂詞是規(guī)則的結(jié)論（亦稱為頭） 右部的謂詞是規(guī)則的前提（亦稱為體） 表示零次或多次重復(fù) 逗號(hào)表示and(邏輯與)例如：bird(X):-animal(X),has(X,feather). grandfather(X,Y):-father(X,Z),father(Z,Y).功能功能 一般表示對象間的因果關(guān)系、蘊(yùn)含關(guān)系或?qū)?yīng)關(guān)系一般表示對象間的因果關(guān)系、蘊(yùn)含關(guān)系或?qū)?yīng)關(guān)系 作為特殊情形，規(guī)則中的謂詞也可以只有謂詞名而無參量例如：run

25、:-start,step1(X),step2(X),end.2/20/202241華北電力大學(xué)華北電力大學(xué)問題問題(question) 格式格式 ?-(),(). 例如： ?-student(john). ?-like(mary,X). 功能功能 問題表示用戶的詢問，是程序運(yùn)行的目標(biāo)問題表示用戶的詢問，是程序運(yùn)行的目標(biāo)2/20/202242華北電力大學(xué)華北電力大學(xué)Prolog的一些內(nèi)建謂詞的一些內(nèi)建謂詞 Prolog提供了一些有用的內(nèi)建謂詞(Built-in Predicates) 內(nèi)建謂詞和用戶定義謂詞使用方式類似 常用內(nèi)建謂詞 等價(jià)謂詞： = 永真和永假： true; fail 載入程序文

26、件： consult/1 終端輸出 write/1; nl/02/20/202243華北電力大學(xué)華北電力大學(xué)PROLOG程序程序 PROLOG程序一般由一組事實(shí)、規(guī)則和問題組成。問題是程序執(zhí)行的起點(diǎn)，稱為程序的目標(biāo)。 例如下面就是一個(gè)PROLOG程序。 likes(bell,sports). likes(mary,music). likes(mary,sports). likes(jane ,smith). friend(john,X):-likes(X,reading),likes(X,music). friend(john,X):-likes(X,sports),likes(X,music

27、). ?-friend(john,Y).四條事實(shí)兩條規(guī)則一個(gè)問題2/20/202244華北電力大學(xué)華北電力大學(xué)PROLOG程序的運(yùn)行機(jī)理程序的運(yùn)行機(jī)理 PROLOG程序的運(yùn)行是從目標(biāo)出發(fā)，并不斷進(jìn)行匹配、合一、歸結(jié)，有時(shí)還要回溯，直到目標(biāo)被完全滿足或不能滿足時(shí)為止 匹配？ 合一？ 回溯？2/20/202245華北電力大學(xué)華北電力大學(xué)PROLOG程序的運(yùn)行機(jī)理程序的運(yùn)行機(jī)理 自由變量與約束變量自由變量與約束變量 PROLOG中稱無值的變量為自由變量，有值的變量為約束變量 一個(gè)變量取了某值就說該變量約束于某值 或者說該變量被某值所約束 或者說該變量被某值實(shí)例化了2/20/202246華北電力大學(xué)華

28、北電力大學(xué)PROLOG程序的運(yùn)行機(jī)理程序的運(yùn)行機(jī)理 匹配合一匹配合一：指兩個(gè)謂詞的名相同，參量項(xiàng)的個(gè)數(shù)相同，參量類型對應(yīng)相同，并且對應(yīng)參量項(xiàng)滿足下列條件之一 (1)如果兩個(gè)都是常量，則必須完全相同(2)如果兩個(gè)都是約束變量，則兩個(gè)約束值必須相同(3)如果其中一個(gè)是常量，一個(gè)是約束變量，則約束值與常量必須相同(4)至少有一個(gè)是自由變量例如：下面的兩個(gè)謂詞 pre1(“ob1”,“ob2”,Z). pre1(ob1,X,Y). 只有當(dāng)變量X被約束為ob2，且Y、Z的約束值相同或者至少有一個(gè)是自由變量時(shí)，它們才是匹配合一的2/20/202247華北電力大學(xué)華北電力大學(xué)PROLOG程序的運(yùn)行機(jī)理程序的

29、運(yùn)行機(jī)理 回溯回溯 在程序運(yùn)行期間，當(dāng)某一個(gè)子目標(biāo)不能滿足（即謂詞匹配失?。r(shí)，控制就返回到前一個(gè)已經(jīng)滿足的子目標(biāo)（如果存在的話），并撤消其有關(guān)變量的約束值，然后再使其重新滿足。成功后，再繼續(xù)滿足原子目標(biāo)。如果失敗的子目標(biāo)前再無子目標(biāo)，則控制就返回到該子目標(biāo)的上一級目標(biāo)（即該子目標(biāo)謂詞所在規(guī)則的頭部）使它重新匹配。回溯也是PROLOG的一個(gè)重要機(jī)制2/20/202248華北電力大學(xué)華北電力大學(xué) 設(shè)所給的詢問是 ?-friend(john,Y).(john和誰是朋友?) 則求解目標(biāo)為 friend(john,Y). 這時(shí)，系統(tǒng)對程序進(jìn)行掃描，尋找能與目標(biāo)謂詞匹配合一的事實(shí)或規(guī)則頭部。顯然，程序中

30、前面的四條事實(shí)均不能與目標(biāo)匹配，而第五個(gè)語句的左端即規(guī)則PROLOG程序的運(yùn)行過程程序的運(yùn)行過程2/20/202249華北電力大學(xué)華北電力大學(xué) friend(john,X):-likes(X,reading),likes(X,music). 頭部可與目標(biāo)謂詞匹配合一。但由于這個(gè)語句又是一個(gè)規(guī)則，所以其結(jié)論要成立則必須其前提全部成立。于是，對原目標(biāo)的求解就轉(zhuǎn)化為對新目標(biāo) likes(X,reading),likes(X,music). 的求解。這實(shí)際是經(jīng)歸結(jié)，規(guī)則頭部被消去，而目標(biāo)子句變?yōu)??-likes(X,reading),likes(X,music). 現(xiàn)在依次對子目標(biāo) likes(X,r

31、eading)和likes(X,music) 求解PROLOG程序的運(yùn)行過程程序的運(yùn)行過程2/20/202250華北電力大學(xué)華北電力大學(xué) 子目標(biāo)的求解過程與主目標(biāo)完全一樣，也是從頭對程序進(jìn)行掃描，不斷進(jìn)行測試和匹配合一等，直到匹配成功或掃描完整個(gè)程序?yàn)橹埂？梢钥闯觯瑢Φ谝粋€(gè)子目標(biāo)like(X,reading)的求解因無可匹配的事實(shí)和規(guī)則而立即失敗，進(jìn)而導(dǎo)致規(guī)則 friend(john,X):-likes(X,reading),likes(X,music).的整體失敗。于是，剛才的子目標(biāo) likes(X,reading)和likes(X,music) PROLOG程序的運(yùn)行過程程序的運(yùn)行過程2/

32、20/202251華北電力大學(xué)華北電力大學(xué) 被撤消，系統(tǒng)又回溯到原目標(biāo)friend(john,X) 這時(shí)，系統(tǒng)從該目標(biāo)剛才的匹配語句處（即第五句）向下繼續(xù)掃描程序中的子句，試圖重新使原目標(biāo)匹配，結(jié)果發(fā)現(xiàn)第六條語句的左部，即規(guī)則 friend(john,X):-likes(X,sports),likes(X,music). 的頭部可與目標(biāo)為謂詞匹配。但由于這個(gè)語句又是一個(gè)規(guī)則，于是，這時(shí)對原目標(biāo)的求解，就又轉(zhuǎn)化為依次對子目標(biāo) likes(X,sports)和likes(X,music)PROLOG程序的運(yùn)行過程程序的運(yùn)行過程2/20/202252華北電力大學(xué)華北電力大學(xué) 的求解。這次子目標(biāo)lik

33、es(X,sports)與程序中的事實(shí)立即匹配成功，且變量X被約束為bell。于是，系統(tǒng)便接著求解第二個(gè)子目標(biāo)。由于變量X已被約束，所以這時(shí)第二個(gè)子目標(biāo)實(shí)際上已變成了 likes(bell,music). 由于程序中不存在事實(shí)likes(bell,music)，所以該目標(biāo)的求解失敗。于是，系統(tǒng)就放棄這個(gè)子目標(biāo)，并使變量X恢復(fù)為自由變量，然后回溯到第一個(gè)子目標(biāo)，重新對它進(jìn)行求解。由于系統(tǒng)已經(jīng)記住了剛才已同第一子目標(biāo)謂詞匹配過的事實(shí)的位置，所以重新求解時(shí)，便從下一個(gè)事實(shí)開始測試。 PROLOG程序的運(yùn)行過程程序的運(yùn)行過程2/20/202253華北電力大學(xué)華北電力大學(xué) 易見，當(dāng)測試到程序中第三個(gè)事實(shí)

34、時(shí)，第一個(gè)子目標(biāo)便求解成功，且變量X被約束為mary。這樣，第二個(gè)子目標(biāo)也就變成了 likes(mary,music). 再對它進(jìn)行求解。這次很快成功。 由于兩個(gè)子目標(biāo)都求解成功，所以，原目標(biāo)friend(john,Y)也成功，且變量Y被約束為mary(由Y與X的合一關(guān)系)。于是，系統(tǒng)回答： Y=mary 程序運(yùn)行結(jié)束。 上面只給出了問題的一個(gè)解。如果需要和可能的話，系統(tǒng)還可把john的所有朋友都找出來。我們把上述程序的運(yùn)行過程再用示意圖描述如下：PROLOG程序的運(yùn)行過程程序的運(yùn)行過程2/20/202254華北電力大學(xué)華北電力大學(xué)圖 PROLOG程序運(yùn)行機(jī)理示例 PROLOG程序的運(yùn)行過程程

35、序的運(yùn)行過程2/20/202255華北電力大學(xué)華北電力大學(xué)循環(huán)循環(huán) Prolog可以實(shí)現(xiàn)計(jì)數(shù)循環(huán)。例：student(1,張三,90.2).student(2,李四,96.5).student(3,王五,96.4).print:-student(Number,Name,Score),write(Number),write(Name),write(Score),nl,Number=3.print2:-student(Number,Name,Score),write(Number),write(Name),write(Score),nl,Number=2. Prolog可以實(shí)現(xiàn)不計(jì)數(shù)循環(huán)（Do循環(huán)

36、）print1:-student(Number,Name,Score),write(Number),write(Name),write(Score),nl,fail.2/20/202256華北電力大學(xué)華北電力大學(xué)表處理與遞歸表處理與遞歸 表是有若干元素的有序序列，表中元素也可以為表 PROLOG中采用一對方括號(hào) 把表元素括起來，每個(gè)元素間用逗號(hào)或空格分開，例如： m,n,d,f 在PROLOG內(nèi)引入“”符號(hào)，如H|T表示一個(gè)以H為首，以T為尾的表 例如表m,n,d,f中，表頭為m表尾為n,d,fapple,orange,banana apple orange,bananaa,b,c,d,e a

37、,b c,d,e prolog prolog 無定義 無定義 2/20/202257華北電力大學(xué)華北電力大學(xué)表處理與遞歸表處理與遞歸 例：設(shè)計(jì)一個(gè)能判斷對象X是表L的成員成員的程序 分析：（1）如果X與L的表頭是同一個(gè)對象，則X是L的成員 （2）如果X是L的表尾的成員，則X是L的成員 程序：member(X,X|Tail).member(X,Head|Tail):-member(X,Tail).2/20/202258華北電力大學(xué)華北電力大學(xué)表處理與遞歸表處理與遞歸 表的拼接拼接程序，即把兩個(gè)表連接成一個(gè)表 append(,L,L). append(H|T,L2,H|Tn):-append(T,

38、L2,Tn). 例： :- ?-append(1,2,3,4,5,1,2,3,4,5). yes:- ?-append(1,2,3,4,5,1,2,3,4,5,6). no2/20/202259華北電力大學(xué)華北電力大學(xué)表處理與遞歸表處理與遞歸 表的輸出輸出print().print(H|T):-write(H),print(T). ?-print(3|4,5,6,7). ?-print(1,2,3).2/20/202260華北電力大學(xué)華北電力大學(xué)表處理與遞歸表處理與遞歸 例：表的倒置倒置reverse(,).reverse(H|T,L):-reverse(T,L1),append(L1,H,L).:- ?-reverse(1,2,3,X).X=3,2,12/20/202261華北電力大學(xué)華北電力大學(xué)截?cái)嘟財(cái)?直到目前為止，我們都一直在使用Prolog內(nèi)建的回溯功能。使用此功能可以方便地寫出結(jié)構(gòu)緊湊的謂詞來 但是，并不是所有的回溯都是必須的，這時(shí)我們需要能夠人工地控制回溯過程 Prolog提供了完成此功能的謂詞，叫做cut，使用符號(hào)！來表示，如果在cut處產(chǎn)生回溯，它會(huì)自動(dòng)地失敗，而不去進(jìn)行其它的選擇2/20/202262華北電力大學(xué)華北電力大學(xué)截?cái)嘟?/p>