NUS CS1101S：SICP JavaScript 描述：三、模块化、对象和状态（3）-阿里云开发者社区

NUS CS1101S：SICP JavaScript 描述：三、模块化、对象和状态（2）https://developer.aliyun.com/article/1427725

练习 3.24

在上面的表实现中，使用equal（由assoc调用）来测试键的相等性。这并不总是适当的测试。例如，我们可能有一个具有数字键的表，在这种情况下，我们不需要与我们查找的数字完全匹配，而只需要在某个公差范围内的数字。设计一个表构造函数make_table，它以一个same_key函数作为参数，该函数将用于测试键的“相等性”。函数make_table应返回一个dispatch函数，该函数可用于访问本地表的适当lookup和insert函数。

练习 3.25

将一维和二维表泛化，展示如何实现一个表，其中值存储在任意数量的键下，并且不同数量的键下可能存储不同的值。lookup和insert函数应以用于访问表的键列表作为输入。

练习 3.26

上面实现的搜索表需要扫描记录列表。这基本上是第 2.3.3 节的无序列表表示。对于大表，可能更有效地以不同的方式构造表。描述一个表实现，其中（键，值）记录使用二叉树组织，假设键可以以某种方式排序（例如，按数字或字母顺序）。（比较第 2 章的练习 2.66。）

练习 3.27

记忆化（也称为制表法）是一种使函数能够记录先前计算过的值的技术。这种技术可以极大地改善程序的性能。记忆化函数维护一个表，其中存储了以产生值的参数为键的先前调用的值。当记忆化函数被要求计算一个值时，它首先检查表，看看值是否已经存在，如果是，就返回该值。否则，它以普通方式计算新值，并将其存储在表中。作为记忆化的一个例子，回想一下第 1.2.2 节中用于计算斐波那契数的指数过程：

function fib(n) {
    return n === 0
           ? 0
           : n === 1
           ? 1
           : fib(n - 1) + fib(n - 2);
}

相同函数的记忆化版本是

const memo_fib = memoize(n => n === 0
                              ? 0
                              : n === 1
                              ? 1
                              : memo_fib(n - 1) +
                                memo_fib(n - 2)
                        );

其中记忆器定义为

function memoize(f) {
    const table = make_table();
    return x => {
               const previously_computed_result =
                   lookup(x, table);
               if (is_undefined(previously_computed_result)) {
                   const result = f(x);
                   insert(x, result, table);
                   return result;
               } else {
                   return previously_computed_result;
               }
           };
}

绘制一个环境图来分析memo_fib(3)的计算。解释为什么memo_fib计算第 n 个斐波那契数的步骤数量与 n 成比例。如果我们简单地将memo_fib定义为memoize(fib)，这种方案是否仍然有效？

3.3.4 数字电路模拟器

设计复杂的数字系统，如计算机，是一项重要的工程活动。数字系统是通过连接简单元素构建的。尽管这些单独元素的行为很简单，但它们的网络可能具有非常复杂的行为。计算机模拟提议的电路设计是数字系统工程师使用的重要工具。在本节中，我们设计了一个用于执行数字逻辑模拟的系统。这个系统代表了一种称为事件驱动模拟的程序类型，其中动作（“事件”）触发以后发生的更多事件，这些事件又触发更多事件，依此类推。

我们的电路的计算模型将由与构成电路的基本组件对应的对象组成。有电线，它们携带数字信号。数字信号在任何时刻只能有两个可能值之一，0 和 1。还有各种类型的数字功能框，它们将携带输入信号的电线连接到其他输出电线。这些框从它们的输入信号计算输出信号。输出信号的延迟时间取决于功能框的类型。例如，反相器是一个原始功能框，它反转其输入。如果反相器的输入信号变为 0，则一个反相器延迟后，反相器将把其输出信号更改为 1。如果反相器的输入信号变为 1，则一个反相器延迟后，反相器将把其输出信号更改为 0。我们以图 3.24 中的符号来绘制反相器。与门也显示在图 3.24 中，它是一个具有两个输入和一个输出的原始功能框。它将其输出信号驱动到与输入的逻辑与值相同的值。也就是说，如果其两个输入信号都变为 1，则一个与门延迟时间后，与门将强制其输出信号为 1；否则输出将为 0。或门是一个类似的两输入原始功能框，它将其输出信号驱动到与输入的逻辑或值相同的值。也就是说，如果至少一个输入信号为 1，则输出将变为 1；否则输出将变为 0。

图 3.24 数字逻辑模拟器中的原始函数。

我们可以将原始函数连接在一起，以构建更复杂的函数。为了实现这一点，我们将一些功能框的输出连接到其他功能框的输入。例如，图 3.25 中显示的半加器电路由一个或门、两个与门和一个反相器组成。它接收两个输入信号A和B，并有两个输出信号S和C。当A和B中恰好有一个为 1 时，S将变为 1，当A和B都为 1 时，C将变为 1。从图中我们可以看到，由于涉及到的延迟，输出可能在不同的时间生成。数字电路设计中的许多困难都源于这一事实。

图 3.25 一个半加器电路。

我们现在将构建一个用于建模我们希望研究的数字逻辑电路的程序。该程序将构建计算对象，对信号进行建模。功能框将由强制执行信号之间正确关系的函数进行建模。

我们模拟的一个基本元素将是一个名为make_wire的函数，用于构建信号线。例如，我们可以按照以下方式构建六根信号线：

const a = make_wire();
const b = make_wire();
const c = make_wire();
const d = make_wire();
const e = make_wire();
const s = make_wire();

我们通过调用一个构造该类型框的函数将一个函数框连接到一组线上。构造函数的参数是要连接到框的线。例如，鉴于我们可以构建与门、或门和反相器，我们可以将图 3.25 中显示的半加器连接在一起：

or_gate(a, b, d);
"ok"
and_gate(a, b, c);
"ok"
inverter(c, e);
"ok"
and_gate(d, e, s);
"ok"

