ch02 构造数据抽象 part01
对于方程：
\[ ax + by \]可以简单实现过程：
(define (linear-combination a b x y) (+ (* a x) (* b y)))
但是这里的+与*只能处理整数。
如果把「加法」与「乘法」抽象出来，让它们可以也可以处理有理数、复数、多项式等类型 的其他内容，过程的泛用性将大大增强：
(define (linear-combination a b x y) (add (mul a x) (mul b y)))
数据抽象导引
- 程序中不对数据做多余的假设。
- 数据的具体定义应该与程序中使用数据的方式无关。
连接程序和数据的界面应该只有「构造函数」和「选择函数」这两类过程。
实例：有理数的算术运算
构造函数与选择函数：
-
构造函数：
(make-rat <n> <d>)返回一个有理数，分子n，分母d -
选择函数：
(number <x>)返回有理数x的分子 -
选择函数：
(denom <x>)返回有理数x的分母
分子、分母组成有理数。运算规则：
\[ \begin{equation} \begin{split} \frac{n_1}{d_1} + \frac{n_2}{d_2} &= \frac{n_1d_2 + n_2d_1}{d_1d_2} & \\ \frac{n_1}{d_1} - \frac{n_2}{d_2} &= \frac{n_1d_2 - n_2d_1}{d_1d_2} & \\ \frac{n_1}{d_1} \times \frac{n_2}{d_2} &= \frac{n_1n_2}{d_1d_2} & \\ \frac{n_1}{d_1} \div \frac{n_2}{d_2} &= \frac{n_1d_2}{d_1n_2} & \\ \frac{n_1}{d_1} &= \frac{n_2}{d_2} & \text{当且仅当$n_1d_2 = n_2d_1$} \\ \end{split} \end{equation} \]序对操作
-
cons建立一个序对（二元组）。 -
car取出第一个元素。「Contents of Address part of Register」 （寄存器地址部分的内容）。 -
cdr取出第二个元素。「Contents of Decrement part of Register」 （寄存器减量部分的内容），读作「could-er」。 -
pair?检查参数是否为序对。
简单的缩写可以嵌套。比如：
-
通过
caar来代替「在car的结果上调用car」 -
cdar来代替（在car的结果上调用cdr）
这种c...r风格的缩写，最多允许四层套嵌。因此cadr,cdadr,cdaddr都是
可以使用的，而cdadadr则可能无法使用。
(define x (cons 1 2)) (car x) ; 1 (cdr x) ; 2 (define x (cons 1 2)) (define y (cons 3 4)) (define z (cons x y)) (car (car z)) ; 1 (car (cdr z)) ; 3
有理数表示
(define (make-rat n d) (cons n d)) ; 构造有理数 (define (numer x) (car x)) ; 取分子 (define (denom x) (cdr x)) ; 取分母
可以看到函数体直接调用了三个方法，所以可以直接给这三个方法建别名也可以：
(define make-rat cons) (define numer car) (define denom cdr)
- 使用别名的优点：别名不是过程，所以少一层过程包装。
-
使用别名的缺点：因为
make-rat其实是cons别名，所以如果在调试过程中追踪make-rat的话会追踪所有的cons。
考虑到缺点，所以这里不用别名，用定义过程包装。
再定义显示分数的方法：
(define (print-rat x) ; 格式化显示，如： 3/4 (newline) (display (numer x)) (display "/") (display (denom x)))
注意这里还少了约分这一步骤：
(define one-half (make-rat 1 2)) (print-rat one-half) ; 1/2 (define one-third (make-rat 1 3)) (print-rat (add-rat one-half one-third)) ; 5/6 (print-rat (mul-rat one-half one-third)) ; 1/6 (print-rat (add-rat one-third one-third)) ; 6/9
强化make-rat方法，加入约分：
(define (make-rat n d)
(let ((g (gcd n d)))
(cons (/ n g) (/ d g))))
练习 2.1
强化make-rat来处理负数。
根据有理数的负数处理规则：
\(\frac{-n}{-d} = \frac{n}{d}\) \(\frac{n}{-d} = \frac{-n}{d}\)
;;; 1-make-rat.scm (define (make-rat n d) (if (< d 0) (cons (- n) (- d)) (cons n d)))
抽象屏障
通过多层抽象，屏蔽内部的细节。
练习 2.2
平面上的线段，用起点s与终点e表示。还有线段的中点m。
打印的方法为：
(define (print-point p)
(newline)
(display "(")
(display (x-point p))
(display ",")
(display (y-point p))
(display ")"))
线段的构造函数和选择函数定义如下：
;;; 2-segment-constructor.scm
(define (make-segment start-point end-point)
(cons start-point end-point))
取得起步与终点：
;;; 2-segment-selector.scm
(define (start-segment seg)
(car seg))
(define (end-segment seg)
(cdr seg))
点的构造函数和选择函数定义如下：
;;; 2-point-constructor.scm
(define (make-point x y)
(cons x y))
;;; 2-point-selector.scm
(define (x-point p)
(car p))
(define (y-point p)
(cdr p))
线段的中点可以通过以下公式计算得出：
\[ \left(\frac{x_{start} + x_{end}}{2} , \frac{y_{start} + y_{end}}{2}\right) \]相应的函数定义如下：
;;; 2-midpoint-segment.scm
(load "2-segment-selector.scm")
(load "2-point-constructor.scm")
(load "2-point-selector.scm")
(define (midpoint-segment seg)
(let ((start (start-segment seg))
(end (end-segment seg)))
(make-point (average (x-point start)
(x-point end))
(average (y-point start)
(y-point end)))))
(define (average x y)
(/ (+ x y)
2.0))
最后，把题目给出的打印点的函数也敲下来：
;;; 2-print-point.scm
(load "2-point-selector.scm")
(define (print-point p)
(newline)
(display "(")
(display (x-point p))
(display ",")
(display (y-point p))
(display ")"))
测试
(load "2-point-constructor.scm") (load "2-point-selector.scm") (load "2-segment-constructor.scm") (load "2-segment-selector.scm") (load "2-midpoint-segment.scm") (load "2-print-point.scm") 1 ]=> (define start (make-point 1 3)) ;Value: start 1 ]=> (define end (make-point 4 3)) ;Value: end 1 ]=> (define seg (make-segment start end)) ;Value: seg 1 ]=> (define mid (midpoint-segment seg)) ;Value: mid 1 ]=> (print-point mid) (2.5,3.) ;Unspecified return value
练习 2.3
设计矩形实现，周长、面积。
我们可以首先写出两种不同的矩形实现，然后再进行面积和周长的计算。
但是，有一个更好的办法，那就是，先不考虑矩形的具体实现，而是使用按愿望思维的 方式，假设已经有某种制造出矩形的办法，以及以下两个选择函数：
-
length-of-rectangle接受一个矩形作为参数，并返回矩形的长的长度 -
width-of-rectangle接受一个矩形作为参数，并返回矩形的宽的长度
有了这两个函数的话，我们就可以根据公式来计算给定矩形的周长和面积了。
周长
矩形的周长可以通过以下公式计算：
\[ perimeter = 2 \times (length+width) \]相应的周长计算函数的定义如下：
;;; 3-perimeter.scm
(define (perimeter-rectangle r)
(let ((length (length-of-rectangle r))
(width (width-of-rectangle r)))
(* 2
(+ length width))))
面积
矩形的面积可以通过以下公式计算：
\[ area = length \times width \]相应的面积计算函数的定义如下：
;;; 3-area.scm
(define (area-rectangle r)
(* (length-of-rectangle r)
(width-of-rectangle r)))
矩形表示(1)：使用两对线段
在前面我们给出了计算矩形的周长和面积的函数，是时候来考虑如何去实现矩形了。
最直观的表示矩形的方法是使用两对线段，一对表示矩形的长，另一对表示矩形的宽。
以下就是一个采用这种表示的矩形，其中矩形的长为一对长度为 3 的线段，而矩形的宽 则是一对长度为 2 的线段：
y
5
(1,4) l1 (4,4)
4 +--------------+
| |
3 w1 | | w2
| |
2 +--------------+
(1,2) l2 (4,2)
1
0 1 2 3 4 5 x
其中 l1 的起点为\((1,4)\)，终点为\((4,4)\)，而 l2 的起点为\((1,2)\)，终点为\((4,2)\)； w1 的起点为\((1,2)\)，终点为\((1,4)\)； w2 的起点为\((4,2)\)，终点为\((4,4)\)。
以下是这种表示相对应的构造函数和选择函数：
;;; 3-rectangle-represent.scm
;; constructor
(define (make-rectangle length-1 length-2 width-1 width-2)
(cons (cons length-1 length-2)
(cons width-1 width-2)))
;; selector
(define (length-1-rectangle r)
(car (car r)))
(define (length-2-rectangle r)
(cdr (car r)))
(define (width-1-rectangle r)
(car (cdr r)))
(define (width-2-rectangle r)
(cdr (cdr r)))
虽然有了矩形的构造函数和选择函数，但是我们还需要借用 练习 2.2 的线段和点的表示 ，才能构造一个完整的矩形表示：
1 ]=> (load "2-point-constructor.scm")
;Loading "2-point-constructor.scm"... done
;Value: make-point
1 ]=> (load "2-point-constructor.scm")
;Loading "2-point-constructor.scm"... done
;Value: make-point
1 ]=> (load "2-segment-constructor.scm")
;Loading "2-segment-constructor.scm"... done
;Value: make-segment
1 ]=> (load "2-segment-selector.scm")
;Loading "2-segment-selector.scm"... done
;Value: end-segment
1 ]=> (load "3-rectangle-represent.scm")
;Loading "3-rectangle-represent.scm"... done
;Value: width-2-rectangle
1 ]=> (define length-1 (make-segment (make-point 1 4)
(make-point 4 4)))
;Value: length-1
1 ]=> (define length-2 (make-segment (make-point 1 2)
(make-point 4 2)))
;Value: length-2
1 ]=> (define width-1 (make-segment (make-point 1 2)
(make-point 1 4)))
;Value: width-1
1 ]=> (define width-2 (make-segment (make-point 4 2)
(make-point 4 4)))
;Value: width-2
1 ]=> (define rectangle (make-rectangle length-1 length-2 width-1 width-2))
;Value: rectangle
1 ]=> rectangle
;Value 11: ((((1 . 4) 4 . 4) (1 . 2) 4 . 2) ((1 . 2) 1 . 4) (4 . 2) 4 . 4)
测试代码的最后，打印出的矩形信息非常不好看，说明我们还需要写一个打印矩形信息的 函数：
;;; 3-print-rectangle.scm (load "2-segment-selector.scm") (load "2-print-point.scm") (define (print-rectangle r) (let ( (l1 (length-1-rectangle r)) (l2 (length-2-rectangle r)) (w1 (width-1-rectangle r)) (w2 (width-2-rectangle r))) (newline) (display "Length 1:") (print-point (start-segment l1)) (print-point (end-segment l1)) (newline) (display "Length 2:") (print-point (start-segment l2)) (print-point (end-segment l2)) (newline) (display "Width 1:") (print-point (start-segment w1)) (print-point (end-segment w1)) (newline) (display "Width 2:") (print-point (start-segment w2)) (print-point (end-segment w2))))
载入打印函数，重新打印前面代码中的矩形表示：
1 ]=> (load "3-print-rectangle.scm") ;Loading "3-print-rectangle.scm"... ; Loading "2-segment-selector.scm"... done ; Loading "2-print-point.scm"... ; Loading "2-point-selector.scm"... done ; ... done ;... done ;Value: print-rectangle 1 ]=> (print-rectangle rectangle) Length 1: (1,4) (4,4) Length 2: (1,2) (4,2) Width 1: (1,2) (1,4) Width 2: (4,2) (4,4) ;Unspecified return value
现在的打印比之前解释器默认的打印信息清晰多了（虽然还是不怎么好看）。
矩形表示(1)：长和宽
要计算周长和面积，我们还缺少length-of-rectangle和width-of-rectangle两个函数
，因为目前的表示使用线段构成，因此通过计算线段的长度，就可以给出相应的边的长度
。
以下是相应的函数实现：
;;; 3-length-and-width-of-rectangle.scm (load "3-rectangle-represent.scm") (load "2-segment-selector.scm") (define (length-of-rectangle r) (let ((length (length-1-rectangle r))) (let ((start (start-segment length)) (end (end-segment length))) (- (x-point end) (x-point start))))) (define (width-of-rectangle r) (let ((width (width-1-rectangle r))) (let ((start (start-segment width)) (end (end-segment width))) (- (y-point end) (y-point start)))))
对前面定义的矩形变量进行测量：
1 ]=> (load "3-length-and-width-of-rectangle.scm") ;Loading "3-length-and-width-of-rectangle.scm"... ; Loading "3-rectangle-represent.scm"... done ; Loading "2-segment-selector.scm"... done ;... done ;Value: width-of-rectangle 1 ]=> (width-of-rectangle rectangle) ;Value: 2 1 ]=> (length-of-rectangle rectangle) ;Value: 3
计算的长和宽都正确，现在可以载入前面定义的周长和面积函数，进行测试了：
1 ]=> (load "3-perimeter.scm") ;Loading "3-perimeter.scm"... done ;Value: perimeter-rectangle 1 ]=> (perimeter-rectangle rectangle) ;Value: 10 1 ]=> (load "3-area.scm") ;Loading "3-area.scm"... done ;Value: area-rectangle 1 ]=> (area-rectangle rectangle) ;Value: 6
矩形表示(2)：使用两条线段
矩形的另一种表示方式是，只使用两条边，一条表示长，一条表示宽。
以下就是一个采用这种表示的矩形，其中矩形的长为一条长度为 3 的线段，而矩形的宽 则是一条长度为 2 的线段：
y
5
(1,4)
4 +
|
3 | width
|
2 +--------------+
(1,2) length (4,2)
1
0 1 2 3 4 5 x
其中 length 的起点为 (1,2) ，终点为 (4,2) ， width 的起点为 (1,2) ，终点为 (1,4) 。
以下是这种表示相对应的构造函数和选择函数：
;;; 3-another-rectangle-represent.scm
(define (make-rectangle length width)
(cons length width))
(define (length-rectangle r)
(car r))
(define (width-rectangle r)
(cdr r))
以及和这种表示相对应的length-of-rectangle和width-of-rectangle：
;;; 3-another-length-and-width-of-rectangle.scm (load "2-segment-selector.scm") (load "2-point-selector.scm") (load "3-another-rectangle-represent.scm") (define (length-of-rectangle r) (let ((length (length-rectangle r))) (let ((start (start-segment length)) (end (end-segment length))) (- (x-point end) (x-point start))))) (define (width-of-rectangle r) (let ((width (width-rectangle r))) (let ((start (start-segment width)) (end (end-segment width))) (- (y-point end) (y-point start)))))
使用新表示来创建矩形：
1 ]=> (load "3-another-rectangle-represent.scm")
;Loading "3-another-rectangle-represent.scm"... done
;Value: width-rectangle
1 ]=> (load "3-another-length-and-width-of-rectangle.scm")
;Loading "3-another-length-and-width-of-rectangle.scm"...
; Loading "2-segment-selector.scm"... done
; Loading "3-another-rectangle-represent.scm"... done
;... done
;Value: width-of-rectangle
1 ]=> (load "2-segment-constructor.scm")
;Loading "2-segment-constructor.scm"... done
;Value: make-segment
1 ]=> (load "2-point-constructor.scm")
;Loading "2-point-constructor.scm"... done
;Value: make-point
1 ]=> (define l (make-segment (make-point 1 2)
(make-point 4 2)))
;Value: l
1 ]=> (define w (make-segment (make-point 1 2)
(make-point 1 4)))
;Value: w
1 ]=> (define r (make-rectangle l w))
;Value: r
计算长和宽的长度：
1 ]=> (load "3-another-length-and-width-of-rectangle.scm") ;Loading "3-another-length-and-width-of-rectangle.scm"... ; Loading "2-segment-selector.scm"... done ; Loading "2-point-selector.scm"... done ; Loading "3-another-rectangle-represent.scm"... done ;... done ;Value: width-of-rectangle 1 ]=> (length-of-rectangle r) ;Value: 3 1 ]=> (width-of-rectangle r) ;Value: 2
计算周长和面积：
1 ]=> (load "3-perimeter.scm") ;Loading "3-perimeter.scm"... done ;Value: perimeter-rectangle 1 ]=> (perimeter-rectangle r) ;Value: 10 1 ]=> (load "3-area.scm") ;Loading "3-area.scm"... done ;Value: area-rectangle 1 ]=> (area-rectangle r) ;Value: 6
两种实现
可以看到，在两种不同的矩形表示中切换时，相应的周长和面积计算函数完全不必修改， 我们只要写好不同实现所需的构造函数和选择函数就行了。
数据意味着什么
数据可以被定义为一组适当的选择函数与构造函数，这些过程必须满足一组特定的条件 才能合法表示。（Hoare的「抽象模型」方法与MIT的「代数规范」）
比如可以完全不用数据结构，只用过程来重新实现序对：
(define (cons x y) (define (dispatch m) (cond ((= m 0) x) ((= m 1) y) (else (error "Argument not 0 or 1 -- CONS" m)))) dispatch) (define (car z) (z 0)) (define (cdr z) (z 1))
注意上面cons的返回值为dispatch方法，它的功能是从两个元素中选一个返回。
上面的实现只要能验证满足序对的所有条件，就是合法的序对的合法实现（证明过程略）。
练习 2.4
题目给出的定义：
;;; 4-cons-and-car.scm (define (cons x y) (lambda (m) (m x y))) (define (car z) (z (lambda (p q) p)))
对应的cdr应该如何定义？（使用1.1.5节的代换模型）
表达式(car (cons 1 2))的展开序列如下：
(car (cons 1 2)) (car (lambda (m) (m 1 2))) ; 展开 cons ((lambda (z) (z (lambda (p q) p))) ; 展开 car ，代换 z (lambda (m) (m 1 2))) ((lambda (m) (m 1 2)) ; 代换 m (lambda (p q) p)) ((lambda (p q) p) ; 代换 p 1 2) 1
根据car的定义，以及上面的展开序列给出的线索，我们可以写出对应的cdr函数：
;;; 4-cdr.scm (define (cdr z) (z (lambda (p q) q)))
表达式(cdr (cons 1 2))的展开序列如下：
(cdr (cons 1 2)) (cdr (lambda (m) (m 1 2))) ; 展开 cons ((lambda (z) (z (lambda (p q) q))) ; 展开 cdr ，代换 z (lambda (m) (m 1 2))) ((lambda (m) (m 1 2)) ; 代换 m (lambda (p q) q)) ((lambda (p q) q) 1 2) ; 代换 q 2
测试：
1 ]=> (load "4-cons-and-car.scm") ;Loading "4-cons-and-car.scm"... done ;Value: car 1 ]=> (load "4-cdr.scm") ;Loading "4-cdr.scm"... done ;Value: cdr 1 ]=> (cdr (cons 1 2)) ;Value: 2
练习 2.5
把a与b的序对表示为乘积\(2^a\)与\(3^b\)对应的整数，就可以用非负整数和算术运算
表示序对。给出cons、car和cdr的定义。
根据题意，构造函数cons的定义可以直接返回两个乘幂之间的乘积：
;;; 5-cons.scm (define (cons x y) (* (expt 2 x) (expt 3 y)))
测试cons，可以看到它返回的是乘积：
(load "5-cons.scm") (cons 3 2) ;Value: 72
car和cdr
根据基本算术定理，每个正整数都可以被分解为唯一的素数相乘序列，我们可以利用
这一点，通过分解cons计算出的整数的序列，从而复原car和cdr。
举个例子， 72可以分解成
\[ 72 = 2^3 \times 3^2 = 2 \times 2 \times 2 \times 3 \times 3 \]
要取出car，我们就不断地进行除二操作，每次除二进行一次计数，直到不能除尽为止，
这时的计数值就是car的值：
;;; 5-car.scm (define (car z) (if (= 0 (remainder z 2)) (+ 1 (car (/ z 2))) 0))
另一方面，要取出cdr，我们就不断地进行除三操作，每次除三进行一次计数，直到
不能除尽为止，这时的计数值就是cdr的值：
;;; 5-cdr.scm (define (cdr z) (if (= 0 (remainder z 3)) (+ 1 (cdr (/ z 3))) 0))
测试
(load "5-cons.scm") (load "5-car.scm") (load "5-cdr.scm") (define x (cons 3 2)) ;Value: x x ;Value: 72 (car x) ;Value: 3 (cdr x) ;Value: 2
练习 2.6
在没有数字这个数据结构和程序语言里，用过程实现数字。
Church计数法（\(\lambda\)演算的发明人Alonzo Church）。在不用数（非负数情况下）的 限制下，把数字0与操作\(+1\)实现为：
(define zero (lambda (f) (lambda (x) x))) (define (add-1 n) (lambda (f) (lambda (x) (f ((n f) x)))))
请直接定义one与two（不用zero和add-1）（提示：利用代换去求值
(add-1 zero)）。请给出加法过程+的一个直接定义（不要反复应用add-1）。
one
\(1=0+1\)，所以one定义可以通过展开(add-1 zero)来获得：
(add-1 zero)
分别代入add-1与zero的定义：
((lambda (n) ; 代入add-1的定义 (lambda (f) (lambda (x) (f ((n f) x))))) (lambda (f) ; 代入zero的定义 (lambda (x) x)))
把zero的定义作为实参代入add-1的形参n：
(lambda (f) (lambda (x) (f (((lambda (f) ; zero代入n (lambda (x) x)) f) x))))
实参f代入：
(lambda (f) (lambda (x) (f ((lambda (x) x) x))))
(lambda (f) (lambda (x) (f x)))
经过展开得出one的定义为：
(define one (lambda (f) (lambda (x) (f x))))
two
可以继续使用add-1和刚得到的one定义来得到two的定义，展开(add-1 one)
的调用即可：
(add-1 one)
(add-1 (lambda (f)
(lambda (x)
(f x))))
((lambda (n) ; add-1
(lambda (f)
(lambda (x)
(f ((n f) x)))))
(lambda (f) ; one
(lambda (x)
(f x))))
(lambda (f)
(lambda (x)
(f ((
(lambda (f) ; one
(lambda (x)
(f x)))
f)
x))))
(lambda (f)
(lambda (x)
(f ((lambda (x)
(f x))
x))))
(lambda (f)
(lambda (x)
(f (f x))))
经过展开得出 two 的定义为：
(define two
(lambda (f)
(lambda (x)
(f (f x)))))
加法函数
通过对比zero、one和two的定义，我们可以发现，它们都接受两个参数f和x，
不同的地方在于函数体内调用f的次数：
(define zero
(lambda (f)
(lambda (x)
x))) ; 没有 f
(define one
(lambda (f)
(lambda (x)
(f x)))) ; 一个 f 调用
(define two
(lambda (f)
(lambda (x)
(f (f x))))) ; 两个 f 调用
因此，我们有理由相信，three和four的定义很可能是：
(define three
(lambda (f)
(lambda (x)
(f (f (f x)))))) ; 三个 f 调用
(define four
(lambda (f)
(lambda (x)
(f (f (f (f x))))))) ; 四个 f 调用
继续推广这一规则，我们就得出了 Church 计数表示(非负)整数的一般规则：
-
从
zero的定义开始，每次数值加一时，函数体内都会增加一个(嵌套的)f函数的调用； -
当两个 Chruch 数相加时，它们的和就等于累积起两个过程中的
f调用。
比如说，(+ 3 2)的计算过程可以展开为：
(+ 3 2)
(+ (lambda (f)
(lambda (x)
(f (f (f x)))))
(lambda (f)
(lambda (x)
(f (f x)))))
; ...
(lambda (f)
(lambda (x)
(f (f (f (f (f x)))))))
根据这个规则，可以写出相应的 Church 计数的加法函数：
(define +
(lambda (m)
(lambda (n)
(lambda (f)
(lambda (x)
(m f (n f x)))))))
加法函数接受两个参数m和n，然后返回一个接受两个参数f和x的函数，加法函数
的函数体内，n的函数体被表达式(n f x)取了出来，然后又在表达式(m f (n f x))
中作为函数m的第二个函数被调用，从而将m和n函数体内的f调用累积起来
（如果有的话），从而形成加法效果。
一个详细的加法展开例子
(+ 2 1)
((lambda (m) ; 展开 +
(lambda (n)
(lambda (f)
(lambda (x)
(m f (n f x))))))
2
1)
((lambda (n) ; 将 2 应用到参数 m
(lambda (f)
(lambda (x)
(2 f (n f x)))))
1)
(lambda (f) ; 将 1 应用到参数 n
(lambda (x)
(2 f (1 f x))))
(lambda (f) ; 展开 1
(lambda (x)
(2 f (
(lambda (f) ; 1
(lambda (x)
(f x)))
f
x))))
(lambda (f) ; 将 f 应用到 参数 f
(lambda (x)
(2 f (
(lambda (x)
(f x))
x))))
(lambda (f) ; 将 x 应用到参数 x
(lambda (x)
(2 f (f x))))
(lambda (f) ; 展开 2
(lambda (x)
(
(lambda (f) ; 2
(lambda (x)
(f (f x))))
f
(f x))))
(lambda (f) ; 将 f 应用到 参数 f
(lambda (x)
(
(lambda (x)
(f (f x)))
(f x))))
(lambda (f) ; 将 (f x) 应用到参数 x ，计算完成
(lambda (x)
(f (f (f x)))))
调用(+ 2 1)的计算结果和前面列出的定义three完全相同，证明我们定义的+函数
是正确的。
See also
关于 Chruch 计数的更多信息，可以参考维基百科 Chruch Encoding 词条的 Chruch Numerals 部分 ，词条还给出了另外的几个计数函数，比如乘法函数和指数函数。
扩展练习：区间算术
练习 2.07
ref 2.14
练习 2.07
ref 2.14
练习 2.09
#lang racket ;; add-interval: ;; (+ [x1 y1] [x2 y2]) ;; = [(+ x1 x2) (y1 y2)] ;; ;; width1 = (- y1 x1) ;; width2 = (- y2 x2) ;; ans_width = (- (+ y1 y2) (+ x1 x2)) ;; = (+ (- y1 x1) (- y2 x2)) ;; = (+ width1 width2) ;; ;; sub/mul/div ...
练习 2.10
ref 2.14
练习 2.11
练习 2.12
#lang racket
(define (make-center-percent center percent)
(cons center (/ percent 100.0)))
(define (lower-bound x)
(let ((center (car x)) (percent (cdr x)))
(- center (* (abs center) percent))))
(define (upper-bound x)
(let ((center (car x)) (percent (cdr x)))
(+ center (* (abs center) percent))))
(define x (make-center-percent 1 5))
x
(lower-bound x)
(upper-bound x)
(define y (make-center-percent -1 5))
y
(lower-bound y)
(upper-bound y)