NUS CS1101S：SICP JavaScript 描述：四、元语言抽象（2）-阿里云开发者社区

NUS CS1101S：SICP JavaScript 描述：四、元语言抽象（1）https://developer.aliyun.com/article/1427733

练习 4.4

回想一下，从第 1.1.6 节中得知，逻辑组合操作&&和||是条件表达式的语法糖：逻辑连接expression[1] && expression[2]是expression[1] ? expression[2] : false的语法糖，逻辑析取expression[1] || expression[2]是expression[1] ? true : expression[2]的语法糖。它们的解析如下：

《 expression[1] logical-operation expression[2] 》=
    list("logical_composition",
         "logical-operation",
         list(《 expression[1]  》, 《 expression[2]  》))

其中logical-operation是&&或||。通过声明适当的语法函数和求值函数eval_and和eval_or，将&&和||作为求值器的新语法形式。或者，展示如何将&&和||实现为派生组件。

练习 4.5

a. 在 JavaScript 中，lambda 表达式不能具有重复参数。第 4.1.1 节中的求值器没有检查这一点。

修改求值器，以便任何尝试应用具有重复参数的函数都会发出错误信号。
实现一个verify函数，检查给定程序中的任何 lambda 表达式是否包含重复参数。有了这样一个函数，我们可以在将其传递给evaluate之前检查整个程序。

为了在 JavaScript 的求值器中实现此检查，您更喜欢这两种方法中的哪一种？为什么？
b. 在 JavaScript 中，lambda 表达式的参数必须与 lambda 表达式的主体块中直接声明的名称不同（而不是在内部块中）。使用上面的首选方法来检查这一点。

练习 4.6

Scheme 语言包括一个名为let的变体。我们可以通过规定let声明隐式引入一个新的块，该块的主体包括声明和声明出现的语句序列中的所有后续语句，来近似 JavaScript 中let的行为。例如，程序

let* x = 3;
let* y = x + 2;
let* z = x + y + 5;
display(x * z);

显示 39 并且可以被视为一种简写

{
  let x = 3;
  {
    let y = x + 2;
    {
      let z = x + y + 5;
      display(x * z);
    }
  }
}

a. 在这样一个扩展的 JavaScript 语言中编写一个程序，当一些关键字let的出现被替换为let*时，其行为会有所不同。
b. 通过设计合适的标记列表表示并编写解析规则，将let*引入为一个新的语法形式。声明标记列表表示的语法谓词和选择器。
c. 假设parse实现了您的新规则，请编写一个let_star_to_nested_let函数，以转换给定程序中的任何let*的出现，如上所述。然后，通过运行evaluate(let_star_to_nested_let(p))来求值扩展语言中的程序p。
d. 作为一种替代方案，考虑通过向evaluate添加一个子句来实现let*，该子句识别新的语法形式并调用一个名为eval_let_star_declaration的函数。为什么这种方法行不通？

练习 4.7

JavaScript 支持重复执行给定语句的*while循环*。具体来说，

while (predicate) { body }

求值predicate，如果结果为true，则求值body，然后再次求值整个while循环。一旦predicate求值为false，while循环终止。

例如，回想一下第 3.1.3 节中迭代阶乘函数的命令式版本：

function factorial(n) {
    let product = 1;
    let counter = 1;
    function iter() {
        if (counter > n) {
            return product;
        } else {
            product = counter * product;
            counter = counter + 1;
            return iter();
        }
    }
    return iter();
}

我们可以使用while循环来制定相同的算法，如下所示：

function factorial(n) {
    let product = 1;
    let counter = 1;
    while (counter <= n) {
        product = counter * product;
        counter = counter + 1;
    }
    return product;
}

当循环被解析如下：

《 while (predicate) block 》 =
        list("while_loop", 《 predicate 》, 《 block 》)

a. 声明一个语法谓词和选择器来处理while循环。
b. 声明一个名为while_loop的函数，该函数接受谓词和主体作为参数，每个参数由一个没有参数的函数表示，并模拟while循环的行为。然后factorial函数如下所示：

function factorial(n) {
    let product = 1;
    let counter = 1;
    while_loop(() => counter <= n,
               () => {
                   product = counter * product;
                   counter = counter + 1;
               });
    return product;
}

你的while_loop函数应该生成一个迭代过程（参见第 1.2.1 节）。
c. 通过定义一个转换函数while_to_application，将while循环安装为一个派生组件，利用你的while_loop函数。
d. 当程序员在循环的主体内决定从包含循环的函数返回时，使用这种方法实现while循环会出现什么问题？
e. 改变你的方法来解决这个问题。直接为求值器安装while循环，使用一个名为eval_while的函数如何？
f. 遵循这种直接的方法，实现一个break;语句，它立即终止它所在的循环。
g. 实现一个predicate;语句，它只终止它所在的循环迭代，并继续求值while循环的谓词。

练习 4.8

函数主体的求值结果由其返回语句确定。继续参考脚注 9 和第 4.1.1 节中声明的求值，这个练习解决了一个问题，即由一系列语句（声明、块、表达式语句和条件语句）组成的 JavaScript 程序在任何函数主体之外的情况下应该是什么结果。

对于这样的程序，JavaScript 在产生值和不产生值的语句之间进行静态区分。（这里的“静态”意味着我们可以通过检查程序而不是运行它来进行区分。）所有声明都不产生值，所有表达式语句和条件语句都产生值。表达式语句的值是表达式的值。条件语句的值是执行的分支的值，如果该分支不产生值，则值为undefined。如果块的主体（语句序列）是产生值的，则块是产生值的，然后它的值是其主体的值。如果序列的任何组成语句是产生值的，则序列是产生值的，然后它的值是其最后产生值的组成语句的值。最后，如果整个程序不产生值，则其值为undefined。

a. 根据这个规范，以下四个程序的值是什么？

1; 2; 3;
1; { if (true) {} else { 2; } }
1; const x = 2;
1; { let x = 2; { x = x + 3; } }

