5.1.3 Subroutines

When designing a machine to perform a computation, we would often prefer to

arrange for components to be shared by different parts of the computation

rather than duplicate the components. Consider a machine that includes two

GCD computations—one that finds the GCD of the contents

of registers a and b and one that finds the GCD of the

contents of registers c and d. We might start by assuming we

have a primitive gcd operation, then expand the two instances of

gcd in terms of more primitive operations. Figure 5.7 shows just

the GCD portions of the resulting machine’s data paths, without

showing how they connect to the rest of the machine. The figure also shows the

corresponding portions of the machine’s controller sequence.

在设计机器以执行某个计算时，我们通常希望让各部分计算共用同一组组件，而不是重复配置。考虑一台包含两个 GCD 计算的机器——一个求寄存器 a 和 b 的内容的最大公约数，另一个求寄存器 c 和 d 的内容的最大公约数。我们可以先假设有一个基本的 gcd 操作，再将两个 gcd 的实例展开为更基本的操作。图 5.7 仅展示了所得机器数据通路中与 GCD 相关的部分，未显示它们如何与机器其余部分相连，同时也给出了机器控制器序列中对应的部分。

Figure 5.7: Portions of the data paths and controller sequence for a machine with two GCD computations.

图 5.7：一台含有两个 GCD 计算的机器的数据通路和控制器序列的相关部分。

This machine has two remainder operation boxes and two boxes for testing

equality. If the duplicated components are complicated, as is the remainder

box, this will not be an economical way to build the machine. We can avoid

duplicating the data-path components by using the same components for both

GCD computations, provided that doing so will not affect the rest of

the larger machine’s computation. If the values in registers a and

b are not needed by the time the controller gets to gcd-2 (or if

these values can be moved to other registers for safekeeping), we can change

the machine so that it uses registers a and b, rather than

registers c and d, in computing the second GCD as well

as the first. If we do this, we obtain the controller sequence shown in

Figure 5.8.

这台机器有两个余数操作框和两个用于检测相等性的框。如果被重复的组件很复杂（如余数框），这将不是一种经济的构造方式。我们可以通过让两个 GCD 计算共用同一组组件来避免数据通路组件的重复，前提是这样做不会影响整台机器其余部分的计算。如果在控制器到达 gcd-2 之前寄存器 a 和 b 中的值已经不再需要（或者这些值可以移到其他寄存器中妥善保存），我们就可以修改机器，使其在计算第二个 GCD 时同样使用寄存器 a 和 b，而不是寄存器 c 和 d。这样做之后，我们得到图 5.8 所示的控制器序列。

Figure 5.8: ↓ Portions of the controller sequence for

a machine that uses the same data-path components for two different

GCD computations.

图 5.8：↓ 一台对两个不同 GCD 计算使用相同数据通路组件的机器的控制器序列相关部分。

We have removed the duplicate data-path components (so that the data paths are

again as in Figure 5.1), but the controller now has two GCD

sequences that differ only in their entry-point labels. It would be better to

replace these two sequences by branches to a single sequence—a gcd

我们已经去掉了重复的数据通路组件（使数据通路重新如图 5.1 所示），但控制器现在有两个 GCD 序列，它们的区别仅在于入口标号不同。更好的做法是将这两个序列替换为分支到单一序列——一个 gcd

subroutine—at the end of which we branch back to the correct place

in the main instruction sequence. We can accomplish this as follows: Before

branching to gcd, we place a distinguishing value (such as 0 or 1) into

a special register, continue. At the end of the gcd subroutine

we return either to after-gcd-1 or to after-gcd-2, depending on

the value of the continue register. Figure 5.9 shows the relevant

portion of the resulting controller sequence, which includes only a single copy

of the gcd instructions.

