過程作為黑箱抽象.ppt

過程作為黑箱抽象,sqrt程序的分解過程: 這里的關鍵問題是，分解中的每一個 過程完成了一件可以標明的工作，這 使它們可以被用作定義其他過程的模 塊。我們可以將square看做一個黑箱， 根本無須關注該過程是如何計算出結 果的。更進一步，在相應過程還沒有 寫好之前，我們可以只關心square 這個名字，把它當做這個過程的抽象， 在這個抽象層次上任何能計算出平方 的過程都可以用。,過程作為黑箱抽象,可就是說，在只考慮過程的返回值時，下面兩個過程應是不可區(qū)分的： (define (square x) (* x x) (define (square x) (exp (double (log x) (define (double x) (+ x x) 可見一個過程定義應該能隱藏起某些細節(jié)，使得過程使用者可能不必自己去寫這些過程，而是從其他程序員那里作為黑箱接受過來。并且在使用時應該不需要去弄清楚它是如何實現(xiàn)的。,過程作為黑箱抽象,局部名： 過程用戶不必關心實現(xiàn)細節(jié)之一就是過程里面的形式參數(shù)的名字，如 (define (square y) (* y y) (define (square x) (* x x) 這兩個過程應該是無法區(qū)分的。 形式參數(shù)的具體名字是什么，完全沒有關系，這樣的名字稱為約束變量，一個過程的定義約束了它的所有形式參數(shù)。如果在一個完整的過程定義里將某個約束變量同一換名(注意不要跟其他形參名一樣，實際上過程的定義也不允許有相同的形參名)，這一過程定義的意義將不會改變。 不被約束的變量稱為自由的。 一個名字的定義被約束于的那一集表達式稱為這個名字的作用域 被聲明為這個過程的形式參數(shù)的那些約束變量，就以這個過程體作為他們的作用域,過程作為黑箱抽象,內部定義和塊結構： 我們再來回顧前面的sqrt程序，其由幾個相互分離的程序組成，問題是這組程序只有sqrt對用戶是重要的，其它過程則會帶來干擾。因此我們希望能夠將這種子過程局部化，將它們隱藏到sqrt的里面。 為使這種方式可能，我們要允許一個過程里面帶有一些內部定義，使它們是局部于這一過程的。如：,過程作為黑箱抽象,平方根程序的內部定義表示： (define (sqrt x) (define (good-enough? guess x) ( (abs (- (square guess) x) 0.001) (define (improve guess x) (average guess (/ x guess) (define (sqrt-iter guess x) (if (good-enough? guess x) guess (sqrt-iter (improve guess x) x) (sqrt-iter 1.0 x) 這種嵌套的定義稱為塊結構。,過程作為黑箱抽象,平方根程序的內部定義表示： 分析上面的過程一種更好的想法是，沒有必要顯示的把x在內部過程中傳來傳去了，既然它們都在x的作用域里，我們可以直接給出如下定義： (define (sqrt x) (define (good-enough? guess) ( (abs (- (square guess) x) 0.001) (define (improve guess) (average guess (/ x guess) (define (sqrt-iter guess) (if (good-enough? guess) guess (sqrt-iter (improve guess) (sqrt-iter 1.0) 這種方式叫做詞法作用域。,線性的遞歸和迭代,考慮階乘函數(shù)： (define (factorial n) (if (= n 1) 1 (* n (factorial (- n 1) 我們利用代換模型， 觀看其求值的行為如圖：,遞歸和迭代,計算階乘函數(shù)的不同的觀點： (define (factorial n) (fact-iter 1 1 n) (define (fact-iter product counter max-count) (if ( counter max-count) product (fact-iter (* counter product) (+ counter 1) max-count),遞歸和迭代,計算階乘函數(shù)的兩種不同方法的比較： 第一個過程中，代換模型揭示出一種先逐步展開而后收縮的形狀，展開階段里，構造起一個推遲操作所形成的鏈條(如前面的乘法鏈條)，收縮階段表現(xiàn)為這些運算的實際執(zhí)行。 這種由一個推遲執(zhí)行的運算鏈條刻畫的計算過程，稱為一個遞歸計算過程 與之相對應，第二個計算過程里并沒有任何增長或收縮。對任何一個n，計算過程的每一步，我們需要保存軌跡里，所有的東西就是變量的當前值，我們稱這種過程為一個迭代計算過程。一般來說，迭代計算過程就是那種其狀態(tài)可以用固定數(shù)目的狀態(tài)變量描述的計算過程；同時還存在一套固定的規(guī)則，描述了計算過程在狀態(tài)轉換時，變量的更新方式。 注意：不要混淆遞歸計算過程和遞歸過程的概念。遞歸過程是一個語法形式上的事實，說明一個過程定義中直接或間接引用了該過程本身。所以我們可以有如下陳述：一個遞歸過程將產(chǎn)生出一個迭代的計算過程。這是由于scheme中使用了一種稱為尾遞歸的編譯技術。,遞歸和迭代,樹形遞歸： 計算斐波那契數(shù)列： (define (fib n) (cond (= n 0) 0) (= n 1) 1) (else (+ (fib (- n 1) (fib (- n 2) 考慮(fib 5)的計算過程： 可以證明計算步驟 相對于n是指數(shù)的 這是一種很糟糕的計算過程。 一般說，樹形遞歸計算過程所需的步驟數(shù)正比與書中的結點數(shù)，空間需求正比于樹的最大深度。,遞歸和迭代,計算斐波那契數(shù)列的迭代過程： (define (fib n) (fib-iter 1 0 n) (define (fib-iter a b count) (if (= count 0) b (fib-iter (+ a b) a (- count 1) 所需的步驟數(shù)相對于n是線性的 但我們也不應作出結論說遞歸計算過程根本沒用。相反遞歸計算過程很自然，往往就是算法的直接翻譯，能幫助我們理解和設計程序，而要規(guī)劃出迭代過程，就不那么明顯了。,實例研究：數(shù)的求冪,問題描述： 計算出bn的值，我們有遞歸定義： bn=b*bn-1 b0=1 直接翻譯如下： (define (expt b n) (if (= n 0) 1 (* b (expt b (- n 1) 這是一個線性遞歸計算過程，需要O(n)步和O(n)空間,實例研究：數(shù)的求冪,等價的線性迭代過程如下： (define (expt b n) (expt-iter b n 1) (define (expt-iter b counter product) (if (= counter 0) product (expt-iter b (- counter 1) (* b product) 需要O(n)步和O(1)空間,實例研究：數(shù)的求冪,算法的改進： 我們可以通過連續(xù)求平方，以更少的步驟完成乘冪的計算。如： b2=b*b b4=b2*b2 b8=b4*b4 三次乘法就可以把b8算出來，而開始的算法主要計算7次乘法。 (define (fast-expt b n) (cond (= n 0) 1) (even? n) (square (fast-expt b (/ n 2) (else (* b (fast-expt b (- n 1) even?是檢測一個整數(shù)是否是偶數(shù)的謂詞 (define (even? n) (= (remainder n 2) 0) 這是一個遞歸計算過程，該過程的增長階為O(logn) 給出該過程相應的迭代算法？,用高階函數(shù)做抽象,如果將過程限制為只能以數(shù)作為參數(shù)，那也會嚴重地限制我們建立抽象的能力。經(jīng)常有一些同樣的程序設計模式能用于若干不同的過程。為了把這種模式描述為相應的概念，我們就需要構造出這樣的過程，讓他們以過程作為參數(shù)，或者以過程作為返回值。這類能操作過程的過程稱為高階過程,用高階函數(shù)做抽象,過程作為參數(shù)： 考慮下面3個過程： 1.計算從a到b的各整數(shù)之和： (define (sum-integers a b) (if ( a b) 0 (+ a (sum-integers (+ a 1) b) 2.計算給定范圍內的整數(shù)的立方之和： (define (sum-cubes a b) (if ( a b) 0 (+ (cube a) (sum-cubes (+ a 1) b),用高階函數(shù)做抽象,3.計算下面的序列之和： 1/(1*3)+ 1/(5*7)+ 1/(9*11)+ 它將收斂到/8： (define (pi-sum a b) (if ( a b) 0 (+ (/ 1.0 (* a (+ a 2) (pi-sum (+ a 4) b) 可以明顯看出上面三個過程共享著一種公共模式：其形式如下： (define ( a b) (if ( a b) 0 (+ ( a) ( ( a) b),用高階函數(shù)做抽象,這種公共模式的存在是一種很強的證據(jù)，說明這里實際上存在著一種很有用的抽象，確實這里用到了求和這一抽象概念，數(shù)學家在很早以前就使用了專門的記號，如： , 這種記法的威力就在于它使數(shù)學家能去處理求和的概念本身，而不只是某個特定的求和。 在這里我們自然希望在使用的程序設計語言中也能寫出這一抽象的過程，而不是只能寫計算特定求和的過程。所幸的是我們所使用的語言提供了這種機制。,用高階函數(shù)做抽象,按照上面的模式，將其中“空位”翻譯為形式參數(shù)： (define (sum term a next b) (if ( a b) 0 (+ (term a) (sum term (next a) next b) 過程sum體現(xiàn)出的就是求和概念的本身，即： 這里的函數(shù)f就對應上面的term，不過sum過程還有一個過程參數(shù)next，它的作用是用來產(chǎn)生后繼的求和參數(shù)。 這樣我們就可以用sum過程來定義其他各種具體的求和過程了。,用高階函數(shù)做抽象,例如： 我們可以用sum重新定義sum-cubes過程如下： (define (cube x) (* x x x) (define (inc n) (+ n 1) (define (sum-cubes a b) (sum cube a inc b) 重新定義sum-integers過程如下： (define (identity x) x) (define (sum-integers a b) (sum identity a inc b),用高階函數(shù)做抽象,重新定義pi-sum過程如下： (define (pi-sum a b) (define (pi-term x) (/ 1.0 (* x (+ x 2) (define (pi-next x) (+ x 4) (sum pi-term a pi-next b) 利用這一過程就能計算的一個近似值了： (* 8 (pi-sum 1 1000) 3.139592655589783 思考： 利用sum定義函數(shù)的近似積分過程(integral f a b dx)，利用如下公式：,用高階函數(shù)做抽象,用lambda構造匿名過程 在前面如果我們要用到一個過程，就必須先給該過程定義一個名稱，然后再在其他過程中通過名字使用該過程。這里我們給出一種定義匿名過程的方法，我們通過引入一種lambda特殊形式完成。 一般而言，lambda用與define同樣的方式創(chuàng)建過程，除了不為有關過程提供名字之外：語法形式如下： (lambda () ) 例如我們可以定義： (lambda (x) (+ x 4) 相應的define定義： (define (plus x) (+ x 4) 等價于: (define (plus x) (lambda (x) (+ x 4) 我們可以按如下方式來閱讀lambda表達式： (lambda (x) (+ x 4)：(該過程 (以x為參數(shù)) (它加起 x 和4),用高階函數(shù)做抽象,我們用lambda重新定義pi-sum過程如下： (define (pi-sum a b) (sum (lambda (x) (/ 1.0 (* x (+ x 2) a (lambda (x) (+ x 4) b) 請利用lambda重新定義過程integral？,用高階函數(shù)做抽象,用let創(chuàng)建局部變量： 考慮計算函數(shù)：f(x,y)=x(1+xy)2+y(1-y)+(1+xy)(1-y) 我們可能希望將它表述為： a=(1+xy) b= (1-y) f(x,y)=xa2+yb+ab 所以在寫f的過程時,我們希望有局部變量，而不止是參變量x和y。為做到這點我們可以用一個匿名的輔助過程來實現(xiàn)，如下： (define (f x y) (lambda (a b) (+ (* x (square a) (* y b) (* a b) (+ 1 (* x y) (- 1 y),用高階函數(shù)做抽象,在我們的程序設計中這一結構非常具有普遍性，因此，語言里專門有一個特殊形式稱為let，使這種編程方式更為方便。一般形式為： (let ( ) ( ) ( ) ) 解釋器把let表達式解釋為lambda表達式的一種語法外衣，形式如下： (lambda ( ) ) ) 根據(jù)這一等價，let表達式描述的變量的作用域就是該let的體，這使我們可以在接近使用的地方創(chuàng)建局部變量,用高階函數(shù)做抽象,利用let，過程f可以重寫如下： (define (f x y) (let (a (+ 1 (* x y) (b (- 1 y) (+ (* x (square a) (* y b) (* a b),用高階函數(shù)做抽象,實例研究：找出函數(shù)的不動點 問題描述： 稱數(shù)x為函數(shù)f的不動點，如果x滿足f(x)=x，對于某些函數(shù)，通過從某個初始猜測出發(fā)，反復地應用f直到值的變化不大時，就可以找到它的一個不動點。f(x),f(f(x),f(f(f(x), 根據(jù)這個思路我們設計一個過程fixed-point，反復應用這個函數(shù)，直到發(fā)現(xiàn)連續(xù)的兩個值之差小于某個并事先給定的容許值。,用高階函數(shù)做抽象,(define tolerance 0.00001) (define (fixed-point f first-guess) (define (close-enough? v1 v2) ( (abs (- v1 v2) tolerance) (define (try guess) (let (next (f guess) (if (close-enough? guess next) next (try next) (try first-guess),用高階函數(shù)做抽象,這一過程類似于我們前面講的sqrt的過程，事實上，我們完全可以將平方根的就算形式化為一個不動點的計算過程。將有y2=x化為y=x/y，可以發(fā)現(xiàn)，這里要做的就是尋找函數(shù)y=x/y的不動點。如： (define (sqrt x) (fixed-point (lambda (y) (/ x y) 1.0) 但是該過程不動點的搜尋并不收斂，我們改進算法如下： (define (sqrt x) (fixed-point (lambda (y) (average y (/ x y) 1.0) 應為實際答案總是在兩個猜測y和x/y之間，為此可以用y和x/y的平均值做猜測值。這種取逼近一個解的一系列值的平均值的方法，是一種稱為平均阻尼的技術。,用高階函數(shù)做抽象,過程作為返回值： 考慮前面的不動點搜尋的算法，我們利用了平均阻尼使這一逼近收斂。但平均阻尼也是一種很有用的一般性技術。很自然，我們希望單獨考慮這一思想：給定一個函數(shù)f后，我們可以考慮另一個函數(shù)，它在x處的值等于x和f(x)的平均值。 我們可以表述如下： (define (average-damp f) (lambda (x) (average x (f x) 利用average-damp我們可以重寫平方根過程如下： (define (sqrt x) (fixed-point (average-damp (lambda (y) (/ x y) 1.0),用高階函數(shù)做抽象,實例研究：牛頓法求函數(shù)的零點 問題描述：如果g(x)是一個可微函數(shù)，那么g(x)=0的一個解就是 f(x)=x