3 表达式

本章研究变量绑定及其作用域。我们用一系列小型语言解释这些概念。我们为这些语言写出 规范，遵照归纳式数据集的解释器秘方实现其解释器。我们的规范和解释器取一 名为环境 (environment) 的上下文参数，以记录待求值的表达式中各个变量的含 义。

3.1 规范和实现策略

而我们的目标是写出程序， 实现语言。概况如 所示。首先是程序，由我们要实现的语言写出。 这叫做源语言 (source language) 或被定语言 (defined language)。前 端接收程序文本（由源语言写成的程序），将其转化为抽象语法树，然后将语法树传给解释 器。解释器是一程序，它查看一段数据结构，根据结构执行一些动作。当然，解释器自身也 由某种语言写成。我们把那种语言叫做实现语言 (implementation language) 或定义语言 (defining language)。我们的大多数实现都遵照这种方式。

另一种常见的组织方式如 所示。其中，编译器替代了解释器，将 抽象语法树翻译为另一种语言（称为目标语言 (target language)）写成的 程序，然后执行。目标语言可能像 那样，由一个解释器执行，也 可能翻译成更底层的语言执行。

通常，目标语言是一种机器语言，由硬件解释。但目标语言也可能是一种特定用途的语言， 比原本的语言简单，为它写一个解释器相对容易。这样，程序可以编译一次，然后在多种不 同的硬件平台上执行。出于历史原因，常称这样的目标语言为字节码 (byte code)，称其解释器称为虚拟机 (virtual machine)。

编译器常常分为两部分：分析器 (analyzer)，尝试推断关于程序的有效信 息；翻译器 (translator)，执行翻译，可能用到来自分析器的信息。这些 阶段既能用推理规则指定，也能用专写规范的语言指定。然后是实现。 续文传递风格和类型探讨了一些简单的分析器和翻译器。

不论采用哪种实现策略，我们都需要一个前端 (front end)，将程序转换为 抽象语法树。因为程序只是字符串，我们的前端要将这些字符组成有意义的单元。分组通常 分为两个阶段：扫描 (scanning) 和解析 (parsing)。

扫描就是将字符序列分为单词、数字、标点、注释等等。这些单元叫做词条 (lexical item)、词素 (lexeme)、或者最常见的词牌 (token)。把程序分 为词牌的方式叫做语言的词法规范 (lexical specification)。扫描器取一字符序 列，生成词牌序列。

解析就是将词牌序列组成有层次的语法结构，如表达式、语句和块。这就像用从句组织（或 称图解西方有diagram sentence之说，以树状图表示句子结构，如我国中学生学习英 文之主、谓、宾。——译注）句子。我们称之为语言的句法 (syntactic) 或语法 (grammatical) 结构。解析器取一词牌序列（由扫描器给出），生成一棵 抽象语法树。

设计前端的标准方式是使用解析器生成器 (parser generator)。解析器生 成器是一程序，取一词法规范和语法，生成一个扫描器和解析器。

[!ht]

由解释器执行

由编译器执行

语言处理系统块状图

大多数主流语言都有解析器生成系统。如果没有解析器生成器，或者没有合适的，可以手写 扫描器和解析器。编译器教材描述了这一过程。本书使用的解析技术及相关语法设计从简， 专为满足我们的需求。

另一种方式是忽略具体语法的细节，把表达式写成列表结构， 就像抽象语法及其表示和中，处理 lambda 演算表达式那样。

3.2 LET：一门简单语言

我们先来定义一种非常简单的语言，根据它最有趣的特性，将其命名为 LET。

3.2.1 定义语法

展示了我们这门简单语言的语法。在这种语言中，程序只能是一个表达式。表达式是 个整数常量、差值表达式、判零表达式、条件表达式、变量、或 let 表达式。

这里是本门语言写成的一个简单表达式，及其抽象语法表示。

(scan&parse "-(55, -(x,11))")

#(struct:a-program

#(struct:diff-exp

#(struct:const-exp 55)

#(struct:diff-exp

#(struct:var-exp x)

#(struct:const-exp 11))))

[!ht]
\begin{align*}\mathit{Program} &::= \mathit{Expression} \\[-3pt] &\mathrel{\phantom{::=}} \fbox{a-program (exp1)} \\[5pt] \mathit{Expression} &::= \mathit{Number} \\[-3pt] &\mathrel{\phantom{::=}} \fbox{const-exp (num)} \\[5pt] \mathit{Expression} &::= (- \mathit{Expression} , \mathit{Expression}) \\[-3pt] &\mathrel{\phantom{::=}} \fbox{diff-exp (exp1 exp2)} \\[5pt] \mathit{Expression} &::= (zero? \mathit{Expression}) \\[-3pt] &\mathrel{\phantom{::=}} \fbox{zero?-exp (exp1)} \\[5pt] \mathit{Expression} &::= if \mathit{Expression} then \mathit{Expression} else \mathit{Expression} \\[-3pt] &\mathrel{\phantom{::=}} \fbox{if-exp (exp1 exp2 exp3)} \\[5pt] \mathit{Expression} &::= \mathit{Identifier} \\[-3pt] &\mathrel{\phantom{::=}} \fbox{var-exp (var)} \\[5pt] \mathit{Expression} &::= let \mathit{Identifier} = \mathit{Expression} in \mathit{Expression} \\[-3pt] &\mathrel{\phantom{::=}} \fbox{let-exp (var exp1 body)}\end{align*}

LET语言的语法

3.2.2 定义值

任何编程语言的规范之中，最重要的一部分就是语言能处理的值的集合。每种语言至少有两 个这样的集合：表达值 (expressed values) 和指代值 (denoted values)。 表达值是指表达式可能的取值，指代值是指可以绑定到变量的值。

本章的语言中，表达值和指代值总是相同。它们是：

\begin{align*}\mathit{ExpVal} &= \mathit{Int} + \mathit{Bool} \\ \mathit{DenVal} &= \mathit{Int} + \mathit{Bool}\end{align*}

状态展示表达值和指代值不同的语言。

要使用这个定义，我们要有表达值数据类型的接口。我们有这几个接口：

num-val : \mathit{Int} \to \mathit{ExpVal}

bool-val : \mathit{Bool} \to \mathit{ExpVal}

expval->num : \mathit{ExpVal} \to \mathit{Int}

expval->bool : \mathit{ExpVal} \to \mathit{Bool}

我们假定，当传给 expval->num 的参数不是整数值，或传给 expval->bool 的 参数不是布尔值时，二者行为未定义。

3.2.3 环境

若要求取表达式的值，我们得知道每个变量的值。我们靠环境记录这些值，就像数据类型的表示策略那样。

环境是一函数，定义域为变量的有限集合，值域为指代值。我们用一些缩写表示环境。

• \rho 表示任一环境。

• \textnormal{[]} 表示空环境。

• \text{[}var = val\text{]}\rho 表示 (extend-env var val \rho)。

• \text{[}var_1 = val_1, var_2 = val2\text{]}\rho 是 var_1 = val_1(\text{[}var_2 = val_2\text{]}\rho) 的缩写，其余同理。

• \text{[}var_1 = val_1, var_2 = val2,\dots\text{]} 表示的环境中， var_1 的值为 val_1，其余同理。

我们偶尔用不同缩进表示复杂环境，以便阅读。例如，我们可能把

