SICP 全笔记

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 可以帮助我们了解我们接下来要做的事情。