计算机程序的构造和解释(SICP) 第2章习题解析 Part1

这次回顾第二章第一部分习题。

学习资料：

https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-001-structure-and-interpretation-of-computer-programs-spring-2005/index.htm

https://github.com/DeathKing/Learning-SICP

https://mitpress.mit.edu/sites/default/files/sicp/index.html

https://www.bilibili.com/video/BV1Xx41117tr?from=search&seid=14983483066585274454

参考资料：

https://sicp.readthedocs.io/en/latest

https://stackoverflow.com/questions/14130878/sicp-2-16-interval-arithmetic-scheme

http://wiki.drewhess.com/wiki/SICP_exercise_2.16

https://en.wikipedia.org/wiki/Interval_arithmetic#Dependency_problem

https://zhuanlan.zhihu.com/p/45914836

https://www.xuebuyuan.com/1470405.html

https://zhuanlan.zhihu.com/p/102913021

2.1(p58)

考虑了边界情形，代码如下：

(load "helper.scm")

(define (make-rat n d)
    (define g (abs (gcd n d)))
    (cond ((= d 0) (error "Zero denominator!" d))
        ((= n 0) (cons 0 1))
        ((< n 0) (cons (/ (- n) g) (/ (- d) g)))
        (else (cons (/ n g) (/ d g)))))

;; test
(define t1 (make-rat 4 6))
(print-rat t1)
(define t2 (make-rat -4 6))
(print-rat t2)
(define t3 (make-rat 4 -6))
(print-rat t3)
(define t4 (make-rat -4 -6))
(print-rat t4)
(define t5 (make-rat 0 100))
(print-rat t5)
(define t6 (make-rat 1 0))

代码如下：

2/3
2/-3
2/-3
2/3
0/1
Exception in error: invalid message argument 0 (who = "Zero denominator!", irritants = ())

2.2(p60)

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

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

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

(define (add p1 p2)
    (make-point (+ (x-point p1) (x-point p2))
                (+ (y-point p1) (y-point p2))))

(define (divide p k)
    (make-point (/ (x-point p) k)
                (/ (y-point p) k)))

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

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

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

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

(define (midpoint-segment segment)
    (divide (add (start-segment segment) (end-segment segment)) 2))

;; test
(define p1 (make-point 1 2))
(define p2 (make-point 3 2))
(define seg (make-segment p1 p2))
(define midpoint (midpoint-segment seg))
(print-point midpoint)

结果如下：

(2,2)

2.3(p60)

通过两种方式定义矩形：

矩形左上角和右下角。
矩阵左上角和长宽。

代码如下：

(load "2.2.scm")

;; point
(define (minus p1 p2)
    (make-point (- (x-point p2) (x-point p1))
                (- (y-point p2) (y-point p1))))

;; rect统一表示出(point dx dy)的形式
;; rect1: 左上角和右下角
(define (rect1 p1 p2)
    (define p (minus p1 p2))
    (cons p1 (cons (x-point p) (y-point p))))

;; rect1: 左上角和长宽
(define (rect2 p dx dy)
    (cons p (cons dx dy)))

;; 长宽
(define (get-dx rect)
    (car (cdr rect)))

(define (get-dy rect)
    (cdr (cdr rect)))

;; 周长
(define (get-C rect)
    (* 2 (+ (get-dx rect) (get-dy rect))))

;; 面积
(define (get-S rect)
    (* (get-dx rect) (get-dy rect)))

;; print函数
(define (print-SC rect)
    (newline)
    (display "C: ")
    (display (get-C rect))
    (newline)
    (display "S: ")
    (display (get-S rect)))

;; test
(define p1 (make-point 1 1))
(define p2 (make-point 3 5))
(define r1 (rect1 p1 p2))
(define r2 (rect2 p1 2 4))
(print-SC r1)
(print-SC r2)

结果如下：

C: 12
S: 8
C: 12
S: 8

2.4(p62)

代码如下：

(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)))

; print
(define (print-cons pair)
    (newline)
    (display "car: ")
    (display (car pair))
    (newline)
    (display "cdr: ")
    (display (cdr pair)))

; test
(define pair (cons 1 2))
(print-cons pair)

结果如下：

car: 1
cdr: 2

解释：

(car (cons x y))
((lambda (p q) p) (x y))
x

(cdr (cons x y))
((lambda (p q) p) (x y))
y

2.5(p62)

题目的意思是用$(a, b)$表示$2^a 3^b$形式的数，然后据此计算出car，cdr，代码如下：

(load "helper.scm")

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

