SICP 第 3 讲（备选版本）：高阶过程

视频元信息

• 所属课程：MIT 6.001 Structure and Interpretation of Computer Programs（SICP）1986 年原版
• 本讲主题：高阶过程（Higher-Order Procedures）
• 授课教师：Hal Abelson（视频中未明确点名，但为 1986 版主讲之一）
• 视频时长：约 25 分钟（根据字幕内容推算）

内容摘要（TL;DR）

本讲从"求和"这一简单程序出发，揭示递归程序的通用模式，进而引入高阶过程的概念——过程可以作为参数传递、作为返回值返回。通过 sum、fixed-point、average-damp、newton-method 等例子，展示如何用高阶过程做抽象，将"做什么"与"怎么做"分离，最终引出"过程作为一等公民"的思想。

一、从简单求和程序出发：发现重复 [00:25]

1.1 几个几乎相同的程序

教师首先在黑板上写下几个程序，它们看起来不同，但结构几乎一致：

程序 1：整数求和

计算从 a 到 b 的整数之和（即 Σᵢ₌ₐᵇ i）：

(define (sum-int a b)
  (if (> a b)
      0
      (+ a (sum-int (+ a 1) b))))

递归思想要点：

• 基础情况（base case）：如果 a > b，没有东西可加，答案为 0
• 递归情况：把问题归约为更小的问题——"从 a+1 到 b 的整数和"，然后再加上 a

易错点：递归思维的关键是——先写已知答案的简单情况，再把问题归约为更简单的问题，最后对子问题的结果做处理。这是本课程反复强调的递归模式。

程序 2：平方和

计算从 a 到 b 的平方之和（即 Σᵢ₌ₐᵇ i²）：

(define (sum-sq a b)
  (if (> a b)
      0
      (+ (square a) (sum-sq (+ a 1) b))))

程序 3：π/8 的级数求和

计算 1/(1×3) + 1/(5×7) + 1/(9×11) + ... 这个级数，其值趋近于 π/8：

(define (pi-sum a b)
  (if (> a b)
      0
      (+ (/ 1 (* a (+ a 2)))
         (pi-sum (+ a 4) b))))

1.2 发现共性

对比这三个程序，它们的差异只有：

其余部分——判断终止条件、返回 0、递归调用、累加——完全一样。

考点：DRY 原则（Don't Repeat Yourself）——"每当你看到自己把同样的东西写了不止一遍，就一定有问题。"重复不仅是浪费时间，更意味着有一个抽象概念没有被提取出来。这里的抽象概念就是求和（sigma notation）本身。

理解：这背后的哲学是——"求和"这个动作，与"求什么的和"无关。我们希望能独立地理解和调试"求和方式"，然后把它复用到各种不同的求和场景中。

二、引入高阶过程：sum 的抽象 [08:53]

2.1 通用求和模式

观察上面的通用模式，可以抽象出：

(define (<?> a b)
  (if (> a b)
      0
      (+ (<term> a)
         (<?> (<next> a) b))))

其中 <term> 和 <next> 是随场景变化的部分。在 Scheme 中，过程可以作为参数传递，所以我们可以把 <term> 和 <next> 直接作为参数传给一个通用的 sum 过程。

2.2 sum 过程的定义

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

参数说明：

• term：一个过程，给定索引，返回该项的值
• a：下界（当前索引）
• next：一个过程，给定当前索引，返回下一个索引
• b：上界

重点：过程作为参数——term 和 next 不是数字，而是过程。这是高阶过程的核心特征。sum 接收过程作为参数，因此它是一个高阶过程。

2.3 用 sum 重写三个程序

整数求和：

(define (identity x) x)

(define (sum-int a b)
  (sum identity a (lambda (x) (+ x 1)) b))

平方和：

(define (sum-sq a b)
  (sum square a (lambda (x) (+ x 1)) b))

π/8 求和：

(define (pi-sum a b)
  (sum (lambda (x) (/ 1 (* x (+ x 2))))
       a
       (lambda (x) (+ x 4))
       b))

2.4 lambda 匿名过程