更好的是，我们可以通过定义一个名为half_ adder的函数来显式命名这个操作，该函数构建这个电路，给定要连接到半加器的四根外部线：

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本身作为创建更复杂电路的构建块。例如，图 3.26 展示了由两个半加器和一个或门组成的全加器。我们可以按照以下方式构建一个全加器：

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";
}

定义了full_adder作为一个函数后，我们现在可以将其用作创建更复杂电路的构建块。（例如，参见练习 3.30。）

图 3.26 一个全加器电路。

实质上，我们的模拟器为我们提供了构建电路语言的工具。如果我们采用了我们在第 1.1 节中研究 JavaScript 时所采用的关于语言的一般观点，我们可以说原始功能框构成了语言的原始元素，将框连接在一起提供了一种组合的手段，指定框作为函数的连线模式作为抽象的手段。

原始功能框

原始功能框实现了一根线上的信号变化如何影响其他线上的信号的“力量”。为了构建功能框，我们使用以下操作：

get_signal(wire)
返回信号线上的当前值。
set_signal(wire, new-value):
将信号线上的信号值更改为新值。
add_action(wire, function-of -no-arguments):
断言指定的函数应该在线上的信号值发生变化时运行。这些函数是信号值变化传递给其他线的工具。

此外，我们将使用一个名为after_delay的函数，该函数接受一个时间延迟和一个要运行的函数，并在给定延迟后执行给定的函数。

使用这些功能，我们可以定义原始的数字逻辑功能。要通过反相器将输入连接到输出，我们使用add_action将输入线与一个函数关联起来，每当输入线上的信号值发生变化时，该函数就会运行。该函数计算输入信号的logical_not，然后在一个inverter_delay之后，将输出信号设置为这个新值：

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");
}

与门稍微复杂一些。如果门的任一输入发生变化，则必须运行动作函数。它计算输入电线上的信号值的logical_and（使用类似于logical_not的函数），并设置在and_gate_delay之后在输出电线上发生新值的变化。

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";
}

练习 3.28

将或门定义为原始函数框。您的or_gate构造函数应类似于and_gate。

练习 3.29

构建或门的另一种方法是作为一个复合数字逻辑设备，由与门和反相器构建而成。定义一个函数or_gate来实现这一点。或门的延迟时间是多少，用and_gate_delay和inverter_delay来表示？

练习 3.30

图 3.27 显示了由串联n个全加器形成的链式进位加法器。这是用于加法两个n位二进制数的最简单形式的并行加法器。输入A[1]、A[2]、A[3]，…，A[n]和B[1]、B[2]、B[3]，…，B[n]是要相加的两个二进制数（每个A[k]和B[k]都是 0 或 1）。电路生成 S[1], S [2], S [3], ..., S [n]，和C，加法的进位。编写一个函数ripple_carry_adder来生成这个电路。该函数应该接受三个n个电线的列表作为参数——A[k]、B[k]和S[k]，还有另一个电线C。链式进位加法器的主要缺点是需要等待进位信号传播。以与门、或门和反相器的延迟来表示，获得n位链式进位加法器的完整输出所需的延迟是多少？

图 3.27 一个用于n位数字的链式进位加法器。

代表电线

在我们的模拟中，电线将是一个计算对象，具有两个本地状态变量：signal_value（最初为 0）和要在信号变化时运行的action_functions集合。我们使用消息传递样式实现电线，作为一组本地函数以及选择适当的本地操作的dispatch函数，就像我们在第 3.1.1 节中的简单银行账户对象中所做的那样：

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，该函数调用无参数函数列表中的每个项目：

function call_each(functions) {
    if (is_null(functions)) {
        return "done";
    } else {
        head(functions)();
        return call_each(tail(functions));
    }
}

本地函数accept_action_function将给定的函数添加到要运行的函数列表中，然后运行新函数一次。（参见练习 3.31。）

设置本地dispatch函数后，我们可以提供以下函数来访问线上的本地操作：³⁰

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);
}

电线具有时变信号，可以逐步连接到设备，这是可变对象的典型特征。我们将它们建模为具有本地状态变量的函数，这些状态变量通过赋值进行修改。创建新电线时，将分配一组新的状态变量（通过make_wire中的let语句），并构造并返回一个新的dispatch函数，捕获具有新状态变量的环境。

电线被各种设备共享，这些设备已连接到它们。因此，通过与一个设备的交互所做的更改将影响连接到电线的所有其他设备。电线通过在建立连接时提供的动作函数来将更改通知给其邻居。

议程

完成模拟器所需的唯一事情是after_delay。这里的想法是我们维护一个数据结构，称为agenda，其中包含要执行的计划。议程定义了以下操作：

make_agenda()：
返回一个新的空议程。
is_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添加新元素：

function after_delay(delay, action) {
    add_to_agenda(delay + current_time(the_agenda),
                  action,
                  the_agenda);
}

模拟由propagate函数驱动，该函数按顺序执行the_agenda上的每个函数。一般来说，随着模拟的运行，新的项目将被添加到日程表中，只要日程表上还有项目，propagate就会继续模拟：

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();
    }
}

一个示例模拟

以下函数在动作上放置一个“探针”，展示了模拟器的运行。探针告诉导线，每当其信号值发生变化时，它应该打印新的信号值，以及当前时间和标识导线的名称。

function probe(name, wire) {
    add_action(wire,
               () => display(name + " " +
                             stringify(current_time(the_agenda)) +
                             ", new value = " +
                             stringify(get_signal(wire))));
}

我们首先初始化日程表，并为原始函数框架指定延迟：

const the_agenda = make_agenda();
const inverter_delay = 2;
const and_gate_delay = 3;
const or_gate_delay = 5;

现在我们定义了四根导线，并在其中两根上放置了探针：

const input_1 = make_wire();
const input_2 = make_wire();
const sum = make_wire();
const 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。现在距离模拟开始已经过去了八个时间单位。此时，我们可以将input_2上的信号设置为 1，并允许值传播：

