SICP——构造程序抽象（六）

1.过程作为参数

以过程为参数或是以过程为返回值的过程，这类过程称为高阶过程

先从两个过程入手，第一个是计算从a到b的各整数之和：

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

第二个是计算给定范围内的整数的立方之和：

# 前提函数
(define (cube a)
    (* a a a) )

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

这两个过程共享着一种公共的基础模式，抽象出来就是：

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

不过数学家很早就认识到序列求和中的抽象模式，并提出了"求和记法"：

b
∑ f(n) = f(a)+ ...+ f(b)
n=a

求和记法的好处在于它能使数学家能去处理求和的概念本身，而不是某个特定的求和

作为程序模式，我们可以把上面计算特定求和的过程抽象成一个类似求和记法的求和概念：

(define (sum term a next b)    # term和next是过程参数
    (if (> a b)
    0
    (+ (term a)
       (sum term (next a) next b))))

计算前面两个过程：

# 求立方和
(define (inc n) (+ n 1))
(define (sum-cubes)
    (sum cube a inc b))
# 求整数和
(define (identity x) x)    # 此处用了一个恒等函数
(define (sum-integers)
    (sum identity a inc b))

以上就是以sum作为基本构件去形式化其他概念的做法，整理一下：

找出多个过程中共享的一种公共模式
将模式模板化列出，过程函数用空位代替
以该模板为基本构件，将其他概念形式化

2.用lambda构造过程

上文中当用过程作为参数时必须要先定义，即使是简单函数，这样难免不爽，不过好在有个特殊形式可以直接刻画，那就是lambda，它可以不与环境中的任何名字关联，直接创造出所需要的过程，语法如下：

(lambda (<形参>) <体>)

借助lambda，可以把求立方和的过程定义为：

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

跟define的区别在于lambda是匿名的，事实上：

(define (sum1 x)
    (+ x 1))

==等价于==

(define sum1 (lambda(x) (+ x 1)))

lambda表达式可用作组合式的运算符，也可以用在任何通常使用过程名的上下文中

lambda的另一个应用是：创建局部变量

假设计算下面函数：

f(x, y) = x(1 + xy)² + y(1 - y) + (1 + xy)*(1 - y)

可以表达为：
a = 1 + xy
b = 1 - y
f(x, y) = xa² + yb + ab

这样我们可以用辅助过程去约束局部变量：

(define (f x y)
    (define (f-helper a b)
        (+ (* x (square a))
            (* y b)
            (* a b)))
    (f-helper (+ 1(* x y))
              (- 1 y)))

提到辅助过程就想起lambda来了，我们可以用简化一下：

(define (f x y)
    ((lambda (a b)              
        (+ (* x (square a))     |
            (* y b)             |   → lambda的体
            (* a b)))           |
     (+ 1 (* x y))
     (- 1 y)))

为了这种结构使用方便，有个专门的特殊形式：let，它的一般形式：

(let ((<var1> <exp1>)       # var1具有值exp1
     (<var2> <exp2>)        # var2具有值exp2……
     ……
     (<var n> <exp n>))
    <体>)                   # 在体中

==等价的lambda==
((lambda (<var1> …… <var n>)
  <体>)
<exp1>
……
<exp n>)

如此一来更简一步：

(define (f x y)
  (let ((a (+ 1 (* x y)))
        (b (- 1 y)))
    (+ (* x (square a))
        (* y b)
        (* a b))))

let是lambda的儿子(let表达式只是作为其基础的lambda表达式的语法外衣)

对于let需要注意的有：

let使人能在尽可能接近其使用的地方建立局部变量约束

# 若x=5，该过程的结果是---------------做完再看-->-------------------------------------38
(+ (let ((x 3)) 
      (+ x (* x 10)))
    x)

变量的值是在let之外计算的

# 若x=2，该过程的结果是---------------做完再看-->-------------------------------------12
(let ((x 3)
      (y (+ x 2)))
  (* x y)

3.过程作为一般性的方法

一般性过程需要更强的抽象，我们以找出函数的不动点来加深理解

如果x满足方程 f(x) = x，那么数x称为函数f的不动点

思路：从某个猜测值出发，反复应用f，直到值的变化不大(有一个容许值)，这时就有一个不动点
根据该思路，可以设计出以函数f和初始猜测值first-guess为参数的过程：

(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 (clost-enough? guess next)
        next
        (try next))))
  (try fitst-guess))

这个过程不禁想起其之前定义的找平方根的过程，因为他们的想法相同：
通过不断的改进猜测，直至结果满足某一评价准则为止

既然它们的模式相同，就可以把平方根的计算形式化为一个寻找不动点的计算过程，描述出思路是：
找到一个y使得y² = x，再转换成：y = x / y，如此一来就是找y |→ x/y的不动点：

|→(读作"映射到")，是lambda的数学写法，等价于(lambda(y) (/ x y))，即在y处的值为x/y的函数

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

但是这么做会有问题：若初始猜测值为y1，那么下一个猜测值将是y2 = x/y1，而再下一个则是y3 = x/y2 = x/(x/y1) = y1，结果是进入了一个无限循环，在y1和y2中间往复震荡

控制这类震荡的一种方法是：不让有关的猜测变化太剧烈，为此可以用y和x/y的平均值，我们取y之后的下个猜测值是(1/2)(y + x/y)，即搜索y|→(1/2)(y+x/y)的不动点：

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

这种取逼近一个解的一系列值的平均值的方法，是一种称为平均阻尼的技术，用来帮助收敛，很具有一般性

4.过程作为返回值

通过上文我们可以把平均阻尼的思想表述为：

(define (average-damp f)    # f是一个过程
  (lambda (x) (average x (f x))))

没错，这个过程是以过程为参数并返回另一个过程，以简单的square过程开刀：

((average-damp square) 10)

不难理解，上式将返回55
利用这一点，我们可以再重做前面的平方根过程：

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

这个过程中结合了三种思想：不动点搜寻、平均阻尼、和函数y| →x/y，在与旧版本的比较中可以发现我们用抽象描述计算过程时，其中想法的越来越清晰

选择过程时要清晰且易理解，使该计算过程中有用的元素能表现为一些相互分离的，并使它们能用于其他应用

上过程是从一个函数出发，找出这一函数在某种变换下的不动点，可以将这思想表述为一个函数：

(define (fixed-point-of-transform g transform guess)   # 三个参数：g是过程参数 transform是变换g的过程 guess为初始猜测
  (fixed-point (transform g) guess))

这是个非常具有一般性的过程，用这重新塑造平方根过程：

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

高阶过程的重要性在于我们能显式地用程序设计语言的要素去描述这些抽象

一般而言，程序设计语言总会对计算元素的可能使用方式强加上某些限制，带有最少限制的元素被称为具有第一级的状态，第一级元素的权利包括：

可以使用变量命名
可以提供给过程作为参数
可以由过程作为结果返回
可以包含在数据结构中

Lisp给了过程完全的第一级状态，因此描述能力惊人

到此，初探构造程序抽象的部分结束，最后献上一段话：

心智的活动，除了尽力产生各种简单的认知之外，主要表现在如下三个方面：

将若干简单认识组合为一个复合认识，因此产生出各种复杂的认识

将两个认识放在一起对照，不管它们如何简单或复杂，这样做时并不将它们合而为一，由此得到有关它们的相互关系的认识

将有关认识与那些在实际中和它们同在的所有其他认识隔离开，这就是抽象，所有具有普遍性的认识都是这样得到的

—John locke，有关人类理解的随笔