3.5 抽象语言的解释器
INFO
来源：3.5 Interpreters for Languages with Abstraction
对应：Disc 11、Disc 12、Disc 13、Disc 14、HW 07、HW 08、HW 09、Lab 11、Lab 12、Lab 13、Lab 14、Scheme、Scheme Challenge、Scheme Contest
计算器语言通过嵌套的调用表达式提供了组合的手段。但它无法定义新的运算符、给值命名，也无法表达通用的计算方法。计算器语言完全不支持抽象，因此不是一门特别强大或通用的编程语言。接下来，我们的任务是定义一门通用编程语言，它把名称绑定到值、并定义新操作，从而支持抽象。
上一节用 Python 源代码给出了一个完整的解释器；这一节不同，采用描述性的方式。配套项目会要求你构建一个功能完整的 Scheme 解释器，把这里介绍的想法实现出来。
3.5.1 结构
本节介绍 Scheme 解释器的一般结构。完成该项目，就能得到这里所描述解释器的一个可用实现。
Scheme 解释器和计算器语言解释器的结构有很多共通之处。解析器生成表达式，再由求值器解释。求值函数检查表达式的形式；遇到调用表达式时，它会调用一个函数，把过程施加到某些参数上。求值器之间的差异，大多与特殊形式、用户自定义函数，以及环境模型的实现有关。
解析。计算器语言解释器里的 scheme_reader 和 scheme_tokens 模块，几乎足以解析任何合法的 Scheme 表达式。但它还不支持引用（quotation）和点列表。完整的 Scheme 解释器应该能解析下面这个输入表达式。
>>> read_line("(car '(1 . 2))")
Pair('car', Pair(Pair('quote', Pair(Pair(1, 2), nil)), nil))实现 Scheme 解释器的第一个任务，是扩展 scheme_reader，让它能正确解析点列表和引用。
求值（Evaluation）。Scheme 一次只求值一个表达式。求值器的骨架实现定义在配套项目的 scheme.py 中。scheme_read 返回的每个表达式都会传给 scheme_eval 函数，由它在当前环境 env 中求值表达式 expr。
scheme_eval 函数对 Scheme 中不同形式的表达式求值：基本表达式、特殊形式和调用表达式。在 Scheme 中，检查组合的第一个元素，就能确定它属于哪种形式。每种特殊形式都有自己的求值规则。下面是 scheme_eval 的一个简化实现，为了便于讨论，我们删掉了一些错误检查和特殊形式的处理。完整的实现见配套项目。
>>> def scheme_eval(expr, env):
"""在环境 env 中求值 Scheme 表达式 expr。"""
if scheme_symbolp(expr):
return env[expr]
elif scheme_atomp(expr):
return expr
first, rest = expr.first, expr.second
if first == "lambda":
return do_lambda_form(rest, env)
elif first == "define":
do_define_form(rest, env)
return None
else:
procedure = scheme_eval(first, env)
args = rest.map(lambda operand: scheme_eval(operand, env))
return scheme_apply(procedure, args, env)过程应用（Procedure application）。上面的最后一种情况会触发第二个过程——过程应用，它由函数 scheme_apply 实现。Scheme 的过程应用，比计算器语言里的 calc_apply 函数通用得多。它能施加到两种参数上：PrimitiveProcedure 或 LambdaProcedure。PrimitiveProcedure 用 Python 实现，它有一个实例属性 fn，绑定到一个 Python 函数。此外，它可能需要、也可能不需要访问当前环境。每次应用该过程时，都会调用这个 Python 函数。
LambdaProcedure 用 Scheme 实现。它有一个 body 属性，是一个 Scheme 表达式，每次应用该过程时都会求值。要把过程施加到参数列表上，就要在一个新环境中求值它的主体表达式。为了构造这个环境，需要给环境添加一个新帧；在这一帧中，过程的形式参数绑定到各个参数。主体则用 scheme_eval 求值。
求值/应用递归。实现求值过程的两个函数 scheme_eval 和 scheme_apply 相互递归。每当遇到调用表达式，求值都需要应用。应用则借助求值，把操作数表达式求值成参数，也用来求值用户定义过程的主体。这种相互递归的过程，其一般结构在各种解释器中都很常见：求值通过应用来定义，应用又通过求值来定义。
这个递归循环终止于语言的基本元素。求值有一个基本情况，就是求值一个基本表达式；有些特殊形式也构成不涉及递归调用的基本情况。函数应用也有一个基本情况，就是把过程施加到一个基本过程上。处理表达式形式的求值函数，与处理函数及其参数的应用函数之间，这种相互递归的结构正是求值过程的本质。
3.5.2 环境
讲完 Scheme 解释器的结构，接下来我们实现构成环境的 Frame 类。每个 Frame 实例代表一个环境，其中符号绑定到值。一个帧有一个存放绑定的字典（bindings），还有一个父帧（parent）；对全局帧来说，父帧是 None。
绑定不能直接访问，而要经过 Frame 的两个方法：lookup 和 define。前者实现第一章描述的环境模型的查找过程：把符号与当前帧的绑定逐一比对，找到就返回它绑定到的值，没找到就继续到父帧中查找。define 方法则总是把符号绑定到当前帧中的一个值。
lookup 的实现和 define 的使用留作练习。为了说明它们的用法，请看下面这个 Scheme 程序示例：
第一个输入表达式是一个 define 特殊形式，由 Python 函数 do_define_form 求值。定义一个函数要经过几步：
- 检查表达式的格式，确保它是一个格式良好的 Scheme 列表，
define关键字后面至少有两个元素。 - 分析第一个元素（这里是一个
Pair），找出函数名factorial和形式参数列表(n)。 - 用给定的形式参数、主体和父环境创建
LambdaProcedure。 - 在当前环境的第一个帧中，把符号
factorial绑定到这个函数。这个例子里，环境只包含全局帧。
第二个输入是调用表达式。传给 scheme_apply 的 procedure，就是刚刚创建并绑定到符号 factorial 的那个 LambdaProcedure；传入的 args 是一个单元素 Scheme 列表 (5)。为了应用该过程，会新建一个帧来扩展全局帧（也就是 factorial 过程的父环境）。在这一帧中，符号 n 绑定到值 5。然后在那个环境里求值 factorial 的主体，并返回它的值。
3.5.3 数据即程序
思考一个求值 Scheme 表达式的程序时，打个比方也许有帮助。关于程序的含义，有一种操作性的观点：程序是对一台抽象机器的描述。例如，再来看这个计算阶乘的过程：
我们也可以用条件表达式，在 Python 中写出一个等价的程序。
>>> def factorial(n):
return 1 if n == 1 else n * factorial(n - 1)我们可以把这个程序看成对一台机器的描述：它由做减法、做乘法和检验相等性的部件组成，还有一个双位开关和另一台阶乘机。（阶乘机是无限的，因为它里面还包含着一台阶乘机。）下图是阶乘机的流程图，展示了各部件如何连接在一起。
同样，我们也可以把 Scheme 解释器看成一台非常特殊的机器，它把对机器的描述作为输入。拿到这个输入后，解释器会自行配置，去模拟所描述的那台机器。例如，把阶乘的定义喂给求值器，它就能计算阶乘。
从这个角度看，我们的 Scheme 解释器是一台通用机器。别的机器只要用 Scheme 程序描述出来，它就能模仿。它是编程语言所操作的数据对象与编程语言本身之间的一座桥梁。设想用户在我们运行中的 Scheme 解释器里输入一个 Scheme 表达式。在用户看来，像 (+ 2 2) 这样的输入表达式是编程语言中的一个表达式，解释器应该求值它。但在 Scheme 解释器看来，这个表达式不过是一串词，要按一套明确定义的规则来处理。
用户的程序就是解释器的数据，这未必会引起混淆。事实上，有时忽略这种区别、让用户能把数据对象显式地当作表达式来求值，反而更方便。在 Scheme 中，只要用到 run 过程，就是在使用这个功能。Python 里也有类似的函数：eval 函数会求值 Python 表达式，exec 函数会执行 Python 语句。因此，
>>> eval('2+2')
4和
>>> 2+2
4两者返回相同的结果。在动态编程语言里，求值在执行过程中构造出来的表达式，是一种常见而强大的特性。很少有语言像 Scheme 这样普遍地这样做，但在程序执行过程中构造并求值表达式的能力，对任何程序员来说都可能是一件很有用的工具。