從Lisp語(yǔ)言了解編程語(yǔ)言的解釋與執(zhí)行

唐詩(shī)

關(guān)鍵詞：Lisp函數(shù)；過(guò)程；程序執(zhí)行

1過(guò)程與數(shù)據(jù)抽象

對(duì)任何程序語(yǔ)言的學(xué)習(xí)，最終都主要集中在三個(gè)方面：基本元素，基本元素的組合功能，對(duì)組合后復(fù)合對(duì)象的抽象功能。

Lisp中的基本元素是表達(dá)式。其組成和現(xiàn)在流行的程序語(yǔ)言并沒(méi)有太大差別，如數(shù)字運(yùn)算符+／，判定謂詞eq？等，Lisp作為一個(gè)語(yǔ)族，不同的方言（如rocket）會(huì)有不同的規(guī)定，但大體功能上和C或者Java等相比并沒(méi)有什么本質(zhì)的區(qū)別。在Lisp中表達(dá)式的組織形式是采用括號(hào)來(lái)構(gòu)成各項(xiàng)求值表達(dá)式，且過(guò)程對(duì)于參數(shù)的調(diào)用采用的是前綴式。這在現(xiàn)在的程序語(yǔ)言中比較少見(jiàn)，但這合理有效且不會(huì)造成歧義。我們可以從離散數(shù)學(xué)中采用前綴式來(lái)標(biāo)識(shí)二元關(guān)系的案例，以找到類(lèi)似的痕跡。

在Lisp中，將基本元素組合構(gòu)成復(fù)合對(duì)象或復(fù)合表達(dá)式。本質(zhì)上，這要求語(yǔ)言提供一種類(lèi)似于“膠水”的東西，能將兩個(gè)或者更多的對(duì)象黏在一起。從最簡(jiǎn)單的開(kāi)始，將兩個(gè)對(duì)象組合在一起構(gòu)成一個(gè)對(duì)象，可以通過(guò)某種操作，從這個(gè)對(duì)象中提取出原本的兩個(gè)對(duì)象。用同樣的方式，將這個(gè)組合后的對(duì)象和新的對(duì)象再用之前的組合方式構(gòu)成一個(gè)新的對(duì)象，如此反復(fù)，就可以構(gòu)成任意數(shù)量的元素，且我們可以有一定的方式將構(gòu)成的元素從其中取出。這種愿望思維構(gòu)成的合理推導(dǎo)，最終將問(wèn)題規(guī)約為兩個(gè)元素的組合，并能通過(guò)一定的方式將其從中取出。Lisp在這里提供的工具叫做序?qū)Γ╬air），具體的表現(xiàn)形式如下。

（ define x（cons 1 2））；定義出x

（ car x）；結(jié)果為1

（ cdr x）；結(jié)果為2

其中，cons就是這個(gè)語(yǔ)言中的膠水工具，我們放入其中的元素有順序之分，且可以通過(guò)car與cdr的方式按照順序取出。有了這個(gè)基本的工具，我們就可以在此基礎(chǔ)上進(jìn)一步構(gòu)造復(fù)合對(duì)象。這就是上文中提到的語(yǔ)言的第三個(gè)重要部分——將復(fù)合對(duì)象作為一個(gè)整體，將其像基本元素一樣，進(jìn)一步進(jìn)行組合操作。

cons體現(xiàn)了閉包（closure）的思想，可以說(shuō)Lisp的數(shù)據(jù)在cons運(yùn)算下是封閉的。從序?qū)Φ介]包運(yùn)算，這體現(xiàn)了Lisp的特性，也展現(xiàn)了和數(shù)學(xué)的聯(lián)系——離散數(shù)學(xué)中的二元關(guān)系有序?qū)?，以及群論中的群?duì)于封閉性的要求，都可以使我們找到其中的影子。

cons的實(shí)現(xiàn)，要求我們將過(guò)程作為第一級(jí)元素，能作為求值表達(dá)式的返回。下面是一些關(guān)于程序語(yǔ)言第一級(jí)元素的特點(diǎn)：（1）可被命名為變量；（2）可作為參數(shù)傳遞給程序；（3）可以作為程序的返回值；（4）可以被結(jié)合為數(shù)據(jù)結(jié)構(gòu)。

