第2章 這是一個(gè)簡單的Lisp程序

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

2.1 英語的一個(gè)子集也要有語法

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

2.2 一個(gè)直截了當(dāng)?shù)慕鉀Q方法

我們接下來開發(fā)的程序會用短語結(jié)構(gòu)語法生成隨機(jī)的句子。一個(gè)最直接的方法就是把每一個(gè)語法規(guī)則寫成一個(gè)獨(dú)立的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)))
每一個(gè)函數(shù)定義的參數(shù)列表都是空的，以為這他不接受任何參數(shù)。嚴(yán)格來說，一個(gè)函數(shù)要是沒有參數(shù)輸入的話，它的返回值就是不變的值，所以我們會使用一個(gè)常量來代替。然而，這些函數(shù)會使用隨機(jī)函數(shù)，因此，即使沒有參數(shù)輸入也會返回不同的值。這些函數(shù)在數(shù)學(xué)體系中是不存在的，但是我們?nèi)匀环Q他們?yōu)楹瘮?shù)，因?yàn)樗麄兪菚祷匾粋€(gè)值的。
現(xiàn)在剩下的就是去定義函數(shù)one-of，他接受的參數(shù)是一系列選擇，隨機(jī)返回其中的一個(gè)元素。這個(gè)函數(shù)的隨后一部分是隨機(jī)選擇一個(gè)單詞返回一個(gè)列表，這樣就可以產(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)了兩個(gè)函數(shù)，elt和random。Elt會從列表中選擇一個(gè)元素。第一個(gè)參數(shù)是列表，第二個(gè)參數(shù)是元素的位置。容易有疏漏的地方是它的位置編號是從0開始，所以表達(dá)式(elt choices 0)的結(jié)果是列表的第一個(gè)元素，而表達(dá)式(elt choices 1)的結(jié)果是第二個(gè)元素。函數(shù)random的返回值是一個(gè)0到n-1之間的整型數(shù)，所以表達(dá)式(random 4)返回的是0,1,2,3四個(gè)數(shù)當(dāng)中的一個(gè)。
現(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)
程序運(yùn)行的還可以，追蹤信息的結(jié)果也和上面的理論推導(dǎo)和相似，但是Lisp定義比語法規(guī)則來說會有一些難以閱讀。問題隨著語法規(guī)則的復(fù)雜化慢慢變得復(fù)雜了。假設(shè)我們想要允許名詞短語之前可以加上不限數(shù)量的形容詞和介詞。用語法的表達(dá)形式，我們會得出下面的規(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, . . .
在這個(gè)表達(dá)形式中，0的意思是不選擇，逗號分隔的是多個(gè)選項(xiàng)中的一個(gè)選擇，后面加上星號的意思是可選。星號的具體意思是可以不加，也可以加多個(gè)。這種標(biāo)記法叫做Kleene星號。之后我們會見到Kleene加號，PP+的意思是一個(gè)或者多個(gè)的重復(fù)PP。
現(xiàn)在的問題是，對于形容詞和介詞的選擇，我們要使用Lisp的某種條件式來實(shí)現(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)))
之前選擇了兩個(gè)Adj和PP的實(shí)現(xiàn)，都是可以用的，下面兩個(gè)例子是錯(cuò)誤的，不可用的程序：
(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*)))))
第一個(gè)例子錯(cuò)在返回的是字面上的append表達(dá)式而不是一個(gè)計(jì)算后的值的列表。第二個(gè)定義會引起無限遞歸。關(guān)鍵點(diǎn)在于，隨著程序的漸漸開發(fā)，原來一些簡單的函數(shù)將會變的復(fù)雜。為了理解他們我們需要理解很多Lisp的慣例-defun，()，case，if，quote還有很多求值規(guī)則，并且必須要符合現(xiàn)實(shí)情況下的語法規(guī)則。程序越來越龐大，問題也會越來越難弄。

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

