庖丁编程

庖丁解牛的程序员版（学学这英文……啧啧……取自《The Tao of Programming》 4.4节 by Geoffrey James）

Prince Wang's programmer was coding software. His fingers danced upon
the keyboard. The program compiled without an error message, and the
program ran like a gentle wind.

``Excellent!'' the Prince exclaimed, ``Your technique is faultless!''

``Technique?'' said the programmer turning from his terminal, ``What I
follow is Tao - beyond all techniques! When I first began to program
I would see before me the whole problem in one mass. After three
years I no longer saw this mass. Instead, I used subroutines. But now
I see nothing. My whole being exists in a formless void. My senses
are idle. My spirit, free to work without plan, follows its own
instinct. In short, my program writes itself. True, sometimes there
are difficult problems. I see them coming, I slow down, I watch
silently. Then I change a single line of code and the difficulties
vanish like puffs of idle smoke. I then compile the program. I sit
still and let the joy of the work fill my being. I close my eyes for
a moment and then log off.''

Prince Wang said, ``Would that all of my programmers were as wise!''

Code-Illuminated for Python

最近在关注Bespin的时候发现了一个有意思的小东西，Code-Illuminated项目。Mozilla Ubiquity项目组为了更好的注释代码而创建了它，Atul Varma在Beautifully Documented Code之中详述了它的前生今世。

我第一眼就喜欢上了这个小玩意儿，因为我觉得他比之doxygen等传统代码文档生成工具有以下几个优点：

1. 形式简洁：左注释右代码，一目了然
2. 表现力丰富：使用CroeleWiki作为注释格式，注释中的代码量更少，表达能力更强
3. 免编译：纯web表现，无需额外工具，速度也非常快

兴奋了一下之后我的第二个念头是，它能用在Python上面么？貌似不行，现在它只能处理Javascript。不过没关系，毛爷爷说“自己动手，丰衣足食”，开源的好处就在这里。CI的逻辑很简单，小改一下就好了（中文注释也没有问题）。

正如Atul的博文中所说，这东西还有很大的潜力可以挖掘。Bespin作为一个在线的源代码编辑应用程序，已经集成了Mercurial的一些版本控制命令。如果Bespin再集成上这么一个在线代码生成和查看的组件将会如何？嘿嘿……

SICP 第二章（下）

和上一章一样，附上我写的习题程序，仅供参考。想要做对这些习题可不太容易，经常是做到下一题的时候才发现上一题甚至几题的解法有缺陷，又回头去改，反反复复，不知道什么时候才是完美。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做了

SICP 第二章（上）

第二章比较长，习题也多很多，所以还是分两次贴比较好。完成这一章的习题要花一些功夫，比如需要DrScheme来画2.2.4那一节的小人儿，2.5节也需要额外代码的支持。习题做到最后，代码都很长了，一个文件里有三百多行。Scheme代码的可读性和条理性在没有注释的情况下比其他语言要差多了，希望下一章能够解决这个问题。

2.6
这个题目比较好玩，使用到了Church Numerals。
第一眼看到这个问题马上让我想起了离散数学，因为他们都定义了一套运算体系。
上wiki查了一下Church Numerals，说的很详细，让我理解了一些基本概念。
one和two的定义用zero和add-1可以比较容易的推导出来。
看了wiki上的说明以及one和two的定义可以看出，n的意义就是对参数x应用n次参数f。
知道这个再写加法就简单了，特别是add-1可以看作n和one的加法。我基本是像搭积木那样把add方法搭出来了。
(define (add a b) (lambda (f) (lambda (x) ((b f) ((a f) x)))))