set_signal(input_2, 1);
"done"
propagate();
"carry 11, new value = 1"
"sum 16, new value = 0"
"done"

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

练习 3.31

在make_wire中定义的内部函数accept_action_function指定了当新的动作函数被添加到导线时，立即运行该函数。解释为什么这种初始化是必要的。特别是，通过上面段落中的半加器示例追踪，并说出如果我们将accept_action_function定义为何，系统的响应会有何不同

function accept_action_function(fun) {
    action_functions = pair(fun, action_functions);
}

实施日程表

最后，我们详细介绍了日程表数据结构，该结构保存了计划用于将来执行的函数。

日程表由时间段组成。每个时间段都是一个数字（时间）和一个队列（参见练习 3.32），该队列保存了计划在该时间段内运行的函数。

function make_time_segment(time, queue) {
    return pair(time, queue);
}
function segment_time(s) { return head(s); }
function segment_queue(s) { return tail(s); }

我们将使用 3.3.2 节中描述的队列操作来操作时间段队列。

日程表本身是一个时间段的一维表。它与 3.3.3 节中描述的表不同之处在于，时间段将按照时间递增的顺序进行排序。此外，我们在日程表的头部存储当前时间（即，上次处理的动作的时间）。新构建的日程表没有时间段，并且当前时间为 0：

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));
    }
}

练习 3.32

待在议程的每个时间段内运行的函数被保存在一个队列中。因此，每个时间段的函数按照它们被添加到议程的顺序被调用（先进先出）。解释为什么必须使用这个顺序。特别是，追踪一个与门的行为，当它的输入在同一个时间段内从0,1变为1,0，并说出如果我们将一个时间段的函数存储在一个普通列表中，只在前面添加和删除函数时，行为会有何不同。

3.3.5 约束的传播

计算机程序通常以单向计算的方式组织，它们对预先指定的参数执行操作以产生期望的输出。另一方面，我们经常以量之间的关系来建模系统。例如，机械结构的数学模型可能包括这样的信息：金属杆的挠度d与杆上的力F、杆的长度L、横截面积A和弹性模量E之间通过方程

dAE = FL

这样的方程不是单向的。给定这些量中的任意四个，我们可以使用它来计算第五个。然而，将方程转化为传统的计算机语言会迫使我们选择其中一个量来根据其他四个计算。因此，一个用于计算面积A的函数不能用于计算挠度d，即使A和d的计算都来自同一个方程。³⁴

在本节中，我们概述了一种能够让我们直接使用关系本身的语言的设计。语言的原始元素是 原始约束，它们陈述了某些量之间的关系。例如，adder(a, b, c)指定了量a、b和c必须满足方程a + b = c，multiplier(x, y, z)表达了约束xy = z，constant(3.14, x)表示x的值必须是 3.14。

我们的语言提供了一种将原始约束组合以表达更复杂关系的方法。我们通过构建 约束网络 来组合约束，其中约束由 连接器 连接。连接器是一个“持有”一个值的对象，可以参与一个或多个约束。例如，我们知道华氏温度和摄氏温度之间的关系是

9C = 5(F – 32)

这样的约束可以被看作是一个由原始加法器、乘法器和常量约束构成的网络（图 3.28）。在图中，我们可以看到左边有一个带有三个端口的乘法器盒子，标有m[1]、m[2]和p。这些将乘法器与网络的其余部分连接起来：m[1]端口连接到一个连接器C，它将持有摄氏温度。m[2]端口连接到一个连接器w，它也连接到一个持有 9 的常量盒子。乘法器盒子约束的p端口连接到另一个乘法器盒子的p端口，后者的m[2]连接到一个常量 5，m[1]连接到一个求和中的一个项。

图 3.28 表达为约束网络的关系9C = 5(F – 32)。

这样的网络进行计算的过程如下：当连接器被赋予一个值（由用户或与其链接的约束框），它会唤醒其所有相关约束（除了刚刚唤醒它的约束），通知它们它有一个值。然后每个唤醒的约束框轮询其连接器，看是否有足够的信息来确定连接器的值。如果是，该框将设置该连接器，然后唤醒其所有相关约束，依此类推。例如，在摄氏度和华氏度之间的转换中，w、x和y立即由常量框设置为 9、5 和 32。连接器唤醒乘法器和加法器，确定没有足够的信息来继续。如果用户（或网络的其他部分）将C设置为一个值（比如 25），最左边的乘法器将被唤醒，它将把u设置为25*9=225。然后u唤醒第二个乘法器，将v设置为 45，v唤醒加法器，将F设置为 77。

使用约束系统

要使用约束系统执行上面概述的温度计算，我们首先调用构造函数make_connector来创建两个连接器C和F，然后将它们链接到一个适当的网络中：

const C = make_connector();
const F = make_connector();
celsius_fahrenheit_converter(C, F);
"ok"

定义创建网络的函数如下：

function celsius_fahrenheit_converter(c, f) {
    const u = make_connector();
    const v = make_connector();
    const w = make_connector();
    const x = make_connector();
    const y = make_connector();
    multiplier(c, w, u);
    multiplier(v, x, u);
    adder(v, y, f);
    constant(9, w);
    constant(5, x);
    constant(32, y);
    return "ok";
}

这个函数创建内部连接器u、v、w、x和y，并使用原始约束构造函数adder、multiplier和constant将它们链接如图 3.28 所示。就像 3.3.4 节中的数字电路模拟器一样，用函数表达这些原始元素的组合自动为我们的语言提供了复合对象的抽象手段。

观察网络的运行，我们可以在连接器C和F上放置探针，使用类似于我们在 3.3.4 节中用来监视电线的probe函数。在连接器上放置探针将导致在给连接器赋值时打印消息：

probe("Celsius temp", C);
probe("Fahrenheit temp", F);

接下来我们将C的值设置为 25。（set_value的第三个参数告诉C这个指令来自user。）

