導言

　　Scheme 是 LISP 的一個方言(dialect)。著名的 SICP 書就是以 Scheme 為教學語言（實際上 SICP 的作者就是 Scheme 的作者）。 雖然 Scheme 本身只是一個精簡化的適合教學的語言，可它首先提出的一些重要的思想，引領了新一代的LISP語言的出現。 實際上， LISP 語言發展的歷史是連續的，之所以我在這里人為的把 LISP 的發展史劃分為上一代和現代，是因為隨著 Scheme 首次引入并規范化了一些重要概念， LISP 語言出現了很多以前從來沒有大規模普及的新特性。以 Common LISP 為代表的 LISP 語言也因為這些新特性，而煥發了第二春。 人所共知的 Paul Graham 大叔，借著這一波 LISP 復興的浪潮，不光寫出了 On Lisp 這樣的好書；而且還用 Common LISP 寫出了一個在線電子商務平臺，在 1998 年的時候以近 5 千萬美元的價格賣給了 Yahoo! (憑借這筆買賣, Paul 大叔現在經營著 Y Combinator 天使投資，成為硅谷著名的天使)。前段時間賣給 Google 的 ITA，負擔著世界上大部分的航班資訊查詢，核心系統也是 Common LISP。 雖然不該把 Common LISP 的很多成就全部歸結到 Scheme, 但 Scheme 作為一個重要的歷史分水嶺，探究一下它的歷史來源還是很有趣的。

　　函數作為一級對象

　　我們都知道 LISP 是一個函數式的編程語言。在 LISP 中，函數是一種基本類型。 類比的看，C 家族的語言中，整數是一個基本的類型，所以，整數類型的變量既可以作為參數傳遞給一個函數，也可以作為返回值返回。比如，兩個整數求和這個函數，用 C 家族的語法就是：

　　int add(int a, int b);

　　因為在 LISP 里面，函數也成了基本類型。如果我們有一個 add 函數如下：

　　(define (add x y) (+ x y))

　　顯然，它在 LISP 里就和 C 里的 int 一樣，能夠作為參數傳遞給其他函數。

　　函數作為參數在 LISP 里非常普遍。 我們知道著名的 APPLY MAP 和 REDUCE 這三個“高階”函數（所謂高階的意義就是參數可以是函數）。其中 APPLY 的最基本形式可以帶兩個參數，第一個參數是函數，第二個參數是一個列表。APPLY 的效果就是把這個 列表 作為參數表，送給第一個參數所代表的函數求值。如果我們在 LISP 里面用 APPLY(add, (1, 2)) 結果就是3，即把 (1,2) 送給add 作為參數，結果自然是 3。 這是函數作為參數的例子，還有函數作為返回值的例子就不一一列舉了。

　　自由變量的幽靈

　　在 add 這個函數的定義中我們可以看到，它的結果和兩個輸入值 x, y 有關。 如果我們用 add(1,2) 調用  add 函數， 我們至少期望變量 x 會被賦值為 1， 變量 y 被賦值為 2。而結果 (+ x y) 則相應的為 3。 在這個簡單的例子中， 顯然，如果 x 和 y 有一個值不知道的話， (+ x y) 的計算就無法完成。我們暫且把這些對函數求值不可缺少的變量稱之為“必要變量”。顯然，這些必要變量的值是需要確定的，否則函數無法進行求值。在我們 add 函數的例子里，x, y 這兩個變量既是全部的必要變量，又是這個函數的參數，所以這個函數的結果就完全由輸入的 x, y 的值確定。可以想象，任何一個像 add這樣的所有的必要變量都是來自于輸入參數的函數，不論在什么地方
被調用，只要輸入的參數值一樣，輸出的結果必然一樣。

　　如果現實中所有的函數都有上面的性質的話，那就沒有這篇文章了。可惜的是我們很快發現有好多函數不符合上面我們說的“輸入的參數值一樣，輸出的結果必然一樣”這個結論。我們甚至無須用 LISP 里面的例子來說明這一點。用 C 語言的都知道，取系統當前時間的函數 time，以及取隨機數的函數 rand, 都是不需要輸入值（0個輸入參數）。因此任何時候這兩個函數被調用的時候，我們都可以認為輸入值一樣（為 void 或 null)。但我們在不同的時間調用 time 或者多次調用 rand，很顯然可以知道他們輸出的結果不可能每次一樣。

　　函數式編程里面有更多的類似的例子。這些例子說明了的確有些函數，對于同樣的輸入值，能夠得到不同的結果。這就很顯然的表明，這些函數的必要變量中，有些不是函數的輸入參數或者內部變量。我們把這些變量，叫做自由變量(free variable) [相反的那些被成為受限變量(bounded variable)]。這里的自由和受限，都是相對函數講的，以變量的取值是不是由函數本身決定來劃分的。

　　雖然自由和受限變量是函數式語言里面的概念，但在命令式語言中也有影子。比方說，C 語言中，函數中用到的全局變量就是自由變量；在 Java 程序中，匿名內部類里面的方法可以用到所在外部類中的成員變量或者所在方法里標記為 final 的那些變量。這些可以被內部類的方法訪問的，又不在內部類方法的參數表里面的變量都是自由變量。樂意翻看 GNU C Library 的好奇讀者會看到，GNU libc 中的 rand 函數就用到了一個 random_data 的變量作為自由變量 (glibc/stdlib/random.c)。 time 也是一樣，通過一個系統調用來設置時間，而這在原理上等價于用到一個叫做”當前時間”的自由變量 (glibc/stdlib/time/time.c)。

