帶你讀《計算機程式的構造和解釋（原書第2版）典藏版》之二：構造資料抽象

點選檢視第一章

第2章 構造資料抽象

現在到了數學抽象中最關鍵的一步：讓我們忘記這些符号所表示的對象。……（數學家）不應在這裡停步，有許多操作可以應用于這些符号，而根本不必考慮它們到底代表着什麼東西。

--Hermann Weyl，The Mathematical Way of Thinking

（思維的數學方式）

我們在第1章裡關注的是計算過程，以及過程在程式中所扮演的角色。在那裡我們還看到了怎樣使用基本資料（數）和基本操作（算術運算）；怎樣通過複合、條件，以及參數的使用将一些過程組合起來，形成複合的過程；怎樣通過define做過程抽象。我們也看到，可以将一個過程看作一類計算演化的一個模式。那裡還對過程中蘊涵着的某些常見計算模式做了一些分類和推理，并做了一些簡單的算法分析。我們也看到了高階過程，這種機制能夠提升語言的威力，因為它将使我們能去操縱通用的計算方法，并能對它們做推理。這些都是程式設計中最基本的東西。

在這一章裡，我們将進一步去考察更複雜的資料。第1章裡的所有過程，操作的都是簡單的數值資料，而對我們希望用計算去處理的許多問題而言，隻有這種簡單資料還不夠。許多程式在設計時就是為了模拟複雜的現象，是以它們就常常需要構造起一些計算對象，這些對象都是由一些部分組成的，以便去模拟真實世界裡的那些具有若幹側面的現象。這樣，與我們在第1章裡所做的事情（通過将一些過程組合起來形成複合的過程，以這種方式構造起各種抽象）相對應，本章将重點轉到各種程式設計語言都包含的另一個關鍵方面：讨論它們所提供的，将資料對象組合起來，形成複合資料的方式。

為什麼在程式設計語言裡需要複合資料呢？與我們需要複合過程的原因一樣：同樣是為了提升我們在設計程式時所位于的概念層次，提高設計的子產品性，增強語言的表達能力。正如定義過程的能力使我們有可能在更高的概念層次上處理計算工作一樣，能夠構造複合資料的能力，也将使我們得以在比語言提供的基本資料對象更高的概念層次上，處理與資料有關的各種問題。

現在考慮設計一個系統，它完成有理數的算術。我們可以設想一個運算add-rat，它以兩個有理數為參數，産生出它們的和。從基本資料出發，一個有理數可以看作兩個整數，一個分子和一個分母。這樣，我們就可以設計出一個程式，其中的每個有理數用兩個整數表示（一個分子和一個分母），而其中的add-rat用兩個過程實作（一個産生和數的分子，另一個産生和數的分母）。然而，這樣做下去會非常難受，因為我們必須明确地始終記住哪個分子與哪個分母互相對應。在一個需要執行大量有理數操作的系統裡，這種記錄工作将會嚴重地攪亂我們的程式，而這些麻煩又與我們心中真正想做的事情毫無關系。如果能将一個分子和一個分母“粘在一起”，形成一個對偶—一個複合資料對象—事情就會好得多了，因為這樣，程式中對有理數的操作就可以按照将它們作為一個概念機關的方式進行了。

複合資料的使用也使我們能進一步提高程式的子產品性。如果我們可以直接在将有理數本身當作對象的方式下操作它們，那麼也就可能把處理有理數的那些程式部分，與有理數如何表示的細節（可能是表示為一對整數）隔離開。這種将程式中處理資料對象的表示的部分，與處理資料對象的使用的部分互相隔離的技術非常具有一般性，形成了一種稱為資料抽象的強有力的設計方法學。我們将會看到，資料抽象技術能使程式更容易設計、維護和修改。

複合對象的使用将真正提高程式設計語言的表達能力。考慮形成“線性組合”ax＋by，我們可能想到寫一個過程，讓它接受a、b、x和y作為參數并傳回ax＋by的值。如果以數值作為參數，這樣做沒有任何困難，因為我們立刻就能定義出下面的過程：

(define (linear-combination a b x y) 
  (+ (* a x) (* b y)))           

但是，如果我們關心的不僅僅是數，假定在寫這個過程時，我們希望表述的是基于加和乘形成線性組合的思想，所針對的可以是有理數、複數、多項式或者其他東西，我們可能将其表述為下面形式的過程：

(define (linear-combination a b x y)     
  (add (mul a x) (mul b y)))           

其中的add和mul不是基本過程＋和 *，而是某些更複雜的東西，它們能對通過參數a、b、x和y送來的任何種類的資料執行适當的操作。在這裡最關鍵的是，linear-combination對于a、b、x和y需要知道的所有東西，也就是過程add和mul能夠執行适當的操作。從過程linear-combination的角度看，a、b、x和y究竟是什麼，其實根本就沒有關系，至于它們是怎樣基于更基本的資料表示就更沒有關系了。這個例子也說明了，為什麼一種程式設計語言能夠提供直接操作複合對象的能力是如此的重要，因為如果沒有這種能力，我們就沒有辦法讓一個像linear-combination這樣的過程将其參數傳遞給add和mul，而不必知道這些參數的具體細節結構。

作為本章的開始，我們要實作上面所說的那樣一個有理數算術系統，它将成為後面讨論複合資料和資料抽象的一個基礎。與複合過程一樣，在這裡需要考慮的主要問題，也是将抽象作為克服複雜性的一種技術。下面将會看到，資料抽象将如何使我們能在程式的不同部分之間建立起适當的抽象屏障。

我們将會看到，形成複合資料的關鍵就在于，程式設計語言裡應該提供了某種“黏合劑”，它們可以用于把一些資料對象組合起來，形成更複雜的資料對象。黏合劑可能有很多不同的種類。确實的，我們還會發現怎樣去構造出根本沒有任何特定“資料”操作，隻是由過程形成的複合資料。這将進一步模糊“過程”和“資料”之間的劃分。實際上，在第1章的最後，這一界限已經開始變得不那麼清楚了。我們還要探索表示序列和樹的一些正常技術。在處理複合資料中的一個關鍵性思想是閉包的概念—也就是說，用于組合資料對象的黏合劑不但能用于組合基本的資料對象，同樣也可以用于複合的資料對象。另一關鍵思想是，複合資料對象能夠成為以混合與比對的方式組合程式子產品的友善界面。我們将通過給出一個利用閉包概念的簡單圖形語言的方式，闡釋有關的思想。

而後我們要引進符号表達式，進一步擴大語言的表述能力。符号表達式的基本部分可以是任意的符号，不一定就是數。我們将探索表示對象集合的各種不同方式，由此可以發現，就像一個給定的數學函數可以通過許多不同的計算過程計算一樣，對于一種給定的資料結構，也可以有許多方式将其表示為簡單對象的組合，而這種表示的選擇，有可能對操作這些資料的計算過程的時間與空間需求造成重大的影響。我們将在符号微分、集合的表示和資訊編碼的上下文中研究這些思想。

随後我們将轉去處理在一個程式的不同部分可能采用不同表示的資料的問題，這就引出了實作通用型操作的需要，這種操作必須能處理許多不同的資料類型。為了維持子產品性，通用型操作的出現，将要求比隻有簡單資料抽象更強大的抽象屏障。特别地，我們将介紹資料導向的程式設計。這是一種技術，它能允許我們孤立地設計每一種資料表示，而後用添加的方式将它們組合進去（也就是說，不需要任何修改）。為了展示這一系統設計方法的威力，在本章的最後，我們将用已經學到的東西實作一個多項式符号算術的程式包，其中多項式的系數可以是整數、有理數、複數，甚至還可以是其他多項式。

2.1 資料抽象導引

從1.1.8節可以看到，在構造更複雜的過程時可以将一個過程用作其中的元素，這樣的過程不但可以看作是一組特定操作，還可以看作一個過程抽象。也就是說，有關過程的實作細節可以被隐蔽起來，這個特定過程完全可以由另一個具有同樣整體行為的過程取代。換句話說，我們可以這樣造成一個抽象，它将這一過程的使用方式，與該過程究竟如何通過更基本的過程實作的具體細節互相分離。針對複合資料的類似概念被稱為資料抽象。資料抽象是一種方法學，它使我們能将一個複合資料對象的使用，與該資料對象怎樣由更基本的資料對象構造起來的細節隔離開。

資料抽象的基本思想，就是設法構造出一些使用複合資料對象的程式，使它們就像是在“抽象資料”上操作一樣。也就是說，我們的程式中使用資料的方式應該是這樣的，除了完成目前工作所必要的東西之外，它們不對所用資料做任何多餘的假設。與此同時，一種“具體”資料表示的定義，也應該與程式中使用資料的方式無關。在我們的系統裡，這樣兩個部分之間的界面将是一組過程，稱為選擇函數和構造函數，它們在具體表示之上實作抽象的資料。為了展示這一技術，下面我們将考慮怎樣設計出一組為操作有理數而用的過程。

2.1.1 執行個體：有理數的算術運算

假定我們希望做有理數上的算術，希望能做有理數的加減乘除運算，比較兩個有理數是否相等，等等。

作為開始，我們假定已經有了一種從分子和分母構造有理數的方法。并進一步假定，如果有了一個有理數，我們有一種方法取得（選出）它的分子和分母。現在再假定有關的構造函數和選擇函數都可以作為過程使用：

• (make-rat ）傳回一個有理數，其分子是整數，分母是整數。
• (numer ）傳回有理數的分子。
• (denom ）傳回有理數的分母。

我們要在這裡使用一種稱為按願望思維的強有力的綜合政策。現在我們還沒有說有理數将如何表示，也沒有說過程numer、denom和make-rat應如何實作。然而，如果我們真的有了這三個過程，那麼就可以根據下面關系去做有理數的加減乘除和相等判斷了：

我們可以将這些規則表述為如下幾個過程：

(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 (- (* (numer x) (denom y))
               (* (numer y) (denom x)))
            (* (denom x) (denom y))))
(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 y) (denom x))))           

這樣，我們已經有了定義在選擇和構造過程numer、denom和make-rat基礎之上的各種有理數運算，而這些基礎還沒有定義。現在需要有某種方式，将一個分子和一個分母粘接起來，構成一個有理數。

序對

為了在具體的層面上實作這一資料抽象，我們所用的語言提供了一種稱為序對的複合結構，這種結構可以通過基本過程cons構造出來。過程cons取兩個參數，傳回一個包含這兩個參數作為其成分的複合資料對象。如果給了一個序對，我們可以用基本過程car和cdr68，按如下方式提取出其中各個部分：

(define x (cons 1 2))
(car x)
1
(cdr x)
2           

請注意，一個序對也是一個資料對象，可以像基本資料對象一樣給它一個名字且操作它。進一步說，還可以用cons去構造那種其元素本身就是序對的序對，并繼續這樣做下去。

(define x (cons 1 2))
(define y (cons 3 4))
(define z (cons x y))
(car (car z))
1
(car (cdr z))
3           

在2.2節裡我們将看到，這種組合起序對的能力表明，序對可以用作構造任意種類的複雜資料結構的通用的基本構件。通過過程cons、car和cdr實作的這樣一種最基本的複合資料，序對，也就是我們需要的所有東西。從序對構造起來的資料對象稱為表結構資料。

有理數的表示

序對為完成這裡的有理數系統提供了一種自然方式，我們可以将有理數簡單表示為兩個整數（分子和分母）的序對。這樣就很容易做出下面make-rat、numer和denom的實作：

(define (make-rat n d) (cons n d))
(define (numer x) (car x))
(define (denom x) (cdr x))           

還有，為了顯示這裡的計算結果，我們可以将有理數列印為一個分子，在斜線符之後列印相應的分母：

(define (print-rat x)
  (newline)
  (display (numer x))
  (display "/")
  (display (denom x)))           

現在就可以試驗我們的有理數過程了：

(define one-half (make-rat 1 2))
(print-rat one-half)
1/2
(define one-third (make-rat 1 3))
(print-rat (add-rat one-half one-third))
5/6
(print-rat (mul-rat one-half one-third))
1/6
(print-rat (add-rat one-third one-third))
6/9           

正如上面最後一個例子所顯示的，我們的有理數實作并沒有将有理數約化到最簡形式。通過修改make-rat很容易做到這件事。如果我們有了一個如1.2.5節中那樣的gcd過程，用它可以求出兩個整數的最大公約數，那麼現在就可以利用它，在構造序對之前将分子和分母約化為最簡單的項：

(define (make-rat n d)
  (let ((g (gcd n d)))
    (cons (/ n g) (/ d g))))           

現在我們就有：

(print-rat (add-rat one-third one-third))
2/3
           

正如所期望的。為了完成這一改動，我們隻需修改構造符make-rat，完全不必修改任何實作實際運算的過程（例如add-rat和mul-rat）。

練習2.1 請定義出make-rat的一個更好的版本，使之可以正确處理正數和負數。當有理數為正時，make-rat應當将其規範化，使它的分子和分母都是正的。如果有理數為負，那麼就應隻讓分子為負。

2.1.2 抽象屏障

在繼續讨論更多複合資料和資料抽象的執行個體之前，讓我們首先考慮一下由有理數的例子提出的幾個問題。前面給出的所有有理數操作，都是基于構造函數make-rat和選擇函數numer、denom定義出來的。一般而言，資料抽象的基本思想就是為每一類資料對象辨別出一組操作，使得對這類資料對象的所有操作都可以基于它們表述，而且在操作這些資料對象時也隻使用它們。

圖2-1形象化地表示了有理數系統的結構。其中的水準線表示抽象屏障，它們隔離了系統中不同的層次。在每一層上，這種屏障都把使用資料抽象的程式（上面）與實作資料抽象的程式（下面）分開來。使用有理數的程式将僅僅通過有理數包提供給“公衆使用”的那些過程（add-rat、sub-rat、mul-rat、div-rat和equal-rat?）去完成對有理數的各種操作；這些過程轉而又是完全基于構造函數和選擇函數make-rat、numer和denom實作的；而這些函數又是基于序對實作的。隻要序對可以通過cons、car和cdr操作，有關序對如何實作的細節與有理數包的其餘部分都完全沒有關系。從作用上看，每一層次中的過程構成了所定義的抽象屏障的界面，聯系起系統中的不同層次。

這一簡單思想有許多優點。第一個優點是這種方法使程式很容易維護和修改。任意一種比較複雜的資料結構，都可以以多種不同方式用程式設計語言所提供的基本資料結構表示。當然，表示方式的選擇會對操作它的程式産生影響，這樣，如果後來表示方式改變了，所有受影響的程式也都需要随之改變。對于大型程式而言，這種工作将非常耗時，而且代價極其昂貴，除非在設計時就已經将依賴于表示的成分限制到很少的一些程式子產品上。

例如，将有理數約化到最簡形式的工作，也完全可以不在構造的時候做，而是在每次通路有理數中有關部分時去做。這樣就會導緻另一套不同的構造函數和選擇函數：

(define (make-rat n d)
  (cons n d))
(define (numer x)
  (let ((g (gcd (car x) (cdr x))))
    (/ (car x) g)))
(define (denom x)
  (let ((g (gcd (car x) (cdr x))))
    (/ (cdr x) g)))           

這一實作與前面實作的不同之處在于何時計算gcd。如果在有理數的典型使用中，我們需要多次通路同一個有理數的分子和分母，那麼最好是在構造有理數的時候計算gcd。如果情況并不是這樣，那麼把對gcd的計算推遲到通路時也許更好一些。在這裡，在任何情況下，當我們從一種表示方式轉到另一種表示時，過程add-rat、sub-rat等等都完全不必修改。

把對于具體表示方式的依賴性限制到少數幾個界面過程，不但對修改程式有幫助，同時也有助于程式的設計，因為這種做法将使我們能保留考慮不同實作方式的靈活性。繼續前面的簡單例子，假定現在我們正在設計有理數程式包，而且還無法決定究竟是在建立時執行gcd，還是應該将它推遲到選擇的時候。資料抽象方法使我們能推遲決策的時間，而又不會阻礙系統其他部分的工作進展。

練習2.2 請考慮平面上線段的表示問題。一個線段用一對點表示，它們分别是線段的始點與終點。請定義構造函數make-segment和選擇函數start-segment、end-segment，它們基于點定義線段的表示。進而，一個點可以用數的序對表示，序對的兩個成分分别表示點的x坐标和y坐标。請據此進一步給出構造函數make-point和選擇函數x-point、y-point，用它們定義出點的這種表示。最後，請基于所定義的構造函數和選擇函數，定義出過程midpoint-segment，它以一個線段為參數，傳回線段的中點（也就是那個坐标值是兩個端點的平均值的點）。為了試驗這些過程，還需要定義一種列印點的方法：

(define (print-point p)
  (newline)
  (display "(")
  (display (x-point p))
  (display ",")
  (display (y-point p))
  (display ")"))           

練習2.3 請實作一種平面矩形的表示（提示：你有可能借用練習2.2的結果）。基于你的構造函數和選擇函數定義幾個過程，計算給定矩形的周長和面積等。現在請再為矩形實作另一種表示方式。你應該怎樣設計系統，使之能提供适當的抽象屏障，使同一個周長或者面積過程對兩種不同表示都能工作？

2.1.3 資料意味着什麼

在2.1.1節裡實作有理數時，我們基于三個尚未定義的過程make-rat、numer和denom，由這些出發去做有理數操作add-rat、sub-rat等等的實作。按照那時的想法，這些操作是基于資料對象（分子、分母、有理數）定義的，這些對象的行為完全由前面三個過程刻畫。

那麼，資料究竟意味着什麼呢？說它就是“由給定的構造函數和選擇函數所實作的東西”還是不夠的。顯然，并不是任意的三個過程都适合作為有理數實作的基礎。在這裡，我們需要保證，如果從一對整數n和d構造出一個有理數x，那麼，抽取出x的numer和denom并将它們相除，得到的結果應該與n除以d相同。換句話說，make-rat、numer和denom必須滿足下面條件，對任意整數n和任意非零整數d，如果x是（make-rat n d），那麼：

事實上，這就是為了能成為适宜表示有理數的基礎，make-rat、numer和denom必須滿足的全部條件。一般而言，我們總可以将資料定義為一組适當的選擇函數和構造函數，以及為使這些過程成為一套合法表示，它們就必須滿足的一組特定條件。

這一觀點不僅可以服務于“高層”資料對象的定義，例如有理數，同樣也可用于低層的對象。請考慮序對的概念，我們在前面用它定義有理數。我們從來都沒有說過序對究竟是什麼，隻說所用的語言為序對的操作提供了三個過程cons、car和cdr。有關這三個操作，我們需要知道的全部東西就是，如果用cons将兩個對象粘接到一起，那麼就可以借助于car和cdr提取出這兩個對象。也就是說，這些操作滿足的條件是：對任何對象x和y，如果z是（cons x y），那麼（car z）就是x，而（cdr z）就是y。我們确實說過這三個過程是所用的語言裡的基本過程。然而，任何能滿足上述條件的三個過程都可以成為實作序對的基礎。下面這個令人吃驚的事實能夠最好地說明這一點：我們完全可以不用任何資料結構，隻使用過程就可以實作序對。下面是有關的定義：

(define (cons x 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))           

過程的這一使用方式與我們有關資料應該是什麼的直覺認識大相徑庭。但不管怎麼說，如果要求我們說明這确實是一種表示序對的合法方式，那麼隻需要驗證，上述幾個過程滿足了前面提出的所有條件。

應該特别注意這裡的一個微妙之處：由（cons x y）傳回的值是一個過程—也就是那個内部定義的過程dispatch，它有一個參數，并能根據參數是0還是1，分别傳回x或者y。與此相對應，（car z）被定義為将z應用于0，這樣，如果z是由（cons x y）形成的過程，将z應用于0将會産生x，這樣就證明了（car（cons x y））産生出x，正如我們所需要的。與此類似，（cdr（cons x y））将（cons x y）産生的過程應用于1而得到y。是以，序對的這一過程實作确實是一個合法的實作，如果隻通過cons、car和cdr通路序對，我們将無法把這一實作與“真正的”資料結構區分開。

上面展示了序對的一種過程性表示，這并不意味着我們所用的語言就是這樣做的（Scheme和一般的Lisp系統都直接實作序對，主要是為了效率），而是說它确實可以這樣做。這一過程性表示雖然有些隐晦，但它确實是一種完全合适的表示序對的方式，因為它滿足了序對需要滿足的所有條件。這一執行個體也說明可以将過程作為對象去操作，是以就自動地為我們提供了一種表示複合資料的能力。這些東西現在看起來好像隻是很好玩，但實際上，資料的過程性表示将在我們的程式設計寶庫裡扮演一種核心角色。有關的程式設計風格通常稱為消息傳遞。在第3章裡讨論模型和模拟時，我們将用它作為一種基本工具。

練習2.4 下面是序對的另一種過程性表示方式。請針對這一表示驗證，對于任意的x和y，（car（cons x y））都将産生出x。

(define (cons x y)
  (lambda (m) (m x y)))
(define (car z)
  (z (lambda (p q) p)))           

對應的cdr應該如何定義？（提示：為了驗證這一表示确實能行，請利用1.1.5節的代換模型。）

練習2.5 請證明，如果将a和b的序對表示為乘積2a 3b對應的整數，我們就可以隻用非負整數和算術運算表示序對。請給出對應的過程cons、car和cdr的定義。

練習2.6 如果覺得将序對表示為過程還不足以令人如雷灌頂，那麼請考慮，在一個可以對過程做各種操作的語言裡，我們完全可以沒有數（至少在隻考慮非負整數的情況下），可以将0和加一操作實作為：

(define zero (lambda (f) (lambda (x) x)))
(define (add-1 n)
  (lambda (f) (lambda (x) (f ((n f) x)))))           

這一表示形式稱為Church計數，名字來源于其發明人數理邏輯學家Alonzo Church（丘奇），l演算也是他發明的。

請直接定義one和two（不用zero和add-1）（提示：利用代換去求值（add-1 zero））。請給出加法過程＋的一個直接定義（不要通過反複應用add-1）。

2.1.4 擴充練習：區間算術

Alyssa P. Hacker正在設計一個幫助人們求解工程問題的系統。她希望這個系統提供的一個特征是能夠去操作不準确的量（例如實體裝置的測量參數），這種量具有已知的精度，是以，在對這種近似量進行計算時，得到的結果也應該是已知精度的數值。

電子工程師将會用Alyssa的系統去計算一些電子量。有時他們必須使用下面公式，從兩個電阻R1和R2計算出并聯等價電阻Rp的值：

此時所知的電阻值通常是由電阻生産廠商給出的帶誤差保證的值，例如你可能買到一支标明“6.8歐姆誤差10%”的電阻，這時我們就隻能确定，這支電阻的阻值在6.8－0.68＝6.12和6.8＋0.68＝7.48歐姆之間。這樣，如果将一支6.8歐姆誤差10%的電阻與另一支4.7歐姆誤差5%的電阻并聯，這一組合的電阻值可以在大約2.58歐姆（如果兩支電阻都有最小值）和2.97歐姆（如果兩支電阻都是最大值）之間。

Alyssa的想法是實作一套“區間算術”，即作為可以用于組合“區間”（表示某種不準确量的可能值的對象）的一組算術運算。兩個區間的加、減、乘、除的結果仍是一個區間，表示的是計算結果的範圍。

Alyssa假設有一種稱為“區間”的抽象對象，這種對象有兩個端點，一個下界和一個上界。她還假定，給了一個區間的兩個端點，就可以用資料構造函數make-interval構造出相應的區間來。Alyssa首先寫出了一個做區間加法的過程，她推理說，和的最小值應該是兩個區間的下界之和，其最大值應該是兩個區間的上界之和：

(define (add-interval x y)
  (make-interval (+ (lower-bound x) (lower-bound y))
                 (+ (upper-bound x) (upper-bound y))))           

Alyssa還找出了這種界的乘積的最小和最大值，用它們做出了兩個區間的乘積（min和max是求出任意多個參數中的最小值和最大值的基本過程）。

(define (mul-interval x y)
  (let ((p1 (* (lower-bound x) (lower-bound y)))
        (p2 (* (lower-bound x) (upper-bound y)))
        (p3 (* (upper-bound x) (lower-bound y)))
        (p4 (* (upper-bound x) (upper-bound y))))
    (make-interval (min p1 p2 p3 p4)
                   (max p1 p2 p3 p4))))           

為了做出兩個區間的除法，Alyssa用第一個區間乘上第二個區間的倒數。請注意，倒數的兩個界限分别是原來區間的上界的倒數和下界的倒數：

(define (div-interval x y)
  (mul-interval x 
                (make-interval (/ 1.0 (upper-bound y))
                               (/ 1.0 (lower-bound y)))))           

練習2.7 Alyssa的程式是不完整的，因為她還沒有确定區間抽象的實作。這裡是區間構造符的定義：

(define (make-interval a b) (cons a b))           

請定義選擇符upper-bound和lower-bound，完成這一實作。

練習2.8 通過類似于Alyssa的推理，說明兩個區間的差應該怎樣計算。請定義出相應的減法過程sub-interval。

練習2.9 區間的寬度就是其上界和下界之差的一半。區間寬度是有關區間所描述的相應數值的非确定性的一種度量。對于某些算術運算，兩個區間的組合結果的寬度就是參數區間的寬度的函數，而對其他運算，組合區間的寬度則不是參數區間寬度的函數。證明兩個區間的和（與差）的寬度就是被加（或減）的區間的寬度的函數。舉例說明，對于乘和除而言，情況并非如此。

