5.1 Designing Register Machines - CloneableX/SICP-learning GitHub Wiki

寄存器机器的设计需要以其 数据路径（data paths） （也就是寄存器及其操作）和操作序列的 控制器（controller） 为基础。我们通过 Euclid 算法解释一个简单寄存器机器的设计，Euclid 算法常用于计算两个整数的最大公约数。我们在第一章时展示过 Euclid 算法，它以迭代过程运行，具体程式如下。

(define (gcd a b)
  (if (= b 0)
      a
      (gcd b (remainder a b))))

能够运算该算法的机器必须能够追踪 a 和 b 两个数字的变化，所以首先让我们假设这些数字存储于对应名称的寄存器中。于是该算法的一个基础操作便是，检测寄存器 b 中的数值是否为 0，如果不为 0 将计算寄存器 a 中数值与寄存器 b 中数值相除后的余数。虽然求余是一个比较复杂的操作，但可以假设目前已经存在一个取余计算模块。在 GCD 算法的每次循环过程中，都需要将寄存器 b 的存储内容替换至寄存器 a 中存储，然后寄存器 b 中存储的内容替换为寄存器 a 和寄存器 b 原有存储数据的取余计算结果。虽然两步操作能够同时进行将提供巨大的便利，但在我们的寄存器机器模型中预想的是每次只能向一个寄存器分配一个新的数据。所以为了实现替换操作，我们只能通过临时寄存器完成替换操作，我们将此寄存器命名为 t。（首先余数将存储在 t 中，然后再将 b 中的数据存储至 a 中，最后再将存储于 t 中的余数存储至 b 中）。

通过下图我们能够使用数据路径图示解释寄存器及其操作。在该图示中，使用矩形表示寄存器（分别是 a、b 和 t）。分配数据至寄存器的路径通过带有 X 标识的箭头表示，并通过箭头连线分别指明数据来源和去向。如果将 X 想象成一个按钮，当它被按下时会将源头寄存器中的数据流入目标寄存器中。按钮旁的标识是用于指代该按钮的名字。按钮的命名规则没有严格要求，不过一般都选择易于记忆的名字（例如 a<-b 表示按下按钮时会将寄存器 b 的数据导向寄存器 a 中）。一个寄存器的数据源也可以是另一个寄存器（如同 a<-b 的关系一样），也可以是操作结果（例如 r<-t 的数据存储）或常量（常量通常是一个构建后不再变化的数据，在数据路径图示中通过一个包含常量的三角形表示）。

通过常量和寄存器内容计算数值的操作在数据路径图示中通过一个包含操作名称的梯形表示。例如，在上图中通过标识 rem 的梯形表示计算寄存器 a 和寄存器 b 余数的操作。箭头（没有按钮的）既能连接输入至操作的常量和寄存器，也能连接操作输入与寄存器。通过包含检测操作名称的圆形图标能够表示一个检测。例如，在 GCD 机器中需要检测寄存器 b 是否为 0。该检测操作由两个箭头连接，分别表示输入的寄存器和常量，但它并没有输出箭头，因为它的计算结果将被控制器使用而不会被数据路径使用。总而言之，数据路径图示展示了机器中所需的寄存器和操作，也展示了这些寄存器与操作是如何连接的。如果我们将箭头想像成电线，而 X 按钮想象成开关，那么数据路图示与用于构建电器原件的机器示例图具有极强的相似性。

如果要使数据路径图示能够正常运算 GCD，还需要注意按钮按下的时机。我们打算在控制器图示中讲解，如同下图。控制器图示中的元素用于说明数据路径中的组件如何操作。控制器图示中的矩形表示数据路径中被按下的按钮，以及通过箭头表示运行步骤的顺序。控制器图示中的菱形表示判断。下一步会延续两个输出箭头的其中一个，选择的标准有赖于菱形检测中的值与哪条数据路径标识的结果对应。我们可以通过一个现实的比方解释控制器，可以将图示想象成一个有岩石在其中滚动的迷宫。它石球滚动至盒子中时，它将按动盒子名称对应的按钮。当巨石滚动至判断节点时（比如 b = 0 的检测时），它将根据检测结果沿着对应的路径滚动。总而言之，数据路径和控制器结合后能够完整地描述计算 GCD 的机器。在向寄存器 a 和寄存器 b 中存储数据后，控制器将从标识为 start 的位置出发。当控制器到达 done 的节点时，寄存器 a 中存储的数据就是 GCD 的结果。

