In order to gain a good understanding of the design of register machines, we
must test the machines we design to see if they perform as expected. One way
to test a design is to hand-simulate the operation of the controller, as in
Exercise 5.5. But this is extremely tedious for all but the simplest
machines. In this section we construct a simulator for machines described in
the register-machine language. The simulator is a Scheme program with four
interface procedures. The first uses a description of a register machine to
construct a model of the machine (a data structure whose parts correspond to
the parts of the machine to be simulated), and the other three allow us to
simulate the machine by manipulating the model:
为了深入理解寄存器机器的设计,我们必须对所设计的机器进行测试,以验证它们是否按预期运行。一种测试方法是手动模拟控制器的操作,如练习 5.5 所示;但对于除最简单的机器之外的所有情形,这样做极为繁琐。在本节中,我们为用寄存器机器语言描述的机器构建一个模拟器。该模拟器是一个 Scheme 程序,提供四个接口过程:第一个过程利用寄存器机器的描述构造出该机器的模型(一种数据结构,其各部分与待模拟机器的各部分相对应),其余三个过程允许我们通过操纵该模型来模拟机器:
constructs and returns a model of the machine with the given registers,
operations, and controller.
构造并返回一台具有给定寄存器、操作和控制器的机器模型。
stores a value in a simulated register in the given machine.
在给定机器的模拟寄存器中存入一个值。
returns the contents of a simulated register in the given machine.
返回给定机器的模拟寄存器中的内容。
simulates the execution of the given machine, starting from the beginning of
the controller sequence and stopping when it reaches the end of the sequence.
从控制器序列的开头开始模拟给定机器的执行,直至到达序列末尾时停止。
As an example of how these procedures are used, we can define
gcd-machine to be a model of the GCD machine of
5.1.1 as follows:
作为这些过程用法的示例,我们可以将 gcd-machine 定义为 5.1.1 中 GCD 机器的模型,如下所示:
The first argument to make-machine is a list of register names. The
next argument is a table (a list of two-element lists) that pairs each
operation name with a Scheme procedure that implements the operation (that is,
produces the same output value given the same input values). The last argument
specifies the controller as a list of labels and machine instructions, as in
5.1.
make-machine 的第一个参数是寄存器名称的表。下一个参数是一张表(由二元素表构成的表),它将每个操作名与实现该操作的 Scheme 过程配对(即对相同的输入值产生相同的输出值)。最后一个参数将控制器指定为标号和机器指令的表,如 5.1 所述。
To compute GCDs with this machine, we set the input registers, start
the machine, and examine the result when the simulation terminates:
要用这台机器计算 GCD,我们设置输入寄存器,启动机器,并在模拟结束时检查结果:
This computation will run much more slowly than a gcd procedure written
in Scheme, because we will simulate low-level machine instructions, such as
assign, by much more complex operations.
这一计算的运行速度将远低于用 Scheme 直接编写的 gcd 过程,因为我们要用复杂得多的操作来模拟底层的机器指令,例如 assign。
(make-machine ⟨register-names⟩
⟨operations⟩
⟨controller⟩) (set-register-contents! ⟨machine-model⟩
⟨register-name⟩
⟨value⟩) (get-register-contents ⟨machine-model⟩
⟨register-name⟩) (start ⟨machine-model⟩) (define gcd-machine
(make-machine
'(a b t)
(list (list 'rem remainder) (list '= =))
'(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))) (set-register-contents! gcd-machine 'a 206)
done
(set-register-contents! gcd-machine 'b 40)
done
(start gcd-machine)
done
(get-register-contents gcd-machine 'a)
2