1 · 读书笔记：计算机程序的构造和解释

Structure and Interpretation of Computer Programs

https://book.douban.com/subject/1148282/

• 是什么（What）— 理论/原则，建立认知模型
• 为什么（Why）— 背后的动机、约束与权衡
• 怎么做（How）— 技巧 + 实践 + 边界（该做与不该做）

1.1 · 核心观点：

编程的本质不是操控计算机，而是管理复杂性。我们通过三种核心机制来驯服复杂性： 原语（primitive）、组合（combination）、抽象（abstraction）。 这三个机制贯穿全书——从过程抽象、数据抽象到元语言抽象，层层递进。

原语 → 组合成复合结构 → 抽象并命名 → 当作新的原语 → 继续组合 → 继续抽象 → …

1.1.1 · 1. 构造过程抽象（Building Abstractions with Procedures）#

把”怎么算”藏起来，只暴露名字 → square(x) 不关心内部是 x*x 还是查表

• What: 过程（Procedure）是对计算模式的抽象。高阶过程（Higher-order Procedure）以过程为参数或返回值，是更强大的抽象手段
• Why: 当我们发现多个计算共享相同模式时，用高阶过程提取公共模式，消除重复，提升表达力
• How:
  • 用**代换模型（Substitution Model）**理解过程调用：应用序 vs 正则序
  • 递归过程 vs 迭代过程：关键区别不在于语法（是否调用自身），而在于计算过程的形状——迭代过程的状态完全由固定数量的状态变量捕获
  • lambda 创建匿名过程，let 本质是 lambda 的语法糖
  • 高阶过程示例：map、filter、accumulate、fixed-point

1.1.2 · 2. 构造数据抽象（Building Abstractions with Data）#

把”怎么存”藏起来，只暴露操作接口 → 用”有理数”不关心内部是两个整数还是浮点数

• What: 数据抽象通过**选择器（selector）和构造器（constructor）**建立抽象屏障（Abstraction Barrier），将数据的使用与表示分离
• Why: 使程序模块化——修改数据表示不需要修改使用数据的代码。推迟决策，保持灵活性
• How:
  • cons/car/cdr 是最基本的数据粘合剂，可以用纯过程实现（消息传递）
  • 闭包性质（Closure Property）：组合的结果本身还能继续被组合（如 pair 的 pair），这是构建复杂数据的基础
  • 序列（Sequence）操作的约定接口（Conventional Interfaces）：map→filter→accumulate 管道，将程序组织为信号流
  • 符号数据使程序可以操纵任意符号表达式（引号 quote），为元编程铺路

1.1.3 · 3. 模块化、对象和状态（Modularity, Objects, and State）#

• What: 引入赋值（assignment）和可变状态后，对象拥有了”身份”和”历史”。代换模型失效，需要环境模型（Environment Model）
• Why: 现实世界的系统由有状态的对象组成，赋值让程序结构与被模拟系统的结构对应，提升模块化
• How:
  • 赋值的代价：失去引用透明性（Referential Transparency），同一表达式在不同时刻可能产生不同值
  • 环境模型：过程 = 代码 + 环境。define/set! 在环境帧中绑定/修改变量
  • **流（Stream）**作为替代方案：用延迟求值（delay/force）模拟无限序列，无需可变状态也能建模时变系统
  • 流 vs 赋值的权衡：流避免了状态副作用，但在需要多个独立时间线交互时会遇到困难

1.1.4 · 4. 元语言抽象（Metalinguistic Abstraction）#

• What: 通过构建**求值器（Evaluator/Interpreter）**来定义新语言。求值器本身就是一个程序，它决定了语言中表达式的含义
• Why: 当现有语言的表达能力不足以优雅地描述问题时，最强大的抽象手段是发明一门新语言
• How:
  • 元循环求值器（Metacircular Evaluator）：用 Scheme 实现 Scheme 的解释器，核心是 eval/apply 的相互递归
    • eval：根据表达式类型分派——自求值、变量查找、特殊形式、过程应用
    • apply：将过程应用于参数——基本过程直接调用，复合过程扩展环境后求值过程体
  • 惰性求值（Lazy Evaluation）：将 apply 中的参数求值推迟到实际需要时，实现正则序语言
  • 非确定性计算（Nondeterministic Computing）：amb 求值器，自动搜索满足约束的解
  • 启示：eval/apply 之间的循环是计算的本质——所有的解释器都遵循这个结构

