第十五章：示例：推論

接下來三章提供了大量的 Lisp 程序例子。選擇這些例子來說明那些較長的程序所采取的形式，和 Lisp 所擅長解決的問題類型。

在這一章中我們將要寫一個基于一組?if-then?規(guī)則的推論程序。這是一個經(jīng)典的例子 —— 不僅在于其經(jīng)常出現(xiàn)在教科書上，還因為它反映了 Lisp 作為一個“符號計算”語言的本意。這個例子散發(fā)著很多早期 Lisp 程序的氣息。

15.1 目標(biāo) (The Aim)

在這個程序中，我們將用一種熟悉的形式來表示信息：包含單個判斷式，以及跟在之后的零個或多個參數(shù)所組成的列表。要表示 Donald 是 Nancy 的家長，我們可以這樣寫：

(parent donald nancy)

事實上，我們的程序是要表示一些從已有的事實作出推斷的規(guī)則。我們可以這樣來表示規(guī)則：

(<- head body)

其中，?head?是?那么...部分?(then-part)，?body?是?如果...部分?(if-part)。在?head?和?body?中我們使用以問號為前綴的符號來表示變量。所以下面這個規(guī)則：

(<- (child ?x ?y) (parent ?y ?x))

表示：如果 y 是 x 的家長，那么 x 是 y 的孩子；更恰當(dāng)?shù)卣f，我們可以通過證明?(parent?y?x)?來證明?(child?x?y)?的所表示的事實。

可以把規(guī)則中的?body?部分(if-part) 寫成一個復(fù)雜的表達(dá)式，其中包含?and?,?or?和?not?等邏輯操作。所以當(dāng)我們想要表達(dá) “如果 x 是 y 的家長，并且 x 是男性，那么 x 是 y 的父親” 這樣的規(guī)則，我們可以寫：

(<- (father ?x ?y) (and (parent ?x ?y) (male ?x)))

一些規(guī)則可能依賴另一些規(guī)則所產(chǎn)生的事實。比如，我們寫的第一個規(guī)則是為了證明?(child?x?y)?的事實。如果我們定義如下規(guī)則：

(<- (daughter ?x ?y) (and (child ?x ?y) (female ?x)))

然后使用它來證明?(daughter?x?y)?可能導(dǎo)致程序使用第一個規(guī)則去證明?(child?x?y)?。

表達(dá)式的證明可以回溯任意數(shù)量的規(guī)則，只要它最終結(jié)束于給出的已知事實。這個過程有時候被稱為反向鏈接 (backward-chaining)。之所以說?反向?(backward) 是因為這一類推論先考慮?head?部分，這是為了在繼續(xù)證明?body?部分之前檢查規(guī)則是否有效。鏈接?(chaining) 來源于規(guī)則之間的依賴關(guān)系，從我們想要證明的內(nèi)容到我們的已知條件組成一個鏈接 (盡管事實上它更像一棵樹)。?λ

15.2 匹配 (Matching)

我們需要有一個函數(shù)來做模式匹配以完成我們的反向鏈接 (back-chaining) 程序，這個函數(shù)能夠比較兩個包含變量的列表，它會檢查在給變量賦值后是否可以使兩個列表相等。舉例，如果??x?和??y?是變量，那么下面兩個列表：

(p ?x ?y c ?x)
(p  a  b c  a)

當(dāng)??x?=?a?且??y?=?b?時匹配，而下面兩個列表：

(p ?x b ?y a)
(p ?y b  c a)

當(dāng)??x?=??y?=?c?時匹配。

我們有一個?match?函數(shù)，它接受兩棵樹，如果這兩棵樹能匹配，則返回一個關(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ù)逐個元素地比較它的參數(shù)時候，它把?binds?參數(shù)中的值分配給變量，這被稱為綁定 (bindings)。如果成功匹配，match?函數(shù)返回生成的綁定；否則，返回?nil?。當(dāng)然并不是所有成功的匹配都會產(chǎn)生綁定，我們的?match?函數(shù)就像?gethash?函數(shù)那樣返回第二個值來表明匹配成功：

> (match '(p ?x) '(p ?x))
NIL
T

如果?match?函數(shù)像上面那樣返回?nil?和?t?，表明這是一個沒有產(chǎn)生綁定的成功匹配。下面用中文來描述?match?算法是如何工作的：

