2.1. 环境数据结构¶

在纯 \(\lambda\)-演算解释器中：

在求值函数调用时，实参（的值）实际上会被 替换 到函数体中， 取代形参（具体取决于归约策略：正则序还是应用序）。

在我们这个应用型 \(\lambda\)-演算解释器中：

我们保证替换仍然是推理函数行为的一种有效方式，但在解释器的实现 中，我们不再采用 替换模型 ，而是采用 基于环境的求值模型 ， 其中值被绑定到标识符（变量名）。

从概念上讲，环境是一组（可能为空的）变量-值对。我们将把这个 集合本身以及其中的每一对都表示为一个数组。例如：

E = [ ]    // the empty environment

E = [ ["y",4], ["x",5], ["f",<sqr_fn>] ]
           // the environment in which y is bound to 4
           //                          x is bound to 5
           //                          f is bound to the squaring function

实际上，环境不止一个，因为作用域不止一个。例如，变量 “x” 可能 在一个作用域中绑定到值 5，而在另一个作用域中绑定到平方函数。

在 JavaScript 中，每个函数都定义自己的作用域。由于函数定义可以 嵌套在其他函数内部，作用域（以及环境）也可以嵌套。我们将使用 嵌套数组来表示环境的这种层次结构。例如，对于下面这段 JavaScript 代码：

function f(x,y) {
  return function (x) {
      return function (y,z) {
         // compute with x,y,z (**)
       };
    };
}
var id = function (x) { return x; };
f(1,2)("hi")(true, id);

其环境对应的嵌套数组将是：

[ "Env",                  // our usual tag

  [ ["y",true],           // the set of bindings in the innermost scope,
    ["z",id]],            // i.e., the top of the stack of environments

  [ "Env",                // the sets of bindings in all of the outer scopes,
                          // i.e.,the rest of the stack of environments
    [["x","hi"]],         //          .
                          //          .
    [ "Env",              //          .
      [["x",1],["y",2]],  //          .
      ["EmptyEnv"]]]]     //          .

环境包含变量到值的绑定。整数是一类值。但函数抽象又是怎样一类 值呢？

它是一个函数定义，包含形参列表、函数体，以及一个 闭包 （closure） ——闭包把一个匿名函数定义与当前环境（即函数定义时存在的那个环境） 打包在一起。

在编程语言中， 指称值 （denoted value）是任何可以绑定到变量名 的值。因此， 环境 不过是从标识符（例如 “x” 和 “g”）到指称值 的映射。

指称值的类型因编程语言而异。在 SLang 1 中，指称值只有两种类型： 数值和闭包。

像往常一样，我们用数组来表示这些指称值，其第一个元素分别是标签 “Num” 或 “Clo”。

这意味着，如果我们严格遵循上面 E1 中环境的表示方式，就应该 把 5 到 “x” 的绑定写成：

[ "x", [ "Num", 5 ] ]

而不是

[ "x", 5 ]

2.2. 确定变量所绑定的值¶

下面的问题让你练习确定 SLang 1 中某个变量绑定到哪个值。要获得 这道题的学分，你必须连续三次正确完成这个随机化问题。

2.3. 在环境中对表达式求值¶

下面的问题让你练习对 SLang 1 表达式进行完整求值。要获得这道题 的学分，你必须连续三次正确完成这个随机化问题。

2.4. 确定 SLang 1 中的指称值¶

下面的问题让你练习 SLang 1 解释器中的指称值。要获得这道题的学分， 你必须连续三次正确完成这个随机化问题。