上面用到了 lambda 来定义匿名过程。例如 (lambda (x) (+ x 1)) 表示"一个接收 x、返回 x+1 的过程"。

考点：lambda 语法——(lambda (参数) 体) 产生一个匿名过程。当某个过程只用一次、不值得命名时，用 lambda 直接写出来更方便。

思考：lambda 的引入让"过程"不再必须绑定到一个名字上，这为后面"过程作为返回值"铺平了道路。

2.5 学生提问：过程与变量的关系

有学生问：sum-sq 是变量吗？教师解释：

• 过程并不特殊。sum-sq 是一个变量，它的值是一个过程。
• 过程可以被命名，因此可以被传递、被返回。
• 当把 term 作为参数传给 sum 时，term 在递归调用中一直被传递下去。
• 当写 (next a) 时，括号表示应用过程 next 到 a，得到下一个索引。

易错点：区分"过程本身"和"应用过程的结果"——next 是过程，(next a) 是应用 next 到 a 的结果。递归调用中传递的是过程 next 本身，而不是 (next a)。

三、抽象的价值：分解与独立演化 [18:31]

3.1 递归实现 vs 迭代实现

教师指出，sum 可以有不同的实现方式。例如，一个迭代版本的 sum：

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

迭代版本可能比递归版本更高效（不消耗栈空间）。

3.2 抽象带来的好处

重点：抽象的核心价值——如果不用 sum 抽象，而是直接写三个程序，那么当想改变"加法方式"（比如从递归改成迭代）时，必须修改每一处。而用了 sum 抽象后，加法方式被封装在 sum 内部，只需修改一处，其他程序不受影响。

理解：这就是"关注点分离"（separation of concerns）——把"求和方式"和"求什么的和"分开，各自独立演化。

3.3 关于格式的提醒

教师强调缩进（pretty printing） 的重要性：对齐过程的参数，让程序可读。这是自动化的习惯，学生也应该学会。

易错点：代码可读性——程序的书写格式直接影响可读性。缩进对齐参数是 Scheme 社区的基本规范。

四、更复杂的例子：不动点与平方根 [21:13]

4.1 Heron 方法求平方根

教师回顾上一讲（第 23 讲）中 Heron 方法（即牛顿法求平方根）的程序，指出它虽然能工作，但不清晰——看不出"在做什么"。

4.2 数学洞察：不动点

Heron 方法的核心是不动点（fixed point） 概念：

• 如果 y 是 x 的平方根的猜测值，那么改进公式为：f(y) = (y + x/y) / 2
• 关键性质：f(√x) = √x——即 √x 是函数 f 的不动点
• 不动点：f(y) = y 的点

理解：把 y = √x 代入 f(y) = (y + x/y)/2，得到 (√x + x/√x)/2 = (√x + √x)/2 = √x。所以 √x 是不动点。

4.3 计算器类比

教师用 HP 35 计算器做类比：在弧度模式下反复按 cos 键，值会越来越接近 0.739...（cos 的不动点）。这说明有些函数可以通过反复迭代找到不动点。

4.4 用 wishful thinking 写程序

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

重点：wishful thinking（愿望式编程）——先假设 fixed-point 已经存在，写出高层逻辑，再实现底层细节。这是 SICP 反复强调的编程方法。

4.5 实现 fixed-point

(define (fixed-point f start)
  (define tolerance 0.00001)
  (define (close-enough? u v)
    (< (abs (- u v)) tolerance))
  (define (iter old new)
    (if (close-enough? old new)
        new
        (iter new (f new))))
  (iter start (f start)))

要点：

• 内部定义 iter 作为循环
• 每次比较 old 和 new 是否足够接近
• 如果足够接近，返回 new
• 否则，用 new 作为新的 old，用 (f new) 作为新的 new

易错点：终止条件——不动点迭代的终止条件是"新旧值足够接近"，而不是"完全相等"。因为浮点数无法精确比较，且迭代可能永远无法精确到达不动点。

五、平均阻尼：加速收敛 [28:00]

5.1 为什么需要平均阻尼

如果直接用 g(y) = x/y 求不动点：

