翻车到坑里

笔记

这一小节主要将数据封装的抽象，类似接口的感觉。

习题

习题 2.1

Exercise 2.1. Define a better version of make-rat that handles both positive and negative arguments. Make-ratshould normalize the sign so that if the rational number is positive, both the numerator and denominator are positive, and if the rational number is negative, only the numerator is negative.

想要得到最简的表达式需要两个步骤，一个是需要除以最大公约数，第二个是符号处理。

最大公约数很简单，直接用前面小节的程序即可。

接着处理符号，考虑到负负得正，而题目中已经说明如果整个分式是负数，则分子保留负号。

那只需要判断分母符号就可以了。因为分母不可以有负号。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
(define (gcd a b)
  (if (= b 0)
      a
      (gcd b (remainder a b))))
    
(define (remainder a b)
  (if (< a b)
      a
      (remainder (- a b) b)))
    
(define (nagetive? x)
  (< x 0))

(define (make-rat n d)
  (define g (gcd (abs n) (abs d)))
  (if (nagetive? d)
      (cons (- (/ n g)) (- (/ d g)))
      (cons (/ n g) (/ d g))))

测试

1
2
3
4
5
6
7
8
(make-rat 2 4)
;=> (1 . 2)
(make-rat 2 -4)
;=> (-1 . 2)
(make-rat (- 2) 4)
;=> (-1 . 2)
(make-rat (- 2) (- 4))
;=> (1 . 2)

习题 2.2

Exercise 2.2. Consider the problem of representing line segments in a plane. Each segment is represented as a pair of points: a starting point and an ending point. Define a constructor make-segment and selectors start-segment and end-segment that define the representation of segments in terms of points. Furthermore, a point can be represented as a pair of numbers: the x coordinate and the y coordinate. Accordingly, specify a constructor make-point and selectors x-point and y-point that define this representation. Finally, using your selectors and constructors, define a procedure midpoint-segment that takes a line segment as argument and returns its midpoint (the point whose coordinates are the average of the coordinates of the endpoints). To try your procedures, you’ll need a way to print points:

1
2
3
4
5
6
7
(define (print-point p)
  (newline)
  (display "(")
  (display (x-point p))
  (display ",")
  (display (y-point p))
  (display ")"))

点只需要记录 $x$，$y$。

线段只需要记录起点和终点。

直接用 cons 记录即可。

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
(define (make-point x y)
  (cons x y))

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

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

(define (print-point p)
  (display "(")
  (display (x-point p))
  (display ",")
  (display (y-point p))
  (display ")")
  (newline))

(define (make-segment begin end)
  (cons begin end))

(define (begin-segment line)
  (car line))

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

(define (mid-point line)
  (define (average x y) (/ (+ x y) 2))
  (make-point (average (x-point (begin-segment line)) (x-point (end-segment line)))
              (average (y-point (begin-segment line)) (y-point (end-segment line)))))

测试

1
2
(print-point (mid-point (make-segment (make-point 1 1) (make-point 2 2))))
;=> (1.5 . 1.5)

习题 2.3

Exercise 2.3. Implement a representation for rectangles in a plane. (Hint: You may want to make use of exercise 2.2.) In terms of your constructors and selectors, create procedures that compute the perimeter and the area of a given rectangle. Now implement a different representation for rectangles. Can you design your system with suitable abstraction barriers, so that the same perimeter and area procedures will work using either representation?

确定一个矩形，只需要对角线上的两点即可。

通过构建抽象屏障（接口）使得实现和抽象分离。这样即使换了矩形的实现方式也不会影响。

这里选择的抽象屏障是矩形的长和宽，也就是无论矩形底层怎么实现，只要实现了长和宽接口就行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
(define (make-rectangle p1 p2)
  (cons p1 p2))

(define (begin-point rect)
  (car rect))

(define (end-point rect)
  (cdr rect))

(define (x-length rect)
  (abs (- (y-point (begin-point rect)) (y-point (end-point rect)))))

(define (y-lenth rect)
  (abs (- (x-point (begin-point rect)) (x-point (end-point rect)))))

(define (perimeter rect)
  (* 2 (+ (x-lenth rect) (y-length rect))))

(define (area rect)
  (* (x-lenth rect) (y-length rect)))

测试

1
2
3
4
(perimeter (make-rectangle (make-point 1 2) (make-point 2 4)))
; => 6
(area (make-rectangle (make-point 1 2) (make-point 2 4)))
; => 2

习题 2.4

Exercise 2.4. Here is an alternative procedural representation of pairs. For this representation, verify that (car (cons x y)) yields x for any objects x and y.

1
2
3
4
(define (cons x y)
  (lambda (m) (m x y)))
(define (car z)
  (z (lambda (p q) p)))

What is the corresponding definition of cdr? (Hint: To verify that this works, make use of the substitution model of section 1.1.5.)

按 Applicative-Order 展开即可。

1
2
3
4
5
6
7
8
9
10
11
(car any-cons)

(any-cons (lambda (p q) p))

