SICP-Refresher-Chapter-2(1)

第二章

本章将重点转到各种程序设计语言都包含的另一个关键方面：讨论它们所提供的，将数据对象组合起来，形成 复合数据 的方式；
复合数据和复合过程一样，是为了提升我们在设计程序时所位于的概念层次，提高设计的模块性，增强语言的表达能力；
复合数据使我们得以在比语言提供的基本数据对象更高的概念层次上，处理与数据有关的各种问题；
将程序中处理数据对象的表示的部分，与处理数据对象的使用的部分相互隔离的技术非常具有一般性，形成了一种称为 数据抽象 的强有力的设计方法学，数据抽象技术能使程序更容易设计，维护和修改；
形成复合数据的关键在于，程序设计语言里应该提供了某种“黏合剂”，它们可以用于把一些数据对象组合起来，形成更复杂的数据对象；
处理复合数据中的关键性思想 - 闭包概念：用于组合数据对象的黏合剂不但能用于组合基本的数据对象，同样也可以用于复合的数据对象；另一关键思想是：复合数据对象能够成为以 混合和匹配 的方式组合的程序模块的界面;
符号表达式进一步扩大语言的表述能力，将探索表示对象集合的不同方式：对于一种给定的数据结构，可以有许多方式将其表示为简单对象的组合，而不同的表示有可能对操作这些数据的计算过程的时间与空间需求造成重大的影响；
通用型操作的出现，将要求比只有简单数据抽象更强大的抽象屏障，引出 数据导向的程序设计 允许我们孤立地设计每一种数据表示，而后用添加的方式将它们组合进去。

数据抽象导引

数据抽象 的基本思想，就是设法构造出一些使用复合数据对象的程序，使用它们就像是在“抽象数据”上操作一样；
“具体数据”表示的定义（如何表示），与程序种使用数据的方式（如何使用），这样的两个部分之间的界面（接口）将是一组过程，称为 选择函数 和 构造函数, 它们在具体表示之上实现抽象的数据。

实例：有理数的算术运算

按愿望思维 的强有力的综合策略（翻译太概括了，就是先形式上整理出可以满足要求的抽象接口但并不实现它们，如果在这些接口上可以实现预先的编程设计，接下来再实现这些接口）；
通过过程 cons, car 和 cdr 实现的这样一种最基本的复合数据，序对，可以用作构造任意种类的复杂数据结构的通用的基本构件；
从序对构造起来的数据对象称为 表结构 数据；

练习 2.1

2.1

1
2
3
4
5
6
7
8
9


(define (gcd a b)
  (if (= b 0)
      a
      (gcd b (remainder a b))))

(define (make-rat-better n d)
  (let ((g (gcd n d)))
    (cond ((< (/ n d) 0) (cons (- (/ (abs n) g)) (/ (abs d) g)))
      (else ( cons (/ n g) (/ d g))))))

抽象屏障

继续深入数据抽象的基本思想：为每一类数据对象标识出一组操作，使得对这类数据对象的所有操作都可以基于这些操作来表述，而且在操作这些数据对象时也只使用它们（隔离）；
抽象屏障隔离了系统中不同的层次，在每一层上，这种屏障都把使用数据抽象的程序（上面）与实现数据抽象的程序（下面）分开来，每一层次中的过程构成了所定义的抽象屏障的接口；
在设计时将依赖于表示的成分限制到很少的一些程序模块上，这种方法就可以使程序很容易维护和修改，而且有助于程序的设计，这种做法将使我们能保留 考虑不同实现方式 的灵活性。

练习 2.2-2.3

2.2

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


(define (make-segment p1 p2)
  (cons p1 p2))

(define (start-segment segment)
  (car segment))

(define (end-segment segment)
  (cdr segment))

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

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

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

(define (midpoint-segment segment)
  (let ((start (start-segment segment))
    (end (end-segment segment)))
    (make-point (/ (+ (x-point start) (x-point end)) 2)
        (/ (+ (y-point start) (y-point end)) 2))))

2.3

 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


(define (make-rectangle p1 p2)
  (let ((p3 (make-point (x-point p1) (y-point p2)))
    (p4 (make-point (x-point p2) (y-point p1))))
    (let ((seg1 (make-segment p1 p3))
      (seg2 (make-segment p1 p4)))
      (cons seg1 seg2))))

(define (width rectangle)
  (let ((width-segment (cdr rectangle)))
    (let ((start (car width-segment))
      (end (cdr width-segment)))
      (abs (- (x-point end) (x-point start))))))

(define (length rectangle)
  (let ((length-segment (car rectangle)))
    (let ((start (car length-segment))
      (end (cdr length-segment)))
      (abs (- (y-point end) (y-point start))))))

(define (perimeter rectangle)
  (* 2
     (+ (width rectangle)
    (length rectangle))))

(define (size rectangle)
  (* (width rectangle)
     (length rectangle)))

;; anoterh way, no need to modify procedur perimeter and size
;; add "-another" to names just to avoid interpreter error
;; remove it when there is a need of test

(define (make-rectangle-another start width length)
  (cons start (const width length)))

(define (width-another rectangle)
  (car (cdr rectangle)))

(define (length-another rectangle)
  (cdr (cdr rectangle)))

数据意味着什么

只要满足一组特定条件的约束，总可以将数据定义为一组适当的选择函数和构造函数，使这一组过程成为该数据的一套合法表示；
可以将过程作为对象去操作，提供了另一种表示复合数据的能力，实际上，数据的过程性表示相关的程序设计风格通常称为 消息传递.

