1、構(gòu)造數(shù)據(jù)抽象 到目前為止，我們操作的都是簡單的數(shù)值數(shù)據(jù)，而對我們希望處理的許多問題而言，這種簡單數(shù)據(jù)還不夠。許多程序在設(shè)計時就是為了模擬復(fù)雜的對象，因此他們就常常需要構(gòu)造起一些計算對象。 與我們在前面所做的事情一樣，我們將重點轉(zhuǎn)到各種程序設(shè)計語言的另一關(guān)鍵方面：討論他們所提供的，將數(shù)據(jù)對象組合起來，形成復(fù)合數(shù)據(jù)的方式，并進(jìn)一步去考查更復(fù)雜的數(shù)據(jù)。同樣的我們還將要看到，與過程抽象相對應(yīng)的，另一種強(qiáng)有力的設(shè)計方法學(xué)數(shù)據(jù)抽象構(gòu)造數(shù)據(jù)抽象數(shù)據(jù)抽象是一種方法學(xué)，它使我們能夠?qū)⒁粋€復(fù)合數(shù)據(jù)對象的使用，與該數(shù)據(jù)對象怎樣由更基本的數(shù)據(jù)對象構(gòu)造起來的細(xì)節(jié)隔離開來。其基本思想，就是設(shè)法構(gòu)造出一些使用復(fù)合對象的程序

2、，使它們就像是在“抽象數(shù)據(jù)”上操作一樣。也就是說，我們的程序中使用數(shù)據(jù)的方式應(yīng)該是這樣的：除了完成當(dāng)前工作所必要的東西之外，它們不對所用數(shù)據(jù)做任何多余的假設(shè)。與此同時，一種“具體”數(shù)據(jù)表示的定義，也應(yīng)該與程序中使用數(shù)據(jù)的方式無關(guān)。我們利用一組稱為選擇函數(shù)和構(gòu)造函數(shù)的過程作為這兩個部分之間的界面。構(gòu)造數(shù)據(jù)抽象實例研究：有理數(shù)的算術(shù)運(yùn)算我們希望能做有理數(shù)的加減乘除，比較兩個有理數(shù)是否相等。我們假定已經(jīng)有了一種從分子和分母構(gòu)造有理數(shù)的方法。進(jìn)一步假定，如果有了一個有理數(shù)，我們有一種方法取得它的分子和分母?，F(xiàn)在再假定有關(guān)的構(gòu)造函數(shù)和選擇函數(shù)都可以做為過程使用：(make-rat )返回一個有理數(shù)，其分

