《计算机程序的构造和解释》全书摘要与逐章导读

第 1 章是怎样展开的AI 辅助

开场：一个看不见的问题。 这一章开头讲的不是语法，而是一个困境。程序指挥一个没有人看得见的计算过程，这意味着程序员的核心技能，是预见一个小错误在下游会造成什么——而作者的例子坚持说，惩罚与错误的大小并不成比例：设计程序里的一个 bug，可能以坍塌的飞机或水坝告终，或是一个机器人毁了自己。接着，Lisp（Scheme 方言）被论证为合适的载体，并从这个框架里提炼出本章的组织性主张：任何真正有力的语言都恰好提供三样东西——基本表达式、组合的手段、抽象的手段。开场的其余部分，只是把这个三元组一步步落到实处。表达式与递归的求值规则先出场，被画成一棵树，值沿着树向上渗透，所以对 (* (+ 2 (* 4 6)) (+ 3 5 7)) 求值，就是把一条规则用到四个组合式上。然后是 define，最简单的抽象，让 circumference 代表 62.8318——不过作者小心地称命名只是一种“有限的”抽象，而正是这个压力，让复合过程成为下一步。

第一个展开：一个模型，及其坦率的免责声明。 有了复合过程，本章需要说明应用一个复合过程“意味着”什么，于是给出代换模型。这里要紧的是紧随其后的限定。代换是给读者推理用的脚手架，不是对解释器的报告：真实的实现是在一个局部环境里约束形式参数（推迟到第3章和第4章），而一旦过程操作可变数据，这个模型就明说会垮掉。作者把这种“超越”说成普通的科学实践，而不是缺陷——这一点值得记住，因为自然的误读是把文本替换当作机器的图景。从这个模型出发，本章分叉到应用序对正则序，然后是 cond/if 和逻辑谓词，这给了它足够的机制去尝试做点真东西。

转向方法：牛顿法求平方根。 那件真东西是平方根，它承载了本章最尖锐的概念区分。平方根的数学定义，即使音译成伪 Lisp，也是完全合法的，却几乎没有告诉你怎样去找一个。所以计算过程与数学函数不是同一类对象，因为它必须是“有效的”——说明式知识对命令式知识——而牛顿法补上了缺失的“怎么做”。造好之后，本章马上把这个结果转成一课关于打包的功课：过程是黑盒，有约束变量和自由变量，而块结构让 good-enough? 和 improve 住在 sqrt 里面，既够不到用户，也够不到别的、正在写他们自己的近似例程的程序员。词法作用域随后完成这一步：因为 x 由 sqrt 自己约束，嵌套的辅助过程就坐在它的作用域里，把它当作自由变量引用，所以 x 不必作为额外的参数传来传去。

第二个展开：作为测量对象的计算过程。 本章现在把口气从“过程意味着什么”换成“过程代价几何”。斐波那契和换零钱给出演示：树形递归容易写，却指数级地浪费，因为朴素的 fib 在许多分支上重复计算同样的小情形，而最终落到 (fib 1) 或 (fib 0) 的叶子数，恰好是 Fib(n+1)——本身就是指数的。这种不对称是最难忘的部分：内存只需要保存沿着树往下的当前路径，所以空间只与 n 成正比地增长，而时间爆炸。迭代随后显得廉价，增长阶的记号（theta）提供了词汇，而逐次平方和欧几里得算法给出真正对数级的替代。这个序列以费马检验收尾，它把测量推进一个新的范畴：随机选一个 a < n，检查 aⁿ 模 n 是否等于 a，然后重复。只有失败是决定性的——卡迈克尔数对每一个 a 都满足这个同余式，所以通过什么也证明不了——但它们稀少得足以让检验保持实用，而有了不可欺骗的变体，每次独立抽取都会使被误导的概率相乘，所以一次通过胜过一半一半，两次胜过四分之三，足够多次试验可以把出错概率降到想要的低。这就界定了概率性算法，一类保证是统计性而非演绎性的方法。

最后的展开：抽象用到自己身上。 高阶过程是通过一个从反面出发的论证到来的。一门没有办法给“立方”命名的语言，仍然可以计算立方，却会迫使每个人停留在一次次乘法的层次上；反过来，一门不能把过程当作参数的语言，只能陈述一个模式的实例，永远陈述不了模式本身。sum 就是演示——给定一个项函数、一个取下一个下标的函数，以及上下界 a 和 b，它把 sum-cubes、sum-integers 和 pi-sum 收成三次调用，就像求和记号 sigma 表达一般的求和。本章随后把这个手段叠加起来：sum 变成 integral；lambda 和 let 处理掉有名字的辅助过程；half-interval 和 fixed-point 表达的是一般方法，而不是特定的计算；而 average-damp 和 deriv 靠“返回”过程越过了剩下的那条线——把 average-damp 用到 square 上，得到一个对 10 返回 55 的过程，而把 fixed-point 同平均阻尼复用，立刻就产生了 cube-root。

