※ [本文转录自 CompBook 看板 #1KX6S-Mb ]
作者: descent (“雄辩是银，沉默是金”) 看板: CompBook
标题: [心得] sicp
时间: Sun Dec 7 22:41:48 2014
全名是: Structure and Interpretation of Computer Programs
中文名称: 算机程序的构造和解
20131024 淘宝订单 20131104 到手, 12 天才收到, 有点久。
费用 42 * 5.1 = 214.2 + 145 = 359.2 委托代买购得。
电子版本 ( http://goo.gl/QwRmW ), 当然是英文的, 要不然我就不用花钱买中文的版本
。
简体中文版本看来薄薄的, 可别以为是本小书, 整整有 472 页, 所以纸质真的不怎么样
(薄的厉害, 我觉得用打印机得到的品质都比这本书好), 在上头写注记得小心点, 一不小
心可能就划破纸张。在阅读上也有点困扰, 整本书歪斜的很厉害, 不好拿着看。
简体中文版本出版日期: 2004 年 2 月 1 日, 我这本是 201306 第八刷, 原文书 1984
年出版，是美麻省理工院 (MIT) 多年使用的一本教材, 1996 年修第二版。
后来 MIT 始用 python 教授此，代替了原本的 Scheme： Why MIT switched from
Scheme to Python ( http://goo.gl/yd2l )
淘宝有些书是影印的版本, 还好这本不是, 我本来还担心这本已经出版了这么久的一段时
间, 会买不到正版的, 不过看来这本书还有陆续再出版。
我的进度很缓慢, 不过我很有耐心和毅力, 忍住开发 os, qt for android, uefi 程式的
相关诱惑, 专心看这本书, 慢慢地, 慢慢地, 我越来越可以看下去了, 速度也提升了一点
点。她有什么魔力让我愿意这样做呢? ref 2 提到: 您法中到如何一网站，一事本，如何
，它完全是在程序的基本能力，而不是“技”。一言以蔽之, 就是在教怎么写程式。很推
荐大一同学和程式初学者读这本, 这本书并不是进阶书而是入门书哦! 但这不表示它很好
读, 请有心理准备。和一般的程式语言书籍不同, 里头的数学味道很重, 几乎都是数学题
目, 牛顿法、最大公因子、微分, 有理数/复数的运算, 真是不习惯。更不习惯的是他所
选用的语言是 lisp 系的 scheme, prefix syntax 让人迷惑, 这是吸引我的最主要部份
, 据说 2008 年已经改用 python (好像是 2009), 若是 python, 我也许就没兴趣了吧!
看着一堆小括号充满萤幕, 真是有趣。
4.1.1 ~ 4.1.4 会写一个 scheme interpreter, 我觉得还是照课本使用 scheme 来读
sicp, 比较不会有和课本出入的地方。
这本教科书我读来实在辛苦, 觉得很难, 所以读得很慢, 不知道是不是因为简体中文的翻
译, 我觉得又让她更难读了。者裘宗燕老师学问应该很好, 不过翻译可能不是他的强项 (
他翻译过很多不错的原文书籍)。
In a production-quality Lisp system,
书中翻成 "在产品质量的 Lisp 系统里", 说实在, 我得看原文才懂这句话。这英文不算
难懂, 但要翻译成通顺的句子那就不容易了。
It calls apply-primitive-procedure to apply primitives;
书上翻译: 它直接调用 apply-primitive-procedure 去应用基本过程
我把它改为: 它直接呼叫 apply-primitive-procedure 去执行 primitives procedure。
To define a variable, we search the first frame for a binding for the
variable
我们需要在第一个框架查找该变量的约束
descent 改: 我们需要在第一个框架查找该变量的定义
还真的不好翻译, 只看中文会看不懂, 查询完原文后就好多了。
This computation will run much more slowly than a gcd procedure written in
Scheme, because we will simulate low-level machine instructions, such as
assign, by much more complex operations.
书上翻译为:
因为我们是在模拟低级的机器指令, 例如 assign, 而使用的却是比他高级得多的操作。
这句话也是怪怪的。
书中的句子有很多像是这样的翻译, 读来不能算是轻松, 我偶尔得对照一下原文词句。
就算翻译的不算好, 但中文版本还是帮了我不少忙, 这本并没有烂到完全看不懂, 大多时
候还是可以理解翻译后的意思, 没有中文翻译, 我无法那么快浏览过一遍, 有些翻不好的
地方如果不是关键处, 倒也无伤大雅。加上对照原文, 对于英文不好的我来说, 甚有帮助
, 这是翻译的价值。与其要求每个人把英文、日文、德文、法文学好, 才能吸收其中的专
业知识, 倒不如用国家力量培养优秀的翻译人员。
( http://goo.gl/z3Rje1 )
目
前 言
第1章 构造程抽象
1.1 程序的基本元素
1.2 程与它所生的算
1.3 用高函做抽象
第2章 构造据象
2.1 据抽象引
2.2 次性据和包性
2.3 符据
2.4 抽象据的多重表示
2.5 有通用型操作的系
第3章 模化、象和
3.1 值和局部
3.2 求值的境模型
3.3 用据做模
3.4 并：是一本
3.5 流
第4章 元言抽象
4.1 元循求值器
4.2 Scheme的形——惰性求值
4.3 Scheme的形——非确定性算
4.4 程序
第5章 寄存器机器里的算
5.1 寄存器机器的
5.2 一寄存器机器模器
5.3 存分配和料收集
5.4 式控制的求值器
5.5
这是本怎么样的书呢? 主要在教如何写程式, 以及程式是怎么样的一个东西。前两章对一
个有涉猎程式的人来说, 大概都能明白, 也就是一般 c++ 程式入门书籍上都会谈到的概
念。
资料抽象 - 将资料结构和操作的函数分开, 形成一个黑箱, 资料结构的改变不会影响这
些操作函数, 将修改程度降到最低。这不是一般的 c++ 程式书籍都会提到的资料封装吗
。
用不同的资料结构来表示同一个抽象资料, 书中提到复数的例子, 可以用直角座标或是极
座标 (很久没听到这名词了吧?) 来表示复数, 但也必须要在这两种资料结构做转换。都
是表示复数, 没道理处理直角座标的程式码无法在极座标上执行, 该怎么做呢? 最直观就
是提供转换的函式, 这不也是在程式设计中会看到的技巧。c++ 可以实作 cast
operator 和这个观念很类似。
再来型别转换一多的话, 程式码会太复杂, 能辨识出型别的操作函数不是很棒, 怎么做?
加个 tag 判断即可。这不就是 if/switch/case 的应用吗?
if circle do_circle
else do_others
而 c++ 为了消除太多 if/switch/case 导入了 virtual function, 这边也用了类似表格
法来处理这样的问题, 类似 c 的 function pointer。这些技巧都不会因为用什么语言而
有所不同, 是基本中的基本。
但从第三章开始, 就不是一般程式设计书籍提到的东西了, 你曾经想过变量与变量值的对
应是怎么实作的吗? 在 script language 里头, 执行一个 expression 时会发生怎么样
的行为呢? 函式的参数如何替换成真正的值? 3.2 有个概括的说明。
而第四章第五章的 metacircular evaluator, register base machine 更不是容易见到
的主题。我实在很怀疑这样的书籍竟然只是定位在入门等级。
从第一章看起 ...
1.1.1 谈 expression
1.1.4 利用 define 来建立 procedure (如同 c function)
1.1.5 谈到了 applicative order, normal order, p13 练习 1.5 有个有趣的题目:
1.5.scm
1 (define (p) (p))
2
3 (define (test x y)
4 (if (= x 0)
5 0
6 y))
当执行 (p) 会怎么样, (p) 会先去找出 p 是什么, 结果又找到 (p), 然后又去找 p 是
什么 ... 永远都找不到, 这就是 applicative order。
而 normal order, 就很顺利执行完毕, 因为 normal order 不需要把 p 计算出来, 有需
要的时候在计算即可。
在 mit-scheme 可以使用 delay 这个函数来执行 normal order, (delay (p)) 就不卡住
了。
ref:
http://www.gnu.org/software/mit-scheme/documentation/mit-scheme-ref/Promises.html
( http://goo.gl/WQTueY )
http://practical-scheme.net/gauche/man/gauche-refe_59.html#Delay-force-and-lazy
( http://goo.gl/TFbVXL )
1.1.6 conditional expressions and predicate, 就是 if/else 用法。
这样读过来之后, 就可以开始用 scheme 写程式了。不过和 c 语言不同, 没有
for/while loop 这种东西, 那替代品是什么呢? 是让人伤透脑筋的 recursive。
1.1.7 从牛顿法开始求根号 X, 正常人应该都忘记什么是牛顿法, 只记得牛顿是谁吧?
square_root.scm
1 (define (sqrt-iter guess x)
2 (if (good-enough? guess x)
3 guess
4 (sqrt-iter (improve guess x)
5 x)))
6
7 (define (improve guess x)
8 (average guess (/ x guess)))
9
10 (define (average x y)
11 (/ (+ x y) 2))
12
13 (define (good-enough? guess x)
14 (< (abs (- (square guess) x)) 0.001))
15
16 (define (sqrt x)
17 (sqrt-iter 1.0 x))
18
19 (sqrt 2)
in mit-scheme
2 error> (load "square_root.scm")
;Loading "square_root.scm"... done
;Value: 1.4142156862745097
书上有写的东西就不说明了, 这种语法, 还真是不习惯。
1.2.1 linear recursion and iteration, 介绍 recursive 和 iteration, 书中用了两
个 factorial 来解释。
factorial.scm
1 ; recursive
2 (define (factorial n)
3 (if (= n 1)
4 1
5 (* n (factorial (- n 1)))))
6 (factorial 5)
7
8 ; iteration
9 (define (factorial n)
10 (fact-iter 1 1 n))
11
12 (define (fact-iter product counter max-count)
13 (if (> counter max-count)
14 product
15 (fact-iter (* counter product)
16 (+ counter 1)
17 max-count)))
iteration 的版本看起来好像是 recursive, 但这和 c 语言的 while, for loop 是一样
的概念。
1.2.3 介绍计算所需的时间, 计算所需要的内存空间。
1.3.2 介绍 lambda, 不过我觉得 the roots of lisp ( http://goo.gl/efetP ) 解释的
比较好。
(lambda (x) (+ x 4)) 这个是 function。
((lambda (x) (+ x 4)) 5) => 9 这叫 function call。
5 是 argument (引数), x 是 parameter (参数), (+ x 4) 是 function body。
lambda 建立的是一个没有名字的函数, 要使用这个函数就要用上述的那个语法。配合上
define, 就可以将这个 function 对应到一个名字。
(define plus4 (lambda (x) (+ x 4)))
也可以写成
(define (plus4 x) (+ x 4))
这是一种语法糖衣。
let 也是一种 lambda 的语法糖衣。
page 42
(define (f x y)
((lambda (a b)
(+ (* x (square a))
(* y b)
(* a b)))
(+ 1 (* x y))
(- 1 y)))
(define (f x y)
(let ((a (+ 1 (* x y)))
(b (- 1 y)))
(+ (* x (square a))
(* y b)
(* a b))))
let 的功能, 可以由 lambda 来提供。
1.3.3 将一个 procedure 当作参数传给一个 procedure
1.3.4 传回一个 procedure, 这还真难懂, 花了我好些时间。
(define (average-damp f)
(lambda (x) (average x (f x))))
真的很难懂吧!
first-class elements:
They may be named by variables.
They may be passed as arguments to procedures.
They may be returned as the results of procedures.
They may be included in data structures. ( http://goo.gl/aLumTA )
符合这些条件的 function 就称为 first-class function, 又是一个流行的名词。当然
符合这些条件的 object 就是 first-class object, 当然符合这些条件的 people 就是
first-class people XD
这是由 the British computer scientist Christopher Strachey (1916-1975) 帮我们
整理出来的概念。
( http://goo.gl/Pbx731 )
2.1.1 p56 介绍了 pair, 有相关的操作函数 cons, car, cdr, list (p66, 为了方便使
用 cons, scheme 提供了 list) p57 最下面的注解解释了 cons, car (Contents of
Address part of Register, cdr (Contents fo Decrement part of Register) 这几个
奇怪的名称。
2.1.3 p61 实作了 cons, car, cdr。
(define (cons x y)
(define (dispatch m)
(cond ((= m 0) x)
((= m 1) y)
(else (error "Argument not 0 or 1