3、子是整數(shù)，分母是整數(shù)(numer )返回有理數(shù)的分子(denom )返回有理數(shù)的分母這里使用一種稱為按愿望思維的策略。現(xiàn)在我們還沒有說有理數(shù)將如何表示，也沒有說過程make-rat，numer和denom應(yīng)如何實現(xiàn)。利用這三個過程我們就可以實現(xiàn)有理數(shù)的運(yùn)算了構(gòu)造數(shù)據(jù)抽象有理數(shù)運(yùn)算過程的實現(xiàn)：加法過程：(define (add-rat x y) (make-rat (+ (* (numer x) (denom y) (* (numer y) (denom x) (* (denom x) (denom y)減法過程：(define (sub-rat x y) (make-rat (- (* (nu

4、mer x) (denom y) (* (numer y) (denom x) (* (denom x) (denom y)構(gòu)造數(shù)據(jù)抽象乘法過程：(define (mul-rat x y) (make-rat (* (numer x) (numer y) (* (denom x) (denom y)除法過程：(define (div-rat x y) (make-rat (* (numer x) (denom y) (* (denom x) (numer y)相等判斷過程：(define (equal-rat? x y) (= (* (numer x) (denom y) (* (numer

5、y) (denom x)構(gòu)造數(shù)據(jù)抽象有理數(shù)的表示：我們已經(jīng)定義了在過程make-rat，numer和denom基礎(chǔ)上的各種有理數(shù)的運(yùn)算過程，而這些基礎(chǔ)還沒有定義?，F(xiàn)在需要某種方式，將一個分子和一個分母粘接起來，構(gòu)成一個有理數(shù)。在實現(xiàn)有理數(shù)之前我們先來看看我們所用的語言提供的一種稱為序?qū)Φ膹?fù)合數(shù)據(jù)。序?qū)橥瓿蛇@里的有理數(shù)系統(tǒng)提供了一種自然的方式，我們可以將有理數(shù)簡單的表示為兩個整數(shù)（分子和分母）的序?qū)?。?gòu)造數(shù)據(jù)抽象序?qū)Γ和瑯游覀冎魂P(guān)心序?qū)x擇函數(shù)和構(gòu)造函數(shù)的形式，而實際過程已由解釋器實現(xiàn)了(cons ),過程cons取兩個參數(shù)，返回一個包含這兩個參數(shù)作為其成分的復(fù)合數(shù)據(jù)對象(car )，其序?qū)χ?/p>

6、的第一個參數(shù)(cdr )，其序?qū)χ械牡诙€參數(shù)注意一個序?qū)σ彩且粋€數(shù)據(jù)對象，可以像基本數(shù)據(jù)對象一樣給它一個名字且操作它。還可用cons構(gòu)造其元素本身就是序?qū)Φ男驅(qū)Γ纾?define x (cons 1 2)(define y (cons 3 4)(define z (cons x y)(car (car z)1(car (cdr z)2構(gòu)造數(shù)據(jù)抽象基于序?qū)Φ挠欣頂?shù)的表示：(define (make-rat n d) (cons n d)(define (numer x) (car x)(define (denom x) (cdr x)為了顯示計算結(jié)果我們再定義一個打印函數(shù)，它以一個有理數(shù)作

7、為輸入并把它打印出來。(define (print-rat x) (newline) (display (numer x) (display /) (display (denom x)這里我們用到了兩個scheme的基本內(nèi)置過程display和newline。 Display為打印數(shù)據(jù)的基本過程， newline為隨后的打印開始一個新行。構(gòu)造數(shù)據(jù)抽象(define one-half (make-rat 1 2)(print-rat one-half)(define one-third (make-rat 1 3)(print-rat (add-rat one-half one-third)(p

8、rint-rat (mul-rat one-half one-third)(print-rat (add-rat one-third one-third)看看上面的過程都會打印出什么？從打印結(jié)果你們發(fā)現(xiàn)了什么問題？能否改進(jìn)？構(gòu)造數(shù)據(jù)抽象抽象屏障：在繼續(xù)討論之前，讓我們首先回顧一下有理數(shù)系統(tǒng)的結(jié)構(gòu)： 問題域中的有理數(shù) 作為分子和分母的有理數(shù) 作為序?qū)Φ挠欣頂?shù) 當(dāng)然序?qū)σ残枰獙崿F(xiàn)使用有理數(shù)的程序add-rat sub-rat cons car cdrmake-rat number denom構(gòu)造數(shù)據(jù)抽象 其中的水平線表示抽象屏障，它隔離了系統(tǒng)的不同層次，它把使用數(shù)據(jù)的程序和實現(xiàn)數(shù)據(jù)的程序分開，使得

9、一層中的過程的實現(xiàn)與其他層的過程的實現(xiàn)完全無關(guān)。從作用上看，每一層中的過程構(gòu)成了所定義的抽象屏障的界面，聯(lián)系起系統(tǒng)中的不同層次。 這種簡單思想有許多優(yōu)點：這種方法使程序很容易維護(hù)和修改有助于程序的設(shè)計，使我們能保留考慮不同實現(xiàn)方式的靈活性，使我們能推遲決策的時間，而又不會阻礙系統(tǒng)其他部分的工作進(jìn)展。你能給出幾種不同的有理數(shù)表示？它們各有什么優(yōu)缺點？構(gòu)造數(shù)據(jù)抽象數(shù)據(jù)意味著什么前面我們看到在抽象層面上數(shù)據(jù)可以描述為一組選擇函數(shù)和構(gòu)造函數(shù)，但是說它就是“由給定的選擇函數(shù)和構(gòu)造函數(shù)所實現(xiàn)的東西”還是不夠的。顯然，并不是任意的三個過程都適合作為有理數(shù)實現(xiàn)的基礎(chǔ)。這里我們還需要保證，如果從整數(shù)n和d構(gòu)造出

10、一個有理數(shù)x，那么抽取出的x的number和denom并將他們相除，得到的結(jié)果應(yīng)該與n除以d相同。也就是說這些基本過程的選擇是帶有約束的。一般而言，我們總可以將數(shù)據(jù)定義為一組適當(dāng)?shù)倪x擇函數(shù)和構(gòu)造函數(shù)，以及為使這些過程成為一套合法表示，它們就必須滿足的一組特定條件。從上面我們可以得出一個結(jié)論：數(shù)據(jù)其實就是一組定義良好的過程。確實，考慮序?qū)Γ覀兺耆梢圆挥萌魏螖?shù)據(jù)結(jié)構(gòu)，只用過程實現(xiàn)它。構(gòu)造數(shù)據(jù)抽象序?qū)Φ倪^程實現(xiàn)：(define (cons x y) (define (dispatch m) (cond (= m 0) x) (= m 1) y) (else (error Argument not

11、 0 or 1 - CONS m) dispatch)(define (car z) (z 0)(define (cdr z) (z 1)這確實與我們有關(guān)數(shù)據(jù)應(yīng)該是什么的直觀認(rèn)識大相徑庭。這一實例說明可以將過程作為對象去操作，因此就自動地為我們提供了一種表示復(fù)合數(shù)據(jù)的能力。這些東西現(xiàn)在看起來好像只是很好玩，但實際上，數(shù)據(jù)的過程性表示將在我們的程序設(shè)計寶庫里扮演一種核心角色。有關(guān)的程序設(shè)計風(fēng)格通常稱為消息傳遞。層次性數(shù)據(jù)和閉包性質(zhì) 前面已經(jīng)看到，序?qū)槲覀兲峁┝艘环N用于構(gòu)造復(fù)合數(shù)據(jù)的基本“粘接劑”，我們可以建立元素本身也是序?qū)Φ男驅(qū)Γ驅(qū)Φ倪@種能力稱為cons的閉包性質(zhì)。一般說，某種數(shù)據(jù)對象的操

12、作滿足閉包性質(zhì)，就是說，通過它組合起數(shù)據(jù)對象得到的結(jié)果本身還可以通過同樣的操作再進(jìn)行組合。閉包性質(zhì)是任何一種組合功能的威力的關(guān)鍵要素，它使我們能夠建立起層次性的結(jié)構(gòu)。層次性數(shù)據(jù)和閉包性質(zhì)層次性結(jié)構(gòu)的表示：圖中展示的是序?qū)Φ臉?biāo)準(zhǔn)表示，其中的序?qū)κ峭ㄟ^(cons 1 2)形成的。這種稱為盒子和指針表示方式中，每個對象表示為一個指向盒子的指針。與基本對象相對應(yīng)的盒子包含著該對象的表示。復(fù)合層次結(jié)構(gòu)的表示：層次性數(shù)據(jù)和閉包性質(zhì)序列的表示：我們可以用序?qū)?gòu)造一種有用的數(shù)據(jù)結(jié)構(gòu)序列，它是一批數(shù)據(jù)對象的一種有序匯集。采用序?qū)Ρ硎拘蛄杏泻芏喾N方式，在這里我們采用一種標(biāo)準(zhǔn)的方式來表示。下面是對序列1，2，3，4

13、的表示：(cons 1 (cons 2 (cons 3 (cons 4 nil)通過嵌套的cons形成的這樣一個序?qū)Φ男蛄蟹Q為一個表，scheme為方便表的構(gòu)造，提供了一個基本操作list，如(list 1 2 3 4)。一般的：(list . )等價于：(cons (cons (cons . (cons nil) . ) 層次性數(shù)據(jù)和閉包性質(zhì)序?qū)Φ拇蛴。?cons 1 2); (1 . 2)(cons (cons 1 2) (cons 3 4);(1 . 2) 3 . 4)(cons 1 (cons 2 (cons 3 nil);(1 2 3) 層次性數(shù)據(jù)和閉包性質(zhì)表的打印：(list 1

14、2 3 4);(1 2 3 4)(define one-through-four (list 1 2 3 4)one-through-four;: (1 2 3 4)(car one-through-four);: 1(cdr one-through-four);:(2 3 4)(car (cdr one-through-four);:2(cons 10 one-through-four);:(10 1 2 3 4) 層次性數(shù)據(jù)和閉包性質(zhì)表操作：利用序?qū)⒃乇硎緸楸碇?，我們就可以使用常?guī)的程序設(shè)計技術(shù)，通過”向下cdr”表的方式完成對表的各種操作了。l返回指定標(biāo)號的元素操作：list-re

15、f(define (list-ref items n) (if (= n 0) (car items) (list-ref (cdr items) (- n 1)(define squares (list 1 4 9 16 25);:(list-ref squares 3)16注意：這里我們習(xí)慣令表元素的編號從0開始。 層次性數(shù)據(jù)和閉包性質(zhì)l返回表的長度操作： length(define (length items) (if (null? items) 0 (+ 1 (length (cdr items)(define odds (list 1 3 5 7)(length odds)4這里我們

16、需要用到scheme提供的一個基本操作null?，用于檢查參數(shù)是不是空表。上面的過程是一個遞歸的過程，空表的length為0，任一表的length等于其cdr的length加1.給出迭代的length過程？ 層次性數(shù)據(jù)和閉包性質(zhì)l連接表操作： append(define (append list1 list2) (if (null? list1) list2 (cons (car list1) (append (cdr list1) list2)(append squares odds);: (1 4 9 16 25 1 3 5 7)(append odds squares);: (1 3 5

17、 7 1 4 9 16 25)append也是一種遞歸方案，能否給出迭代形式？ 層次性數(shù)據(jù)和閉包性質(zhì)對表的映射：例：對給定表的所有元素按給定因子做一次放縮(define (scale-list items factor) (if (null? items) nil (cons (* (car items) factor) (scale-list (cdr items) factor)(scale-list (list 1 2 3 4 5) 10);:(10 20 30 40 50) 這里我們想抽象出這一具有一般性的想法，將其中公共模式表述為一個高階過程，這一高階過程稱為map，它有一個過程參數(shù)

18、和一個表參數(shù)，返回將這一過程應(yīng)用于表中各個元素得到的結(jié)果形成的表。 層次性數(shù)據(jù)和閉包性質(zhì)對表的映射過程：map(define (map proc items) (if (null? items) nil (cons (proc (car items) (map proc (cdr items)(map (lambda (x) (* x x) (list 1 2 3 4)(1 4 9 16)用map重新定義scale-list過程：(define (scale-list items factor) (map (lambda (x) (* x factor) items) 層次性數(shù)據(jù)和閉包性質(zhì)層次

19、性結(jié)構(gòu)：(1 2) 3 4)是通過(cons (list 1 2) (list 3 4)構(gòu)造出來的，其結(jié)構(gòu)如下：認(rèn)識這種元素本身也是序列的序列的另一種方式，是把它們看作樹。序列里的元素就是樹的分支，而那些本身也是序列的元素就形成了樹中的子樹。如圖： 層次性數(shù)據(jù)和閉包性質(zhì)樹操作：統(tǒng)計葉子數(shù)目操作：count-leaves(define (count-leaves x) (cond (null? x) 0) (not (pair? x) 1) (else (+ (count-leaves (car x) (count-leaves (cdr x)為了實現(xiàn)這一過程，我們需要一個判斷參數(shù)是否為序?qū)Φ暮?/p>

20、數(shù)，scheme提供了基本過程pair? 層次性數(shù)據(jù)和閉包性質(zhì)對樹的映射：(define (scale-tree tree factor) (cond (null? tree) nil) (not (pair? tree) (* tree factor) (else (cons (scale-tree (car tree) factor) (scale-tree (cdr tree) factor)(scale-tree (list 1 (list 2 (list 3 4) 5) (list 6 7)10);:(10 (20 (30 40) 50) (60 70)該過程以一個數(shù)值因子和一顆葉子

21、為數(shù)值的樹作為參數(shù)，返回一顆具有同樣形狀的樹。 層次性數(shù)據(jù)和閉包性質(zhì)下面我們利用前面介紹表的map過程重寫如下：(define (scale-tree tree factor) (map (lambda (sub-tree) (if (pair? sub-tree) (scale-tree sub-tree factor) (* sub-tree factor) tree)也已看到這里map過程的寫法已經(jīng)沒有在用于處理表時那么自然了，究其原因是因為map過程并不具備處理層次結(jié)構(gòu)的能力，這樣我們在使用是就必須把相關(guān)處理寫到其參數(shù)proc的過程里面。自然地，我們希望能有一個能處理這種層次結(jié)構(gòu)的ma

22、p過程，當(dāng)然其肯定也包含了處理表結(jié)構(gòu)的能力，應(yīng)為樹結(jié)構(gòu)是一種比表更抽象的結(jié)構(gòu)。 層次性數(shù)據(jù)和閉包性質(zhì)重寫前面的map過程如下：(define (map proc items) (cond (null? items) nil) (pair? items) (cons (map proc (car items) (map proc (cdr items) (else (proc items)請利用新定義的map過程重寫scale-list和scale-tree 層次性數(shù)據(jù)和閉包性質(zhì)序列作為一種約定的界面：下面這個例子以一棵樹為參數(shù)，計算出那些值為奇數(shù)的葉子的平方：(define (sum-odd-

23、squares tree) (cond (null? tree) 0) (not (pair? tree) (if (odd? tree) (square tree) 0) (else (+ (sum-odd-squares (car tree) (sum-odd-squares (cdr tree)該過程的大致處理步驟如下：l枚舉出一棵樹的樹葉；l過濾他們，選出其中的奇數(shù)；l對選出的每個數(shù)求平方；l再用+累積起得到的結(jié)果，從0開始。 層次性數(shù)據(jù)和閉包性質(zhì)這種過程可以很自然地用流過一些級聯(lián)的處理步驟的信號的方式描述，其中的每個處理步驟實現(xiàn)程序方案中的一個部分，如圖所示：我們從一個枚舉器開始，它

24、產(chǎn)生出由個給定的樹的所有樹葉組成“信號”。這一信號流過一個過濾器，所有不是奇數(shù)的數(shù)都被刪除了。這樣得到的信號又通過一個映射，這是一個“轉(zhuǎn)換裝置”，它將square過程應(yīng)用于每個元素。這一映射的輸出被饋入一個累積器，該裝置用+將得到的所有元素組合起來，從0開始。 enumerate ：tree leavesfilter：odd?map ： squareaccumulate ：+,0層次性數(shù)據(jù)和閉包性質(zhì)序列操作：要組織好反映上面信號流的結(jié)構(gòu)的程序，最關(guān)鍵的一點就是將注意力集中在處理過程中從一個步驟流向下一個步驟的“信號”。這些信號應(yīng)該有穩(wěn)定而靈活的結(jié)構(gòu)，基于其上的基本操作可以組織好這些處理過程。表

25、在這里就是一個良好的選擇?；诒斫Y(jié)構(gòu)我們可以很好的實現(xiàn)信號流圖中的過程如下：l前面的map過程可以用來實現(xiàn)信號流圖中的映射步驟：l過濾一個序列，就是選出其中滿足某個給定謂詞的元素，實現(xiàn)如下：(define (filter predicate sequence) (cond (null? sequence) nil) (predicate (car sequence) (cons (car sequence) (filter predicate (cdr sequence) (else (filter predicate (cdr sequence) 層次性數(shù)據(jù)和閉包性質(zhì)累積工作可以實現(xiàn)如下：(

26、define (accumulate op initial sequence) (if (null? sequence) initial (op (car sequence) (accumulate op initial (cdr sequence)剩下的就是枚舉出需要處理的數(shù)據(jù)序列，對于上面的例子，需要枚舉出一棵樹的所有樹葉，可實現(xiàn)如下：(define (enumerate-tree tree) (cond (null? tree) nil) (not (pair? tree) (list tree) (else (append (enumerate-tree (car tree) (enu

27、merate-tree (cdr tree) 層次性數(shù)據(jù)和閉包性質(zhì)現(xiàn)在，我們就可以像上面的信號流圖那些重新構(gòu)造sum-odd-squares了。我們需要枚舉一棵樹的樹葉序列，過濾它，只留下序列中的奇數(shù)，求每個元素的平方，而后加起來得到的結(jié)果：(define (sum-odd-squares tree) (accumulate + 0 (map square (filter odd? (enumerate-tree tree) 將程序表示為一些針對序列的操作，這樣做的價值就在于能幫助我們得到模塊化的程序設(shè)計，也就是說，得到由一些比較獨(dú)立的片段的組合構(gòu)成的設(shè)計。而模塊化結(jié)構(gòu)是控制復(fù)雜性的一種威力強(qiáng)

28、大的策略。 在這里，用表實現(xiàn)的序列被作為一種方便的界面，我們可以利用這種界面去組合其各種處理模塊，并將程序?qū)?shù)據(jù)結(jié)構(gòu)的依賴性局限到不多的幾個序列操作上。通過修改這些操作，就可以在序列的不同表示之間轉(zhuǎn)換，并保持程序的整個設(shè)計不變。 符號數(shù)據(jù) 到目前為止，我們已經(jīng)使用過的所有復(fù)合數(shù)據(jù)，最終都是從數(shù)值出發(fā)構(gòu)造起來的。接下來，我們將要擴(kuò)充所用語言的描述能力，引進(jìn)將任意符號作為數(shù)據(jù)的能力。 我們希望構(gòu)造出表(a b)，當(dāng)然這里不能用(list a b)，因為這將構(gòu)造出a和b的值的表，而不是其符號本身。為了能構(gòu)造出這些符號，我們使用的語言里就需要有一種新元素，它具有引用數(shù)據(jù)對象的能力。在scheme里我們

29、通過一個單引號來引用一個對象。符號數(shù)據(jù)現(xiàn)在我們可以通過單引號區(qū)分一個符號和他們的值了：(define a 1)(define b 2)(list a b);:(1 2) (list a b);: (a b)(list a b);: (a 2)引號也可以用于復(fù)合對象：(car (a b c);: a(cdr (a b c);: (b c)符號數(shù)據(jù)對符號的操作：為了能對符號進(jìn)行各種操作，我們的語言提供了一個基本過程eq?，這個過程以兩個符號作為參數(shù)，檢查它們是否為同樣的符號。我們利用eq?實現(xiàn)一個稱為memq的有用過程，它以一個符號和一個表為參數(shù)。如果這個符號不包含在這個表里，就返回假；否則返回該

30、表的由這個符號的第一次出現(xiàn)開始的那個子集：(define (memq item x) (cond (null? x) false) (eq? item (car x) x) (else (memq item (cdr x)(memq apple (pear banana prune);:false(memq apple (x (apple sauce) y apple pear);:(apple pear)符號數(shù)據(jù)解釋器在求值下面各個表達(dá)式時將打印出什么？(list a b c)(list (list george)(cdr (x1 x2) (y1 y2)(cadr (x1 x2) (y1 y

31、2)(pair? (car (a short list)(memq red (red shoes) (blue socks)(memq red (red shoes blue socks)符號數(shù)據(jù)實例研究：符號求導(dǎo) 我們希望實現(xiàn)一個過程，以一個代數(shù)表達(dá)式和一個變量作為參數(shù)，返回這個表達(dá)式相對于該變量的導(dǎo)數(shù)。如：參數(shù)為ax2+bx+c和x，它應(yīng)該返回2ax+b。 當(dāng)然，一個強(qiáng)有力的符號求導(dǎo)系統(tǒng)的開發(fā)是很困難的，為了使有關(guān)討論簡單化，我們在這里考慮一個非常簡單的符號求導(dǎo)程序，它處理的表達(dá)式都是由對于兩個參數(shù)的加和乘運(yùn)算構(gòu)造起來的。這樣其求導(dǎo)可以通過下面幾條規(guī)則完成： 0 cx1()()()()dc

32、dxdxdxd uvdudvdxdxdxd uvdvduuvdxdxdx當(dāng) 是一個常量，或者一個與 不同的變量符號數(shù)據(jù)為了能在一個過程中體現(xiàn)這些規(guī)則，我們用一下按愿望思維，就像在前面設(shè)計有理數(shù)的實現(xiàn)所做的那樣。假設(shè)現(xiàn)在已經(jīng)有了一種表示代數(shù)表達(dá)式的方式，那么我們需要判斷該表達(dá)式是否為一個和式、乘式、常量、變量，還需要能提取出表達(dá)式的各個部分。也就是說我么在這里需要一組構(gòu)造函數(shù)、選擇函數(shù)和謂詞作為我們求導(dǎo)程序的界面：(variable? e) e是變量嗎？(same- variable? v1 v2) v1和v2是統(tǒng)一變量嗎？(sum? e) e是和式嗎？(addend e) e的被加數(shù)(auge

33、nd e) e的加數(shù)(make-sum a1 a2) 構(gòu)造a1與a2的和式(product? e) e是乘式嗎？(multiplier e) e的被乘數(shù)(multiplicand e) e的乘數(shù)(make-product m1 m2) 構(gòu)造m1與m2的乘式符號數(shù)據(jù)利用上面這些過程，以及判斷表達(dá)式是否數(shù)值的基本過程number？，我們就可以將各種求導(dǎo)規(guī)則用下面的過程表達(dá)出來了：(define (deriv exp var) (cond (number? exp) 0) (variable? exp) (if (same-variable? exp var) 1 0) (sum? exp) (ma

34、ke-sum (deriv (addend exp) var) (deriv (augend exp) var) 符號數(shù)據(jù) (product? exp) (make-sum (make-product (multiplier exp) (deriv (multiplicand exp) var) (make-product (deriv (multiplier exp) var) (multiplicand exp) (else (error unknown expression type - DERIV exp) 過程deriv包含了一個完整的求導(dǎo)算法。因為它是基于抽象數(shù)據(jù)表述的，因此，無論

35、我們?nèi)绾芜x擇代數(shù)表達(dá)式的具體表示，只要設(shè)計了一組正確的選擇函數(shù)和構(gòu)造函數(shù)，這個過程都可以工作。符號數(shù)據(jù)代數(shù)表達(dá)式的表示：我們可以想出很多用表結(jié)構(gòu)表示代數(shù)表達(dá)式的方法，一種特別直截了當(dāng)?shù)倪x擇，是采用Lisp里面表示組合式的那種帶括號的前綴形式：變量就是符號，他們可以用基本謂詞symbol?判斷：(define (variable? x) (symbol? x)兩個變量相同就是表示它們的符號相互eq?：(define (same-variable? v1 v2) (and (variable? v1) (variable? v2) (eq? v1 v2)和式與乘式都構(gòu)造為表：(define (ma

36、ke-sum a1 a2) (list + a1 a2)(define (make-product m1 m2) (list * m1 m2)和式就是第一個元素為符號+的表：(define (sum? x) (and (pair? x) (eq? (car x) +)符號數(shù)據(jù)被加數(shù)是表示和式的表里的第二個元素：(define (addend s) (cadr s)加數(shù)是表示和式的表里的第三個元素：(define (augend s) (caddr s)乘是就是第一個元素為符號*的表：(define (product? x) (and (pair? x) (eq? (car x) *)被乘數(shù)是表

37、示乘式的表里的第二個元素：(define (multiplier p) (cadr p)乘數(shù)是表示乘式的表里的第三個元素：有了代數(shù)表達(dá)式的具體表示以后我們就能實際使用求導(dǎo)程序了：(define (multiplicand p) (caddr p);: (deriv (+ x 3) x);: (deriv (* x y) x);: (deriv (* (* x y) (+ x 3) x)符號數(shù)據(jù)有了代數(shù)表達(dá)式的具體表示以后，我們就能實際使用求導(dǎo)程序了：(define (multiplicand p) (caddr p);:(+ 1 0) (deriv (+ x 3) x);: (+ (* x 0

38、) (* 1 y)(deriv (* x y) x);: (deriv (* (* x y) (+ x 3) x);: (+ (* (* x y) (+ 1 0) (* (+ (* x 0) (* 1 y) (+ x 3)我們可以看到程序產(chǎn)生的結(jié)果是對的，但是他們沒有經(jīng)過化簡。當(dāng)然，我們希望程序能夠知道x*0=0,1*y=y以及0+y=y。我們可以想想在有理數(shù)中碰到的情形。同樣我們可以通過修改選擇函數(shù)和構(gòu)造函數(shù)實現(xiàn)這一化簡，完全不必修改deriv。符號數(shù)據(jù)新的make-sum過程，當(dāng)兩個求和對象都是數(shù)時，返回他們的和，當(dāng)其中一個為零時，返回另外一個對象：(define (make-sum a1

39、 a2) (cond (=number? a1 0) a2) (=number? a2 0) a1) (and (number? a1) (number? a2) (+ a1 a2) (else (list + a1 a2)該過程用到了=number?，它檢查某個表達(dá)式是否等于一個給定的數(shù)。(define (=number? exp num) (and (number? exp) (= exp num)符號數(shù)據(jù)與make-sum類似，修改后的make-prouct過程，設(shè)法引進(jìn)下面的規(guī)則：0與任何對象的乘積都是0，1與任何東西的乘積總是那個對象(define (make-product m1

40、m2) (cond (or (=number? m1 0) (=number? m2 0) 0) (=number? m1 1) m2) (=number? m2 1) m1) (and (number? m1) (number? m2) (* m1 m2) (else (list * m1 m2)下面使這一新版過程對前面三個例子的結(jié)果：;:1;: y;: (+ (* x y) (* y (+ x 3)雖然大有改觀，但第三個例子還是說明，這不足以滿足我們認(rèn)為的最簡形式。思考這里所謂的最簡形式的含義，它有沒有統(tǒng)一的風(fēng)格？抽象數(shù)據(jù)的多重表示 抽象屏障是控制復(fù)雜性的強(qiáng)有力的工具。通過對數(shù)據(jù)對象基礎(chǔ)表

41、示的屏蔽，我們就可以將設(shè)計一個大程序的任務(wù)，分割為一組可以分別處理的較小任務(wù)。但是，這種類型的數(shù)據(jù)抽象還不夠強(qiáng)大有力。從一個角度看，對于一個數(shù)據(jù)對象可能存在多種有用的表示方法，而且我們也可能希望所設(shè)計的系統(tǒng)能處理多種表示形式。例如：復(fù)數(shù)可以表示為兩種等價的形式：直角坐標(biāo)（實部和虛部）和極坐標(biāo)（模和幅角）。有時采用直角坐標(biāo)形式更合適，有時極坐標(biāo)形勢更方便。所以，我們可能希望一個系統(tǒng)能同時采用兩種表示形式。而其中的過程可以對具有任意表示形式的復(fù)數(shù)工作。接下來我們就通過實現(xiàn)這一復(fù)數(shù)系統(tǒng)來展示抽象數(shù)據(jù)的多重表示技術(shù)。抽象數(shù)據(jù)的多重表示利用一個按愿望思維，我們希望有如下2個構(gòu)造函數(shù)和4個選擇函數(shù)：mak

42、e-frome-real-imag:返回一個采用實部和虛部描述的復(fù)數(shù)；make-frome-mag-ang:返回一個采模和幅角描述的復(fù)數(shù)；real-part:以一個復(fù)數(shù)為參數(shù)，返回其實部；imag-part:以一個復(fù)數(shù)為參數(shù)，返回其虛部；magnitude:以一個復(fù)數(shù)為參數(shù)，返回它的模；angle：以一個復(fù)數(shù)為參數(shù)，返回其幅角；這些過程的性質(zhì)是：(make-from-real-imag (real-part z) (imag-part z)(make-from-mag-ang (magnitude z) (angle z)產(chǎn)生出的復(fù)數(shù)都等于z。利用這些構(gòu)造函數(shù)和現(xiàn)在函數(shù)，我們就可以實現(xiàn)復(fù)數(shù)的運(yùn)

43、算了。抽象數(shù)據(jù)的多重表示我們希望，加減法采用實部和虛部的方式描述，而乘除法采用模和幅角的方式描述：(define (add-complex z1 z2) (make-from-real-imag (+ (real-part z1) (real-part z2) (+ (imag-part z1) (imag-part z2)(define (sub-complex z1 z2) (make-from-real-imag (- (real-part z1) (real-part z2) (- (imag-part z1) (imag-part z2)(define (mul-complex z1

44、 z2) (make-from-mag-ang (* (magnitude z1) (magnitude z2) (+ (angle z1) (angle z2)(define (div-complex z1 z2) (make-from-mag-ang (/ (magnitude z1) (magnitude z2) (- (angle z1) (angle z2)抽象數(shù)據(jù)的多重表示為了完成這一復(fù)數(shù)包，我們必須選擇一種表示方法，而且必須基于基本的數(shù)值和基本的表結(jié)構(gòu)。有兩種顯而易見的方式完成這一工作：可以將復(fù)數(shù)按“直角坐標(biāo)形式”表述為一個有序?qū)Γ▽嵅?，虛部），或者“極坐標(biāo)形式”表示為序?qū)Γ＃?/p>

45、幅角）。假設(shè)現(xiàn)在已經(jīng)設(shè)計出了這兩種復(fù)數(shù)系統(tǒng)的具體表示形式?；谥苯亲鴺?biāo)的表示形式：(define (real-part z) (car z)(define (imag-part z) (cdr z)(define (magnitude z) (sqrt (+ (square (real-part z) (square (imag-part z)(define (angle z) (atan (imag-part z) (real-part z)(define (make-from-real-imag x y) (cons x y)(define (make-from-mag-ang r a)

46、(cons (* r (cos a) (* r (sin a)上面用到了一個反正切函數(shù)atan，它取兩個參數(shù)y和x，返回正切是y/x的角度。參數(shù)的符號決定角度所在的象限抽象數(shù)據(jù)的多重表示基于極坐標(biāo)的表示形式：(define (real-part z) (* (magnitude z) (cos (angle z)(define (imag-part z) (* (magnitude z) (sin (angle z)(define (magnitude z) (car z)(define (angle z) (cdr z)(define (make-from-real-imag x y) (c

47、ons (sqrt (+ (square x) (square y) (atan y x)(define (make-from-mag-ang r a) (cons r a)數(shù)據(jù)抽象的規(guī)則保證了復(fù)數(shù)的加減乘除運(yùn)算的同一套實現(xiàn)對這兩種表示都能正常工作。抽象數(shù)據(jù)的多重表示究竟應(yīng)該選擇哪一種表示方式？我們處在一個尷尬的境地了，因為這兩表示形式同樣的有用，我們希望同時獲得這兩種表示形式的優(yōu)點。能不能在同一個系統(tǒng)里包含兩種不同的表示形式？答案是能，但我們需要一種方式，將極坐標(biāo)形式的數(shù)據(jù)和直角坐標(biāo)形式的數(shù)據(jù)區(qū)分。完成這種區(qū)分的一種方式，就是在每個復(fù)數(shù)里包含一個類型標(biāo)志部分用符號rectangular或者p

48、olar。此后如果我們需要操作一個復(fù)數(shù)，借助于這個標(biāo)志就可以確定應(yīng)該使用的選擇函數(shù)了。為了能對帶標(biāo)志數(shù)據(jù)進(jìn)行各種操作，我們將假定有過程type-tag和contents,它們分別從數(shù)據(jù)對象中提取出類型標(biāo)志和實際內(nèi)容。還要假定有一個過程它以標(biāo)志和實際內(nèi)容為參數(shù)，生成出一個帶標(biāo)志的數(shù)據(jù)對象。實現(xiàn)這些的直接方式就是采用普通表結(jié)構(gòu)：(define (attach-tag type-tag contents) (cons type-tag contents)(define (type-tag datum) (if (pair? datum) (car datum) (error Bad tagged d

49、atum - TYPE-TAG datum) 抽象數(shù)據(jù)的多重表示(define (contents datum) (if (pair? datum) (cdr datum) (error Bad tagged datum - CONTENTS datum)利用這些過程，我們就可以定義出謂詞rectangular?和polar?,他們分別辨識直角坐標(biāo)表示和極坐標(biāo)表示的復(fù)數(shù)：(define (rectangular? z) (eq? (type-tag z) rectangular)(define (polar? z) (eq? (type-tag z) polar)有了類型標(biāo)志之后，我們可以修改

50、前面的代碼，使兩種不同表示能夠共存于同一個系統(tǒng)中了。在不同的表示形式中，構(gòu)造一個復(fù)數(shù)時，總為它加上對應(yīng)的標(biāo)志。此外還必須保證所用的過程名不沖突。這樣應(yīng)為過程名也加上相應(yīng)的后綴。經(jīng)過修改后的兩種表示形式如下： 抽象數(shù)據(jù)的多重表示修改后的直角坐標(biāo)表示：(define (real-part-rectangular z) (car z)(define (imag-part-rectangular z) (cdr z)(define (magnitude-rectangular z) (sqrt (+ (square (real-part-rectangular z) (square (imag-par

51、t-rectangular z)(define (angle-rectangular z) (atan (imag-part-rectangular z) (real-part-rectangular z)(define (make-from-real-imag-rectangular x y) (attach-tag rectangular (cons x y)(define (make-from-mag-ang-rectangular r a) (attach-tag rectangular (cons (* r (cos a) (* r (sin a)抽象數(shù)據(jù)的多重表示修改后的極坐標(biāo)表示

52、：(define (real-part-polar z) (* (magnitude-polar z) (cos (angle-polar z)(define (imag-part-polar z) (* (magnitude-polar z) (sin (angle-polar z)(define (magnitude-polar z) (car z)(define (angle-polar z) (cdr z)(define (make-from-real-imag-polar x y) (attach-tag polar (cons (sqrt (+ (square x) (square

53、 y) (atan y x)(define (make-from-mag-ang-polar r a) (attach-tag polar (cons r a)抽象數(shù)據(jù)的多重表示基于上面的兩種表示我們需要實現(xiàn)通用型函數(shù)，它們首先檢查參數(shù)的標(biāo)志，而后去調(diào)用處理該類數(shù)據(jù)的適當(dāng)過程。(define (real-part z) (cond (rectangular? z) (real-part-rectangular (contents z) (polar? z) (real-part-polar (contents z) (else (error Unknown type - REAL-PART z

54、)(define (imag-part z) (cond (rectangular? z) (imag-part-rectangular (contents z) (polar? z) (imag-part-polar (contents z) (else (error Unknown type - IMAG-PART z)抽象數(shù)據(jù)的多重表示(define (magnitude z) (cond (rectangular? z) (magnitude-rectangular (contents z) (polar? z) (magnitude-polar (contents z) (else

55、(error Unknown type - MAGNITUDE z)(define (angle z) (cond (rectangular? z) (angle-rectangular (contents z) (polar? z) (angle-polar (contents z) (else (error Unknown type - ANGLE z)我們可以看到前面的復(fù)數(shù)加減乘除的運(yùn)算仍然無須改動。抽象數(shù)據(jù)的多重表示最后，我們還需要確定采用那種構(gòu)造復(fù)數(shù)的方式。一種合理的選擇是：在手頭有實部和虛部時采用直角坐標(biāo)表示，有模和幅角時采用極坐標(biāo)表示：(define (make-from-rea

56、l-imag x y) (make-from-real-imag-rectangular x y)(define (make-from-mag-ang r a) (make-from-mag-ang-polar r a)抽象數(shù)據(jù)的多重表示這樣回過頭來看我們所定義的過程，我們用一種非常自然的鑒別方式，成功的把復(fù)數(shù)的兩種不同表示形式包含到同一個復(fù)數(shù)包中了。這樣得到的系統(tǒng)具有如下圖所示的結(jié)構(gòu)：使用復(fù)數(shù)的程序復(fù)數(shù)算術(shù)包直角坐標(biāo)表示 極坐標(biāo)表示add-complex sub-complex mul-complex div-complexreal-part imag-partMagnitude angle

57、抽象數(shù)據(jù)的多重表示數(shù)據(jù)導(dǎo)向的程序設(shè)計和可加性： 基于類型的分派，在系統(tǒng)設(shè)計中是一種獲得模塊性的強(qiáng)有力的策略。而另一方面，同前面那樣實現(xiàn)的分派有兩個顯著的弱點。一是，其中的這些通用型界面過必須知道所有的不同表示，如果現(xiàn)在希望增加另一種表示，我們就必須將這一新表示方法標(biāo)識為一種新類型，而且要在每個通用界面過程里增加一個句子，檢查這一新類型，并對這種表示形式使用適當(dāng)?shù)倪x擇函數(shù)。還有一個弱點就是，即使這些獨(dú)立的表示形式可以分別設(shè)計，我們也必須保證在整個系統(tǒng)里不存在兩個名字相同的過程。 由此帶來的問題是，這種實現(xiàn)通用型界面的技術(shù)不具有可加性。因為每次增加一種新表示時，實現(xiàn)通用選擇函數(shù)的人都必須修改它們的

58、過程，而那些做獨(dú)立表示界面的人也必須修改其代碼，以避免名字沖突問題。很多時候這種做法會帶來極大的不變，而且還很容易引進(jìn)錯誤。接下來我們介紹將系統(tǒng)進(jìn)一步模塊化的方法，通過使用一種稱為數(shù)據(jù)導(dǎo)向的程序設(shè)計的編程技術(shù)。抽象數(shù)據(jù)的多重表示事實上，我們正是在處理一個二維表格，其中的一個維上包含著所有的可能操作，另一個維就是所有的可能類型。如圖： 數(shù)據(jù)導(dǎo)向的程序設(shè)計就是一種使程序能直接利用這種表格工作的程序設(shè)計技術(shù)。它用操作名和參數(shù)類型的組合到表格中查找，以便找出應(yīng)該調(diào)用的適當(dāng)過程，并將這一過程應(yīng)用于參數(shù)的內(nèi)容。這樣把一種新的表示包加入系統(tǒng)里，我們就不需要修改任何現(xiàn)存的過程，而只要在這個表格里添加一些新的項

59、目即可。抽象數(shù)據(jù)的多重表示為了實現(xiàn)這一計劃，現(xiàn)在假定有兩個過程put和get，用于處理這種操作類型表格：l(put )：將項加入表格中，以和作為這個表項的索引l(get )：在表中查找和對應(yīng)的項，如果找到就返回找到的項，否則就返回假。 下面我們要說明，這種數(shù)據(jù)導(dǎo)向的程序設(shè)計可以如何用于復(fù)數(shù)系統(tǒng)。我們在定義完復(fù)數(shù)的表示的程序包后，要通過向表格中加入一些項的方式，告訴系統(tǒng)如何去操作直角坐標(biāo)形式表示的數(shù)，這樣就建立起了與系統(tǒng)其它部分的界面。我們通過安裝的方式向表中加入我們要提供出來的過程。抽象數(shù)據(jù)的多重表示直角坐標(biāo)表示包的安裝過程：(define (install-rectangular-packa

60、ge); internal procedures (define (real-part z) (car z) (define (imag-part z) (cdr z) (define (make-from-real-imag x y) (cons x y) (define (magnitude z) (sqrt (+ (square (real-part z) (square (imag-part z) (define (angle z) (atan (imag-part z) (real-part z) (define (make-from-mag-ang r a) (cons (* r