收束：为挣得的东西命名。 最后一个运动是把线索系在一起，而不是增加材料。牛顿法由 deriv 重建为一个不动点过程，然后两个平方根程序——本章前三分之一手工做出来的那个，和牛顿版本——都从同一个 fixed-point-of-transform 里落了出来，这是本章自己的证明：它一直是在抽象方法，而不只是计算。在此基础上，本章命名了一等公民地位及其四项权利：过程可以被命名、被当作参数传递、被当作结果返回、被存进数据结构（最后一项要到后面才演示）。Lisp 四项都给了；作者承认这使高效实现变复杂，并论证表达力偿还了这笔代价。这一章于是恰好结束在它开头的那个三元组所指向的地方：抽象的手段被转用在它们自己身上，使抽象不再只是被构造，而是被操作。

关键论点，以及支撑它们的原文

它是怎样运作的

本章论证所依靠的 3 个机制。

常见误读

第 1 章的核心概念

计算过程

计算机内部一个看不见、无形、却真实存在的实体，在程序的指引下，随着演化操作数据。

适用处： 它不是物质，也看不见，却做着实实在在的智力工作，并能影响物理世界。

抽象的手段

让复合元素可以被命名、并当作单一单元来处理的语言特性。

适用处： 仅仅 define 只给出有限的抽象手段；过程定义才是更有力的那一种。

组合式

一个带括号的表，表示过程应用，运算符在最左，其余是运算对象。

适用处： 像 (define x 3) 这样的定义不是组合式；它们是特殊形式。

环境

解释器里“名字-对象”对的存储，使符号有了含义。

适用处： 这里叫作全局环境，因为以后的计算会涉及好几个环境。

特殊形式

自带求值规则的一种表达式类型，在一般的组合式规则之外。

适用处： define 是迄今引入的唯一特殊形式；这类规则的集合加上一般规则，就构成这门语言的语法。

复合过程

一个有名字的复合操作，它的形式参数代表应用时提供的实参。

适用处： 使用起来，与解释器内置的基本过程没有区别。

第 1 章划线与批注AI 陪读

第 2 章是怎样展开的AI 辅助

这一章一开头就论证：复合数据之所以有价值，原因恰与复合过程相同——它提高了你思考和写作的层次。演示是有理数程序包：cons 把分子和分母粘在一起，一旦一个有理数可以作为一个对象传来传去，一个线性组合的例程就不必再亲手追踪哪个整数和哪个整数配对。由此，本章提炼出它的组织性想法，即“数据抽象”：构造函数和选择函数构成一道屏障，因为只有它们碰表示，格式的改变就只波及那几个过程，而建在它们之上的一切继续工作。开场还确定了本章的有效性标准——使一样东西成为数据表示的，是它的构造函数和选择函数所满足的“条件”（取回分子和分母必须重现这个比值），而不是它是用什么做的。

第一个展开：条件就够了，所以过程就足够

这个标准随后被一路压到序对本身。如果一个序对必须做的只是满足 cons/car/cdr 的恒等式，那么 cons 就可以直接返回一个记住它两个参数、并回应下标 0 和 1 的过程；代换验证了这些恒等式，而这个抽象的使用者分不出它同存储结构的区别。这是本章第一个真正的概念收获——表示被消解为行为——而区间算术给出了一个屏障要紧的演算例子。与它并行的是第二个收获，“闭包”性质：因为序对的各部分本身可以是序对，一种基本体就成了层次结构的通用建筑块。

展开继续：序列作为约定的接口

闭包产生表和树，本章现在为它们寻找合适的词汇。map 抽象出逐元素的处理，递归加上 map 处理树，然后 enumerate/filter/map/accumulate 把程序变成显式的信号流管道。这里的论证被小心地限定了：不管哪种办法，机器运行的是同一个计算过程；变的是程序员的框架。在普通的递归版奇数平方和里，枚举阶段被涂抹在基本情形检验和递归下降里，对应不上任何可辨认的部分。一旦这四个操作成了词汇，各阶段变得可见，各块成了标准部件——那个过程的片段，和一个偶数斐波那契过程的片段，可以自由重组，而嵌套循环通过 flatmap，成了“生成-过滤-映射”的管道，比如素数和对、排列、八皇后。

一次反转，还不是转折：数据对象作为过程

图形语言随后把先前的洞见倒着走一遍。画家“就是”一个接受框架的过程，所以 flip-vert 只需要把框架反转，beside 只需要把两个画家缩小到半个框架并调用每一个——两者都不知道任何一个画家是怎么画的。画家在 beside 和 below 下封闭，而因为这些操作是普通的 Scheme 过程，不需要特殊的组合机制：square-of-four 接受四个画家操作，返回另一个。框架变换把这推广为 transform-painter，这一节以“分层设计”收尾：每一层提供自己的基本元素、组合手段和抽象的手段，所以规格上的小改动只触及一个层。