数据路径和控制器的图示已经能够满足类似 GCD 的简单机器的表示需求，但还不足以描述类似 Lisp 解释器的大型机器。为了使描述复杂机器成为可能，我们需要创建一门语言，它能够通过文字形式表达数据路径和控制器图示提供所有信息。我们将从直接反映图示的符号开始。

通过描述寄存器及其操作能够定义一台机器的数据路径。为了更方便地描述寄存器，需要为寄存器提供一个名字，以此区分向指定寄存器赋值的按钮。同时也需要给这些按钮提供名字，以此区分该按钮控制下的数据源寄存器。（数据源可以是一个寄存器、常量或操作）。为了描述操作也需要给它提供名字，通过名字能够区分操作的输入（输入可以是寄存器或常量）。

控制器通过指令序列定义，该序列中除了指令还含有区分入口点的标识。指令可以是下列的任一形式。

• 数据路径中按下后将数据分配给寄存器的按钮名称（与控制器图示中盒子的名称一致）
• 检测指令，能够执行指定检测
• 条件分支（也称为 branch 指令），由控制器标识指定的路径，主要基于检测指令的检测结果进行选择。（检测指令和条件指令在控制器图示中以菱形组件的形式一同出现）。如果检测结果为 false，控制器将继续运行序列中的下一指令。否则，控制器应该继续运行标识之后的指令。
• 非条件分支（也称 goto 指令）根据标识名称跳转至需要继续执行的控制节点。

机器以控制器指令序列的起点为始，当执行至指令序列的末端时结束。不过在分支改变控制流时是个例外，此时的指令将按它们列表排列的顺序执行。

下图展示了 GCD 机器的描述方式。这个示例只是大体描述 GCD 机器的较简单情况。其中每个寄存器只有一个按钮，每个按钮和检测只被控制器使用一次。

不过上述机器描述可读性较差。因为为了理解指令，我们不得不回去查询按钮名称和操作名称，接着为了理解按钮的行为，我们可能需要回到操作名称的定义处。因此我们需要转换描述，将数据路径和控制器描述结合以方便同时查阅。

为了构建这种形式的描述，需要取缔按钮和操作名称根据其行为进行名称定义的随意性。也就是说，在控制器中表示「按下按钮 t<-r」需要分别替换为数据路径中的「按钮 t<-r 将操作 rem 中的值分配给了寄存器 t」，「rem 操作的输入是寄存器 a 和 b 的值」，转换后也就是在控制器中我们会描述为「按下该按钮，会将寄存器 a 和寄存器 b 中的数据通过 rem 操作计算的结果分配给寄存器 t」。与之类似，在控制器中描述「执行 = 检测」，在数据路径中表示「= 检测操作寄存器 b 的数据和常量 0」。最终我们会忽略数据路径描述的部分，只留下控制器序列。所以，GCD 机器的描述如下。

(controller
 test-b
   (test (op =) (reg b) (const 0))
   (branch (label gcd-done))
   (assign t (op rem) (reg a) (reg b))
   (assign a (reg b))
   (assign b (reg t))
   (goto (label test-b))
 gcd-done)

这种描述方式更具可读性，但它也有一些缺点。

• 对于大型机器来说该描述过于冗长，因为控制器指令序列为了完整描述数据路径，将导致这些数据路径的元素重复出现在描述中。虽然在 GCD 的示例中这尚未构成问题，但当实例中按钮和操作不止一次被使用时情况将发生变化。甚至，在重复的数据路径描述中数据路径的结构将变得模糊。特别是对于大型机器，它拥有寄存器、操作和按钮的数量，及它们如何连接将难以分辨。
• 由于控制器指令的定义与 Lisp 表达式类似，容易忘记区分将其与 Lisp 表达式混淆，但它们只能够表示合法的机器操作。例如，操作只能够直接操作常量和寄存器内容，而不能操作操作计算结果。

即使存在上述缺陷，我们还是打算在本章使用该寄存器机器语言，因为我们更加关心对于控制器的理解，而不是数据路径中的元素和连接关系。不过，我们需要记住在真实的机器设计中数据路径设计才是关键所在。

现在我们需要修改 GCD 机器，使其能够计算我们输入数字的 GCD 值，并将结果打印在终端。我们并不打算讨论如何使机器读取内容和打印结果，所以直接假设目前已经存在一些基础操作能够完成读取和打印的需求（就像我们在 Scheme 中使用 read 和 display 一样）。

read 操作能够用于产生一个数据，并能够存储于寄存器中。但 read 并不能以任意寄存器作为输入，它的数据来自机器外部。同时我们将允许机器的行为也拥有类似特性，接下来便可以通过 read 和其他操作描绘计算数据的过程。

