Exercise 5.1. Design a register machine to compute factorials using the iterative algorithm specified by the following procedure. Draw data-path and controller diagrams for this machine.
(define (factorial n)
(define (iter product counter)
(if (> counter n)
product
(iter (* counter product)
(+ counter 1))))
(iter 1 1))
下面是 data-path 图:
data-path:
1->p 1->c
+-----------+ +---+ +-----------+
+--->| product |<--X---| 1 |---X-->| counter |
| +-+---------+ +-+-+ +-+---------+
| | | | ^
| +---------+ +----+-------+ | |
| | | | | |
| | | | | |
X t1- p | | | | X t2->c
| --+----+-- --v---+--- |
| \ * / \ + / |
| ---+-- ---+-- |
| | | |
| *->t1 X +->t2 X |
| | | |
| +----+ +----+ |
| | t1 | | t2 | |
| +--+-+ +--+-+ |
| | | |
| | | |
+-------------------+ +--------+
(补记:注意 controller 图的意思。data-path 只是表示了链接,但是使用什么顺序按按钮是通过 controller 来表示的)
相对于这个 data-path 图的 controller 图如下:
controller diagram
start
|
+----v-----+
| 1->c |
+----+-----+
v
+----------+
| 1->p |
+----+-----+
|
/--v--\
+----->X > X ------> done
| \--+--/
| |
| +----v-----+
| | +->t2 |
| +----+-----+
| |
| +----v-----+
| | *->t1 |
| +----+-----+
| |
| +----v-----+
| | t1->p |
| +----+-----+
| |
| +----v-----+
| | t2->c |
| +----+-----+
| |
+----------+
那我们画这个图有什么用呢?这个图把一个 Lisp 程序分解为了底层的数据的传递。在第五章中,我们将要模拟这些寄存器,以及数据的流动。画 data-path 可以帮助我们了解我们接下来要做的事情。