第2章 這是一個簡單的Lisp程序

Certum quod factum（吐槽：意大利語逼格是高呀~）
一切的本源都是自身的構(gòu)成（吐槽：格言什么的最難理解了）
-Giovanni Battista Vico（意大利皇家史官）
只學詞匯是永遠不會精通一門外語的。必須要結(jié)合聽說讀寫，才能精通一門語言。對于編程語言，道理也是一樣。
本章展示的是如何將普通函數(shù)與Lisp的特殊形式結(jié)合在一起，形成一個完整的程序。通過學習這個構(gòu)建的過程，Lisp剩下的詞匯你也會學好的。

2.1 英語的一個子集也要有語法

我們將要開發(fā)的程序會生成隨機的英語句子。下面是一個英語的子集的簡單語法：
句子=>名詞短語+動詞短語
名詞短語=>冠詞+名詞
動詞短語=>動詞+名詞短語
冠詞=>the,a…
名詞=>man,ball,woman,table…
動詞=>hit,took,saw,liked…
技術上來講，上面的描述被稱作上下文無關的短語結(jié)構(gòu)語法，潛在的范式叫做生成型句法。這種概念是應用在我們生成句子的時候，我們會生成一個動詞短語，之后是一個名詞短語。名詞短語的定義就是冠詞后面加上一個名詞。冠詞的意思就是the，或者a或者其他冠詞。這種形式主義是上下文無關的，因為應用的規(guī)則與所用的單詞無關，這種生成的方法就是定義了一個語言的句法規(guī)則（相對的就是非句子的集合）。接下來我們演示一下單個句子使用規(guī)則的應用流程：
要獲得一個句子，首先連接一個名詞短語和一個動詞短語
要獲得一個名詞短語，連接一個冠詞和名詞
選擇冠詞the
選擇名詞man
名詞短語的結(jié)果是the man
為了獲得動詞短語，連接一個動詞和一個名詞短語
選擇動詞hit
獲取一個名詞短語，連接一個冠詞和一個名詞
選擇冠詞the
選怎名詞ball
名詞短語結(jié)果是the ball
動詞短語的結(jié)果是hit the ball
句子是the man hit the ball

2.2 一個直截了當?shù)慕鉀Q方法