過(guò)程可以像數(shù)據(jù)一樣作為參數(shù)與返回，這是函數(shù)式編程語(yǔ)言的特點(diǎn)，我們可以在如今市面上常見(jiàn)的函數(shù)式語(yǔ)言如scala中找到類(lèi)似的特性，如此一來(lái)，可以采用常規(guī)的分派方式實(shí)現(xiàn)cons。不過(guò)我們可以更進(jìn)一步，采用純粹過(guò)程的方式來(lái)實(shí)現(xiàn)cons，Lisp語(yǔ)言中提供了lambda表達(dá)式來(lái)作為過(guò)程的定義和返回，我們可以如下實(shí)現(xiàn)cons的功能。

實(shí)際代換結(jié)果表明沒(méi)有問(wèn)題。這被稱(chēng)作邱奇變換。

在面向?qū)ο笳Z(yǔ)言中，我們習(xí)慣說(shuō)，對(duì)于某個(gè)程序的調(diào)用，返回某種數(shù)據(jù)。例如，數(shù)字、字符串或者我們通過(guò)構(gòu)造形成的某個(gè)數(shù)據(jù)對(duì)象，但是更進(jìn)一步，我們?nèi)?wèn)一個(gè)數(shù)據(jù)是什么時(shí)，結(jié)果可能會(huì)語(yǔ)焉不詳。當(dāng)我們說(shuō)數(shù)字1時(shí)，我們知道這并不是指我們打印文本中的“1”這個(gè)符號(hào)，它應(yīng)該是一種象征，代表著某種高度的抽象，可以是一個(gè)雞蛋，一個(gè)蘋(píng)果，可以讓打印文本中顯示出1這個(gè)符號(hào)，也可以是別的什么東西。我們也知道，對(duì)它的操作得到的結(jié)果意味著什么，例如，1+1=2。而2也是某種抽象。

我們的程序代碼，其本質(zhì)其實(shí)是用程序語(yǔ)言對(duì)我們所理解的世界的一種模擬，我們對(duì)于現(xiàn)實(shí)的理解，包括對(duì)于抽象的理解，都會(huì)反映在我們程序中。邱奇的lambda演算，以及邱奇計(jì)數(shù)，可以啟發(fā)我們對(duì)計(jì)數(shù)的純粹函數(shù)的理解。邱奇計(jì)數(shù)采用的是如下方式來(lái)代表O和+1的操作的。

（define zero （lambda （f）

（lambda （x）x）））

（define （add_l n）（lambda （f） （lambda （x）（f（（n f）x）））））

其思想是通過(guò)函數(shù)調(diào)用次數(shù)來(lái)表示數(shù)字，0次調(diào)用來(lái)表示0，1次調(diào)用來(lái)表示1。結(jié)合上文，可以看到，數(shù)字0在這里事實(shí)上是一個(gè)lambda過(guò)程，該過(guò)程參數(shù)為一個(gè)過(guò)程，返回一個(gè)過(guò)程，作為返回結(jié)果的過(guò)程，接收過(guò)程作為參數(shù)，對(duì)該參數(shù)過(guò)程調(diào)用0次，其結(jié)果，體現(xiàn)為傳人的參數(shù)直接返回——包括參數(shù)本身也是lambda過(guò)程的情況。相應(yīng)的，（add_l n）過(guò)程以一個(gè)過(guò)程作為參數(shù)，返回結(jié)果是一個(gè)過(guò)程，該返回結(jié)果的過(guò)程，接收作為參數(shù)的過(guò)程，對(duì)該參數(shù)過(guò)程調(diào)用n+l次。以此為基礎(chǔ)，對(duì)于0調(diào)用add_l得到1和2，就是如下形式。