• 假设 x = 2，从 y = 1 开始
• g(1) = 2，g(2) = 1，g(1) = 2，g(2) = 1...
• 振荡，永远不收敛

考点：振荡问题——某些函数的不动点迭代会振荡。平均阻尼是一种阻尼振荡的经典方法。

5.2 平均阻尼的定义

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

解释：

• average-damp 接收一个过程 f
• 返回一个新过程：接收 x，返回 x 和 f(x) 的平均值
• 这个新过程比原过程更"稳定"

5.3 用平均阻尼重写 sqrt

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

重点：过程作为返回值——average-damp 是一个返回过程的过程。这是高阶过程的另一个核心特征，与"过程作为参数"并列。

理解：(average-damp (lambda (y) (/ x y))) 返回一个过程，这个过程接收 y，返回 (y + x/y)/2——正好是 Heron 方法的改进公式。

5.4 学生提问：lambda 的嵌套

有学生问：为什么 average-damp 里用了两次 lambda？能不能写成 (lambda (f x) ...)？

教师解释：

• (lambda (f x) ...) 会创建一个接收两个参数的过程，返回一个数值
• 而 average-damp 需要的是：接收一个过程 f，返回一个过程
• 这两者类型不同

易错点：返回过程 vs 返回数值——(lambda (f x) (average x (f x))) 返回数值；(lambda (f) (lambda (x) (average x (f x)))) 返回过程。前者不能用于 fixed-point，因为 fixed-point 需要一个过程作为参数。

5.5 不用 lambda 的等价写法

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

这等价于 lambda 版本，但需要给内部过程起个名字。lambda 的好处是匿名，不需要起名字。

考点：lambda 的本质——lambda 是"匿名过程"的构造器。当过程只用一次、不值得命名时，用 lambda 更简洁。(define (foo x) ...) 本质上是 (define foo (lambda (x) ...)) 的语法糖。

六、牛顿法：更一般的求根方法 [31:00]

6.1 牛顿法数学原理

牛顿法用于求函数 f(y) = 0 的根：

y_{n+1} = y_n - f(y_n) / f'(y_n)

其中 f' 是 f 的导数。

6.2 用牛顿法求平方根

要求 √x，即求 y² = x，即 f(y) = y² - x = 0 的根。

(define (sqrt x)
  (newton-method (lambda (y) (- (square y) x))
                 1.0))

6.3 实现 newton-method

(define (newton-method f guess)
  (fixed-point
    (lambda (x) (- x (/ (f x) ((deriv f) x))))
    guess))

其中 deriv 是求导过程。

6.4 实现 deriv（数值求导）

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

其中 dx 是一个很小的数（如 0.00001）。

考点：数值求导的局限——数值求导会产生噪声，精度有限。教师提到"数值分析专家应该跳出来说'别这么做'"。但这里是为了理解概念，实际工程中可能需要符号求导或自动微分。

6.5 牛顿法的抽象结构

教师展示了一张幻灯片，描述牛顿法的"机器"结构：

• 输入：x（要求平方根的数）
• 构造过程：(lambda (y) (- (square y) x))
• 这个过程被送入 newton-method
• 其中一部分进入 deriv，产生导数的近似
• 最终产生一个迭代过程，送入 fixed-point
• 输出：√x

重点：抽象层次——从最底层的数值操作，到 deriv、newton-method、fixed-point，每一层都封装了特定的概念。这种分层抽象让复杂系统可以被理解。

七、过程作为一等公民 [37:00]

7.1 Christopher Strachey 与一等公民

教师引用 Christopher Strachey（计算机科学先驱、指称语义学发明者之一）的观点：过程应该是一等公民（first-class citizens）。

7.2 一等公民的权利

考点：一等公民的四个权利（这是 SICP 的核心概念之一）：

1. 可以被变量命名——(define f (lambda (x) ...))
2. 可以作为参数传递——(sum term a next b)
3. 可以作为返回值返回——(average-damp f)
4. 可以包含在数据结构中——（本讲尚未涉及，后续会讲）

7.3 一等公民的意义

