柯里化的前生今世（六）：詞法作用域和閉包

關於

本文是系列文章中的第六篇，發布在業餘程序員的個人修養這個專欄中：

柯里化的前生今世（一）：函數面面觀

柯里化的前生今世（二）：括弧神教

柯里化的前生今世（三）：語言和同像性

柯里化的前生今世（四）：編譯器與解釋器

柯里化的前生今世（五）：動態作用域

在上一篇中，我們介紹了動態作用域，並進行了相關名詞的解釋。

我們解釋了什麼是環境，什麼是幀，如何在一個環境中對表達式求值。

我們用一個內部結構表示了函數，實現了一個微型的支持動態作用域的解釋器。

這一篇，我們將再往前一步，實現詞法作用域（lexical scope）。

動態作用域 vs 詞法作用域

作用域（scope）的概念大家可能比較陌生，

但是閉包（closure）的概念在這幾年非常流行，幾乎已經沒有什麼主流語言不支持它了。

從實現角度，和函數一樣我們將用另外一種內部結構表示閉包，

; function in the dynamic-scope(struct function (param body)); closure in the lexical-scope(struct closure (param body env))

它封裝了某函數的形參列表param，函數體body，

還封裝了該函數被定義時的環境env。

當封裝的這個函數被調用時，我們會用實參擴展封裝下來的這個環境，

函數體在這個擴展後的環境中求值。

（註：在動態作用域中，我們用實參擴展的是函數被調用時的環境

對比如下，留意; here那一行

