人工智能編程范式：Common Lisp案例學(xué)習(xí)
Peter Norvig

前言

范式（paradigm）：名詞加派，一個實例或者一個模式铸豁，樣本慷荔；特別是指一個出類拔萃的典型樣例。這本書涉及的有三個方面：人工智能領(lǐng)域口柳，或者說AI苹粟；計算機編程技術(shù)；編程語言Common Lisp跃闹。本書可以給讀者的內(nèi)容有嵌削，對于AI的一些主要問題和技術(shù)的理解毛好，一些重要的AI編程程序理解，還有使用Common Lisp來創(chuàng)建苛秕，讀取肌访，修改程序的能力。本書的所有的程序示范樣例都是使用一種好的編程風(fēng)格范式來編寫艇劫。在AI的研究歷史上也有使用廣泛應(yīng)用的技術(shù)來解決重要問題的優(yōu)秀程序吼驶。
僅僅是以博雅教育，素質(zhì)教育需要來說店煞，一門課程盡量要包含在一本集文化之大成的書籍中蟹演，所以這本書，就是來定義AI課程的一本集文化之大成的書籍顷蟀。但這并不是暗示說轨帜，書中寫的程序是最好的，僅僅是說他們是最具有代表性的衩椒。
換個角度來說，這本書是一本是一本高度技術(shù)性的知識綱要哮兰，這些知識會讓一個中級的Lisp程序員成為專家的過程中有所助益毛萌。第一部分和第二部分的布置，讓新手可以快速上手喝滞，但如果是完完全全的新手的話阁将，即使是配合這些材料，也可能會舉步維艱右遭。對于真正的新手來說做盅，還好是有至少五本入門的書籍來參考，詳情請見后面的參考書目窘哈。
一般來說吹榴，教計算機編程的方式是這樣，首先解釋要用的語言的語法構(gòu)成滚婉，之后給學(xué)生看看十行規(guī)模的代碼图筹，然后就要求學(xué)生開始寫程序。本書中让腹，我們采用的方法是學(xué)習(xí)讀寫代碼的最好方法（就是反過來远剩，增強讀代碼能力的好的方式就是去寫）。在對Lisp的簡短介紹之后骇窍，我們馬上開始進(jìn)入復(fù)雜的程序瓜晤，然后要求讀者去理解代碼，修改代碼腹纳。
本書預(yù)設(shè)的前提就是痢掠，當(dāng)你理解了什么是好的代碼驱犹，并有一些有趣的想法的時候，你就可以寫一些有用的代碼了志群。也就是說以寫散文的角度寫代碼着绷。有一句話，寫在Pascal語言軟件工具的封面上锌云，是Kernighan和Plauger說的：
優(yōu)秀的編程技巧是如何習(xí)得的荠医，是從經(jīng)典的程序中見習(xí)得到的，優(yōu)秀的代碼是如何實踐一般的概念和好的編程實現(xiàn)桑涎，讓代碼清晰易懂彬向，容易修改維護，人性化攻冷，而且可靠高效娃胆。對經(jīng)典代碼的認(rèn)真學(xué)習(xí)和模仿就可以習(xí)得更好的技巧。
高傲的工匠往往只是展現(xiàn)完成的杰作等曼，卻把創(chuàng)造過程中里烦，一開始犯下的錯誤和不可避免的彎路給隱藏掉了。不幸的是禁谦，這樣的遮遮掩掩成為了后來的學(xué)習(xí)者的障礙胁黑；當(dāng)一個研究數(shù)學(xué)的學(xué)生看到教科書上那數(shù)十行的證明過程的時候，除了驚嘆他簡潔的美之外州泊，但是也沒有辦法學(xué)到構(gòu)建這一個證明的過程丧蘸。本書試圖展現(xiàn)的就是一個完整的開發(fā)過程，展露無遺遥皂。每一章的開頭都有一個簡略版本的程序力喷，不是通用的程序，只在一些例子中可用演训。之后弟孟，我們就會對這些缺點進(jìn)行分析，然后遞增地構(gòu)建一個基本程序的完整版本仇祭。因此披蕉，讀者不僅能夠看到程序最終的結(jié)果，而且也可以看到如何從錯誤中學(xué)習(xí)乌奇，講一個初級的未完成的程序進(jìn)行精煉没讲。還有，讀者如果覺得一些特定的章節(jié)太難而不得不跳過的話礁苗，評估一些問題的價值爬凑，不要被細(xì)節(jié)所煩擾。
本書所著述的是一些松散的知識集合试伙，被稱作AI編程技術(shù)嘁信，但是有一點要認(rèn)識到于样，那就是這些知識之間是沒有非常明確的分界線的。一個人在成為一個優(yōu)秀的AI程序員之前潘靖，必定已經(jīng)是一個優(yōu)秀的程序員穿剖。因此，書中的一些主題（特別是在第三部分和第五部分）并沒有AI的相關(guān)內(nèi)容卦溢，只有一些對AI行業(yè)從業(yè)者的基本背景糊余。

