动态作用域、词法作用域与表达式求值的环境模型
光剑系列的第四作！前三篇：
第一篇：Let's build our mathematics by using lambda calculus && church encoding!
第二篇：惰性求值、无穷流与发生的魔法
第三篇：协程、生成器与 call/cc 的控制流
引子
在惰性求值、无穷流与发生的魔法中，我们使用无参 lambda 构建了一个 thunk。
想必有读者读完之后苦思冥想，最后发现“不对呀！主播，你为什么要用一个 lambda 呢？这里用 quote 不是也可以起到‘冻结计算’的作用？最后用一次 eval 将被冻结的原始表达式求值就可以得到真实值了。”
比如说，我们使用过的这个示例：
(define x (lambda () (+ 1 2)))
(x)
3就可以转化为下面的形式：
(define x '(+ 1 2))
(eval x)
3如果你这么想了，恭喜你！你自己发现了一条通向本文核心内容，函数抽象的动态作用域与词法作用域区别的道路。
接下来，请容我解释动态作用域、词法作用域，它们的区别以及 thunk 两种构建方法与它们的联系。在本文中，我们还将手动在 scheme 中构建一套动态作用域的函数抽象/应用体系。最终成果如下：
;; 假设使用支持 SRFI-39 的实现（chez 等很多支持）
(define x (make-parameter 10))
(define (f y) (+ (x) y))
(f 5) ; => 15
(parameterize ([x 100])
(f 5)) ; => 105 ; x 按调用链动态解析分道扬镳——当自由变量出现
上面的两种方法看似都能实现对计算的“冻结”，但是它们的作用真的完全一样吗？
答案是否定的。原因在于，lambda 构建的 thunk 保存了 thunk 定义时的“环境”，而 quote 构建的 thunk 保存的仅仅是代码的“文本”（符号表达式）。当表达式中含有自由变量时，区别就显现出来了。
一个很简单的例子：
> (define x 3)
> (define y 5)
> (define thunk1 (lambda () (+ x y))) ; 期望的值是 3+5=8
> (define thunk2 '(+ x y)) ; 同上
> (thunk1)
8
> (eval thunk2) ; 对两个 thunk 求值，得到预期的 8
8
> (let ([x 100]) (thunk1)) ; 用一个 let 包裹，然后求值。依然得到 8
8
> (let ([x 100]) (eval thunk2)) ; 在某些实现中，eval 会在当前环境中求值。但是 R6RS 标准要求 eval 给定环境参数，并且没有给出获取当前环境的方法
105我们惊讶地发现，第二种方法构建的 thunk，求出来的值发生了变化！在没有外部的 let 时，它得到的值就是我们想要的 8，但是包裹了一层 let 之后，它的值竟然神秘的变成了 105！
表达式求值的环境模型
上面的现象，其实源于解释器对于表达式求值的策略。
诸位对于表达式求值的实现有什么印象呢？
可能有不少人想到的都是代入（β 规约）吧？对于一个函数 (define (f x) (+ x 2))，调用 (f 3) 的时候就是将 x=3 代入，得到 (+ 3 2)，然后求值得到 5.
这样的模型看上去确实很简单，但是却隐藏了很大的复杂性。比如说：
(define (id x) x)
(define (double x) (+ x x))
(define (square x) (* x x))
(id (double (square 3)))最后那行函数应用，嵌套的三个函数的参数都叫做“x”，然而却是三个完全不同的东西。贸然将 x 代换成 3 可能会误伤内层函数的无关变量。这里我们需要应用 α 变换，为内层的函数参数生成新的、独一无二的变量名。比如说 x0/x1/x2……这是一个代码混淆器。
而且，代换模型在遇到可变状态和副作用时会产生根本性的困难。
为了避免这些麻烦，解释器实际采用的求值策略是另一种：环境模型。
“环境”是一个从名字到值的映射。解释器在求值过程中会维护一个当前环境，遇到任何符号都会去环境中查找它对应的值。
变量的声明/绑定，就是向环境中添加新的键值对（名字-值的对应）。函数的应用，也自然地转化成了“将实际参数作为值，绑定到形式参数上”的变量绑定。
环境不是一个单一的映射，也可以是多个映射（帧，frame）串起来构成的链表。这样的结构非常利于处理作用域嵌套：每一个子作用域都是一个新的帧，链接在父作用域环境前面。查找变量时从最前面的帧向后一帧帧查找，第一次找到就返回。这样就能轻松实现作用域遮蔽的特性，在全局作用域和局部作用域使用同样的变量名。退出作用域之后，就删除它对应的帧。这样就能够简单地清除它对于父作用域带来的影响。
这就是环境模型。它简单优雅地解决了作用域嵌套时的遮蔽和变量销毁，以及不同位置的无关同名变量带来的问题。大部分的解释器使用的都是环境模型，而不是原始的代入。
动态作用域与词法作用域
在了解了环境模型之后，我们终于可以深入这个有趣的话题了！
定义一个函数时，我们可能会用到不在函数参数列表中的变量：
int x = 100;
int f() {
return x * 2;
}这样的变量就是所谓的“自由变量”。动态作用域与词法作用域，就是处理这些变量的两种不同策略。
词法作用域
函数中自由变量的意义取决于函数定义时的上下文，即函数在代码文本中的位置。
比如说，上面的那个函数，无论在哪里调用，它内部引用的 x 都是定义时环境上下文中的 x（第一行定义的 x）。不会因为调用时的环境中有其他叫做 x 的变量而发生变化。
int main() {
int x = 3;
cout << f(); // 200
}要实现这个，函数不能仅仅是参数列表和函数体代码。它还需要捕获定义时的环境，然后把它和参数以及函数体一起打包成一个闭包（closure）。
动态作用域
与上面相反，动态作用域的函数中的自由变量，其含义取决于调用时的环境。
（假设 C++ 是动态作用域的）
int main() {
int x = 3;
cout << f(); // 6
}int main() {
cout << f(); // CE
}动态作用域的函数被调用时，会去调用者的环境链中查找自由变量的含义，而不是从自己被定义时的环境中查找。找不到就报错。
动态作用域的函数，实现可以远比词法作用域简单。你只需要保存它的代码（函数体），然后调用时放到当前环境中求值就行了。不用维护闭包。
动态作用域的缺陷
动态作用域有很大的问题。调用者手里的变量绑定，可能会莫名其妙地改变函数自由变量的值，从而导致函数产生奇怪的行为。（就像我们开头的例子中 quote 版 thunk 求出来的值发生了变化）
这是非常不好的，因为它破坏了过程抽象。设计良好的封装/抽象，使用者不应该知道或者关心内部的细节。而动态作用域却要求你小心翼翼地处理函数中的自由变量——我凭什么要知道函数里用了哪些自由变量、都叫什么、取什么值才能得到正确结果？
所以，几乎所有现代语言（比如 C++、Java、Python、JavaScript……，以及 scheme 和 common lisp 等现代 lisp 方言）都采用了词法作用域。
但是在早期，许多语言是动态作用域的（比如早期的 lisp）。这并不是因为它们的作者“选择”了动态作用域，而是因为动态作用域实在是太简单、易于实现和容易想到了。缺乏经验的语言设计者，第一次想到的就是它，他们自然把自己的语言实现为动态作用域的。
在现代，elisp（Emacs lisp）由于领域特定的便利性，依然保留着动态作用域的特性。不过也可以手动启用词法作用域。common lisp 也保留着手动开启动态作用域的方式。
两种 thunk 实现到不同作用域策略的对应
用 lambda 实现的 thunk，本质上是 scheme 中的一个函数。自然也就继承了 scheme 中函数的共性：词法作用域、闭包。它是词法作用域的。
而用 quote 实现的 thunk，就是简单地保存了函数的“代码”，并且把它放在调用环境中求值。这是典型的动态作用域特征。
所以，在开头的那个例子中，你会看见 lambda 版 thunk 没有被外面的 let 影响，而 quote 版则做出了奇怪的行为。
一个有趣的旁注：C++ 宏中的“动态”魅影
谈到动态作用域这种“通过外部环境影响内部行为”的特性，一些熟悉 C++ 的读者可能会会心一笑，想起那个著名（甚至可以说是臭名昭著）的技巧：
#define private public
#include <some_library>这里的 #define 就像一个动态绑定，它在 #include 这个“调用”发生时，强行改变了库内部代码的含义，让原本私有的成员变量变得公开可见。这与我们在 Lisp 中用 let 动态地为一个函数“注入”自由变量值的行为，在哲学思想上何其相似！它们都展现了强大的灵活性，也都带来了“跨越边界的幽灵般行为”（Spooky Action at a Distance）的风险，使得代码的局部推理变得困难。
然而，我们必须清晰地认识到，两者貌合神离。C++ 宏的魔法发生在编译前的“预处理期”，它是一种静态的文本替换游戏。而我们所讨论的动态作用域，是语言语义的核心部分，它发生在程序真正执行的“运行期”，根据函数的调用链来动态地解析变量。
尽管机制不同，这个 C++ 的例子却生动地提醒我们：任何允许上下文影响代码块内部语义的机制，都是一柄需要被审慎使用的强大“光剑”。
手动构建动态作用域函数
下面是本文的高潮环节！我们已经理解了动态作用域的原理——函数的意义由其“调用时”的环境决定。现在，我们将利用 Scheme 的元编程能力，亲手构建一套动态作用域的函数体系。
我们的核心思路很简单：
- “冻结”代码：一个动态作用域的函数，本质上就是它未经求值的“代码”本身。我们需要将函数的参数列表和函数体保存下来。
quote是实现这一点的完美工具。 - “在调用时求值”：当函数被调用时，我们再用
eval在当前的（也就是调用者的）环境中，将“解冻”后的代码求值。
仅仅 eval 函数体是不够的，我们还需要处理参数绑定。调用者传入的实际参数，必须先绑定到函数定义时的形式参数上。我们该如何在一个已经存在的环境中“注入”这些新的绑定呢？
答案是巧妙地利用 let。我们可以在调用时动态地生成一个 let 表达式，用它来包裹原始的函数体。这个 let 会为形式参数创建绑定，而函数体中的自由变量，则会自然地在 let 外层的环境中——也就是调用者的环境中——被查找。这完美地复刻了动态作用域的行为！
好，设计思路清晰了，我们开始动手实现。
首先，我们需要一个辅助函数 make-let，它的作用是接收一个绑定列表（比如 ((x 1) (y 2))）和一个函数体列表，然后生成一个完整的 let S-表达式。得益于 Scheme 的同象性（代码即数据），这件事做起来就像拼接列表一样简单：
; make-let: 根据绑定和函数体，生成一个 let 表达式
(define (make-let bindings body)
(append `(let ,bindings) body))一个 let 表达式的结构是 (let ((var1 val1) ...) body1 body2 ...)。我们的 make-let 精确地构造了这个结构。
接下来是核心部分 dynamic-procedure。它将接收一个参数列表（符号列表）和函数体（S-表达式列表），然后返回一个真正可被调用的 Scheme 函数（一个闭包）。这个返回的函数才是我们的“动态作用域函数”。
当这个函数被调用时，它会执行我们之前设计的魔法：
- 用
map和list将形式参数和接收到的实际参数配对，形成let所需的绑定。 - 调用
make-let生成包裹着函数体的let表达式。 - 用
eval在当前环境中执行这个表达式。
(define (dynamic-procedure params body)
; 返回一个普通的 lambda，它 captures 了 params 和 body
(lambda actual-args ; 使用不定参数来接收所有传入的实参
(let ([bindings (map list params actual-args)])
(eval
(make-let bindings body)
; (environment) ; 在某些 Scheme 实现中需要指定求值环境，不过 chez scheme 中缺省参数默认使用当前环境，符合我们的要求
))))大功告成！为了让定义函数更方便，我们最后再来一个语法糖宏 define-dynamic，让它的写法和普通的 define 几乎一模一样。
(define-syntax define-dynamic
(syntax-rules ()
((_ (name param ...) body ...)
(define name (dynamic-procedure '(param ...) '(body ...))))))现在，我们可以像这样定义和使用我们的动态作用域函数了：
(define x 10)
; 定义一个动态函数 f，它有一个参数 y 和一个自由变量 x
(define-dynamic (f y)
(+ x y))
(f 5) ; => 15, 因为这里的 x 是全局的 10
(let ([x 100])
(f 5)) ; 你觉得这里的求值结果会是什么呢？似乎大功告成了？
？？？？？
为什么最后那行调用，得到的值仍然是 15？！
我们刚刚的实现，存在致命的缺陷。这使得它无法实现动态作用域。
首先是第一个错误：我们的 dynamic-procedure 返回了一个 lambda。它含有一个闭包。这个闭包捕获了它被定义时的环境，eval 求值时使用的也是这个环境。
我们不能返回任何闭包。很可惜 scheme 的几乎所有东西都是函数，也就是闭包。
所幸我们还有宏。
(define (make-let bindings body)
(append `(let ,bindings) body))
(define (dynamic-procedure params body)
(cons params body))
(define-syntax funcall
(syntax-rules ()
((_ f x ...)
(eval
(make-let
(map list (car f) (list x ...))
(cdr f))))))
(define-syntax define-dynamic
(syntax-rules ()
((_ (name param ...) body ...)
(define name (dynamic-procedure '(param ...) '(body ...))))))呃，依然不行。
这份代码中还有第二个错误：eval。
eval 要求两个参数：表达式和环境。单参 eval 是 chez 的扩展，默认在 interaction-environment 返回的顶层环境中求值。而 let 创建的绑定并不在顶层，刚刚的 (let ([x 100]) (f 5)) 依然会得到 15.
我们需要一些手法来捕获当前环境。
在某些实现中，我们有 current-environment 之类的手法来捕获当前环境。所以，只需要将 funcall 改成下面这样：
(define-syntax funcall
(syntax-rules ()
((_ f x ...)
(eval
(make-let
(map list (car f) (list x ...))
(cdr f))
(current-environment))))) ; 或换成实现提供的具体方法这样就行了。
然而，RnRS 标准（和 chez scheme）并没有提供这种方便的函数。
这就让 eval 完全废掉了（不能用在这里）。失去了 eval，我们不再能通过运行时代码生成来解决问题（因为任何构建出来的符号列表最终都需要通过 eval 转换为代码执行）。
我们必须使用宏。放弃代码 -> 数据 -> 代码的转换（因为最后一步依赖于 eval，而它无法提供我们想要的效果），直接用宏对代码进行操作。
大概的思路是让 define-dynamic 作为一个宏，接受函数名、参数列表和函数体，展开的结果是一个宏定义，将函数名定义为一个宏，匹配实际参数，并且展开成 let 表达式套函数体。不过这个技术有点过于复杂，留作读者练习 :P
上面的宏方案相当难以实现，还有另外的一些问题：宏不是普通的函数，不具备一等公民特性，不能作为值传递。宏如果进行了递归会无限展开。
我们有更好的方法，不过需要依赖于已有的库（SRFI）
SRFI 39 提供了参数对象，类似于 common lisp 或者 elisp 提供的动态作用域对象。可以让我们演示动态作用域：
;; 假设使用支持 SRFI-39 的实现（chez 等很多支持）
(define x (make-parameter 10))
(define (f y) (+ (x) y))
(f 5) ; => 15
(parameterize ([x 100])
(f 5)) ; => 105 ; x 按调用链动态解析后记
累了……本来都以为写完了，得到了一个高潮和尾声。结果没想到是一个反高潮，引出了无穷多的问题，到现在还没有办法全部解决……
实现动态作用域的特性可能确实需要手写解释器。不依赖于库或者手写解释器的方法就留给读者探索吧。一定是非常好的练习。
为你们的练习提供一些工具：
syntax->datum 函数：将一个语法对象剥离上下文转化为 S 表达式（符号列表）
datum->syntax 函数：接受两个参数 template 和 data（template 是第一个参数，data 是第二个参数），第一个参数是一个语法实体，第二个参数是一个符号列表。返回一个语法实体，内容是 data，上下文与 template 相同。
小示例：
(define-syntax print
(lambda (stx)
(syntax-case stx ()
((_ a)
(begin (display (syntax->datum stx))
(newline)
(datum->syntax #'stx 'b))))))
> (print a)
(print a)
Exception: variable b is not bound
Type (debug) to enter the debugger.
> (define b 5)
> (print b)
(print b)
5这两个函数是 syntax-case 打破卫生性，捕获调用者环境中的标识符。读者们，你们应该都能察觉到这和实现动态作用域的相关性。