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

关于

在上一篇中，我们介绍了动态作用域，并进行了相关名词的解释。我们解释了什么是环境，什么是帧，如何在一个环境中对表达式求值。我们用一个内部结构表示了函数，实现了一个微型的支持动态作用域的解释器。这一篇，我们将再往前一步，实现词法作用域（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\n") (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\n") (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?\n") (symbol? exp)) (define (eval-symbol exp env) (display "eval-symbol\n") (get-symbol-value env exp)) (define (is-self-eval-exp? exp env) (display "is-self-eval-exp?\n") (number? exp)) (define (eval-self-eval-exp exp env) (display "eval-self-eval-exp\n") exp) (define (is-list? exp env) (display "is-list?\n") (list? exp)) (define (is-lambda? exp env) (display "is-lambda?\n") (eq? (car exp) 'lambda)) (define (eval-lambda exp env) (display "eval-lambda\n") (let ((param (caadr exp)) (body (caddr exp))) (closure param body env))) (define (is-function-call-list? exp env) (display "is-function-call-list?\n") #t) (define (eval-function-call-list exp env) (display "eval-function-call-list\n") (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 "\n\n") (display (eval-exp '(lambda (x) x) *env*)) (display "\n\n") (display (eval-exp '((lambda (x) x) 1) *env*)) (display "\n\n") (display (eval-exp '((lambda (x) ((lambda (y) x) 2)) 1) *env*)) (display "\n\n") (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 LispLet Over Lambda