人工智能編程范式：Common Lisp案例學習
Peter Norvig

前言

范式（paradigm）：名詞，一個實例或者一個模式，樣本；特別是指一個出類拔萃的典型樣例。這本書涉及的有三個方面：人工智能領域，或者說AI；計算機編程技術；編程語言Common Lisp。本書可以給讀者的內(nèi)容有，對于AI的一些主要問題和技術的理解，一些重要的AI編程程序理解，還有使用Common Lisp來創(chuàng)建，讀取，修改程序的能力。本書的所有的程序示范樣例都是使用一種好的編程風格范式來編寫。在AI的研究歷史上也有使用廣泛應用的技術來解決重要問題的優(yōu)秀程序。
僅僅是以博雅教育，素質(zhì)教育需要來說，一門課程盡量要包含在一本集文化之大成的書籍中，所以這本書，就是來定義AI課程的一本集文化之大成的書籍。但這并不是暗示說，書中寫的程序是最好的，僅僅是說他們是最具有代表性的。
換個角度來說，這本書是一本是一本高度技術性的知識綱要，這些知識會讓一個中級的Lisp程序員成為專家的過程中有所助益。第一部分和第二部分的布置，讓新手可以快速上手，但如果是完完全全的新手的話，即使是配合這些材料，也可能會舉步維艱。對于真正的新手來說，還好是有至少五本入門的書籍來參考，詳情請見后面的參考書目。
一般來說，教計算機編程的方式是這樣，首先解釋要用的語言的語法構成，之后給學生看看十行規(guī)模的代碼，然后就要求學生開始寫程序。本書中，我們采用的方法是學習讀寫代碼的最好方法（就是反過來，增強讀代碼能力的好的方式就是去寫）。在對Lisp的簡短介紹之后，我們馬上開始進入復雜的程序，然后要求讀者去理解代碼，修改代碼。
本書預設的前提就是，當你理解了什么是好的代碼，并有一些有趣的想法的時候，你就可以寫一些有用的代碼了。也就是說以寫散文的角度寫代碼。有一句話，寫在Pascal語言軟件工具的封面上，是Kernighan和Plauger說的：
優(yōu)秀的編程技巧是如何習得的，是從經(jīng)典的程序中見習得到的，優(yōu)秀的代碼是如何實踐一般的概念和好的編程實現(xiàn)，讓代碼清晰易懂，容易修改維護，人性化，而且可靠高效。對經(jīng)典代碼的認真學習和模仿就可以習得更好的技巧。
高傲的工匠往往只是展現(xiàn)完成的杰作，卻把創(chuàng)造過程中，一開始犯下的錯誤和不可避免的彎路給隱藏掉了。不幸的是，這樣的遮遮掩掩成為了后來的學習者的障礙；當一個研究數(shù)學的學生看到教科書上那數(shù)十行的證明過程的時候，除了驚嘆他簡潔的美之外，但是也沒有辦法學到構建這一個證明的過程。本書試圖展現(xiàn)的就是一個完整的開發(fā)過程，展露無遺。每一章的開頭都有一個簡略版本的程序，不是通用的程序，只在一些例子中可用。之后，我們就會對這些缺點進行分析，然后遞增地構建一個基本程序的完整版本。因此，讀者不僅能夠看到程序最終的結果，而且也可以看到如何從錯誤中學習，講一個初級的未完成的程序進行精煉。還有，讀者如果覺得一些特定的章節(jié)太難而不得不跳過的話，評估一些問題的價值，不要被細節(jié)所煩擾。
本書所著述的是一些松散的知識集合，被稱作AI編程技術，但是有一點要認識到，那就是這些知識之間是沒有非常明確的分界線的。一個人在成為一個優(yōu)秀的AI程序員之前，必定已經(jīng)是一個優(yōu)秀的程序員。因此，書中的一些主題（特別是在第三部分和第五部分）并沒有AI的相關內(nèi)容，只有一些對AI行業(yè)從業(yè)者的基本背景。

為什么用Lisp？為什么用Common Lisp？

