NUS CS1101S：SICP JavaScript 描述：三、模块化、对象和状态（1）https://developer.aliyun.com/article/1427723
现在我们将函数对象sum_of_squares应用于参数 6 和 10。这将导致一个新的环境 E2，其中参数x和y绑定到参数。在 E2 中，我们求值语句
return square(x) + square(y);
这导致我们求值square(x)，其中square在程序框架中找到，x为 6。再次，我们建立一个新的环境 E3，在其中x绑定到 6，并在其中求值square的主体，即return x * x;。同样作为应用sum_of_squares的一部分，我们必须求值子表达式square(y)，其中y为 10。对square的第二次调用创建了另一个环境 E4，在其中square的参数x绑定到 10。在 E4 中，我们必须求值return x * x;。
需要注意的重要一点是，每次调用square都会创建一个包含x绑定的新环境。我们可以在这里看到不同的帧是如何保持分开的不同的名为x的本地变量的。请注意，square创建的每个帧都指向程序环境，因为这是square函数对象指定的环境。
在子表达式被求值之后，结果被返回。square的两次调用生成的值被sum_of_squares相加，这个结果被f返回。由于我们这里的重点是环境结构，我们不会详细讨论这些返回值是如何从调用传递到调用的；然而，这也是求值过程的一个重要方面，我们将在第 5 章中详细讨论它。
练习 3.9
在 1.2.1 节中，我们使用替换模型来分析两个计算阶乘的函数，一个是递归版本
function factorial(n) { return n === 1 ? 1 : n * factorial(n - 1); }
和迭代版本
function factorial(n) { return fact_iter(1, 1, n); } function fact_iter(product, counter, max_count) { return counter > max_count ? product : fact_iter(counter * product, counter + 1, max_count); }
展示了使用factorial函数的每个版本来求值factorial(6)的环境结构。¹⁶
3.2.3 帧作为本地状态的存储库
我们可以转向环境模型，看看如何使用函数和赋值来表示具有本地状态的对象。例如，考虑通过调用函数创建的“取款处理器”（来自第 3.1.1 节）
function make_withdraw(balance) { return amount => { if (balance >= amount) { balance = balance - amount; return balance; } else { return "insufficient funds"; } }; }
让我们描述一下
const W1 = make_withdraw(100);
接着
W1(50); 50
图 3.6 显示了在程序环境中声明make_withdraw函数的结果。这产生了一个包含指向程序环境的指针的函数对象。到目前为止，这与我们已经看到的例子没有什么不同，只是函数主体中的返回表达式本身是一个 lambda 表达式。
图 3.6 在程序环境中定义make_withdraw的结果。
当我们将函数make_withdraw应用到一个参数时，计算的有趣部分发生了：
const W1 = make_withdraw(100);
我们通常是通过设置环境 E1 来开始的，在这个环境中，参数balance绑定到参数 100。在这个环境中，我们求值make_withdraw的主体，即返回语句，其返回表达式是一个 lambda 表达式。对这个 lambda 表达式的求值构造了一个新的函数对象，其代码由 lambda 表达式指定，其环境是 E1，lambda 表达式被求值以产生函数的环境。由对make_withdraw的调用返回的结果是这个函数对象。由于常量声明本身是在程序环境中被求值的，所以它在程序环境中绑定到W1。图 3.7 显示了生成的环境结构。
图 3.7 求值const W1 = make_withdraw(100);的结果。
现在我们可以分析当W1应用到一个参数时会发生什么：
W1(50); 50
我们首先构建一个帧，在这个帧中，W1的参数amount绑定到参数 50。需要注意的关键点是，这个帧的封闭环境不是程序环境，而是环境 E1，因为这是由W1函数对象指定的环境。在这个新环境中，我们求值函数的主体：
if (balance >= amount) { balance = balance - amount; return balance; } else { return "insufficient funds"; }
生成的环境结构如图 3.8 所示。正在求值的表达式引用了amount和balance。变量amount将在环境中的第一个帧中找到，而balance将通过跟随封闭环境指针到 E1 中找到。
图 3.8 应用函数对象W1创建的环境。
当执行赋值时，E1 中balance的绑定被更改。在调用W1完成时，balance为 50，并且仍然由函数对象W1指向包含balance的帧。绑定amount的帧（我们执行了更改balance的代码）不再相关，因为构造它的函数调用已经终止，并且没有来自环境其他部分的指针指向该帧。下次调用W1时，这将构建一个绑定amount的新帧，其封闭环境为 E1。我们看到 E1 充当了为函数对象W1保存局部状态变量的“位置”。图 3.9 显示了调用W1后的情况。
图 3.9 调用W1后的环境。
观察当我们通过再次调用make_withdraw创建第二个withdraw对象时会发生什么：
const W2 = make_withdraw(100);
这产生了图 3.10 中的环境结构，显示W2是一个函数对象，即一个带有一些代码和一个环境的对。W2的环境 E2 是通过调用make_withdraw创建的。它包含一个带有自己的局部绑定balance的帧。另一方面，W1和W2具有相同的代码：make_withdraw主体中 lambda 表达式指定的代码。¹⁷我们在这里看到了为什么W1和W2表现为独立对象。对W1的调用引用存储在 E1 中的状态变量balance，而对W2的调用引用 E2 中存储的balance。因此，对一个对象的局部状态的更改不会影响另一个对象。
图 3.10 使用const W2 = make_withdraw(100);创建第二个对象。
练习 3.10
在make_withdraw函数中，局部变量balance作为make_withdraw的参数创建。我们还可以使用我们可以称之为立即调用的 lambda 表达式单独创建局部状态变量，如下所示：
function make_withdraw(initial_amount) { return (balance => amount => { if (balance >= amount) { balance = balance - amount; return balance; } else { return "insufficient funds"; } })(initial_amount); }
外部 lambda 表达式在求值后立即被调用。它的唯一目的是创建一个名为balance的局部变量，并将其初始化为initial_amount。使用环境模型分析make_withdraw的这个替代版本，绘制类似上面的图形以说明交互。
const W1 = make_withdraw(100); W1(50); const W2 = make_withdraw(100);
展示make_withdraw的两个版本创建具有相同行为的对象。这两个版本的环境结构有何不同？
3.2.4 内部声明
在本节中，我们处理包含声明的函数体或其他块（例如条件语句的分支）。每个块为在块中声明的名称打开一个新的作用域。为了在给定环境中求值一个块，我们通过一个包含在块的主体中直接声明的所有名称的新帧来扩展该环境，然后在新构建的环境中求值主体。
1.1.8 节介绍了函数可以具有内部声明的概念，从而导致块结构，如下面的函数计算平方根：
function sqrt(x) { function is_good_enough(guess) { return abs(square(guess) - x) < 0.001; } function improve(guess) { return average(guess, x / guess); } function sqrt_iter(guess){ return is_good_enough(guess) ? guess : sqrt_iter(improve(guess)); } return sqrt_iter(1); }
现在我们可以使用环境模型来看为什么这些内部声明的行为符合预期。图 3.11 显示了在求值表达式sqrt(2)时，内部函数is_good_enough首次被调用，其中guess等于 1。
图 3.11 带有内部声明的sqrt函数。
观察环境的结构。名称sqrt在程序环境中绑定到一个函数对象，其关联的环境是程序环境。当调用sqrt时，形成了一个新的环境 E1，它是程序环境的下属，在其中参数x绑定到 2。然后在 E1 中求值了sqrt的主体。该主体是一个带有本地函数声明的块，因此 E1 被扩展为这些声明的新框架，导致新的环境 E2。然后在 E2 中求值了该块的主体。由于主体中的第一条语句是…
function is_good_enough(guess) { return abs(square(guess) - x) < 0.001; }
求值此声明在环境 E2 中创建了函数is_good_enough。更准确地说，E2 中的第一个框架中的名称is_good_enough绑定到一个函数对象，其关联的环境是 E2。类似地，improve和sqrt_iter在 E2 中被定义为函数。为简洁起见，图 3.11 仅显示了is_good_enough的函数对象。
在定义了本地函数之后，仍然在环境 E2 中求值了表达式sqrt_iter(1)。因此，在环境 E2 中绑定到sqrt_iter的函数对象被调用，并以 1 作为参数。这创建了一个环境 E3，在其中sqrt_iter的参数guess绑定到 1。然后sqrt_iter调用is_good_enough，并以guess的值（来自 E3）作为is_good_enough的参数。这建立了另一个环境 E4，在其中is_good_enough的参数guess绑定到 1。尽管sqrt_iter和is_good_enough都有一个名为guess的参数，但这些是位于不同框架中的两个不同的本地变量。此外，E3 和 E4 都将 E2 作为其封闭环境，因为sqrt_iter和is_good_enough函数都将 E2 作为其环境部分。这的一个结果是is_good_enough主体中出现的名称x将引用 E1 中出现的x的绑定，即调用原始sqrt函数时的x的值。
因此，环境模型解释了使本地函数声明成为模块化程序的两个关键属性。
- 本地函数的名称不会干扰封闭函数之外的名称，因为当块在求值时，本地函数名称将绑定在创建时的框架中，而不是绑定在程序环境中。
- 本地函数可以通过使用参数名称作为自由名称来访问封闭函数的参数。这是因为本地函数的主体在比封闭函数的求值环境低的环境中进行求值。
练习 3.11
在 3.2.3 节中，我们看到环境模型如何描述具有本地状态的函数的行为。现在我们已经看到了内部声明的工作原理。典型的消息传递函数包含了这两个方面。考虑 3.1.1 节中的银行账户函数：
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; } function dispatch(m) { return m === "withdraw" ? withdraw : m === "deposit" ? deposit : "Unknown request: make_account"; } return dispatch; }
展示由交互序列生成的环境结构
const acc = make_account(50); acc("deposit")(40); 90 acc("withdraw")(60); 30
acc的本地状态在哪里保存？假设我们定义另一个帐户。
const acc2 = make_account(100);
如何保持两个帐户的本地状态不同？acc和acc2之间共享环境结构的哪些部分？
更多关于块的内容
正如我们所看到的，sqrt中声明的名称的作用域是sqrt的整个主体。这解释了为什么相互递归可以工作，就像这种（相当浪费的）检查非负整数是否为偶数的方式一样。
function f(x) { function is_even(n) { return n === 0 ? true : is_odd(n - 1); } function is_odd(n) { return n === 0 ? false : is_even(n - 1); } return is_even(x); }
当在调用f期间调用is_even时，环境图看起来像调用sqrt_iter时的图 3.11 中的图。函数is_even和is_odd在 E2 中绑定到指向 E2 的环境中调用这些函数的函数对象。因此，is_even中的is_odd指的是正确的函数。尽管is_odd在is_even之后定义，但这与sqrt_iter的主体中improve和sqrt_iter本身指向正确的函数没有区别。
有了处理块内声明的方法，我们可以重新审视顶层的名称声明。在 3.2.1 节中，我们看到在顶层声明的名称被添加到程序框架中。更好的解释是整个程序被放置在一个隐式块中，在全局环境中进行求值。上面描述的块的处理然后处理顶层：全局环境通过包含隐式块中声明的所有名称的绑定的框架进行扩展。该框架是程序框架，结果环境是程序环境。
我们说一个块的主体在一个包含在块主体中直接声明的所有名称的环境中进行求值。当进入块时，局部声明的名称被放入环境中，但没有关联的值。在求值块主体时，其声明的求值将名称分配给右边的表达式的结果，就好像声明是一个赋值一样。由于名称添加到环境中是与声明的求值分开的，整个块都在名称的范围内，一个错误的程序可能会在其声明被求值之前尝试访问名称的值；未分配名称的求值会发出错误信号。¹⁸
3.3 用可变数据建模
第 2 章讨论了复合数据作为构建计算对象的手段，这些对象有几个部分，以模拟具有多个方面的现实世界对象。在该章中，我们介绍了数据抽象的学科，根据这一学科，数据结构是根据构造函数来指定的，构造函数创建数据对象，选择器访问复合数据对象的部分。但是现在我们知道第 2 章没有涉及的数据的另一个方面。希望模拟由具有不断变化状态的对象组成的系统，这导致我们需要修改复合数据对象，以及构造和从中选择。为了模拟具有不断变化状态的复合对象，我们将设计数据抽象，以包括除选择器和构造函数之外的操作，称为变异器，这些操作修改数据对象。例如，模拟银行系统需要我们改变账户余额。因此，用于表示银行账户的数据结构可能允许一个操作
set_balance(account, new-value)
更改指定帐户的余额为指定的新值的操作。定义了突变器的数据对象称为可变数据对象。
第 2 章介绍了对偶对作为合成复合数据的通用“粘合剂”。我们从定义对偶对的基本突变器开始这一部分，以便对偶对可以作为构造可变数据对象的构建块。这些突变器极大地增强了对偶对的表示能力，使我们能够构建除了我们在第 2.2 节中使用的序列和树之外的数据结构。我们还提供了一些模拟的示例，其中复杂系统被建模为具有局部状态的对象集合。
3.3.1 可变列表结构
对对的基本操作——pair、head和tail——可以用来构造列表结构和从列表结构中选择部分，但它们无法修改列表结构。到目前为止，我们使用的列表操作也是如此，比如append和list，因为这些可以用pair、head和tail来定义。要修改列表结构，我们需要新的操作。
对于对来说，原始的修改器是set_head和set_tail。函数set_head接受两个参数，第一个参数必须是对。它修改这个对，用set_head的第二个参数的指针替换head指针。¹⁹
例如，假设x绑定到list(list("a", "b"), "c", "d")，y绑定到list("e", "f")，如图 3.12 所示。求值表达式set_head(x, y)修改了x绑定的对，用y的值替换了它的head。操作的结果如图 3.13 所示。结构x已被修改，现在等价于list(list("e", "f"), "c", "d")。代表列表list("a", "b")的对，由被替换的指针标识，现在已从原始结构中分离。²⁰
图 3.12 列表x：list(list("a", "b"), "c", "d")和y：list("e", "f")。
图 3.13 set_head(x, y)对图 3.12 中的列表的影响。
将图 3.13 与图 3.14 进行比较，它说明了执行的结果
const z = pair(y, tail(x));
x和y绑定到图 3.12 中的原始列表。现在，名称z绑定到由pair操作创建的新对；x绑定的列表保持不变。set_tail操作类似于set_head。唯一的区别是用tail指针替换对的head指针。在图 3.12 中执行set_tail(x, y)的效果如图 3.15 所示。这里，x的tail指针已被替换为指向list("e", "f")。此外，曾经是x的tail的列表list("c", "d")现在已从结构中分离。
图 3.14 const z = pair(y, tail(x));对图 3.12 中的列表的影响。
图 3.15 set_tail(x, y)对图 3.12 中的列表的影响。
函数pair通过创建新的对来构建新的列表结构，而set_head和set_tail修改现有的对。事实上，我们可以使用这两个修改器来实现pair，再加上一个get_new_pair函数，它返回一个不属于任何现有列表结构的新对。我们获得新对，将其head和tail指针设置为指定的对象，并将新对作为pair的结果返回。²¹
function pair(x, y) { const fresh = get_new_pair(); set_head(fresh, x); set_tail(fresh, y); return fresh; }
练习 3.12
在 2.2.1 节中引入了以下用于追加列表的函数：
function append(x, y) { return is_null(x) ? y : pair(head(x), append(tail(x), y)); }
函数append通过将x的元素依次添加到y的前面来形成一个新的列表。函数append_mutator类似于append，但它是一个修改器而不是构造器。它通过将它们拼接在一起来追加列表，修改x的最后一个对，使其tail现在是y。（使用空的x调用append_mutator是一个错误。）
function append_mutator(x, y) { set_tail(last_pair(x), y); return x; }
这里last_pair是一个返回其参数中的最后一个对的函数：
function last_pair(x) { return is_null(tail(x)) ? x : last_pair(tail(x)); }
考虑交互
const x = list("a", "b"); const y = list("c", "d"); const z = append(x, y); z; ["a", ["b", ["c", ["d, null]]]] tail(x); response const w = append_mutator(x, y); w; ["a", ["b", ["c", ["d", null]]]] tail(x); response
缺少的response是什么？绘制框和指针图来解释你的答案。
练习 3.13
考虑以下make_cycle函数，它使用了练习 3.12 中定义的last_pair函数：
function make_cycle(x) { set_tail(last_pair(x), x); return x; }
绘制一个框和指针图，显示由z创建的结构
const z = make_cycle(list("a", "b", "c"));
如果我们尝试计算last_pair(z)会发生什么？
练习 3.14
以下功能非常有用，尽管有些晦涩：
function mystery(x) { function loop(x, y) { if (is_null(x)) { return y; } else { const temp = tail(x); set_tail(x, y); return loop(temp, x); } } return loop(x, null); }
函数loop使用“临时”名称temp来保存x的tail的旧值，因为下一行的set_tail会破坏tail。解释mystery一般是做什么的。假设v由以下定义
const v = list("a", "b", "c", "d");
绘制代表v绑定的列表的框和指针图。假设我们现在求值
const w = mystery(v);
绘制框和指针图，显示在求值此程序后v和w的结构。v和w的值将打印为什么？
共享和身份
我们在 3.1.3 节中提到了由赋值引入的“相同”和“改变”的理论问题。当不同的数据对象之间共享个别成对时，这些问题在实践中会出现。例如，考虑以下结构形成的结构
const x = list("a", "b"); const z1 = pair(x, x);
如图 3.16 所示，z1是一个head和tail都指向同一个x的成对。z1的head和tail共享x是pair实现的直接方式的结果。一般来说，使用pair构造列表将导致成对的交织结构，其中许多单个成对被许多不同的结构共享。
图 3.16 由pair(x, x)形成的列表z1。
与图 3.16 相比，图 3.17 显示了由此创建的结构
const z2 = pair(list("a", "b"), list("a", "b"));
在这个结构中，两个list("a", "b")列表中的成对是不同的，尽管它们包含相同的字符串。²²
图 3.17 由pair(list("a", "b"), list("a", "b"))形成的列表z2。
当被视为列表时，z1和z2都代表“相同”的列表：
list(list("a", "b"), "a", "b")
一般来说，如果我们只使用pair，head和tail在列表上操作，共享是完全不可检测的。但是，如果我们允许在列表结构上使用变异器，共享就变得重要。作为共享可能产生的差异的一个例子，考虑以下函数，该函数修改了应用于它的结构的head：
function set_to_wow(x) { set_head(head(x), "wow"); return x; }
尽管z1和z2是“相同”的结构，但将set_to_wow应用于它们会产生不同的结果。对于z1，改变head也会改变tail，因为在z1中head和tail是相同的成对。对于z2，head和tail是不同的，因此set_to_wow只修改head：
z1; [["a", ["b", null]], ["a", ["b", null]]] set_to_wow(z1); [["wow", ["b", null]], ["wow", ["b", null]]] z2; [["a", ["b", null]], ["a", ["b", null]]] set_to_wow(z2); [["wow", ["b", null]], ["a", ["b", null]]]
检测列表结构中的共享的一种方法是使用原始谓词===，我们在 1.1.6 节中引入了它来测试两个数字是否相等，并在 2.3.1 节中扩展了它来测试两个字符串是否相等。当应用于两个非原始值时，x === y测试x和y是否是相同的对象（即x和y是否作为指针相等）。因此，对于图 3.16 和 3.17 中定义的z1和z2，head(z1) === tail(z1)为真，head(z2) === tail(z2)为假。
如下一节所示，我们可以利用共享来大大扩展可以由成对表示的数据结构的范围。另一方面，共享也可能是危险的，因为对结构所做的修改也会影响其他恰好共享修改部分的结构。变异操作set_head和set_tail应该谨慎使用；除非我们对数据对象的共享有很好的理解，否则变异可能会产生意想不到的结果。²³
练习 3.15
绘制框和指针图，解释set_to_wow对上述z1和z2结构的影响。
练习 3.16
Ben Bitdiddle 决定编写一个函数来计算任何列表结构中的成对数。“很容易”，他推理道。“任何结构中的成对数是head中的数加上tail中的数再加一来计算当前的成对数。”于是 Ben 写下了以下函数
function count_pairs(x) { return ! is_pair(x) ? 0 : count_pairs(head(x)) + count_pairs(tail(x)) + 1; }
展示这个函数是不正确的。特别是，绘制盒和指针图，表示由恰好三对组成的列表结构，Ben 的函数将返回 3；返回 4；返回 7；根本不返回。
练习 3.17
设计练习 3.16 中count_pairs函数的正确版本，该函数返回任何结构中不同对的数量。（提示：遍历结构，维护一个辅助数据结构，用于跟踪已经计数的对。）
练习 3.18
编写一个函数，检查列表并确定它是否包含循环，也就是说，一个试图通过连续的tail找到列表末尾的程序会进入无限循环。练习 3.13 构建了这样的列表。
练习 3.19
使用仅占用恒定空间的算法重新执行练习 3.18。（这需要一个非常聪明的想法。）
突变只是赋值
当我们引入复合数据时，我们在 2.1.3 节中观察到，对可以纯粹用函数表示：
function pair(x, y) { function dispatch(m) { return m === "head" ? x : m === "tail" ? y : error(m, "undefined operation – pair"); } return dispatch; } function head(z) { return z("head"); } function tail(z) { return z("tail"); }
对于可变数据，同样的观察是正确的。我们可以使用赋值和本地状态将可变数据对象实现为函数。例如，我们可以扩展上面的对实现，以处理set_head和set_tail，类似于我们在 3.1.1 节中使用make_account实现银行账户的方式：
function pair(x, y) { function set_x(v) { x = v; } function set_y(v) { y = v; } return m => m === "head" ? x : m === "tail" ? y : m === "set_head" ? set_x : m === "set_tail" ? set_y : error(m, "undefined operation – pair"); } function head(z) { return z("head"); } function tail(z) { return z("tail"); } function set_head(z, new_value) { z("set_head")(new_value); return z; } function set_tail(z, new_value) { z("set_tail")(new_value); return z; }
理论上，只需要赋值就可以解释可变数据的行为。一旦我们承认在我们的语言中进行赋值，我们就提出了所有问题，不仅是赋值的问题，而且是可变数据的问题。²⁴
练习 3.20
绘制环境图来说明语句序列的求值
const x = pair(1, 2); const z = pair(x, x); set_head(tail(z), 17); head(x); 17
使用上面给出的对的函数实现。（比较练习 3.11。）
3.3.2 表示队列
改变器set_head和set_tail使我们能够使用对来构建不能仅用pair、head和tail构建的数据结构。本节展示了如何使用对来表示称为队列的数据结构。3.3.3 节将展示如何表示称为表的数据结构。
队列是一个序列，其中项目被插入到一端（称为队列的后端），并从另一端（前端）删除。图 3.18 显示了一个最初为空的队列，其中插入了项目a和b。然后移除了a，插入了c和d，并移除了b。因为项目总是按照插入的顺序移除，所以队列有时被称为FIFO（先进先出）缓冲区。
图 3.18 队列操作。
在数据抽象方面，我们可以将队列视为以下一组操作定义：
- 一个构造器：
make_queue()
返回一个空队列（不包含任何项目的队列）。 - 一个谓词：
is_empty_queue(queue)
测试队列是否为空。 - 一个选择器：
front_queue(queue)
返回队列前端的对象，如果队列为空则发出错误信号；它不修改队列。 - 两个改变器：
insert_queue(queue, item)
在队列的后端插入项目，并将修改后的队列作为其值返回。delete_queue(queue)
移除队列前端的项目，并返回修改后的队列作为其值，如果在删除前队列为空，则发出错误信号。
因为队列是一系列项目，我们当然可以将其表示为普通列表；队列的前端将是列表的head，在队列中插入项目将相当于在列表末尾添加一个新元素，从队列中删除项目只是取列表的tail。然而，这种表示是低效的，因为为了插入一个项目，我们必须扫描列表直到达到末尾。由于我们扫描列表的唯一方法是通过连续的tail操作，因此对于n个项目的列表，这种扫描需要Θ(n)步骤。通过对列表表示的简单修改，可以克服这个缺点，使得队列操作可以实现为需要Θ(1)步骤；也就是说，需要的步骤数与队列的长度无关。
列表表示的困难之处在于需要扫描以找到列表的末尾。我们需要扫描的原因是，尽管将列表表示为一对对的链表是标准的方法，它很容易为我们提供指向列表开头的指针，但它并没有为我们提供指向末尾的指针。避免这个缺点的修改是将队列表示为列表，以及一个额外的指针，指示列表中的最后一对。这样，当我们要插入一个项目时，我们可以查看后指针，从而避免扫描列表。
然后，队列表示为一对指针，front_ptr和rear_ptr，分别指示普通列表中的第一对和最后一对。由于我们希望队列是一个可识别的对象，我们可以使用pair来组合这两个指针。因此，队列本身将是这两个指针的pair。图 3.19 说明了这种表示。
图 3.19 将队列实现为具有前端和后端指针的列表。
为了定义队列操作，我们使用以下函数，这些函数使我们能够选择和修改队列的前端和后端指针：
function front_ptr(queue) { return head(queue); } function rear_ptr(queue) { return tail(queue); } function set_front_ptr(queue, item) { set_head(queue, item); } function set_rear_ptr(queue, item) { set_tail(queue, item); }
现在我们可以实现实际的队列操作。如果队列的前端指针是空列表，我们将考虑队列为空：
function is_empty_queue(queue) { return is_null(front_ptr(queue)); }
make_queue构造函数返回一个最初为空的队列，其head和tail都是空列表：
function make_queue() { return pair(null, null); }
要选择队列前端的项目，我们返回由前端指针指示的对的head：
function front_queue(queue) { return is_empty_queue(queue) ? error(queue, "front_queue called with an empty queue") : head(front_ptr(queue)); }
要在队列中插入一个项目，我们遵循图 3.20 中指示的结果的方法。我们首先创建一个新的对，其head是要插入的项目，其tail是空列表。如果队列最初为空，我们将队列的前端和后端指针设置为这个新对。否则，我们修改队列中的最后一对，使其指向新对，并且将后端指针设置为新对。
function insert_queue(queue, item) { const new_pair = pair(item, null); if (is_empty_queue(queue)) { set_front_ptr(queue, new_pair); set_rear_ptr(queue, new_pair); } else { set_tail(rear_ptr(queue), new_pair); set_rear_ptr(queue, new_pair); } return queue; }
图 3.20 在图 3.19 的队列上使用insert_queue(q, "d")的结果。
要删除队列前端的项目，我们只需修改前端指针，使其现在指向队列中的第二个项目，可以通过跟随第一个项目的tail指针找到（参见图 3.21）：²⁵
function delete_queue(queue) { if (is_empty_queue(queue)) { error(queue, "delete_queue called with an empty queue"); } else { set_front_ptr(queue, tail(front_ptr(queue))); return queue; } }
图 3.21 在图 3.20 的队列上使用delete_queue(q)的结果。
练习 3.21
Ben Bitdiddle 决定测试上述队列实现。他将函数输入 JavaScript 解释器，并开始尝试它们：
const q1 = make_queue(); insert_queue(q1, "a"); [["a", null], ["a", null]] insert_queue(q1, "b"); [["a", ["b", null]], ["b", null]] delete_queue(q1); [["b", null], ["b", null]] delete_queue(q1); [null, ["b", null]]
“这全都错了！”他抱怨道。“解释器的响应显示最后一个项目被插入队列两次。当我删除两个项目时，第二个b仍然存在，所以队列不是空的，尽管它应该是。”Eva Lu Ator 建议 Ben 误解了发生了什么。“不是项目被插入队列两次，”她解释道。“只是标准的 JavaScript 打印机不知道如何理解队列表示。如果你想正确打印队列，你必须为队列定义自己的打印函数。”解释 Eva Lu 所说的。特别是，说明 Ben 的示例产生了它们所产生的打印结果。定义一个函数print_queue，该函数以队列作为输入并打印队列中的项目序列。
练习 3.22
我们可以将队列表示为具有本地状态的函数，而不是将队列表示为一对指针。本地状态将包括指向普通列表的开头和结尾的指针。因此，make_queue函数将具有以下形式
function make_queue() { let front_ptr = ...; let rear_ptr = ...; 〈declarations of internal functions〉 function dispatch(m) {...} return dispatch; }
完成make_queue的定义，并使用此表示提供队列操作的实现。
练习 3.23
双端队列（“deque”）是一个序列，其中项目可以在前端或后端插入和删除。双端队列的操作包括构造函数make_deque，谓词is_empty_deque，选择器front_deque和rear_deque，以及变异器front_insert_deque，front_delete_deque，rear_insert_deque和rear_delete_ deque。展示如何使用对表示 deque，并给出操作的实现。²⁶所有操作应在Θ(1)步骤中完成。
3.3.3 表示表
当我们在第 2 章研究了各种表示集合的方式时，在第 2.3.3 节中提到了通过识别键索引的记录表的维护任务。在第 2.4.3 节中的数据导向编程的实现中，我们广泛使用了二维表，其中使用两个键存储和检索信息。在这里，我们看到如何将表构建为可变列表结构。
首先考虑一维表，其中每个值都存储在单个键下。我们将表实现为记录的列表，每个记录都实现为一个由键和相关值组成的对。这些记录通过将head指向连续记录的对粘合在一起形成列表。这些粘合对被称为表的支柱。为了在向表中添加新记录时有一个可以更改的位置，我们将表构建为头列表。头列表在开头有一个特殊的支柱对，其中包含一个虚拟的“记录”——在这种情况下是任意选择的字符串"table"。图 3.22 显示了表的盒子和指针图。
a: 1 b: 2 c: 3
图 3.22 以头列表形式表示的表。
为了从表中提取信息，我们使用lookup函数，该函数以键作为参数并返回相关值（如果在该键下没有存储值，则返回undefined）。lookup函数是根据assoc操作定义的，该操作期望键和记录列表作为参数。请注意，assoc从不看到虚拟记录。assoc函数返回具有给定键作为head的记录。²⁷然后lookup函数检查assoc返回的结果记录是否不是undefined，并返回记录的值（tail）。
function lookup(key, table) { const record = assoc(key, tail(table)); return is_undefined(record) ? undefined : tail(record); } function assoc(key, records) { return is_null(records) ? undefined : equal(key, head(head(records))) ? head(records) : assoc(key, tail(records)); }
要在指定的键下向表中插入一个值，我们首先使用assoc来查看表中是否已经存在具有该键的记录。如果没有，我们通过将键与值进行pair形成一个新记录，并将其插入到表的记录列表的头部（在虚拟记录之后）。如果已经存在具有该键的记录，我们将该记录的tail设置为指定的新值。表的标题为我们提供了一个固定的位置，以便插入新记录。²⁸
function insert(key, value, table) { const record = assoc(key, tail(table)); if (is_undefined(record)) { set_tail(table, pair(pair(key, value), tail(table))); } else { set_tail(record, value); } return "ok"; }
要构造一个新表，我们只需创建一个包含字符串"table"的列表：
function make_table() { return list("table"); }
二维表
在二维表中，每个值都由两个键索引。我们可以将这样的表构造为一个一维表，其中每个键都标识一个子表。图 3.23 显示了该表的框和指针图。
"math": "+": 43 "-": 45 "*": 42 "letters": "a": 97 "b": 98
该对象有两个子表。（子表不需要特殊的标题字符串，因为标识子表的键就起到了这个作用。）
图 3.23 二维表。
当我们查找一个项目时，我们使用第一个键来标识正确的子表。然后我们使用第二个键来标识子表中的记录。
function lookup(key_1, key_2, table) { const subtable = assoc(key_1, tail(table)); if (is_undefined(subtable)) { return undefined; } else { const record = assoc(key_2, tail(subtable)); return is_undefined(record) ? undefined : tail(record); } }
要在一对键下插入一个新项目，我们使用assoc来查看是否已经存储了第一个键下的子表。如果没有，我们构建一个包含单个记录（key_2，value）的新子表，并将其插入到第一个键下的表中。如果有一个
如果第一个键的子表已经存在，我们将使用上面描述的一维表的插入方法将新记录插入到该子表中：
function insert(key_1, key_2, value, table) { const subtable = assoc(key_1, tail(table)); if (is_undefined(subtable)) { set_tail(table, pair(list(key_1, pair(key_2, value)), tail(table))); } else { const record = assoc(key_2, tail(table)); if (is_undefined(record)) { set_tail(subtable, pair(pair(key_2, value), tail(subtable))); } else { set_tail(record, value); } } return "ok"; }
创建本地表
上面定义的lookup和insert操作将表作为参数。这使我们能够使用访问多个表的程序。处理多个表的另一种方法是为每个表单独拥有lookup和insert函数。我们可以通过过程化地表示一个表来实现这一点，将其作为一个对象，该对象将内部表作为其本地状态的一部分。当发送适当的消息时，这个“表对象”提供用于在内部表上操作的函数。以下是以这种方式表示的二维表的生成器：
function make_table() { const local_table = list("table"); function lookup(key_1, key_2) { const subtable = assoc(key_1, tail(local_table)); if (is_undefined(subtable)) { return undefined; } else { const record = assoc(key_2, tail(subtable)); return is_undefined(record) ? undefined : tail(record); } } function insert(key_1, key_2, value) { const subtable = assoc(key_1, tail(local_table)); if (is_undefined(subtable)) { set_tail(local_table, pair(list(key_1, pair(key_2, value)), tail(local_table))); } else { const record = assoc(key_2, tail(subtable)); if (is_undefined(record)) { set_tail(subtable, pair(pair(key_2, value), tail(subtable))); } else { set_tail(record, value); } } } function dispatch(m) { return m === "lookup" ? lookup : m === "insert" ? insert : error(m, "unknown operation – table"); } return dispatch; }
使用make_table，我们可以实现第 2.4.3 节中用于数据导向编程的get和put操作，如下所示：
const operation_table = make_table(); const get = operation_table("lookup"); const put = operation_table("insert");
函数get以两个键作为参数，put以两个键和一个值作为参数。这两个操作都访问同一个本地表，该表封装在通过调用make_table创建的对象中。
NUS CS1101S：SICP JavaScript 描述：三、模块化、对象和状态（3）https://developer.aliyun.com/article/1427726
