《计算机程序的构造和解释》（SICP 第二版）
“计算机科学”不是一门科学，它的意义与计算机也没多大关系。计算机革命是我们思考方式和表达思想方式的革命。 —— 第一版前言
全书概览
SICP（Structure and Interpretation of Computer Programs）是 MIT 计算机科学入门课程的教材，自 1980 年起使用，被誉为”编程圣经”。它不是教某一门编程语言的语法，而是教你如何控制大型软件系统的智力复杂度。
核心思想：程序首先是写给人读的，只是顺便给机器执行。
三条控制复杂度的主线
全书围绕三种控制软件复杂度的核心技术展开：
- 建立抽象（Abstraction）—— 通过构造抽象屏障，在适当的时候隐藏细节
- 约定接口（Conventional Interfaces）—— 建立标准化的接口，用”混搭”的方式组合标准模块
- 元语言抽象（Metalinguistic Abstraction）—— 发明新的语言来描述设计，每种语言强调某些方面而弱化另一些方面
五章结构
| 章节 | 主题 | 核心问题 |
|---|---|---|
| 第1章 | 用过程构造抽象 | 如何用过程（函数）组织计算逻辑 |
| 第2章 | 用数据构造抽象 | 如何设计和组合数据结构 |
| 第3章 | 模块化、对象和状态 | 如何处理时间和状态变化 |
| 第4章 | 元语言抽象 | 如何设计新的编程语言 |
| 第5章 | 寄存器机器计算 | 如何在硬件层面实现语言 |
第1章：用过程构造抽象
1.1 编程的基本元素
- 表达式（Expressions）：最基本的计算单元
- 命名与环境（Naming and the Environment）：变量绑定是最基本的抽象手段
- 组合式求值（Evaluating Combinations）：操作符 + 操作数的求值规则
- 复合过程（Compound Procedures）：
define是最重要的抽象机制 - 过程应用的代换模型：用参数替换形参来理解过程调用
- 条件表达式与谓词
- 牛顿法求平方根：用过程描述迭代逼近的算法
- 过程作为黑盒抽象：过程的使用者不需要知道它如何实现
关键洞察：将过程的”是什么”（what）与”怎么做”（how）分离，是控制复杂度的第一步。
1.2 过程与它们所产生的计算过程
一个过程是计算过程局部演化的模式。它规定了过程的每一步如何建立在前一步之上。
核心概念：
- 线性递归 vs 线性迭代：同样的计算可以有完全不同的”形状”
- 递归过程：先展开后收缩，需要保存调用链（消耗空间 O(n)）
- 迭代过程：状态可用固定数量的变量描述（空间 O(1)）
- 注意：“递归过程”描述语法，“递归计算过程”描述演化形态
- 树形递归：如斐波那契数列，时间指数增长，空间线性增长
- 增长的阶（Orders of Growth）：用 Θ 记法描述资源消耗
- 求幂：快速幂算法（Θ(log n)）展示了算法设计的威力
- 最大公约数：欧几里得算法的精妙
- 素性检测：概率算法的思想（费马小定理）
要成为专家程序员，必须学会可视化各种过程产生的计算过程的形状。就像摄影新手需要学会预判曝光效果一样。
1.3 用高阶过程构造抽象
过程也是一等公民——可以作为参数传递、作为返回值返回、可以命名。
- 过程作为参数：如
sum抽象出求和模式，传入不同的 term 函数 - Lambda 构造过程：匿名函数，不必给每个过程都命名
- 过程作为通用方法：如牛顿法求根，是一种通用的计算模式
- 过程作为返回值：闭包（closure）——过程携带它的环境
高阶函数极大地增强了语言的表达能力。用 100 个函数操作 1 种数据结构，比用 10 个函数操作 10 种数据结构更好。（Alan Perlis）
第2章：用数据构造抽象
2.1 数据抽象导引
数据抽象的核心思想：将数据的使用方式与它的表示方式分离。
以有理数为例：
- 构造函数：
(make-rat n d) - 选择函数：
(numer x)、(denom x) - 所有操作（加减乘除）都通过这些抽象接口实现
抽象屏障（Abstraction Barriers）
使用有理数的程序
--------------------- ← 抽象屏障
有理数的运算操作（add-rat, mul-rat...）
--------------------- ← 抽象屏障
有理数的构造/选择函数（make-rat, numer, denom）
--------------------- ← 抽象屏障
具体的表示方式（序对）
每一层只通过它下面一层的接口访问数据。改变表示方式时，只需要修改一层。
数据到底是什么？
数据不仅仅是一组选择函数和构造函数，更重要的是——这些函数必须满足特定的约束条件。
例如，对于有理数
(make-rat n d)，必须满足numer(x)/denom(x) = n/d。
这是一个深刻的洞察：数据的意义由它的行为（约束条件）定义，而不是由它的表示定义。
2.2 层次性数据与闭包性质
闭包性质（Closure Property）：组合数据对象的结果本身也可以被组合。
- cons 的闭包性造就了 list 结构
- 序列作为标准接口：
map、filter、accumulate - 用序列操作组合数据处理管道
- 图画语言示例：用组合子构造复杂图形
序列操作是函数式编程的核心范式之一——将计算表达为对序列的变换，每一步都是纯函数，易于理解和组合。
2.3 符号数据
- 引号（quote）：引入符号计算
- 符号求导：展示如何用抽象数据结构表达数学公式变换
- 集合的表示：同一抽象可以有多种实现（未排序表、排序表、二叉树、散列）
- 霍夫曼编码树：综合案例
2.4 抽象数据的多重表示
同一个抽象数据可以有多种表示方式。如何让不同表示共存？
- 带标志数据（Tagged data）：在数据上加类型标签
- 数据导向编程（Data-Directed Programming）：用表格分派操作，可加性（additivity）——新增表示方式时不需要修改已有代码
2.5 带有通用操作的系统
- 通用算术运算：一套操作 + 多种数值类型（整数、有理数、实数、复数）
- 不同类型的组合：强制类型转换（coercion）
- 符号代数系统：综合案例
第3章：模块化、对象和状态
这一章是全书思想最深刻的部分之一——引入时间与状态。
3.1 赋值与局部状态
为什么需要赋值？ 当需要建模随时间变化的系统时，对象需要有”状态”。
set! 引入了赋值操作，打破了代换模型。
引入赋值的好处
- 可以封装状态，模拟现实世界中独立的对象
- 模块化更好：每个对象自己维护状态，不需要把所有状态传来传去
引入赋值的代价
一旦引入赋值，代换模型就失效了。同一表达式在不同时间求值可能得到不同结果。
- 引用透明性（referential transparency）丧失：相等的东西不能互相替换
- 无法再用”等于”来简单推理程序
- 并发编程变得极其困难
- 函数式编程的优美性质不再成立
这是一个根本性的权衡：为了模块化（封装状态），我们牺牲了推理的简单性。
3.2 求值的环境模型
赋值出现后，需要新的模型来理解程序如何运行——环境模型。
核心概念：
- 框架（Frame）：变量绑定的表格
- 环境（Environment）：框架的链（从当前框架一直到全局环境）
- 过程的值 = 代码 + 定义时的环境（即闭包）
- 过程应用 = 在新框架中绑定形参，然后在该环境中求值过程体
环境模型是理解 JavaScript、Python 等现代语言闭包机制的基础。
3.3 用可变数据建模
- 可变表结构
- 队列的表示
- 表格的表示（一维、二维）
- 数字电路模拟器：一个完整的事件驱动仿真系统
- 约束传播系统：声明式编程的例子
3.4 并发：时间是本质问题
在并发系统中，时间的本质变得复杂。多个独立进程同时操作共享状态，事件的顺序不确定。
核心问题：多个进程共享状态时，如何保证正确性？
并发控制机制：
- 串行化（Serialization）：互斥访问共享资源
- 互斥元（Mutex）：实现串行化的基本原语
- 死锁问题：多个进程互相等待对方释放资源
这一章揭示了一个深刻的真相：状态和时间是绑定在一起的。 没有时间，就没有状态变化；没有并发，时间就不那么重要。
3.5 流
流（Streams）是一种优雅的替代方案——用延迟求值来模拟状态，同时保留函数式编程的优美性质。
- 流是延迟的列表：
cons-stream的尾部在需要时才计算 - 无穷流：自然数流、素数流、斐波那契流
- 用流范式建模信号处理系统
- 流与延迟求值
- 函数式程序的模块化 vs 对象式程序的模块化
流提供了第三种可能性：既保留函数式的纯粹性（无赋值），又能模块化地描述随时间变化的系统。时间被重新表示为序列的索引。
第4章：元语言抽象
每一种语言的设计，都是为了强调某个特定的方面，而弱化另一些方面。
这一章是全书的高潮——自己动手写解释器。
4.1 元循环求值器
用 Scheme 本身写一个 Scheme 解释器。这就是”元循环”（metacircular）的含义。
求值器的核心只有两个部分：
- eval（求值）：对表达式进行分类，然后分派到对应的求值规则
- apply（应用）：将过程应用于参数
eval(expression, environment) → value
apply(procedure, arguments) → value
它们互相递归调用，形成了语言的核心循环。
这是计算机科学中最深刻的思想之一：语言的本质可以用它自己来描述。 写解释器是真正理解一门语言的最好方式。
4.2 变体——惰性求值
修改解释器，实现惰性求值（normal-order evaluation）：参数在真正需要时才计算。
- 传名调用 vs 传值调用
- 惰性流
- 副作用与惰性的张力
4.3 变体——非确定性计算
引入 amb 操作符（ambiguous），实现自动搜索的编程范式。
- 程序可以有多个可能的值，解释器自动回溯寻找满足条件的解
- 非确定性编程的例子：逻辑谜题、自然语言解析
- 实现 amb 求值器：需要维护回溯点
4.4 逻辑程序设计
实现一个类似 Prolog 的查询语言。
- 演绎信息检索：用规则和事实进行推理
- 查询系统的工作原理：模式匹配 + 合一（unification）
- 逻辑编程 = 数学逻辑吗？不完全是（封闭世界假设、否定问题）
- 实现查询系统
这一章展示了元语言抽象的威力：通过改变解释器，你可以创造全新的编程范式。 这也是 Lisp 被称为”可编程的编程语言”的原因。
第5章：寄存器机器计算
从软件到硬件，一步步下降到机器层面。
5.1 寄存器机器的设计
用一种寄存器机器语言描述计算过程。理解程序如何在机器上执行。
5.2 寄存器机器模拟器
用 Scheme 写一个寄存器机器的模拟器。
5.3 存储分配与垃圾收集
垃圾回收的本质：维护无限内存的幻觉。
- 内存作为向量
- 标记-清除算法（Mark-and-Sweep）
- 停止-复制算法（Stop-and-Copy）
5.4 显式控制求值器
用寄存器机器语言重新实现 Scheme 求值器。展示高级语言如何映射到机器指令。
5.5 编译
实现一个编译器，将 Scheme 程序编译为寄存器机器指令。
- 编译的结构
- 词法寻址（Lexical Addressing）：用”第几层框架 + 第几个变量”加速查找
- 编译代码与解释器的接口
从解释器到编译器，从高级语言到机器码，这一章完成了整个抽象栈的贯通。
全书核心思想提炼
1. 抽象是控制复杂度的根本手段
从过程抽象到数据抽象，从抽象屏障到元语言抽象——SICP 反复强调：
- 抽象 = 分离”是什么”与”怎么做”
- 好的抽象让使用者不需要关心实现细节
- 抽象屏障让系统的各部分可以独立演化
2. 编程语言是表达思想的媒介
程序首先是写给人读的，只是顺便给机器执行。
语言的设计深刻影响我们思考问题的方式。Lisp/Scheme 的极简语法让元编程变得自然。
3. 状态与时间是编程的根本难题
- 函数式编程（无状态）推理简单，但模块化不够
- 对象式编程（有状态）模块化好，但推理困难
- 流/惰性求值试图找到第三条道路
- 并发让时间问题暴露无遗
4. 元语言抽象是最强的控制复杂度手段
当问题变得足够复杂时，最好的方法不是在现有语言里写更多代码，而是设计一门新的语言来描述这个领域。
5. “计算机科学”与计算机关系不大
计算机革命是我们思考方式和表达思想方式的革命。 数学提供了处理”是什么”的精确框架，计算提供了处理”怎么做”的精确框架。
SICP 教的不是编程技巧，而是程序性认识论（procedural epistemology）——从命令式的角度研究知识的结构。
名言警句
- “Lisp 程序员知道一切东西的价值，却对一切东西的代价一无所知。” —— Alan Perlis
- “语法糖导致分号癌。” —— Alan Perlis
- “软件不像任何其他东西，它注定要被抛弃——关键是永远把它看作一个肥皂泡。” —— Alan Perlis
- “计算机就像小提琴。新手说它声音难听。确实难听，但等你学会了用它……” —— Marvin Minsky
- “用 100 个函数操作 1 种数据结构，比用 10 个函数操作 10 种数据结构更好。” —— Alan Perlis
- “Pascal 是用来建造金字塔的——宏伟、壮丽、静态；Lisp 是用来建造有机体的——宏伟、壮丽、动态。” —— Alan Perlis
与其他知识的关联
- 《程序员修炼之道》—— 同样强调编程的”道”而非”术”
- 《代码大全》—— 另一部软件构造经典，更偏工程实践
- 《设计模式》—— SICP 的高阶函数和流就是模式的函数式版本
- 《重构》—— SICP 中的抽象屏障思想是重构的理论基础
- 函数式编程 —— SICP 用 Scheme 展示了函数式的核心思想
- Lisp 语言 —— 理解 Lisp 的宏系统和元编程能力
- 解释器与编译器 —— SICP 第4、5章是手写解释器/编译器的经典入门
阅读建议
- 第一遍：读前 3 章，做练习，理解核心思想
- 第二遍：读第 4 章，亲手实现元循环解释器——这会彻底改变你对编程的理解
- 第三遍：读第 5 章，贯通从高级语言到机器码的完整链条
- 最重要的事：一定要写代码。SICP 不是用来”读”的，是用来”做”的。
相关资源：MIT 6.001 课程录像、在线版 SICP、SICP 习题解答社区。