接下來三章提供了大量的 Lisp 程序例子。選擇這些例子來說明那些較長(zhǎng)的程序所采取的形式，和 Lisp 所擅長(zhǎng)解決的問題類型。
在這一章中我們將要寫一個(gè)基于一組?`if-then`?規(guī)則的推論程序。這是一個(gè)經(jīng)典的例子 —— 不僅在于其經(jīng)常出現(xiàn)在教科書上，還因?yàn)樗从沉?Lisp 作為一個(gè)“符號(hào)計(jì)算”語(yǔ)言的本意。這個(gè)例子散發(fā)著很多早期 Lisp 程序的氣息。
[TOC]
## 15.1 目標(biāo) (The Aim)[](http://acl.readthedocs.org/en/latest/zhCN/ch15-cn.html#the-aim "Permalink to this headline")
在這個(gè)程序中，我們將用一種熟悉的形式來表示信息：包含單個(gè)判斷式，以及跟在之后的零個(gè)或多個(gè)參數(shù)所組成的列表。要表示 Donald 是 Nancy 的家長(zhǎng)，我們可以這樣寫：
~~~
(parent donald nancy)
~~~
事實(shí)上，我們的程序是要表示一些從已有的事實(shí)作出推斷的規(guī)則。我們可以這樣來表示規(guī)則：
~~~
(<- head body)
~~~
其中，?`head`?是?**那么...部分**?(then-part)，?`body`?是?**如果...部分**?(if-part)。在?`head`?和?`body`?中我們使用以問號(hào)為前綴的符號(hào)來表示變量。所以下面這個(gè)規(guī)則：
~~~
(<- (child ?x ?y) (parent ?y ?x))
~~~
表示：如果 y 是 x 的家長(zhǎng)，那么 x 是 y 的孩子；更恰當(dāng)?shù)卣f，我們可以通過證明?`(parent?y?x)`?來證明?`(child?x?y)`?的所表示的事實(shí)。
可以把規(guī)則中的?*body*?部分(if-part) 寫成一個(gè)復(fù)雜的表達(dá)式，其中包含?`and`?,?`or`?和?`not`?等邏輯操作。所以當(dāng)我們想要表達(dá) “如果 x 是 y 的家長(zhǎng)，并且 x 是男性，那么 x 是 y 的父親” 這樣的規(guī)則，我們可以寫：
~~~
(<- (father ?x ?y) (and (parent ?x ?y) (male ?x)))
~~~
一些規(guī)則可能依賴另一些規(guī)則所產(chǎn)生的事實(shí)。比如，我們寫的第一個(gè)規(guī)則是為了證明?`(child?x?y)`?的事實(shí)。如果我們定義如下規(guī)則：
~~~
(<- (daughter ?x ?y) (and (child ?x ?y) (female ?x)))
~~~
然后使用它來證明?`(daughter?x?y)`?可能導(dǎo)致程序使用第一個(gè)規(guī)則去證明?`(child?x?y)`?。
表達(dá)式的證明可以回溯任意數(shù)量的規(guī)則，只要它最終結(jié)束于給出的已知事實(shí)。這個(gè)過程有時(shí)候被稱為反向鏈接 (backward-chaining)。之所以說?*反向*?(backward) 是因?yàn)檫@一類推論先考慮?*head*?部分，這是為了在繼續(xù)證明?*body*?部分之前檢查規(guī)則是否有效。*鏈接*?(chaining) 來源于規(guī)則之間的依賴關(guān)系，從我們想要證明的內(nèi)容到我們的已知條件組成一個(gè)鏈接 (盡管事實(shí)上它更像一棵樹)。?[λ](http://acl.readthedocs.org/en/latest/zhCN/notes-cn.html#notes-248)
## 15.2 匹配 (Matching)[](http://acl.readthedocs.org/en/latest/zhCN/ch15-cn.html#matching "Permalink to this headline")
我們需要有一個(gè)函數(shù)來做模式匹配以完成我們的反向鏈接 (back-chaining) 程序，這個(gè)函數(shù)能夠比較兩個(gè)包含變量的列表，它會(huì)檢查在給變量賦值后是否可以使兩個(gè)列表相等。舉例，如果?`?x`?和?`?y`?是變量，那么下面兩個(gè)列表：
~~~
(p ?x ?y c ?x)
(p a b c a)
~~~
當(dāng)?`?x?=?a`?且?`?y?=?b`?時(shí)匹配，而下面兩個(gè)列表：
~~~
(p ?x b ?y a)
(p ?y b c a)
~~~
當(dāng)?`?x?=??y?=?c`?時(shí)匹配。
我們有一個(gè)?`match`?函數(shù)，它接受兩棵樹，如果這兩棵樹能匹配，則返回一個(gè)關(guān)聯(lián)列表（assoc-list）來顯示他們是如何匹配的：
~~~
(defun match (x y &optional binds)
(cond
((eql x y) (values binds t))
((assoc x binds) (match (binding x binds) y binds))
((assoc y binds) (match x (binding y binds) binds))
((var? x) (values (cons (cons x y) binds) t))
((var? y) (values (cons (cons y x) binds) t))
(t
(when (and (consp x) (consp y))
(multiple-value-bind (b2 yes)
(match (car x) (car y) binds)
(and yes (match (cdr x) (cdr y) b2)))))))
(defun var? (x)
(and (symbolp x)
(eql (char (symbol-name x) 0) #\?)))
(defun binding (x binds)
(let ((b (assoc x binds)))
(if b
(or (binding (cdr b) binds)
(cdr b)))))
~~~
**圖 15.1: 匹配函數(shù)。**
~~~
> (match '(p a b c a) '(p ?x ?y c ?x))
((?Y . B) (?X . A))
T
> (match '(p ?x b ?y a) '(p ?y b c a))
((?Y . C) (?X . ?Y))
T
> (match '(a b c) '(a a a))
NIL
~~~
當(dāng)?`match`?函數(shù)逐個(gè)元素地比較它的參數(shù)時(shí)候，它把?`binds`?參數(shù)中的值分配給變量，這被稱為綁定 (bindings)。如果成功匹配，`match`?函數(shù)返回生成的綁定；否則，返回?`nil`?。當(dāng)然并不是所有成功的匹配都會(huì)產(chǎn)生綁定，我們的?`match`?函數(shù)就像?`gethash`?函數(shù)那樣返回第二個(gè)值來表明匹配成功：
~~~
> (match '(p ?x) '(p ?x))
NIL
T
~~~
如果?`match`?函數(shù)像上面那樣返回?`nil`?和?`t`?，表明這是一個(gè)沒有產(chǎn)生綁定的成功匹配。下面用中文來描述?`match`?算法是如何工作的：
1. 如果 x 和 y 在?`eql`?上相等那么它們匹配；否則，
2. 如果 x 是一個(gè)已綁定的變量，并且綁定匹配 y ，那么它們匹配；否則，
3. 如果 y 是一個(gè)已綁定的變量，并且綁定匹配 x ，那么它們匹配；否則，
4. 如果 x 是一個(gè)未綁定的變量，那么它們匹配，并且為 x 建立一個(gè)綁定；否則，
5. 如果 y 是一個(gè)未綁定的變量，那么它們匹配，并且為 y 建立一個(gè)綁定；否則，
6. 如果 x 和 y 都是?`cons`?，并且它們的?`car`?匹配，由此產(chǎn)生的綁定又讓?`cdr`?匹配，那么它們匹配。
下面是一個(gè)例子，按順序來說明以上六種情況：
~~~
> (match '(p ?v b ?x d (?z ?z))
'(p a ?w c ?y ( e e))
'((?v . a) (?w . b)))
((?Z . E) (?Y . D) (?X . C) (?V . A) (?W . B))
T
~~~
`match`?函數(shù)通過調(diào)用?`binding`?函數(shù)在一個(gè)綁定列表中尋找變量（如果有的話）所關(guān)聯(lián)的值。這個(gè)函數(shù)必須是遞歸的，因?yàn)橛羞@樣的情況 “匹配建立一個(gè)綁定列表，而列表中變量只是間接關(guān)聯(lián)到它的值：?`?x`?可能被綁定到一個(gè)包含?`(?x?.??y)`?和?`(?y?.?a)`?的列表”：
~~~
> (match '(?x a) '(?y ?y))
((?Y . A) (?X . ?Y))
T
~~~
先匹配?`?x`?和?`?y`?，然后匹配?`?y`?和?`a`?，我們間接確定?`?x`?是?`a`?。
## 15.3 回答查詢 (Answering Queries)[](http://acl.readthedocs.org/en/latest/zhCN/ch15-cn.html#answering-queries "Permalink to this headline")
在介紹了綁定的概念之后，我們可以更準(zhǔn)確的說一下我們的程序?qū)⒁鍪裁矗核玫揭粋€(gè)可能包含變量的表達(dá)式，根據(jù)我們給定的事實(shí)和規(guī)則返回使它正確的所有綁定。比如，我們只有下面這個(gè)事實(shí)：
~~~
(parent donald nancy)
~~~
然后我們想讓程序證明：
~~~
(parent ?x ?y)
~~~
它會(huì)返回像下面這樣的表達(dá)：
~~~
(((?x . donald) (?y . nancy)))
~~~
它告訴我們只有一個(gè)可以讓這個(gè)表達(dá)式為真的方法：?`?x`?是?`donald`?并且?`?y`?是?`nancy`?。
在通往目標(biāo)的路上，我們已經(jīng)有了一個(gè)的重要部分：一個(gè)匹配函數(shù)。 下面是用來定義規(guī)則的一段代碼：
~~~
(defvar *rules* (make-hash-table))
(defmacro <- (con &optional ant)
`(length (push (cons (cdr ',con) ',ant)
(gethash (car ',con) *rules*))))
~~~
**圖 15.2 定義規(guī)則**
規(guī)則將被包含于一個(gè)叫做?`*rules*`?的哈希表，通過頭部 (head) 的判斷式構(gòu)建這個(gè)哈系表。這樣做加強(qiáng)了我們無法使用判斷式中的變量的限制。雖然我們可以通過把所有這樣的規(guī)則放在分離的列表中來消除限制，但是如果這樣做，當(dāng)我們需要證明某件事的時(shí)侯不得不和每一個(gè)列表進(jìn)行匹配。
我們將要使用同一個(gè)宏?`<-`?去定義事實(shí) (facts)和規(guī)則 (rules)。一個(gè)事實(shí)將被表示成一個(gè)沒有?*body*?部分的規(guī)則。這和我們對(duì)規(guī)則的定義保持一致。一個(gè)規(guī)則告訴我們你可以通過證明?*body*?部分來證明?*head*?部分，所以沒有?*body*?部分的規(guī)則意味著你不需要通過證明任何東西來證明?*head*?部分。這里有兩個(gè)對(duì)應(yīng)的例子：
~~~
> (<- (parent donald nancy))
1
> (<- (child ?x ?y) (parent ?y ?x))
1
~~~
調(diào)用?`<-`?返回的是給定判斷式下存儲(chǔ)的規(guī)則數(shù)量；用?`length`?函數(shù)來包裝?`push`?能使我們免于看到頂層中的一大堆返回值。
下面是我們的推論程序所需的大多數(shù)代碼：
~~~
(defun prove (expr &optional binds)
(case (car expr)
(and (prove-and (reverse (cdr expr)) binds))
(or (prove-or (cdr expr) binds))
(not (prove-not (cadr expr) binds))
(t (prove-simple (car expr) (cdr expr) binds))))
(defun prove-simple (pred args binds)
(mapcan #'(lambda (r)
(multiple-value-bind (b2 yes)
(match args (car r)
binds)
(when yes
(if (cdr r)
(prove (cdr r) b2)
(list b2)))))
(mapcar #'change-vars
(gethash pred *rules*))))
(defun change-vars (r)
(sublis (mapcar #'(lambda (v) (cons v (gensym "?")))
(vars-in r))
r))
(defun vars-in (expr)
(if (atom expr)
(if (var? expr) (list expr))
(union (vars-in (car expr))
(vars-in (cdr expr)))))
~~~
**圖 15.3: 推論。**
上面代碼中的?`prove`?函數(shù)是推論進(jìn)行的樞紐。它接受一個(gè)表達(dá)式和一個(gè)可選的綁定列表作為參數(shù)。如果表達(dá)式不包含邏輯操作，它調(diào)用?`prove-simple`?函數(shù)，前面所說的鏈接 (chaining)正是在這個(gè)函數(shù)里產(chǎn)生的。這個(gè)函數(shù)查看所有擁有正確判斷式的規(guī)則，并嘗試對(duì)每一個(gè)規(guī)則的?*head*?部分和它想要證明的事實(shí)做匹配。對(duì)于每一個(gè)匹配的?*head*?，使用匹配所產(chǎn)生的新的綁定在?*body*?上調(diào)用?`prove`。對(duì)?`prove`?的調(diào)用所產(chǎn)生的綁定列表被?`mapcan`?收集并返回：
~~~
> (prove-simple 'parent '(donald nancy) nil)
(NIL)
> (prove-simple 'child '(?x ?y) nil)
(((#:?6 . NANCY) (#:?5 . DONALD) (?Y . #:?5) (?X . #:?6)))
~~~
以上兩個(gè)返回值指出有一種方法可以證明我們的問題。（一個(gè)失敗的證明將返回 nil。）第一個(gè)例子產(chǎn)生了一組空的綁定，第二個(gè)例子產(chǎn)生了這樣的綁定：?`?x`?和?`?y`?被（間接）綁定到?`nancy`?和?`donald`?。
順便說一句，這是一個(gè)很好的例子來實(shí)踐 2.13 節(jié)提出的觀點(diǎn)。因?yàn)槲覀冇煤瘮?shù)式的風(fēng)格來寫這個(gè)程序，所以可以交互式地測(cè)試每一個(gè)函數(shù)。
第二個(gè)例子返回的值里那些?*gensyms*?是怎么回事？如果我們打算使用含有變量的規(guī)則，我們需要避免兩個(gè)規(guī)則恰好包含相同的變量。如果我們定義如下兩條規(guī)則：
~~~
(<- (child ?x ?y) (parent ?y ?x))
(<- (daughter ?y ?x) (and (child ?y ?x) (female ?y)))
~~~
第一條規(guī)則要表達(dá)的意思是：對(duì)于任何的?`x`?和?`y`?， 如果?`y`?是?`x`?的家長(zhǎng)，則?`x`?是?`y`?的孩子。第二條則是：對(duì)于任何的?`x`?和?`y`?， 如果?`y`?是?`x`?的孩子并且?`y`?是女性，則?`y`?是?`x`?的女兒。在每一條規(guī)則內(nèi)部，變量之間的關(guān)系是顯著的，但是兩條規(guī)則使用了相同的變量并非我們刻意為之。
如果我們使用上面所寫的規(guī)則，它們將不會(huì)按預(yù)期的方式工作。如果我們嘗試證明“ a 是 b 的女兒”，匹配到第二條規(guī)則的?*head*?部分時(shí)會(huì)將?`a`?綁定到?`?y`?，將?`b`?綁定到 ?x。我們無法用這樣的綁定匹配第一條規(guī)則的?*head*?部分：
~~~
> (match '(child ?y ?x)
'(child ?x ?y)
'((?y . a) (?x . b)))
NIL
~~~
為了保證一條規(guī)則中的變量只表示規(guī)則中各參數(shù)之間的關(guān)系，我們用?*gensyms*?來代替規(guī)則中的所有變量。這就是?`change-vars`?函數(shù)的目的。一個(gè)?*gensym*?不可能在另一個(gè)規(guī)則中作為變量出現(xiàn)。但是因?yàn)橐?guī)則可以是遞歸的，我們必須防止出現(xiàn)一個(gè)規(guī)則和自身沖突的可能性，所以在定義和使用一個(gè)規(guī)則時(shí)都要調(diào)用?`chabge-vars`?函數(shù)。
現(xiàn)在只剩下定義用以證明復(fù)雜表達(dá)式的函數(shù)了。下面就是需要的函數(shù)：
~~~
(defun prove-and (clauses binds)
(if (null clauses)
(list binds)
(mapcan #'(lambda (b)
(prove (car clauses) b))
(prove-and (cdr clauses) binds))))
(defun prove-or (clauses binds)
(mapcan #'(lambda (c) (prove c binds))
clauses))
(defun prove-not (clause binds)
(unless (prove clause binds)
(list binds)))
~~~
**圖 15.4 邏輯操作符 (Logical operators)**
操作一個(gè)?`or`?或者?`not`?表達(dá)式是非常簡(jiǎn)單的。操作?`or`?時(shí)，我們提取在?`or`?之間的每一個(gè)表達(dá)式返回的綁定。操作?`not`?時(shí)，當(dāng)且僅當(dāng)在?`not`?里的表達(dá)式產(chǎn)生?`none`?時(shí)，返回當(dāng)前的綁定。
`prove-and`?函數(shù)稍微復(fù)雜一點(diǎn)。它像一個(gè)過濾器，它用之后的表達(dá)式所建立的每一個(gè)綁定來證明第一個(gè)表達(dá)式。這將導(dǎo)致?`and`?里的表達(dá)式以相反的順序被求值。除非調(diào)用?`prove`?中的?`prove-and`?函數(shù)則會(huì)先逆轉(zhuǎn)它們。
現(xiàn)在我們有了一個(gè)可以工作的程序，但它不是很友好。必須要解析?`prove-and`?返回的綁定列表是令人厭煩的，它們會(huì)變得更長(zhǎng)隨著規(guī)則變得更加復(fù)雜。下面有一個(gè)宏來幫助我們更愉快地使用這個(gè)程序：
~~~
(defmacro with-answer (query &body body)
(let ((binds (gensym)))
`(dolist (,binds (prove ',query))
(let ,(mapcar #'(lambda (v)
`(,v (binding ',v ,binds)))
(vars-in query))
,@body))))
~~~
**圖 15.5 介面宏 (Interface macro)**
它接受一個(gè)?`query`?（不被求值）和若干表達(dá)式構(gòu)成的?`body`?作為參數(shù)，把?`query`?所生成的每一組綁定的值賦給?`query`?中對(duì)應(yīng)的模式變量，并計(jì)算?`body`?。
~~~
> (with-answer (parent ?x ?y)
(format t "~A is the parent of ~A.~%" ?x ?y))
DONALD is the parent of NANCY.
NIL
~~~
這個(gè)宏幫我們做了解析綁定的工作，同時(shí)為我們?cè)诔绦蛑惺褂?`prove`?提供了一個(gè)便捷的方法。下面是這個(gè)宏展開的情況：
~~~
(with-answer (p ?x ?y)
(f ?x ?y))
;;將被展開成下面的代碼
(dolist (#:g1 (prove '(p ?x ?y)))
(let ((?x (binding '?x #:g1))
(?y (binding '?y #:g1)))
(f ?x ?y)))
~~~
**圖 15.6: with-answer 調(diào)用的展開式**
下面是使用它的一個(gè)例子：
~~~
(<- (parent donald nancy))
(<- (parent donald debbie))
(<- (male donald))
(<- (father ?x ?y) (and (parent ?x ?y) (male ?x)))
(<- (= ?x ?y))
(<- (sibling ?x ?y) (and (parent ?z ?x)
(parent ?z ?y)
(not (= ?x ?y))))
;;我們可以像下面這樣做出推論
> (with-answer (father ?x ?y)
(format t "~A is the father of ~A.~%" ?x ?y))
DONALD is the father of DEBBIE.
DONALD is the father of NANCY.
NIL
> (with-answer (sibling ?x ?y))
(format t "~A is the sibling of ~A.~%" ?x ?y))
DEBBLE is the sibling of NANCY.
NANCY is the sibling of DEBBIE.
NIL
~~~
**圖 15.7: 使用中的程序**
## 15.4 分析 (Analysis)[](http://acl.readthedocs.org/en/latest/zhCN/ch15-cn.html#analysis "Permalink to this headline")
看上去，我們?cè)谶@一章中寫的代碼，是用簡(jiǎn)單自然的方式去實(shí)現(xiàn)這樣一個(gè)程序。事實(shí)上，它的效率非常差。我們?cè)谶@里是其實(shí)是做了一個(gè)解釋器。我們能夠把這個(gè)程序做得像一個(gè)編譯器。
這里做一個(gè)簡(jiǎn)單的描述。基本的思想是把整個(gè)程序打包到兩個(gè)宏?`<-`?和?`with-answer`?，把已有程序中在*運(yùn)行期*做的多數(shù)工作搬到*宏展開期*（在 10.7 節(jié)的?`avg`?可以看到這種構(gòu)思的雛形) 用函數(shù)取代列表來表示規(guī)則，我們不在運(yùn)行時(shí)用?`prove`?和?`prove-and`?這樣的函數(shù)來解釋表達(dá)式，而是用相應(yīng)的函數(shù)把表達(dá)式轉(zhuǎn)化成代碼。當(dāng)一個(gè)規(guī)則被定義的時(shí)候就有表達(dá)式可用。為什么要等到使用的時(shí)候才去分析它呢？這同樣適用于和?`<-`?調(diào)用了相同的函數(shù)來進(jìn)行宏展開的?`with-answer`?。
聽上去好像比我們已經(jīng)寫的這個(gè)程序復(fù)雜很多，但其實(shí)可能只是長(zhǎng)了兩三倍。想要學(xué)習(xí)這種技術(shù)的讀者可以看?*On Lisp*?或者*Paradigms of Artificial Intelligence Programming*?，這兩本書有一些使用這種風(fēng)格寫的示例程序。
