軟件工程大師能夠組織好自己的程序顾稀，預(yù)先發(fā)現(xiàn)自己程序的行為方式达罗，即使發(fā)生問題也能很快的排出錯誤，就像一部汽車一樣静秆，擁有各個獨立的模塊粮揉，可以分別構(gòu)造、替換抚笔、排出錯誤扶认。我們這一章正是要了解這種抽象的能力，將對計算過程的認識從實際層面隔離開來殊橙，形成更為高階的抽象認識辐宾。
接下來的課程將使用Lisp中的scheme方言，這一語言應(yīng)用的范圍并不廣膨蛮，但是有一個很好的優(yōu)點是：計算過程的Lisp描述本身又可以作為Lisp的數(shù)據(jù)來表示和操作叠纹。
1.1 程序設(shè)計的基本元素（Lisp語言基礎(chǔ)知識）
在程序的設(shè)計中，我們必須要處理兩類：過程和數(shù)據(jù)敞葛。這一章的例子中我們使用的是簡單的數(shù)值數(shù)據(jù)吊洼，以將我們對注意力放在構(gòu)造過程對規(guī)則中去罐柳。
① 表達式
程序設(shè)計里面最簡單的就是表達式膏萧，你最好找到一個lisp的解釋器，輸入表達式然后得到響應(yīng)勇蝙，我使用的是DrRacket和mit-scheme豺鼻。
你可以嘗試輸入一些表達式综液，這里和我們平常的程序設(shè)計語言不同的是對于表達式的求值，使用的是前綴的方式儒飒，這樣也有兩個好處：1> 完全適用于任意多個實際參數(shù)的過程谬莹；2> 允許嵌套可以直接擴充；
我們建議在適用復(fù)雜的表達式的時候桩了，保持各運算對象的垂直對齊：
② 命名和環(huán)境
我們編寫復(fù)雜的程序附帽，也是一步步由簡單的過程構(gòu)成，如果必須記住并重復(fù)每一個細節(jié)井誉，這棟大廈是根本無法完工的蕉扮。好在解釋器提供了一個名字和對象的關(guān)聯(lián)功能，也就是lisp中的define颗圣，提供了一種由名字到過程的簡單抽象喳钟。
如此以來屁使，當(dāng)我們在計算圓周的時候就不需要重復(fù)的輸入pi和radius的值，直接經(jīng)由define定義的名字引用就可以了奔则。
解釋器提供的這種由符號到具體值的關(guān)聯(lián)過程也就意味著必須要有一種存儲能力蛮寂，這種存儲被稱為環(huán)境，而環(huán)境所扮演的角色就是用于確定表達式中各個符號的意義易茬。一個過程可能完全涉及多個不同的環(huán)境酬蹋，這點后面講。
③ 組合式的求值
組合式求值不難理解抽莱，一般來說有以下步驟：
1> 求值各個子表達式的值除嘹；
2> 將最左邊的運算符應(yīng)用于第一步求得的各個子表達式的值；
我們來看一個例子：
( *? ? ? ? ? (+ 2? (* 4 6) )
? ? ? ? ? ? ? (+ 3 5 7)? ? ? ? ? ? )
這一求值過程有三個子表達式岸蜗，共有4個運算符尉咕，我們畫一張圖來理解：
這個樹形分支結(jié)構(gòu)的每個節(jié)點的最左邊是我們的運算符，相應(yīng)的右邊是表達式或者具體的值璃岳。用這種結(jié)構(gòu)來看待求值的過程年缎，可以想象子表達式求得的值向上穿行，最終形成計算結(jié)果的一個過程（390）铃慷。
反復(fù)的運用于步驟1单芜，始終能把我們帶到一個子節(jié)點，他的最左邊是運算符犁柜，右邊是相應(yīng)的具體的值洲鸠，我們通常所說的運算符（+ - * /）其實也是指令序列與之關(guān)聯(lián)，也就是環(huán)境中的每個符號都有意義馋缅。
④ 定義過程
我們這里所說的過程就像我們最開始學(xué)習(xí)程序設(shè)計中的定義函數(shù)扒腕，這是一種威力更強大的抽象技術(shù)，我們可以組合多個操作萤悴，然后為其提供一個名字瘾腰，在lisp中我們?nèi)缦露x過程：
這一過程也就是：
（define (函數(shù)名? 形參）? （函數(shù)體）)
我們也可以將我們定義好的過程由于其他過程的定義中：
(define (sum-of-squares x y)? ? ? (+ (square x) (square y)) )
⑤ 過程求值的代換模型
我們這里要講解一個代換模型，而后的篇章將發(fā)現(xiàn)這個簡單模型越來越不適用覆履，直到必須使用更精細的模型取代蹋盆，這種從簡而繁的過程正是建立復(fù)制事物的基礎(chǔ)。
我們繼續(xù)定義函數(shù)f硝全，使得其有如下行為：
(define? (f a)? ? ? (sum-of-squares (+ a 1) (* a 2)))
我們來看看（f 5）的求值過程：
我們從實際參數(shù)5出發(fā)栖雾，一步一步向上求值，得到最終的結(jié)果136伟众，每一步我們都將得到的具體值傳遞給相應(yīng)的過程析藕。這樣的一個求值過程稱為應(yīng)用序。還有一種被稱為正則序的過程赂鲤，如下：
完全展開而后求值被就是正則序噪径，這兩種方式得到結(jié)果是一樣的，而應(yīng)用序剔除了重復(fù)計算的過程数初，效率更高找爱，Lisp采用的是應(yīng)用序。
⑥ 條件語句和斷言
這里使用cond條件的三條語句泡孩，將順序求值车摄，如果1，2仑鸥，3中有一為真吮播，表達式的結(jié)果就是其后的值，如果都為false的話cond的值就沒有定義眼俊。
變式意狠，else語句：
變式，if語句：
備注：復(fù)合邏輯運算符and,or,not同于我們學(xué)過的程序語言的求值方式疮胖，不作講解环戈。
⑦ 采用牛頓法求平方根
說明性的知識與存在性的知識之間本身存在著巨大的差異，在計算機的世界里我們需要的是更多行動性的知識澎灸，我們先來看看平方根的定義：
有了這個定義以后我們并不能轉(zhuǎn)化成有效的程序院塞，我們沒有相應(yīng)的求解的方式，只能簡單的對一個數(shù)是否是另一個數(shù)的平方根進行判斷性昭，來看看牛頓大神的方法（哪里都有他）：（牛頓法詳細為什么這么做）
假設(shè)我們要求出x的平方根拦止，初始的猜測值為y，我們只需要計算(y + (x / y))? /? 2糜颠，就能改進我們的猜測值汹族，隨著多次的迭代我們就將越來越趨近于我們的答案。有了方法以后其兴，我們來看看如何轉(zhuǎn)換成相應(yīng)的代碼：
1.2 過程與它們所產(chǎn)生的計算
我們在1.1節(jié)中已經(jīng)學(xué)習(xí)了編寫程序的基本規(guī)則鞠抑，但這還遠遠不夠，就像下象棋一樣忌警，你只了解基本的走法是不可能戰(zhàn)勝對手的搁拙，你必須要學(xué)會打譜，了解一下經(jīng)典的開局法绵、戰(zhàn)術(shù)和策略箕速。我們編寫的過程就是這種策略，要想成為編程專家朋譬，你必須要了解不同種類的過程所產(chǎn)生的計算過程和結(jié)果盐茎，所消耗的計算機資源以及計算過程的形狀。下面我們從最基本的過程策略講起：
① 線性的遞歸和迭代（兩種常見模式）
讓我們以階乘函數(shù) 徙赢，其數(shù)學(xué)定義為：
我們直接將其翻譯成遞歸代碼形式：
我們還可以使用一種線性的迭代字柠，它的原理就是如果我們準備3個變量探越，product保存乘積，counter作為計數(shù)器窑业，max-count作為我們要計算的數(shù)钦幔。當(dāng)我們同樣計算6的階乘的時候，我們首先令product為1常柄，計算器counter為1鲤氢，通過不斷的使用product = counter * product，counter = counter +1的方法西潘，更新counter卷玉，將乘積累積在product直到counter的值超越了所要求得的階乘值時，停止喷市，這一過程可以定義為如下函數(shù)：
兩種過程雖然都是同一個函數(shù)的求解相种，但是其計算過程的形狀完全不同，遞歸過程有一個完全展開而后計算收縮的鏈條品姓，這個鏈條是由解釋器負責(zé)維護蚂子；而迭代過程卻不需要有這一的鏈條，所有的東西都在product缭黔、counter食茎、max-count中保存，這種過程有變量更新計數(shù)馏谨，和函數(shù)結(jié)束時候的檢測别渔。
這里特別要注意一下，我們區(qū)分兩個概念：過程和計算過程惧互，當(dāng)我們所某一個過程是遞歸過程的時候哎媚，形如上面兩個過程是說其形式上都有調(diào)用自身的現(xiàn)象。但這兩個遞歸過程的計算過程卻不同喊儡，第一個遞歸調(diào)用過程的計算有線性遞歸拨与，而第二個遞歸過程的計算過程卻是線性迭代。所以說我們看事物的時候不要被起表面形式所迷惑艾猜，深究事物的本質(zhì)有其重大的意義买喧。
② 樹形遞歸
樹形遞歸是我們要介紹的另外一種計算模式，最典型的例子就是斐波拉契數(shù)列匆赃，數(shù)學(xué)定義我們就不再重復(fù)介紹淤毛，直接上代碼（遞歸形式）
其計算形狀為典型的樹形：
我們明顯看出這一計算過程有太多的重復(fù)，特別是對fib3的計算基本上占了大部分的內(nèi)容算柳。
當(dāng)然也可以使用迭代的方式低淡，構(gòu)建兩個變量a、b滿足如下關(guān)系：
完整的代碼如下：
兩個計算過程比較來看樹形遞歸的確不如迭代高效，但有一個明顯的優(yōu)點是便于理解蔗蹋，幾乎是斐波拉契數(shù)列的直譯版本何荚。如果使用迭代的方法，我們需要重構(gòu)這個過程猪杭，發(fā)現(xiàn)其中的奧秘餐塘，對大部分人來說可能過于困難。
實例：換零錢的方法統(tǒng)計
我們有5種貨幣：1美分胁孙、5美分唠倦、10美分称鳞、25美分涮较、50美分，換成1美元換法（美元里面美元角的概念冈止，所以1美元=100美分）描述如下：
1->（樹形左側(cè)）用了最大的面額的狂票，減去最大面額的值，繼續(xù)處理（默認使用最大面額）熙暴；
2->（樹形右側(cè)）沒有用最大面額兌換的闺属，不考慮最大的面額，繼續(xù)處理（不用最大面額）周霉；
畫個圖分析一下：
我并沒有畫完掂器，因為這個過程太過龐大了，但大致的結(jié)構(gòu)如上圖俱箱。
我們用一個簡化的圖形來說明這個過程：
計算的結(jié)果和我列舉的一樣7種狞谱，當(dāng)amount為0的時候只有一種乃摹；當(dāng)amount＜0或者貨幣沒有的時候為0種。
③ 增長率
我們有時候需要估算不同代碼在消耗計算資源上的不同跟衅，畢竟如果一個算法耗時太長以至于無法忍受的程度孵睬，就算其有解也是毫無意義的。我們引入一種標記方法：Θ（讀作theta）伶跷，R（n）表示一個在參數(shù)n的規(guī)模下掰读，所消耗的計算資源（resource），記為：
Θ（f（n）） =? R（n）
這一計算方法為我們在估算一個計算過程的問題規(guī)模改變時叭莫，提供了有用的線索磷支，對于某種計算過程：
這三種計算過程的不同步長，有同樣的增長率
④ 求冪
我們接下來的內(nèi)容具體分析一下不同計算過程的資源占用率食寡，看看如何改進我們的計算過程雾狈。求冪的數(shù)學(xué)定義我們就不作講解了，先來看看第一個版本：
這一模型基本上是數(shù)學(xué)函數(shù)的直接代碼翻譯抵皱，這一模型需要Θ（n）步和Θ（n）的空間（遞歸）善榛，我們很容易翻譯成迭代形式：
這一模型需要Θ（n）步和Θ（1）的空間辩蛋，我們還有方法改進這一模型嗎？
觀察這一一個事實：
對于指數(shù)為2的乘冪都可以使用以上這種方法求解移盆，計算模型變更為：
定義新的計算過程如下：
⑤ 最大公約數(shù)
最大公約數(shù)的數(shù)學(xué)定義我們不做解釋悼院，將一個著名的算法說一下，歐幾里得算法：
GCD（a咒循，b） = GCD（b据途，r）其中r是a除以b的余數(shù)
多次相除以后r必定為0，剩下的b就是最大公約數(shù)叙甸，看一個例子：
我們很容易將其翻譯成代碼計算過程：
分析其資源消耗率颖医，我們發(fā)現(xiàn)一個定理，Lame定理：歐幾里得算法所需要的k步計算出一對整數(shù)的gcd裆蒸，那個這兩個整數(shù)中較小的那個數(shù)必然大于或者等于第k個斐波拉契數(shù)熔萧。這樣，算法的增長率也就是Θ（log n）僚祷。
⑥ 實例：素數(shù)檢測
素數(shù)定義為在大于1的自然數(shù)中佛致，除了1和它自身外不能再有其他因子。最直接的方法就是從2開始直接計算被測驗數(shù)n是否能被整除辙谜，請看下面的代碼：
其中核心的函數(shù)是find-divisor俺榆，它有兩個參數(shù)，被測驗數(shù)n和測試因子（從2開始計算）装哆。這一函數(shù)的結(jié)束判斷有兩種罐脊，cond的第一個條件是被測驗數(shù)大于了n的開方，停止檢查（求值的范圍只能在1至n的開方之間）烂琴；第二個條件就是找到了能被整除的數(shù)test-divisor爹殊，結(jié)束檢查不是素數(shù)。else執(zhí)行我們的遞歸調(diào)用奸绷，更新測試數(shù)梗夸，繼續(xù)查驗。這也就意味著這一計算過程擁有the-tan的開方的增長率号醉。
費馬檢測法：
第二種方法使用的是反症，對于給定的整數(shù)n，隨機選取一個數(shù)a＜n畔派，計算出a的n次方除以n的余數(shù)铅碍，如果得到的結(jié)果不等于a，那么n就肯定不是素數(shù)线椰；如果得到的結(jié)果等于a胞谈，那么n是素數(shù)的概率就要大些。多次測驗以后我們的信心就會不斷的增強。我們來看看代碼：
先來看看主要函數(shù)fast-prime烦绳？卿捎，輸入兩個值被檢測數(shù)n和測驗次數(shù)times，當(dāng)測驗次數(shù)遞減為0任然沒有檢測出不是素數(shù)的話径密，輸出true午阵；否則調(diào)用fermat-test函數(shù)測驗n在隨機生成數(shù)a的情況下是否滿足費馬檢測條件，如果滿足素數(shù)的條件繼續(xù)下一次調(diào)用fast-prime享扔？底桂，并將次數(shù)times更新減去1；
再來看看fermat-test函數(shù)惧眠，主要使用的是random生成了1到n-1之間的隨機數(shù)a籽懦，放入try-it封裝的expmod函數(shù)進行處理，返回的結(jié)果與a比較看是否滿足費馬條件锉试；
最后來看看expmod函數(shù)猫十，它有三個參數(shù)隨機數(shù)base（隨機數(shù)）览濒，exp（冪）呆盖，和m（被測驗數(shù)），主要用于計算一個數(shù)的冪對另外一個數(shù)取模的結(jié)果贷笛，用到了1.2.4中的奇偶分形判別法应又，并將結(jié)果與被測驗數(shù)n取模的結(jié)果返回給調(diào)用函數(shù)。
總結(jié)一下乏苦，費馬檢測這種方法不同于我們已經(jīng)學(xué)到的其他算法株扛，通過費馬檢測的數(shù)只能說是概率上很有可能是素數(shù)，如果我們測驗的次數(shù)足夠多汇荐，我們能夠?qū)⑦@種概率調(diào)至任意我們滿意的程度洞就。這一類算法叫做概率算法。
1.3 使用高階過程構(gòu)造抽象
如果我們將過程限制為只能接受以數(shù)為參數(shù)掀淘，就會嚴重的限制我們構(gòu)建抽象的能力旬蟋，在這一小節(jié)中我們需要了解高階過程的抽象原理，所謂的高階過程就是以過程為參數(shù)革娄，或者以過程作為返回值的過程倾贰。
① 以過程作為參數(shù)
我們首先觀察三個過程：
雖然表面上看是三個不同的計算過程，但是其模型幾乎是一樣的拦惋，我們替換出來就是：
有了這個模型以后匆浙，我們嘗試寫出通用的求和算法：
同計算模型不同的地方是，這里有term和next兩個過程作為參數(shù)厕妖，只需要一些簡單的定義首尼，就可以用作計算a到b的立方和了：
同樣的原理，上面的三個例子都可以使用這種方法稍加改變就能開始計算。
② 用lambda構(gòu)造過程
lambda表達式提供了一個更加簡練的函數(shù)式語法來寫匿名方法软能，不需要定義過多的輔助過程挠羔。
使用的方法上和define相同，只是不提供相應(yīng)的函數(shù)名：
使用let創(chuàng)建局部變量：
假設(shè)我們有如下函數(shù)
為了便于理解埋嵌，我們令：
我們使用兩種方法定義這一計算過程（普通和lambda）：
這種結(jié)構(gòu)非常清晰和好用破加，以至于專門發(fā)明了一種叫做let的表達式：
使得var1具有exp1的值，var2具有exp2的值雹嗦，依次類推范舀。我們使用新的let表達式重寫上面的lambda結(jié)構(gòu)：
let表達式的第一部分維持的是一個變量名-表達式的對偶表，每個變量名關(guān)聯(lián)于對應(yīng)的表達式的值了罪，這些變量名都為let的局部變量锭环，再來求值let的body中的內(nèi)容。我們觀察到這一表達式僅僅是lambda表達式的一個變種泊藕，不需要解釋器再提供其他的新的機制就可以依靠lambda來實現(xiàn)辅辩。有兩點需要注意的地方：
1> let使得人們能在盡可能接近其使用的地方建立起局部變量約束；
2> 變量的值是在let之外計算的娃圆。（說明：
? ? 注：如果x的值是2玫锋，那么在let內(nèi)的x=3，y=4讼呢，y的值是在let之外計算的撩鹿，不同于其局部性變量x的值，這一點要特別的注意）
③ 找出函數(shù)零點（求根）和不動點的一般方法
區(qū)間折半法尋找方程的根：
這種方法的基本思路是如果有f(a)< 0 < f(b)也就是說f(a)和f(b)中必然有一個零點悦屏，我們可以通過求得a和b的平均值來計算出相應(yīng)的f(value)如果為正节沦，就同f(a)繼續(xù)計算中間點，如果為負础爬，就同f(b)計算中間點甫贯，函數(shù)逐漸逼近到我們想要的任何精度即可求出f(x) = 0。直接上代碼：
找出函數(shù)的不動點：
函數(shù)的不動點是指f(x) = x看蚜，對于某些函數(shù)叫搁，通過不斷的調(diào)用：
當(dāng)我們看到結(jié)果的value變化不大的時候，就說我們找到了函數(shù)的不動點失乾。請看代碼：
這時候我們回想起之前講到的計算某一個數(shù)的平方根常熙，我們將其轉(zhuǎn)換成一個方程就是：
為了不掉入一個無限循環(huán)，這里的y的取值范圍需要作如下處理：
代碼如下：
④ 過程作為返回值
我們這一小節(jié)研究的是如何將過程返回給調(diào)用函數(shù)碱茁，這將進一步提高我們程序的表達力裸卫。我們需要來看看在講述不動點尋找函數(shù)的平方根的例子中的平均阻尼思想化作新的一個以過程為返回值的函數(shù)
原來的函數(shù)是：
新定義一個average-damp函數(shù)如下：
這里的average-damp是一個過程，它的參數(shù)f也是一個過程纽竣，同樣的返回值是lambda定義的另外一個過程墓贿，我們使用這一新的技術(shù)來更新一起的計算平方根的過程：
這一新的計算方法很好的將三種技術(shù)：不動點搜尋茧泪、平均阻尼以及函數(shù)y=x/y，很好的結(jié)合在了同一個方法中聋袋，并且分割開來各有各的函數(shù)定義队伟。特別的清晰和便于理解。
計算一個數(shù)的平方根的方法我們使用了多種幽勒，但這種依靠不同部件的合理組合正是我們需要學(xué)習(xí)的能力嗜侮，因為它有很強的重構(gòu)能力。就像螺絲和螺母一樣啥容，我們依靠他可以建成高樓大廈锈颗，也能構(gòu)造座椅板凳。一點點的修改就可以用于計算一個數(shù)的立方根：
※ 牛頓法計算平方根：
現(xiàn)在我們再來看看我們之前講到過的使用牛頓法計算一個數(shù)的平方根的方法咪惠。這里用到了一個計算導(dǎo)數(shù)的過程還不是很理解击吱，寫在這里以后在回來看看（&*此處需要重復(fù)閱讀-2017-10-03*）：
一些想法：上面的這兩種計算一個數(shù)的平方根，其實都是在對函數(shù)的某個不動點求值的一種變化遥昧。站在這個層面上我們可以在上升一個臺階覆醇，造就出一個專門用于計算不動點的過程：
這就是我們所說的高階函數(shù)操作這些一般性的方法，建立了更高層次的一種抽象炭臭。真正的大師永脓，能從眾多令人迷惑不解的模式中識別出更高層次的抽象，并基于此去構(gòu)造更偉大的程序徽缚。這是一種能力憨奸，需要時間的打磨才能理解革屠、融匯凿试、貫通。時間還長似芝，路還遠那婉，還要努力。
2017年10月03日15:11:22 ? 完