(extend-env 'x 3

(extend-env 'y 7

(extend-env 'u 5 \rho)))

缩写为

[x=3]

[y=7]

[u=5]\rho

3.2.4 定义表达式的行为

我们语言中的六种表达式各对应一个左边为 \mathit{Expression} 的生成式。表达式 接口包含七个过程，六个是构造器，一个是观测器。我们用 \mathit{ExpVal} 表示表 达值的集合。

构造器：

const-exp: \mathit{Int} \to \mathit{Exp}

zero?-exp: \mathit{Exp} \to \mathit{Exp}

if-exp: \mathit{Exp} \times \mathit{Exp} \times \mathit{Exp} \to \mathit{Exp}

diff-exp: \mathit{Exp} \times \mathit{Exp} \to \mathit{Exp}

var-exp: \mathit{Var} \to \mathit{Exp}

let-exp: \mathit{Var} \times \mathit{Exp} \times \mathit{Exp} \to \mathit{Exp}

观测器：

value-of: \mathit{Exp} \times \mathit{Env} \to \mathit{ExpVal}

实现之前，我们先写出这些过程的行为规范。依照解释器秘方，我们希望 value-of 查看表达式，判断其类别，然后返回恰当的值。

(value-of (const-exp n) \rho) = (num-val n)

(value-of (var-exp var) \rho) = (apply-env \rho var)

(value-of (diff-exp exp_1 exp_2) \rho)

= (num-val

(-

(expval->num (value-of exp_1 \rho))

(expval->num (value-of exp_2 \rho))))

任何环境中，常量表达式的值都是这个常量。变量引用的值从某一环境中查询而得。差值表 达式的值为第一个操作数在某一环境中的值减去第二个操作数在同一环境中的值。当然，准 确来说，我们得确保操作数的值是数字，且结果是表示为表达值的数字。

展示了如何结合这些规则求取构造器生成的表达式的值。在本例以 及其他例子中，我们用 \textnormal{\guillemotleft} exp \textnormal{\guillemotright} 表示表达式 exp 的抽象语法树，用 \lceil n \rceil 表示 (num-val n)，用 \lfloor val \rfloor 表示 (expval->num val)。我们还运用了一点事实：\lfloor \lceil n \rceil \rfloor = n。

\textnormal{[}{\star}\textnormal{]} 列出 中所有应用 \lfloor \lceil n \rceil \rfloor = n 的地方。

\textnormal{[}{\star}{\star}\textnormal{]} 给出一个表达值 val \in \mathit{ExpVal}，且 \lceil \lfloor val \rfloor \rceil \neq val。

3.2.5 定义程序的行为

在我们的语言中，整个程序只是一个表达式。要找出这个表达式的值，我们要定义程序中自 由变量的值。所以程序的值就是在适当的初始环境中求出的该表达式的值。我们把初始环境 设为 [i=1,v=5,x=10]。

(value-of-program exp)

= (value-of exp [i=\lceil \tt{1} \rceil,v=\lceil \tt{5} \rceil,x=\lceil \tt{10} \rceil])

3.2.6 定义条件

接下来是这门语言的布尔值接口。这门语言有一个布尔值构造器 zero?，一个布尔值 观测器 if 表达式。

当且仅当操作数的值为0，zero? 表达式的值为真。像 那样， 可将其写成一条推理规则。我们以 bool-val 为构造器，把布尔值转换为表达值；以 expval->num 为提取器，判断表达式的值是否为整数，如果是，则返回该整数。

令 \rho = [i=1,v=5,x=10]。

(value-of

<<-(-(x,3), -(v,i))>>

\rho)

= \lceil(-

\lfloor(value-of <<-(x,3)>> \rho)\rfloor

\lfloor(value-of <<-(v,i)>> \rho)\rfloor)\rceil

= \lceil(-

(-

\lfloor(value-of <> \rho)\rfloor

\lfloor(value-of <<3>> \rho)\rfloor)

\lfloor(value-of <<-(v,i)>> \rho)\rfloor)\rceil

= \lceil(-

(-

10

\lfloor(value-of <<3>> \rho)\rfloor)

\lfloor(value-of <<-(v,i)>> \rho)\rfloor)\rceil

= \lceil(-

(-

10

3)

\lfloor(value-of <<-(v,i)>> \rho)\rfloor)\rceil

= \lceil(-

7

\lfloor(value-of <<-(v,i)>> \rho)\rfloor)\rceil

\columnbreak

= \lceil(-

7

(-

\lfloor(value-of <> \rho)\rfloor

\lfloor(value-of <> \rho)\rfloor))\rceil

= \lceil(-

7

(-

5

\lfloor(value-of <> \rho)\rfloor))\rceil

= \lceil(-

7

(-

5

1))\rceil

= \lceil(-

7

4)\rceil

= \lceil3\rceil

按照规范做简单运算

\infer{\begin{alignedat}{-1} & (value-of (zero?-exp exp_1) \rho) \\ &\hphantom{xx}= \begin{cases} (bool-val #t) & 若 (expval->num val_1) = 0 \\ (bool-val #f) & 若 (expval->num val_1) \neq 0 \hphantom{x} \end{cases} \end{alignedat}} {(value-of exp_1 \rho) = val_1}

一个 if 表达式就是一个布尔值观测器。欲求 if 表达式 (if-exp exp_1 exp_2 exp_3) 的值，首先判断子表达式 exp_1 的值；若该值为 真，整个表达式的值应为子表达式 exp_2 的值，否则为子表达式 exp_3 的值。这 也很容易写成推理规则。就像在前一个例子中使用 expval->num 一样，我们用 expval->bool 提取表达值的布尔部分。

\infer{\begin{alignedat}{-1} & (value-of (if-exp exp_1 exp_2 exp_3) \rho) \\ &\hphantom{xx}= \begin{cases} (value-of exp_2 \rho) & 若 (expval->bool val_1) = #t \\ (value-of exp_3 \rho) & 若 (expval->bool val_1) = #f \hphantom{x} \end{cases} \end{alignedat}} {(value-of exp_1 \rho) = val_1}

用这种推理规则很容易指定任意表达式的期望行为，但却不适合展示推理过程。像 (value-of exp_1 \rho) 这样的前件表示一部分计算，所以一个计算过程应 该是一棵树，就像deriv-tree那种。很不幸的是，这样的树极为晦涩。因此，我 们经常把规则转为方程，然后就能用相等代换展示计算过程。

if-exp 的方程式规范是：

(value-of (if-exp exp_1 exp_2 exp_3) \rho)

= (if (expval->bool (value-of exp_1 \rho))

(value-of exp_2 \rho)

(value-of exp_3 \rho))

展示了用这些规则进行简单运算的过程。

[!t]令 \rho = [x=\lceil33\rceil,y=\lceil22\rceil]。

(value-of

<>

\rho)

= (if (expval->bool (value-of <> \rho))

(value-of <<-(y,2)>> \rho)

(value-of <<-(y,4)>> \rho))

= (if (expval->bool (bool-val #f))

(value-of <<-(y,2)>> \rho)

(value-of <<-(y,4)>> \rho))

= (if #f

(value-of <<-(y,2)>> \rho)

(value-of <<-(y,4)>> \rho))

= (value-of <<-(y,4)>> \rho)

= \lceil18\rceil

条件表达式的简单计算过程

3.2.7 定义 let

接下来我们处理用 let 表达式创建新变量绑定的问题。我们给这门解释性语言添加语 法，以关键字 let 起始，然后是一个声明，关键字 in，及其主体。例如，

let x = 5

in -(x, 3)

像 lambda 变量绑定一样（见occurs-free?），let 变量绑定于主体之中。

如同其主体，整个 let 形式也是一个表达式，所以 let 表达式可以嵌套，例如

let z = 5

in let x = 3

in let y = -(x, 1)    % 这里 x = 3

in let x = 4

in -(z, -(x,y)) % 这里 x = 4

在本例中，第一个差值表达式中使用的 x 指代外层声明，另一个差值表达式中使用的 x 指代内层声明，所以整个表达式的值是3。

let 声明的右边也是一个表达式，所以它可以任意复杂。例如

let x = 7

in let y = 2

in let y = let x = -(x,1)

in -(x,y)

in -(-(x,8), y)

这里第三行声明的 x 绑定到 6，所以 y 的值是 4，整个表达式的值是 ((-1)-4) = -5。

可以将规范写成一条规则。

\infer{\begin{alignedat}{-1} & (value-of (let-exp var exp_1 body) \rho) \\ &\hphantom{xx}= (value-of body [var=val_1]\rho) \end{alignedat}} {(value-of exp_1 \rho) = val_1}

像之前那样，将其转为方程通常更方便。

(value-of (let-exp var exp_1 body) \rho)

= (value-of body [var=(value-of exp_1 \rho)]\rho)

展示了一个例子，其中 \rho_0 表示任意环境。

3.2.8 实现 LET 规范

接下来的任务是用一组Scheme过程实现这一规范。我们的实现以 SLLGEN见 附录B。——译注 为前端，表达式用 中的数据类型表示。在我们的实现中，表达值的表示如 所示。数据 类型声明了构造器 num-val 和 bool-val，用来将整数值和布尔值转换为表达值。 我们还定义了提取器，用来将表达值转为整数或布尔值。如果表达值类型不符预期，提取器 报错。

[!t]

(define-datatype program program?

(a-program

(exp1 expression?)))

(define-datatype expression expression?

(const-exp

(num number?))

(diff-exp

(exp1 expression?)

(exp2 expression?))

(zero?-exp

(exp1 expression?))

(if-exp

(exp1 expression?)

(exp2 expression?)

(exp3 expression?))

(var-exp

(var identifier?))

(let-exp

(var identifier?)

(exp1 expression?)

(body expression?)))

LET 语言的语法数据类型

只要满足数据类型的表示策略中的定义，任意一种环境实现都可使用。过程 init-env 创建 指定的初始环境，供 value-of-program 使用。

init-env : () \to \mathit{Env}

用法 : (init-env) = [i=\lceil1\rceil,v=\lceil5\rceil,x=\lceil10\rceil]

(define init-env

(lambda ()

(extend-env

'i (num-val 1)

(extend-env

'v (num-val 5)

(extend-env

'x (num-val 10)

(empty-env))))))

[!t]

(define-datatype expval expval?

(num-val

(num number?))

(bool-val

(bool boolean?)))

expval->num : \mathit{ExpVal} \to \mathit{Int}

(define expval->num

(lambda (val)

(cases expval val

(num-val (num) num)

(else (report-expval-extractor-error 'num val)))))

expval->bool : \mathit{ExpVal} \to \mathit{Bool}

(define expval->bool

(lambda (val)

(cases expval val

(bool-val (bool) bool)

(else (report-expval-extractor-error 'bool val)))))

LET 语言的表达值

现在我们可以写出解析器，如 和fig-3.9 所示。主过程 是 run，它取一个字符串，解析它，把结果传给 value-of-program。最令人感 兴趣的过程是 value-of，它取一表达式和一环境，用解释器秘方计算规范所要求的答 案。在代码中，我们插入了相关的推理规则定义，以便观察 value-of 的代码如何与 规范对应。

在下面的练习以及全书之中，短语 “扩展语言，添加……”表示向语言规范添加规则或者方程， 并增改相应的解释器，实现指定特性。

run : \mathit{String} \to \mathit{ExpVal}

(define run

(lambda (string)

(value-of-program (scan&parse string))))

value-of-program : \mathit{Program} \to \mathit{ExpVal}

(define value-of-program

(lambda (pgm)

(cases program pgm

(a-program (exp1)

(value-of exp1 (init-env))))))

value-of : \mathit{ExpVal} \times \mathit{Env} \to \mathit{Bool}

(define value-of

(lambda (exp env)

(cases expression exp

\fbox{ (value-of (const-exp n) \rho) = n}

(const-exp (num) (num-val num))

\fbox{ (value-of (var-exp var) \rho) = (apply-env \rho var)}

(var-exp (var) (apply-env env var))

\fbox{\begin{math}\begin{alignedat}{-1}& (value-of (diff-exp exp_1 exp_2) \rho) = \\ &\hphantom{xxx}\lceil(- \lfloor(value-of exp_1 \rho)\rfloor \lfloor(value-of exp_2 \rho)\rfloor)\rceil\end{alignedat}\end{math}}

(diff-exp (exp1 exp2)

(let ((val1 (value-of exp1 env))

(val2 (value-of exp2 env)))

(let ((num1 (expval->num val1))

(num2 (expval->num val2)))

(num-val

(- num1 num2)))))

\begin{comment}

...)))

\end{comment} \smallskip

LET 语言的解释器

[!ht]

\smallskip \begin{comment}

(((...

\end{comment}

\fbox{\infer{\begin{alignedat}{-1}&(value-of (zero?-exp exp_1) \rho) \\ &\hphantom{x}= \begin{cases} (bool-val #t) & 若 (expval->num val_1) = 0 \\ (bool-val #f) & 若 (expval->num val_1) \neq 0 \end{cases} \end{alignedat}}{(value-of exp_1 \rho) = val_1}}

(zero?-exp (exp1)

(let ((val1 (value-of exp1 env)))

(let (num1 (expval->num val1))

(if (zero? num1)

(bool-val #t)

(bool-val #f)))))

\fbox{\infer{\begin{alignedat}{-1}&(value-of (if-exp exp_1 exp_2 exp_3) \rho) \\ &\hphantom{x}= \begin{cases} (value-of exp_2 \rho) & 若 (expval->bool val_1) = #t \\ (value-of exp_3 \rho) & 若 (expval->bool val_1) = #f \end{cases} \end{alignedat}}{(value-of exp_1 \rho) = val_1}}

(if-exp (exp1 exp2 exp3)

(if (expval->bool (value-of exp1 env))

(value-of exp2 env)

(value-of exp3 env)))

\fbox{\infer{\begin{alignedat}{-1}&(value-of (let-exp var exp_1 body) \rho) \\ &\hphantom{x}= (value-of body [var=val_1]\rho) \end{alignedat}}{(value-of exp_1 \rho) = val_1}}

(let-exp (var exp1 body)

(let ((val1 (value-of exp1 env)))

(value-of body

(extend-env var val1 env)))))))

LET 语言的解释器，续

\textnormal{[}{\star}\textnormal{]} 我们只有一个算术操作，选减法为什么比加法好？

\textnormal{[}{\star}\textnormal{]}  把 中的推导写成deriv-tree那样的推理树。

\textnormal{[}{\star}\textnormal{]} 把 中的推导写成deriv-tree那样的推理树。

\textnormal{[}{\star}\textnormal{]} 扩展语言，添加新操作符 minus，它取一参数 n，返回 -n。例如， minus(- (minus(5), 9)) 的值应为14。

\textnormal{[}{\star}\textnormal{]} 扩展语言，添加加法、乘法和整数除法操作。

\textnormal{[}{\star}\textnormal{]} 向该语言添加等值比较谓词 equal?，以及顺序比较谓词 greater? 和 less?。

\textnormal{[}{\star}{\star}\textnormal{]}  向该语言添加列表处理操作，包括 cons、car、cdr、null? 和 emptylist。列表可以包含任何表达值，包括其他列表。像定义值那样，给 出语言表达值和指代值的定义。例如：

let x = 4

in cons(x,

cons(cons(-(x,1),

emptylist),

emptylist))

应返回一表达值，表示列表 (4 (3))。

\textnormal{[}{\star}{\star}\textnormal{]}  向该语言添加操作 list。该操作取任意数量的参数，返回一表达值，包含由参数值组 成的列表。例如：

let x = 4

in list(x, -(x,1), -(x,3))

应返回一表达值，表示列表 (4 3 1)。

\textnormal{[}{\star}\textnormal{]} 真正的语言可能有很多上述练习那样的操作符。调整解释器代码，以便添加新操作符。

\textnormal{[}{\star}\textnormal{]}  向该语言添加 cond 表达式。语法为：

\mathit{Expression} ::= cond \{}\mathit{Expression}  ==> \mathit{Expression}\^{*} end

在这种表达式里，==> 左边的表达式按序求值，直到其中一个返回真。整个表达式的 值是真值表达式右边对应表达式的值。如果没有条件为真，该表达式应报错。

\textnormal{[}{\star}\textnormal{]}  修改语言，把整数作为唯一的表达值。修改 if，以 0 为假，以所有其他值为真。相 应地修改谓词。

\textnormal{[}{\star}{\star}\textnormal{]}  前一题的另一做法是给语言添加新的非终结符 \mathit{Bool\mbox{-}exp}，作为布尔 值表达式。修改条件表达式的生成式：

\mathit{Expression} ::= if \mathit{Bool\mbox{-}exp} then \mathit{Expression} else \mathit{Expression}

为 \mathit{Bool\mbox{-}exp} 写出适当的生成式，实现 value-of-bool-exp。 按这种方式， 中的谓词应放在哪里？

\textnormal{[}{\star}\textnormal{]}  扩展语言，添加新操作 print，它取一参数，打印出来，返回整数1。在我们的规范框 架下，为什么不能表示这一操作？

\textnormal{[}{\star}{\star}\textnormal{]}  扩展语言，允许 let 声明任意数量的变量，语法为：

\mathit{Expression} ::= let \{}\mathit{Identifier} = \mathit{Expression}\^* in \mathit{Expression}

像 Scheme 中的 let 那样，声明右边在当前环境中求值，每个新变量绑定到对应声明 右边的值，然后求主体的值。例如：

let x = 30

in let x = -(x,1)

y = -(x,2)

in -(x,y)

值应为1。

\textnormal{[}{\star}{\star}\textnormal{]}  扩展语言，添加表达式 let*，像 Scheme 的 let* 那样。则：

let x = 30

in let* x = -(x,1) y = -(x,2)

in -(x,y)

值应为2。

\textnormal{[}{\star}{\star}\textnormal{]}  向该语言添加表达式：

\mathit{Expression} ::= unpack \{\mathit{Identifier}\}^* = \mathit{Expression} in \mathit{Expression}

则：如果 lst 恰好是三元素的列表，unpack x y z = lst in ... 将 x、 y 和 z 绑定到 lst 的各元素；否则报错。例如：

let u = 7

in unpack x y = cons(u,cons(3,emptylist))

in -(x,y)

值应为4。

3.3 PROC：有过程的语言

目前为止，我们的语言只能进行定义好的操作。要想让这种解释性语言更有用，必须能创建 新过程。我们把新语言叫做 PROC。

按照 Scheme 的设计，我们把过程作为语言的表达值，则：

\begin{align*}\mathit{ExpVal} &= \mathit{Int} + \mathit{Bool} + \mathit{Proc} \\ \mathit{DenVal} &= \mathit{Int} + \mathit{Bool} + \mathit{Proc}\end{align*}

其中，\mathit{Proc} 是一值集合，表示过程。我们把 \mathit{Proc} 作为一种 抽象数据类型。下面我们考虑它的接口和规范。

我们还需要语法来创建和调用过程。对应的生成式为：

\begin{align*}\mathit{Expression} &::= proc (\mathit{Identifier}) \mathit{Expression} \\[-3pt] &\mathrel{\phantom{::=}} \fbox{proc-exp (var body)} \\[5pt] \mathit{Expression} &::= letrec(\mathit{Expression} \mathit{Expression}) \\[-3pt] &\mathrel{\phantom{::=}} \fbox{call-exp (rator rand)}\end{align*}

在 (proc var body) 中，变量 var 是绑定 变量 (bound variable) 或形参 (formal parameter)。在过程调用 (call-exp exp_1 exp_2) 中，表达式 exp_1 是操作符 (operator)，表达式 exp_2 是操作数 (operand) 或实际参数 (actual parameter)。我们用实参 (argument) 指代实 际参数的值。

这是这种语言的两个小例子。

let f = proc (x) -(x,11)

in (f (f 77))

(proc (f) (f (f 77))

proc (x) -(x,11))

第一个程序创建过程 f，将实参减11，然后用 77 两次调用 f，得到的答案为55。 第二个程序创建的过程取一参数，连续两次用 77 调用该参数；然后将减 11 的过程传给创 建的过程，结果仍为 55。

现在我们来看数据类型 \mathit{Proc}。它的接口包含构造器 procedure，用于 创建过程值；观测器 apply-procedure，用于调用过程值。

接下来的任务是，明确表示过程的值需要包含哪些信息。欲知此，我们考虑在程序中任意位 置写 proc 表达式时发生了什么。

词法作用域规则告诉我们，调用一个过程时，过程的形参绑定到调用时的实参，然后在该环 境内求值过程的主体。过程中出现的自由变量也应该遵守词法绑定规则。考虑表达式：

let x = 200

in let f = proc (z) -(z,x)

in let x = 100

in let g = proc (z) -(z,x)

in -((f 1), (g 1))

这里我们两次求值表达式 proc (z) -(z,x)。第一次求值时，x 绑定到 200，所 以根据词法绑定规则，得到的过程将实参减 200，我们将其命名为 f。第二次求值时， x 绑定到 100，得出的过程应将实参减 100，我们将该过程命名为 g。

这两个过程由同一个表达式生成，而行为不同。由此可得，proc 表达式的值一定以某 种方式依赖求值环境。因此，构造器 procedure 必定取三个参数：绑定变量、主体以 及环境。proc 表达式定义为：

(value-of (proc-exp var body) \rho)

= (proc-val (procedure var body \rho))

像 bool-val 和 num-val 一样，proc-val 是一构造器，生成一个 \mathit{Proc} 的表达值。

调用过程时，我们要找出操作符和操作数的值。如果操作符是一个 proc-val，那么我 们要以操作数的值调用它。

(value-of (call-exp rator rand) \rho)

= (let ((proc (expval->proc (value-of rator \rho)))

(arg (value-of rand \rho)))

(apply-procedure proc arg))

这里，我们用了一个判断式 expval->proc，像 expval->num，它判断表达值 (value-of rator \rho) 是否由 proc-val 生成，如果是，则从中提取 出包含的过程。

最后，我们考虑调用 apply-procedure 时发生了什么。词法作用域规则告诉我们，调 用过程时，过程主体的求值环境将其形参绑定到调用时的实参；而且，任何其他变量的值必 须和过程创建时相同。因此，这些过程应满足条件

(apply-procedure (procedure var body \rho) val)

= (value-of body [var=val]\rho)

3.3.1 一个例子

我们用一个例子展示定义的各部分是如何配合的。由于我们还没有写出过程的实现，这个计 算过程用规范表示。令 \rho 为任一环境。

(value-of

<

in let f = proc (z) -(z,x)

in let x = 100

in let g = proc (z) -(z,x)

in -((f 1), (g 1))>>

\rho)

= (value-of

<

in let x = 100

in let g = proc (z) -(z,x)

in -((f 1), (g 1))>>

[x=\lceil200\rceil]\rho)

= (value-of

<

in let g = proc (z) -(z,x)

in -((f 1), (g 1))>>

[f=(proc-val (procedure z <<-(z,x)>> [x=\lceil200\rceil]\rho))]

[x=\lceil200\rceil]\rho)

= (value-of

<

in -((f 1), (g 1))>>

[x=\lceil100\rceil]\rho

[f=(proc-val (procedure z <<-(z,x)>> [x=\lceil200\rceil]\rho))]

[x=\lceil200\rceil]\rho)

= (value-of

<

in -((f 1), (g 1))>>

[g=(proc-val (procedure z <<-(z,x)>>

[x=\lceil100\rceil][f=...][x=\lceil200\rceil]\rho))]

[x=\lceil100\rceil]\rho

[f=(proc-val (procedure z <<-(z,x)>> [x=\lceil200\rceil]\rho))]

[x=\lceil200\rceil]\rho)

= \lceil(-

(value-of <<(f 1)>>

[g=(proc-val (procedure z <<-(z,x)>>

[x=\lceil100\rceil][f=...][x=\lceil200\rceil]\rho))]

[x=\lceil100\rceil]\rho

[f=(proc-val (procedure z <<-(z,x)>> [x=\lceil200\rceil]\rho))]

[x=\lceil200\rceil]\rho)

(value-of <<(g 1)>>

[g=(proc-val (procedure z <<-(z,x)>>

[x=\lceil100\rceil][f=...][x=\lceil200\rceil]\rho))]

[x=\lceil100\rceil]\rho

[f=(proc-val (procedure z <<-(z,x)>> [x=\lceil200\rceil]\rho))]

[x=\lceil200\rceil]\rho))\rceil

= \lceil(-

(apply-procedure

(procedure z <<-(z,x)>> [x=\lceil200\rceil]\rho)

\lceil1\rceil)

(apply-procedure

(procedure z <<-(z,x)>> [x=\lceil100\rceil][f=...][x=\lceil200\rceil]\rho)

\lceil1\rceil))\rceil

= \lceil(-

(value-of <<-(z,x)>> [z=\lceil1\rceil][x=\lceil200\rceil]\rho)

(value-of <<-(z,x)>> [z=\lceil1\rceil][x=\lceil100\rceil][f=...][x=\lceil200\rceil]\rho))\rceil

= \lceil(- -199 -99)\rceil

= \lceil-100\rceil

其中，绑定到的 f 过程将实参减 200，绑定到 g 的过程将实参减 100，所以 (f 1) 的值是 -199，(g 1) 的值是 -99。

3.3.2 表示过程

根据过程表示法中介绍的方法，我们可以按照过程表示法，用过程在 apply-procedure 中的动作表示它们。欲如此，我们将 procedure 的值定义为 实现语言的过程，它取一实参，返回下面规范要求的值：

(apply-procedure (procedure var body \rho) val)

= (value-of body (extend-env var val \rho))

因此，完整的实现是：

proc? : \mathit{SchemeVal} \to \mathit{Bool}

(define proc?

(lambda (val)

(procedure? val)))

procedure : \mathit{Var} \times \mathit{Exp} \times \mathit{Env} \to \mathit{Proc}

(define procedure

(lambda (var body env)

(lambda (val)

(value-of body (extend-env var val env)))))

apply-procedure : \mathit{Proc} \times \mathit{ExpVal} \to \mathit{ExpVal}

(define apply-procedure

(lambda (proc1 val)

(proc1 val)))

这里定义的函数 proc? 不完全准确，因为不是每个 Scheme 过程都能作为我们语言中 的过程。我们需要它，只是为了定义数据类型 expval。

另一种方式是用数据结构表示法那样的数据结构表示法。

proc? : \mathit{SchemeVal} \to \mathit{Bool}

procedure : \mathit{Var} \times \mathit{Exp} \times \mathit{Env} \to \mathit{Proc}

(define-datatype proc proc?

(procedure

(var identifier?)

(body expression?)

(saved-env environment?)))

apply-procedure : \mathit{Proc} \times \mathit{ExpVal} \to \mathit{ExpVal}

(define apply-procedure

(lambda (proc1 val)

(cases proc proc1

(procedure (var body saved-env)

(value-of body (extend-env var val saved-env))))))

这些数据结构常称为闭包 (closure)，因为它们自给自足，包含过程调用所需要的 一切。有时，我们说过程闭合于 (closed over, closed in) 创建时的环境。

显然，这些实现都满足过程接口的定义。

不论哪种实现，我们都要给数据类型 expval 添加变体：

(define-datatype exp-val exp-val?

(num-val

(val number?))

(bool-val

(val boolean?))

(proc-val

(val proc?)))

同时给 value-of 添加两条新语句：

(proc-exp (var body)

(proc-val (procedure var body env)))

(call-exp (rator rand)

(let ((proc (expval->proc (value-of rator env)))

(arg (value-of rand env)))

(apply-procedure proc arg)))

记住：一定要给语言的每个扩展写出规范。参见ex-note的说明。

\textnormal{[}{\star}\textnormal{]}  在很多语言中，过程创建和命名必须同时进行。修改本节的语言，用 letproc 替换 proc，以支持此性质。

\textnormal{[}{\star}\textnormal{]}  在PROC中，过程只能有一个参数，但是可以用返回其他过程的过程来模拟多参数过程。例如， 可以写出这样的代码：

let f = proc (x) proc (y) ...

in ((f 3) 4)

这个小技巧叫做咖哩化 (Currying)，该过程则 称作咖喱式 (Curried) 的。写出一个咖喱式的过程，它取两个参数，返回 二者之和。在我们的语言中，可以把 x+y 写成 -(x,-(0,y))。

\textnormal{[}{\star}{\star}\textnormal{]} 扩展本节的语言，添加多参数过程及其调用，语法为：

\begin{align*}\mathit{Expression} &::= proc (\{\mathit{Identifier}\}^{*(,)}) \mathit{Expression} \\[-3pt] \mathit{Expression} &::= (\mathit{Expression} \mathit{\{Expression\}^{*}})\end{align*}

\textnormal{[}{\star}{\star}{\star}\textnormal{]} 本节的内置操作（如差值）和过程调用使用不同的具体语法。修改具体语法，不要让语言的 用户区分哪些是内置操作，哪些是自定义的过程。根据所使用的解析技术，这道练习可能很 容易，也可能非常难。

\textnormal{[}{\star}{\star}\textnormal{]}  下面的PROC程序值是什么？

let makemult = proc (maker)

proc (x)

if zero?(x)

then 0

else -(((maker maker) -(x,1)), -4)

in let times4 = proc (x) ((makemult makemult) x)

in (times4 3)

用这个程序里的小技巧写出PROC阶乘过程。提示：你可以使用咖 喱化（）定义双参数过程 times。

\textnormal{[}{\star}{\star}\textnormal{]}  用上述程序里的小技巧写出 中的互递归程序 odd 和 even。

\textnormal{[}{\star}\textnormal{]}  提炼上述练习中的技巧，用它在 PROC 中定义任意递归过程。考虑下面的代码：

let makerec = proc (f)

let d = proc (x)

proc (z) ((f (x x)) z)

in proc (n) ((f (d d)) n)

in let maketimes4 = proc (f)

proc (x)

if zero?(x)

then 0

else -((f -(x,1)), -4)

in let times4 = (makerec maketimes4)

in (times4 3)

证明它返回12。

\textnormal{[}{\star}{\star}\textnormal{]}  我们用数据结构表示过程时，在闭包中记录了整个环境。但是显然，我们只需要自由变量的 绑定。修改过程的表示，只保留自由变量。

\textnormal{[}{\star}\textnormal{]} 给语言添加另一种过程 traceproc。traceproc 类似 proc，但会在入口和 出口处打印跟踪消息。

\textnormal{[}{\star}{\star}\textnormal{]}  设计过程的另一种方法是动态绑定 (dynamic binding)（或称动态定界 (dynamic scoping)）：求值过程主体的环境由调用处的环境扩展而得。例如，在

let a = 3

in let p = proc (x) -(x,a)

a = 5

in -(a, (p 2))

中，过程主体内的 a 绑定到 5，而不是 3。修改语言，使用动态绑定。做两次，一次 用过程表示法表示过程，一次用数据结构表示法。

\textnormal{[}{\star}{\star}\textnormal{]} 很不幸的是，使用动态绑定的程序很可能异常晦涩。例如，在词法绑定中，批量替换过程的 绑定变量，决不会改变程序的行为：我们甚至可以像消除变量名那样，删除所有变量， 将它们替换为词法地址。但在动态绑定中，这种转换就危险了。

例如，在动态绑定中，过程 proc (z) a 返回调用者环境中的变量 a。那么程序

let a = 3

in let p = proc (z) a

in let f = proc (x) (p 0)

in let a = 5

in (f 2)

返回 5，因为调用处 a 的值为 5。如果 f 的形参为 a 呢？

3.4 LETREC：支持递归过程的语言

现在我们来定义支持递归的新语言 LETREC。因为我们的语言只有单参数过程，所以我们降 低难度，只让 letrec 表达式声明一个单参数过程，例如：

letrec double (x)

= if zero?(x) then 0 else -((double -(x,1)), -2)

in (double 6)

递归声明的左边是递归过程的名字和绑定变量，= 右边是过程主体，其生成式为：

\begin{align*}\mathit{Expression} &::= letrec \mathit{Identifier} (\mathit{Identifier}) = \mathit{Expression} in \mathit{Expression} \\[-3pt] &\mathrel{\phantom{::=}} \fbox{letrec-exp (p-name b-var p-body letrec-body)}\end{align*}

letrec 表达式的值是其主体的值，在符合期望行为的环境中求出：

(value-of

(letrec-exp proc\mbox{-}name bound\mbox{-}var proc\mbox{-}body letrec\mbox{-}body)

\rho)

= (value-of

letrec\mbox{-}body

(extend-env-rec proc\mbox{-}name bound\mbox{-}var proc\mbox{-}body \rho))

这里，我们给环境接口新增一个过程 extend-env-rec。但我们仍然得回答这个问题： (extend-env-rec proc\mbox{-}name bound\mbox{-}var proc\mbox{-}body \rho) 的期望行为是什么？

我们定义该环境的行为如下：设 \rho_1 为 (extend-env-rec proc\mbox{-}name bound\mbox{-}var proc\mbox{-}body \rho) 产生的 环境。那么 (apply-env \rho_1 var) 应返回什么？

1. 如果变量 var 与 proc\mbox{-}name 相同，那么 (apply-env \rho_1 var) 应返回一个闭包，其绑定变量为 bound\mbox{-}var，主体为 proc\mbox{-}body，环境为绑定 proc\mbox{-}name 时所在的环境。而我们已经 有这个环境了：就是 \rho_1！所以：

   (apply-env \rho_1 proc\mbox{-}name)

   = (proc-val (procedure bound\mbox{-}var proc\mbox{-}name \rho_1))

2. 如果 var 与 proc\mbox{-}name 不同，那么：

   (apply-env \rho_1 var) = (apply-env \rho var)

和 fig-3.11 展示了一个例子。 的最后一行递归调用 double，找出了原来的 double， 正合所愿。

满足这些要求的任何方法都能够用来实现 extend-env-rec。这里我们使用对应于抽象 语法表示的方法。练习讨论了其他实现策略。

如，在抽象语法表示中，我们为 extend-env-rec 新增一种变 体。apply-env 倒数第二行的 env 对应上述 \rho_1。

(value-of <

then 0

else -((double -(x,1)), -2)

in (double 6)>> \rho_0)

= (value-of <<(double 6)>>

(extend-env-rec double x <> \rho_0))

= (apply-procedure

(value-of <> (extend-env-rec double x

<> \rho_0))

(value-of <<6>> (extend-env-rec double x

<> \rho_0)))

= (apply-procedure

(value-of <> (extend-env-rec double x

<> \rho_0))

\lceil6\rceil)

= (value-of

<>

[x=\lceil6\rceil](extend-env-rec

double x <> \rho_0))

...

= (-

(value-of

<<(double -(x,1))>>

[x=\lceil6\rceil](extend-env-rec

double x <> \rho_0))

-2)

extend-env-rec 计算过程

[!ht]

= (-

(apply-procedure

(value-of

<>

[x=\lceil6\rceil](extend-env-rec

double x <> \rho_0))

(value-of

<<(double -(x,1))>>

[x=\lceil6\rceil](extend-env-rec

double x <> \rho_0)))

-2)

= (-

(apply-procedure

(procedure x <>

(extend-env-rec double x <> \rho_0))

\lceil5\rceil)

-2)

= ...

extend-env-rec 计算过程，续

[!ht]

(define-datatype environment environment?

(empty-env)

(extend-env

(var identifier?)

(val expval?)

(env environment?))

(extend-env-rec

(p-name identifier?)

(b-var identifier?)

(body expression?)

(env environment?)))

(define apply-env

(lambda (env search-var)

(cases environment env

(empty-env ()

(report-no-binding-found search-var))

(extend-env (saved-var saved-val saved-env)

(if (eqv? saved-var search-var)

saved-val

(apply-env saved-env search-var)))

(extend-env-rec (p-name b-var p-body saved-env)

(if (eqv? search-var p-name)

(proc-val (procedure b-var p-body env))

(apply-env saved-env search-var))))))

向环境添加 extend-env-rec

\textnormal{[}{\star}\textnormal{]} apply-env 倒数第二行调用 proc-val 的目的是什么？

\textnormal{[}{\star}\textnormal{]}  扩展上面的语言，允许声明任意数量参数的过程，像 那样。

\textnormal{[}{\star}\textnormal{]}  扩展上面的语言，允许声明任意数量的单参数互递归过程，例如：

letrec

even(x) = if zero?(x) then 1 else (odd -(x,1))

odd(x)  = if zero?(x) then 0 else (even -(x,1))

in (odd 13)

\textnormal{[}{\star}{\star}\textnormal{]}  扩展上面的语言，允许声明任意数量的互递归过程，每个过程的参数数量也任意，就 像 那样。

\textnormal{[}{\star}{\star}{\star}\textnormal{]}  用过程表示法中环境的过程表示法实现 extend-env-rec。

\textnormal{[}{\star}\textnormal{]}  目前为止，我们看到的表示法都很低效，因为每次查找过程时，它们都要新创建一个闭包， 但每次的闭包都相同。我们可以只创建一次闭包，把值放入长度为 1 的向量，再将其放入 一个显式循环结构中，像这样：

这里是创建这种数据结构的代码：

(define extend-env-rec

(lambda (p-names b-vars bodies saved-env)

(let ((vec (make-vector (length p-names))))

(let ((new-env (extend-env p-names vec saved-env)))

(vector-set! vec 0

(proc-val (procedure b-var body new-env)))

new-env))))

修改环境数据类型和 apply-env 的定义，完成这种表示的实现。确保 apply-env 总是返回表达值。

\textnormal{[}{\star}{\star}\textnormal{]}  扩展这种实现，处理 中的语言。

\textnormal{[}{\star}{\star}\textnormal{]}  使用动态绑定（），不需要任何特殊机制，靠 let 就能创建 递归过程。这是出于历史兴趣。在早年的编程语言设计中，LETREC：支持递归过程的语言讨论的那些方法 还鲜为人知。要验证动态绑定实现的递归，试试程序：

let fact = proc (n) add1(n)

in let fact = proc (n)

if zero?(n)

then 1

else *(n, (fact -(n,1)))

in (fact 5)

试试词法绑定，再试试动态绑定。用动态绑定的被定语言写出LETREC：支持递归过程的语言中的互递归过 程 even 和 odd。

3.5 定界和变量绑定

我们已经在很多地方见到过变量的声明和使用，现在我们来系统讨论这些思想。

在大多数编程语言中，变量只能以两种方式出现：引用 (reference) 或声明 (declaration)。变量引用就是使用变量。例如，在 Scheme 表达式

(f x y)

中出现的变量 f、x 和 y 均为引用。但在

(lambda (x) (+ x 3))

或

(let ((x (+ y 7))) (+ x 3))

中，第一个出现的 x 是声明：引入一个变量，作为某个值的名字。在 lambda 表达式中，变量的值在过程调用时提供。在 let 表达式中，变量的值由表达式 (+ y z) 求得。

我们说变量引用由对应的声明绑定 (bound)，且绑定到它的值。 在occurs-free?，我们已经见过用声明绑定变量的例子。

[!t]

简单等深线

大多数编程语言中的声明都有有限的作用域，所以同一个变量名在程序的不同部分可用于不 同的目的。例如，我们反复把 lst 用作绑定变量，它的作用域每次都限制在对应的 lambda 表达式主体内。

每种编程语言都有一些规则来判断各个变量引用指代哪一声明。这些规则通常 叫做定界 (scoping) 规则。声明在程序中生效的部分叫做声明 的作用域 (scope)。

我们可以不加执行地判断程序中的各个变量引用对应于哪个声明。这样的性质不必执行程序 就能计算出来，名为静态 (static) 性质。

要找出某个变量引用对应于哪一声明，我们向外 (outward) 查找，直到找 出变量的声明。这里是一个简单的 Scheme 示例。

(let ((x 3)              称之为 x1

(y 4))

(+ (let ((x            称之为 x2

(+ y 5)))

(* x y))          这个 x 指代 x2

x))                 这个 x 指代 x1

在这个例子中，内层的 x 绑定到 9，所以表达式的值为

(let ((x 3)

(y 4))

(+ (let ((x

(+ y 5)))

(* x y))

x))

= (+ (let ((x

(+ 4 5)))

(* x 4))

3)

= (+ (let ((x 9))

(* x 4))

3)

= (+ 36

3)

= 39

这样的定界规则叫做词法定界 (lexical scoping) 规则，这样声明的变量 叫做词法变量 (lexical variable)。

使用词法定界，我们可以重新声明一个变量，给作用域戳个“洞 ”。这样的内层声明遮蔽 (shadow) 外层声明。 例如，在上例的乘式 (* x y) 中，内层的 x 遮蔽了外层的。

词法作用域是嵌套式的：每个作用域完全包裹在另一个里面。我们用等深线 (contour diagram) 解释这点。 展示了上例的等深线。每个作用域 用一个框圈起来，箭头连接声明与其作用域。

展示了一个更复杂的程序和它的等深线。其中的第 5 行、第 7 行 和第 8 行，表达式 (+ x y z) 出现了三次。第 5 行在 x2 和 z2 的作用 域内，x2 和 z2 的作用域在 z1 的作用域内，z1 的作用域在 x1 和 y1 的作用域内。所以，第5行的 x 指代 x2，y 指代 y1，z 指代 z2。第 7 行在 x4 和 y2 的作用域内，x4 和y2 的作用域在 x2 和 z2 的作用域内，x2 和 z2 的作用域 在z1 的作用域内，z1 的作用域在 x1 和 y1 的作用域内。所以，第 7行的 x 指代 x4，y 指代 y2，z 指代 z2。最后，第 8 行在 x3 的作用域内，x3 的作用域在 x2 和 z2 的作用域内， x2 和 z2 的作用域在 z1 的作用域内，z1 的作用域在 x1 和 y1 的作用域内。所以，第8行的 x 指代 x3，y 指代 y1， z 指代z2。

较复杂的等深线

变量与值的对应关系叫做绑定 (binding)。我们可以通过规范来理解如何创 建绑定。

由 proc 声明的变量在过程调用时绑定。

(apply-procedure (procedure var body \rho) val)

= (value-of body (extend-env var val \rho))

let 声明的变量绑定到声明右边的值。

(value-of (let-exp var val body) \rho)

= (value-of body (extend-env var val \rho))

letrec 声明的变量也要绑定到声明右边的值。

(value-of

(letrec-exp proc\mbox{-}name bound\mbox{-}var proc\mbox{-}body letrec\mbox{-}body)

\rho)

= (value-of

letrec\mbox{-}body

(extend-env-rec proc\mbox{-}name bound\mbox{-}var proc\mbox{-}body \rho))

绑定的期限 (extent) 指绑定保持的时长。在我们的语言中，就像在 Scheme 中一样，所有的绑定都是半无限 (semi-infinite) 的，意思是变量 一旦绑定，该绑定就要（至少是有可能）无限期地保留。这是因为绑定可能隐藏在已返回的 闭包之中。在半无限的语言中，垃圾回收器收集不能再访问的绑定。这只能在运行时判定， 因此我们说这是一条动态 (dynamic) 性质。

很可惜的是，“动态”有时表示“在表达式求 值期间”，有时又表示“无法事先计算”。如 果我们不允许 let 的值为过程，那么 let 绑定会在 let 主体求值结束时到期。 这叫做动态期限，而它是一条静态性质。 因为这种期限是一条静态性质，所以我们可以准确预测绑定何时可以抛弃。 ex3.28 等几道练习中的动态绑定表现类似。

3.6 消除变量名

定界算法的执行过程可以看作始自变量引用的外出旅行。在旅途中，到达对应的声明之前可 能会跨越多条等深线。跨越的等深线数目叫做变量引用的词深 (lexical depth)（或静深 (static depth)）。由于惯用“从0开始的 索引”，所以不计最后跨过的等深线。例如，在 Scheme 表达式

(lambda (x)

((lambda (a)

(x a))

x))

中，最后一行 x 的引用以及 a 的引用词深均为 0，而第三行 x 的引用词 深为 1。

因此，我们可以完全消除变量名，写成这样

(nameless-lambda

((nameless-lambda

(#1 #0))

#0))

这里，每个 nameless-lambda 都声明了一个新的无名变量，每个变量引用由其词深替 代；这个数字准确标示了要使用的声明。这些数字叫做词法地址 (lexical address) 或德布鲁金索引 (de Bruijn index)。编译器例行计算每个变量 引用的词法地址。除非用来提供调试信息，计算一旦完成，变量名即可丢弃。

这样记录信息有用，因为词法地址预测了怎样从环境中找出某个变量。

考虑我们语言中的表达式

let x = exp_1

in let y = exp_2

in -(x,y)

在差值表达式中，y 和 x 的词深分别为0和1。

现在假设在某个适当环境中求得 exp_1 和 exp_2 的值，分别为 val_1 和 val_2，那么这个表达式的值为

(value-of

<exp_1

in let y = exp_2

in -(x,y)>>

\rho)

=

(value-of

<exp_2

in -(x,y)>>

[x=val_1]\rho)

=

(value-of

<<-(x,y)>>

[y=val_2][x=val_1]\rho)

所以，求差值表达式的值时，y 深度为 0，x 深度为 1，正如词深预测的那样。

如果用关联列表表示环境（见），那么环境看起来像是

所以不论 val_1 和 val_2 值为何，x 和 y 的值都是取环境中第 1 个 元素的余项和第 0 个元素的余项。

过程的主体也是这样。考虑

let a = 5

in proc (x) -(x,1)

在过程的主体中，x 的词深是 0，a 的词深是 1。

这个表达式的值为：

(value-of

<>

\rho)

= (value-of <>

(extend-env a \lceil5\rceil \rho))

= (proc-val (procedure x <<-(x,a)>> [a=\lceil5\rceil]\rho))

这个过程的主体只能通过 apply-procedure 求值：

(apply-procedure

(procedure x <<-(x,a)>> [a=\lceil5\rceil]\rho)

\lceil7\rceil)

= (value-of <<-(x,a)>>

[x=\lceil7\rceil][a=\lceil5\rceil]\rho)

每个变量又一次出现在词深预测的环境位置。

3.7 实现词法地址

现在，我们来实现上述词法地址分析。我们写出过程 translation-of-program，它取 一程序，从声明中移除所有变量，并将每个变量引用替换为词深。

例如，程序

let x = 37

in proc (y)

let z = -(y,x)

in -(x,y)

将翻译为

#(struct:a-program

#(struct:nameless-let-exp

#(struct:const-exp 37)

#(struct:nameless-proc-exp

#(struct:nameless-let-exp

#(struct:diff-exp

#(struct:nameless-var-exp 0)

#(struct:nameless-var-exp 1))

#(struct:diff-exp

#(struct:nameless-var-exp 2)

#(struct:nameless-var-exp 1))))))

然后，我们写出新版的 value-of-program 来求无名程序的值，它不需要把变量放入 环境中。

3.7.1 翻译器

因为是写翻译器，我们得知道源语言和目标语言。目标语言中的某些部分源语言中没有，例 如 nameless-var-exp 和 nameless-let-exp；源语言中的某些部分目标语言中 没有，它们由后者中的对应结构取代，例如 var-exp 和 let-exp。

我们可以为每种语言写一个 define-datatype，也可以让二者共用一个。因为我们使 用的前端是 SLLGEN，后者更容易。我们给 SLLGEN 的语法添加生成式：

\begin{align*}\mathit{Expression} &::= %lexref \mathit{number} \\[-3pt] &\mathrel{\phantom{::=}} \fbox{nameless-var-exp (num)} \\[5pt] \mathit{Expression} &::= %let \mathit{Expression} in \mathit{Expression} \\[-3pt] &\mathrel{\phantom{::=}} \fbox{nameless-let-exp (exp1 body)} \\[5pt] \mathit{Expression} &::= %lexproc \mathit{Expression} \\[-3pt] &\mathrel{\phantom{::=}} \fbox{nameless-proc-exp (body)}\end{align*}

新的构造器名字用 % 开头，因为在我们的语言中，% 通常是注释字符。

我们的翻译器将拒绝任何含有无名结构（nameless-var-exp、nameless-let-exp 或 nameless-proc-exp）的程序。我们的解释器将拒绝任何含有原先具名结构 （var-exp、let-exp 或 proc-exp）的程序，因为它们理应被替换。

要计算任何变量引用的词法地址，我们需要它所在的作用域。这是一种上下文 (context) 信息，所以它和辅助过程和上下文参数的继承属性类似。

所以 translation-of-program 将取两个参数：一个表达式和一个静态环境 (static environment)。静态环境是一个变量列表，表示当前表达式所在的作用域。最 内部作用域声明的变量成为列表的第一个元素。

例如，翻译上例中的最后一行时，静态环境为：

(z y x)

所以，在静态环境中搜索变量就是查找它在静态环境中的位置，也就是词法地址：查得 x 为 2，y 为 1，z 为 0。

[!t]

\mathit{Senv} = \mathit{Listof}(\mathit{Sym})

\mathit{Lexaddr} = \mathit{N}

empty-senv : \mathit{()} \to \mathit{Senv}

(define empty-senv

(lambda ()

'()))

extend-senv : \mathit{Var} \times \mathit{Senv} \to \mathit{Senv}

(define extend-senv

(lambda (var senv)

(cons var senv)))

apply-senv : \mathit{Senv} \times \mathit{Var} \to \mathit{Lexaddr}

(define apply-senv

(lambda (senv var)

(cond

((null? senv)

(report-no-binding-found var))

((eqv? var (car senv))

0)

(else

(+ 1 (apply-senv (cdr senv) var))))))

实现静态环境

进入新的作用域就要给静态环境添加一个新元素。我们添加过程 extend-senv 来完成 这一步。

由于静态环境只是变量列表，这些过程很容易实现，如 所示。

翻译器有两个过程：translation-of 处理表达式，translation-of-program 处 理程序。

senv 表示一些声明，我们从中翻译表达式 e。要完成这点，我们像 或 ex2.26 那样递归复制语法树，除了

1. 调用 apply-senv，用正确的词法地址，把每个 var-exp 替换为 nameless-var-exp。

2. 把每个 let-exp 替换为一个 nameless-let-exp。新表达式的右侧由旧 表达式的右侧译得。它与原式的作用域相同，所以我们在同样的静态环境 senv 中翻 译它。新表达式的主体由旧表达式的主体译得。但是主体位于新的作用域内，多了一个绑 定变量 var。所以我们在静态环境 (extend-senv var senv) 中翻译主 体。

3. 把每个 proc-exp 替换为一个 nameless-proc-exp，主体在新的作用域 内译得，该作用域由静态环境 (extend-senv var senv) 表示。

translation-of 代码如 所示。

过程 translation-of-program 在适当的初始静态环境中执行 translation-of。

translation-of : \mathit{Exp} \times \mathit{Senv} \to \mathit{Nameless\mbox{-}exp}

(define translation-of

(lambda (exp senv)

(cases expression exp

(const-exp (num)

(const-exp num))

(diff-exp (exp1 exp2)

(diff-exp

(translation-of exp1 senv)

(translation-of exp2 senv)))

(zero?-exp (exp1)

(zero?-exp

(translation-of exp1 senv)))

(if-exp (exp1 exp2 exp3)

(if-exp

(translation-of exp1 senv)

(translation-of exp2 senv)

(translation-of exp3 senv)))

(var-exp (var)

(nameless-var-exp

(apply-senv senv var)))

(let-exp (var exp1 body)

(nameless-let-exp

(translation-of exp1 senv)

(translation-of body

(extend-senv var senv))))

(proc-exp (var body)

(nameless-proc-exp

(translation-of body

(extend-senv var senv))))

(call-exp (rator rand)

(call-exp

(translation-of rator senv)

(translation-of rand senv)))

(else

(report-invalid-source-expression exp)))))

词法地址翻译器

translation-of : \mathit{Program} \to \mathit{Nameless\mbox{-}exp}

(define translation-of-program

(lambda (pgm)

(cases program pgm

(a-program (exp1)

(a-program

(translation-of exp1 (init-senv)))))))

translation-of : \mathit{()} \to \mathit{Senv}

(define init-senv

(lambda ()

(extend-senv 'i

(extend-senv 'v

(extend-senv 'x

(empty-senv))))))

3.7.2 无名解释器

凭借词法地址分析器的预测，我们的解释器不必在运行时直接搜索变量。

由于我们的程序中没有任何变量，我们不能把变量放入环境中；但是因为我们明确知道如何 从环境中寻找它们，我们不需要！

我们的顶层过程是 run：

run : \mathit{String} \to \mathit{ExpVal}

(define run

(lambda (string)

(value-of-program

(translation-of-program

(scan&parse string)))))

我们不用全功能的环境，而是用无名环境，其接口如下：

nameless-environment?: \mathit{SchemeVal} \to \mathit{Bool}

empty-nameless-env: \mathit{()} \to \mathit{Nameless\mbox{-}env}

extend-nameless-env: \mathit{ExpVal} \times \mathit{Nameless\mbox{-}env} \to \mathit{Nameless\mbox{-}env}

apply-nameless-env: \mathit{Nameless\mbox{-}env} \times \mathit{Lexaddr} \to \mathit{DenVal}

我们可以用指代值列表实现无名环境，这样 apply-nameless-env 只需调用 list-ref。这种实现如 所示。

s3.7-eg例子中最后一行的无名环境如下

由于更改了环境接口，我们需要查看代码中所有依赖这套接口的地方。我们的解释器中使用 环境的只有两处：过程和 value-of。

修改过程规范时，只需把旧规范中的变量名移除：

(apply-procedure (procedure var body \rho) val)

= (value-of body (extend-nameless-env val \rho))

[!ht]

nameless-environment? : \mathit{SchemeVal} \to \mathit{Bool}

(define nameless-environment?

(lambda (x)

((list-of exp-val?) x)))

empty-nameless-env : \mathit{()} \to \mathit{Nameless\mbox{-}env}

(define empty-nameless-env

(lambda () '()))

extend-nameless-env : \mathit{Expval} \times \mathit{Nameless\mbox{-}env} \to \mathit{Nameless\mbox{-}env}

(define extend-nameless-env

(lambda (val nameless-env)

(cons val nameless-env)))

apply-nameless-env : \mathit{Nameless\mbox{-}env} \times \mathit{Lexaddr} \to \mathit{DenVal}

(define apply-nameless-env

(lambda (nameless-env n)

(list-ref nameless-env n)))

无名环境

这一规范的实现可定义为：

procedure : \mathit{Nameless\mbox{-}exp} \times \mathit{Nameless\mbox{-}env} \to \mathit{Proc}

(define-datatype proc proc?

(procedure

(body expression?)

(saved-nameless-env nameless-environment?)))

apply-procedure : \mathit{Proc} \times \mathit{ExpVal} \to \mathit{ExpVal}

(define apply-procedure

(lambda (proc1 val)

(cases proc proc1

(procedure

(body saved-nameless-env)

(value-of body

(extend-nameless-env val saved-nameless-env))))))

现在，我们可以写出 value-of。它的大部分与前一个解释器相同，只是原先使用 env 的地方现在用 nameless-env。但我们要处理新的部分： nameless-var-exp、nameless-let-exp 和 nameless-proc-exp，它们分别 取代对应的 var-exp、let-exp 和 proc-exp。其实现如 所示。nameless-var-exp 用于环境查询。nameless-let-exp 先求出式子右边的 exp_1，然后用式子右边的值扩展环境，并在新环境内求主体的值。这和 let 所 做相同，只是没有变量。nameless-proc 生成一个 proc，随后可供 apply-procedure 调用。

[!t]

value-of : \mathit{Nameless\mbox{-}exp} \times \mathit{Nameless\mbox{-}env} \to \mathit{ExpVal}

(define value-of

(lambda (exp nameless-env)

(cases expression exp

(const-exp (num) \ldots 同前 \ldots)

(diff-exp (exp1 exp2) \ldots 同前 \ldots)

(zero?-exp (exp1) \ldots 同前 \ldots)

(if-exp (exp1 exp2 exp3) \ldots 同前 \ldots)

(call-exp (rator rand) \ldots 同前 \ldots)

(nameless-var-exp (n)

(apply-nameless-env nameless-env n))

(nameless-let-exp

(exp1 body)

(let ((val (value-of exp1 nameless-env)))

(value-of body

(extend-nameless-env val nameless-env))))

(nameless-proc-exp (body)

(proc-val

(procedure body nameless-env)))

(else

(report-invalid-translated-expression exp)))))

无名解释器的 value-of

最后是新的 value-of-program：

value-of-program : \mathit{Nameless\mbox{-}program} \to \mathit{ExpVal}

(define value-of-program

(lambda (pgm)

(cases program pgm

(a-program (exp1)

(value-of exp1 (init-nameless-env))))))

\textnormal{[}{\star}\textnormal{]}  扩展词法地址翻译器和解释器，处理 中的 cond。

\textnormal{[}{\star}\textnormal{]}  扩展词法地址翻译器和解释器，处理 中的 unpack。

\textnormal{[}{\star}{\star}\textnormal{]}  扩展词法地址翻译器和解释器，处理 letrec。修改 translation-of 的上下文 参数，不仅记录每个绑定变量的名字，也记录变量是否由 letrec 绑定。对 letrec 绑定变量的引用，生成一种新的引用，名为 nameless-letrec-var-exp。 然后你可以继续用上面的无名环境表示，解释器则要以适当的方式处理nameless-letrec-var-exp。

\textnormal{[}{\star}{\star}\textnormal{]}  修改词法地址翻译器和解释器，像 那样处理多参数的 let 表 达式、过程和过程调用。用肋排表示法（）表示无名环境。在这种 表示法中，词法地址包含两个非负数：词深，指明跨越的等深线数目，与之前相同；位置， 指明变量在声明中的位置。

\textnormal{[}{\star}{\star}{\star}\textnormal{]}  修改词法地址翻译器和解释器，使用 中的瘦身过程表示法。要如此， 你不能在 (extend-senv var senv) 中翻译过程的主体，而是在一个新的静 态环境中，它指明了各个变量在瘦身表示中的位置。

\textnormal{[}{\star}{\star}{\star}\textnormal{]}  翻译器不止能记录变量的名字。例如，考虑程序

let x = 3

in let f = proc (y) -(y,x)

in (f 13)

这里，不必运行我们就能看出：在过程调用处，f 绑定到一个过程，其主体为 -(y,x)，x 的值与过程创建处相同。因此我们完全可以避免在环境中查找 f。扩展翻译器，记录“已知过程”，生成代码，避免在 调用这样的过程时搜索环境。

\textnormal{[}{\star}{\star}{\star}\textnormal{]} 在前一个例子中，f 的唯一用途是作为一个已知过程。因此，由表达式 proc (y) -(y,x) 产生的过程从未使用。修改翻译器，避免产生这样的过程。