※ [本文轉錄自 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