為什么用Lisp？為什么用Common Lisp单寂？

Lisp贬芥，是最古老的編程語言之一，卻在當(dāng)下還廣泛使用的使用宣决。Lisp的版本很多蘸劈，在基本的特性部分是相同的，但是在細(xì)節(jié)上差異卻很大尊沸。本書使用的Common Lisp是一個Lisp的分支版本威沫，他被認(rèn)為是Lisp的標(biāo)準(zhǔn)版本。選擇Lisp主要有三個理由：
首先洼专，Lisp是AI編程領(lǐng)域最流行的語言壹甥，特別是在美國。如果你想學(xué)一門語言壶熏，肯定是學(xué)大家都在用的，通用的浦译，而不是只有你一個使用的語言棒假。
第二，Lisp語言在定義新的對象的時候生成更加優(yōu)雅精盅。特別是Lisp可以針對手上的問題定義新的語言特性帽哑。對于AI編程來說，語言新定義是個特別有用的特性叹俏，因為需要經(jīng)常處理復(fù)雜的信息妻枕，這些信息是以普通文本的方式出現(xiàn)的。 Lisp是少數(shù)允許將程序代碼和數(shù)據(jù)完全等同的語言之一粘驰。根據(jù)各個語言的定義屡谐，所有的語言都會提供一個定義程序的方式，但是很多其他語言都會限制程序使用的方式蝌数，或者限制程序定義的范圍愕掏，或者要求程序員顯式聲明沒有意義的細(xì)節(jié)。
第三顶伞，Lisp可以在很短的時間沒就開發(fā)出程序原型來饵撑。Lisp程序是簡潔的剑梳，不用處理底層的細(xì)節(jié)。Common Lisp提供了大量預(yù)先定義好的對象滑潘，包括700多個函數(shù)垢乙。編程環(huán)境來講也是很好的。（比如調(diào)試工具语卤，可調(diào)編譯器追逮，集成的編輯器，還有窗口系統(tǒng)的接口）粱侣。動態(tài)的交互式的Lisp環(huán)境羊壹，可以方便地在程序開發(fā)的時候試驗和更改程序。
這里必須提到的是齐婴，在歐洲和日本油猫，Prolog語言在AI工程領(lǐng)域已經(jīng)和Lisp一樣流行了。Prolog在可塑性和簡潔性上和Lisp相差無幾柠偶。最近情妖，Lisp也開始走向世界，而Prolog也慢慢傳進(jìn)了美國诱担。之后來說毡证，一個AI從業(yè)者將會要同事掌握兩種語言。本書將會在地十一章和十二章介紹Prolog的關(guān)鍵概念蔫仙，并且在后續(xù)的章節(jié)使用這些概念料睛。
另一個非常流行的Lisp方言是Scheme，但是主要是用在編程語言設(shè)計和技術(shù)的教育實驗領(lǐng)域摇邦，不太用來進(jìn)行大型項目的開發(fā)恤煞。Scheme會在第22章和23章出現(xiàn)。至于其他的Lisp方言施籍，比如Franz Lisp居扒，MacLisp，InterLisp丑慎，ZetaLisp喜喂，還有Standard Lisp，一般都被認(rèn)識已經(jīng)淘汰了竿裂。還有一些Lisp方言是作為語言的嵌入式擴展延續(xù)了下來玉吁。例如，GNU的Emacs就是使用elisp的腻异，而計算機制圖軟件AutoCAD就是用Autolisp诈茧，一個Xlisp的衍生版本。在未來捂掰，或許Scheme會成為一個流行的擴展語言敢会，他簡短精悍曾沈，而且功能強大，并且有一個官方認(rèn)可的標(biāo)準(zhǔn)定義鸥昏。
有一個軼事是說塞俱，Lisp（還有Prolog）是專用的語言，而其他像Pascal和Care語言都是通用的語言吏垮。實際上障涯，卻是反過來說才對。Pascal和C語言都是專用的語言膳汪，他們在一個馮諾依曼結(jié)構(gòu)的計算機上操作寄存器和內(nèi)存唯蝶。他們語法的主體是算是表達(dá)式和布爾表達(dá)式，當(dāng)他們系統(tǒng)一些結(jié)構(gòu)化數(shù)據(jù)結(jié)構(gòu)的時候遗嗽，對流程抽象和控制抽象的機制就顯得匱乏了粘我。另外，他們的設(shè)計師面向狀態(tài)的痹换，也就是征字，通過賦值語句改變變量的值來計算結(jié)果。
在另一方面娇豫，Lisp對于數(shù)學(xué)運算沒有特定的語法匙姜。加操作和乘操作和其他操作是一樣的，比如追加冯痢，字符處理都一樣的語法氮昧。但是Lisp提供了所有編程中需要的東西：定義數(shù)據(jù)結(jié)構(gòu)，函數(shù)浦楣，還有兩者的結(jié)合郭计。
這種賦值主導(dǎo)，面向狀態(tài)的編程風(fēng)格Lisp也是可以實現(xiàn)的椒振，但是另外還有面向?qū)ο螅谝?guī)則梧乘，和函數(shù)式編程風(fēng)格都在Lisp中有支持澎迎。這種靈活性來自于Lisp的兩個關(guān)鍵特性：第一，Lisp具有強大的宏选调，可以用來擴展語言基礎(chǔ)夹供，通過宏定義，在新的編程風(fēng)格發(fā)明之后仁堪，舊的語言逐漸死去哮洽，新的語言更迭，但是Lisp只要定義幾個宏就能跟上步伐了弦聂。宏之所以強大是因為Lisp程序是由一種簡單的數(shù)據(jù)結(jié)構(gòu)組成的：列表鸟辅，在早期氛什，大部分的程序操作都是通過這種列表數(shù)據(jù)結(jié)構(gòu)來解釋的。當(dāng)今匪凉，Lisp已經(jīng)是編譯更加常用于解釋了枪眉，程序員也更加依賴Lisp 的第二個特性：函數(shù)。當(dāng)然再层，其他語言也有函數(shù)贸铜，但是Lisp的特點在于他允許在程序運行中創(chuàng)建新的函數(shù)。
語言的靈活性讓Lisp跟上了編程風(fēng)格的變遷聂受，但是更加重要的是蒿秦，Lisp可以適應(yīng)你的特定編程問題。在其他語言中蛋济，都是你的問題來適應(yīng)編程語言棍鳖，用Lisp則是可以用語言擴展來適應(yīng)問題。
由于靈活性瘫俊，Lisp已經(jīng)成為了快速建模領(lǐng)域的翹楚鹊杖，比如AI，圖形和UI建模扛芽。Lisp已經(jīng)是前沿編程領(lǐng)域的統(tǒng)治性語言骂蓖，有些問題非常的復(fù)雜，以至于還沒有一個清晰的解決方案來開始項目進(jìn)程川尖。AI的很多問題就是這樣登下。
根據(jù)你的觀點來看，Common Lisp的規(guī)亩Ｔ可能是優(yōu)點被芳，也可能是缺點。在David Touretzky寫的入門書籍中馍悟，側(cè)重點是放在簡潔上畔濒。他選擇去寫一些簡潔的輕量程序，而不是引入一個深奧的新特性锣咒，這種方法完全適用于初學(xué)者侵状，但是本書的讀者應(yīng)該都已經(jīng)過了初學(xué)者這一階段。也就是說毅整，新特性的引入將會在合適的時候暴露給讀者趣兄。大多數(shù)時候，新特性就如介紹的一樣來描述悼嫉，但是有時候?qū)τ诘图壓瘮?shù)如何工作的解釋會轉(zhuǎn)移程序工作的理解的注意力艇潭。在給與被當(dāng)做成人來看待之后，讀者也需要承擔(dān)起責(zé)任來，在不熟悉的來源尋找自己對術(shù)語的解釋和理解蹋凝。

