[PLT] 柯里化的前生今世（六）：词法作用域和闭包
关于
本文是系列文章中的第六篇，
在上一篇中，我们介绍了动态作用域，并进行了相关名词的解释。
我们解释了什么是环境，什么是帧，如何在一个环境中对表达式求值。
我们用一个内部结构表示了函数，实现了一个微型的支持动态作用域的解释器。
这一篇，我们将再往前一步，实现词法作用域（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了，这又是什么？
这不过是一个“坑”，仅此而已，敬请期待吧~
