> For the complete documentation index, see [llms.txt](https://zlt-shadow.gitbook.io/sicp-in-python-cn/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://zlt-shadow.gitbook.io/sicp-in-python-cn/di-3-zhang-jie-shi-ji-suan-ji-cheng-xu/3.5-chou-xiang-yu-yan-jie-shi-qi.md).

# 3.5 抽象语言解释器

计算器语言通过嵌套调用表达式提供了一种组合方法。 但是，无法定义新的操作符、为值命名或表示通用的计算方法。 Calculator不支持任何形式的抽象。 因此，它不是一种特别强大或通用的编程语言。 现在，我们开始定义一种通用编程语言，这种语言通过将名称绑定到值并定义新的操作来支持抽象。 

上一节以Python源代码的形式提供了完整的解释器，与上一节不同，本节采用了一种描述性的方法。 配套项目要求您通过构建一个功能齐全的Scheme解释器来实现这里提出的想法。

### 3.5.1 结构

本节描述Scheme解释器的一般结构。 完成该项目将生成这里描述的解释器的工作实现。 

Scheme的解释器可以与计算器解释器共享大部分相同的结构。 解析器产生由计算器解释的表达式。求值函数检查表达式的形式，对于调用表达式，它调用函数将过程应用于某些参数。 计算器的大部分差异与特殊形式、用户定义函数和实现计算的环境模型有关。 

**解析。** 计算器解释器中的[scheme\_reader](http://composingprograms.com/examples/scalc/scheme_reader.py.html)和[scheme\_tokens](http://composingprograms.com/examples/scalc/scheme_tokens.py.html)模块几乎足以解析任何有效的Scheme表达式。 但是，它还不支持引号或虚线列表。 完整的Scheme解释器应该能够解析下面的输入表达式。

```
>>> read_line("(car '(1 . 2))")
Pair('car', Pair(Pair('quote', Pair(Pair(1, 2), nil)), nil))
```

实现Scheme解释器的第一个任务是扩展scheme\_reader以正确解析虚线列表和引号。 

**计算。** Scheme一次只计算一个表达式。 计算器的框架实现在配套项目的scheme.py中定义。 从scheme\_read返回的每个表达式都被传递给scheme\_eval函数，该函数计算当前环境env中的表达式expr。

scheme\_eval函数计算Scheme中不同形式的表达式：原语、特殊形式和调用表达式。Scheme中的组合形式可以通过检查其第一个元素来确定。 每种特殊形式都有自己的评价规则。 scheme\_eval的简化实现如下所示。为了集中讨论，我们删除了一些错误检查和特殊的表单处理。一个完整的实现将出现在配套项目中。

```
>>> def scheme_eval(expr, env):
        """Evaluate Scheme expression expr in environment env."""
        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中的程序应用过程比Calculator中的calc\_apply函数要普遍得多。它应用两种类型的参数：原始过程或LambdaProcedure。 原语过程是用Python实现的；它有一个绑定到Python函数的实例属性fn。 此外，它可能需要也可能不需要访问当前环境。 每当应用这个过程时，就会调用这个Python函数。 

在Scheme中实现了一个lambdaprocedures。 它具有一个主体属性，该属性是一个方案表达式，在应用该过程时进行计算。 若要将过程应用于参数列表，则要在新环境中计算体表达式。要构造这个环境，需要向环境添加一个新的框架，在这个框架中，过程的形式参数被绑定到参数。 主体使用scheme\_eval进行计算。 

**Eval /应用递归。** 实现计算过程的函数scheme\_eval和scheme\_apply是相互递归的。 每当遇到调用表达式时，都需要应用程序求值。 应用程序使用求值将操作数表达式求值为参数，以及求值用户定义过程体。这种相互递归过程的一般结构在译员中非常普遍地出现：评价是根据应用来定义的，应用是根据评价来定义的。 

这个递归循环以语言原语结束。 求值有一个基本情况，它对一个原始表达式求值。 一些特殊形式也构成了不需要递归调用的基本情况。函数应用程序有一个应用基本过程的基本用例。 这种在处理表达式形式的eval函数和处理函数及其参数的apply函数之间的相互递归结构构成了评估过程的本质。

### 3.5.2 环境

现在我们已经描述了Scheme解释器的结构，接下来我们来实现形成环境的Frame类。 每个Frame实例代表一个环境，在这个环境中符号被绑定到值。 一个框架有一个绑定字典，还有一个父框架，这个父框架对于全局框架来说是None。 

绑定不是直接访问的，而是通过两个框架方法：lookup和define。 第一部分实现了第一章中描述的环境计算模型的查找过程。 符号与当前框架的绑定相匹配。 如果找到它，则返回它所绑定的值。 如果没有找到，查找将继续到父框架。 另一方面，define方法总是将符号绑定到当前框架中的值。 

lookup的实现和define的使用留作练习。 为了说明它们的使用，考虑下面的示例方案程序：

```
(define (factorial n)
  (if (= n 0) 1 (* n (factorial (- n 1)))))
(factorial 5)
120
```

第一个输入表达式是一个define特殊形式，由do\_define\_form Python函数求值。定义函数有以下几个步骤：

1. 检查表达式的格式，以确保它是一个格式良好的模式列表，关键字define后面至少有两个元素。 
2. 分析第一个元素(在本例中是一对元素)，以查找函数名factorial和形式参数列表(n)。
3. 使用提供的形式参数、体和父环境创建一个LambdaProcedure。 
4. 在当前环境的第一框架中将符号factorial绑定到这个函数。 在这种情况下，环境仅由全局框架组成。

第二个输入是一个调用表达式。传递给scheme\_apply的过程是刚刚创建并绑定到符号factorial的LambdaProcedure。传递的args是一个单元素的方案列表(5)。为了应用这个过程，将创建一个扩展了全局框架(factorial过程的父环境)的新框架。在这一框架中，符号n与值5绑定。然后，在该环境中计算factorial的函数体，并返回它的值。

### 3.5.3 数据作为程序

在考虑计算Scheme表达式的程序时，一个类比可能会有所帮助。对程序意义的一种操作观点是，程序是对抽象机器的描述。例如，再次考虑计算阶乘的过程：

```
(define (factorial n)
  (if (= n 0) 1 (* n (factorial (- n 1)))))
```

我们也可以在Python中使用条件表达式表示一个等价的程序：

```
>>> def factorial(n):
        return 1 if n == 1 else n * factorial(n - 1)
```

我们可以把这个程序看作是一个机器的描述，它包含了一个减量、乘法和相等检验的部件，以及一个两位置开关和另一个阶乘机器。(阶乘机是无限的，因为它包含了另一个阶乘机。)下图是阶乘机的流程图，显示了各个部件是如何连接在一起的。

![](/files/-MXjL6twXEHrig_P84hm)

同样，我们可以把方案解释器看作是一个非常特殊的机器，它将机器的描述作为输入。 有了这个输入，解释器就会配置自己来模拟所描述的机器。 例如，如果我们向计算程序提供阶乘的定义，那么计算程序将能够计算阶乘。 

从这个角度来看，我们的Scheme解释器被看作是一台通用机器。 当其他机器被描述为方案程序时，它就会模仿它们。它充当由我们的编程语言操纵的数据对象和编程语言本身之间的桥梁。 假设用户在运行的Scheme解释器中输入Scheme表达式。从用户的角度来看，像(+ 2)这样的输入表达式是编程语言中的表达式，解释器应该对其求值。 然而，从Scheme解释器的角度来看，表达式只是一个由单词组成的句子，需要根据一组定义良好的规则进行操作。 

用户的程序是解释器的数据，这一点不必引起混淆。 实际上，有时忽略这一区别并让用户能够显式地计算作为表达式的数据对象是很方便的。 在Scheme中，只要使用运行过程，我们就使用这个工具。 Python中也存在类似的函数:eval函数将对Python表达式求值，exec函数将执行Python语句。 因此

```
>>> eval('2+2')
4
```

```
>>> 2+2
4
```

上面两者都返回相同的结果。对作为执行的一部分构造的表达式求值是动态编程语言中一个常见且强大的特性。在很少的语言中，这种做法像Scheme中那样常见，但是在程序执行过程中构造和计算表达式的能力对任何程序员来说都是有价值的工具。