SICP-Refresher-Chapter-1(3)

用高阶函数做抽象

过程提供了这样的能力：
1. 能为公共的模式命名，建立抽象；
2. 直接在抽象的层次上工作。
如果不同的过程具有同样的设计模式，可以将这种模式提取出来构成高阶过程：
1. 它以过程为参数，以不同的过程参数调用可以实现前面所讲的具有相同设计模式的不同的过程的功能；
2. 可以将过程作为返回值；
3. 是强有力的抽象机制，极大地增强语言的表述能力。

过程作为参数

以序列求和中的抽象模式引出以过程作为参数的主题。

练习 1.29-1.33

1.29

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


(define (integral-simpson f a b n)
  (define h (/ (- b a) n))
  (define (compute count)
    (cond ((or (= count 0) (= count n)) (f (+ a (* count h))))
	  ((= (remainder count 2) 1) (* 4 (f (+ a (* count h)))))
	  ((= (remainder count 2) 0) (* 2 (f (+ a (* count h)))))))
  (define (count-next count)
    (+ count 1))
  (* (/ h 3)
     (sum compute 0 count-next n)))

1.30

1
2
3
4
5
6


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

1.31

 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
26
27
28
29
30
31
32
33


(define (product term a next b)
  (if (> a b)
      1
      (*
       (term a)
       (product term (next a) next b))))

;; a

(define (compute-next y)
  (+ y 1))

(define (factorial n)
  (define (keep-same x)
    x)
  (product keep-same 1 compute-next n))

(define (compute-pi n)
  (define (pi-term n)
    (if (even? n)
	(/ (+ n 2) (+ n 1))
	(/ (+ n 1) (+ n 2))))
  (* (product pi-term 1 compute-next n)
     4))

;; b

(define (product-iter term a next b)
  (define (iter a result)
    (if (> a b)
	result
	(iter (next a) (* result term(a)))))
  (iter a 1))

1.32

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


;; a

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

(define (sum term a next b)
  (accumulate + 0 term a next b))

(define (product term a next b)
  (accumulate * 1 term next b))

;; b

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

1.33

 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
26
27


;; (load "./1.20.scm")
;; (load "./1.21.scm")

(define (filtered-accumulate filter combiner null-value term a next b)
  (cond ((> a b) null-value)
	((filter a)
	 (combiner (term a)
		   (filtered-accumulate filter combiner null-value term (next a) next b)))
	(else (filtered-accumulate filter combiner null-value term (next a) next b))))

(define (keep-same n)
    n)

(define (compute-next n)
  (+ n 1))

;; a

(define (prime-sum a b)
  (filtered-accumulate prime? + 0 keep-same a compute-next b))

;; b

(define (gcd-product n)
  (define (gcd-equals-1? a)
    (= (gcd a n) 1))
  (filtered-accumulate gcd-equals-1? * 1 keep-same 1 compute-next (- n 1)))

用 lambda 构造过程

lambda:
1. 用与 define 同样的方式创建过程，除了不为有关过程提供名字之外，两者创建的过程完全一样；
2. 仅有的不同之处就是这种过程没有与环境中的任何名字相关联；
3. lambda 表达式可以用在任何通常使用过程名的上下文中。
let:
1. let 表达式只是作为其基础的 lambda 表达式的语法外衣罢了；
2. let 使人能在尽可能接近其使用的地方建立局部变量约束；
3. let 表达式描述的变量的值是在 let 最终创建的作用域之外计算的。

练习 1.34

1.34

1
2
3
4


;; (f f)
;; (f 2)
;; (2 2)
;; error, the object 2 is not applicable.

过程作为一般性的方法

一般性(general)方法的两个更精细的实例：
1. 找出函数零点；
2. 找出函数不动点；
一般性过程与其中涉及的特定函数无关，只要函数都符合一般性过程要求的特征（如参数个数，返回值类型等），而不用考虑函数到底是怎样进行特定计算过程的。

练习 1.35-1.39

1.35

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


(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))

(fixed-point (lambda (x) (+ 1 (/ 1 x))) 1.0) ;1.618.327...

1.36

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


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

(define tolerance 0.00001)

(define (report-evolution n)
  (newline)
  (display " *** ")
  (display n))

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

(fixed-point (lambda (x) (/ (log 1000) (log x))) 2) ;>20 steps

(fixed-point (lambda (x) (average x (/ (log 1000) (log x)))) 2) ;only 9 steps on my computer

1.37

 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
26
27
28
29
30


;; 0.6180...

;; recursive

(define (cont-frac n d k)
  (define (recursive count)
    (if (= count k)
	(/ (n count) (d count))
	(/ (n count) (+ (d count) (recursive (+ count 1))))))
  (recursive 1))

(cont-frac (lambda (i) 1.0)
	   (lambda (i) 1.0)
	   11)			; generates 0.6180555... after 11 steps

;; iterative

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

(/ 1 (cont-frac-iter (lambda (i) 1.0)
		     (lambda (i) 1.0)
		     11))		;also requires 11 steps