set_value(C, 25, "user");
"Probe: Celsius temp = 25"
"Probe: Fahrenheit temp = 77"
"done"

C上的探针醒来并报告值。C也通过网络传播其值，如上所述。这将F设置为 77，探针上报告了这一点。

现在我们可以尝试将F设置为一个新值，比如 212：

set_value(F, 212, "user");
"Error! Contradiction: (77, 212)"

连接器抱怨它已经感知到矛盾：它的值是 77，有人试图将其设置为 212。如果我们真的想要使用新的值重新使用网络，我们可以告诉C忘记它的旧值：

forget_value(C, "user");
"Probe: Celsius temp = ?"
"Probe: Fahrenheit temp = ?"
"done"

C发现"user"，最初设置其值的人，现在正在撤回该值，因此C同意失去其值，如探针所示，并通知网络的其余部分。这些信息最终传播到F，现在F发现没有理由继续相信自己的值是 77。因此，F也放弃了它的值，如探针所示。

现在F没有值，我们可以自由地将其设置为 212：

set_value(F, 212, "user");
"Probe: Fahrenheit temp = 212"
"Probe: Celsius temp = 100"
"done"?

这个新值在网络中传播，强制C的值为 100，并由C上的探针注册。请注意，同一个网络被用来计算C给定F和计算F给定C。这种计算的非定向性是约束系统的显著特征。

实现约束系统

约束系统是通过具有局部状态的过程对象实现的，与 3.3.4 节中的数字电路模拟器非常相似。尽管约束系统的原始对象有些复杂，但整个系统更简单，因为不必担心议程和逻辑延迟。

连接器的基本操作如下：

has_value(connector)
告诉连接器是否有值。
get_value(connector)
返回连接器的当前值。
set_value(connector, new-value, informant)
表示通知者正在请求连接器将其值设置为新值。
forget_value(connector, retractor)
告诉连接器，撤回者正在请求它忘记其值。
connect(connector, new-constraint)
告诉连接器参与新的约束。

连接器通过函数inform_ about_value与约束进行通信，该函数告诉给定约束连接器具有值，并且inform_about_no_value告诉约束连接器已经失去了它的值。

Adder在加数连接器a1和a2以及一个sum连接器之间构造一个加法器约束。加法器实现为具有本地状态的函数（下面的函数me）：

function adder(a1, a2, sum) {
    function process_new_value() {
        if (has_value(a1) && has_value(a2)) {
            set_value(sum, get_value(a1) + get_value(a2), me);
        } else if (has_value(a1) && has_value(sum)) {
            set_value(a2, get_value(sum) - get_value(a1), me);
        } else if (has_value(a2) && has_value(sum)) {
            set_value(a1, get_value(sum) - get_value(a2), me);
        } else {}
    }
    function process_forget_value() {
        forget_value(sum, me);
        forget_value(a1, me);
        forget_value(a2, me);
        process_new_value();
    }
    function me(request) {
        if (request === "I have a value.") {
            process_new_value();
        } else if (request === "I lost my value.") {
            process_forget_value();
        } else {
            error(request, "unknown request – adder");
        }
    }
    connect(a1, me);
    connect(a2, me);
    connect(sum, me);
    return me;
}

函数adder将新的加法器连接到指定的连接器并将其作为其值返回。代表加法器的函数me充当本地函数的分派。与分派一起使用以下“语法接口”（参见第 3.3.4 节中的脚注 30）：

function inform_about_value(constraint) {
    return constraint("I have a value.");
}
function inform_about_no_value(constraint) {
    return constraint("I lost my value.");
}

当加法器被告知其连接器之一具有值时，将调用加法器的本地函数process_new_value。加法器首先检查看看a1和a2是否都有值。如果是这样，它会告诉sum将其值设置为两个加数的和。set_value的informant参数是me，即加法器对象本身。如果a1和a2都没有值，那么加法器会检查看看也许a1和sum有值。如果是这样，它会将a2设置为这两者的差。最后，如果a2和sum有值，这就为加法器提供了足够的信息来设置a1。如果加法器被告知其连接器之一失去了值，它会要求所有连接器现在都失去它们的值。（实际上只有这些值是由此加法器设置的才会丢失。）然后运行process_new_value。这最后一步的原因是一个或多个连接器可能仍然具有值（即，连接器可能具有一个不是最初由加法器设置的值），并且这些值可能需要通过加法器传播回去。

乘法器与加法器非常相似。如果因子中的任何一个为 0，即使另一个因子未知，它也会将其product设置为 0。

function multiplier(m1, m2, product) {
    function process_new_value() {
        if ((has_value(m1) && get_value(m1) === 0)
         || (has_value(m2) && get_value(m2) === 0)) {
            set_value(product, 0, me);
        } else if (has_value(m1) && has_value(m2)) {
            set_value(product, get_value(m1) * get_value(m2), me);
        } else if (has_value(product) && has_value(m1)) {
            set_value(m2, get_value(product) / get_value(m1), me);
        } else if (has_value(product) && has_value(m2)) {
            set_value(m1, get_value(product) / get_value(m2), me);
        } else {}
    }
    function process_forget_value() {
        forget_value(product, me);
        forget_value(m1, me);
        forget_value(m2, me);
        process_new_value();
    }
    function me(request) {
        if (request === "I have a value.") {
            process_new_value();
        } else if (request === "I lost my value.") {
            process_forget_value();
        } else {
            error(request, "unknown request – multiplier");
        }
    }
    connect(m1, me);
    connect(m2, me);
    connect(product, me);
    return me;
}

“常量”构造函数只是设置指定连接器的值。发送到常量框的任何“我有一个值。”或“我失去了我的价值。”消息都会产生错误。

function constant(value, connector) {
    function me(request) {
        error(request, "unknown request – constant");
    }
    connect(connector, me);
    set_value(connector, value, me);
    return me;
}

最后，探针打印有关设置或取消指定连接器的消息：