练习 2.4-2.6

2.4

1
2
3
4
5
6
7
8


(define (cons x y)
  (lambda (m) (m x y)))

(define (car z)
  (z (lambda (p q) p)))

(define (cdr z)
  (z (lambda (p q) q)))

2.5

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


(define (cons a b)
  (* (expt 2 a)
     (expt 3 b)))

(define (get-a-b z n count)
  (let ((remain (remainder z n)))
    (if (= remain 0)
    (get-a-b (/ z n) n (+ count 1))
    count)))

(define (car z)
  (get-a-b z 2 0))

(define (cdr z)
  (get-a-b z 3 0))

2.6

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


(define zero (lambda (f) (lambda (x) x)))

(define (add-1 n)
  (lambda (f) (lambda (x) (f ((n f) x)))))

(define one
  (lambda (f)
    (lambda (x)
      (f x))))

(define two
  (lambda (f)
    (lambda (x)
      (f (f x)))))

(define (+ a b)
  (lambda (f)
    (lambda (x)
      ((a f) ((b f) x)))))

扩展练习：区间算术

无。

练习 2.7-2.16

2.7

1
2
3
4
5
6
7
8


(define (make-interval a b)
  (cons a b))

(define (upper-bound z)
  (max (car z) (cdr z)))

(define (lower-bound z)
  (min (car z) (cdr z)))

2.8

1
2
3
4


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

(define (sub-interval x y)
  (add-interval x (make-interval (- (upper-bound y)) (- (lower-bound y)))))

2.9

1
2
3
4
5
6
7
8


(define (interval-width interval)
  (/ (- (upper-bound interval) (lower-bound interval)) 2))

(define (width-accumulated? combiner interval1 interval2)
  (let ((width1 (interval-width interval1))
    (width2 (interval-width interval2))
    (combined-width (interval-width (combiner interval1 interval2))))
   (= combined-width (+ width1 width2))))

2.10

1
2
3
4
5
6
7
8


(define (div-interval x y)
  (let ((upper (upper-bound y))
    (lower (lower-bound y)))
    (if (or (and (< lower 0) (> upper 0)) (= lower 0) (= upper 0))
    (error "the second interval acrossing the zero point")
    (mul-interval x
              (make-interval (/ 1.0 (upper-bound y))
                     (/ 1.0 (lower-bound y)))))))

2.11

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


(define (mul-interval x y)
   (define (positive? x) (>= x 0))
   (define (negative? x) (< x 0))
   (let ((xl (lower-bound x))
     (xu (upper-bound x))
     (yl (lower-bound y))
     (yu (upper-bound y)))
     (cond ((and (positive? xl) (positive? yl))
        (make-interval (* xl yl) (* xu yu)))
       ((and (positive? xl) (negative? yl))
        (make-interval (* xu yl) (* (if (negative? yu) xl xu) yu)))
       ((and (negative? xl) (positive? yl))
        (make-interval (* xl yu) (* xu (if (negative? xu) yl yu))))
       ((and (positive? xu) (positive? yu))
        (let ((l (min (* xl yu) (* xu yl)))
          (u (max (* xl yl) (* xu yu))))
          (make-interval l u)))
       ((and (positive? xu) (negative? yu))
        (make-interval (* xu yl) (* xl yl)))
       ((and (negative? xu) (positive? yu))
        (make-interval (* xl yu) (* xl yl)))
       (else
        (make-interval (* xu yu) (* xl yl))))))

2.12

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


(define (make-cent-percent c p)
  (let ((w (* c p)))
    (make-interval (- c w) (+ c w))))

(define (center i)
  (/ (+ (lower-bound i) (upper-bound i)) 2))

(define (width i)
  (/ (- (upper-bound i) (lower-bound i)) 2))

(define (percent i)
  (/ (width i) (center i)))

2.13

1
2
3
4
5
6
7
8


(define (percent-accumulated? x y)
  (let ((px (percent x))
    (py (percent y))
    (pr (percent (mul-interval x y))))
    (= pr (percent-accumulated px py))))

(define (percent-accumulated p1 p2)
  (/ 1 (abs (- (/ 1 p1) (/ 1 p2)))))

2.14

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


(define (part1 r1 r2)
  (div-interval (mul-interval r1 r2)
        (add-interval r1 r2)))

(define (part2 r1 r2)
  (let ((one (make-interval 1 1)))
    (div-interval one
          (add-interval (div-interval one r1)
                (div-interval one r2)))))

;; when procedure make-cent-percent and a very small amount percent are applied to construct a interval,
;; the results of both procedures defined before applied to such intervals are approaching the same.

2.15

1
2


;; 测试 execise 2.14 的过程可以证明了这个观点，
;; 使用带有更少非确定性的变量的公式实现的过程可以输出更精确的结果。

2.16

1
2
3
4
5
6
7
8


;; 一句话：不确定度的累积

;; 对表示范围的区间进行操作可能会使区间的范围继续扩张；
;; 等式中区间的个数越多，区间自带的不确定性相互影响，
;; 最终结果的范围扩张程度就越大；
;; 所以是根据第二个公式实现的过程的输出结果相比起来更加精确一些；

;; 没实现一个无缺陷的区间算术包。

文章目录

第二章

数据抽象导引

实例：有理数的算术运算

练习 2.1

抽象屏障

练习 2.2-2.3

数据意味着什么

练习 2.4-2.6

扩展练习：区间算术

练习 2.7-2.16