第一部分Common Lisp介紹
第1章 介紹一下Lisp
你在學(xué)的時候覺得已經(jīng)明白了返十，寫的時候更加確信了解了策肝，教別人的時候就更有自信的了肛捍。一直到你開始編程的時候才明白什么是真正的理解——Alan Perlis隐绵，耶魯大學(xué)計算機(jī)科學(xué)家
本章是為了完全沒有Lisp經(jīng)驗的人準(zhǔn)備的。如果你在Lisp編程方面有足夠的自信拙毫，可以快速瀏覽這一章或者直接跳過依许。本章會進(jìn)展的比較快，沒有編程經(jīng)驗的讀者或者發(fā)現(xiàn)本章很難理解的讀者請去尋找一些入門類的書籍來看看缀蹄，在前言里有推薦峭跳。
計算機(jī)就是允許實行計算的機(jī)器。一個字符處理程序可以處理字符缺前，就像計算器處理數(shù)字一樣蛀醉，原理都是相同的。兩個環(huán)境都是衅码，你提供輸入（字符或者數(shù)字）拯刁，并且定義一個操作（比如刪除一個字符或者加上兩個數(shù)字），之后得出一個結(jié)果（一份完整的文檔或者計算結(jié)果）逝段。
我們稱任何計算機(jī)內(nèi)存中的實體為一個可計算對象垛玻，簡稱對象。因此奶躯，字符帚桩，段落和數(shù)字都可以是對象。由于那些操作本身（刪除或者增加）也必須在計算機(jī)內(nèi)存中保存嘹黔，所以也是對象账嚎。
正常來說，一個計算機(jī)用戶和一個程序員的區(qū)別在于参淹，用戶給計算機(jī)提供的是新的輸入醉锄，或者數(shù)據(jù)（字符或者數(shù)字），而程序員則是定義新的操作浙值，或者程序恳不，還有新的數(shù)據(jù)類型。每一個新的對象开呐，或是數(shù)據(jù)或是程序烟勋，都必須按照之前定義的對象來定義。壞消息是筐付，這個定義正確合理的過程可能是非陈训耄枯燥乏味的。好消息是每一個新的對象都可以在未來的對象定義中使用瓦戚。因此沮尿，再復(fù)雜的程序也可以使用簡單精簡的對象來進(jìn)行構(gòu)建。本書包含了一些典型的AI問題，每一個問題都會慢慢分解成可管理的小部分畜疾，每一個部分都會由Common Lisp來具體描述赴邻。理想情況下，讀者會通過學(xué)習(xí)這些例子學(xué)到足夠的知識啡捶，破解新的AI問題姥敛。
讓我們來考慮一個簡單的計算例子：兩個數(shù)字的和，簡單說2+2,瞎暑。如果我們手邊有一個計算器彤敛，就可以輸入2+2=，然后就會顯示答案了了赌。在使用波蘭標(biāo)志的計算器上墨榄，我們可以輸入 2 2 +來得到同樣的結(jié)果。Lisp也有計算功能勿她，用戶可以使用交互式對話來輸入表達(dá)式渠概，之后就可以看到答案。交互模式和其他大部分只有批處理模式的語言不同嫂拴，批處理只能輸入整個程序編譯運行播揪，然后才能看到結(jié)果。
只要輕按一下電源鍵筒狠，一個便攜式計算機(jī)就可以開始工作猪狈。Lisp程序也是需要被打開的，但是具體的細(xì)節(jié)根據(jù)機(jī)器的不同有所區(qū)別辩恼，所以我就不解釋你的Lisp如何工作了雇庙。假設(shè)我們已經(jīng)成功打開了Lisp，某種的提示符就會出現(xiàn)灶伊。在我的計算機(jī)上疆前，提示符就是符號“>”，這樣就顯示Lisp已經(jīng)準(zhǔn)備好接受輸入了聘萨。所以我們面對的屏幕是這樣子的：
>
現(xiàn)在我們輸入算式竹椒，然后看看結(jié)果。很明顯米辐，Lisp的表達(dá)式和算術(shù)表達(dá)式有一些不一樣：一個算式由括號列表組成胸完，開頭是操作的名字，之后是任意數(shù)量的操作數(shù)翘贮，或者參數(shù)赊窥。這種表達(dá)式叫做前綴表達(dá)式。
> (+ 2 2)
4
>
可見狸页，Lisp打印答案锨能，4，之后又輸出另一個提示符，>址遇，來接受接下來的輸入叔收。本書中的Lisp表達(dá)式的輸入都是打印字符，和用戶輸入的字符是一樣的傲隶。一般來說，程序員輸入的字符是小寫的窃页，計算機(jī)輸出的字符都是大寫的跺株。當(dāng)然，像字符+和4是沒有區(qū)別的脖卖。
為了節(jié)省書的空間乒省，我們有時候吧輸入和輸出放在同一行，中間用一個箭頭分割（=>）畦木，讀者可以理解為相等于袖扛，也可以是看做用于在鍵盤上按下的回車鍵，表示輸入結(jié)束十籍。
> (+ 2 2) => 4
使用括號前綴表達(dá)式的好處之一就是括號可以清楚的標(biāo)記表達(dá)式的開始和結(jié)束蛆封。如果我們想，我們可以給+添加更多的參數(shù)勾栗，他會將參數(shù)全部相加惨篱。
> (+ 1 2 3 4 5 6 7 8 9 10) =>55
接下來我們嘗試更加復(fù)雜的算式：
> (- (+ 9000 900 90 9) (+ 5000 500 50 5)) =>4444
這個例子表示表達(dá)式是可以嵌套的。函數(shù)-的參數(shù)就是括號列表围俘，而函數(shù)+的每一個參數(shù)都是原子砸讳。Lisp表達(dá)式可能和標(biāo)準(zhǔn)的數(shù)學(xué)表達(dá)不太一樣，但是這種方式也是有好處的界牡；表達(dá)式是由函數(shù)名后面加上參數(shù)組成的簿寂，所以+符號就不用重復(fù)出現(xiàn)了。比標(biāo)記更加重要的是求值的規(guī)則宿亡。在Lisp中常遂，列表的求值是首先對所有的參數(shù)求值，之后用函數(shù)操作參數(shù)挽荠，進(jìn)而計算結(jié)果烈钞。這個求之規(guī)則比一般的數(shù)學(xué)求值要簡單的多，數(shù)學(xué)中的求值需要記憶很多的規(guī)則坤按，比如在求和和求差之前必須先進(jìn)行加和除操作毯欣。我們接下來會看到，真實的Lisp求值規(guī)則會有點復(fù)雜臭脓，但是不會很過分酗钞。
有時候熟悉其他編程語言的程序員，會有一些先入為主的概念，會對學(xué)習(xí)Lisp造成阻礙砚作。對于他們窘奏，有三點需要明確，第一葫录，其他許多語言由表達(dá)式和語句的區(qū)分着裹，比如表達(dá)式2+2，有一個值米同。但是一個語句骇扇，像x=2+2，就沒有值面粮。語句是有效果的少孝，但是并不返回值。在Lisp中熬苍，是沒有這樣的分別的：沒一個表達(dá)式都會返回一個值稍走，有些表達(dá)式是有效果的，但是仍然會返回一個值柴底。
第二婿脸，Lisp的語法規(guī)則比其他語言的規(guī)則簡單。特別是標(biāo)點符號更少：只有括號柄驻，引號（單引號盖淡，雙引號，反引號）凿歼，空格褪迟，還有逗號作為互相之間的分隔符。因此答憔，在其它語言中味赃，語句y=a*x+3會被解析成七個獨立的符號，在Lisp中卻被看做一個符號虐拓。為了構(gòu)成一個標(biāo)記的列表心俗，我們在記號之間插入空格（y = a * x + 3）。雖然這不是一個合法的符號列表語句蓉驹，但是是一個Lisp數(shù)據(jù)的對象城榛。第三，很多語言是用分號作為語句的結(jié)尾态兴，Lisp不需要分號狠持，表達(dá)式是用括號來分界的。Lisp選擇使用分號作為注釋開始的標(biāo)記瞻润，分號之后的這行的所有內(nèi)容都是注釋喘垂。
> (+ 2 2) ; this is a comment
4

1.1 符號計算

