我们开始这本书是通过研究过程，并通过用 JavaScript 编写的函数来描述过程。为了解释这些函数的含义，我们使用了一系列的求值模型：第 1 章的替换模型，第 3 章的环境模型，以及第 4 章的元循环求值器。我们对元循环求值器的研究，特别是消除了 JavaScript 类似语言如何解释的许多神秘。但是，即使元循环求值器也留下了一些重要的问题没有解答，因为它未能阐明 JavaScript 系统中的控制机制。例如，求值器没有解释子表达式的求值如何返回一个值给使用这个值的表达式。此外，求值器也没有解释一些递归函数如何生成迭代过程（即使用恒定空间进行求值），而其他递归函数将生成递归过程。本章将解决这两个问题。
我们将描述过程，以传统计算机的逐步操作为基础。这样的计算机，或者寄存器机，顺序执行操作指令，这些指令操作固定一组称为寄存器的存储元素的内容。典型的寄存器机指令将原始操作应用于一些寄存器的内容，并将结果分配给另一个寄存器。我们对寄存器机执行的过程的描述看起来非常像传统计算机的“机器语言”程序。但是，我们不会专注于任何特定计算机的机器语言，而是会检查几个 JavaScript 函数，并设计一个特定的寄存器机来执行每个函数。因此，我们将从硬件架构师的角度而不是机器语言计算机程序员的角度来处理我们的任务。在设计寄存器机时，我们将开发用于实现重要编程构造（如递归）的机制。我们还将提供一种描述寄存器机设计的语言。在第 5.2 节中，我们将实现一个使用这些描述来模拟我们设计的机器的 JavaScript 程序。
我们的寄存器机的大多数原始操作都非常简单。例如，一个操作可能会将从两个寄存器中获取的数字相加，产生一个结果存储到第三个寄存器中。这样的操作可以通过简单描述的硬件来执行。然而，为了处理列表结构，我们还将使用head、tail和pair的内存操作，这需要一个复杂的存储分配机制。在第 5.3 节中，我们将研究它们的实现，以更基本的操作为基础。
在第 5.4 节中，当我们积累了将简单函数表述为寄存器机的经验后，我们将设计一台机器，执行第 4.1 节中元循环求值器描述的算法。这将填补我们对 JavaScript 程序如何解释的理解中的空白，通过为求值器中的控制机制提供一个明确的模型。在第 5.5 节中，我们将研究一个简单的编译器，将 JavaScript 程序转换为可以直接使用求值器寄存器机的寄存器和操作执行的指令序列。
5.1 设计寄存器机
设计一个寄存器机器，我们必须设计它的数据路径（寄存器和操作）和控制器，以便对这些操作进行排序。为了说明一个简单寄存器机器的设计，让我们来看一下欧几里得算法，它用于计算两个整数的最大公约数（GCD）。正如我们在 1.2.5 节中看到的，欧几里得算法可以通过迭代过程来执行，如下函数所示：
function gcd(a, b) { return b === 0 ? a : gcd(b, a % b); }
执行此算法的机器必须跟踪两个数字a和b，因此让我们假设这些数字存储在两个具有这些名称的寄存器中。所需的基本操作是测试寄存器b的内容是否为零，并计算寄存器a的内容除以寄存器b的余数。余数操作是一个复杂的过程，但暂时假设我们有一个计算余数的原始设备。在 GCD 算法的每个周期中，寄存器a的内容必须被寄存器b的内容替换，b的内容必须被a的旧内容除以b的旧内容的余数替换。如果这些替换可以同时进行将会很方便，但在我们的寄存器机器模型中，我们假设每次只能为一个寄存器分配一个新值。为了完成这些替换，我们的机器将使用第三个“临时”寄存器，我们称之为t。（首先余数将被放置在t中，然后b的内容将被放置在a中，最后存储在t中的余数将被放置在b中。）
我们可以通过使用图 5.1 中显示的数据路径图来说明此机器所需的寄存器和操作。在此图中，寄存器（a、b和t）由矩形表示。将值分配给寄存器的每种方法都由一个带有按钮的箭头表示——绘制为——在箭头头部后面，从数据源指向寄存器。按下按钮时，允许数据源的值“流”入指定的寄存器。每个按钮旁边的标签是我们将用来引用按钮的名称。这些名称是任意的，可以选择具有助记值（例如，a<-b表示按下将寄存器b的内容分配给寄存器a的按钮）。寄存器的数据源可以是另一个寄存器（如a<-b分配中），操作结果（如t<-r分配中），或者是一个常数（一个无法更改的内置值，在数据路径图中由包含常数的三角形表示）。
图 5.1 GCD 机器的数据路径。
计算常数和寄存器内容的值的操作在数据路径图中由一个梯形表示，其中包含操作的名称。例如，图 5.1 中标记为rem的框表示一个计算所附寄存器a和b的内容的余数的操作。箭头（没有按钮）从输入寄存器和常数指向框，箭头将操作的输出值连接到寄存器。测试由包含测试名称的圆圈表示。例如，我们的 GCD 机器有一个测试操作，用于测试寄存器b的内容是否为零。测试也有从其输入寄存器和常数的箭头，但它没有输出箭头；它的值由控制器而不是数据路径使用。总的来说，数据路径图显示了机器所需的寄存器和操作，以及它们之间的连接方式。如果我们将箭头视为电线，按钮视为开关，数据路径图就非常像可以由电子元件构建的机器的接线图。
为了使数据路径实际计算 GCD，必须按正确的顺序按下按钮。我们将根据控制器图表描述这个顺序，如图 5.2 所示。控制器图表的元素指示应如何操作数据路径组件。控制器图表中的矩形框标识要按下的数据路径按钮，并且箭头描述从一步到下一步的顺序。图表中的菱形代表一个决定。根据菱形中指定的数据路径测试的值，将遵循两个顺序箭头中的一个。我们可以根据物理类比来解释控制器：将图表视为一个迷宫，弹珠在其中滚动。当弹珠滚入一个框中时，它会按照框的名称按下数据路径按钮。当弹珠滚入决策节点（例如b = 0的测试）时，它会根据指定测试的结果离开节点。
图 5.2 GCD 机器的控制器。
将数据路径和控制器结合起来，完全描述了一个计算 GCD 的机器。我们将控制器（滚动的弹珠）放在标有start的地方，然后在寄存器a和b中放入数字。当控制器到达done时，我们将在寄存器a中找到 GCD 的值。
练习 5.1
设计一个寄存器机器，使用以下函数指定的迭代算法计算阶乘。为这台机器绘制数据路径和控制器图表。
function factorial(n) { function iter(product, counter) { return counter > n ? product : iter(counter * product, counter + 1); } return iter(1, 1); }
5.1.1 描述寄存器机器的语言
数据路径和控制器图表足以表示诸如 GCD 之类的简单机器，但对于描述 JavaScript 解释器之类的大型机器来说，它们是笨重的。为了能够处理复杂的机器，我们将创建一种以文本形式呈现数据路径和控制器图表中提供的所有信息的语言。我们将从直接反映图表的符号开始。
我们通过描述寄存器和操作来定义机器的数据路径。为了描述一个寄存器，我们给它一个名称，并指定控制分配给它的按钮。我们给每个按钮一个名称，并指定进入由按钮控制的寄存器的数据的来源（来源可以是寄存器、常量或操作）。为了描述一个操作，我们给它一个名称，并指定它的输入（寄存器或常量）。
我们将机器的控制器定义为一系列指令，以及标识序列中入口点的标签。指令可以是以下之一：
- 按下数据路径按钮的名称，以将值分配给寄存器。（这对应于控制器图表中的一个框。）
- 一个
test指令，执行指定的测试。 - 一个条件分支（
branch指令）到控制器标签指示的位置，基于先前测试的结果。（测试和分支一起对应于控制器图表中的菱形。）如果测试为假，则控制器应继续执行序列中的下一条指令。否则，控制器应继续执行标签后的指令。 - 一个无条件分支（
go_to指令），命名控制器标签，以便继续执行。
机器从控制器指令序列的开头开始，并在执行到达序列末尾时停止。除非分支改变了控制流，否则指令将按照它们列出的顺序执行。
图 5.3 显示了以这种方式描述的 GCD 机器。这个例子只是暗示了这些描述的一般性，因为 GCD 机器是一个非常简单的情况：每个寄存器只有一个按钮，并且每个按钮和测试在控制器中只使用一次。
图 5.3 GCD 机器的规范。
不幸的是，阅读这样的描述是困难的。为了理解控制器指令，我们必须不断地参考按钮名称和操作名称的定义，为了理解按钮的功能，我们可能必须参考操作名称的定义。因此，我们将转换我们的符号，将数据路径和控制器描述的信息合并在一起，以便我们可以一起看到。
为了获得这种描述形式，我们将用它们的行为定义替换任意按钮和操作名称。也就是说，我们将说（在控制器中）“按下分配给寄存器t的按钮”并分别说（在数据路径中）“按钮t<-r将rem操作的值分配给寄存器t”和“rem操作的输入是寄存器a和b的内容”，我们将说（在控制器中）“按下将rem操作的值分配给寄存器t的按钮”。类似地，我们将说（在控制器中）“执行=测试”并分别说（在数据路径中）“=测试作用于寄存器b的内容和常量 0”，我们将说“对寄存器b的内容和常量 0 执行=测试”。我们将省略数据路径描述，只保留控制器序列。因此，GCD 机器的描述如下：
controller( list( "test_b", test(list(op("="), reg("b"), constant(0))), branch(label("gcd_done")), assign("t", list(op("rem"), reg("a"), reg("b"))), assign("a", reg("b")), assign("b", reg("t")), go_to(label("test_b")), "gcd_done"))
这种描述形式比图 5.3 中所示的形式更容易阅读，但它也有缺点：
- 对于大型机器来说，它更冗长，因为每当在控制器指令序列中提到元素时，就会重复数据路径元素的完整描述。（这在 GCD 示例中不是问题，因为每个操作和按钮只使用一次。）此外，重复数据路径描述会使机器的实际数据路径结构变得模糊；对于大型机器来说，有多少寄存器、操作和按钮以及它们如何相互连接并不明显。
- 因为机器定义中的控制器指令看起来像 JavaScript 表达式，很容易忘记它们不是任意的 JavaScript 表达式。它们只能表示合法的机器操作。例如，操作只能直接作用于常量和寄存器的内容，而不能作用于其他操作的结果。
尽管存在这些缺点，但在本章中我们将使用这种寄存器机器语言，因为我们更关心理解控制器，而不是理解数据路径中的元素和连接。然而，我们应该记住，数据路径设计在设计真实机器时至关重要。
练习 5.2
使用寄存器机器语言描述练习 5.1 中的迭代阶乘机器。
行动
让我们修改 GCD 机器，以便我们可以输入我们想要的最大公约数的数字并打印答案。我们不会讨论如何制作一个可以读取和打印的机器，而是假设（就像我们在 JavaScript 中使用prompt和display时一样）它们作为原始操作是可用的。
prompt操作类似于我们一直在使用的操作，因为它产生一个可以存储在寄存器中的值。但prompt不从任何寄存器中获取输入；它的值取决于我们设计的机器之外发生的事情。
我们将允许我们机器的操作具有这样的行为，并且将绘制和标注prompt的使用，就像我们对任何计算值的其他操作一样。
另一方面，display操作在根本上与我们一直在使用的操作不同：它不会产生要存储在寄存器中的输出值。 尽管它有一个效果，但这个效果不是在我们设计的机器的一部分上。 我们将这种操作称为动作。 我们将在数据路径图中表示动作，就像我们表示计算值的操作一样 - 作为一个包含动作名称的梯形。 箭头从任何输入（寄存器或常数）指向动作框。 我们还将一个按钮与动作关联起来。 按下按钮会使动作发生。 为了使控制器按下动作按钮，我们使用一种称为perform的新类型指令。 因此，打印寄存器a的内容的动作在控制器序列中表示为指令
perform(list(op("display"), reg("a")))
图 5.4 显示了新 GCD 机器的数据路径和控制器。 与其在打印答案后停止，我们让它重新开始，以便它反复读取一对数字，计算它们的 GCD，并打印结果。 这种结构类似于我们在第 4 章解释器中使用的驱动循环。
图 5.4 一个读取输入并打印结果的 GCD 机器。
5.1.2 机器设计中的抽象
我们经常定义一个机器包括实际上非常复杂的“原始”操作。 例如，在第 5.4 节和 5.5 节中，我们将把 JavaScript 的环境操作视为原始操作。 这种抽象是有价值的，因为它使我们能够忽略机器的某些部分的细节，以便我们可以集中精力处理设计的其他方面。 然而，我们将大量复杂性隐藏起来，并不意味着机器设计是不切实际的。 我们总是可以用更简单的原始操作来替换复杂的“原始”。
考虑 GCD 机器。 该机器具有一个指令，计算寄存器a和b的内容的余数，并将结果赋给寄存器t。 如果我们想要构建 GCD 机器而不使用原始的余数运算，我们必须指定如何通过更简单的操作（如减法）来计算余数。 实际上，我们可以编写一个 JavaScript 函数以这种方式找到余数：
function remainder(n, d) { return n < d ? n : remainder(n - d, d); }
因此，我们可以用减法和比较测试来替换 GCD 机器数据路径中的余数运算。 图 5.5 显示了详细机器的数据路径和控制器。指令
assign("t", list(op("rem"), reg("a"), reg("b")))
在 GCD 控制器定义中被替换为包含循环的一系列指令，如图 5.6 所示。
图 5.5 详细 GCD 机器的数据路径和控制器。
图 5.6 GCD 机器的控制器指令序列，如图 5.5 所示。
练习 5.3
设计一个使用牛顿法计算平方根的机器，如第 1.1.7 节中描述的，并在第 1.1.8 节中用以下代码实现：
function sqrt(x) { function is_good_enough(guess) { return math_abs(square(guess) - x) < 0.001; } function improve(guess) { return average(guess, x / guess); } function sqrt_iter(guess) { return is_good_enough(guess) ? guess : sqrt_iter(improve(guess)); } return sqrt_iter(1); }
首先假设is_good_enough和improve操作作为原始操作可用。 然后展示如何通过算术操作来扩展这些操作。 通过绘制数据路径图和用寄存器机器语言编写控制器定义，描述每个sqrt机器设计的版本。
5.1.3 子程序
设计执行计算的机器时，我们通常希望安排组件被不同部分的计算共享，而不是复制组件。考虑一个包括两个 GCD 计算的机器——一个是寻找寄存器a和b中内容的 GCD，另一个是寻找寄存器c和d中内容的 GCD。我们可能首先假设有一个原始的gcd操作，然后用更原始的操作来扩展两个gcd的实例。图 5.7 仅显示了结果机器数据路径的 GCD 部分，而没有显示它们如何连接到机器的其余部分。该图还显示了机器控制器序列的相应部分。
图 5.7 具有两个 GCD 计算的机器的数据路径和控制器序列的部分。
这台机器有两个余数运算框和两个用于测试相等性的框。如果复制的组件很复杂，比如余数框，这将不是一种经济的建造机器的方式。我们可以通过使用相同的组件来避免复制数据路径组件进行两个 GCD 计算，只要这样做不会影响较大机器的其余计算。如果寄存器a和b中的值在控制器到达gcd_2时不再需要（或者这些值可以移动到其他寄存器以供安全保管），我们可以更改机器，使其在计算第二个 GCD 时使用寄存器a和b，而不是寄存器c和d。如果这样做，我们将获得图 5.8 所示的控制器序列。
图 5.8 使用相同的数据路径组件进行两个不同的 GCD 计算的机器的控制器序列的部分。
我们已经删除了重复的数据路径组件（使数据路径再次如图 5.1 所示），但是控制器现在有两个仅在它们的入口点标签上不同的 GCD 序列。最好用单个序列的分支替换这两个序列——一个gcd子程序——在该子程序的末尾我们再次分支到主指令序列中的正确位置。我们可以通过以下方式实现这一点：在分支到gcd之前，我们将一个区分值（如 0 或 1）放入特殊寄存器continue。在gcd子程序结束时，根据continue寄存器的值，我们返回到after_gcd_1或after_gcd_2。图 5.9 显示了结果控制器序列的相关部分，其中仅包括gcd指令的单个副本。
图 5.9 使用continue寄存器避免图 5.8 中重复的控制器序列。
这是处理小问题的合理方法，但如果控制器序列中有许多 GCD 计算的实例，这将是很笨拙的。为了决定在gcd子程序之后继续执行的位置，我们需要在数据路径中进行测试，并在控制器中为所有使用gcd的地方添加分支指令。实现子程序的更强大方法是使continue寄存器保存控制器序列中执行完成后应继续执行的入口点的标签。实现这种策略需要寄存器机器的数据路径和控制器之间的一种新连接：必须有一种方法将标签分配给寄存器，以便可以从寄存器中获取此值，并用于在指定的入口点继续执行。
为了反映这种能力，我们将扩展寄存器机器语言的assign指令，允许将寄存器分配为控制器序列中标签的值（作为一种特殊类型的常量）。我们还将扩展go_to指令，允许执行继续在寄存器的内容描述的入口点处继续，而不仅仅是在常量标签描述的入口点处。使用这些新构造，我们可以通过分支到continue寄存器中存储的位置来终止gcd子程序。这导致了图 5.10 中显示的控制器序列。
图 5.10 将标签分配给continue寄存器简化并概括了图 5.9 中显示的策略。
具有多个子例程的机器可以使用多个继续寄存器（例如gcd_continue，factorial_continue），或者我们可以让所有子例程共享一个continue寄存器。共享更经济，但是如果我们有一个子例程（sub1）调用另一个子例程（sub2），我们必须小心。除非sub1在设置continue以调用sub2之前将continue的内容保存在其他寄存器中，否则sub1完成时将不知道要去哪里。下一节中开发的处理递归的机制也提供了解决嵌套子例程调用问题的更好解决方案。
5.1.4 使用堆栈实现递归
到目前为止，我们所展示的思想可以通过指定具有与过程的每个状态变量对应的寄存器的寄存器机器来实现任何迭代过程。该机器重复执行控制器循环，改变寄存器的内容，直到满足某个终止条件。在控制器序列的每一点上，机器的状态（表示迭代过程的状态）完全由寄存器的内容（状态变量的值）确定。
然而，实现递归过程需要额外的机制。考虑以下用于计算阶乘的递归方法，我们在 1.2.1 节中首次研究了这个方法：
function factorial(n) { return n === 1 ? 1 : n * factorial(n - 1); }
从函数中我们可以看到，计算n!需要计算(n – 1)!. 我们的 GCD 机器，模拟了函数
function gcd(a, b) { return b === 0 ? a : gcd(b, a % b); }
同样需要计算另一个 GCD。但是gcd函数和factorial之间有一个重要的区别，gcd函数将原始计算减少为新的 GCD 计算，而factorial需要计算另一个阶乘作为子问题。在 GCD 中，新 GCD 计算的答案是原始问题的答案。要计算下一个 GCD，我们只需将新参数放入 GCD 机器的输入寄存器中，并通过执行相同的控制器序列重用机器的数据路径。当机器完成解决最终的 GCD 问题时，它已经完成了整个计算。
在阶乘（或任何递归过程）的情况下，新阶乘子问题的答案不是原始问题的答案。必须将(n – 1)!的值乘以n才能得到最终答案。如果我们试图模仿 GCD 设计，并通过减少n寄存器并重新运行阶乘机器来解决阶乘子问题，我们将不再拥有旧值n以便将结果相乘。因此，我们需要第二个阶乘机器来处理
子问题。这第二个阶乘计算本身有一个阶乘子问题，需要第三个阶乘机器，依此类推。由于每个阶乘机器中包含另一个阶乘机器，因此总机器包含无限数量的类似机器的嵌套，因此无法从固定的有限数量的部分构建。
然而，如果我们能够安排在机器的每个嵌套实例中使用相同的组件，我们就可以将阶乘过程实现为一个寄存器机。具体来说，计算n!的机器应该使用相同的组件来处理计算(n – 1)!的子问题，以及(n – 2)!的子问题，依此类推。这是合理的，因为阶乘过程规定需要无限数量的相同机器的副本来执行计算，但在任何给定时间只有一个副本需要处于活动状态。当机器遇到递归子问题时，它可以暂停主问题的工作，重复使用相同的物理部件来处理子问题，然后继续暂停的计算。
在子问题中，寄存器的内容将与主问题中的内容不同。（在这种情况下，n寄存器被递减。）为了能够继续暂停的计算，机器必须保存任何在解决子问题后将需要的寄存器的内容，以便在解决子问题后恢复这些内容以继续暂停的计算。在阶乘的情况下，我们将保存n的旧值，在完成对递减的n寄存器的阶乘计算后将其恢复。
由于嵌套递归调用的深度没有先验限制，我们可能需要保存任意数量的寄存器值。这些值必须以它们被保存的相反顺序进行恢复，因为在递归的嵌套中，最后进入的子问题是第一个完成的。这决定了使用“栈”或“后进先出”数据结构来保存寄存器值。我们可以通过添加两种指令来扩展寄存器机器语言以包括一个栈：使用save指令将值放入栈中，并使用restore指令从栈中恢复值。在一系列值被保存到栈上后，一系列restore将以相反的顺序检索这些值。
借助栈的帮助，我们可以为每个阶乘子问题重复使用阶乘机器的数据路径的单个副本。在重用操作数据路径的控制器序列方面存在类似的设计问题。为了重新执行阶乘计算，控制器不能简单地回到开始，因为在解决(n – 1)!子问题后，机器仍然必须将结果乘以n。控制器必须暂停计算n!，解决(n – 1)!子问题，然后继续计算n!。阶乘计算的这种观点表明了在 5.1.3 节中描述的子程序机制的使用，其中控制器使用continue寄存器来转移到解决子问题的序列的部分，然后继续在主问题上离开的地方。因此，我们可以制作一个返回到存储在continue寄存器中的入口点的阶乘子程序。在每个子程序调用周围，我们保存和恢复continue，就像我们对n寄存器做的那样，因为阶乘计算的每个“级别”将使用相同的continue寄存器。也就是说，阶乘子程序在调用自身解决子问题时必须在continue中放入一个新值，但为了返回到调用它解决子问题的地方，它将需要旧值。
图 5.11 显示了实现递归factorial函数的机器的数据路径和控制器。该机器有一个堆栈和三个寄存器，称为n，val和continue。为了简化数据路径图，我们没有命名寄存器分配按钮，只有堆栈操作按钮（sc和sn用于保存寄存器，rc和rn用于恢复寄存器）。要操作这台机器，我们将要计算阶乘的数放入寄存器n中并启动机器。当机器到达fact_done时，计算完成，答案将在val寄存器中找到。在控制器序列中，每次递归调用之前都会保存n和continue，并在调用返回时恢复。从调用返回是通过跳转到continue中存储的位置来实现的。机器启动时会初始化continue寄存器，以便最后的返回将到达fact_done。val寄存器保存了阶乘计算的结果，不会在递归调用之前保存，因为在子程序返回后，旧的val内容是没有用的。只有新值，也就是子计算产生的值，是需要的。
图 5.11 递归阶乘机器。
尽管原则上阶乘计算需要一个无限的机器，但是图 5.11 中的机器实际上是有限的，除了堆栈，堆栈可能是无限的。然而，任何特定的堆栈物理实现都将是有限大小的，这将限制机器可以处理的递归调用的深度。阶乘的这种实现说明了将递归算法实现为普通寄存器机器加上堆栈的一般策略。当遇到递归子问题时，我们在堆栈上保存当前值将在解决子问题后需要的寄存器，解决递归子问题，然后恢复保存的寄存器并继续在主问题上执行。continue寄存器必须始终保存。是否需要保存其他寄存器取决于特定的机器，因为并非所有递归计算都需要在解决子问题时修改的寄存器的原始值（参见练习 5.4）。
双重递归
让我们来看一个更复杂的递归过程，即我们在 1.2.2 节中介绍的树递归计算斐波那契数：
function fib(n) { return n === 0 ? 0 : n === 1 ? 1 : fib(n - 1) + fib(n - 2); }
就像阶乘一样，我们可以使用寄存器机器来实现递归斐波那契计算，其中有寄存器n，val和continue。这台机器比阶乘的机器更复杂，因为在控制器序列中有两个地方需要进行递归调用——一次是计算Fib(n – 1)，一次是计算Fib(n – 2)。为了为每个调用设置准备，我们保存将来需要的寄存器的值，将n寄存器设置为需要递归计算的数（n – 1或n – 2），并将continue分配给主序列中的入口点以便返回（分别是afterfib_n_1或afterfib_n_2）。然后我们进入fib_loop。当我们从递归调用返回时，答案在val中。图 5.12 显示了这台机器的控制器序列。
图 5.12 计算斐波那契数的机器的控制器。
练习 5.4
指定实现以下每个函数的寄存器机器。对于每台机器，编写一个控制器指令序列，并绘制一个显示数据路径的图。
- a. 递归指数运算：
function expt(b, n) { return n === 0 ? 1 : b * expt(b, n - 1); }
- b. 迭代指数运算：
function expt(b, n) { function expt_iter(counter, product) { return counter === 0 ? product : expt_iter(counter - 1, b * product); } return expt_iter(n, 1); }
练习 5.5
手动模拟阶乘和斐波那契机器，使用一些复杂的输入（需要执行至少一个递归调用）。显示执行中每个重要点的堆栈内容。
练习 5.6
Ben Bitdiddle 观察到斐波那契机器的控制器序列有额外的save和额外的restore，可以删除以使机器更快。这些指令在哪里？
5.1.5 指令摘要
我们的寄存器机器语言中的控制器指令具有以下形式之一，其中每个input[i]是reg(register-name)或constant(constant-value)。
这些指令是在 5.1.1 节中引入的：
assign(register-name, reg(register-name)) assign(register-name, constant(constant-value)) assign(register-name, list(op(operation-name), input[1], ..., input[n])) perform(list(op(operation-name), input[1], ..., input[n])) test(list(op(operation-name), input[1], ..., input[n])) branch(label(label-name)) go_to(label(label-name))
使用寄存器保存标签是在 5.1.3 节中引入的：
assign(register-name, label(label-name)) go_to(reg(register-name))
使用堆栈的指令是在 5.1.4 节中引入的：
save(register-name) restore(register-name)
到目前为止，我们看到的唯一类型的constant-value是一个数字，但稍后我们还将使用字符串和列表。例如，constant("abc")是字符串"abc"，constant(null)是空列表，constant(list("a", "b", "c"))是列表list("a", "b", "c")。
5.2 寄存器机器模拟器
为了更好地理解寄存器机器的设计，我们必须测试我们设计的机器，以查看它们是否按预期运行。测试设计的一种方法是手动模拟控制器的操作，就像练习 5.5 中那样。但是，除了最简单的机器外，这种方法非常乏味。在本节中，我们构建了一个模拟器，用于模拟寄存器机器语言描述的机器。该模拟器是一个 JavaScript 程序，具有四个接口函数。第一个使用寄存器机器的描述来构建机器的模型（一个数据结构，其部分对应于要模拟的机器的部分），另外三个允许我们通过操作模型来模拟机器：
make_machine(register-names, operations, controller)
构建并返回具有给定寄存器、操作和控制器的机器模型。set_register_contents(machine-model, register-name, value)
在给定机器中的模拟寄存器中存储一个值。get_register_contents(machine-model, register-name)
返回给定机器中模拟寄存器的内容。start(machine-model)
模拟给定机器的执行，从控制器序列的开头开始，直到到达序列的末尾。
NUS CS1101S：SICP JavaScript 描述：五、使用寄存器机进行计算（2）https://developer.aliyun.com/article/1427743