b. 修改求值器以符合这个规范。

4.1.3 求值器数据结构

除了定义组件的表示形式之外，求值器实现还必须定义求值器在程序执行过程中内部操作的数据结构，例如函数和环境的表示以及true和false的表示。

谓词的测试

为了将条件语句的谓词限制为适当的谓词（求值为布尔值的表达式），我们坚持要求is_truthy函数只应用于布尔值，并且我们只接受布尔值true为真值。is_truthy的相反称为is_falsy。

function is_truthy(x) {
    return is_boolean(x)
           ? x
           : error(x, "boolean expected, received");
}
function is_falsy(x) { return ! is_truthy(x); }

表示函数

为了处理原始数据，我们假设有以下函数可用：

apply_primitive_function(fun, args)
将给定的原始函数应用于列表args中的参数值，并返回应用的结果。
is_primitive_function(fun)
测试fun是否为原始函数。

这些处理原始数据的机制在 4.1.4 节中进一步描述。

使用构造函数make_function构建复合函数，由参数、函数体和环境组成：

function make_function(parameters, body, env) {
    return list("compound_function", parameters, body, env);
}
function is_compound_function(f) {
    return is_tagged_list(f, "compound_function");
}
function function_parameters(f) { return list_ref(f, 1); }
function function_body(f) { return list_ref(f, 2); }
function function_environment(f) { return list_ref(f, 3); }

表示返回值

我们在 4.1.1 节中看到，当遇到return语句时，序列的求值终止，如果函数体的求值没有遇到return语句，则函数应用的求值需要返回值undefined。为了识别返回语句导致的值，我们引入返回值作为求值器数据结构。

function make_return_value(content) {
    return list("return_value", content);
}
function is_return_value(value) {
    return is_tagged_list(value, "return_value");
}
function return_value_content(value) {
    return head(tail(value));
}

环境操作

求值器需要操作来操作环境。如 3.2 节所述，环境是帧的序列，其中每个帧都是将符号与其对应值关联的绑定表。我们使用以下操作来操作环境：

lookup_symbol_value(symbol, env)
返回在环境env中绑定到symbol的值，如果symbol未绑定，则发出错误。
extend_environment(symbols, values, base-env)
返回一个新环境，由一个新帧组成，其中列表symbols中的符号绑定到列表values中的相应元素，封闭环境是环境base-env。
assign_symbol_value(symbol, value, env)
找到env中symbol绑定的最内层帧，并更改该帧，使symbol现在绑定到value，如果symbol未绑定，则发出错误。

为了实现这些操作，我们将环境表示为帧的列表。环境的封闭环境是列表的tail。空环境就是空列表。

function enclosing_environment(env) { return tail(env); }
function first_frame(env) { return head(env); }
const the_empty_environment = null;

每个环境的帧都表示为两个列表的对：一个是该帧中绑定的名称列表，另一个是相关值的列表。

function make_frame(symbols, values) { return pair(symbols, values); }
function frame_symbols(frame) { return head(frame); }
function frame_values(frame) { return tail(frame); }

通过将符号与值关联的新帧扩展环境，我们将一个由符号列表和值列表组成的帧添加到环境中。如果符号的数量与值的数量不匹配，则发出错误。

function extend_environment(symbols, vals, base_env) {
    return length(symbols) === length(vals)
           ? pair(make_frame(symbols, vals), base_env)
           : error(pair(symbols, vals),
                   length(symbols) < length(vals)
                   ? "too many arguments supplied"
                   : "too few arguments supplied");
}

这是在 4.1.1 节中由apply使用的，将函数的参数绑定到其参数。

要在环境中查找符号，我们扫描第一个帧中的符号列表。如果找到所需的符号，我们返回值列表中的相应元素。如果在当前帧中找不到符号，则搜索封闭环境，依此类推。如果达到空环境，则发出"未绑定的名称"错误。

function lookup_symbol_value(symbol, env) {
    function env_loop(env) {
        function scan(symbols, vals) {
            return is_null(symbols)
                   ? env_loop(enclosing_environment(env))
                   : symbol === head(symbols)
                   ? head(vals)
                   : scan(tail(symbols), tail(vals));
        }
        if (env === the_empty_environment) {
            error(symbol, "unbound name");
        } else {
            const frame = first_frame(env);
            return scan(frame_symbols(frame), frame_values(frame));
        }
    }
    return env_loop(env);
}

要在指定的环境中为符号分配新值，我们扫描符号，就像在lookup_symbol_value中一样，并在找到时更改相应的值。

function assign_symbol_value(symbol, val, env) {
    function env_loop(env) {
        function scan(symbols, vals) {
            return is_null(symbols)
                   ? env_loop(enclosing_environment(env))
                   : symbol === head(symbols)
                   ? set_head(vals, val)
                   : scan(tail(symbols), tail(vals));
        }
        if (env === the_empty_environment) {
            error(symbol, "unbound name – assignment");
        } else {
            const frame = first_frame(env);
            return scan(frame_symbols(frame), frame_values(frame));
        }
    }
    return env_loop(env);
}

这里描述的方法只是表示环境的许多合理方法中的一种。由于我们使用数据抽象来将求值器的其余部分与表示的详细选择隔离开来，如果需要，我们可以更改环境表示。（见练习 4.9。）在生产质量的 JavaScript 系统中，求值器环境操作的速度，特别是符号查找的速度，对系统的性能有重大影响。这里描述的表示虽然在概念上很简单，但并不高效，通常不会在生产系统中使用。¹⁶

练习 4.9

我们可以将框架表示为绑定的列表，其中每个绑定都是一个符号-值对，而不是将框架表示为列表对。重写环境操作以使用这种替代表示。

练习 4.10

函数lookup_symbol_value和assign_symbol_value可以用更抽象的函数来表达环境结构的遍历。定义一个捕获常见模式的抽象，并根据这个抽象重新定义这两个函数。

练习 4.11

