NUS CS1101S：SICP JavaScript 描述：五、使用寄存器机进行计算（3）https://developer.aliyun.com/article/1427744
编译块
通过在块的编译体之前添加一个assign指令来编译块。该赋值通过将在块中声明的名称绑定到值"unassigned"的帧扩展了当前环境。这个操作既需要又修改了env寄存器。
function compile_block(stmt, target, linkage) { const body = block_body(stmt); const locals = scan_out_declarations(body); const unassigneds = list_of_unassigned(locals); return append_instruction_sequences( make_instruction_sequence(list("env"), list("env"), list(assign("env", list(op("extend_environment"), constant(locals), constant(unassigneds), reg("env"))))), compile(body, target, linkage)); }
编译 lambda 表达式
Lambda 表达式构造函数。lambda 表达式的对象代码必须具有以下形式
〈construct function object and assign it to target register〉 〈linkage〉
编译 lambda 表达式时，我们还会生成函数体的代码。虽然在函数构造时不会执行函数体，但是将其插入到对象代码中 lambda 表达式的代码之后是很方便的。如果 lambda 表达式的链接是一个标签或者"return"，那么这样做是可以的。但是如果链接是"next"，我们需要通过跳转到函数体之后插入的标签的链接来跳过函数体的代码。因此，对象代码的形式如下
〈construct function object and assign it to target register〉 〈code for given linkage〉 or go_to(label("after_lambda")) 〈compilation of function body〉 "after_lambda"
函数 compile_lambda_expression 生成构造函数对象的代码，然后是函数体的代码。函数对象将在运行时通过将当前环境（声明点的环境）与编译函数体的入口点（新生成的标签）组合来构造。
function compile_lambda_expression(exp, target, linkage) { const fun_entry = make_label("entry"); const after_lambda = make_label("after_lambda"); const lambda_linkage = linkage === "next" ? after_lambda : linkage; return append_instruction_sequences( tack_on_instruction_sequence( end_with_linkage(lambda_linkage, make_instruction_sequence(list("env"), list(target), list(assign(target, list(op("make_compiled_function"), label(fun_entry), reg("env")))))), compile_lambda_body(exp, fun_entry)), after_lambda); }
函数compile_lambda_expression使用特殊的组合器tack_on_ instruction_sequence（来自 5.5.4 节）而不是append_instruction_ sequences来将函数体附加到 lambda 表达式代码中，因为函数体不是将在进入组合序列时执行的指令序列的一部分；相反，它只是在序列中，因为那是一个方便的放置位置。
函数compile_lambda_body构造函数主体的代码。此代码以入口点的标签开头。接下来是指令，这些指令将导致运行时求值环境切换到正确的环境，以求值函数主体——即函数的环境，扩展为包括参数与调用函数时的参数的绑定。之后是函数主体的代码，增强以确保它以返回语句结束。增强的主体使用目标val进行编译，以便其返回值将被放置在val中。传递给此编译的链接描述符是无关紧要的，因为它将被忽略。⁴⁴由于需要链接参数，我们随意选择了"next"。
function compile_lambda_body(exp, fun_entry) { const params = lambda_parameter_symbols(exp); return append_instruction_sequences( make_instruction_sequence(list("env", "fun", "argl"), list("env"), list(fun_entry, assign("env", list(op("compiled_function_env"), reg("fun"))), assign("env", list(op("extend_environment"), constant(params), reg("argl"), reg("env"))))), compile(append_return_undefined(lambda_body(exp)), "val", "next")); }
为了确保所有函数最终都通过执行返回语句结束，compile_lambda_body在 lambda 主体中附加了一个返回语句，其返回表达式是文字undefined。为此，它使用函数append_return_ undefined，该函数构造了解析器的标记列表表示（来自 4.1.2 节）的序列，其中包括主体和一个return undefined;语句。
function append_return_undefined(body) { return list("sequence", list(body, list("return_statement", list("literal", undefined)))); }
对 lambda 主体的这种简单转换是确保没有显式返回的函数具有返回值undefined的第三种方法。在元循环求值器中，我们使用了返回值对象，它还在停止序列求值中发挥了作用。在显式控制求值器中，没有显式返回的函数继续到一个入口点，该入口点将undefined存储在val中。参见练习 5.35，了解处理插入返回语句的更加优雅的方法。
练习 5.34
42 脚注指出编译器并未识别所有死代码的实例。编译器要检测所有死代码的实例需要什么？
提示：答案取决于我们如何定义死代码。一个可能的（也有用的）定义是“在序列中跟随返回语句的代码”——但是在if (false)...的结果分支中的代码呢？或者在练习 4.15 中调用run_forever()之后的代码呢？
练习 5.35
append_return_undefined的当前设计有点粗糙：它总是将return undefined;附加到 lambda 主体，即使在主体的每个执行路径中已经有了返回语句。重写append_return_undefined，使其仅在不包含返回语句的路径末尾插入return undefined;。在下面的函数上测试您的解决方案，用任何表达式替换e[1]和e[2]，用任何（非返回）语句替换s[1]和s[2]。在t中，返回语句应该添加在两个(*)或仅在(**)中。在w和h中，返回语句应该添加在一个(*)中。在m中，不应添加返回语句。
5.5.3 编译应用程序和返回语句
编译过程的本质是编译函数应用程序。使用给定目标和链接的应用程序的代码具有以下形式
〈compilation of function expression, target fun, linkage "next"〉 〈evaluate argument expressions and construct argument list in* argl〉 〈compilation of function call with given target and linkage〉
寄存器env，fun和argl在函数和参数表达式的求值过程中可能需要保存和恢复。请注意，这是编译器中唯一指定目标不是val的地方。
所需的代码由compile_application生成。这将递归编译函数表达式，以生成将要应用的函数放入fun的代码，并编译参数表达式，以生成求值应用的各个参数表达式的代码。参数表达式的指令序列（由construct_arglist组合）与构造argl中的参数列表的代码组合在一起，生成的参数列表代码与函数代码和执行函数调用的代码（由compile_function_call生成）组合在一起。在附加代码序列时，必须在函数表达式的求值周围保留env寄存器（因为求值函数表达式可能会修改env，这将需要用于求值参数表达式），并且在构造参数列表时必须保留fun寄存器（因为求值参数表达式可能会修改fun，这将需要用于实际的函数应用）。continue寄存器在整个过程中也必须保留，因为它在函数调用中需要用于链接。
function compile_application(exp, target, linkage) { const fun_code = compile(function_expression(exp), "fun", "next"); const argument_codes = map(arg => compile(arg, "val", "next"), arg_expressions(exp)); return preserving(list("env", "continue"), fun_code, preserving(list("fun", "continue"), construct_arglist(argument_codes), compile_function_call(target, linkage))); }
构建参数列表的代码将求值每个参数表达式为val，然后使用pair将该值与在argl中累积的参数列表组合起来。由于我们按顺序将参数添加到argl的前面，所以我们必须从最后一个参数开始，以第一个结束，这样参数将按顺序出现在生成的列表中。我们不想浪费一条指令来将argl初始化为空列表以准备进行这一系列的求值，因此我们让第一个代码序列构造初始的argl。参数列表构造的一般形式如下：
〈compilation of last argument, targeted to val〉 〈assign("argl", list(op("list"), reg("val"))), 〈compilation of next argument, targeted to val〉 〈assign("argl", list(op("pair"), reg("val"), reg("argl"))), ... 〈compilation of first argument, targeted to val〉 assign("argl", list(op("pair"), reg("val"), reg("argl"))),
在每个参数求值周围必须保留argl寄存器，除了第一个（这样迄今为止累积的参数不会丢失），并且在每个参数求值周围必须保留env（供后续参数求值使用）。
编译这个参数代码有点棘手，因为第一个要求值的参数表达式的特殊处理以及在不同位置需要保留argl和env。construct_arglist函数以求值各个参数表达式的代码作为参数。如果根本没有参数表达式，它只是发出指令
assign(argl, constant(null))
否则，construct_arglist创建代码，用最后一个参数初始化argl，并附加代码来求值其余的参数，并依次将它们添加到argl中。为了从后到前处理参数，我们必须按照compile_application提供的顺序反转参数代码序列的列表。
function construct_arglist(arg_codes) { if (is_null(arg_codes)) { return make_instruction_sequence(null, list("argl"), list(assign("argl", constant(null)))); } else { const rev_arg_codes = reverse(arg_codes); const code_to_get_last_arg = append_instruction_sequences( head(rev_arg_codes), make_instruction_sequence(list("val"), list("argl"), list(assign("argl", list(op("list"), reg("val")))))); return is_null(tail(rev_arg_codes)) ? code_to_get_last_arg : preserving(list("env"), code_to_get_last_arg, code_to_get_rest_args(tail(rev_arg_codes))); } } function code_to_get_rest_args(arg_codes) { const code_for_next_arg = preserving(list("argl"), head(arg_codes), make_instruction_sequence(list("val", "argl"), list("argl"), list(assign("argl", list(op("pair"), reg("val"), reg("argl")))))); return is_null(tail(arg_codes)) ? code_for_next_arg : preserving(list("env"), code_for_next_arg, code_to_get_rest_args(tail(arg_codes))); }
应用函数
在求值函数应用的元素之后，编译的代码必须将fun中的函数应用于argl中的参数。该代码执行的基本上与第 4.1.1 节中的元循环求值器中的apply函数或第 5.4.2 节中的显式控制求值器中的apply_dispatch入口相同的分发。它检查要应用的函数是原始函数还是编译函数。对于原始函数，它使用apply_primitive_function；我们很快将看到它如何处理编译函数。函数应用代码的形式如下：
test(list(op("primitive_function"), reg("fun"))), branch(label("primitive_branch")), "compiled_branch", 〈code to apply compiled function with given target and appropriate linkage〉 "primitive_branch", assign(target, list(op("apply_primitive_function"), reg("fun"), reg("argl"))), 〈linkage〉 "after_call"
注意，编译的分支必须跳过原始分支。因此，如果原始函数调用的链接是"next"，则复合分支必须使用跳转到原始分支之后插入的标签的链接。（这类似于compile_conditional中真分支使用的链接。）
function compile_function_call(target, linkage) { const primitive_branch = make_label("primitive_branch"); const compiled_branch = make_label("compiled_branch"); const after_call = make_label("after_call"); const compiled_linkage = linkage === "next" ? after_call : linkage; return append_instruction_sequences( make_instruction_sequence(list("fun"), null, list(test(list(op("is_primitive_function"), reg("fun"))), branch(label(primitive_branch)))), append_instruction_sequences( parallel_instruction_sequences( append_instruction_sequences( compiled_branch, compile_fun_appl(target, compiled_linkage)), append_instruction_sequences( primitive_branch, end_with_linkage(linkage, make_instruction_sequence(list("fun", "argl"), list(target), list(assign( target, list(op("apply_primitive_function"), reg("fun"), reg("argl")))))))), after_call)); }
原始分支和复合分支（例如compile_ conditional中的真分支和假分支）使用parallel_instruction_sequences附加，而不是普通的append_instruction_sequences，因为它们不会按顺序执行。
应用编译函数
函数应用和返回的处理是编译器最微妙的部分。编译函数（由compile_lambda_expression构造）具有一个入口点，这是一个标签，指定函数代码的起始位置。在这个入口点的代码中，计算val中的结果，并通过执行编译返回语句的指令结束。
编译函数应用程序的代码与显式控制求值器（第 5.4.2 节）使用堆栈的方式相同：在跳转到编译函数的入口点之前，它将函数调用的继续保存到堆栈中，然后是一个标记，允许将堆栈恢复到调用之前的状态，并将继续保持在顶部。
// set up for return from function save("continue"), push_marker_to_stack(), // jump to the function's entry point assign("val", list(op("compiled_function_entry"), reg("fun"))), go_to(reg("val")),
编译返回语句（使用compile_return_statement）会生成相应的代码来恢复堆栈并恢复并跳转到continue。
revert_stack_to_marker(), restore("continue"), 〈evaluate the return expression and store the result in val〉 go_to(reg("continue")), // "return"-linkage code
除非函数进入无限循环，否则它将通过执行上述返回代码结束，该代码是由程序中的return语句或由compile_lambda_body插入的返回undefined生成的。
具有给定目标和链接的编译函数应用程序的直接代码将设置continue，使函数返回到本地标签而不是最终链接，以将函数值从val复制到目标寄存器（如果需要）。如果链接是标签，它将如下所示：
assign("continue", label("fun_return")), // where function should return to save("continue"), // will be restored by the function push_marker_to_stack(), // allows the function to revert stack to find fun_return assign("val", list(op("compiled_function_entry"), reg("fun"))), go_to(reg("val")), // eventually reverts stack, restores and jumps to continue "fun_return", // the function returns to here assign(target, reg("val")), // included if target is not val go_to(label(linkage)), // linkage code
或者像这样-在开始时保存调用者的继续，以便在结束时恢复并转到它-如果链接是return（也就是说，如果应用程序在return语句中并且其值是要返回的结果）：
save("continue"), // save the caller's continuation assign("continue", label("fun_return")), // where function should return to save("continue"), // will be restored by the function push_marker_to_stack(), // allows the function to revert stack to find fun_return assign("val", list(op("compiled_function_entry"), reg("fun"))), go_to(reg("val")), // eventually reverts stack, restores and jumps to continue "fun_return", // the function returns to here assign(target, reg("val")), // included if target is not val restore("continue"), // restore the caller's continuation go_to(reg("continue")), // linkage code
这段代码设置continue，使函数返回到标签fun_return并跳转到函数的入口点。fun_return处的代码将函数的结果从val传输到目标寄存器（如果需要），然后跳转到链接指定的位置。（链接始终是return或标签，因为compile_function_call会将复合函数分支的next链接替换为after_call标签。）在跳转到函数的入口点之前，我们保存continue并执行push_marker_to_stack()以使函数能够返回到程序中预期的位置并具有预期的堆栈。revert_stack_to_marker()和restore("continue")指令由compile_return_statement为函数体中的每个return语句生成。
实际上，如果目标不是val，那么上面的代码就是我们的编译器将生成的代码。然而，通常情况下，目标是val（编译器指定不同寄存器的唯一时间是将函数表达式的求值目标指向fun），因此函数结果直接放入目标寄存器，无需跳转到复制它的特殊位置。相反，我们通过设置continue来简化代码，使被调用函数直接“返回”到调用者链接指定的位置：
〈set up continue for linkage and push the marker〉 assign("val", list(op("compiled_function_entry"), reg("fun"))), go_to(reg("val")),
如果链接是一个标签，我们将设置continue，使函数继续在该标签处。（也就是说，被调用函数结束时的go_to(reg("continue"))相当于上面的fun_return处的go_to(label(linkage))。）
assign("continue", label(linkage)), save("continue"), push_marker_to_stack(), assign("val", list(op("compiled_function_entry"), reg("fun"))), go_to(reg("val")),
如果链接是return，我们不需要分配continue：它已经保存了所需的位置。（也就是说，被调用函数结束时的go_to(reg("continue"))会直接到达fun_return处的go_to(reg("continue"))所指定的位置。）
save("continue"), push_marker_to_stack(), assign("val", list(op("compiled_function_entry"), reg("fun"))), go_to(reg("val")),
使用这种实现的return链接，编译器生成尾递归代码。在返回语句中的函数调用，其值是要返回的结果，进行直接转移，而不在堆栈上保存不必要的信息。
假设我们处理了链接为return且目标为val的函数调用的情况，方式与非val目标的情况相同。这将破坏尾递归。我们的系统仍然会为任何函数调用返回相同的值。但每次调用函数时，我们都会保存continue并在调用后返回以撤消（无用的）保存。这些额外的保存会在函数调用的嵌套中累积。⁴⁸
函数compile_fun_appl通过考虑四种情况生成上述函数应用代码，具体取决于调用的目标是否为val以及链接是否为return。请注意，指令序列被声明为修改所有寄存器，因为执行函数体可能以任意方式更改寄存器。⁴⁹
function compile_fun_appl(target, linkage) { const fun_return = make_label("fun_return"); return target === "val" && linkage !== "return" ? make_instruction_sequence(list("fun"), all_regs, list(assign("continue", label(linkage)), save("continue"), push_marker_to_stack(), assign("val", list(op("compiled_function_entry"), reg("fun"))), go_to(reg("val")))) : target !== "val" && linkage !== "return" ? make_instruction_sequence(list("fun"), all_regs, list(assign("continue", label(fun_return)), save("continue"), push_marker_to_stack(), assign("val", list(op("compiled_function_entry"), reg("fun"))), go_to(reg("val")), fun_return, assign(target, reg("val")), go_to(label(linkage)))) : target === "val" && linkage === "return" ? make_instruction_sequence(list("fun", "continue"), all_regs, list(save("continue"), push_marker_to_stack(), assign("val", list(op("compiled_function_entry"), reg("fun"))), go_to(reg("val")))) : // target !== "val" && linkage === "return" error(target, "return linkage, target not val – compile"); }
我们已经展示了如何在链接是return时为函数应用生成尾递归链接代码，也就是说，当应用在返回语句中时，它的值是要返回的结果。同样，正如在 5.4.2 节中解释的那样，这里使用的堆栈标记机制（以及显式控制求值器）仅在这种情况下产生尾递归行为。为函数应用生成的代码的这两个方面结合在一起，确保当函数通过返回函数调用的值结束时，不会累积堆栈。
编译返回语句
无论给定的链接和目标如何，返回语句的代码都采用以下形式：
revert_stack_to_marker(), restore("continue"), // saved by compile_fun_appl 〈evaluate the return expression and store the result in val〉 go_to(reg("continue")) // "return"-linkage code
使用标记还原堆栈的指令，然后恢复continue对应于compile_fun_appl生成的指令，用于保存continue和标记堆栈。通过使用return链接编译返回表达式时生成最终跳转到continue。函数compile_return_statement与所有其他代码生成器不同，因为它忽略了目标和链接参数——它总是使用目标val和链接return编译返回表达式。
function compile_return_statement(stmt, target, linkage) { return append_instruction_sequences( make_instruction_sequence(null, list("continue"), list(revert_stack_to_marker(), restore("continue"))), compile(return_expression(stmt), "val", "return")); }
5.5.4 组合指令序列
本节描述了指令序列的表示和组合的详细信息。回想一下 5.5.1 节，指令序列被表示为所需寄存器的列表，修改的寄存器和实际指令。我们还将标签（字符串）视为指令序列的退化情况，它不需要或修改任何寄存器。因此，为了确定指令序列所需和修改的寄存器，我们使用选择器。
function registers_needed(s) { return is_string(s) ? null : head(s); } function registers_modified(s) { return is_string(s) ? null : head(tail(s)); } function instructions(s) { return is_string(s) ? list(s) : head(tail(tail(s))); }
要确定给定序列是否需要或修改给定寄存器，我们使用谓词。
function needs_register(seq, reg) { return ! is_null(member(reg, registers_needed(seq))); } function modifies_register(seq, reg) { return ! is_null(member(reg, registers_modified(seq))); }
通过这些谓词和选择器，我们可以实现编译器中使用的各种指令序列组合器。
基本组合器是append_instruction_sequences。它以两个将按顺序执行的指令序列作为参数，并返回一个指令序列，其语句是两个序列的语句附加在一起。微妙的一点是确定所需和修改的寄存器。它修改了任一序列修改的寄存器；它需要那些必须在第一个序列运行之前初始化的寄存器（第一个序列需要的寄存器），以及第二个序列需要但第一个序列未初始化（修改）的寄存器。
函数append_instruction_sequences给出了两个指令序列seq1和seq2，并返回指令序列，其指令是seq1的指令，后跟seq2的指令，其修改的寄存器是seq1或seq2修改的寄存器，并且所需的寄存器是seq1所需的寄存器以及seq2所需的寄存器，这些寄存器不被seq1修改。（在集合操作方面，所需寄存器的新集合是seq1所需的寄存器的并集，与seq2所需的寄存器和seq1修改的寄存器的差集。）因此，append_instruction_sequences的实现如下：
function append_instruction_sequences(seq1, seq2) { return make_instruction_sequence( list_union(registers_needed(seq1), list_difference(registers_needed(seq2), registers_modified(seq1))), list_union(registers_modified(seq1), registers_modified(seq2)), append(instructions(seq1), instructions(seq2))); }
这个函数使用一些简单的操作来操作列表表示的集合，类似于第 2.3.3 节中描述的（无序）集合表示：
function list_union(s1, s2) { return is_null(s1) ? s2 : is_null(member(head(s1), s2)) ? pair(head(s1), list_union(tail(s1), s2)) : list_union(tail(s1), s2); } function list_difference(s1, s2) { return is_null(s1) ? null : is_null(member(head(s1), s2)) ? pair(head(s1), list_difference(tail(s1), s2)) : list_difference(tail(s1), s2); }
函数preserving，第二个主要的指令序列组合器，接受一个寄存器列表regs和两个要顺序执行的指令序列seq1和seq2。它返回一个指令序列，其指令是seq1的指令，后跟seq2的指令，seq1中被seq1修改但seq2所需的寄存器在seq1周围有适当的save和restore指令来保护。为了实现这一点，preserving首先创建一个具有所需的save，然后是seq1的指令，然后是所需的restore的序列。这个序列需要被保存和恢复的寄存器，以及seq1所需的寄存器，并修改了seq1修改的寄存器，但不包括被保存和恢复的寄存器。然后以通常的方式附加这个增强的序列和seq2。以下函数以递归方式实现了这种策略，遍历要保留的寄存器列表：
function preserving(regs, seq1, seq2) { if (is_null(regs)) { return append_instruction_sequences(seq1, seq2); } else { const first_reg = head(regs); return needs_register(seq2, first_reg) && modifies_register(seq1, first_reg) ? preserving(tail(regs), make_instruction_sequence( list_union(list(first_reg), registers_needed(seq1)), list_difference(registers_modified(seq1), list(first_reg)), append(list(save(first_reg)), append(instructions(seq1), list(restore(first_reg))))), seq2) : preserving(tail(regs), seq1, seq2); } }
另一个序列组合器tack_on_instruction_sequence由compile_lambda_expression使用，用于将函数体附加到另一个序列。因为函数体不是“内联”执行作为组合序列的一部分，所以它的寄存器使用对嵌入它的序列的寄存器使用没有影响。因此，当我们将其附加到其他序列时，我们忽略函数体的所需和修改的寄存器集。
function tack_on_instruction_sequence(seq, body_seq) { return make_instruction_sequence( registers_needed(seq), registers_modified(seq), append(instructions(seq), instructions(body_seq))); }
函数compile_conditional和compile_function_call使用一个特殊的组合器parallel_instruction_sequences来附加跟随测试的两个替代分支。这两个分支永远不会按顺序执行；对于测试的任何特定求值，将进入其中一个分支。因此，第二个分支所需的寄存器仍然需要由组合序列，即使这些寄存器被第一个分支修改。
function parallel_instruction_sequences(seq1, seq2) { return make_instruction_sequence( list_union(registers_needed(seq1), registers_needed(seq2)), list_union(registers_modified(seq1), registers_modified(seq2)), append(instructions(seq1), instructions(seq2))); }
5.5.5 编译代码的示例
现在我们已经看到了编译器的所有元素，让我们看一个编译代码的示例，看看这些元素如何组合在一起。我们将通过将parse应用于程序的字符串表示（这里使用反引号ˋ...ˋ）来编译递归factorial函数的声明作为compile的第一个参数，反引号可以像单引号和双引号一样工作，但允许字符串跨越多行。
compile(parse(ˋ function factorial(n) { return n === 1 ? 1 : factorial(n - 1) * n; } ˋ), "val", "next");
我们已经指定声明的值应放在val寄存器中。我们不在乎编译后的代码在执行声明后做什么，因此我们选择"next"作为链接描述符是任意的。
函数compile确定它得到了一个函数声明，因此将其转换为常量声明，然后调用compile_declaration。这将编译代码来计算要分配的值（目标为val），然后是安装声明的代码，然后是将声明的值（即值undefined）放入目标寄存器的代码，最后是链接代码。在计算值时，env寄存器被保留，因为它需要用于安装声明。因为链接是"next"，所以在这种情况下没有链接代码。因此，编译代码的骨架如下
〈save env if modified by code to compute value〉 〈compilation of declaration value, target val, linkage "next"〉 〈restore env if saved above〉 perform(list(op("assign_symbol_value"), constant("factorial"), reg("val"), reg("env"))), assign("val", constant(undefined))
编译生成名称factorial的值的表达式是一个 lambda 表达式，其值是计算阶乘的函数。函数compile通过调用compile_lambda_expression来处理这个问题，它编译函数体，将其标记为新的入口点，并生成将函数体与运行时环境组合并将结果分配给val的指令。然后，序列跳过编译的函数代码，该代码插入到此处。函数代码本身首先通过将参数n绑定到函数参数的帧来扩展函数的声明环境。然后是实际的函数体。由于名称的值的代码不修改env寄存器，因此不会生成上面显示的可选的save和restore。（此时不执行entry1处的函数代码，因此其对env的使用是无关紧要的。）因此，编译代码的骨架变为
assign("val", list(op("make_compiled_function"), label("entry1"), reg("env"))), go_to(label("after_lambda2")), "entry1", assign("env", list(op("compiled_function_env"), reg("fun"))), assign("env", list(op("extend_environment"), constant(list("n")), reg("argl"), reg("env"))), 〈compilation of function body〉 "after_lambda2", perform(list(op("assign_symbol_value"), constant("factorial"), reg("val"), reg("env"))), assign("val", constant(undefined))
函数体总是使用目标val和链接"next"编译（由compile_lambda_body）。在这种情况下，函数体由单个返回语句组成：⁵⁰
return n === 1 ? 1 : factorial(n - 1) * n;
函数compile_return_statement生成代码，使用标记还原堆栈并恢复continue寄存器，然后编译返回表达式，目标为val，链接为"return"，因为其值将从函数返回。返回表达式是一个条件表达式，compile_conditional生成代码，首先计算谓词（目标为val），然后检查结果并在谓词为假时绕过真分支。在谓词代码周围保留env和continue寄存器，因为它们可能需要用于条件表达式的其余部分。真分支和假分支都使用目标val和链接"return"进行编译。（也就是说，条件的值，即由其任一分支计算得到的值，是函数的值。）
revert_stack_to_marker(), restore("continue"), 〈save continue, env if modified by predicate and needed by branches〉 〈compilation of predicate, target val, linkage "next"〉 〈restore continue, env if saved above〉 test(list(op("is_falsy"), reg("val"))), branch(label("false_branch4")), "true_branch3", 〈compilation of true branch, target val, linkage "return"〉 "false_branch4", 〈compilation of false branch, target val, linkage "return"〉 "after_cond5",
谓词n === 1是一个函数应用（在转换运算符组合后）。这查找函数表达式（符号"==="）并将该值放入fun中。然后将参数1和n的值组合成argl。然后测试fun是否包含原始函数或复合函数，并相应地分派到原始分支或复合分支。两个分支都在after_call标签处恢复。复合分支必须设置continue以跳过原始分支，并将标记推送到堆栈以匹配函数的编译返回语句中的还原操作。在函数和参数表达式的求值周围保留寄存器的要求不会导致寄存器的保存，因为在这种情况下，这些求值不会修改相关寄存器。
assign("fun", list(op("lookup_symbol_value"), constant("==="), reg("env"))), assign("val", constant(1)), assign("argl", list(op("list"), reg("val"))), assign("val", list(op("lookup_symbol_value"), constant("n"), reg("env"))), assign("argl", list(op("pair"), reg("val"), reg("argl"))), test(list(op("is_primitive_function"), reg("fun"))), branch(label("primitive_branch6")), "compiled_branch7", assign("continue", label("after_call8")), save("continue"), push_marker_to_stack(), assign("val", list(op("compiled_function_entry"), reg("fun"))), go_to(reg("val")), "primitive_branch6", assign("val", list(op("apply_primitive_function"), reg("fun"), reg("argl"))), "after_call8",
真分支，即常量 1，编译（目标为val和链接return）为
assign("val", constant(1)), go_to(reg("continue")),
假分支的代码是另一个函数调用，其中函数是符号"*"的值，参数是n和另一个函数调用的结果（对factorial的调用）。每个调用都设置了fun和argl以及自己的原始和复合分支。图 5.17 显示了factorial函数声明的完整编译。请注意，由于谓词中的函数调用修改了这些寄存器并且需要用于函数调用和分支中的“返回”链接，因此上面显示的continue和env的可能“保存”和“恢复”实际上是生成的。
图 5.17 factorial函数声明的编译。
练习 5.36
考虑以下阶乘函数的声明，它与上面给出的函数略有不同：
function factorial_alt(n) { return n === 1 ? 1 : n * factorial_alt(n - 1); }
编译此函数并将生成的代码与factorial的代码进行比较。解释您发现的任何差异。这两个程序中哪一个执行效率更高？
练习 5.37
编译迭代阶乘函数
function factorial(n) { function iter(product, counter) { return counter > n ? product : iter(product * counter, counter + 1); } return iter(1, 1); }
注释生成的代码，显示迭代和递归版本的factorial之间的基本差异，使一个进程构建堆栈空间，另一个在恒定堆栈空间中运行。
练习 5.38
编译了哪个程序以生成图 5.18 中显示的代码？
图 5.18 编译器输出的示例。参见练习 5.38。
练习 5.39
我们的编译器为应用程序的参数产生什么样的求值顺序？是从左到右（如 ECMAScript 规范所规定的）还是从右到左，还是其他顺序？编译器中的哪个部分确定了这个顺序？修改编译器，使其产生其他求值顺序。（参见 5.4.1 节中对显式控制求值器的求值顺序的讨论。）改变参数求值的顺序如何影响构造参数列表的代码的效率？
练习 5.40
理解编译器对优化堆栈使用的“保留”机制的一种方法是看看如果我们不使用这个想法会生成什么额外的操作。修改“保留”，使其总是生成“保存”和“恢复”操作。编译一些简单的表达式，并识别生成的不必要的堆栈操作。将代码与保留机制完整生成的代码进行比较。
练习 5.41
我们的编译器在避免不必要的堆栈操作方面很聪明，但在编译语言的原始函数调用方面一点也不聪明，这些原始函数调用是通过机器提供的原始操作来实现的。例如，考虑编译计算a + 1的代码量：代码在argl中设置参数列表，将原始加法函数（通过在环境中查找符号"+"找到）放入fun，并测试函数是原始的还是复合的。编译器总是生成代码来执行测试，以及原始和复合分支的代码（只有一个会被执行）。我们没有展示实现原始的控制器部分，但我们假设这些指令利用了机器数据路径中的原始算术操作。考虑如果编译器可以开放代码原始操作——也就是说，如果它可以生成代码直接使用这些原始机器操作，将会生成多少更少的代码。表达式a + 1可能被编译成如下简单的形式⁵¹
assign("val", list(op("lookup_symbol_value"), constant("a"), reg("env"))), assign("val", list(op("+"), reg("val"), constant(1)))
在这个练习中，我们将扩展我们的编译器以支持对选定原语的开放编码。将为这些原语函数的调用生成专用代码，而不是一般的函数应用代码。为了支持这一点，我们将用特殊的参数寄存器arg1和arg2来扩展我们的机器。机器的原始算术操作将从arg1和arg2中获取它们的输入。结果可以放入val、arg1或arg2中。
编译器必须能够识别源程序中开放编码原语的应用。我们将扩展compile函数中的分派，以识别这些原语的名称，以及它当前识别的句法形式。对于我们编译器的每个句法形式，都有一个代码生成器。在这个练习中，我们将为开放编码的原语构建一组代码生成器。
- a. 与句法形式不同，开放编码的原语都需要求值它们的参数表达式。编写一个名为
spread_arguments的代码生成器，供所有开放编码代码生成器使用。函数spread_arguments应接受参数表达式列表，并将给定的参数表达式编译为连续的参数寄存器。注意，参数表达式可能包含对开放编码原语的调用，因此在参数表达式求值期间必须保留参数寄存器。 - b. JavaScript 运算符
===、*、-和+等在寄存器机器中作为原始函数实现，并在全局环境中用符号===、*、-和+引用。在 JavaScript 中，不可能重新声明这些名称，因为它们不符合名称的句法限制。这意味着可以安全地开放编码它们。对于每个原始函数===、*、-和+，编写一个代码生成器，该代码生成器接受一个带有命名该函数的函数表达式的应用，以及一个目标和链接描述符，并生成代码将参数传播到寄存器，然后执行针对给定目标和给定链接的操作。使compile分派到这些代码生成器。 - c. 尝试在“阶乘”示例上使用你的新编译器。将生成的代码与不使用开放编码产生的结果进行比较。
5.5.6 词法寻址
编译器执行的最常见优化之一是名称查找的优化。到目前为止，我们实现的编译器生成使用求值器机器的lookup_symbol_value操作的代码。这通过将名称与当前绑定的每个名称进行比较来搜索名称，通过运行时环境逐帧向外工作。如果框架嵌套深或名称很多，这种搜索可能很昂贵。例如，考虑在返回的五个参数的函数的应用中，求解表达式x * y * z时查找x的值的问题。
((x, y) => (a, b, c, d, e) => ((y, z) => x * y * z)(a * b * x, c + d + x))(3, 4)
每次lookup_symbol_value搜索x时，它必须确定符号x不等于y或z（在第一个框架中），也不等于a、b、c、d或e（在第二个框架中）。因为我们的语言是词法作用域的，任何组件的运行时环境都将与组件所在的程序的词法结构相对应。因此，编译器在分析上述表达式时可以知道，每次应用函数时，x * y * z中的x的绑定将在当前框架的外部两个框架处找到，并且将是该框架中的第一个绑定。
我们可以利用这一事实，通过发明一种新的名称查找操作lexical_address_lookup，它接受环境和由两个数字组成的词法地址作为参数：帧编号，指定要跳过多少帧，和位移编号，指定在该帧中要跳过多少绑定。操作lexical_address_lookup将生成相对于当前环境存储在该词法地址的名称的值。如果我们将lexical_address_lookup操作添加到我们的机器中，我们可以让编译器生成使用这个操作引用名称的代码，而不是lookup_symbol_value。同样，我们的编译代码可以使用新的lexical_address_assign操作，而不是assign_symbol_value。使用词法寻址，对象代码中不需要包含任何名称的符号引用，帧在运行时也不需要包含符号。
为了生成这样的代码，编译器必须能够确定它即将编译引用的名称的词法地址。程序中名称的词法地址取决于代码中的位置。例如，在以下程序中，表达式e[1]中x的地址是(2,0)——向后两个帧，帧中的第一个名称。在那一点上，y的地址是(0,0)，c的地址是(1,2)。在表达式e[2]中，x在(1,0)，y在(1,1)，c在(0,2)。
((x, y) => (a, b, c, d, e) => ((y, z) => e1)(e2, c + d + x))(3, 4);
编译器产生使用词法寻址的代码的一种方法是维护一个称为编译时环境的数据结构。这个数据结构跟踪当执行特定的名称访问操作时，绑定将位于运行时环境的哪个帧的哪个位置。编译时环境是一个帧的列表，每个帧包含一个符号列表。与符号相关联的值将不会有，因为值不是在编译时计算的。（练习 5.47 将改变这一点，作为常量的优化。）编译时环境成为compile的一个额外参数，并传递给每个代码生成器。对compile的顶层调用使用包括所有原始函数和原始值名称的编译时环境。当编译 lambda 表达式的主体时，compile_lambda_body通过包含函数参数的帧扩展编译时环境，以便使用扩展的环境编译主体。同样，当编译块的主体时，compile_block通过包含主体的本地名称的帧扩展编译时环境。在编译的每个点上，compile_name和compile_assignment_declaration使用编译时环境以生成适当的词法地址。
练习 5.42 到 5.45 描述了如何完成词法寻址策略的草图，以便将词法查找纳入编译器。练习 5.46 和 5.47 描述了编译时环境的其他用途。
练习 5.42
编写一个实现新查找操作的函数lexical_address_lookup。它应该接受两个参数——词法地址和运行时环境，并返回存储在指定词法地址的名称的值。如果名称的值是字符串"unassigned"，函数lexical_address_lookup应该发出错误信号。还要编写一个实现改变指定词法地址处名称的值的操作的函数lexical_address_assign。
练习 5.43
修改编译器以维护上述编译时环境。也就是说，向compile和各种代码生成器添加一个编译时环境参数，并在compile_lambda_body和compile_block中扩展它。
练习 5.44
编写一个函数find_symbol，它以符号和编译时环境作为参数，并返回相对于该环境的符号的词法地址。例如，在上面显示的程序片段中，在编译表达式e[1]期间的编译时环境是
list(list("y", "z"), list("a", "b", "c", "d", "e"), list("x", "y"))
函数find_symbol应该产生
find_symbol("c", list(list("y", "z"), list("a", "b", "c", "d", "e"), list("x", "y"))); list(1, 2) find_symbol("x", list(list("y", "z"), list("a", "b", "c", "d", "e"), list("x", "y"))); list(2, 0) find_symbol("w", list(list("y", "z"), list("a", "b", "c", "d", "e"), list("x", "y"))); "not found"
练习 5.45
使用练习 5.44 中的find_symbol，重写compile_assignment_declaration和compile_name以输出词法地址指令。在find_symbol返回"not found"的情况下（即名称不在编译时环境中），应报告编译时错误。在一些简单情况下测试修改后的编译器，例如本节开头的嵌套 lambda 组合。
练习 5.46
在 JavaScript 中，试图为声明为常量的名称分配新值会导致错误。练习 4.11 展示了如何在运行时检测此类错误。通过本节中介绍的技术，我们可以在编译时检测尝试为常量分配新值的行为。为此，扩展函数compile_lambda_body和compile_block以记录在编译时环境中名称是声明为变量（使用let或作为参数）还是常量（使用const或function）。修改compile_assignment以在检测到对常量的赋值时报告适当的错误。
练习 5.47
编译时对常量的了解打开了许多优化的大门，使我们能够生成更高效的目标代码。除了在练习 5.46 中扩展编译时环境以指示声明为常量的名称外，如果在编译时知道常量的值或其他可以帮助我们优化代码的信息，我们可以存储常量的值。
- a. 诸如
const name = literal;的常量声明允许我们在声明的范围内用literal替换所有name的出现，这样就不必在运行时环境中查找name。这种优化称为常量传播。使用扩展的编译时环境存储字面常量，并修改compile_name以在生成的assign指令中使用存储的常量而不是lookup_symbol_value操作。 - b. 函数声明是一个派生组件，它扩展为常量声明。让我们假设全局环境中原始函数的名称也被视为常量。如果我们进一步扩展我们的编译时环境以跟踪哪些名称指向编译函数，哪些指向原始函数，我们可以将检查函数是编译还是原始的测试从运行时移动到编译时。这使得目标代码更加高效，因为它通过编译器替换了在生成的代码中每个函数应用必须执行一次的测试。使用这样扩展的编译时环境，修改
compile_function_call，以便在编译时确定所调用的函数是编译还是原始时，只生成compiled_branch或primitive_branch中的指令。 - c. 像第(a)部分那样用字面值替换常量名称为另一种优化铺平了道路，即用编译时计算的结果替换对字面值的原始函数的应用。这种优化称为常量折叠，通过在编译器中执行加法，将诸如
40 + 2之类的表达式替换为42。扩展编译器以对数字的算术运算和字符串连接执行常量折叠。
5.5.7 将编译代码与求值器进行接口
我们还没有解释如何将编译代码加载到求值器机器中，或者如何运行它。我们将假设明确控制求值器机器已经被定义，就像第 5.4.4 节中所述，其中还有脚注 43（第 5.5.2 节）中指定的其他操作。我们将实现一个名为compile_and_go的函数，该函数编译 JavaScript 程序，将生成的目标代码加载到求值器机器中，并使机器运行求值器全局环境中的代码，打印结果，并进入求值器的驱动循环。我们还将修改求值器，以便解释组件可以调用编译函数以及解释函数。然后，我们可以将编译函数放入机器中，并使用求值器调用它：
compile_and_go(parse(ˋ function factorial(n) { return n === 1 ? 1 : factorial(n - 1) * n; } ˋ));
EC-求值值：
undefined
EC-求值输入：
factorial(5);
EC-求值值：
120
为了使求值器能够处理编译函数（例如，求值上面的factorial调用），我们需要更改apply_dispatch（第 5.4.2 节）处的代码，以便它识别编译函数（与复合函数或原始函数不同），并直接将控制转移到编译代码的入口点。⁵²
"apply_dispatch", test(list(op("is_primitive_function"), reg("fun"))), branch(label("primitive_apply")), test(list(op("is_compound_function"), reg("fun"))), branch(label("compound_apply")), test(list(op("is_compiled_function"), reg("fun"))), branch(label("compiled_apply")), go_to(label("unknown_function_type")), "compiled_apply", push_marker_to_stack(), assign("val", list(op("compiled_function_entry"), reg("fun"))), go_to(reg("val")),
在compiled_apply处，与compound_apply一样，我们将一个标记推送到堆栈，以便编译函数中的返回语句可以将堆栈恢复到此状态。请注意，在标记堆栈之前，在compiled_apply处没有保存continue，因为求值器被安排在apply_dispatch处，继续将位于堆栈顶部。
为了使我们能够在启动求值器机器时运行一些编译代码，我们在求值器机器的开头添加了一个branch指令，如果flag寄存器被设置，该指令将使机器转到新的入口点。⁵³
branch(label("external_entry")), // branches if flag is set "read_evaluate_print_loop", perform(list(op("initialize_stack"))), ...
external_entry处的代码假定机器以val包含的指令序列的位置启动，该指令序列将结果放入val，并以go_to(reg("continue"))结束。从这个入口点开始跳转到由val指定的位置，但首先分配continue，以便执行将返回到print_result，该函数打印val中的值，然后转到求值器的读取-求值-打印循环的开头。⁵⁴
"external_entry", perform(list(op("initialize_stack"))), assign("env", list(op("get_current_environment"))), assign("continue", label("print_result")), go_to(reg("val")),
现在我们可以使用以下函数来编译函数声明，执行编译代码，并运行读取-求值-打印循环，以便尝试该函数。因为我们希望编译代码继续到continue的位置，并在val中返回结果，所以我们使用val作为目标编译程序，并使用"return"作为链接。为了将编译器生成的目标代码转换为求值器寄存器机器的可执行指令，我们使用寄存器机器模拟器（第 5.2.2 节）中的assemble函数。为了使解释程序引用编译程序中顶层声明的名称，我们扫描顶层名称，并通过将这些名称绑定到"unassigned"来扩展全局环境，知道编译代码将为它们分配正确的值。然后，我们将val寄存器初始化为指向指令列表，设置flag以便求值器将转到external_entry，然后启动求值器。
function compile_and_go(program) { const instrs = assemble(instructions(compile(program, "val", "return")), eceval); const toplevel_names = scan_out_declarations(program); const unassigneds = list_of_unassigned(toplevel_names); set_current_environment(extend_environment( toplevel_names, unassigneds, the_global_environment)); set_register_contents(eceval, "val", instrs); set_register_contents(eceval, "flag", true); return start(eceval); }
如果我们已经设置了堆栈监视，就像在第 5.4.4 节的末尾一样，我们可以检查编译代码的堆栈使用情况：
compile_and_go(parse(ˋ function factorial(n) { return n === 1 ? 1 : factorial(n - 1) * n; } ˋ));
总推送次数= 0
最大深度= 0
EC-求值值：
undefined
EC-求值输入：
factorial(5);
总推送次数= 36
最大深度= 14
EC-求值值：
120
将此示例与使用相同函数的解释版本求值factorial(5)进行比较，该函数显示在第 5.4.4 节的末尾。解释版本需要 151 次推送和最大堆栈深度为 28。这说明了我们编译策略带来的优化。
解释和编译
有了本节中的程序，我们现在可以尝试解释和编译的替代执行策略。解释器将机器提升到用户程序的级别；编译器将用户程序降低到机器语言的级别。我们可以将 JavaScript 语言（或任何编程语言）视为建立在机器语言上的一系列连贯的抽象。解释器适用于交互式程序开发和调试，因为程序执行步骤是根据这些抽象组织的，因此对程序员更易理解。编译代码可以更快地执行，因为程序执行步骤是根据机器语言组织的，并且编译器可以进行跨越更高级抽象的优化。
解释和编译的选择也导致将语言移植到新计算机的不同策略。假设我们希望为新机器实现 JavaScript。一种策略是从第 5.4 节的显式控制求值器开始，并将其指令转换为新机器的指令。另一种策略是从编译器开始，并更改代码生成器，以便为新机器生成代码。第二种策略允许我们首先使用运行在原始 JavaScript 系统上的编译器编译任何 JavaScript 程序，并将其与运行时库的编译版本链接起来，在新机器上运行任何 JavaScript 程序。更好的是，我们可以编译编译器本身，并在新机器上运行它来编译其他 JavaScript 程序。或者我们可以编译第 4.1 节中的解释器之一，以产生在新机器上运行的解释器。
练习 5.48
通过比较编译代码和求值器在相同计算中使用的堆栈操作，我们可以确定编译器优化堆栈使用的程度，无论是在速度上（减少总堆栈操作次数）还是在空间上（减少最大堆栈深度）。将这种优化的堆栈使用与相同计算的特定用途机器的性能进行比较，可以在一定程度上反映编译器的质量。
- a. 练习 5.28 要求您确定作为
n的函数，求值器计算n!所需的推送次数和最大堆栈深度。练习 5.13 要求您对图 5.11 中显示的特定用途阶乘机执行相同的测量。现在使用编译的factorial函数执行相同的分析。
取编译版本中推送次数与解释版本中推送次数的比率，并对最大堆栈深度做同样的操作。由于计算n!所需的操作次数和堆栈深度与n成线性关系，因此这些比率在n变大时应该接近常数。这些常数是多少？同样，找出特定用途机器的堆栈使用量与解释版本的使用量的比率。
比较特定用途与解释代码的比率与编译与解释代码的比率。您应该会发现，特定用途的机器比编译代码更有效，因为手工定制的控制器代码应该比我们的基本通用编译器生成的代码要好得多。 - b. 您能否提出改进编译器的建议，以帮助它生成性能更接近手工定制版本的代码？
练习 5.49
进行类似于练习 5.48 中的分析，以确定编译树递归斐波那契函数的有效性
function fib(n) { return n < 2 ? n : fib(n - 1) + fib(n - 2); }
与使用图 5.12 的专用斐波那契机器相比的效果。（有关解释性能的测量，请参见练习 5.30。）对于斐波那契，使用的时间资源与n不成线性关系；因此，堆栈操作的比值不会接近与n无关的极限值。
练习 5.50
本节描述了如何修改显式控制求值器，以便解释代码可以调用编译函数。展示如何修改编译器，以便编译函数不仅可以调用原始函数和编译函数，还可以调用解释函数。这需要修改compile_function_call来处理复合（解释）函数的情况。确保处理与compile_fun_appl中相同的所有target和linkage组合。要执行实际的函数应用，代码需要跳转到求值器的compound_apply入口点。这个标签不能在目标代码中直接引用（因为汇编器要求所有被汇编的代码引用的标签都在那里定义），所以我们将在求值器机器中添加一个名为compapp的寄存器来保存这个入口点，并添加一个指令来初始化它：
assign("compapp", label("compound_apply")), branch(label("external_entry")), // branches if flag is set "read_evaluate_print_loop", ...
要测试您的代码，请先声明一个调用函数g的函数f。使用compile_and_go编译f的声明并启动求值器。现在，在求值器中输入，声明g并尝试调用f。
练习 5.51
本节实现的compile_and_go接口很笨拙，因为编译器只能被调用一次（在启动求值器机器时）。通过提供一个compile_and_run原语来增强编译器-解释器接口，可以从显式控制求值器中调用它，如下所示：
EC-求值输入：
compile_and_run(parse(ˋ function factorial(n) { return n === 1 ? 1 : factorial(n - 1) * n; } ˋ));
EC-求值值：
undefined
EC-求值输入：
factorial(5)
EC-求值值：
120
练习 5.52
作为使用显式控制求值器的读取-求值-打印循环的替代方案，设计一个执行读取-编译-执行-打印循环的寄存器机器。也就是说，该机器应该运行一个循环，读取一个程序，编译它，组装和执行生成的代码，并打印结果。在我们的模拟设置中很容易运行，因为我们可以安排调用函数compile和assemble作为“寄存器机器操作”。
练习 5.53
使用编译器编译第 4.1 节的元循环求值器，并使用寄存器机器模拟器运行此程序。因为解析器以字符串作为输入，所以您需要将程序转换为字符串。最简单的方法是使用反引号（-），就像我们对compile_and_go和compile_and_run的示例输入所做的那样。由于多层解释，生成的解释器运行速度会非常慢，但使所有细节正常工作是一个有益的练习。
练习 5.54
通过将第 5.4 节的显式控制求值器翻译成 C，开发一个简陋的 JavaScript 在 C 中的实现（或者您选择的其他低级语言）。为了运行这段代码，您还需要提供适当的存储分配例程和其他运行时支持。
练习 5.55
作为练习 5.54 的对照，修改编译器，使其将 JavaScript 函数编译成 C 指令序列。编译第 4.1 节的元循环求值器，以生成用 C 编写的 JavaScript 解释器。