練習2.10 Ben Bitdiddle是個專業程式員，他看了Alyssa工作後評論說，除以一個跨過橫跨0的區間的意義不清楚。請修改Alyssa的代碼，檢查這種情況并在出現這一情況時報錯。

練習2.11 在看了這些東西之後，Ben又說出了下面這段有些神秘的話：“通過監測區間的端點，有可能将mul-interval分解為9種情況，每種情況中所需的乘法都不超過兩次。”請根據Ben的建議重寫這個過程。

在排除了自己程式裡的錯誤之後，Alyssa給一個可能使用者示範自己的程式。那個使用者卻說她的程式解決的問題根本不對。他希望能夠有一個程式，可以用于處理那種用一個中間值和一個附加誤差的形式表示的數，也就是說，希望程式能處理3.5±0.15而不是[3.35，3.65]。Alyssa回到自己的辦公桌來糾正這一問題，另外提供了一個構造符和一個選擇符：

(define (make-center-width c w)
  (make-interval (- c w) (+ c w)))
(define (center i)
  (/ (+ (lower-bound i) (upper-bound i)) 2))
(define (width i)
  (/ (- (upper-bound i) (lower-bound i)) 2))           

不幸的是，Alyssa的大部分使用者是工程師，現實中的工程師經常遇到隻有很小非準确性的測量值，而且常常是以區間寬度對區間中點的比值作為路徑成本。他們通常用的是基于有關部件的參數的百分數描述的誤差，就像前面描述電阻值的那種方式一樣。

練習2.12 請定義一個構造函數make-center-percent，它以一個中心點和一個百分比為參數，産生出所需要的區間。你還需要定義選擇函數percent，通過它可以得到給定區間的百分數誤差，選擇函數center與前面定義的一樣。

練習2.13 請證明，在誤差為很小的百分數的條件下，存在着一個簡單公式，利用它可以從兩個被乘區間的誤差算出乘積的百分數誤內插補點。你可以假定所有的數為正，以簡化這一問題。

經過相當多的工作之後，Alyssa P. Hacker釋出了她的最後系統。幾年之後，在她已經忘記了這個系統之後，接到了一個憤怒的使用者Lem E. Tweakit的發瘋式的電話。看起來Lem注意到并聯電阻的公式可以寫成兩個代數上等價的公式：

和

這樣他就寫了兩個程式，它們以不同的方式計算并聯電阻值：

(define (par1 r1 r2)
  (div-interval (mul-interval r1 r2)
                (add-interval r1 r2)))
(define (par2 r1 r2)
  (let ((one (make-interval 1 1))) 
    (div-interval one
                  (add-interval (div-interval one r1)
                                (div-interval one r2)))))           

Lem抱怨說，Alyssa程式對兩種不同計算方法給出不同的值。這确實是很嚴重的抱怨。

練習2.14 請确認Lem是對的。請你用各種不同的算術表達式來檢查這一系統的行為。請做出兩個區間A和B，并用它們計算表達式A/A和A/B。如果所用區間的寬度相對于中心值取很小百分數，你将會得到更多的認識。請檢查對于中心－百分比形式（見練習2.12）進行計算的結果。

練習2.15 另一使用者Eva Lu Ator也注意到了由不同的等價代數表達式計算出的區間的差異。她說，如果一個公式可以寫成一種形式，其中具有非準确性的變量不重複出現，那麼Alyssa的系統産生出的區間的限界更緊一些。她說，是以，在計算并聯電阻時，par2是比par1“更好的”程式。她說得對嗎？

練習2.16 請給出一個一般性的解釋：為什麼等價的代數表達式可能導緻不同計算結果？你能設計出一個區間算術包，使之沒有這種缺陷嗎？或者這件事情根本不可能做到？（警告：這個問題非常難。）

2.2 層次性資料和閉包性質

正如在前面已經看到的，序對為我們提供了一種用于構造複合資料的基本“黏結劑”。圖2-2展示的是一種以形象的形式看序對的标準方式，其中的序對是通過（cons 1 2）形成的。在這種稱為盒子和指針表示方式中，每個對象表示為一個指向盒子的指針。與基本對象相對應的盒子裡包含着該對象的表示，例如，表示數的盒子裡就放着那個具體的數。用于表示序對的盒子實際上是一對方盒，其中左邊的方盒裡放着序對的car（指向car的指針），右邊部分放着相應的cdr。

前面已經看到了，我們不僅可以用cons去組合起各種數值，也可以用它去組合起序對（你在做練習2.2和練習2.3時已經，或者說應該，熟悉這一情況了）。作為這種情況的推論，序對就是一種通用的建築砌塊，通過它可以構造起所有不同種類的資料結構來。圖2-3顯示的是組合起數值1、2、3、4的兩種不同方式。

我們可以建立元素本身也是序對的序對，這就是表結構得以作為一種表示工具的根本基礎。我們将這種能力稱為cons的閉包性質。一般說，某種組合資料對象的操作滿足閉包性質，那就是說，通過它組合起資料對象得到的結果本身還可以通過同樣的操作再進行組合。閉包性質是任何一種組合功能的威力的關鍵要素，因為它使我們能夠建立起層次性的結構，這種結構由一些部分構成，而其中的各個部分又是由它們的部分構成，并且可以如此繼續下去。

從第1章的開始，我們在處理過程的問題中就利用了閉包性質，而且是最本質性的東西，因為除了最簡單的程式外，所有程式都依賴于一個事實：組合式的成員本身還可以是組合式。在這一節裡，我們要着手研究複合資料的閉包所引出的問題。這裡将要描述一些用起來很友善的技術，包括用序對來表示序列和樹。還要給出一種能以某種很生動的形式顯示閉包的圖形語言。

2.2.1 序列的表示

利用序對可以構造出的一類有用結構是序列—一批資料對象的一種有序彙集。顯然，采用序對表示序列的方式很多，一種最直接的表示方式如圖2-4所示，其中用一個序對的鍊條表示出序列1，2，3，4，在這裡，每個序對的car部分對應于這個鍊中的條目，cdr則是鍊中下一個序對。最後的一個序對的cdr用一個能辨明不是序對的值表示，标明序列的結束，在盒子指針圖中用一條對角線表示，在程式裡用變量nil的值。整個序列可以通過嵌套的cons操作構造起來：

(cons 1
      (cons 2
            (cons 3
                  (cons 4 nil))))           

通過嵌套的cons形成的這樣一個序對的序列稱為一個表，Scheme為友善表的構造，提供了一個基本操作list74，上面序列也可以通過（list 1 2 3 4）産生。一般說：

(list <a1> <a2> ... <an>)           

等價于：

(cons <a1> (cons <a2> (cons ... (cons <an> nil) ...)))           

Lisp系統通常用元素序列的形式列印出表，外面用括号括起。按照這種方式，圖2-4裡的資料對象就将列印為（1 2 3 4）：

(define one-through-four (list 1 2 3 4))
one-through-four
(1 2 3 4)           

請當心，不要将表達式（list 1 2 3 4）和表（1 2 3 4）搞混了。後面這個表是對前面表達式求值得到的結果。如果想去求值表達式（1 2 3 4），解釋器就會試圖将過程1應用于參數2、3和4，這時會發出一個出錯信号。

我們可以将car看作選取表的第一項的操作，将cdr看作是選取表中除去第一項之後剩下的所有項形成的子表。car和cdr的嵌套應用可以取出一個表裡的第二、第三以及後面的各項。構造符cons可用于構造表，它在原有的表前面增加一個元素：

(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)
(cons 5 one-through-four)
(5 1 2 3 4)           

nil的值用于表示序對的鍊結束，它也可以當作一個不包含任何元素的序列，空表。單詞“nil”是拉丁詞彙“nihil”的縮寫，這個拉丁詞彙表示“什麼也沒有”。

表操作

利用序對将元素的序清單示為表之後，我們就可以使用正常的程式設計技術，通過順序“向下cdr”表的方式完成對表的各種操作了。例如，下面的過程list-ref的實際參數是一個表和一個數n，它傳回這個表中的第n個項。這裡人們習慣令表元素的編号從0開始。計算list-ref的方法如下：

• 對n＝0，list-ref應傳回表的car。
• 否則，list-ref傳回表的cdr的第（n－1）個項。

(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           

我們經常要向下cdr整個的表，為了幫助做好這件事，Scheme包含一個基本操作null?，用于檢查參數是不是空表。傳回表中項數的過程length可以說明這一典型應用模式：

(define (length items)
  (if (null? items)
      0
      (+ 1 (length (cdr items)))))
(define odds (list 1 3 5 7))
(length odds)
4           

過程length實作一種簡單的遞歸方案，其中的遞歸步驟是：

• 任意一個表的length就是這個表的cdr的length加一。

順序地這樣應用，直至達到了基礎情況：

• 空表的length是0。

我們也可以用一種疊代方式來計算length：

(define (length items)
  (define (length-iter a count)
    (if (null? a)
        count
        (length-iter (cdr a) (+ 1 count))))
  (length-iter items 0))           

另一常用程式設計技術是在向下cdr一個表的過程中“向上cons”出一個結果表，例如過程append，它以兩個表為參數，用它們的元素組合成一個新表：

(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也是用一種遞歸方案實作的。要得到表list1和list2的append，按如下方式做：

• 如果list1是空表，結果就是list2。
• 否則應先做出list1的cdr和list2的append，而後再将list1的car通過cons加到結果的前面：

(define (append list1 list2)
       (if (null? list1)
           list2
           (cons (car list1) (append (cdr list1) list2))))           

練習2.17 請定義出過程last-pair，它傳回隻包含給定（非空）表裡最後一個元素的表：

(last-pair (list 23 72 149 34))
(34)           

練習2.18 請定義出過程reverse，它以一個表為參數，傳回的表中所包含的元素與參數表相同，但排列順序與參數表相反：

(reverse (list 1 4 9 16 25))
(25 16 9 4 1)           

練習2.19 請考慮1.2.2節的兌換零錢方式計數程式。如果能夠輕而易舉地改變程式裡所用的兌換币種就更好了。譬如說，那樣我們就能計算出1英鎊的不同兌換方式的數目。在寫前面那個程式時，有關币種的知識中有一部分出現在過程first-denomination裡，另一部分出現在過程裡count-change（它知道有5種U.S.硬币）。如果能夠用一個表來提供可用于兌換的硬币就更好了。

我們希望重寫出過程cc，使其第二個參數是一個可用硬币的币值表，而不是一個指定可用硬币種類的整數。而後我們就可以針對各種貨币定義出一些表：

(define us-coins (list 50 25 10 5 1))
(define uk-coins (list 100 50 20 10 5 2 1 0.5))           

然後我們就可以通過如下方式調用cc：

(cc 100 us-coins)
292           

為了做到這件事，我們需要對程式cc做一些修改。它仍然具有同樣的形式，但将以不同的方式通路自己的第二個參數，如下面所示：

(define (cc amount coin-values)
  (cond ((= amount 0) 1)
        ((or (< amount 0) (no-more? coin-values)) 0)
        (else
         (+ (cc amount
                (except-first-denomination coin-values))
            (cc (- amount
                   (first-denomination coin-values))
                coin-values)))))           

請基于表結構上的基本操作，定義出過程first-denomination、except-first-denomination和no-more?。表coin-values的排列順序會影響cc給出的回答嗎？為什麼？

練習2.20 過程＋、*和list可以取任意個數的實際參數。定義這類過程的一種方式是采用一種帶點尾部記法形式的define。在一個過程定義中，如果在形式參數表的最後一個參數之前有一個點号，那就表明，當這一過程被實際調用時，前面各個形式參數（如果有的話）将以前面的各個實際參數為值，與平常一樣。但最後一個形式參數将以所有剩下的實際參數的表為值。例如，假若我們定義了：

(define (f x y . z) <body>)           

過程f就可以用兩個以上的參數調用。如果求值：

(f 1 2 3 4 5 6)           

那麼在f的體裡，x将是1，y将是2，而z将是表（3 4 5 6）。給了定義：

(define (g . w) <body>)           

過程g可以用0個或多個參數調用。如果求值：

(g 1 2 3 4 5 6)           

那麼在g的體裡，w将是表（1 2 3 4 5 6）。

請采用這種記法形式寫出過程same-parity，它以一個或者多個整數為參數，傳回所有與其第一個參數有着同樣奇偶性的參數形成的表。例如：

(same-parity 1 2 3 4 5 6 7)
(1 3 5 7)
(same-parity 2 3 4 5 6 7)
(2 4 6)           

對表的映射

一個特别有用的操作是将某種變換應用于一個表的所有元素，得到所有結果構成的表。舉例來說，下面過程将一個表裡的所有元素按給定因子做一次縮放：

(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)           

我們可以抽象出這一具有一般性的想法，将其中的公共模式表述為一個高階過程，就像1.3節裡所做的那樣。這一高階過程稱為map，它有一個過程參數和一個表參數，傳回将這一過程應用于表中各個元素得到的結果形成的表。

(define (map proc items)
  (if (null? items)
      nil
      (cons (proc (car items))
            (map proc (cdr items)))))
(map abs (list -10 2.5 -11.6 17))
(10 2.5 11.6 17)
(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))           

map是一種很重要的結構，不僅因為它代表了一種公共模式，而且因為它建立起了一種處理表的高層抽象。在scale-list原來的定義裡，程式的遞歸結構将人的注意力吸引到對于表中逐個元素的處理上。通過map定義scale-list抑制了這種細節層面上的情況，強調的是從元素表到結果表的一個縮放變換。這兩種定義形式之間的差異，并不在于計算機會執行不同的計算過程（其實不會），而在于我們對這同一個過程的不同思考方式。從作用上看，map幫我們建起了一層抽象屏障，将實作表變換的過程的實作，與如何提取表中元素以及組合結果的細節隔離開。與圖2-1裡所示的屏障類似，這種抽象也提供了新的靈活性，使我們有可能在保持從序列到序列的變換操作架構的同時，改變序列實作的低層細節。2.2.3節将把序列的這種使用方式擴充為一種組織程式的架構。

練習2.21 過程square-list以一個數值表為參數，傳回每個數的平方構成的表：

(square-list (list 1 2 3 4))
(1 4 9 16)           

下面是square-list的兩個定義，請填充其中缺少的表達式以完成它們：

(define (square-list items)
  (if (null? items)
      nil
      (cons <??> <??>)))
(define (square-list items)
  (map <??> <??>))           

練習2.22 Louis Reasoner試圖重寫練習2.21的第一個square-list過程，希望使它能生成一個疊代計算過程：

(define (square-list items)
  (define (iter things answer)
    (if (null? things)
        answer
        (iter (cdr things) 
              (cons (square (car things))
                    answer))))
  (iter items nil))           

但是很不幸，在按這種方式定義出的square-list産生出的結果表中，元素的順序正好與我們所需要的相反。為什麼？

Louis又試着修正其程式，交換了cons的參數：

(define (square-list items)
  (define (iter things answer)
    (if (null? things)
        answer
        (iter (cdr things)
              (cons answer
                    (square (car things))))))
  (iter items nil))           

但還是不行。請解釋為什麼。

練習2.23 過程for-each與map類似，它以一個過程和一個元素表為參數，但它并不傳回結果的表，隻是将這一過程從左到右應用于各個元素，将過程應用于元素得到的值都丢掉不用。for-each通常用于那些執行了某些動作的過程，如列印等。看下面例子：

(for-each (lambda (x) (newline) (display x))
          (list 57 321 88))
57
321
88           

由for-each的調用傳回的值（上面沒有顯示）可以是某種任意的東西，例如邏輯值真。請給出一個for-each的實作。

2.2.2 層次性結構

将表作為序列的表示方式，可以很自然地推廣到表示那些元素本身也是序列的序列。舉例來說，我們可以認為對象（（1 2）3 4）是通過下面方式構造出來的：

(cons (list 1 2) (list 3 4))           

這是一個包含三個項的表，其中的第一項本身又是表（1 2）。這一情況也由解釋器的列印形式所肯定。圖2-5用序對的語言展示出這一結構的表示形式。

認識這種元素本身也是序列的序列的另一種方式，是把它們看作樹。序列裡的元素就是樹的分支，而那些本身也是序列的元素就形成了樹中的子樹。圖2-6顯示的是将圖2-5的結構看作樹的情況。

遞歸是處理樹結構的一種很自然的工具，因為我們常常可以将對于樹的操作歸結為對它們的分支的操作，再将這種操作歸結為對分支的分支的操作，如此下去，直至達到了樹的葉子。作為例子，請比較一下2.2.1節的length過程和下面的count-leaves過程，這個過程統計出一棵樹中樹葉的數目：

(define x (cons (list 1 2) (list 3 4)))
(length x)
3
(count-leaves x)
4
(list x x)
(((1 2) 3 4) ((1 2) 3 4))
(length (list x x))
2
(count-leaves (list x x))
8           

為了實作count-leaves，可以先回憶一下length的遞歸方案：

• 表x的length是x的cdr的length加一。

count-leaves的遞歸方案與此類似，對于空表的值也相同：

• 空表的count-leaves是0，

但是在遞歸步驟中，當我們去掉一個表的car時，就必須注意這一car本身也可能是樹，其樹葉也需要考慮。這樣，正确的歸約步驟應該是：

• 對于樹x的count-leaves應該是x的car的count-leaves與x的cdr的count-leaves之和。

最後，在通過car達到一個實際的樹葉時，我們還需要另一種基本情況：

• 一個樹葉的count-leaves是1。

為了有助于寫出樹上的各種遞歸，Scheme提供了基本過程pair?，它檢查其參數是否為序對。下面就是我們完成的過程79：

(define (count-leaves x)
  (cond ((null? x) 0)  
        ((not (pair? x)) 1)
        (else (+ (count-leaves (car x))
                 (count-leaves (cdr x))))))           

練習2.24 假定現在要求值表達式（list 1（list 2（list 3 4））），請給出由解釋器列印出的結果，給出與之對應的盒子指針結構，并将它解釋為一棵樹（參見圖2-6）。

練習2.25 給出能夠從下面各表中取出7的car和cdr組合：

(1 3 (5 7) 9)
((7))
(1 (2 (3 (4 (5 (6 7))))))           

練習2.26 假定已将x和y定義為如下的兩個表：

(define x (list 1 2 3))
(define y (list 4 5 6))           

解釋器對于下面各個表達式将列印出什麼結果：

(append x y)
(cons x y)
(list x y)           

練習2.27 修改練習2.18中所做的reverse過程，得到一個deep-reverse過程。它以一個表為參數，傳回另一個表作為值，結果表中的元素反轉過來，其中的子樹也反轉。例如：

(define x (list (list 1 2) (list 3 4)))
x
((1 2) (3 4))
(reverse x)
((3 4) (1 2))
(deep-reverse x)
((4 3) (2 1))           

練習2.28 寫一個過程fringe，它以一棵樹（表示為表）為參數，傳回一個表，表中的元素是這棵樹的所有樹葉，按照從左到右的順序。例如：

(define x (list (list 1 2) (list 3 4)))
(fringe x)
(1 2 3 4)
(fringe (list x x))
(1 2 3 4 1 2 3 4)           

練習2.29 一個二叉活動體由兩個分支組成，一個是左分支，另一個是右分支。每個分支是一個具有确定長度的杆，上面或者吊着一個重量，或者吊着另一個二叉活動體。我們可以用複合資料對象表示這種二叉活動體，将它通過其兩個分支構造起來（例如，使用list）：

(define (make-mobile left right)
  (list left right))           

分支可以從一個length（它應該是一個數）再加上一個structure構造出來，這個structure或者是一個數（表示一個簡單重量），或者是另一個活動體：

(define (make-branch length structure)
  (list length structure))           

a) 請寫出相應的選擇函數left-branch和right-branch，它們分别傳回活動體的兩個分支。還有branch-length和branch-structure，它們傳回一個分支上的成分。

b) 用你的選擇函數定義過程total-weight，它傳回一個活動體的總重量。

c) 一個活動體稱為是平衡的，如果其左分支的力矩等于其右分支的力矩（也就是說，如果其左杆的長度乘以吊在杆上的重量，等于這個活動體右邊的同樣乘積），而且在其每個分支上吊着的子活動體也都平衡。請設計一個過程，它能檢查一個二叉活動體是否平衡。

d) 假定我們改變活動體的表示，采用下面構造方式：

(define (make-mobile left right)
  (cons left right))
(define (make-branch length structure)
  (cons length structure))           

你需要對自己的程式做多少修改，才能将它改為使用這種新表示？

對樹的映射

map是處理序列的一種強有力抽象，與此類似，map與遞歸的結合也是處理樹的一種強有力抽象。舉例來說，可以有與2.2.1節的scale-list類似的scale-tree過程，以一個數值因子和一棵葉子為數值的樹作為參數，傳回一棵具有同樣形狀的樹，樹中的每個數值都乘以了這個因子。對于scale-tree的遞歸方案也與count-leaves的類似：

(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))           

實作scale-tree的另一種方法是将樹看成子樹的序列，并對它使用map。我們在這種序列上做映射，依次對各棵子樹做縮放，并傳回結果的表。對于基礎情況，也就是當被處理的樹是樹葉時，就直接用因子去乘它：

(define (scale-tree tree factor)
  (map (lambda (sub-tree)
         (if (pair? sub-tree)
             (scale-tree sub-tree factor)
             (* sub-tree factor)))
       tree))           

對于樹的許多操作可以采用類似方式，通過序列操作和遞歸的組合實作。

練習2.30 請定義一個與練習2.21中square-list過程類似的square-tree過程。也就是說，它應該具有下面的行為：

(square-tree
 (list 1
       (list 2 (list 3 4) 5)
       (list 6 7)))
(1 (4 (9 16) 25) (36 49))           

請以兩種方式定義square-tree，直接定義（即不使用任何高階函數），以及使用map和遞歸定義。

練習2.31 将你在練習2.30做出的解答進一步抽象，做出一個過程，使它的性質保證能以下面形式定義square-tree：

(define (square-tree tree) (tree-map square tree))           

練習2.32 我們可以将一個集合表示為一個元素互不相同的表，是以就可以将一個集合的所有子集表示為表的表。例如，假定集合為（1 2 3），它的所有子集的集合就是（（）（3）（2）（2 3）（1）（1 3）（1 2）（1 2 3））。請完成下面的過程定義，它生成出一個集合的所有子集的集合。請解釋它為什麼能完成這一工作。

(define (subsets s)
  (if (null? s)
      (list nil)
      (let ((rest (subsets (cdr s))))
        (append rest (map <??> rest)))))           

2.2.3 序列作為一種約定的界面

我們一直強調資料抽象在對複合資料的工作中的作用，借助這種思想，我們就能設計出不會被資料表示的細節糾纏的程式，使程式能夠保持很好的彈性，得以應用到不同的具體表示上。在這一節裡，我們将要介紹與資料結構有關的另一種強有力的設計原理—使用約定的界面。

在1.3節裡我們看到，可以通過實作為高階過程的程式抽象，抓住處理數值資料的一些程式模式。要在複合資料上工作做出類似的操作，則對我們操控資料結構的方式有着深刻的依賴性。舉個例子，考慮下面與2.2.2節中count-leaves過程類似的過程，它以一棵樹為參數，計算出那些值為奇數的葉子的平方和：

(define (sum-odd-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))))))           

從表面上看，這一過程與下面的過程很不一樣。下面這個過程構造出的是所有偶數的斐波那契數Fib(k) 的一個表，其中的k小于等于某個給定整數n：

(define (even-fibs n)
  (define (next k)
    (if (> k n)
        nil
        (let ((f (fib k)))
          (if (even? f)
              (cons f (next (+ k 1)))
              (next (+ k 1))))))
  (next 0))           

雖然這兩個過程在結構上差異非常大，但是對于兩個計算的抽象描述卻會揭示出它們之間極大的相似性。第一個程式：

• 枚舉出一棵樹的樹葉；
• 過濾它們，選出其中的奇數；
• 對選出的每一個數求平方；
• 用＋累積起得到的結果，從0開始。

而第二個程式：

• 枚舉從0到n的整數；
• 對每個整數計算相應的斐波那契數；
• 過濾它們，選出其中的偶數；
• 用cons累積得到的結果，從空表開始。

信号處理工程師們可能會發現，這種過程可以很自然地用流過一些級聯的處理步驟的信号的方式描述，其中的每個處理步驟實作程式方案中的一個部分，如圖2-7所示。對于第一種情況sum-odd-squares，我們從一個枚舉器開始，它産生出由給定的樹的所有樹葉組成“信号”。這一信号流過一個過濾器，所有不是奇數的數都被删除了。這樣得到的信号又通過一個映射，這是一個“轉換裝置”，它将square過程應用于每個元素。這一映射的輸出被饋入一個累積器，該裝置用＋将得到的所有元素組合起來，以初始的0開始。even-fibs的工作過程與此類似。

遺憾的是，上面的兩個過程定義并沒有展現出這種信号流結構。譬如說，如果仔細考察sum-odd-squares過程，就會發現其中的枚舉工作部分地由檢查null?和pair?實作，部分地由過程的樹形遞歸結構實作。與此類似，在那些檢查中也可以看到一部分累積工作，另一部分是用在遞歸中的加法。一般而言，在這兩個過程裡，沒有一個部分正好對應于信号流描述中的某一要素。我們的兩個過程采用不同的方式分解了這個計算，将枚舉工作散布在程式中各處，并将它與映射、過濾器和累積器混在一起。如果我們能夠重新組織這一程式，使得信号流結構明顯表現在寫出的過程中，将會大大提高結果代碼的清晰性。