我们的语言通过使用不同的关键字const和let区分常量和变量，并阻止对常量进行赋值。然而，我们的解释器并没有利用这种区别；函数assign_symbol_value将愉快地为给定的符号分配一个新值，而不管它是作为常量还是变量声明的。通过在尝试在赋值的左侧使用常量时调用函数error来纠正这个缺陷。您可以按照以下步骤进行：

引入谓词is_constant_declaration和is_variable_declaration，允许您区分这两种类型。如 4.1.2 节所示，parse通过使用标签"constant_declaration"和"variable_declaration"来区分它们。
更改scan_out_declarations和（如果必要）extend_environment，使常量在绑定它们的框架中与变量区分开来。
更改assign_symbol_value，使其检查给定的符号是作为变量还是常量声明的，并在后一种情况下发出错误信号，不允许对常量进行赋值操作。
更改eval_declaration，使其在遇到常量声明时调用一个新函数assign_constant_value，该函数不执行您在assign_symbol_value中引入的检查。
如果需要，更改apply以确保仍然可以对函数参数进行赋值。

练习 4.12

a. JavaScript 的规范要求实现在尝试访问名称的值之前对其声明进行求值时发出运行时错误（请参见 3.2.4 节的末尾）。为了在求值器中实现这种行为，更改lookup_symbol_value，如果它找到的值是"unassigned"，则发出错误信号。
b.同样，如果我们尚未求值其let声明，我们就不应该为变量分配新值。更改赋值的求值，以便在这种情况下，对使用let声明的变量进行赋值会发出错误信号。

练习 4.13

在我们在本书中使用的 ECMAScript 2015 的严格模式之前，JavaScript 变量的工作方式与 Scheme 变量有很大不同，这将使得将 Scheme 适应到 JavaScript 的工作变得不那么引人注目。

a.在 ECMAScript 2015 之前，JavaScript 中声明局部变量的唯一方法是使用关键字var而不是关键字let。使用var声明的变量的作用域是立即周围的函数声明或 lambda 表达式的整个主体，而不仅仅是立即封闭的块。修改scan_out_declarations和eval_block，使得使用const和let声明的名称遵循var的作用域规则。
b. 在非严格模式下，JavaScript 允许未声明的名称出现在赋值语句的=左侧。这样的赋值会将新的绑定添加到全局环境中。修改函数assign_symbol_value使赋值行为如此。严格模式禁止这样的赋值，旨在使程序更安全。通过阻止赋值向全局环境添加绑定来解决了什么安全问题？

4.1.4 作为程序运行求值器

有了求值器，我们手头上有了一个描述（用 JavaScript 表达）JavaScript 语句和表达式如何被求值的过程。将求值器表达为程序的一个优点是我们可以运行这个程序。这使我们在 JavaScript 中运行时，得到了 JavaScript 本身如何求值表达式的工作模型。这可以作为实验求值规则的框架，正如我们将在本章后面所做的那样。

我们的求值器程序最终将表达式简化为原始函数的应用。因此，我们运行求值器所需要的就是创建一个机制，调用底层 JavaScript 系统来模拟原始函数的应用。

每个原始函数名称和运算符都必须有一个绑定，这样当evaluate求值原始应用的函数表达式时，它将找到一个对象传递给apply。因此，我们建立了一个全局环境，将唯一对象与原始函数和运算符的名称相关联，这些名称可以出现在我们将要求值的表达式中。全局环境还包括undefined和其他名称的绑定，以便它们可以在要求值的表达式中用作常量。

function setup_environment() {
    return extend_environment(append(primitive_function_symbols,
                                     primitive_constant_symbols),
                              append(primitive_function_objects,
                                     primitive_constant_values),
                              the_empty_environment);
}
const the_global_environment = setup_environment();

我们如何表示原始函数对象并不重要，只要apply能够使用is_primitive_function和apply_primitive_function函数识别和应用它们。我们选择将原始函数表示为以字符串"primitive"开头并包含在底层 JavaScript 中实现该原始函数的函数的列表。

function is_primitive_function(fun) {
    return is_tagged_list(fun, "primitive");
}
function primitive_implementation(fun) { return head(tail(fun)); }

函数setup_environment将从列表中获取原始名称和实现函数：¹⁷

const primitive_functions = list(list("head", head ),
                                 list("tail", tail ),
                                 list("pair", pair ),
                                 list("is_null", is_null ),
                                 list("+", (x, y) => x + y ),
                                 〈more primitive functions〉
                                );
const primitive_function_symbols =
    map(f => head(f), primitive_functions);
const primitive_function_objects =
    map(f => list("primitive", head(tail(f))),
        primitive_functions);

与原始函数类似，我们通过函数setup_environment在全局环境中定义其他原始常量。

const primitive_constants = list(list("undefined", undefined),
                                 list("math_PI", math_PI)
                                 〈more primitive constants〉
                                );
const primitive_constant_symbols =
    map(c => head(c), primitive_constants);
const primitive_constant_values =
    map(c => head(tail(c)), primitive_constants);

要应用原始函数，我们只需使用底层 JavaScript 系统将实现函数应用于参数：¹⁸

function apply_primitive_function(fun, arglist) {
    return apply_in_underlying_javascript(
               primitive_implementation(fun), arglist);
}

为了方便运行元循环求值器，我们提供了一个驱动循环，模拟了底层 JavaScript 系统的读取-求值-打印循环。它打印一个提示符并将输入程序读取为一个字符串。它将程序字符串转换为标记列表表示的语句，如 4.1.2 节所述的过程，称为解析，由原始函数parse完成。我们在每个打印的结果之前加上一个输出提示，以区分程序的值和可能打印的其他输出。驱动循环获取前一个程序的程序环境作为参数。如 3.2.4 节末尾所述，驱动循环将程序视为在一个块中：它扫描出声明，通过包含每个名称绑定到"unassigned"的框架扩展给定的环境，并根据扩展的环境求值程序，然后将其作为参数传递给驱动循环的下一次迭代。

