人工智能程序設計語言-2015課件

人工智能程序設計語言華北電力大學計算機系

11/7/20221內容綜述函數型程序設計語言LISP邏輯性程序設計語言PROLOGPROLOG程序設計11/7/20222華北電力大學內容綜述函數型程序設計語言LISP邏輯性程序設計語言PROLOGPROLOG程序設計11/7/20223華北電力大學綜述人工智能程序設計語言函數型語言邏輯性語言面向對象語言混合型語言11/7/20225華北電力大學綜述-函數型語言函數型語言LISP是一種函數型程序設計語言。LISP程序由一組函數組成，程序的執(zhí)行過程就是一系列的函數調用和求值過程。但LISP還不是純函數型語言，準確地講，它是基于λ--函數的語言。除LISP外，20世紀70年代J.Backus還提出了一種稱為FP的所謂純函數型程序設計語言。但該語言現(xiàn)在還限于理論研究，實現(xiàn)上還存在一定困難。11/7/20226華北電力大學綜述-邏輯型語言邏輯型語言邏輯型程序設計語言起源于PROLOG（PROgramminginLOGic）。PROLOG語言首先由法國馬塞大學的Colmerauer和它的研究小組于1972年研制成功，后來在歐洲得到進一步發(fā)展。特別是1981年日本宣布要以PROLOG作為他們正在研制的新一代計算機——智能計算機的核心語言，更使PROLOG舉世矚目，迅速風靡世界。11/7/20227華北電力大學綜述-邏輯型語言現(xiàn)在PROLOG幾乎在人工智能的所有領域都獲得了應用,成為與LISP并駕齊驅的甚至更加流行的智能程序設計語言。由于PROLOG語言是一種邏輯型程序設計語言,因此用它編寫的程序也就是邏輯程序,即在PROLOG程序中一般不需告訴計算機“怎么做”,而只需告訴它“做什么”。因此,PROLOG亦屬陳述性語言。與通常的過程性程序設計語言相比,PROLOG是更高級的語言。11/7/20228華北電力大學綜述-混合型語言混合型語言1.函數型與邏輯型相結合的語言

函數型與邏輯型語言的結合方式有耦合型和統(tǒng)一型兩類。統(tǒng)一型又可分為具有歸結語義的函數型語言和集成式語言兩個子類。耦合型語言意為將具有歸約語義的函數型語言和具有歸結語義的邏輯型語言組合在一起,并在二者之間提供一個接口而形成的一種混合型語言。其典型代表有：11/7/202210華北電力大學綜述-混合型語言2.函數型與面向對象相結合的語言

在LISP語言的基礎上再擴充面向對象機制而產生的語言,稱為函數型的面向對象程序設計語言(亦稱為面向對象的LISP)。這種語言現(xiàn)已成為一個家族,其中比較著名的有：(1)Flavors由MIT的LispMachine小組于1979年研制而成,它的基語言是SymbolicsCommonLISP。(2)LOOPS(Lisp-Object-OrientedProgrammingSystem)。它是在InterLisp-D環(huán)境上實現(xiàn)的基于LISP的OOP語言,由Xerox公司于1983年推出。11/7/202212華北電力大學綜述-混合型語言3.邏輯型與面向對象相結合的語言

這類語言著名的有:(1)SPOOL。日本IBM分部于1985年推出的以面向對象思想擴充的PROLOG語言。(2)Orient84K。Keio大學于1984年發(fā)表的基于PROLOG和Smalltalk的并行執(zhí)行語言。(3)Vulan。一種面向對象的邏輯型語言。11/7/202214華北電力大學內容綜述函數型程序設計語言LISP邏輯性程序設計語言PROLOGPROLOG程序設計11/7/202215華北電力大學函數型程序設計語言LISPLISP是第一個人工智能程序設計語言LIStProcessing，表處理語言1960年由MIT的麥卡錫和他的研究小組設計，擅長表處理，即符號處理許多人工智能系統(tǒng)用LISP語言編寫LISP被譽為人工智能的數學，是人工智能研究和開發(fā)的主要工具11/7/202216華北電力大學

函數型程序設計語言LISP