序列操作

要組織好這些程式，使之能夠更清晰地反映上面信号流的結構，最關鍵的一點就是将注意力集中在處理過程中從一個步驟流向下一個步驟的“信号”。如果我們用一些表來表示這些信号，那麼就可以利用表操作實作每一步驟的處理。舉例來說，我們可以用2.2.1節的map過程實作信号流圖中的映射步驟：

(map square (list 1 2 3 4 5))
(1 4 9 16 25)           

過濾一個序列，也就是選出其中滿足某個給定謂詞的元素，可以按下面方式做：

(define (filter predicate sequence)
  (cond ((null? sequence) nil)
        ((predicate (car sequence))
         (cons (car sequence)
               (filter predicate (cdr sequence))))
        (else (filter predicate (cdr sequence)))))           

例如，

(filter odd? (list 1 2 3 4 5))
(1 3 5)           

累積工作可以實作如下：

(define (accumulate op initial sequence)
  (if (null? sequence)
      initial
      (op (car sequence)
          (accumulate op initial (cdr sequence)))))
(accumulate + 0 (list 1 2 3 4 5))
15
(accumulate * 1 (list 1 2 3 4 5))
120
(accumulate cons nil (list 1 2 3 4 5))
(1 2 3 4 5)           

剩下的就是實作有關的信号流圖，枚舉出需要處理的資料序列。對于even-fibs，我們需要生成出一個給定區間裡的整數序列，這一序列可以如下做出：

(define (enumerate-interval low high)
  (if (> low high)
      nil
      (cons low (enumerate-interval (+ low 1) high))))
(enumerate-interval 2 7)
(2 3 4 5 6 7)           

要枚舉出一棵樹的所有樹葉，則可以用80：

(define (enumerate-tree tree)
  (cond ((null? tree) nil)
        ((not (pair? tree)) (list tree))
        (else (append (enumerate-tree (car tree))
                      (enumerate-tree (cdr tree))))))
(enumerate-tree (list 1 (list 2 (list 3 4)) 5))
(1 2 3 4 5)           

現在，我們就可以像上面的信号流圖那樣重新構造sum-odd-squares和even-fibs了。對于sum-odd-squares，我們需要枚舉一棵樹的樹葉序列，過濾它，隻留下序列中的奇數，求每個元素的平方，而後加起得到的結果：

(define (sum-odd-squares tree)
  (accumulate +
              0
              (map square
                   (filter odd?
                           (enumerate-tree tree)))))           

對于even-fibs，我們需要枚舉出從0到n的所有整數，對某個整數生成相應的斐波那契數，通過過濾隻留下其中的偶數，并将結果積累在一個表裡：

(define (even-fibs n)
  (accumulate cons
              nil
              (filter even?
                      (map fib
                           (enumerate-interval 0 n)))))           

将程式表示為一些針對序列的操作，這樣做的價值就在于能幫助我們得到子產品化的程式設計，也就是說，得到由一些比較獨立的片段的組合構成的設計。通過提供一個标準部件的庫，并使這些部件都有着一些能以各種靈活方式互相連接配接的約定界面，将能進一步推動人們去做子產品化的設計。

在工程設計中，子產品化結構是控制複雜性的一種威力強大的政策。舉例來說，在真實的信号處理應用中，設計者通常總是從标準化的過濾器和變換裝置族中選出一些東西，通過級聯的方式構造出各種系統。與此類似，序列操作也形成了一個可以混合和比對使用的标準的程式元素庫。例如，我們可以在另一個構造前n＋1個斐波那契數的平方的程式裡，使用取自過程sum-odd-squares和even-fibs的片段：

(define (list-fib-squares n)
  (accumulate cons
              nil
              (map square
                   (map fib
                        (enumerate-interval 0 n)))))
(list-fib-squares 10)
(0 1 1 4 9 25 64 169 441 1156 3025)           

我們也可以重新安排有關的各個片段，将它們用在産生一個序列中所有奇數的平方之乘積的計算裡：

(define (product-of-squares-of-odd-elements sequence)
  (accumulate *
              1
              (map square
                   (filter odd? sequence))))
(product-of-squares-of-odd-elements (list 1 2 3 4 5))
225           

我們同樣可以采用序列操作的方式，重新去形式化各種正常的資料處理應用。假定有一個人事記錄的序列，現在希望找出其中薪水最高的程式員的工資數額。假定現在有一個選擇函數salary傳回記錄中的工資數，另有謂詞programmer?檢查某個記錄是不是程式員，此時我們就可以寫：

(define (salary-of-highest-paid-programmer records)
  (accumulate max
              0
              (map salary
                   (filter programmer? records))))           

這些例子給了我們一些啟發，範圍廣大的許多操作都可以表述為序列操作。

在這裡，用表實作的序列被作為一種友善的界面，我們可以利用這種界面去組合起各種處理子產品。進一步說，如果以序列作為所用的統一表示結構，我們就能将程式對于資料結構的依賴性局限到不多的幾個序列操作上。通過修改這些操作，就可以在序列的不同表示之間轉換，并保持程式的整個設計不變。在3.5節裡還要繼續探索這方面的能力，那時将把序列處理的範型推廣到無窮序列。

練習2.33 請填充下面缺失的表達式，完成将一些基本的表操作看作累積的定義：

(define (map p sequence)
  (accumulate (lambda (x y) <??>) nil sequence))
(define (append seq1 seq2)
  (accumulate cons <??> <??>))
(define (length sequence)
  (accumulate <??> 0 sequence))           

練習2.34 對于x的某個給定值，求出一個多項式在x的值，也可以形式化為一種累積。假定需要求下面多項式的值：

anxn＋an－1xn－1＋…＋a1x＋a0           

采用著名的Horner規則，可以構造出下面的計算：

(… (anx＋an－1) x＋…＋a1) x＋a0           

換句話說，我們可以從an開始，乘以x，再加上an－1，乘以x，如此下去，直到處理完a0^82。請填充下面的模闆，做出一個利用Horner規則求多項式值的過程。假定多項式的系數安排在一個序列裡，從a0直至an。

(define (horner-eval x coefficient-sequence)
  (accumulate (lambda (this-coeff higher-terms) <??>)
              0
              coefficient-sequence))           

例如，為了計算1＋3x＋5x^3＋x^5在x＝2的值，你需要求值：

(horner-eval 2 (list 1 3 0 5 0 1))           

練習2.35 将2.2.2節的count-leaves重新定義為一個累積：

(define (count-leaves t)
  (accumulate <??> <??> (map <??> <??>)))           

練習2.36 過程accumulate-n與accumulate類似，除了它的第三個參數是一個序列的序列，假定其中每個序列的元素個數相同。它用指定的累積過程去組合起所有序列的第一個元素，而後是所有序列的第二個元素，并如此做下去，傳回得到的所有結果的序列。例如，如果s是包含着4個序列的序列（（1 2 3）（4 5 6）（7 8 9）（10 11 12）），那麼（accumulate-n＋0 s）的值就應該是序列（22 26 30）。請填充下面accumulate-n定義中所缺失的表達式：

(define (accumulate-n op init seqs)
  (if (null? (car seqs))
      nil
      (cons (accumulate op init <??>)
            (accumulate-n op init <??>))))           

練習2.37 假定我們将向量v＝(vi) 表示為數的序列，将矩陣m＝(mij) 表示為向量（矩陣行）的序列。例如，矩陣：

用序列（（1 2 3 4）（4 5 6 6）（6 7 8 9））表示。對于這種表示，我們可以用序列操作簡潔地表達基本的矩陣與向量運算。這些運算（任何有關矩陣代數的書裡都有描述）如下：

(dot-product v w)      傳回和穒viwi;
(matrix-*-vector m v)  傳回向量 t，其中ti＝穓mijvj;
(matrix-*-matrix m n)  傳回矩陣 p，其中pij＝穔miknkj;
(transpose m)          傳回矩陣 n，其中nij＝mji.           

我們可以将點積（dot product）定義為：

(define (dot-product v w)
  (accumulate + 0 (map * v w)))           

請填充下面過程裡缺失的表達式，它們計算出其他的矩陣運算結果（過程accumulate-n在練習2.36中定義）。

(define (matrix-*-vector m v)
  (map <??> m))
(define (transpose mat)
  (accumulate-n <??> <??> mat))
(define (matrix-*-matrix m n)
  (let ((cols (transpose n)))
    (map <??> m)))           

練習2.38 過程accumulate也稱為fold-right，因為它将序列的第一個元素組合到右邊所有元素的組合結果上。也有一個fold-left，它與fold-right類似，但卻是按照相反方向去操作各個元素：

(define (fold-left op initial sequence)
  (define (iter result rest)
    (if (null? rest)
        result
        (iter (op result (car rest))
              (cdr rest))))
  (iter initial sequence))           

下面表達式的值是什麼？

(fold-right / 1 (list 1 2 3))
(fold-left / 1 (list 1 2 3))
(fold-right list nil (list 1 2 3))
(fold-left list nil (list 1 2 3))           

如果要求用某個op時保證fold-right和fold-left對任何序列都産生同樣的結果，請給出op應該滿足的性質。

練習2.39 基于練習2.38的fold-right和fold-left完成reverse（練習2.18）下面的定義：

(define (reverse sequence)
  (fold-right (lambda (x y) <??>) nil sequence))
(define (reverse sequence)
  (fold-left (lambda (x y) <??>) nil sequence))           

嵌套映射

我們可以擴充序列範型，将許多通常用嵌套循環表述的計算也包含進來84。現在考慮下面的問題：給定了自然數n，找出所有不同的有序對i和j，其中1≤j＜i≤n，使得i＋j是素數。例如，假定n是6，滿足條件的序對就是：

完成這一計算的一種很自然的組織方式：首先生成出所有小于等于n的正自然數的有序對；而後通過過濾，得到那些和為素數的有序對；最後對每個通過了過濾的序對（i, j），産生出一個三元組（i, j, i＋j）。

這裡是生成有序對的序列的一種方式：對于每個整數i≤n，枚舉出所有的整數j＜i，并對每一對i和j生成序對（i, j）。用序列操作的方式說，我們要對序列（enumerate-interval 1 n）做一次映射。對于這個序列裡的每個i，我們都要對序列（enumerate-interval 1（- i 1））做映射。對于後一序列中的每個j，我們生成出序對（list i j）。這樣就對每個i得到了一個序對的序列。将針對所有i的序列組合到一起（用append累積起來），就能産生出所需的序對序列了。

(accumulate append
            nil
            (map (lambda (i)
                   (map (lambda (j) (list i j))
                        (enumerate-interval 1 (- i 1))))
                 (enumerate-interval 1 n)))           

由于在這類程式裡常要用到映射，并用append做累積，我們将它獨立出來定義為一個過程：

(define (flatmap proc seq)
  (accumulate append nil (map proc seq)))           

現在可以過濾這一序對的序列，找出那些和為素數的序對。對序列裡的每個元素調用過濾謂詞。由于這個謂詞的參數是一個序對，是以它必須将兩個整數從序對裡提取出來。這樣，作用到序列中每個元素上的謂詞就是：

(define (prime-sum? pair)
  (prime? (+ (car pair) (cadr pair))))           

最後還要生成出結果的序列，為此隻需将下面過程映射到通過過濾後的序對上，對每個有序對裡的兩個元素，這一過程生成出一個包含了它們的和的三元組：

(define (make-pair-sum pair)
  (list (car pair) (cadr pair) (+ (car pair) (cadr pair))))           

将所有這些組合到一起，就得到了完整的過程：

(define (prime-sum-pairs n)
  (map make-pair-sum
       (filter prime-sum?
               (flatmap
                (lambda (i)
                  (map (lambda (j) (list i j))
                       (enumerate-interval 1 (- i 1))))
                (enumerate-interval 1 n)))))           

嵌套的映射不僅能用于枚舉這種區間，也可用于其他序列。假設我們希望生成集合S的所有排列，也就是說，生成這一集合的元素的所有可能排序方式。例如，{1，2，3}的所有排列是{1，2，3}，{1，3，2}，{2，1，3}，{2，3，1}，{3，1，2}和{3，2，1}。這裡是生成S所有排列的序列的一種方案：對于S裡的每個x，遞歸地生成S－x的所有排列的序列86，而後将x加到每個序列的前面。這樣就能對S裡的每個x，産生出了S的所有以x開頭的排列。将對所有x的序列組合起來，就可以得到S的所有排列。

(define (permutations s)
  (if (null? s)                    ; empty set?
      (list nil)                   ; sequence containing empty set
      (flatmap (lambda (x)
                 (map (lambda (p) (cons x p))
                      (permutations (remove x s))))
               s)))           

請注意這裡所用的政策，看看它如何将生成S的所有排列的問題，歸結為生成元素少于S的集合的所有排列的問題。在終極情況中我們将達到空表，它表示沒有元素的集合。對此我們生成出的就是（list nil），這是一個隻包含一個元素的序列，其中是一個沒有元素的集合。在permutations過程中所用的remove過程傳回除指定項之外的所有元素，它可以簡單地用一個過濾器表示：

(define (remove item sequence)
  (filter (lambda (x) (not (= x item)))
          sequence))           

練習2.40 請定義過程unique-pairs，給它整數n，它産生出序對 (i, j)，其中1≤j＜i≤n。請用unique-pairs去簡化上面prime-sum-pairs的定義。

練習2.41 請寫出一個過程，它能産生出所有小于等于給定整數n的正的相異整數i、j和k的有序三元組，使每個三元組的三個元之和等于給定的整數s。

練習2.42 “八皇後謎題”問的是怎樣将八個皇後擺在國際象棋盤上，使得任意一個皇後都不能攻擊另一個皇後（也就是說，任意兩個皇後都不在同一行、同一列或者同一對角線上）。一個可能的解如圖2-8所示。解決這一謎題的一種方法按一個方向處理棋盤，每次在每一列裡放一個皇後。如果現在已經放好了k－1個皇後，第k個皇後就必須放在不會被已在棋盤上的任何皇後攻擊的位置上。我們可以遞歸地描述這一過程：假定我們已經生成了在棋盤的前k－1列中放置k－1個皇後的所有可能方式，現在需要的就是對于其中的每種方式，生成出将下一個皇後放在第k列中每一行的擴充集合。而後過濾它們，隻留下能使位于第k列的皇後與其他皇後相安無事的那些擴充。這樣就能産生出将k個皇後放置在前k列的所有格局的序列。繼續這一過程，我們将能産生出這一謎題的所有解，而不是一個解。

将這一解法實作為一個過程queens，令它傳回在n×n棋盤上放n個皇後的所有解的序列。queens内部的過程queen-cols，傳回在棋盤的前k列中放皇後的所有格局的序列。

(define (queens board-size)
  (define (queen-cols k)  
    (if (= k 0)
        (list empty-board)
        (filter
         (lambda (positions) (safe? k positions))
         (flatmap
          (lambda (rest-of-queens)
            (map (lambda (new-row)
                   (adjoin-position new-row k rest-of-queens))
                 (enumerate-interval 1 board-size)))
          (queen-cols (- k 1))))))
  (queen-cols board-size))           

這個過程裡的rest-of-queens是在前k－1列放置k－1個皇後的一種方式，new-row是在第k列放置所考慮的行編号。請完成這一程式，為此需要實作一種棋盤格局集合的表示方式；還要實作過程adjoin-position，它将一個新的行列格局加入一個格局集合；empty-board，它表示空的格局集合。你還需要寫出過程safe?，它能确定在一個格局中，在第k列的皇後相對于其他列的皇後是否為安全的（請注意，我們隻需檢查新皇後是否安全—其他皇後已經保證相安無事了）。

練習2.43 Louis Reasoner在做練習2.42時遇到了麻煩，他的queens過程看起來能行，但卻運作得極慢（Louis居然無法忍耐到它解出6×6棋盤的問題）。當Louis請Eva Lu Ator幫忙時，她指出他在flatmap裡交換了嵌套映射的順序，将它寫成了：

(flatmap
 (lambda (new-row)
   (map (lambda (rest-of-queens)
          (adjoin-position new-row k rest-of-queens))
        (queen-cols (- k 1))))
 (enumerate-interval 1 board-size))           

請解釋一下，為什麼這樣交換順序會使程式運作得非常慢。估計一下，用Louis的程式去解決八皇後問題大約需要多少時間，假定練習2.42中的程式需用時間T求解這一難題。

2.2.4 執行個體：一個圖形語言

本節将介紹一種用于畫圖形的簡單語言，以展示資料抽象和閉包的威力，其中也以一種非常本質的方式使用了高階過程。這一語言的設計就是為了很容易地做出一些模式，例如圖2-9中所示的那類圖形，它們是由某些元素的重複出現而構成的，這些元素可以變形或者改變大小。在這個語言裡，資料元素的組合都用過程表示，而不是用表結構表示。就像cons滿足一種閉包性質，使我們能構造出任意複雜的表結構一樣，這一語言中的操作也滿足閉包性質，使我們很容易構造出任意複雜的模式。

圖形語言

在1.1節裡開始研究程式設計時我們就強調說，在描述一種語言時，應該将注意力集中到語言的基本原語、它的組合手段以及它的抽象手段，這是最重要的。這裡的工作也将按照同樣的架構進行。

這一圖形語言的優美之處，部分就在于語言中隻有一種元素，稱為畫家（painter）。一個畫家将畫出一個圖像，這種圖像可以變形或者改變大小，以便能正好放到某個指定的平行四邊形架構裡。舉例來說，這裡有一個稱為wave的基本畫家，它能做出如圖2-10所示的折線畫，而所做出圖畫的實際形狀依賴于具體的架構—圖2-10裡的四個圖像都是由同一個畫家wave産生的，但卻是相對于四個不同的架構。有些畫家比它更精妙：稱為rogers的基本畫家能畫出MIT的創始人William Barton Rogers的畫像，如圖2-11所示89。圖2-11裡的四個圖像是相對于與圖2-10中wave形象同樣的四個架構畫出來的。

為了組合起有關的圖像，我們要用一些可以從給定畫家構造出新畫家的操作。例如，操作beside從兩個畫家出發，産生一個複合型畫家，它将第一個畫家的圖像畫在架構中左邊的一半裡，将第二個畫家的圖像畫在架構裡右邊一半裡。與此類似，below從兩個畫家出發産生一個組合型畫家，将第一個畫家的圖像畫在第二個畫家的圖像之下。有些操作将一個畫家轉換為另一個新畫家。例如，flip-vert從一個畫家出發，産生一個将該畫家所畫圖像上下颠倒畫出的畫家，而flip-horiz産生的畫家将原畫家的圖像左右反轉後畫出。

圖2-12說明了從wave出發，經過兩步做出一個名為wave4的畫家的方式：

(define wave2 (beside wave (flip-vert wave)))
(define wave4 (below wave2 wave2))           

在按這種方法構造複雜的圖像時，我們利用了一個事實：畫家在有關語言的組合方式下是封閉的：兩個畫家的beside或者below還是畫家，是以還可以用它們作為元素去構造更複雜的畫家。就像用cons構造起各種表結構一樣，我們所用的資料在組合方式下的閉包性質非常重要，因為這使我們能用不多幾個操作構造出各種複雜的結構。

一旦能做畫家的組合之後，我們就希望能抽象出典型的畫家組合模式，以便将這種組合操作實作為一些Scheme過程。這也意味着我們并不需要這種圖形語言裡包含任何特殊的抽象機制，因為組合的方式就是采用普通的Scheme過程。這樣，對于畫家，我們就自動有了能夠做原來可以對過程做的所有事情。例如，我們可以将wave4中的模式抽象出來：

(define (flipped-pairs painter)
  (let ((painter2 (beside painter (flip-vert painter))))
    (below painter2 painter2)))           

并将wave4重新定義為這種模式的執行個體：

(define wave4 (flipped-pairs wave))           

我們也可以定義遞歸操作。下面就是一個這樣的操作，它在圖形的右邊做分割和分支，就像在圖2-13和圖2-14中顯示的那樣：

(define (right-split painter n)
  (if (= n 0)
      painter
      (let ((smaller (right-split painter (- n 1))))
        (beside painter (below smaller smaller)))))           

通過同時在圖形中向上和向右分支，我們可以産生出一種平衡的模式（見練習2.44、圖2-13和圖2-14）：

(define (corner-split painter n)
  (if (= n 0)
      painter
      (let ((up (up-split painter (- n 1)))
            (right (right-split painter (- n 1))))
        (let ((top-left (beside up up))
              (bottom-right (below right right))
              (corner (corner-split painter (- n 1))))
          (beside (below painter top-left)
                  (below bottom-right corner))))))           

将某個corner-split的4個拷貝适當地組合起來，我們就可以得到一種稱為square-limit的模式，将它應用于wave和rogers的效果見圖2-9。

(define (square-limit painter n)
  (let ((quarter (corner-split painter n)))
    (let ((half (beside (flip-horiz quarter) quarter)))
      (below (flip-vert half) half))))           

練習2.44 請定義出corner-split裡使用的過程up-split，它與right-split類似，除在其中交換了below和beside的角色之外。

高階操作

除了可以獲得組合畫家的抽象模式之外，我們同樣可以在高階上工作，抽象出畫家的各種組合操作的模式。也就是說，可以把畫家操作看成是操控和描寫這些元素的組合方法的元素—寫出一些過程，它們以畫家操作作為參數，建立出各種新的畫家操作。

舉例來說，flipped-pairs和square-limit兩者都将一個畫家的四個拷貝安排在一個正方形的模式中，它們之間的差異僅僅在這些拷貝的旋轉角度。抽象出這種畫家組合模式的一種方式是定義下面的過程，它基于四個單參數的畫家操作，産生出一個畫家操作，這一操作裡将用這四個操作去變換一個給定的畫家，并将得到的結果放入一個正方形裡。tl、tr、bl和br分别是應用于左上角、右上角、左下角和右下角的四個拷貝的變換：

(define (square-of-four tl tr bl br)
  (lambda (painter)
    (let ((top (beside (tl painter) (tr painter)))
          (bottom (beside (bl painter) (br painter))))
      (below bottom top))))           

操作flipped-pairs可以基于square-of-four定義如下90：

(define (flipped-pairs painter)
  (let ((combine4 (square-of-four identity flip-vert
                                  identity flip-vert)))
    (combine4 painter)))           

而square-limit可以描述為：

(define (square-limit painter n)
  (let ((combine4 (square-of-four flip-horiz identity
                                  rotate180 flip-vert)))
    (combine4 (corner-split painter n))))           

練習2.45 可以将right-split和up-split表述為某種廣義劃分操作的執行個體。請定義一個過程split，使它具有如下性質，求值：

(define right-split (split beside below))
(define up-split (split below beside))           

産生能夠出過程right-split和up-split，其行為與前面定義的過程一樣。

架構

在我們進一步弄清楚如何實作畫家及其組合方式之前，還必須首先考慮架構的問題。一個架構可以用三個向量描述：一個基準向量和兩個角向量。基準向量描述的是架構基準點相對于平面上某個絕對基準點的偏移量，角向量描述了架構的角相對于架構基準點的偏移量。如果兩個角向量正交，這個架構就是一個矩形。否則它就是一個一般的平行四邊形。

圖2-15顯示的是一個架構和與之相關的三個向量。根據資料抽象原理，我們現在完全不必去說清楚架構的具體表示方式，而隻需要說明，存在着一個構造函數make-frame，它能從三個向量出發做出一個架構。與之對應的選擇函數是origin-frame、edge1-frame和edge2-frame（見練習2.47）。

我們将用機關正方形 (0≤x, y≤1) 裡的坐标去描述圖像。對于每個架構，我們要為它關聯一個架構坐标映射，借助它完成有關圖像的位移和伸縮，使之能夠适配于這個架構。這一映射的功能就是把機關正方形變換到相應架構，所采用的方法也就是将向量v＝(x, y) 映射到下面的向量和：

Origin (Frame)＋x·Edge1 (Frame)＋y·Edge2 (Frame)           

例如，點 (0, 0) 将被映射到給定架構的原點，(1, 1) 被映射到與原點對角的那個點，而（0.5, 0.5）被映射到給定架構的中心點。我們可以通過下面過程建立起架構的坐标映射：

(define (frame-coord-map frame)
  (lambda (v)
    (add-vect
     (origin-frame frame)
     (add-vect (scale-vect (xcor-vect v)
                           (edge1-frame frame))
               (scale-vect (ycor-vect v)
                           (edge2-frame frame))))))           

請注意看，這裡将frame-coord-map應用于一個架構的結果是傳回了一個過程，它對于每個給定的向量傳回另一個向量。如果參數向量位于機關正方形裡，得到的對應結果向量也将位于相應的架構裡。例如：

((frame-coord-map a-frame) (make-vect 0 0))           

傳回的向量如下：

(origin-frame a-frame)           

練習2.46 從原點出發的一個二維向量v可以用一個由x坐标和y坐标構成的序對表示。請為這樣的向量實作一個資料抽象：給出一個構造函數make-vect，以及對應的選擇函數xcor-vect和ycor-vect。借助于你給出的構造函數和選擇函數，實作過程add-vect、sub-vect和scale-vect，它們能完成向量加法、向量減法和向量的伸縮。

(x1，y1)＋(x2，y2)＝(x1＋x2，y1＋y2)
(x1，y1)－(x2，y2)＝(x1－x2，y1－y2)
                                                             s·(x，y)＝(sx，sy)           

練習2.47 下面是實作架構的兩個可能的過程函數：