1. 如果 x 和 y 在?eql?上相等那么它們匹配；否則，
2. 如果 x 是一個已綁定的變量，并且綁定匹配 y ，那么它們匹配；否則，
3. 如果 y 是一個已綁定的變量，并且綁定匹配 x ，那么它們匹配；否則，
4. 如果 x 是一個未綁定的變量，那么它們匹配，并且為 x 建立一個綁定；否則，
5. 如果 y 是一個未綁定的變量，那么它們匹配，并且為 y 建立一個綁定；否則，
6. 如果 x 和 y 都是?cons?，并且它們的?car?匹配，由此產(chǎn)生的綁定又讓?cdr?匹配，那么它們匹配。

下面是一個例子，按順序來說明以上六種情況：

> (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ù)在一個綁定列表中尋找變量（如果有的話）所關(guān)聯(lián)的值。這個函數(shù)必須是遞歸的，因為有這樣的情況 “匹配建立一個綁定列表，而列表中變量只是間接關(guān)聯(lián)到它的值：??x?可能被綁定到一個包含?(?x?.??y)?和?(?y?.?a)?的列表”：

> (match '(?x a) '(?y ?y))
((?Y . A) (?X . ?Y))
T

先匹配??x?和??y?，然后匹配??y?和?a?，我們間接確定??x?是?a?。

15.3 回答查詢 (Answering Queries)

在介紹了綁定的概念之后，我們可以更準(zhǔn)確的說一下我們的程序?qū)⒁鍪裁矗核玫揭粋€可能包含變量的表達(dá)式，根據(jù)我們給定的事實和規(guī)則返回使它正確的所有綁定。比如，我們只有下面這個事實：

(parent donald nancy)

然后我們想讓程序證明：

(parent ?x ?y)

它會返回像下面這樣的表達(dá)：

(((?x . donald) (?y . nancy)))

它告訴我們只有一個可以讓這個表達(dá)式為真的方法：??x?是?donald?并且??y?是?nancy?。

在通往目標(biāo)的路上，我們已經(jīng)有了一個的重要部分：一個匹配函數(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ī)則將被包含于一個叫做?*rules*?的哈希表，通過頭部 (head) 的判斷式構(gòu)建這個哈系表。這樣做加強了我們無法使用判斷式中的變量的限制。雖然我們可以通過把所有這樣的規(guī)則放在分離的列表中來消除限制，但是如果這樣做，當(dāng)我們需要證明某件事的時侯不得不和每一個列表進(jìn)行匹配。

我們將要使用同一個宏?<-?去定義事實 (facts)和規(guī)則 (rules)。一個事實將被表示成一個沒有?body?部分的規(guī)則。這和我們對規(guī)則的定義保持一致。一個規(guī)則告訴我們你可以通過證明?body?部分來證明?head?部分，所以沒有?body?部分的規(guī)則意味著你不需要通過證明任何東西來證明?head?部分。這里有兩個對應(yīng)的例子：

> (<- (parent donald nancy))
1
> (<- (child ?x ?y) (parent ?y ?x))
1

調(diào)用?<-?返回的是給定判斷式下存儲的規(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)行的樞紐。它接受一個表達(dá)式和一個可選的綁定列表作為參數(shù)。如果表達(dá)式不包含邏輯操作，它調(diào)用?prove-simple?函數(shù)，前面所說的鏈接 (chaining)正是在這個函數(shù)里產(chǎn)生的。這個函數(shù)查看所有擁有正確判斷式的規(guī)則，并嘗試對每一個規(guī)則的?head?部分和它想要證明的事實做匹配。對于每一個匹配的?head?，使用匹配所產(chǎn)生的新的綁定在?body?上調(diào)用?prove。對?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)))

以上兩個返回值指出有一種方法可以證明我們的問題。（一個失敗的證明將返回 nil。）第一個例子產(chǎn)生了一組空的綁定，第二個例子產(chǎn)生了這樣的綁定：??x?和??y?被（間接）綁定到?nancy?和?donald?。

順便說一句，這是一個很好的例子來實踐 2.13 節(jié)提出的觀點。因為我們用函數(shù)式的風(fēng)格來寫這個程序，所以可以交互式地測試每一個函數(shù)。

