第三章

  1. 有效的程序综合需要一些组织原则，它们应能指导我们系统化地完成系统的整体设计， 特别是需要一些能帮助我们构造起模块化的大型系统的策略，也就是说，使这些系统 能够“自然地”划分为一些具有内聚力地部分，使这些部分可以分别进行开发和维护；
  2. 有一种非常强有力的设计策略，特别适合用于构造那类模拟真实物理系统的程序，那 就是基于被模拟系统的结构去设计程序的结构；这样在很大程度上组织大型程序的方 式会受到我们对于被模拟系统的认识的支配；
  3. 两种策略：
    1. 将注意力集中在对象上，将一个大型系统看成一大批对象，它们的行为可能随着时 间的进展而不断变化；
      1. 迫使我们抛弃老的计算的代换模形，转向更机械式的，理论上也更不容易把握 的环境模形；
    2. 将注意力集中在流过系统的信息流上。
      1. 使用被称为延时求值的技术松解在我们的模形中对时间的模拟与计算机求值过 程中的各种事件发生的顺序；

赋值和局部状态

  1. 如果一个系统中的状态变量可以分组，形成一些内部紧密结合的子系统，每个子系统 与其他子系统之间只存在松散联系，此时将这个系统看作是由一些独立对象组成的观 点就会特别有用；
  2. 这种观点有可能成为组织这一系统的计算模形的有力框架：要使这样的一个模型成为 模块化的，就要求它能分解为一批计算对象，使它们能够模拟系统里的实际对象，每 一个简单对象必须有它自己的一些局部状态变量，用于描述实际对象的状态；

局部状态变量

  1. 第三章引入赋值运算符之前， SICP 中所有过程可以看作一些可计算的数学函数 的描述，对一个过程的调用将计算出相应函数作用于给定参数应得到的值，用同样 的实际参数两次调用同一个过程，总会产生出相同的结果；
  2. (set! <name> <new-value>) 应是一个符号， 是任何表达式， set! 将修改 ，使它的值变成求值 得到的结果；
  3. (begin <exp1> <exp2> ... <expk>) 将导致表达式 到 按顺序求 值，最后一个表达式 的值又将作为整个 begin 形式的值返回；

练习 3.1-3.4

  • 3.1

    1
2
3
4

    (define (make-accumulator n)
    (lambda (amount)
      (begin (set! n (+ n amount))
         n)))

  • 3.2

    1
