5.1 描述和定義ELIZA

現(xiàn)在，我們已經(jīng)有了ELIZA的一個(gè)大概概念，我們可以開始描述和定義程序了，之后可以開始實(shí)現(xiàn)和調(diào)試。
ELIZA的算法可以簡(jiǎn)單描述為這樣：（1）讀取一個(gè)輸入（2）找到一個(gè)匹配模式的輸入（3）將輸入轉(zhuǎn)化成一個(gè)回答（4）打印回答。這四步會(huì)在每一個(gè)輸入中循環(huán)往復(fù)。
步驟1到步驟4的實(shí)現(xiàn)和定義順序是任意的：對(duì)于1，使用內(nèi)建的read函數(shù)來讀取一個(gè)單詞的列表，第四步就是用print來打印回復(fù)的單詞的列表。
當(dāng)然，這個(gè)定義還是有缺點(diǎn)的。用戶必須使用列表的形式，帶括號(hào)的輸入，用戶也不可以使用read不能讀取的符號(hào)，比如引號(hào)，逗號(hào)，頓號(hào)。所以我們的輸入不會(huì)是隨心所欲的，但是這種對(duì)于方便的小小犧牲可以讓問題更好解決一些。

5.2 模式匹配

最難的部分就是第二步和第三步，模式匹配的表示和轉(zhuǎn)化。這里有四件事情需要考慮：一個(gè)通用的模式和回復(fù)，還有一個(gè)特定的輸入和對(duì)輸入的轉(zhuǎn)化。既然我們將輸入作成一個(gè)列表，那么其他的組件也應(yīng)該是列表形式的，例如

模式：(I need a X)
回復(fù)：(what would it mean to you if got a X ?)

輸入：(I need a vacation)
轉(zhuǎn)化：(what would it mean to you if you got a vacation ?)

模式匹配，就必須在字面意義上對(duì)i匹配i，need匹配need，a匹配a，對(duì)變量X就匹配vacation。先決條件就是有一些方式?jīng)Q定了X是一個(gè)變量而need就不是。我們必須安排vacation在回復(fù)中替代X，來得到最終的轉(zhuǎn)化。
暫時(shí)把轉(zhuǎn)化回復(fù)的模式的問題擱置，我們可以看到，模式匹配的問題就是一個(gè)Lisp函數(shù)equal的生成。下面我們展示的函數(shù)simple-equal，就類似于內(nèi)建函數(shù)equal，函數(shù)pat-match，就是被擴(kuò)展成模式匹配變量：
(defun simple-equal (x y)
? “Are x and y equal? (Don’t check inside strings.)”
? (if (or (atom x) (atom y))
? ? (eql x y)
? ? (and (simple-equal (first x) (first y))
? ??(simple-equal (rest x) (rest y)))))

(defun pat-match (pattern input)
? “Does pattern match input? Any variable can match anything.”
? (if (variable-p pattern)
? ?T
? ? (if (or (atom pattern) (atom input))
? ? ? (eql pattern input)
? ? ? (and (pat-match (first pattern) (first input))
? ? ? ? (pat-match (rest pattern) (reat input))))))

在我們往下走之前，我們需要決定一個(gè)模式匹配變量的實(shí)現(xiàn)。我們可以，比個(gè)例子來說，給定一個(gè)符號(hào)的集合來作為變量，比如X,Y,Z。是可以定義一個(gè)類型的結(jié)構(gòu)variable，但是之后我們每一次想要變量的時(shí)候就不得不輸入(make-varibale :name ‘X)來進(jìn)行創(chuàng)建了。另一個(gè)選擇就是使用符號(hào)，但是不指定符號(hào)的名字。例如，在Prolog中，變量時(shí)從大寫字母和小寫的常量開始的。但是Common Lisp是大小寫敏感的，所以這個(gè)方法不適用。但是在基于Lisp的AI程序開發(fā)中有一個(gè)傳統(tǒng)就是，適用問號(hào)開頭的符號(hào)作為變量。
現(xiàn)在為止，我們已經(jīng)可以處理原子類型的符號(hào)，就是那些沒有內(nèi)部結(jié)構(gòu)的對(duì)象。但是無論在Lisp中還是在物理世界，事情在第一次出現(xiàn)后總是會(huì)變得更加復(fù)雜，結(jié)果就是即使是原子也開始有組件了。特別是，富豪有名字，字符串可以通過symbol-name函數(shù)進(jìn)行訪問。字符串中的元素就是字符，可以已通過函數(shù)char訪問。問號(hào)的表示是通過轉(zhuǎn)義字符來表示。所以斷言variable-p可以如下定義，我們現(xiàn)在有了一個(gè)完整的模式匹配器：

