計算機科學叢書 點選檢視第二章
計算機程式的構造和解釋（原書第2版）典藏版
Structure and Interpretation of Computer Programs，Second Edition
哈羅德阿貝爾森（Harold Abelson）
[美] 傑拉爾德傑伊薩斯曼（Gerald Jay Sussman） 著
朱莉薩斯曼（Julie Sussman）
裘宗燕 譯
第1章 構造過程抽象
心智的活動，除了盡力産生各種簡單的認識之外，主要表現在如下三個方面：1）将若幹簡單認識組合為一個複合認識，由此産生出各種複雜的認識。2）将兩個認識放在一起對照，不管它們如何簡單或者複雜，在這樣做時并不将它們合而為一。由此得到有關它們的互相關系的認識。3）将有關認識與那些在實際中和它們同在的所有其他認識隔離開，這就是抽象，所有具有普遍性的認識都是這樣得到的。
John Locke, An Essay Concerning Human Vnderstanding
（有關人類了解的随筆，1690）
我們準備學習的是有關計算過程的知識。計算過程是存在于計算機裡的一類抽象事物，在其演化程序中，這些過程會去操作一些被稱為資料的抽象事物。人們建立出一些稱為程式的規則模式，以指導這類過程的進行。從作用上看，就像是我們在通過自己的寫作魔力去控制計算機裡的精靈似的。
一個計算過程确實很像一種神靈的巫術，它看不見也摸不到，根本就不是由物質組成的。然而它卻又是非常真實的，可以完成某些智力性的工作。它可以回答提問，可以通過在銀行裡支付現金或者在工廠裡操縱機器人等等方式影響這個世界。我們用于指揮這種過程的程式就像是巫師的咒語，它們是用一些詭秘而深奧的程式設計語言，通過符号表達式的形式精心編排而成，它們描述了我們希望相應的計算過程去完成的工作。
在正常工作的計算機裡，一個計算過程将精密而準确地執行相應的程式。這樣，初學程式設計的人們就像巫師的徒弟們那樣，必須學習如何去了解和預期他們所發出的咒語的效果。程式裡即使有一點小錯誤（常常被稱為程式錯誤（bug）或者故障（glitch）），也可能産生複雜而無法預料的後果。
幸運的是，學習程式的危險性遠遠小于學習巫術，因為我們要去控制的神靈以一種很安全的方式被限制着。而真實的程式設計則需要極度細心，需要經驗和智慧。例如，在一個計算機輔助設計系統裡的一點小毛病，就可能導緻一架飛機或者一座水壩的災難性損毀，或者一個工業機器人的自我破壞。
軟體工程大師們能組織好自己的程式，使自己能合理地确信這些程式所産生的計算過程将能完成預期的工作。他們可以事先看到自己系統的行為方式，知道如何去構造這些程式，使其中出現的意外問題不會導緻災難性的後果。而且，在發生了這種問題時，他們也能排除程式中的錯誤。設計良好的計算系統就像設計良好的汽車或者核反應堆一樣，具有某種子產品化的設計，其中的各個部分都可以獨立地構造、替換、排除錯誤。
用Lisp程式設計
為了描述這類計算過程，我們需要有一種适用的語言。我們将為此使用程式設計語言Lisp。正如人們每天用自然語言（如英語、法語或日語等）表述自己的想法，用數學形式的記法描述定量的現象一樣，我們将要用Lisp表述過程性的思想。Lisp是20世紀50年代後期發明的一種記法形式，是為了能對某種特定形式的邏輯表達式（稱為遞歸方程）的使用做推理。遞歸方程可以作為計算的模型。這一語言是由John McCarthy設計的，基于他的論文“Recursive Functions of Symbolic Expressions and Their Computation by Machine”（符号表達式的遞歸函數及其機械計算，McCarthy 1960）。
雖然在開始時，McCarthy是想以Lisp作為一種數學記述形式，但它确實是一種實用的程式設計語言。一個Lisp解釋器就像是一台機器，它能實作用Lisp語言描述的計算過程。第一個Lisp解釋器是McCarthy在MIT電子研究實驗室的人工智能組和MIT計算中心裡他的同僚和學生的幫助下實作的1。Lisp的名字來自表處理（LISt Processing），其設計是為了提供符号計算的能力，以便能用于解決一些程式設計問題，例如代數表達式的符号微分和積分。它包含了适用于這類目的的一些新資料對象，稱為原子和表，這是它與那一時代的所有其他語言之間最明顯的不同之處。
Lisp并不是一個刻意的設計努力的結果，它以一種試驗性的非正式的方式不斷演化，以滿足使用者的需要和實際實作的各種考慮。Lisp的這種非官方演化持續了許多年，Lisp使用者社團具有抵制制定這一語言的“官方”定義企圖的傳統。這種演化方式以及語言初始概念的靈活和優美，使得Lisp成為今天還在廣泛使用的曆史第二悠久的語言（隻有Fortran比它更老）。這一語言還在不斷調整，以便去包容有關程式設計的最新思想。正因為這樣，今天的Lisp已經形成了一族方言，它們共享着初始語言的大部分特征，也可能有這樣或那樣的重要差異。用于本書的Lisp方言名為Scheme2。
由于Lisp的試驗性質以及強調符号操作的特點，開始時的這個語言對于數值計算而言是很低效的，至少與Fortran比較時是這樣。經過這麼多年的發展，人們已經開發出了Lisp編譯器，它們可以将程式翻譯為機器代碼，這樣的代碼能相當高效地完成各種數值計算。Lisp已經可以非常有效地用于一些特殊的應用領域3。雖然Lisp還沒有完全戰勝有關它特别低效的诋毀，但它現在已被用于許多性能并不是最重要考慮因素的應用領域。例如，Lisp已經成為作業系統外殼語言的一種選擇，作為編輯器和計算機輔助設計系統的擴充語言等等。
既然Lisp并不是一種主流語言，我們為什麼要用它作為讨論程式設計的基礎呢？這是因為，這一語言具有許多獨有的特征，這些特征使它成為研究重要程式的設計、構造，以及各種資料結構，并将其關聯于支援它們的語言特征的一種極佳媒介。這些特征之中最重要的就是：計算過程的Lisp描述（稱為過程）本身又可以作為Lisp的資料來表示和操作。這一事實的重要性在于，現存的許多威力強大的程式設計技術，都依賴于填平在“被動的”資料和“主動的”過程之間的傳統劃分。正如我們将要看到的，Lisp可以将過程作為資料進行處理的靈活性，使它成為探索這些技術的最友善的現存語言之一。能将過程表示為資料的能力，也使Lisp成為編寫那些必須将其他程式當作資料去操作的程式的最佳語言，例如支援計算機語言的解釋器和編譯器。除了這些考慮之外，用Lisp程式設計本身也是極其有趣的。
1.1 程式設計的基本元素
一個強有力的程式設計語言，不僅是一種指揮計算機執行任務的方式，它還應該成為一種架構，使我們能夠在其中組織自己有關計算過程的思想。這樣，當我們描述一個語言時，就需要将注意力特别放在這一語言所提供的，能夠将簡單的認識組合起來形成更複雜認識的方法方面。每一種強有力的語言都為此提供了三種機制：
- 基本表達形式，用于表示語言所關心的最簡單的個體。
- 組合的方法，通過它們可以從較簡單的東西出發構造出複合的元素。
- 抽象的方法，通過它們可以為複合對象命名，并将它們當作單元去操作。
在程式設計中，我們需要處理兩類要素：過程和資料（以後讀者将會發現，它們實際上并不是這樣嚴格分離的）。非形式地說，資料是一種我們希望去操作的“東西”，而過程就是有關操作這些資料的規則的描述。這樣，任何強有力的程式設計語言都必須能表述基本的資料和基本的過程，還需要提供對過程和資料進行組合和抽象的方法。
本章隻處理簡單的數值資料，這就使我們可以把注意力集中到過程構造的規則方面4。在随後幾章裡我們将會看到，用于構造過程的這些規則同樣也可以用于操作各種資料。
1.1.1 表達式
開始做程式設計，最簡單方式就是去觀看一些與Lisp方言Scheme解釋器互動的典型執行個體。設想你坐在一台計算機的終端前，用鍵盤輸入了一個表達式，解釋器的響應就是将它對這一表達式的求值結果顯示出來。
你可以鍵入的一種基本表達式就是數（更準确地說，你鍵入的是由數字組成的表達式，它表示的是以10作為基數的數）。如果你給Lisp一個數
486
解釋器的響應是列印出
可以用表示基本過程的表達形式（例如＋或者 *），将表示數的表達式組合起來，形成複合表達式，以表示求要把有關過程應用于這些數。例如：
(+ 137 349)
486
(- 1000 334)
666
(* 5 99)
495
(/ 10 5)
2
(+ 2.7 10)
12.7 像上面這樣的表達式稱為組合式，其構成方式就是用一對括号括起一些表達式，形成一個表，用于表示一個過程應用。在表裡最左的元素稱為運算符，其他元素都稱為運算對象。要得到這種組合式的值，采用的方式就是将由運算符所刻畫的過程應用于有關的實際參數，而所謂實際參數也就是那些運算對象的值。
将運算符放在所有運算對象左邊，這種形式稱為字首表示。剛開始看到這種表示時會感到有些不習慣，因為它與正常數學表示差别很大。然而字首表示也有一些優點，其中之一就是它完全适用于可能帶有任意個實參的過程，例如在下面執行個體中的情況：
(+ 21 35 12 7)
75
(* 25 4 12)
1200 在這裡不會出現歧義，因為運算符總是最左邊的元素，而整個表達式的範圍也由括号界定。
字首表示的第二個優點是它可以直接擴充，允許出現組合式嵌套的情況，也就是說，允許組合式的元素本身又是組合式：
(+ (* 3 5) (- 10 6))
19 原則上講，對于這種嵌套的深度，以及Lisp解釋器可以求值的表達式的整體複雜性，都沒有任何限制。倒是我們自己有可能被一些并不很複雜的表達式搞糊塗，例如：
(+ (* 3 (+ (* 2 4) (+ 3 5))) (+ (- 10 7) 6)) 對于這個表達式，解釋器可以馬上求值出57。将上述表達式寫成下面的形式有助于閱讀：
(+ (* 3
(+ (* 2 4)
(+ 3 5)))
(+ (- 10 7)
6)) 這就是遵循一種稱為美觀列印的格式規則。按照這種規則，在寫一個很長的組合式時，我們令其中的各個運算對象垂直對齊。這樣縮格排列的結果能很好地顯示出表達式的結構。
即使對于非常複雜的表達式，解釋器也總是按同樣的基本循環運作：從終端讀入一個表達式，對這個表達式求值，而後列印出得到的結果。這種運作模式常常被人們說成是解釋器運作在一個讀入－求值－列印循環之中。請特别注意，在這裡完全沒有必要顯式地去要求解釋器列印表達式的值7。
1.1.2 命名和環境
程式設計語言中一個必不可少的方面，就是它需要提供一種通過名字去使用計算對象的方式。我們将名字辨別符稱為變量，它的值也就是它所對應的那個對象。
在Lisp方言Scheme裡，給事物命名通過define（定義）的方式完成，輸入：
(define size 2)
會導緻解釋器将值2與名字size相關聯8。一旦名字size與2關聯之後，我們就可以通過這個名字去引用值2了：
size
2
(* 5 size)
10 下面是另外幾個使用define的例子：
(define pi 3.14159)
(define radius 10)
(* pi (* radius radius))
314.159
(define circumference (* 2 pi radius))
circumference
62.8318 define是我們所用的語言裡最簡單的抽象方法，它允許我們用一個簡單的名字去引用一個組合運算的結果，例如上面算出的circumference。一般而言，計算得到的對象完全可以具有非常複雜的結構，如果每次需要使用它們時，都必須記住并重複地寫出它們的細節，那将是極端不友善的事情。實際上，構造一個複雜的程式，也就是為了去一步步地建立出越來越複雜的計算性對象。解釋器使這種逐漸的程式構造過程變得非常友善，因為我們可以通過一系列互動式動作，逐漸建立起所需要的名字－對象關聯。這種特征鼓勵人們采用遞增的方式去開發和調試程式。在很大程度上，這一情況也出于另一個事實，那就是，一個Lisp程式通常總是由一大批相對簡單的過程組成的。
應該看到，我們可以将值與符号關聯，而後又能提取出這些值，這意味着解釋器必須維護某種存儲能力，以便保持有關的名字-值對偶的軌迹。這種存儲被稱為環境（更精确地說，是全局環境，因為我們以後将看到，在一個計算過程中完全可能涉及若幹不同環境）。
1.1.3 組合式的求值
本章的一個目标，就是要把與過程性思維有關的各種問題隔離出來。現在讓我們考慮組合式的求值問題。解釋器本身就是按照下面過程工作的。
- 要求值一個組合式，做下面的事情：
1) 求值該組合式的各個子表達式。
2) 将作為最左子表達式（運算符）的值的那個過程應用于相應的實際參數，所謂實際參數也就是其他子表達式（運算對象）的值。
即使是一條這樣簡單的規則，也顯示出計算過程裡的一些具有普遍性的重要問題。首先，由上面的第一步可以看到，為了實作對一個組合式的求值過程，我們必須先對組合式裡的每個元素執行同樣的求值過程。是以，在性質上，這一求值過程是遞歸的，也就是說，它在自己的工作步驟中，包含着調用這個規則本身的需要。
在這裡應該特别注意，采用遞歸的思想可以多麼簡潔地描述深度嵌套的情況。如果不用遞歸，我們就需要把這種情況看成相當複雜的計算過程。例如，對下清單達式求值：
(* (+ 2 (* 4 6))
(+ 3 5 7)) 需要将求值規則應用于4個不同的組合式。如圖1-1中所示，我們可以采用一棵樹的形式，用圖形表示這一組合式的求值過程，其中的每個組合式用一個帶分支的結點表示，由它發出的分支對應于組合式裡的運算符和各個運算對象。終端結點（即那些不再發出分支的結點）表示的是運算符或者數值。以樹的觀點看這種求值過程，可以設想那些運算對象的值向上穿行，從終端結點開始，而後在越來越高的層次中組合起來。一般而言，我們應該把遞歸看作一種處理層次性結構的（像樹這樣的對象）極強有力的技術。事實上，“值向上穿行”形式的求值形式是一類更一般的計算過程的一個例子，這種計算過程稱為樹形積累。
進一步的觀察告訴我們，反複地應用第一個步驟，總可以把我們帶到求值中的某一點，在這裡遇到的不是組合式而是基本表達式，例如數、内部運算符或者其他名字。處理這些基礎情況的方式如下規定：
- 數的值就是它們所表示的數值。
- 内部運算符的值就是能完成相應操作的機器指令序列。
- 其他名字的值就是在環境中關聯于這一名字的那個對象。
我們可以将第二種規定看作是第三種規定的特殊情況，為此隻需将像＋和 * 一類的運算符也包含在全局環境裡，并将相應的指令序列作為與之關聯的“值”。對于初學者，應該指出的關鍵一點是，環境所扮演的角色就是用于确定表達式中各個符号的意義。在如Lisp這樣的互動式語言裡，如果沒有關于有關環境的任何資訊，那麼說例如表達式（＋ x 1）的值是毫無意義的，因為需要有環境為符号 x 提供意義（甚至需要它為符号＋提供意義）。正如我們将要在第3章看到的，環境是具有普遍性的概念，它為求值過程的進行提供了一種上下文，對于我們了解程式的執行起着極其重要的作用。
請注意，上面給出的求值規則裡并沒有處理定義。例如，對（define x 3）的求值并不是将define應用于它的兩個實際參數：其中的一個是符号 x 的值，另一個是3。這是因為define的作用就是為 x 關聯一個值（也就是說，（define x 3）并不是一個組合式）。
一般性求值規則的這種例外稱為特殊形式，define是至今我們已經看到的唯一的一種特殊形式，下面還将看到另外一些特殊形式。每個特殊形式都有其自身的求值規則，各種不同種類的表達式（每種有着與之相關聯的求值規則）組成了程式設計語言的文法形式。與大部分其他程式設計語言相比，Lisp的文法非常簡單。也就是說，對各種表達式的求值規則可以描述為一個簡單的通用規則和一組針對不多的特殊形式的專門規則。
1.1.4 複合過程
我們已經看到了Lisp裡的某些元素，它們必然也會出現在任何一種強有力的程式設計語言裡。這些東西包括：
- 數和算術運算是基本的資料和過程。
- 組合式的嵌套提供了一種組織起多個操作的方法。
- 定義是一種受限的抽象手段，它為名字關聯相應的值。
現在我們來學習過程定義，這是一種威力更加強大的抽象技術，通過它可以為複合操作提供名字，而後就可以将這樣的操作作為一個單元使用了。
現在我們要考察如何表述“平方”的想法。我們可能想說“求某個東西的平方，就是用它自身去乘以它自身”。在這個語言裡，這件事情應該表述為：
(define (square x) (* x x)) 可以按如下方式了解這一描述：
這樣我們就有了一個複合過程，給它取的名字是square。這一過程表示的是将一個東西乘以它自身的操作。被乘的東西也給定了一個局部名字x，它扮演着與自然語言裡代詞同樣的角色。求值這一定義的結果是建立起一個複合過程，并将它關聯于名字square。
過程定義的一般形式是：
其中
是一個符号，過程定義将在環境中關聯于這個符号。
（形式參數）是一些名字，它們用在過程體中，用于表示過程應用時與它們對應的各個實際參數。
是一個表達式，在應用這一過程時，這一表達式中的形式參數将用與之對應的實際參數取代，對這樣取代後的表達式的求值，産生出這個過程應用的值。
和
被放在一對括号裡，成為一組，就像實際調用被定義過程時的寫法。
定義好square之後，我們就可以使用它了：
(square 21)
441
(square (+ 2 5))
49
(square (square 3))
81 我們還可以用square作為基本構件去定義其他過程。例如，x2＋y2可以表述為：
(+ (square x) (square y)) 現在我們很容易定義一個過程sum-of-squares，給它兩個數作為實際參數，讓它産生這兩個數的平方和：
(define (sum-of-squares x y)
(+ (square x) (square y)))
(sum-of-squares 3 4)
25 現在我們又可以用sum-of-squares作為構件，進一步去構造其他過程：
(define (f a)
(sum-of-squares (+ a 1) (* a 2)))
(f 5)
136 複合過程的使用方式與基本過程完全一樣。實際上，如果人們隻看上面sum-of-squares的定義，根本就無法分辨出square究竟是（像＋和 * 那樣）直接做在解釋器裡呢，還是被定義為一個複合過程。
1.1.5 過程應用的代換模型
為了求值一個組合式（其運算符是一個複合過程的名字），解釋器的工作方式将完全按照1.1.3節中所描述的那樣，采用與以運算符名為基本過程的組合式一樣的計算過程。也就是說，解釋器将對組合式的各個元素求值，而後将得到的那個過程（也就是該組合式裡運算符的值）應用于那些實際參數（即組合式裡那些運算對象的值）。
我們可以假定，把基本運算符應用于實參的機制已經在解釋器裡做好了。對于複合過程，過程應用的計算過程是：
- 将複合過程應用于實際參數，就是在将過程體中的每個形參用相應的實參取代之後，對這一過程體求值。
為了說明這種計算過程，讓我們看看下面組合式的求值：
(f 5)
其中的f是1.1.4節定義的那個過程。我們首先提取出f的體：
(sum-of-squares (+ a 1) (* a 2)) 而後用實際參數5代換其中的形式參數：
(sum-of-squares (+ 5 1) (* 5 2)) 這樣，問題就被歸約為對另一個組合式的求值，其中有兩個運算對象，有關的運算符是sum-of-squares。求值這一組合式牽涉三個子問題：我們必須對其中的運算符求值，以便得到應該去應用的那個過程；還需要求值兩個運算對象，以得到過程的實際參數。這裡的（＋5 1）産生出6，（* 5 2）産生出10，是以我們就需要将sum-of-squares過程用于6和10。用這兩個值代換sum-of-squares體中的形式參數x和y，表達式被歸約為：
(+ (square 6) (square 10)) 使用square的定義又可以将它歸約為：
(+ (* 6 6) (* 10 10)) 通過乘法又能将它進一步歸約為：
(+ 36 100) 最後得到：
136 上面描述的這種計算過程稱為過程應用的代換模型，在考慮本章至今所定義的過程時，我們可以将它看作确定過程應用的“意義”的一種模型。但這裡還需要強調兩點：
- 代換的作用隻是為了幫助我們領會過程調用中的情況，而不是對解釋器實際工作方式的具體描述。通常的解釋器都不采用直接操作過程的正文，用值去代換形式參數的方式去完成對過程調用的求值。在實際中，它們一般采用提供形式參數的局部環境的方式，産生“代換”的效果。我們将在第3章和第4章考察一個解釋器的細節實作，在那裡更完整地讨論這一問題。
- 随着本書讨論的進展，我們将給出有關解釋器如何工作的一系列模型，一個比一個更精細，并最終在第5章給出一個完整的解釋器和一個編譯器。這裡的代換模型隻是這些模型中的第一個—作為形式化地考慮這種求值過程的起點。一般來說，在模拟科學研究或者工程中的現象時，我們總是從最簡單的不完全的模型開始。随着更細緻地檢查所考慮的問題，這些簡單模型也會變得越來越不合适，進而必須用進一步精化的模型取代。代換模型也不例外。特别地，在第3章中，我們将要讨論将過程用于“變化的資料”的問題，那時就會看到替換模型完全不行了，必須用更複雜的過程應用模型來代替它。
應用序和正則序
按照1.1.3節給出的有關求值的描述，解釋器首先對運算符和各個運算對象求值，而後将得到的過程應用于得到的實際參數。然而，這并不是執行求值的唯一可能方式。另一種求值模型是先不求出運算對象的值，直到實際需要它們的值時再去做。采用這種求值方式，我們就應該首先用運算對象表達式去代換形式參數，直至得到一個隻包含基本運算符的表達式，然後再去執行求值。如果我們采用這一方式，對下面表達式的求值：
(f 5) 将按照下面的序列逐漸展開：
(sum-of-squares (+ 5 1) (* 5 2))
(+ (square (+ 5 1)) (square (* 5 2)) )
(+ (* (+ 5 1) (+ 5 1)) (* (* 5 2) (* 5 2))) 而後是下面歸約：
(+ (* 6 6) (* 10 10))
(+ 36 100)
136 這給出了與前面求值模型同樣的結果，但其中的計算過程卻是不一樣的。特别地，在對下面表達式的歸約中，對于（＋5 1）和（* 5 2）的求值各做了兩次：
(* x x) 其中的x分别被代換為（＋5 1）和（* 5 2）。
這種“完全展開而後歸約”的求值模型稱為正則序求值，與之對應的是現在解釋器裡實際使用的“先求值參數而後應用”的方式，它稱為應用序求值。可以證明，對那些可以通過替換去模拟，并能産生出合法值的過程應用（包括本書前兩章中的所有過程），正則序和應用序求值将産生出同樣的值（參見練習1.5中一個“非法”值的例子，其中正則序和應用序将給出不同的結果）。
Lisp采用應用序求值，部分原因在于這樣做能避免對于表達式的重複求值（例如上面的（＋5 1）和（* 5 2）的情況），進而可以提高一些效率。更重要的是，在超出了可以采用替換方式模拟的過程範圍之後，正則序的處理将變得更複雜。而在另一些方面，正則序也可以成為特别有價值的工具，我們将在第3章和第4章研究它的某些内在性質16。
1.1.6 條件表達式和謂詞
至此我們能定義出的過程類的表達能力還非常有限，因為還沒辦法去做某些檢測，而後依據檢測的結果去确定做不同的操作。例如，我們還無法定義一個過程，使它能計算出一個數的絕對值。完成此事需要先檢查一個數是正的、負的或者零，而後依據遇到的不同情況，按照下面規則采取不同的動作：
這種結構稱為一個分情況分析，在Lisp裡有着一種針對這類分情況分析的特殊形式，稱為cond（表示“條件”）。其使用形式如下：
(define (abs x)
(cond ((> x 0) x)
((= x 0) 0)
((< x 0) (- x)))) 條件表達式的一般性形式為：
這裡首先包含了一個符号cond，在它之後跟着一些稱為子句的用括号括起的表達式對偶
。在每個對偶中的第一個表達式是一個謂詞，也就是說，這是一個表達式，它的值将被解釋為真或者假。
條件表達式的求值方式如下：首先求值謂詞
，如果它的值是false，那麼就去求值
，如果
的值是false就去求值
。這一過程将繼續做下去，直到發現了某個謂詞的值為真為止。此時解釋器就傳回相應子句中的序清單達式
的值，以這個值作為整個條件表達式的值。如果無法找到值為真的
，cond的值就沒有定義。
我們用術語謂詞指那些傳回真或假的過程，也指那種能求出真或者假的值的表達式。求絕對值的過程abs使用了基本謂詞＞、＜和＝，這幾個謂詞都以兩個數為參數，分别檢查第一個數是否大于、小于或者等于第二個數，并據此分别傳回真或者假。
寫絕對值函數的另一種方式是：
(define (abs x)
(cond ((< x 0) (- x))
(else x))) 用自然語言來說，就是“如果x小于0就傳回－x，否則就傳回x”。else是一個特殊符号，可以用在cond的最後一個子句中
的位置，這樣做時，如果該cond前面的所有子句都被跳過，它就會傳回最後子句中
的值。事實上，所有永遠都求出真值的表達式都可以用在這個
的位置上。
下面是又一種寫絕對值函數的方式：
(define (abs x)
(if (< x 0)
(- x)
x)) 這裡采用的是特殊形式if，它是條件表達式的一種受限形式，适用于分情況分析中隻有兩個情況的需要。if表達式的一般形式是：
(if <predicate> <consequent> <alternative>) 在求值一個if表達式時，解釋器從求值其
部分開始，如果
得到真值，解釋器就去求值
并傳回其值，否則它就去求值
并傳回其值。
除了一批基本謂詞如<、＝和 > 之外，還有一些邏輯複合運算符，利用它們可以構造出各種複合謂詞。最常用的三個複合運算符是：
解釋器将從左到右一個個地求值
，如果某個
求值得到假，這一and表達式的值就是假，後面的那些
也不再求值了。如果前面所有的
都求出真值，這一and表達式的值就是最後那個
的值。
求值得到真，or表達式就以這個表達式的值作為值，後面的那些
也不再求值了。如果所有的
都求出假值，這一or表達式的值就是假。
如果
求出的值是假，not表達式的值就是真；否則其值為假。
注意，and和or都是特殊形式而不是普通的過程，因為它們的子表達式不一定都求值。not則是一個普通的過程。
作為使用這些邏輯複合運算符的例子，數x的值位于區間5 < x < 10之中的條件可以寫為：
(and (> x 5) (< x 10)) 作為另一個例子，下面定義了一個謂詞，它檢測某個數是否大于或者等于另一個數：
(define (>= x y)
(or (> x y) (= x y))) 或者也可以定義為：
(define (>= x y)
(not (< x y))) 練習1.1 下面是一系清單達式，對于每個表達式，解釋器将輸出什麼結果？假定這一系清單達式是按照給出的順序逐個求值的。
10
(+ 5 3 4)
(- 9 1)
(/ 6 2)
(+ (* 2 4) (- 4 6))
(define a 3)
(define b (+ a 1))
(+ a b (* a b))
(= a b)
(if (and (> b a) (< b (* a b)))
b
a)
(cond ((= a 4) 6)
((= b 4) (+ 6 7 a))
(else 25))
(+ 2 (if (> b a) b a))
(* (cond ((> a b) a)
((< a b) b)
(else -1))
(+ a 1)) 練習1.2 請将下面表達式變換為字首形式：
練習1.3 請定義一個過程，它以三個數為參數，傳回其中較大的兩個數之和。
練習1.4 請仔細考察上面給出的允許運算符為複合表達式的組合式的求值模型，根據對這一模型的認識描述下面過程的行為：
(define (a-plus-abs-b a b)
((if (> b 0) + -) a b)) 練習1.5 Ben Bitdiddle發明了一種檢測方法，能夠确定解釋器究竟采用哪種序求值，是采用應用序，還是采用正則序。他定義了下面兩個過程：
(define (p) (p))
(define (test x y)
(if (= x 0)
0
y)) 而後他求值下面的表達式：
(test 0 (p)) 如果某個解釋器采用的是應用序求值，Ben會看到什麼樣的情況？如果解釋器采用正則序求值，他又會看到什麼情況？請對你的回答做出解釋。（無論采用正則序或者應用序，假定特殊形式if的求值規則總是一樣的。其中的謂詞部分先行求值，根據其結果确定随後求值的子表達式部分。）
1.1.7 執行個體：采用牛頓法求平方根
上面介紹的過程都很像正常的數學函數，它們描述的是如何根據一個或者幾個參數去确定一個值。然而，在數學的函數和計算機的過程之間有一個重要差異，那就是，這一過程還必須是有效可行的。
作為目前情況下的一個執行個體，現在我們來考慮求平方根的問題。我們可以将平方根函數定義為：
＝那樣的y，使得y≥0而且y^2＝x
這就描述出了一個完全正統的數學函數，我們可以利用它去判斷某個數是否為另一個數的平方根，或根據上面叙述，推導出一些有關平方根的一般性事實。然而，另一方面，這一定義并沒有描述一個計算過程，因為它确實沒有告訴我們，在給定了一個數之後，如何實際地找到這個數的平方根。即使将這個定義用類似Lisp的形式重寫一遍也完全無濟于事：
(define (sqrt x)
(the y (and (>= y 0)
(= (square y) x)))) 這隻不過是重新提出了原來的問題。
函數與過程之間的沖突，不過是在描述一件事情的特征，與描述如何去做這件事情之間的普遍性差異的一個具體反映。換一種說法，人們有時也将它說成是說明性的知識與行動性的知識之間的差異。在數學裡，人們通常關心的是說明性的描述（是什麼），而在計算機科學裡，人們則通常關心行動性的描述（怎麼做）。
計算機如何算出平方根呢？最常用的就是牛頓的逐漸逼近方法。這一方法告訴我們，如果對x的平方根的值有了一個猜測y，那麼就可以通過執行一個簡單操作去得到一個更好的猜測：隻需要求出y和x/y的平均值（它更接近實際的平方根值）。例如，可以用這種方式去計算2的平方根，假定初始值是1：
繼續這一計算過程，我們就能得到對2的平方根的越來越好的近似值。
現在，讓我們設法用過程的語言來描述這一計算過程。開始時，我們有了被開方數的值（現在需要做的就是算出它的平方根）和一個猜測值。如果猜測值已經足夠好了，有關工作也就完成了。如若不然，那麼就需要重複上述計算過程去改進猜測值。我們可以将這一基本政策寫成下面的過程：
(define (sqrt-iter guess x)
(if (good-enough- guess x)
guess
(sqrt-iter (improve guess x)
x))) 改進猜測的方式就是求出它與被開方數除以上一個猜測的平均值：
(define (improve guess x)
(average guess (/ x guess))) (define (average x y)
(/ (+ x y) 2)) 我們還必須說明什麼叫作“足夠好”。下面的做法隻是為了說明問題，它确實不是一個很好的檢測方法（參見練習1.7）。這裡的想法是，不斷改進答案直至它足夠接近平方根，使得其平方與被開方數之差小于某個事先确定的誤內插補點（這裡用的是0.001）：
(define (good-enough- guess x)
(< (abs (- (square guess) x)) 0.001)) 最後還需要一種方式來啟動整個工作。例如，我們可以總用1作為對任何數的初始猜測值：
(define (sqrt x)
(sqrt-iter 1.0 x)) 如果把這些定義都送給解釋器，我們就可以使用sqrt了，就像可以使用其他過程一樣：
(sqrt 9)
3.00009155413138
(sqrt (+ 100 37))
11.704699917758145
(sqrt (+ (sqrt 2) (sqrt 3)))
1.7739279023207892
(square (sqrt 1000))
1000.000369924366 這個sqrt程式也說明，在用于寫純粹的數值計算程式時，至今已介紹的簡單程式設計語言已經足以寫出可以在其他語言（例如C或者Pascal）中寫出的任何東西了。這看起來很讓人吃驚，因為這一語言中甚至還沒有包括任何疊代結構（循環），它們用于指揮計算機去一遍遍地做某些事情。而另一方面，sqrt-iter展示了如何不用特殊的疊代結構來實作疊代，其中隻需要使用正常的過程調用能力24。
練習1.6 Alyssa P. Hacker看不出為什麼需要将if提供為一種特殊形式，她問：“為什麼我不能直接通過cond将它定義為一個正常過程呢？”Alyssa的朋友Eva Lu Ator斷言确實可以這樣做，并定義了if的一個新版本：
(define (new-if predicate then-clause else-clause)
(cond (predicate then-clause)
(else else-clause))) Eva給Alyssa示範她的程式：
(new-if (= 2 3) 0 5)
5
(new-if (= 1 1) 0 5)
0 她很高興地用自己的new-if重寫了求平方根的程式：
(define (sqrt-iter guess x)
(new-if (good-enough- guess x)
guess
(sqrt-iter (improve guess x)
x))) 當Alyssa試着用這個過程去計算平方根時會發生什麼事情呢？請給出解釋。
練習1.7 對于确定很小的數的平方根而言，在計算平方根中使用的檢測good-enough?是很不好的。還有，在現實的計算機裡，算術運算總是以一定的有限精度進行的。這也會使我們的檢測不适合非常大的數的計算。請解釋上述論斷，用例子說明對很小和很大的數，這種檢測都可能失敗。實作good-enough?的另一種政策是監視猜測值在從一次疊代到下一次的變化情況，當改變值相對于猜測值的比率很小時就結束。請設計一個采用這種終止測試方式的平方根過程。對于很大和很小的數，這一方式都能工作嗎？
練習1.8 求立方根的牛頓法基于如下事實，如果y是x的立方根的一個近似值，那麼下式将給出一個更好的近似值：
請利用這一公式實作一個類似平方根過程的求立方根的過程。（在1.3.4節裡，我們将看到如何實作一般性的牛頓法，作為這些求平方根和立方根過程的抽象。）
1.1.8 過程作為黑箱抽象
sqrt是我們用一組手工定義的過程來實作一個計算過程的第一個例子。請注意，在這裡sqrt-iter的定義是遞歸的，也就是說，這一過程的定義基于它自身。能夠基于一個過程自身來定義它的想法很可能會令人感到不安，人們可能覺得它不夠清晰，這種“循環”定義怎麼能有意義呢？是不是完全刻畫了一個能夠由計算機實作的計算過程呢？在1.2節裡，我們将更細緻地讨論這一問題。現在首先來看看sqrt執行個體所顯示出的其他一些要點。
可以看到，對于平方根的計算問題可以自然地分解為若幹子問題：怎樣說一個猜測是足夠好了，怎樣去改進一個猜測，等等。這些工作中的每一個都通過一個獨立的過程完成，整個sqrt程式可以看作一族過程（如圖1-2所示），它們直接反映了從原問題到子問題的分解。
這一分解的重要性，并不僅僅在于它将一個問題分解成了幾個部分。當然，我們總可以拿來一個大程式，并将它分割成若幹部分—最前面10行、後面10行、再後面10行等等。這裡最關鍵的問題是，分解中的每一個過程完成了一件可以清楚标明的工作，這使它們可以被用作定義其他過程的子產品。例如，當我們基于square定義過程good-enough?之時，就是将square看作一個“黑箱”。在這樣做時，我們根本無須關注這個過程是如何計算出它的結果的，隻需要注意它能計算出平方值的事實。關于平方是如何計算的細節被隐去不提了，可以推遲到後來再考慮。情況确實如此，如果隻看good-enough?過程，與其說square是一個過程，不如說它是一個過程的抽象，即所謂的過程抽象。在這一抽象層次上，任何能計算出平方的過程都同樣可以用。
這樣，如果我們隻考慮傳回值，那麼下面這兩個求平方的過程就是不可區分的。它們中的每一個都取一個數值參數，産生出這個數的平方作為值25。
(define (square x) (* x x))
(define (square x)
(exp (double (log x))))
(define (double x) (+ x x)) 由此可見，一個過程定義應該能隐藏起一些細節。這将使過程的使用者可能不必自己去寫這些過程，而是從其他程式員那裡作為一個黑箱而接受了它。使用者在使用一個過程時，應該不需要去弄清它是如何實作的。
局部名
過程使用者不必去關心的實作細節之一，就是在有關的過程裡面形式參數的名字，這是由實作者所選用的。也就是說，下面兩個過程定義應該是無法區分的：
(define (square x) (* x x))
(define (square y) (* y y)) 這一原則（過程的意義應該不依賴于其作者為形式參數所選用的名字）從表面看起來很明顯，但其影響卻非常深遠。最直接的影響是，過程的形式參數名必須局部于有關的過程體。例如，我們在前面平方根程式中的good-enough?定義裡使用了square：
(define (good-enough- guess x)
(< (abs (- (square guess) x)) 0.001)) good-enough?作者的意圖就是要去确定，函數的第一個參數的平方是否位于第二個參數附近一定的誤差範圍内。可以看到，good-enough?的作者用名字guess表示其第一個參數，用x表示第二個參數，而送給square的實際參數就是guess。如果square的作者也用x（上面确實如此）表示參數，那麼就可以明顯看出，good-enough?裡的x必須與square裡的那個x不同。在過程square運作時，絕不應該影響good-enough?裡所用的那個x的值，因為在square完成計算之後，good-enough?裡可能還需要用x的值。
如果參數不是它們所在的過程體裡局部的東西，那麼square裡的x就會與good-enough?裡的參數x相混淆。如果這樣，good-enough?的行為方式就将依賴于我們所用的square的不同版本。這樣，square也就不是我們所希望的黑箱了。
過程的形式參數在過程體裡扮演着一種非常特殊的角色，在這裡，形式參數的具體名字是什麼，其實完全沒有關系。這樣的名字稱為限制變量，是以我們說，一個過程的定義限制了它的所有形式參數。如果在一個完整的過程定義裡将某個限制變量統一換名，這一過程定義的意義将不會有任何改變。如果一個變量不是被限制的，我們就稱它為自由的。一個名字的定義被限制于的那一集表達式稱為這個名字的作用域。在一個過程定義裡，被聲明為這個過程的形式參數的那些限制變量，就以這個過程的體作為它們的作用域。
在上面good-enough?的定義中，guess和x是限制變量，而<、-、abs和square則是自由的。要想保證good-enough?的意義與我們對guess和x的名字選擇無關，隻要求它們的名字與<、-、abs和square都不同就可以了（如果将guess重新命名為abs，我們就會因為捕獲了變量名abs而引進了一個錯誤，因為這樣做就把一個原本自由的名字變成限制的了）。good-enough?的意義當然與其中的自由變量有關，顯然它的意義依賴于（在這一定義之外的）一些事實：要求符号abs是一個過程的名字，該過程能求出一個數的絕對值。如果我們将good-enough?的定義裡的abs換成cos，它計算出的就會是另一個不同函數了。
内部定義和塊結構
至今我們才僅僅分離出了一種可用的名字：過程的形式參數是相應過程體裡的局部名字。平方根程式還展現出了另一種情況，我們也會希望能控制其中的名字使用。現在這個程式由幾個互相分離的過程組成：
(define (sqrt x)
(sqrt-iter 1.0 x))
(define (sqrt-iter guess x)
(if (good-enough- guess x)
guess
(sqrt-iter (improve guess x) x)))
(define (good-enough- guess x)
(< (abs (- (square guess) x)) 0.001))
(define (improve guess x)
(average guess (/ x guess))) 問題是，在這個程式裡隻有一個過程對使用者是重要的，那就是，這裡所定義的sqrt确實是sqrt。其他的過程（sqrt-iter、good-enough?和improve）則隻會幹擾他們的思維，因為他們再也不能定義另一個稱為good-enough?的過程，作為需要與平方根程式一起使用的其他程式的一部分了，因為現在sqrt需要它。在許多程式員一起構造大系統的時候，這一問題将會變得非常嚴重。舉例來說，在構造一個大型的數值過程庫時，許多數值函數都需要計算出一系列的近似值，是以我們就可能希望有一些名字為good-enough?和improve的過程作為其中的輔助過程。由于這些情況，我們也希望将這個種子過程局部化，将它們隐藏到sqrt裡面，以使sqrt可以與其他采用逐漸逼近的過程共存，讓它們中的每一個都有自己的good-enough- 過程。為了使這一方式成為可能，我們要允許一個過程裡帶有一些内部定義，使它們是局部于這一過程的。例如，在解決平方根問題時，我們可以寫：
(define (sqrt x)
(define (good-enough- guess x)
(< (abs (- (square guess) x)) 0.001))
(define (improve guess x)
(average guess (/ x guess)))
(define (sqrt-iter guess x)
(if (good-enough- guess x)
guess
(sqrt-iter (improve guess x) x)))
(sqrt-iter 1.0 x)) 這種嵌套的定義稱為塊結構，它是最簡單的名字包裝問題的一種正确解決方式。實際上，在這裡還潛藏着一個很好的想法。除了可以将所用的輔助過程定義放到内部，我們還可能簡化它們。因為x在sqrt的定義中是受限制的，過程good-enough?、improve和sqrt-iter也都定義在sqrt裡面，也就是說，都在x的定義域裡。這樣，顯式地将x在這些過程之間傳來傳去也就沒有必要了。我們可以讓x作為内部定義中的自由變量，如下所示。這樣，在外圍的sqrt被調用時，x由實際參數得到自己的值。這種方式稱為詞法作用域。
(define (sqrt x)
(define (good-enough- guess)
(< (abs (- (square guess) x)) 0.001))
(define (improve guess)
(average guess (/ x guess)))
(define (sqrt-iter guess)
(if (good-enough- guess)
guess
(sqrt-iter (improve guess))))
(sqrt-iter 1.0)) 下面将廣泛使用這種塊結構，以幫助我們将大程式分解成一些容易把握的片段28。塊結構的思想來自程式設計語言Algol 60，這種結構出現在各種最新的程式設計語言裡，是幫助我們組織大程式的結構的一種重要工具。
1.2 過程及其産生的計算
我們現在已經考慮了程式設計中的一些要素：使用過許多基本的算術操作，對操作進行組合，通過定義各種複合過程，對複合操作進行抽象。但是，即使是知道了這些，我們還不能說自己已經了解了如何去程式設計式。我們現在的情況就像是在學下象棋的過程中的一個階段，此時已經知道了移動棋子的各種規則，但卻還不知道典型的開局、戰術和政策。就像初學象棋的人們那樣，我們還不知道程式設計領域中各種有用的常見模式，缺少有關各種棋步的價值（值得定義哪些過程）的知識，缺少對所走棋步的各種後果（執行一個過程的效果）做出預期的經驗。
能夠看清楚所考慮的動作的後果的能力，對于成為程式設計專家是至關重要的，就像這種能力在所有綜合性的創造性的活動中的作用一樣。要成為一個專業攝影家，必須學習如何去考察各種景象，知道在各種可能的暴光和顯影選擇條件下，景象中各個區域在影像中的明暗程度。隻有在此之後，人才能去做反向推理，對取得所需效果應該做的取景、亮度、曝光和顯影等等做出規劃。在程式設計裡也一樣，在這裡，我們需要對計算過程中各種動作的進行情況做出規劃，用一個程式去控制這一過程的進展。要想成為專家，我們就需要學會去看清各種不同種類的過程會産生什麼樣的計算過程。隻有在掌握了這種技能之後，我們才能學會如何去構造出可靠的程式，使之能夠表現出所需要的行為。
一個過程也就是一種模式，它描述了一個計算過程的局部演化方式，描述了這一計算過程中的每個步驟是怎樣基于前面的步驟建立起來的。在有了一個刻畫計算過程的過程描述之後，我們當然希望能做出一些有關這一計算過程的整體或全局行為的論斷。一般來說這是非常困難的，但我們至少還是可以試着去描述過程演化的一些典型模式。
在這一節裡，我們将考察由一些簡單過程所産生的計算過程的“形狀”，還将研究這些計算過程消耗各種重要計算資源（時間和空間）的速率。這裡将要考察的過程都是非常簡單的，它們所扮演的角色就像是攝影術中的測試模式，是作為極度簡化的攝影模式，而其自身并不是很實際的例子。
1.2.1 線性的遞歸和疊代
首先考慮由下面表達式定義的階乘函數：
n!＝n·(n－1)·(n－2) …3·2·1 計算階乘的方式有許多種，一種最簡單方式就是利用下述認識：對于一個正整數n，n!就等于n乘以（n－1）!：
n!＝n·[(n－1)·(n－2) …3·2·1]＝n·(n－1)! 這樣，我們就能通過算出（n－1）!，并将其結果乘以n的方式計算出n!。如果再注意到1!就是1，這些認識就可以直接翻譯成一個過程了：
(define (factorial n)
(if (= n 1)
1
(* n (factorial (- n 1))))) 我們可以利用1.1.5節介紹的代換模型，觀看這一過程在計算6!時表現出的行為，如圖1-3所示。
現在讓我們采用另一種不同的觀點來計算階乘。我們可以将計算階乘n!的規則描述為：先乘起1和2，而後将得到的結果乘以3，而後再乘以4，這樣下去直到達到n。更形式地說，我們要維持着一個變動中的乘積product，以及一個從1到n的計數器counter，這一計算過程可以描述為counter和product的如下變化，從一步到下一步，它們都按照下面規則改變：
product ← counter·product
counter ← counter + 1 可以看到，n!也就是計數器counter超過n時乘積product的值。
我們又可以将這一描述重構為一個計算階乘的過程：
(define (factorial n)
(fact-iter 1 1 n))
(define (fact-iter product counter max-count)
(if (> counter max-count)
product
(fact-iter (* counter product)
(+ counter 1)
max-count))) 與前面一樣，我們也可以應用替換模型來檢視6!的計算過程，如圖1-4所示。
現在對這兩個計算過程做一個比較。從一個角度看，它們并沒有很大差異：兩者計算的都是同一個定義域裡的同一個數學函數，都需要使用與n正比的步驟數目去計算出n!。确實，這兩個計算過程甚至采用了同樣的乘運算序列，得到了同樣的部分乘積序列。但另一方面，如果我們考慮這兩個計算過程的“形狀”，就會發現它們的進展情況大不相同。
考慮第一個計算過程。代換模型揭示出一種先逐漸展開而後收縮的形狀，如圖1-3中的箭頭所示。在展開階段裡，這一計算過程構造起一個推遲進行的操作所形成的鍊條（在這裡是一個乘法的鍊條），收縮階段表現為這些運算的實際執行。這種類型的計算過程由一個推遲執行的運算鍊條刻畫，稱為一個遞歸計算過程。要執行這種計算過程，解釋器就需要維護好那些以後将要執行的操作的軌迹。在計算階乘n!時，推遲執行的乘法鍊條的長度也就是為儲存其軌迹需要儲存的資訊量，這個長度随着n值而線性增長（正比于n），就像計算中的步驟數目一樣。這樣的計算過程稱為一個線性遞歸過程。
與之相對應，第二個計算過程裡并沒有任何增長或者收縮。對于任何一個n，在計算過程中的每一步，在我們需要儲存軌迹裡，所有的東西就是變量product、counter和max-count的目前值。我們稱這種過程為一個疊代計算過程。一般來說，疊代計算過程就是那種其狀态可以用固定數目的狀态變量描述的計算過程；而與此同時，又存在着一套固定的規則，描述了計算過程在從一個狀态到下一狀态轉換時，這些變量的更新方式；還有一個（可能有的）結束檢測，它描述這一計算過程應該終止的條件。在計算n!時，所需的計算步驟随着n線性增長，這種過程稱為線性疊代過程。
我們還可以從另一個角度來看這兩個過程之間的對比。在疊代的情況裡，在計算過程中的任何一點，那幾個程式變量都提供了有關計算狀态的一個完整描述。如果我們令上述計算在某兩個步驟之間停下來，要想重新喚醒這一計算，隻需要為解釋器提供有關這三個變量的值。而對于遞歸計算過程而言，這裡還存在着另外的一些“隐含”資訊，它們并未儲存在程式變量裡，而是由解釋器維持着，指明了在所推遲的運算所形成的鍊條裡的漫遊中，“這一計算過程處在何處”。這個鍊條越長，需要儲存的資訊也就越多30。
在做疊代與遞歸之間的比較時，我們必須當心，不要搞混了遞歸計算過程的概念和遞歸過程的概念。當我們說一個過程是遞歸的時候，論述的是一個文法形式上的事實，說明這個過程的定義中（直接或者間接地）引用了該過程本身。在說某一計算過程具有某種模式時（例如，線性遞歸），我們說的是這一計算過程的進展方式，而不是相應過程書寫上的文法形式。當我們說某個遞歸過程（例如fact-iter）将産生出一個疊代的計算過程時，可能會使人感到不舒服。然而這一計算過程确實是疊代的，因為它的狀态能由其中的三個狀态變量完全刻畫，解釋器在執行這一計算過程時，隻需要保持這三個變量的軌迹就足夠了。
區分計算過程和寫出來的過程可能使人感到困惑，其中的一個原因在于各種常見語言（包括Ada、Pascal和C）的大部分實作的設計中，對于任何遞歸過程的解釋，所需要消耗的存儲量總與過程調用的數目成正比，即使它所描述的計算過程從原理上看是疊代的。作為這一事實的後果，要在這些語言裡描述疊代過程，就必須借助于特殊的“循環結構”，如do、repeat、until、for和while等等。我們将在第5章裡考察的Scheme的實作則沒有這一缺陷，它将總能在常量空間中執行疊代型計算過程，即使這一計算是用一個遞歸過程描述的。具有這一特性的實作稱為尾遞歸的。有了一個尾遞歸的實作，我們就可以利用正常的過程調用機制表述疊代，這也會使各種複雜的專用疊代結構變成不過是一些文法糖衣了31。
練習1.9 下面幾個過程各定義了一種加起兩個正整數的方法，它們都基于過程inc（它将參數增加1）和dec（它将參數減少1）。
(define (+ a b)
(if (= a 0)
b
(inc (+ (dec a) b))))
(define (+ a b)
(if (= a 0)
b
(+ (dec a) (inc b)))) 請用代換模型展示這兩個過程在求值（＋4 5）時所産生的計算過程。這些計算過程是遞歸的或者疊代的嗎？
練習1.10 下面過程計算一個稱為Ackermann函數的數學函數：
(define (A x y)
(cond ((= y 0) 0)
((= x 0) (* 2 y))
((= y 1) 2)
(else (A (- x 1)
(A x (- y 1)))))) 下面各表達式的值是什麼：
(A 1 10)
(A 2 4)
(A 3 3) 請考慮下面的過程，其中的A就是上面定義的過程：
(define (f n) (A 0 n))
(define (g n) (A 1 n))
(define (h n) (A 2 n))
(define (k n) (* 5 n n)) 請給出過程f、g和h對給定整數值n所計算的函數的數學定義。例如，（k n）計算的是5n2。
1.2.2 樹形遞歸
另一種常見計算模式稱為樹形遞歸。作為例子，現在考慮斐波那契（Fibonacci）數序列的計算，這一序列中的每個數都是前面兩個數之和：
0, 1, 1, 2, 3, 5, 8, 13, 21, …
一般說，斐波那契數由下面規則定義：
我們馬上就可以将這個定義翻譯為一個計算斐波那契數的遞歸過程：
(define (fib n)
(cond ((= n 0) 0)
((= n 1) 1)
(else (+ (fib (- n 1))
(fib (- n 2)))))) 考慮這一計算的模式。為了計算（fib 5），我們需要計算出（fib 4）和（fib 3）。而為了計算（fib 4），又需要計算（fib 3）和（fib 2）。一般而言，這一展開過程看起來像一棵樹，如圖1-5所示。請注意，這裡的每層分裂為兩個分支（除了最下面），反映出對fib過程的每個調用中兩次遞歸調用自身的事實。
上面過程作為典型的樹形遞歸具有教育意義，但它卻是一種很糟的計算斐波那契數的方法，因為它做了太多的備援計算。在圖1-5中，求（fib 3）差不多是這裡的一半工作，這一計算整個地重複做了兩次。事實上，不難證明，在這一過程中，計算（fib 1）和（fib 0）的次數（一般說，也就是上面樹裡樹葉的個數）正好是Fib(n＋1)。要領會這種情況有多麼糟糕，我們可以證明Fib(n) 值的增長相對于n是指數的。更準确地說（見練習1.13），Fib(n) 就是最接近
的整數，其中：
就是黃金分割的值，它滿足方程：
這樣，該過程所用的計算步驟數将随着輸入增長而指數性地增長。另一方面，其空間需求隻是随着輸入增長而線性增長，因為，在計算中的每一點，我們都隻需儲存樹中在此之上的結點的軌迹。一般說，樹形遞歸計算過程裡所需的步驟數将正比于樹中的結點數，其空間需求正比于樹的最大深度。
我們也可以規劃出一種計算斐波那契數的疊代計算過程，其基本想法就是用一對整數a和b，将它們分别初始化為Fib(1)＝1和Fib(0)＝0，而後反複地同時使用下面變換規則：
a←a＋b b←a
不難證明，在n次應用了這些變換後，a和b将分别等于Fib(n＋1) 和Fib(n)。是以，我們可以用下面過程，以疊代方式計算斐波那契數：
(define (fib n)
(fib-iter 1 0 n))
(define (fib-iter a b count)
(if (= count 0)
b
(fib-iter (+ a b) a (- count 1)))) 計算Fib(n)的這種方法是一個線性疊代。這兩種方法在計算中所需的步驟上差異巨大—後一方法相對于n為線性的，前一個的增長像Fib(n) 一樣快，即使不大的輸入也可能造成很大的差異。
但是我們也不應做出結論，說樹形遞歸計算過程根本沒有用。當我們考慮的是在層次結構性的資料上操作，而不是對數操作時，将會發現樹形遞歸計算過程是一種自然的、威力強大的工具32。即使是對于數的計算，樹形遞歸計算過程也可能幫助我們了解和設計程式。以計算斐波那契數的程式為例，雖然第一個fib過程遠比第二個低效，但它卻更加直截了當，基本上就是将斐波那契序列的定義直接翻譯為Lisp語言。而要規劃出那個疊代過程，則需要注意到，這一計算過程可以重新塑造為一個采用三個狀态變量的疊代。
執行個體：換零錢方式的統計
要想得到一個疊代的斐波那契算法需要一點點智慧。與此相對應，現在考慮下面的問題：給了半美元、四分之一美元、10美分、5美分和1美分的硬币，将1美元換成零錢，一共有多少種不同方式？更一般的問題是，給定了任意數量的現金，我們能寫出一個程式，計算出所有換零錢方式的種數嗎？
采用遞歸過程，這一問題有一種很簡單的解法。假定我們所考慮的可用硬币類型種類排了某種順序，于是就有下面的關系：
将總數為a的現金換成n種硬币的不同方式的數目等于
- 将現金數a換成除第一種硬币之外的所有其他硬币的不同方式數目，加上
- 将現金數a－d換成所有種類的硬币的不同方式數目，其中的d是第一種硬币的币值。
要問為什麼這一說法是對的，請注意這裡将換零錢分成兩組時所采用的方式，第一組裡都沒有使用第一種硬币，而第二組裡都使用了第一種硬币。顯然，換成零錢的全部方式的數目，就等于完全不用第一種硬币的方式的數目，加上用了第一種硬币的換零錢方式的數目。而後一個數目也就等于去掉一個第一種硬币值後，剩下的現金數的換零錢方式數目。
這樣就可以将某個給定現金數的換零錢方式的問題，遞歸地歸約為對更少現金數或者更少種類硬币的同一個問題。仔細考慮上面的歸約規則，設法使你确信，如果采用下面方式處理退化情況，我們就能利用上面規則寫出一個算法來33：
- 如果a就是0，應該算作是有1種換零錢的方式。
- 如果a小于0，應該算作是有0種換零錢的方式。
- 如果n是0，應該算作是有0種換零錢的方式。
我們很容易将這些描述翻譯為一個遞歸過程：
(define (count-change amount)
(cc amount 5))
(define (cc amount kinds-of-coins)
(cond ((= amount 0) 1)
((or (< amount 0) (= kinds-of-coins 0)) 0)
(else (+ (cc amount
(- kinds-of-coins 1))
(cc (- amount
(first-denomination kinds-of-coins))
kinds-of-coins)))))
(define (first-denomination kinds-of-coins)
(cond ((= kinds-of-coins 1) 1)
((= kinds-of-coins 2) 5)
((= kinds-of-coins 3) 10)
((= kinds-of-coins 4) 25)
((= kinds-of-coins 5) 50))) （過程first-denomination以可用的硬币種數作為輸入，傳回第一種硬币的币值。這裡認為硬币已經從最大到最小排列好了，其實采用任何順序都可以）。我們現在就能回答開始的問題了，下面是換1美元硬币的不同方式數目：
(count-change 100)
292 count-change産生出一個樹形的遞歸計算過程，其中的備援計算與前面fib的第一種實作類似（它計算出292需要一點時間）。另一方面，要想設計出一個更好的算法，使之能算出同樣結果，就不那麼明顯了。我們将這一問題留給讀者作為一個挑戰。人們認識到，樹形遞歸計算過程有可能極其低效，但常常很容易描述和了解，這就導緻人們提出了一個建議，希望能利用世界上的這兩個最好的東西。人們希望能設計出一種“靈巧編譯器”，使之能将一個樹形遞歸的過程翻譯為一個能計算出同樣結果的更有效的過程34。
練習1.11 函數 f 由如下的規則定義：如果n＜3，那麼 f(n)＝n；如果n≥3，那麼 f(n)＝f(n－1)＋2f(n－2)＋3f(n－3)。請寫一個采用遞歸計算過程計算 f 的過程。再寫一個采用疊代計算過程計算 f 的過程。
練習1.12 下面數值模式稱為帕斯卡三角形：
三角形邊界上的數都是1，内部的每個數是位于它上面的兩個數之和35。請寫一個過程，它采用遞歸計算過程計算出帕斯卡三角形。
練習1.13 證明Fib(n) 是最接近
的整數，其中
。提示：利用歸納法和斐波那契數的定義（見1.2.2節），證明
。
1.2.3 增長的階
前面一些例子說明，不同的計算過程在消耗計算資源的速率上可能存在着巨大差異。描述這種差異的一種友善方式是用增長的階的記法，以便我們了解在輸入變大時，某一計算過程所需資源的粗略度量情況。
令n是一個參數，它能作為問題規模的一種度量，令R(n) 是一個計算過程在處理規模為n的問題時所需要的資源量。在前面的例子裡，我們取n為給定函數需要計算的那個數，當然也存在其他可能性。例如，如果我們的目标是計算出一個數的平方根的近似值，那麼就可以将n取為所需精度的數字個數。對于矩陣乘法，我們可以将n取為矩陣的行數。一般而言，總存在着某個有關問題特性的數值，使我們可以相對于它去分析給定的計算過程。與此類似，R(n)也可以是所用的内部寄存器數目的路徑成本，也可能是需要執行的機器操作數目的路徑成本，或者其他類似東西。在每個時刻隻能執行固定數目的操作的計算機裡，所需的時間将正比于需要執行的基本機器指令條數。
我們稱R(n) 具有Θ(f(n)) 的增長階，記為R(n)＝Θ(f(n))（讀作“f(n) 的theta”），如果存在與n無關的整數k1和k2，使得：
對任何足夠大的n值都成立（換句話說，對足夠大的n，值R(n) 總位于k1f(n) 和k2f(n) 之間）。
舉例來說，在1.2.1節中描述的計算階乘的線性遞歸計算過程裡，步驟數目的增長正比于輸入n。也就是說，這一計算過程所需步驟的增長為Θ(n)，其空間需求的增長也是Θ(n)。對于疊代的階乘，其步數還是Θ(n) 而空間是Θ(1)，即為一個常數36。樹形遞歸的斐波那契計算需要
步和Θ(n) 空間，這裡的f就是1.2.2節中描述的黃金分割率。
增長的階為我們提供了對計算過程行為的一種很粗略的描述。例如，某計算過程需要n2步，另一計算過程需要1000n2步，還有一個計算過程需要3n2＋10n＋17步，它們增長的階都是Θ(n^2)。但另一方面，增長的階也為我們在問題規模改變時，預期一個計算過程的行為變化提供了有用的線索。對于一個Θ(n)（線性）的計算過程，規模增大一倍大緻将使它所用的資源增加了一倍。對于一個指數的計算過程，問題規模每增加1都将導緻所用資源按照某個常數倍增長。在1.2節剩下的部分，我們将考察兩個算法，其增長的階都是對數型增長的，是以，當問題規模增大一倍時，所需資源量隻增加一個常數。
練習1.14 請畫出有關的樹，展示1.2.2節的過程count-change在将11美分換成硬币時所産生的計算過程。相對于被換現金量的增加，這一計算過程的空間和步數增長的階各是什麼？
練習1.15 在角（用弧度描述）x足夠小時，其正弦值可以用sinx≈x計算，而三角恒等式：
可以減小sin的參數的大小（為完成這一練習，我們認為一個角是“足夠小”，如果其數值不大于0.1弧度）。這些想法都展現在下述過程中：
(define (cube x) (* x x x))
(define (p x) (- (* 3 x) (* 4 (cube x))))
(define (sine angle)
(if (not (> (abs angle) 0.1))
angle
(p (sine (/ angle 3.0))))) a) 在求值（sine 12.15）時，p将被使用多少次？
b) 在求值（sine a）時，由過程sine所産生的計算過程使用的空間和步數（作為a的函數）增長的階是什麼？
1.2.4 求幂
現在考慮對一個給定的數計算乘幂的問題，我們希望這一過程的參數是一個基數b和一個正整數的指數n，過程計算出b^n。做這件事的一種方式是通過下面這個遞歸定義：
它可以直接翻譯為如下過程：
(define (expt b n)
(if (= n 0)
1
(* b (expt b (- n 1))))) 這是一個線性的遞歸計算過程，需要Θ(n) 步和Θ(n) 空間。就像階乘一樣，我們很容易将其形式化為一個等價的線性疊代：
(define (expt b n)
(expt-iter b n 1))
(define (expt-iter b counter product)
(if (= counter 0)
product
(expt-iter b
(- counter 1)
(* b product)))) 這一版本需要Θ(n) 步和Θ(1) 空間。
我們可以通過連續求平方，以更少的步驟完成乘幂計算。例如，不是采用下面這樣的方式算b^8：
b·(b·(b·(b·(b·(b·(b·b))))))
而是用三次乘法算出它來：
這一方法對于指數為2的乘幂都可以用。如果采用下面規則，我們就可以借助于連續求平方，去完成一般的乘幂計算：
這一方法可以定義為如下的過程：
(define (fast-expt b n)
(cond ((= n 0) 1)
((even? n) (square (fast-expt b (/ n 2))))
(else (* b (fast-expt b (- n 1)))))) 其中檢測一個整數是否偶數的謂詞可以基于基本過程remainder定義：
(define (even? n)
(= (remainder n 2) 0)) 由fast-expt演化出的計算過程，在空間和步數上相對于n都是對數的。要看到這些情況，請注意，在用fast-expt計算b2n時，隻需要比計算bn多做一次乘法。每做一次新的乘法，能夠計算的指數值（大約）增大一倍。這樣，計算指數n所需要的乘法次數的增長大約就是以2為底的n的對數值，這一計算過程增長的階為Θ(log n)^37。
随着n變大，Θ(log n) 增長與Θ(n) 增長之間的差異也會變得非常明顯。例如對n＝1000，fast-expt隻需要14次乘法38。我們也可能采用連續求平方的想法，設計出一個具有對數步數的計算乘幂的疊代算法（見練習1.16）。但是，就像疊代算法的常見情況一樣，寫出這一算法就不像對遞歸算法那樣直截了當了。
練習1.16 請定義一個過程，它能産生出一個按照疊代方式的求幂計算過程，其中使用一系列的求平方，就像一樣fast-expt隻用對數個步驟那樣。（提示：請利用關系
＝
，除了指數n和基數b之外，還應維持一個附加的狀态變量a，并定義好狀态變換，使得從一個狀态轉到另一狀态時乘積a b^n不變。在計算過程開始時令a取值1，并用計算過程結束時a的值作為回答。一般說，定義一個不變量，要求它在狀态之間保持不變，這一技術是思考疊代算法設計問題時的一種非常強有力的方法。）
練習1.17 本節裡的求幂算法的基礎就是通過反複做乘法去求乘幂。與此類似，也可以通過反複做加法的方式求出乘積。下面的乘積過程與expt過程類似（其中假定我們的語言隻有加法而沒有乘法）：
(define (* a b)
(if (= b 0)
0
(+ a (* a (- b 1))))) 這一算法具有相對于b的線性步數。現在假定除了加法之外還有運算double，它能求出一個整數的兩倍；還有halve，它将一個（偶數）除以2。請用這些運算設計一個類似fast-expt的求乘積過程，使之隻用對數的計算步數。
練習1.18 利用練習1.16和1.17的結果設計一個過程，它能産生出一個基于加、加倍和折半運算的疊代計算過程，隻用對數的步數就能求出兩個整數的乘積40。
練習1.19 存在着一種以對數步數求出斐波那契數的巧妙算法。請回憶1.2.2節fib-iter計算過程中狀态變量a和b的變換規則，a←a＋b和b←a，現在将這種變換稱為T變換。通過觀察可以發現，從1和0開始将T反複應用n次，将産生出一對數Fib(n＋1) 和Fib(n)。換句話說，斐波那契數可以通過将Tn（變換T的n次方）應用于對偶 (1, 0) 而産生出來。現在将T看作變換族Tpq中p＝0且q＝1的特殊情況，其中Tpq是對于對偶 (a, b) 按照a←bq＋aq＋ap和b←bp＋aq規則的變換。請證明，如果我們應用變換Tpq兩次，其效果等同于應用同樣形式的一次變換Tp'q'，其中的p'和q'可以由p和q計算出來。這就指明了一條求出這種變換的平方的路徑，使我們可以通過連續求平方的方式去計算Tn，就像fast-expt過程裡所做的那樣。将所有這些集中到一起，就形成了下面的過程，其運作隻需要對數的步數：
(define (fib n)
(fib-iter 1 0 0 1 n))
(define (fib-iter a b p q count)
(cond ((= count 0) b)
((even? count)
(fib-iter a
b
<??> ; compute p'
<??> ; compute q'
(/ count 2)))
(else (fib-iter (+ (* b q) (* a q) (* a p))
(+ (* b p) (* a q))
p
q
(- count 1))))) 1.2.5 最大公約數
兩個整數a和b的最大公約數（GCD）定義為能除盡這兩個數的那個最大的整數。例如，16和28的GCD就是4。在第2章裡，當我們要去研究有理數算術的實作時，就會需要GCD，以便能把有理數約化到最簡形式（要将有理數約化到最簡形式，我們必須将其分母和分子同時除掉它們的GCD。例如，16/28将約簡為4/7）。找出兩個整數的GCD的一種方式是對它們做因數分解，并從中找出公共因子。但存在着一個更高效的著名算法。
這一算法的思想基于下面的觀察：如果r是a除以b的餘數，那麼a和b的公約數正好也是b的r的公約數。是以我們可以借助于等式：
GCD(a, b)＝GCD(b, r)
這就把一個GCD的計算問題連續地歸約到越來越小的整數對的GCD的計算問題。例如：
GCD(206, 40)＝GCD(40, 6) ＝GCD(6, 4) ＝GCD(4, 2) ＝GCD(2, 0) ＝2
将GCD (206, 40) 歸約到GCD (2, 0)，最終得到2。可以證明，從任意兩個正整數開始，反複執行這種歸約，最終将産生出一個數對，其中的第二個數是0，此時的GCD就是另一個數。這一計算GCD的方法稱為歐幾裡得算法42。
不難将歐幾裡得算法寫成一個過程：
(define (gcd a b)
(if (= b 0)
a
(gcd b (remainder a b)))) 這将産生一個疊代計算過程，其步數依所涉及的數的對數增長。
歐幾裡得算法所需的步數是對數增長的，這一事實與斐波那契數之間有一種有趣關系：
Lamé定理：如果歐幾裡得算法需要用k步計算出一對整數的GCD，那麼這對數中較小的那個數必然大于或者等于第k個斐波那契數。
我們可以利用這一定理，做出歐幾裡得算法的增長階估計。令n是作為過程輸入的兩個數中較小的那個，如果計算過程需要k步，那麼我們就一定有
。這樣，步數k的增長就是n的對數（對數的底是φ）。這樣，算法的增長階就是Θ(log n)。
練習1.20 一個過程所産生的計算過程當然依賴于解釋器所使用的規則。作為一個例子，考慮上面給出的疊代式gcd過程，假定解釋器用第1.1.5節讨論的正則序去解釋這一過程（對if的正則序求值規則在練習1.5中描述）。請采用（正則序的）代換方法，展示在求值表達式（gcd 206 40）中産生的計算過程，并指明實際執行的remainder運算。在采用正則序求值（gcd 206 40）中實際執行了多少次remainder運算？如果采用應用序求值呢？
1.2.6 執行個體：素數檢測
本節将描述兩種檢查整數n是否素數的方法，第一個具有
的增長階，而另一個“機率”算法具有Θ(log n) 的增長階。本節最後的練習提出了若幹基于這些算法的程式設計作業。
尋找因子
自古以來，數學家就被有關素數的問題所吸引，許多人都研究過确定整數是否素數的方法。檢測一個數是否素數的一種方法就是找出它的因子。下面的程式能找出給定數n的（大于1的）最小整數因子。它采用了一種直接方法，用從2開始的連續整數去檢查它們能否整除n。
(define (smallest-divisor n)
(find-divisor n 2))
(define (find-divisor n test-divisor)
(cond ((> (square test-divisor) n) n)
((divides? test-divisor n) test-divisor)
(else (find-divisor n (+ test-divisor 1)))))
(define (divides? a b)
(= (remainder b a) 0)) 我們可以用如下方式檢查一個數是否素數：n是素數當且僅當它是自己的最小因子：
(define (prime? n)
(= n (smallest-divisor n))) find-divisor的結束判斷基于如下事實，如果n不是素數，它必然有一個小于或者等于
的因子。這也意味着該算法隻需在1和
之間檢查因子。由此可知，确定是否素數所需的步數将具有
的增長階。
費馬檢查
的素數檢查基于數論中著名的費馬小定理的結果45。
費馬小定理：如果n是一個素數，a是小于n的任意正整數，那麼a的n次方與a模n同餘。
（兩個數稱為是模n同餘，如果它們除以n的餘數相同。數a除以n的餘數稱為a取模n的餘數，或簡稱為a取模n）。
如果n不是素數，那麼，一般而言，大部分的a＜n都将滿足上面關系。這就引出了下面這個檢查素數的算法：對于給定的整數n，随機任取一個a＜n并計算出an取模n的餘數。如果得到的結果不等于a，那麼n就肯定不是素數。如果它就是a，那麼n是素數的機會就很大。現在再另取一個随機的a并采用同樣方式檢查。如果它滿足上述等式，那麼我們就能對n是素數有更大的信心了。通過檢查越來越多的a值，我們就可以不斷增加對有關結果的信心。這一算法稱為費馬檢查。
為了實作費馬檢查，我們需要有一個過程來計算一個數的幂對另一個數取模的結果：
(define (expmod base exp m)
(cond ((= exp 0) 1)
((even? exp)
(remainder (square (expmod base (/ exp 2) m))
m))
(else
(remainder (* base (expmod base (- exp 1) m))
m)))) 這個過程很像1.2.4節的fast-expt過程，它采用連續求平方的方式，使相對于計算中指數，步數增長的階是對數的。
執行費馬檢查需要選取位于1和n－1之間（包含這兩者）的數a，而後檢查a的n次幂取模n的餘數是否等于a。随機數a的選取通過過程random完成，我們假定它已經包含在Scheme的基本過程中，它傳回比其整數輸入小的某個非負整數。這樣，要得到1和n－1之間的随機數，隻需用輸入n－1去調用random，并将結果加1：
(define (fermat-test n)
(define (try-it a)
(= (expmod a n n) a))
(try-it (+ 1 (random (- n 1))))) 下面這個過程的參數是某個數，它将按照由另一參數給定的次數運作上述檢查。如果每次檢查都成功，這一過程的值就是真，否則就是假：
(define (fast-prime? n times)
(cond ((= times 0) true)
((fermat-test n) (fast-prime? n (- times 1)))
(else false))) 機率方法
從特征上看，費馬檢查與我們前面已經熟悉的算法都不一樣。前面那些算法都保證計算的結果一定正确，而費馬檢查得到的結果則隻有機率上的正确性。說得更準确些，如果數n不能通過費馬檢查，我們可以确信它一定不是素數。而n通過了這一檢查的事實隻能作為它是素數的一個很強的證據，但卻不是對n為素數的保證。我們能說的是，對于任何數n，如果執行這一檢查的次數足夠多，而且看到n通過了檢查，那麼就能使這一素數檢查出錯的機率減小到所需要的任意程度。
不幸的是，這一斷言并不完全正确。因為确實存在着一些能騙過費馬檢查的整數：某些數n不是素數但卻具有這樣的性質，對任意整數a＜n，都有an與a模n同餘。由于這種數極其罕見，是以費馬檢查在實踐中還是很可靠的。也存在着一些費馬檢查的不會受騙的變形，它們也像費馬方法一樣，在檢查整數n是否為素數時，選擇随機的整數a＜n并去檢查某些依賴于n和a的關系（練習1.28是這類檢查的一個例子）。另一方面，與費馬檢查不同的是可以證明，對任意的數n，相應條件對整數a＜n中的大部分都不成立，除非n是素數。這樣，如果n對某個随機選出的a能通過檢查，n是素數的機會就大于一半。如果n對兩個随機選擇的a能通過檢查，n是素數的機會就大于四分之三。通過用更多随機選擇的a值運作這一檢查，我們可以使出現錯誤的機率減小到所需要的任意程度。
能夠證明，存在着使這樣的出錯機會達到任意小的檢查算法，激發了人們對這類算法的極大興趣，已經形成了人所共知稱為機率算法的領域。在這一領域中已經有了大量研究工作，機率算法也已被成功地應用于許多重要領域。
練習1.21 使用smallest-divisor過程找出下面各數的最小因子：199、1999、19999。
練習1.22 大部分Lisp實作都包含一個runtime基本過程，調用它将傳回一個整數，表示系統已經運作的時間（例如，以微秒計）。在對整數n調用下面的timed-prime-test過程時，将列印出n并檢查n是否為素數。如果n是素數，過程将列印出三個星号，随後是執行這一檢查所用的時間量。
(define (timed-prime-test n)
(newline)
(display n)
(start-prime-test n (runtime)))
(define (start-prime-test n start-time)
(if (prime? n)
(report-prime (- (runtime) start-time))))
(define (report-prime elapsed-time)
(display " *** ")
(display elapsed-time)) 請利用這一過程寫一個search-for-primes過程，它檢查給定範圍内連續的各個奇數的素性。請用你的過程找出大于1 000、大于10 000、大于100 000和大于1 000 000的三個最小的素數。請注意其中檢查每個素數所需要的時間。因為這一檢查算法具有
的增長階，你可以期望在10 000附近的素數檢查的耗時大約是在1 000附近的素數檢查的倍。你得到的資料确實如此嗎？對于100 000和1 000 000得到的資料，對這一
預測的支援情況如何？有人說程式在你的機器上運作的時間正比于計算所需的步數，你得到的結果符合這種說法嗎？
練習1.23 在本節開始時給出的那個smallest-divisor過程做了許多無用檢查：在它檢查了一個數是否能被2整除之後，實際上已經完全沒必要再檢查它是否能被任何偶數整除了。這說明test-divisor所用的值不應該是2，3，4，5，6，...，而應該是2，3，5，7，9，...。請實作這種修改。其中應定義一個過程next，用2調用時它傳回3，否則就傳回其輸入值加2。修改smallest-divisor過程，使它去使用（next test-divisor）而不是（＋test-divisor 1）。讓timed-prime-test結合這個smallest-divisor版本，運作練習1.22裡的12個找素數的測試。因為這一修改使檢查的步數減少一半，你可能期望它的運作速度快一倍。實際情況符合這一預期嗎？如果不符合，你所觀察到的兩個算法速度的比值是什麼？你如何解釋這一比值不是2的事實？
練習1.24 修改練習1.22的timed-prime-test過程，讓它使用fast-prime?（費馬方法），并檢查你在該練習中找出的12個素數。因為費馬檢查具有
的增長速度，對接近1 000 000的素數檢查與接近1000的素數檢查作對期望時間之間的比較有怎樣的預期？你的資料确實表明了這一預期嗎？你能解釋所發現的任何不符合預期的地方嗎？
練習1.25 Alyssa P. Hacker提出，在寫expmod時我們做了過多的額外工作。她說，畢竟我們已經知道怎樣計算乘幂，是以隻需要簡單地寫：
(define (expmod base exp m)
(remainder (fast-expt base exp) m)) 她說的對嗎？這一過程能很好地用于我們的快速素數檢查程式嗎？請解釋這些問題。
練習1.26 Louis Reasoner在做練習1.24時遇到了很大困難，他的fast-prime?檢檢視起來運作得比他的prime?檢查還慢。Louis請他的朋友Eva Lu Ator過來幫忙。在檢查Louis的代碼時，兩個人發現他重寫了expmod過程，其中用了一個顯式的乘法，而沒有調用square：
(define (expmod base exp m)
(cond ((= exp 0) 1)
((even? exp)
(remainder (* (expmod base (/ exp 2) m)
(expmod base (/ exp 2) m))
m))
(else
(remainder (* base (expmod base (- exp 1) m))
m)))) “我看不出來這會造成什麼不同，”Louis說。“我能看出，”Eva說，“采用這種方式寫出該過程時，你就把一個
的計算過程變成Θ(n) 的了。”請解釋這一問題。
練習1.27 證明腳注47中列出的Carmichael數确實能騙過費馬檢查。也就是說，寫一個過程，它以整數n為參數，對每個a＜n檢查a^n是否與a模n同餘。用你的過程去檢查前面給出的那些Carmichael數。
練習1.28 費馬檢查的一種不會被欺騙的變形稱為Miller-Rabin檢查（Miller 1976; Rabin 1980），它來源于費馬小定理的一個變形。這一變形斷言，如果n是素數，a是任何小于n的整數，則a的 (n－1) 次幂與1模n同餘。要用Miller-Rabin檢查考察數n的素性，我們應随機地取一個數a＜n并用過程expmod求a的 (n－1) 次幂對n的模。然而，在執行expmod中的平方步驟時，我們需要檢視是否遇到了“1取模n的非平凡平方根”，也就是說，是不是存在不等于1或者n－1的數，其平方取模n等于1。可以證明，如果1的這種非平凡平方根存在，那麼n就不是素數。還可以證明，如果n是非素數的奇數，那麼，至少有一半的數a＜n，按照這種方式計算a^(n-1)，将會遇到1取模n的非平凡平方根。這也是Miller-Rabin檢查不會受騙的原因。請修改expmod過程，讓它在發現1的非平凡平方根時報告失敗，并利用它實作一個類似于fermat-test的過程，完成Miller-Rabin檢查。通過檢查一些已知素數和非素數的方式考驗你的過程。提示：送出失敗信号的一種簡單方式就是讓它傳回0。
1.3 用高階函數做抽象
我們已經看到，在作用上，過程也就是一類抽象，它們描述了一些對于數的複合操作，但又并不依賴于特定的數。例如，在定義：
(define (cube x) (* x x x)) 時，我們讨論的并不是某個特定數值的立方，而是對任意的數得到其立方的方法。當然，我們也完全可以不去定義這一過程，而總是寫出下面這樣的表達式：
(* 3 3 3)
(* x x x)
(* y y y) 并不明确地提出cube。但是，這樣做将把自己置于一個非常糟糕的境地，迫使我們永遠在語言恰好提供了的那些特定基本操作（例如這裡的乘法）的層面上工作，而不能基于更進階的操作去工作。我們寫出的程式也能計算立方，但是所用的語言卻不能表述立方這一概念。人們對功能強大的程式設計語言有一個必然要求，就是能為公共的模式命名，建立抽象，而後直接在抽象的層次上工作。過程提供了這種能力，這也是為什麼除最簡單的程式語言外，其他語言都包含定義過程的機制的原因。
然而，即使在數值計算過程中，如果将過程限制為隻能以數作為參數，那也會嚴重地限制我們建立抽象的能力。經常有一些同樣的程式設計模式能用于若幹不同的過程。為了把這種模式描述為相應的概念，我們就需要構造出這樣的過程，讓它們以過程作為參數，或者以過程作為傳回值。這類能操作過程的過程稱為高階過程。本節将展示高階過程如何能成為強有力的抽象機制，極大地增強語言的表述能力。
1.3.1 過程作為參數
考慮下面的三個過程，第一個計算從a到b的各整數之和：
(define (sum-integers a b)
(if (> a b)
0
(+ a (sum-integers (+ a 1) b)))) 第二個計算給定範圍内的整數的立方之和：
(define (sum-cubes a b)
(if (> a b)
0
(+ (cube a) (sum-cubes (+ a 1) b)))) 第三個計算下面的序列之和：
它将（非常緩慢地）收斂49到?8：
(define (pi-sum a b)
(if (> a b)
0
(+ (/ 1.0 (* a (+ a 2))) (pi-sum (+ a 4) b)))) 可以明顯看出，這三個過程共享着一種公共的基礎模式。它們的很大一部分是共同的，隻在所用的過程名字上不一樣：用于從a算出需要加的項的函數，還有用于提供下一個a值的函數。我們可以通過填充下面模闆中的各空位，産生出上面的各個過程：
(define (<name> a b)
(if (> a b)
0
(+ (<term> a)
(<name> (<next> a) b)))) 這種公共模式的存在是一種很強的證據，說明這裡實際上存在着一種很有用的抽象，在那裡等着浮現出來。确實，數學家很早就認識到序列求和中的抽象模式，并提出了專門的“求和記法”，例如：
用于描述這一概念。求和記法的威力在于它使數學家能去處理求和的概念本身，而不隻是某個特定的求和—例如，借助它去形式化某些并不依賴于特定求和序列的求和結果。
與此類似，作為程式模式，我們也希望所用的語言足夠強大，能用于寫出一個過程，去表述求和的概念，而不是隻能寫計算特定求和的過程。我們确實可以在所用的過程語言中做到這些，隻要按照上面給出的模式，将其中的“空位”翻譯為形式參數：
(define (sum term a next b)
(if (> a b)
0
(+ (term a)
(sum term (next a) next b)))) 請注意，sum仍然以作為下界和上界的參數a和b為參數，但是這裡又增加了過程參數term和next。使用sum的方式與其他函數完全一樣。例如，我們可以用它去定義sum-cubes（還需要一個過程inc，它得到參數值加一）：
(define (inc n) (+ n 1))
(define (sum-cubes a b)
(sum cube a inc b)) 我們可以用這個過程算出從1到10的立方和：
(sum-cubes 1 10)
3025 利用一個恒等函數幫助算出項值，我們就可以基于sum定義出sum-integers：
(define (identity x) x)
(define (sum-integers a b)
(sum identity a inc b)) 而後就可以求出從1到10的整數之和了：
(sum-integers 1 10)
55 我們也可以按同樣方式定義pi-sum50：
(define (pi-sum a b)
(define (pi-term x)
(/ 1.0 (* x (+ x 2))))
(define (pi-next x)
(+ x 4))
(sum pi-term a pi-next b)) 利用這一過程就能計算出π的一個近似值了:
(* 8 (pi-sum 1 1000))
3.139592655589783 一旦有了sum，我們就能用它作為基本構件，去形式化其他概念。例如，求出函數f在範圍a和b之間的定積分的近似值，可以用下面公式完成
其中的dx是一個很小的值。我們可以将這個公式直接描述為一個過程：
(define (integral f a b dx)
(define (add-dx x) (+ x dx))
(* (sum f (+ a (/ dx 2.0)) add-dx b)
dx))
(integral cube 0 1 0.01)
.24998750000000042
(integral cube 0 1 0.001)
.249999875000001 （cube在0和1間積分的精确值是1/4。）
練習1.29 辛普森規則是另一種比上面所用規則更精确的數值積分方法。采用辛普森規則，函數f在範圍a和b之間的定積分的近似值是：
其中h＝(b－a)/n，n是某個偶數，而yk＝f(a＋kh)（增大n能提高近似值的精度）。請定義一個具有參數f、a、b和n，采用辛普森規則計算并傳回積分值的過程。用你的函數求出cube在0和1之間的積分（用n＝100和n＝1000），并将得到的值與上面用integral過程所得到的結果比較。
練習1.30 上面的過程sum将産生出一個線性遞歸。我們可以重寫該過程，使之能夠疊代地執行。請說明應該怎樣通過填充下面定義中缺少的表達式，完成這一工作。
(define (sum term a next b)
(define (iter a result)
(if <??>
<??>
(iter <??> <??>)))
(iter <??> <??>)) 練習1.31 a) 過程sum是可以用高階過程表示的大量類似抽象中最簡單的一個。請寫出一個類似的稱為product的過程，它傳回在給定範圍中各點的某個函數值的乘積。請說明如何用product定義factorial。另請按照下面公式計算π的近似值：
b) 如果你的product過程生成的是一個遞歸計算過程，那麼請寫出一個生成疊代計算過程的過程。如果它生成一個疊代計算過程，請寫一個生成遞歸計算過程的過程。
練習1.32 a) 請說明，sum和product（練習1.31）都是另一稱為accumulate的更一般概念的特殊情況，accumulate使用某些一般性的累積函數組合起一系列項：
(accumulate combiner null-value term a next b) accumulate取的是與sum和product一樣的項和範圍描述參數，再加上一個（兩個參數的）combiner過程，它描述如何将目前項與前面各項的積累結果組合起來，另外還有一個null-value參數，它描述在所有的項都用完時的基本值。請寫出accumulate，并說明我們能怎樣基于簡單地調用accumulate，定義出sum和product來。
b) 如果你的accumulate過程生成的是一個遞歸計算過程，那麼請寫出一個生成疊代計算過程的過程。如果它生成一個疊代計算過程，請寫一個生成遞歸計算過程的過程。
練習1.33 你可以通過引進一個處理被組合項的過濾器（filter）概念，寫出一個比accumulate（練習1.32）更一般的版本。也就是說，在計算過程中，隻組合起由給定範圍得到的項裡的那些滿足特定條件的項。這樣得到的filtered-accumulate抽象取與上面累積過程同樣的參數，再加上一個另外的描述有關過濾器的謂詞參數。請寫出filtered-accumulate作為一個過程，說明如何用filtered-accumulate表達以下内容：
a) 求出在區間a到b中所有素數之和（假定你已經寫出了謂詞prime?）。
b) 小于n的所有與n互素的正整數（即所有滿足GCD(i, n)＝1的整數i＜n）之乘積。
1.3.2 用lambda構造過程
在1.3.1節裡用sum時，我們必須定義出一些如pi-term和pi-next一類的簡單函數，以便用它們作為高階函數的參數，這種做法看起來很不舒服。如果不需要顯式定義pi-term和pi-next，而是有一種方法去直接刻畫“那個傳回其輸入值加4的過程”和“那個傳回其輸入與它加2的乘積的倒數的過程”，事情就會友善多了。我們可以通過引入一種lambda特殊形式完成這類描述，這種特殊形式能夠建立出所需要的過程。利用lambda，我們就能按照如下方式寫出所需的東西：
(lambda (x) (+ x 4)) (lambda (x) (/ 1.0 (* x (+ x 2)))) 這樣就可以直接描述pi-sum過程，而無須定義任何輔助過程了：
(define (pi-sum a b)
(sum (lambda (x) (/ 1.0 (* x (+ x 2))))
a
(lambda (x) (+ x 4))
b)) 借助于lambda，我們也可以寫出integral過程而不需要定義輔助過程add-dx：
(define (integral f a b dx)
(* (sum f
(+ a (/ dx 2.0))
(lambda (x) (+ x dx))
b)
dx)) 一般而言，lambda用與define同樣的方式建立過程，除了不為有關過程提供名字之外：
(lambda (\<formal-parameters>) \<body>) 這樣得到的過程與通過define建立的過程完全一樣，僅有的不同之處，就是這種過程沒有與環境中的任何名字相關聯。事實上，
(define (plus4 x) (+ x 4)) 等價于
(define plus4 (lambda (x) (+ x 4))) 我們可以按如下方式來閱讀lambda表達式：
(lambda (x) (+ x 4))
↑ ↑ ↑ ↑ ↑
該過程 以x為參數 它加起 x 和 4 像任何以過程為值的表達式一樣，lambda表達式可用作組合式的運算符，例如：
((lambda (x y z) (+ x y (square z))) 1 2 3)
12 或者更一般些，可以用在任何通常使用過程名的上下文中53。
用let建立局部變量
lambda的另一個應用是建立局部變量。在一個過程裡，除了使用那些已經限制為過程參數的變量外，我們常常還需要另外一些局部變量。例如，假定我們希望計算函數：
f(x, y)＝x(1＋xy)2＋y(1－y)＋(1＋xy)(1－y) 可能就希望将它表述為：
在寫計算 f 的過程時，我們可能希望還有幾個局部變量，不隻是x和y，還有中間值的名字如a和b。做到這些的一種方式就是利用輔助過程去限制局部變量：
(define (f x y)
(define (f-helper a b)
(+ (* x (square a))
(* y b)
(* a b)))
(f-helper (+ 1 (* x y))
(- 1 y))) 當然，我們也可以用一個lambda表達式，用以描述限制局部變量的匿名過程。這樣，f的體就變成了一個簡單的對該過程的調用：
(define (f x y)
((lambda (a b)
(+ (* x (square a))
(* y b)
(* a b)))
(+ 1 (* x y))
(- 1 y))) 這一結構非常有用，是以，語言裡有一個專門的特殊形式稱為let，使這種程式設計方式更為友善。利用let，過程f可以寫為：
(define (f x y)
(let ((a (+ 1 (* x y)))
(b (- 1 y)))
(+ (* x (square a))
(* y b)
(* a b)))) let表達式的一般形式是：
(let ((<var1> <exp1>)
(<var2> <exp2>)
(<varn> <expn>))
<body>) 可以将它讀作：
令 <var1> 具有值 <exp1> 而且
<var2> 具有值 <exp2> 而且
<varn> 具有值 <expn>
在 <body> 中 let表達式的第一部分是個名字-表達式對偶的表，當let被求值時，這裡的每個名字将被關聯于對應表達式的值。在将這些名字限制為局部變量的情況下求值let的體。這一做法正好使let表達式被解釋為替代如下表達式的另一種文法形式：
((lambda (<var1> ...<varn>)
<body>)
<exp1>
<expn>) 這樣，解釋器裡就不需要為提供局部變量增加任何新機制。let表達式隻是作為其基礎的lambda表達式的文法外衣罷了。
根據這一等價關系，我們可以認為，由let表達式描述的變量的作用域就是該let的體，這也意味着：
?let使人能在盡可能接近其使用的地方建立局部變量限制。例如，如果x的值是5，下面表達式
(+ (let ((x 3))
(+ x (* x 10)))
x) 就是38。在這裡，位于let體裡的x是3，是以這一let表達式的值是33。另一方面，作為最外層的＋的第二個參數的x仍然是5。
?變量的值是在let之外計算的。在為局部變量提供值的表達式依賴于某些與局部變量同名的變量時，這一規定就起作用了。例如，如果x的值是2，表達式：
(let ((x 3)
(y (+ x 2)))
(* x y)) 将具有值12，因為在這裡let的體裡，x将是3而y是4（其值是外面的x加2）。
有時我們也可以通過内部定義得到與let同樣的效果。例如可以将上述f定義為：
(define (f x y)
(define a (+ 1 (* x y)))
(define b (- 1 y))
(+ (* x (square a))
(* y b)
(* a b))) 當然，在這種情況下我們更願意用let，而僅将define用于内部過程54。
練習1.34 假定我們定義了：
(define (f g)
(g 2)) 而後就有：
(f square)
4
(f (lambda (z) (* z (+ z 1))))
6 如果我們（堅持）要求解釋器去求值（f f），那會發生什麼情況呢？請給出解釋。
1.3.3 過程作為一般性的方法
我們在1.1.4節裡介紹了複合過程，是為了作為一種将若幹操作的模式抽象出來的機制，使所描述的計算不再依賴于所涉及的特定的數值。有了高階過程，例如1.3.1節的integral過程，我們開始看到一種威力更強大的抽象，它們也是一類方法，可用于表述計算的一般性過程，與其中所涉及的特定函數無關。本節将讨論兩個更精細的執行個體—找出函數零點和不動點的一般性方法，并說明如何通過過程去直接描述這些方法。
通過區間折半尋找方程的根
區間折半方法是尋找方程 f(x)＝0根的一種簡單而又強有力的方法，這裡的 f 是一個連續函數。這種方法的基本想法是，如果對于給定點a和b有 f(a)＜0＜f(b)，那麼 f 在a和b之間必然有一個零點。為了确定這個零點，令x是a和b的平均值并計算出 f(x)。如果 f(x)＞0，那麼在a和x之間必然有的一個 f 的零點；如果 f(x)＜0，那麼在x和b之間必然有的一個 f 的零點。繼續這樣做下去，就能确定出越來越小的區間，且保證在其中必然有 f 的一個零點。當區間“足夠小”時，就結束這一計算過程了。因為這種不确定的區間在計算過程的每一步都縮小一半，所需步數的增長将是Q(log(L/T))，其中L是區間的初始長度，T是可容忍的誤差（即認為“足夠小”的區間的大小）。下面是一個實作了這一政策的過程：
(define (search f neg-point pos-point)
(let ((midpoint (average neg-point pos-point)))
(if (close-enough? neg-point pos-point)
midpoint
(let ((test-value (f midpoint)))
(cond ((positive? test-value)
(search f neg-point midpoint))
((negative? test-value)
(search f midpoint pos-point))
(else midpoint)))))) 假定開始時給定了函數 f，以及使它取值為負和為正的兩個點。我們首先算出兩個給定點的中點，而後檢查給定區間是否已經足夠小。如果是的話，就傳回這一中點的值作為回答；否則就算出 f 在這個中點的值。如果檢查發現得到的這個值為正，那麼就以從原來負點到中點的新區間繼續下去；如果這個值為負，就以中點到原來為正的點為新區間并繼續下去。還有，也存在着檢測值恰好為0的可能性，這時中點就是我們所尋找的根。
為了檢查兩個端點是否“足夠接近”，我們可以用一個過程，它與1.1.7節計算平方根時所用的那個過程很類似：
(define (close-enough? x y)
(< (abs (- x y)) 0.001)) search很難直接去用，因為我們可能會偶然地給了它一對點，相應的 f 值并不具有這個過程所需的正負号，這時就會得到錯誤的結果。讓我們換一種方式，通過下面的過程去用search，這一過程檢查是否某個點具有負的函數值，另一個點是正值，并根據具體情況去調用search過程。如果這一函數在兩個給定點的值同号，那麼就無法使用折半方法，在這種情況下過程發出錯誤信号。
(define (half-interval-method f a b)
(let ((a-value (f a))
(b-value (f b)))
(cond ((and (negative? a-value) (positive? b-value))
(search f a b))
((and (negative? b-value) (positive? a-value))
(search f b a))
(else
(error "Values are not of opposite sign" a b))))) 下面執行個體用折半方法求π的近似值，它正好是sin x＝0在2和4之間的根：
(half-interval-method sin 2.0 4.0)
3.14111328125 這裡是另一個例子，用折半方法找出x3－2x－3＝0在1和2之間的根：
(half-interval-method (lambda (x) (- (* x x x) (* 2 x) 3))
1.0
2.0)
1.89306640625 找出函數的不動點
數x稱為函數 f 的不動點，如果x滿足方程 f(x)＝x。對于某些函數，通過從某個初始猜測出發，反複地應用 f
f(x), f( f(x)), f( f( f(x))), . . .
直到值的變化不大時，就可以找到它的一個不動點。根據這個思路，我們可以設計出一個過程fixed-point，它以一個函數和一個初始猜測為參數，産生出該函數的一個不動點的近似值。我們将反複應用這個函數，直至發現連續的兩個值之差小于某個事先給定的容許值：
(define tolerance 0.00001)
(define (fixed-point f first-guess)
(define (close-enough? v1 v2)
(< (abs (- v1 v2)) tolerance))
(define (try guess)
(let ((next (f guess)))
(if (close-enough? guess next)
next
(try next))))
(try first-guess)) 例如，下面用這一方法求出的是餘弦函數的不動點，其中用1作為初始近似值：
(fixed-point cos 1.0)
.7390822985224023 類似地，我們也可以找出方程y＝sin y＋cos y的一個解：
(fixed-point (lambda (y) (+ (sin y) (cos y)))
1.0)
1.2587315962971173 這一不動點的計算過程使人回憶起1.1.7節裡用于找平方根的計算過程。兩者都是基于同樣的想法：通過不斷地改進猜測，直至結果滿足某一評價準則為止。事實上，我們完全可以将平方根的計算形式化為一個尋找不動點的計算過程。計算某個數x的平方根，就是要找到一個y使得y2＝x。将這一等式變成另一個等價形式y＝x/y，就可以發現，這裡要做的就是尋找函數yx/y的不動點58。是以，可以用下面方式試着去計算平方根：
(define (sqrt x)
(fixed-point (lambda (y) (/ x y))
1.0)) 遺憾的是，這一不動點搜尋并不收斂。考慮某個初始猜測y1，下一個猜測将是y2＝x/y1，而再下一個猜測是y3＝x/y2＝x/(x/y1)＝y1。結果是進入了一個無限循環，其中沒完沒了地反複出現兩個猜測y1和y2，在答案的兩邊往複振蕩。
控制這類振蕩的一種方法是不讓有關的猜測變化太劇烈。因為實際答案總是在兩個猜測y和x/y之間，我們可以做出一個猜測，使之不像x/y那樣遠離y，為此可以用y和x/y的平均值。這樣，我們就取y之後的下一個猜測值為 (1/2)(y＋x/y) 而不是x/y。做出這種猜測序列的計算過程也就是搜尋y (1/2)(y＋x/y) 的不動點：
(define (sqrt x)
(fixed-point (lambda (y) (average y (/ x y)))
1.0)) （請注意，y＝(1/2)(y＋x/y) 是方程y＝x/y經過簡單變換的結果，導出它的方式是在方程兩邊都加y，然後将兩邊都除以2。）
經過這一修改，平方根過程就能正常工作了。事實上，如果我們仔細分析這一定義，那麼就可以看到，它在求平方根時産生的近似值序列，正好就是1.1.7節原來那個求平方根過程産生的序列。這種取逼近一個解的一系列值的平均值的方法，是一種稱為平均阻尼的技術，它常常用在不動點搜尋中，作為幫助收斂的手段。
練習1.35 請證明黃金分割率f（1.2.2節）是變換x1＋1/x的不動點。請利用這一事實，通過過程fixed-point計算出f的值。
練習1.36 請修改fixed-point，使它能列印出計算中産生的近似值序列，用練習1.22展示的newline和display基本過程。而後通過找出xlog(1000)/log(x) 的不動點的方式，确定xx＝1000的一個根（請利用Scheme的基本過程log，它計算自然對數值）。請比較一下采用平均阻尼和不用平均阻尼時的計算步數。（注意，你不能用猜測1去啟動fixed-point，因為這将導緻除以log(1)＝0。）
練習1.37 a) 一個無窮連分式是一個如下形式的表達式：
作為一個例子，我們可以證明在所有的Ni和Di都等于1時，這一無窮連分式産生出1/f，其中的f就是黃金分割率（見1.2.2節的描述）。逼近某個無窮連分式的一種方法是在給定數目的項之後截斷，這樣的一個截斷稱為k項有限連分式，其形式是：
假定n和d都是隻有一個參數（項的下标i）的過程，它們分别傳回連分式的項Ni和Di。請定義一個過程cont-frac，使得對（cont-frac n d k）的求值計算出k項有限連分式的值。通過如下調用檢查你的過程對于順序的k值是否逼近1/f：
(cont-frac (lambda (i) 1.0)
(lambda (i) 1.0)
k) 你需要取多大的k才能保證得到的近似值具有十進制的4位精度？
b) 如果你的過程産生一個遞歸計算過程，那麼請寫另一個産生疊代計算的過程。如果它産生疊代計算，請寫出另一個過程，使之産生一個遞歸計算過程。
練習1.38 在1737年，瑞士數學家萊昂哈德·歐拉發表了一篇論文De Fractionibus Continuis，文中包含了e－2的一個連分式展開，其中的e是自然對數的底。在這一分式中，Ni全都是1，而Di依次為1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, …。請寫出一個程式，其中使用你在練習1.37中所做的cont-frac過程，并能基于歐拉的展開式求出e的近似值。
練習1.39 正切函數的連分式表示由德國數學家J.H. Lambert在1770年發表：
其中的x用弧度表示。請定義過程（tan-cf x k），它基于Lambert公式計算正切函數的近似值。k描述的是計算的項數，就像練習1.37一樣。
1.3.4 過程作為傳回值
上面的例子說明，将過程作為參數傳遞，能夠顯著增強我們的程式設計語言的表達能力。通過建立另一種其傳回值本身也是過程的過程，我們還能得到進一步的表達能力。
我們将闡釋這一思想，現在還是先來看1.3.3節最後描述的不動點例子。在那裡我們構造出一個平方根程式的新版本，它将這一計算看作一種不動點搜尋過程。開始時，我們注意到就是函數yx/y的不動點，而後又利用平均阻尼使這一逼近收斂。平均阻尼本身也是一種很有用的一般性技術。很自然，給定了一個函數 f 之後，我們就可以考慮另一個函數，它在x處的值等于x和 f（x）的平均值。
我們可以将平均阻尼的思想表述為下面的過程：
(define (average-damp f)
(lambda (x) (average x (f x)))) 這裡的average-damp是一個過程，它的參數是一個過程f，傳回值是另一個過程（通過lambda産生），當我們将這一傳回值過程應用于數x時，得到的将是x和（f x）的平均值。例如，将average-damp應用于square過程，就會産生出另一個過程，它在數值x處的值就是x和x2的平均值。将這樣得到的過程應用于10，将傳回10與100的平均值55：
((average-damp square) 10)
55 利用average-damp，我們可以重做前面的平方根過程如下：
(define (sqrt x)
(fixed-point (average-damp (lambda (y) (/ x y)))
1.0)) 請注意，看看上面這一公式中怎樣把三種思想結合在同一個方法裡：不動點搜尋，平均阻尼和函數yx/y。拿這一平方根計算的過程與1.1.7節給出的原來版本做一個比較，将是很有教益的。請記住，這些過程表述的是同一計算過程，也應注意，當我們利用這些抽象描述該計算過程時，其中的想法如何變得更加清晰了。将一個計算過程形式化為一個過程，一般說，存在很多不同的方式，有經驗的程式員知道如何選擇過程的形式，使其特别地清晰且易了解，使該計算過程中有用的元素能表現為一些互相分離的個體，并使它們還可能重新用于其他的應用。作為重用的一個簡單執行個體，請注意x的立方根是函數yx/y^2的不動點，是以我們可以立刻将前面的平方根過程推廣為一個提取立方根的過程：
(define (cube-root x)
(fixed-point (average-damp (lambda (y) (/ x (square y))))
1.0)) 牛頓法
在1.1.7節介紹平方根過程時曾經提到牛頓法的一個特殊情況。如果xg(x) 是一個可微函數，那麼方程g(x)＝0的一個解就是函數x f(x) 的一個不動點，其中：
這裡的Dg(x) 是g對x的導數。牛頓法就是使用我們前面看到的不動點方法，通過搜尋函數 f 的不動點的方式，去逼近上述方程的解61。對于許多函數，以及充分好的初始猜測x，牛頓法都能很快收斂到g(x)＝0的一個解62。
為了将牛頓方法實作為一個過程，我們首先必須描述導數的思想。請注意，“導數”不像平均阻尼，它是從函數到函數的一種變換。例如，函數x x3的導數是另一個函數x 3x2。一般而言，如果g是一個函數而dx是一個很小的數，那麼g的導數在任一數值x的值由下面函數（作為很小的數dx的極限）給出:
這樣，我們就可以用下面過程描述導數的概念（例如取dx為0.00001）：
(define (deriv g)
(lambda (x)
(/ (- (g (+ x dx)) (g x))
dx))) 再加上定義：
(define dx 0.00001) 與average-damp一樣，deriv也是一個以過程為參數，并且傳回一個過程值的過程。例如，為了求出函數x->x3在5的導數的近似值（其精确值為75），我們可以求值：
(define (cube x) (* x x x))
((deriv cube) 5)
75.00014999664018 有了deriv之後，牛頓法就可以表述為一個求不動點的過程了：
(define (newton-transform g)
(lambda (x)
(- x (/ (g x) ((deriv g) x)))))
(define (newtons-method g guess)
(fixed-point (newton-transform g) guess)) newton-transform過程描述的就是在本節開始處的公式，基于它去定義newtons-method已經很容易了。這一過程以一個過程為參數，它計算的就是我們希望去找到零點的函數，這裡還需要給出一個初始猜測。例如，為确定x的平方根，可以用初始猜測1，通過牛頓法去找函數y->y2－x的零點63。這樣就給出了求平方根函數的另一種形式：
(define (sqrt x)
(newtons-method (lambda (y) (- (square y) x))
1.0)) 抽象和第一級過程
上面我們已經看到用兩種方式，它們都能将平方根計算表述為某種更一般方法的執行個體，一個是作為不動點搜尋過程，另一個是使用牛頓法。因為牛頓法本身表述的也是一個不動點的計算過程，是以我們實際上看到了将平方根計算作為不動點的兩種形式。每種方法都是從一個函數出發，找出這一函數在某種變換下的不動點。我們可以将這一具有普遍性的思想表述為一個函數：
(define (fixed-point-of-transform g transform guess)
(fixed-point (transform g) guess)) 這個非常具有一般性的過程有一個計算某個函數的過程參數g，一個變換g的過程，和一個初始猜測，它傳回經過這一變換後的函數的不動點。
我們可以利用這一抽象重新塑造本節的第一個平方根計算（搜尋y->x/y在平均阻尼下的不動點），以它作為這個一般性方法的執行個體：
(define (sqrt x)
(fixed-point-of-transform (lambda (y) (/ x y))
average-damp
1.0)) 與此類似，我們也可以将本節的第二個平方根計算（是用牛頓法搜尋y y2－x的牛頓變換的執行個體）重新描述為：
(define (sqrt x)
(fixed-point-of-transform (lambda (y) (- (square y) x))
newton-transform
1.0)) 我們在1.3節開始時研究複合過程，并将其作為一種至關重要的抽象機制，因為它使我們能将一般性的計算方法，用這一程式設計語言裡的元素明确描述。現在我們又看到，高階函數能如何去操作這些一般性的方法，以便建立起進一步的抽象。
作為程式設計者，我們應該對這類可能性保持高度敏感，設法從中識别出程式裡的基本抽象，基于它們去進一步構造，并推廣它們以建立威力更加強大的抽象。當然，這并不是說總應該采用盡可能抽象的方式去寫程式，程式設計專家們知道如何根據工作中的情況，去選擇合适的抽象層次。但是，能基于這種抽象去思考确實是最重要的，隻有這樣才可能在新的上下文中去應用它們。高階過程的重要性，就在于使我們能顯式地用程式設計語言的要素去描述這些抽象，使我們能像操作其他計算元素一樣去操作它們。
一般而言，程式設計語言總會對計算元素的可能使用方式強加上某些限制。帶有最少限制的元素被稱為具有第一級的狀态。第一級元素的某些“權利或者特權”包括：
- 可以用變量命名；
- 可以提供給過程作為參數；
- 可以由過程作為結果傳回；
- 可以包含在資料結構中65。
Lisp不像其他程式設計語言，它給了過程完全的第一級狀态。這就給有效實作提出了挑戰，但由此所獲得的描述能力卻是極其驚人的66。
練習1.40 請定義一個過程cubic，它和newtons-method過程一起使用在下面形式的表達式裡：
(newtons-method (cubic a b c) 1) 能逼近三次方程x3＋ax2＋bx＋c的零點。
練習1.41 請定義一個過程double，它以一個有一個參數的過程作為參數，double傳回一個過程。這一過程将原來那個參數過程應用兩次。例如，若inc是個給參數加1的過程，（double inc）将給參數加2。下面表達式傳回什麼值：
(((double (double double)) inc) 5) 練習1.42 令 f 和g是兩個單參數的函數，f 在g之後的複合定義為函數x f(g(x))。請定義一個函數compose實作函數複合。例如，如果inc是将參數加1的函數，那麼：
((compose square inc) 6)
49 練習1.43 如果 f 是一個數值函數，n是一個正整數，那麼我們可以構造出 f 的n次重複應用，将其定義為一個函數，這個函數在x的值是 f( f(…( f(x))…))。舉例說，如果 f 是函數x x＋1，n次重複應用 f 就是函數x x＋n。如果 f 是求一個數的平方的操作，n次重複應用 f 就求出其參數的2n次幂。請寫一個過程，它的輸入是一個計算 f 的過程和一個正整數n，傳回的是能計算 f 的n次重複應用的那個函數。你的過程應該能以如下方式使用：
((repeated square 2) 5)
625 提示：你可能發現使用練習1.42的compose能帶來一些友善。
練習1.44 平滑一個函數的想法是信号進行中的一個重要概念。如果 f 是一個函數，dx是某個很小的數值，那麼 f 的平滑也是一個函數，它在點x的值就是 f(x－dx)、f(x) 和 f(x＋dx) 的平均值。請寫一個過程smooth，它的輸入是一個計算 f 的過程，傳回一個計算平滑後的 f 的過程。有時可能發現，重複地平滑一個函數，得到經過n次平滑的函數（也就是說，對平滑後的函數再做平滑，等等）也很有價值。說明怎樣利用smooth和練習1.43的repeated，對給定的函數生成n次平滑函數。
練習1.45 在1.3.3節裡，我們看到企圖用樸素的方法去找y->x/y的不動點，以便計算平方根的方式不收斂，這個缺陷可以通過平均阻尼的方式彌補。同樣方法也可用于找立方根，将它看作平均阻尼後的y->x/y^2的不動點。遺憾的是，這一計算過程對于四次方根卻行不通，一次平均阻尼不足以使對y->x/y^3的不動點搜尋收斂。而另一方面，如果我們求兩次平均阻尼（即，用y->x/y^3的平均阻尼的平均阻尼），這一不動點搜尋就會收斂了。請做一些試驗，考慮将計算n次方根作為基于y->x/yn－1的反複做平均阻尼的不動點搜尋過程，請設法确定各種情況下需要做多少次平均阻尼。并請基于這一認識實作一個過程，它使用fixed-point、average-damp和練習1.43的repeated過程計算n次方根。假定你所需要的所有算術運算都是基本過程。
練習1.46 本章描述的一些數值算法都是疊代式改進的執行個體。疊代式改進是一種非常具有一般性的計算政策，它說的是：為了計算出某些東西，我們可以從對答案的某個初始猜測開始，檢查這一猜測是否足夠好，如果不行就改進這一猜測，将改進之後的猜測作為新的猜測去繼續這一計算過程。請寫一個過程iterative-improve，它以兩個過程為參數：其中之一表示告知某一猜測是否足夠好的方法，另一個表示改進猜測的方法。iterative-improve的傳回值應該是一個過程，它以某一個猜測為參數，通過不斷改進，直至得到的猜測足夠好為止。利用iterative-improve重寫1.1.7節的sqrt過程和1.3.3節的fixed-point過程。