; 计算max k, p ^ k | d
(define (degree d p)
    (define (degree-iter d1 i)
        (if (not (= (remainder d1 p) 0))
            i
            (degree-iter (/ d1 p) (+ i 1))))
    (degree-iter d 0))

(define (car d)
    (degree d 2))

(define (cdr d)
    (degree d 3))

;; print-cons
(define (print-cons pair)
    (newline)
    (display "car: ")
    (display (car pair))
    (newline)
    (display "cdr: ")
    (display (cdr pair)))

; test
(define num (cons 3 6))
(newline)
(display num)
(print-cons num)

结果如下：

car: 3
cdr: 6

2.6(p62)

注意到：

one = (add-l zero)
two = (add-l one)

代入可得：

(add-l zero)
(lambda (f) (lambda (x) (f ((zero f) x))))
(lambda (f) (lambda (x) (f ((lambda (x) x) x))))
(lambda (f) (lambda (x) (f x)))
(define one
    (lambda (f) (lambda (x) (f x))))

(add-l one)
(lambda (f) (lambda (x) (f ((one f) x))))
(lambda (f) (lambda (x) (f ((lambda (x) (f x))) x)))
(lambda (f) (lambda (x) (f (f x))))

代码如下：

(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)))))

2.7(p63)

(load "helper.scm")

(define (make-interval a b) 
    (if (> a b)
        (error "a <= b does not satisfied!" 0)
        (cons a b)))

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

(define (upper-bound interval)
    (cdr interval))

; test
(define i1 (make-interval 2 3))
(print-interval i1)
(define i2 (make-interval 4 3))

结果如下：

lower-bound: 2
upper-bound: 3
Exception in error: invalid message argument 0 (who = "a <= b does not satisfied!", irritants = ())

辅助函数：

;; print interval
(define (print-interval interval)
    (newline)
    (display "lower-bound: ")
    (display (lower-bound interval))
    (newline)
    (display "upper-bound: ")
    (display (upper-bound interval)))

2.8(p63)

(load "2.7.scm")

(define (sub-interval i1 i2)
    (make-interval (- (lower-bound i1) (upper-bound i2))
                   (- (upper-bound i1) (lower-bound i2))))

; test
(define i1 (make-interval 4 6))
(define i2 (make-interval 2 3))
(define i3 (sub-interval i1 i2))
(print-interval i3)

结果如下：

lower-bound: 1
upper-bound: 4

2.9(p63)

对于区间：

$i= (l, u)$

定义宽度函数：

$f(i)= \frac {u- l}2$

任取区间：

$\begin{aligned} i_1&=(l_1, u_1)\\ i_2&=(l_2, u_2) \end{aligned}$

那么

$\begin{aligned} f(i_1 + i_2) &= f((l_1+l_2, u_1 + u_2))\\ &=\frac {u_1 + u_2 - l_1 -l_2}2\\ &= f(i_1) + f(i_2)\\ f(i_1 - i_2) &= f((l_1-u_2, u_1 - l_2))\\ &= \frac {u_1 + u_2 - l_1 -l_2}2\\ &= f(i_1) + f(i_2)\\ f(i_1 \times i_2) &= f((l_1\times l_2, u_1\times u_2))\\ &=\frac{u_1\times u_2 - l_1\times l_2} 2\\ f(i_1 / i_2) &= f((l_1/ u_2, u_1/ l_2))\\ &=\frac{u_1/ l_2- l_1/ u_2} 2 \end{aligned}$

2.10(p63)

(load "helper.scm")

(define (make-interval a b) 
    (cond ((> a b) (error "a <= b does not satisfied!" 0))
          ((and (<= a 0) (<= 0 b)) (error "Zero error" 0))
          (else (cons a b))))

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

(define (upper-bound interval)
    (cdr interval))

; test
(define i1 (make-interval 2 3))
(print-interval i1)
(define i2 (make-interval (- 4) 3))

结果如下：

lower-bound: 2
upper-bound: 3
Exception in error: invalid message argument 0 (who = "Zero error", irritants = ())

2.11(p63)

这题顺着2.10的思路剔除包含$0$的情形，所以这里只分了$5$种情形，根据边界的正负讨论即可，注意如果区间包含$0$，则应该报错；题干中的$9$种情形包含了区间端点一正一负的情形：

(load "2.10.scm")