(define (make-frame origin edge1 edge2)
  (list origin edge1 edge2))
(define (make-frame origin edge1 edge2)
  (cons origin (cons edge1 edge2)))           

請為每個構造函數提供适當的選擇函數，為架構做出相應的實作。

畫家

一個畫家被表示為一個過程，給了它一個架構作為實際參數，它就能通過适當的位移和伸縮，畫出一幅與這個架構比對的圖像。也就是說，如果p是一個畫家而f是一個架構，通過以f作為實際參數調用p，就能産生出f中p的圖像。

基本畫家的實作細節依賴于特定圖形系統的各種特性和被畫圖像的種類。例如，假定現在有了一個過程draw-line，它能在螢幕上兩個給定點之間畫出一條直線，那麼我們就可以利用它建立一個畫折線圖的畫家，例如從通過下面的線段表建立出圖2-10的wave畫家：

(define (segments->painter segment-list)
  (lambda (frame)
    (for-each
     (lambda (segment)
       (draw-line
        ((frame-coord-map frame) (start-segment segment))
        ((frame-coord-map frame) (end-segment segment))))
     segment-list)))           

這裡所給出的線段都用相對于機關正方形的坐标描述，對于表中的每個線段，這個畫家将根據架構坐标映射，對線段的各個端點做變換，而後在兩個端點之間畫一條直線。

将畫家表示為過程，就在這一圖形語言中豎立起一道強有力的抽象屏障。這就使我們可以建立和混用基于各種圖形能力的各種類型的基本畫家。任何過程隻要能取一個架構作為參數，畫出某些可以伸縮後适合這個架構的東西，它就可以作為一個畫家。

練習2.48 平面上的一條直線段可以用一對向量表示—從原點到線段起點的向量，以及從原點到線段終點的向量。請用你在練習2.46做出的向量表示定義一種線段表示，其中用構造函數make-segment以及選擇函數start-segment和end-segment。

練習2.49 利用segments->painter定義下面的基本畫家：

a) 畫出給定架構邊界的畫家。

b) 通過連接配接架構兩對角畫出一個大叉子的畫家。

c) 通過連接配接架構各邊的中點畫出一個菱形的畫家。

d) 畫家wave。

畫家的變換群組合

各種對畫家的操作（例如flip-vert或者beside）的功能就是建立另一個畫家，這其中涉及原來的畫家，還涉及根據參數架構派生出的某些架構。舉例來說，flip-vert在反轉畫家時完全不必知道它們究竟如何工作，它隻需知道怎樣将一個架構上下颠倒就足夠了。産生出的畫家使用的仍是原來的畫家，隻不過是讓它在一個颠倒的架構裡工作。

對于畫家的操作都基于一個過程transform-painter，它以一個畫家以及有關怎樣變換架構和生成畫家的資訊作為參數。對一個架構調用這樣的變換去産生畫家，實際完成的是對這個架構的一個變換，并基于變換後的架構去調用原來的畫家。transform-painter的參數是一些點（用向量表示），它們描述了新架構的各個角。在用于做架構變換時，第一個點描述的是新架構的原點，另外兩個點描述的是新架構的兩個邊向量的終點。這樣，位于機關正方形裡的參數描述的就是一個包含在原架構裡面的架構。

(define (transform-painter painter origin corner1 corner2)
  (lambda (frame)
    (let ((m (frame-coord-map frame)))
      (let ((new-origin (m origin)))
        (painter
         (make-frame new-origin
                     (sub-vect (m corner1) new-origin)
                     (sub-vect (m corner2) new-origin)))))))           

從下面可以看到如何給出反轉畫家的定義：

(define (flip-vert painter)
  (transform-painter painter
                     (make-vect 0.0 1.0)   ; new origin
                     (make-vect 1.0 1.0)   ; new end of edge1
                     (make-vect 0.0 0.0))) ; new end of edge2           

利用transform-painter很容易定義各種新的變換。例如，我們可以定義出一個畫家，它将自己的圖像收縮到給定架構右上的四分之一區域裡：

(define (shrink-to-upper-right painter)
  (transform-painter painter
                     (make-vect 0.5 0.5)
                     (make-vect 1.0 0.5)
                     (make-vect 0.5 1.0)))           

另一個變換将圖形按照逆時針方向旋轉90度：

(define (rotate90 painter)
  (transform-painter painter
                     (make-vect 1.0 0.0)
                     (make-vect 1.0 1.0)
                     (make-vect 0.0 0.0)))           

或者将圖像向中心收縮：

(define (squash-inwards painter)
  (transform-painter painter
                     (make-vect 0.0 0.0)
                     (make-vect 0.65 0.35)
                     (make-vect 0.35 0.65)))           

架構變換也是定義兩個或者更多畫家的組合的關鍵。例如，beside過程以兩個畫家為參數，分别将它們變換為在參數架構的左半邊和右半邊畫圖，這樣就産生出一個新的複合型畫家。當我們給了這一畫家一個架構後，它首先調用其變換後的第一個畫家在架構的左半邊畫圖，而後調用變換後的第二個畫家在架構的右半邊畫圖：

(define (beside painter1 painter2)
  (let ((split-point (make-vect 0.5 0.0)))
    (let ((paint-left
           (transform-painter painter1
                              (make-vect 0.0 0.0)
                              split-point
                              (make-vect 0.0 1.0)))
          (paint-right
           (transform-painter painter2
                              split-point
                              (make-vect 1.0 0.0)
                              (make-vect 0.5 1.0))))
      (lambda (frame)
        (paint-left frame)
        (paint-right frame)))))           

請特别注意，這裡的畫家資料抽象，特别是将畫家用過程表示，怎樣使beside的實作變得如此簡單。這裡的beside過程完全不必了解作為其成分的各個畫家的任何東西，它隻需知道這些畫家能夠在指定架構裡畫出一些東西就夠了。

練習2.50 請定義變換flip-horiz，它能在水準方向上反轉畫家。再定義出對畫家做反時針方向上180度和270度旋轉的變換。

練習2.51 定義對畫家的below操作，它以兩個畫家為參數。在給定了一個架構後，由below得到的畫家将要求第一個畫家在架構的下部畫圖，要求第二個畫家在架構的上部畫圖。請按兩種方式定義below：首先寫出一個類似于上面beside的過程；另一個則直接通過beside和适當的旋轉操作（來自練習2.50）完成有關工作。

強健設計的語言層次

在上述的圖形語言中，我們演習了前面介紹的有關過程和資料抽象的關鍵思想。其中的基本資料抽象和畫家都用過程表示實作，這就使該語言能以一種統一方式去處理各種本質上完全不同的畫圖能力。實作組合的方法也滿足閉包性質，使我們很容易構造起各種複雜的設計。最後，用于做過程抽象的所有工具，現在也都可用作組合畫家的抽象手段。

我們也對程式設計的另一個關鍵概念有了一點認識，這就是分層設計的問題。這一概念說的是，一個複雜的系統應該通過一系列的層次構造出來，為了描述這些層次，需要使用一系列的語言。構造各個層次的方式，就是設法組合起作為這一層次中部件的各種基本元素，而這樣構造出的部件又可以作為另一個層次裡的基本元素。在分層設計中，每個層次上所用的語言都提供了一些基本元素、組合手段，還有對該層次中的适當細節做抽象的手段。

在複雜系統的工程中廣泛使用這種分層設計方法。例如，在計算機工程裡，電阻和半導體被組合起來（用模拟電路的語言），産生出一些部件，例如與門、或門等等；這些門電路又被作為數字電路設計的語言中的基本元素97。将這類部件組合起來，構成了處理器、總線和存儲系統，随即，又通過它們的組合構造出各種計算機，此時采用的是适合于描述計算機體系結構的語言。計算機的組合可以進一步構成分布式系統，采用的是适合描述網絡互聯的語言。我們還可以這樣做下去。

作為分層設計的一個小例子，我們的圖形語言用了一些基本元素（基本畫家），它們是基于描述點和直線的語言建立起來，為segments->painter提供線段表，或者為rogers之類提供着色能力。前面關于這一圖形語言的描述，主要是集中在這些基本元素的組合方面，采用的是beside和below一類的幾何組合手段。我們也在更高的層次上工作，将beside和below作為基本元素，在一個具有square-of-four一類操作的語言中處理它們，這些操作抓住了一些将幾何組合手段組合起來的常見模式。

分層設計有助于使程式更加強健，也就是說，使我們更有可能在給定規範發生一些小改變時，隻需對程式做少量的修改。例如，假定我們希望改變圖2-9所示的基于wave的圖像，我們就可以在最低的層次上工作，直接去修改wave元素的表現細節；也可以在中間層次上工作，改變corner-split裡重複使用wave的方式；也可以在最高的層次上工作，改變對圖形中各個角上4個副本的安排。一般來說，分層結構中的每個層次都為表述系統的特征提供了一套獨特詞彙，以及一套修改這一系統的方式。

練習2.52 在上面描述的各個層次上工作，修改圖2-9中所示的方塊的限制。特别是：

a) 給練習2.49的基本wave畫家加入某些線段（例如，加上一個笑臉）。

b) 修改corner-split的構造模式（例如，隻用up-split和right-split的圖像的各一個副本，而不是兩個）。

c) 修改square-limit，換一種使用square-of-four的方式，以另一種不同模式組合起各個角區（例如，你可以讓大的Rogers先生從正方形的每個角向外看）。

2.3 符号資料

到目前為止，我們已經使用過的所有複合資料，最終都是從數值出發構造起來的。在這一節裡，我們要擴充所用語言的表述能力，引進将任意符号作為資料的功能。

2.3.1 引号

如果我們能構造出采用符号的複合資料，我們就可以有下面這類的表：

(a b c d)
(23 45 17)
((Norah 12) (Molly 9) (Anna 7) (Lauren 6) (Charlotte 4))           

這些包含着符号的表看起來就像是我們語言裡的表達式：

(* (+ 23 45) (+ x 9))
(define (fact n) (if (= n 1) 1 (* n (fact (- n 1)))))           

為了能夠操作這些符号，我們的語言裡就需要有一種新元素：為資料對象加引号的能力。假定我們希望構造出表（a b），當然不能用（list a b）完成這件事，因為這一表達式将要構造出的是a和b的值的表，而不是這兩個符号本身的表。在自然語言的環境中，這種情況也是衆所周知的，在那裡的單詞和句子可能看作語義實體，也可以看作是字元的序列（文法實體）。在自然語言裡，常見的方式就是用引号表明一個詞或者一個句子應作為文字看待，将它們直接作為字元的序列。例如說，“John”的第一個字母顯然是“J”。如果我們對某人說“大聲說你的名字”，此時希望聽到的是那個人的名字。如果說“大聲說‘你的名字’”，此時希望聽到的就是詞組“你的名字”。請注意，我們在這裡不得不用嵌套的引号去描述别人應該說的東西。

我們可以按照同樣的方式，将表和符号标記為應該作為資料對象看待，而不是作為應該求值的表達式。然而，這裡所用的引号形式與自然語言中的不同，我們隻在被引對象的前面放一個引号（按照習慣，在這裡用單引号）。在Scheme裡可以不寫結束引号，因為這裡已經靠空白和括号将對象分隔開，一個單引号的意義就是引用下一個對象。

現在我們就可以區分符号和它們的值了：