LISP語言的主要特點：LISP程序由一組函數組成，程序的執(zhí)行過程是函數的調用過程程序和數據在形式上是相同的，即都是符號表達式，簡稱為S─表達式遞歸是LISP語言的主要控制結構程序以交互方式運行11/7/202217華北電力大學LISP的程序結構LISP的程序一般由函數的定義和函數的調用兩部分組成。其一般格式為：(DEFUN(<函數名>(<形參表>)<函數體>)(<函數名>(<形參表>)<函數體>)

…(<函數名>(<形參表>)<函數體>))

(<函數名><實參表>)(<函數名><實參表>)…(<函數名><實參表>)“DEFUN”是定義函數的關鍵字“函數名”可以是系統(tǒng)的內部函數(名),也可以是用戶用DEFUN定義的函數(名)11/7/202218華北電力大學LISP的基本函數LISP的函數一律使用前綴表示方式,分為內部函數(基本或系統(tǒng)函數)和用戶自定義函數兩類基本函數的種類有十多個，僅給出主要的幾類表處理函數算數函數求值與賦值函數謂詞函數條件函數11/7/202220華北電力大學表處理函數表處理是LISP的主要特色，下面僅給出最常用的幾個：1)CAR函數 功能 取出表中的表頭。 如 CAR′(LISPLanguageProgram)) 返回值 LISP2)CDR函數功能 取出表中的表尾如 (CDR′(LISPLanguageProgram))返回值(LanguageProgram)11/7/202221華北電力大學算術函數LISP的算術表達式也是用函數表示的，稱為算術函數舉例說明(+25)表示2+5，返回值為7(-(*48)(/105))表示4×8-10/5，返回值為3011/7/202223華北電力大學求值與賦值函數撇號′是禁止求值函數QUOTE的簡寫形式賦值函數有多個SET函數是最基本的一個功能 把S─表達式賦給變量例如：(SET′X′8);X得到值8(SET′Y′(abc));Y得到值(abc)(SET′Z(CDRY);Z得到值(bc)11/7/202224華北電力大學謂詞函數

(2)相等謂詞EQUAL功能 判斷兩個參數是否邏輯相等例如：(EQUAL′a′a);返回T(EQUAL′(ab)′(ac));返回NIL

(3)判空表函數NULL功能 判斷參數是否為空表，是則返回T，否則返回NIL11/7/202226華北電力大學條件函數條件函數類似于分支語句，其作用是控制程序的流程

格式 (COND(P1e1) (P2e2) … (Pnen))其中Pi(i=1,...,n)為謂詞，ei(i=1,...,n)為一個或多個S─表達式

功能 如果P1為真，則COND函數的值為e1。否則，判斷P2，……直到某個Pi真為止，然后將對應的ei作為函數值。若沒有一個Pi的值為非NIL，則COND的返回值為NIL。特別地，Pi也可以為邏輯常量T，這時則對其對應的各表達式求值，并把最后一個表達式的值作為COND的返回值

11/7/202227華北電力大學條件函數例如：(COND((NULLx)0)((ATOMx)1)((LISTPx)(LENGTHx)))其語義是，若x的值為NIL，則COND的返回值為0;若x為原子，則COND的返回值為1;若x的值為表，則COND的返回值為表的長度11/7/202228華北電力大學例定義求N!的LISP函數階乘的公式是n!＝n×(n-1)!1!＝10!＝1其LISP函數如下：(DEFUNN!(n)(COND((=n0)1)((=n1)1)(T(*n(N!(-n1))))))該函數的最后一行中又調用了它自己→這個函數N!是遞歸定義的11/7/202230華北電力大學例HANOI（DEFUNHANOI（abcn）

當只有一個盤子時，直接將a上的盤子移動到c上

（COND（（＝n1）（MOVE－DISKac））

其他情況，通過遞歸，先將柱a上的n－1個盤子通過柱c移到柱b上

（T（HANOIacb（－n1））

再將柱a上的一個盤子移動到柱c上

（MOVE－DISKac）

最后再通過遞歸，將柱b上的n－1個盤子通過柱a移動到柱c上 （HANOIbac（－n1）））））函數MOVE-DISK起顯示的作用，表示從柱from到柱to移動了一個盤子

（DEFUNMOVE－DISK（fromto）

TERPRI是回車換行函數，PRINC是顯示參數的函數 （TERPRI）

（PRINC”MoveDiskFrom”）

（PRINCfrom）

（PRINC”To”）

（PRINCto））

11/7/202231華北電力大學內容綜述函數型程序設計語言LISP邏輯性程序設計語言PROLOGPROLOG程序設計11/7/202232華北電力大學邏輯型程序設計語言PROLOG1972年，法國馬賽大學的Alain.Colmerauer提出了Prolog的雛型1975年，Prolog被用于問題求解系統(tǒng)，此后在許多領域獲得了應用，如關系數據庫、定理證明、智能問題求解、計算機輔助設計、規(guī)劃生成等領域Prolog語言是以一階謂詞邏輯的Horn子句集為語法，以Robinson的消解原理為工具，加上深度優(yōu)先的控制策略而形成的人工智能通用程序設計語言11/7/202233華北電力大學Horn邏輯文字：原子公式(正文字)或原子公式的否定(負文字)P,Q,?R子句：若干文字的析取 ?P∨Q∨R在數理邏輯中，霍恩子句（HornClause）是帶有最多一個肯定文字的子句(文字的析取)Horn子句：子句L1∨L2∨…∨Ln中如果至多只含一個正文字，那么該子句稱為Horn子句。Horn子句P∨?Q1∨?Q2∨…∨?Qn通常表示為：PQ1,Q2,…,Qn11/7/202234華北電力大學Horn邏輯Horn子句的類型：過程：PQ1,Q2,…,Qn事實：P目標：Q1,Q2,…,Qn空子句：?11/7/202235華北電力大學Horn邏輯例:過程：AT(dog,x)

AT(Zhang,x) 事實：AT(Zhang,train)

目標：AT(dog,train)

首先目標中過程調用AT(dog,train)與過程名AT(dog,x)匹配，合一為{train/x}，調用過程AT(Zhang,x)，從而產生新目標

AT(Zhang,train)，與事實匹配，產生目標?。因而調用成功，輸出“是”。11/7/202236華北電力大學Prolog的基本特點Prolog既是一種邏輯程序設計語言，又是一個邏輯系統(tǒng)Prolog是一種描述性語言，是一種面向問題的語言，只需要告訴它要做什么，即給出問題的形式描述，而不需要知道應該如何做Prolog完全依靠匹配、回溯來進行搜索Prolog有很強的描述能力11/7/202237華北電力大學內容綜述函數型程序設計語言LISP邏輯性程序設計語言PROLOGPROLOG程序設計PROLOG語句PROLOG程序PROLOG程序的運行機理其它11/7/202238華北電力大學PROLOG的語句PROLOG語言只有三種語句，分別為:事實(fact)規(guī)則(rule)問題(question)

11/7/202239華北電力大學事實(fact)格式 <謂詞名>(<項表>).謂詞名是以小寫英文字母打頭的字母、數字、下劃線等組成的字符串項表是以逗號隔開的項序列例如：student(john).like(mary,music).功能一般表示對象的性質或關系

作為特殊情形，事實也可以只有謂詞名而無參量例如：abc.repeat.11/7/202240華北電力大學規(guī)則(rule)格式<謂詞名>(<項表>):-<謂詞名>(<項表>){,<謂詞名>(<項表>)}.“:-”號表示“if”左部的謂詞是規(guī)則的結論（亦稱為頭）右部的謂詞是規(guī)則的前提（亦稱為體）{}表示零次或多次重復逗號表示and(邏輯與)例如：bird(X):-animal(X),has(X,feather).grandfather(X,Y):-father(X,Z),father(Z,Y).功能一般表示對象間的因果關系、蘊含關系或對應關系作為特殊情形，規(guī)則中的謂詞也可以只有謂詞名而無參量例如：run:-start,step1(X),step2(X),end.11/7/202241華北電力大學問題(question)格式?-<謂詞名>(<項表>){,<謂詞名>(<項表>)}.例如：?-student(john).?-like(mary,X).功能問題表示用戶的詢問，是程序運行的目標11/7/202242華北電力大學Prolog的一些內建謂詞Prolog提供了一些有用的內建謂詞(Built-inPredicates)內建謂詞和用戶定義謂詞使用方式類似常用內建謂詞等價謂詞：=永真和永假：true;fail載入程序文件：consult/1終端輸出write/1;nl/011/7/202243華北電力大學PROLOG程序PROLOG程序一般由一組事實、規(guī)則和問題組成。問題是程序執(zhí)行的起點，稱為程序的目標。例如下面就是一個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).?-friend(john,Y).四條事實兩條規(guī)則一個問題11/7/202244華北電力大學PROLOG程序的運行機理PROLOG程序的運行是從目標出發(fā)，并不斷進行匹配、合一、歸結，有時還要回溯，直到目標被完全滿足或不能滿足時為止匹配？合一？回溯？11/7/202245華北電力大學PROLOG程序的運行機理自由變量與約束變量PROLOG中稱無值的變量為自由變量，有值的變量為約束變量一個變量取了某值就說該變量約束于某值或者說該變量被某值所約束或者說該變量被某值實例化了11/7/202246華北電力大學PROLOG程序的運行機理匹配合一：指兩個謂詞的名相同，參量項的個數相同，參量類型對應相同，并且對應參量項滿足下列條件之一(1)如果兩個都是常量，則必須完全相同(2)如果兩個都是約束變量，則兩個約束值必須相同(3)如果其中一個是常量，一個是約束變量，則約束值與常量必須相同(4)至少有一個是自由變量例如：下面的兩個謂詞