第二個例子返回的值里那些?gensyms?是怎么回事？如果我們打算使用含有變量的規(guī)則，我們需要避免兩個規(guī)則恰好包含相同的變量。如果我們定義如下兩條規(guī)則：

(<- (child ?x ?y) (parent ?y ?x))

(<- (daughter ?y ?x) (and (child ?y ?x) (female ?y)))

第一條規(guī)則要表達(dá)的意思是：對于任何的?x?和?y?， 如果?y?是?x?的家長，則?x?是?y?的孩子。第二條則是：對于任何的?x?和?y?， 如果?y?是?x?的孩子并且?y?是女性，則?y?是?x?的女兒。在每一條規(guī)則內(nèi)部，變量之間的關(guān)系是顯著的，但是兩條規(guī)則使用了相同的變量并非我們刻意為之。

如果我們使用上面所寫的規(guī)則，它們將不會按預(yù)期的方式工作。如果我們嘗試證明“ a 是 b 的女兒”，匹配到第二條規(guī)則的?head?部分時會將?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ù)的目的。一個?gensym?不可能在另一個規(guī)則中作為變量出現(xiàn)。但是因為規(guī)則可以是遞歸的，我們必須防止出現(xiàn)一個規(guī)則和自身沖突的可能性，所以在定義和使用一個規(guī)則時都要調(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)

操作一個?or?或者?not?表達(dá)式是非常簡單的。操作?or?時，我們提取在?or?之間的每一個表達(dá)式返回的綁定。操作?not?時，當(dāng)且僅當(dāng)在?not?里的表達(dá)式產(chǎn)生?none?時，返回當(dāng)前的綁定。

prove-and?函數(shù)稍微復(fù)雜一點。它像一個過濾器，它用之后的表達(dá)式所建立的每一個綁定來證明第一個表達(dá)式。這將導(dǎo)致?and?里的表達(dá)式以相反的順序被求值。除非調(diào)用?prove?中的?prove-and?函數(shù)則會先逆轉(zhuǎn)它們。

現(xiàn)在我們有了一個可以工作的程序，但它不是很友好。必須要解析?prove-and?返回的綁定列表是令人厭煩的，它們會變得更長隨著規(guī)則變得更加復(fù)雜。下面有一個宏來幫助我們更愉快地使用這個程序：

(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)

它接受一個?query?（不被求值）和若干表達(dá)式構(gòu)成的?body?作為參數(shù)，把?query?所生成的每一組綁定的值賦給?query?中對應(yīng)的模式變量，并計算?body?。

> (with-answer (parent ?x ?y)
    (format t "~A is the parent of ~A.~%" ?x ?y))
DONALD is the parent of NANCY.
NIL

這個宏幫我們做了解析綁定的工作，同時為我們在程序中使用?prove?提供了一個便捷的方法。下面是這個宏展開的情況：

(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)用的展開式

下面是使用它的一個例子：

(<- (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)

看上去，我們在這一章中寫的代碼，是用簡單自然的方式去實現(xiàn)這樣一個程序。事實上，它的效率非常差。我們在這里是其實是做了一個解釋器。我們能夠把這個程序做得像一個編譯器。

這里做一個簡單的描述。基本的思想是把整個程序打包到兩個宏?<-?和?with-answer?，把已有程序中在運行期做的多數(shù)工作搬到宏展開期（在 10.7 節(jié)的?avg?可以看到這種構(gòu)思的雛形) 用函數(shù)取代列表來表示規(guī)則，我們不在運行時用?prove?和?prove-and?這樣的函數(shù)來解釋表達(dá)式，而是用相應(yīng)的函數(shù)把表達(dá)式轉(zhuǎn)化成代碼。當(dāng)一個規(guī)則被定義的時候就有表達(dá)式可用。為什么要等到使用的時候才去分析它呢？這同樣適用于和?<-?調(diào)用了相同的函數(shù)來進(jìn)行宏展開的?with-answer?。

聽上去好像比我們已經(jīng)寫的這個程序復(fù)雜很多，但其實可能只是長了兩三倍。想要學(xué)習(xí)這種技術(shù)的讀者可以看?On Lisp?或者Paradigms of Artificial Intelligence Programming?，這兩本書有一些使用這種風(fēng)格寫的示例程序。