; function-call in the dynamic-scope(define (eval-function-call-list exp) (display "eval-function-call-list
") (let* ((fn (eval-exp (car exp))) (arg (eval-exp (cadr exp))) (body (function-body fn)) (param (function-param fn)) (frame (create-frame))) (extend-frame frame param arg) (let* ((env *env*) (value ())) (set! *env* (extend-env *env* frame)) ; here (set! value (eval-exp body)) (set! *env* env) value))); function-call in the lexical-scope(define (eval-function-call-list exp env) (display "eval-function-call-list
") (let* ((clos (eval-exp (car exp) env)) (arg (eval-exp (cadr exp) env)) (body (closure-body clos)) (lexical-env (closure-env clos)) (param (closure-param clos)) (frame (create-frame))) (extend-frame frame param arg) (let ((executing-env (extend-env lexical-env frame))) ; here (eval-exp body executing-env))))

以上我們看到，為了能讓表達式在指定的環境中求值，

我們就不能把環境看做全局變數了，我們的eval-exp要增加一個env參數。

放碼過來

完整的代碼如下，

我們增加了內部結構closure，

修改了eval-exp讓它可以接受給定的env作為參數，

同時導致了所有的相關函數都要增加env參數，包括handle-decision-tree。

值得注意的是eval-function-call-list，

它拿到閉包clos，會解開得到裡面包裝的詞法環境lexical-env，

然後用實參擴展它(extend-env lexical-env frame)，

最後函數體在這個擴展後的環境中求值(eval-exp body executing-env)。

#lang racket; tool(struct closure (param body env))(define (create-frame) (make-hash))(define (extend-frame frame key value) (hash-set! frame key value))(define (extend-env env frame) (cons frame env))(define (get-symbol-value env key) (let lookup-env ((env env)) (if (null? env) (error get-symbol-value "failed to find symbol") (let ((head-frame (car env))) (if (hash-has-key? head-frame key) (hash-ref head-frame key ()) (lookup-env (cdr env)))))))(define (handle-decision-tree tree exp env) (if (null? tree) (error handle-decision-tree "failed to make decision") (let* ((head (car tree)) (predicator (car head)) (decision (cadr head))) (if (predicator exp env) (if (not (list? decision)) (decision exp env) (handle-decision-tree decision exp env)) (handle-decision-tree (cdr tree) exp env))))); env(define *env* `(,(create-frame))); main(define (eval-exp exp env) (handle-decision-tree `((,is-symbol? ,eval-symbol) (,is-self-eval-exp? ,eval-self-eval-exp) (,is-list? ((,is-lambda? ,eval-lambda) (,is-function-call-list? ,eval-function-call-list)))) exp env))(define (is-symbol? exp env) (display "is-symbol?
") (symbol? exp))(define (eval-symbol exp env) (display "eval-symbol
") (get-symbol-value env exp))(define (is-self-eval-exp? exp env) (display "is-self-eval-exp?
") (number? exp))(define (eval-self-eval-exp exp env) (display "eval-self-eval-exp
") exp)(define (is-list? exp env) (display "is-list?
") (list? exp))(define (is-lambda? exp env) (display "is-lambda?
") (eq? (car exp) lambda))(define (eval-lambda exp env) (display "eval-lambda
") (let ((param (caadr exp)) (body (caddr exp))) (closure param body env)))(define (is-function-call-list? exp env) (display "is-function-call-list?
") #t)(define (eval-function-call-list exp env) (display "eval-function-call-list
") (let* ((clos (eval-exp (car exp) env)) (arg (eval-exp (cadr exp) env)) (body (closure-body clos)) (lexical-env (closure-env clos)) (param (closure-param clos)) (frame (create-frame))) (extend-frame frame param arg) (let ((executing-env (extend-env lexical-env frame))) (eval-exp body executing-env))))

測試

(display (eval-exp 1 *env*))(display "

")(display (eval-exp (lambda (x) x) *env*))(display "

")(display (eval-exp ((lambda (x) x) 1) *env*))(display "

")(display (eval-exp ((lambda (x) ((lambda (y) x) 2)) 1) *env*))(display "

")(display (eval-exp ((lambda (x) ((lambda (f) ((lambda (x) (f 3)) 2)) (lambda (z) x))) 1) *env*))

詞法作用域和閉包

詞法作用域

我們看到測試用例中，與動態作用域不同的結果。

; dynamic-scope(display (eval-exp ((lambda (x) ((lambda (f) ((lambda (x) (f 3)) 2)) (lambda (z) x))) 1))); result: 2; lexical-scope(display (eval-exp ((lambda (x) ((lambda (f) ((lambda (x) (f 3)) 2)) (lambda (z) x))) 1) *env*)); result: 1

當函數f被調用時(f 3)，形參z => 3，

但是函數體中的x，還是(lambda (z) x)函數定義時x的值x => 1。

而不是(f 3)函數調用時x的值x => 2。

這種性質就稱為詞法作用域。

閉包

結合以上的實現，我們看到，閉包只不過是一個數據結構，

它封裝了函數的形參，函數體，以及該函數被定義時的環境。

並沒有什麼特別神秘的地方。

但是閉包的引入，方便了我們去理解程序，

讓我們更容易確認函數體中自由變數的值，例如x。

也讓類庫更安全，類庫的表現和具體使用場景無關。

閉包與對象

對象

閉包與對象有很強的聯繫，很多面向對象編程思想的擁躉們，

經常以「對象」可以封裝狀態而引以為豪。

而事實上，無論是面向對象還是函數式，只不過表達思想的不同方式罷了，

詞法作用域和閉包一樣可以封裝「狀態」。

; let over lambda(define obj (let ((state 1)) (list (lambda () state) (lambda (v) (set! state v)))))(define obj-get-state (car obj))(define obj-set-state (cadr obj)); test(obj-get-state) ; 1(obj-set-state 2)(obj-get-state) ; 2

以上我們定義了一個對象obj，並得到了它的get和set函數，

我們用obj-set-state函數修改狀態，用obj-get-state得到內部封裝的狀態，

發現obj確實封裝了狀態，從面向對象的意義來看它就是一個「對象」了。

類

那麼面向對象中的類是什麼呢？

它其實是一個對象的工廠函數，每次new都創建一個具有獨立狀態的新對象。

下面我們用閉包模擬一下。

; lambda over let over lambda(define create-obj (lambda () (let ((state 1)) (list (lambda () state) (lambda (v) (set! state v))))))(define obj1 (create-obj))(define obj1-get-state (car obj1))(define obj1-set-state (cadr obj1))(define obj2 (create-obj))(define obj2-get-state (car obj2))(define obj2-set-state (cadr obj2)); test(obj1-get-state) ; 1(obj1-set-state 2)(obj1-get-state) ; 2(obj2-get-state) ; 1(obj2-set-state 3)(obj2-get-state) ; 3

我們發現，obj1和obj2獨立維護了自身的狀態，

而且它們是用同一個工廠create-obj創建出來的，

那麼這個工廠函數，就可以類比面向對象中的「類」了。

類的靜態變數

在面向對象語言中，某個class是可以有靜態變數的，

同一個class的這些變數值是相同的。

那麼，我們在create-obj這個工廠函數之上再加一層閉包let好了，

讓各個obj共享「類」的變數。

; let over lambda over let over lambda(define let-create-obj (let ((hidden 5)) (lambda () (let ((state 1)) (list (lambda () (+ hidden state)) (lambda (v) (set! state v)))))))(define obj1 (let-create-obj))(define obj1-get-state (car obj1))(define obj1-set-state (cadr obj1))(define obj2 (let-create-obj))(define obj2-get-state (car obj2))(define obj2-set-state (cadr obj2)); test(obj1-get-state) ; 6(obj1-set-state 2)(obj1-get-state) ; 7(obj2-get-state) ; 6(obj2-set-state 3)(obj2-get-state) ; 8

let over lambda

我們看到了閉包的表現力，同用一種模式模擬了面向對象語言中的很多概念，

「對象」，「類」，「類的靜態變數」，看起來都那麼的簡潔純凈，

當然，只要我們需要，我們還可以

「lambda over let over lambda over let over lambda」，等等。

因此，理解了閉包與對象的關係之後，我們就會放平自己的心態，

不會做某種語言的無腦粉，不同的思想也會儘可能多的為我們的目標服務，

當然，Lisp也不是萬能的，現在看來，它只是一個「玩具」罷了。

下文

本文實現了一個簡單的具有詞法作用域的Lisp方言，

為了加深理解，我們還類比了閉包與對象這兩個有趣的概念。

下文，我們要介紹高大上的continuation了，這又是什麼？

這不過是一個「坑」，僅此而已，敬請期待吧~

---

參考

On Lisp

Let Over Lambda

推薦閱讀：