function probe(name, connector) {
    function print_probe(value) {
        display("Probe: " + name + " = " + stringify(value));
    }
    function process_new_value() {
        print_probe(get_value(connector));
    }
    function process_forget_value() {
        print_probe("?");
    }
    function me(request) {
        return request === "I have a value."
               ? process_new_value()
               : request === "I lost my value."
               ? process_forget_value()
               : error(request, "unknown request – probe");
    }
    connect(connector, me);
    return me;
}

表示连接器

连接器表示为具有本地状态变量value的过程对象，即连接器的当前值；informant，设置连接器值的对象；和constraints，连接器参与的约束列表。

function make_connector() {
    let value = false;
    let informant = false;
    let constraints = null;
    function set_my_value(newval, setter) {
        if (!has_value(me)) {
            value = newval;
            informant = setter;
            return for_each_except(setter,
                                   inform_about_value,
                                   constraints);
        } else if (value !== newval) {
            error(list(value, newval), "contradiction");
        } else {
            return "ignored";
        }
    }
    function forget_my_value(retractor) {
        if (retractor === informant) {
            informant = false;
            return for_each_except(retractor,
                                   inform_about_no_value,
                                   constraints);
        } else {
            return "ignored";
        }
    }
    function connect(new_constraint) {
        if (is_null(member(new_constraint, constraints))) {
            constraints = pair(new_constraint, constraints);
        } else {}
        if (has_value(me)) {
            inform_about_value(new_constraint);
        } else {}
        return "done";
    }
    function me(request) {
        if (request === "has_value") {
            return informant !== false;
        } else if (request === "value") {
            return value;
        } else if (request === "set_value") {
            return set_my_value;
        } else if (request === "forget") {
            return forget_my_value;
        } else if (request === "connect") {
            return connect;
        } else {
            error(request, "unknown operation – connector");
        }
    }
    return me;
}

当有请求设置连接器的值时，将调用连接器的本地函数set_my_value。如果连接器当前没有值，它将设置其值并记住请求设置值的约束作为informant。然后，连接器将通知除了请求设置值的约束之外的所有参与约束。这是通过以下迭代器实现的，该迭代器将指定的函数应用于列表中除给定项之外的所有项：

function for_each_except(exception, fun, list) {
    function loop(items) {
        if (is_null(items)) {
            return "done";
        } else if (head(items) === exception) {
            return loop(tail(items));
        } else {
            fun(head(items));
            return loop(tail(items));
        }
    }
    return loop(list);
}

如果要求连接器忘记其值，则运行forget_my_value，这是一个本地函数，首先检查请求是否来自最初设置值的相同对象。如果是这样，连接器会通知其关联的约束丢失了值。

本地函数connect将指定的新约束添加到约束列表中，如果它尚未在该列表中。然后，如果连接器具有值，它会告知新约束这一事实。

连接器的函数me用作对其他内部函数的调度，并且也代表连接器作为一个对象。以下函数为调度提供了语法接口：

function has_value(connector) {
    return connector("has_value");
}
function get_value(connector) {
    return connector("value");
}
function set_value(connector, new_value, informant) {
    return connector("set_value")(new_value, informant);
}
function forget_value(connector, retractor) {
    return connector("forget")(retractor);
}
function connect(connector, new_constraint) {
   return connector("connect")(new_constraint);
}

练习 3.33

使用原始乘法器、加法器和常量约束，定义一个名为averager的函数，该函数以三个连接器a，b和c作为输入，并建立约束，使得c的值是a和b的平均值。

练习 3.34

Louis Reasoner 想要构建一个平方器，这是一个具有两个端子的约束设备，使得第二个端子上的连接器 b 的值始终是第一个端子上连接器 a 的值的平方。他提出了以下由乘法器制成的简单设备：

function squarer(a, b) {
    return multiplier(a, a, b);
}

这个想法存在一个严重的缺陷。请解释。

练习 3.35

Ben Bitdiddle 告诉 Louis，避免练习 3.34 中的麻烦的一种方法是将平方器定义为一个新的原始约束。填写 Ben 的轮廓中用于实现这种约束的函数的缺失部分：

function squarer(a, b) {
    function process_new_value() {
        if (has_value(b)) {
            if (get_value(b) < 0) {
                error(get_value(b), "square less than 0 – squarer");
            } else {
                alternative[1]
            }
        } else {
            alternative[2]
        }
    }
    function process_forget_value() {
        body[1]
    }
    function me(request) {
        body[2]
    }
    statements
    return me;
}

练习 3.36

假设我们在程序环境中求值以下语句序列：

const a = make_connector();
const b = make_connector();
set_value(a, 10, "user");

在set_value的求值过程中的某个时间，将求值连接器的本地函数中的以下表达式：

for_each_except(setter, inform_about_value, constraints);

绘制一个环境图，显示上述表达式的求值环境。

练习 3.37

与更注重表达式的定义风格相比，celsius_fahrenheit_converter函数显得很繁琐，例如

function celsius_fahrenheit_converter(x) {
   return cplus(cmul(cdiv(cv(9), cv(5)), x), cv(32));
}
const C = make_connector();
const F = celsius_fahrenheit_converter(C);

在这里，cplus，cmul等是算术操作的“约束”版本。例如，cplus接受两个连接器作为参数，并返回一个与这些连接器相关的连接器，通过加法器约束：

function cplus(x, y) {
    const z = make_connector();
    adder(x, y, z);
    return z;
}

定义类似的函数cminus，cmul，cdiv和cv（常量值），使我们能够像上面的转换器示例一样定义复合约束。³⁷

3.4 并发性：时间至关重要

我们已经看到了具有局部状态的计算对象作为建模工具的强大力量。然而，正如 3.1.3 节所警告的那样，这种力量是有代价的：失去了引用透明性，引发了关于相同性和变化的一系列问题，并且需要放弃替换模型的求值，转而采用更复杂的环境模型。