符号插曲，以及作为效率所在地的表示

符号微分以相反的顺序重演开头的方法：deriv 先针对抽象的和、积与变量写好，然后才选定前缀表的表示，化简被限制在构造函数里。集合随后表明互补的一点——在一个固定的接口之后，效率是在表示里得到或失去的。无序的表给出线性的成员检验和平方级的交集；有序使平均检验减半，并且因为交集的每一步都从两个集合之一中丢掉一个元素，把交集化为两个大小之和；二叉树则达到对数级的搜索。收益被明确说是有条件的：按顺序把 1 到 7 一个个并入，得到的是每个左子树都为空的树，不比表好。霍夫曼编码树作为一个持续的例子，结束这段插曲——变长的前缀码，基于树的编码和解码，合并算法，以及按权重排序的集合。

转折：多重表示、表格，与层次的极限

真正的转折，出现在同一个对象有几种好的表示的时候。复数的直角形式便于加法，极坐标形式便于乘法，而在由许多人长期写成的系统里，没有哪种表示能事先商定。类型标志使得按表示分别设选择函数成为可能——没有标志，序对 (3,4) 的模长，在 5 和 3 之间含混不清——但靠显式条件的分派，迫使每个通用过程都知道每一种表示，每个名字都保持全局唯一，这无法扩展。补救办法是数据导向的程序设计：一张带 put 和 get 的二维“操作-类型”表，apply-generic 读标志、查一个格子、应用找到的东西，所以添一种表示，就意味着添加表项，而不是编辑代码。程序包按行分解这张表，消息传递按列分解它；带 scheme-number、有理数和复数程序包的通用算术，展示了两层标志的运作。

收束：强制、塔，和一个被承认的未决问题

跨类型的操作随后分三步升级——显式的成对过程，强制表，最后是带 raise 和 lower 的类型塔——而本章坦率地说，这座塔能成立，只因为每种类型恰好只有一个上级类型。在一种类型有几个上级的地方（一个等腰直角三角形，既在三角形之下，又在直角三角形之下），没有唯一的向上之路，而要关联这些类型就需要代价高昂的搜索。多项式给出了这套机制的最后一个案例，也反驳了自满：项表是通过抽象的构造函数和选择函数访问的，add-terms 和 mul-terms 调用的是“通用的” add 和 mul，所以这个程序包继承了任何系数类型，并以数据导向的方式递归，选用稀疏的有序表作为表示。本章结束时给出的不是一个解法，而是一个承认——多项式类型不能叠成一座塔，而强制一般来说仍然所知甚少——脚注则指向点值表示和拉格朗日插值、数的零次强制、欧几里得算法的欧几里得环论证、有理系数 GCD 的陷阱，以及齐佩尔的概率性方法。

关键论点，以及支撑它们的原文

它是怎样运作的

本章论证所依靠的 3 个机制。

常见误读

第 2 章的核心概念

数据抽象

把程序构造成：使用一个复合数据对象的代码，对它是怎么构造的不做任何假设。 选择表示和抽象的选择函数，使系统的其余部分不受表示变化的影响。

适用处： 一旦程序的不同部分用不同方式表示同样的数据，单靠简单的数据抽象就不够了；通用操作需要更强的屏障。 只有当访问真的通过抽象的选择函数和构造函数时才行。

抽象屏障

一道层次的边界，一小组接口过程把数据抽象的使用者同它的实现者隔开。

适用处： 只有所有的操作都通过选定的操作进行时才成立；直接访问表示就会破坏它。

序对

由 cons 做成的唯一基本复合结构，各部分由 car 和 cdr 读出。

适用处： 序对可以任意嵌套，所以一种基本体就足以充当更大结构的粘合剂。

一厢情愿的想法

假定构造函数和选择函数已经存在，这样高层操作就可以在选定任何表示之前先写出来。 假定所需的选择函数和构造函数已经存在，这样你现在就可以写算法。

适用处： 只有当所假定的过程以后能满足所规定的条件时才有效。 只有在你以后真的实现了每一个假定的谓词、选择函数和构造函数时才安全。

数据即选择函数加条件

数据不只是随便三个过程返回的东西；构造函数和选择函数必须满足所述条件。

适用处： 任意的三个过程不构成一种表示。

数据的过程性表示

把序对表示为一个被要求时就返回其各部分的过程，而不是存储结构。 把数据对象表示为一个接受操作名并自己执行它的过程。

适用处： 就正确性而言是够用的，但真正的 Lisp 为了效率直接实现序对。 按这里的给法，它只允许单个参数的通用过程。

第 2 章划线与批注AI 陪读

第 3 章是怎样展开的AI 辅助