const input_prompt = "M-evaluate input: ";
const output_prompt = "M-evaluate value: ";
function driver_loop(env) {
    const input = user_read(input_prompt);
    if (is_null(input)) {
       display("evaluator terminated");
    } else {
       const program = parse(input);
       const locals = scan_out_declarations(program);
       const unassigneds = list_of_unassigned(locals);
       const program_env = extend_environment(locals, unassigneds, env);
       const output = evaluate(program, program_env);
       user_print(output_prompt, output);
       return driver_loop(program_env);
    }
}

我们使用 JavaScript 的prompt函数从用户那里请求并读取输入字符串：

function user_read(prompt_string) {
    return prompt(prompt_string);
}

当用户取消输入时，函数prompt返回null。我们使用一个特殊的打印函数user_print，以避免打印复合函数的环境部分，这可能是一个非常长的列表（甚至可能包含循环）。

function user_print(string, object) {
    function prepare(object) {
        return is_compound_function(object)
               ? "< compound-function >"
               : is_primitive_function(object)
               ? "< primitive-function >"
               : is_pair(object)
               ? pair(prepare(head(object)),
                      prepare(tail(object)))
               : object;
    }
    display(string + " " + stringify(prepare(object)));
}

现在我们需要做的就是初始化全局环境并启动驱动程序循环来运行求值器。以下是一个示例交互：

const the_global_environment = setup_environment();
driver_loop(the_global_environment);

M-求值输入：

function append(xs, ys) {
    return is_null(xs)
           ? ys
           : pair(head(xs), append(tail(xs), ys));
}

M-求值值：

undefined

M-求值输入：

append(list("a", "b", "c"), list("d", "e", "f"));

M-求值值：

["a", ["b", ["c", ["d", ["e", ["f", null]]]]]]

练习 4.14

Eva Lu Ator 和 Louis Reasoner 各自对元循环求值器进行实验。Eva 输入了map的定义，并运行了一些使用它的测试程序。它们都很好。相比之下，Louis 安装了map的系统版本作为元循环求值器的原语。当他尝试时，事情变得非常糟糕。解释为什么 Louis 的map失败，即使 Eva 的工作正常。

4.1.5 数据作为程序

在考虑一个求值 JavaScript 语句和表达式的 JavaScript 程序时，类比可能会有所帮助。程序含义的一个操作视图是，程序是对一个抽象（也许是无限大的）机器的描述。例如，考虑计算阶乘的熟悉程序：

function factorial(n) {
    return n === 1
           ? 1
           : factorial(n - 1) * n;
}

我们可以将这个程序看作是一个包含递减、乘法和相等测试部分的机器的描述，还有一个两位置开关和另一个阶乘机器。（阶乘机器是无限的，因为它包含另一个阶乘机器。）图 4.3 是阶乘机器的流程图，显示了部件如何连接在一起。

图 4.3 阶乘程序，视为一个抽象机器。

以类似的方式，我们可以将求值器视为一个非常特殊的机器，它以描述一个机器作为输入。根据这个输入，求值器配置自身以模拟所描述的机器。例如，如果我们向求值器提供factorial的定义，如图 4.4 所示，求值器将能够计算阶乘。

图 4.4 求值器模拟阶乘机器。

从这个角度来看，我们的求值器被视为通用机器。当这些机器被描述为 JavaScript 程序时，它模仿其他机器。¹⁹这是令人震惊的。试着想象一个类似的电路求值器。这将是一个电路，它以编码其他电路计划的信号作为输入，比如一个滤波器。给定这个输入，电路求值器将表现得像一个具有相同描述的滤波器。这样一个通用电路几乎是难以想象的复杂。值得注意的是，程序求值器是一个相当简单的程序。²⁰

求值器的另一个引人注目的方面是，它充当了我们编程语言中操作的数据对象和编程语言本身之间的桥梁。想象一下，求值器程序（用 JavaScript 实现）正在运行，用户正在向求值器输入程序并观察结果。从用户的角度来看，输入程序如x * x;是编程语言中的一个程序，求值器应该执行它。然而，从求值器的角度来看，程序只是一个字符串，或者在解析后是一个标记列表表示，根据一套明确定义的规则进行操作。

用户的程序是求值器的数据并不一定会引起混淆。事实上，有时忽略这种区别并给用户明确地将一个字符串作为 JavaScript 语句进行求值的能力是很方便的，使用 JavaScript 的原始函数eval，它以字符串作为参数。它解析字符串，并且——只要它在语法上是正确的——在eval应用的环境中求值所得到的表示。因此，

eval("5 * 5;");

和

evaluate(parse("5 * 5;"), the_global_environment);

都将返回 25。²¹

练习 4.15

给定一个一参数函数f和一个对象a，如果求值表达式f(a)返回一个值（而不是以错误消息终止或永远运行），则称f在a上“停止”。证明不可能编写一个函数halts，它可以正确地确定对于任何函数f和对象a，f是否在a上停止。使用以下推理：如果你有这样一个函数halts，你可以实现以下程序：

function run_forever() { return run_forever(); }
function strange(f) {
    return halts(f, f)
           ? run_forever();
           : "halted";
}

现在考虑求值表达式strange(strange)并展示任何可能的结果（无论是停止还是永远运行）都违反了halts的预期行为。

4.1.6 内部声明

在 JavaScript 中，声明的作用域是紧邻声明的整个块，而不仅仅是从声明发生的地方开始的块的部分。本节将更详细地讨论这个设计选择。

让我们重新审视第 3.2.4 节中在函数f的主体中本地声明的相互递归函数is_even和is_odd。

function f(x) {
    function is_even(n) {
        return n === 0
               ? true
               : is_odd(n - 1);
    }
    function is_odd(n) {
        return n === 0
               ? false
               : is_even(n - 1);
    }
    return is_even(x);
}

