第一章 构造程序抽象

导读

计算机科学是一门关于计算的学科，而计算本身是一个极其抽象的概念。当我们面对一个复杂问题时，如何将其分解为可管理的小部分？如何通过编程语言将我们的思想精确地表达出来？这正是本章要探讨的核心问题。

《计算机程序的构造和解释》（SICP）的第一章"构造程序抽象"是整本书的基石。在这一章中，我们将学习如何使用 Lisp/Scheme 语言的基本元素来构造程序，理解表达式的求值过程，掌握如何将简单的过程组合成更复杂的过程，以及如何通过高阶过程实现更高层次的抽象。

本章的学习目标包括：

• 理解程序设计语言的基本元素：基本过程、基本数据和组合手段
• 掌握表达式的求值模型（应用序与正则序）
• 学会使用条件表达式和谓词进行分支控制
• 理解过程定义与过程抽象的本质
• 区分递归过程与递归过程体、迭代过程与迭代过程体
• 掌握高阶过程的概念与应用
• 理解过程作为参数和返回值的重要性

核心概念详解

1.1 Lisp 的基本元素与表达式

Lisp（LISt Processing）是除 Fortran 之外最古老的高级编程语言之一，由 John McCarthy 于 1958 年发明。Scheme 是 Lisp 的一种方言，由 Gerald Jay Sussman 和 Guy Lewis Steele Jr. 于 1975 年设计。SICP 使用 Scheme 作为教学语言，原因在于其语法极其简洁，语义清晰，非常适合用来学习程序设计的本质。

在 Scheme 中，程序的基本构建块是表达式。表达式分为两类：原子表达式和组合表达式。

原子表达式是最简单的表达式，包括数字、符号和字符串。例如：

42           ; 数字
'hello       ; 符号
#t           ; 布尔值真

组合表达式（也称为复合表达式）是将一个或多个表达式用括号括起来形成的。组合表达式的第一个元素是操作符（或称运算符），后面的元素是操作数（或称运算对象）。例如：

(+ 1 2)      ; 加法，结果为 3
(* 3 4)      ; 乘法，结果为 12
(+ (* 3 4) (* 5 6))  ; 嵌套组合，结果为 54

这种将操作符放在操作数之前的表示法称为前缀表示法（prefix notation）。前缀表示法有两个显著优点：第一，它可以接受任意数量的操作数，例如 (+ 1 2 3 4 5) 可以直接计算五个数的和；第二，嵌套表达式没有歧义，不需要考虑运算符优先级的问题。

1.2 命名与环境

在程序设计中，我们经常需要将计算结果保存起来以便后续使用。Scheme 使用 define 特殊形式来实现命名：

(define pi 3.14159)
(define radius 10)
(define area (* pi (* radius radius)))

define 的语法为 (define <名称> <值>)，它将名称与值关联起来。在求值模型中，名称被存储在一个称为环境（environment）的结构中。环境可以看作是一个表格，其中每一行包含一个名称和与之对应的值。

全局环境是 Scheme 系统启动时建立的环境，其中包含了所有预定义的名称和值的关联。当我们使用 define 时，我们实际上是在全局环境中添加新的关联。

理解环境的重要性在于：当我们求值一个符号时，Scheme 会在环境中查找该符号对应的值。如果找不到，就会报错。这种查找机制是程序求值的基础。

1.3 组合过程的求值

当我们定义了一个过程（procedure）并调用它时，Scheme 解释器需要执行一系列步骤来求值这个组合表达式。对于一般的组合表达式，求值规则如下：

求值组合表达式中的各个子表达式

将最左边子表达式的值作为过程，其余子表达式的值作为参数，应用于该过程

对于复合过程（由 define 定义的过程），求值规则进一步细化为：

求值过程体中的各个表达式，使用由参数绑定到的值扩展后的环境

过程体的最后一个表达式的值就是过程调用的返回值

这个求值过程可以用一个树形结构来可视化。例如，对于表达式 (+ (* 3 4) (* 5 6))，我们可以画出如下的求值树：

(+ 12 30)
       /         \
   (* 3 4)    (* 5 6)