(define (mul-interval x y)
    (define x1 (lower-bound x))
    (define x2 (upper-bound x))
    (define y1 (lower-bound y))
    (define y2 (upper-bound y))
    (cond ((and (<= 0 x1) (<= 0 y1)) (make-interval (* x1 y1) (* x2 y2)))
          ((and (<= 0 x1) (<= y2 0)) (make-interval (* x2 y1) (* x1 y2)))
          ((and (<= x2 0) (<= 0 y1)) (make-interval (* x1 y2) (* x2 y1)))
          ((and (<= x2 0) (<= y2 0)) (make-interval (* x2 y2) (* x1 y1)))
          (else (error "Error!" 0))))

; test
(define i1 (make-interval 2 3))
(define i2 (make-interval 3 4))
(print-interval (mul-interval i1 i2))

(define i3 (make-interval -3 -2))
(define i4 (make-interval 3 4))
(print-interval (mul-interval i3 i4))

(define i5 (make-interval 2 3))
(define i6 (make-interval -4 -3))
(print-interval (mul-interval i5 i6))

(define i7 (make-interval -3 -2))
(define i8 (make-interval -4 -3))
(print-interval (mul-interval i7 i8))

结果如下：

lower-bound: 6
upper-bound: 12
lower-bound: -12
upper-bound: -6
lower-bound: -12
upper-bound: -6
lower-bound: 6
upper-bound: 12

2.12(p64)

(load "2.10.scm")

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

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

(define (percent i)
    (define c (center i))
    (define w (/ (- (upper-bound i) (lower-bound i)) 2))
    (/ w c))

; print
(define (print-interval-percent interval)
    (newline)
    (display "center: ")
    (display (center interval))
    (newline)
    (display "percent: ")
    (display (percent interval)))

; test
(define i1 (make-center-percent 1 0.1))
(print-interval-percent i1)

结果如下：

center: 1.0
percent: 0.10000000000000003

2.13(p64)

结论正确，下面严格分析这个结论，假设我们用百分比表示法表示区间，设

$i= (x-px, x+ px)\triangleq x(1- p, 1+p)$

考虑两个区间（假设$p\ll 1$）

$\begin{aligned} i_1 &=x_1 (1-p_1, 1+p_1)\\ i_2 &= x_2 (1-p_2, 1+p_2) \end{aligned}$

那么

$\begin{aligned} i_1\times i_2 &= x_1 x_2 (1-p_1-p_2 +p_1 p_2, 1+p_1+p_2 + p_1 p_2)\\ &\approx x_1x_2(1-p_1-p_2, 1+p_1 +p_2) \end{aligned}$

所以乘法积的误差约等于

$p_1 +p_2$

2.14(p64)

编写测试程序：

(load "2.12.scm")
(load "helper.scm")

; parallel resistors
(define (par1 r1 r2)
  (div-interval (mul-interval r1 r2)
                (add-interval r1 r2)))

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

; test
; (define A (make-center-percent 100 0.0001))
; (define B (make-center-percent 200 0.0005))
(define A (make-interval 50 150))
(define B (make-interval 60 140))
(define C1 (par1 A A))
(newline)
(display "par1")
(print-interval C1)
(define C2 (par2 A A))
(newline)
(display "par2")
(print-interval C2)
(define D1 (par1 A B))
(newline)
(display "par1")
(print-interval D1)
(define D2 (par2 A B))
(newline)
(display "par2")
(print-interval D2)

得到如下结果：

par1
lower-bound: 8.333333333333334
upper-bound: 225.0
par2
lower-bound: 25.0
upper-bound: 75.0
par1
lower-bound: 10.344827586206897
upper-bound: 190.9090909090909
par2
lower-bound: 27.272727272727273
upper-bound: 72.41379310344827

2.15(p65)

结论正确，下面严格分析这个结论，假设我们用百分比表示法表示区间，设

$i= (x-px, x+ px)\triangleq x(1- p, 1+p)$

考虑两个区间

$\begin{aligned} i_1 &=x_1 (1-p_1, 1+p_1)\\ i_2 &= x_2 (1-p_2, 1+p_2) \end{aligned}$

所以