本書的大概

本書共分為五個部分
第一部分是介紹Common Lisp編程語言本身鲁纠。
第1章給出一個快速的入門，用一些精簡的例子來展示Lisp的特性仙粱。有經(jīng)驗的讀者可以跳過房交。
第2章是一些進(jìn)一步的例子，展示Lisp原語是如何組織成一個程序的伐割。初學(xué)者的話要認(rèn)真的學(xué)習(xí)候味，即使是有經(jīng)驗的程序員也要看一下來熟悉一下編程感覺還有我的編程風(fēng)格。
第3章是Lisp原語的概覽隔心“兹海可以大概瀏覽一下，然后當(dāng)做一個參考手冊硬霍，后面有提到的再來查閱帜慢。
第一部分是有意做的很精簡的，更多的空間來留給AI編程唯卖。那就意味著需要一個更加詳細(xì)的參考手冊（或者說在線幫助）來了解語言本身的一個深奧特性了粱玲。后面會推薦一些參考書。
讀者或許也想?yún)⒖嫉?5章拜轨，那里有調(diào)試和錯誤處理的提示抽减。
第二部分包含的是四個早期的AI程序，全部使用基于規(guī)則的模式匹配技術(shù)橄碾。一開始是相對簡單的版本卵沉，之后會不斷地改進(jìn)他們漸漸變成跟家復(fù)雜的程序，讀者可以一步步學(xué)習(xí)到高級的編程技巧法牲。
第4章展示一個GPS（General Problem Solver）通用問題解決的重構(gòu)史汗。這個實現(xiàn)遵循STRIPS（stanford Research Institute Problem Solver）方法。
第5章描述的是ELIZA拒垃，是一個模仿人的對話程序停撞。之后的第6章是在GPS和ELIZA中使用的技術(shù)總結(jié)的章節(jié)，后續(xù)的程序中都可以將他們作為工具使用悼瓮。
第7章是一個解決高校水平的代數(shù)單詞程序戈毒，叫做Student。
第8章開發(fā)一個MACSYMA程序的子集來做符號代數(shù)谤牡，包含微分和積分。對于高等數(shù)學(xué)有感不適的同學(xué)可以跳過這一章姥宝。
第三部分我們先放放AI翅萤，來看看一個通用的工具，是的編程更加的高效。那些對這部分精通的讀者可能就是一個高級的Lisp程序員了套么。
第9章是一個高效技術(shù)的詳細(xì)學(xué)習(xí)培己，將緩存，索引胚泌，編譯和延遲計算連接起來省咨。第10章包括的內(nèi)容是低層的效率問題，比如使用生命玷室，避免垃圾收集和選擇正確的數(shù)據(jù)結(jié)構(gòu)零蓉。
第11章介紹Prolog語言。這是有這雙重目的：展示如何給另一個語言寫一個解釋器穷缤，還有介紹Prolog的重要特性敌蜂，這樣在合適的時候就可以使用了。第12章說的是Prolog的編譯器可以比解釋器快上20倍到200倍津肛。
第13章概略介紹一下面向?qū)ο蟮木幊田L(fēng)格章喉，之后會瀏覽Common Lisp對象系統(tǒng)（CLOS）。
第14章討論面向邏輯和面向?qū)ο缶幊痰膬?yōu)點和限制身坐，并且用第三部分的技術(shù)來開發(fā)一個知識展示系統(tǒng)秸脱。
第四部分是一些高級的AI程序
第15章使用第三部分的技術(shù)來實現(xiàn)一個更加高效的MACSYMA實現(xiàn)。他會使用一些權(quán)威格式的概念部蛇，并且使用一系列更加特殊的函數(shù)來代替很通用的重寫規(guī)則方法摊唇。
第16章是EMYCIN專家系統(tǒng)shell，一個后端的基于規(guī)則的鏈接系統(tǒng)搪花。醫(yī)療專家系統(tǒng)MYCIN也會簡要介紹遏片。
第17章介紹多面體的Waltz行標(biāo)記算法（使用Huffman-Clowes標(biāo)記）。強制傳輸和回溯的方法也會討論撮竿。
第18章展示一個出色游戲程序Othello吮便。其中使用的技術(shù)，alpha-beta搜索幢踏，適用于很多種雙人游戲髓需。
第19章是自然語言處理的介紹。包括上下文無關(guān)的語法房蝉，自上而下或者自下而上的分析僚匆，圖表分析，還有一些語義揭示和參考搭幻。
第20章是擴展之前章節(jié)的語義范圍咧擂，并引入邏輯語法，用的是第11章開發(fā)的Prolog編譯器檀蹋。
第21章是一個適當(dāng)綜合的用邏輯語法格式描述的英語語法松申。這里會討論一些現(xiàn)實的綜合問題的簡單想法。
第五部分包含的材料對于AI來說是次要的，但是對于Lisp程序員是很重要的贸桶。
第22章是介紹Lisp方言Scheme舅逸。開發(fā)一個簡單的Scheme解釋器，之后是一個完全的尾遞歸解釋器皇筛，然后是一個顯式操作continuation和支持call/cc的解釋器琉历。第23章是一個Scheme編譯器。
第24章是介紹那些單獨在ANSI Common Lisp中的特性水醋。包括loop宏旗笔，還有錯誤處理，打印离例，序列化换团，包設(shè)備。
第25章是一個錯誤處理和調(diào)試的Lisp程序宫蛆。
文獻(xiàn)列出了200多個文件艘包，綜合索引。另外耀盗，附錄提供了一個公開的可獲得的Lisp程序目錄想虎。