这种树形结构清晰地展示了表达式的求值顺序和依赖关系。树的叶子节点是原子表达式（数字或符号），内部节点是组合表达式。求值从叶子节点开始，逐步向根节点推进。

1.4 应用序与正则序

Scheme 采用应用序（applicative order）求值策略：在将操作符应用于操作数之前，先求值所有操作数。这与正则序（normal order）形成对比——正则序会先展开表达式，直到只剩下基本操作，然后再求值。

考虑以下例子：

(define (square x) (* x x))
(square (+ 2 3))

在应用序下，求值过程为：

先求值参数 (+ 2 3)，得到 5

将 5 绑定到 x

求值 (* 5 5)，得到 25

在正则序下，求值过程为：

展开为 (* (+ 2 3) (+ 2 3))

再求值，先计算两个 (+ 2 3)，各得 5

最后计算 (* 5 5)，得到 25

两种策略在这个例子中结果相同，但在某些情况下会有差异。例如，如果过程体中参数被使用多次，正则序可能导致重复计算；如果参数未被使用，正则序可以避免不必要的计算。Scheme 选择应用序主要是出于效率考虑。

1.5 条件表达式与谓词

程序经常需要根据不同条件执行不同操作。Scheme 提供了 cond 特殊形式来实现多分支条件：

(define (abs x)
  (cond ((> x 0) x)
        ((= x 0) 0)
        ((< x 0) (- x))))

cond 的语法为一系列子句，每个子句包含一个谓词（测试条件）和一个 consequent（结果表达式）。求值时，从上到下依次检查每个谓词，当某个谓词的值为真时，就求值对应的 consequent，其值就是整个 cond 表达式的值。

除了 cond，Scheme 还提供了 if 特殊形式用于简单的二选一情况：

(define (abs x)
  (if (< x 0)
      (- x)
      x))

if 的语法为 (if <predicate> <consequent> <alternative>)。如果谓词为真，求值 consequent；否则求值 alternative。

谓词（predicate）是返回布尔值的过程。Scheme 中的标准谓词包括：

• =：数值相等
• <、>：数值比较
• <=、>=：数值比较（含等于）
• even?、odd?：奇偶判断
• zero?：是否为零
• not：逻辑非

逻辑组合通过 and、or、not 实现：

(define (>= x y)
  (or (> x y) (= x y)))

(define (>= x y)
  (not (< x y)))

and 和 or 是特殊形式，因为它们具有短路求值的特性：and 在遇到第一个假值时立即返回假，or 在遇到第一个真值时立即返回该值。

1.6 过程定义与过程抽象

过程定义是程序设计中最重要的抽象手段之一。通过 define 和参数列表，我们可以将一段计算逻辑封装成一个命名的过程：

(define (square x) (* x x))

(define (sum-of-squares x y)
  (+ (square x) (square y)))

(define (f a)
  (sum-of-squares (+ a 1) (* a 2)))

过程定义使得我们可以将一个复杂的计算分解为多个步骤，每个步骤用一个过程来表示。这种分解方式就是过程抽象（procedural abstraction）。

过程抽象的关键在于：过程的使用者（调用者）只需要知道过程的输入（参数）和输出（返回值），而不需要知道过程内部是如何实现的。这种"黑盒"抽象使得我们可以管理大型程序的复杂性。

过程抽象还引出了过程接口（procedure interface）的概念。过程的接口包括过程的名称、参数的数量和类型、以及过程的返回值。良好的过程抽象应该具有清晰的接口，使得使用者可以方便地调用过程，而不需要了解其内部实现细节。

1.7 递归与迭代

递归和迭代是程序设计中两种基本的控制结构，它们都可以用来描述重复执行的计算过程。

递归过程（recursive process）是指在过程的定义中调用了该过程本身。递归过程遵循"展开-收缩"的模式：

(define (factorial n)
  (if (= n 1)
      1
      (* n (factorial (- n 1)))))

计算 (factorial 4) 的过程为：

(* 4 (factorial 3))
(* 4 (* 3 (factorial 2)))
(* 4 (* 3 (* 2 (factorial 1))))
(* 4 (* 3 (* 2 1)))
(* 4 (* 3 2))
(* 4 6)
24

