[Back]

2.1 数据抽象导引

2.1

(define (make-rat a b)
    (define (minimize-rat x y) 
        (let ((g (gcd x y)))
            (cons x y)))
    (cond ((< b 0) (minimize-rat (- a) (- b)))
          ((= b 0) (display "error: denom can't be zero."))
          (else (minimize-rat a b))))

2.2

(define (make-point x y) (cons x y))
(define (x-point p) (car p))
(define (y-point p) (cdr p))
(define (display-point p)
    (newline)
    (display "(" (x-point p) "," (y-point p) ")"))
(define (make-segment a b c d)
    (let ((x (make-point a b))
          (y (make-point c d)))
        (cons x y)))
(define (start-point l) (car l))
(define (end-point l) (cdr l))
(define (mid-point l)
    (make-point (average (x-point (start-point l)) (x-point (end-point l))) 
                (average (y-point (start-point l)) (y-point (end-point l)))))

2.3

(define (make-rectangle l1 l2)
    (cons l1 l2))
(define (rec-circ m)
    (* 2 (+ (width m)
        (height m))))
(define (rec-area m)
    (* (width m)
        (height m)))
(define (width m) (segment-length (cdr m)))
(define (height m) (segment-length (car m)))
(define (segment-length l)
    (sqrt (+ (square (- (x-point (start-point l))
                        (x-point (end-point l))))
            (square (- (y-point (start-point l))
                        (y-point (end-point l)))))))

(define (width m) 
    (segment-length (make-segment (x-point (start-point (car m))) 
                                    (y-point (start-point (car m)))
                                (x-point (start-point (cdr m)))
                                (y-point (start-point (cdr m))))))

考虑第一种方式:使用两条同起点的互相垂直线段做参数,抽象屏障为width和height对area和circ的封闭

第二种方式:同方向的两个平行向量,只需修改width函数即可。

2.4

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

2.5

对任意的A和n,我们都有A^n > 0,同时,指数函数对数域的算术运算封闭。

(define (cons a b)
    (* (expt 2 a)
        (expt 3 b)))
(define (car z)
    (define (iter z result)
        (if (not (= (remainder z 2) 0))
            result
            (iter (/ z 2) (+ result 1))))
    (iter z 0))
(define (cdr z)
    (define (iter z result)
        (if (not (= (remainder z 3) 0))
            result
            (iter (/ z 3) (+ result 1))))
    (iter z 0))

2.6

(define one (lambda (f) (lambda (x) (f x))))
(define two (lambda (f) (lambda (x) (f (f x)))))
(define (add a b)
	(lambda (f) (lambda (x) ((b f) ((a f) x)))))

参见Lambda演算

2.7

(define (lower-bound inter) (min (car inter) (cdr inter)))
(define (upper-bound inter) (max (car inter) (cdr inter)))

实际上可能按照书上的用意是不需要进行一次比较的,但是为了规范化还是写了上去

2.8

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

2.9

由于乘除多了一个选择过程,因此并没有一个确定的从原上下界得到的公式,所以宽度和原宽度也是不关联的,如int1=(-2.43 1.56)int2=(3.44 5.67)和 int1=(1.33 4.87) int2=(-8.76 -5.71) 而加减的证明也是很简单的。

2.10

(define (zero-check? int)
    (cond ((and (< (lower-bound int) 0) (> (upper-bound int) 0)) 1)
          ((or (= (lower-bound int) 0) (= (upper-bound int) 0)) 1)
          (else 0)))
(define (div-interval x y)
    (if (= (zero-check? y) 1)
        (display "Error:Interval contains zero.")
        (mul-interval x
                    (make-interval (/ 1.0 (upper-bound y))
                                    (/ 1.0 (lower-bound y))))))

2.11

(define (mul-interval x y)
    (let ((a (lower-bound x))
        (b (upper-bound x))
        (c (lower-bound y))
        (d (upper-bound y)))
    (cond ((and (> b 0) (< c 0) (> d 0)) (make-interval (* b c) (* b d)))
          ((and (and (> a 0) (> c 0))
                (and (< b 0) (< d 0))) (make-interval (* a c) (* b d)))
          ((and (> b 0) (< d 0)) (make-interval (* b c) (* a d)))
          ((and (< a 0) (> b 0) (> c 0)) (make-interval (* a d) (* b d)))
          ((and (< b 0) (> c 0)) (make-interval (* a d) (* b c)))
          ((and (< b 0) (< c 0) (> d 0)) (make-interval (* a d) (* a c))))))

2.12

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

2.13

int1 = (a , b) = (a - ab , a + ab) int2 = (c , d) = (c - cd , c + cd)
int3 = int1 * int2 = (ac - acd - abc + abcd , ac + abc + acd + abcd)
width(int3) = ac(b + d)
mid(int3) = ac(bd + 1)
percent(int3) = b + d / (bd + 1)

2.14

使用以下数据做测试:

(define int1 (make-interval 4.5 0.1))
(define int2 (make-interval 3.8 0.05))

得到结果:

(2.0555666173071367 . 2.064924586428089)
(2.058739094000193 . 2.0617425780121357)

可以看出是不一致的, 我们来试试A/A 和A/B

得到结果:

(0.9980019980019979 . 1.0020020020020022)
(1.1824350982403533 . 1.1859877303074589)

查看一下结果的百分比:

0.19999980000021655
0.14999992500004136

可以看到会更加大一些,我们拿多组数据进行测试,发现A/A的百分误差为2*A

A/B的误差为A+B,而B+A的误差也是A+B

然而根据推到A/A的误差应该为2*A /( A *A+1),可见由于A特别小,近似等于了2*A。

所以第一个计算电阻方式的误差应该会是(b+d)+(ab+cd)/(a+c)

第二个是 (bc+ad)/(a+c),显然要小很多。

2.15

的确由于不确定度的计算规则,在数学上而言减少对变量的运算会是更加精确的区间,但是这个区间在工程上或者测量上显然不是更加好的置信区间,因为它会引进一个(1±0)的精确区间。我们应该算出更大的误差区间才是较好的。

2.16

我已经在2.14阐述过了这个一般问题。显然,引入更多的区间运算意味着更多的误差,这是不可避免的。

如何设计一个包来弥补这样的缺陷呢?

//补:暂时上我认为,这是一个不可解的问题。

//2019.10.6 研究形式化证明以后。我认识到只需要制定一套与IEEE754不同的浮点数系统,就可以在某种程度上减少这个误差,我们需要形式化的证明两个实数的相等性,也就是,使用一个equality的dependent type。