和上一章一样，附上我写的习题程序，仅供参考。想要做对这些习题可不太容易，经常是做到下一题的时候才发现上一题甚至几题的解法有缺陷，又回头去改，反反复复，不知道什么时候才是完美。2.4和2.5节的习题我只在Eli Bendersky的blog上看到了，不过是用clisp写的，我的版本是MIT Scheme。这两节的题目可以看做是一个大作业，很难很复杂，但是如果不做，可以说第二章就相当于没看了。
2.4/5节也”路过“了一个计算机语言设计中很重要但不太引人注目的问题，那就是”类型“。程序语言的类型系统的设计和构建并不是看起来那么简单的问题。有兴趣的同学可以看看Benjamin C.Pierce的《Types and Programming Languages》，国内译作《类型和程序设计语言》，不过貌似翻译的并不太好。
http://dl.getdropbox.com/u/1584769/chapter2.tar
2.53
(list 'a 'b 'c) = (list (quote a) (quote b) (quote c)) = (a b c)
(list (list 'george)) = (list (list (quote george))) = ((george))
(cdr '((x1 x2) (y1 y2))) = ((y1 y2))
(cadr '((x1 x2) (y1 y2))) = (y1 y2)
(pair? (car '(a short list))) = #f
(memq 'red '((red shoes) (blue socks))) = #f
(memq 'red '(red shoes blue socks)) = (red shoes blue socks)
2.55
1 ]=> (car ''abracadabra)
;Value: quote
其实为什么会这样作者已经在注释中解释了
“'”等价于quote函数，单引号都会被翻译成(quote x x x)，就好像C语言中的宏替换一样
替换之后，在最外层的quote作用下，内层的quote就变成一个符号而不起函数的作用了
就好像'(quote abracadabra)一样
2.56
该小节中给出的选择函数还是有问题的
(deriv '(x) 'x)
会出错
原因很简单，cadr的参数不够长
2.60
函数 复杂度
element-of-set? O(n)
union-set O(n)
adjoin-set O(1)
intersection-set O(n^2)
相比原来，adjoin-set的复杂度明显降低了，其他不变。
显然，这种允许重复的集合更加适合频繁增加元素的场合。
2.63
a) tree2list-1显然是把树变成“左中右”的表，相比之下tree2list-2就不是那么明显了，不过结果是这两者的结果是相同的。
b) 两者都是O(n)的复杂度
2.64
这个函数只是生成的平衡二叉树，并没有经过排序（左小右大）
比如，(list->tree (list 3 1 5 7 9))只会生成(5 (3 () (1 () ())) (7 () (9 () ())))
该函数依赖于排好序的参数才能产生符合要求的二叉树
不过，假设2.63-2.65的输入都是已经排序的也无妨
a) tree->list总是平衡的，因为它往一侧放多少个元素，就会往另一侧放相同多的元素
b) 复杂度为O(n)，每个元素只调用了一次tree->list
2.65
因为2.62以及“集合作为排序的表”(sets as ordered list)一节已经实现了O(n)的union-set和intersection-set
而这里的list->tree以及tree->list也都是O(n)的，所以只需要把树先转成表，然后合并表，最后把表转成树
这样的函数的复杂度也肯定是O(n)的
注意，能够这样的前提条件是输入的树（表）都是已经经过排序的
2.67
左0右1
(0 1 1 0 0 1 0 1 0 1 1 1 0) -> (a d a b b c a)
2.68
(a d a b b c a) -> (0 1 1 0 0 1 0 1 0 1 1 1 0)
2.69
验证生成的树的办法就是把上两题用这棵树编码和解码
不过，编码解码的结果和上两题不同是完全有可能的，因为Huffman树不是唯一的
2.70
生成的树：
((((((leaf get 2) (leaf job 2) (get job) 4) (leaf sha 3) (get job sha) 7) (((leaf boom 1) (leaf wah 1) (boom wah) 2) (leaf a 2) (boom wah a) 4) (get job sha boom wah a) 11) (leaf yip 9) (get job sha boom wah a yip) 20) (leaf na 16) (get job sha boom wah a yip na) 36)
编码（84位）：
(0 0 0 0 0 0 0 1 1 0 0 0 0 1 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 0 0 0 0 1 0 0 0 1 1 1 1 1 1 1 1 1 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 1 0 0 1 0 0)
如果使用定长编码，字母表中有8个符号，每个符号长为3位
消息中共有36个符号，总长需要36*3=108位
2.71
这样的树有n个元素，频度为2^k次方的符号需要k+1位来表示
这样，出现最频繁的符号只需要一位，而最不频繁的需要n-1位
2.72
member-of?函数的复杂度为O(n)
对于出现最频繁的符号，在将其编码的过程中，只会用member-of?检查一次根节点的symbol（其中包含n个元素）
因此将出现最频繁的符号编码的复杂度为O(n)
对于出现最不频繁的符号，在将其编码的过程中，会使用member-of?检查所有中间节点的symbol
最坏情况下的比对次数为n + (n-1) + (n-2) + ...
因此将出现最不频繁的符号编码的复杂度显然是O(n^2)
2.73
要顺利跑起来这一题，记得从SICP的官方网站把第二章的代码下载下来，里面有get/put函数，它们都是第三章才实现的
另外还需要从2.56拿一部分代码过来
注意：重写的deriv是有问题的，实际上并不需要使用operands函数
d) 理解了<op>/<type>表，改动很简单
--- 2.73d.scm 2009-08-08 15:31:56.000000000 +0800
+++ 2.73b.scm 2009-08-08 15:31:17.000000000 +0800
@@ -86,9 +86,9 @@
(deriv (base expr) var)))
;; interface to the rest of the system
(define (tag x) (attach-tag 'deriv x))
- (put '+ 'deriv sum)
- (put '* 'deriv multiply)
- (put '^ 'deriv exponentiation)
+ (put 'deriv '+ sum)
+ (put 'deriv '* multiply)
+ (put 'deriv '^ exponentiation)
'done)
(define (variable? expr) (symbol? expr))
@@ -100,7 +100,7 @@
((variable? expr) (if (same-variable? expr var)
1
0))
- (else ((get (operator expr) 'deriv) expr var))))
+ (else ((get 'deriv (operator expr)) expr var))))
(install-deriv-package)
(newline)
2.74
a) 题目明确说了名字是主键，那就使用key方法来取得一条记录的主键值
(define (key record) (car record))
(define (content record) (cadr record))
(define (get-records division)
; god knows how to get them
)
(define (get-record name division)
(define (get-record-internal name records)
(cond ((null? records) ())
((eq? name (key (car records))) (content (car records)))
(else (get-record-internal name (cdr records)))))
(get-record-internal name (get-records division)))
b) 从指定的部门取某个人的salary信息，就要先拿到这个部门的get-salary方法，再拿到这个人的记录
这些操作对记录的结构并没有特殊的要求，只要能够取得相应的get-salary方法就好
(define (get-salary division name)
((get 'get-salary division) (get-record name division)))
c) 好像并没有什么特别之处……
(define (find-employee-record name divisions)
(if (null? divisions)
()
(let ((record (get-record name (car divisions))))
(if (eq? record ())
(find-employee-record name (cdr divisions))
record))))
d) 新公司必须有唯一的部门标识符，必须要注册自己的一系列访问函数
2.76
显式分派是最糟糕的设计。数据导向的设计会使加入新的新的操作比较容易，消息传递方式的设计会使加入新类型比较容易。
只要看看那张<op>/<type>表就很清楚了。
2.77
开始之前，先期
(install-rectangular-package)
(install-polar-package)
(install-scheme-number-package)
(install-rational-package)
(install-complex-package)
先定义z这个复数：
(define z (make-complex-from-real-imag 3 4))
-> lookup ('make-from-real-imag, 'complex) from the (<op>, <type>) table
-> ('complex (make-from-real-imag 3 4)), from complex package
-> lookup ('make-from-real-imag, 'rectangular) from the (<op>, <type>) table
-> ('complex 'rectangular 3 . 4), from rectangular package
然后求它的模：
(apply-generic 'magnitude z)
-> lookup ('magnitude, 'complex) from the (<op>, <type>) table
-> error: No method for these types -- APPLY-GENERIC (magnitude (complex))
原因：操作类型表中只存在('magnitude, 'rectangular)和('magnitude, 'polar)，并不存在('magnitude, 'complex)
搜索一下代码很容易就可以看出这一点
为install-complex-package函数添加了题目中的代码之后，运行的过程应该是这样的：
(apply-generic 'magnitude z)
-> lookup ('magnitude, 'complex)
-> (apply-generic 'magnitude ('rectangular 3 . 4))
-> lookup ('magnitude, 'rectangular)
-> magnitude method from rectangular package
-> 5
注意：apply-generic方法在查找操作类型表时，都是查找的方法所在的表
例如，参数是'magnitude，即查找magnitude方法时，实际查找的是'(magnitude)
因此，在构造操作类型表时需要特别注意这一点，否则会找不到方法
2.80
此题和2.79需要注意的地方一样，除了scheme-number，其他包中都不能简单的使用等于零来判断，而应该复用通用的=zero?
2.81
(define put-coercion put)
(define get-coercion get) ;这样就可以调试了
a) 会陷入complex->complex的死循环
2.82
不知道是不是我对Scheme还不熟的原因，调试程序实在是让我头大
反例还是很好举的，例如(add rational complex scheme-number)（这里只写出了类型）
而操作类型表之后只有rational->complex和scheme-number->rational
就会出现这样的情况：
因为没有complex->rational，没法将所有加数都转化为有理数
因为没有scheme-number->complex，没有办法将所有加数都转化为复数
因为没有rational->scheme-number和complex->scheme-number，没有办法将所有加数都转化为一般数
所以加法就算不了了
实际上，用scheme-number->rational之后这个加法还是可以算的，但此时apply-generic无法识别这种情况
另外，要测试这一题还要另外修改一下你希望测试的方法，因为所有的方法的参数个数是一定的
2.83
raise是通用的，不需要为每一种类型添加一个raise操作，但两个类型之间的互相转换是必不可少的
这里为了简单起见，认为scheme-number就是整数
2.84
还是局限在两个参数的情况比较好处理
type-gt?和type-lt?的道理是一样的，就是t1和t2在比赛
从最低级的开始，先碰到t1，说明t1比t2小，反之亦然
2.85
只实现了复数的部分，其他类似
2.86
因为复数是塔的顶端，所有其他类型的数都能转化为复数。
2.84和2.85的apply-generic结合之后可以比较完美的自动化解决类型上下转换的问题
把他们应用到2.81的代码中去就好
2.88
在2.80的基础上引入polynomial-package
在polynomial包内部，不能使用=zero?作为内部函数的名称
因为=zero?是一个全局函数，而且用在了polynomial包的内部
这里用的是is-zero，防止出现命名冲突
2.89
这一题和2.90和在一起做了，程序太长了受不了了，没有vim的折叠帮忙实在驾驭不了
2.91
做出来2.89和2.90的话这一题就很简单啦，再说大部分程序书上都给你写好了
不过书上只要你加上div-terms，如果你向我一样手痒的话，也可以顺带加上div-coeffs
这两个除法函数都只应该返回一个多项式，那就是商，所以呢我们还应该有mod-terms/coeffs，来返回余数多项式……
这个代数系统也不是没有问题的，比如=zero?的结果，按理说应该是一个布尔值，但是布尔值的类型应该是布尔，而不应该是多项式
2.92
要把这个题调通，首先要把前面写的类型转换的代码集成进来，为了方便，我们还是只处理两个参数的情况
类型转换树是complex <- rational <- scheme-number
想了半天没想出来，怒了，去Eli Bendersky的blog翻到2.5.3看2.92的解答，结果只有一个词：skiping……囧……
继续Google，搜到纽约大学一个博士后的blog上面有他的2.92的程序，看得一知半解
觉得他的测试数据有问题，至少没有测到我最关心的几种特殊情况
黔驴技穷了……
2.93
2.91的时候提了一下=zero?应该返回布尔类型的值，这一题就遇到这问题了，还好不是很难改
之前手比较贱，一不小心把这一题要做的东西差不多都改完了，现在要加的就是一个通用型的gcd
我的程序里的general-gcd比2.93题目中的更加一般，不仅仅局限于稀疏型的多项式，这样看起来2.93的代码已经把2.94也做完了
有个比较有趣的地方就是题目给的分子x^3+1（即('x '((3 1) (0 1)))）和分母x^2+1（即('x '((2 1) (0 1)))）的最大公约数并不是1
而是(polynomial sparse-poly x (0 2))。这样，由于在构造有理数(rational)的时候使用了general-gcd，最初构造出来的rf就是：
(rational (polynomial sparse-poly x (3 1/2) (0 1/2)) polynomial sparse-poly x (2 1/2) (0 1/2))
而rf + rf则是：
(rational (polynomial sparse-poly x (3 1) (0 1)) polynomial sparse-poly x (2 1/2) (0 1/2))
幸运的是，这个结果至少没错。
2.95
一开始这个结果太难看了：(polynomial sparse-poly x (2 1458/169) (1 -2916/169) (0 1458/169))
没人不会怀疑它是不是错了，不过从高考那种专门给难看数据的考试得出的经验，也许我们不应该怀疑MITScheme解释器，因为它之前都工作的好好的
这个体系另一个缺陷的地方是对于有理数，复数使用的sqrt/square/atan这几个函数是绕不过去的
也就是说，如果你试着用实部或者虚部是有理数的复数进行乘除运算，那肯定会出错
如果你更手痒一点，把这个问题也解决了吧……我累了，为'(scheme-number polynomial)写了一个乘法函数，作为一点小小的妥协
另外，我死都没法把drop/project集成进apply-generic，即使我做了正确的修改
这两个东西的问题在于有可能被非类型塔的类型调用，比如complex下面的rectangular/polar，或者polynomial下的sparse/dense-poly
2.95.scm实际上已经把2.96a做了
没有评论:
发表评论