從Lisp語言了解編程語言的解釋與執行

唐詩

關鍵詞：Lisp函數；過程；程序執行

1過程與數據抽象

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

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

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

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

（ car x）；結果為1

（ cdr x）；結果為2

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

cons體現了閉包（closure）的思想，可以說Lisp的數據在cons運算下是封閉的。從序對到閉包運算，這體現了Lisp的特性，也展現了和數學的聯系——離散數學中的二元關系有序對，以及群論中的群對于封閉性的要求，都可以使我們找到其中的影子。

cons的實現，要求我們將過程作為第一級元素，能作為求值表達式的返回。下面是一些關于程序語言第一級元素的特點：（1）可被命名為變量；（2）可作為參數傳遞給程序；（3）可以作為程序的返回值；（4）可以被結合為數據結構。

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

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

在面向對象語言中，我們習慣說，對于某個程序的調用，返回某種數據。例如，數字、字符串或者我們通過構造形成的某個數據對象，但是更進一步，我們去問一個數據是什么時，結果可能會語焉不詳。當我們說數字1時，我們知道這并不是指我們打印文本中的“1”這個符號，它應該是一種象征，代表著某種高度的抽象，可以是一個雞蛋，一個蘋果，可以讓打印文本中顯示出1這個符號，也可以是別的什么東西。我們也知道，對它的操作得到的結果意味著什么，例如，1+1=2。而2也是某種抽象。

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

（define zero （lambda （f）

（lambda （x）x）））

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

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

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

2分層次的抽象

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

比如，在系統已經有了整數計算功能的情況下，我們若要使其能夠完成有理數的計算。數學意義上有理數可以由分數表示，是分子和分母構成的一個整體，那么按照抽象的原則，對于具體的實現，我們可以通過構造函數和選擇函數來完成。構造函數可以通過整數的分子和分母構造出有理數，選擇函數可以針對一個有理數獲取其分子或者分母。最簡單的實現如下。

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

其他諸如減法、乘法以及除法，也可以按照類似的方式實現。實際上，這是在底層的細節實現和上層的實際使用之間，構造了一個水平的抽象屏障。這種數據抽象的方法是一種廣泛采用的控制復雜度的方法。因此，當底層有修改，可以只在底層進行，而不會影響上層的使用。

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

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

3狀態和環境

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

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

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

環境是一個結構化的對象，由一個個的框架構成，包含一些約束，這些約束包括管理變量名字與對應的值。每個框架包含一個指針，指向當前這個框架的外部環境。環境對于程序過程是非常重要的，其確定了表達式求值的上下文。在沒有上下文的情況，程序語言的表達式沒有任何意義。

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

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

4新語言構建

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

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

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

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

5結束語

編程語言是在對現實世界理解的基礎上，對于世界的模擬，用以解決各類問題。從這個角度說，各個語言在其本質上有共通的地方。本文是以Lisp語言為線索討論相關的執行，這是一種萬物皆函數的觀察理解世界的方式。另外，諸如面向對象，抑或是其他的方式，則是從其他的角度，用類似的底層工具，采取合適的模型，構筑起適合解決對應問題的方式。