lisp

The Little JavaScripter
kuangjc5566 - 你是如何成為Lisp程序員的？

問題之：你是如何成為Lisp程序員的？

答：我成為Lisp程序員的道路曲折而漫長。我曾於2007年10月3日在自己的日記中總結了自己的學習經歷，現抄錄於此。

最早在2000年5月，斯托曼院士訪華時告訴我，Lisp （或者它的現代變種Scheme）是功能最強大的編程語言，他本人就是一位高級的Lisp程序員，他還精通C ，GNU Emacs就是採用C和Lisp兩者開發的。我當時已經掌握了C，但不會用Lisp，但是我完全相信他說的都是真的。於是，一心想成為編程高手的我，決定學習和掌握這門編程語言。我從2000年下半年開始學習Lisp。下面總結的學習經歷大致按照時間先後順序排出：

有必要先說明一點，在我遇到斯托曼院士之前，我在上大學時曾經閱讀過一本關於人工智能的著作，《Artificial Intelligence --- Making machines "think"》，
作者是Neill Graham，這本書的最後一章（第14章）是關於Lisp語言的簡介，
所以我對人工智能和Lisp的概念並不完全陌生。這本書前面的章節都很好理解，但是在這最後一章，我遇到了很大困難。我花了許多時間試圖明白其中的道理，不過最後成效不彰，現在回想起來，究其緣故，最主要的就是我沒有一個適當的上機練習環境，在讀了許多書中的東西後，當時我感覺似乎明白了其道理，但是實際上並沒有真正理解清楚。不過，有兩點在我看來無疑是確定的：一、Lisp早已經成為人工智能研究項目的首選（或者說是默認的）編程工具，在人工智能領域沒有其他語言能撼動其領導地位。二、對於具有表結構的數據操作，對於列表（list）頭元素（pair的car的部分）的處理採用遞歸方式比較好，而對於眾多的體元素（pair的cdr的部分）則採用迭代的方式處理效率更好。

斯托曼院士回國後，我首先在計算機上嘗試用Emacs Lisp編程，
它是嵌入在GNU Emacs文本編輯器中的解釋器。在龐大的Lisp家譜中，
Emacs Lisp不是Common Lisp，而是早期的MacLisp的一個直系後代，
同時在一些方面作了簡化和強化。同時我開始閱讀Robert Chassell所著《Introduction to Emacs Lisp Programming》，Robert Chassell是斯托曼院士早年結識的戰友，也是自由軟件基金會的合創人之一，他很早就使用GNU Emacs，而且使用Emacs Lisp程序定制GNU Emacs，斯托曼友善地把Robert Chassell介紹給我認識。這本書既是自由文檔（可以從GNU的網站自由下載），又是自由軟件基金會出版社（GNU Press）的出版物。等我讀完了這本書之後，我覺得這本書實在太美妙了，作者的文筆十分了不起（即使對於想學習英文寫作的人，幫助也應該很大），把這本書介紹給其他人是完全值得的。我於是找了兩位翻譯人員（毛文濤博士和呂芳女士），把它譯成了中文，我則擔任了全書的編輯和審校工作。中文版質量很高，我很滿意，它作為一本很偉大的編程入門書籍十分適合廣大讀者自學（我認為讀者應該搞到一本閱讀）。我至今還想自己動手翻譯這本書的第三版，可惜如今我很難再找到當年那麼多的時間做編輯和審校之類的工作了。