((lambda (m) (m x y)) (lambda (p q) p))

((lambda (p q) p) x y)

(lambda (x y) x)

; x

观察 (lambda (p q) p)

把 (p q) 视为一个 cons 那么 cdr cons 就是 cdr (p q)

结果是 q ，写成 lambda 表达式

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

习题 2.5

Exercise 2.5. Show that we can represent pairs of nonnegative integers using only numbers and arithmetic operations if we represent the pair $a$ and $b$ as the integer that is the product $2^a$ $3^b$. Give the corresponding definitions of the procedures cons, car, and cdr.

先写 cons ，根据 $a$ , $b$ 构造数字

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

因为数字是由 $2^a \cdot 3^b$ 的形式构建的，所以一直除以 2 就能得到有多少个 2 相乘

1
2
3
4
(define (cars x)
    (if (odd? x)
        0
        (+ 1 (cars (/ x 2)))))

类似的

1
2
3
4
(define (cdrs x)
    (if (not (= (remainder x 3) 0))
        0
        (+ 1 (cdrs (/ x 3)))))

习题 2.6

Exercise 2.6. In case representing pairs as procedures wasn’t mind-boggling enough, consider that, in a language that can manipulate procedures, we can get by without numbers (at least insofar as nonnegative integers are concerned) by implementing 0 and the operation of adding 1 as

1
2
3
(define zero (lambda (f) (lambda (x) x)))
(define (add-1 n)
  (lambda (f) (lambda (x) (f ((n f) x)))))

This representation is known as Church numerals, after its inventor, Alonzo Church, the logician who invented the $\lambda$ calculus.

Define one and two directly (not in terms of zero and add-1). (Hint: Use substitution to evaluate (add-1 zero)). Give a direct definition of the addition procedure + (not in terms of repeated application of add-1).

直接代入展开

1
2
3
4
5
6
7
8
9
10
11
12
13
(add-1 zero)

; 为了方便这里先展开 add-1
(lambda (f) (lambda (x) (f ((zero f) x))))

; 展开 zero 得
(lambda (f) (lambda (x) (f (((lambda (f) (lambda (x) x)) f) x))))

; 将 zero 中的 f 代入得
(lambda (f) (lambda (x) (f ((lambda (x) x) x))))

; 将 x 带入得
(lambda (f) (lambda (x) (f x)))

所以定义 one 为

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

用类似的方法

1
2
3
4
5
6
7
8
9
(add-1 one)

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

(lambda (f) (lambda (x) (f (((lambda (f) (lambda (x) (f x))) f) x))))

(lambda (f) (lambda (x) (f ((lambda (x) (f x)) x))))

(lambda (f) (lambda (x) (f (f x))))

所以定义 two 为

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

习题 2.7

Exercise 2.7. Alyssa’s program is incomplete because she has not specified the implementation of the interval abstraction. Here is a definition of the interval constructor:

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

Define selectors upper-bound and lower-bound to complete the implementation.

因为是 cons 结构。所以直接调用 car 和 cdr 即可。

1
2
3
4
5
(define (upper-bound interval)
  (cdr interval))

(define (lower-bound interval)
  (car interval))

习题 2.8

Exercise 2.8. Using reasoning analogous to Alyssa’s, describe how the difference of two intervals may be computed. Define a corresponding subtraction procedure, called sub-interval.

区间减法最小值为下界减上界

最大值为上界减下界

1
2
3
(define (sub-interval x y)
  (make-interval (- (lower-bound x) (upper-bound y))
                 (- (upper-bound x) (lower-bound y))))

还可以用 (add-interval) 实现。

习题 2.9

Exercise 2.9. The width of an interval is half of the difference between its upper and lower bounds. The width is a measure of the uncertainty of the number specified by the interval. For some arithmetic operations the width of the result of combining two intervals is a function only of the widths of the argument intervals, whereas for others the width of the combination is not a function of the widths of the argument intervals. Show that the width of the sum (or difference) of two intervals is a function only of the widths of the intervals being added (or subtracted). Give examples to show that this is not true for multiplication or division.

区间 $[2,4]$ 宽度为 $(4-2) \div 2 = 1$

区间 $[4,8]$ 宽度为 $(8-4) \div 2 = 2$

两个区间的乘积为 $[8,32]$ ，宽度为 $(32-8) \div = 12$

区间 $[4,6]$ 宽度为 $(6-4) \div 2 = 1$

区间 $[6,10]$ 宽度为 $(10-6) \div 2 = 2$

两个区间的乘积为 $[24,60]$ ，宽度为 $(60-24) \div 2 = 18$

可见同样的区间长度，一个是 $12$ ，另一个是 $18$ ，不仅仅由原本的区间宽度决定。

习题 2.10

Exercise 2.10. Ben Bitdiddle, an expert systems programmer, looks over Alyssa’s shoulder and comments that it is not clear what it means to divide by an interval that spans zero. Modify Alyssa’s code to check for this condition and to signal an error if it occurs.

区间包含零那么区间异号