Lisp，是最古老的編程語言之一，卻在當下還廣泛使用的使用。Lisp的版本很多，在基本的特性部分是相同的，但是在細節(jié)上差異卻很大。本書使用的Common Lisp是一個Lisp的分支版本，他被認為是Lisp的標準版本。選擇Lisp主要有三個理由：
首先，Lisp是AI編程領域最流行的語言，特別是在美國。如果你想學一門語言，肯定是學大家都在用的，通用的，而不是只有你一個使用的語言。
第二，Lisp語言在定義新的對象的時候生成更加優(yōu)雅。特別是Lisp可以針對手上的問題定義新的語言特性。對于AI編程來說，語言新定義是個特別有用的特性，因為需要經(jīng)常處理復雜的信息，這些信息是以普通文本的方式出現(xiàn)的。 Lisp是少數(shù)允許將程序代碼和數(shù)據(jù)完全等同的語言之一。根據(jù)各個語言的定義，所有的語言都會提供一個定義程序的方式，但是很多其他語言都會限制程序使用的方式，或者限制程序定義的范圍，或者要求程序員顯式聲明沒有意義的細節(jié)。
第三，Lisp可以在很短的時間沒就開發(fā)出程序原型來。Lisp程序是簡潔的，不用處理底層的細節(jié)。Common Lisp提供了大量預先定義好的對象，包括700多個函數(shù)。編程環(huán)境來講也是很好的。（比如調(diào)試工具，可調(diào)編譯器，集成的編輯器，還有窗口系統(tǒng)的接口）。動態(tài)的交互式的Lisp環(huán)境，可以方便地在程序開發(fā)的時候試驗和更改程序。
這里必須提到的是，在歐洲和日本，Prolog語言在AI工程領域已經(jīng)和Lisp一樣流行了。Prolog在可塑性和簡潔性上和Lisp相差無幾。最近，Lisp也開始走向世界，而Prolog也慢慢傳進了美國。之后來說，一個AI從業(yè)者將會要同事掌握兩種語言。本書將會在地十一章和十二章介紹Prolog的關鍵概念，并且在后續(xù)的章節(jié)使用這些概念。
另一個非常流行的Lisp方言是Scheme，但是主要是用在編程語言設計和技術的教育實驗領域，不太用來進行大型項目的開發(fā)。Scheme會在第22章和23章出現(xiàn)。至于其他的Lisp方言，比如Franz Lisp，MacLisp，InterLisp，ZetaLisp，還有Standard Lisp，一般都被認識已經(jīng)淘汰了。還有一些Lisp方言是作為語言的嵌入式擴展延續(xù)了下來。例如，GNU的Emacs就是使用elisp的，而計算機制圖軟件AutoCAD就是用Autolisp，一個Xlisp的衍生版本。在未來，或許Scheme會成為一個流行的擴展語言，他簡短精悍，而且功能強大，并且有一個官方認可的標準定義。
有一個軼事是說，Lisp（還有Prolog）是專用的語言，而其他像Pascal和Care語言都是通用的語言。實際上，卻是反過來說才對。Pascal和C語言都是專用的語言，他們在一個馮諾依曼結構的計算機上操作寄存器和內(nèi)存。他們語法的主體是算是表達式和布爾表達式，當他們系統(tǒng)一些結構化數(shù)據(jù)結構的時候，對流程抽象和控制抽象的機制就顯得匱乏了。另外，他們的設計師面向狀態(tài)的，也就是，通過賦值語句改變變量的值來計算結果。
在另一方面，Lisp對于數(shù)學運算沒有特定的語法。加操作和乘操作和其他操作是一樣的，比如追加，字符處理都一樣的語法。但是Lisp提供了所有編程中需要的東西：定義數(shù)據(jù)結構，函數(shù)，還有兩者的結合。
這種賦值主導，面向狀態(tài)的編程風格Lisp也是可以實現(xiàn)的，但是另外還有面向?qū)ο?，基于?guī)則，和函數(shù)式編程風格都在Lisp中有支持。這種靈活性來自于Lisp的兩個關鍵特性：第一，Lisp具有強大的宏，可以用來擴展語言基礎，通過宏定義，在新的編程風格發(fā)明之后，舊的語言逐漸死去，新的語言更迭，但是Lisp只要定義幾個宏就能跟上步伐了。宏之所以強大是因為Lisp程序是由一種簡單的數(shù)據(jù)結構組成的：列表，在早期，大部分的程序操作都是通過這種列表數(shù)據(jù)結構來解釋的。當今，Lisp已經(jīng)是編譯更加常用于解釋了，程序員也更加依賴Lisp 的第二個特性：函數(shù)。當然，其他語言也有函數(shù)，但是Lisp的特點在于他允許在程序運行中創(chuàng)建新的函數(shù)。
語言的靈活性讓Lisp跟上了編程風格的變遷，但是更加重要的是，Lisp可以適應你的特定編程問題。在其他語言中，都是你的問題來適應編程語言，用Lisp則是可以用語言擴展來適應問題。
由于靈活性，Lisp已經(jīng)成為了快速建模領域的翹楚，比如AI，圖形和UI建模。Lisp已經(jīng)是前沿編程領域的統(tǒng)治性語言，有些問題非常的復雜，以至于還沒有一個清晰的解決方案來開始項目進程。AI的很多問題就是這樣。
根據(jù)你的觀點來看，Common Lisp的規(guī)?？赡苁莾?yōu)點，也可能是缺點。在David Touretzky寫的入門書籍中，側(cè)重點是放在簡潔上。他選擇去寫一些簡潔的輕量程序，而不是引入一個深奧的新特性，這種方法完全適用于初學者，但是本書的讀者應該都已經(jīng)過了初學者這一階段。也就是說，新特性的引入將會在合適的時候暴露給讀者。大多數(shù)時候，新特性就如介紹的一樣來描述，但是有時候?qū)τ诘图壓瘮?shù)如何工作的解釋會轉(zhuǎn)移程序工作的理解的注意力。在給與被當做成人來看待之后，讀者也需要承擔起責任來，在不熟悉的來源尋找自己對術語的解釋和理解。