子程序——在其末尾再分支回到主指令序列中的正确位置。实现方法如下：在分支到 gcd 之前，将一个区分值（如 0 或 1）存入一个专用寄存器 continue。在 gcd 子程序的末尾，根据 continue 寄存器的值，返回到 after-gcd-1 或 after-gcd-2。图 5.9 展示了所得控制器序列的相关部分，其中只包含 gcd 指令的一份副本。

Figure 5.9: ↓ Using a continue register to

avoid the duplicate controller sequence in Figure 5.8.

图 5.9：↓ 用 continue 寄存器避免图 5.8 中控制器序列的重复。

This is a reasonable approach for handling small problems, but it would be

awkward if there were many instances of GCD computations in the

controller sequence. To decide where to continue executing after the

gcd subroutine, we would need tests in the data paths and branch

instructions in the controller for all the places that use gcd. A more

powerful method for implementing subroutines is to have the continue

register hold the label of the entry point in the controller sequence at which

execution should continue when the subroutine is finished. Implementing this

strategy requires a new kind of connection between the data paths and the

controller of a register machine: There must be a way to assign to a register a

label in the controller sequence in such a way that this value can be fetched

from the register and used to continue execution at the designated entry point.

对于规模较小的问题，这是一种合理的处理方式，但如果控制器序列中有很多 GCD 计算的实例，就会变得很不方便。为了决定在 gcd 子程序结束后从哪里继续执行，我们需要在数据通路中加入检测，并在控制器中为所有使用 gcd 的位置加入分支指令。实现子程序的一种更强大的方法是：让 continue 寄存器保存控制器序列中某个入口点的标号，子程序结束后从该入口点继续执行。实现这一策略需要在寄存器机器的数据通路与控制器之间建立一种新的连接方式：必须有办法将控制器序列中的一个标号赋值给某个寄存器，使得该值可以从寄存器中取出，并用于在指定的入口点继续执行。

To reflect this ability, we will extend the assign instruction of the

register-machine language to allow a register to be assigned as value a label

from the controller sequence (as a special kind of constant). We will also

extend the goto instruction to allow execution to continue at the entry

point described by the contents of a register rather than only at an entry

point described by a constant label. Using these new constructs we can

terminate the gcd subroutine with a branch to the location stored in the

continue register. This leads to the controller sequence shown in

Figure 5.10.

为了体现这种能力，我们将扩展寄存器机器语言中的 assign 指令，使得寄存器可以被赋予一个来自控制器序列的标号（作为一种特殊的常量）。我们还将扩展 goto 指令，使得执行可以继续到由寄存器内容描述的入口点，而不仅限于由常量标号描述的入口点。利用这些新构件，我们可以用一条分支到 continue 寄存器所存储位置的指令来终止 gcd 子程序。这样得到的控制器序列如图 5.10 所示。

Figure 5.10: ↓ Assigning labels to the

continue register simplifies and generalizes the strategy shown in

Figure 5.9.

图 5.10：↓ 将标号赋给 continue 寄存器，使图 5.9 中的策略得到简化和推广。

A machine with more than one subroutine could use multiple continuation

registers (e.g., gcd-continue, factorial-continue) or we could

have all subroutines share a single continue register. Sharing is more

economical, but we must be careful if we have a subroutine (sub1) that

calls another subroutine (sub2). Unless sub1 saves the contents

of continue in some other register before setting up continue for

the call to sub2, sub1 will not know where to go when it is

finished. The mechanism developed in the next section to handle recursion also

provides a better solution to this problem of nested subroutine calls.

一台含有多个子程序的机器可以使用多个延续寄存器（continuation register）（如 gcd-continue、factorial-continue），也可以让所有子程序共享一个 continue 寄存器。共享更为经济，但若某个子程序（sub1）调用了另一个子程序（sub2），则必须小心处理。除非 sub1 在为调用 sub2 设置 continue 之前，先将 continue 的内容保存到其他寄存器中，否则 sub1 在结束时将不知道该返回到哪里。下一节中为处理递归而发展出的机制，也为这种嵌套子程序调用问题提供了更好的解决方案。