閱讀完這本書之後，我意識到如果想使用Emacs Lisp開發非玩具級別的實際應用程序，那麼根據作者的推薦，自由軟件基金會出版的《GNU Emacs Lisp Reference Manual》是必不可少的工具書，我打印了這份文檔的第2.4版本，厚厚的共四本。後來這份文檔正式出版，從GNU網站上訂購的圖書升級到了2.6版本，針對的是GNU Emacs version 21。我不太認同Eric Raymond在他的名著《The Art of Unix Programming》中對Emacs Lisp的評論，他以為Emacs Lisp只能為Emacs編輯器本身編寫控製程序，而趕不上其他腳本語言全面。實際上，我認為只要熟悉了Emacs Lisp的細節，其他任何腳本語言能完成的工作，都可以使用Emacs Lisp程序完成。我親眼看見斯托曼院士在GNU Emacs內完成電子郵件的編輯、收發等工作，不用Eric Raymond開發的fetchmail程序一樣幹得很好。我自己也利用Emacs Lisp編寫過CGI應用程序，效果也不錯。

Bob Glickstein曾經寫過一本《Writing GNU Emacs Extensions》，可以配合Robert Chassell的書與《GNU Emacs Lisp Reference Manual》，作為補充讀物。

讀了Robert Chassell的書之後，我開始花時間閱讀David Touretzky博士所著的《Common Lisp: A Gentle Introduction to Symbolic Computation》，這本書可以從互聯網上自由下載，讀者可以自行在萬維網上google得到它。這也是一本偉大的Lisp著作，內容已經是基於 Common Lisp的，但是作者並沒有特意強調這一點。我把下載的PDF文件打印出來，自己動手把打印出的文檔紙張裝訂成了兩卷手冊。我從這本書中得到的最大收穫是我充分認識到Lisp中的一切都是對象：數字原子（numeric atoms）和符號原子（symbolic atoms）都是對象。數字原子求值返回它自身的值，而符號原子則有名稱（name）、類型（type）、值（value）、秉性表（plist）和綁定表（bindlist）。這五個字段可以放入一個數據結構中，並在實現中以C語言的struct表達。

在閱讀這些材料的同時，我又從網上找到了Gary Knott教授編寫的一份文檔，《Interpreting Lisp》，這份文檔篇幅不長，從來沒有正式出版成書。在這份文檔中，作者利用C語言編寫了一個微小的Lisp實現，非常接近於最初的Lisp實現。最可貴的是他將實現的源代碼和盤托出。從這本書中，我清晰地看到瞭如何構造Lisp對象的結構，我開始認識到內存垃圾收集算法的重要性。在理解了David Touretzky博士所著的《Common Lisp: A Gentle Introduction to Symbolic Computation》介紹的Lisp對象的結構基礎上，我明白了書中圖示的Lisp對像中若僅在結構設計時安排五個字段是不夠的，還需要有供垃圾回收（GC，Garbage CCollector）模塊操作的字段才行。

在2001-2002期間，我開始接觸Scheme。在此之前的2000年8月，Rorbert Chassell曾來中國訪問，我們在西安時，他向我介紹了Scheme是我應該關注的語言。 Scheme於1985年誕生於MIT，發明人有兩位：一位是Gerald Sussman教授，他是自由軟件基金會的董事會成員之一，另一位是Guy J.Steele博士，下面即將更多地提到。我首先使用了Dorai Sitaram所著的教材《Teaching Yourself Scheme in Fixnum Days》，這份文檔可以從網絡自由下載，不過坦率地說，這本書教材不太適合初學者，閱讀它的人至少應該具有很多基礎知識或者經驗才行。我並沒有從這本書從獲得太多的幫助，對Scheme的基本概念也沒有搞清楚，特別是連續（Continuation）之類的概念沒有理解。不過，收穫還是有很多，我意識到 Scheme是一個非常優美的Lisp變種，它繼承了源自Algol60和早期Lisp兩者的特點。這份教材的最後還列舉出了一個具體的編程實例，講授如何利用Scheme編寫CGI程序。現在我看來，在CGI編程等領域， Perl和PHP等腳本語言獲得廣泛應用簡直就是鑽了Lisp社團不善營銷的空子。