第3章一开头就承认前面所讲的有一个局限：光靠抽象，并不能告诉你怎样安排一个程序的布局。强大的过程和复合数据让你造出大东西，却没说接缝该设在哪里，于是本章动身去寻找模块性的“组织原则”。它提出的策略是模仿——把程序构造得像它所建模的系统，这样扩展这个世界，就意味着在代码里加一个对应物，而不是整个重写。试金石是银行账户：能不能取出100美元，取决于全部交易的历史，被压缩成一个当前余额，所以程序的自然单位，就是带着这个余额的对象。从这一个例子出发，本章宣布了它将用余下篇幅展开的两种对立的世界观——一个有状态对象的世界，和一个流的世界——并立刻警告说，第一种是有代价的：代换模型必须放弃，换成环境模型。

它是怎样展开的

第一个运动把这笔代价详细地兑现。赋值买来局部状态，但变量不再命名一个值，而成了对一个可变位置的引用，前面几章里简单的推理就垮了：把 balance 代换进 make-simplified-withdraw，得出错误的答案，因为两处出现再也无法区分。本章用一个成对的比较使这种损失更尖锐——由相同文本写出的两个函数式过程是可互换的，由相同文本写出的两个取款器却不是——所以相同的文本不再意味着相同的含义。随之而来的后果是：在命令式代码里，赋值的“顺序”成了含义的一部分。命令式的阶乘碰巧把两个 set! 放对了顺序；把它们对调，答案就错了，而函数式的版本压根没有可以对调的顺序。诊断了问题之后，本章给出替代的机制：两条规则，一次调用据此建立一个被过程对象所指向的环境所包围的框架，而一个 lambda 把代码同它的出生地配成一对。这恰恰解释了为什么每次 make-withdraw 调用都留下自己私有的 balance，以及为什么两个取款器从不互相干扰。

第二个运动把赋值带进数据本身。有了 set-car! 和 set-cdr!，共享不再是一个看不见的实现细节，而成了可观察的：z1 和 z2 打印出来一样，同一个改变过程却从一个产生 ((wow b) wow b)，从另一个产生 ((wow b) a b)，因为在 z1 里 car 和 cdr 是同一个序对；eq? 直接暴露出这个区别。本章小心地坚持：没有任何新东西被偷运进来——用带内部 set! 的过程做成的序对，自己提供 set-car! 和 set-cdr!，所以承认赋值，就已经承认了可变数据的一切困难。可变序对随后作为工程回报了自己：带头尾指针的常数时间队列，以及作为带头表的表格，一维和二维的，包装成局部对象。

接下来是两个较大的模拟，它们标志着对象观点内部的一次安静的转移。数字电路模拟器彻头彻尾是有方向的：导线是带动作过程的可变的、传递消息的对象，门安排延时的信号变化，而一个由按时间排序的段构成的议程，驱动传播。随后的约束网络用同样的材料造成——连接器和基本约束，作为带局部状态的过程性对象——却抛弃了有特权的方向。本章论证，要点不在算术，而在没有输入和输出：普通的面积过程无法倒着运行，而一个摄氏-华氏网络，当告诉它 C 是 25 时回答 77，而在这个值被撤回之后，掉转过来，当告诉它 F 是 212 时给出 C = 100。要保持诚实，需要关于理由的簿记：一个连接器只在提供它的那一方要求时才撤回它的值，所以撤回 C 使 F 因为没有理由而放弃 77，而在 C 仍在时断言 F，只会引起矛盾。

转折在哪里

真正的转折随时间而来。一旦并发进程共享可变状态，赋值的隐藏结构就要紧了：它读、算、写，所以第二次读可能在第一次写落地之前插进来，从100美元里取10美元和25美元，可能留下75美元。本章没有禁止同时的改变——正确，却浪费，因为给一个私人账户存钱，没有理由要等一个共享的账户——而是采纳较弱的标准：结果必须与“某种”顺序执行相符，这意味着几种不同的结果可能都是正确的。建立在互斥元上的串行化器强制执行这一点，而这个判据是有牙齿的：把两个并行过程串行化，把 x 的可能值从五个减少到 101 或 121。但本章拒绝那个令人安心的结论：每个对象各设串行化器就能使并发安全。它们一次只能处理一个资源；一个跨两个账户的交换，仍可能在一方计算差额、另一方改变账户时被破坏，而通常的补救——输出串行化器——故意破坏了对象的模块性。在互斥元之下是原子的 test-and-set!；在它们之上潜伏着死锁，两个人朝相反方向交换 a1 和 a2，永远等下去，靠按固定的编号顺序获取资源来缓解，有时还需要彻底的检测和恢复。又因为共享状态在流水线式或分布式系统里甚至没有良好定义，并发里的时间就归结为通信——这恰恰是流的观点所需要的开口。

它是怎样收尾的

