设计一个能执行数字逻辑模拟的系统，是事件驱动的模拟程序的典型代表。在这种系统里，一个活动（“事件”）可能引发后续某个而时间发生的另一些事件，它们又会引发随后的时间以此类推。
模拟数字电路
数字电路的计算模型有一些对象组成，它们对应于构造电路的各种基本构件。这其中有用于传递数字信号的连线，还有不同功能的数字功能块。
逻辑门
逻辑门无疑是数字功能块
高中的数字电路介绍了三种逻辑门。分别是与门，或门，非门。在sicp书中，称为与门，或门，反门。
与门
与门的逻辑很简单，它有两个输入，一个输出。其中，全1出1,有0出0。
或门
或门也有两个输入，一个输出。它的逻辑是有1出1,全0出0
反门
单输入，单输出，对输入取反。
半加器
将基本的供能件组合起来，就可以构造出更复杂的功能。半加器就是一个例子。
半加器包括一个或门，两个与门和一个反门。这个半加器有两个输入信号A和B，以及两个输出S和C。当A和B都出1时，C出1，当A和B之1出1时，S出1。从半加器可以看出，由于延时的存在，这些输出可能在不同的时间产生，有关数字电路设计的的许多困难由延时产生。
构造程序
构造一个程序，使其能支持我们构造模拟连线的计算对象，这种对象能够“保持”信号。电路里的功能块用函数模拟，它们能严格维持信号之间的正确关系。
模拟中用到的第一个基本元素是make_wire，它用于构造连线。例如，我们通过下面的方式构造出6条连线
1
2
3
4
5
6
| const a = make_wire();
const b = make_wire();
const c = make_wire();
const d = make_wire();
const e = make_wire();
const s = make_wire();
|
要把一个功能块连到一组连线上，我们要调用这种功能块的构造函数，把要连接到这一功能块的连线作为实际参数提供给这个函数。
例如：
1
2
3
4
| or_gate(a, b, d);
and_gate(a, b, c);
inverter(c, e);
and_gate(d, e, s);
|
这段程序表示的是上面的半加器。
半加器的构造函数，如下所示，它有四条外部连线以及两条内部连线
1
2
3
4
5
6
7
8
9
| function half_adder(a, b, s, c) {
const d = make_wire();
const e = make_wire();
or_gate(a, b, d);
and_gate(a, b, c);
inverter(c, e);
and_gate(d, e, s);
return "ok";
}
|
做好这种定义的优势是，我们接下来又可以使用half_adder作为基本构件，进一步创造更复杂的电路，例如，全加器。
全加器由两个半加器和一个或门组成。
1
2
3
4
5
6
7
8
9
| function full_adder(a, b, c_in, sum, c_out) {
const s = make_wire();
const c1 = make_wire();
const c2 = make_wire();
half_adder(b, c_in, s, c1);
half_adder(a, s, sum, c2);
or_gate(c1, c2, c_out);
return "ok";
}
|
基本功能块
针对连线，我们要有以下的操作
- get_signal(wire)
返回连线wire上的当前信号值
- set_signal(wire, newvalue)
将连线wire上的信号改为新值value
- add_action(wire, function-of-no-arguments)
这个操作要求，一旦连线wire上的信号值改变，function-of-no-arguments指定的函数就该运行。这种函数可用于把连线wire的值的变化传到其他连线。
除此以外，我们还需要一个函数after_delay，其参数是一个延迟时间和一个函数。after_delay将在指定的时延后执行这个函数
利用这些函数，就可以定义基本的数字逻辑功能。
为了把一个反门连接到输出，我们应该用add_action为输入连线关联一个函数，当输入连线的值改变时这个函数就会执行。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| function inverter(input, output) {
function invert_input() {
const new_value = logical_not(get_signal(input));
after_delay(inverter_delay,
() => set_signal(output, new_value));
}
add_action(input, invert_input);
return "ok";
}
function logical_not(s) {
return s === 0
? 1
: s === 1
? 0
: error(s, "invalid signal");
}
|
与门的情况要更为复杂。因为这种门的输入之一发生变化时，相应的动作函数都要执行。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| function and_gate(a1, a2, output) {
function and_action_function() {
const new_value = logical_and(get_signal(a1),
get_signal(a2));
after_delay(and_gate_delay,
() => set_signal(output, new_value));
}
add_action(a1, and_action_function);
add_action(a2, and_action_function);
return "ok";
}
function logical_and(s1, s2) {
return s1 === 1 && s2 === 1
? 1
: s1 === 0 || s1 === 1
? s2 === 0 || s2 === 1
? 0
: error(s2, "invalid signal")
: error(s1, "invalid signal");
}
|
或门的代码不作解释
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| function or_gate(a1, a2, output) {
function or_action_function() {
const new_value = logical_or(get_signal(a1),
get_signal(a2));
after_delay(or_gate_delay,
() => set_signal(output, new_value));
}
add_action(a1, or_action_function);
add_action(a2, or_action_function);
return "ok";
}
function logical_or(s1, s2) {
return s1 === 0 && s2 === 0
? 0
: s1 === 0 || s1 === 1
? s2 === 0 || s2 === 1
? 1
: error(s2, "invalid signal")
: error(s1, "invalid signal");
}
|
连线的表示
在模拟中，连线是一种包含两个局部状态变量的计算对象，其中一个是信号值signal_value，初始值取作0，另一个是一组函数action_functions。信号值改变时这些函数都应该运行。我们采用消息传递风格，也就是把连线实现成一组局部函数和一个dispatch函数，后者负责选取适当的局部操作。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| function make_wire() {
let signal_value = 0;
let action_functions = null;
function set_my_signal(new_value) {
if (signal_value !== new_value) {
signal_value = new_value;
return call_each(action_functions);
} else {
return "done";
}
}
function accept_action_function(fun) {
action_functions = pair(fun, action_functions);
fun();
}
function dispatch(m) {
return m === "get_signal"
? signal_value
: m === "set_signal"
? set_my_signal
: m === "add_action"
? accept_action_function
: error(m, "unknown operation -- wire");
}
return dispatch;
}
|
这里的set_my_signal检查了新信号值是否改变了连线的信号，如果是，它就调用call_each运行所有的动作函数。
1
2
3
4
5
6
7
8
| function call_each(functions) {
if (is_null(functions)) {
return "done";
} else {
head(functions)();
return call_each(tail(functions));
}
}
|
还记得之前提到过的针对连线，我们应该有的操作吗？现在可以完成它们了
1
2
3
4
5
6
7
8
9
| function get_signal(wire) {
return wire("get_signal");
}
function set_signal(wire, new_value) {
return wire("set_signal")(new_value);
}
function add_action(wire, action_function) {
return wire("add_action")(action_function);
}
|
待处理表
之前还提到过，我们需要一个函数after_delay。为此，我们将维护一个成为待处理表的数据结构。
我们为待处理表定义以下操：
- make_agenda()
返回一个空待处理表
- is_empty_agenda_item(agenda)
在参数待处理表agenda为空时返回true
- first_agenda_item(agenda)
返回待处理表agenda里的第一个项目
- remove_first_agenda_item(agenda)
修改待处理表agenda,删除其中第一个项目
- add_to_agenda(time, action, agenda)
修改待处理表agenda,加入一项，要求在特定时间time运行动作函数action
- current_agenda(agenda)
返回当前模拟的时间
用the_agenda表示待处理表，after_delay的内容就如下
1
2
3
4
5
| function after_delay(delay, action) {
add_to_agenda(delay + current_time(the_agenda),
action,
the_agenda);
}
|
模拟过程则有一个propagate驱动，它会一个个执行the_agenda里的一个个项目。只要待处理表中存在项目，propagate就会一直运行下去
1
2
3
4
5
6
7
8
9
10
| function propagate() {
if (is_empty_agenda(the_agenda)) {
return "done";
} else {
const first_item = first_agenda_item(the_agenda);
first_item();
remove_first_agenda_item(the_agenda);
return propagate();
}
}
|
待处理表的实现
最后，我们要做的就是待处理表的实现。
待处理表由一些时间段组成，每个时间段是由一个数值(表示时间)和一个队列组成的序对，队列里保存着已经安排好将在该时间段运行的函数
注意，在这里FIFO的队列是有必要的，它能够保证我们的操作按顺序执行。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
| function make_time_segment(time, queue) {
return pair(time, queue);
}
function segment_time(s) { return head(s); }
function segment_queue(s) { return tail(s); }
function make_agenda() { return list(0); }
function current_time(agenda) { return head(agenda); }
function set_current_time(agenda, time) {
set_head(agenda, time);
}
function segments(agenda) { return tail(agenda); }
function set_segments(agenda, segs) {
set_tail(agenda, segs);
}
function first_segment(agenda) { return head(segments(agenda)); }
function rest_segments(agenda) { return tail(segments(agenda)); }
function is_empty_agenda(agenda) {
return is_null(segments(agenda));
}
function add_to_agenda(time, action, agenda) {
function belongs_before(segs) {
return is_null(segs) || time < segment_time(head(segs));
}
function make_new_time_segment(time, action) {
const q = make_queue();
insert_queue(q, action);
return make_time_segment(time, q);
}
function add_to_segments(segs) {
if (segment_time(head(segs)) === time) {
insert_queue(segment_queue(head(segs)), action);
} else {
const rest = tail(segs);
if (belongs_before(rest)) {
set_tail(segs, pair(make_new_time_segment(time, action),
tail(segs)));
} else {
add_to_segments(rest);
}
}
}
const segs = segments(agenda);
if (belongs_before(segs)) {
set_segments(agenda,
pair(make_new_time_segment(time, action), segs));
} else {
add_to_segments(segs);
}
}
function remove_first_agenda_item(agenda) {
const q = segment_queue(first_segment(agenda));
delete_queue(q);
if (is_empty_queue(q)) {
set_segments(agenda, rest_segments(agenda));
} else {}
}
function first_agenda_item(agenda) {
if (is_empty_agenda(agenda)) {
error("agenda is empty -- first_agenda_item");
} else {
const first_seg = first_segment(agenda);
set_current_time(agenda, segment_time(first_seg));
return front_queue(segment_queue(first_seg));
}
}
|
待处理表本身是一个一个时间段的一维表格。但我们要在表的头部维持一个当前时间。（即在此之前最后处理的那个动作的时间）。新建的待处理表的当前时间是0。
待处理表为空即其中没有时间段。
加入待处理表的时候，我们应检查待处理表是否为空。如果是，则创建一个时间段，加入待处理表，如果不是，我们就要扫描待处理表，检查其中各时间段的时间，把动作加入与之关联的队列。
参考：
- 3.3.4 A Simulator for Digital Circuits