這里并不是在Lisp中實(shí)現(xiàn)實(shí)際的數(shù)字技術(shù)，但是我們可以通過(guò)這種方式，來(lái)理解數(shù)據(jù)和過(guò)程在本質(zhì)上的統(tǒng)一。實(shí)際上，我們已經(jīng)能夠看出，哪怕是作為最基本元素的數(shù)字，本質(zhì)上也是可以理解為過(guò)程，和一般理解為純粹過(guò)程“加法”沒(méi)有本質(zhì)的不同。

2分層次的抽象

Lisp方言眾多，在不同的場(chǎng)景處理不同的問(wèn)題時(shí)，由Lisp構(gòu)造和提供一集對(duì)應(yīng)的功能，這些功能可以由原始Lisp通過(guò)各類(lèi)方式封裝實(shí)現(xiàn)，抑或是考慮對(duì)應(yīng)的功能對(duì)解釋器進(jìn)行適度的修改。最終，不必在最底層和一個(gè)個(gè)的基本元素打交道，而是在更高的層次上進(jìn)行使用。這是控制大型系統(tǒng)的重要方法——理解復(fù)雜事物的關(guān)鍵，就是避免不必要的觀察、計(jì)算和思考。

比如，在系統(tǒng)已經(jīng)有了整數(shù)計(jì)算功能的情況下，我們?nèi)粢蛊淠軌蛲瓿捎欣頂?shù)的計(jì)算。數(shù)學(xué)意義上有理數(shù)可以由分?jǐn)?shù)表示，是分子和分母構(gòu)成的一個(gè)整體，那么按照抽象的原則，對(duì)于具體的實(shí)現(xiàn)，我們可以通過(guò)構(gòu)造函數(shù)和選擇函數(shù)來(lái)完成。構(gòu)造函數(shù)可以通過(guò)整數(shù)的分子和分母構(gòu)造出有理數(shù)，選擇函數(shù)可以針對(duì)一個(gè)有理數(shù)獲取其分子或者分母。最簡(jiǎn)單的實(shí)現(xiàn)如下。

所有對(duì)于有理數(shù)的操作，如有理數(shù)的加減乘除，因?yàn)橹饕玫降氖菍?duì)于分子分母提取操作和生成新的有理數(shù)，所以可以直接用構(gòu)造函數(shù)和選擇函數(shù)進(jìn)行如下處理。

其他諸如減法、乘法以及除法，也可以按照類(lèi)似的方式實(shí)現(xiàn)。實(shí)際上，這是在底層的細(xì)節(jié)實(shí)現(xiàn)和上層的實(shí)際使用之間，構(gòu)造了一個(gè)水平的抽象屏障。這種數(shù)據(jù)抽象的方法是一種廣泛采用的控制復(fù)雜度的方法。因此，當(dāng)?shù)讓佑行薷?，可以只在底層進(jìn)行，而不會(huì)影響上層的使用。

抽象屏障的構(gòu)建，不只是在水平層面上，也可以在垂直角度上。例如，對(duì)于復(fù)數(shù)的構(gòu)建，就有兩種方式：直角坐標(biāo)式的和極坐標(biāo)式的。如此一來(lái)，當(dāng)我們有一個(gè)復(fù)數(shù)的實(shí)部和虛部，或者模和偏轉(zhuǎn)角時(shí)，實(shí)際上有兩種不同的復(fù)數(shù)實(shí)現(xiàn)方式。這兩種在處理不同的運(yùn)算時(shí)各有優(yōu)劣，在同一個(gè)運(yùn)算包中保留兩種實(shí)現(xiàn)，那就需要存在兩種構(gòu)造函數(shù)和選擇函數(shù)，這兩者在垂直方向上有一道屏障，而在水平層面上，兩者共同在復(fù)數(shù)屏障之下。