最后一个运动，不用赋值重建变化。流是一个序对，其余部分是一个未求值的承诺，所以每个阶段只在下一个阶段要求时才产生一个元素：在 10,000 和 1,000,000 之间找一个素数，只检验到 10,009 为止的数，而不是造出一个百万元素的表。delay 和 force 原来不过是 lambda 加记忆化——而记忆化不是优化，而是必需，因为同一个承诺被反复强制，递归的流程序否则会无休止地重算。由此，本章收获了无穷的 integers、fibs，埃拉托色尼筛法，隐式的自指定义，级数的欧拉加速和表格加速，交错的无穷序对流，以及信号处理里的反馈回路，在那里被积函数的延时，使 solve 能把结系在自己身上。然后它拒绝宣布胜利。显式的 delay 很别扭，把世界分成普通过程和期待承诺的过程，所以像 integral 这样的东西的每个调用者，都得知道这个约定——可是通过正则序求值使延时普遍化更糟，因为可变性与延时求值在程序设计语言里，不知道能否良好结合。流甚至可以取代局部状态，如蒙特卡罗估计 π；但把真正独立的主体的请求流合并起来，实时顺序的问题就原封不动地回来了。本章有意不作了结地收尾：两种世界观，各自用另一方付不起的代价买来模块性，谁也吸收不了谁。

关键论点，以及支撑它们的原文

它是怎样运作的

本章论证所依靠的 3 个机制。

常见误读

第 3 章的核心概念

模块性

把系统构造得能自然地分成一致的几个部分，各部分可以分别建造和维护。

适用处： 这是组织的目标，单靠抽象并不能保证。

局部状态

一个对象的行为取决于它的历史时，它就有状态；状态变量概括了这段历史。 每个连接器和约束，都是一个封闭了私有变量、按消息分派的过程。

适用处： 只有当状态变量聚成松耦合的子系统时才有用。 第3章表明，这种建模能力的代价，是引用透明性，并且迫使时间进入模型。

代换模型

先前把过程应用理解为用值替换参数的看法；赋值会破坏它。 把符号当作值的名字，于是应用一个过程，就意味着在文本上用实参替换形参。

适用处： 一旦有了 set! 就不够用了；由环境模型取代。 一旦 set! 让一个变量的值在求值过程中改变，它就失效。

引用透明性

在表达式里，相等的东西可以互相代换而不改变其值。

适用处： 一旦 set! 进入语言，就被违反。

函数式程序设计

不用赋值的程序设计，所以同一个调用、同样的参数，总得到同样的结果。

适用处： 与依赖赋值的命令式程序设计相对。

命令式程序设计

大量使用赋值去更新变量的程序设计。

适用处： 引来函数式代码里没有的赋值顺序方面的 bug。

第 3 章划线与批注AI 陪读

第 4 章是怎样展开的AI 辅助

开场。 这一章是靠放宽框架开始的，而不是引入一项技术。它的主张是：没有哪门固定的程序设计语言——包括 Lisp——会在问题变难时一直够用，而它所想到的不足，是适配上的，而不是能力上的。给出的类比是电气工程师，并排用着两套分层的记号，电路作为电阻和晶体管构成的网络，同样的系统又作为信号处理模块，因为单靠哪一种记号，都无法同时兼顾物理的视角和功能的视角。提出的补救是“元语言抽象”：当语言不再适配问题，就发明一门新的，并用一个求值器实现它。而在这里，本章种下了它余下篇幅都要去兑现的想法——决定表达式含义的求值器，本身不过是另一个程序，一个普通的 Lisp 过程。这单单一个观察，就把程序员从语言使用者变成语言设计者，因为赋予含义的机制，就在人已经在写的那些程序的空间之内。随之而来一个更强的推论：几乎任何像样的程序，都可以读成某种语言的求值器，而书重新审视了它自己前面的系统——多项式操作器、数字逻辑模拟器、约束传播器——表明每一个都有真正的基本元素、组合手段和抽象手段。这个检验并不平凡；仅仅接受输入，并不使一个系统成为一门语言。开场随后预告了要来的四个求值器：元循环的、惰性的、非确定性的，和逻辑的。

第一个展开：元循环求值器。 本章用 Lisp 建一个 Lisp 求值器，而构造的组织围绕着保持核心小巧。像 cond 和 let 这样的派生表达式，没有它们自己的求值规则；它们在求值之前被改写成 if 和 lambda 形式，所以一个多子句的 cond 成了嵌套的 if，在任何持有多个动作的分支外包一层 begin。因为翻译先发生，求值器只需要给小小的核心集合以显式规则，而添加便利的语法对它毫无代价。内部数据结构随后确定什么是真、什么是过程、什么是环境——变量-值的表构成的框架；基本过程被约束在一个全局环境里；一个读-求值-打印循环驱动全局。这个求值器被有意剥得很简，把错误处理和调试都略去了。回报是概念上的：既然程序是对一台抽象机器的描述，喂给求值器这样一份描述，它就“成了”那台机器。阶乘被读成一台由递减、乘法和相等检验部件、一个开关，以及它自己的一份副本构成的机器。作者设想了一个能把自己重新配置成任何别的电路的通用电路，来使这一点更尖锐——复杂得几乎无法想象——这就是为什么一个能放进一个短程序的通用求值器，是了不起的。它也是语言与其自身数据之间的桥梁，因为它所消费的程序，是用户的。