隐藏在状态、相同性和变化的复杂性下的核心问题是，通过引入赋值，我们被迫将时间引入我们的计算模型中。在引入赋值之前，我们所有的程序都是无时间的，即任何具有值的表达式始终具有相同的值。相比之下，回想一下在 3.1.1 节开头介绍的从银行账户中提取和返回结果余额的建模示例：

withdraw(25);
75
withdraw(25);
50

这里对同一表达式的连续求值产生了不同的值。这种行为是由于赋值语句（在本例中是对变量balance的赋值）的执行划定了值发生变化的时间点。求值表达式的结果不仅取决于表达式本身，还取决于求值是在这些时间点之前还是之后发生的。以计算对象的局部状态构建模型迫使我们面对时间作为编程中的一个基本概念。

我们可以进一步构建计算模型，使其与我们对物理世界的感知相匹配。世界中的对象不是按顺序一个接一个地变化。相反，我们将它们视为同时并发执行。因此，通常自然地将系统建模为同时执行的线程（计算步骤序列）的集合。正如我们可以通过以对象的方式组织模型来使程序更加模块化，将计算模型分成部分以便分别和同时演变也是合适的。即使程序将在顺序计算机上执行，将程序编写成并发执行的方式也会迫使程序员避免不必要的时间约束，从而使程序更加模块化。

除了使程序更加模块化外，并发计算还可以比顺序计算提供速度优势。顺序计算机一次只执行一个操作，因此执行任务所需的时间与执行的总操作数成正比。然而，如果可以将问题分解为相对独立并且只需要偶尔通信的部分，那么可能可以将这些部分分配给单独的计算处理器，从而产生与可用处理器数量成正比的速度优势。

不幸的是，赋值引入的复杂性在并发存在时变得更加棘手。并发执行的事实，无论是因为世界是并行运行的，还是因为我们的计算机是，并发执行都会增加我们对时间理解的复杂性。

3.4.1 并发系统中时间的本质

表面上，时间似乎很简单。它是对事件施加的一种排序。对于任何事件A和B，要么A发生在B之前，A和B同时发生，或者A发生在B之后。例如，回到银行账户的例子，假设彼得从一个初始含有 100 美元的联合账户中提取了 10 美元，而保罗从中提取了 25 美元，留下 65 美元在账户中。根据两次提取的顺序，账户中的余额序列要么是 100 90 65，要么是 100 75 65。在银行系统的计算机实现中，这种不断变化的余额序列可以通过对变量balance进行连续赋值来建模。

然而，在复杂情况下，这样的观点可能会有问题。假设彼得和保罗，以及其他人，通过遍布全球的银行机器网络访问同一个银行账户。账户中的实际余额序列将严重依赖于访问的详细时间和机器之间通信的细节。

事件顺序的不确定性可能会在并发系统的设计中带来严重问题。例如，假设彼得和保罗的提取是作为两个共享一个公共变量balance的独立线程实现的，每个线程由第 3.1.1 节中给出的函数指定：

function withdraw(amount) {
    if (balance >= amount) {
        balance = balance - amount;
        return balance;
    } else {
        return "Insufficient funds";
    }
}

如果两个线程独立操作，那么彼得可能会测试余额并尝试提取合法金额。然而，保罗可能会在彼得检查余额和彼得完成提取之间提取一些资金，从而使彼得的测试无效。

事情可能会变得更糟。考虑这个声明

balance = balance - amount;

作为每个提取过程的一部分执行。这包括三个步骤：(1) 访问balance变量的值；(2) 计算新的余额；(3) 将balance设置为这个新值。如果彼得和保罗的提取同时执行这个语句，那么两个提取可能会交错访问balance和将其设置为新值的顺序。

图 3.29 中的时序图描述了一系列事件的顺序，其中balance从 100 开始，Peter 取款 10，Paul 取款 25，最终balance的值却是 75。正如图中所示，这种异常的原因是 Paul 将 75 赋给balance的假设是要减少的balance的值为 100。然而，当 Peter 将balance改为 90 时，这个假设变得无效。这对银行系统来说是一个灾难性的失败，因为系统中的总金额没有得到守恒。交易之前，系统中的总金额是 100 美元。之后，Peter 有 10 美元，Paul 有 25 美元，银行有 75 美元。^41

图 3.29 时序图显示了两笔银行取款事件的交错顺序可能导致最终余额不正确。

这里展示的一般现象是，多个线程可以共享一个公共状态变量。使这变得复杂的是，可能有多个线程同时尝试操作共享状态。对于银行账户的例子，在每笔交易中，每个客户都应该能够假设其他客户不存在。当客户以依赖于余额的方式改变余额时，他们必须能够假设在改变的那一刻之前，余额仍然是他们认为的那样。

并发程序的正确行为

上面的例子典型地说明了可能潜入并发程序的微妙错误。这种复杂性的根源在于不同线程之间共享的变量的赋值。我们已经知道，在编写使用赋值的程序时必须小心，因为计算的结果取决于赋值发生的顺序。^42 在并发线程中，我们必须特别小心赋值，因为我们可能无法控制不同线程所做的赋值的顺序。如果可能同时进行几个这样的更改（例如两个存款人访问联合账户），我们需要某种方式来确保我们的系统行为正确。例如，在联合银行账户的取款情况下，我们必须确保金钱是守恒的。为了使并发程序行为正确，我们可能需要对并发执行施加一些限制。

对并发的一种可能限制是规定不能同时发生改变任何共享状态变量的两个操作。这是一个非常严格的要求。对于分布式银行业务，这将要求系统设计者确保只能一次进行一笔交易。这既低效又过于保守。图 3.30 展示了 Peter 和 Paul 共享一个银行账户，Paul 也有一个私人账户。该图说明了从共享账户中取款（Peter 和 Paul 各取一笔）以及向 Paul 的私人账户存款。^43 从共享账户中取款的两笔操作不能同时进行（因为两者都访问并更新同一个账户），Paul 的存款和取款也不能同时进行（因为两者都访问并更新 Paul 钱包中的金额）。但是允许 Paul 向他的私人账户存款与 Peter 从共享账户中取款同时进行应该没有问题。