我們接下來開發(fā)的程序會用短語結(jié)構(gòu)語法生成隨機的句子。一個最直接的方法就是把每一個語法規(guī)則寫成一個獨立的Lisp函數(shù)：
(defun sentence () (append (noun-phrase) (verb-phrase)))
(defun noun-phrase () (append (Article) (Noun)))
(defun verb-phrase () (append (Verb) (noun-phrase)))
(defun Article () (one-of ‘(the a)))
(defun Noun () (one-of ‘(man ball woman table)))
(defun Verb () (one-of ‘(hit took saw liked)))
每一個函數(shù)定義的參數(shù)列表都是空的，以為這他不接受任何參數(shù)。嚴格來說，一個函數(shù)要是沒有參數(shù)輸入的話，它的返回值就是不變的值，所以我們會使用一個常量來代替。然而，這些函數(shù)會使用隨機函數(shù)，因此，即使沒有參數(shù)輸入也會返回不同的值。這些函數(shù)在數(shù)學體系中是不存在的，但是我們?nèi)匀环Q他們?yōu)楹瘮?shù)，因為他們是會返回一個值的。
現(xiàn)在剩下的就是去定義函數(shù)one-of，他接受的參數(shù)是一系列選擇，隨機返回其中的一個元素。這個函數(shù)的隨后一部分是隨機選擇一個單詞返回一個列表，這樣就可以產(chǎn)生自由的互相組合了。
(defun one-of (set)
?”Pick one element of set, and make a list of it.”
?(list (random-elt set)))
(defun random-elt (choices)
?”Choose an element from a list at random.”
? (elt choices (random (length choices))))
這里出現(xiàn)了兩個函數(shù)，elt和random。Elt會從列表中選擇一個元素。第一個參數(shù)是列表，第二個參數(shù)是元素的位置。容易有疏漏的地方是它的位置編號是從0開始，所以表達式(elt choices 0)的結(jié)果是列表的第一個元素，而表達式(elt choices 1)的結(jié)果是第二個元素。函數(shù)random的返回值是一個0到n-1之間的整型數(shù)，所以表達式(random 4)返回的是0,1,2,3四個數(shù)當中的一個。
現(xiàn)在我們測試一下程序：
> (sentence) => (THE WOMAN HIT THE BALL)
> (sentence) => (THE WOMAN HIT THE MAN)
> (sentence) => (THE BALL SAW THE WOMAN)
> (sentence) => (THE BALL SAW THE TABLE)
> (noun-phrase) => <THE MAN)
> (verb-phrase) => (LIKED THE WOMAN)
> (trace sentence noun-phrase verb-phrase article noun verb) =>
(SENTENCE NOUN-PHRASE VERB-PHRASE ARTICLE NOUN VERB)
> (sentence) =>
(1 ENTER SENTENCE)
(1 ENTER NOUN-PHRASE)
(1 ENTER ARTICLE)
(1 EXIT ARTICLE: (THE))
(1 ENTER NOUN)
(1 EXIT NOUN: (MAN))
(1 EXIT NOUN-PHRASE: (THE MAN))
(1 ENTER VERB-PHRASE)
(1 ENTER VERB)
(1 EXIT VERB: (HIT))
(1 ENTER NOUN-PHRASE)
(1 ENTER ARTICLE)
(1 EXIT ARTICLE: (THE))
(1 ENTER NOUN)
(1 EXIT NOUN: (BALL))
(1 EXIT NOUN-PHRASE: (THE BALL))
(1 EXIT VERB-PHRASE: (HIT THE BALL))
(1 EXIT SENTENCE: (THE MAN HIT THE BALL))
(THE MAN HIT THE BALL)
程序運行的還可以，追蹤信息的結(jié)果也和上面的理論推導和相似，但是Lisp定義比語法規(guī)則來說會有一些難以閱讀。問題隨著語法規(guī)則的復雜化慢慢變得復雜了。假設我們想要允許名詞短語之前可以加上不限數(shù)量的形容詞和介詞。用語法的表達形式，我們會得出下面的規(guī)則：
Noun-Phrase => Article + Adj* + Noun + PP*
Adj* => 0, Adj + Adj*
PP* => 0, PP + PP*
PP => Prep + Noun-Phrase
Adj => big, little, blue, green, . . .
Prep => to, in, by, with, . . .
在這個表達形式中，0的意思是不選擇，逗號分隔的是多個選項中的一個選擇，后面加上星號的意思是可選。星號的具體意思是可以不加，也可以加多個。這種標記法叫做Kleene星號。之后我們會見到Kleene加號，PP+的意思是一個或者多個的重復PP。
現(xiàn)在的問題是，對于形容詞和介詞的選擇，我們要使用Lisp的某種條件式來實現(xiàn)：
(defun Adj* ()
?(if (= (random 2) 0)
??nil
??(append (Adj) (Adj*))))
(defun PP* ()
?(if (random-elt ‘(t nil))
??(append (PP) (PP*))
??nil))
(defun noun-phrase () (append (Article) (Adj*) (Noun) (PP*)))
(defun PP () (append (Prep) (noun-phrase)))
(defun Adj () (one-of ‘(big little blue green adiabatic)))
(defun Prep () (one-of ‘(to in by with on)))
之前選擇了兩個Adj和PP的實現(xiàn)，都是可以用的，下面兩個例子是錯誤的，不可用的程序：
(defun Adj* ()
?“Warning – incorrect definition of Adjectives.”
?(one-of ‘(nil (append (Adj) (Adj*)))))
(defun Adj* ()
?“Warning – incorrect definition of Adjectives.”
?(one-of ‘( list nil (append (Adj) (Adj*)))))
第一個例子錯在返回的是字面上的append表達式而不是一個計算后的值的列表。第二個定義會引起無限遞歸。關鍵點在于，隨著程序的漸漸開發(fā)，原來一些簡單的函數(shù)將會變的復雜。為了理解他們我們需要理解很多Lisp的慣例-defun，()，case，if，quote還有很多求值規(guī)則，并且必須要符合現(xiàn)實情況下的語法規(guī)則。程序越來越龐大，問題也會越來越難弄。

2.3 一個基于規(guī)則的解決方法