到現(xiàn)在為止甜刻，我們所做的數(shù)學(xué)計算和一個計算器能做的沒有區(qū)別。Lisp比計算器強大的地方有兩個：第一正勒，它允許我們操作除了數(shù)字之外的其他對象得院。第二，后面的計算中章贞，如果需要我們可以定義新的對象祥绞。慢慢來，一點點看看這兩個重要的特性鸭限。
除開數(shù)字之外蜕径，Lisp也可以表示字符（字母），字符的串（字符串）里覆，和任意的字符，這些個字符可以被外部解釋為任意的數(shù)學(xué)表達(dá)缆瓣。Lisp也可以非原子類型的對象喧枷，也就是將多個對象包括近一個列表中宏。這項功能是語言本身的基礎(chǔ)功能弓坞，很好的集成完畢了隧甚；事實上，Lisp的名字由來就是列表處理的意思渡冻。
下面呢是一個列表計算的例子：
> (append '(Pat Kim) '(Robin Sandy)) => (PAT KIM ROBIN SANDY)
這個表達(dá)式將兩個名字的列表追加在一起戚扳。至于求值規(guī)則是和數(shù)字的求值一樣的規(guī)則：應(yīng)用這個函數(shù)（這里是append）到后面的參數(shù)上。
之前沒有見過的族吻，就是這個單引號（'）帽借，他會對接下來要求值的表達(dá)式進(jìn)行鎖定，不加修改的返回超歌。如果不加上單引號砍艾，例如表達(dá)式(Pat Kim)，就會把Pat當(dāng)成一個函數(shù)名然后應(yīng)用到表達(dá)式Kim上巍举。這不是我們想象出來的過程脆荷，單引號的功能就是使得Lisp將列表當(dāng)做數(shù)據(jù)來看而不是一個函數(shù)調(diào)用來看。
> '(Pat Kim) ?=> (PAT KIM)
在其他編程語言中（包括英語中）懊悯，引號都是成對出現(xiàn)的：一個來標(biāo)記開始蜓谋，一個來標(biāo)記結(jié)束。在Lisp中炭分，一個單引號被用來標(biāo)記表達(dá)式的開始桃焕。既然我們知道，一對括號已經(jīng)用來規(guī)定表達(dá)式的開始和結(jié)束捧毛，那么后邊用來標(biāo)記結(jié)束的引號就顯得多余了覆旭。引號可以用在列表退子，或者符號，甚至是其他任何對象上型将。下面是一些例子：
> 'John=> JOHN
> '(John 0 Public) => (JOHN 0 PUBLIC)
>'2 => 2
>2 => 2
> '(+ 2 2 ) => (+ 2 2 )
> (+ 2 2 ) => 4
> John => Error: JOHN is not a bound variable
> (John 0 Public) => Error: JOHN is not a function
'2求值是2是因為表達(dá)式加上引號寂祥，2求值為2是因為2本身求值就是2。一個結(jié)果七兜，兩個原由丸凭。對比之下，john的求值腕铸，加上引號的就是輸出john惜犀，但是不加上引號的就會輸出錯誤，因為對一個符號求值意味著在系統(tǒng)中這個符號是有所指向的狠裹，但是之前并沒有什么對象賦值給john虽界。
符號計算是允許互相嵌套的，甚至也可以和數(shù)字計算進(jìn)行混合涛菠。下面的表達(dá)式以之前不太一樣的方式建立了一個姓名的列表莉御，他使用了內(nèi)建的函數(shù)list。之后我們會看到另一個內(nèi)建函數(shù)length俗冻，他會求出列表的元素個數(shù)礁叔。
> (append '(Pat Kim) (list '(John 0 Public) 'Sandy))
(PAT KIM (JOHN 0 PUBLIC) SANDY)
> (length (append '(Pat Kim) (list '(John 0 Public) 'Sandy)))
4
關(guān)于符號有非常重要的四點需要講解：
第一Lisp對于對象的操作是不會附加任何信息的。比如迄薄，從人的視角來看琅关，Robin Sandy很明顯就是一個人的名字，還有John Q Public是一個人名讥蔽，中間名涣易，姓的組合。Lisp是沒有這些個預(yù)設(shè)的概念的冶伞，對于Lisp來說都毒，Robin也好xyzzy也好都只是符號而已。
第二為了進(jìn)行上面的計算碰缔，必須先要了解一個Common Lisp中定義的函數(shù)账劲，比如append，length金抡，還有+函數(shù)瀑焦。學(xué)習(xí)一門外語包括了記憶那門語言的詞匯（或者知道上哪兒查詢），還要對規(guī)范語言的基本規(guī)則和定義語義的基礎(chǔ)進(jìn)行了解梗肝。Common Lisp提供了超過700個內(nèi)建函數(shù)榛瓮。具體的很多函數(shù)需要讀者去參考別的書籍，但是大部分重要的函數(shù)會在第一部分有所介紹巫击。
第三Common Lisp是不區(qū)分大小寫的禀晓，也就是說精续，John還是john或者是JoHn都是一個意思，打印出來都是JOHN粹懒。在環(huán)境中重付，變量print-case是可以控制打印出來的大小寫的，默認(rèn)是大寫的凫乖，也可以設(shè)置成小寫的确垫。
第四構(gòu)成符號的字符種類是非常繁多的：數(shù)字，字母帽芽，還有其他符號删掀，比如加號和嘆號。符號構(gòu)成的規(guī)則說起來有點小復(fù)雜导街，但是一般來說披泪，構(gòu)成符號的都是字母，有時候會在單詞之間用分隔符搬瑰，-款票，或許在符號的最后會有數(shù)字結(jié)尾。有些程序猿在變量的命名方面會更加不拘小節(jié)跌捆，可能會包含類似于問號徽职，美元符號等等的字符象颖。例如佩厚，一個美元轉(zhuǎn)日元的程序可能會這樣命名$-to-yen或者$->yen。在Pascal或者C中说订，命名也許是DollarsToYen抄瓦，或者dollarstoyen，dol2yen陶冷。當(dāng)然這些規(guī)則之外有很多的例外钙姊，我們等他們出現(xiàn)的時候再解釋吧。

1.2 變量

符號計算的基本概覽之后埂伦，我們接下去看看煞额，或許就是一門語言最最重要的一個特性：按照其他對象定義新的對象的能力，給新對象賦予名字以待后用沾谜。符號再一次扮演了一個重要的角色膊毁，用來給變量命名。一個變量可以存儲一個值基跑，這個值可以是任何Lisp對象婚温。給變量賦值的方法有一個就是用setf函數(shù)：
> (setf p '(John 0 Public)) => (JOHN 0 PUBLIC)
> p => (JOHN 0 PUBLIC)
> (setf x 10) => 10
> (+ X x) => 20
> (+ x (length p)) ?=> 13
在把值(John Q Public)賦值給變量p之后，我們可以使用變量的名字p來指向這個值媳否。相似的栅螟，再把這個值賦值給變量x荆秦，我們就可以用x和p來指向這個值。
符號力图，在Common Lisp中也會被用來命名函數(shù)步绸。每一個符號都可以被用來當(dāng)做變量名或者函數(shù)名，或者兩者都是搪哪。例如靡努，append和length是函數(shù)名，但是沒有作為變量的對應(yīng)值晓折，符號pi沒有對應(yīng)函數(shù)但是卻又對應(yīng)變量惑朦，它的值是3.1415926535897936（近似值）。

1.3 特殊形式

細(xì)心的讀者可能會發(fā)現(xiàn)漓概，setf違反了求值規(guī)則漾月。之前我們提到的函數(shù)像+，-胃珍，還有append梁肿，他們的規(guī)則是先對所有的參數(shù)求值，之后再把函數(shù)應(yīng)用到參數(shù)上觅彰。但是setf沒有遵循這條規(guī)則吩蔑，因為setf根本就不是一個函數(shù)。相反的填抬，這是Lisp的基本句法烛芬，Lisp有一些為數(shù)不多的句法表達(dá)式。姑且稱之為特殊形式飒责。在其他語言中赘娄，也有相同目的的語句存在，也確實有一些相同意義的語法標(biāo)記宏蛉，比如if和loop遣臼。第一，Lisp的句法形式總是在列表中的第一個拾并，后面跟著其他的符號揍堰。Setf就是這些特殊形式中的一個，所以（setf x 10）是一個特殊表達(dá)式嗅义。第二屏歹，特殊形式的表達(dá)式會返回一個值。相比其他的語言芥喇，是有效果但是不返回值的西采。
在對表達(dá)式(setf x (+ 1 2))求值的過程中，我們將符號x作為變量名继控，并且賦值(+ 1 2)械馆，也就是3.如果說setf是一個普通函數(shù)胖眷，那么操作的順序就是先對兩個參數(shù)求值，之后再使用兩個值來進(jìn)行計算霹崎，這顯然不是我們想要的效果珊搀。Setf被稱作特殊形式是因為他做的事情就是特殊的：如果沒有setf，寫一個函數(shù)給一個變量賦值就是完全不可能的事情尾菇。Lisp的核心哲學(xué)就是先提供一些為數(shù)不多的特殊形式境析，他們的功能是函數(shù)無法替代做到的，之后再由用戶來寫函數(shù)實現(xiàn)想實現(xiàn)的各種功能派诬。
術(shù)語特殊形式的確是有些讓人費解劳淆，他即表示setf又表示以setf開頭的表達(dá)式。有一本書Common Lispcraft中作者就為了辨析兩個意思把setf稱作一個特殊函數(shù)默赂，而特殊形式就用來指代setf的表達(dá)式沛鸵。這種說法暗示了setf僅僅是另一種函數(shù)，一種第一個參數(shù)不求值的函數(shù)缆八，這樣的觀點在Lisp還只是被看做一門解釋語言的時候大行其道∏現(xiàn)代的觀點認(rèn)為setf不應(yīng)該被看做是一種特殊的函數(shù)，而是應(yīng)該作為一種特殊的句法標(biāo)記奈辰，由編譯器來特別處理栏妖。因此，特殊形式(setf x (+ 2 1))的意思應(yīng)該就是等同于C語言中的x = 2 + 1奖恰。本書中當(dāng)有產(chǎn)生歧義的危險的時候吊趾，我們會將setf稱作一個特殊形式操作符，而表達(dá)式(setf x 3)稱作特殊形式表達(dá)式房官。
另外要說的是趾徽，引號僅僅是一個特殊形式的縮寫续滋。表達(dá)式’x等同于(quote x)翰守，這個特殊形式表達(dá)式求值是x。本章使用的特殊形式操作符見下表：

1.4 列表

到現(xiàn)在為止我們見到的列表相關(guān)函數(shù)有兩個：append和length疲酌。列表的重要性值得我們在看看更多的列表操作函數(shù)：
> P => (JOHN 0 PUBLIC)
> (first p) =>? JOHN
> (rest p) => (0 PUBLIC)
> (second p) => 0
> (third p) => PUBLIC
> (fourth p) => NIL
> (length p) => 3
函數(shù)的命名也都蠻巧妙的蜡峰，first，second朗恳，third湿颅，fourth：依次返回第1234個元素。Rest的意思就沒那么明顯粥诫，意思是除第一個元素之外的后續(xù)元素油航，符號nil和一堆括號()的意思是完全相同的，表示一個空列表怀浆。Nil同時也用來表示Lisp中的假谊囚，也就是false的值怕享。因此表達(dá)式(fourth p)的值就是nil，因為p本來就沒有第四個元素。請注意，列表的構(gòu)成元素不一定要是原子循诉，子列表也是可以的担神。
> (setf x '((1st element) 2 (element 3) ((4) 5))
((1ST ELEMENT) 2 (ELEMENT 3) ((4) 5)
> (length x) => 5
> (first x) => (1ST ELEMENT)
> (second x) => 2
> (third x) => (ELEMENT 3)
> (fourth x) => ((4))
> (first (fourth x)) => (4)
> (first (first (fourth x))) => 4
> (fifth x) => 5
> (first x) => (1ST ELEMENT)
> (second (first x)) => ELEMENT
我們已經(jīng)學(xué)會怎么訪問列表內(nèi)部的元素了，完完全全新建一個列表也是可以的明肮，例子：
> P => (JOHN Q PUBLIC)
> (cons 'Mr p) => (MR JOHN Q PUBLIC)
> (cons (first p) (rest p)) => (JOHN Q PUBLIC)
> (setf town (list 'Any town 'USA)) => (ANYTOWN USA)
?> (list p 'of town 'may 'have 'already 'won!) =>
((JOHN Q PUBLIC) OF (ANYTOWN USA) MAY HAVE ALREADY WON!)
> (append p '(of) town '(may have already won!)) =>
(JOHN Q PUBLIC OF ANYTOWN USA MAY HAVE ALREADY WON!)
> P => (JOHN Q PUBLIC)
函數(shù)cons就是construct構(gòu)造的縮寫。接受的參數(shù)是一個元素加一個列表。（等一下我們再看第二個參數(shù)不是列表的情況）谨敛。之后cons就會構(gòu)造一個新的列表，第一個元素就是第一個參數(shù)滤否，之后的元素就是第二個參數(shù)中的元素佣盒。函數(shù)list，接受任意數(shù)量的參數(shù)顽聂，之后會按順序形成一個列表肥惭。因此，append的參數(shù)必須是列表紊搪，而list的參數(shù)可能是列表或者原子蜜葱。有一點很重要，這些函數(shù)都是創(chuàng)建一個新的列表耀石，并不破壞原有的列表牵囤。表達(dá)式(append p q)的意思是創(chuàng)建一個完全全新的列表，用的就是p和q的元素滞伟，但是p揭鳞，q本身是不會改變的。
現(xiàn)在我們暫且放下抽象的列表函數(shù)梆奈，來看一個簡答的問題：如果以列表的形式給出一個人的名字野崇，怎么提取出它的家族名呢？對于(JOHN Q PUBLIC)亩钟，或許可以使用函數(shù)third乓梨，但是對于滅幼中間名的名字怎么辦？Common Lisp中有一個函數(shù)叫做last清酥；或許可以有效果扶镀，我們可以這么做：
> (last p) => (PUBLIC)
> (first (last p)) => PUBLIC
Last直接返回的不是最后一個元素本身，而是僅僅含有最后一個元素的列表焰轻。這樣的設(shè)計好像有些有悖常理臭觉，不符合邏輯，實際上是這樣。在ANSI Common Lisp中蝠筑，last的定義是返回一個列表的最后n個元素忆肾，而個數(shù)這個選項的默認(rèn)值就是1。因此(last p)=(last p 1)=(PUBLIC)菱肖，而(last p 2)=(0 PUBLIC)客冈，這樣子定義或許是有些違背常理。所以我們才需要last和first結(jié)合來完成這個功能稳强，獲取真實的最后一個元素场仲。為了表示他的功能，我們給他一個名正言順退疫，叫做last-name函數(shù)渠缕。Setf是用來定義變量名字的，所以對于函數(shù)的定義并不適用褒繁。定義函數(shù)的方法將會在下一節(jié)講到亦鳞。

1.5 定義一個新的函數(shù)

特殊形式defun就是define function的縮寫。先來定義一下上一節(jié)中的last-name函數(shù)棒坏。
(defun last-name (name)
"Select the last name from a name represented as a list."
(first (last name)))
給出一個新的函數(shù)名叫做last-name燕差。參數(shù)列表中只有一個參數(shù)，(name)坝冕，意思就是函數(shù)只接受一個參數(shù)徒探，指向的就是名字。接下來雙引號中的內(nèi)容叫做文檔字符串喂窟，用來說明函數(shù)是做什么用的测暗。文檔字符串本身并不參與計算，但是在調(diào)試和理解大型系統(tǒng)的時候是一個利器磨澡。函數(shù)定義的函數(shù)體就是(first (last name))碗啄，也就是之前用來獲取p的家族名的程序。不同的地方在于我們這一次是要獲取所有名字的家族名稳摄，不僅僅是p稚字。
一般來說，函數(shù)的定義遵循下面的格式（文檔字符串是可選的秩命，其他部分是必須的）：
(defun函數(shù)的名字 (參數(shù)列表 ...)
"文檔字符串 "
函數(shù)體 ... )
函數(shù)名必須是一個符號尉共，參數(shù)一般也是符號褒傅，函數(shù)體是由一個或者多個表達(dá)式所組成弃锐，函數(shù)被調(diào)用的時候這些歌表達(dá)式就會被求值。最后一個表達(dá)式的值返回殿托，作為整個函數(shù)調(diào)用的值霹菊。
一個新的函數(shù)last-name定義之后，就可以像其他Lisp函數(shù)一樣來使用了：
> (last-name p) => PUBLIC
> (last-name '(Rear Admiral Grace Murray Hopper)) =>HOPPER
> (last-name '(Rex Morgan MD)) => MD
> (last-name '(Spot)) => SPOT
> (last-name '(Aristotle)) => ARISTOTLE
最后三個例子指出了編程過程當(dāng)中固有的限制。當(dāng)我們說定義了一個函數(shù)last-name的時候旋廷，我們并不是真的認(rèn)為每一個人都是有一個姓的鸠按；僅僅是在一個列表形式的名字上的一個操作而已。憑直覺講饶碘，MD應(yīng)該是一個頭銜目尖，Spot大概是一條狗的名字，而Aristotle亞里士多德生活在姓這個概念發(fā)明出來之前的年代扎运。但是我們還是可以不斷改進(jìn)自己的程序last-name來適應(yīng)這些例外的情況瑟曲。
我們也可以定一個函數(shù)叫做first-name，雖然這個定義很多余（功能和first函數(shù)一樣）豪治，但是顯式重新定義也是可以的洞拨。之后就可以使用first-name來處理姓名列表，而first用來處理任意的列表负拟，計算機(jī)的操作是完全相同的烦衣，但是我們作為程序員（或者是閱讀程序的人），會少了很多困惑掩浙。定義像first-name這樣的函數(shù)的另一個好處是花吟，如果我們決定改變名字的表現(xiàn)，我們只需要更改first-name的定義厨姚。這可比在一個大型程序中更改first的應(yīng)用來的方便示辈。
(defun first-name (name)
"Select the first name from a name represented as a list."
(first name))
> p => (JOHN 0 PUBLIC)
> (first-name p) => JOHN
> (first-name '(Wilma Flintstone)) => WILMA
> (setf names '((John 0 Public) (Malcolm X)
(Admiral Grace Murray Hopper) (Spot)
(Aristotle) (A A Milne) (Z Z Top)
(Sir Larry Olivier) (Miss Scarlet)) =>
((JOHN 0 PUBLIC) (MALCOLM X) (ADMIRAL GRACE MURRAY HOPPER)
(SPOT) (ARISTOTLE) (A A MILNE) (Z Z TOP) (SIR LARRY OLIVIER)
(MISS SCARLET))
> (first-name (first names) => JOHN
最后一個表達(dá)式中，我們用的那個函數(shù)是先提取列表中的第一個元素遣蚀，也就是一耳光列表矾麻，在提取這第一個元素的元素。

1.6 使用函數(shù)

One good thing about defining a list of names, as we did above, is that it makes it
easier to test our functions. Consider the following expression, which can be used to
test the 1 ast-name function:
上面定義的一大串名字的列表芭梯，接下來可以用來測試我們的函數(shù)险耀。看看下面的表達(dá)式玖喘，就是用來測試last-name函數(shù)：
> (mapcar #'last-name names)
(PUBLIC X HOPPER SPOT ARISTOTLE MILNE TOP OLIVIER SCARLET)
井號加上單引號#’甩牺，這個標(biāo)記是用來將符號轉(zhuǎn)換成函數(shù)名的意思。和引號的功能類似累奈。內(nèi)建函數(shù)mapcar接受了兩個參數(shù)贬派，一個函數(shù)和一個列表。這個表達(dá)式返回一個列表澎媒，列表的每一個元素都是第二個參數(shù)中的元素經(jīng)過第一個參數(shù)-函數(shù)搞乏，處理過后的結(jié)果。換句話說戒努，mapcar調(diào)用等同于：
(list (last-name (first names))
(last-name (second names))
(last-name (third names))
.. . )
mapcar的名字來自于maps请敦，定位，地圖的意思，這是前半部分map侍筛，意味著后續(xù)函數(shù)會操作每一個列表的元素萤皂。后半部分car指的是Lisp函數(shù)car，first函數(shù)的老名字匣椰。Cdr是rest函數(shù)的老名字裆熙。Car和cdr是一個縮寫，（contents of the address register）和（contents of the decrement register）禽笑，這些名字的第一次使用是在一臺IBM 704機(jī)器上弛车，是Lisp的第一個版本實現(xiàn)。我很確信你也認(rèn)為first和rest是個更好的名字蒲每，而且他們會在我們關(guān)于列表的討論中一直替代car和cdr存在纷跛。但是我們在跳出列表視角，看是將兩個看做是一對值的時候邀杏，還是會使用car和cdr的贫奠。
還有更多mapcar的例子：
> (mapcar #' - '0 2 3 4) => (-1 -2 -3 -4)
> (mapcar #'+ '0 234) '00 20 30 40)) => 01 22 33 44)
最后一個例子顯示了，mapcar是可以接受三個參數(shù)的望蜡，在這種情況下唤崭，第一個參數(shù)應(yīng)該是一個二元程序，也就是支持兩個參數(shù)的輸入脖律，之后就可以處理對應(yīng)的元素谢肾。一般來說mapcar會希望n元函數(shù)作為第一個參數(shù)，之后是n個列表小泉。之后的操作就是函數(shù)收集每一個列表的元素芦疏，依次來。之后一個個處理微姊，知道其中一個列表到了盡頭酸茴。Mapcar就會返回一耳光所有函數(shù)返回值的列表作為結(jié)果。
現(xiàn)在我們理解了mapcar兢交，接下來測試一下first-name函數(shù)：
> (mapcar #'first-name names)
(JOHN MALCOLM ADMIRAL SPOT ARISTOTLE A Z SIR MISS)
這些歌結(jié)果可能讓人比較失望薪捍，因為有很多不正常的結(jié)果在。假如我們想要去掉那些頭銜或者稱呼配喳，miss或者Admiral酪穿，做一個真正的名字的輸出版本。記下來可以這么修改：
(defparameter *titles*
'(Mr Mrs Miss Ms Sir Madam Dr Admiral Major General)
"A list of titles that can appear at the start of a name.")
最新引入的特殊形式操作符叫做defparameter晴裹，用來定義一個參數(shù)被济，也就是一個變量，在計算過程中不改變息拜。但是我們要加新東西的時候會更新（比如加上法語Mme或者軍銜Lt.）溉潭。defparameter同時給出變量名和值净响，定義的變量之后的程序就可以使用少欺。在這個例子中我們練習(xí)的選項就是提供一個文檔字符串來描述變量喳瓣。在Lisp程序員之間有個慣例就是將特殊變量的名字用星號給包裹起來，這也僅僅是一個慣例而已赞别；在Lisp中畏陕，星號僅僅是一個字符，沒有特別的含義仿滔。
我們接下來定義一個新的first-name版本惠毁，代替之前的版本。這個版本的改進(jìn)僅僅是我們可以更改變量的值崎页，也可以改變函數(shù)的值鞠绰。這個定義的邏輯是，如果名字的第一個單詞是titles列表的一個成員的話飒焦，就會忽略這個單詞蜈膨，返回后面的first-name部分。否則牺荠，我們像之前一樣使用第一個元素的話翁巍。另一個內(nèi)建函數(shù)member，就會檢測休雌，如果第一個參數(shù)是列表的一部分灶壶，就會將第二個參數(shù)傳進(jìn)去。
特殊形式if的語法是這樣(if 測試條件 then部分 else部分)杈曲。在Lisp中有很多特殊形式是用來做條件測試的驰凛；if是本例子中最合適的。If語句的求值順序是最先求值測試部分担扑。如果為真洒嗤，那么then部分就會被求值并且作為if語句的值返回。如果測試部分為假魁亦，那么else部分就會被求值渔隶，之后返回。有一些語言堅持說是if語句的測試部分的值必須是true或者是false洁奈，Lisp對待這個問題寬容很多间唉。測試部分求值的結(jié)果任何都是合法的。只有值nil被認(rèn)為是false的值利术；其他所有的值都看做是true呈野。在下面first-name的定義中，如果第一個元素是titles中的印叁，函數(shù)member會返回一個非nil的值（true）被冒。如果不是军掂，就會返回nil（false）。雖然所有的非nil值都被看做是true昨悼，按照慣例常量t一般是用來表示真蝗锥。
(defun first-name (name)
"Select the first name from a name represented as a list."
(if (member (first name) *titles*)
(first-name (rest name))
(first name)))
當(dāng)我們使用一個新的first-name版本的時候，結(jié)果會更好一些率触。另外终议，函數(shù)的操作會一次性把很多的前綴去掉。
> (mapcar #'first-name names)
(JOHN MALCOLM GRACE SPOT ARISTOTLE A Z LARRY SCARLET)
> (first-name '(Madam Major General Paula Jones)
PAULA
通過追蹤first-name的執(zhí)行過程葱蝗，我們可以看到程序是如何運行的穴张，都有那些值輸入，以及輸出了哪些值两曼。特殊形式trace和untrace就是這個用處的皂甘。
> (trace first-name)
(FIRST-NAME)
> (first-name '(John Q Public))
(1 ENTER FIRST-NAME: (JOHN Q PUBLIC))
(1 EXIT FIRST-NAME: JOHN)
JOHN
當(dāng)first-name被調(diào)用，按照定義就是單個參數(shù)的輸入悼凑，一個名字偿枕，值是(JOHN Q PUBLIC)，最終返回的值是JOHN佛析。Trace打印的兩行信息是顯示函數(shù)的輸入和輸出益老，之后是Lisp打印的最終結(jié)果JOHN。
下一個例子更加復(fù)雜一些寸莫，函數(shù)first-name被調(diào)用了四次捺萌。第一次，輸入的名字是(Madam Major General Paula Jones)膘茎。因為第一個元素是Madam桃纯，是titles的元素之一，結(jié)果就是再一次調(diào)用first-name披坏，輸入的就是剩下的部分(Major General Paula Jones)态坦。過程反復(fù)了兩簇，最終輸入的名字是(Paula Jones)棒拂。Paula不是titles的元素伞梯，就成為了first-name的結(jié)果，也就是這四次調(diào)用的結(jié)果帚屉。Trace是開啟追蹤谜诫，也可以用untrace來關(guān)閉追蹤。
> (first-name '(Madam Major General Paula Jones)) =>
(1 ENTER FIRST-NAME: (MADAM MAJOR GENERAL PAULA JONES))
(2 ENTER FIRST-NAME: (MAJOR GENERAL PAULA JONES))
(3 ENTER FIRST-NAME: (GENERAL PAULA JONES))
(4 ENTER FIRST-NAME: (PAULA JONES))
(4 EXIT FIRST-NAME: PAULA)
(3 EXIT FIRST-NAME: PAULA)
(2 EXIT FIRST-NAME: PAULA)
(1 EXIT FIRST-NAME: PAULA)
PAULA
> (untrace first-name) => (FIRST-NAME)
> (first-name '(Mr Blue Jeans)) => BLUE
First-name函數(shù)可以被稱作是遞歸的攻旦，因為它的函數(shù)定義中包含了對自身的調(diào)用喻旷。第一次接觸遞歸這個概念的程序員或許認(rèn)為他很神秘。但是遞歸函數(shù)事實上和非遞歸函數(shù)沒有區(qū)別牢屋。任何函數(shù)對于給定的輸入都會返回正確的值且预。對于這句話的理解可以拆成兩部分來看槽袄，一個函數(shù)必須返回一個值，函數(shù)不能返回任何錯誤的值锋谐。兩句話等價于前面的一句話遍尺，但是思考起來就更加容易，程序的設(shè)計也更加方便怀估。
接下來我說明一下first-name問題的抽象描述狮鸭，突出一下函數(shù)的設(shè)計合搅，說明一個事實多搀，遞歸的解決方案并不以任何方式和Lisp綁定的。
function first-name(name);
if 名字的第一個元素師title的元素
then 搞點復(fù)雜的事情包first-name找出來
else 返回第一個元素
這把整個問題剖開成了兩個部分灾部。在第二部分中康铭，直接返回答案，并且就是正確答案赌髓，我們還沒有定義第一部分的該做些什么从藤。但是我們知道答案應(yīng)該就在第一個元素之后的列表中，我們要做的就是對后面的列表進(jìn)行操作锁蠕。這部分就是說再一次調(diào)用first-name夷野，即使還沒有完成所有的定義。
function first-name(name);
if 名字的第一個元素師title的元素
then 將first-name應(yīng)用到名字的剩余部分
else 返回第一個元素
現(xiàn)在荣倾，first-name的第一部分就是遞歸的悯搔，第二部分仍然沒有改變。第二部分會返回正確的值舌仍，這是我們確信的妒貌，第一部分返回的值只是first-name返回的。所以first-name作為一個整體反悔了正確的答案铸豁。因此灌曙，對于求名字的答案，我們算是做了一半了节芥，另外一半就是要看返回的一些答案了在刺。但是每一個遞歸調(diào)用都會砍掉第一個元素，在剩下的中尋找头镊，所以對于n個元素的列表至多有n重遞歸調(diào)用蚣驼。這樣函數(shù)的正確就完整了。深入學(xué)習(xí)之后拧晕，遞歸的思想就不是一個令人困惑的謎題隙姿，而是一種有價值的思想。

1.7 高階函數(shù)

函數(shù)步進(jìn)可以被調(diào)用或者操作參數(shù)厂捞，還可以像其他對象一樣被操作输玷。接受一個函數(shù)作為參數(shù)的函數(shù)被稱作高階函數(shù)队丝。之前的mapcar就是一例。為了顯示高階函數(shù)的編程風(fēng)格欲鹏，我們來定義一個新的函數(shù)叫做mappend机久。接受兩個參數(shù)，一個函數(shù)一個列表赔嚎。mappend將函數(shù)定位到每一個列表的元素上膘盖，然后將他們追加在一個結(jié)果中。第一個定義使用了apply函數(shù)尤误，會把指定的函數(shù)應(yīng)用到參數(shù)列表中侠畔。
(defun mappend (fn the-list)
"Apply fn to each element of list and append the results."
(apply #'append (mapcar fn the-list)))
現(xiàn)在我們嘗試?yán)斫鈇pply和mappend是如何工作的。第一個例子是將加函數(shù)應(yīng)用到四個參數(shù)上损晤。
> (apply #'+ '(123 4)) => 10
下一個例子是將append應(yīng)用在兩個參數(shù)的列表上软棺，每一個參數(shù)都是列表，如果參數(shù)不是列表尤勋，就會報錯喘落。
> (a pp 1 y #' append ' ((1 2 3) (a b c))) => (1 2 3 ABC)
我們現(xiàn)在定義一個新函數(shù)self-and-double，引用到多個參數(shù)上最冰。
> (defun self-and-double (x) (list x (+ x x)))
> (self-and-double 3)=> (3 6)
> (apply #'self-and-double '(3)) => (3 6)
如果我們給self-and-double輸入超過一個參數(shù)瘦棋，或者輸入不是數(shù)字的話，就會報錯暖哨。對表達(dá)式(self-and-double 3 4)或者(self-and-double 'Kim)求值就會報錯《呐螅現(xiàn)在，讓我們回到定位函數(shù)鹿蜀。
> (mapcar #'self-and-double '(1 10 300)) => ((1 2) (10 20) (300 600))
> (mappend #'self-and-double '(1 10 300)) => (1 2 10 20 300 600)
給mapcar傳遞一個三個參數(shù)的列表箕慧，結(jié)果總是三個元素的列表。每一個值及時調(diào)用函數(shù)產(chǎn)生的結(jié)果茴恰。相對的颠焦，mappend被調(diào)用的時候，返回的是一個大列表往枣，就相當(dāng)于mapcar的所有都是在一個追加列表中伐庭。如果給mappend傳遞的函數(shù)不是返回列表的話，會報錯分冈，原因是append要求他的參數(shù)是列表圾另。
現(xiàn)在考慮這樣一個問題：給定一個列表，返回的列表是由原始列表中的數(shù)字和這些數(shù)字的負(fù)數(shù)組成的列表雕沉。例如輸入是(testing 1 2 3 test)就返回 (1 -1 2 -2 3 -3)集乔。這個問題用mappend做組件很容易就解決了。
(defun numbers-and-negations (input)
"Given a list, return only the numbers and their negations."
(mappend #'number-and-negation input))
(defun number-and-negation (x)
"If x is a number, return a list of x and -x."
(if (numberp x)
(list x (- x))
nil ) )
> (numbers-and-negations '(testing 1 2 3 test)) => (1 -1 2 -2 3 -3)
下面mappend的可選定義并沒有使用mapcar坡椒，代替的是一次構(gòu)建一個元素扰路。
(defun mappend (fn the-list)
"Apply fn to each element of list and append the results."
(if (null the-list)
nil
(append (funcall fn (first the-list))
(mappend fn (rest the-list)))))
Funcall類似于apply尤溜，他接受函數(shù)作為第一個參數(shù)，然后將函數(shù)應(yīng)用到后面的參數(shù)中汗唱，但是在funcall中宫莱，后面的參數(shù)是獨立列出的。
> (funcall #' + 2 3) => 5
> (apply #'+ '(2 3)) => 5
> (funcall #' + '(2 3)) => Error: (23) is not a number.
這幾個表達(dá)式分別等價于(+ 2 3)哩罪， (+ 2 3)授霸，和(+ ’(2 3))。
到現(xiàn)在為止用的函數(shù)际插，要么是Common Lisp預(yù)定義好的碘耳，要么是defun引入的，都是有名字的腹鹉，沒有名字就可以使用的函數(shù)也是有的藏畅，需要介紹特殊句法lambda敷硅。
Lambda這個名字來自于數(shù)學(xué)家阿隆佐邱奇發(fā)明的函數(shù)表達(dá)法功咒。Lisp一般是傾向于使用簡潔的希臘字母，但是lambda是一個例外绞蹦。更加貼切的名字應(yīng)該是叫make-function力奋。Lambda表達(dá)式是從Russell和Whitehead合著的《數(shù)學(xué)原理》中的表達(dá)法導(dǎo)出得來，他在綁定變量的上面加上了一個標(biāo)記符號幽七。邱奇想要的是一個一維的字符串景殷，所以他將標(biāo)記符移動到了表達(dá)式的前面”x(x + x)，在標(biāo)記的下面什么都沒有是比較搞笑澡屡，所以邱奇就把這個符號替換成了lambda字母猿挚，但是lambda的大寫希臘字母很容易和其他字母搞混，一般是用小寫的lambda放在前面驶鹉。約翰麥卡錫曾經(jīng)是邱奇教授在普林斯頓的學(xué)生绩蜻，所以當(dāng)麥卡錫在1958年發(fā)明Lisp的時候，他繼承了lambda標(biāo)記法室埋。在鍵盤上沒有希臘字母的時代办绝，麥卡錫就用lambda來表示，一直延續(xù)到了今天姚淆。一般來說一個lambda表達(dá)式是這樣子的：
(lambda (參數(shù) ...) 主體 ...)
一個lambda表達(dá)式是一個函數(shù)的非原子式名字孕蝉，就像append是一個內(nèi)建函數(shù)的原子式名字。這樣子的匿名函數(shù)腌逢，第一次使用就是在調(diào)用的位置進(jìn)行調(diào)用降淮，但是如果我們想要在函數(shù)中調(diào)用的話，還是需要加上#’符號搏讶。
> (lambda (x) (+ x 2)) 4) => 6
> (funcall #'(lambda (x) (+ x 2)) 4) => 6
為了理解兩者之間的差別佳鳖，我們必須要搞清楚表達(dá)式是究竟如何求值的纳本。求值的正常規(guī)則是這樣：對所有的符號求值為所指向的對象。所以在(+ x 2)中的x求值的結(jié)果是名字為x的變量的值腋颠。列表的求值是兩種方式之一繁成，如果列表中的第一個元素是特殊形式操作符，之后的列表就根據(jù)特殊形式的語法規(guī)則進(jìn)行求值淑玫。否則巾腕，列表就解釋成一個函數(shù)調(diào)用。作為函數(shù)絮蒿，第一個元素以一種獨特的方式求值尊搬。這就意味著，他就是一個符號或者是一個lambda表達(dá)式土涝。無論哪一種佛寿，第一個元素的名字的函數(shù)都會對后面的參數(shù)求值后的結(jié)果操作。這些值是有正常求值規(guī)則決定的但壮。如果我們想要指向一個除了第一個元素的調(diào)用意外的位置冀泻，就需要使用#’，否則表達(dá)式就會用正常的求值規(guī)則蜡饵，也不會被看做是函數(shù)弹渔。例如：
> append => Error: APPEND is not a bound variable
> (1 ambda (x) (+ x 2)) => Error: LAMBDA is not a function
還有一些正確使用函數(shù)的例子：
> (mapcar #'(lambda (x) (+ x x)
'(1 2 3 4 5)) =>
(2 4 6 8 10)
? > (mappend #'(lambda (1) (list 1 (reverse 1)))
'((1 2 3) (a b c))) =>
(1 2 3) (3 2 1) (A B C) (C B A))
有時候使用其他編程語言的程序員還不能使用lambda表達(dá)式來看問題。Lambda表達(dá)式很有用的理由有兩個：第一溯祸，對于一些邊角料一般的程序沒必要專門分配一個名字肢专。比如對于表達(dá)式(a+b )*( c+d)，在程序中需要焦辅，但是沒有必要一定要加上一個temp或者temp2這樣的名字來存儲博杖。使用lambda就可以讓代碼更賤清楚一些，不用再找一個名字了筷登。
第二點更重要的是剃根，lambda表達(dá)式使得在運行時創(chuàng)建函數(shù)稱為可能。這種強大的技術(shù)在大部分的編程語言中是不可能實現(xiàn)的仆抵。這些運行是函數(shù)跟继，被稱為閉包，將會在3.16小節(jié)介紹镣丑。

1.8 其他數(shù)據(jù)類型

到現(xiàn)在為止舔糖，我們只見到了四種Lisp對象：數(shù)字，符號莺匠，列表和函數(shù)金吗。Lisp實際上定義了25中不同類型的對象：向量，數(shù)組，結(jié)構(gòu)摇庙，字符旱物，流，哈希表卫袒，等等宵呛。這里我們再引入一個，字符串夕凝。你會在之后看到宝穗，字符串和數(shù)字一樣，是求值為自身的码秉。字符串主要用在打印信息逮矛，符號則是主要用在與其他對象的關(guān)系，變量命名转砖。字符串的打印形式是在兩邊都會有一個雙引號须鼎。
> "a string" => "a string"
> (length "a string") => 8
> (length "") => 0

1.9 總結(jié)：Lisp的求值規(guī)則

現(xiàn)在我們總結(jié)一下Lisp的求值規(guī)則：
每一個表達(dá)式，不是列表就是原子
每一個待求值的列表府蔗，不是特殊形式表達(dá)式就是一個函數(shù)應(yīng)用
特殊形式表達(dá)式的定義晋控，就是第一個元素是特殊形式操作符的列表。表達(dá)式的求值遵循的是怪異的求值規(guī)則礁竞。例如糖荒，setf的求之規(guī)則就是：第二個參數(shù)正常求值，將第一個參數(shù)賦值模捂，然后返回那個值。Defun的規(guī)則是定義一個西函數(shù)蜘矢，返回函數(shù)的名字狂男。Quote的規(guī)則是返回不求值的第一個參數(shù)。標(biāo)記’x實際上就是quote函數(shù)的縮寫品腹。相似的岖食，標(biāo)記#’f是特殊形式表達(dá)式(function f)的縮寫
'John = (quote John) => JOHN
(setf p 'John) => JOHN
(defun twice (x) (+ x x)) => TWICE
(if (= 2 3) (error) (+ 5 6) => 11
函數(shù)應(yīng)用的求值規(guī)則：首先對列表第一個元素之外的所有參數(shù)求值，之后找到第一個元素對應(yīng)的函數(shù)舞吭，應(yīng)用在參數(shù)上泡垃。
(+ 2 3) => 5
(- (+ 90 9) (+ 50 5 (length '(Pat Kim)))) => 42
請注意如果'(Pat Kim)沒有引號的話，會被當(dāng)做函數(shù)應(yīng)用來處理羡鸥。
每一個原子蔑穴，不是非符號就是符號撮弧。（這里相當(dāng)于廢話辙售，原文是a symbol or an nonsymbol，我的理解是符號是原子蜓席，不能進(jìn)行破拆得對象也就是具有原子的特性。比如字符串捐腿，任何求值為自身的數(shù)字纵朋，字符串）
符號被求值出來的值就是變量名最近被賦值的那個值。符號由字母組成茄袖，可能有數(shù)字操软，極少會有標(biāo)記符號。為了避免歧義宪祥，我們使用的符號大部分是字母字符組成寺鸥，只有少數(shù)例外。例外比如是全局變量品山，是用星號包裹的胆建。
names
p
*print-pretty*
非符號原子是求值為自身。現(xiàn)在為止肘交，我們所知的只有數(shù)字和字符串是非符號原子笆载。數(shù)字是由數(shù)組成的，可能還有十進(jìn)制點和符號涯呻。另外的一些支持是科學(xué)記數(shù)法凉驻，分?jǐn)?shù)，負(fù)數(shù)复罐，還有不同進(jìn)制的數(shù)字涝登。字符串是由雙引號包裹的字符。
42 ?=> 42
-273.15 ?=> -273.15
"a string" => "a string"
還有一些小細(xì)節(jié)會讓定義變得復(fù)雜一些效诅，但是這里這樣的定義足夠了胀滚。
對于Lisp初學(xué)者來說，引起困惑的其中一點就是讀取表達(dá)式和求值表達(dá)式的區(qū)別乱投。初學(xué)者在輸入的時候經(jīng)常想像：
> ( + (* 3 4 ) (* 5 6))
會這樣想像咽笼，首先機(jī)器讀取(+，知道是加函數(shù)戚炫，之后就會讀取(* 3 4)計算出值是12剑刑，之后讀取(* 5 6)計算出值是30，最后計算出值是42双肤。事實上施掏，機(jī)器真正的行為是一次性讀取了整個表達(dá)式。列表(+ (* 3 4) (* 5 6))茅糜。在被讀取之后七芭，系統(tǒng)才開始求值。求職的過程可以用解釋器看到列表顯示限匣，或者用編譯器來翻譯成機(jī)器碼指令抖苦，之后執(zhí)行毁菱。
之前我們的描述不是很準(zhǔn)確，說锌历，數(shù)是由數(shù)字組成贮庞，可能還會有十進(jìn)制小數(shù)點和符號。準(zhǔn)確的說法應(yīng)該是這樣究西，一個數(shù)字的打印形式窗慎，是函數(shù)讀取的形式也是函數(shù)打印的形式，是由數(shù)字組成卤材，可能還有十進(jìn)制小數(shù)點和符號遮斥。數(shù)字在機(jī)器內(nèi)部的行書根據(jù)機(jī)器不同而不同，但你可以確信的是在內(nèi)存的特定位置會有一個bit位的模式存在扇丛，內(nèi)部的數(shù)字自然是不包含打印的字符的十進(jìn)制形式术吗。相似的，字符串的打印形式是用雙引號括起來帆精；它的內(nèi)部形式是一個字符向量较屿。
初學(xué)者對于表達(dá)式的讀取和求值可能已有了比較好的理解，但是對于表達(dá)式求值的效率了解仍然不多卓练。有一次一個學(xué)生使用了一個單字母的符號作為變量名隘蝎，因為他覺得計算機(jī)檢索一個字母會比檢索多個字母快一些。事實上襟企，短的名字在讀取的過程是會快一些嘱么，但是在求值中是沒有區(qū)別的。每一根變量顽悼，不管名字是什么樣的曼振，都僅僅是一個內(nèi)存位置，內(nèi)存的訪問和變量名字是無關(guān)的表蝙。

1.10 是什么造就了Lisp的與眾不同拴测？

是什么讓Lisp區(qū)別于其他編程語言？為什么Lisp是一個適用于AI的編程語言府蛇？下面主要是說了八點重要的因素：
對列表的內(nèi)建支持
自動存儲管理
動態(tài)類型
頭等函數(shù)
統(tǒng)一的語法
交互式環(huán)境
可擴(kuò)展性
歷史悠久
總的來說，這些因素可以讓程序猿慢慢做決定屿愚。舉個例子汇跨，對于變量的命名來說，我么可以使用內(nèi)建的列表函數(shù)來構(gòu)造和操作名字妆距，而不用顯式地決定變量名字的展現(xiàn)是什么樣子穷遂。如果我們決定改變展現(xiàn)，回頭更改程序的一部分是很容易的娱据，其他部分不用修改蚪黑。
這種延遲決定的能力，或者更加精確點說，做出臨時的非綁定的決定的能力忌穿，通常是一件好事抒寂，因為這就意味著一些不恰當(dāng)?shù)募?xì)節(jié)可以被忽視了。當(dāng)然延遲做決定的負(fù)面影響也是有的掠剑。首先屈芜，我們給編譯器的信息越少，就會有更大的幾率產(chǎn)生很多低效率的代碼朴译。第二井佑，我們告訴編譯器越少，編譯器給出的前后不一致或者警告就會越少眠寿。錯誤的發(fā)生可能會延遲到運行狀態(tài)躬翁。我們會深入的考慮每一個因素，權(quán)衡每一點的利弊：

列表的內(nèi)建支持

列表盯拱，是一個非常豐富多彩的結(jié)構(gòu)盒发，在任何語言中都會有列表的實現(xiàn)，Lisp是讓他變的更加易用坟乾。很多AI應(yīng)用程序包含了常態(tài)可變大小的列表迹辐，定長的數(shù)據(jù)結(jié)構(gòu)，類似于向量是比較難用的甚侣。
再起的Lisp版本將列表作為他們唯一的內(nèi)聚數(shù)據(jù)結(jié)構(gòu)明吩。Common Lisp也提供了其他的數(shù)據(jù)結(jié)構(gòu)，因為列表并不總是最高效的選擇殷费。

自動內(nèi)存管理

不需要關(guān)心內(nèi)存位置的細(xì)節(jié)印荔，試下自動內(nèi)存管理可以給程序員省下很多精力，也會讓函數(shù)式編程更加方便详羡。其他的語言則會給程序員一些選擇仍律。變量的內(nèi)存位置是在棧中，意思是過程開始的時候被分配实柠，過程結(jié)束就會銷毀水泉，這是比較有效率的方式，但是卻排除了函數(shù)會返回復(fù)雜值的可能性窒盐。另一個選擇草则，就是顯式地分配內(nèi)存并且手動釋放。也可以用函數(shù)式編程但是可能會導(dǎo)致錯誤發(fā)生蟹漓。
舉個例子炕横，計算表達(dá)式a * （b + c），abc都是數(shù)字葡粒。其實用任何語言都能實現(xiàn)這個計算份殿，下面是Pascal和Lisp的代碼：
/* Pascal */
a * ( b + c )
;;;Lisp
( * a ( + b c))
他們之間唯一的區(qū)別就是Pascal使用的是中綴表達(dá)式膜钓，而Lisp使用前綴表達(dá)式。現(xiàn)在卿嘲，我們把abc都替換成矩陣颂斜。假設(shè)我們已有矩陣的加法和乘法過程。在Lisp中表達(dá)式形式是和上面完全一樣的腔寡；只有函數(shù)名變化了焚鲜。在Pascal中，我們需要聲明臨時變量來保存棧中的中間結(jié)果放前，之后用一系列的過程調(diào)用替換函數(shù)表達(dá)式：
/* Pascal */
var temp, result: matrix;
add(b,c,temp);
mult(a,temp,result);
return(result);
;;;Lisp
(mult a (add b c))
用Pascal實現(xiàn)的另一種方式是在堆內(nèi)存中分配矩陣的空間忿磅。之后就可以和Lisp使用一樣的表達(dá)式了。然而凭语，實踐中卻不會這么做葱她，因為這需要顯式地管理內(nèi)存。
/* Pascal */
var a,b,c,x,y: matrix;
x := add(b,c);
y := mult(a,x);
free(x);
return y;
一般來說似扔，對于Pascal程序員吨些，選擇銷毀哪一個數(shù)據(jù)結(jié)構(gòu)是很艱難的決定，如果搞錯了炒辉，就很容易造成內(nèi)存溢出豪墅。更糟的話，程序員如果銷毀了還在使用的結(jié)構(gòu)黔寇，之后對這塊內(nèi)存的再分配就會報錯偶器。Lisp自動分配和銷毀結(jié)構(gòu)，所以都沒有這些問題缝裤。

動態(tài)類型

Lisp程序員不需要給出變量的類型聲明屏轰，因為語言本身會在運行時確定每一個對象的類型，而不是在編譯時指定憋飞。這會讓Lisp程序更簡短霎苗，開發(fā)更快，也可以使得原來并沒有某項功能的函數(shù)榛做，擴(kuò)展成適應(yīng)特定對象的函數(shù)唁盏。在Pascal中，我們可以寫一個函數(shù)來對一百個整數(shù)的數(shù)組進(jìn)行排序检眯，但是我們不能將這個過程用在200個整數(shù)的數(shù)組或者100個字符串的排序升敲。在lisp中，一個函數(shù)適應(yīng)所有對象轰传。
理解這個優(yōu)點的一個方式就是看看在其他語言中，實現(xiàn)這靈活性有多難瘪撇。Pascal是不可能的获茬；事實上轉(zhuǎn)為修正Pascal的問題而發(fā)明的Modula語言也是不可能港庄。Ada語言的設(shè)計考慮了靈活的通用函數(shù)，但是Ada的方案還不是很理想：他用過長的篇幅來實現(xiàn)Lisp中的簡短功能恕曲，并且Ada的編譯器也是過于冗雜鹏氧。（反正就是黑其他語言）。
換句話說佩谣，動態(tài)類型的缺點把还，就是一些錯誤會待到運行時才會被探測出來。強類型語言的一個巨大的好處就是在編譯時錯誤就可以檢測出來茸俭。強類型語言的一大失敗之處也是只能找出一小部分的錯誤吊履。編譯器可以告訴你諸如將字符串誤傳入數(shù)字函數(shù)中這樣的問題，但是他不會發(fā)現(xiàn)调鬓，將奇數(shù)傳入需要偶數(shù)的函數(shù)這類問題艇炎。

頭等函數(shù)

頭等，頭等對象的意思就是可以再任何地方使用腾窝，以操作其他對象相同的方式進(jìn)行操作的對象缀踪。在Pascal或者C中，函數(shù)可以作為參數(shù)傳遞給另一個函數(shù)虹脯，但是他們不是頭等的驴娃，因為在運行的時候不可以創(chuàng)建一個新的函數(shù)，也不可以創(chuàng)建一個沒有名字的匿名函數(shù)循集。在Lisp中我們可以使用lambda表達(dá)式唇敞，這個會在3.16小節(jié)解釋。

統(tǒng)一的語法

Lisp程序的語法簡單易學(xué)暇榴，打字錯誤易糾正厚棵。另外可以寫程序操作其他程序或者定義一種全新的語言-這是一個強大的技術(shù)。簡單的語法使得Lisp易于分析蔼紧。要使用的編輯器應(yīng)該支持自動縮進(jìn)還有括號匹配婆硬。不然看Lisp程序就頭大了。
當(dāng)然了奸例，有些人是反對一切都訴諸括號彬犯。對于反對有兩個回應(yīng)，第一查吊，換個角度想想看谐区，如果Lisp是用所謂傳統(tǒng)的語法，括號對就會用什么來替代呢逻卖？在算術(shù)或者邏輯運算的條件下宋列，就需要一個隱式的運算符優(yōu)先級，在控制流的情況下就需要一個開始結(jié)束的標(biāo)記存在评也。但是這兩個都不一定是優(yōu)點炼杖。隱式的優(yōu)先級制度是惡名昭彰的錯誤易發(fā)地帶灭返，而開始結(jié)束標(biāo)記僅僅是給代碼徒增空間，沒有實際的意義坤邪。很多語言都從開始結(jié)束標(biāo)記脫離了：C語言就是用了花括號{}熙含，效果和括號一樣。一些現(xiàn)代的函數(shù)式語言（比如Haskell）就是用橫向空格符號艇纺，沒有任何顯式的組織怎静。
第二，很多Lisp程序員都考慮過黔衡，用預(yù)處理器將傳統(tǒng)的語法翻譯成Lisp語法蚓聘。但是沒有一個最終流行的。并不是程序員們覺得Lisp的括號能忍员帮，而是找到了括號的好或粮，相信你用過一段也會覺得好的。
還有一點很重要的就是Lisp數(shù)據(jù)的語法和程序的語法是一樣的捞高。顯然氯材，將數(shù)據(jù)轉(zhuǎn)化成程序是非常方便的。更好的是硝岗，直接省掉了讓通用函數(shù)處理I/O的時間氢哮，Lisp函數(shù)的讀取和打印都是自動處理任何的列表，結(jié)構(gòu)型檀，字符串或者數(shù)字冗尤。這樣開發(fā)過程中單個函數(shù)的測試就很平常了。在傳統(tǒng)語言胀溺，比如C或者Pascal裂七，你會寫一個特定目的的函數(shù)來讀取打印每一個對象，以做到調(diào)試的目的仓坞，也有一些特殊目的的驅(qū)動來做這件事情背零。由于又花時間又容易出錯，往往是避免測試的无埃。Lisp的特性使得測試更加容易徙瓶，開發(fā)更加快捷。

交互式環(huán)境

傳統(tǒng)上來說嫉称，一個程序員會先寫一個完整的程序侦镇，編譯，修正編譯器報出的錯誤织阅，之后運行調(diào)試壳繁。這個過程就是批處理交互。對于很龐大的程序，編譯器的等待時間就占用了調(diào)試的很大一部分氮趋。在Lisp中一般是一次寫一個小函數(shù)伍派，馬上就從求值系統(tǒng)中獲得反饋。這種方式就是交互式環(huán)境剩胁。只有更改過的函數(shù)需要重新編譯，所以等待的時間大大縮短了祥国。另外昵观，Lisp程序員可以在任何時候輸入任意的表達(dá)式調(diào)試。
請注意舌稀，交互式和批處理語言的概念和解釋型語言與編譯型語言是不一樣的啊犬。這兩者經(jīng)常被搞混，Lisp的價值在于是一門交互式語言壁查。實際上有經(jīng)驗的Common Lisp程序員傾向于使用編譯器觉至。重點在于交互式而不是解釋型。
交互式環(huán)境的概念變得流行起來睡腿，甚至傳統(tǒng)的語言语御，C和Pascal都開始提供交互式版本，所以這已經(jīng)不是Lisp獨有的優(yōu)勢了席怪。一個C解釋器可能會允許程序員輸入表達(dá)式应闯，之后馬上求值反饋，但是不會允許寫函數(shù)挂捻，比如碉纺，便利符號表，找出用戶定義的函數(shù)刻撒，然后打印信息骨田。在C中，甚至是解釋的C中声怔，符號表都僅僅是為了適應(yīng)解釋器的無用發(fā)明态贤，程序結(jié)束就銷毀。在Lisp中捧搞，符號表是頭等對象抵卫，都是由函數(shù)來進(jìn)行訪問維護(hù)的。
Common Lisp提供了一個極其豐富的工具集胎撇，包括了超過700個內(nèi)建函數(shù)（ANSI Common Lisp提供了900多個）介粘。因此，寫程序更多的是對已有的代碼進(jìn)行堆砌晚树，寫一些原創(chuàng)的新代碼會少一些姻采。除開標(biāo)準(zhǔn)函數(shù)，Common Lisp的實現(xiàn)一般會提供交互式編譯器擴(kuò)展爵憎，調(diào)試器和圖形窗口慨亲。

可擴(kuò)展性

在Lisp發(fā)明的1958年婚瓜，沒有人預(yù)見到，在過去的幾十年間刑棵，編程語言設(shè)計和編程理論會有如此巨大的發(fā)展巴刻。早期的其他語言已經(jīng)退出歷史的舞臺，取而代之的是基于更新觀念的語言蛉签。但是Lisp延續(xù)了下來胡陪，因為它本身的適應(yīng)能力。Lisp是可擴(kuò)展的碍舍，面對新的流行特性柠座，他在不斷的演進(jìn)自己。
擴(kuò)展語言最簡便的方法就是宏片橡，在語言架構(gòu)中妈经，case和if-then-else結(jié)構(gòu)就是宏來實現(xiàn)的。但是Lisp的靈活性遠(yuǎn)不止如此捧书，全新的編程風(fēng)格也能簡單實現(xiàn)吹泡。很多AI應(yīng)用程序是基于規(guī)則編程的概念上的，其他的編程風(fēng)格鳄厌，比如面向?qū)ο筌窈灿肅ommon Lisp對象系統(tǒng)（CLOS）來實現(xiàn)了，宏冪函數(shù)數(shù)據(jù)類型的集合已經(jīng)整合進(jìn)了ANSI Common Lisp中了嚎。
下面的例子展示了Lisp已經(jīng)在前言走了多遠(yuǎn)：
(PROG (LIST DEPTH TEMP RESTLIST)
(SETQ RESTLIST (LIST (CONS (READ) 0)) )
A (COND
((NOT RESTLIST) (RETURN ‘DONE))
(T (SETQ LIST (UNCONS (UNCONS RESTLIST
RESTLIST)DEPTH))
(COND ((ATOM LIST)
(MAPC ‘PRIN1 (LIST ‘”ATOM:” LIST ‘”,” ‘DEPTH DEPTH))
(TERPRI))
(T (SETQ TEMP (UNCONS LIST LIST))
(COND (LIST
(SETQ RESTLIST (CONS(CONS LIST DEPTH) RESTLIST))))
(ADD1 DEPTH)) RESTLIST))
))))
(GO A))
請注意泪漂，這里有一個現(xiàn)在已經(jīng)被摒棄了的go語句，程序也缺少足夠的縮進(jìn)（附注歪泳，其實是markdown的代碼語法不支持縮進(jìn)萝勤，我嘗試了很多代碼的表現(xiàn)，圖片啦呐伞，加粗啦敌卓，最后這個反引號算是效果還不錯了，只是沒辦法行內(nèi)縮進(jìn)伶氢。）用遞歸實現(xiàn)的版本如下：
(PROG NIL (
(LABEL ATOMPRINT (LAMBDA (RESTLIST)
(COND ((NOT RESTLIST) (RETURN ‘DONE))
((ATOM (CAAR RESTLIST)) (MAPC ‘PRIN1
(LIST ‘”ATOM:” (CAAR RESTLIST)
‘”,” ‘DEPTH (CDAR RESTLIST)))
(TERPRI)
(ATOMPRINT (CDR RESTLIST)))
(T (ATOMPRINT (GRAFT
(LIST (CONS (CAAAR RESTLIST) (ADD1 (CDAR RESTLIST))))
(AND (CDAAR RESTLIST) (LIST (CONS (CDAAR RESTLIST)
(CDAR RESTLIST))))
(CDR RESTLIST )))))))
(LIST (CONS (READ ) 0))))
這兩個版本都很難閱讀趟径，使用現(xiàn)代的眼光來看（文本編輯器和自動縮進(jìn)），更簡單的版本也可以實現(xiàn)癣防。
(defun atomprint (exp &optional (depth 0))
“print each atom in exp. Along with its depth of nesting.”
(if (atom exp)
(format t “~&ATOM: ~a,DEPTH ~d” exp depth)
(dolist (element exp)
Atomprint element (+ depth 1))))

1.11 練習(xí)題

【m】1.1 定義一個last-name來處理"Rex Morgan MD," "Morton Downey, Jr.,"
【m】1.2 定義一個取冪的函數(shù)蜗巧，將數(shù)字乘n次方，例如(power 3 2)就是3的2次方蕾盯，9幕屹。
Write a function that counts the number of atoms in an expression.
For example: (count-atoms '(a (b) c)) = 3. Notice that there is something of an
ambiguity in this: should (a nil c) count as three atoms, or as two, because it is
equivalent to (a () c)?
【m】1.3 寫一個函數(shù)來計算表達(dá)式中原子的數(shù)量。例如，(count-atoms '(a (b) c)) = 3望拖。有一點需要辨明渺尘，表達(dá)式(a nil c)的原子數(shù)量是算作三個還是兩個？因為這個表達(dá)式等于(a () c)说敏。
【m】1.4 寫一個函數(shù)來計算一個表達(dá)式中出現(xiàn)的另一個表達(dá)式的次數(shù)鸥跟。例如：
(count- anywhere 'a '( a (a) b) a)) => 3
【m】1.5 寫一個函數(shù)來計算兩個數(shù)字序列的點積（笛卡爾乘積）。
(dot-product '(10 20) '(3 4) = 10 x 3 + 20 x 4 = 110

1.12 習(xí)題答案

1.2

exanswer1.2.JPG

1.3

exanswer1.3.JPG

1.4

exanswer1.4.JPG

1.5

exanswer1.5.JPG