(add one two)
(lambda (f) (lambda (x) ((two f) ((one f) x)))
(lambda (f) (lambda (x) ((f (f ((one f) x))))))
(lambda (f) (lambda (x) (((f (f (f x)))))))

2.9
(define x (make-interval 6.12 6.8))
(define y (make-interval 4.47 4.9))
(newline)
(display (= (width-interval (add-interval x y)) (+ (width-interval x) (width-interval y))))
很遗憾，上面这段程序执行的结果是：#f
我很不解，用display分别打印了这两个结果，显示的都是0.555，于是我就更不解了。
郁闷了一小会儿，想起来自己默认是用的guile，于是改用MIT Scheme，还是#f。
但是MIT Scheme分别打印出来的两种方式的运算结果是：
    ;Loading "2.7.scm"...
    #f
    .5549999999999997
    .5550000000000002
    ;... done
这就清楚了，原来他们真的“有点”不一样。

2.13
数学上比较简单。
假设第一个区间的中点是v1，误差是t1；第二个区间的中点是v2，误差是t2。v1 t1 v2 t2都大于零。
乘积的区间是[v1*v2*(1-t1-t2-t1*t2), v1*v2(1+t1+t2+t1*t2)]，显然误差就是(t1+t2)/(1+t1*t2)
由于t1和t2都非常小，t1*t2就成芝麻了，忽略，结果就成了一个非常简单的t1+t2。
对于v1 t1 v2 t2的值分布的其他情况同理可证。

2.14
确实不一样，为什么呢？

2.15
要解释2.14的问题，需要回过头来看练习2.9。
2.9表明了两个区间进行加减的时候，结果区间的误差也是参数区间用同样运算符进行运算得到的结果。
区间相加，误差也相加
但是这个结论对于其他运算（减法、乘法和除法）竟然都并不成立。
对于减法，区间相减，误差还是相加。
沿用2.13的变量，两个区间相乘的结果的误差t=(t1+t2)/(1+t1*t2)。算出除法的结果误差有点麻烦，但结果也是t=(t1+t2)/(1+t1*t2)。
因此，对于par1和par2，需要对每一步的运算的误差进行计算，才能得到t(par1)和t(par2)。（好消息是t(one)=0）
步骤省略，结果是：
t(par1)=(t1+t2)(2+t1*t2)/(1+3*t1*t2+t1^2+t2^2) ~ 2*(t1+t2)
t(par2)=(t1+t2)
显然，按照这种计算方法，t(par2)只有t(par1)的一半不到。

2.16
为什么等价的代数表达式可能导致不同计算结果？
这本来就是一个伪命题。既然他们是等价的，计算结果就不应该不同。
唯一的可能就是，我们使用的方法不正确，也就是说，误差的计算是不能传递的。
要证明这一点很容易，很显然，除法就是误差传递的障碍。
没有缺陷的区间算术表示方法也许存在，但至少我不知道，嘿嘿。

关于区间运算，其实还有很多有意思的东西。下面这个链接就是一个入口，等我重新温习《具体数学》的时候再回头看吧：
http://wiki.drewhess.com/wiki/SICP_exercise_2.16

2.19
coin-values的排列顺序和最后结果无关，组合部分先后顺序。

2.22
(cons 4 ())和(list 4)等价，因为表的特征就是最后一个cons的后半部分指向nil
但是(cons () 4)产生的并不是(4)，而是(() . 4)。
为什么？这个序对的后半部分不是指向nil，当然和(list 4)完全不同。

2.23
如果想在一个条件分支中写多个语句，记得用cond

2.24
(define x (list 1 (list 2 3))) -> (1 (2 3)) -> (cdr x) = ((2 3))
(define y (cons 1 (list 2 3))) -> (1 2 3)   -> (cdr y) = (2 3)
(define z (cons 1 (cons 2 3))) -> (1 2 . 3) -> (cdr z) = (2 . 3)
为什么会有这样的不同呢？最关键的地方在于(list 1 2)和(cons 1 2)是不等价的。
(list 1 2)等价于(cons 1 (cons 2 nil))，表(list)的最后一个元素总是空(nil)。
这样就比较好画方块图和树了。

2.26
把list转化为cons就好

2.29
程序我没有测试，因为书上没有给测试数据，而且测试数据构造也太麻烦了，就pass了。
至于d)，修改非常简单，把多余的car干掉就好

2.32
程序没错，去google了一下别人的填空，一样，但是不知道为什么scheme就是跑不出来，guile也报错 -_-

2.42
这个题真的难了我一下，不过也可能是我头天晚上去K歌的缘故
卡住我的主要是棋盘的表示方式，其实只需要把棋盘看作一个栈，把行号逐一压进去就好
不过safe?函数的k参数迷惑了我，让我以为需要把行号和列号作为一个序对压栈
后来回头google了一下，还真的有人用序对的方法作出了这个题
不过这样的话效率肯定是比不过只用整数的咯

2.43
Louis把嵌套映射的顺序改变后，程序变成了完全的深度优先搜索，没有剪枝的效果，程序要走完整个棋盘的所有组合，也就是8^8次方种可能性……
因此Louis的程序的复杂度很显然是O(n^n)，因为queen-cols函数被他执行了n^n遍
相比之下2.42的程序的复杂度是O(n)，度量的准绳就是queen-cols函数被调用的次数
O(n^n)/O(n)并不能改变O(n^n)的本质，Louis的程序比老师的慢了O(n^n)个数量级

2.44
比较可惜，没法测试这个程序

2.49
鬼知道wave是由什么坐标连起来的……

代码边线

今天闲逛的时候看到Intel官方blog上的一篇帖子《给VS2005的编辑器添加右边界线》，很有意思，因为好的代码风格是代码成功的一半。

Vim能不能也有相同或者类似的功能呢？google之，Vim果然不负我望（http://stackoverflow.com/questions/235439/vim-80-column-layout-concerns）：

 highlight OverLength ctermbg=red ctermfg=white guibg=#592929
 match OverLength /\%121v.*/

这段代码设置了一个新的配色方案叫OverLength，背景红色前景白色，第二句话将其和每行超出120个字符的部分进行匹配。什么意思呢？换句话说，在执行了以上代码之后，Vim会用红色高亮你编辑的文本每行中超出120个字符的部分，像这样：

虽然不像Visual Studio里面用线标出界限那么显而易见，但和textwidth等选项一起用起来也足够了：）

Valerie Aurora

标题并不是什么电影明星的名字，她是一位Linux Kernel Hacker，一位女性。她的主页在这里。

我也不知道怎么转到了她的blog，反正这两天我就在各位大牛的博客中游荡，好像刘姥姥进了大观园，觉得什么都新鲜。Aurora为Linux内核的主要贡献在文件系统方面，btrfs/zfs什么的，我能找到的和她唯一的共同点就是非常喜欢漫画Calvin&Hobbes：）

Aurora另一个让我关注的地方就是她在2002年写了一篇文章《HOWTO
Encourage Women in Linux》，并且是LinuxChix社区的创始人之一。LinuxChix.org旨在帮助女性了解和使用Linux并使她们更轻松的融入开源社区。事实上在国内，大多数人在进入开源社区时遇到的困难和Aurora在文章中提到的女性融入开源社区的困难非常类似，很多情况下语言的障碍和性别的障碍一样让人望而却步。

BTW: 上个星期的荷包岛之旅，我的脚底板被晒伤了……