1.38

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


(define (compute-next i)
  (define the-count 1)
  (define the-number 2)
  (cond ((= the-count i) the-number)
	((= (remainder (- i the-count) 3) 0)
	 (+ (* (/ (- i the-count) 3) 2) the-number))
	(else 1)))

(define (cont-frac n d k)
  (define (recursive count)
    (if (> count k)
	(/ (n count) (d count))
	(/ (n count) (+ (d count) (recursive (+ count 1))))))
  (recursive 0))

(cont-frac (lambda (i) 1.0) compute-next 10) ;0.718281822... e: 2.718281828...

1.39

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


(define (higher-level-cont-frac combiner n d k)
  (define (recursive count)
    (if (= count k)
	(/ (n count) (d count))
	(/ (n count) (combiner (d count) (recursive (+ count 1))))))
  (recursive 1))

(define (tan-cf x k)
  (higher-level-cont-frac -
			  (lambda (i) (if (= i 1) x (square x)))
			  (lambda (i) (- (* i 2) 1))
			  k))
;; test

(define tan60 (/ (sqrt 3) 1))
(define tolerance 0.0001)

(< (abs (- (tan-cf (/ pi 3) 10) tan60)) tolerance) ;passed

过程作为返回值

创建一种其返回值本身也是过程的过程，能使程序设计语言得到进一步的表达能力；
将一个计算过程形式化为一个过程，一般来说存在很多不同的方式，有经验的程序员知道如何选择过程的形式，使其特别地清晰且易理解，使该计算过程中有用的元素能表现为一些相互分离的个体，并使它们还可能重新用于其他的应用；
复合过程作为一种至关重要的抽象机制，使我们能将一般性的计算方法明确描述为这一程序设计语言中的的元素，高阶函数可以操作这些一般性的方法以便建立起进一步的抽象；
编程者应该对第3条所述的可能性保持高度敏感，设法从中识别出程序里的基本抽象，基于它们去进一步构造，并推广它们以创建威力更加强大的抽象。；
在工作中选择合适的抽象层次，但重要的是能基于这种抽象去思考；
高阶过程的重要性，在于使我们能显式地将这些抽象描述为程序设计语言的要素，使我们能像操作其他计算要素一样去操作它们；
Lisp 给了过程完全的第一级状态（一等公民）。

练习 1.40-1.46

1.40

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


;; (load "./1.35.scm")

(define dx 0.00001)

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

(define (newton-transform g)
  (lambda (x)
    (- x (/ (g x) ((deriv g) x)))))

(define (newton-method g guess)
  (fixed-point (newton-transform g) guess))

(define (cubic a b c)
  (lambda (x)
    (+ (cube x)
       (* a (square x))
       (* b x)
       c)))

(newton-method (cubic 1 2 3) 1)		;-1.2756822...

1.41

1
2
3
4
5
6
7
8


(define (double f)
  (lambda (x)
    (f (f x))))

(define (inc n)
  (+ n 1))

(((double (double double)) inc) 5)	;21

1.42

1
2
3
4
5
6
7
8


(define (inc n)
  (+ n 1))

(define (compose f1 f2)
  (lambda (x)
    (f1 (f2 x))))

((compose square inc) 6)

1.43

1
2
3
4
5
6
7
8


;; (load "./1.42.scm")

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

((repeated square 2) 5)			;625

1.44

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


;; (load "./1.42.scm")
;; (load "./1.43.scm")

(define dx 0.00001)

(define (smooth f)
  (lambda (x) (/ (+ (f (- x dx)) (f x) (f (+ x dx))) 3)))

(define (smooth-n f n)
 ((repeated smooth
	    n)
  f))

1.45

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


;; (load "./1.35.scm")
;; (load "./1.43.scm")

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

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

(define (root n x)
  (fixed-point
   ((repeated
     average-damp
     (quotient n 2))
    (lambda (y) (/ x (expt y (- n 1)))))
   1.0))

1.46

 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
26
27
28
29
30
31
32


(define (iterative-improve good-enough? improve)
  (lambda (x)
    (if (good-enough? x)
	x
	((iterative-improve good-enough? improve) (improve x)))))

;; sqrt

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

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

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

  ((iterative-improve good-enough? improve) 1.0))

;; fixed-point

(define tolerance 0.00001)

(define (fixed-point f first-guess)
  (define (close-enough? guess)
    (< (abs (- guess (f guess))) tolerance))

  (define (improve guess)
    (f guess))

  ((iterative-improve close-enough? improve) first-guess))

文章目录

用高阶函数做抽象

过程作为参数

练习 1.29-1.33

1.29

1.30

1.31

1.32

1.33

用 lambda 构造过程

练习 1.34

1.34

过程作为一般性的方法

练习 1.35-1.39

1.35

1.36

1.37

1.38

1.39

过程作为返回值

练习 1.40-1.46

1.40

1.41

1.42

1.43

1.44

1.45

1.46