2
3
4
5
6
7
8

    (define (make-monitored f)
  (let ((count 0))
    (lambda (x)
      (cond
       ((eq? x 'how-many-calls?) count)
       ((eq? x 'reset-count) (set! count 0))
       (else (begin (set! count (+ count 1))
            (f x)))))))

  • 3.3

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

    (define (make-account balance password)
  (define (withdraw amount)
    (if (>= balance amount)
    (begin (set! balance (- balance amount))
           balance)
    "Insufficient funds"))
  (define (deposit amount)
    (set! balance (+ balance amount))
    balance)
  (define (dispatch p m)
    (if (eq? p password)
    (cond ((eq? m 'withdraw) withdraw)
          ((eq? m 'deposit) deposit)
          (else (error "Unknown request -- MAKE-ACCOUNT"
               m)))
    (error "Incorrect password")))
  dispatch)

  • 3.4

     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 (make-account balance password)
  (define (call-the-cops)
    (display "Cops on the way..."))
  (define (withdraw amount)
    (if (>= balance amount)
    (begin (set! balance (- balance amount))
           balance)
    "Insufficient funds"))
  (define (deposit amount)
    (set! balance (+ balance amount))
    balance)
  (let ((failure-entries 0))
    (define (dispatch p m)
      (if (eq? p password)
      (begin (set! failure-entries 0)
         (cond ((eq? m 'withdraw) withdraw)
               ((eq? m 'deposit) deposit)
               (else (error "Unknown request -- MAKE-ACCOUNT"
                    m))))
      (begin (set! failure-entries (+ 1 failure-entries))
         (if (< failure-entries 7)
             (error "Incorrect password")
             (call-the-cops)))))
    dispatch))

引进赋值带来的收益

  1. 将赋值引进所用的程序设计语言，将会使我们陷入许多困难的概念问题的丛林中；
  2. 将系统看作是一集带有局部状态的独立对象，也是一种维护模块化设计的强有力技术；
  3. 与所有状态都必须显式地操作和传递额外参数的方式相比，通过引进赋值和将状态 隐藏在局部变量中的技术，我们能以一种更模块化的方式构造系统；

练习 3.5-3.6

  • 3.5

     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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

    (define (monte-carlo trials experiment)
  (define (iter trials-remaining trials-passed)
    (cond ((= trials-remaining 0)
       (/ trials-passed trials))
      ((experiment)
       (iter (- trials-remaining 1) (+ trials-passed 1)))
      (else
       (iter (- trials-remaining 1) trials-passed))))
  (iter trials 0))

(define (make-point x y)
  (cons x y))

(define (x-point p)
  (car p))

(define (y-point p)
  (cdr p))

(define (mid-point p1 p2)
  (let ((x (/ (+ (x-point p1) (x-point p2)) 2))
    (y (/ (+ (y-point p1) (y-point p2)) 2)))
    (make-point x y)))

;; there the rectangular is just a square.
(define (radius-square p1 p2)
  (let ((x1 (x-point p1))
    (x2 (x-point p2)))
    (square (abs (/ (- x1 x2) 2)))))

(define (p r1 r2 m1 m2 rs)
  (< (+ (square (- r1 m1))
     (square (- r2 m2)))
      rs))

(define (random-in-range low high)
  (let ((range (- high low)))
    (+ low (random range))))

(define (estimate-integral p x1 x2 y1 y2 n)
  (let ((p1 (make-point x1 y1))
    (p2 (make-point x2 y2)))
    (let ((center (mid-point p1 p2)))
      (define (integral-test)
    (let ((r1 (random-in-range x1 x2))
          (r2 (random-in-range y1 y2))
          (m1 (x-point center))
          (m2 (y-point center))
          (rs (radius-square p1 p2)))
      (p r1 r2 m1 m2 rs)))
      (monte-carlo n integral-test))))

(estimate-integral p 2.0 8.0 4.0 10.0 100000) ;393/500

  • 3.6

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

    (define rand
  (let ((x random-init))
    (define (generate)
      (begin (set! x (rand-update x))
         x))
    (define (reset n)
      (set! x n))
    (define (dispatch s)
      (cond ((eq? s 'generate)
         (generate))
        ((eq? s 'reset)
         reset)
        (else (error "Unknown request -- RAND"
             s))))
    dispatch))

引进赋值的代价

  1. 不用任何赋值的程序设计称为函数式程序设计；
  2. 本质上讲，代换的最终基础就是，这一语言里的符号不过是作为值的名字；而一旦 引进了 set! 和变量的值可以变化的想法，一个变量就不再是一个简单的名字，变 量索引着一个可以保存值的位置，而存储在那里的值也是可以改变的；
  3. 如果一个语言支持在表达式里“同一的东西可以相互替换”的观念，这样的替换不会 改变有关表达式的值；这个语言就称为具有引用透明性，在我们的计算机语言里包 含了 set! 之后，也就打破了引用透明性，这使确定能否通过等价的表达式代换去 简化表达式变成了一个异常错综复杂的问题了；
  4. 广泛采用赋值的程序设计被称为命令式程序设计；
  5. 带有赋值的程序将强迫人们去考虑赋值的相对顺序，以保证每个语句所用的的是被 修改变量的正确版本；在函数式程序设计中，这类问题根本就不会出现；如果考虑 有着多个并发执行的进程的应用程序，命令式程序设计的复杂性还会变得更糟糕；

练习 3.7-3.8

  • 3.7

     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 (make-account balance pass)
  (let ((password (list pass)))
    (define (withdraw amount)
      (if (>= balance amount)
      (begin (set! balance (- balance amount))
         balance)
      "Insufficient funds"))
    (define (deposit amount)
      (begin (set! balance (+ balance amount))
         balance))
    (define (joint new-password)
      (begin (set! password (cons new-password password))
         dispatch))
    (define (dispatch p m)
      (if (memq p password)
      (cond ((eq? m 'withdraw) withdraw)
        ((eq? m 'deposit) deposit)
        ((eq? m 'joint) joint)
        (else (error "Unknown request -- MAKE-ACCOUNT"
                 m)))
      (error "Incorrect password")))
    dispatch))

(define (make-joint  acc old-pass new-pass)
  ((acc old-pass 'joint) new-pass))

  • 3.8

    1
2
3
4
5
6
7
8

    (define (g y)
  (define (f x)
    (let ((z y))
      (set! y x)
      z))
  f)

(define f (g 0))