構(gòu)造數(shù)據(jù)抽象課件

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

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

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

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

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

6、ns取兩個(gè)參數(shù)，返回一個(gè)包含這兩個(gè)參數(shù)作為其成分的復(fù)合數(shù)據(jù)對(duì)象(car )，其序?qū)χ械牡谝粋€(gè)參數(shù)(cdr )，其序?qū)χ械牡诙€(gè)參數(shù)注意一個(gè)序?qū)σ彩且粋€(gè)數(shù)據(jù)對(duì)象，可以像基本數(shù)據(jù)對(duì)象一樣給它一個(gè)名字且操作它。還可用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ù)抽象構(gòu)造數(shù)據(jù)抽象基于序?qū)Φ挠欣頂?shù)的表示：(define (make-rat n d) (cons n d)(define (numer x) (car x)(defi

7、ne (denom x) (cdr x)為了顯示計(jì)算結(jié)果我們?cè)俣x一個(gè)打印函數(shù)，它以一個(gè)有理數(shù)作為輸入并把它打印出來(lái)。(define (print-rat x) (newline) (display (numer x) (display /) (display (denom x)這里我們用到了兩個(gè)scheme的基本內(nèi)置過(guò)程display和newline。 Display為打印數(shù)據(jù)的基本過(guò)程， newline為隨后的打印開(kāi)始一個(gè)新行。構(gòu)造數(shù)據(jù)抽象構(gòu)造數(shù)據(jù)抽象(define one-half (make-rat 1 2)(print-rat one-half)(define one-third (

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

9、 denom構(gòu)造數(shù)據(jù)抽象構(gòu)造數(shù)據(jù)抽象 其中的水平線表示抽象屏障，它隔離了系統(tǒng)的不同層次，它把使用數(shù)據(jù)的程序和實(shí)現(xiàn)數(shù)據(jù)的程序分開(kāi)，使得一層中的過(guò)程的實(shí)現(xiàn)與其他層的過(guò)程的實(shí)現(xiàn)完全無(wú)關(guān)。從作用上看，每一層中的過(guò)程構(gòu)成了所定義的抽象屏障的界面，聯(lián)系起系統(tǒng)中的不同層次。 這種簡(jiǎn)單思想有許多優(yōu)點(diǎn)：這種方法使程序很容易維護(hù)和修改有助于程序的設(shè)計(jì)，使我們能保留考慮不同實(shí)現(xiàn)方式的靈活性，使我們能推遲決策的時(shí)間，而又不會(huì)阻礙系統(tǒng)其他部分的工作進(jìn)展。你能給出幾種不同的有理數(shù)表示？它們各有什么優(yōu)缺點(diǎn)？構(gòu)造數(shù)據(jù)抽象構(gòu)造數(shù)據(jù)抽象數(shù)據(jù)意味著什么前面我們看到在抽象層面上數(shù)據(jù)可以描述為一組選擇函數(shù)和構(gòu)造函數(shù)，但是說(shuō)它就是“由給

10、定的選擇函數(shù)和構(gòu)造函數(shù)所實(shí)現(xiàn)的東西”還是不夠的。顯然，并不是任意的三個(gè)過(guò)程都適合作為有理數(shù)實(shí)現(xiàn)的基礎(chǔ)。這里我們還需要保證，如果從整數(shù)n和d構(gòu)造出一個(gè)有理數(shù)x，那么抽取出的x的number和denom并將他們相除，得到的結(jié)果應(yīng)該與n除以d相同。也就是說(shuō)這些基本過(guò)程的選擇是帶有約束的。一般而言，我們總可以將數(shù)據(jù)定義為一組適當(dāng)?shù)倪x擇函數(shù)和構(gòu)造函數(shù)，以及為使這些過(guò)程成為一套合法表示，它們就必須滿足的一組特定條件。從上面我們可以得出一個(gè)結(jié)論：數(shù)據(jù)其實(shí)就是一組定義良好的過(guò)程。確實(shí)，考慮序?qū)?，我們完全可以不用任何?shù)據(jù)結(jié)構(gòu)，只用過(guò)程實(shí)現(xiàn)它。構(gòu)造數(shù)據(jù)抽象構(gòu)造數(shù)據(jù)抽象序?qū)Φ倪^(guò)程實(shí)現(xiàn)：(define (cons x

11、 y) (define (dispatch m) (cond (= m 0) x) (= m 1) y) (else (error Argument not 0 or 1 - CONS m) dispatch)(define (car z) (z 0)(define (cdr z) (z 1)這確實(shí)與我們有關(guān)數(shù)據(jù)應(yīng)該是什么的直觀認(rèn)識(shí)大相徑庭。這一實(shí)例說(shuō)明可以將過(guò)程作為對(duì)象去操作，因此就自動(dòng)地為我們提供了一種表示復(fù)合數(shù)據(jù)的能力。這些東西現(xiàn)在看起來(lái)好像只是很好玩，但實(shí)際上，數(shù)據(jù)的過(guò)程性表示將在我們的程序設(shè)計(jì)寶庫(kù)里扮演一種核心角色。有關(guān)的程序設(shè)計(jì)風(fēng)格通常稱為消息傳遞。構(gòu)造數(shù)據(jù)抽象層次性數(shù)據(jù)和閉包性質(zhì)

12、 前面已經(jīng)看到，序?qū)槲覀兲峁┝艘环N用于構(gòu)造復(fù)合數(shù)據(jù)的基本“粘接劑”，我們可以建立元素本身也是序?qū)Φ男驅(qū)?，序?qū)Φ倪@種能力稱為cons的閉包性質(zhì)。一般說(shuō)，某種數(shù)據(jù)對(duì)象的操作滿足閉包性質(zhì)，就是說(shuō)，通過(guò)它組合起數(shù)據(jù)對(duì)象得到的結(jié)果本身還可以通過(guò)同樣的操作再進(jìn)行組合。閉包性質(zhì)是任何一種組合功能的威力的關(guān)鍵要素，它使我們能夠建立起層次性的結(jié)構(gòu)。構(gòu)造數(shù)據(jù)抽象層次性數(shù)據(jù)和閉包性質(zhì)層次性結(jié)構(gòu)的表示：圖中展示的是序?qū)Φ臉?biāo)準(zhǔn)表示，其中的序?qū)κ峭ㄟ^(guò)(cons 1 2)形成的。這種稱為盒子和指針表示方式中，每個(gè)對(duì)象表示為一個(gè)指向盒子的指針。與基本對(duì)象相對(duì)應(yīng)的盒子包含著該對(duì)象的表示。復(fù)合層次結(jié)構(gòu)的表示：構(gòu)造數(shù)據(jù)抽象層次性

13、數(shù)據(jù)和閉包性質(zhì)序列的表示：我們可以用序?qū)?gòu)造一種有用的數(shù)據(jù)結(jié)構(gòu)序列，它是一批數(shù)據(jù)對(duì)象的一種有序匯集。采用序?qū)Ρ硎拘蛄杏泻芏喾N方式，在這里我們采用一種標(biāo)準(zhǔn)的方式來(lái)表示。下面是對(duì)序列1，2，3，4的表示：(cons 1 (cons 2 (cons 3 (cons 4 nil)通過(guò)嵌套的cons形成的這樣一個(gè)序?qū)Φ男蛄蟹Q為一個(gè)表，scheme為方便表的構(gòu)造，提供了一個(gè)基本操作list，如(list 1 2 3 4)。一般的：(list . )等價(jià)于：(cons (cons (cons . (cons nil) . ) 構(gòu)造數(shù)據(jù)抽象層次性數(shù)據(jù)和閉包性質(zhì)序?qū)Φ拇蛴。?cons 1 2); (1 . 2)

14、(cons (cons 1 2) (cons 3 4);(1 . 2) 3 . 4)(cons 1 (cons 2 (cons 3 nil);(1 2 3) 構(gòu)造數(shù)據(jù)抽象層次性數(shù)據(jù)和閉包性質(zhì)表的打?。?list 1 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-f

15、our);:(10 1 2 3 4) 構(gòu)造數(shù)據(jù)抽象層次性數(shù)據(jù)和閉包性質(zhì)表操作：利用序?qū)⒃乇硎緸楸碇?，我們就可以使用常?guī)的程序設(shè)計(jì)技術(shù)，通過(guò)”向下cdr”表的方式完成對(duì)表的各種操作了。l返回指定標(biāo)號(hào)的元素操作：list-ref(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í)慣令表元素的編號(hào)從0開(kāi)始。 構(gòu)造數(shù)據(jù)抽象層次性數(shù)據(jù)和閉包性質(zhì)l返回表的長(zhǎng)度操作

16、： length(define (length items) (if (null? items) 0 (+ 1 (length (cdr items)(define odds (list 1 3 5 7)(length odds)4這里我們需要用到scheme提供的一個(gè)基本操作null?，用于檢查參數(shù)是不是空表。上面的過(guò)程是一個(gè)遞歸的過(guò)程，空表的length為0，任一表的length等于其cdr的length加1.給出迭代的length過(guò)程？ 構(gòu)造數(shù)據(jù)抽象層次性數(shù)據(jù)和閉包性質(zhì)l連接表操作： append(define (append list1 list2) (if (null? list1)

17、 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 7 1 4 9 16 25)append也是一種遞歸方案，能否給出迭代形式？ 構(gòu)造數(shù)據(jù)抽象層次性數(shù)據(jù)和閉包性質(zhì)對(duì)表的映射：例：對(duì)給定表的所有元素按給定因子做一次放縮(define (scale-list items factor) (if (null? items) nil (cons (* (car items) factor) (scale

18、-list (cdr items) factor)(scale-list (list 1 2 3 4 5) 10);:(10 20 30 40 50) 這里我們想抽象出這一具有一般性的想法，將其中公共模式表述為一個(gè)高階過(guò)程，這一高階過(guò)程稱為map，它有一個(gè)過(guò)程參數(shù)和一個(gè)表參數(shù)，返回將這一過(guò)程應(yīng)用于表中各個(gè)元素得到的結(jié)果形成的表。 構(gòu)造數(shù)據(jù)抽象層次性數(shù)據(jù)和閉包性質(zhì)對(duì)表的映射過(guò)程：map(define (map proc items) (if (null? items) nil (cons (proc (car items) (map proc (cdr items)(map (lambda (x

19、) (* x x) (list 1 2 3 4)(1 4 9 16)用map重新定義scale-list過(guò)程：(define (scale-list items factor) (map (lambda (x) (* x factor) items) 構(gòu)造數(shù)據(jù)抽象層次性數(shù)據(jù)和閉包性質(zhì)層次性結(jié)構(gòu)：(1 2) 3 4)是通過(guò)(cons (list 1 2) (list 3 4)構(gòu)造出來(lái)的，其結(jié)構(gòu)如下：認(rèn)識(shí)這種元素本身也是序列的序列的另一種方式，是把它們看作樹(shù)。序列里的元素就是樹(shù)的分支，而那些本身也是序列的元素就形成了樹(shù)中的子樹(shù)。如圖： 構(gòu)造數(shù)據(jù)抽象層次性數(shù)據(jù)和閉包性質(zhì)樹(shù)操作：統(tǒng)計(jì)葉子數(shù)目操作：co

20、unt-leaves(define (count-leaves x) (cond (null? x) 0) (not (pair? x) 1) (else (+ (count-leaves (car x) (count-leaves (cdr x)為了實(shí)現(xiàn)這一過(guò)程，我們需要一個(gè)判斷參數(shù)是否為序?qū)Φ暮瘮?shù)，scheme提供了基本過(guò)程pair? 構(gòu)造數(shù)據(jù)抽象層次性數(shù)據(jù)和閉包性質(zhì)對(duì)樹(shù)的映射：(define (scale-tree tree factor) (cond (null? tree) nil) (not (pair? tree) (* tree factor) (else (cons (sca

21、le-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)該過(guò)程以一個(gè)數(shù)值因子和一顆葉子為數(shù)值的樹(shù)作為參數(shù)，返回一顆具有同樣形狀的樹(shù)。 構(gòu)造數(shù)據(jù)抽象層次性數(shù)據(jù)和閉包性質(zhì)下面我們利用前面介紹表的map過(guò)程重寫如下：(define (scale-tree tree factor) (map (lambda (sub-tree) (if (pair? sub-tree) (sca

22、le-tree sub-tree factor) (* sub-tree factor) tree)也已看到這里map過(guò)程的寫法已經(jīng)沒(méi)有在用于處理表時(shí)那么自然了，究其原因是因?yàn)閙ap過(guò)程并不具備處理層次結(jié)構(gòu)的能力，這樣我們?cè)谑褂檬蔷捅仨毎严嚓P(guān)處理寫到其參數(shù)proc的過(guò)程里面。自然地，我們希望能有一個(gè)能處理這種層次結(jié)構(gòu)的map過(guò)程，當(dāng)然其肯定也包含了處理表結(jié)構(gòu)的能力，應(yīng)為樹(shù)結(jié)構(gòu)是一種比表更抽象的結(jié)構(gòu)。 構(gòu)造數(shù)據(jù)抽象層次性數(shù)據(jù)和閉包性質(zhì)重寫前面的map過(guò)程如下：(define (map proc items) (cond (null? items) nil) (pair? items) (cons

23、 (map proc (car items) (map proc (cdr items) (else (proc items)請(qǐng)利用新定義的map過(guò)程重寫scale-list和scale-tree 構(gòu)造數(shù)據(jù)抽象層次性數(shù)據(jù)和閉包性質(zhì)序列作為一種約定的界面：下面這個(gè)例子以一棵樹(shù)為參數(shù)，計(jì)算出那些值為奇數(shù)的葉子的平方：(define (sum-odd-squares tree) (cond (null? tree) 0) (not (pair? tree) (if (odd? tree) (square tree) 0) (else (+ (sum-odd-squares (car tree) (s

24、um-odd-squares (cdr tree)該過(guò)程的大致處理步驟如下：l枚舉出一棵樹(shù)的樹(shù)葉；l過(guò)濾他們，選出其中的奇數(shù)；l對(duì)選出的每個(gè)數(shù)求平方；l再用+累積起得到的結(jié)果，從0開(kāi)始。 構(gòu)造數(shù)據(jù)抽象層次性數(shù)據(jù)和閉包性質(zhì)這種過(guò)程可以很自然地用流過(guò)一些級(jí)聯(lián)的處理步驟的信號(hào)的方式描述，其中的每個(gè)處理步驟實(shí)現(xiàn)程序方案中的一個(gè)部分，如圖所示：我們從一個(gè)枚舉器開(kāi)始，它產(chǎn)生出由個(gè)給定的樹(shù)的所有樹(shù)葉組成“信號(hào)”。這一信號(hào)流過(guò)一個(gè)過(guò)濾器，所有不是奇數(shù)的數(shù)都被刪除了。這樣得到的信號(hào)又通過(guò)一個(gè)映射，這是一個(gè)“轉(zhuǎn)換裝置”，它將square過(guò)程應(yīng)用于每個(gè)元素。這一映射的輸出被饋入一個(gè)累積器，該裝置用+將得到的所有元素

25、組合起來(lái)，從0開(kāi)始。 enumerate ：tree leavesfilter：odd?map ： squareaccumulate ：+,0構(gòu)造數(shù)據(jù)抽象層次性數(shù)據(jù)和閉包性質(zhì)序列操作：要組織好反映上面信號(hào)流的結(jié)構(gòu)的程序，最關(guān)鍵的一點(diǎn)就是將注意力集中在處理過(guò)程中從一個(gè)步驟流向下一個(gè)步驟的“信號(hào)”。這些信號(hào)應(yīng)該有穩(wěn)定而靈活的結(jié)構(gòu)，基于其上的基本操作可以組織好這些處理過(guò)程。表在這里就是一個(gè)良好的選擇?；诒斫Y(jié)構(gòu)我們可以很好的實(shí)現(xiàn)信號(hào)流圖中的過(guò)程如下：l前面的map過(guò)程可以用來(lái)實(shí)現(xiàn)信號(hào)流圖中的映射步驟：l過(guò)濾一個(gè)序列，就是選出其中滿足某個(gè)給定謂詞的元素，實(shí)現(xiàn)如下：(define (filter pre

26、dicate sequence) (cond (null? sequence) nil) (predicate (car sequence) (cons (car sequence) (filter predicate (cdr sequence) (else (filter predicate (cdr sequence) 構(gòu)造數(shù)據(jù)抽象層次性數(shù)據(jù)和閉包性質(zhì)累積工作可以實(shí)現(xiàn)如下：(define (accumulate op initial sequence) (if (null? sequence) initial (op (car sequence) (accumulate op initi

27、al (cdr sequence)剩下的就是枚舉出需要處理的數(shù)據(jù)序列，對(duì)于上面的例子，需要枚舉出一棵樹(shù)的所有樹(shù)葉，可實(shí)現(xiàn)如下：(define (enumerate-tree tree) (cond (null? tree) nil) (not (pair? tree) (list tree) (else (append (enumerate-tree (car tree) (enumerate-tree (cdr tree) 構(gòu)造數(shù)據(jù)抽象層次性數(shù)據(jù)和閉包性質(zhì)現(xiàn)在，我們就可以像上面的信號(hào)流圖那些重新構(gòu)造sum-odd-squares了。我們需要枚舉一棵樹(shù)的樹(shù)葉序列，過(guò)濾它，只留下序列中的奇數(shù)，求

28、每個(gè)元素的平方，而后加起來(lái)得到的結(jié)果：(define (sum-odd-squares tree) (accumulate + 0 (map square (filter odd? (enumerate-tree tree) 將程序表示為一些針對(duì)序列的操作，這樣做的價(jià)值就在于能幫助我們得到模塊化的程序設(shè)計(jì)，也就是說(shuō)，得到由一些比較獨(dú)立的片段的組合構(gòu)成的設(shè)計(jì)。而模塊化結(jié)構(gòu)是控制復(fù)雜性的一種威力強(qiáng)大的策略。 在這里，用表實(shí)現(xiàn)的序列被作為一種方便的界面，我們可以利用這種界面去組合其各種處理模塊，并將程序?qū)?shù)據(jù)結(jié)構(gòu)的依賴性局限到不多的幾個(gè)序列操作上。通過(guò)修改這些操作，就可以在序列的不同表示之間轉(zhuǎn)換，并

29、保持程序的整個(gè)設(shè)計(jì)不變。 構(gòu)造數(shù)據(jù)抽象符號(hào)數(shù)據(jù) 到目前為止，我們已經(jīng)使用過(guò)的所有復(fù)合數(shù)據(jù)，最終都是從數(shù)值出發(fā)構(gòu)造起來(lái)的。接下來(lái)，我們將要擴(kuò)充所用語(yǔ)言的描述能力，引進(jìn)將任意符號(hào)作為數(shù)據(jù)的能力。 我們希望構(gòu)造出表(a b)，當(dāng)然這里不能用(list a b)，因?yàn)檫@將構(gòu)造出a和b的值的表，而不是其符號(hào)本身。為了能構(gòu)造出這些符號(hào)，我們使用的語(yǔ)言里就需要有一種新元素，它具有引用數(shù)據(jù)對(duì)象的能力。在scheme里我們通過(guò)一個(gè)單引號(hào)來(lái)引用一個(gè)對(duì)象。構(gòu)造數(shù)據(jù)抽象符號(hào)數(shù)據(jù)現(xiàn)在我們可以通過(guò)單引號(hào)區(qū)分一個(gè)符號(hào)和他們的值了：(define a 1)(define b 2)(list a b);:(1 2) (list

30、 a b);: (a b)(list a b);: (a 2)引號(hào)也可以用于復(fù)合對(duì)象：(car (a b c);: a(cdr (a b c);: (b c)構(gòu)造數(shù)據(jù)抽象符號(hào)數(shù)據(jù)對(duì)符號(hào)的操作：為了能對(duì)符號(hào)進(jìn)行各種操作，我們的語(yǔ)言提供了一個(gè)基本過(guò)程eq?，這個(gè)過(guò)程以兩個(gè)符號(hào)作為參數(shù)，檢查它們是否為同樣的符號(hào)。我們利用eq?實(shí)現(xiàn)一個(gè)稱為memq的有用過(guò)程，它以一個(gè)符號(hào)和一個(gè)表為參數(shù)。如果這個(gè)符號(hào)不包含在這個(gè)表里，就返回假；否則返回該表的由這個(gè)符號(hào)的第一次出現(xiàn)開(kāi)始的那個(gè)子集：(define (memq item x) (cond (null? x) false) (eq? item (car x)

31、x) (else (memq item (cdr x)(memq apple (pear banana prune);:false(memq apple (x (apple sauce) y apple pear);:(apple pear)構(gòu)造數(shù)據(jù)抽象符號(hào)數(shù)據(jù)解釋器在求值下面各個(gè)表達(dá)式時(shí)將打印出什么？(list a b c)(list (list george)(cdr (x1 x2) (y1 y2)(cadr (x1 x2) (y1 y2)(pair? (car (a short list)(memq red (red shoes) (blue socks)(memq red (red s

32、hoes blue socks)構(gòu)造數(shù)據(jù)抽象符號(hào)數(shù)據(jù)實(shí)例研究：符號(hào)求導(dǎo) 我們希望實(shí)現(xiàn)一個(gè)過(guò)程，以一個(gè)代數(shù)表達(dá)式和一個(gè)變量作為參數(shù)，返回這個(gè)表達(dá)式相對(duì)于該變量的導(dǎo)數(shù)。如：參數(shù)為ax2+bx+c和x，它應(yīng)該返回2ax+b。 當(dāng)然，一個(gè)強(qiáng)有力的符號(hào)求導(dǎo)系統(tǒng)的開(kāi)發(fā)是很困難的，為了使有關(guān)討論簡(jiǎn)單化，我們?cè)谶@里考慮一個(gè)非常簡(jiǎn)單的符號(hào)求導(dǎo)程序，它處理的表達(dá)式都是由對(duì)于兩個(gè)參數(shù)的加和乘運(yùn)算構(gòu)造起來(lái)的。這樣其求導(dǎo)可以通過(guò)下面幾條規(guī)則完成： 0 cx1()()()()dcdxdxdxd uvdudvdxdxdxd uvdvduuvdxdxdx當(dāng) 是一個(gè)常量，或者一個(gè)與 不同的變量構(gòu)造數(shù)據(jù)抽象符號(hào)數(shù)據(jù)為了能在一個(gè)過(guò)

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

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

35、據(jù)抽象符號(hào)數(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) 過(guò)程deriv包含了一個(gè)完整的求導(dǎo)算法。因?yàn)樗腔诔橄髷?shù)據(jù)表述的，因此，無(wú)論我們?nèi)绾芜x擇代數(shù)表達(dá)式的具體表示，只要設(shè)計(jì)了一組正確的選擇函數(shù)和構(gòu)造函數(shù)，這個(gè)過(guò)程都可以工作。構(gòu)造數(shù)據(jù)抽象符

36、號(hào)數(shù)據(jù)代數(shù)表達(dá)式的表示：我們可以想出很多用表結(jié)構(gòu)表示代數(shù)表達(dá)式的方法，一種特別直截了當(dāng)?shù)倪x擇，是采用Lisp里面表示組合式的那種帶括號(hào)的前綴形式：變量就是符號(hào)，他們可以用基本謂詞symbol?判斷：(define (variable? x) (symbol? x)兩個(gè)變量相同就是表示它們的符號(hào)相互eq?：(define (same-variable? v1 v2) (and (variable? v1) (variable? v2) (eq? v1 v2)和式與乘式都構(gòu)造為表：(define (make-sum a1 a2) (list + a1 a2)(define (make-produc

37、t m1 m2) (list * m1 m2)和式就是第一個(gè)元素為符號(hào)+的表：(define (sum? x) (and (pair? x) (eq? (car x) +)構(gòu)造數(shù)據(jù)抽象符號(hào)數(shù)據(jù)被加數(shù)是表示和式的表里的第二個(gè)元素：(define (addend s) (cadr s)加數(shù)是表示和式的表里的第三個(gè)元素：(define (augend s) (caddr s)乘是就是第一個(gè)元素為符號(hào)*的表：(define (product? x) (and (pair? x) (eq? (car x) *)被乘數(shù)是表示乘式的表里的第二個(gè)元素：(define (multiplier p) (cadr

38、p)乘數(shù)是表示乘式的表里的第三個(gè)元素：有了代數(shù)表達(dá)式的具體表示以后我們就能實(shí)際使用求導(dǎo)程序了：(define (multiplicand p) (caddr p);: (deriv (+ x 3) x);: (deriv (* x y) x);: (deriv (* (* x y) (+ x 3) x)構(gòu)造數(shù)據(jù)抽象符號(hào)數(shù)據(jù)有了代數(shù)表達(dá)式的具體表示以后，我們就能實(shí)際使用求導(dǎo)程序了：(define (multiplicand p) (caddr p);:(+ 1 0) (deriv (+ x 3) x);: (+ (* x 0) (* 1 y)(deriv (* x y) x);: (deriv

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

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

41、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)下面使這一新版過(guò)程對(duì)前面三個(gè)例子的結(jié)果：;:1;: y;: (+ (* x y) (* y (+ x 3)雖然大有改觀，但第三個(gè)例子還是說(shuō)明，這不足以滿足我們認(rèn)為的最簡(jiǎn)形式。思考這里所謂的最簡(jiǎn)形式的含義，它有沒(méi)有統(tǒng)一的風(fēng)格？構(gòu)造數(shù)據(jù)抽象抽象數(shù)據(jù)的多重表示 抽象屏障是控制復(fù)雜性的強(qiáng)有力的工具。通過(guò)對(duì)數(shù)據(jù)對(duì)象基礎(chǔ)表示的屏蔽，我們就可以將設(shè)計(jì)一個(gè)大程序

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

43、-imag:返回一個(gè)采用實(shí)部和虛部描述的復(fù)數(shù)；make-frome-mag-ang:返回一個(gè)采模和幅角描述的復(fù)數(shù)；real-part:以一個(gè)復(fù)數(shù)為參數(shù)，返回其實(shí)部；imag-part:以一個(gè)復(fù)數(shù)為參數(shù)，返回其虛部；magnitude:以一個(gè)復(fù)數(shù)為參數(shù)，返回它的模；angle：以一個(gè)復(fù)數(shù)為參數(shù)，返回其幅角；這些過(guò)程的性質(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ù)，我們就可以實(shí)現(xiàn)復(fù)數(shù)的運(yùn)算了。構(gòu)造數(shù)據(jù)抽象抽象數(shù)

44、據(jù)的多重表示我們希望，加減法采用實(shí)部和虛部的方式描述，而乘除法采用模和幅角的方式描述：(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 z2) (

45、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)構(gòu)造數(shù)據(jù)抽象抽象數(shù)據(jù)的多重表示為了完成這一復(fù)數(shù)包，我們必須選擇一種表示方法，而且必須基于基本的數(shù)值和基本的表結(jié)構(gòu)。有兩種顯而易見(jiàn)的方式完成這一工作：可以將復(fù)數(shù)按“直角坐標(biāo)形式”表述為一個(gè)有序?qū)Γ▽?shí)部，虛部），或者“極坐標(biāo)形式”表示為序?qū)Γ＃?/p>

46、幅角）。假設(shè)現(xiàn)在已經(jīng)設(shè)計(jì)出了這兩種復(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)

47、(cons (* r (cos a) (* r (sin a)上面用到了一個(gè)反正切函數(shù)atan，它取兩個(gè)參數(shù)y和x，返回正切是y/x的角度。參數(shù)的符號(hào)決定角度所在的象限構(gòu)造數(shù)據(jù)抽象抽象數(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

48、 y) (cons (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)算的同一套實(shí)現(xiàn)對(duì)這兩種表示都能正常工作。構(gòu)造數(shù)據(jù)抽象抽象數(shù)據(jù)的多重表示究竟應(yīng)該選擇哪一種表示方式？我們處在一個(gè)尷尬的境地了，因?yàn)檫@兩表示形式同樣的有用，我們希望同時(shí)獲得這兩種表示形式的優(yōu)點(diǎn)。能不能在同一個(gè)系統(tǒng)里包含兩種不同的表示形式？答案是能，但我們需要一種方式，將極坐標(biāo)形式的數(shù)據(jù)和直角坐標(biāo)形式的數(shù)據(jù)區(qū)分。完成這種區(qū)分的一種方式，就是在每個(gè)復(fù)數(shù)里包含一個(gè)類型標(biāo)志部分用符號(hào)re

49、ctangular或者polar。此后如果我們需要操作一個(gè)復(fù)數(shù)，借助于這個(gè)標(biāo)志就可以確定應(yīng)該使用的選擇函數(shù)了。為了能對(duì)帶標(biāo)志數(shù)據(jù)進(jìn)行各種操作，我們將假定有過(guò)程type-tag和contents,它們分別從數(shù)據(jù)對(duì)象中提取出類型標(biāo)志和實(shí)際內(nèi)容。還要假定有一個(gè)過(guò)程它以標(biāo)志和實(shí)際內(nèi)容為參數(shù)，生成出一個(gè)帶標(biāo)志的數(shù)據(jù)對(duì)象。實(shí)現(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

50、Bad tagged datum - TYPE-TAG datum) 構(gòu)造數(shù)據(jù)抽象抽象數(shù)據(jù)的多重表示(define (contents datum) (if (pair? datum) (cdr datum) (error Bad tagged datum - CONTENTS datum)利用這些過(guò)程，我們就可以定義出謂詞rectangular?和polar?,他們分別辨識(shí)直角坐標(biāo)表示和極坐標(biāo)表示的復(fù)數(shù)：(define (rectangular? z) (eq? (type-tag z) rectangular)(define (polar? z) (eq? (type-tag z) pol

51、ar)有了類型標(biāo)志之后，我們可以修改前面的代碼，使兩種不同表示能夠共存于同一個(gè)系統(tǒng)中了。在不同的表示形式中，構(gòu)造一個(gè)復(fù)數(shù)時(shí)，總為它加上對(duì)應(yīng)的標(biāo)志。此外還必須保證所用的過(guò)程名不沖突。這樣應(yīng)為過(guò)程名也加上相應(yīng)的后綴。經(jīng)過(guò)修改后的兩種表示形式如下： 構(gòu)造數(shù)據(jù)抽象抽象數(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-rectangu

52、lar z) (square (imag-part-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 (

53、sin a)構(gòu)造數(shù)據(jù)抽象抽象數(shù)據(jù)的多重表示修改后的極坐標(biāo)表示：(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 (co

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

55、se (error Unknown type - REAL-PART z)(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)構(gòu)造數(shù)據(jù)抽象抽象數(shù)據(jù)的多重表示(define (magnitude z) (cond (rectangular? z) (magnitude-rectangular (contents z) (pola

56、r? z) (magnitude-polar (contents z) (else (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)算仍然無(wú)須改動(dòng)。構(gòu)造數(shù)據(jù)抽象抽象數(shù)據(jù)的多重表示最后，我們還需要確定采用那種構(gòu)造復(fù)數(shù)的方式。一種合理的選擇是：在手頭有實(shí)部和

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

58、-complex div-complexreal-part imag-partMagnitude angle構(gòu)造數(shù)據(jù)抽象抽象數(shù)據(jù)的多重表示數(shù)據(jù)導(dǎo)向的程序設(shè)計(jì)和可加性： 基于類型的分派，在系統(tǒng)設(shè)計(jì)中是一種獲得模塊性的強(qiáng)有力的策略。而另一方面，同前面那樣實(shí)現(xiàn)的分派有兩個(gè)顯著的弱點(diǎn)。一是，其中的這些通用型界面過(guò)必須知道所有的不同表示，如果現(xiàn)在希望增加另一種表示，我們就必須將這一新表示方法標(biāo)識(shí)為一種新類型，而且要在每個(gè)通用界面過(guò)程里增加一個(gè)句子，檢查這一新類型，并對(duì)這種表示形式使用適當(dāng)?shù)倪x擇函數(shù)。還有一個(gè)弱點(diǎn)就是，即使這些獨(dú)立的表示形式可以分別設(shè)計(jì)，我們也必須保證在整個(gè)系統(tǒng)里不存在兩個(gè)名字相同的過(guò)程。

59、 由此帶來(lái)的問(wèn)題是，這種實(shí)現(xiàn)通用型界面的技術(shù)不具有可加性。因?yàn)槊看卧黾右环N新表示時(shí)，實(shí)現(xiàn)通用選擇函數(shù)的人都必須修改它們的過(guò)程，而那些做獨(dú)立表示界面的人也必須修改其代碼，以避免名字沖突問(wèn)題。很多時(shí)候這種做法會(huì)帶來(lái)極大的不變，而且還很容易引進(jìn)錯(cuò)誤。接下來(lái)我們介紹將系統(tǒng)進(jìn)一步模塊化的方法，通過(guò)使用一種稱為數(shù)據(jù)導(dǎo)向的程序設(shè)計(jì)的編程技術(shù)。構(gòu)造數(shù)據(jù)抽象抽象數(shù)據(jù)的多重表示事實(shí)上，我們正是在處理一個(gè)二維表格，其中的一個(gè)維上包含著所有的可能操作，另一個(gè)維就是所有的可能類型。如圖： 數(shù)據(jù)導(dǎo)向的程序設(shè)計(jì)就是一種使程序能直接利用這種表格工作的程序設(shè)計(jì)技術(shù)。它用操作名和參數(shù)類型的組合到表格中查找，以便找出應(yīng)該調(diào)用的適當(dāng)

60、過(guò)程，并將這一過(guò)程應(yīng)用于參數(shù)的內(nèi)容。這樣把一種新的表示包加入系統(tǒng)里，我們就不需要修改任何現(xiàn)存的過(guò)程，而只要在這個(gè)表格里添加一些新的項(xiàng)目即可。構(gòu)造數(shù)據(jù)抽象抽象數(shù)據(jù)的多重表示為了實(shí)現(xiàn)這一計(jì)劃，現(xiàn)在假定有兩個(gè)過(guò)程put和get，用于處理這種操作類型表格：l(put )：將項(xiàng)加入表格中，以和作為這個(gè)表項(xiàng)的索引l(get )：在表中查找和對(duì)應(yīng)的項(xiàng)，如果找到就返回找到的項(xiàng)，否則就返回假。 下面我們要說(shuō)明，這種數(shù)據(jù)導(dǎo)向的程序設(shè)計(jì)可以如何用于復(fù)數(shù)系統(tǒng)。我們?cè)诙x完復(fù)數(shù)的表示的程序包后，要通過(guò)向表格中加入一些項(xiàng)的方式，告訴系統(tǒng)如何去操作直角坐標(biāo)形式表示的數(shù)，這樣就建立起了與系統(tǒng)其它部分的界面。我們通過(guò)安裝的方式