1
2
3
4
5
6
7
8
9
(define (div-interval x y)
  (if (or (and (< (lower-bound x) 0)
               (> (upper-bound x) 0))
          (and (< (lower-bound y) 0)
               (> (upper-bound y) 0)))
      (error "interval span zero")
      (mul-interval x 
                (make-interval (/ 1.0 (upper-bound y))
                               (/ 1.0 (lower-bound y))))))

习题 2.11

Exercise 2.11. In passing, Ben also cryptically comments: By testing the signs of the endpoints of the intervals, it is possible to break mul-interval into nine cases, only one of which requires more than two multiplications.’’ Rewrite this procedure using Ben’s suggestion.

假设有四个正数 $a$ , $b$ , $c$ , $d$ 组成两个区间 $x(a,b)$ ，$y(c,d)$ 。

理论上有 $ 2 \times 2 \times 2 \times 2 = 16$ 种排列组合。

但是 $(a,-b)$ 和 $(c,-d)$ 的情况不符合区间上界大于下界的要求。

排除这两种组合后有 $3 \times 3 = 9$ 种组合。

按符号分类讨论

组合 Max Min
$(a,b)$ $(c,d)$ $b \cdot d$ $a \cdot c$
$(-a,b)$ $(c,d)$ $b \cdot d$ $-a \cdot d$
$(-a,-b)$ $(c,d)$ $-b \cdot c$ $-a \cdot d$
$(a,b)$ $(-c,d)$ $b \cdot d$ $b \cdot -c$
$(-a,b)$ $(-c,d)$ $-a \cdot -c$ 或 $b \cdot d$ $-a \cdot -c$ 或 $ b \cdot d$
$(-a,-b)$ $(-c,-d)$ $-a \cdot -c$ $-b \cdot -d$
$(a,b)$ $(-c,-d)$ $a \cdot -d$ $b \cdot -c$
$(-a,b)$ $(-c,-d)$ $-a \cdot -c$ $b \cdot -c$
$(-a,-b)$ $(-c,-d)$ $-a \cdot -c$ $-b \cdot -d$

习题 2.12

Exercise 2.12. Define a constructor make-center-percent that takes a center and a percentage tolerance and produces the desired interval. You must also define a selector percent that produces the percentage tolerance for a given interval. The center selector is the same as the one shown above.

1
2
3
4
5
(define (make-center-percent c p)
  (make-interval (* c (- 1 p)) (* c (+ 1 p))))

(define (percent x)
  (- (/ (upper-bound x) (center x)) 1))

习题 2.13

Exercise 2.13. Show that under the assumption of small percentage tolerances there is a simple formula for the approximate percentage tolerance of the product of two intervals in terms of the tolerances of the factors. You may simplify the problem by assuming that all numbers are positive.

题目要求找出一个估计区间乘法误差的公式。

按题目中的假设有两个区间 $x(c_x,p_x)$ , $y(c_y,p_y)$ ，所有数都是正数。

那么乘法的最大值是 $(c_x + c_x p_x)(c_y + c_y p_y)$

展开为 $c_x c_y + c_x c_y p_y + c_x c_y p_x + c_x c_y p_x p_y$

提取公因式 $c_x c_y(1 + p_y + p_x + p_x p_y)$

乘法的最小值是 $(c_x - c_x p_x)(c_y - c_y p_y)$

展开为 $c_x c_y (1 - p_y - p_x + p_x p_y)$

跟最大值的式子很像。将两个式子改写为

最大值 $c_x c_y (1 + p_x p_y) + c_x c_y (p_x + p_y)$

最小值 $c_x c_y (1 + p_x p_y) - c_x c_y (p_x + p_y)$

显然中点为 $c_x c_y (1 + p_x p_y)$ ，宽度为 $c_x c_y (p_x + p_y)$

所以乘法区间的误差为
$$
\begin{align}
\frac {c_x c_y (p_x + p_y)}{c_x c_y(1 + p_x p_y)} = \frac{p_x + p_y}{1 + p_x p_y} \approx p_x + p_y
\end{align}
$$

习题 2.14

Exercise 2.14. Demonstrate that Lem is right. Investigate the behavior of the system on a variety of arithmetic expressions. Make some intervals A and B, and use them in computing the expressions A/A and A/B. You will get the most insight by using intervals whose width is a small percentage of the center value. Examine the results of the computation in center-percent form (see exercise 2.12).

显然这种说法是对的

1
2
3
4
(par1 (make-center-percent 5 0.01) (make-center-percent 10 0.01))
; => (3.2346534653465353 . 3.4346801346801343)
(par2 (make-center-percent 5 0.01) (make-center-percent 10 0.01))
; => (3.3 . 3.3666666666666663)

最直接的原因是区间除法 $A / A \ne 1$ 。

所以 $\frac{1}{R_1}$ 通分的时候 $\frac{1}{R_1} \cdot \frac{R_2}{R_2} \ne \frac{R_2}{R_1R_2} $ 。

因此最后的结果会有偏差。