两项改进，然后是第一次转折。 离开元循环求值器之前，本章先修复，再调优它。依次的 define 悄悄破坏了块结构所许诺的同时作用域；把内部定义扫描出来，改成一个带 set! 的 let，恢复了它。然后是一次性能上的分离，带来了持久的结构后果：普通的求值器每过一遍，都要重新判断自己看的是哪种表达式，所以一个循环或递归，会一遍遍回答同样的语法问题。把分析同执行分开，使分析产生一个执行过程，只付一次语法的代价——lambda 体在过程创建时被分析，此后每次应用只运行结果。脚注结束这一节（宏、环境、通用性、停机定理），本章迎来第一次真正的转折：转向惰性求值。正则序把参数的求值推迟到需要时，用被强制并记忆化的 thunk 实现。收益是具体的：在普通的 Scheme 下，一个在不被使用的参数位置上带 (/ 1 0) 的过程调用会出错，而用延时的参数，它直接返回 1，因为那个参数从不被计算。像 unless 这样的过程成了可写的，非严格的 cons 成为可能——这正是表和流合并的地方，因为你可以不计算元素就取一个表的长度，而普通的表操作开始作用在无穷表上，延时被统一起来。

第二次转折：非确定性计算。 本章随后改变语言，比惰性深得多。amb 让一个表达式有几个可能的值，而求值器靠按时间顺序的回溯在它们之间搜索。区别在于种类：程序员现在陈述要求，而机制隐藏了选择是怎么做出的：prime-sum-pair 看上去像是对它自己问题的重述——从每个表里取一个元素，坚持要求和是素数——却能运行，先打印出 (3 20)，要求时再给出 (3 110) 和 (8 35)，然后报告什么也不剩了。正如惰性隐藏了延时和强制，这隐藏了选择。本章把 amb 用于自然语言解析，语法规则作为作用于全局 *unparsed* 的过程，并指出一句话可能有几种合法的解析。实现建立在分析求值器之上：每个表达式被交付两条后续路径，一条是带着一个值走的成功延续，一条是尝试死掉时走的失败延续。死去的分支调用失败路径，去试下一个备选；amb 自己的“试下一个”循环，和驱动程序的 try-again，都复用同一条第二路径；而赋值把自己包在一条失败路径里，先恢复旧值，所以撤退不留残余。

第三次转折：逻辑程序设计与查询系统。 本章最后也是最长的一个运动，从“怎么做”转向关系性的“是什么”。它先从用户一侧介绍查询语言——带 ?变量 的简单模式，复合的组合手段 and、or、not 和 lisp-value，以及作为这门语言抽象手段的规则，用 lives-near、wheel、outranked-by 和 append-to-form 加以说明。然后解释机制：查询作用在框架的流上，各组合手段过滤并扩展这些流；合一把模式匹配推广，使规则的结论能被匹配；而规则的应用原来与 eval/apply 相映。关键的是，本章坦率地说了逻辑的表面在哪里漏了。子句的顺序没有逻辑含义，却决定会发生什么：一条对称的 married 规则会永远循环，而因为否定只过滤那些变量已被约束的框架，把 not 子句放在最前面，会丢掉那唯一的空框架，查询什么也不返回——哪种顺序更便宜，则取决于数据的相对大小。实现一节随后提供了机制：以数据导向风格分派特殊形式的 qeval，把断言匹配同规则应用合并起来的 simple-query，靠唯一的规则应用编号实现的变量重命名，守护合一的 depends-on?，交错的延时流，被索引的数据库，把 ?x 改写成 (? x) 的语法过程，以及作为约束表的框架。

收束。 本章结束在它自己的局限上，而不是一场胜利。习题推动着往效率、not 的正确性，以及通过非确定性求值或环境重新设计系统去。结尾的脚注与此一脉相承：失败即否定被标出需要恰当的引用；把一个变量同含有它自己的表达式合一，被表明要求一个可能不存在的不动点，被比作对发散级数的非法操作；而 ?x 记号被承认原本可以交给读入宏处理，只是为清晰起见写了出来。本章于是结束在它开始的地方，封闭世界假设和自指上——它已经证明，四种相当不同的语言，都是作为对同一个可访问的 Lisp 程序的修改而得到的，其中最远的一种，仍复用了它的基本结构。