目前，我們構(gòu)建的有理數(shù)、復(fù)數(shù)，加上Lisp中原本就有的整數(shù)，對(duì)于他們的操作需要使用各自的運(yùn)算符，這與我們?cè)跀?shù)學(xué)上的習(xí)慣不同。一般來(lái)講，數(shù)學(xué)中使用+／等符號(hào)時(shí)，我們不會(huì)考慮這些符號(hào)作用的數(shù)字具體是什么類(lèi)型，而在我們目前的實(shí)現(xiàn)中，目前這是做不到的?？紤]到通用運(yùn)算符的效果，要達(dá)成這個(gè)目標(biāo)，就需要考慮數(shù)據(jù)“類(lèi)”的問(wèn)題。例如，給數(shù)據(jù)加上標(biāo)簽，另外，維護(hù)一張表，在表中根據(jù)不同的數(shù)據(jù)類(lèi)型以及運(yùn)算目標(biāo)，放置對(duì)應(yīng)的實(shí)際操作過(guò)程，在進(jìn)行通用的運(yùn)算時(shí)，先剝離數(shù)據(jù)類(lèi)型的標(biāo)簽，根據(jù)類(lèi)型和操作標(biāo)簽的提示，到表中找到過(guò)程處理對(duì)應(yīng)的數(shù)據(jù)——這是一種比較典型的數(shù)據(jù)導(dǎo)向編程，本質(zhì)上就是這些數(shù)據(jù)對(duì)象本身攜帶著如何操作他們的信息。除此之外，我們也可以在構(gòu)造過(guò)程中直接加上過(guò)程，將數(shù)據(jù)和對(duì)應(yīng)數(shù)據(jù)類(lèi)型的操作結(jié)合，在調(diào)用通用運(yùn)算符時(shí)提取使用，這是另一種組織系統(tǒng)的方式，叫做“消息傳遞”。

3狀態(tài)和環(huán)境

賦值是一項(xiàng)在程序語(yǔ)言中很常見(jiàn)的功能。不過(guò)上文對(duì)于Lisp的討論都沒(méi)有涉及這一塊，也就是沒(méi)有狀態(tài)（state）。這意味著在確定了一個(gè)對(duì)象的值后，在整個(gè)過(guò)程中它都不會(huì)改變。

Lisp具有賦值功能，一個(gè)對(duì)象在賦值前后其值可能不一樣，這時(shí)這個(gè)對(duì)象是有狀態(tài)的。在賦值前后，對(duì)于相同對(duì)象的同樣操作，可能會(huì)產(chǎn)生不同的結(jié)果，這一般叫做副作用。如果在沒(méi)有賦值的情況下，一個(gè)個(gè)的符號(hào)，其實(shí)就是對(duì)應(yīng)它實(shí)際值的名字，因此在引入賦值后，一個(gè)個(gè)的變量就是一個(gè)個(gè)保存值的位置索引，而存儲(chǔ)在那里的值是可以改變的。我們對(duì)它的引用，實(shí)際是通過(guò)它獲取保存在其中的實(shí)際值。在這里，最本質(zhì)的一點(diǎn)是我們引入了時(shí)間的概念。在符號(hào)無(wú)法直接由原本的值代換來(lái)解釋執(zhí)行的情況下，我們需要采用環(huán)境模型。

我們對(duì)于Lisp中過(guò)程的特殊地位已經(jīng)有了一定的了解。對(duì)于Lisp中的list，本質(zhì)是由一個(gè)個(gè)的cons不斷調(diào)用完成的。我們已經(jīng)知道cons本質(zhì)是一個(gè)過(guò)程，因此這里可以說(shuō)list也是一個(gè)過(guò)程。而我們所要說(shuō)的環(huán)境模型中的環(huán)境，其實(shí)就是一張表，或者一個(gè)函數(shù)。

環(huán)境是一個(gè)結(jié)構(gòu)化的對(duì)象，由一個(gè)個(gè)的框架構(gòu)成，包含一些約束，這些約束包括管理變量名字與對(duì)應(yīng)的值。每個(gè)框架包含一個(gè)指針，指向當(dāng)前這個(gè)框架的外部環(huán)境。環(huán)境對(duì)于程序過(guò)程是非常重要的，其確定了表達(dá)式求值的上下文。在沒(méi)有上下文的情況，程序語(yǔ)言的表達(dá)式?jīng)]有任何意義。