到了2001夏天，我從美國獲得了《Structure and Interpretation of Computer Programs》的教師手冊，是我的朋友James Gray幫我買的，他是我一個很好的朋友，不過我這裡要善意地埋怨一下，他做事有些馬大哈，我原來希望他給我搞到這本書的學生用書，沒有想到他卻寄來了教師手冊，我想他在買書時沒有仔細區分一下，而此著作的教師手冊和學生用書的封面都採用了同一圖案，作者和MIT出版社的編輯的確很優秀，他們在營銷本書時非常成功，後來專門還開設了一個網站推廣本書和相關的教學材料，網上公佈了教材的全部內容，加上兩位作者課堂教學的視頻錄像。教師手冊價格比較便宜，James在購買時要么沒有仔細辨認清楚，要么就是幫我省錢，才寄來了這本教師手冊。我當時沒有學生手冊，也就沒有繼續學習Scheme。不過話說回來，James寄給我的教師手冊我一直都留在我手頭，後來對於我在黑客道教學中講授Scheme幫助極大，在這裡還是應該深深地感謝James Gray。

不久（2003年），我買了一本Patrick Winston教授所著的《Common Lisp》第三版，作者是麻省理工學院人工智能實驗室的主任（斯托曼早年就是他手下的兵），在美國的人工智能研究領域名氣很大，我就是衝著他的名氣才買此書的。閱讀完之後，我覺得這位教授名副其實，而不像我在國內見到的一些人徒有虛名，拿不出真東西。這是一本介紹Common Lisp的極好教材。後來Hans Hagen （ConTeXt排版軟件包的主要作者之一）告訴我這本書的合著者Berthold Klaus Paul Horn在TeX社團名氣也很大，的確如此，從本書的排版質量即可看出許多名堂來，排版樣式一看就是典型的TeX風格。作為中文TeX用戶俱樂部（CTUG）的主席，我已經知道，國內學術界（我指的是數學界和計算機科學技術界）很少有人精通TeX排版系統，鮮有人能使用它排版自己的講義或著作。

讀了這本書之後，我感覺自己必須閱讀Common Lisp的語言參考手冊，許多問題必須在看到語言規範（這是基本的尺度）之後才能搞清楚。 Guy L. Steele博士寫過這樣的手冊，而且他寫了兩次，第一個版本是在Common Lisp標準化之前完成的，第二個版本是在標準化完成之後寫成的，但是網上有人評論說有些該寫的東西沒有寫進去，此書是否會有第三版不得而知。 Guy L. Steele博士是非常著名的語言手冊的作者，他已經為C、Common Lisp、Java等編程語言都寫過的語言參考手冊，都非常成功，這些參考手冊都是一版再版，銷路極好，比位於瑞士的國家標準化組織（ISO）發布的非常昂貴的標准文檔銷路好許多。他寫的這些語言參考手冊已經成為編寫這些語言編譯器作者們的大救星。

大約在同時，我下載了《On Lisp》，這是Paul Graham博士編寫的一本優秀著作，從中我得到了許多Lisp概念的細節，特別是Lisp的macro機制，
以及黑客們如何利用Lisp思考問題。作者介紹的自底向上（bottom up）的方法論對我觸動很大，而作者的講解是非常富於啟發性的（作者曾專程赴意大利的美術學院學習過油畫創作，所以具有很高的藝術修養）。從那時開始，混合編程（Hybrid Programming）的思想在我頭腦中開始成型，我堅信Lisp將會成為一種非常長壽的編程語言，這使我聯想起斯托曼院士當年在四川九寨溝就GNU Emacs開發對我講過的話。在GNU Emacs和Lisp背後隱含的方法論是永遠不會過時的。

2004年，我真正找到了Lisp編程的感覺，覺得自己開始進入狀態，
並開始使用Scheme開發真正的應用程序，我編寫的程序是一個網絡應用程序，即一個網絡留言板（Web-based bulletin System），在萬維網上可以運行，
CGI的模塊是採用Scheme寫的，Apache在服務器上通過Scheme的CGI程序接上了PostgreSQL數據庫。我使用的是PLT Scheme的103版本，我非常喜歡這個版本，既簡單又很乾淨，我用C語言和PostgreSQL提供的libpg編寫了一個DA （database adaptor），讓Scheme程序可以訪問PostgreSQL數據庫。