print 与之前按基础方式使用的操作有所不同。它并不会产生输出结果并存储于寄存器中。虽然它会产生一些结果，但这些结果并不显现于机器内部。我们将这类操作称为 动作（action）。我们将在数据路径图示中描述动作，如同之前描述计算数值的操作一样，通过一个包含动作名称的梯形表示。指向动作组件的箭头可以来自寄存器或常量，也可以为该箭头分配一个按钮。当按下该按钮时此动作将运行。我们通过一种新指令 perform 使控制器按下动作的按钮。所以，打印寄存器 a 内容的动作可以表示为下列控制器指令。

(perform (op print) (reg a))

下图展示了新的 GCD 机器的数据路径和控制器。不过在打印结果后我们并没有让机器停止，而是使其继续运作，不断读取数据继续计算这对数据 GCD 结果，并将结果打印。该结构与第四章使用的驱动循环十分类似。

通常在定义机器时会现出一些较复杂的基础操作。例如，后续章节中会将 Scheme 环境操作视为基础操作。因为抽象能够让我们忽略机器的某些细节，集中精力在设计中需要关心的部分，所以它具有一定的价值。虽然通过抽象能够清除大量的复杂性，但并不意味着机器设计是不切实际的。我们也能够将更简单的基础操作替换复杂的基础操作。

以 GCD 机器为实例思考。机器中存在计算寄存器 a 和 b 的数据余数的指令，并且该指令能够将计算结果存入寄存器 t 中。如果我们打算不通过基础求余操作构建 GCD 机器，就必须明确使用更简单的操作实现余数计算的方式。于是，我们可以编写下列 Scheme 程式实现求余。

(define (remainder n d)
  (if (< n d)
      n
      (remainder (- n d) d)))

所以只要通过减法操作和比较检测就能够替换 GCD 机器中的求余操作。下图展示了该机器的数据路径和控制器。

GCD 控制器中的指令 (assign t (op rem) (reg a) (reg b)) 被一个含有循环的指令序列替换，如下图。

在设计执行计算的机器时，我们通常更倾向于在不同的计算模块间共享计算组件，而不是重复制造计算组件。思考一台包含两个 GCD 运算机器，一个 GCD 运算输入数据来源于寄存器 a 和 b，而另一个 GCD 计算数据来源于寄存器 c 和 d。开始时，我们会假设自己拥有一个基础操作 gcd，并在此基础上扩展两个 gcd 实例。如下图，它展示了机器的 GCD 计算部分的数据路径，但没有展示这些计算部分如何与机器的其他部分连接。同时图示还展示了机器 GCD 计算对应的控制器序列部分。

该机器拥有两个求余操作以及两个相等检测。重复组件不仅使机器复杂化，同时也不经济。通过在 GCD 计算中使用相同的组件能够避免数据路径中重复组件的情况，并且也不会影响大型计算的其他计算部件。如果寄存器 a 和 b 的值暂时不被控制器 gcd-2 需要（或者这些数据能够被移动至其他寄存器并安全保存），我们便能改变机器使其能够使用寄存器 a 和 b，而不是只能使用寄存器 c 和 d。如果按此方式实现，将产生如下图的控制器序列。

虽然我们已经移除了重复的数据路径组件，但控制器还是存在两个 GCD 序列，而它们的区别仅在于入口标识的不同。如果将两个序列通过分支的方式实现为一个序列将会是更好的方式，这种分支方式称为 子程序（subroutine），在每个序列结尾都返回至主指令序列的对应节点。可以通过下列方式实现，首先在将 gcd 进行分支前，需要将一个不同的数值（比如 0 或 1）存入一个特别的寄存器 continue。在 gcd 子程序的结尾我们将返回 after-gcd-1 或 after-gcd-2，返回结果根据 continue 寄存器中的值确定。下图展示了该控制器的相关部分，它只包含 gcd 指令的一个单独拷贝。

虽然该方法有效解决了控制器重复的问题，但如果存在大量的 GCD 计算实例时将出现糟糕的情况。为了确定在 gcd 子程序之后如何继续执行，可能需要在数据路径中进行检测，并导向所有使用 gcd 的地方。更好的方法是使 continue 寄存器保存控制器序列的子程序执行完成后将要继续执行的入口标识。要实现这种策略需要在数据路径和寄存器机器之间构建一种新的连接方式。这种方式能够给寄存器分配一个标识，并且这个值能从寄存器中取出，并继续进入对应的入口标识继续执行。