Lisp的基礎(chǔ)環(huán)境為我們提供各類(lèi)基本操作。之后，每一次的過(guò)程調(diào)用，都會(huì)臨日寸生產(chǎn)一個(gè)新的框架，框架中包含形式參數(shù)到被使用的實(shí)際參數(shù)的映射。一個(gè)變量對(duì)于某個(gè)特定環(huán)境的值，是在這一環(huán)境中包含著該變量的第一個(gè)框架里這個(gè)變量的約束值。過(guò)程構(gòu)建的實(shí)質(zhì)是lambda表達(dá)式相對(duì)于某個(gè)環(huán)境求值時(shí)，一個(gè)過(guò)程對(duì)象通過(guò)對(duì)原過(guò)程的代碼文本和求值時(shí)的環(huán)境指針進(jìn)行的重構(gòu)。

賦值會(huì)帶來(lái)狀態(tài)和副作用，但它依舊有用且功能強(qiáng)大。它可以讓我們將復(fù)雜的計(jì)算過(guò)程模塊化，從其中任意一個(gè)模塊看，其他模塊像隨著時(shí)間不斷變化，他們隱藏起自己隨時(shí)間變化的內(nèi)部狀態(tài)。這種策略將注意力集中在對(duì)象上，比較符合我們對(duì)于世界的認(rèn)知。

4新語(yǔ)言構(gòu)建

我們所要面對(duì)的問(wèn)題復(fù)雜度是不斷加深的。包含Lisp在內(nèi)的任何一門(mén)確定的程序語(yǔ)言是不可能完全滿(mǎn)足全部需要。為此，可以以上文提到的技術(shù)為基礎(chǔ)，構(gòu)建新的語(yǔ)言。具體而言，是通過(guò)構(gòu)造解釋器的方式實(shí)現(xiàn)這些語(yǔ)言。

對(duì)于某個(gè)程序語(yǔ)言的解釋器，本質(zhì)也是一個(gè)過(guò)程，在應(yīng)用這個(gè)語(yǔ)言的一個(gè)表達(dá)式時(shí)，能夠執(zhí)行求值表達(dá)式所要求的動(dòng)作。其中最基本的思想是：解釋器決定了一個(gè)程序設(shè)計(jì)語(yǔ)言中各個(gè)表達(dá)式的意義，但其本身也不過(guò)是另一個(gè)程序。

實(shí)際上，任何程序都可以看作某個(gè)語(yǔ)言的解釋器，如上面提到的對(duì)于有理數(shù)復(fù)數(shù)的算術(shù)規(guī)則，實(shí)際就可以看作在構(gòu)造函數(shù)和選擇函數(shù)過(guò)程上的新的語(yǔ)言規(guī)則的構(gòu)建。

實(shí)現(xiàn)一個(gè)Lisp的解釋器，使用的語(yǔ)言本身也是Lisp，看上去有些循環(huán)定義。不過(guò)實(shí)際上這種情況并不少見(jiàn)。對(duì)于沒(méi)有顯式的循環(huán)語(yǔ)法的Lisp，循環(huán)實(shí)現(xiàn)采用遞歸調(diào)用的方式。一個(gè)程序過(guò)程的定義在一定情況下可以包含對(duì)其自身的使用。使用與被解釋語(yǔ)言同樣的語(yǔ)言寫(xiě)出的解釋器被稱(chēng)為元循環(huán)。因?yàn)槠?，這里不再展開(kāi)。

5結(jié)束語(yǔ)

編程語(yǔ)言是在對(duì)現(xiàn)實(shí)世界理解的基礎(chǔ)上，對(duì)于世界的模擬，用以解決各類(lèi)問(wèn)題。從這個(gè)角度說(shuō)，各個(gè)語(yǔ)言在其本質(zhì)上有共通的地方。本文是以L(fǎng)isp語(yǔ)言為線(xiàn)索討論相關(guān)的執(zhí)行，這是一種萬(wàn)物皆函數(shù)的觀察理解世界的方式。另外，諸如面向?qū)ο?，抑或是其他的方式，則是從其他的角度，用類(lèi)似的底層工具，采取合適的模型，構(gòu)筑起適合解決對(duì)應(yīng)問(wèn)題的方式。