这个过程形成了一个链式的延迟操作，解释器必须记住后续要执行的操作。这种计算过程称为线性递归（linear recursion），其空间复杂度与递归深度成正比。

迭代过程（iterative process）使用循环的方式重复执行，不需要保存延迟操作：

(define (factorial n)
  (fact-iter 1 1 n))

(define (fact-iter product counter max-count)
  (if (> counter max-count)
      product
      (fact-iter (* counter product)
                 (+ counter 1)
                 max-count)))

计算 (factorial 4) 的过程为：

(fact-iter 1 1 4)
(fact-iter 1 2 4)
(fact-iter 2 3 4)
(fact-iter 6 4 4)
(fact-iter 24 5 4)
24

迭代过程的计算状态可以用有限个状态变量完全描述。在上面的例子中，状态变量是 product、counter 和 max-count。

重要区分：递归过程（recursive procedure）指的是过程的定义形式（过程中调用了自身），而递归计算过程（recursive process）指的是计算过程的演化形式（需要保存延迟操作）。类似地，迭代过程和迭代计算过程也有这样的区分。一个递归过程可以产生迭代计算过程，这就是尾递归（tail recursion）的概念。

在大多数命令式语言（如 C、Java）中，递归调用会消耗栈空间，因此迭代过程通常用循环语句实现。但在 Scheme 中，解释器实现了尾递归优化（tail recursion optimization），使得递归过程产生的迭代计算过程不会消耗额外的栈空间。因此，在 Scheme 中，迭代必须通过递归调用来表达，这是 Scheme 语言设计的特色之一。

1.8 树形递归

树形递归是指过程中有多次递归调用的情况。经典的例子是斐波那契数列和汉诺塔问题。

(define (fib n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (fib (- n 1))
                 (fib (- n 2))))))

这个递归过程会产生一棵指数级大小的调用树，导致大量的重复计算。其时间复杂度为 O(2^n)，空间复杂度为 O(n)。

可以通过迭代方式重写斐波那契计算，将时间复杂度降为 O(n)：

(define (fib n)
  (fib-iter 0 1 n))

(define (fib-iter a b count)
  (if (= count 0)
      a
      (fib-iter b (+ a b) (- count 1))))

1.9 高阶过程

高阶过程（higher-order procedure）是指以过程作为参数或返回值的过程。高阶过程是更强有力的抽象手段，它允许我们在过程级别上进行抽象。

过程作为参数：

(define (sum term a next b)
  (if (> a b)
      0
      (+ (term a)
         (sum term (next a) next b))))

这个 sum 过程接受四个参数：一个过程 term、两个边界值 a 和 b、以及一个过程 next。它可以用来表示各种求和运算：

(define (sum-integers a b)
  (sum (lambda (x) x) a (lambda (x) (+ x 1)) b))

(define (sum-cubes a b)
  (sum (lambda (x) (* x x x)) a (lambda (x) (+ x 1)) b))

(define (sum-pi a b)
  (define (pi-term x)
    (/ 1.0 (* x (+ x 2))))
  (define (pi-next x)
    (+ x 4))
  (* 8 (sum pi-term a pi-next b)))

lambda 表达式用于创建匿名过程。(lambda (<parameters>) <body>) 创建一个过程，其参数由 <parameters> 指定，过程体由 <body> 指定。

过程作为返回值：

(define (make-adder x)
  (lambda (y) (+ x y)))

(define add5 (make-adder 5))
(add5 3)  ; 结果为 8

make-adder 返回一个过程，该过程将参数 y 加上 x。这里 x 被"捕获"在返回的过程中，形成闭包（closure）。

1.10 过程作为一般性抽象

高阶过程不仅可以用于数值计算，还可以用于表示一般的计算方法。例如，数值积分可以通过高阶过程来表示：

(define (integral f a b dx)
  (define (add-dx x) (+ x dx))
  (* (sum f (+ a (/ dx 2.0)) add-dx b)
     dx))

这里 f 是一个过程参数，代表被积函数。integral 过程可以接受任何函数作为被积函数，实现了高度的抽象。

另一个重要的例子是函数的复合：

(define (compose f g)
  (lambda (x) (f (g x))))

(define (repeated f n)
  (if (= n 1)
      f
      (compose f (repeated f (- n 1)))))

