第三章 模块化、对象与状态
导读
在前两章中，我们学习的程序都是无状态的——过程的输出完全由输入决定，相同的输入总是产生相同的输出。这种编程风格称为函数式编程（functional programming）或声明式编程（declarative programming）。然而，现实世界中的许多系统是有状态的：银行账户有余额，时钟显示当前时间，图形界面有状态。如何对这类有状态的系统进行建模？如何在程序中引入状态的概念？
第三章"模块化、对象与状态"是 SICP 的一个重要转折点。在这一章中，我们将引入赋值（assignment）的概念，学习如何使用 set! 修改变量的值，从而在程序中引入状态。我们将探讨赋值带来的深刻变化：从函数式编程转向命令式编程，从无状态的过程转向有状态的对象。我们还将学习如何使用环境模型来理解有状态程序的求值过程，以及如何通过消息传递实现对象。
本章的学习目标包括：
- 理解赋值和状态的概念
- 掌握环境模型及其在求值中的应用
- 学会使用赋值构建有状态的对象
- 理解流（stream）的概念和延迟求值技术
- 掌握迭代器的实现和使用
- 了解并发编程的基本问题
核心概念详解
3.1 赋值与局部状态
赋值是引入状态的基本手段。Scheme 使用 set! 特殊形式来修改变量的值：
(define balance 100)
(define (withdraw amount)
(if (>= balance amount)
(begin (set! balance (- balance amount))
balance)
"Insufficient funds"))set! 的语法为 (set! <name> <new-value>)，它将名称对应的变量修改为新值。begin 特殊形式用于将多个表达式组合成一个，按顺序求值，返回最后一个表达式的值。
引入赋值后，withdraw 过程的行为不再仅由参数决定，还依赖于 balance 的当前值。我们说 withdraw 具有局部状态（local state）。每次调用 withdraw 可能会产生不同的结果，即使参数相同。
赋值的影响：引入赋值后，我们失去了许多函数式编程的良好性质。例如，替换模型（substitution model）不再适用，因为同一个名称在不同时刻可能对应不同的值。我们需要更复杂的求值模型——环境模型。
3.2 赋值的代价
赋值带来了强大的表达能力，但也带来了复杂性：
引用透明性丧失：在纯函数式程序中，表达式可以用其值替换而不改变程序行为（引用透明性）。引入赋值后，这种性质不再成立。
时间顺序变得重要：在有状态的程序中，操作的执行顺序会影响结果。例如：
(define w1 (make-withdraw 100))
(define w2 (make-withdraw 100))
(w1 50) ; 返回 50
(w2 70) ; 返回 30
; 但如果 w1 和 w2 共享同一个 balance，结果会不同等价性变得复杂：在函数式编程中，两个过程如果对所有输入产生相同输出，则等价。在有状态程序中，等价性需要考虑状态的变化历史。
推理困难：有状态程序的行为依赖于执行历史，使得推理和验证变得更加困难。
3.3 环境模型
环境模型（environment model）是理解有状态程序求值过程的框架。它扩展了第一章的求值模型，引入了环境的概念。
环境结构：
- 环境是帧（frame）的序列
- 每帧是绑定（binding）的表格，将名称与值关联
- 每帧有一个指向外围环境（enclosing environment）的指针
- 全局环境是所有环境的基础
过程创建：
当使用 lambda 创建过程时，过程对象包含：
- 参数列表
- 过程体
- 指向创建环境的环境指针
过程应用：
将过程应用于参数时：
创建新帧，将参数绑定到对应的值
新帧的外围环境是过程的环境指针指向的环境
在新帧的环境中求值过程体
赋值操作：
set! 在环境中查找名称对应的绑定，修改该绑定的值。如果找不到绑定，报错。
(define (make-withdraw balance)
(lambda (amount)
(if (< balance amount)
"Insufficient funds"
(begin (set! balance (- balance amount))
balance))))当调用 (make-withdraw 100) 时：
创建新环境 E1，其中 balance 绑定到 100
在 E1 中求值 lambda 表达式，创建过程对象 W，其环境指针指向 E1
返回 W
当调用 (W 50) 时：
创建新环境 E2，其中 amount 绑定到 50，外围环境是 E1
在 E2 中求值过程体
set! 修改 E1 中 balance 的值为 50
返回 50
3.4 使用赋值构建对象
使用赋值和词法作用域，我们可以构建有状态的对象：
(define (make-account balance)
(define (withdraw amount)
(if (>= balance amount)
(begin (set! balance (- balance amount))
balance)
"Insufficient funds"))
(define (deposit amount)
(set! balance (+ balance amount))
balance)
(define (dispatch m)
(cond ((eq? m 'withdraw) withdraw)
((eq? m 'deposit) deposit)
(else (error "Unknown request -- MAKE-ACCOUNT" m))))
dispatch)make-account 返回一个消息传递过程 dispatch。通过向 dispatch 发送不同的消息，可以获取不同的操作：
(define acc (make-account 100))
((acc 'withdraw) 50) ; 返回 50
((acc 'deposit) 30) ; 返回 80这种风格称为消息传递风格（message-passing style），它是面向对象编程的基础。对象（acc）封装了状态（balance）和行为（withdraw、deposit），通过消息（'withdraw、'deposit）进行交互。
3.5 命令式编程的示例
引入赋值后，我们可以使用命令式风格重写许多过程。例如，计算阶乘：
; 函数式风格（递归）
(define (factorial n)
(if (= n 0) 1 (* n (factorial (- n 1)))))
; 命令式风格（迭代）
(define (factorial n)
(let ((product 1)
(counter 1))
(define (iter)
(if (> counter n)
product
(begin (set! product (* counter product))
(set! counter (+ counter 1))
(iter))))
(iter)))命令式风格使用显式的状态变量和赋值来描述计算过程。这种风格更接近于机器的执行方式，但通常不如函数式风格清晰。
3.6 流（Stream）
流（stream）是一种延迟计算的序列。与列表不同，流的元素在需要时才计算，这使得流可以表示无限序列。
流的实现：
(define (cons-stream a b) (cons a (delay b)))
(define (stream-car stream) (car stream))
(define (stream-cdr stream) (force (cdr stream)))
(define the-empty-stream '())
(define (stream-null? stream) (null? stream))delay 创建延迟对象（thunk），force 强制求值延迟对象。cons-stream 构造流时，第一个元素立即求值，第二个元素延迟求值。
流的优势：
模块化：流允许我们将程序分解为独立的模块，每个模块生成或转换流，模块之间通过流连接。
无限序列：流可以表示无限序列，只计算需要的部分。
(define (integers-starting-from n)
(cons-stream n (integers-starting-from (+ n 1))))
(define integers (integers-starting-from 1))
(define (divisible? x y) (= (remainder x y) 0))
(define no-sevens
(stream-filter (lambda (n) (not (divisible? n 7)))
integers))效率：流只在需要时计算元素，避免不必要的计算。
流的映射与过滤：
(define (stream-map proc stream)
(if (stream-null? stream)
the-empty-stream
(cons-stream (proc (stream-car stream))
(stream-map proc (stream-cdr stream)))))
(define (stream-filter pred stream)
(cond ((stream-null? stream) the-empty-stream)
((pred (stream-car stream))
(cons-stream (stream-car stream)
(stream-filter pred (stream-cdr stream))))
(else (stream-filter pred (stream-cdr stream)))))隐式流定义：
流可以通过隐式方式定义，即流的元素由流本身定义：
(define ones (cons-stream 1 ones))
(define (add-streams s1 s2)
(stream-map + s1 s2))
(define integers
(cons-stream 1 (add-streams ones integers)))
(define fibs
(cons-stream 0
(cons-stream 1
(add-streams (stream-cdr fibs)
fibs))))这种定义方式利用了延迟求值：在计算流的后续元素时，前面的元素已经计算完成。
3.7 流作为信号处理系统
流提供了一种强大的模块化手段，可以将程序组织为信号处理系统。每个模块接受输入流，产生输出流，模块之间通过流连接。
(define (scale-stream stream factor)
(stream-map (lambda (x) (* x factor)) stream))
(define (integral integrand initial-value dt)
(define int
(cons-stream initial-value
(add-streams (scale-stream integrand dt)
int)))
int)这种风格类似于电子工程中的信号处理：每个组件对信号进行变换，信号在组件之间流动。流使得我们可以用声明式的方式描述信号处理系统。
3.8 流与延迟求值的实现
delay 和 force 的实现可以使用 memoization（记忆化）技术，避免重复计算：
(define (memo-proc proc)
(let ((already-run? #f)
(result #f))
(lambda ()
(if (not already-run?)
(begin (set! result (proc))
(set! already-run? #t)
result)
result))))
(define (delay expr) (memo-proc (lambda () expr)))
(define (force delayed) (delayed))memo-proc 将一个过程包装为记忆化版本：第一次调用时计算结果并保存，后续调用直接返回保存的结果。这使得流的效率更高，因为每个元素只计算一次。
3.9 迭代器与流
流可以用来实现迭代器，以声明式方式处理序列数据：
; 生成斐波那契数列的前 n 项
(define (fib-stream n)
(define (fib-gen a b count)
(if (= count 0)
the-empty-stream
(cons-stream a (fib-gen b (+ a b) (- count 1)))))
(fib-gen 0 1 n))
; 使用流处理数据
(define (sum-stream stream)
(if (stream-null? stream)
0
(+ (stream-car stream)
(sum-stream (stream-cdr stream)))))3.10 赋值的深入理解
赋值不仅仅是改变变量的值。从环境模型的角度看，赋值是修改环境中的绑定。这种修改会影响所有使用该绑定的过程。
共享状态：
(define (make-simplifier)
(let ((table (make-table)))
(define (simplify exp)
(cond ((number? exp) exp)
((variable? exp) exp)
((sum? exp)
(make-sum (simplify (addend exp))
(simplify (augend exp))))
(else exp)))
(lambda (exp)
(let ((result (lookup table exp)))
(if result
result
(let ((new-result (simplify exp)))
(insert! table exp new-result)
new-result))))))这个简化器使用表格缓存已计算的结果，避免重复计算。表格是共享状态，通过词法作用域封装在返回的过程中。
重要知识点
1. 对象系统的三个要素
一个完整的对象系统包含三个要素：
- 状态封装：对象的状态对外部不可见，只能通过消息访问
- 消息传递：对象通过接受消息来执行操作
- 局部状态修改：对象的状态可以通过操作修改
Scheme 通过词法作用域和赋值实现了这三个要素，虽然不如专门的对象语言（如 Smalltalk、Java）语法简洁，但功能完整。
2. 环境模型的求值规则
环境模型的求值规则比替换模型复杂得多：
组合表达式求值：
求值组合表达式的子表达式
第一个子表达式的值是过程，其余是参数
创建新环境，将参数绑定到形式参数
在过程的环境中求值过程体
lambda 表达式求值：
创建过程对象，包含参数、过程体和环境指针
环境指针指向当前环境
define 和 set! 求值：
define 在当前环境的当前帧中创建新绑定
set! 在当前环境中查找绑定，修改绑定的值
3. 流的时间模型
流提供了一种处理时间的方式。在函数式编程中，时间是隐式的——所有值都是永恒的。在命令式编程中，时间是显式的——状态随时间变化。流介于两者之间：流可以表示随时间变化的序列，但每个元素一旦计算就是永恒的。
流的这种特性使得我们可以用声明式的方式处理时间序列数据，同时保持函数式编程的许多优点。
4. 记忆化与效率
记忆化（memoization）是一种重要的优化技术，通过缓存已计算的结果避免重复计算。在流的实现中，记忆化使得每个元素只计算一次，大大提高了效率。
记忆化也用于其他场景，如动态规划、编译器优化等。理解记忆化的原理和应用，对于编写高效程序非常重要。
5. 并发与状态
引入状态后，并发编程成为一个重要问题。多个线程同时修改共享状态可能导致不一致。例如：
; 银行账户的 withdraw 操作
(define (make-account balance)
(define (withdraw amount)
(if (>= balance amount)
(begin (set! balance (- balance amount))
balance)
"Insufficient funds")))如果两个线程同时调用 withdraw，可能出现竞态条件（race condition）：两个线程都检查余额足够，然后都执行扣款，导致余额为负。
解决这个问题需要引入同步机制，如互斥锁（mutex）、信号量（semaphore）等。SICP 在后续章节中详细讨论了并发控制。
常见误区
1. 过度使用赋值
引入赋值后，一些开发者倾向于使用赋值来实现所有功能。然而，赋值增加了程序的复杂性，使得推理和验证更加困难。应该尽量使用函数式风格，只在必要时使用赋值。
; 不推荐：使用赋值实现迭代
(define (sum n)
(let ((result 0))
(define (iter i)
(if (> i n)
result
(begin (set! result (+ result i))
(iter (+ i 1)))))
(iter 1)))
; 推荐：使用函数式风格
(define (sum n)
(define (iter i acc)
(if (> i n)
acc
(iter (+ i 1) (+ acc i))))
(iter 1 0))2. 混淆词法作用域和动态作用域
Scheme 使用词法作用域：过程的含义由其定义时的环境决定，而不是调用时的环境。一些其他语言（如早期的 Lisp）使用动态作用域：过程的含义由调用时的环境决定。
(define x 10)
(define (foo) x)
(define (bar)
(let ((x 20))
(foo)))
; 词法作用域：(bar) 返回 10
; 动态作用域：(bar) 返回 203. 对流的理解不够深入
流不仅仅是"延迟计算的列表"。流提供了一种全新的编程范式，允许我们处理无限序列、建立信号处理系统、实现声明式的数据处理。理解流的本质——延迟求值和记忆化——对于掌握流的应用非常重要。
4. 忽略环境模型的复杂性
环境模型比替换模型复杂得多，但它是理解有状态程序的基础。忽略环境模型可能导致对有状态程序行为的错误理解。特别是在涉及闭包、高阶过程和赋值时，环境模型是正确推理程序行为的关键工具。
5. 对并发问题的轻视
在单线程程序中，状态的变化是顺序的，容易推理。但在多线程环境中，状态的变化可能是并发的，需要仔细考虑同步问题。即使在不直接使用多线程的场景中，理解并发问题也有助于设计更好的状态管理方案。
实践应用
1. 随机数生成器
使用赋值可以构建有状态的随机数生成器：
(define rand
(let ((x random-init))
(lambda ()
(set! x (rand-update x))
x)))这个随机数生成器封装了状态（当前随机数），每次调用返回新的随机数。
2. 蒙特卡罗模拟
使用随机数生成器可以进行蒙特卡罗模拟。例如，估算 π 的值：
(define (estimate-pi trials)
(sqrt (/ 6 (monte-carlo trials cesaro-test))))
(define (cesaro-test)
(= (gcd (rand) (rand)) 1))
(define (monte-carlo trials experiment)
(define (iter trials-remaining trials-passed)
(cond ((= trials-remaining 0)
(/ trials-passed trials))
((experiment)
(iter (- trials-remaining 1)
(+ trials-passed 1)))
(else
(iter (- trials-remaining 1)
trials-passed))))
(iter trials 0))3. 流式 I/O
流可以用于处理 I/O 操作，将 I/O 表示为无限流：
(define (read-line-stream)
(let ((line (read-line)))
(if (eof-object? line)
the-empty-stream
(cons-stream line (read-line-stream)))))
(define (write-line-stream stream)
(if (stream-null? stream)
'done
(begin (display (stream-car stream))
(newline)
(write-line-stream (stream-cdr stream)))))4. 响应式编程
流的思想是现代响应式编程（reactive programming）的基础。在响应式编程中，数据被表示为随时间变化的流，程序通过组合和转换流来响应数据变化。
; 模拟响应式编程
(define (mouse-click-stream)
; 返回鼠标点击事件的流
...)
(define (double-click-stream)
(let ((clicks (mouse-click-stream)))
(stream-filter (lambda (pair)
(< (time-diff (car pair) (cadr pair))
500))
(stream-map list clicks (stream-cdr clicks)))))5. 惰性求值语言
流的延迟求值思想可以扩展到整个语言，构建惰性求值（lazy evaluation）语言。在惰性求值语言中，所有表达式都是延迟求值的，只在需要时才计算。Haskell 就是这样一种语言。
; 模拟惰性求值
(define (lazy-eval exp env)
(cond ((self-evaluating? exp) exp)
((variable? exp) (lookup-variable-value exp env))
((quoted? exp) (text-of-quotation exp))
((lambda? exp)
(make-procedure (lambda-parameters exp)
(lambda-body exp)
env))
((application? exp)
(let ((proc (lazy-eval (operator exp) env))
(args (delay (lazy-eval (operands exp) env))))
(apply proc args)))
(else (error "Unknown expression type -- LAZY-EVAL" exp))))本章小结
本章介绍了模块化、对象与状态的概念，是 SICP 从函数式编程转向命令式编程的关键章节。我们学习了：
赋值与局部状态：使用 set! 修改变量的值，引入状态的概念。赋值使得过程的行为依赖于执行历史。
赋值的代价：引入赋值后，失去了引用透明性、时间顺序变得重要、等价性变得复杂、推理困难。
环境模型：环境模型是理解有状态程序求值的框架。它引入了环境、帧、绑定的概念，解释了过程创建、应用和赋值的行为。
对象与消息传递：使用赋值和词法作用域构建有状态的对象，通过消息传递进行交互。这是面向对象编程的基础。
流与延迟求值：流是延迟计算的序列，可以表示无限序列，提供强大的模块化手段。delay 和 force 实现延迟求值，记忆化提高效率。
流作为信号处理系统：流允许我们将程序组织为信号处理系统，每个模块对流进行变换，模块之间通过流连接。
并发与状态：引入状态后，并发编程成为一个重要问题。多个线程同时修改共享状态需要同步机制。
本章的核心思想是：状态和赋值带来了强大的表达能力，但也增加了复杂性。在实际编程中，应该根据问题的性质选择合适的编程风格——函数式或命令式。流提供了一种折中方案，允许我们用声明式的方式处理有状态的数据。
在下一章中，我们将学习元语言抽象，即如何通过构建解释器来定义新的语言，实现更高层次的抽象。