Exercise 3.30 · 习题

Exercise 3.30: Figure 3.27 shows a

ripple-carry adder formed by stringing together n full-adders.
This is the simplest form of parallel adder for adding two n-bit binary
numbers. The inputs A
1, A
2, A
3, …, A
n and
B
1, B
2, B
3,
…, B
n are the two binary numbers to be added (each A
k and
B
k is a 0 or a 1). The circuit generates S
1, S
2,
S
3, …, S
n,
the n bits of the sum, and C, the carry from the addition. Write a
procedure ripple-carry-adder that generates this circuit. The procedure
should take as arguments three lists of n wires each—the A
k, the
B
k, and the S
k—and also another wire C. The major drawback of the
ripple-carry adder is the need to wait for the carry signals to propagate.
What is the delay needed to obtain the complete output from an n-bit
ripple-carry adder, expressed in terms of the delays for and-gates, or-gates,
and inverters?

SVG

Figure 3.27: A ripple-carry adder for n-bit numbers.

Representing wires

A wire in our simulation will be a computational object with two local state
variables: a signal-value (initially taken to be 0) and a collection of
action-procedures to be run when the signal changes value. We implement
the wire, using message-passing style, as a collection of local procedures
together with a dispatch procedure that selects the appropriate local
operation, just as we did with the simple bank-account object in
3.1.1:

(define (make-wire)
(let ((signal-value 0)
(action-procedures '()))
(define (set-my-signal! new-value)
(if (not (= signal-value new-value))
(begin (set! signal-value new-value)
(call-each
action-procedures))
'done))
(define (accept-action-procedure! proc)
(set! action-procedures
(cons proc action-procedures))
(proc))
(define (dispatch m)
(cond ((eq? m 'get-signal)
signal-value)
((eq? m 'set-signal!)
set-my-signal!)
((eq? m 'add-action!)
accept-action-procedure!)
(else (error "Unknown operation:
WIRE" m))))
dispatch))

The local procedure set-my-signal! tests whether the new signal value
changes the signal on the wire. If so, it runs each of the action procedures,
using the following procedure call-each, which calls each of the items
in a list of no-argument procedures:

(define (call-each procedures)
(if (null? procedures)
'done
(begin ((car procedures))
(call-each (cdr procedures)))))

The local procedure accept-action-procedure! adds the given procedure to
the list of procedures to be run, and then runs the new procedure once. (See
Exercise 3.31.)

With the local dispatch procedure set up as specified, we can provide
the following procedures to access the local operations on
wires:

(define (get-signal wire)
(wire 'get-signal))
(define (set-signal! wire new-value)
((wire 'set-signal!) new-value))
(define (add-action! wire action-procedure)
((wire 'add-action!) action-procedure))

Wires, which have time-varying signals and may be incrementally attached to
devices, are typical of mutable objects. We have modeled them as procedures
with local state variables that are modified by assignment. When a new wire is
created, a new set of state variables is allocated (by the let
expression in make-wire) and a new dispatch procedure is
constructed and returned, capturing the environment with the new state
variables.

The wires are shared among the various devices that have been connected to
them. Thus, a change made by an interaction with one device will affect all
the other devices attached to the wire. The wire communicates the change to
its neighbors by calling the action procedures provided to it when the
connections were established.

The agenda

The only thing needed to complete the simulator is after-delay. The
idea here is that we maintain a data structure, called an
agenda,
that contains a schedule of things to do. The following operations are defined
for agendas:

(make-agenda) returns a new empty agenda.

(empty-agenda? ⟨agenda⟩) is true if the specified agenda is
empty.

(first-agenda-item ⟨agenda⟩) returns the first item on the
agenda.

(remove-first-agenda-item! ⟨agenda⟩) modifies the agenda by
removing the first item.

(add-to-agenda! ⟨time⟩ ⟨action⟩ ⟨agenda⟩)
modifies the agenda by adding the given action procedure to be run at the
specified time.

(current-time ⟨agenda⟩) returns the current simulation time.

The particular agenda that we use is denoted by the-agenda. The
procedure after-delay adds new elements to the-agenda:

(define (after-delay delay action)
(add-to-agenda!
(+ delay (current-time the-agenda))
action
the-agenda))

The simulation is driven by the procedure propagate, which operates on
the-agenda, executing each procedure on the agenda in sequence. In
general, as the simulation runs, new items will be added to the agenda, and
propagate will continue the simulation as long as there are items on the
agenda:

(define (propagate)
(if (empty-agenda? the-agenda)
'done
(let ((first-item
(first-agenda-item the-agenda)))
(first-item)
(remove-first-agenda-item! the-agenda)
(propagate))))

A sample simulation

The following procedure, which places a “probe” on a wire, shows the
simulator in action. The probe tells the wire that, whenever its signal
changes value, it should print the new signal value, together with the current
time and a name that identifies the wire:

(define (probe name wire)
(add-action!
wire
(lambda ()
(newline)
(display name)
(display " ")
(display (current-time the-agenda))
(display " New-value = ")
(display (get-signal wire)))))

We begin by initializing the agenda and specifying delays for the primitive
function boxes:

(define the-agenda (make-agenda))
(define inverter-delay 2)
(define and-gate-delay 3)
(define or-gate-delay 5)

Now we define four wires, placing probes on two of them:

(define input-1 (make-wire))
(define input-2 (make-wire))
(define sum (make-wire))
(define carry (make-wire))

(probe 'sum sum)
sum 0 New-value = 0

(probe 'carry carry)
carry 0 New-value = 0

Next we connect the wires in a half-adder circuit (as in Figure 3.25),
set the signal on input-1 to 1, and run the simulation:

(half-adder input-1 input-2 sum carry)
ok

(set-signal! input-1 1)
done

(propagate)
sum 8 New-value = 1
done

The sum signal changes to 1 at time 8. We are now eight time units from
the beginning of the simulation. At this point, we can set the signal on
input-2 to 1 and allow the values to propagate:

(set-signal! input-2 1)
done

(propagate)
carry 11 New-value = 1
sum 16 New-value = 0
done

The carry changes to 1 at time 11 and the sum changes to 0 at

time 16.

练习 3.30：图 3.27 展示了一个行波进位加法器 (ripple-carry adder)，由 n 个全加器串联而成。这是将两个 n 位二进制数相加的最简单并行加法器形式。输入 A₁、A₂、A₃、……、Aₙ 和 B₁、B₂、B₃、……、Bₙ 是两个待相加的二进制数（每个 Aₖ 和 Bₖ 均为 0 或 1）。电路产生 S₁、S₂、S₃、……、Sₙ（即和的 n 位）以及 C（进位）。请编写一个过程 ripple-carry-adder 来生成此电路。该过程应以三组各含 n 条连线的表为参数——即 Aₖ、Bₖ 和 Sₖ——以及另一条连线 C。行波进位加法器的主要缺点是需要等待进位信号逐级传播。请用与门、或门和反门的延迟时间来表达从一个 n 位行波进位加法器获得完整输出所需的延迟。

SVG

图 3.27：n 位数的行波进位加法器。

表示连线

在我们的模拟中，一条连线是一个带有两个局部状态变量的计算对象：一个 signal-value（初始值取为 0）和一组在信号值改变时运行的 action-procedures（动作过程）。我们用消息传递风格实现连线，将其作为一组局部过程和一个分派过程的集合——该分派过程选择适当的局部操作，就像我们在 3.1.1 节中处理简单银行账户对象时所做的那样：

(define (make-wire)
(let ((signal-value 0)
(action-procedures '()))
(define (set-my-signal! new-value)
(if (not (= signal-value new-value))
(begin (set! signal-value new-value)
(call-each
action-procedures))
'done))
(define (accept-action-procedure! proc)
(set! action-procedures
(cons proc action-procedures))
(proc))
(define (dispatch m)
(cond ((eq? m 'get-signal)
signal-value)
((eq? m 'set-signal!)
set-my-signal!)
((eq? m 'add-action!)
accept-action-procedure!)
(else (error “Unknown operation:\nWIRE” m))))
dispatch))

局部过程 set-my-signal! 检测新信号值是否改变了连线上的信号。若是，它使用如下过程 call-each 依次运行每个动作过程，call-each 负责调用一个无参过程表中的每一项：

(define (call-each procedures)
(if (null? procedures)
'done
(begin ((car procedures))
(call-each (cdr procedures)))))

局部过程 accept-action-procedure! 将给定过程加入待运行的过程表，然后立即运行一次新过程。（参见练习 3.31。）

有了上述局部分派过程，我们可以提供以下过程来访问连线的局部操作：

(define (get-signal wire)
(wire 'get-signal))
(define (set-signal! wire new-value)
((wire 'set-signal!) new-value))
(define (add-action! wire action-procedure)
((wire 'add-action!) action-procedure))

连线具有随时间变化的信号，并可随时连接到各种器件，是典型的可变对象。我们将其建模为带有局部状态变量的过程，这些变量通过赋值加以修改。每当创建一条新连线，就会分配一组新的状态变量（由 make-wire 中的 let 表达式完成），并构造并返回一个新的分派过程，该过程捕获了含有新状态变量的环境。

各连线由已连接到它的各种器件共享。因此，与某一器件交互所产生的变化将影响所有连接到该连线的其他器件。连线通过调用在建立连接时提供给它的动作过程，将变化通知其邻居。

议程

完成模拟器所需的最后一个要素是 after-delay。其思路是维护一个称为议程 (agenda) 的数据结构，其中包含待执行事项的调度表。以下操作定义于议程之上：

(make-agenda) 返回一个新的空议程。

(empty-agenda? ⟨agenda⟩) 若指定议程为空则为真。

(first-agenda-item ⟨agenda⟩) 返回议程中的第一项。

(remove-first-agenda-item! ⟨agenda⟩) 通过移除第一项来修改议程。

(add-to-agenda! ⟨time⟩ ⟨action⟩ ⟨agenda⟩) 通过添加给定动作过程（在指定时刻运行）来修改议程。

(current-time ⟨agenda⟩) 返回当前模拟时间。

我们使用的具体议程记为 the-agenda。过程 after-delay 向 the-agenda 添加新元素：

(define (after-delay delay action)
(add-to-agenda!
(+ delay (current-time the-agenda))
action
the-agenda))

模拟由过程 propagate 驱动，它在 the-agenda 上运作，按顺序执行议程中的每个过程。一般而言，模拟运行时会不断向议程中添加新项，propagate 将持续模拟，直到议程中没有任何项目为止：

(define (propagate)
(if (empty-agenda? the-agenda)
'done
(let ((first-item
(first-agenda-item the-agenda)))
(first-item)
(remove-first-agenda-item! the-agenda)
(propagate))))

一个模拟示例

下面的过程在一条连线上放置一个“探针”，展示模拟器的运行效果。探针告知连线：每当其信号值改变时，应打印新的信号值，连同当前时间以及标识该连线的名称：

(define (probe name wire)
(add-action!
wire
(lambda ()
(newline)
(display name)
(display “ ”)
(display (current-time the-agenda))
(display “ New-value = ”)
(display (get-signal wire)))))

我们首先初始化议程并指定各基本功能盒的延迟时间：

(define the-agenda (make-agenda))
(define inverter-delay 2)
(define and-gate-delay 3)
(define or-gate-delay 5)

接下来定义四条连线，并在其中两条上放置探针：

(define input-1 (make-wire))
(define input-2 (make-wire))
(define sum (make-wire))
(define carry (make-wire))

(probe 'sum sum)
sum 0 New-value = 0

(probe 'carry carry)
carry 0 New-value = 0

然后将连线接入一个半加器电路（如图 3.25 所示），将 input-1 的信号设为 1，并运行模拟：

(half-adder input-1 input-2 sum carry)
ok

(set-signal! input-1 1)
done

(propagate)
sum 8 New-value = 1
done

sum 信号在时刻 8 变为 1。此时距模拟开始已过去 8 个时间单位。接着，我们将 input-2 的信号设为 1，并让各值继续传播：

(set-signal! input-2 1)
done

(propagate)
carry 11 New-value = 1
sum 16 New-value = 0
done

carry 在时刻 11 变为 1，sum 在时刻 16 变为 0。