$\begin{aligned} \frac{i_1 i_2}{i_1 + i_2} &=\frac{ x_1x_2((1-p_1)(1-p_2), (1+p_1)(1+p_2) )}{(x_1+x_2)\left(1 - \frac{p_1 x_1 +p_2 x_2}{x_1 + x_2}, 1 +\frac{p_1 x_1 +p_2 x_2}{x_1 + x_2} \right)}\\ &=\frac{x_1 x_2}{x_1 +x_2} \left( \frac{(1-p_1)(1-p_2)}{1 +\frac{p_1 x_1 +p_2 x_2}{x_1 + x_2} }, \frac{(1+p_1)(1+p_2)}{1 -\frac{p_1 x_1 +p_2 x_2}{x_1 + x_2} }\right)\\ &= \left( \frac{x_1x_2(1-p_1)(1-p_2)}{ {x_1 + x_2} +{p_1 x_1 +p_2 x_2} }, \frac{x_1x_2(1+p_1)(1+p_2)}{ {x_1 + x_2} -p_1 x_1 -p_2 x_2}\right)\\ \frac{1}{1/i_1 + 1/i_2}&= \frac{1}{1/x_1 \times (1/ (1+p_1), 1/ (1- p_1)) +1/x_2 \times (1/ (1+p_2), 1/ (1- p_2))}\\ &= \frac 1 {\left(\frac 1{x_1(1+p_1)}, \frac 1{x_1(1-p_1)}\right) + \left(\frac 1{x_2(1+p_2)}, \frac 1{x_2(1-p_2)}\right)}\\ &= \left( \frac1{\frac 1{x_1(1-p_1)} + \frac 1{x_2(1-p_2)} },\frac 1 {\frac 1{x_1(1+p_1)} + \frac 1{x_2(1+p_2)} } \right)\\ &= \left( \frac {x_1x_2(1-p_1)(1-p_2)}{x_1(1-p_1)+x_2(1-p_2)},\frac {x_1x_2(1+p_1)(1+p_2)}{x_1(1+p_1)+x_2(1+p_2)}\right)\\ &= \left( \frac {x_1x_2(1-p_1)(1-p_2)}{x_1+x_2-p_1 x_1-p_2x_2}, \frac {x_1x_2(1+p_1)(1+p_2)}{x_1+x_2+p_1 x_1+p_2x_2} \right) \end{aligned}$

注意到

$\frac{x_1x_2(1-p_1)(1-p_2)}{ {x_1 + x_2} +{p_1 x_1 +p_2 x_2} } \le \frac {x_1x_2(1-p_1)(1-p_2)}{x_1+x_2-p_1 x_1-p_2x_2}\le \frac {x_1x_2(1+p_1)(1+p_2)}{x_1+x_2+p_1 x_1+p_2x_2}\le \frac{x_1x_2(1+p_1)(1+p_2)}{ {x_1 + x_2} -p_1 x_1 -p_2 x_2}$

所以par1的区间范围总比par2的区间范围大。

原答案（从误差分析角度考虑，供参考）：

这里只考虑$p\ll 1$的情形。

考虑

$\begin{aligned} i_1 + i_2 &= x_1 (1-p_1, 1+p_1) +x_2 (1-p_2, 1+p_2) \\ &=(x_1 + x_2 - p_1 x_1 -p_2 x_2, x_1 + x_2 + p_1 x_1+p_2 x_2)\\ &= (x_1+x_2)\left(1 - \frac{p_1 x_1 +p_2 x_2}{x_1 + x_2}, 1 +\frac{p_1 x_1 +p_2 x_2}{x_1 + x_2} \right)\\ i_1 \times i_2 &= x_1x_2(1-p_1-p_2 + p_1 p_2, 1+p_1+p_2 + p_1 p_2)\\ &\approx x_1x_2(1-p_1-p_2 , 1+p_1+p_2 )\\ \frac 1 {i_1}&= \frac{1}{x_1(1-p, 1+p)}\\ &\overset{泰勒展开}= \frac 1 {x_1} \left( 1+\sum_{i=1}p^i \times(-1)^i, 1+\sum_{i=1}p ^i\right)\\ & \approx \frac 1 {x_1} (1-p, 1+p) \end{aligned}$

所以