如何使用本書

本書預(yù)期的讀者范圍是很寬的：任何想要成為一個高級Lisp程序員的人，任何想要成為一個高級AI從業(yè)者的人叛拷，下面是一些推薦的學(xué)習(xí)路徑：
AI課程的入門導(dǎo)論課程：專注在第一部分和第二部分舌厨，機上至少一個第四部分的例子。
AI高級編程課程：專注在第一忿薇，二裙椭，四和五部分，跳過了一些不感興趣的章節(jié)署浩，時間上允許的話加上第三部分揉燃。
高級編程語言課程：專注在第一部分和第五部分，還有第三部分的一些選擇章節(jié)筋栋。
? . For the Professional Lisp Programmer: Read as much of the book as possible, and
refer back to it often. Part III and chapter 25 are particularly important.
對于專業(yè)的Lisp程序員：盡量多看看書中的每一個細(xì)節(jié)炊汤，仔細(xì)復(fù)習(xí)。第三部分和第25章特別重要弊攘。

可以作為參考的書籍和文獻(xiàn)

最精準(zhǔn)的參考書籍是Steele寫的Common Lisp the Language抢腐。從1984年到1990年，這本書就是Common Lisp的非官方定義襟交，但是到了1990年迈倍，情況因為Common Lisp the Language第二版的問世而復(fù)雜了很多。這本書也是Steele寫的捣域，包含了ANSI子委員會X3J13的推薦部分啼染，這些章節(jié)就是定義了一個Lisp的標(biāo)準(zhǔn)醋界。這些推薦內(nèi)容包括很多較小的改動和澄清定義，也有一些全新的材料提完，面向?qū)ο蟮木幊蹋e誤條件處理丘侠，還有l(wèi)oop宏徒欣。新的材料將書的厚度從465頁增加到了1029頁。
知道ANSI推薦的內(nèi)容被完全接受蜗字，Common Lisp的用戶一直處在一種分裂的打肝，互相不兼容的標(biāo)準(zhǔn)中：就是原始的Common Lisp和ANSI Common Lisp。本書中的大部分代碼是對兩種標(biāo)準(zhǔn)都兼容的挪捕。一個ANSI函數(shù)最經(jīng)常的使用的就是loop宏粗梭。ANSI函數(shù)map-into，complement和reduce也是用的级零，只是比較少断医。本書包括了所有函數(shù)的定義，即使是那些使用原始的Common Lisp系統(tǒng)的代碼仍然可以運行奏纪。
Common Lisp the Language的確是一個成文的標(biāo)準(zhǔn)鉴嗤，但是有時候簡練的語言或許會成為初學(xué)者的一個障礙。Common Lisp：the Reference序调，用很多實用的例子提供了完整的語言參考醉锅。Robert Wilensky寫的Common LISPcraft和Artificial Intelligence Programming也包含了簡短的Common Lisp函數(shù)的總結(jié)。他們都不是很綜合发绢，但這也可能是耗時硬耍，因為就會讓讀者更加直接的看到重要的函數(shù)（至少作者這么認(rèn)為）。
看書的時候手邊有個電腦是個很好的注意边酒，自己來嘗試和實踐書上的例子经柴。電腦是蠻有用的，因為Lisp是自生成文檔的甚纲，通過函數(shù)apropos口锭，describe，還有documentation介杆。很多實現(xiàn)也提供更多的擴展文檔鹃操。使用help命令或者菜單就可以獲得。
下面我推薦五本入門的Lisp教科書春哨。第一本比其他的更加擠出一些荆隘。
Common Lisp: A Gentle Introduction to Symbolic Computation，最最適合初學(xué)者的教科書赴背，也包括那些不是學(xué)計算機的學(xué)生翘狱。
A Programmer's Guide to Common Lisp，適合那些有編程經(jīng)驗签夭，但是沒有Lisp經(jīng)驗的讀者饮六。
Common LISPcraft，更加綜合拯田，但仍然適合作為入門和參考書籍。
Common Lisp，Wade L. Hennessey番川，胡亂的包含了一些主題，但是他實現(xiàn)的啟蒙討論確實其他書籍沒有的脊框。
LISP第三版颁督，包含了最全面的編程建議，但是不是一個綜合的參考書浇雹。也許對初學(xué)者很困難沉御。包括了一部分AI的例子。
還有一些書籍是展示如何寫AI程序和工具的昭灵，但是沒有一本是具有這本書的深度的吠裆。盡管如此，專業(yè)的AI程序員會想要熟悉下面的只是烂完，根據(jù)增序排列硫痰。
LISP，同上
Programming Paradigms in Lisp窜护，Rajeev SangaI效斑，體現(xiàn)不一樣的Lisp編程風(fēng)格，展現(xiàn)一些有用的AI工具柱徙。
Programming for Artificial Intelligence缓屠，Wolfgang Kreutzer，Bruce McKenzie护侮，包含了一些基于規(guī)則和模式匹配的基本系統(tǒng)敌完，但是有Lisp，Prolog和Smalltalk的內(nèi)容羊初，因此沒有介紹語言的細(xì)節(jié)滨溉。
.Artificial Intelligence Programming (2d edition)，Eugene Charniak, Christo-
pher Riesbeck, Drew McDermott, and James Meehan长赞，包括了150頁的Lisp概覽晦攒，之后是AI工具的高階討論，只是沒有任何程序得哆。
AI in Practice: Examples in Pop-11脯颜，Allan Ramsey，Rosalind Barrett贩据，五個高級AI程序的高質(zhì)量實現(xiàn)栋操。不太湊巧的是使用的一種不流行的語言闸餐。
當(dāng)前的文本結(jié)合了最后兩個的長處：表述了真實的AI程序和構(gòu)建程序所需要的工具。更進(jìn)一步矾芙，表述是以一種增量的形式遞進(jìn)舍沙，一開始是簡單的版本，之后會更加完整精致剔宪。

習(xí)題的一些小貼士

習(xí)題從頭到尾都有场勤。讀者可以通過做這些習(xí)題來測試自己理解學(xué)習(xí)的水平。練習(xí)的分級是用規(guī)模來分級歼跟，分別是s，m格遭，h哈街，d，可以解釋為題目的復(fù)雜程度或者是需要解決問題所花銷的時間拒迅。

從習(xí)題所需要花銷的時間這個角度可以看出概念是不是很好地被理解了骚秦。如果對著在概念山不清晰，可能就需要花費幾個小時的時間來理解一個m標(biāo)記的問題璧微。習(xí)題在每一個小節(jié)的末尾都會出現(xiàn)作箍。
致謝
（這個就不看了，作者感謝了很多人前硫，基本上都是我不認(rèn)識的人）