Posted on 2008-03-18 19:34
dennis 閱讀(7697)
評論(11) 編輯 收藏 所屬分類:
計算機科學(xué)與基礎(chǔ)
讀《代碼大全2》，已經(jīng)讀了一半，喘口氣。總結(jié)八個字：百科全書，受益匪淺。小到一個賦值語句、一個循環(huán)的編寫，大到需求分析、架構(gòu)設(shè)計，無所不包，看后半部分目錄，更是扯到了重構(gòu)、軟件工藝、程序員的性格特征這樣的話題。恰好手邊的工作暫時比較有閑，可以實踐下“創(chuàng)建高質(zhì)量的代碼”中的部分建議，晚上讀書，第二天就重構(gòu)，樂在其中。這一部分中對設(shè)計、子程序、類、變量、語句的處理建議，可能你平常已經(jīng)在這么做，可作者這么精辟地概括出來讓人嘆服，而有些地方是你平常絕對很少注意的，特別是在變量和三種常見控制語句的處理上。
說說我認為是缺點的地方，就是作者貌似對函數(shù)式語言了解很少，舉的例子全部用的是廣泛應(yīng)用的靜態(tài)語言（c/c++,java,vb)。例如作者有這么一句話：
如果為我工作的程序員用遞歸去計算階乘，那么我寧愿換人。作者對遞歸的態(tài)度相當謹慎，這在靜態(tài)命令式語言中顯然是正確的，但是在函數(shù)式語言中，由于有尾遞歸優(yōu)化的存在，遞歸反而是最自然的形式，況且我打心里認為遞歸更符合人類思維。請注意，在FP中只有尾遞歸的程序才是線性迭代的，否則寫出來的遞歸可能是線性遞歸或者樹形遞歸，兩種情況下都可能導(dǎo)致堆棧溢出并且性能較差。
scheme寫階乘：
(define (fac n)
(if (= 1 n)
1
(* n (fac (- n 1)))))
顯然這個版本不是尾遞歸，計算過程是一個線性遞歸過程，計算(fac 4)的過程如下：
(* 4 （fac 3))
(* 4 (3 * (fac 2)))
(* 4 (3 * (* 2 (fac 1))))
(* 4 (3 * (* 2 1)))
(* 4 (3 * 2))
(* 4 6)
24
因為解釋器是采用應(yīng)用序求值，需要將表達式完全展開，然后依次求值，在這個過程中，解釋器內(nèi)部需要保存一條長長的推遲計算的軌跡。
改寫成一個尾遞歸版本：
(define (fac n)
(define (fac-iter product n)
(if (= 1 n)
product
(fac-iter (* n product) (- n 1))))
(fac-iter 1 n))
我們來看看它的計算過程：
(fac-iter 1 4)
(fac-iter 4 3)
(fac-iter 12 2)
(fac-iter 24 1)
24
可以看到，在這個過程中，解釋器不需要保存計算軌跡，迭代的中間結(jié)果通過product變量來保存，這是一個線性迭代的計算過程。
最后再看一個
斐波拉契數(shù)列的例子：
(define (fib n)
(cond ((= n 0) 0)
((= n 1) 1)
(else
(+ (fib (- n 1)) (fib (- n 2))))))
這個計算過程展開是一個樹形遞歸的過程(為什么說是樹形？展開下計算過程就知道），改寫為線性迭代：
(define (fib n)
(define (fib-iter a b count)
(if (= count 0)
b
(fib-iter (+ a b) a (- count 1))))
(fib-iter 1 0 n))
上述的內(nèi)容在sicp第一章里有更詳細的介紹和討論。