构造过程抽象

SICP 选用 Lisp 作为讨论程序设计的基础，考虑到的是 Lisp 的一个重要特征：计算过程的 Lisp 描述（即过程）本身又可以作为 Lisp 的数据来表示和操作。

一、程序设计的基本元素

每种强有力的语言都提供了三种机制：

1. 基本表达形式：用于表示语言所关心的最简单的个体。
2. 组合的方法：通过它们可以从较简单的东西出发构造出复合的元素。
3. 抽象的方法：通过它们可以为复合对象命名，并将它们作为单元去操作。

1.1 表达式

(+ 21 35 12 7)

这种形式称为前缀表示

1.2 命名和环境

(define size 2)

define 是我们所用的语言里最简单的抽象方法。

1.3 过程应用的代换模型

• 正则序求值：完全展开而后规约
• 应用序求值：先求值参数而后应用

1.4 牛顿法求平方根

(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 (sqrt x)
  (sqrt-iter 1.0 x))

1.5 练习1.6

习题解答

二、过程与它们所产生的计算

2.1 练习1.11

迭代计算过程:

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

(define (fib-iter a b c n)
  (if (< n 3)
      a
      (fib-iter (+ a
                   (* 2 b)
                   (* 3 c))
                a
                b
                (- n 1))))

2.2 练习1.12

(define (Paska line row)
  (cond ((> row line) 0)
        ((= row 1) 1)
        ((= row line) 1)
        (else (+ (Paska (- line 1)
                        (- row 1))
                 (Paska (- line 1)
                        row)))))

2.3 练习1.16

(define (fast-expt b n)
    (expt-iter b n 1))

(define (square b)
  (* b b))

(define (expt-iter b n a)
    (cond ((= n 0)
            a)
          ((even? n)
            (expt-iter (square b)
                       (/ n 2)
                       a))
          ((odd? n)
            (expt-iter b
                       (- n 1)
                       (* b a)))))

2.4 练习1.18

(define (multi a b)
    (multi-iter a b 0))

(define (multi-iter a b product)
    (cond ((= b 0)
            product)
          ((even? b)
            (multi-iter (double a)
                        (halve b)
                        product))
          ((odd? b)
            (multi-iter a
                        (- b 1)
                        (+ a product)))))

三、用高阶函数做抽象

2.1 过程作为参数

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

(define (cube n)
  (* n n n))

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

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

(define (sum-cubes a b)
  (sum cube inc a b))

2.2 练习1.29

(define (y k f a b n)
  (f (+ a
        (* k (/ (- b a) n)))))

(define (xinpushen f a b n)
  (define (z k)
    (+ (y k f a b n)
     (* 4 (y (+ k 1) f a b n))
     (y (+ k 2) f a b n)))
  (define (xps-next n) (+ n 2))
  (* (sum z xps-next 0 (- n 2))
     (/ (/ (- b a) n) 3.0)))

2.3 练习1.30

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

2.4 练习1.31

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

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

(define (factorial n)
  (define (fac-term n)
    (* (/ (- n 1) n)
       (/ (+ n 1) n)))
  (define (fac-next n)
    (+ n 2))
  (* (product2 fac-term fac-next 3.0 n)
     4))

2.5 练习1.32

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

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

2.6 练习1.33

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

(define (prime-sum a b)
  (define (term a) a)
  (define (next a) (+ a 1))
  (accumulate + 0 prime? term next a b))

2.7 练习 1.37

阅读习题解答

(define (cont-frac n d k)
  (define (iter s)
    (if (= s k)
        (d k)
        (/ (n s) (+ (d s) (iter (+ s 1))))))
  (iter 1))

(define (cont-frac N D k)

    (define (iter i result)
        (if (= i 0)
            result
            (iter (- i 1)
                  (/ (N i)
                     (+ (D i) result)))))
    (iter k 0))

想法：

• 对于递归而言，由低次往高次计算，无须对算式进行转换，就是原本算式的计算顺序
• 对于迭代而言，由高次往低次计算，所以需要一个变量保存每次计算后的结果