$\begin{aligned} \frac{i_1 i_2}{i_1 + i_2} &=\frac{ x_1x_2(1-p_1-p_2 , 1+p_1+p_2 )}{(x_1+x_2)\left(1 - \frac{p_1 x_1 +p_2 x_2}{x_1 + x_2}, 1 +\frac{p_1 x_1 +p_2 x_2}{x_1 + x_2} \right)}\\ &\approx \frac{x_1x_2}{x_1 + x_2}(1-p_1-p_2 , 1+p_1+p_2 )\left(1 - \frac{p_1 x_1 +p_2 x_2}{x_1 + x_2}, 1 +\frac{p_1 x_1 +p_2 x_2}{x_1 + x_2} \right) \\ &\approx\frac{x_1x_2}{x_1 + x_2} \left(1- \left(p_1+p_2+\frac{p_1 x_1 +p_2 x_2}{x_1 + x_2}\right), 1+\left(p_1+p_2+\frac{p_1 x_1 +p_2 x_2}{x_1 + x_2}\right)\right)\\ \frac{1}{1/{i_1} + 1/{i_2} } &\approx \frac{1}{\frac 1 {x_1} (1-p_1, 1+p_1) + \frac 1 {x_2} (1-p_2, 1+p_2)}\\ &= \frac{1}{ (\frac{1}{x_1 } -\frac{p_1}{x_1 }, \frac{1}{x_1 } +\frac{p_1}{x_1 })+ (\frac{1}{x_2 } -\frac{p_2}{x_2 }, \frac{1}{x_2 } +\frac{p_2}{x_2})}\\ &= \frac{1}{\left(\frac{1}{x_1 } +\frac{1}{x_2 } -\frac{p_1}{x_1 }-\frac{p_2}{x_2 }, \frac{1}{x_1 } +\frac{1}{x_2 } +\frac{p_1}{x_1 }+\frac{p_2}{x_2 } \right)}\\ &= \frac{x_1x_2}{x_1 + x_2} \left(1- \frac{\frac{p_1}{x_1}+\frac{p_2}{x_2 } }{\frac{1}{x_1 } +\frac{1}{x_2 } }, 1+\frac{\frac{p_1}{x_1}+\frac{p_2}{x_2 } }{\frac{1}{x_1 } +\frac{1}{x_2 } }\right)\\ &= \frac{x_1x_2}{x_1 + x_2} \left(1- \frac{ {p_1}{x_2}+{p_2}{x_2 } }{ {x_1 } +{x_2 } }, 1+\frac{ {p_1}{x_2}+{p_2}{x_2 } }{ {x_1 } +{x_2 } }\right) \end{aligned}$

上述约等于号均表示忽略了高阶项。

记

$\begin{aligned} p_a& = p_1+p_2+\frac{p_1 x_1 +p_2 x_2}{x_1 + x_2}\\ p_b & =\frac{ {p_1}{x_2}+{p_2}{x_2 } }{ {x_1 } +{x_2 } } \end{aligned}$

那么

$\begin{aligned} p_a-p_b& = \frac{1}{x_1 + x_2} \left((p_1+p_2)(x_1 + x_2) + p_1 x_1 +p_2 x_2-{p_1}{x_2}-{p_2}{x_2 }\right)\\ &= \frac{2(p_1 x_1 +p_2 x_2)}{x_1 + x_2}\\ &\ge 0 \end{aligned}$

所以方法1的误差总体来说较大。

2.16(p65)

参考资料：

https://stackoverflow.com/questions/14130878/sicp-2-16-interval-arithmetic-scheme

http://wiki.drewhess.com/wiki/SICP_exercise_2.16

https://en.wikipedia.org/wiki/Interval_arithmetic#Dependency_problem

https://zhuanlan.zhihu.com/p/45914836

https://www.xuebuyuan.com/1470405.html

域的定义：

https://zhuanlan.zhihu.com/p/102913021

原因解释：

该区间运算系统不满足域的定义（只考虑正数区间的情形），首先$1$元必然为$[1,1]$，对于$[a,b], a<b$，其逆元必然为$[1/b, 1/a]$，注意该区间不满足区间的定义（右端点大于等于左端点），由此可以推出不是每个元素都存在逆元，从而该运算系统不是域。

如果该系统是域，记区间分别为$i_1, i_2$，那么

$\begin{aligned} (i_1^{-1} +i_2^{-1})^{-1} & = (i_1 + i_2)^{-1} (i_1 i_2) \Leftrightarrow\\ (i_1 + i_2) & = (i_1 i_2)(i_1^{-1} +i_2^{-1})\Leftrightarrow\\ i_1 + i_2 & = i_1 + i_2 \end{aligned}$

此时两种电阻计算结果相同。

从这个角度来说，个人感觉无法设计出满足域性质的区间运算系统，但是有近似计算的方法。

记区间集合为$I$，一般的区间运算可以定义为：

$f:I^n \to I$

注意该运算实际上多元函数的推广：

$f:\mathbb R^n \to \mathbb R$

具体计算方法如下：

$\begin{aligned} A &= \{f(x_1,\ldots,x_n)| x_k \in i_k ,k=1,\ldots ,n\}\\ f(i_1,\ldots,i_n)&= [\min A, \max B] \end{aligned}$

按照定义，可以利用两种方法进行区间运算：

求$f(x_1,\ldots,x_n)$的极值点。
利用蒙特卡洛模拟的方法计算。

值的回顾的习题

2.6，2.15，2.16