要实现这种特性，需要扩展 assign 指令，使寄存器能够被赋值来自控制器序列的标识（也就是一种特殊类型的常量）。同时还需要扩展 goto 指令，使其能够根据寄存器中描述的入口标识继续执行，而不是只能根据入口点的常量标识执行。通过这些新特性，gcd 子程序便能够根据 continue 寄存器中的存储的内容进行跳转。修改后的控制器序列如下。

拥有超过一个子程序的机器会使用多延续寄存器（例如 gcd-continue、factorial-continue）或者所有子程序都共享一个 continue 寄存器。共享策略是更加经济的选择，但当存在一个子程序 sub1 调用另一个子程序 sub2 时必须保持警惕。如果在调用 sub2 重新赋值 continue 之前，sub1 没有将 continue 的内容转移至其他寄存器中，sub1 在运行结束后将无从知晓该向哪里跳转。下一节实现的机制需要处理递归，同时要为内嵌子程序的调用提供一个良好的解决方案。

根据之前讲解的理论，我们能够利用寄存器机器和对应的状态变量实现任何迭代过程。寄存器机器会重复执行控制器循环并改变寄存器存储内容，直到达到终止条件为止。在控制器序列的每个节点中，机器状态（迭代过程中的状态）完全由寄存器存储内容（状态变量数据）决定。

不过要实现递归过程就需要另一套理论了。思考下列计算阶乘的递归方法。

(define (factorial n)
  (if (= n 1) 1 (* (factorial (- n 1) n))))

如同我们从上述程式中看到的一样，计算 n! 结果的前提是得到 (n-1)! 的结果。这与 GCD 机器的程式模型十分类似。不过它与 gcd 程式之间有些许不同，gcd 程式会将原先的 GCD 计算转换为新的 GCD 计算，而对于 factorial 需要将需要将其他的阶乘作为子问题进行计算。在 GCD 中，新的 GCD 计算产生的结果便是最初计算的结果。如果要计算下一个 GCD，只需要将新参数存储至输入寄存器中，继续执行相同的控制器序列，重复应用数据路径即可。当机器完成了最后的 GCD 计算就意味着整个 GCD 计算的完结。

而在阶乘的例子（或者说递归过程的例子）中，阶乘子问题的计算结果并不是初始问题的答案。计算 (n-1)! 得到的结果必须与 n 相乘才是最终的答案。如果我们打算模仿 GCD 的设计实现阶乘，便需要 n 递减的寄存器并重复运行阶乘机器，而我们将难以得到一个可用的 n 的数据进行相乘得出最终结果。因为我们需要通过第二台阶乘机器解决阶乘的子问题。以此类推，第二台阶乘机器需要第三台阶乘机器帮助它完成阶乘子问题的计算。于是每台阶乘机器中都含有另一台解决子问题的阶乘机器，也就是说整个阶乘机器将含有无限内嵌的类似的机器，它的结构也不是固定的、有限的。

不过我们可以将阶乘过程实现为一个寄存器机器，并为每个内嵌的机器实例分配类似的组件。也就是说，计算 n! 的机器应该使用相同的组件计算 (n-1)! 等子问题。尽管阶乘过程复述拷贝自类似机器的未绑定数据，并使用这些数据进行运算，而且要保持这些拷贝中的一个在任何时刻都可用，但这个方案还是可行的。当机器发现一个递归子问题时，它能够在主问题中将当前工作挂起，然后使用类似的机器结构运算子问题，以及在继续出现子问题时将当前计算挂起。

在子问题中，寄存器的存储内容与在主问题中存储的内容有所不同。在本例中寄存器 n 是递减的。为了能够继续将运算过程挂起，机器必须能够保存任意寄存器的内容，并在子问题运算完成后恢复这些内容继续运行之前被挂起的运算过程。在阶乘的例子中，我们需要储存 n 的旧数据，并在完成递减的 n 寄存器后能够将存储内容恢复。

在深层的递归调用时并不存在先验限制，我们可能需要保存寄存器的数据。当这个递归的最后一个子问题运算完成时，这些数据需要按存储的相反顺序恢复。这个过程可以用 堆（stack） 表示，或者也可以说成「后进先出」数据结构，对寄存器数据进行存储。通过添加两种指令便能够使寄存器机器语言支持堆这种数据结构。通过 save 指令能够将数据存入堆中，通过 restore 指令能够从堆中取出数据。在堆中存入一组数据后，通过 restore 会将这组数据按相反的顺序取出。