本書的大概

本書共分為五個部分
第一部分是介紹Common Lisp編程語言本身。
第1章給出一個快速的入門，用一些精簡的例子來展示Lisp的特性。有經(jīng)驗的讀者可以跳過。
第2章是一些進一步的例子，展示Lisp原語是如何組織成一個程序的。初學者的話要認真的學習，即使是有經(jīng)驗的程序員也要看一下來熟悉一下編程感覺還有我的編程風格。
第3章是Lisp原語的概覽?？梢源蟾艦g覽一下，然后當做一個參考手冊，后面有提到的再來查閱。
第一部分是有意做的很精簡的，更多的空間來留給AI編程。那就意味著需要一個更加詳細的參考手冊（或者說在線幫助）來了解語言本身的一個深奧特性了。后面會推薦一些參考書。
讀者或許也想?yún)⒖嫉?5章，那里有調(diào)試和錯誤處理的提示。
第二部分包含的是四個早期的AI程序，全部使用基于規(guī)則的模式匹配技術。一開始是相對簡單的版本，之后會不斷地改進他們漸漸變成跟家復雜的程序，讀者可以一步步學習到高級的編程技巧。
第4章展示一個GPS（General Problem Solver）通用問題解決的重構。這個實現(xiàn)遵循STRIPS（stanford Research Institute Problem Solver）方法。
第5章描述的是ELIZA，是一個模仿人的對話程序。之后的第6章是在GPS和ELIZA中使用的技術總結的章節(jié)，后續(xù)的程序中都可以將他們作為工具使用。
第7章是一個解決高校水平的代數(shù)單詞程序，叫做Student。
第8章開發(fā)一個MACSYMA程序的子集來做符號代數(shù)，包含微分和積分。對于高等數(shù)學有感不適的同學可以跳過這一章。
第三部分我們先放放AI，來看看一個通用的工具，是的編程更加的高效。那些對這部分精通的讀者可能就是一個高級的Lisp程序員了。
第9章是一個高效技術的詳細學習，將緩存，索引，編譯和延遲計算連接起來。第10章包括的內(nèi)容是低層的效率問題，比如使用生命，避免垃圾收集和選擇正確的數(shù)據(jù)結構。
第11章介紹Prolog語言。這是有這雙重目的：展示如何給另一個語言寫一個解釋器，還有介紹Prolog的重要特性，這樣在合適的時候就可以使用了。第12章說的是Prolog的編譯器可以比解釋器快上20倍到200倍。
第13章概略介紹一下面向?qū)ο蟮木幊田L格，之后會瀏覽Common Lisp對象系統(tǒng)（CLOS）。
第14章討論面向邏輯和面向?qū)ο缶幊痰膬?yōu)點和限制，并且用第三部分的技術來開發(fā)一個知識展示系統(tǒng)。
第四部分是一些高級的AI程序
第15章使用第三部分的技術來實現(xiàn)一個更加高效的MACSYMA實現(xiàn)。他會使用一些權威格式的概念，并且使用一系列更加特殊的函數(shù)來代替很通用的重寫規(guī)則方法。
第16章是EMYCIN專家系統(tǒng)shell，一個后端的基于規(guī)則的鏈接系統(tǒng)。醫(yī)療專家系統(tǒng)MYCIN也會簡要介紹。
第17章介紹多面體的Waltz行標記算法（使用Huffman-Clowes標記）。強制傳輸和回溯的方法也會討論。
第18章展示一個出色游戲程序Othello。其中使用的技術，alpha-beta搜索，適用于很多種雙人游戲。
第19章是自然語言處理的介紹。包括上下文無關的語法，自上而下或者自下而上的分析，圖表分析，還有一些語義揭示和參考。
第20章是擴展之前章節(jié)的語義范圍，并引入邏輯語法，用的是第11章開發(fā)的Prolog編譯器。
第21章是一個適當綜合的用邏輯語法格式描述的英語語法。這里會討論一些現(xiàn)實的綜合問題的簡單想法。
第五部分包含的材料對于AI來說是次要的，但是對于Lisp程序員是很重要的。
第22章是介紹Lisp方言Scheme。開發(fā)一個簡單的Scheme解釋器，之后是一個完全的尾遞歸解釋器，然后是一個顯式操作continuation和支持call/cc的解釋器。第23章是一個Scheme編譯器。
第24章是介紹那些單獨在ANSI Common Lisp中的特性。包括loop宏，還有錯誤處理，打印，序列化，包設備。
第25章是一個錯誤處理和調(diào)試的Lisp程序。
文獻列出了200多個文件，綜合索引。另外，附錄提供了一個公開的可獲得的Lisp程序目錄。