(define a 1)
(define b 2)
(list a b)
(1 2)
(list 'a 'b)
(a b)
(list 'a b)
(a 2)           

引号也可以用于複合對象，其中采用的是表的友善的輸出表示方式：

(car 'a b c))
a
(cdr 'a b c))
(b c)           

記住這些之後，我們就可以通過求值 '() 得到空表，這樣就可以丢掉變量nil了。

為了能對符号做各種操作，我們還需要用另一個基本過程eq?，這個過程以兩個符号作為參數，檢查它們是否為同樣的符号。利用eq?可以實作一個稱為memq的有用過程，它以一個符号和一個表為參數。如果這個符号不包含在這個表裡（也就是說，它與表裡的任何項目都不eq?），memq就傳回假；否則就傳回該表的由這個符号的第一次出現開始的那個子表：

(define (memq item x)
  (cond ((null? x) false)
        ((eq? item (car x)) x)
        (else (memq item (cdr x)))))           

舉例來說，表達式：

(memq 'apple '(pear banana prune))           

的值是假，而表達式：

(memq 'apple '(x (apple sauce) y apple pear))           

的值是（apple pear）。

練習2.53 解釋器在求值下面各個表達式時将列印出什麼？

(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 shoes blue socks))           

練習2.54** 如果兩個表包含着同樣元素，這些元素也按同樣順序排列，那麼就稱這兩個表equal?。例如：

(equal? '(this is a list) '(this is a list))

是真；而

(equal? '(this is a list) '(this (is a) list))

是假。說得更準确些，我們可以從符号相等的基本eq?出發，以遞歸方式定義出equal?。a和b是equal?的，如果它們都是符号，而且這兩個符号滿足eq?；或者它們都是表，而且（car a）和（car b）互相equal?，它們的（cdr a）和（cdr b）也是equal?。請利用這一思路定義出equal?過程。

練習2.55 Eva Lu Ator輸入了表達式：

(car ''abracadabra)           

令她吃驚的是解釋器列印出的是quote。請解釋這一情況。

2.3.2 執行個體：符号求導

為了闡釋符号操作的情況，并進一步闡釋資料抽象的思想，現在考慮設計一個執行代數表達式的符号求導的過程。我們希望該過程以一個代數表達式和一個變量作為參數，傳回這個表達式相對于該變量的導數。例如，如果送給這個過程的參數是ax2＋bx＋c和x，它應該傳回2ax＋b。符号求導數對于Lisp有着特殊的曆史意義，它正是推動人們去為符号操作開發計算機語言的重要執行個體之一。進一步說，它也是人們為符号數學工作開發強有力系統的研究領域的開端，今天已經有越來越多的應用數學家和實體學家們正在使用這類系統。

為了開發出一個符号計算程式，我們将按照2.1.1節開發有理數系統那樣，采用同樣的資料抽象政策。也就是說，首先定義一個求導算法，令它在一些抽象對象上操作，例如“和”、“乘積”和“變量”，并不考慮這些對象實際上如何表示，以後才去關心具體表示的問題。

對抽象資料的求導程式

為了使有關的讨論簡單化，我們在這裡考慮一個非常簡單的符号求導程式，它處理的表達式都是由對于兩個參數的加和乘運算構造起來的。對于這種表達式求導的工作可以通過下面幾條歸約規則完成：

可以看到，這裡的最後兩條規則具有遞歸的性質，也就是說，要想得到一個和式的導數，我們首先要找出其中各個項的導數，而後将它們相加。這裡的每個項又可能是需要進一步分解的表達式。通過這種分解，我們能得到越來越小的片段，最終将産生出常量或者變量，它們的導數就是0或者1。

為了能在一個過程中展現這些規則，我們用一下按願望思維，就像在前面設計有理數的實作時所做的那樣。如果現在有了一種表示代數表達式的方式，我們一定能判斷出某個表達式是否為一個和式、乘式、常量或者變量，也能提取出表達式裡的各個部分。對于一個和式（舉例來說），我們可能希望取得其被加項（第一個項）和加項（第二個項）。我們還需要能從幾個部分出發構造出整個表達式。讓我們假定現在已經有了一些過程，它們實作了下述的構造函數、選擇函數和謂詞：

(variable? e)     e是變量嗎？
(same-variable? v1 v2)     v1和v2是同一個變量嗎？
(sum? e)     e是和式嗎？
(addend e)     e的被加數
(augend e)     e的加數
(make-sum a1 a2)     構造起a1與a2的和式
(product? e)     e是乘式嗎？
(multiplier e)     e的被乘數
(multiplicand e)     e的乘數
(make-product m1 m2)     構造起m1與m2的乘式           

利用這些過程，以及判斷表達式是否數值的基本過程number?，我們就可以将各種求導規則用下面的過程表達出來了：

(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)))
        ((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裡包含了一個完整的求導算法。因為它是基于抽象資料表述的，是以，無論我們如何選擇代數表達式的具體表示，隻要設計了一組正确的選擇函數和構造函數，這個過程都可以工作。表示的問題是下面必須考慮的問題。

代數表達式的表示

我們可以設想出許多用表結構表示代數表達式的方法。例如，可以利用符号的表去直接反應代數的記法形式，将表達式ax＋b表示為表（a x ＋ b）。然而，一種特别直截了當的選擇，是采用Lisp裡面表示組合式的那種帶括号的字首形式，也就是說，将ax＋b表示為（＋ ( a x) b）。這樣，我們有關求導問題的資料表示就是：

• 變量就是符号，它們可以用基本謂詞symbol?判斷：

(define (variable? x) (symbol? x))           

• 兩個變量相同就是表示它們的符号互相eq?：

(define (same-variable? v1 v2)
  (and (variable? v1) (variable? v2) (eq? v1 v2)))           

• 和式與乘式都構造為表：

(define (make-sum a1 a2) (list ? a1 a2))
(define (make-product m1 m2) (list ? m1 m2))           

• 和式就是第一個元素為符号＋的表：

(define (sum? x)
  (and (pair? x) (eq? (car x) '()))           

• 被加數是表示和式的表裡的第二個元素：

(define (addend s) (cadr s))           

• 加數是表示和式的表裡的第三個元素：

(define (augend s) (caddr s))           

• 乘式就是第一個元素為符号 * 的表：

(define (product? x)
  (and (pair? x) (eq? (car x) '()))           

• 被乘數是表示乘式的表裡的第二個元素：

(define (multiplier p) (cadr p))           

• 乘數是表示乘式的表裡的第三個元素：

(define (multiplicand p) (caddr p))           

這樣，為了得到一個能夠工作的符号求導程式，我們隻需将這些過程與deriv裝在一起。現在讓我們看幾個表現這一程式的行為的執行個體：

(deriv '(+ x 3) 'x)
(+ 1 0)
(deriv '(* x y) 'x)
(+ (* x 0) (* 1 y))
(deriv '(* (* x y) (+ x 3)) 'x)
(+ (* (* x y) (+ 1 0))
   (* (+ (* x 0) (* 1 y))
      (+  x 3)))           

程式産生出的這些結果是對的，但是它們沒有經過化簡。我們确實有：

當然，我們也可能希望這一程式能夠知道x·0＝0，1·y＝y以及0＋y＝y。是以，第二個例子的結果就應該是簡單的y。正如上面的第三個例子所顯示的，當表達式變得更加複雜時，這一情況也可能變成嚴重的問題。

現在所面臨的困難很像我們在做有理數首先時所遇到的問題：希望将結果化簡到最簡單的形式。為了完成有理數的化簡，我們隻需要修改構造函數和選擇函數的實作。這裡也可以采取同樣的政策。我們在這裡也完全不必修改deriv，隻需要修改make-sum，使得當兩個求和對象都是數時，make-sum求出它們的和傳回。還有，如果其中的一個求和對象是0，那麼make-sum就直接傳回另一個對象。

(define (make-sum a1 a2)
  (cond ((=number? a1 0) a2)
        ((=number? a2 0) a1)
        ((and (number? a1) (number? a2)) (+ a1 a2))
        (else (list ? a1 a2))))           

在這個實作裡用到了過程＝number?，它檢查某個表達式是否等于一個給定的數。

(define (=number? exp num)
  (and (number? exp) (= exp num)))           

與此類似，我們也需要修改make-product，設法引進下面的規則：0與任何東西的乘積都是0，1與任何東西的乘積總是那個東西：

(define (make-product m1 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))))           

下面是這一新過程版本對前面三個例子的結果：

(deriv '(+ x 3) 'x)
1
(deriv '(* x y) 'x)
y
(deriv '(* (* x y) (+ x 3)) 'x)
(+ (* x y) (* y (+ x 3)))           

顯然情況已經大大改觀。但是，第三個例子還是說明，要想做出一個程式，使它能将表達式做成我們都能同意的“最簡單”形式，前面還有很長的路要走。代數化簡是一個非常複雜的問題，除了其他各種因素之外，還有另一個根本性的問題：對于某種用途的最簡形式，對于另一用途可能就不是最簡形式。

練習2.56 請說明如何擴充基本求導規則，以便能夠處理更多種類的表達式。例如，通過給程式deriv增加一個新子句，并以适當方式定義過程exponentiation?、base、exponent和make-exponentiation的方式，實作下述求導規則（你可以考慮用符号**表示乘幂）：

請将如下規則也構造到程式裡：任何東西的0次幂都是1，而它們的1次幂都是其自身。

練習2.57 請擴充求導程式，使之能處理任意項（兩項或者更多項）的和與乘積。這樣，上面的最後一個例子就可以表示為：

(deriv '(* x y (+ x 3)) 'x)           

設法通過隻修改和與乘積的表示，而完全不修改過程deriv的方式完成這一擴充。例如，讓一個和式的addend是它的第一項，而其augend是和式中的其餘項。

練習2.58 假定我們希望修改求導程式，使它能用于正常數學公式，其中＋和 * 采用的是中綴運算符而不是字首。由于求導程式是基于抽象資料定義的，要修改它，使之能用于另一種不同的表達式表示，我們隻需要換一套工作在新的、求導程式需要使用的代數表達式的表示形式上的謂詞、選擇函數和構造函數。

a) 請說明怎樣做出這些過程，以便完成在中綴表示形式（例如（x＋（3（x＋（y＋2）））））上的代數表達式求導。為了簡化有關的工作，現在可以假定＋和 總是取兩個參數，而且表達式中已經加上了所有的括号。

b) 如果允許标準的代數寫法，例如（x ＋ 3 *（x ＋ y ＋ 2）），問題就會變得更困難許多。在這種表達式裡可能不寫不必要的括号，并要假定乘法應該在加法之前完成。你還能為這種表示方式設計好适當的謂詞、選擇函數和構造函數，使我們的求導程式仍然能工作嗎？

2.3.3 執行個體：集合的表示

在前面的執行個體中，我們已經構造起兩類複合資料對象的表示：有理數和代數表達式。在這兩個執行個體中，我們都采用了某一種選擇，在構造時或者選擇成員時去簡化（約簡）有關的表示。除此之外，選擇用表的形式來表示這些結構都是直截了當的。現在我們要轉到集合的表示問題，此時，表示方式的選擇就不那麼顯然了。實際上，在這裡存在幾種選擇，而且它們互相之間在幾個方面存在明顯的不同。

非形式地說，一個集合就是一些不同對象的彙集。要給出一個更精确的定義，我們可以利用資料抽象的方法，也就是說，用一組可以作用于“集合”的操作來定義它們。這些操作是union-set，intersection-set，element-of-set? 和adjoin-set。其中element-of-set?是一個謂詞，用于确定某個給定元素是不是某個給定集合的成員。adjoin-set以一個對象和一個集合為參數，傳回一個集合，其中包含了原集合的所有元素，再加上剛剛加入進來的這個新元素。union-set計算出兩個集合的并集，這也是一個集合，其中包含了所有屬于兩個參數集合之一的元素。intersection-set計算出兩個集合的交集，它包含着同時出現在兩個參數集合中的那些元素。從資料抽象的觀點看，我們在設計有關的表示方面具有充分的自由，隻要在這種表示上實作的上述操作能以某種方式符合上面給出的解釋。

集合作為未排序的表

集合的一種表示方式是用其元素的表，其中任何元素的出現都不超過一次。這樣，空集就用空表來表示。對于這種表示形式，element-of-set?類似于2.3.1節的過程memq，但它應該用equal? 而不是eq?，以保證集合元素可以不是符号：

(define (element-of-set? x set)
  (cond ((null? set) false)
        ((equal? x (car set)) true)
        (else (element-of-set? x (cdr set)))))           

利用它就能寫出adjoin-set。如果要加入的對象已經在相應集合裡，那麼就傳回那個集合；否則就用cons将這一對象加入表示集合的表裡：

(define (adjoin-set x set)
  (if (element-of-set? x set)
      set
      (cons x set)))           

實作intersection-set時可以采用遞歸政策：如果我們已知如何做出set2與set1的cdr的交集，那麼就隻需要确定是否應将set1的car包含到結果之中了，而這依賴于（car set1）是否也在set2裡。下面是這樣寫出的過程：

(define (intersection-set set1 set2)
  (cond ((or (null? set1) (null? set2)) '())
        ((element-of-set? (car set1) set2)        
         (cons (car set1)
               (intersection-set (cdr set1) set2)))
        (else (intersection-set (cdr set1) set2))))           

在設計一種表示形式時，有一件必須關注的事情是效率問題。為考慮這一問題，就需要考慮上面定義的各集合操作所需要的工作步數。因為它們都使用了element-of-set?，這一操作的速度對整個集合的實作效率将有重大影響。在上面這個實作裡，為了檢查某個對象是否為一個集合的成員，element-of-set?可能不得不掃描整個集合（最壞情況是這一進制素恰好不在集合裡）。是以，如果集合有n個元素，element-of-set?就可能需要n步才能完成。這樣，這一操作所需的步數将以

的速度增長。adjoin-set使用了這個操作，是以它所需的步數也以

的速度增長。而對于intersection-set，它需要對set1的每個元素做一次element-of-set?檢查，是以所需步數将按所涉及的兩個集合的大小之乘積增長，或者說，在兩個集合大小都為n時就是

。union-set的情況也是如此。

練習2.59 請為采用未排序表的集合實作定義union-set操作。

練習2.60 我們前面說明了如何将集合表示為沒有重複元素的表。現在假定允許重複，例如，集合 {1，2，3} 可能被表示為表（2 3 2 1 3 2 2）。請為在這種表示上的操作設計過程element-of-set?、adjoin-set、union-set和intersection-set。與前面不重複表示裡的相應操作相比，現在各個操作的效率怎麼樣？在什麼樣的應用中你更傾向于使用這種表示，而不是前面那種無重複的表示？

集合作為排序的表

加速集合操作的一種方式是改變表示方式，使集合元素在表中按照上升序排列。為此，我們就需要有某種方式來比較兩個元素，以便确定哪個元素更大一些。例如，我們可以按字典序做符号的比較；或者同意采用某種方式為每個對象關聯一個唯一的數，在比較元素的時候就比較與之對應的數。為了簡化這裡的讨論，我們将僅僅考慮集合元素是數值的情況，這樣就可以用 > 和 < 做元素的比較了。下面将數的集合表示為元素按照上升順序排列的表。在前面第一種表示方式下，集合 {1，3，6，10} 的元素在相應的表裡可以任意排列，而在現在的新表示方式中，我們就隻允許用表（1 3 6 10）。

從操作element-of-set?可以看到采用有序表示的一個優勢：為了檢查一個項的存在性，現在就不必掃描整個表了。如果檢查中遇到的某個元素大于當時要找的東西，那麼就可以斷定這個東西根本不在表裡：

(define (element-of-set? x set)
  (cond ((null? set) false)
        ((= x (car set)) true)
        ((< x (car set)) false)
        (else (element-of-set? x (cdr set)))))           

這樣能節約多少步數呢？在最壞情況下，我們要找的項目可能是集合中的最大元素，此時所需步數與采用未排序的表示時一樣。但另一方面，如果需要查找許多不同大小的項，我們總可以期望，有些時候這一檢索可以在接近表開始處的某一點停止，也有些時候需要檢查表的一大部分。平均而言，我們可以期望需要檢查表中的一半元素，這樣，平均所需的步數就是大約n/2。這仍然是

的增長速度，但與前一實作相比，平均來說，現在我們節約了大約一半的步數（這一解釋并不合理，因為前面說未排序表需要檢查整個表，考慮的隻是一種特殊情況：查找沒有出現在表裡的元素。如果查找的是表裡存在的元素，即使采用未排序的表，平均查找長度也是表元素的一半。—譯者注）。

操作intersection-set的加速情況更使人印象深刻。在未排序的表示方式裡，這一操作需要

的步數，因為對set1的每個元素，我們都需要對set2做一次完全的掃描。對于排序表示則可以有一種更聰明的方法。我們在開始時比較兩個集合的起始元素，例如x1和x2。如果x1等于x2，那麼這樣就得到了交集的一個元素，而交集的其他元素就是這兩個集合的cdr的交集。如果此時的情況是x1小于x2，由于x2是集合set2的最小元素，我們立即可以斷定x1不會出現在集合set2裡的任何地方，是以它不應該在交集裡。這樣，兩集合的交集就等于集合set2與set1的cdr的交集。與此類似，如果x2小于x1，那麼兩集合的交集就等于集合set1與set2的cdr的交集。下面是按這種方式寫出的過程：

(define (intersection-set set1 set2)
  (if (or (null? set1) (null? set2))
      '()    
      (let ((x1 (car set1)) (x2 (car set2)))
        (cond ((= x1 x2)
               (cons x1
                     (intersection-set (cdr set1)
                                       (cdr set2))))
              ((< x1 x2)
               (intersection-set (cdr set1) set2))
              ((< x2 x1)
               (intersection-set set1 (cdr set2)))))))           

為了估計出這一過程所需的步數，請注意，在每個步驟中，我們都将求交集問題歸結到更小集合的交集計算問題—去掉了set1和set2之一或者是兩者的第一個元素。這樣，所需步數至多等于set1與set2的大小之和，而不像在未排序表示中它們的乘積。這也就是

的增長速度，而不是

—這一加速非常明顯，即使對中等大小的集合也是如此。

練習2.61 請給出采用排序表示時adjoin-set的實作。通過類似element-of-set?的方式說明，可以如何利用排序的優勢得到一個過程，其平均所需的步數是采用未排序表示時的一半。

練習2.62 請給出在集合的排序表示上union-set的一個

實作。

集合作為二叉樹

如果将集合元素安排成一棵樹的形式，我們還可以得到比排序表表示更好的結果。樹中每個結點儲存集合中的一個元素，稱為該結點的“資料項”，它還連結到另外的兩個結點（可能為空）。其中“左邊”的連結所指向的所有元素均小于本結點的元素，而“右邊”連結到的元素都大于本結點裡的元素。圖2-16顯示的是一棵表示集合的樹。同一個集合表示為樹可以有多種不同的方式，我們對一個合法表示的要求就是，位于左子樹裡的所有元素都小于本結點裡的資料項，而位于右子樹裡的所有元素都大于它。

樹表示方法的優點在于：假定我們希望檢查某個數x是否在一個集合裡，那麼就可以用x與樹頂結點的資料項相比較。如果x小于它，我們就知道現在隻需要搜尋左子樹；如果x比較大，那麼就隻需搜尋右子樹。在這樣做時，如果該樹是“平衡的”，也就是說，每棵子樹大約是整個樹的一半大，那麼，這樣經過一步，我們就将需要搜尋規模為n的樹的問題，歸約為搜尋規模為n/2的樹的問題。由于經過每個步驟能夠使樹的大小減小一半，我們可以期望搜尋規模為n的樹的計算步數以Q(log n) 速度增長10。在集合很大時，相對于原來的表示，現在的操作速度将明顯快得多。

我們可以用表來表示樹，将結點表示為三個元素的表：本結點中的資料項，其左子樹和右子樹。以空表作為左子樹或者右子樹，就表示沒有子樹連接配接在那裡。我們可以用下面過程描述這種表示：

(define (entry tree) (car tree))
(define (left-branch tree) (cadr tree))
(define (right-branch tree) (caddr tree))
(define (make-tree entry left right)
  (list entry left right))           

現在，我們就可以采用上面描述的方式實作過程element-of-set?了：

(define (element-of-set? x set)
  (cond ((null? set) false)
        ((= x (entry set)) true)
        ((< x (entry set))
         (element-of-set? x (left-branch set)))
        ((> x (entry set))
         (element-of-set? x (right-branch set)))))           

向集合裡加入一個項的實作方式與此類似，也需要Q(log n) 步數。為了加入元素x，我們需要将x與結點資料項比較，以便确定x應該加入右子樹還是左子樹中。在将x加入适當的分支之後，我們将新構造出的這個分支、原來的資料項與另一分支放到一起。如果x等于這個資料項，那麼就直接傳回這個結點。如果需要将x加入一個空子樹，那麼我們就生成一棵樹，以x作為資料項，并讓它具有空的左右分支。下面是這個過程：

(define (adjoin-set x set)
  (cond ((null? set) (make-tree x '() '()))
        ((= x (entry set)) set)
        ((< x (entry set))
         (make-tree (entry set) 
                    (adjoin-set x (left-branch set))
                    (right-branch set)))
        ((> x (entry set))
         (make-tree (entry set)
                    (left-branch set)
                    (adjoin-set x (right-branch set))))))           

我們在上面斷言，搜尋樹的操作可以在對數步數中完成，這實際上依賴于樹“平衡”的假設，也就是說，每個樹的左右子樹中的結點大緻上一樣多，是以每棵子樹中包含的結點大約就是其父的一半。但是我們怎麼才能確定構造出的樹是平衡的呢？即使是從一棵平衡的樹開始工作，采用adjoin-set加入元素也可能産生出不平衡的結果。因為新加入元素的位置依賴于它與當時已經在樹中的那些項比較的情況。我們可以期望，如果“随機地”将元素加入樹中，平均而言将會使樹趨于平衡。但在這裡并沒有任何保證。例如，如果我們從空集出發，順序将數值1至7加入其中，我們就會得到如圖2-17所示的高度不平衡的樹。在這個樹裡，所有的左子樹都為空，是以它與簡單排序表相比一點優勢也沒有。解決這個問題的一種方式是定義一個操作，它可以将任意的樹變換為一棵具有同樣元素的平衡樹。在每執行過幾次adjoin-set操作之後，我們就可以通過執行它來保持樹的平衡。當然，解決這一問題的方法還有許多，大部分這類方法都涉及設計一種新的資料結構，設法使這種資料結構上的搜尋和插入操作都能夠在Q(log n) 步數内完成。

練習2.63 下面兩個過程都能将樹變換為表：

(define (tree->list-1 tree)
  (if (null? tree)
      '()
      (append (tree->list-1 (left-branch tree))
              (cons (entry tree)
                    (tree->list-1 (right-branch tree))))))
(define (tree->list-2 tree)
  (define (copy-to-list tree result-list)
    (if (null? tree)
        result-list
        (copy-to-list (left-branch tree)
                      (cons (entry tree)
                            (copy-to-list (right-branch tree)
                                          result-list)))))
  (copy-to-list tree '()))           

a) 這兩個過程對所有的樹都産生同樣結果嗎？如果不是，它們産生出的結果有什麼不同？它們對圖2-16中的那些樹産生什麼樣的表？

b) 将n個結點的平衡樹變換為表時，這兩個過程所需的步數具有同樣量級的增長速度嗎？如果不一樣，哪個過程增長得慢一些？

練習2.64 下面過程list->tree将一個有序表變換為一棵平衡二叉樹。其中的輔助函數partial-tree以整數n和一個至少包含n個元素的表為參數，構造出一棵包含這個表的前n個元素的平衡樹。由partial-tree傳回的結果是一個序對（用cons構造），其car是構造出的樹，其cdr是沒有包含在樹中那些元素的表。

(define (list->tree elements)
  (car (partial-tree elements (length elements))))
(define (partial-tree elts n)
  (if (= n 0)
      (cons '() elts)
      (let ((left-size (quotient (- n 1) 2)))
        (let ((left-result (partial-tree elts left-size)))
          (let ((left-tree (car left-result))
                (non-left-elts (cdr left-result))
                (right-size (- n (+ left-size 1))))
            (let ((this-entry (car non-left-elts))
                  (right-result (partial-tree (cdr non-left-elts)
                                              right-size)))
              (let ((right-tree (car right-result))
                    (remaining-elts (cdr right-result)))
                (cons (make-tree this-entry left-tree right-tree)
                      remaining-elts))))))))           

a) 請簡要地并盡可能清楚地解釋為什麼partial-tree能完成工作。請畫出将list->tree用于表（1 3 5 7 9 11）産生出的樹。

b) 過程list->tree轉換n個元素的表所需的步數以什麼量級增長？

練習2.65 利用練習2.63和練習2.64的結果，給出對采用（平衡）二叉樹方式實作的集合的union-set和intersection-set操作的

集合與資訊檢索

我們考察了用表表示集合的各種選擇，并看到了資料對象表示的選擇可能如何深刻地影響到使用資料的程式的性能。關注集合的另一個原因是，這裡所讨論的技術在涉及資訊檢索的各種應用中将會一次又一次地出現。

現在考慮一個包含大量獨立記錄的資料庫，例如一個企業中的人事檔案，或者一個會計系統裡的交易記錄。典型的資料管理系統都需将大量時間用在通路和修改所存的資料上，是以就需要通路記錄的高效方法。完成此事的一種方式是将每個記錄中的一部分當作辨別key（鍵值）。所用鍵值可以是任何能唯一辨別記錄的東西。對于人事檔案而言，它可能是雇員的ID編碼。對于會計系統而言，它可能是交易的編号。在确定了采用什麼鍵值之後，就可以将記錄定義為一種資料結構，并包含key選擇過程，它可以從給定記錄中提取出有關的鍵值。

現在就可以将這個資料庫表示為一個記錄的集合。為了根據給定鍵值确定相關記錄的位置，我們用一個過程lookup，它以一個鍵值和一個資料庫為參數，傳回具有這個鍵值的記錄，或者在找不到相應記錄時報告失敗。lookup的實作方式幾乎與element-of-set?一模一樣，如果記錄的集合被表示為未排序的表，我們就可以用：

(define (lookup given-key set-of-records)
  (cond ((null? set-of-records) false)
        ((equal? given-key (key (car set-of-records)))
         (car set-of-records))
        (else (lookup given-key (cdr set-of-records)))))           

不言而喻，還有比未排序表更好的表示大集合的方法。常常需要“随機通路”其中記錄的資訊檢索系統通常用某種基于樹的方法實作，例如用前面讨論過的二叉樹。在設計這種系統時，資料抽象的方法學将很有幫助。設計師可以建立某種簡單而直接的初始實作，例如采用未排序的表。對于最終系統而言，這種做法顯然并不合适，但采用這種方式提供一個“一揮而就”的資料庫，對用于測試系統的其他部分則可能很有幫助。然後可以将資料表示修改得更加精細。如果對資料庫的通路都是基于抽象的選擇函數和構造函數，這種表示的改變就不會要求對系統其餘部分做任何修改。

練習2.66 假設記錄的集合采用二叉樹實作，按照其中作為鍵值的數值排序。請實作相應的lookup過程。

2.3.4 執行個體：Huffman編碼樹

本節将給出一個實際使用表結構和資料抽象去操作集合與樹的例子。這一應用是想确定一些用0和1（二進制位）的序清單示資料的方法。舉例說，用于在計算機裡表示文本的ASCII标準編碼将每個字元表示為一個包含7個二進制位的序列，采用7個二進制位能夠區分27種不同情況，即128個可能不同的字元。一般而言，如果我們需要區分n個不同字元，那麼就需要為每個字元使用log2 n個二進制位。假設我們的所有資訊都是用A、B、C、D、E、F、G和H這樣8個字元構成的，那麼就可以選擇每個字元用3個二進制位，例如：

A 000     C 010     E 100     G 110
B 001     D 011     F 101     H 111           

采用這種編碼方式，消息：

BACADAEAFABBAAAGAH

将編碼為54個二進制位

001000010000011000100000101000001001000000000110000111

像ASCII碼和上面A到H編碼這樣的編碼方式稱為定長編碼，因為它們采用同樣數目的二進制位表示消息中的每一個字元。變長編碼方式就是用不同數目的二進制位表示不同的字元，這種方式有時也可能有些優勢。舉例說，莫爾斯電報碼對于字母表中各個字母就沒有采用同樣數目的點和劃，特别是最常見的字母E隻用一個點表示。一般而言，如果在我們的消息裡，某些符号出現得很頻繁，而另一些卻很少見，那麼如果為這些頻繁出現的字元指定較短的碼字，我們就可能更有效地完成資料的編碼（對于同樣消息使用更少的二進制位）。請考慮下面對于字母A到H的另一種編碼：

A 0     C 1010     E 1100     G 1110
B 100     D 1011     F 1101     H 1111           

采用這種編碼方式，上面的同樣資訊将編碼為如下的串：

100010100101101100011010100100000111001111

這個串中隻包含42個二進制位，也就是說，與上面定長編碼相比，現在的這種方式節約了超過20%的空間。

采用變長編碼有一個困難，那就是在讀0/1序列的過程中确定何時到達了一個字元的結束。莫爾斯碼解決這一問題的方式是在每個字母的點劃序列之後用一個特殊的分隔符（它用的是一個間歇）。另一種解決方式是以某種方式設計編碼，使得其中每個字元的完整編碼都不是另一字元編碼的開始一段（或稱字首）。這樣的編碼稱為字首碼。在上面例子裡，A編碼為0而B編碼為100，沒有其他字元的編碼由0或者100開始。

一般而言，如果能夠通過變長字首碼去利用被編碼消息中符号出現的相對頻度，那麼就能明顯地節約空間。完成這件事情的一種特定方式稱為Huffman編碼，這個名稱取自其發明人David Huffman。一個Huffman編碼可以表示為一棵二叉樹，其中的樹葉是被編碼的符号。樹中每個非葉結點代表一個集合，其中包含了這一結點之下的所有樹葉上的符号。除此之外，位于樹葉的每個符号還被賦予一個權重（也就是它的相對頻度），非葉結點所包含的權重是位于它之下的所有葉結點的權重之和。這種權重在編碼和解碼中并不使用。下面将會看到，在構造樹的過程中需要它們的幫助。

圖2-18顯示的是上面給出的A到H編碼所對應的Huffman編碼樹，樹葉上的權重表明，這棵樹的設計所針對的消息是，字母A具有相對權重8，B具有相對權重3，其餘字母的相對權重都是1。

給定了一棵Huffman樹，要找出任一符号的編碼，我們隻需從樹根開始向下運動，直到到達了儲存着這一符号的樹葉為止，在每次向左行時就給代碼加上一個0，右行時加上一個1。在确定向哪一分支運動時，需要檢查該分支是否包含着與這一符号對應的葉結點，或者其集合中包含着這個符号。舉例說，從圖2-18中樹的根開始，到達D的葉結點的方式是走一個右分支，而後一個左分支，而後是右分支，而後又是右分支，是以其代碼為1011。

在用Huffman樹做一個序列的解碼時，我們也從樹根開始，通過位序列中的0或1确定是移向左分支還是右分支。每當我們到達一個葉結點時，就生成出了消息中的一個符号。此時就重新從樹根開始去确定下一個符号。例如，如果給我們的是上面的樹和序列10001010。從樹根開始，我們移向右分支（因為串中第一個位是1），而後向左分支（因為第二個位是0），而後再向左分支（因為第三個位也是0）。這時已經到達B的葉，是以被解碼消息中的第一個符号是B。現在再次從根開始，因為序列中下一個位是0，這就導緻一次向左分支的移動，使我們到達A的葉。然後我們再次從根開始處理剩下的串1010，經過右左右左移動後到達了C。這樣，整個消息也就是BAC。

生成Huffman樹

給定了符号的“字母表”和它們的相對頻度，我們怎麼才能構造出“最好的”編碼呢？換句話說，哪樣的樹能使消息編碼的位數達到最少？Huffman給出了完成這件事的一個算法，并且證明了，對于符号所出現的相對頻度與構造樹的消息相符的消息而言，這樣産生出的編碼确實是最好的變長編碼。我們并不打算在這裡證明Huffman編碼的最優性質，但将展示如何去構造Huffman樹。

生成Huffman樹的算法實際上十分簡單，其想法就是設法安排這棵樹，使得那些帶有最低頻度的符号出現在離樹根最遠的地方。這一構造過程從葉結點的集合開始，這種結點中包含各個符号和它們的頻度，這就是開始構造編碼的初始資料。現在要找出兩個具有最低權重的葉，并歸并它們，産生出一個以這兩個結點為左右分支的結點。新結點的權重就是那兩個結點的權重之和。現在我們從原來集合裡删除前面的兩個葉結點，并用這一新結點代替它們。随後繼續這一過程，在其中的每一步都歸并兩個具有最小權重的結點，将它們從集合中删除，并用一個以這兩個結點作為左右分支的新結點取而代之。當集合中隻剩下一個結點時，這一過程終止，而這個結點就是樹根。下面顯示的是圖2-18中的Huffman樹的生成過程：

初始樹葉    {(A 8) (B 3) (C 1) (D 1) (E 1) (F 1) (G 1) (H 1)}
歸并    {(A 8) (B 3) ({C D} 2) (E 1) (F 1) (G 1) (H 1)}
歸并    {(A 8) (B 3) ({C D} 2) ({E F} 2) (G 1) (H 1)}
歸并    {(A 8) (B 3) ({C D} 2) ({E F} 2) ({G H} 2)}
歸并    {(A 8) (B 3) ({C D} 2) ({E F G H} 4)}
歸并    {(A 8) ({B C D} 5) ({E F G H} 4)}
歸并    {(A 8) ({B C D E F G H} 9)}
最後歸并    {({A B C D E F G H} 17)}           

這一算法并不總能描述一棵唯一的樹，這是因為，每步選擇出的最小權重結點有可能不唯一。還有，在做歸并時，兩個結點的順序也是任意的，也就是說，随便哪個都可以作為左分支或者右分支。

Huffman樹的表示

在下面的練習中，我們将要做出一個使用Huffman樹完成消息編碼和解碼，并能根據上面給出的梗概生成Huffman樹的系統。開始還是讨論這種樹的表示。

将一棵樹的樹葉表示為包含符号leaf、葉中符号和權重的表：

(define (make-leaf symbol weight)
  (list 'leaf symbol weight))
(define (leaf? object)
  (eq? (car object) 'leaf))
(define (symbol-leaf x) (cadr x))
(define (weight-leaf x) (caddr x))           

一棵一般的樹也是一個表，其中包含一個左分支、一個右分支、一個符号集合和一個權重。符号集合就是符号的表，這裡沒有用更複雜的集合表示。在歸并兩個結點做出一棵樹時，樹的權重也就是這兩個結點的權重之和，其符号集就是兩個結點的符号集的并集。因為這裡的符号集用表來表示，通過2.2.1節的append過程就可以得到它們的并集：

(define (make-code-tree left right)
  (list left
        right
        (append (symbols left) (symbols right))
        (+ (weight left) (weight right))))           

如果以這種方式構造，我們就需要采用下面的選擇函數：

(define (left-branch tree) (car tree))
(define (right-branch tree) (cadr tree))
(define (symbols tree)
  (if (leaf? tree)
      (list (symbol-leaf tree))
      (caddr tree)))
(define (weight tree)
  (if (leaf? tree)
      (weight-leaf tree)
      (cadddr tree)))           

在對樹葉或者一般樹調用過程symbols和weight時，它們需要做的事情有一點不同。這些不過是通用型過程（可以處理多于一種資料的過程）的簡單執行個體，有關這方面的情況，在2.4節和2.5節将有很多讨論。

解碼過程

下面的過程實作解碼算法，它以一個0/1的表和一棵Huffman樹為參數：

(define (decode bits tree)
  (define (decode-1 bits current-branch)
    (if (null? bits)
        '()
        (let ((next-branch
               (choose-branch (car bits) current-branch)))
          (if (leaf? next-branch)
              (cons (symbol-leaf next-branch)
                    (decode-1 (cdr bits) tree))
              (decode-1 (cdr bits) next-branch)))))
  (decode-1 bits tree))
(define (choose-branch bit branch)
  (cond ((= bit 0) (left-branch branch))
        ((= bit 1) (right-branch branch))
        (else (error "bad bit -- CHOOSE-BRANCH" bit))))           

過程decode-1有兩個參數，其中之一是包含二進制位的表，另一個是樹中的目前位置。它不斷在樹裡“向下”移動，根據表中下一個位是0或者1選擇樹的左分支或者右分支（這一工作由過程choose-branch完成）。一旦到達了葉結點，它就把位于這裡的符号作為消息中的下一個符号，将其cons到對于消息裡随後部分的解碼結果之前。而後這一解碼又從樹根重新開始。請注意choose-branch裡最後一個子句的錯誤檢查，如果過程遇到了不是0/1的東西時就會報告錯誤。

帶權重元素的集合

在樹表示裡，每個非葉結點包含着一個符号集合，在這裡表示為一個簡單的表。然而，上面讨論的樹生成算法要求我們也能對樹葉和樹的集合工作，以便不斷地歸并一對一對的最小項。因為在這裡需要反複去确定集合裡的最小項，采用某種有序的集合表示會比較友善。

我們準備将樹葉和樹的集合表示為一批元素的表，按照權重的上升順序排清單中的元素。下面用于構造集合的過程adjoin-set與練習2.61中描述的過程類似，但這裡比較的是元素的權重，而且加入集合的新元素原來絕不會出現在這個集合裡。

(define (adjoin-set x set)
  (cond ((null? set) (list x))
        ((< (weight x) (weight (car set))) (cons x set))
        (else (cons (car set)
                    (adjoin-set x (cdr set))))))           

下面過程以一個符号-權重對偶的表為參數，例如（（A 4）（B 2）（C 1）（D 1）），它構造出樹葉的初始排序集合，以便Huffman算法能夠去做歸并：

(define (make-leaf-set pairs)
  (if (null? pairs)
      '()
      (let ((pair (car pairs)))
        (adjoin-set (make-leaf (car pair)    ; symbol
                               (cadr pair))  ; frequency
                    (make-leaf-set (cdr pairs))))))           

練習2.67 請定義一棵編碼樹和一個樣例消息：

(define sample-tree
  (make-code-tree (make-leaf 誂 4)
                  (make-code-tree
                   (make-leaf 誃 2)
                   (make-code-tree (make-leaf 誅 1)
                                   (make-leaf 誄 1)))))
(define sample-message ?0 1 1 0 0 1 0 1 0 1 1 1 0))           

然後用過程decode完成該消息的編碼，給出編碼的結果。

練習2.68 過程encode以一個消息和一棵樹為參數，産生出被編碼消息所對應的二進制位的表：

(define (encode message tree)
  (if (null? message)
      '()
      (append (encode-symbol (car message) tree)
              (encode (cdr message) tree))))           

其中的encode-symbol是需要你寫出的過程，它能根據給定的樹産生出給定符号的二進制位表。你所設計的encode-symbol在遇到未出現在樹中的符号時應報告錯誤。請用在練習2.67中得到的結果檢查所實作的過程，工作中用同樣一棵樹，看看得到的結果是不是原來那個消息。

練習2.69 下面過程以一個符号-頻度對偶表為參數（其中沒有任何符号出現在多于一個對偶中），并根據Huffman算法生成出Huffman編碼樹。

(define (generate-huffman-tree pairs)
  (successive-merge (make-leaf-set pairs)))           

其中的make-leaf-set是前面給出的過程，它将對偶表變換為葉的有序集，successive-merge是需要你寫的過程，它使用make-code-tree反複歸并集合中具有最小權重的元素，直至集合裡隻剩下一個元素為止。這個元素就是我們所需要的Huffman樹。（這一過程稍微有點技巧性，但并不很複雜。如果你正在設計的過程變得很複雜，那麼幾乎可以肯定是在什麼地方搞錯了。你應該盡可能地利用有序集合表示這一事實。）

練習2.70 下面帶有相對頻度的8個符号的字母表，是為了有效編碼20世紀50年代的搖滾歌曲中的詞語而設計的。（請注意，“字母表”中的“符号”不必是單個字母。）

A     2     NA     16
BOOM     1     SHA     3
GET     2     YIP     9
JOB     2     WAH     1           

請用（練習2.69的）generate-huffman-tree過程生成對應的Huffman樹，用（練習2.68的）encode過程編碼下面的消息：

Get a job
Sha na na na na na na na na 
Get a job 
Sha na na na na na na na na 
Wah yip yip yip yip yip yip yip yip yip 
Sha boom           

這一編碼需要多少個二進制位？如果對這8個符号的字母表采用定長編碼，完成這個歌曲的編碼最少需要多少個二進制位？

練習2.71 假定我們有一棵n個符号的字母表的Huffman樹，其中各符号的相對頻度分别是1，2，4，…，2n－1。請對n＝5和n＝10勾勒出有關的樹的樣子。對于這樣的樹（對于一般的n），編碼出現最頻繁的符号用多少個二進制位？最不頻繁的符号呢？

練習2.72 考慮你在練習2.68中設計的編碼過程。對于一個符号的編碼，計算步數的增長速率是什麼？請注意，這時需要把在每個結點中檢查符号表所需的步數包括在内。一般性地回答這一問題是非常困難的。現在考慮一類特殊情況，其中的n個符号的相對頻度如練習2.71所描述的。請給出編碼最頻繁的符号所需的步數和最不頻繁的符号所需的步數的增長速度（作為n的函數）。

2.4 抽象資料的多重表示

我們已經介紹過資料抽象，這是一種構造系統的方法學，采用這種方法，将使一個程式中的大部分描述能與這一程式所操作的資料對象的具體表示的選擇無關。舉例來說，在2.1.1節裡，我們看到如何将一個使用有理數的程式的設計與有理數的實作工作互相分離，具體實作中采用的是計算機語言所提供的構造複合資料的基本機制。這裡的關鍵性思想就是構築起一道抽象屏障—對于上面情況，也就是有理數的選擇函數和構造函數（make-rat，numer，denom）—它能将有理數的使用方式與其借助于表結構的具體表示形式隔離開。與此類似的抽象屏障，也把執行有理數算術的過程（add-rat，sub-rat，mul-rat和div-rat）與使用有理數的“高層”過程隔離開。這樣做出的程式所具有的結構如圖2-1所示。

資料抽象屏障是控制複雜性的強有力工具。通過對資料對象基礎表示的屏蔽，我們就可以将設計一個大程式的任務，分割為一組可以分别處理的較小任務。但是，這種類型的資料抽象還不夠強大有力，因為在這裡說資料對象的“基礎表示”并不一定總有意義。

從一個角度看，對于一個資料對象也可能存在多種有用的表示方式，而且我們也可能希望所設計的系統能處理多種表示形式。舉一個簡單的例子，複數就可以表示為兩種幾乎等價的形式：直角坐标形式（實部和虛部）和極坐标形式（模和幅角）。有時采用直角坐标形式更合适，有時極坐标形式更友善。的确，我們完全可能設想一個系統，其中的複數同時采用了兩種表示形式，而其中的過程可以對具有任意表示形式的複數工作。

更重要的是，一個系統的程式設計常常是由許多人通過一個相當長時期的工作完成的，系統的需求也在随着時間而不斷變化。在這樣一種環境裡，要求每個人都在資料表示的選擇上達成一緻是根本就不可能的事情。是以，除了需要将表示與使用相隔離的資料抽象屏障之外，我們還需要有抽象屏障去隔離互不相同的設計選擇，以便允許不同的設計選擇在同一個程式裡共存。進一步說，由于大型程式常常是通過組合起一些現存子產品構造起來的，而這些模闆又是獨立設計的，我們也需要一些方法，使程式員可能逐漸地将許多子產品結合成一個大型系統，而不必去重新設計或者重新實作這些子產品。

在這一節裡，我們将學習如何去處理資料，使它們可能在一個程式的不同部分中采用不同的表示方式。這就需要我們去構造通用型過程—也就是那種可以在不止一種資料表示上操作的過程。這裡構造通用型過程所采用的主要技術，是讓它們在帶有類型标志的資料對象上工作。也就是說，讓這些資料對象包含着它們應該如何處理的明确資訊。我們還要讨論資料導向的程式設計，這是一種用于構造采用了通用型操作的系統有力而且友善的技術。

我們将從簡單的複數執行個體開始，看看如何采用類型标志和資料導向的風格，為複數分别設計出直角坐标表示和極坐标表示，而又維持一種抽象的“複數”資料對象的概念。做到這一點的方式就是定義基于通用型選擇函數定義複數的算術運算（add-complex、sub-complex、mul-complex和div-complex），使這些選擇函數能通路一個複數的各個部分，無論複數采用的是什麼表示方式。作為結果的複數系統如圖2-19所示，其中包含兩種不同類型的抽象屏障，“水準”抽象屏障扮演的角色與圖2-1中的相同，它們将“高層”操作與“低層”表示隔離開。此外，還存在着一道“垂直”屏障，它使我們能夠隔離不同的設計，并且還能夠安裝其他的表示方式。

在2.5節裡，我們将說明如何利用類型标志和資料導向的風格去開發一個通用型算術包，其中提供的過程（add、mul等）可以用于操作任何種類的“數”，在需要另一類新的數時也很容易進行擴充。在2.5.3節裡，我們還要展示如何在執行符号代數的系統裡使用通用型算術功能。

2.4.1 複數的表示

這裡要開發一個完成複數算術運算的系統，作為使用通用型操作的程式的一個簡單的，但不那麼實際的例子。開始時，我們要讨論将複數表示為有序對的兩種可能表示方式：直角坐标形式（實部和虛部）以及極坐标形式（模和幅角）。2.4.2節将展示如何通過類型标志和通用型操作，使這兩種表示共存于同一個系統中。

與有理數一樣，複數也可以很自然地用有序對表示。我們可以将複數集合設想為一個帶有兩個坐标軸（“實”軸和“虛”軸）的二維空間（見圖2-20）。按照這一觀點，複數z＝x＋iy（其中i2＝－1）可看作這個平面上的一個點，其中的實坐标是x而虛坐标為y。在這種表示下，複數的加法就可以歸結為兩個坐标分别相加：

實部 (z1＋z2)＝實部 (z1)＋實部 (z2)

虛部 (z1＋z2)＝虛部 (z1)＋虛部 (z2)

在需要乘兩個複數時，更自然的考慮是采用複數的極坐标形式，此時複數用一個模和一個幅角表示（圖2-20中的r和A）。兩個複數的乘積也是一個向量，得到它的方式是模相乘，幅角相加。

模 (z1·z2)＝模 (z1)·模 (z2)

幅角 (z1·z2)＝幅角 (z1)＋幅角 (z2)

可見，複數有兩種不同表示方式，它們分别适合不同的運算。當然，從編寫使用複數的程式的開發人員角度看，資料抽象原理的建議是所有複數操作都應該可以使用，無論計算機所用的具體表示形式是什麼。例如，我們也常常需要取得一個複數的模，即使它原本采用的是複數的直角坐标表示。同樣，我們也常常需要得到複數的實部，即使它實際采用的是極坐标形式。

在設計一個這樣的系統時，我們将沿用在2.1.1節設計有理數包時所采用的同樣的資料抽象政策，假定所有複數運算的實作都基于如下四個選擇函數：real-part、imag-part、magnitude和angle；還要假定有兩個構造複數的過程：make-from-real-imag傳回一個采用實部和虛部描述的複數，make-from-mag-ang傳回一個采用模和幅角描述的複數。這些過程的性質是，對于任何複數z，下面兩者：

(make-from-real-imag (real-part z) (imag-part z))           

(make-from-mag-ang (magnitude z) (angle z))           

産生出的複數都等于z。

利用這些構造函數和選擇函數，我們就可以實作複數算術了，其中使用由這些構造函數和選擇函數所刻畫的“抽象資料”，就像前面在2.1.1節中針對有理數所做的那樣。正如上面公式中所描述的，複數的加法和減法采用實部和虛部的方式描述，而乘法和除法采用模和幅角的方式描述：

(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)
  (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))))           

為了完成這一複數包，我們必須選擇一種表示方式，而且必須基于基本的數值和基本表結構，基于它們實作各個構造函數和選擇函數。現在有兩種顯見的方式完成這一工作：可以将複數按“直角坐标形式”表示為一個有序對（實部，虛部），或者按照“極坐标形式”表示為有序對（模，幅角）。究竟應該選擇哪一種方式呢？

為了将不同選擇的情況看得更清楚些，現在讓我們假定有兩個程式員，Ben Bitdiddle和Alyssa P. Hacker，他們正在分别獨立地設計這一複數系統的具體表示形式。Ben選擇了複數的直角坐标表示形式，采用這一選擇，選取複數的實部與虛部是直截了當的，因為這種複數就是由實部和虛部構成的。而為了得到模和幅角，或者需要在給定模和幅角的情況下構造複數時，他利用了下面的三角關系：

這些公式建立起實部和虛部對偶 (x，y) 與模和幅角對偶 (r，A) 之間的聯系。Ben在這種表示之下給出了下面這幾個選擇函數和構造函數：

(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) 
  (cons (* r (cos a)) (* r (sin a))))           

而在另一邊，Alyssa卻選擇了複數的極坐标形式。對于她而言，選取模和幅角的操作直截了當，但必須通過三角關系去得到實部和虛部。Alyssa的表示是：

(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) 
  (cons (sqrt (+ (square x) (square y)))
        (atan y x)))
(define (make-from-mag-ang r a) (cons r a))           

資料抽象的規則保證了add-complex、sub-complex、mul-complex和div-complex的同一套實作對于Ben的表示或者Alyssa的表示都能正常工作。

2.4.2 帶标志資料

認識資料抽象的一種方式是将其看作“最小允諾原則”的一個應用。在2.4.1節中實作複數系統時，我們可以采用Ben的直角坐标表示形式或者Alyssa的極坐标表示形式，由選擇函數和構造函數形成的抽象屏障，使我們可以把為自己所用資料對象選擇具體表示形式的事情盡量向後推，而且還能保持系統設計的最大靈活性。

最小允諾原則還可以推進到更極端的情況。如果我們需要的話，那麼還可以在設計完成選擇函數和構造函數，并決定了同時使用Ben的表示和Alyssa的表示之後，仍然維持所用表示方式的不确定性。如果要在同一個系統裡包含這兩種不同表示形式，那麼就需要有一種方式，将極坐标形式的資料與直角坐标形式的資料區分開。否則的話，如果現在要找出對偶（3, 4）的magnitude，我們将無法知道答案是5（将資料解釋為直角坐标表示形式）還是3（将資料解釋為極坐标表示）。完成這種區分的一種方式，就是在每個複數裡包含一個類型标志部分—用符号rectangular或者polar。此後如果我們需要操作一個複數，借助于這個标志就可以确定應該使用的選擇函數了。

為了能對帶标志資料進行各種操作，我們将假定有過程type-tag和contents，它們分别從資料對象中提取出類型标志和實際内容（對于複數的情況，其中的極坐标或者直角坐标）。還要假定有一個過程attach-tag，它以一個标志和實際内容為參數，生成出一個帶标志的資料對象。實作這些的直接方式就是采用普通的表結構：

(define (attach-tag type-tag contents)
  (cons type-tag contents))
(define (type-tag datum)
  (if (pair? datum)
      (car datum)
      (error "Bad tagged datum -- TYPE-TAG" datum)))
(define (contents datum)
  (if (pair? datum)
      (cdr datum)
      (error "Bad tagged datum -- CONTENTS" datum)))           

利用這些過程，我們就可以定義出謂詞rectangular?和polar?，它們分别辨識直角坐标的和極坐标的複數：

(define (rectangular? z)
  (eq? (type-tag z) 'rectangular))
(define (polar? z)
  (eq? (type-tag z) 'polar))           

有了類型标志之後，Ben和Alyssa現在就可以修改自己的代碼，使他們的兩種不同表示能夠共存于同一個系統中了。當Ben構造一個複數時，總為它加上标志，說明采用的是直角坐标；而當Alyssa構造複數時，總将其标志設定為極坐标。此外，Ben和Alyssa還必須保證他們所用的過程名并不沖突。保證這一點的一種方式是，Ben總為在他的表示上操作的過程名字加上字尾rectangular，而Alyssa為她的過程名加上字尾polar。這裡是Ben根據2.4.1節修改後的直角坐标表示：

(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-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 (sin a)))))           

下面是修改後的極坐标表示：

(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 y)))
                     (atan y x))))