关键论点，以及支撑它们的原文

它是怎样运作的

本章论证所依靠的 3 个机制。

常见误读

第 4 章的核心概念

元语言抽象

从编写程序上升一层，去设计、构造程序所用的语言。

适用处： 在所有工程中都要紧，但只有在编程中，新语言才也能被执行，因为你可以为它构造一个求值器。

求值器（解释器）

一个普通的过程，接受一门语言的表达式，并执行赋予该表达式含义的任何动作。

适用处： 求值器确定表达式的含义，所以改变求值规则，就意味着编辑一个程序，而不是等待一门新语言；它不是程序世界之外的特权制品。

元循环求值器

用某门语言本身写成的、该语言的求值器——这里是用 Lisp 写成的 Lisp 求值器。

适用处： 这种循环只是表面的：求值是一个过程，而 Lisp 是本书描述过程的工具，所以这个定义是有根基的，而不是空洞的。

eval/apply 循环

这个两步的循环：环境中的表达式归约为应用于实参的过程，后者又归约为新环境里的新表达式。

适用处： 这种回归只在环境中查到的符号，和直接应用的基本过程处终止。

通过数据抽象得到的抽象语法

通过谓词和选择函数来检验和拆解表达式，而不是把它们的表表示硬接线到求值器里。

适用处： 它使求值器与表面记号解耦，但除非把分派做成数据导向的，eval 的 cond 分派仍然固定了存在哪些表达式类型。

派生表达式

通过翻译成别的特殊形式来实现、而不是直接求值的特殊形式。

适用处： 只对其含义能完全由现有形式表达的形式成立，如 cond 通过嵌套的 if，let 通过 lambda 应用。

第 4 章划线与批注AI 陪读

第 5 章是怎样展开的AI 辅助

这一章开头不是一台新机器，而是对旧求值器的不满。上一章的元循环求值器，是用它声称要解释的那门语言写成的，能描述 Lisp 表达式的含义，却说不出控制是怎样运作的：它从未解释一个子表达式的值怎样找回向它索取的那一方，也没解释为什么有些递归过程能在常数空间里运行。它只是借用了宿主 Lisp 的控制机制。所以这一章完全下降到 Lisp 之下，到寄存器机器——一组固定的寄存器，一组固定的基本操作，和一个给它们排序的控制器。开场的例子是 GCD 机器，用三种方式呈现：数据通路图，控制器图，以及一种稍后要喂给模拟器的文本描述语言。开场的要点是：在这样一台机器的任何一个控制器点上，一个迭代计算的整个状态，就是各寄存器的内容。什么也没有藏起来。

展开一：标号，然后是栈

展开从把这个主张推到崩溃开始。把标号存进寄存器，使 gcd 成了一个真正的子程序，可以从不止一个地方调用——一个温和的扩展。使这个模型垮掉的是阶乘。你不能为递归调用重复使用同一台机器，靠递减 n 并重新开始，因为旧的 n 仍然被最后一次乘法需要；重新开始会抹掉待办工作所依赖的值。化解的办法是带 save 和 restore 的栈：因为同一时刻只有一个嵌套实例是活跃的，保存活着的寄存器加上返回标号（continue 总是被保存），就让一台带 n、val 和 continue 的有限机器，能挂起外层实例、解决内层实例、再恢复并完成，深度只受栈的大小限制。因此留下来的主张是个更锋利的主张——迭代只需要寄存器，递归需要一个额外的机制，而一台有限的机器仍然够用。

展开二：让模型可执行，再给它内存

在图上论证了模型之后，这一章让它跑起来。模拟器用 pc、flag、一个 execute 循环和消息传递分派，完成了机器模型；然后是汇编器，它把控制器文本扫描一遍，把标号同指令分开，并给每条指令挂上一个执行过程，在汇编时而不是运行时解析寄存器查找和标号引用。（这种一次性分析的想法，悄悄是两节之后编译器的种子。）从模拟器的调试练习，本章转向存储：表结构被表示成指向 the-cars 和 the-cdrs 向量的带类型指针，基本的表操作成了向量操作，而停止-复制垃圾收集——写成寄存器机器代码，从 begin-garbage-collection 经 gc-loop、update-car/update-cdr、relocate-old-result-in-new，一直到 gc-flip——维持着内存无限的幻觉。收集器的逻辑值得精确说明，因为很容易误读：判据不是程序还“需要”什么，而是从机器寄存器出发还“可达”什么。不可达的对象再也不会被碰到，所以回收它们是安全的；可达的对象即使程序永远不会再看它们，也会被保留。当扫描指针遇上空闲指针时，收集结束，这意味着没有发现新东西，每个活对象都已被搬走。

显式控制求值器：让控制可见