compose 将两个函数组合成一个新函数，repeated 将函数重复应用 n 次。这些都是高阶过程的典型应用。

重要知识点

1. 抽象屏障（Abstraction Barriers）

抽象屏障是管理复杂性的核心机制。在程序设计中，我们通过将系统分层，每层只向上一层提供必要的接口，来降低系统的复杂性。

例如，在实现有理数运算时，我们可以设置以下抽象层次：

• 第一层：使用有理数的程序（使用 add-rat、sub-rat 等）
• 第二层：有理数的抽象表示（使用 make-rat、numer、denom）
• 第三层：有理数的具体表示（使用 cons、car、cdr）
• 第四层：Lisp 的复合数据结构（cons 的实现）

每一层都依赖于下一层提供的抽象，同时为上一层提供服务。抽象屏障使得我们可以独立修改每一层的实现，而不影响其他层。

2. 作用域与词法作用域

变量的作用域是指变量在程序中可见的区域。Scheme 使用词法作用域（lexical scoping）规则：一个名称的作用域是其定义所在的表达式的主体部分。

(define (sqrt x)
  (define (good-enough? guess)
    (< (abs (- (square guess) x)) 0.001))
  (define (improve guess)
    (average guess (/ x guess)))
  (define (sqrt-iter guess)
    (if (good-enough? guess)
        guess
        (sqrt-iter (improve guess))))
  (sqrt-iter 1.0))

在这个例子中，good-enough?、improve 和 sqrt-iter 都定义在 sqrt 的内部，它们可以访问 sqrt 的参数 x。这种机制称为词法作用域，它是块结构（block structure）的基础。

词法作用域的一个重要推论是闭包（closure）性质：一个过程可以"记住"其定义时的环境，即使在该环境已经不存在的情况下仍然可以访问那些变量。

3. 不动点与平均阻尼

不动点（fixed point）是函数的重要概念。如果 f(x) = x，则 x 是 f 的不动点。许多数学问题可以转化为求函数不动点的问题。

(define tolerance 0.00001)

(define (fixed-point f first-guess)
  (define (close-enough? v1 v2)
    (< (abs (- v1 v2)) tolerance))
  (define (try guess)
    (let ((next (f guess)))
      (if (close-enough? guess next)
          next
          (try next))))
  (try first-guess))

利用不动点，我们可以计算平方根：

(define (sqrt x)
  (fixed-point (lambda (y) (/ x y)) 1.0))

但这个计算可能不收敛。通过平均阻尼（average damping）技术可以改善收敛性：

(define (average-damp f)
  (lambda (x) (average x (f x))))

(define (sqrt x)
  (fixed-point (average-damp (lambda (y) (/ x y))) 1.0))

4. let 表达式

let 特殊形式用于在局部作用域中绑定变量：

(let ((x 3)
      (y 4))
  (+ (* x x) (* y y)))

let 实际上是 lambda 表达式的语法糖：

((lambda (x y) (+ (* x x) (* y y))) 3 4)

let 使得代码更加清晰，特别是当需要在局部绑定多个变量时。需要注意的是，let 中的绑定是并行的，各个右端表达式在包含 let 的环境中求值，而不是在 let 创建的新环境中求值。

常见误区

1. 混淆递归过程与递归计算过程

这是初学者最容易犯的错误之一。一个过程在语法上是递归的（过程中调用了自身），并不意味着计算过程也是递归的。如果递归调用是尾调用（tail call），即调用结果直接返回，不做额外操作，那么计算过程是迭代的。

; 递归过程，递归计算
(define (fact n)
  (if (= n 0) 1 (* n (fact (- n 1)))))

; 递归过程，迭代计算（尾递归）
(define (fact n) (fact-iter n 1))
(define (fact-iter n product)
  (if (= n 0) product (fact-iter (- n 1) (* n product))))

2. 忽略尾递归优化的重要性

在 Scheme 中，尾递归是保证迭代计算的标准方式。如果不用尾递归，可能导致栈溢出。理解尾递归的本质是理解 Scheme 程序执行模型的关键。

3. 滥用全局变量