另一個(gè)實(shí)現(xiàn)的方法就是先關(guān)注語法的規(guī)則，之后再去考慮怎么個(gè)流程。我們來回顧一下原始的語法規(guī)則：
句子=>名詞短語+動詞短語
名詞短語=>冠詞+名詞
動詞短語=>動詞+名詞短語
冠詞=>the,a…
名詞=>man,ball,woman,table…
動詞=>hit,took,saw,liked…
這些規(guī)則的意思是左邊的是由右邊的組成的，有一點(diǎn)復(fù)雜的地方，右邊的構(gòu)成形式有兩種，一種是兩個(gè)對象的連接，比如名詞短語=>冠詞+名詞，另一種是列表名詞=>man,ball,。就實(shí)現(xiàn)來說，每一種可能性都可以用列表中的元素表示，至于兩個(gè)對象的連接，也可以展開。下面是規(guī)則的代碼實(shí)現(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
這個(gè)規(guī)則的Lisp版本只是對原始規(guī)則的近似模仿。特別是符號->,沒有什么特別的意義，只是裝飾用的。
特殊形式操作符defvar和defparameter都會引入一個(gè)新的變量，賦值給他；他們之間的區(qū)別是變量，grammer，在程序運(yùn)行期間是可變的。而一個(gè)參數(shù)，simple-grammar，一般來說是不可變的常量。更改一個(gè)參數(shù)被認(rèn)為是對程序本身的修改，而不是程序修改值。
一旦規(guī)則的列表定義完成，就可以用給定的目錄符號來修改了。函數(shù)assoc就是干這個(gè)活兒的。Assoc接受兩個(gè)參數(shù)，一個(gè)關(guān)鍵字和一個(gè)列表的列表，返回的是第一個(gè)關(guān)鍵字打頭的列表。沒有的話就返回nil。下面是例子：
> (assoc ‘noun *grammar*) => (NOUN -> MAN BALL WOMAN TABLE)
雖然用列表實(shí)現(xiàn)的規(guī)則很簡單，但是定義函數(shù)，中間差一個(gè)操作語法規(guī)則抽象層還是很重要的。我們需要三個(gè)函數(shù)：一個(gè)用來獲取規(guī)則右邊的對象，一個(gè)用來獲取左邊，還有一個(gè)根據(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*)))
定義的這些個(gè)函數(shù)會讓讀取規(guī)則的函數(shù)更加方便，更改規(guī)則也會更好用。
現(xiàn)在，我們準(zhǔn)備好直接面對問題了：定義一個(gè)函數(shù)，生成句子（或者其他的短語）。這個(gè)函數(shù)的名字叫做generate。他必須要應(yīng)付三種情況：1，最簡單的情況，一個(gè)相關(guān)規(guī)則的重寫集合的符號傳進(jìn)generate。根據(jù)這個(gè)參數(shù)隨機(jī)生成。2，如果符號不能重寫規(guī)則，就必須是一個(gè)終極符號-單詞或其他語法類別-就可以放一邊了。事實(shí)上，我們返回的是輸入的單詞的列表。所有的結(jié)果都需要變成單詞列表的形式。3，一些情況下，符號被修改的時(shí)候，我們會選擇一個(gè)符號列表，并嘗試根據(jù)這個(gè)生成。因此，generate也必須接受一個(gè)列表作為輸入，生成列表的每一個(gè)元素，聚合在一起。接下來對應(yīng)的部分是第一個(gè)對應(yīng)第三種情況，第二個(gè)對應(yīng)第一種，第三個(gè)對應(yīng)第二種。在定義中可能會用到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ù)篇幅很短，信息量很大：編程的精髓在于知道什么該寫，什么不該寫。
這種編程風(fēng)格叫做數(shù)據(jù)驅(qū)動編程，因?yàn)閿?shù)據(jù)（使用相關(guān)目錄重寫的列表）驅(qū)動接下來的程序操作。在Lisp中這是一種自然易用的方式，可以寫出精細(xì)可擴(kuò)展的程序，因?yàn)樵诓恍薷脑瓉沓绦虻幕A(chǔ)上加上一段新的數(shù)據(jù)也是可以的。
下面是generate應(yīng)用的例子：
> (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引入一個(gè)新的變量（在這里是choices）并且給變量綁定一個(gè)值。在這種情況下，引入這個(gè)變量會減少兩次對rewrites的調(diào)用，let形式的一般形式是這樣的：
（let （（變量 值）…））
?包含變量的函數(shù)體）
Let函數(shù)是對那些沒有參數(shù)的函數(shù)引入變量最常用的方式。一種竭力要避免的方式就是在引入變量之前嘗試去使用變量：
(defun generate (phrase)
?(setf choices …) ;;;wrong!
?… choices …)
因?yàn)檫@個(gè)符號choices現(xiàn)在指向一個(gè)特殊變量或者全局變量，這個(gè)變量可能會被其它函數(shù)修改，所以這種方式要竭力避免。Generate函數(shù)現(xiàn)在還不可靠，因?yàn)闆]有保證choices會在接下來的引用中一直保持同樣的值。使用let，我們會引入一個(gè)全新的變量，沒有其他人可以訪問；因此就保證了他的值會保持下去。
【m】2.1 使用cond寫一個(gè)generate的版本，但是要避免調(diào)用rewrites兩次。
【m】2.2 寫一個(gè)generate的版本，顯式區(qū)分終極符號（那些沒有重寫規(guī)則的符號）和非終極符號。

2.4 之后的兩種思路

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

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

哦我們來展示一下方法（2）的核心功能，定義一個(gè)新的語法，包含的有形容詞，介詞短語，固有名稱和代詞。之后可以將函數(shù)generate函數(shù)應(yīng)用，卻不用修改新的語法。
(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應(yīng)該是withhim才正確，才是正常的語法。隨機(jī)輸出的句子很顯然有時(shí)候是沒有什么意義的。

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í)而不是函數(shù)）來展現(xiàn)信息的另一個(gè)好處就是這些信息可以對對個(gè)目的使用。假設(shè)我們想要一個(gè)函數(shù)，生成的不僅是單詞的列表還要有一個(gè)句子的完整語法。例如，列表(a woman took a ball)的嵌套形式就是：
(SENTENCE (NOUN-PHRASE (ARTICLE A) (NOUN WOMAN))
?(VERB-PHRASE (VERB TOOK)
??(NOUN-PHRASE (ARTICLE A) (NOUN BALL))))
對應(yīng)的語言意義樹可以這么描述：

2.1.2.JPG

2.7 練習(xí)題

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

2.8 習(xí)題答案

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