SICP——过程结构

发表于 | 分类于

范围

第一章 构造过程抽象

1.1.7 ~ 1.1.8 节，P13 - 20

keywords：牛顿法求平方根、局部名、约束/自由变量、作用域、块结构（内部定义过程/过程抽象）

笔记

1.1.7 牛顿法求平方根

平方根

  • 根号 x 是某个大于等于零的数 y， y^2 = x
  • 这是一个函数，不是一个切实可行的过程

牛顿法

  • 如果 y 是 x 的平方根，y == x/y
  • 要求 x 的平方根 y，从一个假设值 y 开始，不断求 y 与 x/y 的平均值，来得到更好的猜测
  • 当猜测“足够好”时，结束循环。

数学的函数和计算机里的函数有一个很重要的区别，就是后者必须是一个切实可行的计算过程。

  • 数学中定义：虽然这是一般性的定义，但没有给出切确的计算过程
  • 牛顿法就是一个切确的计算过程。
  • 函数与过程的矛盾，是描述一件事情的特征和描述如何去做这就事情直接的普遍性差异的一个具体反映。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
(define (sqrt-iter guess x)
  (if (good-enough? guess x)
      guess
      (sqrt-iter (improve guess x) x)))

(define (improve guess x)
  (average guess (/ x guess)))

(define (average x y)
  (/ (+ x y) 2))

(define (good-enough? guess x)
  (< (abs (- (square guess) x)) 0.001))

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

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

(define (sqrt x)
  (sqrt-iter 1.0 x))

(sqrt 9)
;Value: 3.00009155413138
  • 过程 good-enough? 就是说明什么情况下算改进到“足够好”，末尾的问号有一个提示 这个参数是一个过程 的作用。
  • 最后封装成 sqrt 时，用 1.0 作为起始的猜测值。
  • 这个程序说明，在用于写纯粹数值计算的程序时，至今介绍的简单程序设计语言足以写出其他语言（例如 C）中写出的任何东西了（amazing）。这个程序甚至没有循环结构，但展示了如何不用特殊的迭代结构来实现迭代，只需常规的过程调用即可。

1.1.8 过程作为黑箱抽象

程序的过程的分解：

1
2
3
4
5
6
7
8
        sqrt
         |
     sqrt-iter
    /        \
good-enough  improve
/        \      \
square  abs    average

  • 对平方根的计算问题可以很自然地分解成若干子问题。分解的重要性并不仅仅在于把这个问题分成了多少个小部分，关键在于分解中的每一个过程完成了一件清楚的工作。
  • 例如 基于 square 来定义 good-enough?时就将前者看成一个黑箱，如何计算平方的细节隐去不谈了，只需要注意它能计算出平方的事实。这里就说square是一个过程抽象
  • 用户在使用一个过程时，应该不需要去弄清它究竟是如何实现的。

可以写出相似的各种谓词，例如判断奇数偶数：

1
2
3
4
5
6
7
(define (remainder a b)
  (if (< a b)
      a
      (remainder (- a b) b)))

(define (odd? x)
  (= (remainder x 2) 1))

局部名

下面这两个过程定义应该是无法区分的：

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

(define (square y) (* y y))

这一原则：过程的意义不应该依赖于作者为其形参所选用的名字，从表面看起来十分明显，但其实意义非常深远。

  • 过程的形参必须局部于有关的过程体。（如果不相关，且两个不同的过程用了同样的参数名字，那两个过程的参数会相互影响，两个过程彼此之间也不是我们所希望的黑箱了）
  • 一个名字的定义被约束，则被约束的那一集表达式称为这个名字的作用域。
  • 这样子的名字叫做约束变量。如果一个变量没有被约束，称它是自由的。

例如 good-enough? 里

1
2
(define (good-enough? guess x)
  (< (abs (- (square guess) x)) 0.001))

guess和 x是约束的，< 、-、 abs、 square 是自由的。形参的具体名字是什么，其实完全没关系。前两个名字guess和 x的选择并不影响good-enough? 这个过程的意义，只要不要跟后面四个相同就可以了。

内部定义和块结构

  • 对于用户来说，只有一个过程是重要的，那就是sqrt。他们需要这个过程，想知道如何使用这个过程。
  • 我们希望隐藏那些辅助过程，例如sqrt-iter、good-enough?之类。虽然 sqrt 需要它，然而那些辅助过程却会干扰那些用 sqrt 的普通用户的思维。我们想要一种方式去“隐藏”
  • 在许多程序员一起构造一个大型系统时，这种情况非常常见。

方法：允许过程里带有一些内部定义，使它们局部于这一个过程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
(define (square x)
  (* x x))

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

(define (average x y)
  (/ (+ x y) 2))

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

(sqrt 9)
;Value: 3.00009155413138

我们可以看到，good-enough?、improve、sqrt-iter这三个过程的 define 声明统统移到了第四行 define sqrt 之中。

  • 这种嵌套定义的结构就是块结构。它就是简单的一种对于名字包装问题的正确解决方式。

这里面有一个很好的想法，就是参数 x 已在sqrt中被限定，good-enough?、improve、sqrt-iter三个过程都是在sqrt内被定义的，因此，把参数x在三个过程中传来传去就没有必要了，而是让x成为内部定义的自由变量。

  • 第一个 define 内的三个 define 中 x 作为内部定义的自由变量。这种方式叫做词法作用域