(define (make-from-mag-ang-polar r a)
  (attach-tag 'polar (cons r a)))           

每個通用型選擇函數都需要實作為這樣的過程，它首先檢查參數的标志，而後去調用處理該類資料的适當過程。例如，為了得到一個複數的實部，real-part需要通過檢查，設法确定是去使用Ben的real-part-rectangular，還是所用Alyssa的real-part-polar。在這兩種情況下，我們都用contents提取出原始的無标志資料，并将它送給所需的直角坐标過程或者極坐标過程：

(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))))
(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))))
(define (magnitude z)
  (cond ((rectangular? z)
         (magnitude-rectangular (contents z)))
        ((polar? 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))))           

在實作複數算術運算時，我們仍然可以采用取自2.4.1節的同樣過程add-complex、sub-complex、mul-complex和div-complex，因為它們所調用的選擇函數現在都是通用型的，對任何表示都能工作。例如，過程add-complex仍然是：

(define (add-complex z1 z2)
  (make-from-real-imag (+ (real-part z1) (real-part z2))
                       (+ (imag-part z1) (imag-part z2))))           

最後，我們還必須選擇是采用Ben的表示還是Alyssa的表示構造複數。一種合理選擇是，在手頭有實部和虛部時采用直角坐标表示，有模和幅角時就采用極坐标表示：

(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))           

這樣得到的複數系統所具有的結構如圖2-21所示。這一系統已經分解為三個相對獨立的部分：複數算術運算、Alyssa的極坐标實作和Ben的直角坐标實作。極坐标或直角坐标的實作可以是Ben和Alyssa獨立工作寫出的東西，這兩部分又被第三個程式員作為基礎表示，用于在抽象構造函數和選擇函數界面之上實作各種複數算術過程。

因為每個資料對象都以其類型作為标志，選擇函數就能夠在不同的資料上以一種通用的方式操作。也就是說，每個選擇函數的定義行為依賴于它操作其上的特定的資料類型。請注意這裡建立不同表示之間的界面的一般性機制：在一種給定的表示實作中（例如Alyssa的極坐标包），複數是一種無類型的對偶（模, 幅角）。當通用型選擇函數對一個polar類型的複數進行操作時，它會剝去标志并将相應内容傳遞給Alyssa的代碼。與此相對應，當Alyssa去構造一個供一般性使用的複數時，她也為其加上類型标志，使這個資料對象可以為高層過程所識别。在将資料對象從一個層次傳到另一層次的過程中，這種剝去和加上标志的規範方式可以成為一種重要的組織政策，正如我們将在2.5節中看到的那樣。

2.4.3 資料導向的程式設計和可加性

檢查一個資料項的類型，并據此去調用某個适當過程稱為基于類型的分派。在系統設計中，這是一種獲得子產品性的強有力政策。而另一方面，像2.4.2節那樣實作的分派有兩個顯著的弱點。第一個弱點是，其中的這些通用型界面過程（real-part、imag-part、magnitude和angle）必須知道所有的不同表示。舉例來說，假定現在希望能為前面的複數系統增加另一種表示，我們就必須将這一新表示方式辨別為一種新類型，而且要在每個通用界面過程裡增加一個子句，檢查這一新類型，并對這種表示形式使用适當的選擇函數。

這一技術還有另一個弱點。即使這些獨立的表示形式可以分别設計，我們也必須保證在整個系統裡不存在兩個名字相同的過程。正因為這一原因，Ben和Alyssa必須去修改原來在2.4.1節中給出的那些過程的名字。

位于這兩個弱點之下的基礎問題是，上面這種實作通用型界面的技術不具有可加性。在每次增加一種新表示形式時，實作通用選擇函數的人都必須修改他們的過程，而那些做獨立表示的界面的人也必須修改其代碼，以避免名字沖突問題。在做這些事情時，所有修改都必須直接對代碼去做，而且必須準确無誤。這當然會帶來極大的不便，而且還很容易引進錯誤。對于上面這樣的複數系統，這種修改還不是什麼大問題。但如果假定現在需要處理的不是複數的兩種表示形式，而是幾百種不同表示形式，假定在抽象資料界面上有許許多多需要維護的通用型選擇函數，再假定（事實上）沒有一個程式員了解所有的界面過程和表示形式，情況又會怎樣呢？在例如大規模的資料庫管理系統中，這一問題是現實存在，且必須去面對的。

現在我們需要的是一種能夠将系統設計進一步子產品化的方法。一種稱為資料導向的程式設計的程式設計技術提供了這種能力。為了了解資料導向的程式設計如何工作，我們首先應該看到，在需要處理的是針對不同類型的一集公共通用型操作時，事實上，我們正是在處理一個二維表格，其中的一個維上包含着所有的可能操作，另一個維就是所有的可能類型。表格中的項目是一些過程，它們針對作為參數的每個類型實作每一個操作。在前一節中開發的複數系統裡，操作名字、資料類型和實際過程之間的對應關系散布在各個通用界面過程的各個條件子句裡，我們也可以将同樣的資訊組織為一個表格，如圖2-22所示。

資料導向的程式設計就是一種使程式能直接利用這種表格工作的程式設計技術。在我們前面的實作裡，是采用一集過程作為複數算術與兩個表示包之間的界面，并讓這些過程中的每一個去做基于類型的顯式分派。下面我們要把這一界面實作為一個過程，由它用操作名和參數類型的組合到表格中查找，以便找出應該調用的适當過程，并将這一過程應用于參數的内容。如果能做到這些，再把一種新的表示包加入系統裡，我們就不需要修改任何現存的過程，而隻要在這個表格裡添加一些新的項目即可。

為了實作這一計劃，現在假定有兩個過程put和get，用于處理這種操作-類型表格：

• (put <op> <type> <item>)

将項<item>加入表格中，以<op>和<type>作為這個表項的索引。

• (get <op> <type>)

在表中查找與<op>和<type>對應的項，如果找到就傳回找到的項，否則就傳回假。

從現在起，我們将假定put和get已經包含在所用的語言裡。在第3章裡（3.3.3節，練習3.24）可以看到如何實作這些函數，以及其他操作表格的過程。

下面我們要說明，這種資料導向的程式設計如何用于複數系統。在開發了直角坐标表示時，Ben完全按他原來所做的那樣實作了自己的代碼，他定義了一組過程或者說一個程式包，并通過向表格中加入一些項的方式，告訴系統如何去操作直角坐标形式表示的數，這樣就建立起了與系統其他部分的界面。完成此事的方式就是調用下面的過程：

