NUS CS1101S：SICP JavaScript 描述：五、使用寄存器机进行计算（2）https://developer.aliyun.com/article/1427743
===操作
list(op("==="), reg(reg[1]), reg(reg[2]))
简单地测试寄存器中所有字段的相等性，而诸如is_pair、is_null、is_string和is_number之类的谓词只需要检查类型字段。
实现堆栈
尽管我们的寄存器机器使用堆栈，但在这里我们不需要做任何特殊处理，因为堆栈可以用列表来建模。堆栈可以是由特殊寄存器the_stack指向的保存值的列表。因此，save(reg)可以被实现为
assign("the_stack", list(op("pair"), reg(reg), reg("the_stack")))
同样，restore(reg)可以被实现为
assign(reg, list(op("head"), reg("the_stack"))) assign("the_stack", list(op("tail"), reg("the_stack")))
和perform(list(op("initialize_stack")))可以被实现为
assign("the_stack", constant(null))
这些操作可以进一步扩展为上述的向量操作。然而，在传统的计算机体系结构中，通常有利于将堆栈分配为单独的向量。然后，通过增加或减少对该向量的索引来推送和弹出堆栈。
练习 5.19
绘制盒子和指针表示以及由以下列表结构产生的内存向量表示（如图 5.14 中所示）。
const x = pair(1, 2); const y = list(x, x);
初始情况下，free指针为p1。free的最终值是多少？哪些指针代表了x和y的值？
练习 5.20
为以下函数实现寄存器机器。假设列表结构内存操作可用作机器原语。
- a. 递归
count_leaves：
function count_leaves(tree) { return is_null(tree) ? 0 : ! is_pair(tree) ? 1 : count_leaves(head(tree)) + count_leaves(tail(tree)); }
- b. 递归
count_leaves并带有显式计数器：
function count_leaves(tree) { function count_iter(tree, n) { return is_null(tree) ? n : ! is_pair(tree) ? n + 1 : count_iter(tail(tree), count_iter(head(tree), n)); } return count_iter(tree, 0); }
练习 5.21
3.3.1 节的练习 3.12 提出了一个append函数，它将两个列表连接起来形成一个新列表，以及一个append_mutator函数，它将两个列表拼接在一起。设计一个寄存器机器来实现这些函数。假设列表结构内存操作可用作原始操作。
5.3.2 维持内存无限的幻觉
5.3.1 节中概述的表示方法解决了实现列表结构的问题，前提是我们有无限的内存。在真实的计算机中，我们最终会耗尽用于构造新对的空间。¹⁴ 然而，在典型计算中生成的大多数对仅用于保存中间结果。在访问这些结果之后，这些对将不再需要——它们是垃圾。例如，计算
accumulate((x, y) => x + y, 0, filter(is_odd, enumerate_interval(0, n)))
构造两个列表：枚举和过滤枚举的结果。当累积完成时，这些列表将不再需要，并且分配的内存可以被回收。如果我们可以安排定期收集所有的垃圾，并且如果这样做以大约与我们构造新对的速度相同的速度回收内存，我们将保留内存无限的幻觉。
为了回收对，我们必须有一种方法来确定哪些分配的对不再需要（即它们的内容不再能影响计算的未来）。我们将研究用于实现这一点的方法称为垃圾收集。垃圾收集基于这样的观察：在基于列表结构的内存的解释中的任何时刻，只有可以通过从当前机器寄存器中的指针开始的一系列head和tail操作到达的对象才能影响计算的未来。任何不可访问的内存单元都可以被回收。 ¹⁵
执行垃圾收集有许多方法。我们将在这里研究的方法称为停止-复制。基本思想是将内存分为两半：“工作内存”和“空闲内存”。当pair构造成对时，它们被分配在工作内存中。当工作内存满时，我们通过定位工作内存中所有有用的对并将其复制到空闲内存中来执行垃圾收集。（通过跟踪所有head和tail指针来定位有用的对，从机器寄存器开始。）由于我们不复制垃圾，所以可能会有额外的空闲内存，我们可以用来分配新的对。此外，工作内存中的任何内容都不再需要，因为其中的所有有用对都已经被复制。因此，如果我们交换工作内存和空闲内存的角色，我们可以继续处理；新的对将在新的工作内存中（原来的空闲内存）分配。当这个满了，我们可以将有用的对复制到新的空闲内存中（原来的工作内存）。
实现停止-复制垃圾收集器
现在我们使用寄存器机器语言更详细地描述停止-复制算法。我们假设有一个名为root的寄存器，其中包含一个指向最终指向所有可访问数据的结构的指针。这可以通过在开始垃圾收集之前将所有机器寄存器的内容存储在由root指向的预分配列表中来安排。我们还假设，除了当前的工作内存之外，还有可用的空闲内存，我们可以将有用的数据复制到其中。当前的工作内存由基地址在名为the_heads和the_tails的寄存器中的向量组成，而空闲内存在名为new_heads和new_tails的寄存器中。
当我们耗尽当前工作内存中的空闲单元时，也就是说，当pair操作尝试将free指针增加到内存向量的末尾之外时，垃圾收集就会被触发。当垃圾收集过程完成时，root指针将指向新的内存，从root可访问的所有对象都将被移动到新的内存中，free指针将指示新内存中可以分配新对的下一个位置。此外，工作内存和新内存的角色将被交换-新的对将在新的内存中构造，从free指示的位置开始，而（之前的）工作内存将作为下一次垃圾收集的新内存可用。图 5.15 显示了垃圾收集前后内存的布局。
图 5.15 垃圾收集过程中内存的重新配置。
垃圾收集过程的状态由维护两个指针来控制：free和scan。它们被初始化为指向新内存的开始。算法从将root指向的一对重新定位到新内存的开始。复制这对，调整root指针指向新位置，并递增free指针。此外，标记这对的旧位置以显示其内容已被移动。标记的方法如下：在“头”位置，我们放置一个特殊标记，表示这是一个已经移动的对象（这样的对象传统上被称为破碎的心）。在“尾”位置，我们放置一个转发地址，指向对象已被移动的位置。
搬迁根节点后，垃圾收集器进入基本循环。算法的每一步中，“扫描”指针（最初指向已搬迁的根节点）指向一个已移动到新内存中的一对，但其“头”和“尾”指针仍指向旧内存中的对象。这些对象都被重新定位，然后“扫描”指针递增。要重新定位一个对象（例如，我们正在扫描的一对中由“头”指针指示的对象），我们检查对象是否已经被移动（由对象的“头”位置上的破碎心标记表示）。如果对象尚未被移动，我们将其复制到free指示的位置，更新free，在对象的旧位置设置一个破碎的心，并更新指向对象的指针（在这个例子中，我们正在扫描的一对的“头”指针）指向新位置。如果对象已经被移动，其转发地址（在破碎心的“尾”位置找到）将替换正在扫描的一对中的指针。最终，所有可访问的对象都将被移动和扫描，此时“扫描”指针将超过free指针，进程将终止。
我们可以将停止-复制算法指定为寄存器机器的一系列指令。重新定位对象的基本步骤是通过一个名为relocate_old_result_in_new的子例程来完成的。这个子例程从一个名为old的寄存器中获取其参数，即要重新定位的对象的指针。它重新定位指定的对象（在此过程中递增free），将指向重新定位对象的指针放入一个名为new的寄存器中，并通过跳转到存储在寄存器relocate_continue中的入口点返回。要开始垃圾收集，我们调用这个子例程来重新定位root指针，然后初始化free和scan。当root的重新定位完成后，我们将新指针安装为新的root，并进入垃圾收集器的主循环。
"begin_garbage_collection", assign("free", constant(0)), assign("scan", constant(0)), assign("old", reg("root")), assign("relocate_continue", label("reassign_root")), go_to(label("relocate_old_result_in_new")), "reassign_root", assign("root", reg("new")), go_to(label("gc_loop")),
在垃圾收集器的主循环中，我们必须确定是否还有更多的对象需要扫描。我们通过测试scan指针是否与free指针重合来做到这一点。如果指针相等，则所有可访问的对象都已经被重新定位，我们将跳转到gc_flip，清理一切，以便我们可以继续中断的计算。如果仍有要扫描的一对，我们调用重新定位子例程来重新定位下一对的“头”（将“头”指针放入old中）。设置relocate_continue寄存器，以便子例程将返回更新“头”指针。
"gc_loop", test(list(op("==="), reg("scan"), reg("free"))), branch(label("gc_flip")), assign("old", list(op("vector_ref"), reg("new_heads"), reg("scan"))), assign("relocate_continue", label("update_head")), go_to(label("relocate_old_result_in_new")),
在update_head中，我们修改正在扫描的一对的“头”指针，然后继续重新定位“尾”。当重新定位和更新“尾”完成后，我们完成了扫描该对，因此我们继续进行主循环。
"update_head", perform(list(op("vector_set"), reg("new_heads"), reg("scan"), reg("new"))), assign("old", list(op("vector_ref"), reg("new_tails"), reg("scan"))), assign("relocate_continue", label("update_tail")), go_to(label("relocate_old_result_in_new")), "update_tail", perform(list(op("vector_set"), reg("new_tails"), reg("scan"), reg("new"))), assign("scan", list(op("+"), reg("scan"), constant(1))), go_to(label("gc_loop")),
子例程relocate_old_result_in_new的重定位对象如下：如果要重定位的对象（由old指向）不是一对，那么我们将返回指向对象的相同指针（在new中不变）。（例如，我们可能正在扫描一个head为数字 4 的对。如果我们按照第 5.3.1 节中描述的方式将head表示为n4，那么我们希望“重定位”的head指针仍然是n4。）否则，我们必须执行重定位。如果要重定位的对的head位置包含一个破碎心标记，那么该对实际上已经被移动，因此我们从破碎心的tail位置检索转发地址，并将其返回到new中。如果old中的指针指向尚未移动的对，则我们将该对移动到新内存中的第一个空闲单元（由free指向），并通过在旧位置存储破碎心标记和转发地址来设置破碎心。子例程relocate_old_result_in_new使用寄存器oldht来保存由old指向的对象的head或tail。¹⁹
"relocate_old_result_in_new", test(list(op("is_pointer_to_pair"), reg("old"))), branch(label("pair")), assign("new", reg("old")), go_to(reg("relocate_continue")), "pair", assign("oldht", list(op("vector_ref"), reg("the_heads"), reg("old"))), test(list(op("is_broken_heart"), reg("oldht"))), branch(label("already_moved")), assign("new", reg("free")), // new location for pair // Update free pointer assign("free", list(op("+"), reg("free"), constant(1))), // Copy the head and tail to new memory perform(list(op("vector_set"), reg("new_heads"), reg("new"), reg("oldht"))), assign("oldht", list(op("vector_ref"), reg("the_tails"), reg("old"))), perform(list(op("vector_set"), reg("new_tails"), reg("new"), reg("oldht"))), // Construct the broken heart perform(list(op("vector_set"), reg("the_heads"), reg("old"), constant("broken_heart"))), perform(list(op("vector_set"), reg("the_tails"), reg("old"), reg("new"))), go_to(reg("relocate_continue")), "already_moved", assign("new", list(op("vector_ref"), reg("the_tails"), reg("old"))), go_to(reg("relocate_continue")),
在垃圾收集过程的最后，我们通过交换指针来交换旧内存和新内存的角色：交换the_heads和new_heads，以及the_tails和new_tails。然后，我们将准备好在内存耗尽时执行另一次垃圾收集。
"gc_flip", assign("temp", reg("the_tails")), assign("the_tails", reg("new_tails")), assign("new_tails", reg("temp")), assign("temp", reg("the_heads")), assign("the_heads", reg("new_heads")), assign("new_heads", reg("temp"))
5.4 显式控制求值器
在第 5.1 节中，我们看到如何将简单的 JavaScript 程序转换为寄存器机器的描述。我们现在将对更复杂的程序执行此转换，即第 4.1.1–4.1.4 节中的元循环求值器，该程序展示了如何用evaluate和apply函数描述 JavaScript 解释器的行为。本节中开发的显式控制求值器展示了在求值过程中使用的基础函数调用和参数传递机制如何可以用寄存器和堆栈上的操作来描述。此外，显式控制求值器可以作为 JavaScript 解释器的实现，用一种非常类似于传统计算机的本机机器语言编写。求值器可以由第 5.2 节的寄存器机器模拟器执行。或者，它可以用作构建 JavaScript 求值器的机器语言实现的起点，甚至是用于求值 JavaScript 程序的专用机器的起点。图 5.16 展示了这样一个硬件实现：一个硅片作为 Scheme 的求值器，该语言在本书的原版中代替了 JavaScript。芯片设计者从与本节描述的求值器类似的寄存器机器的数据路径和控制器规格开始，并使用设计自动化程序构建集成电路布局。²⁰
图 5.16 Scheme 求值器的硅片实现。
寄存器和操作
在设计显式控制求值器时，我们必须指定在我们的寄存器机器中使用的操作。我们描述了元循环求值器，使用诸如is_literal和make_function之类的函数来描述抽象语法。在实现寄存器机器时，我们可以将这些函数扩展为基本的列表结构内存操作的序列，并在我们的寄存器机器上实现这些操作。然而，这将使我们的求值器非常冗长，使基本结构被细节所遮盖。为了阐明表述，我们将在寄存器机器的原始操作中包括第 4.1.2 节中给出的语法函数和第 4.1.3 和 4.1.4 节中给出的表示环境和其他运行时数据的函数。为了完全指定一个可以在低级机器语言中编程或在硬件中实现的求值器，我们将用更基本的操作替换这些操作，使用我们在第 5.3 节中描述的列表结构实现。
我们的 JavaScript 求值器寄存器机器包括一个堆栈和七个寄存器：comp、env、val、continue、fun、argl和unev。comp寄存器用于保存要求值的组件，env包含要执行求值的环境。在求值结束时，val包含在指定环境中求值组件获得的值。continue寄存器用于实现递归，如第 5.1.4 节中所述。（求值器需要递归调用自身，因为求值一个组件需要求值其子组件。）fun、argl和unev寄存器用于求值函数应用。
我们不会提供数据路径图来显示求值器的寄存器和操作如何连接，也不会提供完整的机器操作列表。这些都隐含在求值器的控制器中，将会详细介绍。
5.4.1 调度程序和基本求值
求值器中的中心元素是从eval_dispatch开始的指令序列。这对应于第 4.1.1 节中描述的元循环求值器的evaluate函数。当控制器从eval_dispatch开始时，它在由env指定的环境中求值由comp指定的组件。求值完成后，控制器将转到存储在continue中的入口点，而val寄存器将保存组件的值。与元循环的evaluate一样，eval_dispatch的结构是对待求值组件的语法类型的情况分析。
"eval_dispatch", test(list(op("is_literal"), reg("comp"))), branch(label("ev_literal")), test(list(op("is_name"), reg("comp"))), branch(label("ev_name")), test(list(op("is_application"), reg("comp"))), branch(label("ev_application")), test(list(op("is_operator_combination"), reg("comp"))), branch(label("ev_operator_combination")), test(list(op("is_conditional"), reg("comp"))), branch(label("ev_conditional")), test(list(op("is_lambda_expression"), reg("comp"))), branch(label("ev_lambda")), test(list(op("is_sequence"), reg("comp"))), branch(label("ev_sequence")), test(list(op("is_block"), reg("comp"))), branch(label("ev_block")), test(list(op("is_return_statement"), reg("comp"))), branch(label("ev_return")), test(list(op("is_function_declaration"), reg("comp"))), branch(label("ev_function_declaration")), test(list(op("is_declaration"), reg("comp"))), branch(label("ev_declaration")), test(list(op("is_assignment"), reg("comp"))), branch(label("ev_assignment")), go_to(label("unknown_component_type")),
求值简单表达式
数字和字符串、名称和 lambda 表达式没有要求值的子表达式。对于这些情况，求值器只需将正确的值放入val寄存器中，并在continue指定的入口点继续执行。简单表达式的求值由以下控制器代码执行：
"ev_literal", assign("val", list(op("literal_value"), reg("comp"))), go_to(reg("continue")), "ev_name", assign("val", list(op("symbol_of_name"), reg("comp"), reg("env"))), assign("val", list(op("lookup_symbol_value"), reg("val"), reg("env"))), go_to(reg("continue")), "ev_lambda", assign("unev", list(op("lambda_parameter_symbols"), reg("comp"))), assign("comp", list(op("lambda_body"), reg("comp"))), assign("val", list(op("make_function"), reg("unev"), reg("comp"), reg("env"))), go_to(reg("continue")),
观察ev_lambda如何使用unev和comp寄存器来保存 lambda 表达式的参数和主体，以便它们可以与env中的环境一起传递给make_function操作。
条件句
与元循环求值器一样，语法形式通过选择性地求值组件的片段来处理。对于条件句，我们必须求值谓词，并根据谓词的值决定是求值结果还是替代方案。
在求值谓词之前，我们保存条件本身，即在comp中，以便稍后提取结果或替代项。为了求值谓词表达式，我们将其移动到comp寄存器中并转到eval_dispatch。env寄存器中的环境已经是正确的环境，用于求值谓词。但是，我们保存env，因为稍后我们将需要它来求值结果或替代项。我们设置continue，以便在求值完谓词后在ev_conditional_decide处恢复求值。然而，首先我们保存continue的旧值，因为稍后我们需要它来返回到等待条件值的语句的求值。
"ev_conditional", save("comp"), // save conditional for later save("env"), save("continue"), assign("continue", label("ev_conditional_decide")), assign("comp", list(op("conditional_predicate"), reg("comp"))), go_to(label("eval_dispatch")), // evaluate the predicate
在求值谓词后，在ev_conditional_decide处恢复时，我们测试它是真还是假，并根据结果在转到eval_dispatch之前将结果或替代项放在comp中。请注意，这里恢复env和continue设置了eval_dispatch具有正确的环境，并在正确的位置继续接收条件的值。
"ev_conditional_decide", restore("continue"), restore("env"), restore("comp"), test(list(op("is_falsy"), reg("val"))), branch(label("ev_conditional_alternative")), "ev_conditional_consequent", assign("comp", list(op("conditional_consequent"), reg("comp"))), go_to(label("eval_dispatch")), "ev_conditional_alternative", assign("comp", list(op("conditional_alternative"), reg("comp"))), go_to(label("eval_dispatch")),
序列求值
显式控制求值器中从ev_sequence开始处理语句序列的部分类似于元循环求值器的eval_ sequence函数。
ev_sequence_next和ev_sequence_continue处的条目形成一个循环，依次求值序列中的每个语句。未求值语句的列表保存在unev中。在ev_sequence处，我们将要求值的语句序列放在unev中。如果序列为空，我们将val设置为undefined，并通过ev_sequence_empty跳转到continue。否则，我们开始序列求值循环，首先在堆栈上保存continue的值，因为continue寄存器将用于循环中的局部控制流，原始值在语句序列之后继续时是需要的。在求值每个语句之前，我们检查序列中是否有其他语句需要求值。如果有，我们保存未求值语句的其余部分（保存在unev中）和必须求值这些语句的环境（保存在env中），并调用eval_dispatch来求值已放置在comp中的语句。在此求值后，这两个保存的寄存器在ev_sequence_continue处被恢复。
该序列中的最终语句在入口点ev_sequence_last_statement处以不同的方式处理。由于在此之后没有更多的语句需要求值，因此在转到eval_dispatch之前，我们不需要保存unev或env。整个序列的值是最后一个语句的值，因此在求值最后一个语句之后，除了继续保存在ev_sequence处保存的入口点外，没有其他事情要做。我们不是设置continue以安排eval_dispatch返回到这里，然后从堆栈中恢复continue并在该入口点继续，而是在转到eval_dispatch之前从堆栈中恢复continue，以便eval_dispatch在求值语句后继续在该入口点继续。
"ev_sequence", assign("unev", list(op("sequence_statements"), reg("comp"))), test(list(op("is_empty_sequence"), reg("unev"))), branch(label("ev_sequence_empty")), save("continue"), "ev_sequence_next", assign("comp", list(op("first_statement"), reg("unev"))), test(list(op("is_last_statement"), reg("unev"))), branch(label("ev_sequence_last_statement")), save("unev"), save("env"), assign("continue", label("ev_sequence_continue")), go_to(label("eval_dispatch")), "ev_sequence_continue", restore("env"), restore("unev"), assign("unev", list(op("rest_statements"), reg("unev"))), go_to(label("ev_sequence_next")), "ev_sequence_last_statement", restore("continue"), go_to(label("eval_dispatch")), "ev_sequence_empty", assign("val", constant(undefined)), go_to(reg("continue")),
与元循环求值器中的eval_sequence不同，ev_sequence不需要检查是否求值了返回语句以终止序列求值。这个求值器中的“显式控制”允许返回语句直接跳转到当前函数应用的继续部分，而不是恢复序列求值。因此，序列求值不需要关心返回，甚至不需要知道语言中返回语句的存在。因为返回语句跳出了序列求值代码，所以在ev_sequence_continue处保存的寄存器的恢复不会被执行。稍后我们将看到返回语句如何从堆栈中移除这些值。
5.4.2 求值函数应用
函数应用由包含函数表达式和参数表达式的组合指定。函数表达式是一个值为函数的子表达式，参数表达式是值为应用函数的参数的子表达式。元循环evaluate通过递归调用自身来处理应用，以求值组合的每个元素，然后将结果传递给apply，执行实际的函数应用。显式控制求值器也是这样做的；这些递归调用是通过go_to指令实现的，同时使用堆栈保存寄存器，在递归调用返回后将被恢复。在每次调用之前，我们将小心地确定哪些寄存器必须被保存（因为它们的值稍后将被需要）²³
与元循环求值器一样，操作符组合被转换为对应于操作符的原始函数的应用。这发生在ev_operator_combination中，在这里在comp中进行了转换，并且通过到ev_application的下降。²⁴
我们通过求值函数表达式开始应用的求值，以产生一个函数，稍后将应用于求值的参数表达式。为了求值函数表达式，我们将其移动到comp寄存器中，并转到eval_dispatch。env寄存器中的环境已经是正确的环境，用于求值函数表达式。但是，我们保存env，因为稍后我们将需要它来求值参数表达式。我们还将参数表达式提取到unev中，并将其保存在堆栈上。我们设置continue，以便eval_dispatch在函数表达式求值后将在ev_appl_did_function_expression处恢复。但首先，我们保存continue的旧值，告诉控制器在应用后继续的位置。
"ev_operator_combination", assign("comp", list(op("operator_combination_to_application"), reg("comp"), reg("env"))), "ev_application", save("continue"), save("env"), assign("unev", list(op("arg_expressions"), reg("comp"))), save("unev"), assign("comp", list(op("function_expression"), reg("comp"))), assign("continue", label("ev_appl_did_function_expression")), go_to(label("eval_dispatch")),
从求值函数表达式返回后，我们继续求值应用的参数表达式，并将结果参数累积到argl中的列表中。（这类似于求值一系列语句，只是我们收集值。）首先，我们恢复未求值的参数表达式和环境。我们将argl初始化为空列表。然后，我们将由求值函数表达式产生的函数分配给fun寄存器。如果没有参数表达式，我们直接转到apply_dispatch。否则，我们在堆栈上保存fun并开始参数求值循环：²⁵
"ev_appl_did_function_expression", restore("unev"), // the argument expressions restore("env"), assign("argl", list(op("empty_arglist"))), assign("fun", reg("val")), // the function test(list(op("is_null"), reg("unev"))), branch(label("apply_dispatch")), save("fun"),
参数求值循环的每个周期从unev中的列表中求值一个参数表达式，并将结果累积到argl中。为了求值参数表达式，我们将其放入comp寄存器中，并转到eval_dispatch，然后设置continue，以便执行将在参数累积阶段恢复。但首先，我们保存到目前为止累积的参数（保存在argl中），环境（保存在env中），以及要求值的剩余参数表达式（保存在unev中）。对于最后一个参数表达式的求值，特殊情况在ev_appl_last_arg中处理。
"ev_appl_argument_expression_loop", save("argl"), assign("comp", list(op("head"), reg("unev"))), test(list(op("is_last_argument_expression"), reg("unev"))), branch(label("ev_appl_last_arg")), save("env"), save("unev"), assign("continue", label("ev_appl_accumulate_arg")), go_to(label("eval_dispatch")),
当参数表达式被求值后，值被累积到argl中的列表中。然后，参数表达式从unev中的未求值参数表达式列表中移除，并且参数求值循环继续。
"ev_appl_accumulate_arg", restore("unev"), restore("env"), restore("argl"), assign("argl", list(op("adjoin_arg"), reg("val"), reg("argl"))), assign("unev", list(op("tail"), reg("unev"))), go_to(label("ev_appl_argument_expression_loop")),
最后一个参数表达式的求值处理方式不同，序列中的最后一个语句也是如此。在去往eval_dispatch之前，没有必要保存环境或未求值的参数表达式列表，因为在求值最后一个参数表达式后将不再需要它们。因此，我们从求值返回到一个特殊的入口点ev_appl_accum_last_arg，它恢复参数列表，累积新的参数，恢复保存的函数，并进行应用。
"ev_appl_last_arg", assign("continue", label("ev_appl_accum_last_arg")), go_to(label("eval_dispatch")), "ev_appl_accum_last_arg", restore("argl"), assign("argl", list(op("adjoin_arg"), reg("val"), reg("argl"))), restore("fun"), go_to(label("apply_dispatch")),
参数求值循环的细节决定了解释器求值组合的参数表达式的顺序（例如，从左到右或从右到左—参见练习 3.8）。这个顺序不是由元循环求值器确定的，元循环求值器从其实现的底层 JavaScript 继承其控制结构。因为我们在ev_appl_argument_expression_loop中使用head来从unev中提取连续的参数表达式，并在ev_appl_accumulate_arg中使用tail来提取其余的参数表达式，显式控制求值器将按照 ECMAScript 规范要求，按照从左到右的顺序求值组合的参数表达式。
函数应用
入口点apply_dispatch对应于元循环求值器的apply函数。当我们到达apply_dispatch时，fun寄存器包含要应用的函数，argl包含要应用的已求值参数的列表。保存的continue值（最初传递给eval_dispatch并保存在ev_application处），告诉在函数应用的结果返回到哪里，存储在堆栈上。应用完成后，控制器转移到由保存的continue指定的入口点，带有应用的结果在val中。与元循环的apply一样，有两种情况需要考虑。要么要应用的函数是原始的，要么是复合函数。
"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")), go_to(label("unknown_function_type")),
我们假设每个原始函数都是这样实现的，以便从argl中获取其参数并将其结果放入val中。要指定机器如何处理原始函数，我们需要提供一系列控制器指令来实现每个原始函数，并安排primitive_apply分派到由fun的内容标识的原始函数的指令。由于我们对求值过程的结构感兴趣，而不是原始函数的细节，因此我们将使用一个apply_primitive_function操作，将fun中的函数应用于argl中的参数。为了模拟 5.2 节中的模拟器的求值器，我们使用apply_primitive_function函数，它调用底层的 JavaScript 系统来执行应用，就像我们在 4.1.1 节中对元循环求值器所做的那样。计算出原始应用的值后，我们恢复continue并转到指定的入口点。
"primitive_apply", assign("val", list(op("apply_primitive_function"), reg("fun"), reg("argl"))), restore("continue"), go_to(reg("continue")),
标记为compound_apply的指令序列指定了复合函数的应用。要应用复合函数，我们以类似于元循环求值器的方式进行。我们构造一个框架，将函数的参数绑定到参数，使用这个框架来扩展函数携带的环境，并在这个扩展的环境中求值函数的主体。
此时，复合函数在寄存器fun中，其参数在argl中。我们将函数的参数提取到unev中，将其环境提取到env中。然后我们用扩展参数绑定的环境构造的环境替换env中的环境。然后我们将函数的主体提取到comp中。自然的下一步将是恢复保存的continue并继续到eval_dispatch来求值主体，并在val中使用结果继续到恢复的延续，就像对序列的最后一个语句所做的那样。但是有一个复杂性！
这个复杂性有两个方面。一方面，在函数体的求值过程中的任何时刻，返回语句可能需要函数返回返回表达式的值作为函数体的值。但是，返回语句可能在函数体中嵌套任意深，因此在遇到返回语句的时刻的堆栈不一定是从函数返回所需的堆栈。调整堆栈以进行返回的一种方法是在堆栈上放置一个标记，可以被返回代码找到。这是通过push_marker_to_stack指令实现的。然后返回代码可以使用revert_stack_to_marker指令将堆栈恢复到标记指示的位置，然后求值返回表达式。
复杂性的另一个方面是，如果函数体的求值在不执行返回语句的情况下终止，函数体的值必须是undefined。为了处理这个问题，我们设置continue寄存器指向return_undefined的入口点，然后去eval_dispatch求值函数体。如果在函数体的求值过程中没有遇到返回语句，函数体的求值将继续在return_undefined处。
"compound_apply", assign("unev", list(op("function_parameters"), reg("fun"))), assign("env", list(op("function_environment"), reg("fun"))), assign("env", list(op("extend_environment"), reg("unev"), reg("argl"), reg("env"))), assign("comp", list(op("function_body"), reg("fun"))), push_marker_to_stack(), assign("continue", label("return_undefined")), go_to(label("eval_dispatch")),
解释器中env寄存器被赋予新值的唯一地方是compound_apply和ev_block（5.4.3 节）。就像在元循环求值器中一样，用于求值函数体的新环境是从函数携带的环境中构建的，以及参数列表和相应的名称绑定列表。
当在ev_return处求值返回语句时，我们使用revert_stack_to_marker指令将堆栈恢复到函数调用开始时的状态，通过从堆栈中删除所有值直到包括标记。因此，restore("continue")将恢复函数调用的延续，这是在ev_application处保存的。然后我们继续求值返回表达式，其结果将放入val中，因此在继续求值返回表达式后返回函数时的值。
"ev_return", revert_stack_to_marker(), restore("continue"), assign("comp", list(op("return_expression"), reg("comp"))), go_to(label("eval_dispatch")),
如果在函数体的求值过程中没有遇到返回语句，求值将继续在return_undefined处，这是在compound_apply中设置的延续。为了从函数中返回undefined，我们将undefined放入val中，并转到在ev_application中放入堆栈的入口点。然而，在我们可以从堆栈中恢复该延续之前，我们必须删除在compound_apply保存的标记。
"return_undefined", revert_stack_to_marker(), restore("continue"), assign("val", constant(undefined)), go_to(reg("continue")),
返回语句和尾递归
在第 1 章中，我们说过，由函数描述的过程如下
function sqrt_iter(guess, x) { return is_good_enough(guess, x) ? guess : sqrt_iter(improve(guess, x), x); }
这是一个迭代过程。即使函数在语法上是递归的（以自身定义），但从一个调用sqrt_iter到下一个调用时，逻辑上并不需要求值器保存信息。一个求值器可以执行sqrt_iter这样的函数，而不需要在函数继续调用自身时增加存储空间，这被称为尾递归求值器。
第 4 章中求值器的元循环实现不是尾递归的。它将返回语句实现为返回值对象的构造函数，该对象包含要返回的值，并检查函数调用的结果是否是这样的对象。如果函数体的求值产生一个返回值对象，则函数的返回值是该对象的内容；否则，返回值是undefined。返回值对象的构造和最终对函数调用结果的检查都是延迟操作，这导致堆栈上的信息积累。
我们的显式控制求值器是尾递归的，因为它不需要包装返回值以进行检查，从而避免了由延迟操作导致的堆栈积累。在ev_return中，为了求值计算函数返回值的表达式，我们直接转移到eval_dispatch，堆栈上除了函数调用之前的内容之外没有其他东西。我们通过使用revert_stack_to_marker来撤销函数对堆栈的任何保存（因为我们正在返回），从而实现这一点。然后，我们在转到eval_dispatch之前从堆栈中恢复continue，而不是安排eval_dispatch在这里返回，然后从堆栈中恢复continue并在该入口点继续。这样，eval_dispatch在求值表达式后将在该入口点继续。最后，我们转移到eval_dispatch而不在堆栈上保存任何信息。因此，当我们继续求值返回表达式时，堆栈与我们即将计算其返回值的函数调用之前的堆栈相同。因此，求值返回表达式——即使它是一个函数调用（如sqrt_iter中的情况，其中条件表达式简化为对sqrt_iter的调用）——都不会导致堆栈上积累任何信息。³⁰
如果我们没有考虑到不需要在求值返回表达式时保留堆栈上的无用信息，我们可能会采取直接的方法来求值返回表达式，然后回来恢复堆栈，并最终在等待函数调用结果的入口点继续：
"ev_return", // alternative implementation: not tail-recursive assign("comp", list(op("return_expression"), reg("comp"))), assign("continue", label("ev_restore_stack")), go_to(label("eval_dispatch")), "ev_restore_stack", revert_stack_to_marker(), // undo saves in current function restore("continue"), // undo save at ev_application go_to(reg("continue")),
这可能看起来像是对我们以前用于求值返回语句的代码的一个微小更改：唯一的区别是，我们延迟了对堆栈中任何寄存器保存的撤销，直到返回表达式的求值之后。解释器对于任何表达式仍然会给出相同的值。但是这个改变对于尾递归实现来说是致命的，因为现在我们必须在求值返回表达式之后回来撤销（无用的）寄存器保存。这些额外的保存将在一系列函数调用中累积。因此，像sqrt_iter这样的过程将需要与迭代次数成比例的空间，而不是需要常量空间。这种差异可能是显著的。例如，使用尾递归，可以仅使用函数调用和返回机制来表示无限循环：
function count(n) { display(n); return count(n + 1); }
没有尾递归，这样的函数最终会耗尽堆栈空间，并且表达真正的迭代将需要除了函数调用之外的某种控制机制。
请注意，我们的 JavaScript 实现需要使用return才能实现尾递归。因为寄存器保存的撤销发生在ev_return，从count函数中删除return将导致最终耗尽堆栈空间。这解释了在第 4 章中无限驱动循环中使用return的原因。
练习 5.22
解释一下，如果从count中删除return，堆栈是如何构建起来的：
function count(n) { display(n); count(n + 1); }
练习 5.23
通过在compound_apply处使用save来实现push_marker_to_stack的等效操作，以在堆栈上存储特殊的标记值。在ev_return和return_undefined处实现revert_stack_to_marker的等效操作，作为一个循环，重复执行restore直到遇到标记。请注意，这将需要将值恢复到与保存时不同的寄存器。这是必要的，因为从堆栈弹出的唯一方法是通过恢复到寄存器。提示：您需要创建一个唯一的常量作为标记，例如使用const marker = list("marker")。因为list创建一个新的对，它不能与堆栈上的其他任何东西===。
练习 5.24
按照 5.2.3 节中save和restore的实现，将push_marker_to_stack和revert_stack_to_marker实现为寄存器机器指令。添加push_marker和pop_marker函数来访问堆栈，与 5.2.1 节中push和pop的实现相呼应。请注意，您不需要实际将标记插入堆栈。相反，您可以向堆栈模型添加一个本地状态变量，以跟踪每次push_marker_to_stack之前的save的位置。如果选择将标记放在堆栈上，请参考练习 5.23 中的提示。
5.4.3 块、赋值和声明
块
块的主体是在当前环境的基础上进行求值的，该环境通过将所有本地名称绑定到值"unassigned"的帧进行扩展。我们暂时利用val寄存器来保存块中声明的所有变量的列表，该列表是通过第 4.1.1 节中的scan_out_declarations获得的。假定scan_out_declarations和list_of_unassigned函数作为机器操作可用。
"ev_block", assign("comp", list(op("block_body"), reg("comp"))), assign("val", list(op("scan_out_declarations"), reg("comp"))), save("comp"), // so we can use it to temporarily hold unassigned values assign("comp", list(op("list_of_unassigned"), reg("val"))), assign("env", list(op("extend_environment"), reg("val"), reg("comp"), reg("env"))), restore("comp"), // the block body go_to(label("eval_dispatch")),
赋值和声明
赋值由ev_assignment处理，通过eval_dispatch到达，其中包含在comp中的赋值表达式。ev_assignment中的代码首先求值表达式的值部分，然后将新值安装到环境中。假定assign_symbol_value函数作为机器操作可用。
"ev_assignment", assign("unev", list(op("assignment_symbol"), reg("comp"))), save("unev"), // save variable for later assign("comp", list(op("assignment_value_expression"), reg("comp"))), save("env"), save("continue"), assign("continue", label("ev_assignment_install")), go_to(label("eval_dispatch")), // evaluate assignment value "ev_assignment_install", restore("continue"), restore("env"), restore("unev"), perform(list(op("assign_symbol_value"), reg("unev"), reg("val"), reg("env"))), go_to(reg("continue")),
变量和常量的声明都是以类似的方式处理的。请注意，赋值的值是被赋的值，声明的值是undefined。这是通过在继续之前将val设置为undefined来处理的。与元循环求值器一样，我们将函数声明转换为一个值表达式为 lambda 表达式的常量声明。这发生在ev_function_declaration，它在comp中进行转换并且继续到ev_declaration。
"ev_function_declaration", assign("comp", list(op("function_decl_to_constant_decl"), reg("comp"))), "ev_declaration", assign("unev", list(op("declaration_symbol"), reg("comp"))), save("unev"), // save declared name assign("comp", list(op("declaration_value_expression"), reg("comp"))), save("env"), save("continue"), assign("continue", label("ev_declaration_assign")), go_to(label("eval_dispatch")), // evaluate declaration value "ev_declaration_assign", restore("continue"), restore("env"), restore("unev"), perform(list(op("assign_symbol_value"), reg("unev"), reg("val"), reg("env"))), assign("val", constant(undefined)), go_to(reg("continue")),
练习 5.25
扩展求值器以处理while循环，将其转换为while_loop函数的应用，如练习 4.7 所示。您可以将while_loop函数的声明粘贴到用户程序的前面。您可以通过假设语法转换器while_to_application作为机器操作来“作弊”。参考练习 4.7，讨论如果允许在while循环中使用return、break和continue语句，这种方法是否有效。如果不行，您如何修改显式控制求值器以运行包含这些语句的while循环程序？
练习 5.26
修改求值器，使其使用基于第 4.2 节的惰性求值的正常顺序求值。
5.4.4 运行求值器
随着显式控制求值者的实施，我们完成了从第 1 章开始的一个发展，其中我们已经探索了逐渐更精确的求值过程模型。 我们从相对不正式的替换模型开始，然后在第 3 章将其扩展为环境模型，这使我们能够处理状态和变化。 在第 4 章的元循环求值者中，我们使用 JavaScript 本身作为一种语言，以使在求值组件期间构建的环境结构更加明确。 现在，通过寄存器机器，我们仔细研究了求值者的存储管理、参数传递和控制机制。 在每个新的描述级别上，我们都不得不提出问题并解决在以前不太精确的求值处理中不明显的模糊问题。 要理解显式控制求值者的行为，我们可以模拟它并监视其性能。
我们将在我们的求值机器中安装一个驱动循环。这起到了第 4.1.4 节中driver_loop函数的作用。 求值者将重复打印提示，读取程序，通过转到eval_dispatch来求值程序，并打印结果。 如果在提示处没有输入任何内容，我们将跳转到标签evaluator_done，这是控制器中的最后一个入口点。 以下说明构成了显式控制求值器的控制器序列的开头：³²
"read_evaluate_print_loop", perform(list(op("initialize_stack"))), assign("comp", list(op("user_read"), constant("EC-evaluate input:"))), assign("comp", list(op("parse"), reg("comp"))), test(list(op("is_null"), reg("comp"))), branch(label("evaluator_done")), assign("env", list(op("get_current_environment"))), assign("val", list(op("scan_out_declarations"), reg("comp"))), save("comp"), // so we can use it to temporarily hold unassigned values assign("comp", list(op("list_of_unassigned"), reg("val"))), assign("env", list(op("extend_environment"), reg("val"), reg("comp"), reg("env"))), perform(list(op("set_current_environment"), reg("env"))), restore("comp"), // the program assign("continue", label("print_result")), go_to(label("eval_dispatch")), "print_result", perform(list(op("user_print"), constant("EC-evaluate value:"), reg("val"))), go_to(label("read_evaluate_print_loop")),
我们将当前环境（最初是全局环境）存储在变量current_environment中，并在每次循环时更新它以记住过去的声明。 操作get_current_environment和set_current_ environment只是获取和设置这个变量。
let current_environment = the_global_environment; function get_current_environment() { return current_environment; } function set_current_environment(env) { current_environment = env; }
当我们在函数中遇到错误（例如在apply_dispatch处指示的“未知函数类型”错误）时，我们会打印错误消息并返回到驱动循环。³³
"unknown_component_type", assign("val", constant("unknown syntax")), go_to(label("signal_error")), "unknown_function_type", restore("continue"), // clean up stack (from apply_dispatch) assign("val", constant("unknown function type")), go_to(label("signal_error")), "signal_error", perform(list(op("user_print"), constant("EC-evaluator error:"), reg("val"))), go_to(label("read_evaluate_print_loop")),
为了模拟的目的，我们在每次通过驱动循环时初始化堆栈，因为在求值中断后（例如未声明的名称）可能不为空。³⁴
如果我们将在第 5.4.1–5.4.4 节中呈现的所有代码片段组合起来，我们可以创建一个求值者机器模型，可以使用第 5.2 节的寄存器机器模拟器运行。
const eceval = make_machine(list("comp", "env", "val", "fun", "argl", "continue", "unev"), eceval_operations, list("read_evaluate_print_loop", 〈entire machine controller as given above〉 "evaluator_done"));
我们必须定义 JavaScript 函数来模拟求值者作为原语使用的操作。 这些是我们在第 4.1 节中用于元循环求值者的相同函数，以及在第 5.4 节中的脚注中定义的少数额外函数。
const eceval_operations = list(list("is_literal", is_literal), 〈complete list of operations for eceval machine〉);
最后，我们可以初始化全局环境并运行求值者：
const the_global_environment = setup_environment(); start(eceval);
EC-求值输入：
function append(x, y) { return is_null(x) ? y : pair(head(x), append(tail(x), y)); }
EC-求值值：
undefined
EC-求值输入：
append(list("a", "b", "c"), list("d", "e", "f"));
EC-求值值：
["a", ["b", ["c", ["d", ["e", ["f", null]]]]]]
当然，以这种方式求值程序将比直接在 JavaScript 中输入它们要花费更长的时间，因为涉及多个级别的模拟。 我们的程序由显式控制求值者机器求值，该机器由 JavaScript 程序模拟，JavaScript 解释器本身也在求值。
监控求值者的性能
模拟可以是指导求值者实施的强大工具。 模拟不仅使探索寄存器机器设计的变化变得容易，还可以监视模拟求值者的性能。 例如，性能中的一个重要因素是求值者如何有效地使用堆栈。 我们可以通过使用收集堆栈使用统计信息的模拟器版本（第 5.2.4 节）定义求值者寄存器机器，并在求值者的print_result入口点添加指令来打印统计信息，观察求值各种程序所需的堆栈操作数量：
"print_result", perform(list(op("print_stack_statistics"))), // added instruction // rest is same as before perform(list(op("user_print"), constant("EC-evaluate value:"), reg("val"))), go_to(label("read_evaluate_print_loop")),
现在与求值者的交互看起来像这样：
EC-求值输入：
function factorial (n) { return n === 1 ? 1 : factorial(n - 1) * n; }
总推送= 4
最大深度= 3
EC-求值值：
undefined
EC-求值输入：
factorial(5);
总推送次数 = 151
最大深度 = 28
EC-求值值：
120
请注意，求值器的驱动循环在每次交互开始时重新初始化堆栈，因此打印的统计数据将仅涉及用于求值上一个程序的堆栈操作。
练习 5.27
使用监控堆栈来探索求值器的尾递归属性（第 5.4.2 节）。启动求值器并定义迭代factorial函数，该函数来自第 1.2.1 节：
function factorial(n) { function iter(product, counter) { return counter > n ? product : iter(counter * product, counter + 1); } return iter(1, 1); }
运行该函数，使用一些小的n值。记录计算n!所需的最大堆栈深度和推送次数。
- a. 您会发现求值
n!所需的最大深度与n无关。那个深度是多少？ - b. 根据您的数据，确定用于求值
n!的总推送操作次数的n的公式，其中n >= 1。请注意，使用的操作次数是n的线性函数，因此由两个常数确定。
练习 5.28
与练习 5.27 进行比较，探索以下函数的行为，用于递归计算阶乘：
function factorial(n) { return n === 1 ? 1 : factorial(n - 1) * n; }
通过使用监控堆栈运行此函数，确定作为n的函数的堆栈的最大深度和用于求值n!的总推送次数。（同样，这些函数将是线性的。）通过使用适当的n表达式填写以下表格来总结您的实验：
| 最大深度 | 推送次数 | |
| 递归阶乘 | ||
| 迭代阶乘 |
最大深度是求值器在执行计算时使用的空间量的度量，推送次数与所需时间相关。
练习 5.29
修改求值器的定义，通过更改ev_return，如第 5.4.2 节所述，使求值器不再是尾递归。重新运行练习 5.27 和 5.28 中的实验，以证明factorial函数的两个版本现在都需要随着输入增长而线性增长的空间。
练习 5.30
监视树递归 Fibonacci 计算中的堆栈操作：
function fib(n) { return n < 2 ? n : fib(n - 1) + fib(n - 2); }
- a. 给出一个关于计算
Fib(n)所需的堆栈的最大深度的n的公式，其中n ≥ 2。提示：在第 1.2.2 节中，我们认为该过程使用的空间随n呈线性增长。 - b. 给出一个公式，用于计算
Fib(n)的总推送次数，其中n ≥ 2。您应该发现推送次数（与使用的时间相关）随着n呈指数增长。提示：让S(n)表示计算Fib(n)时使用的推送次数。您应该能够证明存在一个公式，用S(n – 1)、S(n – 2)和一些固定的“开销”常数k来表示S(n)。给出公式，并说明k是多少。然后证明S(n)可以表示为aFib(n + 1) + b，并给出a和b的值。
练习 5.31
我们的求值器目前只捕获并信号两种错误——未知组件类型和未知函数类型。其他错误将使我们退出求值器读取-求值-打印循环。当我们使用寄存器机模拟器运行求值器时，这些错误会被底层 JavaScript 系统捕获。这类似于当用户程序出错时计算机崩溃。³⁵制作一个真正的错误系统是一个大项目，但值得努力去理解这里涉及的内容。
- a. 在求值过程中发生的错误，例如尝试访问未绑定的名称，可以通过更改查找操作来捕获，使其返回一个不同的条件代码，这个代码不可能是任何用户名称的可能值。求值器可以测试这个条件代码，然后执行必要的操作转到
signal_error。找到求值器中需要进行这种更改的所有地方并修复它们。这是很多工作。 - b. 处理错误的问题更糟糕，这些错误是通过应用原始函数来发出的，比如尝试除以零或尝试提取字符串的
head。在专业编写的高质量系统中，每个原始应用都会作为原始的一部分进行安全检查。例如，对head的每次调用都可以首先检查参数是否是一对。如果参数不是一对，应用将返回一个特殊的条件代码给求值器，然后报告失败。我们可以通过使每个原始函数检查适用性并在失败时返回适当的特殊条件代码来安排在我们的寄存器机器模拟器中。然后，求值器中的primitive_apply代码可以检查条件代码，并在必要时转到signal_error。构建这个结构并使其工作。这是一个重大项目。
5.5 编译
第 5.4 节的显式控制求值器是一个寄存器机器，其控制器解释 JavaScript 程序。在本节中，我们将看到如何在控制器不是 JavaScript 解释器的寄存器机器上运行 JavaScript 程序。
显式控制求值器机器是通用的——它可以执行任何可以用 JavaScript 描述的计算过程。求值器的控制器编排其数据路径的使用，以执行所需的计算。因此，求值器的数据路径是通用的：它们足以执行我们想要的任何计算，只要有适当的控制器。³⁶
商用通用计算机是围绕一组寄存器和操作组织的寄存器机器，构成了一组高效和方便的通用数据路径。通用机器的控制器是一个解释器，用于解释我们一直在使用的寄存器机器语言。这种语言被称为机器的本地语言，或者简称为机器语言。用机器语言编写的程序是使用机器的数据路径的指令序列。例如，显式控制求值器的指令序列可以被视为通用计算机的机器语言程序，而不是专用解释器机器的控制器。
在高级语言和寄存器机器语言之间弥合差距的常见策略有两种。显式控制求值器说明了解释的策略。用机器的本地语言编写的解释器配置机器以执行用于求值的语言（称为源语言）编写的程序。源语言的原始函数被实现为用给定机器的本地语言编写的子例程库。要解释的程序（称为源程序）表示为数据结构。解释器遍历这个数据结构，分析源程序。在这样做的同时，它通过从库中调用适当的原始子例程来模拟源程序的预期行为。
在这一部分，我们探讨了编译的替代策略。给定源语言和机器的编译器将源程序翻译成等效的程序（称为目标程序），用机器的本地语言编写。我们在这一部分实现的编译器将 JavaScript 编写的程序翻译成要使用显式控制求值器机器数据路径执行的指令序列。³⁷
与解释相比，编译可以大大提高程序执行的效率，我们将在编译器概述中解释。另一方面，解释器提供了一个更强大的交互式程序开发和调试环境，因为正在执行的源程序可以在运行时进行检查和修改。此外，由于整个原语库都存在，因此在调试期间可以构建新程序并将其添加到系统中。
考虑到编译和解释的互补优势，现代程序开发环境采用混合策略。这些系统通常组织得很好，以便解释函数和编译函数可以相互调用。这使程序员可以编译那些假定已经调试的程序部分，从而获得编译的效率优势，同时保留解释执行模式，用于程序中处于交互式开发和调试状态的部分。
编译器概述
我们的编译器在结构和功能上都与我们的解释器非常相似。因此，编译器用于分析组件的机制将类似于解释器使用的机制。此外，为了方便地接口编译和解释的代码，我们将设计编译器生成遵循与解释器相同的寄存器使用约定的代码：环境将保留在env寄存器中，参数列表将累积在argl中，要应用的函数将在fun中，函数将在val中返回它们的答案，并且函数应返回的位置将保留在continue中。通常，编译器将源程序转换为执行与解释器在求值相同源程序时执行的基本相同的寄存器操作的目标程序。
这种描述提出了实现一个基本编译器的策略：我们以与解释器相同的方式遍历组件。当我们遇到解释器在求值组件时执行的寄存器指令时，我们不执行该指令，而是将其累积到一个序列中。生成的指令序列将成为目标代码。观察编译相对于解释的效率优势。每次解释器求值一个组件时，例如f(96, 22)，它都会执行对组件进行分类的工作（发现这是一个函数应用），并测试参数表达式列表的结束（发现有两个参数表达式）。使用编译器，组件只在编译时分析一次。编译器生成的目标代码仅包含求值函数表达式和两个参数表达式、组装参数列表以及将函数（在fun中）应用于参数（在argl中）的指令。
这与我们在第 4.1.7 节的分析求值器中实现的优化相同。但是在编译代码中还有进一步提高效率的机会。解释器运行时，遵循一个必须适用于语言中的任何组件的过程。相比之下，编译代码的一个特定段意味着执行某个特定的组件。这可能会有很大的不同，例如在使用堆栈保存寄存器时。当解释器求值一个组件时，必须为任何可能发生的情况做好准备。在求值子组件之前，解释器保存所有以后可能需要的寄存器，因为子组件可能需要任意求值。另一方面，编译器可以利用它正在处理的特定组件的结构来生成避免不必要的堆栈操作的代码。
以应用程序f(96, 22)为例。在解释器求值应用程序的函数表达式之前，它通过保存包含参数表达式和环境的寄存器来为此求值做好准备，这些值稍后将被需要。然后解释器求值函数表达式以获取val中的结果，恢复保存的寄存器，最后将结果从val移动到fun。然而，在我们处理的特定表达式中，函数表达式是名称f，其求值是通过不改变任何寄存器的机器操作lookup_symbol_value完成的。我们在本节中实现的编译器将利用这一事实，并生成使用指令求值函数表达式的代码。
assign("fun", list(op("lookup_symbol_value"), constant("f"), reg("env")))
lookup_symbol_value的参数在编译时从解析器对f(96, 22)的表示中提取。这段代码不仅避免了不必要的保存和恢复，还直接将查找的值分配给fun，而解释器将在val中获取结果，然后将其移动到fun。
编译器还可以优化对环境的访问。在分析了代码之后，编译器可以知道特定名称的值将位于哪个帧中，并直接访问该帧，而不是执行lookup_symbol_value搜索。我们将在第 5.5.6 节讨论如何实现这样的词法寻址。然而，在那之前，我们将专注于上述寄存器和堆栈优化的类型。编译器还可以执行许多其他优化，例如将原始操作“内联”编码，而不是使用通用的apply机制（参见练习 5.41）；但我们在这里不会强调这些。本节的主要目标是在一个简化（但仍然有趣）的上下文中说明编译过程。
5.5.1 编译器的结构
在第 4.1.7 节中，我们修改了我们原始的元循环解释器，将分析与执行分开。我们分析每个组件以产生一个以环境为参数并执行所需操作的执行函数。在我们的编译器中，我们将基本上进行相同的分析。但是，我们不会生成执行函数，而是生成要由我们的寄存器机器运行的指令序列。
compile函数是编译器中的顶层调度。它对应于第 4.1.1 节的evaluate函数，第 4.1.7 节的analyze函数，以及第 5.4.1 节中显式控制求值器的eval_dispatch入口。编译器和解释器一样，使用了第 4.1.2 节中定义的组件语法函数。compile函数对要编译的组件的句法类型进行案例分析。对于每种类型的组件，它都会分派到一个专门的代码生成器。
function compile(component, target, linkage) { return is_literal(component) ? compile_literal(component, target, linkage) : is_name(component) ? compile_name(component, target, linkage) : is_application(component) ? compile_application(component, target, linkage) : is_operator_combination(component) ? compile(operator_combination_to_application(component), target, linkage) : is_conditional(component) ? compile_conditional(component, target, linkage) : is_lambda_expression(component) ? compile_lambda_expression(component, target, linkage) : is_sequence(component) ? compile_sequence(sequence_statements(component), target, linkage) : is_block(component) ? compile_block(component, target, linkage) : is_return_statement(component) ? compile_return_statement(component, target, linkage) : is_function_declaration(component) ? compile(function_decl_to_constant_decl(component), target, linkage) : is_declaration(component) ? compile_declaration(component, target, linkage) : is_assignment(component) ? compile_assignment(component, target, linkage) : error(component, "unknown component type – compile"); }
目标和链接
函数compile和它调用的代码生成器除了要编译的组件外，还需要两个参数。一个是目标，它指定编译后的代码将返回组件的值的寄存器。还有一个链接描述符，它描述了组件编译后的代码在执行完毕后应该如何进行。链接描述符可以要求代码执行以下三种操作之一：
- 继续到下一个指令序列（这是由链接描述符
"next"指定的）， - 跳转到
continue寄存器的当前值，作为从函数调用返回的一部分（这由链接描述符"return"指定），或 - 跳转到命名的入口点（这是通过使用指定的标签作为链接描述符来指定的）。
例如，使用val寄存器作为目标和链接为"next"编译字面量5应该产生指令
assign("val", constant(5))
使用链接"return"编译相同的表达式应该产生指令
assign("val", constant(5)), go_to(reg("continue"))
在第一种情况下，执行将继续进行下一个指令序列。在第二种情况下，我们将跳转到continue寄存器中存储的任何入口点。在这两种情况下，表达式的值将被放入目标val寄存器中。我们的编译器在编译返回语句的返回表达式时使用"return"链接。就像在显式控制求值器中一样，从函数调用返回发生在三个步骤中：
- 1. 将堆栈恢复到标记并恢复
continue（它保存了在函数调用开始时设置的继续） - 2. 计算返回值并将其放入
val - 3. 跳转到
continue中的入口点
返回语句的编译显式生成了用于恢复堆栈和恢复continue的代码。返回表达式使用目标val和链接"return"进行编译，以便计算返回值的生成代码将返回值放入val，并以跳转到continue结束。
指令序列和堆栈使用
每个代码生成器返回一个包含它为组件生成的目标代码的指令序列。复合组件的代码生成是通过组合子组件的简单代码生成器的输出来完成的，就像复合组件的求值是通过求值子组件来完成的。
组合指令序列的最简单方法是一个名为append_instruction_sequences的函数，它接受两个要依次执行的指令序列作为参数。它将它们附加在一起并返回组合的序列。也就是说，如果seq[1]和seq[2]是指令序列，那么求值
append_instruction_sequences(seq[1], seq[2])
产生序列
seq[1] seq[2]
每当需要保存寄存器时，编译器的代码生成器使用preserving，这是一种更微妙的组合指令序列的方法。函数preserving接受三个参数：一组寄存器和两个要依次执行的指令序列。它以这样的方式附加序列，以便在第一个序列的执行过程中保留集合中每个寄存器的内容，如果这对于执行第二个序列是必要的。也就是说，如果第一个序列修改了寄存器并且第二个序列实际上需要寄存器的原始内容，那么preserving在附加序列之前将寄存器的save和restore包装在第一个序列周围。否则，preserving简单地返回附加的指令序列。因此，例如，
preserving(list(reg[1], reg[2]), seq[1], seq[2])
根据seq[1]和seq[2]如何使用reg[1]和reg[2]，产生以下四种指令序列之一：
seq[1] save(reg[1]), save(reg[2]), save(reg[2]), seq[2] seq[1] seq[1] save(reg[1]), restore(reg[1]), restore(reg[2]), seq[1] seq[2] seq[2] restore(reg[1]), restore(reg[2]), seq[2]
通过使用preserving来组合指令序列，编译器避免了不必要的堆栈操作。这也隔离了是否在preserving函数内生成save和restore指令的细节，将它们与编写每个单独代码生成器时出现的问题分开。实际上，除了调用函数的代码保存continue和返回函数的代码恢复它之外，代码生成器并没有显式产生save或restore指令：这些对应的save和restore指令是由不同的compile调用显式生成的，而不是由preserving匹配生成的（我们将在 5.5.3 节中看到）。
原则上，我们可以简单地将指令序列表示为指令列表。然后，append_instruction_sequences函数可以通过执行普通的列表append来组合指令序列。然而，preserving将是一个复杂的操作，因为它必须分析每个指令序列以确定序列如何使用其寄存器。preserving也将是低效的，因为它必须分析其每个指令序列参数，即使这些序列本身可能已经通过对preserving的调用构造，这样它们的部分已经被分析。为了避免这种重复的分析，我们将与每个指令序列关联一些关于其寄存器使用的信息。当我们构造基本指令序列时，我们将明确提供这些信息，并且组合指令序列的函数将从与要组合的序列相关联的信息中推导出组合序列的寄存器使用信息。
指令序列将包含三个信息：
- 必须在序列中的指令执行之前初始化的寄存器集合（这些寄存器被称为序列需要的寄存器），
- 指令序列中被指令修改的寄存器集合，
- 序列中的实际指令。
我们将把指令序列表示为其三个部分的列表。因此，指令序列的构造函数是
function make_instruction_sequence(needs, modifies, instructions) { return list(needs, modifies, instructions); }
例如，查找当前环境中符号x的值，将结果赋给val，然后继续执行的两条指令序列需要初始化寄存器env和continue，并修改寄存器val。因此，这个序列将被构造为
make_instruction_sequence list("env", "continue"), list("val"), list(assign("val", list(op("lookup_symbol_value"), constant("x"), reg("env"))), go_to(reg("continue"))));
组合指令序列的函数在 5.5.4 节中显示。
练习 5.32
在求值函数应用时，显式控制求值器总是在函数表达式的求值周围保存和恢复env寄存器，在每个参数表达式的求值周围保存和恢复env（最后一个除外），在每个参数表达式的求值周围保存和恢复argl，并在参数表达式序列的求值周围保存和恢复fun。对于以下每个应用，说出这些save和restore操作中哪些是多余的，因此可以通过编译器的preserving机制消除：
f("x", "y") f()("x", "y") f(g("x"), y) f(g("x"), "y")
练习 5.33
使用preserving机制，编译器将避免在应用的函数表达式的求值周围保存和恢复env，在函数表达式是名称的情况下。我们也可以将这样的优化构建到求值器中。事实上，5.4 节的显式控制求值器已经通过将没有参数的应用视为特殊情况来执行类似的优化。
- a.将显式控制求值器扩展为识别函数表达式为名称的组件的一个单独类，并利用这一事实来求值这些组件。
- b. Alyssa P. Hacker 建议通过扩展求值器以识别越来越多的特殊情况，我们可以合并所有编译器的优化，这将消除编译的优势。你对这个想法有什么看法？
5.5.2 编译组件
在本节和下一节中，我们实现了compile函数分派到的代码生成器。
编译链接代码
一般来说，每个代码生成器的输出都将以由函数compile_linkage生成的指令结尾，这些指令实现了所需的链接。如果链接是"return"，那么我们必须生成指令go_to(reg("continue"))。这需要continue寄存器，不修改任何寄存器。如果链接是"next"，那么我们不需要包括任何额外的指令。否则，链接是一个标签，我们会生成一个go_to到该标签，这是一个不需要或修改任何寄存器的指令。
function compile_linkage(linkage) { return linkage === "return" ? make_instruction_sequence(list("continue"), null, list(go_to(reg("continue")))) : linkage === "next" ? make_instruction_sequence(null, null, null) : make_instruction_sequence(null, null, list(go_to(label(linkage)))); }
链接代码通过保留continue寄存器附加到指令序列，因为"return"链接将需要continue寄存器：如果给定的指令序列修改continue并且链接代码需要它，continue将被保存和恢复。
function end_with_linkage(linkage, instruction_sequence) { return preserving(list("continue"), instruction_sequence, compile_linkage(linkage)); }
编译简单组件
字面表达式和名称的代码生成器构造指令序列，将所需的值分配给目标寄存器，然后按链接描述符指定的方式继续。
字面值在编译时从被编译的组件中提取，并放入assign指令的常量部分。对于名称，当运行编译程序时，会生成一个指令来使用lookup_symbol_value操作，以查找当前环境中与符号关联的值。与字面值一样，符号在编译时从被编译的组件中提取。因此，symbol_of_name(component)只在编译程序时执行一次，并且该符号出现为assign指令中的常量。
function compile_literal(component, target, linkage) { const literal = literal_value(component); return end_with_linkage(linkage, make_instruction_sequence(null, list(target), list(assign(target, constant(literal))))); } function compile_name(component, target, linkage) { const symbol = symbol_of_name(component); return end_with_linkage(linkage, make_instruction_sequence(list("env"), list(target), list(assign(target, list(op("lookup_symbol_value"), constant(symbol), reg("env")))))); }
这些任务说明修改目标寄存器，查找符号的指令需要env寄存器。
赋值和声明的处理方式与解释器中的处理方式类似。函数compile_assignment_declaration递归生成代码，计算与符号关联的值，并将更新环境中与符号关联的值的两条指令序列附加到其中，并将整个组件的值（赋值的值或声明的undefined）分配给目标寄存器。递归编译的目标为val和链接为"next"，以便代码将其结果放入val并继续在其后附加的代码。附加的代码保留env，因为更新符号-值关联需要环境，并且计算值的代码可能是复杂表达式的编译，可能以任意方式修改寄存器。
function compile_assignment(component, target, linkage) { return compile_assignment_declaration( assignment_symbol(component), assignment_value_expression(component), reg("val"), target, linkage); } function compile_declaration(component, target, linkage) { return compile_assignment_declaration( declaration_symbol(component), declaration_value_expression(component), constant(undefined), target, linkage); } function compile_assignment_declaration( symbol, value_expression, final_value, target, linkage) { const get_value_code = compile(value_expression, "val", "next"); return end_with_linkage(linkage, preserving(list("env"), get_value_code, make_instruction_sequence(list("env", "val"), list(target), list(perform(list(op("assign_symbol_value"), constant(symbol), reg("val"), reg("env"))), assign(target, final_value))))); }
附加的两条指令序列需要env和val并修改目标。请注意，尽管我们为此序列保留了env，但我们没有保留val，因为get_value_code旨在将其结果明确放入val以供此序列使用。（实际上，如果我们保留了val，我们将会有一个错误，因为这将导致在运行get_value_code后恢复val的先前内容。）
编译条件
使用给定目标和链接编译的条件代码的形式为
〈compilation of predicate, target val, linkage "next"〉 test(list(op("is_falsy"), reg("val"))), branch(label("false_branch")), "true_branch", 〈compilation of consequent with given target and given linkage or* after_cond〉 "false_branch", 〈compilation of alternative with given target and linkage〉 "after_cond"
为了生成这段代码，我们编译谓词、结果和替代，并将生成的代码与用于测试谓词结果的指令以及用于标记真假分支和条件结束的新生成标签组合起来。在这种代码排列中，如果测试为假，我们必须绕过真分支。唯一的小复杂之处在于如何处理真分支的链接。如果条件的链接是"return"或者一个标签，那么真假分支都将使用相同的链接。如果链接是"next"，那么真分支将以跳过假分支代码到条件结束标签的跳转结束。
function compile_conditional(component, target, linkage) { const t_branch = make_label("true_branch"); const f_branch = make_label("false_branch"); const after_cond = make_label("after_cond"); const consequent_linkage = linkage === "next" ? after_cond : linkage; const p_code = compile(conditional_predicate(component), "val", "next"); const c_code = compile(conditional_consequent(component), target, consequent_linkage); const a_code = compile(conditional_alternative(component), target, linkage); return preserving(list("env", "continue"), p_code, append_instruction_sequences( make_instruction_sequence(list("val"), null, list(test(list(op("is_falsy"), reg("val"))), branch(label(f_branch)))), append_instruction_sequences( parallel_instruction_sequences( append_instruction_sequences(t_branch, c_code), append_instruction_sequences(f_branch, a_code)), after_cond))); }
在谓词代码周围保留env寄存器，因为它可能会被true和false分支所需要，continue也被保留，因为它可能会被这些分支中的链接代码所需要。真假分支的代码（它们不是顺序执行的）使用特殊的组合器parallel_instruction_sequences进行附加，该组合器在 5.5.4 节中描述。
编译序列
语句序列的编译与显式控制求值器中它们的求值并行进行，唯一的例外是：如果一个return语句出现在序列的任何位置，我们将其视为最后一条语句。序列的每个语句都会被编译——最后一条语句（或return语句）使用指定为序列的链接，其他语句使用"next"链接（执行序列的其余部分）。单个语句的指令序列被附加在一起，以便保留env（需要用于序列的其余部分）和continue（可能需要用于序列末尾的链接）。
function compile_sequence(seq, target, linkage) { return is_empty_sequence(seq) ? compile_literal(make_literal(undefined), target, linkage) : is_last_statement(seq) || is_return_statement(first_statement(seq)) ? compile(first_statement(seq), target, linkage) : preserving(list("env", "continue"), compile(first_statement(seq), target, "next"), compile_sequence(rest_statements(seq), target, linkage)); }
将return语句视为序列中的最后一条语句，避免编译return语句之后永远不会执行的“死代码”。删除is_return_statement检查不会改变对象程序的行为；然而，有许多原因不编译死代码，这超出了本书的范围（安全性、编译时间、对象代码的大小等），许多编译器对死代码会发出警告。
NUS CS1101S：SICP JavaScript 描述：五、使用寄存器机进行计算（4）https://developer.aliyun.com/article/1427745