完成了這個項目之後，好事成雙，我得到了渴望已久的《Structure and Interpretation of Computer Programs》（簡稱SICP，或者“紫皮書”），作者就是Harold Abelson教授和Gerald Sussman教授。正是這一年，我開始利用自己頭腦中形成的數學觀點，特別是在我的泛系尺度論中表達的思想，來認真學習Scheme，並且主動地從中國古代的陰陽太極圖模型來理解當今電子計算機系統上的計算模型。這一過程延續了很長時間，直到2005年的冬天才最終獲得成功！這期間的許多思想寫入了我的著作《自由軟件：新的遊戲規則》第三卷內篇的第二章“論尺度”。今後我還準備花更多的時間把它擴展開來，形成一部單行本的著作《泛系尺度論》，在這個單行本中，我將利用更長的篇幅把中國古代的哲理思想、現代數學思想和計算機編程融為一體，對整個計算理論提出自己完整的一家之言。在黑客道九個段位中，初段就是講“計算的本質”，裡面就納入了我的思想方法和編程經驗。

2004-2005年期間，我仔細地研究了R5RS文檔中除了第七章之外的所有內容，
收穫巨大。對於第七章的內容，當時仍然有些疑惑，因為這些材料需要理解大量的關於lambda calculi的細節和大量的預備知識，我當時還沒有找到充分的材料鑽研。另外，在研究PLT Scheme的源代碼時，內存垃圾回收算法對我而言，仍然是一大疑難問題，顯然，對於內存垃圾回收技術，我還需要學習更多的背景材料。

到了2005年的年底，我把R5RS翻譯成了中文。在完成翻譯的過程中，我知道瞭如何利用形式語言和擴展的巴科斯－勞爾範式（EBNF）來定義一門編程語言的形式句法和語義規則，以及如何正確理解和讀懂它。

2005-2006期間，我學習了其他許多關於Lisp編程的書籍，包括Paul Graham博士的《ANSI Common Lisp》、 Matthew Flatt等人合著的《How to Design
Programs》, Brian Harvey和Matthew Wright合著的《Simply Scheme ---
Introducing Computer Science》（此書的封面設計別出心裁，非常值得回味）、
Daniel Friedmann和Matthias Felleisen合著的《The Little Schemer》和
《The Seasoned Schemer》。另外我花了相當多的時間仔細閱讀《The Scheme Programming Language, 3e》，這是R. Dybvig教授的代表作，他是Chez Scheme實現的設計大師。年底我得到了《Hackers and Painters》（“黑客和畫家”），這是Paul Graham博士所著的散文集，與Robert Chassell一樣，他也是一位偉大的作家，他的行文非常容易閱讀，而且這本書中的內容如同其書名副標題一樣，的確收入了許多偉大的想法，這些想法對於創新公司利用Lisp開發創新項目是非常富有啟發性的。

2006年7月15日，我的學生千俊哲從南韓的漢城大學帶來了他學習的兩本著作的複印件：George Springer和Daniel P. Friedman合著的《Scheme and the Art of Programming》，以及Mark Watson的《Programming in Scheme: Learn Scheme through Artificial Intelligence Programs》。前一本的難度在紫皮書之下，比較好讀，其中許多程序如同棋譜一樣，展現了許多高級編程技巧，值得反复思考，我立即在PLT Scheme實現上驗證了書中的大部分代碼；後一本則介紹如何使用MIT Scheme來設計人工智能程序，非常精彩。