图 3.30 在 Bank1 的联合账户和 Bank2 的私人账户中同时存款和取款。

对并发的限制较少会确保并发系统产生与线程按某种顺序顺序运行时相同的结果。这一要求有两个重要方面。首先，它不要求线程实际上按顺序运行，而只要求产生与它们按顺序运行时相同的结果。例如，在图 3.30 的例子中，银行账户系统的设计者可以安全地允许保罗的存款和彼得的取款同时发生，因为最终结果将与这两个操作按顺序发生时的结果相同。其次，一个并发程序可能产生多个可能的“正确”结果，因为我们只要求结果与某些顺序的结果相同。例如，假设彼得和保罗的联合账户一开始有 100 美元，彼得存入 40 美元，同时保罗取出账户中的一半。然后，顺序执行可能导致账户余额为 70 美元或 90 美元（见练习 3.38）⁴⁴。

对并发程序的正确执行还有更弱的要求。用于模拟扩散（比如物体中的热量流动）的程序可能由大量线程组成，每个线程代表一小块空间，它们同时更新自己的值。每个线程反复将自己的值更改为自己的值和邻居的值的平均值。这种算法收敛到正确的答案，不受操作顺序的影响；对共享值的并发使用没有任何限制的必要。

练习 3.38

假设彼得、保罗和玛丽共享一个最初包含 100 美元的联合银行账户。同时，彼得存入 10 美元，保罗取出 20 美元，玛丽取出账户中的一半，执行以下命令：

彼得：	`balance = balance + 10`
保罗：	`balance = balance - 20`
玛丽：	`balance = balance - (balance / 2)`

a. 假设银行系统强制这三个线程按某种顺序顺序运行，请列出这三个交易完成后balance的所有不同可能值。
b. 如果系统允许线程交错，还可能产生哪些其他值？画出类似图 3.29 中的时间图，解释这些值是如何产生的。

3.4.2 控制并发的机制

我们已经看到处理并发线程的困难根源在于需要考虑不同线程中事件顺序的交错。例如，假设我们有两个线程，一个有三个有序事件（a，b，c），另一个有三个有序事件（x，y，z）。如果两个线程同时运行，而不限制它们的执行交错方式，那么与两个线程的各自顺序一致的 20 种不同可能的事件顺序：

（`a`，`b`，`c`，`x`，`y`，`z`）	（`a`，`x`，`b`，`y`，`c`，`z`）	（`x`，`a`，`b`，`c`，`y`，`z`）	（`x`，`a`，`y`，`z`，`b`，`c`）
（`a`，`b`，`x`，`c`，`y`，`z`）	（`a`，`x`，`b`，`y`，`z`，`c`）	（`x`，`a`，`b`，`y`，`c`，`z`）	（`x`，`y`，`a`，`b`，`c`，`z`）
（`a`，`b`，`x`，`y`，`c`，`z`）	（`a`，`x`，`y`，`b`，`c`，`z`）	（`x`，`a`，`b`，`y`，`z`，`c`）	（`x`，`y`，`a`，`b`，`z`，`c`）
（`a`，`b`，`x`，`y`，`z`，`c`）	（`a`，`x`，`y`，`b`，`z`，`c`）	（`x`，`a`，`y`，`b`，`c`，`z`）	（`x`，`y`，`a`，`z`，`b`，`c`）
（`a`，`x`，`b`，`c`，`y`，`z`）	（`a`，`x`，`y`，`z`，`b`，`c`）	（`x`，`a`，`y`，`b`，`z`，`c`）	（`x`，`y`，`z`，`a`，`b`，`c`）

作为设计这个系统的程序员，我们必须考虑这 20 种顺序的影响，并检查每种行为是否可接受。随着线程和事件数量的增加，这种方法很快变得难以控制。

设计并发系统的更实际的方法是设计通用机制，允许我们限制并发线程的交错，以确保程序行为是正确的。为此目的已经开发了许多机制。在本节中，我们描述其中之一，即序列化程序。

对共享状态进行序列化访问

序列化实现了以下思想：线程将同时执行，但将有一定的函数集合不能同时执行。更确切地说，序列化创建了一组特殊的函数集，以便每次只允许在每个序列化集中执行一个函数。如果正在执行集合中的某个函数，则试图执行集合中任何函数的线程将被迫等待，直到第一次执行完成。

我们可以使用序列化来控制对共享变量的访问。例如，如果我们想要基于该变量的先前值更新共享变量，我们将变量的先前值的访问和对变量的新值的赋值放在同一个函数中。然后，我们通过使用相同的序列化程序对所有这些函数进行序列化，以确保没有其他分配给变量的函数可以与此函数同时运行。这保证了变量的值在访问和相应的赋值之间不能被更改。

序列化程序

为了使上述机制更具体，假设我们已经扩展了 JavaScript，包括一个名为concurrent_execute的函数：

concurrent_execute(f[1], f[2], ..., f[k])

每个f必须是一个没有参数的函数。函数concurrent_execute为每个f创建一个单独的线程，该线程将f（无参数）应用于f。这些线程都同时运行。[^45]

作为如何使用它的示例，考虑

let x = 10;
concurrent_execute(() => { x = x * x; },
                   () => { x = x + 1; });

这创建了两个并发线程——T[1]，将x设置为x乘以x，以及T[2]，增加x。执行完成后，x将保留五种可能的值之一，具体取决于T[1]和T[2]的事件交错：

101:	`T[1]`将`x`设置为 100，然后`T[2]`将`x`增加到 101。
121:	`T[2]`将`x`增加到 11，然后`T[1]`将`x`设置为`x`乘以`x`。
110:	`T[2]`在`T[1]`之间将`x`从 10 更改为 11
	在求值`x * x`期间访问`x`的值。