另一個實現(xiàn)的方法就是先關注語法的規(guī)則，之后再去考慮怎么個流程。我們來回顧一下原始的語法規(guī)則：
句子=>名詞短語+動詞短語
名詞短語=>冠詞+名詞
動詞短語=>動詞+名詞短語
冠詞=>the,a…
名詞=>man,ball,woman,table…
動詞=>hit,took,saw,liked…
這些規(guī)則的意思是左邊的是由右邊的組成的，有一點復雜的地方，右邊的構(gòu)成形式有兩種，一種是兩個對象的連接，比如名詞短語=>冠詞+名詞，另一種是列表名詞=>man,ball,。就實現(xiàn)來說，每一種可能性都可以用列表中的元素表示，至于兩個對象的連接，也可以展開。下面是規(guī)則的代碼實現(xiàn)：
(defparameter *simple-grammar*
?'(sentence -> (noun-phrase verb-phrase))
?(noun-phrase -> (Article Noun))
?(verb-phrase -> (Verb noun-phrase))
?(Article -> the a)
?(Noun -> man ball woman table)
?(Verb -> hit took saw liked))
"A grammar for a trivial subset of English.")
(defvar *grammar* *simple-grammar*
"The grammar used by generate. Initially, this is
這個規(guī)則的Lisp版本只是對原始規(guī)則的近似模仿。特別是符號->,沒有什么特別的意義，只是裝飾用的。
特殊形式操作符defvar和defparameter都會引入一個新的變量，賦值給他；他們之間的區(qū)別是變量，grammer，在程序運行期間是可變的。而一個參數(shù)，simple-grammar，一般來說是不可變的常量。更改一個參數(shù)被認為是對程序本身的修改，而不是程序修改值。
一旦規(guī)則的列表定義完成，就可以用給定的目錄符號來修改了。函數(shù)assoc就是干這個活兒的。Assoc接受兩個參數(shù)，一個關鍵字和一個列表的列表，返回的是第一個關鍵字打頭的列表。沒有的話就返回nil。下面是例子：
> (assoc ‘noun *grammar*) => (NOUN -> MAN BALL WOMAN TABLE)
雖然用列表實現(xiàn)的規(guī)則很簡單，但是定義函數(shù)，中間差一個操作語法規(guī)則抽象層還是很重要的。我們需要三個函數(shù)：一個用來獲取規(guī)則右邊的對象，一個用來獲取左邊，還有一個根據(jù)目錄尋找可能的對象。
(defun rule-lhs (rule)
?”The lsft-hand side of a rule.”
?(first rule))
(defun rule-rhs (rule)
?”The right-hand side of a rule.”
?(rest (rest rule)))
(defun rewrites (category)
?“Return a list of the possible rewrites for the category.”
?(rule-rhs (assoc category *grammar*)))
定義的這些個函數(shù)會讓讀取規(guī)則的函數(shù)更加方便，更改規(guī)則也會更好用。
現(xiàn)在，我們準備好直接面對問題了：定義一個函數(shù)，生成句子（或者其他的短語）。這個函數(shù)的名字叫做generate。他必須要應付三種情況：1，最簡單的情況，一個相關規(guī)則的重寫集合的符號傳進generate。根據(jù)這個參數(shù)隨機生成。2，如果符號不能重寫規(guī)則，就必須是一個終極符號-單詞或其他語法類別-就可以放一邊了。事實上，我們返回的是輸入的單詞的列表。所有的結(jié)果都需要變成單詞列表的形式。3，一些情況下，符號被修改的時候，我們會選擇一個符號列表，并嘗試根據(jù)這個生成。因此，generate也必須接受一個列表作為輸入，生成列表的每一個元素，聚合在一起。接下來對應的部分是第一個對應第三種情況，第二個對應第一種，第三個對應第二種。在定義中可能會用到mappend函數(shù)。
(defun generate (phrase)
?“Generate a random sentence or phrase”
?(cond ((listp phrase)
? ?(mappend #’generate phrase))
? ?((rewrites phrase)
? ?(generate (random-elt (rewrites phrase))))
? ?(t (list phrase))))
如數(shù)中許多程序一樣，函數(shù)篇幅很短，信息量很大：編程的精髓在于知道什么該寫，什么不該寫。
這種編程風格叫做數(shù)據(jù)驅(qū)動編程，因為數(shù)據(jù)（使用相關目錄重寫的列表）驅(qū)動接下來的程序操作。在Lisp中這是一種自然易用的方式，可以寫出精細可擴展的程序，因為在不修改原來程序的基礎上加上一段新的數(shù)據(jù)也是可以的。
下面是generate應用的例子：
> (generate 'sentence)=>(THE TABLE SAW THE BALL)
> (generate 'sentence) ?=> (THE WOMAN HIT A TABLE)
> (generate 'noun-phrase) =>? (THE MAN)
> (generate 'verb-phrase) ?=> (TOOK A TABLE)
使用if來替代cond來寫generate也是可以的：
(defun generate (phrase)
?“Generate a random sentence or phrase”
?(if (listp phrase)
? ?(mappend #’generate phrase)
? ?(let ((choices (rewrites phrase)))
? ? ?(if (null choices)
? ? ? ?(list phrase)
? ? ? ?(generate (random-elt choices))))))
接下來是使用特殊形式let的版本，let引入一個新的變量（在這里是choices）并且給變量綁定一個值。在這種情況下，引入這個變量會減少兩次對rewrites的調(diào)用，let形式的一般形式是這樣的：
（let （（變量 值）…））
?包含變量的函數(shù)體）
Let函數(shù)是對那些沒有參數(shù)的函數(shù)引入變量最常用的方式。一種竭力要避免的方式就是在引入變量之前嘗試去使用變量：
(defun generate (phrase)
?(setf choices …) ;;;wrong!
?… choices …)
因為這個符號choices現(xiàn)在指向一個特殊變量或者全局變量，這個變量可能會被其它函數(shù)修改，所以這種方式要竭力避免。Generate函數(shù)現(xiàn)在還不可靠，因為沒有保證choices會在接下來的引用中一直保持同樣的值。使用let，我們會引入一個全新的變量，沒有其他人可以訪問；因此就保證了他的值會保持下去。
【m】2.1 使用cond寫一個generate的版本，但是要避免調(diào)用rewrites兩次。
【m】2.2 寫一個generate的版本，顯式區(qū)分終極符號（那些沒有重寫規(guī)則的符號）和非終極符號。

2.4 之后的兩種思路

接下來程序的展現(xiàn)的兩種方式的兩個版本總是在程序開發(fā)的過程中一再出現(xiàn)：（1）將問題直接描述成Lisp代碼。（2）使用最自然地方式描述問題，之后再來寫這種方式的解釋器。
第二種范式包括了一個額外的步驟，因此更加是個規(guī)模較小的問題。然而，使用第二種思路的程序更加容易修改和擴展。當需要處理特別多的數(shù)據(jù)的時候，這種思路就比較管用。自然語言的語法實際上就是這種情況，大部分AI問題都適用這個描述。方法2背后的思想就是將問題盡可能限制在自己的術語環(huán)境內(nèi)，并且將解決方法的核心最小化，用Lisp直接寫出來。
很幸運的是，Lisp設計一種新的表達法是很方便的，也就是設計一門新的編程語言。因此，Lisp所鼓勵的是構(gòu)建更加穩(wěn)健的程序。通篇都是這兩種方式。讀者會注意到，很多情況下，我們使用第二種。

2.5 不改變程序就能改變語法

哦我們來展示一下方法（2）的核心功能，定義一個新的語法，包含的有形容詞，介詞短語，固有名稱和代詞。之后可以將函數(shù)generate函數(shù)應用，卻不用修改新的語法。
(defparameter *bigger-grammar*
?‘((sentence -> (noun-phrase verb-phrase))
?(noun-phrase -> (Article Adj* Noun PP*) (Name) (Pronoun))
?(verb-phrase -> (Verb noun-phrase PP*))
?(PP* -> () (PP PP*))
?(Adj* -> () (Adj Adj*))
?(PP -> (Prep noun-phrase))
?(Prep -> to in by with on)
?(Adj -> big little blue green adiabatic)
?(Article -> the a)
?(Name -> Pat Kim Lee Terry Robin)
?Noun -> man ball woman table)
?(Verb -> hit took saw liked)
?(Pronoun -> he she it these those that)))
(setf *grammar* *bigger-grammar*)
> (generate ‘sentence)
(A TABLE ON A TABLE IN THE BLUE ADIABATIC MAN SAW ROBIN WITH A LITTLE WOMAN)
> (generate ‘sentence)
(TERRY SAW A ADIABATIC TABLE ON THE GREEN BALL BY THAT WITH KIM IN THESE BY A GREEN WOMAN BY A LITTLE ADIABATIC TABLE IN ROBIN ON LEE)
> (generate 'sentence)
(THE GREEN TABLE HIT IT WITH HE)
很明顯的是生成的句子有代詞問題，with he應該是withhim才正確，才是正常的語法。隨機輸出的句子很顯然有時候是沒有什么意義的。

2.6 對一些程序使用相同的數(shù)據(jù)

Another advantage of representing information in a declarative form-as rules or
facts rather than as Lisp functions-is that it can be easier to use the information for
multiple purposes. Suppose we wanted a function that would generate not just the
list of words in a sentence but a representation of the complete syntax of a sentence.
For example, instead ofthe list< a woman took a ba 11 ), we wantto getthe nested list:
聲明的形式（最為規(guī)則或者事實而不是函數(shù)）來展現(xiàn)信息的另一個好處就是這些信息可以對對個目的使用。假設我們想要一個函數(shù)，生成的不僅是單詞的列表還要有一個句子的完整語法。例如，列表(a woman took a ball)的嵌套形式就是：
(SENTENCE (NOUN-PHRASE (ARTICLE A) (NOUN WOMAN))
?(VERB-PHRASE (VERB TOOK)
??(NOUN-PHRASE (ARTICLE A) (NOUN BALL))))
對應的語言意義樹可以這么描述：

2.1.2.JPG

2.7 練習題

【h】2.3 寫一個其他語言的語法，除了英語之外的，比如一種編程語言的子集。
【m】2.4 描述combine-all的一種方式就是兩個列表的向量叉乘之后在append。寫一個高階函數(shù)croos-product，用它來定義combine-all。
這個練習的目的就是讓你的代碼盡可能的通用，因為你永遠不知道接下來會面對什么。

2.8 習題答案

2.1

(defun generate (phrase)
?“Generate a random sentence or phrase”
?(let ((choices nil))
? ?(cond ((listp phrase)
? ? ?(mappend #’generate phrase))
? ? ?((setf choices (rewrites phrase))
? ? ?(generate (random-elt choices)))
? ? ?(t (list phrase)))))

2.2

(defun generate (phrase)
?“Generate a random sentence or phrase”
?(cond ((listp phrase)
? ?(mappend #’generate phrase))
? ?((non-terminal-p phrase)
? ?(generate (random-elt (rewrites phrase))))
? ?(t (list phrase))))
(defun non-terminal-p (category)
?“True if this is a category in the grammar.”
?(not (null (rewrites category))))

2.4

(defun cross-product (fn xlist ylist)
?“Return a list of all (fn x y) values.”
?(mappend #’(lambda (y)
? ?(mapcar #’(lambda (x) (funcall fn x y))
? ? ?xlist))
? ?ylist))
(defun combine-all (xlist ylist)
?“Return a list of lists formed by appending a y to an x”
?(cross-product #’append xlist ylist))
現(xiàn)在我們可以使用另一種方式來使用cross-product：
> (cross-product #'+ '(1 2 3) '(10 20 30))
(11 12 13
21 22 23
31 32 33)
> (cross-product #'list '(a b c d e f g h)
'(1 2 3 4 5 6 7 8))
(A 1) (8 1) (C 1) (0 1) (E 1) (F 1) (G 1) (H 1)
(A 2) (8 2) (C 2) (0 2) (E 2) (F 2) (G 2) (H 2)
(A 3) (8 3) (C 3) (0 3) (E 3) (F 3) (G 3) (H 3)
(A 4) (8 4) (C 4) (0 4) (E 4) (F 4) (G 4) (H 4)
(A 5) (8 5) (C 5) (0 5) (E 5) (F 5) (G 5) (H 5)
(A 6) (8 6) (C 6) (0 6) (E 6) (F 6) (G 6) (H 6)
(A 7) (8 7) (C 7) (0 7) (E 7) (F 7) (G 7) (H 7)
(A 8) (8 8) (C 8) (0 8) (E 8) (F 8) (G 8) (H 8))