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

唐詩

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

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

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

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

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

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

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

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

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

cons體現(xiàn)了閉包（closure）的思想，可以說Lisp的數(shù)據(jù)在cons運算下是封閉的。從序?qū)Φ介]包運算，這體現(xiàn)了Lisp的特性，也展現(xiàn)了和數(shù)學(xué)的聯(lián)系——離散數(shù)學(xué)中的二元關(guān)系有序?qū)Γ约叭赫撝械娜簩τ诜忾]性的要求，都可以使我們找到其中的影子。

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

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

實際代換結(jié)果表明沒有問題。這被稱作邱奇變換。

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

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

（define zero （lambda （f）

（lambda （x）x）））

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

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

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

2分層次的抽象

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

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

所有對于有理數(shù)的操作，如有理數(shù)的加減乘除，因為主要用到的是對于分子分母提取操作和生成新的有理數(shù)，所以可以直接用構(gòu)造函數(shù)和選擇函數(shù)進(jìn)行如下處理。

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

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

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

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

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

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

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

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

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

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

4新語言構(gòu)建

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

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

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

實現(xiàn)一個Lisp的解釋器，使用的語言本身也是Lisp，看上去有些循環(huán)定義。不過實際上這種情況并不少見。對于沒有顯式的循環(huán)語法的Lisp，循環(huán)實現(xiàn)采用遞歸調(diào)用的方式。一個程序過程的定義在一定情況下可以包含對其自身的使用。使用與被解釋語言同樣的語言寫出的解釋器被稱為元循環(huán)。因為篇幅原因，這里不再展開。

5結(jié)束語

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