2006年7月送走了千俊哲之後的夏天，我一直在瑞士蘇黎世度假（八月下旬我還去了西班牙馬德里參加了國際數學家大會），蘇黎世中央圖書館（ZB，Zentralbibliothek Zuerich）是一所了不起的圖書館，現有藏書一百二十萬種。據說列寧當年在歐洲流亡時曾來到蘇黎世，就睡在這個圖書館裡讀書學習。八月份時，大多數瑞士人也在休假，圖書館的人不多，非常安靜。我在這段時間從圖書館中找到了非常多的背景材料，包括HP Barendregt所著的數學經典教材《The Lambda Calculus --- Its Syntax and Semantics》，這本書於1981年由North Holland出版社出版，對這一數學分支作了詳盡的介紹，我認為對於這一主題，今後再也無人可以寫得比這本著作更好了。另外，我找到了第一本關於 lambda calculus的著作，是由這個理論的創始人Alonzo Church教授創作的，《The Calculi of Lambda-conversion》簡直是無價之寶，在這本小冊子中，作為數學家，作者清晰而精煉地闡明了lambda calculi的全部內容。任何一位想掌握lambda calculus的人都應該仔細閱讀本書。在圖書館中還找到了《An Introduction to Lmabda Calculi for Computer Scientists》，作者是Chris Hankin。 Matthias Felleisen和Matthew Flatt合寫的《Programming Language and Lambda Calculi》也打印出來了，並仔細閱讀了兩遍，這兩人是PLT Scheme研發小組的核心成員。在蘇黎世中央圖書館的書架上，我還看到了SCIP紫皮書的第一版的德文本，書中的內容與英文版第二版大同小異，但是我敏銳地發現，第一版的第四章中沒有收入eval和apply兩個高階算子構成的太極推手圖，第二版中則出現了。

我花時間研究了《Lisp 1.5 Programmer's Manual》，這是世界上第一份真正意義上正式發布過的Lisp穩定實現版本的手冊，作者就是John McCarthy等人，極具學術權威性，我認為任何一位Lisp程序員都應該閱讀這本手冊。時隔多年後，我又開始閱讀關於人工智能方面的著作，《Lisp, Lore and Logic》是W. Richard Stark寫的，《Artificial Intelligence, theory and practice》是Thomas Dean等人寫的，他們都已經使用Common Lisp來說明問題。閱讀時，我參考了前面已經提到的Partrick Winston教授編寫的經典教材《Artificial Intelligence, 3e》。

2007年初，我開始關注Scheme社團中尚處於起草狀態中的R6RS，這個文件將成為新的Scheme語言規範。我現在仍然認為Common Lisp太複雜、太龐大，回廠大修似乎也不太可能，因為工業界已經很好地接受了Common Lisp，而Scheme將是未來的主流。我開始按照這一規範來開發自己的Scheme實現版本，這一實現版本稱為MNM Scheme。

2007年6月至7月間，我在瑞士蘇黎世的Campus Zollikerberg打印了R5.97RS，
我花了許多時間理解這一新的規範，特別是它與前一個版本（R5RS）的差異。
同時，我重新思考了PLT Scheme實現的源代碼和涉及模塊（modules）、名稱空間（namespaces）、盒子（box）類型、define-values和其他附加在R5RS規範之上的特性與實現風格。

從蘇黎世中央圖書館借到的另外一本具有重大價值的著作就是Richard Jones和Rafael Lins合著的《Garbage Collection》，這本書極大地幫助我理解了內存垃圾回收算法設計的細節。我從此開始真正明白了Scheme實現工作中的最後一個陰暗角落。對於一切Lisp對象，內存垃圾收集的算法設計時其實不存在理論上的最優算法，算法的效率受到多種因素的影響，而Lisp的設計者可以根據自己的設計思想來決定應該怎樣回收內存垃圾。