我们的意图是，函数is_even主体中的名称is_odd应该指的是在is_even之后声明的函数is_odd。名称is_odd的作用域是f的整个主体块，而不仅仅是从is_odd的声明发生的地方开始的f主体的部分。事实上，当我们考虑is_odd本身是根据is_even定义的时候——所以is_even和is_odd是相互递归的函数——我们看到这两个声明的唯一令人满意的解释是将它们视为is_even和is_odd同时添加到环境中。更一般地，在块结构中，局部名称的作用域是在求值声明的整个块中。

在第 4.1.1 节的元循环求值器中，块的求值通过扫描块中的声明并使用包含所有声明名称绑定的帧扩展当前环境来实现局部名称的同时作用域。因此，在求值块体的新环境中已经包含了is_even和is_odd的绑定，任何一个这些名称的出现都指向正确的绑定。一旦它们的声明被求值，这些名称就绑定到它们声明的值，即具有扩展环境作为环境部分的函数对象。因此，例如，当is_even在f的主体中被应用时，它的环境已经包含了符号is_odd的正确绑定，而在is_even的主体中求值名称is_odd会检索到正确的值。

练习 4.16

考虑第 1.3.2 节中的函数f_3：

function f_3(x, y) {
    const a = 1 + x * y;
    const b = 1 - y;
    return x * square(a) + y * b + a * b;
}

a. 绘制在求值f_3的返回表达式期间生效的环境的图表。
b. 在求值函数应用时，求值器创建两个帧：一个用于参数，一个用于在函数的主体块中直接声明的名称，而不是在内部块中声明的名称。由于所有这些名称具有相同的作用域，一个实现可以合并这两个帧。更改求值器，使得对主体块的求值不会创建新的帧。您可以假设这不会导致帧中出现重复的名称（练习 4.5 证明了这一点）。

练习 4.17

Eva Lu Ator 正在编写程序，其中函数声明和其他语句是交错的。她需要确保在应用函数之前对声明进行求值。她抱怨道：“为什么求值器不能处理这个琐事，并且将所有函数声明提升到它们出现的块的开头？块外的函数声明应该提升到程序的开头。”

a. 修改求值器以遵循 Eva 的建议。
b. JavaScript 的设计者决定遵循 Eva 的方法。讨论这个决定。
c. 此外，JavaScript 的设计者决定允许使用赋值重新分配函数声明的名称。相应地修改您的解决方案并讨论这一决定。

练习 4.18

在我们的解释器中，递归函数是通过一种迂回的方式获得的：首先声明将引用递归函数的名称，并将其分配给特殊值"unassigned"；然后在该名称的范围内定义递归函数；最后将定义的函数分配给名称。当递归函数被应用时，主体中名称的任何出现都会正确地引用递归函数。令人惊讶的是，可以在不使用声明或赋值的情况下指定递归函数。以下程序通过应用递归阶乘函数计算 10 的阶乘：²³

(n => (fact => fact(fact, n))
      ((ft, k) => k === 1
                  ? 1
                  : k * ft(ft, k - 1)))(10);

a. 通过求值表达式来检查这确实计算了阶乘。为计算斐波那契数设计一个类似的表达式。
b. 考虑上面给出的函数f：

function f(x) {
    function is_even(n) {
        return n === 0
               ? true
               : is_odd(n - 1);
    }
    function is_odd(n) {
        return n === 0
               ? false
               : is_even(n - 1);
    }
    return is_even(x);
}

填写缺失的表达式以完成对f的替代声明，该声明没有内部函数声明：

function f(x) {
    return ((is_even, is_odd) => is_even(is_even, is_odd, x))
           ((is_ev, is_od, n) => n === 0 ? true : is_od(〈??〉, 〈??〉, 〈??〉),
            (is_ev, is_od, n) => n === 0 ? false : is_ev( 〈??〉, 〈??〉, 〈??〉));
}

顺序声明处理

我们 4.1.1 节的求值器设计对块的求值施加了运行时负担：它需要扫描块的主体以查找本地声明的名称，使用绑定这些名称的新框架扩展当前环境，并在此扩展环境中求值块主体。或者，块的求值可以使用空框架扩展当前环境。然后，块主体中每个声明的求值将向该框架添加一个新的绑定。为了实现这一设计，我们首先简化eval_block：

