这就是一初中代数题。
设有两个interval，分别为(c1, p1)和(c2, p2)。依题意c1,p1,c2,p2皆大于0，并且p1, p2小于1。
第一个interval范围是c1(1-p1)~c1(1+p1)。
第二个interval范围是c2(1-p2)~c2(1+p2)。
显然乘积interval的范围是c1c2(1-p1)(1-p2)~c1c2(1+p1)(1+p2)。
两值相减除以2得到误差为c1c2(p1+p2)，中值为c1c2(1+p1p2)。
乘积的percentage tolerance为(p1+p2)/(1+p1p2)。当p1p2都很小的时候，可以简化为p1+p2。
原来的做法做了四次乘法。新的方法只有一种情况需要做四次乘法。
(define (make-interval a b) (cons a b))
(define (upper-bound i) (cdr i))
(define (lower-bound i) (car i))
(define (mul-interval x y)
(let ((p1 (* (lower-bound x) (lower-bound y)))
(p2 (* (lower-bound x) (upper-bound y)))
(p3 (* (upper-bound x) (lower-bound y)))
(p4 (* (upper-bound x) (upper-bound y))))
(make-interval (min p1 p2 p3 p4)
(max p1 p2 p3 p4))))
; for every interval [l, u]
; there are 3 possibilities:
; 0 <= l <= u, abbreviated as ++
; l <= 0 <= u, abbreviated as -+
; l <= u <= 0, abbreviated as --
; so we have 9 cases:
; -------------------
; x | ++ | ++ | ++ |
; y | ++ | -+ | -- |
; -------------------
; x | -+ | -+ | -+ |
; y | ++ | -+ | -- |
; -------------------
; x | -- | -- | -- |
; y | ++ | -+ | -- |
; -------------------
(define (mul-interval x y)
(let ((xl (lower-bound x))
(xu (upper-bound x))
(yl (lower-bound y))
(yu (upper-bound y)))
(cond ((and (>= xl 0) (>= xu 0) (>= yl 0) (>= yu 0))
(make-interval (* xl yl) (* xu yu)))
((and (>= xl 0) (>= xu 0) (<= yl 0) (>= yu 0))
(make-interval (* xu yl) (* xu yu)))
((and (>= xl 0) (>= xu 0) (<= yl 0) (<= yu 0))
(make-interval (* xu yl) (* xl yu)))
((and (<= xl 0) (>= xu 0) (>= yl 0) (>= yu 0))
(make-interval (* xl yu) (* xu yu)))
((and (<= xl 0) (>= xu 0) (<= yl 0) (>= yu 0))
(make-interval (min (* xl yu) (* xu yl)) (max (* xl yl) (* xu yu))))
((and (<= xl 0) (>= xu 0) (<= yl 0) (<= yu 0))
(make-interval (* xu yl) (* xl yl)))
((and (<= xl 0) (<= xu 0) (>= yl 0) (>= yu 0))
(make-interval (* xl yu) (* xu yl)))
((and (<= xl 0) (<= xu 0) (<= yl 0) (>= yu 0))
(make-interval (* xl yu) (* xl yl)))
((and (<= xl 0) (<= xu 0) (<= yl 0) (<= yu 0))
(make-interval (* xu yu) (* xl yl))))))
其实这题应该直接用数学代数式推导，不应该用这种形式。
(define (make-interval a b) (cons a b))
(define (upper-bound i) (cdr i))
(define (lower-bound i) (car i))
(define (add-interval x y)
(make-interval (+ (lower-bound x) (lower-bound y))
(+ (upper-bound x) (upper-bound y))))
(define (mul-interval x y)
(let ((p1 (* (lower-bound x) (lower-bound y)))
(p2 (* (lower-bound x) (upper-bound y)))
(p3 (* (upper-bound x) (lower-bound y)))
(p4 (* (upper-bound x) (upper-bound y))))
(make-interval (min p1 p2 p3 p4)
(max p1 p2 p3 p4))))
(define (width-interval i)
(/ (-
(upper-bound i)
(lower-bound i))
2))
; for add-interval,
; the width of the result of combining two intervals
; is a function only of the widths of the argument intervals
; HOW TO prove that?
; we used an informal method
(width-interval
(add-interval x y))
; ->
(width-interval
(make-interval (+ (lower-bound x) (lower-bound y))
(+ (upper-bound x) (upper-bound y))))
; ->
(/ (-
(+ (upper-bound x) (upper-bound y))
(+ (lower-bound x) (lower-bound y))) 2)
; ->
(/ (+
(- (upper-bound x) (lower-bound x))
(- (upper-bound y) (lower-bound y))) 2)
; ->
(+
(/ (- (upper-bound x) (lower-bound x)) 2)
(/ (- (upper-bound y) (lower-bound y)) 2))
; ->
(+
(width-interval x)
(width-interval y))
; to show that for mul-interval,
; the width of the result of combining two intervals
; is NOT a function only of the widths of the argument intervals
(width-interval
(mul-interval (make-interval 0 2)
(make-interval 1 3)))
(width-interval
(mul-interval (make-interval 1 3)
(make-interval 1 3)))
(define (upper-bound i) (cdr i))
(define (lower-bound i) (car i))
我习惯把小的放左边。默认了这种行为，没做检查。
老潘早就知道丘奇数不好惹，反正第一次看的时候就觉得很费脑子。但这次终于绕不过去了必须得弄明白。。。真不知道我提前知道了一些lambda calculus是好还是不好，因为我实际上不用推那个add-1就知道one应该怎么写。。。我就当这是好事了~毕竟这道题并不是让你理解substitution model，而是理解“用过程表示数据”。啊！我突然明白大家说Lisp里面代码就是数据原来还有这层意思，太tm狡猾了！！！
; *zero* is a (higher-order) function "(lambda (f) (lambda (x) x)" that
; takes a function as the sole argument (f),
; and returns another function "(lambda (x) x)"
; which applies f on its sole argument (x) 0 times
; we can see x is actually a dummy...
(define zero
(lambda (f) (lambda (x) x)))
; we clearly see that, the approach is to represent numbers by functions
; if we apply *number* functions to a function f,
; we get a function that repeatly applies f to its argument *number* times.
; that is, (n f) evaluates to a function which repeatly applies f to its argument n times.
; so ((n f) x) is the result of repeatly applying f to x n times
; (f ((n f) x)) is the result of repeatly applying f to x (n + 1) times
; *add-1* is a (higher-order) function that
; takes a function (representing a number) as the sole argument (n),
; and returns another function (representing a number) "(lambda (f) (lambda (x) (f ((n f) x))))",
; which takes a function as the sole argument (f),
; and returns another function "(lambda (x) (f ((n f) x)))",
; which actually applies f on x (n + 1) times
; so *add-1* returns the function representing n + 1
(define (add-1 n)
(lambda (f) (lambda (x) (f ((n f) x)))))
; if we take the advice and use the substitution model...
; one is (add-1 zero)
(add-1 zero)
(add-1 (lambda (f) (lambda (x) x)))
(lambda (f) (lambda (x) (f (((lambda (f) (lambda (x) x)) f) x))))
(lambda (f) (lambda (x) (f ((lambda (x) x) x))))
(lambda (f) (lambda (x) (f x)))
; so one is...
(define one
(lambda (f) (lambda (x) (f x))))
; and two...
(define two
(lambda (f) (lambda (x) (f (f x)))))
; and plus...
(define (+ a b)
(lambda (f) (lambda (x) ((b f) ((a f) x)))))
核心思想是用function表示正整数。
从0开始：0是一个高阶函数，它的唯一参数是函数f，f亦只有一个参数（虽然我们单从这里看不出来，但没办法我就是知道！），输出是另一个函数out（是个lambda!），out还是只有一个参数x，其作用是把x作为f的参数，执行零次。有0就有1。1唯一的不同就是最后那下执行一次。有1就有2，2就是最后那下执行两次。。。注意这里面的执行是把前一次执行得到的结果作为后一次执行的参数，就好比(f (f (f ... (f x)...)))。
注意 使用这种方式，正整数n这个信息就隐藏或者说保存在执行“输出函数out”时，执行f的次数中。。。比如我们想知道这个信息，我们可以先执行n，这样就得到了out。然后我们执行out，假如我们执行n时传入的f有记录自己被执行了多少次的功能（比如每执行一次就把一个全局变量加1），我们就能extract这个信息出来，对不？你看你看：
(define count 0)
(define two
(lambda (f) (lambda (x) (f (f x)))))
((two (lambda (x) (set! count (+ 1 count)))) 'x)
(print count)
当然我们一般不需要这么做。这么做相当于一种信息格式的转换 - 把用函数表示的数，转成了我们一般认知的数。信息自然是没丢，但要是你所有用来操作数的过程都使用“函数”这个格式（比如lambda calculus里），你转它做什么？
说句题外话，其实lambda calculus里所有的东西，包括数，都是函数；而所有的函数都只有一个参数，你要不服只能用curry这个技术。
(define (cons x y)
(* (expt 2 x) (expt 3 y)))
(define (keep-divide-until-remainder-not-zero remain count divisor predicate?)
(if (predicate? remain)
count
(keep-divide-until-remainder-not-zero (/ remain divisor) (+ count 1) divisor predicate?)))
; when dividing by 2, we use odd? to determine if we may go on dividing
; false means we can go on
(define (car z)
(keep-divide-until-remainder-not-zero z 0 2 odd?))
; when dividing by 3, we see if the remainder of the division is 0,
; to determine if we may go on dividing
; false means we can go on
(define (cdr z)
(keep-divide-until-remainder-not-zero z 0 3
(lambda (m) (if (eq? (remainder m 3) 0) #f #t))))
(define c (cons 5 6))
(car c)
(cdr c)
这题让我们内部用2^a3^b来储存a和b。之后我们用这个积能够被2或3连续整除的次数来得到a和b。
SICP讲到有趣的东西了：用过程表示数据。
(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)))
"...Consider the notion of a pair, which we used in order to define our rational numbers. We never actually said what a pair was, only that the language supplied procedures cons, car, and cdr for operating on pairs. But the only thing we need to know about these three operations is that if we glue two objects together using cons we can retrieve the objects using car and cdr. That is, the operations satisfy the condition that, for any objects x and y, if z is (cons x y) then (car z) is x and (cdr z) is y. Indeed, we mentioned that these three procedures are included as primitives in our language. However, any triple of procedures that satisfies the above condition can be used as the basis for implementing pairs."
书中讲到的constructors and selectors构成了abstracton barriers，说白了就是数据抽象与外部的接口。通过定义constructors and selectors，数据结构的内部实现被隔离开来-可以单独改变它，而不影响client code。
觉得constructors and selectors简直就是OO里面的。。。
弄清了这些，2.3这道题基本上就是说，设计出不同的数据结构表示平面上的矩形，但要提供一样的constructors and selectors，以便计算周长和面积的client code不会break。嗯嗯。。。
; constructor and selectors, 1st implementation
; well, we may represent the rectangle in terms of
; 2 orthogonal segments sharing one end
(define (make-rec seg1 seg2)
(cons seg1 seg2))
; or (define make-rec cons)
(define (seg1 rec)
(car rec))
; or (define seg1 car)
(define (seg2 rec)
(cdr rec))
; or (define seg2 cdr)
; constructor and selectors, 2nd implementation
; on the other hand, we can just save the 4 points
; of the 2 orthogonal segments
(define (make-rec seg1 seg2)
(list (start-segment seg1) (end-segment seg1)
(start-segment seg2) (end-segment seg2)))
(define (seg1 rec)
(cons (car rec) (cadr rec)))
(define (seg2 rec)
(cons (caddr rec) (cadddr rec)))
; constructor and selectors, 3rd implementation
; as another alternative way, we can save one segment
; with the angle whose value is seg1/seg2
(define (make-rec seg1 seg2)
(cons seg1 seg1/seg2))
(define (seg1 rec)
(car rec))
(define (seg2 rec)
(/ (car rec) (cdr rec)))
;------------------------------
(define (perimeter rec)
(define (len seg)
(sqrt
(+
(sqr (- (caar seg) (cadr seg)))
(sqr (- (cdar seg) (cddr seg))))))
(* 2 (len (seg1 rec) (seg2 rec))))
(define (area rec)
(* (seg1 rec) (seg2 rec)))
第一种是简单的记录两条临边，第二种记录了两个临边的四个点，第三种貌似是记录了一个边和一个角，但其本质还是俩临边。为什么我想起了银魂里的冬佩利？？总之明白主旨就行了。。。
在语言级别支持AOP就是爽！不过这里面的规则超级复杂啊啊啊啊啊啊！！！记不住只好写下来。要理解这些，首先要明白Python中的type和class（new-style class已经和type统一了）自身也是在程序空间中可以被操纵的object。
主要手段有：
__get__和__set__(其实还有__delete__)
__getattr__(类似method missing)
__setattr__（虽然和上边那个长得像，但其实这俩很不一样，不放一起）
__getattribute__（和__setattr__一样都是终极大法）
1. __get__和__set__ 是定义在descriptor(http://docs.python.org/tut/node18.html)的class/type中的。
Any new-style object that defines the methods __get__(), __set__(), or __delete__(). When a class attribute is a descriptor, its special binding behavior is triggered upon attribute lookup. Normally, writing a.b looks up the object b in the class dictionary for a, but if b is a descriptor, the defined method gets called. Understanding descriptors is a key to a deep understanding of Python because they are the basis for many features including functions, methods, properties, class methods, static methods, and reference to super classes.
先说说怎么正确定义descriptor。下文说的class都是new-style的。那些descriptor的特殊方法（__get__, __set__, __delete__)必须定义为class/type object attribute，之后通过实例化得到这些方法的instance object，才被视作descriptor。换句话说，假如我就搞一个object出来，在上面直接安一个__get__，此object将不被视作descriptor（所以，定义了这三个方法的class/type object本身并不是descriptor。上面的英文描述并不完全准确。我太刨根问底儿了）。
光有了descriptor还不行，descriptor只有作为class/type object attribute才起作用。直接在某object上安一个descriptor，是达不到目的的。
这些都做好了之后，才是怎么引发那三个特殊方法。如果前面做的都对，那么从在instance object上对descriptor做reference, bind/rebind, 和unbind操作，会分别引发__get__, __set__, 和__delete__。此外，在class/type object上对descriptor做的reference操作也会引发__get__。
规则好复杂。。。龙与地下城的感觉又回来了，口胡。
2. __getattr__，__setattr__，以及__getattribute__
这三个也是必须定义为class/type object attribute，通过实例化得到这些方法的instance object，当其attribute被bind/rebind时，会被__setattr__拦截。当instance attribute被reference并且没找到时，触发__getattr__。
__getattribute__则拦截所有instance attribute reference，并且优先于__getattr__。后面我会说为什么。
3. 如果1和2同时出现。。。然后我们从instance object去bind/rebind或者reference那个descriptor的attribute:
bind/rebind时，__setattr__优先；reference时，既然有了descriptor，那肯定不会attribute找不到，因此__getattr__不会被调。但是__getattribute__仍优先于descriptor的__get__。
其实所谓谁优先什么的，嘿嘿，__getattribute__和__setattr__都是定义在built-in的object里面的。实际上descriptor包括__getattr__那些小把戏就是它们俩实现的。。。所以你把它们俩override以后，descriptor当然就不管用了。不信你在你的__getattribute__/__setattr__里面调object的那个，descriptor就又会冒出来了。。。看我下面最后一个测试代码，里面有。
也就是说只有__getattribute__和__setattr__是需要解释器特殊支持的，别的都可以用这俩实现。上面我说的那些优先级根本不用记。只要规则记住了就能用好这些。
强烈建议Guido把__setattr__改成__setattribute__。。。现在这样不是添乱麽！
测试代码：
test_descriptor.py test_getsetattr.py test_getsetattr_and_descriptor.py
http://effbot.org/zone/import-confusion.htm
虽然这里讲了一些，但是要想完全明白，就得理解Python module也是object：和所有的instance，class/type一样。另外还要明白，当一个Module被import时，其中的statement被执行。
