Lisp永恒之道
Lisp之魅
長久以來，Lisp一直被許多人視為史上最非凡的編程語言。它不僅在50多年前誕生的時候帶來了諸多革命性的創(chuàng)新并極大地影響了后來編程語言的發(fā)展，即使在一大批現(xiàn)代語言不斷涌現(xiàn)的今天，Lisp的諸多特性仍然未被超越。當(dāng)各式各樣的編程語言擺在面前，我們可以從運行效率、學(xué)習(xí)曲線、社區(qū)活躍度、廠商支持等多種不同的角度進(jìn)行評判和選擇，但我特別看中的一點在于語言能否有效地表達(dá)編程者的設(shè)計思想。學(xué)習(xí)C意味著學(xué)習(xí)如何用過程來表達(dá)設(shè)計思想，學(xué)習(xí)Java意味著學(xué)習(xí)如何用對象來表達(dá)設(shè)計思想，而雖然Lisp與函數(shù)式編程有很大的關(guān)系，但學(xué)習(xí)Lisp絕不僅僅是學(xué)習(xí)如何用函數(shù)表達(dá)設(shè)計思想。實際上，函數(shù)式編程并非Lisp的本質(zhì)，在已經(jīng)掌握了lambda、高階函數(shù)、閉包、惰性求值等函數(shù)式編程概念之后，學(xué)習(xí)Lisp仍然大大加深了我對編程的理解。學(xué)習(xí)Lisp所收獲的是如何“自由地”表達(dá)你的思想，這正是Lisp***的魅力所在，也是這門古老的語言仍然具有很強的生命力的根本原因。
Lisp之源
Lisp意為表處理(List Processing)，源自設(shè)計者John McCarthy于1960年發(fā)表的一篇論文《符號表達(dá)式的遞歸函數(shù)及其機器計算》。McCarthy在這篇論文中向我們展示了用一種簡單的數(shù)據(jù)結(jié)構(gòu)S表達(dá)式(S-expression)來表示代碼和數(shù)據(jù)，并在此基礎(chǔ)上構(gòu)建一種完整的語言。Lisp語言形式簡單、內(nèi)涵深刻，Paul Graham在《Lisp之根源》中將其對編程的貢獻(xiàn)與歐幾里德對幾何的貢獻(xiàn)相提并論。
Lisp之形
然而，與數(shù)學(xué)世界中簡單易懂的歐氏幾何形成鮮明對比，程序世界中的Lisp卻一直是一種古老而又神秘的存在，真正理解其精妙的人還是少數(shù)。從表面上看，Lisp最明顯的特征是它“古怪”的S表達(dá)式語法。S表達(dá)式是一個原子(atom)，或者若干S表達(dá)式組成的列表(list)，表達(dá)式之間用空格分開，放入一對括號中。“列表“這個術(shù)語可能會容易讓人聯(lián)想到數(shù)據(jù)結(jié)構(gòu)中的鏈表之類的線形結(jié)構(gòu)，實際上，Lisp的列表是一種可嵌套的樹形結(jié)構(gòu)。下面是一些S表達(dá)式的例子:
- foo
- ()
- (a b (c d) e)
- (+ (* 2 3) 5)
- (defun factorial (N)
- (if (= N 1)
- 1
- (* N (factorial (- N 1)))
- )
- )
據(jù)說，這個古怪的S表達(dá)式是McCarthy在發(fā)明Lisp時候所采用的一種臨時語法，他實際上是準(zhǔn)備為Lisp加上一種被稱為M表達(dá)式(M-expression)的語法，然后再把M表達(dá)式編譯為S表達(dá)式。用一個通俗的類比，S表達(dá)式相當(dāng)于是JVM的字節(jié)碼，而M表達(dá)式相當(dāng)于Java語言，但是后來Lisp的使用者都熟悉并喜歡上了直接用S表達(dá)式編寫程序，并且他們發(fā)現(xiàn)S表達(dá)式有許多獨特的優(yōu)點，所以M表達(dá)式的引入也就被無限期延遲了。
許多Lisp的入門文章都比較強調(diào)Lisp的函數(shù)式特性，而我認(rèn)為這是一種誤導(dǎo)。真正的Lisp之門不在函數(shù)式編程，而在S表達(dá)式本身，Lisp***的奧秘就藏在S表達(dá)式后面。S表達(dá)式是Lisp的語法基礎(chǔ)，語法是語義的載體，形式是實質(zhì)的寄托。“S表達(dá)式”是程序的一種形，正如“七言”是詩的一種形，“微博”是信息的一種形。正是形的不同，讓微博與博客有了質(zhì)的差異，同樣的道理，正是S表達(dá)式讓Lisp與C、Java、SQL等語言有了天壤之別。
Lisp之道
一門語言能否有效地表達(dá)編程者的設(shè)計思想取決于其抽象機制的語義表達(dá)能力。根據(jù)抽象機制的不同，語言的抽象機制形成了面向過程、面向?qū)ο?、函?shù)式、并發(fā)式等不同的范式。當(dāng)你采用某一種語言，基本上就表示你已經(jīng)“面向XXX“了，你的思維方式和解決問題的手段就會依賴于語言所提供的抽象方式。比如，采用Java語言通常意味著采用面向?qū)ο蠓治鲈O(shè)計；采用Erlang通常意味著按Actor模型對并發(fā)任務(wù)進(jìn)行建模。
有經(jīng)驗的程序員都知道，無論是面向XXX編程，程序設(shè)計都有一條“抽象原則“：What與How解耦。但是，普通語言的問題就在于表達(dá)What的手段非常有限，無非是過程、類、接口、函數(shù)等幾種方式，而諸多領(lǐng)域問題是無法直接抽象為函數(shù)或接口的。比如，你完全可以在C語言中定義若干函數(shù)來做到make file所做的事情，但C代碼很難像make file那樣聲明式地體現(xiàn)出target、depends等語義，它們只會作為實現(xiàn)細(xì)節(jié)被淹沒在一個個的C函數(shù)之中。采用OOP或是FP等其它范式也會遇到同樣的困難，也就是說make file語言所代表的抽象維度與面向過程、OOP以及FP的抽象維度是正交的，使得各種范式無法直接表達(dá)出make file的語義。這就是普通語言的“剛性”特征，它要求我們必須以語言的抽象維度去分析和解決問題，把問題映射到語言的基本語法和語義。
更進(jìn)一步，如果仔細(xì)探究這種剛性的根源，我們會發(fā)現(xiàn)正是由于普通語言語法和語義的緊耦合造成了這種剛性。比如，C語言中printf("hello %s", name)符合函數(shù)調(diào)用語法，它表達(dá)了函數(shù)調(diào)用語義，除此之外別無他義；Java中interface IRunnable { ... }符合接口定義語法，它表達(dá)了接口定義語義，除此之外別無他義。如果你認(rèn)為“語法和語義緊耦合“是理所當(dāng)然的，看不出這有什么問題，那么理解Lisp就會讓你對此產(chǎn)生更深的認(rèn)識。
當(dāng)你看到Lisp的(f a (b c))的時候，你會想到什么？會不會馬上聯(lián)想到函數(shù)求值或是宏擴展？就像在C語言里看到gcd(10, 15)馬上想到函數(shù)調(diào)用，或者在Java里看到class A馬上想到類定義一樣。如果真是這樣，那它就是你理解Lisp的一道障礙，因為你已經(jīng)習(xí)慣了順著語言去思考，總是在想這一句話機器怎么解釋執(zhí)行？那一句話又對應(yīng)語言的哪個特性？理解Lisp要反過來，讓語言順著你，Lisp的(f a (b c))可以是任何語義，完全由你來定，它可以是函數(shù)定義、類定義、數(shù)據(jù)庫查詢、文件依賴關(guān)系，異步任務(wù)的執(zhí)行關(guān)系，業(yè)務(wù)規(guī)則 ...
下面我準(zhǔn)備先通過幾個具體的例子逐步展示Lisp的本質(zhì)。需要說明的是，由于Lisp的S表達(dá)式和XML的語法形式都是一種樹形結(jié)構(gòu)，在語義表達(dá)方面二者并無本質(zhì)的差別。所以，為了理解方便，下面我暫且用多數(shù)人更為熟悉的XML來寫代碼，請記住我們可以很輕易地把XML代碼和Lisp代碼相互轉(zhuǎn)換。
首先，我們可以輕易地用XML來定義一個求兩個數(shù)***公約數(shù)的函數(shù)：
- <func name='gcd' return_type='int'>
- <params>
- <a type='int'/>
- <b type='int'/>
- </params>
- <body>
- <if>
- <equals>
- <a/>
- <int>0</int>
- </equals>
- </if>
- <then>
- <return><b/></return>
- </then>
- <else>
- <return>
- <gcd>
- <modulo><b/><a/></modulo>
- <a/>
- </gcd>
- </return>
- </else>
- </body>
- </func>
其次，我們可以用它來定義類：
- <class name="Computer">
- <field access="private" type="MainBoard" name="main-board" />
- <field access="private" type="CPU" name="cpu" />
- <field access="private" type="Memory" name="memory" />
- <method access="public" return_type="boolean" name="powerOn" />
- <params>...</params>
- <body>...</body>
- </method>
- <method access="public" return_type="boolean" name="powerOff" />
- <params>...</params>
- <body>...</body>
- </method>
- </class>
還可以輕易地用它來編寫關(guān)系查詢：
- <sql>
- <select>
- <column name="employees.id" />
- <column name="bonus.amount" />
- </select>
- <from>
- <table name="employees" />
- <table name="bonus" />
- </from>
- <where>
- <equals>
- <column name="employees.id" />
- <column name="bonus.employee_id" />
- </equals>
- </where>
- </sql>
還可以用它來實現(xiàn)類似make file的自動化構(gòu)建(語法取自ant)：
- <project name="MyProject" default="dist" basedir=".">
- <property name="src" location="src"/>
- <property name="build" location="build"/>
- <property name="dist" location="dist"/>
- <target name="init">
- <mkdir dir="${build}"/>
- </target>
- <target name="compile" depends="init" description="compile the source " >
- <javac srcdir="${src}" destdir="${build}"/>
- </target>
- <target name="dist" depends="compile" description="generate the distribution" >
- <mkdir dir="${dist}/lib"/>
- <jar jarfile="${dist}/lib/MyProject-${DSTAMP}.jar" basedir="${build}"/>
- </target>
- <target name="clean" description="clean up" >
- <delete dir="${build}"/>
- <delete dir="${dist}"/>
- </target>
- </project>
一口氣舉了這么多個例子，目的在于用XML這種樹形結(jié)構(gòu)來說明Lisp的S表達(dá)式所能夠描述的語義。不知道你是否發(fā)現(xiàn)了S表達(dá)式和XML這種樹形語法在語義構(gòu)造方面有著特別的“柔性”？我們可以輕易地用它構(gòu)造出函數(shù)、變量、條件判斷語義；類、屬性、方法語義；可以輕易地構(gòu)造出關(guān)系模型的select、where語義；可以輕易地構(gòu)造出make的target、depends語義，等等數(shù)不清的語義。在普通語言里，你可以定義一個函數(shù)、一個類，但你無法為C語言增加匿名函數(shù)特性，也沒法給Java語言加上RAII語義，甚至連自己創(chuàng)造一個foreach循環(huán)都不行，而自定義語義意味著在Lisp之上你創(chuàng)造了一門語言！不管是面向過程，面向?qū)ο螅瘮?shù)式，還是關(guān)系模型，在Lisp里統(tǒng)統(tǒng)都變成了一種DSL，而Lisp本身也就成了一種定義語言的語言，即元語言(Meta Language)。
Lisp的柔性與S表達(dá)式有著密切的關(guān)系。Lisp并不限制你用S表達(dá)式來表達(dá)什么語義，同樣的S表達(dá)式語法可以表達(dá)各種不同領(lǐng)域的語義，這就是語法和語義解耦。如果說普通語言的剛性源于“語法和語義緊耦合”，那么Lisp的柔性正是源于“語法和語義解耦”！“語法和語義解耦”使得Lisp可以隨意地構(gòu)造各種領(lǐng)域的DSL，而不強制用某一種范式或是領(lǐng)域視角去分析和解決問題。本質(zhì)上，Lisp編程是一種超越了普通編程范式的范式，這就是Lisp之道：面向語言編程(LOP, Language Oriented Programming)。Wikipedia上是這樣描述LOP的：
Language oriented programming (LOP) is a style of computer programming in which, rather than solving problems in general-purpose programming languages, the programmer creates one or more domain-specific languages for the problem first, and solves the problem in those languages ... The concept of Language Oriented Programming takes the approach to capture requirements in the user's terms, and then to try to create an implementation language as isomorphic as possible to the user's descriptions, so that the mapping between requirements and implementation is as direct as possible.
LOP范式的基本思想是從問題出發(fā)，先創(chuàng)建一門描述領(lǐng)域模型的DSL，再用DSL去解決問題，它具有高度的聲明性和抽象性。SQL、make file、CSS等DSL都可以被認(rèn)為是LOP的具體實例，下面我們再通過兩個常見的例子來理解LOP的優(yōu)勢。
例1：在股票交易系統(tǒng)中，交易協(xié)議定義若干二進(jìn)制的消息格式，交易所和客戶端需要對消息進(jìn)行編碼和解碼。
消息格式是一種抽象的規(guī)范，本身不對語言做任何的限制，你可以用C，C++，Java，或者Python。普通的實現(xiàn)方式是按照消息格式規(guī)范，在相應(yīng)的語言中定義消息結(jié)構(gòu)，并編寫相應(yīng)的編解碼函數(shù)。假設(shè)為一個消息定義結(jié)構(gòu)和實現(xiàn)編解碼函數(shù)的工作量為M，不同消息類型的數(shù)量為N，這種方式的工作量大致為M*N。也就是說每增加一種消息類型，就需要為該消息定義結(jié)構(gòu)，實現(xiàn)編解碼函數(shù)，引入bug的可能性當(dāng)然也和M*N成正比。如果仔細(xì)觀察不難發(fā)現(xiàn)，各個消息結(jié)構(gòu)其實是高度類似的，編解碼函數(shù)也大同小異，但是普通語言卻找不到一種抽象機制能表達(dá)這種共性，比如，我們無法通過面向?qū)ο蟮姆椒ǘx一個基類把消息結(jié)構(gòu)的共性抽象出來，然后讓具體的消息去繼承它，達(dá)到復(fù)用的目的。這正是由于普通語言的抽象維度限制所致，在普通語言中，你只能從函數(shù)、接口等維度對事物進(jìn)行抽象，而恰好消息格式共性所在的維度與這些抽象維度并不匹配。
其實，不同消息類型的共性在于它們都具有相同的領(lǐng)域語義，比如：“某字段內(nèi)容是另一個字段內(nèi)容的md5碼”就是一種消息格式的領(lǐng)域語義，這種領(lǐng)域語義是OOP的抽象機制無法描述的。LOP的思路是先創(chuàng)建一門消息定義DSL，比如，類似Google的Protocol Buffer，Android的AIDL。然后，通過DSL編寫消息定義文件，直接聲明式地描述消息的結(jié)構(gòu)特征，比如，我們可以聲明式地描述“某字段內(nèi)容是另一個字段內(nèi)容的md5碼”。我們還需要為DSL開發(fā)編譯器用于生成C、Java等通用語言的消息定義和編解碼函數(shù)。
有了消息定義DSL和編譯器之后，由于DSL編寫消息定義是一種高度聲明式的編程方法，每增加一種消息的只需要多編寫一個消息定義文件而已，工作量幾乎可以忽略不計。所有的工作量都集中在編譯器的開發(fā)上，工作量是一個常數(shù)C，與消息的數(shù)量沒有關(guān)系；質(zhì)量保證方面也只需要關(guān)注編譯器這一點，不會因為增加新的消息類型而引入bug。
例2：在圖書管理系統(tǒng)中，需要支持在管理界面上對書籍、學(xué)生、班級等各種實體進(jìn)行管理操作。
如果按傳統(tǒng)的三層架構(gòu)，一般需要在后端程序中為每一種實體定義一個類，并定義相應(yīng)的方法實現(xiàn)CRUD操作，與之相應(yīng)的，還需要在前端頁面中為每一個實體編寫相應(yīng)的管理頁面。這些實體類的CRUD操作都是大同小異的，但細(xì)節(jié)又各不相同，雖然我們很想復(fù)用某些共同的設(shè)計實現(xiàn)，但OOP所提供的封裝、繼承、多態(tài)等抽象機制不足以有效捕獲實體之間的共性，大量的代碼還是必須放在子類中來完成。比如，Student和Book實體類的實現(xiàn)非常相似，但是如果要通過OOP的方式去抽象它們的共性，得出的結(jié)果多半是Entity這樣的大而空的基類，很難起到復(fù)用的效果。
其實，不同實體之間的共性還是在于它們具有相同的領(lǐng)域語義，比如：實體具有屬性，屬性具有類型，屬性具有取值范圍，屬性不具有可讀取、可編輯等訪問屬性，實體之間有關(guān)聯(lián)關(guān)系等。LOP方法正是直接面向這種領(lǐng)域語義的。采用LOP方法，我們并不需要為每一個實體類單獨編寫CRUD方法，也不需要單獨編寫管理頁面，只需要定義一種DSL并實現(xiàn)其編譯器；然后，用DSL聲明式地編寫實體描述文件，去描述實體的屬性列表，屬性的類型、取值范圍，屬性所支持的操作，屬性之間的關(guān)系和約束條件等；***，通過這個實體描述文件自動生成后端的實體類和前端管理頁面。采用LOP，不論前后端采用何種技術(shù)，Java也好，C#也好，JSP也好，ASP.NET也好，都可以自動生成它們的代碼。采用LOP的工作量和質(zhì)量都集中在DSL的設(shè)計和編譯器的開發(fā)，與實體的數(shù)量無關(guān)，也就是說，越是龐大的系統(tǒng)，實體類越多越是能體現(xiàn)LOP的優(yōu)勢。
通過上面兩個小例子我們可以感受到，LOP是一種面向領(lǐng)域的，高度聲明式的編程方式，它的抽象維度與領(lǐng)域模型的維度完全一致。LOP能讓程序員從復(fù)雜的實現(xiàn)細(xì)節(jié)中解脫出來，把關(guān)注點集中在問題的本質(zhì)上，從而提高編程的效率和質(zhì)量。
接下來的問題是如果需要為某領(lǐng)域設(shè)計DSL，我們是應(yīng)該發(fā)明一門類似SQL這樣的專用DSL呢，還是用XML或S表達(dá)式去定義DSL呢？它們各有何優(yōu)缺點呢？
我認(rèn)為采用XML或S表達(dá)式定義DSL的優(yōu)點主要有：1) SQL、make file、CSS等專用DSL都只能面向各自的領(lǐng)域，而一個實際的領(lǐng)域問題通常是跨越多個領(lǐng)域的，有時我們需要將不同領(lǐng)域融合在一起，但是由于普通語言的剛性，多語言融合通常會是一件非常困難的事情，而XML和S表達(dá)式語法結(jié)構(gòu)的單一性和“代碼及數(shù)據(jù)”的特點使得跨領(lǐng)域融合毫無障礙。2) 在為DSL開發(fā)編譯器或解釋器的方面，二者難度不同。對XML和S表達(dá)式定義的DSL進(jìn)行語法分析非常簡單，相比之下，對SQL這樣的專用DSL進(jìn)行語法分析，雖然可以借助Lex、Yacc、ANTLR等代碼生成工具，但總的來講復(fù)雜度還是要明顯高一些。
當(dāng)然，XML和S表達(dá)式的優(yōu)點也正好是其缺點，由于XML和S表達(dá)式的語法形式是固定的，不能像專用DSL那樣自由地設(shè)計語法。所以，一般來講專用DSL的語法顯得更加簡潔。換句話說，XML和Lisp其實是在語法和語義間做了一個交換，用語法的限制換來了語義的靈活。
Lisp之器
接下來我們繼續(xù)探討DSL的解釋執(zhí)行問題。DSL代碼的解釋執(zhí)行一般分為3種典型的方式：1) 通過專門的解釋器解釋執(zhí)行；2) 編譯生成其他語言的代碼，再通過其他語言的解釋器解釋執(zhí)行(或編譯運行)；3) 自解釋。比如，第1類的代表是SQL，上一節(jié)舉的兩個例子都屬于第2類，而第3類自解釋正是Lisp的特色。
為了理解自解釋，我們可以先從內(nèi)部DSL的解釋執(zhí)行說起。內(nèi)部DSL是指嵌入在宿主語言中的DSL，比如，Google Test單元測試框架定義了一套基于流暢接口(Fluent Interface)的C++單元測試DSL。從語義構(gòu)造的角度看，內(nèi)部DSL直接借用宿主語言的語法定義了自己的領(lǐng)域語義，是一種語法和語義解耦；從解釋執(zhí)行的角度看，內(nèi)部DSL是隨宿主語言的解釋器而自動解釋的，不需要像外部DSL一樣開發(fā)專門的解釋器，因而實現(xiàn)的代價很低。當(dāng)然，并不是說設(shè)計內(nèi)部DSL不用關(guān)心任何的解釋實現(xiàn)，實際上，還是需要熟悉宿主語言的特性，并利用該特性使得DSL能隨著宿主語言的解釋器得到解釋執(zhí)行。
Lisp擁有強大的自解釋特性，這得益于***的Lisp之器：宏 (macro)。宏使得Lisp編寫的DSL可以被Lisp解釋器直接解釋執(zhí)行，這在原理上與內(nèi)部DSL是相通的，只是內(nèi)部DSL一般是利用宿主語言的鏈?zhǔn)秸{(diào)用等特性，通常形式簡陋，功能有限，而Lisp的宏則要強大和靈活得多。
C語言中也有宏的概念，不過Lisp的宏與C語言的宏完全不同，C語言的宏是簡單的字符串替換。比如，下面的宏定義：
#define square(x) (x*x)
square(1+1)的期望結(jié)果是4，而實際上它會被替換成(1+1*1+1)，結(jié)果是3。這個例子說明，C語言的宏只在預(yù)編譯階段進(jìn)行簡單的字符串替換，對程序語法結(jié)構(gòu)缺乏理解，非常脆弱。Lisp的宏不是簡單的字符串替換，而是一套完整的代碼生成系統(tǒng)，它是在語法解析的基礎(chǔ)上把Lisp代碼從一種形式轉(zhuǎn)換為另一種形式，本質(zhì)上起到了普通語言編譯器的作用。不同的是，普通編譯器是把一種語言的代碼轉(zhuǎn)換為另一種語言的代碼，比如，Java編譯器把Java代碼轉(zhuǎn)換成Java字節(jié)碼；而Lisp宏的輸入和輸出都是S表達(dá)式，它本質(zhì)上是把一種DSL轉(zhuǎn)換為另一種DSL。下面的例子是宏的一個典型用法。
例3：假設(shè)Lisp解釋器已經(jīng)具備解釋執(zhí)行面向過程DSL的能力，需要實現(xiàn)類似ant的自動化構(gòu)建工具。
我們可以基于宏構(gòu)建一門類ant的DSL，宏的作用是把類ant DSL通過宏展開變成面向過程的DSL，***被Lisp解釋器所解釋執(zhí)行。這樣用Lisp編寫的ant DSL就不需要被編譯為其他語言，也不需要像XML的ant一樣依賴于專門的解釋器了。
當(dāng)然，和開發(fā)專門的解釋器/編譯器相比，Lisp的宏也并非沒有缺點，宏難以理解，開發(fā)和調(diào)試更加困難。到底是開發(fā)專門的解釋器/編譯器還是直接采用宏應(yīng)該視具體情況而定。
總結(jié)
Lisp采用單一的S表達(dá)式語法表達(dá)不同的語義，實現(xiàn)了語法和語義解耦。這使得Lisp具有強大的語義構(gòu)造能力，擅長于構(gòu)造DSL實現(xiàn)面向語言編程，而宏使得Lisp具有自解釋能力，讓不同DSL之間的轉(zhuǎn)換游刃有余。進(jìn)入Lisp的世界應(yīng)當(dāng)從理解面向語言編程入門，這是Lisp之道，而函數(shù)式編程和宏皆為Lisp之器，以道馭器方為正途。
后記
本文是我學(xué)習(xí)Lisp的一個總結(jié)，也是寫給有興趣學(xué)習(xí)Lisp的程序員的入門資料。必須說明，我還是一個標(biāo)準(zhǔn)的Lisp初學(xué)者，幾乎沒有寫過像樣的Lisp程序，文中的錯誤和不足在所難免，希望讀者批評指正，感謝！
原文鏈接：http://www.cnblogs.com/weidagang2046/archive/2012/06/03/tao_of_lisp.html
【編輯推薦】