(defun variable-p (x)
“Is x a variable (a symbol beginning with ‘?’) ?”
(and (symbol x) (equal (char (symbol-name x) 0) #\?)))
> (pat-match '(I need a ?X) '(I need a vacation))
T
?> (pat-match '(I need a ?X) '(I really need a vacation))
NIL

每一種情況我們都能得到正確的答案，但是我們沒有獲得人格關(guān)于X是什么的提示，所以就不能在回復(fù)中替代什么了。我們需要修改pat-match來返回某種變量和回復(fù)的值的表格。在這個(gè)選擇的當(dāng)口，有經(jīng)驗(yàn)的Common Lisp程序員可以用投機(jī)取巧的方法來節(jié)省時(shí)間：找找看現(xiàn)在手邊是不是有現(xiàn)成的函數(shù)可以完成任務(wù)中的發(fā)部分工作。我們想要的是在回復(fù)中替代變量的值。機(jī)警的程序員可能在一些參考書或者本書的索引中找到了函數(shù)substitute，subst和sublis。這些函數(shù)都是可以用一個(gè)表達(dá)式來替代舊的表達(dá)式的函數(shù)。Sublis看下來是最合適的，因?yàn)樗辉试S我們一次性做一些替換。Sublis接受兩個(gè)參數(shù)，第一個(gè)是新老的對(duì)的列表。第二個(gè)是一個(gè)進(jìn)行替換的表達(dá)式。對(duì)于這個(gè)一對(duì)中的每一個(gè)，car都由cdr來替代，換句話說，我們會(huì)把每一對(duì)都格式化成類似于(cons old new)的形式。（這樣的列表被稱為聯(lián)合列表，a-list，因?yàn)樗?lián)合了鍵和值，請(qǐng)見3.6小節(jié)），根據(jù)上面的例子：
> (sub 1 is '((?X . vacation))
'(what would it mean to you if you got a ?X ?)
(WHAT WOULD IT MEAN TO YOU IF YOU GOT A VACATION ?)
現(xiàn)在我們要修改pat-match來返回一個(gè)列表，而不是在成功的時(shí)候僅僅返回T，下面是第一個(gè)嘗試修改的例子：
(defun pat-match (pattern input)
?“Does pattern match input? WARNING: buggy version.”
? (if (variable-p pattern)
? ? (list (cons pattern input))
? ? (if (or (atom pattern) (atom input))
? ? ? (eql pattern input)
? ? ? (append (pat-match (first pattern) (first input))
? ? ? ? (pat-match (rest pattern) (rest input))))))

這個(gè)實(shí)現(xiàn)看上去是很合理的：如果模式是一個(gè)變量，他會(huì)返回一個(gè)單元素的a-list如果輸入都是列表，那么就會(huì)追加在聯(lián)合列表。然而還是有一些問題，測(cè)試語句(eql pattern input)可能會(huì)返回T，那不是列表的話，append函數(shù)可能會(huì)報(bào)錯(cuò)的。第二，這個(gè)測(cè)試也可能會(huì)返回nil，也就是表示失敗，但是會(huì)被認(rèn)為是一個(gè)列表，追加到答案的后面。第三，我們還沒有分清楚哪一些是匹配失敗，返回nil相對(duì)那些匹配一切的情況，但是沒有變量。所以他就會(huì)返回空的聯(lián)合列表。（這就是在之前討論的子斷言問題），第四，我們想要變量的綁定統(tǒng)一，如果？X在模式中被兩次使用的話，我們不會(huì)匹配兩個(gè)不同的輸入的值。最后，對(duì)于pat-match，同時(shí)檢查列表的first和rest是很低效的，甚至當(dāng)對(duì)應(yīng)的first部分匹配失敗的時(shí)候（是不是在一個(gè)七行的程序中就有5個(gè)bug，感到很神奇？）
我們?cè)谌〉脙蓚€(gè)主要的共識(shí)之后就能分析這些問題了，首先，讓pat-match成為一個(gè)純粹的斷言會(huì)讓事情更加方便，所以我們同意在表示失敗的時(shí)候返回nil，這也就意味著我們需要在一個(gè)非nil的值來表示空的綁定列表。第二，如果我們要保持變量值的前后一致性，first就必須知道rest在做設(shè)么。我們可以通過傳遞綁定列表個(gè)pat-match的第三個(gè)參數(shù)來實(shí)現(xiàn)。加一個(gè)可選的參數(shù)，這樣就可以簡(jiǎn)化調(diào)用(pat-match a b)。
為了從這些實(shí)現(xiàn)決定中抽象，我們定義常量fail和no-bindings來表示兩個(gè)問題的返回值。特殊形式defconstant被用來顯示這些值是不會(huì)改變的。（習(xí)慣上來說，特殊變量會(huì)在名字前后加上星號(hào)，但是這個(gè)慣例我們?cè)谶@里不遵循。理由是星號(hào)的意思就是引起注意，小心啦，這個(gè)變量可能會(huì)被詞法域之外的某些操作改變值的，但是常量，當(dāng)然就不會(huì)別更改了。）
(defconstant fail nil “Indicates pat-match failure”)
(defconstant no-bindings ‘((t . t))
“Indicates pat-match success, with no variables.”)
接下來我們從assoc函數(shù)中抽象出下面四個(gè)函數(shù)：
(defun get-binding (var bindings)
“Finding a (variable . value) pair in a binding list.”
(assoc var bindings))