pre1(“ob1”,“ob2”,Z).pre1("ob1",X,Y).只有當變量X被約束為"ob2"，且Y、Z的約束值相同或者至少有一個是自由變量時，它們才是匹配合一的11/7/202247華北電力大學PROLOG程序的運行機理回溯在程序運行期間，當某一個子目標不能滿足（即謂詞匹配失?。r，控制就返回到前一個已經滿足的子目標（如果存在的話），并撤消其有關變量的約束值，然后再使其重新滿足。成功后，再繼續(xù)滿足原子目標。如果失敗的子目標前再無子目標，則控制就返回到該子目標的上一級目標（即該子目標謂詞所在規(guī)則的頭部）使它重新匹配?；厮菀彩荘ROLOG的一個重要機制11/7/202248華北電力大學設所給的詢問是?-friend(john,Y).(john和誰是朋友?)則求解目標為friend(john,Y).這時，系統(tǒng)對程序進行掃描，尋找能與目標謂詞匹配合一的事實或規(guī)則頭部。顯然，程序中前面的四條事實均不能與目標匹配，而第五個語句的左端即規(guī)則PROLOG程序的運行過程11/7/202249華北電力大學friend(john,X):-likes(X,reading),likes(X,music).頭部可與目標謂詞匹配合一。但由于這個語句又是一個規(guī)則，所以其結論要成立則必須其前提全部成立。于是，對原目標的求解就轉化為對新目標likes(X,reading),likes(X,music).的求解。這實際是經歸結，規(guī)則頭部被消去，而目標子句變?yōu)?-likes(X,reading),likes(X,music).現(xiàn)在依次對子目標likes(X,reading)和likes(X,music)求解PROLOG程序的運行過程11/7/202250華北電力大學子目標的求解過程與主目標完全一樣，也是從頭對程序進行掃描，不斷進行測試和匹配合一等，直到匹配成功或掃描完整個程序為止?？梢钥闯?，對第一個子目標like(X,reading)的求解因無可匹配的事實和規(guī)則而立即失敗，進而導致規(guī)則friend(john,X):-likes(X,reading),likes(X,music).的整體失敗。于是，剛才的子目標likes(X,reading)和likes(X,music)PROLOG程序的運行過程11/7/202251華北電力大學被撤消，系統(tǒng)又回溯到原目標friend(john,X)這時，系統(tǒng)從該目標剛才的匹配語句處（即第五句）向下繼續(xù)掃描程序中的子句，試圖重新使原目標匹配，結果發(fā)現(xiàn)第六條語句的左部，即規(guī)則friend(john,X):-likes(X,sports),likes(X,music).的頭部可與目標為謂詞匹配。但由于這個語句又是一個規(guī)則，于是，這時對原目標的求解，就又轉化為依次對子目標likes(X,sports)和likes(X,music)PROLOG程序的運行過程11/7/202252華北電力大學的求解。這次子目標likes(X,sports)與程序中的事實立即匹配成功，且變量X被約束為bell。于是，系統(tǒng)便接著求解第二個子目標。由于變量X已被約束，所以這時第二個子目標實際上已變成了likes(bell,music).由于程序中不存在事實likes(bell,music)，所以該目標的求解失敗。于是，系統(tǒng)就放棄這個子目標，并使變量X恢復為自由變量，然后回溯到第一個子目標，重新對它進行求解。由于系統(tǒng)已經記住了剛才已同第一子目標謂詞匹配過的事實的位置，所以重新求解時，便從下一個事實開始測試。PROLOG程序的運行過程11/7/202253華北電力大學易見，當測試到程序中第三個事實時，第一個子目標便求解成功，且變量X被約束為mary。這樣，第二個子目標也就變成了likes(mary,music).再對它進行求解。這次很快成功。由于兩個子目標都求解成功，所以，原目標friend(john,Y)也成功，且變量Y被約束為mary(由Y與X的合一關系)。于是，系統(tǒng)回答：Y=mary程序運行結束。上面只給出了問題的一個解。如果需要和可能的話，系統(tǒng)還可把john的所有朋友都找出來。我們把上述程序的運行過程再用示意圖描述如下：PROLOG程序的運行過程11/7/202254華北電力大學圖PROLOG程序運行機理示例PROLOG程序的運行過程②①③④⑤⑥⑦⑧⑨11/7/202255華北電力大學循環(huán)Prolog可以實現(xiàn)計數循環(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可以實現(xiàn)不計數循環(huán)（Do循環(huán)）print1:-student(Number,Name,Score),write(Number),write(Name),write(Score),nl,fail.11/7/202256華北電力大學表處理與遞歸表是有若干元素的有序序列，表中元素也可以為表PROLOG中采用一對方括號[]把表元素括起來，每個元素間用逗號或空格分開，例如：

[m,n,d,f]在PROLOG內引入“｜”符號，如[H|T]表示一個以H為首，以T為尾的表例如表[m,n,d,f]中，表頭為m表尾為[n,d,f][apple,orange,banana]apple[orange,banana][[a,b],[c],[d,e]][a,b][[c],[d,e]]['prolog']'prolog'

[][]無定義無定義

11/7/202257華北電力大學表處理與遞歸例：設計一個能判斷對象X是表L的成員的程序分析：（1）如果X與L的表頭是同一個對象，則X是L的成員（2）如果X是L的表尾的成員，則X是L的成員程序：member(X,[X|Tail]).member(X,[Head|Tail]):-member(X,Tail).11/7/202258華北電力大學表處理與遞歸表的拼接程序，即把兩個表連接成一個表append([],L,L).append([H|T],L2,[H|Tn]):-append(T,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]).no11/7/202259華北電力大學表處理與遞歸表的輸出 print([]). print([H|T]):-write(H),print(T).?-print([3|[4,5,6,7]]).?-print([1,2,3]).11/7/202260華北電力大學表處理與遞歸例：表的倒置 reverse([],[]). reverse([H|T],L):-reverse(T,L1),append(L1,[H],L).:-?-reverse([1,2,3],X).X=[3,2,1]11/7/202261華北電力大學截斷直到目前為止，我們都一直在使用Prolog內建的回溯功能。使用此功能可以方便地寫出結構緊湊的謂詞來但是，并不是所有的回溯都是必須的，這時我們需要能夠人工地控制回溯過程Prolog提供了完成此功能的謂詞，叫做cut，使用符號！來表示，如果在cut處產生回溯，它會自動地失敗，而不去進行其它的選擇11/7/202262華北電力大學截斷—例子p(a).p(b).q(b).r