(define (install-rectangular-package)
  ;; 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 (cos a)) (* r (sin a))))
  ;; interface to the rest of the system
  (define (tag x) (attach-tag 'rectangular x))
  (put 'real-part ?rectangular) real-part)
  (put 'imag-part ?rectangular) imag-part)
  (put 'magnitude ?rectangular) magnitude)
  (put 'angle ?rectangular) angle)
  (put 'make-from-real-imag 'rectangular 
       (lambda (x y) (tag (make-from-real-imag x y))))
  (put 'make-from-mag-ang 'rectangular 
       (lambda (r a) (tag (make-from-mag-ang r a))))
  'done)           

請注意，這裡的所有内部過程，與2.4.1節裡Ben在自己獨立工作中寫出的過程完全一樣，在将它們與系統的其他部分建立聯系時，也不需要做任何修改。進一步說，由于這些過程定義都是上述安裝過程内部的東西，Ben完全不必擔心它們的名字會與直角坐标程式包外面的其他過程的名字互相沖突。為了能與系統裡的其他部分建立起聯系，Ben将他的real-part過程安裝在操作名字real-part和類型（rectangular）之下，其他選擇函數的情況也都與此類似。這一界面還定義了提供給外部系統的構造函數，它們也與Ben自己定義的構造函數一樣，隻是其中還需要完成添加标志的工作。

Alyssa的極坐标包與此類似：

(define (install-polar-package)
  ;; internal procedures
  (define (magnitude z) (car z))
  (define (angle z) (cdr z))
  (define (make-from-mag-ang r a) (cons r a))
  (define (real-part z)
    (* (magnitude z) (cos (angle z))))
  (define (imag-part z)
    (* (magnitude z) (sin (angle z))))
  (define (make-from-real-imag x y) 
    (cons (sqrt (+ (square x) (square y)))
          (atan y x)))
  ;; interface to the rest of the system
  (define (tag x) (attach-tag 'polar x))
  (put 'real-part ?polar) real-part)
  (put 'imag-part ?polar) imag-part)
  (put 'magnitude ?polar) magnitude)
  (put 'angle ?polar) angle)
  (put 'make-from-real-imag 'polar
       (lambda (x y) (tag (make-from-real-imag x y))))
  (put 'make-from-mag-ang 'polar 
       (lambda (r a) (tag (make-from-mag-ang r a))))
  'done)           

雖然Ben和Alyssa兩個人仍然使用着他們原來的過程定義，這些過程也有着同樣的名字（例如real-part），但對于其他過程而言，這些定義都是内部的（參見1.1.8節），是以在這裡不會出現名字沖突問題。

複數算術的選擇函數通過一個通用的名為apply-generic的“操作”過程通路有關表格，這個過程将通用型操作應用于一些參數。apply-generic在表格中用操作名和參數類型查找，如果找到，就去應用查找中得到的過程：

(define (apply-generic op . args)
  (let ((type-tags (map type-tag args)))
    (let ((proc (get op type-tags)))
      (if proc
          (apply proc (map contents args))
          (error
            "No method for these types -- APPLY-GENERIC"
            (list op type-tags))))))           

利用apply-generic，各種通用型選擇函數可以定義如下：

(define (real-part z) (apply-generic 'real-part z))
(define (imag-part z) (apply-generic 'imag-part z))
(define (magnitude z) (apply-generic 'magnitude z))
(define (angle z) (apply-generic 'angle z))           

請注意，如果要将一個新表示形式加入這個系統，上述這些都完全不必修改。

我們同樣可以從表中提取出構造函數，用到包之外的程式中，從實部和虛部或者模和幅角構造出複數來。就像在2.4.2節中那樣，當我們有的是實部和虛部時就構造直角坐标表示的複數，有模和幅角時就構造極坐标的數：

(define (make-from-real-imag x y)
  ((get 'make-from-real-imag 'rectangular) x y))
(define (make-from-mag-ang r a)
  ((get 'make-from-mag-ang 'polar) r a))           

練習2.73 2.3.2節描述了一個執行符号求導的程式：

(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)))
        ((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。我們也可以将這一程式變換到資料導向的風格，将基本求導過程重新寫成：

(define (deriv exp var)
   (cond ((number? exp) 0)
         ((variable? exp) (if (same-variable? exp var) 1 0))
         (else ((get 'deriv (operator exp)) (operands exp)
                                            var))))
(define (operator exp) (car exp))
(define (operands exp) (cdr exp))           

a) 請解釋上面究竟做了些什麼。為什麼我們無法将相近的謂詞number?和same-variable?也加入資料導向分派中？

b) 請寫出針對和式與積式的求導過程，并把它們安裝到表格裡，以便上面程式使用所需要的輔助性代碼。

c) 請選擇一些你希望包括的求導規則，例如對乘幂（練習2.56）求導等等，并将它們安裝到這一資料導向的系統裡。

d) 在這一簡單的代數運算器中，表達式的類型就是構造起它們來的代數運算符。假定我們想以另一種相反的方式做索引，使得deriv裡完成分派的代碼行像下面這樣：

((get (operator exp) 'deriv) (operands exp) var)           

求導系統裡還需要做哪些相應的改動？

練習2.74 Insatiable Enterprise公司是一個高度分散經營的聯合公司，由大量分布在世界各地的分支機構組成。公司的計算機設施已經通過一種非常巧妙的網絡連接配接模式連接配接成一體，它使得從任何一個使用者的角度看，整個網絡就像是一台計算機。在第一次試圖利用網絡能力從各分支機構的檔案中提取管理資訊時，Insatiable的總經理非常沮喪地發現，雖然所有分支機構的檔案都被實作為Scheme的資料結構，但是各分支機構所用的資料結構卻各不相同。她馬上召集了各分支機構的經理會議，希望尋找一種政策內建起這些檔案，以便在維持各個分支機構中現存獨立工作方式的同時，又能滿足公司總部管理的需要。

請說明這種政策可以如何通過資料導向的程式設計技術實作。作為例子，假定每個分支機構的人事記錄都存放在一個獨立檔案裡，其中包含了一集以雇員名字作為鍵值的記錄。而有關集合的結構卻由于分支機構的不同而不同。進一步說，某個雇員的記錄本身又是一個集合（各分支機構所用的結構也不同），其中所包含的資訊也在一些作為鍵值的辨別符之下，例如address和salary。特别是考慮如下問題：

a) 請為公司總部實作一個get-record過程，使它能從一個特定的人事檔案裡提取出一個特定的雇員記錄。這一過程應該能應用于任何分支機構的檔案。請說明各個獨立分支機構的檔案應具有怎樣的結構。特别是考慮，它們必須提供哪些類型資訊？

b) 請為公司總部實作一個get-salary過程，它能從任何分支機構的人事檔案中取得某個給定雇員的薪金資訊。為了使這一操作能夠工作，這些記錄應具有怎樣的結構？

c) 請為公司總部實作一個過程find-employee-record，該過程需要針對一個特定雇員名，在所有分支機構的檔案去查找對應的記錄，并傳回找到的記錄。假定這一過程的參數是一個雇員名和所有分支檔案的表。

d) 當Insatiable購并新公司後，要将新的人事檔案結合到系統中，必須做哪些修改？

消息傳遞

在資料導向的程式設計裡，最關鍵的想法就是通過顯式處理操作－類型表格（例如圖2-22裡的表格）的方式，管理程式中的各種通用型操作。我們在2.4.2節中所用的程式設計風格，是一種基于類型進行分派的組織方式，其中讓每個操作管理自己的分派。從效果上看，這種方式就是将操作－類型表格分解為一行一行，每個通用型過程表示表格中的一行。

另一種實作政策是将這一表格按列進行分解，不是采用一批“智能操作”去基于資料類型進行分派，而是采用“智能資料對象”，讓它們基于操作名完成所需的分派工作。如果我們想這樣做，所需要做的就是做出一種安排，将每一個資料對象（例如一個采用直角坐标表示的複數）表示為一個過程。它以操作的名字作為輸入，能夠去執行指定的操作。按照這種方式，make-from-real-imag應該寫成下面樣子：

(define (make-from-real-imag x y)
  (define (dispatch op)
    (cond ((eq? op 'real-part) x)
          ((eq? op 'imag-part) y)
          ((eq? op 'magnitude)
           (sqrt (+ (square x) (square y))))
          ((eq? op 'angle) (atan y x))
          (else
           (error "Unknown op -- MAKE-FROM-REAL-IMAG" op))))
  dispatch)           

與之對應的apply-generic過程應該對其參數應用一個通用型操作，此時它隻需要簡單地将操作名饋入該資料對象，并讓那個對象去完成工作：

(define (apply-generic op arg) (arg op))

請注意，make-from-real-imag傳回的值是一個過程—它内部的dispatch過程。這也就是當apply-generic要求執行一個操作時所調用的過程。

這種風格的程式設計稱為消息傳遞，這一名字源自将資料對象設想為一個實體，它以“消息”的方式接收到所需操作的名字。在2.1.3節中我們已經看到過一個消息傳遞的例子，在那裡看到的是如何用沒有資料對象而隻有過程的方式定義cons、car和cdr。現在我們看到的是，消息傳遞并不是一種數學機巧，而是一種有價值的技術，可以用于組織帶有通用型操作的系統。在本章剩下的部分裡，我們将要繼續使用資料導向的程式設計（而不是用消息傳遞），進一步讨論通用型算術運算的問題。在第3章裡我們将會回到消息傳遞，并在那裡看到它可能怎樣成為構造模拟程式的強有力工具。

練習2.75 請用消息傳遞的風格實作構造函數make-from-mag-ang。這一過程應該與上面給出的make-from-real-imag過程類似。

練習2.76 一個帶有通用型操作的大型系統可能不斷演化，在演化中常需要加入新的資料對象類型或者新的操作。對于上面提出的三種政策—帶有顯式分派的通用型操作，資料導向的風格，以及消息傳遞的風格—請描述在加入一個新類型或者新操作時，系統所必須做的修改。哪種組織方式最适合那些經常需要加入新類型的系統？哪種組織方式最适合那些經常需要加入新操作的系統？

2.5 帶有通用型操作的系統

在前一節裡，我們看到了如何去設計一個系統，使其中的資料對象可以以多于一種方式表示。這裡的關鍵思想就是通過通用型界面過程，将描述資料操作的代碼連接配接到幾種不同表示上。現在我們将看到如何使用同樣的思想，不但定義出能夠在不同表示上的通用操作，還能定義針對不同參數種類的通用型操作。我們已經看到過幾個不同的算術運算包：語言内部的基本算術（＋，－，*，/），2.1.1節的有理數算術（add-rat，sub-rat，mul-rat，div-rat），以及2.4.3節裡實作的複數算術。現在我們要使用資料導向技術構造起一個算術運算包，将前面已經構造出的所有算術包都結合進去。

圖2-23展示了我們将要構造的系統的結構。請注意其中的各抽象屏障。從某些使用“數值”的人的觀點看，在這裡隻存在一個過程add，無論提供給它的數是什麼。add是通用型界面的一部分，這一界面将使那些使用數的程式能以一種統一的方式，通路互相分離的正常算術、有理數算術和複數算術程式包。任何獨立的算術程式包（例如複數包）本身也可能通過通用型過程（例如add-complex）通路，它也可能由針對不同表示形式設計的包（直角坐标表示和極坐标表示）組合而成。進一步說，這一系統具有可加性，這樣，人們還可以設計出其他獨立的算術包，并将其組合到這一通用型的算術系統中。

2.5.1 通用型算術運算

設計通用型算術運算的工作類似于設計通用型複數運算。我們希望（例如）有一個通用型的加法過程add，對于正常的數，它的行為就像正常的基本加法＋；對于有理數，它就像add-rat，對于複數就像add-complex。我們可以沿用在2.4.3節為實作複數上的通用選擇函數所用的同樣政策，去實作add和其他通用算術運算。下面将為每種數附着一個類型标志，以便通用型過程能夠根據其參數的類型完成到某個适用的程式包的分派。

通用型算術過程的定義如下：

(define (add x y) (apply-generic 'add x y))
(define (sub x y) (apply-generic 'aub x y))
(define (mul x y) (apply-generic 'mul x y))
(define (div x y) (apply-generic 'div x y))           

下面我們将從安裝處理正常數（即，語言中基本的數）的包開始，對這種數采用的标志是符号scheme-number。這個包裡的算術運算都是基本算術過程（是以不需要再定義過程去處理無标志的數）。因為每個操作都有兩個參數，是以用表（scheme-number scheme-number）作為表格中的鍵值去安裝它們：

(define (install-scheme-number-package)
  (define (tag x)
    (attach-tag 'acheme-number x))    
  (put 'add ?scheme-number scheme-number)
       (lambda (x y) (tag (+ x y))))
  (put 'aub ?scheme-number scheme-number)
       (lambda (x y) (tag (- x y))))
  (put 'mul ?scheme-number scheme-number)
       (lambda (x y) (tag (* x y))))
  (put 'div ?scheme-number scheme-number)
       (lambda (x y) (tag (/ x y))))
  (put 'make 'acheme-number
       (lambda (x) (tag x)))
  'done)           

Scheme數值包的使用者可以通過下面過程，建立帶标志的正常數：

(define (make-scheme-number n)
  ((get 'make 'acheme-number) n))           

現在我們已經做好了通用型算術系統的架構，可以将新的數類型加入其中了。下面是一個執行有理數算術的程式包。請注意，由于具有可加性，我們可以直接把取自2.1.1節的有理數代碼作為這個程式包的内部過程，完全不必做任何修改：

(define (install-rational-package)
  ;; internal procedures
  (define (numer x) (car x))
  (define (denom x) (cdr x))
  (define (make-rat n d)
    (let ((g (gcd n d)))
      (cons (/ n g) (/ d g))))
  (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 (- (* (numer x) (denom y))
                 (* (numer y) (denom x)))
              (* (denom x) (denom y))))
  (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))))
  ;; interface to rest of the system
  (define (tag x) (attach-tag 'rational x))
  (put 'add ?rational rational)
       (lambda (x y) (tag (add-rat x y))))
  (put 'aub ?rational rational)
       (lambda (x y) (tag (sub-rat x y))))
  (put 'mul ?rational rational)
       (lambda (x y) (tag (mul-rat x y))))
  (put 'div ?rational rational)
       (lambda (x y) (tag (div-rat x y))))
  (put 'make 'rational
       (lambda (n d) (tag (make-rat n d))))
  'done)
(define (make-rational n d)
  ((get 'make 'rational) n d))           

我們可以安裝上另一個處理複數的類似程式包，采用的标志是complex。在建立這個程式包時，我們要從表格裡抽取出操作make-from-real-imag和make-from-mag-ang，它們原來分别定義在直角坐标和極坐标包裡。可加性使我們能把取自2.4.1節同樣的add-complex、sub-complex、mul-complex和div-complex過程用作内部操作。

(define (install-complex-package)
  ;; imported procedures from rectangular and polar packages
  (define (make-from-real-imag x y)
    ((get 'make-from-real-imag 'rectangular) x y))
  (define (make-from-mag-ang r a)
    ((get 'make-from-mag-ang 'polar) r a))
  ;; internal procedures
  (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)
    (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))))
  ;; interface to rest of the system
  (define (tag z) (attach-tag 'complex z))
  (put 'add ?complex complex)
       (lambda (z1 z2) (tag (add-complex z1 z2))))
  (put 'aub ?complex complex)
       (lambda (z1 z2) (tag (sub-complex z1 z2))))
  (put 'mul ?complex complex)
       (lambda (z1 z2) (tag (mul-complex z1 z2))))
  (put 'div ?complex complex)
       (lambda (z1 z2) (tag (div-complex z1 z2))))
  (put 'make-from-real-imag 'complex
       (lambda (x y) (tag (make-from-real-imag x y))))
  (put 'make-from-mag-ang 'complex
       (lambda (r a) (tag (make-from-mag-ang r a))))
  'done)           

在複數包之外的程式可以從實部和虛部出發構造複數，也可以從模和幅角出發。請注意這裡如何将原先定義在直角坐标和極坐标包裡的內建過程導出，放入複數包中，又如何從這裡導出送給外面的世界。

(define (make-complex-from-real-imag x y)
  ((get 'make-from-real-imag 'complex) x y))
(define (make-complex-from-mag-ang r a)
  ((get 'make-from-mag-ang 'complex) r a))           

這裡描述的是一個具有兩層标志的系統。一個典型的複數如直角坐标表示的3＋4i，現在的表示形式如圖2-24所示。外層标志（complex）用于将這個數引導到複數包，一旦進入複數包，下一個标志（rectangular）就會引導這個數進入直角坐标表示包。在一個大型的複雜系統裡可能有許多層次，每層與下一層次之間的連接配接都借助于一些通用型操作。當一個資料對象被“向下”傳輸時，用于引導它進入适當程式包的最外層标志被剝除（通過使用contents），下一層次的标志（如果有的話）變成可見的，并将被用于下一次分派。

在上面這些程式包裡，我們使用了add-rat、add-complex以及其他算術過程，完全按照它們原來寫出的形式。一旦把這些過程定義為不同安裝過程内部的東西，它們的名字就沒有必要再互相不同了，可以在兩個包中都簡單地将它們命名為add、sub、mul和div。

練習2.77 Louis Reasoner試着去求值（magnitude z），其中的z就是圖2-24裡的那個對象。令他吃驚的是，從apply-generic出來的不是5而是一個錯誤資訊，說沒辦法對類型（complex）做操作magnitude。他将這次互動的情況給Alyssa P. Hacker看，Alyssa說“問題出在沒有為complex數定義複數選擇函數，而隻是為polar和rectangular數定義了它們。你需要做的就是在complex包裡加入下面這些東西”：

(put 'real-part '(complex) real-part)
(put 'imag-part '(complex) imag-part)
(put 'magnitude '(complex) magnitude)
(put 'angle '(complex) angle)           

請詳細說明為什麼這樣做是可行的。作為一個例子，請考慮表達式（magnitude z）的求值過程，其中z就是圖2-24裡展示的那個對象，請追蹤一下這一求值過程中的所有函數調用。特别是看看apply-generic被調用了幾次？每次調用中分派的是哪個過程？

練習2.78 包scheme-number裡的内部過程幾乎什麼也沒做，隻不過是去調用基本過程＋、－等等。直接使用語言的基本過程當然是不可能的，因為我們的類型标志系統要求每個資料對象都附加一個類型。然而，事實上所有Lisp實作都有自己的類型系統，使用在系統實作的内部，基本謂詞symbol?和number?等用于确定某個資料對象是否具有特定的類型。請修改2.4.2節中type-tag、contents和attach-tag的定義，使我們的通用算術系統可以利用Scheme的内部類型系統。這也就是說，修改後的系統應該像原來一樣工作，除了其中正常的數直接采用Scheme的數形式，而不是表示為一個car部分是符号scheme-number的序對。

練習2.79 請定義一個通用型相等謂詞equ?，它能檢查兩個數是否相等。請将它安裝到通用算術包裡。這一操作應該能處理正常的數、有理數和複數。

練習2.80 請定義一個通用謂詞＝zero?，檢查其參數是否為0，并将它安裝到通用算術包裡。這一操作應該能處理正常的數、有理數和複數。

2.5.2 不同類型資料的組合

前面已經看到了如何定義出一個統一的算術系統，其中包含正常的數、複數和有理數，以及我們希望發明的任何其他數值類型。但在那裡也忽略了一個重要的問題。我們至今定義的所有運算，都把不同資料類型看作互相完全分離的東西，也就是說，這裡有幾個完全分離的程式包，它們分别完成兩個正常的數，或者兩個複數的加法。我們至今還沒有考慮的問題是下面事實：定義出能夠跨過類型界限的操作也很有意義，譬如完成一個複數和一個正常數的加法。在前面，我們一直煞費苦心地在程式的各個部分之間引進了屏障，以使它們能夠分别開發和分别了解。現在卻又要引進跨類型的操作。當然，我們必須以一種經過精心考慮的可控方式去做這件事情，以使我們在支援這種操作的同時又沒有嚴重地損害子產品間的分界。

處理跨類型操作的一種方式，就是為每一種類型組合的合法運算設計一個特定過程。例如，我們可以擴充複數包，使它能提供一個過程用于加起一個複數和一個正常的數，并用标志（complex scheme-number）将它安裝到表格裡：

;; to be included in the complex package
(define (add-complex-to-schemenum z x)
  (make-from-real-imag (+ (real-part z) x)
                       (imag-part z)))
(put 'add ?complex scheme-number)
     (lambda (z x) (tag (add-complex-to-schemenum z x))))           

這一技術确實可以用，但也非常麻煩。對于這樣的一個系統，引進一個新類型的代價就不僅僅需要構造出針對這一類型的所有過程的包，還需要構造并安裝好所有實作跨類型操作的過程。後一件事所需要的代碼很容易就會超過定義類型本身所需的那些操作。這種方法也損害了以添加方式組合獨立開發的程式包的能力，至少給獨立程式包的實作者增加了一些限制，要求他們在對獨立程式包工作時，必須同時關注其他的程式包。比如，在上面例子裡，如果要處理複數和正常數的混合運算，将其看作複數包的責任是合理的。然而，有關有理數和複數的組合工作卻存在許多選擇，完全可以由複數包、有理數包，或者由另外的，使用了從前面兩個包中取出的操作的第三個包完成。在設計包含許多程式包和許多跨類型操作的系統時，要想規劃好一套統一的政策，厘清各種包之間的責任，很容易變成非常複雜的任務。

強制

最一般的情況是需要處理針對一批完全無關的類型的一批完全無關的操作，直接實作跨類型操作很可能就是解決問題的最好方式了，當然，這樣做起來确實比較麻煩。幸運的是，我們常常可以利用潛藏在類型系統之中的一些額外結構，将事情做得更好些。不同的資料類型通常都不是完全互相無關的，常常存在一些方式，使我們可以把一種類型的對象看作另一種類型的對象。這種過程就稱為強制。舉例來說，如果現在需要做正常數值與複數的混合算術，我們就可以将正常數值看成是虛部為0的複數。這樣就把問題轉換為兩個複數的運算問題，可以由複數包以正常的方式處理了。

一般而言，要實作這一想法，我們可以設計出一些強制過程，它們能把一個類型的對象轉換到另一類型的等價對象。下面是一個典型的強制過程，它将給定的正常數值轉換為一個複數，其中的實部為原來的數而虛部是0：

(define (scheme-number->complex n)
  (make-complex-from-real-imag (contents n) 0))           

我們将這些強制過程安裝到一個特殊的強制表格中，用兩個類型的名字作為索引：

(put-coercion 'acheme-number 'complex scheme-number->complex)           

（這裡假定了存在着用于操縱這個表格的put-coercion和get-coercion過程。）一般而言，這一表格裡的某些格子将是空的，因為将任何資料對象轉換到另一個類型并不是都能做的。例如并不存在某種将任意複數轉換為正常數值的方式，是以，這個表格中就不應包括一般性的complex->scheme-number過程。

一旦将上述轉換表格裝配好，我們就可以修改2.4.3節的apply-generic過程，得到一種處理強制的統一方法。在要求應用一個操作時，我們将首先檢查是否存在針對實際參數類型的操作定義，就像前面一樣。如果存在，那麼就将任務分派到由操作－類型表格中找出的相應過程去，否則就去做強制。為了簡化讨論，這裡隻考慮兩個參數的情況。我們檢查強制表格，檢視其中第一個參數類型的對象能否轉換到第二個參數的類型。如果可以，那就對第一個參數做強制後再試驗操作。如果第一個參數類型的對象不能強制到第二個類型，那麼就試驗另一種方式，看看能否從第二個參數的類型轉換到第一個參數的類型。最後，如果不存在從一個類型到另一類型的強制，那麼就隻能放棄了。下面是這個過程：

(define (apply-generic op . args)
  (let ((type-tags (map type-tag args)))
    (let ((proc (get op type-tags)))
      (if proc
          (apply proc (map contents args))
          (if (= (length args) 2)
              (let ((type1 (car type-tags))
                    (type2 (cadr type-tags))
                    (a1 (car args))
                    (a2 (cadr args)))
                (let ((t1->t2 (get-coercion type1 type2))
                      (t2->t1 (get-coercion type2 type1)))
                  (cond (t1->t2
                         (apply-generic op (t1->t2 a1) a2))
                        (t2->t1
                         (apply-generic op a1 (t2->t1 a2)))
                        (else
                         (error "No method for these types"
                                (list op type-tags))))))
              (error "No method for these types"
                     (list op type-tags)))))))           

與顯式定義的跨類型操作相比，這種強制模式有許多優越性。就像在上面已經說過的。雖然我們仍然需要寫出一些與各種類型有關的強制過程（對于n個類型的系統可能需要n2個過程），但是卻隻需要為每一對類型寫一個過程，而不是為每對類型和每個通用型操作寫一個過程。能夠這樣做的基礎就是，類型之間的适當轉換隻依賴于類型本身，而不依賴于所實際應用的操作。

另一方面，也可能存在一些應用，對于它們而言我們的強制模式還不足夠一般。即使需要運算的兩種類型的對象都不能轉換到另一種類型，也完全可能在将這兩種類型的對象都轉換到第三種類型後執行這一運算。為了處理這種複雜性，同時又能維持我們系統的子產品性，通常就需要在建立系統時利用類型之間的進一步結構，有關情況見下面的讨論。

類型的層次結構

上面給出的強制模式，依賴于一對對類型之間存在着某種自然的關系。在實際中，還常常存在着不同類型間互相關系的更“全局性”的結構。例如，假定我們想要構造出一個通用型的算術系統，處理整數、有理數、實數、複數。在這樣的一個系統裡，一種很自然的做法是把整數看作是一類特殊的有理數，而有理數又是一類特殊的實數，實數轉而又是一類特殊的複數。這樣，我們實際有的就是一個所謂的類型的層次結構，在其中，（例如）整數是有理數的子類型（也就是說，任何可以應用于有理數的操作都可以應用于整數）。與此相對應，人們也說有理數形成了整數的一個超類型。在這個例子裡所看到的類型層次結構是最簡單的一種，其中一個類型隻有至多一個超類型和至多一個子類型。這樣的結構稱為一個類型塔，如圖2-25所示。

如果我們面對的是一個塔結構，那麼将一個新類型加入層次結構的問題就可能極大地簡化了，因為需要做的所有事情，也就是刻畫清楚這一新類型将如何嵌入正好位于它之上的超類型，以及它如何作為下面一個類型的超類型。舉例說，如果我們希望做一個整數和一個複數的加法，那麼并不需要明确定義一個特殊強制函數integer->complex。相反，我們可以定義如何将整數轉換到有理數，如何将有理數轉換到實數，以及如何将實數轉換到複數。而後讓系統通過這些步驟将該整數轉換到複數，在此之後再做兩個複數的加法。

我們可以按照下面的方式重新設計那個apply-generic過程。對于每個類型，都需要提供一個raise過程，它将這一類型的對象“提升”到塔中更高一層的類型。此後，當系統遇到需要對兩個不同類型的運算時，它就可以逐漸提升較低的類型，直至所有對象都達到了塔的同一個層次（練習2.83和練習2.84關注的就是實作這種政策的一些細節）。

類型塔的另一優點，在于使我們很容易實作一種概念：每個類型能夠“繼承”其超類型中定義的所有操作。舉例說，如果我們沒有為找出整數的實部提供一個特定過程，但也完全可能期望real-part過程對整數有定義，因為事實上整數是複數的一個子類型。對于類型塔的情況，我們可以通過修改apply-generic過程，以一種統一的方式安排好這些事情。如果所需操作在給定對象的類型中沒有明确定義，那麼就将這個對象提升到它的超類型并再次檢查。在向塔頂攀登的過程中，我們也不斷轉換有關的參數，直至在某個層次上找到了所需的操作而後去執行它，或者已經到達了塔頂（此時就隻能放棄了）。

與其他層次結構相比，塔形結構的另一優點是它使我們有一種簡單的方式去“下降”一個資料對象，使之達到最簡單的表示形式。例如，如果現在做了2＋3i和4－3i的加法，如果結果是整數6而不是複數6＋0i當然就更好了。練習2.85讨論了實作這種下降操作的一種方式。這裡的技巧在于需要有一種一般性的方式，分辨出哪些是可以下降的對象（例如6＋0i），哪些是不能下降的對象（例如6＋2i）。

層次結構的不足

如果在一個系統裡，有關的資料類型可以自然地安排為一個塔形，那麼正如在前面已經看到的，處理不同類型上通用型操作的問題将能得到極大的簡化。遺憾的是，事情通常都不是這樣。圖2-26展示的是類型之間關系的一種更複雜情況，其中顯示出的是表示幾何圖形的各種類型之間的關系。從這個圖裡可以看到，一般而言，一個類型可能有多于一個子類型，例如三角形和四邊形都是多邊形的子類型。此外，一個類型也可能有多于一個超類型，例如，等腰直角三角形可以看作是等腰三角形，又可以看作是直角三角形。這種存在多重超類型的問題特别令人棘手，因為這就意味着，并不存在一種唯一方式在層次結構中去“提升”一個類型。當我們需要将一個操作應用于一個對象時，為此而找出“正确”超類型的工作（例如，這就是apply-generic這類過程中的一部分）可能涉及對整個類型網絡的大範圍搜尋。由于一般說一個類型存在着多個子類型，需要在類型層次結構中“下降”一個值時也會遇到類似的問題。在設計大型系統時，處理好一大批互相有關的類型而同時又能保持子產品性，這是一個非常困難的問題，也是目前正在繼續研究的一個領域。

練習2.81 Louis Reasoner注意到，甚至在兩個參數的類型實際相同的情況下，apply-generic也可能試圖去做參數間的類型強制。由此他推論說，需要在強制表格中加入一些過程，以将每個類型的參數“強制”到它們自己的類型。例如，除了上面給出的scheme-number->complex強制之外，他覺得應該有：

(define (scheme-number->scheme-number n) n)
(define (complex->complex z) z)
(put-coercion 'acheme-number 'acheme-number
              scheme-number->scheme-number)
(put-coercion 'complex 'complex complex->complex)           

a) 如果安裝了Louis的強制過程，如果在調用apply-generic時各參數的類型都為scheme-number或者類型都為complex，而在表格中又找不到相應的操作，這時會出現什麼情況？例如，假定我們定義了一個通用型的求幂運算：

(define (exp x y) (apply-generic 'exp x y))           

并在Scheme數值包裡放入了一個求幂過程，但其他程式包裡都沒有：

;; following added to Scheme-number package
(put 'exp ?scheme-number scheme-number)
     (lambda (x y) (tag (expt x y)))) ; using primitive expt           

如果對兩個複數調用exp會出現什麼情況？

b) Louis真的糾正了有關同樣類型參數的強制問題嗎？apply-generic還能像原來那樣正确工作嗎？

c) 請修改apply-generic，使之不會試着去強制兩個同樣類型的參數。

練習2.82 請闡述一種方法，設法推廣apply-generic，以便處理多個參數的一般性情況下的強制問題。一種可能政策是試着将所有參數都強制到第一個參數的類型，而後試着強制到第二個參數的類型，并如此試下去。請給出一個例子說明這種政策還不夠一般（就像上面對兩個參數的情況給出的例子那樣）。（提示：請考慮一些情況，其中表格裡某些合用的操作将不會被考慮。）

練習2.83 假定你正在設計一個通用型的算術包，處理圖2-25所示的類型塔，包括整數、有理數、實數和複數。請為每個類型（除複數外）設計一個過程，它能将該類型的對象提升到塔中的上面一層。請說明如何安裝一個通用的raise操作，使之能對各個類型工作（除複數之外）。

練習2.84 利用練習2.83的raise操作修改apply-generic過程，使它能通過逐層提升的方式将參數強制到同樣的類型，正如本節中讨論的。你将需要安排一種方式，去檢查兩個類型中哪個更高。請以一種能與系統中其他部分“相容”，而且又不會影響向塔中加入新層次的方式完成這一工作。

練習2.85 本節中提到了“簡化”資料對象表示的一種方法，就是使之在類型塔中盡可能地下降。請設計一個過程drop（下落），使它能在如練習2.83所描述的類型塔中完成這一工作。這裡的關鍵是以某種一般性的方式，判斷一個資料對象能否下降。舉例來說，複數 1.5＋0i至多可以下降到real，複數1＋0i至多可以下降到integer，而複數2＋3i就根本無法下降。現在提出一種确定一個對象能否下降的計劃：首先定義一個運算project（投影），它将一個對象“壓”到塔的下面一層。例如，投影一個複數就是丢掉其虛部。這樣，一個數能夠向下落，如果我們首先project它而後将得到的結果raise到開始的類型，最終得到的東西與開始的東西相等。請闡述實作這一想法的具體細節，并寫出一個drop過程，使它可以将一個對象盡可能地下落。你将需要設計各種各樣的投影函數119，并需要把project安裝為系統裡的一個通用型操作。你還需要使用一個通用型的相等謂詞，例如練習2.79所描述的。最後，請利用drop重寫練習2.84的apply-generic，使之可以“簡化”其結果。

練習2.86 假定我們希望處理一些複數，它們的實部、虛部、模和幅角都可以是正常數值、有理數，或者我們希望加入系統的任何其他數值類型。請描述和實作系統需要做的各種修改，以滿足這一需要。你應設法将例如sine和cosine一類的運算也定義為在正常數和有理數上的通用運算。

2.5.3 執行個體：符号代數

符号表達式的操作是一種很複雜的計算過程，它能夠展示出在設計大型系統時常常會出現的許多困難問題。一般來說，一個代數表達式可以看成一種具有層次結構的東西，它是将運算符作用于一些運算對象而形成的一棵樹。我們可以從一集基本對象，例如常量和變量出發，通過各種代數運算符如加法和乘法的組合，構造起各種各樣的代數表達式。就像在其他語言裡一樣，在這裡也需要形成各種抽象，使我們能夠有簡單的方式去引用複合對象。在符号代數中，與典型抽象的有關想法包括線性組合、多項式、有理函數和三角函數等等。可以将這些看作是複合的“類型”，它們在制導對表達式的處理過程方面非常有用。例如，我們可以将表達式：

x2 sin (y2＋1)＋x cos 2y＋cos (y3－2y2)           

看作一個x的多項式，其參數是y的多項式的三角函數，而y的多項式的系數是整數。

下面我們将試着開發一個完整的代數演算系統。這類系統都是異乎尋常地複雜的程式，包含着深入的代數知識和美妙的算法。我們将要做的，隻是考察代數演算系統中一個簡單但卻很重要的部分，多項式算術。我們将展示在設計這樣一個系統時所面臨的各種抉擇，以及如何應用抽象資料和通用型操作的思想，以利于組織好這一工作項目。

多項式算術

要設計一個執行多項式算術的系統，第一件事情就是确定多項式到底是什麼。多項式通常總是針對某些特定的變量（多項式中的未定元）定義的。為了簡單起見，我們把需要考慮的多項式限制到隻有一個未定元的情況（單變元多項式）。下面将多項式定義為項的和式，而每個項或者就是一個系數，或者是未定元的乘方，或者是一個系數與一個未定元乘方的乘積。系數也定義為一個代數表達式，但它不依賴于這個多項式的未定元。例如：

5x2＋3x＋7           

是x的一個簡單多項式，而

(y2＋1) x3＋(2y) x＋1           

是x的一個多項式，而其參數又是y的多項式。

這樣，我們就已經繞過了某些棘手問題。例如，上面的第一個多項式是否與多項式5y2＋3y＋7相同？為什麼？合理的回答可以是“是，如果我們将多項式看作一種純粹的數學函數；但又不是，如果隻是将多項式看作一種文法形式”。第二個多項式在代數上等價于一個y的多項式，其系數是x的多項式。我們的系統将應認定這一情況嗎，或者不認定？進一步說，表示一個多項式的方式可以有很多種—例如，将其作為因子的乘積，或者（對于單變元多項式）作為一組根，或者作為多項式在些特定集合裡各個點處的值的清單。我們可以使一點手段以避免這些問題。現在我們确定，在這一代數演算系統裡，一個“多項式”就是一種特殊的文法形式，而不是在其之下的數學意義。

現在必須進一步去考慮怎樣做多項式算術。在這個簡單的系統裡，我們将僅僅考慮加法和乘法。進一步說，我們還強制性地要求兩個參與運算的多項式具有相同的未定元。

下面将根據我們已經熟悉的資料抽象的一套方式，開始設計這個系統。多項式将用一種稱為poly的資料結構表示，它由一個變量和一組項組成。我們假定已有選擇函數variable 和term-list，用于從一個多項式中提取相應的部分。還有一個構造函數make-poly，從給定變量和項表構造出一個多項式。一個變量也就是一個符号，是以我們可以用2.3.2節的same-variable?過程做變量的比較。下面過程定義多項式的加法和乘法：

define (add-poly p1 p2)
  (if (same-variable? (variable p1) (variable p2))
      (make-poly (variable p1)
                 (add-terms (term-list p1)
                            (term-list p2)))
      (error "Polys not in same var -- ADD-POLY"
             (list p1 p2))))
(define (mul-poly p1 p2)
  (if (same-variable? (variable p1) (variable p2))
      (make-poly (variable p1)
                 (mul-terms (term-list p1)
                            (term-list p2)))
      (error "Polys not in same var -- MUL-POLY"
             (list p1 p2))))           

為了将多項式結合到前面建立起來的通用算術系統裡，我們需要為其提供類型标志。這裡采用标志polynomial，并将适合用于帶标志多項式的操作安裝到操作表格裡。我們将所有代碼都嵌入完成多項式包的安裝過程中，與在2.5.1節裡采用的方式類似：

(define (install-polynomial-package)
  ;; internal procedures
  ;; representation of poly
  (define (make-poly variable term-list)
    (cons variable term-list))
  (define (variable p) (car p))
  (define (term-list p) (cdr p))
  <過程 same-variable? 和 variable? 取自2.3.2節>
  ;; representation of terms and term lists
  <過程 adjoin-term ...coeff 在下面定義>
  (define (add-poly p1 p2) ...)
  <add-poly 使用的過程>
  (define (mul-poly p1 p2) ...)
  <mul-poly 使用的過程>
  ;; interface to rest of the system
  (define (tag p) (attach-tag 'polynomial p))
  (put 'add ?polynomial polynomial) 
       (lambda (p1 p2) (tag (add-poly p1 p2))))
  (put 'mul ?polynomial polynomial) 
       (lambda (p1 p2) (tag (mul-poly p1 p2))))
  (put 'make 'polynomial
       (lambda (var terms) (tag (make-poly var terms))))
  'done)           

多項式加法通過一項項的相加完成，同次的項（即，具有同樣未定元幂次的項）必須歸并到一起。完成這件事的方式是建立一個同次的新項，其系數是兩個項的系數之和。僅僅出現在一個求和多項式中的項就直接累積到正在構造的多項式裡。

為了能完成對于項表的操作，我們假定有一個構造函數the-empty-termlist，它傳回一個空的項表，還有一個構造函數adjoin-term将一個新項加入一個項表裡。我們還假定有一個謂詞empty-termlist?，可用于檢查一個項表是否為空；選擇函數first-term提取出一個項表中最高次數的項，選擇函數rest-terms傳回除最高次項之外的其他項的表。為了能對項進行各種操作，我們假定已經有一個構造函數make-term，它從給定的次數和系數構造出一個項；選擇函數order和coeff分别傳回一個項的次數和系數。這些操作使我們可以将項和項表都看成資料抽象，其具體實作就可以另行單獨考慮了。

下面是一個過程，它從兩個需要求和的多項式構造起一個項表：

(define (add-terms L1 L2)
  (cond ((empty-termlist? L1) L2)
        ((empty-termlist? L2) L1)
        (else
         (let ((t1 (first-term L1)) (t2 (first-term L2)))
           (cond ((> (order t1) (order t2))
                  (adjoin-term
                   t1 (add-terms (rest-terms L1) L2)))
                 ((< (order t1) (order t2))
                  (adjoin-term
                   t2 (add-terms L1 (rest-terms L2))))
                 (else
                  (adjoin-term
                   (make-term (order t1)
                              (add (coeff t1) (coeff t2)))
                   (add-terms (rest-terms L1)
                              (rest-terms L2)))))))))           

在這裡需要注意的最重要的地方是，我們采用了通用型的加法過程add去求需要歸并的項的系數之和。這樣做有一個特别有利的後果，下面就會看到。

為了乘起兩個項表，我們用第一個表中的每個項去乘另一表中所有的項，通過反複應用mul-term-by-all-terms（這個過程用一個給定的項去乘一個項表裡的各個項）完成項表的乘法。這樣得到的結果項表（對于第一個表的每個項各有一個表）通過求和積累起來。乘起兩個項形成一個新項的方式是求出兩個因子的次數之和作為結果項的次數，求出兩個因子的系數的乘積作為結果項的系數：

(define (mul-terms L1 L2)
  (if (empty-termlist? L1)
      (the-empty-termlist)
      (add-terms (mul-term-by-all-terms (first-term L1) L2)
                 (mul-terms (rest-terms L1) L2))))
(define (mul-term-by-all-terms t1 L)
  (if (empty-termlist? L)
      (the-empty-termlist)
      (let ((t2 (first-term L)))
        (adjoin-term
         (make-term (+ (order t1) (order t2))
                    (mul (coeff t1) (coeff t2)))
         (mul-term-by-all-terms t1 (rest-terms L))))))           

這些也就是多項式加法和乘法的全部了。請注意，因為我們這裡的操作都是基于通用型過程add和mul描述的，是以這個多項式包将自動地能夠處理任何系數類型，隻要它是這裡的通用算術程式包能夠處理的。如果我們還把2.5.2節所讨論的強制機制也包括進來，那麼我們也就自動地有了能夠處理不同系數類型的多項式操作的能力，例如

由于我們已經把多項式的求和、求乘積的過程add-poly和mul-poly作為針對類型polynomial的操作，安裝進通用算術系統的add和mul操作裡，這樣得到的系統将能自動處理如下的多項式操作：

能夠完成此事的原因是，當系統試圖去歸并系數時，它将通過add和mul進行分派。由于這時的系數本身也是多項式（y的多項式），它們将通過使用add-poly和mul-poly完成組合。這樣就産生出一種“資料導向的遞歸”，舉例來說，在這裡，對mul-poly的調用中還會遞歸地調用mul-poly，以便去求系數的乘積。如果系數的系數仍然是多項式（在三個變元的多項式中可能出現這種情況），資料導向就會保證這一系統仍能進入另一層遞歸調用，并能這樣根據被處理資料的結構進入任意深度的遞歸調用。

項表的表示

我們最後面臨的工作，就是需要為項表實作一種很好的表示形式。從作用上看，一個項表就是一個以項的次數作為鍵值的系數集合，是以，任何能夠用于有效表示集合的方法（見2.2.3節的讨論）都可以用于完成這一工作。但另一方面，我們所用的過程add-terms和mul-terms都以順序方式進行通路，按照從最高次項到最低次項的順序，是以應該考慮采用某種有序表表示。

我們應該如何構造表示項表的表結構呢？有一個需要考慮的因素是可能需要操作的多項式的“密度”。一個多項式稱為稠密的，如果它大部分次數的項都具有非0系數。如果一個多項式有許多系數為0的項，那麼就稱它是稀疏的。例如：

A :   x5＋2x4＋3x2－2x－5           

是稠密的，而

B :   x100＋2x2＋1           

是稀疏的。

對于稠密多項式而言，項表的最有效表示方式就是直接采用其系數的表。例如，上面的多項式A可以很好地表示為（1 2 0 3 -2 -5）。在這種表示中，一個項的次數也就是從這個項開始的子表的長度減1124。對于像B那樣的稀疏多項式，這種表示将變得十分可怕，因為它将是一個很大的幾乎全都是0值的表，其中零零落落地點綴着幾個非0項。對于稀疏多項式有一種更合理方式，那就是将它們表示為非0項的表，表中的每一項包含着多項式裡的一個次數和對應于這個次數的系數。按照這種模式，多項式B可以有效地表示為（（100 1）（2 2）（0 1））。由于被操作的大部分多項式運算都是稀疏多項式，我們采用後一種方式。現在假定項表被表示為項的表，按照從最高次到最低次的順序安排。一旦我們做出了這一決定，為項表實作選擇函數和構造函數就已經直截了當了。

(define (adjoin-term term term-list)
  (if (=zero? (coeff term))
      term-list
      (cons term term-list)))
(define (the-empty-termlist) '())
(define (first-term term-list) (car term-list))
(define (rest-terms term-list) (cdr term-list))
(define (empty-termlist? term-list) (null? term-list))
(define (make-term order coeff) (list order coeff))
(define (order term) (car term))
(define (coeff term) (cadr term))           

這裡的＝zero?在練習2.80中定義（另見下面練習2.87）。

多項式程式包的使用者可以通過下面過程建立多項式：

(define (make-polynomial var terms)
  ((get 'make 'polynomial) var terms))           

練習2.87 請在通用算術包中為多項式安裝＝zero?，這将使adjoin-term也能對系數本身也是多項式的多項式使用。

練習2.88 請擴充多項式系統，加上多項式的減法。（提示：你可能發現定義一個通用的求負操作非常有用。）

練習2.89 請定義一些過程，實作上面讨論的适宜稠密多項式的項表表示。

練習2.90 假定我們希望有一個多項式系統，它應該對稠密多項式和稀疏多項式都非常有效。一種途徑就是在我們的系統裡同時允許兩種表示形式。這時的情況類似于2.4節複數的例子，那裡同時允許采用直角坐标表示和極坐标表示。為了完成這一工作，我們必須區分不同的項表類型，并将針對項表的操作通用化。請重新設計這個多項式系統，實作這種推廣。這将是一項需要付出很多努力的工作，而不是一個局部修改。

練習2.91 一個單變元多項式可以除以另一個多項式，産生出一個商式和一個餘式。例如：

除法可以通過長除完成。也就是說，用被除式的最高次項除以除式的最高次項，得到商式的第一項；而後用這個結果乘以除式，并從被除式中減去這個乘積。剩下的工作就是用減後得到的差作為新的被除式，以便産生出随後的結果。當除式的次數超過被除式的次數時結束，将此時的被除式作為餘式。還有，如果被除式就是0，那麼就傳回0作為商和餘式。

我們可以基于add-poly和mul-poly的模型，設計出一個除法過程div-poly。這一過程首先檢查兩個多項式是否具有相同的變元，如果是的話就剝去這一變元，将問題送給過程div-terms，它執行項表上的除法運算。div-poly最後将變元重新附加到div-terms傳回的結果上。将div-terms設計為同時計算出除法的商式和餘式是比較友善的。div-terms可以以兩個表為參數，傳回一個商式的表和一個餘式的表。

請完成下面div-terms的定義，填充其中空缺的表達式，并基于它實作div-poly。該過程應該以兩個多項式為參數，傳回一個包含商和餘式多項式的表。

(define (div-terms L1 L2)
  (if (empty-termlist? L1)
      (list (the-empty-termlist) (the-empty-termlist))
      (let ((t1 (first-term L1))
            (t2 (first-term L2)))
        (if (> (order t2) (order t1))
            (list (the-empty-termlist) L1)
            (let ((new-c (div (coeff t1) (coeff t2)))
                  (new-o (- (order t1) (order t2))))
              (let ((rest-of-result
                     <遞歸地計算結果的其餘部分>
                     ))
                <形成完整的結果>
                ))))))           

符号代數中類型的層次結構

我們的多項式系統顯示出，一種類型（多項式）的對象事實上可以是一個複雜的對象，又以許多不同類型的對象作為其組成部分。這種情況并不會給定義通用型操作增加任何實際困難。我們需要做的就是針對這種複合對象的各個部分的操作，并安裝好适當的通用型過程。事實上，我們可以看到多項式形成了一類“遞歸資料抽象”，因為多項式的某些部分本身也可能是多項式。我們的通用型操作和資料導向的程式設計風格完全可以處理這種複雜性，這裡并沒有多少困難。

但另一方面，多項式代數也是這樣的一個系統，其中的資料類型不能自然地安排到一個類型塔裡。例如，在這裡可能有x的多項式，其系數是y的多項式；也完全可能有y的多項式，其系數是x的多項式。這些類型中沒有哪個類型自然地位于另一類型的“上面”，然而我們卻常常需要去求不同集合的成員之和。有幾種方式可以完成這件事情。一個可能性就是将一個多項式變換到另一個多項式的類型，這可以通過展開并重新安排多項式裡的項，使兩個多項式都具有同樣的主變元。也可以通過對變元的排序，在其中強行加入一個類型塔結構，并且永遠把所有的多項式都變換到一種“規範形式”，使具有最高優先級的變元成為主變元，将優先級較低的變元藏在系數裡面。這種政策工作的相當好，但是，在做這種變換時，有可能毫無必要地擴大了多項式，使它更難讀，也可能操作起來的效率更低。塔形政策在這個領域中确實不大自然，對于另一些領域也是一樣，如果在那裡使用者可以動态地通過已有類型的各種組合形式引進新類型。這樣的例子如三角函數、幂級數和積分。

如果說在設計大型代數演算系統時，對于強制的控制會變成一個很嚴重的問題，那完全不應該感到奇怪。這種系統裡的大部分複雜性都牽涉多個類型之間的關系。确實，公平地說，我們到現在還沒有完全了解強制。事實上，我們還沒有完全了解類型的概念。但無論如何，已知的東西已經為我們提供了支援大型系統設計的強有力的結構化和子產品化原理。

練習2.92 通過加入強制性的變量序擴充多項式程式包，使多項式的加法和乘法能對具有不同變量的多項式進行。（這絕不簡單！）

擴充練習：有理函數

我們可以擴充前面已經做出的通用算術系統，将有理函數也包含進來。有理函數也就是“分式”，其分子和分母都是多項式，例如：

這個系統應該能做有理函數的加減乘除，并可以完成下面的計算：

（這裡的和已經經過了簡化，删除了公因子。正常的“交叉乘法”得到的将是一個4次多項式的分子和5次多項式的分母。）

修改前面的有理數程式包，使它能使用通用型操作，就能完成我們希望做的事情，除了無法将分式化簡到最簡形式之外。

練習2.93 請修改有理數算術包，采用通用型操作，但在其中改寫make-rat，使它并不企圖去将分式化簡到最簡形式。對下面兩個多項式調用make-rational做出一個有理函數，以便檢查你的系統：

(define p1 (make-polynomial 'x ?(2 1)(0 1))))
(define p2 (make-polynomial 'x ?(3 1)(0 1))))
(define rf (make-rational p2 p1))           

現在用add将rf與它自己相加。你會看到這個加法過程不能将分式化簡到最簡形式。

我們可以用與前面針對整數工作時的同樣想法，将分子和分母都是多項式的分式簡化到最簡形式：修改make-rat，将分子和分母都除以它們的最大公因子。“最大公因子”的概念對于多項式也是有意義的。事實上，我們也可以用與整數的歐幾裡得算法本質上相同的算法求出兩個多項式的GCD（最大公因子）126。對于整數的算法是：

(define (gcd a b)
  (if (= b 0)
      a
      (gcd b (remainder a b))))           

利用它，再做一點非常明顯的修改，就可以定義出一個對項表工作的GCD操作：

(define (gcd-terms a b)
  (if (empty-termlist? b)
      a
      (gcd-terms b (remainder-terms a b))))           

其中的remainder-terms提取出由項表除法操作div-terms傳回的表裡的餘式成分，該操作在練習2.91中實作。

練習2.94 利用div-terms實作過程remainder-terms，并用它定義出上面的gcd-terms。現在寫出一個過程gcd-poly，它能計算出兩個多項式的多項式GCD（如果兩個多項式的變元不同，這個過程應該報告錯誤）。在系統中安裝通用型操作greatest-common-divisor，使得遇到多項式時，它能歸約到gcd-poly，對于正常的數能歸約到正常的gcd。作為試驗，請做：

(define p1 (make-polynomial 'x ?(4 1) (3 -1) (2 -2) (1 2))))
(define p2 (make-polynomial 'x ?(3 1) (1 -1))))
(greatest-common-divisor p1 p2)           

并用手工檢查得到的結果。

練習2.95 請定義多項式P1、P2和P3：

P1 : x2－2x＋1 P2 : 11x2＋7 P3 : 13x＋5

現在定義Q1為P1和P2的乘積，定義Q2為P1和P3的乘積，而後用greatest-common-divisor（練習2.94）求出Q1和Q2的GCD。請注意得到的回答與P1并不一樣。這個例子将非整數操作引進了計算過程，進而引起了GCD算法的困難。要了解這裡發生了什麼，請試着手工追蹤gcd-terms在計算GCD或者做除法時的情況。

如果我們對于GCD算法采用下面的修改，就可以解決練習2.95揭示出的問題（這隻能對整數系數的多項式使用）。在GCD計算中執行任何多項式除法之前，我們先将被除式乘以一個整數的常數因子，選擇的方式是保證在除的過程中不出現分數。這樣得到的回答将比實際的GCD多出一個整的常數因子，但它不會在将有理函數化簡到最簡形式的過程中造成任何問題。由于将用這個GCD去除分子和分母，是以這個常數因子會被消除掉。

說得更精确些，如果P和Q都是多項式，令O1是P的次數（P的最高次項的次數），令O2是Q的次數，令c是Q的首項系數。可以證明，如果我們給P乘上一個整數化因子c1＋O1－O2，得到的多項式用div-terms算法除以Q将不會引進任何分數。将被除式乘上這樣的常數後除以除式，這種操作在某些地方稱為P對于Q的僞除，這樣除後得到的餘式也被稱為僞餘。

練習2.96

a) 請實作過程pseudoremainder-terms，它就像是remainder-terms，但是像上面所描述的那樣，在調用div-terms之前，先将被除式乘了整數化因子。請修改gcd-terms使之能使用pseudoremainder-terms，并檢驗現在greatest-common-divisor能否對練習2.95的例子産生出一個整系數的答案。

b) 現在的GCD保證能得到整系數，但它們将比P1的系數大，請修改gcd-terms使它能從答案的所有系數中删除公因子，方法是将這些系數都除以它們的（整數）最大公約數。

至此我們已經弄清了如何将一個有理函數化簡到最簡形式：

• 用取自練習2.96的gcd-terms版本計算出分子和分母的GCD；
• 在你得到了這個GCD後，在用GCD去除分子和分母之前，先将它們都乘以同一個整數化因子，以使除以這個GCD不會引進任何非整數系數。作為這個因子，你可以使用得到的GCD的首項系數的1＋O1－O2次幂。其中O2是這個GCD的次數，O1是分子與分母的次數中大的那一個。這将保證用這個GCD去除分子和分母不會引進任何分數。
• 這一操作得到的結果将是具有整系數的分子和分母。它們的系數通常會由于整數化因子而變得非常大。是以最後一步是去除這個多餘的因子，為此需要首先計算出分子和分母中所有系數的（整數）最大公約數，而後除去這個公約數。

練習2.97

a) 請将這一算法實作為過程reduce-terms，它以兩個項表n和d為參數，傳回一個包含nn和dd的表，它們分别是由n和d通過上面描述的算法簡化而得到的最簡形式。另請寫出一個與add-poly類似的過程reduce-poly，它檢查兩個多項式是否具有同樣變元。如果是的話，reduce-poly就剝去其中變元，并将問題交給reduce-terms，最後為reduce-terms傳回的表裡的兩個項表重新附加上變元。

b) 請定義一個類似于reduce-terms的過程，它完成的工作就像是make-rat對整數做的事情：

(define (reduce-integers n d)
  (let ((g (gcd n d)))
    (list (/ n g) (/ d g))))           

再将reduce定義為一個通用型操作，它調用apply-generic完成到reduce-poly（對于polynomial參數）或者到reduce-integers（對scheme-number參數）的分派。你可以很容易讓有理數算術包将分式簡化到最簡形式，采用的方式就是讓make-rat在組合給定分子和分母，做出有理數之前也調用reduce。這一系統現在就能處理整數或者多項式的有理表達式了。為測試你的程式，請首先試驗下面的擴充練習：

(define p1 (make-polynomial 'x ?(1 1)(0 1))))
(define p2 (make-polynomial 'x ?(3 1)(0 -1))))
(define p3 (make-polynomial 'x ?(1 1))))
(define p4 (make-polynomial 'x ?(2 1)(0 -1))))
(define rf1 (make-rational p1 p2))
(define rf2 (make-rational p3 p4))
(add rf1 rf2)           

看看能否得到正确結果，結果是否正确地化簡為最簡形式。

GCD計算是所有需要完成有理函數操作的系統的核心。上面所使用的算法雖然在數學上直截了當，但卻異常低效。低效的部分原因在于大量的除法操作，部分在于由僞除産生的巨大的中間系數。在開發代數演算系統的領域中，一個很活躍問題就是設計計算多項式GCD的更好算法。