在堆的帮助下，我们便能轻易重复使用每个阶乘子问题的机器数据路径。不过存在一个与重复使用控制器序列操作数据路径类似的问题。为了重复执行阶乘运算，控制器不能循环回到起始节点，因为在解决 (n-1)! 子问题后，机器必须将该计算结果与 n 相乘。而控制器也必须将 n! 的运算挂起，才能进行 (n-1)! 子问题的运算，在子问题运算完成之后才能继续主问题的运算。所以阶乘计算的情况比较适合使用子程序机制，通过 continue 寄存器转换子问题计算的序列，然后从主问题中断的节点再继续进行计算。所以，我们可以创建一个阶乘子程序，该子程序能够返回存储于 continue 寄存器中的入口节点。在每次子程序调用的前后，我们相继从 continue 寄存器中存入和取出入口节点，如同对 n 寄存器的操作一样，而阶乘计算的每个层级都将使用同样的 continue 寄存器。当阶乘子程序需要运算自身的子问题时，需要在 continue 寄存器中存入新的数值，而且它还需要原有的数值帮助子程序返回调用它的地方。

下图展示了实现递归 factorial 程式的机器的数据路径和控制器。该机器拥有一个堆和三个寄存器，分别叫做 n、val 和 continue。为了简化数据路径，我们没有为寄存器赋值按钮命名，只为堆操作按钮进行了命名（sc 和 sn 是向寄存器存储数据，rc 和 rn 是从寄存器中取出数据）。为了运行该机器，需要在寄存器 n 中存入打算进行阶乘计算的数值。当机器到达 fact-done 节点时，阶乘计算结束，并且在 val 寄存器中存储着计算结果。在控制器序列中，n 和 continue 在每次递归调用前都会进行储存，在递归调用后会将储存的数据取出。在调用运算结束后，它将通过 continue 中储存的标识进行跳转。在机器启动时 continue 的初始值是机器的结束节点 fact-done。val 寄存器会存储阶乘运算的结果，不过在递归调用前其中并不会存入任何内容，因为 val 的原有内容只有子程序返回后才会失效。此时只有子运算产生的结果才是有用的数据，它也会作为新数据存入 val 寄存器中。

尽管阶乘运算的概念需要无限机器作为基础，但上图中的机器除了堆模块实际是一个有限结构。不过，任何堆的特殊实现也是有限大小的，这也将限制机器的递归调用层级。阶乘的实现只是为了解释递归算法的常用策略，主要是使用堆存储寄存器机器数据。当遭遇递归子问题时，我们将在堆中存储当前子问题运算结束后需要被应用的寄存器数据，然后恢复存储于堆中的寄存器数据并继续运行主问题，我们通过这种方式处理递归问题。continue 寄存器问题被存入数据。是否还有其他的寄存器的数据需要存储要根据机器的需要，因为不是所有递归运算都会在子问题运算期间修改寄存器的原始数据。

下面我们将研究一个更加复杂的递归，就是在以前章节介绍过的斐波那契数列。

(define (fib n)
  (if (< n 2)
      n
      (+ (fib (- n 1)) (fib (- n 2)))))

在计算阶乘的部分我们实现了一个递归的阶乘运算过程，其中使用了寄存器 n、val 和 continue。不过斐波那契机器比阶乘机器更加复杂，因为在该机器的控制器序列中有两个节点会执行递归调用，一个节点是计算 Fib(n-1)，另一个节点是计算 Fib(n-2)。为了使这些递归调用都正常运行，我们需要将递归调用后需要使用的数值储存至寄存器，可以将递归计算 Fib 函数的值存储在寄存器 n 中，并将递归结束后继续拆迁的主序列中断点记录在 continue 中，然后回到 fib-loop 节点。当递归调用返回结束时，计算结果存储于 val 中。下图展示了该机器的控制器序列。

在我们的寄存器机器语言中的控制器指令为下列形式中的任意一种，每个 <inputi> 是 (reg <register-name>) 或 (const <contant-value>) 中的一种。下面这些指令已经讲解过了，这里只是进行汇总。

(assign <register-name> (reg <register-name>))
(assign <register-name> (const <constant-value>))
(assign <register-name>
        (op <operation-name>)
        <input1> ... <inputn>)
(perform (op <operation-name>) <input1> ... <inputn>)
(test (op <operation-name>) <input1> ... <inputn>)
(branch (label <label-name>))
(goto (label <label-name>))

下面的指令是使用寄存器处理标识的。

(assign <register-name> (label <label-name>))
(goto (reg <register-name>))

下面为堆的相关指令。

(save <register-name>)
(restore <register-name>)

这些指令中只有 <constant-value> 是数字，不过稍后也会出现字符串、标识和列表的情况。如下。

(const "abc")    ; is the string "abc"
(const abc)      ; is the symbol abc
(const (a b c))  ; is the list (a b c)
(const ())       ; is the empty list