(defun binding-val (binding)
“Get the value part of a single binding.”
(cdr binding))

(defun lookup (var bindings)
“Get the value part (for var) from a binding list.”
(binding-val (get-binding var bindings)))

(defun extend-bindings (var val bindings)
“Add a (var . value) pair to a binding list.”
(cons (cons var val) bindings))

現(xiàn)在變量和綁定都定義好了，pat-match就很簡(jiǎn)單了。他由5部分組成。首先，如果綁定列表是fail，那么匹配失?。ㄒ?yàn)橛行┫惹暗钠ヅ浔囟ㄊ鞘×耍?。如果模式是一個(gè)單個(gè)的變量，匹配就會(huì)返回match-variable所返回的值；可能是一個(gè)現(xiàn)有的綁定列表，或者一個(gè)擴(kuò)展，或者是fail。接下來，如果模式和輸入都是列表，我們首先在每一個(gè)列表的第一個(gè)元素遞歸調(diào)用pat-match。這回返回一個(gè)綁定列表（或者fail），我們會(huì)用來匹配列表的神域部分。這僅僅是一種調(diào)用不普通的程序的情況。座椅這種非正式地證明函數(shù)會(huì)終結(jié)的方式是很好的：兩個(gè)遞歸調(diào)用中的每一個(gè)都會(huì)降低模式和輸入的規(guī)模，pat-match會(huì)檢查原子的模式和輸入，所以函數(shù)作為一個(gè)整體苜蓿返回一個(gè)答案（除非模式和輸入都是無限的規(guī)模）。如果這四個(gè)情況沒有一種成功，之后匹配失敗。

(defun pat-match (pattern input &optional (bindings no-bindings))
?“Match pattern against input in the context of the bindings”
? (cond ((eq bindings fail) fail)
? ? ((variable-p pattern)
? ? (match-variable pattern input bindings))
? ? ((eql pattern input) bindings)
? ? ((and (consp pattern) (consp input))
? ? (pat-match (rest pattern) (rest input)
? ? ? (pat-match (first pattern) (first input)
? ? ? ?bindings)))
? ? (t fail))))

(defun match-variable (var input bindings)
? “Does VAR match input? Uses (or updates) and returns bindings.”
? (let ((binding (get-binding var bindings)))
? ? (cond ((not binding) (extend-bindings var input bindings))
? ? ? ((equal input (binding-val binding)) bindings)
? ? ? (t fail))))

現(xiàn)在測(cè)試一下pat-match
> (pat-match '(i need a ?X) '(i need a vacation))
(?X . VACATION) (T . T))
答案就是綁定在點(diǎn)對(duì)的變量的列表；列表的每一個(gè)元素都是一個(gè)(variable . value)對(duì)，(T . T)就是no-bindings的結(jié)余。這不是一件壞事，而是可以通過讓extend-bindings增加一些復(fù)雜性來消除。

(defun extend-bindings (var val bindings)
?“Add a (var . value) pair to a binding list.”
? (cons (cons var val)
? ?;;Once we add a “real” binding,
? ?;;we can get rid of the dummy no-bindings
? ? (if (eq bindings no-bindings)
? ? ?Nil
? ? ?bindings)))

> (pat-match '(i need a ?X) '(i really need a vacation))
NIL
? > (pat-match '(this is easy) '(this is easy) )
((T. T))
> (pat-match '(?X is ?X) '((2 + 2) is 4) )
NIL
> (pat-match '(?X ;s ?X) '?2 + 2) is (2 + 2)))
((?X 2 + 2))
> (pat-match '(?P need. ?X) , (; need a long vacation))
((?X A LONG VACATION) (?P . I))

請(qǐng)注意nil和((T . T))的區(qū)別，后一個(gè)意思是匹配成功，但是沒有綁定返回。還有，記住(?X 2 + 2) 表示的意思是(? X . (2 + 2))。
Pat-match的更好的實(shí)現(xiàn)在第六章會(huì)給出。另一個(gè)實(shí)現(xiàn)在第10.4小節(jié)，更加的高效但是也更加臃腫。