如何使用本書

本書預期的讀者范圍是很寬的：任何想要成為一個高級Lisp程序員的人，任何想要成為一個高級AI從業(yè)者的人，下面是一些推薦的學習路徑：
AI課程的入門導論課程：專注在第一部分和第二部分，機上至少一個第四部分的例子。
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程序員：盡量多看看書中的每一個細節(jié)，仔細復習。第三部分和第25章特別重要。

可以作為參考的書籍和文獻

最精準的參考書籍是Steele寫的Common Lisp the Language。從1984年到1990年，這本書就是Common Lisp的非官方定義，但是到了1990年，情況因為Common Lisp the Language第二版的問世而復雜了很多。這本書也是Steele寫的，包含了ANSI子委員會X3J13的推薦部分，這些章節(jié)就是定義了一個Lisp的標準。這些推薦內(nèi)容包括很多較小的改動和澄清定義，也有一些全新的材料，面向?qū)ο蟮木幊?，錯誤條件處理，還有l(wèi)oop宏。新的材料將書的厚度從465頁增加到了1029頁。
知道ANSI推薦的內(nèi)容被完全接受，Common Lisp的用戶一直處在一種分裂的，互相不兼容的標準中：就是原始的Common Lisp和ANSI Common Lisp。本書中的大部分代碼是對兩種標準都兼容的。一個ANSI函數(shù)最經(jīng)常的使用的就是loop宏。ANSI函數(shù)map-into，complement和reduce也是用的，只是比較少。本書包括了所有函數(shù)的定義，即使是那些使用原始的Common Lisp系統(tǒng)的代碼仍然可以運行。
Common Lisp the Language的確是一個成文的標準，但是有時候簡練的語言或許會成為初學者的一個障礙。Common Lisp：the Reference，用很多實用的例子提供了完整的語言參考。Robert Wilensky寫的Common LISPcraft和Artificial Intelligence Programming也包含了簡短的Common Lisp函數(shù)的總結。他們都不是很綜合，但這也可能是耗時，因為就會讓讀者更加直接的看到重要的函數(shù)（至少作者這么認為）。
看書的時候手邊有個電腦是個很好的注意，自己來嘗試和實踐書上的例子。電腦是蠻有用的，因為Lisp是自生成文檔的，通過函數(shù)apropos，describe，還有documentation。很多實現(xiàn)也提供更多的擴展文檔。使用help命令或者菜單就可以獲得。
下面我推薦五本入門的Lisp教科書。第一本比其他的更加擠出一些。
Common Lisp: A Gentle Introduction to Symbolic Computation，最最適合初學者的教科書，也包括那些不是學計算機的學生。
A Programmer's Guide to Common Lisp，適合那些有編程經(jīng)驗，但是沒有Lisp經(jīng)驗的讀者。
Common LISPcraft，更加綜合，但仍然適合作為入門和參考書籍。
Common Lisp，Wade L. Hennessey，胡亂的包含了一些主題，但是他實現(xiàn)的啟蒙討論確實其他書籍沒有的。
LISP第三版，包含了最全面的編程建議，但是不是一個綜合的參考書。也許對初學者很困難。包括了一部分AI的例子。
還有一些書籍是展示如何寫AI程序和工具的，但是沒有一本是具有這本書的深度的。盡管如此，專業(yè)的AI程序員會想要熟悉下面的只是，根據(jù)增序排列。
LISP，同上
Programming Paradigms in Lisp，Rajeev SangaI，體現(xiàn)不一樣的Lisp編程風格，展現(xiàn)一些有用的AI工具。
Programming for Artificial Intelligence，Wolfgang Kreutzer，Bruce McKenzie，包含了一些基于規(guī)則和模式匹配的基本系統(tǒng)，但是有Lisp，Prolog和Smalltalk的內(nèi)容，因此沒有介紹語言的細節(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)。不太湊巧的是使用的一種不流行的語言。
當前的文本結合了最后兩個的長處：表述了真實的AI程序和構建程序所需要的工具。更進一步，表述是以一種增量的形式遞進，一開始是簡單的版本，之后會更加完整精致。

習題的一些小貼士

習題從頭到尾都有。讀者可以通過做這些習題來測試自己理解學習的水平。練習的分級是用規(guī)模來分級，分別是s，m，h，d，可以解釋為題目的復雜程度或者是需要解決問題所花銷的時間。

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