11:	`T[2]`访问`x`，然后`T[1]`将`x`设置为 100，然后`T[2]`设置`x`。
100:	`T[1]`访问`x`（两次），然后`T[2]`将`x`设置为 11，然后`T[1]`设置`x`。

我们可以通过使用序列化函数来限制并发，这些函数是由序列化程序创建的。序列化程序是由make_serializer构造的，其实现如下所示。序列化程序接受一个函数作为参数，并返回一个行为类似于原始函数的序列化函数。对给定序列化程序的所有调用都返回相同集合中的序列化函数。

因此，与上面的示例相比，执行

let x = 10;
const s = make_serializer();
concurrent_execute(s(() => { x = x * x; }),
                   s(() => { x = x + 1; }));

可以产生x的两个可能值，101 或 121。其他可能性被消除，因为T[1]和T[2]的执行不能交错。

这是从 3.1.1 节中的make_account函数的一个版本，其中存款和取款已经被序列化：

function make_account(balance) {
    function withdraw(amount) {
        if (balance > amount) {
            balance = balance - amount;
            return balance;
        } else {
            return "Insufficient funds";
        }
    }
    function deposit(amount) {
        balance = balance + amount;
        return balance;
    }
    const protect = make_serializer();
    function dispatch(m) {
        return m === "withdraw"
               ? protect(withdraw)
               : m === "deposit"
               ? protect(deposit)
               : m === "balance"
               ? balance
               : error(m, "unknown request – make_account");
    }
    return dispatch;
}

通过这种实现，两个线程不能同时从单个帐户中提取或存款。这消除了图 3.29 中所示错误的来源，即 Peter 在 Paul 访问余额以计算新值和 Paul 实际执行分配之间更改帐户余额的时间。另一方面，每个帐户都有自己的序列化程序，因此不同帐户的存款和取款可以同时进行。

练习 3.39

如果我们改为按照以下方式对执行进行序列化，上述并发执行中的五种可能性中哪些仍然存在：

let x = 10;
const s = make_serializer();
concurrent_execute( () => { x = s(() => x * x)(); },
                   s(() => { x = x + 1; }));

练习 3.40

给出执行后可能的所有x的值

let x = 10;
concurrent_execute(() => { x = x * x; },
                   () => { x = x * x * x; });

如果我们使用序列化函数，那么这些可能性中还剩下哪些呢：

let x = 10;
const s = make_serializer(); concurrent_execute(s(() => { x = x * x; }),
                   s(() => { x = x * x * x; }));

练习 3.41

Ben Bitdiddle 担心最好按照以下方式实现银行账户（已更改的部分已在注释行中）：

function make_account(balance) {
    function withdraw(amount) {
        if (balance > amount) {
            balance = balance - amount;
            return balance;
        } else {
            return "Insufficient funds";
        }
    }
    function deposit(amount) {
        balance = balance + amount;
        return balance;
    }
    const protect = make_serializer();
    function dispatch(m) {
        return m === "withdraw"
               ? protect(withdraw)
               : m === "deposit"
               ? protect(deposit)
               : m === "balance"
               ? protect(() => balance)(undefined) // serialized
               : error(m, "unknown request – make_account");
    }
    return dispatch;
}

因为允许对银行余额进行未序列化访问可能会导致异常行为。你同意吗？有没有任何情景可以证明 Ben 的担忧？

练习 3.42

Ben Bitdiddle 建议，针对每个withdraw和deposit消息创建一个新的序列化函数是浪费时间。他说make_account可以被改变，这样对protect的调用就在dispatch函数之外完成。也就是说，一个账户每次要求提取函数时都会返回相同的序列化函数（该函数是在创建账户时同时创建的）。

function make_account(balance) {
    function withdraw(amount) {
        if (balance > amount) {
            balance = balance - amount;
            return balance;
        } else {
            return "Insufficient funds";
        }
    }
    function deposit(amount) {
        balance = balance + amount;
        return balance;
    }
    const protect = make_serializer();
    const protect_withdraw = protect(withdraw);
    const protect_deposit = protect(deposit);
    function dispatch(m) {
        return m === "withdraw"
               ? protect_withdraw
               : m === "deposit"
               ? protect_deposit
               : m === "balance"
               ? balance
               : error(m, "unknown request – make_account");
    }
    return dispatch;
}

这样改变安全吗？特别是，这两个版本的make_account允许的并发性有什么区别吗？

使用多个共享资源的复杂性

序列化器提供了一个强大的抽象，有助于隔离并发程序的复杂性，以便可以小心地（希望）正确地处理。然而，当只有一个共享资源（如单个银行账户）时，使用序列化器相对来说是相对简单的，但是当存在多个共享资源时，并发编程可能会非常困难。

为了说明可能出现的困难之一，假设我们希望交换两个银行账户的余额。我们访问每个账户以查找余额，计算余额之间的差额，从一个账户中提取这个差额，并将其存入另一个账户。我们可以这样实现：

function exchange(account1, account2) {
    const difference = account1("balance") - account2("balance");
    account1("withdraw")(difference);
    account2("deposit")(difference);
}

当只有一个线程尝试进行交换时，这个函数运行良好。然而，假设 Peter 和 Paul 都可以访问账户a[1]、a[2]和a[3]，Peter 交换a[1]和a[2]，同时 Paul 并发地交换a[1]和a[3]。即使对于单个账户的存款和取款都是串行化的（就像本节中上面显示的make_account函数一样），exchange仍然可能产生不正确的结果。例如，Peter 可能计算a[1]和a[2]的余额差，但是 Paul 可能在 Peter 完成交换之前改变a[1]的余额。为了正确的行为，我们必须安排exchange函数在整个交换过程中锁定对账户的任何其他并发访问。

NUS CS1101S：SICP JavaScript 描述：三、模块化、对象和状态（4）https://developer.aliyun.com/article/1427728

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

NUS CS1101S：SICP JavaScript 描述：三、模块化、对象和状态（3）