function eval_block(component, env) {
    const body = block_body(component);
    return evaluate(body, extend_environment(null, null, env);
}

函数eval_declaration不再能假定环境已经为该名称绑定。它不再使用assign_symbol_value来更改现有绑定，而是调用一个新函数add_binding_to_frame，将名称绑定到值表达式的值的第一个框架中的环境中。

function eval_declaration(component, env) {
    add_binding_to_frame(
        declaration_symbol(component),
        evaluate(declaration_value_expression(component), env),
        first_frame(env));
    return undefined;
}
function add_binding_to_frame(symbol, value, frame) {
    set_head(frame, pair(symbol, head(frame)));
    set_tail(frame, pair(value, tail(frame)));
}

顺序声明处理后，声明的范围不再是直接包围声明的整个块，而只是从声明发生的地方开始的块的一部分。尽管我们不再具有同时的范围，但顺序声明处理将正确地求值本节开头的函数f的调用，但出于“意外”的原因：由于内部函数的声明首先出现，直到所有这些函数都声明完毕之前，不会求值对这些函数的任何调用。因此，is_odd在执行is_even时已经被声明。实际上，对于任何内部声明首先出现在主体中且声明的值表达式的求值实际上不使用任何声明的名称的函数，顺序声明处理将给出与我们在 4.1.1 节中的扫描名称求值器相同的结果。练习 4.19 展示了一个不遵守这些限制的函数的示例，因此替代求值器与我们的扫描名称求值器并不等价。

顺序声明处理比扫描名称更高效且更易于实现。但是，使用顺序处理时，名称引用的声明可能取决于求值块中语句的顺序。在练习 4.19 中，我们看到对于是否希望这样做的观点可能会有不同。

练习 4.19

Ben Bitdiddle，Alyssa P. Hacker 和 Eva Lu Ator 正在就求值程序的期望结果进行争论

const a = 1;
function f(x) {
    const b = a + x;
    const a = 5;
    return a + b;
}
f(10);

Ben 断言应该使用声明的顺序处理结果：b被声明为 11，然后a被声明为 5，因此结果是 16。Alyssa 反对相互递归需要内部函数声明的同时作用规则，并且认为将函数名称与其他名称区别对待是不合理的。因此，她主张在第 4.1.1 节中实现的机制。这将导致在计算b的值时，a尚未被赋值。因此，在 Alyssa 看来，该函数应该产生错误。Eva 有第三种观点。她说，如果a和b的声明确实是同时的，那么在计算b时应该使用a的值 5。因此，在 Eva 看来，a应该是 5，b应该是 15，结果应该是 20。你支持这些观点中的哪一个（如果有的话）？你能想出一种实现内部声明的方法，使其符合 Eva 的期望吗？

4.1.7 将语法分析与执行分离

上面实现的求值器很简单，但非常低效，因为组件的语法分析与其执行交织在一起。因此，如果一个程序被执行多次，它的语法将被分析多次。例如，考虑使用以下factorial定义来求值factorial(4)：

function factorial(n) {
    return n === 1
           ? 1
           : factorial(n - 1) * n;
}

每次调用factorial时，求值器必须确定函数体是条件表达式并提取谓词。只有这样才能求值谓词并根据其值进行分派。每次求值表达式factorial(n - 1) * n或子表达式factorial(n - 1)和n - 1时，求值器必须执行evaluate中的情况分析，以确定表达式是一个应用程序，并必须提取其函数表达式和参数表达式。这种分析是昂贵的。重复执行它是浪费的。

我们可以通过安排事物，使得语法分析只执行一次，从而使求值器变得更加高效。我们将evaluate分成两部分，analyze函数只接受组件。它执行语法分析并返回一个新函数，执行函数，它封装了执行分析组件所需的工作。执行函数以环境作为参数并完成求值。这样做可以节省工作，因为analyze只会在组件上调用一次，而执行函数可能会被多次调用。

通过将分析和执行分开，evaluate现在变成了

function evaluate(component, env) {
    return analyze(component)(env);
}

调用analyze的结果是要应用于环境的执行函数。analyze函数与第 4.1.1 节中的原始evaluate执行的情况分析相同，只是我们分派的函数只执行分析，而不是完全求值。

function analyze(component) {
    return is_literal(component)
           ? analyze_literal(component)
           : is_name(component)
           ? analyze_name(component)
           : is_application(component)
           ? analyze_application(component)
           : is_operator_combination(component)
           ? analyze(operator_combination_to_application(component))
           : is_conditional(component)
           ? analyze_conditional(component)
           : is_lambda_expression(component)
           ? analyze_lambda_expression(component)
           : is_sequence(component)
           ? analyze_sequence(sequence_statements(component))
           : is_block(component)
           ? analyze_block(component)
           : is_return_statement(component)
           ? analyze_return_statement(component)
           : is_function_declaration(component)
           ? analyze(function_decl_to_constant_decl(component))
           : is_declaration(component)
           ? analyze_declaration(component)
           : is_assignment(component)
           ? analyze_assignment(component)
           : error(component, "unknown syntax – analyze");
}

这是最简单的语法分析函数，处理文字表达式。它返回一个执行函数，忽略其环境参数，只返回文字的值。

function analyze_literal(component) {
    return env => literal_value(component);
}

查找名称的值仍然必须在执行阶段完成，因为这取决于知道环境。

function analyze_name(component) {
    return env => lookup_symbol_value(symbol_of_name(component), env);
}

分析一个应用程序，我们分析函数表达式和参数表达式，并构造一个执行函数，该函数调用函数表达式的执行函数（以获取要应用的实际函数）和参数表达式的执行函数（以获取实际参数）。然后我们将这些传递给execute_application，这类似于第 4.1.1 节中的apply。execute_application函数与apply不同之处在于，复合函数的函数体已经被分析过，因此不需要进行进一步的分析。相反，我们只需在扩展环境上调用函数体的执行函数。

function analyze_application(component) {
    const ffun = analyze(function_expression(component));
    const afuns = map(analyze, arg_expressions(component));
    return env => execute_application(ffun(env),
                                      map(afun => afun(env), afuns));
}
function execute_application(fun, args) {
    if (is_primitive_function(fun)) {
        return apply_primitive_function(fun, args);
    } else if (is_compound_function(fun)) {
        const result = function_body(fun)
                       (extend_environment(function_parameters(fun),
                                           args,
                                           function_environment(fun)));
        return is_return_value(result)
               ? return_value_content(result)
               : undefined;
    } else {
        error(fun, "unknown function type – execute_application");
    }
}

对于条件语句，我们在分析时提取并分析谓词、结果和替代。

function analyze_conditional(component) {
    const pfun = analyze(conditional_predicate(component));
    const cfun = analyze(conditional_consequent(component));
    const afun = analyze(conditional_alternative(component));
    return env => is_truthy(pfun(env)) ? cfun(env) : afun(env);
}

分析 lambda 表达式也实现了效率的主要提升：我们只对 lambda 主体进行一次分析，即使由 lambda 表达式的求值产生的函数可能被多次应用。

function analyze_lambda_expression(component) {
    const params = lambda_parameter_symbols(component);
    const bfun = analyze(lambda_body(component));
    return env => make_function(params, bfun, env);
}

对一系列语句的分析更为复杂。序列中的每个语句都经过分析，产生一个执行函数。这些执行函数组合在一起，产生一个接受环境作为参数并按顺序调用每个单独执行函数的执行函数。

function analyze_sequence(stmts) {
    function sequentially(fun1, fun2) {
        return env => {
                   const fun1_val = fun1(env);
                   return is_return_value(fun1_val)
                          ? fun1_val
                          : fun2(env);
               };
    }
    function loop(first_fun, rest_funs) {
        return is_null(rest_funs)
               ? first_fun
               : loop(sequentially(first_fun, head(rest_funs)),
                      tail(rest_funs));
    }
    const funs = map(analyze, stmts);
    return is_null(funs)
           ? env => undefined
           : loop(head(funs), tail(funs));
}

块的主体只被扫描一次以获取局部声明。当调用块的执行函数时，这些绑定将被安装在环境中。

function analyze_block(component) {
    const body = block_body(component);
    const bfun = analyze(body);
    const locals = scan_out_declarations(body);
    const unassigneds = list_of_unassigned(locals);
    return env => bfun(extend_environment(locals, unassigneds, env));
}

对于返回语句，我们分析返回表达式。返回语句的执行函数只是调用返回表达式的执行函数，并将结果包装在返回值中。

function analyze_return_statement(component) {
    const rfun = analyze(return_expression(component));
    return env => make_return_value(rfun(env));
}

函数analyze_assignment必须推迟实际设置变量，直到执行时才会提供环境。然而，分析赋值值表达式（递归地）在分析期间是效率的主要提升，因为赋值值表达式现在只会被分析一次。对于常量和变量声明也是如此。

function analyze_assignment(component) {
    const symbol = assignment_symbol(component);
    const vfun = analyze(assignment_value_expression(component));
    return env => {
               const value = vfun(env);
               assign_symbol_value(symbol, value, env);
               return value;
           };
}
function analyze_declaration(component) {
    const symbol = declaration_symbol(component);
    const vfun = analyze(declaration_value_expression(component));
    return env => {
               assign_symbol_value(symbol, vfun(env), env);
               return undefined;
           };
}

我们的新求值器使用与 4.1.2、4.1.3 和 4.1.4 节中相同的数据结构、语法函数和运行时支持函数。

练习 4.20

扩展本节中的求值器以支持while循环。（见练习 4.7。）

练习 4.21

Alyssa P. Hacker 不明白为什么analyze_sequence需要这么复杂。所有其他分析函数都是相应求值函数（或 4.1.1 节中的evaluate子句）的直接转换。她期望analyze_sequence看起来像这样：

function analyze_sequence(stmts) {
    function execute_sequence(funs, env) {
        if (is_null(funs)) {
            return undefined;
        } else if (is_null(tail(funs))) {
            return head(funs)(env);
        } else {
            const head_val = head(funs)(env);
            return is_return_value(head_val)
                   ? head_val
                   : execute_sequence(tail(funs), env);
        }
    }
    const funs = map(analyze, stmts);
    return env => execute_sequence(funs, env);
}

Eva Lu Ator 向 Alyssa 解释，文本中的版本在分析时更多地求值了序列的工作。Alyssa 的序列执行函数不是内置调用各个执行函数，而是按顺序循环调用这些函数：实际上，尽管序列中的各个语句已经被分析，但序列本身还没有被分析。

比较analyze_sequence的两个版本。例如，考虑常见情况（函数体的典型情况），即序列只有一个语句。Alyssa 程序生成的执行函数会做什么工作？上述文本中程序生成的执行函数又会做什么工作？这两个版本在包含两个表达式的序列中如何比较？

练习 4.22

设计并进行一些实验，比较原始的元循环求值器与本节中的版本的速度。使用你的结果来估计在各种函数中分析与执行所花费的时间比例。

4.2 惰性求值

现在我们有了一个表达为 JavaScript 程序的求值器，我们可以通过修改求值器来实验语言设计的替代选择。事实上，新语言通常是通过首先编写一个将新语言嵌入到现有高级语言中的求值器来发明的。例如，如果我们希望与 JavaScript 社区的其他成员讨论对 JavaScript 的某个修改方面，我们可以提供一个体现了这种改变的求值器。接收者可以使用新的求值器进行实验，并发送评论作为进一步的修改。高级实现基础不仅使得测试和调试求值器更容易；此外，嵌入使得设计者能够从基础语言中吸取特性，就像我们嵌入的 JavaScript 求值器使用了基础 JavaScript 的原语和控制结构一样。设计者只有在以后（如果有必要）才需要费力地在低级语言或硬件中构建完整的实现。在本节和下一节中，我们将探讨一些提供显著额外表达能力的 JavaScript 变体。

4.2.1 正常顺序和应用顺序

在第 1.1 节，我们开始讨论求值模型时，我们注意到 JavaScript 是一种 应用顺序 语言，也就是说，当函数被应用时，JavaScript 函数的所有参数都会被求值。相反，正常顺序 语言会延迟求值函数参数，直到实际参数值被需要为止。延迟求值函数参数直到最后可能的时刻（例如，直到它们被原始操作所需）被称为延迟求值。²⁹ 考虑函数

function try_me(a, b) {
    return a === 0 ? 1 : b;
}

在 JavaScript 中求值try_me(0, head(null));会导致错误。使用延迟求值，就不会出现错误。求值该语句将返回 1，因为参数head(null)永远不会被求值。

利用延迟求值的一个例子是声明一个函数unless

function unless(condition, usual_value, exceptional_value) {
    return condition ? exceptional_value : usual_value;
}

可以在诸如下面的语句中使用

unless(is_null(xs), head(xs), display("error: xs should not be null"));

这在应用顺序语言中不起作用，因为在调用unless之前通常值和异常值都会被求值（参见练习 1.6）。延迟求值的一个优点是，一些函数，比如unless，即使求值它们的一些参数会产生错误或不会终止，也可以进行有用的计算。

如果在求值参数之前进入函数体，则我们说该函数对该参数是 非严格 的。如果在进入函数体之前求值参数，则我们说该函数对该参数是严格的。³⁰ 在纯粹的应用顺序语言中，所有函数对每个参数都是严格的。在纯粹的正常顺序语言中，所有复合函数对每个参数都是非严格的，原始函数可以是严格的也可以是非严格的。还有一些语言（参见练习 4.29）允许程序员对他们定义的函数的严格性进行详细控制。

一个引人注目的例子是一个可以有用地变为非严格的函数pair（或者一般来说，几乎任何数据结构的构造函数）。即使元素的值未知，也可以进行有用的计算，将元素组合成数据结构并对生成的数据结构进行操作。例如，计算列表的长度而不知道列表中各个元素的值是完全有意义的。我们将在第 4.2.3 节中利用这个想法，将第 3 章的流实现为由非严格对组成的列表。

练习 4.23

假设（在普通的应用顺序 JavaScript 中）我们按上面所示定义unless，然后根据unless定义factorial如下

function factorial(n) {
    return unless(n === 1,
                  n * factorial(n - 1),
                  1);
}

如果我们尝试求值factorial(5)会发生什么？我们的函数在正常顺序语言中会工作吗？

练习 4.24

Ben Bitdiddle 和 Alyssa P. Hacker 对于实现诸如unless之类的惰性求值的重要性存在分歧。Ben 指出可以在应用序中实现unless作为一个语法形式。Alyssa 反驳说，如果这样做，unless将只是语法，而不是可以与高阶函数一起使用的函数。在这个论点的双方填写细节。展示如何将unless实现为一个派生组件（类似于操作符组合），通过在evaluate中捕获函数表达式为unless的应用。给出一个可能有用的情况的例子，其中unless作为函数而不是语法形式可用。

4.2.2 惰性求值的解释器

而不仅仅是evaluate，我们使用

基本思想是，在应用函数时，解释器必须确定哪些参数需要求值，哪些需要延迟。延迟的参数不会被求值；相反，它们会被转换为称为thunk的对象。thunk 必须包含在需要时产生参数值所需的信息，就好像它在应用时已经被求值一样。因此，thunk 必须包含参数表达式和函数应用被求值的环境。

在 thunk 中求值表达式的过程称为forcing。通常情况下，只有在需要其值时才会强制执行 thunk：当它被传递给将使用 thunk 值的原始函数时；当它是条件语句的谓词的值时；当它是即将被应用为函数的函数表达式的值时。我们可以选择是否对 thunk 进行记忆化，类似于第 3.5.1 节中对流的优化。使用记忆化时，第一次强制执行 thunk 时，它会存储计算出的值。后续的强制执行只需返回存储的值，而不重复计算。我们将使我们的解释器进行记忆化，因为这对许多应用来说更有效率。然而，这里有一些棘手的考虑。

修改求值器

惰性求值和第 4.1 节中的求值器在evaluate和apply中对函数应用的处理上的主要区别。

evaluate的is_application子句变成

: is_application(component)
? apply(actual_value(function_expression(component), env),
        arg_expressions(component), env)

这几乎与第 4.1.1 节中evaluate的is_application子句相同。然而，对于惰性求值，我们调用apply并传入参数表达式，而不是对它们进行求值后产生的参数。由于如果参数需要延迟，我们将需要环境来构造 thunk，因此我们也必须传递环境。我们仍然求值函数表达式，因为apply需要实际的函数来进行分派（原始函数与复合函数）并应用它。

在这一节中，我们将实现一个与 JavaScript 相同的正常顺序语言，只是每个参数中的复合函数是非严格的。原始函数仍然是严格的。修改第 4.1.1 节的求值器，使其解释的语言以这种方式运行并不困难。几乎所有所需的更改都集中在函数应用周围。

function actual_value(exp, env) {
   return force_it(evaluate(exp, env));
}

来代替，这样如果表达式的值是 thunk，它将被强制执行。

我们的新版本的apply也几乎与第 4.1.1 节中的版本相同。不同之处在于evaluate传入了未求值的参数表达式：对于原始函数（严格的），我们在应用原始函数之前求值所有参数；对于复合函数（非严格的），我们在应用函数之前延迟所有参数。

function apply(fun, args, env) {
    if (is_primitive_function(fun)) {
        return apply_primitive_function(
                   fun,
                   list_of_arg_values(args, env));              // changed
    } else if (is_compound_function(fun)) {
        const result = evaluate(
                           function_body(fun),
                           extend_environment(
                               function_parameters(fun),
                               list_of_delayed_args(args, env), // changed
                               function_environment(fun)));
        return is_return_value(result)
               ? return_value_content(result)
               : undefined;
    } else {
        error(fun, "unknown function type – apply");
    }
}

处理参数的函数与 4.1.1 节中的list_of_values几乎相同，只是list_of_delayed_args延迟参数而不是求值它们，而list_of_arg_values使用actual_value而不是evaluate：

function list_of_arg_values(exps, env) {
    return map(exp => actual_value(exp, env), exps);
}
function list_of_delayed_args(exps, env) {
    return map(exp => delay_it(exp, env), exps);
}

我们必须更改求值器的另一个地方是在处理条件语句时，我们必须使用actual_value而不是evaluate来获取谓词表达式的值，然后再测试它是真还是假：

function eval_conditional(component, env) {
    return is_truthy(actual_value(conditional_predicate(component), env))
           ? evaluate(conditional_consequent(component), env)
           : evaluate(conditional_alternative(component), env);
}

最后，我们必须更改driver_loop函数（来自 4.1.4 节），以使用actual_value而不是evaluate，这样如果延迟的值传播回读取-求值-打印循环，它将在打印之前被强制。我们还更改提示，指示这是惰性求值器：

const input_prompt = "L-evaluate input: ";
const output_prompt = "L-evaluate value: ";
function driver_loop(env) {
    const input = user_read(input_prompt);
    if (is_null(input)) {
        display("evaluator terminated");
    } else {
        const program = parse(input);
        const locals = scan_out_declarations(program);
        const unassigneds = list_of_unassigned(locals);
        const program_env = extend_environment(locals, unassigneds, env);
        const output = actual_value(program, program_env);
        user_print(output_prompt, output);
        return driver_loop(program_env);
    }
}

做出这些更改后，我们可以启动求值器并对其进行测试。成功求值 4.2.1 节中讨论的try_me表达式表明解释器正在执行惰性求值：

const the_global_environment = setup_environment(); driver_loop(the_global_environment);

左求值输入：

function try_me(a, b) {
    return a === 0 ? 1 : b;
}

左求值值：

undefined