- 以下均為個(gè)人閱讀SICP的理解，如有不正確的地方歡迎留言交流
- 所有代碼均在Racket上運(yùn)行過
- bilibili上的SICP原版視頻課程非常不錯(cuò)，強(qiáng)烈推薦
SICP從理論上講解計(jì)算機(jī)程序的創(chuàng)建、執(zhí)行和研究，它采用了Lisp語言作為輔助工具（不是專門講授Lisp）來幫助學(xué)習(xí)者思考計(jì)算的產(chǎn)生、問題的分解、過程和數(shù)據(jù)的抽象。SICP第1章主要圍繞過程（類似函數(shù)、方法）這一程序設(shè)計(jì)中最常見的形式展開的，分3個(gè)部分進(jìn)行了論述，分別是基本元素（表達(dá)定義、應(yīng)用規(guī)則、條件分支等）、過程計(jì)算（遞歸、迭代等）以及高級(jí)抽象（高階過程、過程入?yún)?、過程返值等）。
程序設(shè)計(jì)的基本元素
我們知道程序語言既要能被計(jì)算機(jī)執(zhí)行，還要便于使用者描述計(jì)算的過程，因此在大多數(shù)程序語言身上都可以看到三種元素：
- 基本表達(dá)式，是對最簡單個(gè)體的表達(dá)，有點(diǎn)類似高級(jí)語言中的基本類型，比如：1、2、3、+、-、*、/等；
- 組合的方法，就是將基本表達(dá)式組合在一起的方法，由簡入繁地表達(dá)復(fù)合元素，比如：3+4表達(dá)的就是一個(gè)數(shù)值計(jì)算的過程
- 抽象的方法，將組合進(jìn)行命名后作為單元進(jìn)行使用，這個(gè)比較容易理解，比如：函數(shù)
程序設(shè)計(jì)就是綜合運(yùn)用這些元素來構(gòu)建我們對特定問題的答案域，通常會(huì)包含操作對象（數(shù)據(jù)）與操作規(guī)則（過程），比如：在程序中表達(dá)數(shù)學(xué)上的3+4就可以像這樣(+ 3 4）。這種前綴表示（即運(yùn)算符在前）方式與常規(guī)數(shù)學(xué)表達(dá)不太一樣，但它的好處也很明顯，比如可以有多個(gè)參數(shù)以及擴(kuò)充嵌套，一旦習(xí)慣后就不容易產(chǎn)生歧義。我認(rèn)為這種表達(dá)式的優(yōu)勢在于計(jì)算規(guī)則比較固定，即將最左值（運(yùn)算符）應(yīng)用于其他元素（運(yùn)算對象）的過程。我們可以對比兩者的差異如下：
3 * 5 + (10 - 6)
(+ (* 3 5) (- 10 6))
對比之下就能體會(huì)前綴方法更純粹和直接，因?yàn)閿?shù)學(xué)上的表達(dá)式隱含著計(jì)算的優(yōu)先級(jí)，而前綴表示則把計(jì)算的過程顯示地表達(dá)出來（比如上題就是一個(gè)顯而易見的加法操作，只是其中的元素要是其他表達(dá)式的值），運(yùn)算符總是位于表達(dá)式的最左側(cè)而子表達(dá)式都用括號(hào)加以分割，這就方便了解釋器按照以下規(guī)則工作：
- 求值該組合式的各個(gè)子表達(dá)式
- 將作為最左子表達(dá)式的值的那個(gè)過程應(yīng)用于相應(yīng)的實(shí)際參數(shù)
這是一個(gè)非常關(guān)鍵且基礎(chǔ)的規(guī)則，首先要理解子表達(dá)式是指什么，以上面計(jì)算過程為例，子表達(dá)式包括了+、(* 3 5)、(- 10 6)，注意運(yùn)算符也是表達(dá)式，而(* 3 5)、(- 10 6)又包含了子表達(dá)式，按照要求先求值，由于都是基本表達(dá)式，所以(* 3 5)、(- 10 6)不產(chǎn)生任何變化；接下來就是將最左子表達(dá)式的值的過程應(yīng)用于相應(yīng)的實(shí)參，注意這里的強(qiáng)調(diào)了過程應(yīng)用，就是真正地計(jì)算(* 3 5)、(- 10 6)，進(jìn)而得到(+ 15 4)；再重復(fù)上面的步驟從而得到最后的結(jié)果19。從上面的描述可以發(fā)現(xiàn)這樣的過程實(shí)際上就一個(gè)遞歸過程（反復(fù)地運(yùn)用上面兩條規(guī)則），這樣就能理解書中的陳述：
在性質(zhì)上，這一求值過程是遞歸的，也就是說，它在自己的工作步驟中，包含著調(diào)用這個(gè)規(guī)則本身的需要
這就揭示了一個(gè)計(jì)算機(jī)程序上很重要的事實(shí)：采用遞歸可以表達(dá)深度嵌套。這一思想幾乎貫穿了第1章后面還能看到很多有力的例子，同時(shí)它也撬動(dòng)了我的認(rèn)知是我逐漸深入閱讀的快樂之源。
現(xiàn)在把上面那段分析過程再提煉下，進(jìn)一步得到：
- 數(shù)的值就是它們所表示的數(shù)值
- 內(nèi)部運(yùn)算符的值就是能完成相應(yīng)操作的機(jī)器指令序列
- 其他名字的值就是在環(huán)境中關(guān)聯(lián)這一名字的那個(gè)對象
這三句話說起來有點(diǎn)拗口，結(jié)合上面的分析，對于(* 3 5)來說如何計(jì)算子表達(dá)式、3、5？數(shù)值就是數(shù)值這一句就搞定了3和5，它們的結(jié)果就是3和5，而這個(gè)運(yùn)算符就變成了機(jī)器指令序列，這樣就得到了計(jì)算結(jié)果。那么第三句話該如何理解呢？這里要引入環(huán)境的概念，環(huán)境的作用就是存儲(chǔ)名字-值對偶，因?yàn)槲覀儾豢赡苤辉诔绦蛑惺褂镁唧w數(shù)字或是其他簡單的表達(dá)，那樣我們程序就只能限定在非常小的用途上，要想辦法擴(kuò)大程序的應(yīng)用就要解開這種約束，最簡單的方式就是創(chuàng)建變量（名字標(biāo)識(shí)符），它可以指代任何值（其實(shí)就是具體的一個(gè)對象、事物），而環(huán)境就是幫助程序去記憶這些名字-值的對應(yīng)，就如同我們定義函數(shù)f(x)=ax+b，那么當(dāng)我們使用f時(shí)其實(shí)就會(huì)自動(dòng)地套入ax+b。第三句話實(shí)際上解釋了將變量如何在表達(dá)式中進(jìn)行代換，這在1.1.5節(jié)中將更加詳細(xì)地進(jìn)行說明。
準(zhǔn)備工作都已經(jīng)就緒了，現(xiàn)在可以來看看如何定義過程（也可以理解為函數(shù)，但從兩者指代的含義上看，兩者不完全一致）：
(define (<name> <formal parameter>) <body>)
看上去并不復(fù)雜，過程的調(diào)用也很簡單，下面就來分析一下過程求值，用書中平方和的例子，它的計(jì)算過程如下：
(f 5)
(sum-of-squares (+ 5 1) (* 5 2))
(+ (square 6) (square 10))
(+ (* 6 6) (* 10 10))
(+ 36 100)
136
不難看出整個(gè)過程就是應(yīng)用上面的計(jì)算規(guī)則（計(jì)算子式+最左值過程應(yīng)用），相比之前簡單的計(jì)算這里增加了對過程的調(diào)用（如sum-of-squares、square），而這個(gè)步驟實(shí)際也是計(jì)算了過程的值也就是關(guān)聯(lián)了該過程名的計(jì)算方法這么一個(gè)對象，比如f就可以理解為被解釋成了sum-of-squares (+ a 1) (* a 2)，而(sum-of-squares (+ 5 1) (* 5 2))則是該過程應(yīng)用于實(shí)際參數(shù)5之上，這里體現(xiàn)出的就是過程應(yīng)用的代換模型，就是將復(fù)合過程應(yīng)用于實(shí)際參數(shù)，就是在將過程體中的每個(gè)形參用相應(yīng)的實(shí)參取代之后，對這一過程體求值。我覺得這里可以借助數(shù)學(xué)上的代數(shù)概念去理解（如下），基本上是一致的。
已知有如下函數(shù)g和f，求解f(5)
g(x) = ax + b
f(x) = 2ag(x) + bx + c
這題一般的解答過程是
f(x) = 2a(ax + b) + bx + c
f(5) = 2a(a*5 + b) + b*5 + c
在計(jì)算的過程中還存在一個(gè)計(jì)算時(shí)機(jī)問題，通常有應(yīng)用序和正則序兩種方式。應(yīng)用序就是上面的計(jì)算步驟，在計(jì)算過程中會(huì)先計(jì)算每個(gè)子式的值再被左值應(yīng)用；而正則式則不急于計(jì)算子式，它將凡是涉及復(fù)合過程的地方先進(jìn)行展開，例如：(square (+ 5 1))在正則序中就會(huì)變?yōu)?* (+ 5 1) (+ 5 1))，講這些的目的都是為了幫助我們理解解釋器的工作方式（即如何計(jì)算我們程序中給出的求值過程）。
求解平方根的過程是一個(gè)用來觀察復(fù)雜過程如何建構(gòu)的不錯(cuò)例子（如下所示），它的流程十分簡單，就是不斷地用一個(gè)猜測值去逼近結(jié)果，如果猜測值精度不夠就采用牛頓法改善，如果精度達(dá)到那么久獲得最終結(jié)果。
(define (average a b)
(/ (+ a b) 2))
(define (improve guess x)
(average guess (/ x guess)))
(define (square x) (* x x))
(define (close-enough? a b)
(< (abs (- (square a) b)) 0.00001))
(define (sqrt y)
(define (sqrt-iter guess)
(if (close-enough? guess y)
guess
(sqrt-iter (improve guess y))))
(sqrt-iter 1.0))
從上面的過程我們看出這樣一個(gè)計(jì)算平方根的問題被分解成若干個(gè)子問題：如何判斷精度到達(dá)，如何改善猜測，每個(gè)子過程又再一次思考類似的問題直至無法分解為更小的子問題，這也是一種“遞歸”，更重要的是分解中的每一個(gè)過程完成了一件可以清楚標(biāo)明的工作，這使它們可以被用作定義其他過程的模塊。標(biāo)明的工作意味著目的的明確性，但對于實(shí)現(xiàn)并不關(guān)注，從這個(gè)層面上看是對過程的抽象從而形成一種完美的“黑箱”（我更愿意稱之為“積木”），由它便可以構(gòu)建規(guī)模更大、功能更多的大型程序。也許你會(huì)覺得這種想法是自然而然的，沒有什么值得大書特書的，但在實(shí)際工作中，我們總是自覺或不自覺地陷入到實(shí)現(xiàn)細(xì)節(jié)的思考中，甚至有時(shí)難以區(qū)分什么是模塊什么是具體實(shí)現(xiàn)，這也導(dǎo)致了我們自己設(shè)計(jì)的程序中大量緊耦合代碼。
練習(xí)
1.3 此題可以作為對1.1.6節(jié)條件表達(dá)式和謂詞的練習(xí)，代碼如下：
(define (sum-of-greater a b c)
(cond ((and (< c a) (< c b)) (+ a b))
((and (< b a) (< b c)) (+ a c))
((and (< a b) (< a c)) (+ b c))))
1.5 此題是對1.1.5節(jié)中正則序、應(yīng)用序的考察，包含了對代換的應(yīng)用
(define (p) (p))
(define (test x y)
(if (= x 0)
0
y))
當(dāng)計(jì)算(test 0 (p))，按如下步驟
(test 0 (p))
(if (= x 0) 0
(p))
使用應(yīng)用序則根據(jù)if的規(guī)則，首先計(jì)算x是否為0，此式為真則后續(xù)不再計(jì)算。使用正則序則根據(jù)先展開再計(jì)算的方式，那么(= x 0)和(p)，而由于(p)再展開仍然是(p)，就會(huì)在這進(jìn)入死循環(huán)
1.6 此題既考察1.1.6條件表達(dá)式和謂語，也考察了對應(yīng)用序的理解和應(yīng)用，實(shí)際上問題的關(guān)鍵不在于用cond替代if，而是對于new-if的使用上。根據(jù)if規(guī)則，求值時(shí)解釋器從求值其<predicate>部分，如<predicate>成立則求值<consequence>否則求值<alternative>，這個(gè)求值順序是這題的關(guān)鍵，<consequence>和<alternative>并非同時(shí)計(jì)算的。
(define (new-if predicate then-clause else-clause)
(cond (predicate then-clause)
(else else-clause)))
觀察new-if就能發(fā)現(xiàn)，由于它是一個(gè)一般過程，所以應(yīng)當(dāng)遵循先計(jì)算各子式在用最左值應(yīng)用，那么then-clause和else-clause就會(huì)分別進(jìn)行計(jì)算，所以當(dāng)用new-if來計(jì)算sqrt-iter時(shí)，就會(huì)去計(jì)算(good-enough？ guess x)、guess、(sqrt-iter (improve guess x) x)，而當(dāng)計(jì)算sqrt-iter時(shí)就又會(huì)觸發(fā)新的遞歸，依次類推會(huì)發(fā)現(xiàn)這將無窮無盡導(dǎo)致解釋器報(bào)錯(cuò)
(define (sqrt-iter guess x)
(new-if (good-enough? guess x)
guess
(sqrt-iter (improve guess x) x)))
1.8 此題實(shí)際上套用sqrt-iter的流程，需要重新實(shí)現(xiàn)improve和good-enough?過程
(define (improve guess x)
(/ (+ (/ x (* guess guess)) (* 2 y)) 3)
(define (cube x) (* x x x))
(define (close-enough? a b)
(< (abs (- (cube a) b)) 0.00001))
(define (cubert y)
(define (cubert-iter guess)
(if (close-enough? guess y)
guess
(cubert-iter (improve guess y))))
(cubert-iter 1.0))
我們可以對比下sqrt-iter的流程就會(huì)發(fā)現(xiàn)應(yīng)該能夠存在一個(gè)通用的流程來把這兩個(gè)統(tǒng)一起來，甚至可以應(yīng)用到求解其他N次方根的過程，而只需要將過程作為參數(shù)即可，這就是1.3章要講解的內(nèi)容了。
(define (rt-iter guess x improve good-enough?)
(if (good-enough? guess x)
guess
(rt-iter (improve guess x) x improve good-enough?)))