1.1.5 · 5. 寄存器机器里的计算（Computing with Register Machines）#

• What: 从抽象下降到具体，展示高级语言的构造如何映射到寄存器机器的基本操作
• Why: 理解计算的物理实现基础，弥合”魔法”与”机制”之间的鸿沟
• How:
  • 寄存器机器模型：数据通路（data path）+ 控制器（controller）
  • 实现递归：用**栈（Stack）**保存和恢复寄存器，将递归过程翻译为迭代式的机器指令
  • 显式控制的求值器：将第 4 章的元循环求值器翻译为寄存器机器，揭示求值过程的具体机制
  • 编译（Compilation）：将高级表达式翻译为目标机器指令序列，比解释更高效

1.2 · 启发点（关键洞察）：

1. 抽象屏障是分层的设计纪律：每一层只通过上层提供的接口使用下层，这不是建议，而是原则。违反屏障的代码在短期内更方便，长期则让系统变得脆弱
2. “过程”和”数据”的界限是模糊的：过程可以作为数据传递和返回（高阶函数），数据可以用过程实现（消息传递式的 cons）。这个洞察直接通向面向对象和函数式的统一
3. 求值 = eval + apply 的无限循环：这是全书最深刻的思想之一。任何编程语言的解释器，无论多复杂，核心都是”分析表达式 → 应用操作”的循环
4. 赋值引入时间，时间引入复杂性：无赋值的纯函数程序没有时间概念，所有表达式可以任意替换。一旦引入 set!，程序就有了”之前”和”之后”，并发问题随之出现
5. 流是时间的函数式替代：用惰性的无限序列代替可变状态来建模随时间变化的量，将”变化”表达为”不同时刻的值的序列”而非”同一变量的反复修改”
6. 约定接口统一了程序的组织方式：enumerate → filter → map → accumulate 的管道模式，将计算分解为标准化的阶段。这个思想后来演化为 Unix 管道、MapReduce、Rx 流
7. 语言不是固定的工具，而是可塑造的材料：程序员不只是语言的使用者，更应该是语言的设计者。遇到问题时，不仅可以写程序解决，还可以创造一门领域特定语言（DSL）来优雅地描述解决方案

1.3 · 行动：

1. 练习用抽象屏障的思维审视日常代码：每个模块/包是否清晰地定义了对外接口？是否有跨层直接访问内部表示的情况？
2. 在设计 API 或库时，思考闭包性质：返回值是否可以继续参与组合？（如 Builder 模式、链式调用、Go 的 io.Reader 组合）
3. 区分递归过程和递归计算过程：Go 中没有尾调用优化，写递归时要意识到是否会爆栈，必要时手动改写为迭代
4. 谨慎使用可变状态：引入 mutation 前问自己——能否用值传递/函数组合替代？尤其在并发场景下
5. 尝试为重复出现的模式构建小型 DSL（哪怕只是一组约定良好的函数），而不是堆砌 if-else

1.4 · 金句：

1. “计算机科学并不是一门关于计算机的科学，正如天文学并不是一门关于望远镜的科学。“（Dijkstra，书中引用）
2. “程序是写给人看的，只是顺便让机器执行。“（Abelson & Sussman）
3. “我们用来控制复杂性的技术在本质上是相同的：组合、抽象、高阶。”
4. “一个强大的程序设计语言，不仅是指挥计算机的手段，更是表达有关方法学的思想的框架。”
5. “与其说 Lisp 有一种奇特的语法，不如说 Lisp 没有语法。“——这使得程序可以像数据一样被操纵（同像性 Homoiconicity）