使用全局变量会破坏过程抽象的封装性，使得过程的行为依赖于外部环境，难以测试和复用。应该尽量使用参数传递数据，而不是依赖全局变量。

4. 混淆 let 和 letrec

let 中的绑定不能引用同一 let 中定义的其他变量，而 letrec 可以。如果需要定义互相递归的局部过程，必须使用 letrec。

; 错误：let 中的绑定不能互相引用
(let ((x 1)
      (y (+ x 1)))  ; 错误！x 在这里未定义
  (+ x y))

; 正确：使用 letrec
(letrec ((even?
          (lambda (n)
            (if (= n 0) #t (odd? (- n 1)))))
         (odd?
          (lambda (n)
            (if (= n 0) #f (even? (- n 1))))))
  (even? 10))

5. 对高阶过程的理解不够深入

高阶过程不仅仅是"接受函数作为参数"的简单概念。它代表了一种在过程级别上进行抽象的能力，是函数式编程的核心特征之一。理解高阶过程需要理解函数作为一等公民（first-class citizen）的概念。

实践应用

1. 数值方法

本章介绍的技术可以直接应用于数值计算。例如，使用牛顿法求平方根：

(define (sqrt x)
  (fixed-point 
   (lambda (y) (average y (/ x y)))
   1.0))

或者使用半区间法求方程的根：

(define (search f neg-point pos-point)
  (let ((midpoint (average neg-point pos-point)))
    (if (close-enough? neg-point pos-point)
        midpoint
        (let ((test-value (f midpoint)))
          (cond ((positive? test-value)
                 (search f neg-point midpoint))
                ((negative? test-value)
                 (search f midpoint pos-point))
                (else midpoint))))))

2. 函数逼近

高阶过程可以用于实现函数逼近。例如，通过有限差分近似导数：

(define (deriv g)
  (lambda (x)
    (/ (- (g (+ x dx)) (g x))
       dx)))

这里 deriv 接受一个函数 g，返回其导数函数。这是符号微分的基础。

3. 通用迭代器

高阶过程可以实现通用的迭代器，用于处理各种序列和集合：

(define (accumulate combiner null-value term a next b)
  (if (> a b)
      null-value
      (combiner (term a)
                (accumulate combiner null-value term (next a) next b))))

(define (filter predicate sequence)
  (cond ((null? sequence) nil)
        ((predicate (car sequence))
         (cons (car sequence)
               (filter predicate (cdr sequence))))
        (else (filter predicate (cdr sequence)))))

这些通用过程可以组合使用，实现复杂的数据处理任务。

4. 连续分数

连续分数是数学中的一个重要概念，可以用递归来计算：

(define (cont-frac n d k)
  (define (iter i result)
    (if (= i 0)
        result
        (iter (- i 1) (/ (n i) (+ (d i) result)))))
  (iter (- k 1) (/ (n k) (d k))))

通过连续分数可以计算黄金比例、自然对数的底 e 等数学常数。

本章小结

本章介绍了程序抽象的基本概念和技术。我们学习了：

表达式与求值：Scheme 的基本语法、前缀表示法、表达式的求值规则。理解了应用序和正则序的区别。

命名与环境：使用 define 进行命名，环境作为名称与值的关联表。

过程定义：使用 define 定义复合过程，实现过程抽象。

条件表达式：使用 cond 和 if 进行分支控制，使用谓词进行测试。

递归与迭代：区分递归过程和递归计算过程、迭代过程和迭代计算过程。理解尾递归的重要性。

高阶过程：过程作为参数和返回值，lambda 表达式，闭包的概念。

抽象屏障：通过分层抽象管理复杂性，词法作用域和块结构。

这些概念构成了程序设计的基础，将在后续章节中不断被扩展和深化。掌握这些基本概念，对于理解更高级的程序设计技术至关重要。

程序设计的本质是抽象。通过将复杂的计算分解为简单的过程，再将简单的过程组合成复杂的过程，我们可以构建出功能强大而又结构清晰的程序。本章介绍的递归、迭代、高阶过程等技术，是实现这种抽象的基本工具。

在下一章中，我们将学习如何构造数据抽象，即如何将数据组合成更复杂的结构，以及如何通过抽象屏障管理数据表示的复杂性。