這時的我已經成長為熟練的C++程序員，站在C++程序員的立場看，一切Lisp對像都有類型，我可以用C++語言內置的類（class）來刻畫它們（即聲明各種用戶自定義的類），一切Lisp對像從存儲空間分配和回收的角度來看具有共性，所以，這可以利用C++的模板來表達Lisp對象的存儲管理結構，而各個Lisp對象佔有的存儲空間大小，則可以利用類的構造函數（constructor）和析構函數（destructor）對內存分配和內存垃圾回收在模板的支持下進行統一的操作。

源自Lisp發展起來的GC是一項“古老”的技術，實際上它已經廣泛地被採用了，Java這門當今新的商業編程語言中就有，而且Java的GC算法設計得非常好，我決定在我的Scheme實現中參考它。 2007年9月，我在從香港飛往蘇黎世的飛機上，我閱讀了美國著名的程序員Bruce Eckel所著的《Thinking in Java》的第四版原著，從作者的介紹中，我結合從《 Garbage Collection》中獲得的知識，我理解了Java的內存垃圾回收算法的總體思路，並構思瞭如何利用他們的算法來改進我的設計。而在我離開蘇黎世回國的同一天（2007年9月26日），R6RS技術委員會的全體編輯成員決定凍結對草案的討論，正式發布了這一規範，從那一天起，我實現MNM Scheme的步伐也大大加快了。（不過，請讀者留意在委員會舉辦的投票時，也有許多人投了反對票，並給出了反對意見，這些意見與支持的意見一起，都是極有研究價值的。）

Scheme的實現版本非常多，而且自己能否動手實現一個是考驗一個計算機專業人士學術修養深淺的好指標（這也是我在黑客道中把第五段的教學內容定為“解釋器的原理與構造”的原因之一）。迄今優秀的Scheme實現有： PLT Scheme、MIT Scheme、Chez Scheme等等。我認為PLT Scheme是非常優秀的實現版本，它是按照GPL發布的自由軟件，值得在這裡推薦給廣大讀者。毫不客氣地講，我的MNM Scheme也應該算一個。

Common Lisp的實現版本很多，拋開Franz Lisp等商業版本不談，自由軟件社團中最有名的兩個實現分別是：Bruno Haible等人從1992年以來一直維護和開發的CLISP，以及卡耐基梅隆大學的小組開發CMU Common Lisp。這兩個Common Lisp實現都很好，我個人比較喜歡使用CLISP。目前最好的Common Lisp編程著作可推薦Peter Seibel寫的《Practical Common Lisp》，這位作者的天分顯然比我高，他原來是Java和Perl程序員，2004年才開始學習Common Lisp，他花了一年的時間學習它，就完全學會了，而且在學習的同時，邊練習、邊寫書，結果很豐碩，寫出的這本書就是讀者能看到的結果，這本書得到了廣泛的認可，它出版後獲得了美國出版界計算機圖書創作的震撼大獎。他在一次採訪中提出了一個新的說法：時代的發展需要“第二代Lisp程序員”，而且每個程序員都應該學習Lisp。 （讓我再次回憶起斯托曼院士在2000年時對我說過的話。）

正如讀者在上面所讀到的，成為一位了解Lisp一切內幕的程序員可真不容易，但是我很高興，因為我已經成功地逾越過了這個初看起來曾經非常高的門檻，我現在已經是這樣一位程序員了。學習Lisp給我帶來了巨大的樂趣，如果沒有這種在編程中產生的樂趣相伴，我絕對不會花這麼長的時間來學習它。今天，我由衷地自豪，因為如果按照Peter Seibel的說法和衡量標準，我已經是第二代優秀的Lisp程序員群體中的一分子。

上面羅列的學習經歷對於一般人而言顯然太長了，黑客道學員們則可以站在我的肩膀上，借鑒我的經驗和教訓，少走許多彎路、避免走死胡同。值得慶幸的是，我已經在黑客道的課程設計中自覺地做了許多工作，凡是參加了黑客道的初段課程學習的學員（S1：“計算的本質”），即可在較短的時間內學會掌握 Lisp。