　　我們知道，在高級語言里面僅僅設計或者加入一個特性不難，難的是讓所有的特性能協調一致的工作。比方說 Java 語言假設一切均為為對象，容器類型也假設裝著對象，但是 int 類型卻不是對象，讓無數程序員為裝箱拆箱大汗淋漓。 回到 LISP， 當函數允許自由變量，函數有能夠被作為參數傳來傳去的時候，自由變量的幽靈就隨著函數作為參數傳遞而在程序各處游蕩。這就帶來了兩個問題，一個涉及到自由變量的值的確定機制，另一個涉及到這個機制的實現。

　　兩種作用域

　　為了說明自由變量的幽靈和作用域，我們還是從一個例子入手。假設我們要一個做加 n 的函數。為了體現出自由變量，我們把它寫成

　　(define (addn s) ( lambda x (+ x s)))

　　這個函數本身沒什么特別的：輸入一個 s, 輸出一個 對任意 x 返回 x＋s 的函數。注意到這個函數的“返回值”是一個函數。 基于這個 addn 函數，我們可以定義 ＋1 函數 add1 函數如下，

　　(define (add1 s) ((addn 1) s))

　　這個也很好解釋，如果輸入一個 s， (addn 1) 返回了一個加一函數，這個函數作用在 s 上，即可得到 s+1。一切看上去很順利，直到我們用一個Scheme 出現前的 LISP 解析器去計算 (add1 4)。 我們期望得到的值是 5， 而它給你的值可能是 8。怎么回事？

　　為了解釋這個 8 的來源，我們可以模擬一下一個基于棧的解釋器的工作過程。(add1 4) 調用首先將參數 s 賦值為 4 然后，展開 add1 函數，即將 s=4 壓棧，計算 (addn 1)。在調用 addn 時。s 又作為了 addn 的形式參數。因此，按照基于棧的解釋器的標準做法，我們在一個新的活動窗口中將 s =1 壓棧。addn 這個函數返回的是一個 “lambda x (+ x s)” 的函數，其中 s 是自由變量。 然而一旦 addn 返回，棧中的 s=1 就會被彈出。當我們把這個返回了的 lambda 表達式作用到 4 上求值時候，x 是這個 lambda 表達式傳入的形式參數，賦值為 4，棧里面的 s 的值 只有 s=4, 因此 (+ x s) 得到的是 8。

　　這顯然不是我們想要的。總結這個結果錯了的原因，是因為我們的解釋器沒有限定 lambda x (+ x s) 里面的自由變量 s 為 1。 而是在計算這個 lambda 表達式的時候才去查找這個自由變量的值。 自由變量的幽靈在函數上開了一個后門，而我們沒有在我們想要的地方堵上它，讓它在函數真正求值的時候泄漏出來。

　　我們不是第一個發現這個問題的人。 實際上， LISP 剛出來沒多久，就有人向 LISP 的發明人 John McCarthy 報告了這個 “BUG”。 John 也認為這是一個小 BUG，就把球踢給了當時寫 LISP 實現的 Steve Russell。此人我之前的文章介紹過，乃是一個水平很高的程序猿(Code Monkey)。他認識到，這個問題的來源，在于返回的 lambda 表達式失去了不應該失去的確定它自由變量值的環境信息，在求值的時候，這些環境信息應該跟著這個 lambda 表達式一起。這樣才能保證沒有這個 BUG。不過 lambda 表達式在 LISP 語言中已經成型了，所以他就引入了一個新叫做 FUNCTION 的修飾符。作為參數的 lambda 表達式或函數要改寫成 (FUNCTION lambda) 。 這樣，這個 lambda 表達式在被 eval 解析的時候就會被標記成 FUNARG，并且靜態綁定到解析時所在環境。而用 APPLY 對函數求值時，有 FUNARG 標簽的函數會在當時綁定的環境中求值，而不是在當前環境中求值。自由變量沒有到處亂跑，而是被限制在了當時綁定的環境里面。 Russell 的這個巧妙設計，成功關閉了自由變量在函數上開的口。這種加上了環境的函數就既能夠被四處傳遞，而不需要擔心自由變量的幽靈到處亂串。 這個東西，后來就被稱為“閉包”。Russell 用 FUNCTION，以用一種“裝飾”的方式，在 LISP 1.5 中第一次引入和實現和閉包。

　　在編程語言的術語中，上面的讓自由變量自由自在的在運行時賦值的機制，一般叫做動態作用域(dynamic scope)，而讓函數和確定自由變量值在解析時靜態綁定的機制，一般稱之為靜態作用域(static dynamic scope)。既然是靜態綁定的環境是解析的時候確定的，而解析器是逐行解析程序的，所以，靜態作用域的環境是完全由程序代碼的結構確定的。因此有時候靜態作用域又被等價的稱為“文法作用域”(lexical scope)。上面我們的例子里。我們的真正意圖是使用靜態作用域，卻遇到了一個使用動態作用域的 LISP 解析器，因此出現了 (add1 4) 等于 8 的錯誤。 但這個問題并不足以說明靜態作用域一定好。動態作用域的問題，關鍵在于違反了 Alpha 變換原則和封裝原則，不過不在此詳細展開了。