重点：抽象的力量——把过程作为一等公民，使得我们可以构造强大的抽象，把一般方法（如牛顿法）清晰地编码出来。这是 SICP 的核心思想，也是函数式编程的基础。

八、课堂问答与补充 [40:00]

8.1 学生提问：能否内联定义？

学生问：能否把 f 的定义直接放进 fixed-point 调用里？

教师回答：可以。任何定义过的东西，都可以把它的定义体放到使用处。例如：

(define (newton-method f guess)
  (fixed-point
    (lambda (x) (- x (/ (f x) ((deriv f) x))))
    guess))

可以写成：

(define (newton-method f guess)
  (fixed-point
    (lambda (x) (- x (/ (f x)
                        ((lambda (x)
                           (/ (- (f (+ x dx)) (f x)) dx))
                         x))))
    guess))

易错点：内联的代价——内联会导致重复计算。例如，每次调用 newton-method 时都会重新计算 (deriv f)，而不是复用。这在性能敏感的场景下可能有问题。

8.2 关于变量名冲突

教师强调：lambda 的参数名是内部名称，不会与外部的同名变量冲突。例如：

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

这里的 a 是 sum 的内部参数，与外部任何叫 a 的变量无关。

考点：词法作用域——lambda 的参数在过程体内部有效，不影响外部。这是词法作用域（lexical scoping）的基本规则。

九、本讲核心概念总结

9.1 高阶过程

考点：高阶过程的定义——高阶过程是接收过程作为参数或返回过程作为值的过程。它是 SICP 的核心概念之一。

9.2 本讲涉及的高阶过程

9.3 抽象的方法论

重点：wishful thinking（愿望式编程）——先假设需要的抽象已经存在，写出高层逻辑，再实现底层细节。这是 SICP 反复强调的编程方法，也是"自顶向下"设计的体现。

9.4 关注点分离

重点：分解与独立演化——把复杂系统分解成多个独立的部分，每部分可以独立理解、独立修改。这是软件工程的核心原则，也是本讲通过 sum 的迭代版本 vs 递归版本所展示的。

十、拓展与延伸

【拓展】高阶过程在其他语言中的体现

• JavaScript：函数是一等公民，map、filter、reduce 都是高阶函数
• Python：函数可以作为参数传递（map、filter、sorted 的 key 参数），但 lambda 语法有限制
• Haskell：纯函数式语言，高阶函数是核心
• Java 8+：通过函数式接口（Function、Consumer 等）和方法引用支持高阶函数
• C：通过函数指针支持类似功能，但没有闭包

【拓展】不动点迭代的收敛性

• 不动点迭代 y_{n+1} = f(y_n) 收敛的充分条件：在不动点附近 |f'(y)| < 1
• 如果 |f'(y)| > 1，迭代会发散
• 平均阻尼相当于把 f 替换为 (x + f(x))/2，其导数绝对值通常更小，因此更容易收敛
• 牛顿法本质上是二阶收敛的，比普通不动点迭代快得多

【拓展】数值求导的精度问题

• 数值求导 (f(x+dx) - f(x))/dx 的误差是 O(dx)（截断误差）
• 但 dx 太小会导致舍入误差放大（因为 f(x+dx) - f(x) 会损失有效数字）
• 实际工程中，dx 通常取 sqrt(epsilon) * x 左右（epsilon 是机器精度）
• 更好的方法是自动微分（automatic differentiation）或符号求导

【拓展】SICP 后续内容预告

• 本讲提到"数据结构"——后续会讲如何把过程放入数据结构中
• 本讲提到的"闭包"概念——后续会深入讲解
• 本讲提到的"迭代 vs 递归"——后续会讲尾递归优化

关键标签/关键词

SICP 高阶过程 higher-order procedures 过程作为参数 过程作为返回值 lambda 匿名过程 sum fixed-point 不动点 average-damp 平均阻尼 newton-method 牛顿法 deriv 数值求导 wishful thinking 愿望式编程 一等公民 first-class citizens 抽象 abstraction 关注点分离 separation of concerns 递归 迭代 Scheme MIT 6.001

生成时间：2026-10-11 14:47:42 生成平台：VideoNote www.xygy.top