有了机器、模拟器和内存，本章建立显式控制求值器：七个寄存器、一个栈，以及对表达式类型做分情形分析的 eval-dispatch，其中应用靠保存寄存器并运行一个运算对象循环来处理。然后是对基本过程和复合过程的 apply，序列的求值，条件，赋值，定义，以及一个带栈监视的驱动循环。把控制用寄存器写出来，解决了先前模型留下未决的问题。运算对象的求值顺序，原来是从宿主语言继承来的；在这里，运算对象循环用 car 取第一个运算对象，用 cdr 取其余的，所以一个组合式必然是从左到右走过的。尾递归也同样成了你看得见的性质，而不是假定的：它成立，是因为求值器不在过程体的最后一个表达式周围保存寄存器。作者表明，加上这样的保存是致命的——栈的深度就会随迭代次数增长，一个只由过程调用构成的循环最终会耗尽栈。尾递归是这个求值器的成就，不是把调用写在最后一个位置上就白得的结果。

转折：从解释到编译

本章真正的枢纽，出现在它不再解释、开始翻译的时候。编译器发出原生的寄存器机器指令，用解释器的灵活性换效率。compile 按语法类型分派，一路带着一个 target 和一个 linkage，而指令序列由 append-instruction-sequences 和 preserving 粘在一起，本章最漂亮的机制就住在后者里：每个序列记录它需要的寄存器和它修改的寄存器，只有当第一个序列修改了第二个所需要的东西时，才在它周围包一对 save/restore——所以大多数调用根本不产生栈上的操作。本章随后编译赋值、定义、if、序列、lambda 和组合式；参数表在 argl 里从后往前建，应用按基本过程还是编译过的代码分派，而一个返回链接复用 continue，所以目标代码生来就是尾递归的。组合手段 preserving、tack-on 和 parallel 管理这些寄存器声明，一个阶乘编译的实例显示出由此得到的骨架，然后词法地址，把运行时的变量搜索，换成针对编译时环境算出的“框架加位移”的查找。加速的两个原因被分开：分析只做一次，以及编译器可以特化。解释器每过一遍都重新给 (f 84 96) 分类，重新检验运算对象表是否结束；更糟的是，它必须为任何延续做好准备，所以总是保存。编译器知道变量查找什么也不会扰乱，就发出一条对 proc 的赋值，省掉保存、恢复，和从 val 的移动。

收束：测量、混用，与可移植性

最后一节通过习题完成词法地址，然后借 apply-dispatch、external-entry 和 compile-and-go，把编译出的代码接回求值器机器，并以让自己的论点可以检验来收尾。被监视的栈报告：解释执行 (factorial 5) 是 144 次压栈、最大深度 28，对编译后的 31 次压栈、深度 14——这是这次特定模拟的数字，但毕竟是数字。随后的裁决故意是双面的：解释在交互式开发上保有真实的优势，因为程序运行时，源程序和全套基本操作仍然可用，这就是为什么真正的 Lisp 系统让编译的和解释的过程互相调用，让程序员编译调试好的部分，而把不稳定的部分留着解释。这种互操作不是运气——编译器被造成遵守求值器的寄存器约定（env、argl、proc、val、continue）。最后的脚注留意杂务（在启动 eceval 之前初始化 flag，让 user-print 不进入编译过程的内部，在检错的代价与速度之间权衡），然后以最宽的主张结束：把 Lisp 移植到新机器，缩成一个手工编码的小内核，加上编译器为它自己提供的操作，由编译器编译它自己，作为对其自身正确性的检验。

关键论点，以及支撑它们的原文

它是怎样运作的

本章论证所依靠的 3 个机制。

常见误读

第 5 章的核心概念

寄存器机器

一台一步一步运行指令的机器，每条指令移动或组合保存在一组固定的、有名字的存储单元里的值。

适用处： 只有常量和寄存器的内容可以直接被操作；每一步给一个寄存器赋值。

数据通路与控制器

数据通路是寄存器、操作和按钮；控制器是决定下一个该按哪个按钮的序列。

适用处： 第5章看重对控制器的理解，多于对数据通路的细节，尽管真正的机器设计两者都需要。

动作

像 print 这样的操作：有外部效果，却不往任何寄存器里返回值；由 perform 调用。

适用处： 与像 read 这样产生值的操作相区别。

子程序

一段共享的指令序列，靠分支进入，由 continue 寄存器记录返回的地方。

适用处： 只有被复用的寄存器的值在别处不再被需要时，共享才是合法的。

延续寄存器

一个保存控制器标号的寄存器，子程序应在那里继续它的调用者。

适用处： 只有嵌套调用保存并恢复它，才能在子程序之间共享。

递归用的栈

一个后进先出的、存放已保存寄存器值的存储，使一份机器副本可以服务每一个嵌套调用。

适用处： 任何物理的栈都是有限的，所以递归深度受到限制。

第 5 章划线与批注AI 陪读