📌 30 秒摘要（Layer 3）
這本書不談語言細節，而教一套可重複套用的設計流程：面對空白畫面時，不要憑靈感，而是照「設計訣竅（Design Recipe）」六個步驟一步步推導——問題分析和資料定義 → 合約/用途說明/函數頭部 → 例子 → 函數模板 → 函數定義 → 測試。真正的價值不在這六步本身，而在它是一整個訣竅家族：書後面每遇到一種新的資料或問題型態（自引用資料、相似定義、生成遞迴、累積器、狀態變數），就在這個骨幹上把某一步展開、或再加一步。核心信念是「程式設計可以教」——而且教的方式是給你一份能自我檢核的清單。
🗺 心智圖（Canvas）
程式設計方法
Link to original 📙 程式設計方法
How to Design Programs (HtDP)
訣竅家族：一個骨幹，五種變體
📐 骨幹 The Recipe
🎯 什麼情境該想到我
當你面對一個新函式／問題，不知道從何下手、容易憑感覺亂寫時。
書把這件事的起因講得很清楚：程式設計要考慮的步驟很多——判斷問題描述中哪些資訊相關、釐清輸入輸出與它們的關係、查明語言有沒有現成的基本操作、寫完還要驗證測試——而**「要解決這些表面上混亂的情況，必須建立一些程式設計原則，即，規定完成任務的順序以及每步怎麼做」**（p.8）。
還有一個更現實的理由：語法錯誤和執行錯誤有程式設計環境幫你抓，但邏輯錯誤不會。書上把
wage寫成(+ 12 h)的例子，每次執行都會產生一個數值，甚至(wage 12/11)還會剛好算對——「只有細心和系統化地設計程式，程式設計者才能捕獲到此類錯誤」（p.8）。
⚙️ 怎麼用
全書的骨架：六個步驟（前言 圖 0.1）
書在前言就把完整的訣竅攤開了，而且明說**「圖 0.1 給出的設計訣竅包含了 6 個程式設計基本步驟，每個步驟都將產生定義明確的中間結果」**（前言 p.II）：
# 步驟（圖 0.1） 產生的中間結果（前言 p.II） 1 問題分析和資料定義 問題資料型別描述 2 合約，用途說明與結果的描述，函數頭部 程式行為的非形式描述 3 例子 說明程式行為的例子 4 函數模板 開發程式的模板或視圖 5 函數定義 把模板轉換成完整的定義 6 測試 通過測試發現錯誤 第 2 章的入門版：圖 2.2
「基於到目前為止所得到的經驗，設計一個程式至少需要如下 4 個步驟」（p.8）
第 2 章處理的是「輸入是數、輸出是數」這種最單純的情況，這時還沒有資料定義可分析、也還沒有模板可推，所以圖 2.2「設計訣竅一覽」只剩四個階段：合約／用途說明和函數頭部／例子／主體／測試（p.10）。下面逐階段附上圖 2.2 的目標與任務欄——這是最容易上手的入門版本，第 1 步與第 4 步等資料變複雜之後才會長出來（見文末「相關工具」）。
1. 合約（contract）
目標：給函數命名
任務：給函數起一個合適的名字（圖 2.2，p.10）「在開發程式時應該給每一個程式一個有意義的名字，並且說明輸入資料和所產生的資料的類型，這稱為程式的合約」（p.8）。合約寫成一行註解，冒號左邊是名字、右邊是輸入與輸出的類型，中間用箭頭隔開：
;; area-of-ring : number number -> number（p.8。書的註腳：輸入箭頭的方法是先鍵入
-再鍵入>。）2. 用途說明和函數頭部
目標：指定輸入和輸出的類型／描述函數的用途說明／闡明函數頭部
任務：以函數需要的未知數為線索研究問題；給每個輸入起一個名字，如果可能的話，使用在問題描述中給定的名字；使用選擇的變數名描述函數應該產生什麼結果；闡明合約和函數頭部（圖 2.2，p.10）圖 2.2 直接給了要填的骨架（p.10）：
;; name : number ...--> number ;; to compute ... from x1 ... (define (name x1 ...) ...)
- 函數頭部**「複述了程式的名字，同時給每個輸入一個不同的名字，它們是（代數）變數，是程式的參數」**（p.8）。
- 用途說明是**「基於合約和參數，簡要闡明一下程式的用途，它是程式要完成的任務的簡短注釋。對於大多數程式，一到兩行就足夠了，更大的程式則需要更多的資訊來說明其目的」**（p.9）。
- 書給的兩個找輸入的線索（p.9）：
- 「如果問題表述包含了數學公式，公式中不同變數的數目可能就是函數的輸入數。」
- 「如果給定的是一個固定數值，它可能要在程式中出現，如果給定的是一個稍後需要確定的未知數，它就是一個輸入，而問題表述中的詢問（或要求）則提示了程式的名字。」
完成後長這樣（p.9）：
;; area-of-ring : number number -> number ;; 計算一個半徑為 outer，洞的半徑為 inner 的環的面積 (define (area-of-ring outer inner) ...)3. 例子
目標：通過例子刻劃輸入和輸出之間的關係
任務：檢查問題表述得到例子；計算例子；如果可能的話檢查計算結果；構造例子（圖 2.2，p.10）「為了更好地了解程式要計算什麼，需要構造一些輸入並確定輸出到底為何」，然後把例子寫進用途說明裡（p.9）：
;; 例子: (area-of-ring 5 3) 的結果為 50.24書列了三個「為什麼要在寫程式體之前先寫例子」的理由（p.9）：
- 「它是唯一可靠的在程式測試中發現邏輯錯誤的途徑。如果借助最終得到的程式來構造例子，有可能會輕信程式，因為運行程式比預測它會做什麼容易得多。」
- 「例子使我們思考資料計算過程，這對於將遇到的複雜程式體的設計是至關重要的。」
- 「例子是用途說明語句的非形式表達。」 後續的讀者——教師、同事、程式購買者——「會喜歡這些抽象概念的具體說明」。
4. 主體（程式體）
目標：定義函數
任務：闡明函數是如何計算它的結果的；使用 Scheme 基本運算、其他函數和變數構造 Scheme 表達式；如果可以的話，翻譯問題描述中的數學公式（圖 2.2，p.10）也就是**「必須將函數頭部中的『…』替換為表達式」，而這個表達式「使用 Scheme 中的基本操作和已定義或即將定義的程式，從參數計算出結果」**（p.9）。
前提條件書講得很硬：「只有理解了如何從給定的輸入計算出結果，才可能闡明程式體。」 至於怎麼寫得出來——公式題就翻譯公式，敘述題就**「細心地挖掘其中的資訊並構造相應的表達式」，而且「觀察並理解如何從特定的輸入得到輸出的例子可能對程式體的設計也會有所幫助」**（p.9）。
5. 測試
目標：發現錯誤（語法和邏輯錯誤）
任務：應用函數於例子中的輸入資料；檢查結果與預期值是否相符（圖 2.2，p.10）做法就是把第 3 步的例子**「如同添加等式一樣」**加在定義窗口下面，按執行、看結果對不對（p.9）。
測試的能力邊界書也寫死了：「測試不能保證程式對所有可能的輸入都產生正確的輸出，因為可能的輸入數目通常是無限的。但測試可以揭示語法錯誤、運行問題以及邏輯錯誤。」（p.9）
結果不對的時候，書要你先懷疑例子本身：「有可能例子本身就是錯誤的，也有可能程式包含了邏輯錯誤，也有可能例子和程式都有錯誤。不管是何種情況，都必須再次歷經程式開發的每一步。」（p.9）
圖 2.1：一個完整走完的例子（p.10）
;; 合約: area-of-ring : number number -> number ;; 用途說明: 計算一個半徑為 outer，其中洞的半徑為 inner 的環的面積 ;; 例子: (area-of-ring 5 3) 的計算結果為 50.24 ;; 定義: [函數頭部的精化] (define (area-of-ring outer inner) (- (area-of-disk outer) (area-of-disk inner))) ;; 測試: (area-of-ring 5 3) ;; 預期的值 50.24注意最後成品裡，合約、用途說明、例子全部以註解的形式留在程式碼裡，測試與預期值也留著——每一步的產物一個都沒有丟掉。
🧪 我實際套用的紀錄
- 2026-07-14：（待填）
⚠️ 注意
- 訣竅不會幫你想出答案。 書講得毫不客氣：「設計訣竅並不是核彈」、「它提供的是完成程式設計過程中不可避免的步驟的指導」；而且**「在程式設計中最富有創新性和最困難的一步是程式體的設計」**（p.10）。訣竅整理的是流程，不是靈感。
- 卡住的原因常常不在程式設計，而在領域。 程式體的設計**「依賴於我們閱讀和理解書面材料的能力，依賴於我們獲取數學關係的能力，依賴於我們所掌握的基本事實」（p.10）。書把這種知識稱為領域知識**：它**「可能來自簡單或複雜的數學，如算術和微分方程，或來自非數學學科，如音樂、生物學、市政工程和藝術等」（p.10）。程式設計者不可能懂所有領域，但「必須準備著去了解不同應用領域的語言，以便和領域專家溝通」**（p.10）。
- 步驟感覺繁瑣，但對「不熟的問題」最省時；熟練後會內化成直覺。（個人註記，非書中原文）
🔗 相關工具
這張卡是訣竅家族的基本款。 前言圖 0.1 的六步驟是全書骨幹，第 2 章的圖 2.2 是它在「輸入是數、輸出是數」情況下的入門版；書之後每遇到一種新的資料或問題型態，就在這個骨幹上把某一步展開、或再加一步。要處理下列情況時，改用對應的加強版：
- 工具-資料驅動的模板推導 —— 輸入是複合／自引用／相互引用資料時，「主體」前面要多一步從資料定義推出模板。書第 16 章示範相互引用的 dir 與 LOFD 時就說：「要設計一個處理 dir 的函數，我們必須並行地開發 dir 處理函數和 LOFD 處理函數的模板」（p.134）。
- 工具-從相似定義提煉抽象 —— 手上出現兩個長得很像的定義，要把它們合成一個時。
- 工具-生成遞迴與終止論證 —— 遞迴不照資料結構走時，比結構遞迴多出一步終止論證。
- 工具-累積器與累積器不變式 —— 遞迴過程中「丟失知識」時，用累積器把知識帶下去（那是做完訣竅之後才加的一步）。
- 工具-狀態變數的設計訣竅 —— 程式需要記住過去發生過什麼時。
- 工具-逐步求精 —— 反覆精化：處理的不是單一函式，而是複雜資訊的資料表示法該怎麼一步步做出來。
- 工具-偽代碼編程流程 —— 姊妹流程，都是「先寫描述再寫程式」，PPP 更偏實務常式的寫法。
- 回連 程式設計方法
🧱 先把資料表示法做對
🎯 什麼情境該想到我
當你要替一堆複雜的真實世界資訊設計資料表示法，一次想不齊、越想越亂的時候。
「在設計真正的函數時，常常會遇到這樣的任務，要求設計複雜形式資訊的資料表示法。完成這種任務最好的方法是使用一種著名的科學方法：反覆精化。」（p.131）
注意這張卡的對象是資料表示法，不是「功能」或「進度」。書給的理由是：「既然資料表示法在程式設計者的工作中起了主導作用，問題的關鍵就是找出真實世界資訊的精確資料表示法。」（p.132）
⚠️ 別跟 stepwise refinement 搞混。 書講的「反覆精化」精化的是資料表示法；Wirth 那套「逐步求精」是把一個抽象步驟逐層展開成實作。名字像，做的事不同。要「先做能跑的最小版本再長肉」，那是 工具-曳光彈開發，不是這張。
⚙️ 怎麼用
先看書借來的類比：科學家怎麼建模型
「科學家們使用數學來表示真實世界，他們努力所得的結果稱為模型。科學家們會使用多種方法測試模型，特別是使用模型來預測世界的屬性。如果模型真的描述了真實世界的本質，那麼這樣作出的預言就是準確的；否則，在預言和實際結果之間就會有矛盾。」（p.131）
書的例子：物理學家**「可能用一個點來表示噴射機，然後使用牛頓方程預測它的運動軌跡為一條直線。後來，如果需要求飛機所受的摩擦力，該物理學家可能會在模型中加上飛機的輪廓線，用來表示其外形」——「一般來說，科學家會改進模型，重新測試它的有效性，直至模型充分準確為止。」**（p.132）
「程式設計者或者計算機科學家應該進行和科學家一樣的行動。」（p.132）
方法本體
「在複雜情形下，要做到這一點的最好方法就是反覆設計表示法，從問題的基本元素開始，在充分理解當前模型後，再添加問題的更多特徵。」（p.132）
拆成可執行的步驟：
先做資料分析，決定看哪裡、忽略什麼。
「需要做的第一個決定是，該把注意力集中在哪裡，又該忽略什麼東西。」（p.133）
書處理檔案系統時，明講**「就我們的用途而言，檔案就像是表；我們忽略為什麼計算要永久地存儲檔案，以及它是怎樣永久存儲檔案的」**（p.132）。想清楚要忽略什麼，跟想清楚要表示什麼一樣重要。
第一個模型只放最基本的元素，能多粗就多粗。 書的模型一把檔案當成**「一個代表檔名的符號」，目錄當成「包含檔案和目錄的表」**（p.133）。
充分理解當前模型再往下走——包括拿它去寫函式。模型一寫完就發現**「目錄類型就是第 14.3 節中的網頁類型。因此，我們可以重用網頁處理函數的模板來處理目錄樹」**（p.133），並配了
how-many之類的習題把模型用過一遍。找出當前模型「藏起來」的東西，加進下一版。 這是往下一版走的判準，書寫得很直接：
「雖然我們很熟悉第一個資料定義，而且它用起來也很方便，但是它隱藏了目錄的本質。具體說來，它隱藏了這樣一個事實，即目錄並不只是檔案和目錄的集合，它還有一些有趣的屬性。」（p.133）
於是模型二引入結構體
(define-struct dir (name content))，「它表明目錄有名字，有內容；現在，如果需要的話，我們還可以加上其他的屬性」（p.133）。一次只加一類特徵，加完就把資料定義重寫一遍。 模型二只補上目錄的屬性；模型三才輪到檔案：「第二個資料定義改進了第一個資料定義，引入了目錄的屬性。檔案也有屬性。要建立檔案屬性的模型，我們還是一樣處理。」（p.134）模型三於是有了
(define-struct file (name size content))，並把 dir 的 content 欄位拆成檔案的表與子目錄的表（p.134-135）。每一版都重新檢查資料定義之間的引用關係，該同時引入的就同時引入。
「因為 dir 的資料定義引用了 LOFD 的定義，而 LOFD 的定義又反過來引用了 dir 的資料定義，所以它們是相互引用的定義，必須同時被引入。」（p.134）
停在「抓住本質」的那一版，然後用它開發函式。
「這第三個目錄層次的（資料表示法）模型抓住了檔案系統的本質，至少是用戶一般可以觀察到的本質。不過，它有兩個結構體定義，四個資料定義，比第一個模型複雜的多。但是，從第一個模型的簡單表示法開始，通過一步一步地改進，我們理解了如何處理這種複雜類型的組織。」（p.135）
接下來的工作是**「使用第 15.2 節中的設計訣竅來開發處理這個資料定義集合的函數，不然的話，我們就完全沒有辦法來理解這種定義」**（p.135）。書第 16.3 節就是拿最精確的模型去寫
how-many、du-dir、find?等函式（p.135-136）。三個模型的演進（書第 16 章的檔案系統例子）
版本 表示什麼 加了什麼 / 為什麼要往下一版 模型一（p.133） file 是符號；dir 是「empty／(cons f d)／(cons d1 d2)」 最原始：檔案＝基本實體，目錄＝容器。優點是「就是第 14.3 節的網頁類型」，模板可直接重用 模型二（p.133-134） (define-struct dir (name content))；dir 與 LOFD 相互引用因為模型一「隱藏了目錄的本質」——目錄有屬性。相互引用的定義必須同時引入 模型三（p.134-135） (define-struct file (name size content))、(define-struct dir (name dirs files))、list-of-files、list-of-directories檔案也有屬性；dir 的 content 再拆成檔案表與子目錄表。兩個結構體定義、四個資料定義 這不是第 16 章才發明的一次性技巧
「本書已經在許多補充練習中使用了反覆精化。例如，移動圖形的練習從簡單的圓和矩形開始；後來，開發了移動整個圖形的程式。類似地，我們先以單詞和嵌入網頁表的形式引入了網頁；在第 15.3 節中，我們改進了嵌入網頁的表示法。不管怎樣說，對於所有這些練習，改進都是建立在表示法上的。」（p.132）
最後一句是這張卡的判準：精化的對象是表示法。
🧪 我實際套用的紀錄
- 2026-07-14：（待填）
⚠️ 注意
- 精化的對象是資料表示法，不是「功能」。 書自己劃了這條線：「對於所有這些練習，改進都是建立在表示法上的」（p.132）。本章沒有談「先做能跑的最小版本再逐個加功能」這類交付順序的問題。
- 越精確不等於越好用。 模型三「比第一個模型複雜的多」（p.135）；模型一雖然粗，但因為型別剛好等於既有的網頁類型，模板可以整套重用（p.133）。精化到夠用就停。
- 要決定忽略什麼。 書把「檔案為什麼能永久保存、怎麼永久保存」整個排除在模型外（p.132）；不排除就做不出第一版。
- 精化只給你資料定義，函式還是要照設計訣竅走。 第三個模型做完，書的下一句話是「現在，我們的任務是，使用第 15.2 節中的設計訣竅來開發處理這個資料定義集合的函數」（p.135）。
- 模型要拿去用才知道對不對。 每個模型後面書都掛了習題：把圖 16.1 的檔案系統轉成該模型的 Scheme 表示、用該模型開發
how-many（習題 16.2.1、16.2.2、16.2.4、16.2.5、16.3.1、16.3.2）。對應到科學家的類比就是「使用模型來預測世界的屬性」（p.131）。
🔗 相關工具
- 工具-設計訣竅 —— 反覆精化產出資料定義之後，函式仍然照設計訣竅開發（p.135）。
- 工具-資料驅動的模板推導 —— 精化的產物是資料定義，而模板是從資料定義推出來的：第 16 章的模型二一定案，書就說「要設計一個處理 dir 的函數，我們必須並行地開發 dir 處理函數和 LOFD 處理函數的模板」（p.134）。
- 回連 程式設計方法
🎯 什麼情境該想到我
當你「已經知道輸入長什麼樣，卻不知道函式的骨架該怎麼寫」的時候。
書把這件事講得很直白：「從資料定義到模板是設計函式過程中的主要步驟」，而且**「函式輸入的資料定義往往在很大程度上決定函式的形狀」（p.79）。骨架不是想出來的，是從資料定義推**出來的。
⚙️ 怎麼用
先寫下資料定義，再照下面的規則機械地把模板抄出來。三種資料型態，三條規則。
規則一：看到「複合資料（結構體）」→ 模板就是一排選擇器，沒有分支
資料有 N 個欄位 → 模板主體就列出 N 個選擇器表達式，一個欄位一行 沒有 cond，因為資料定義裡沒有「兩者之一」 剩下的問題只有一個：「這 N 個值要怎麼組成答案」
- 資料分析時就對齊了：「如果發現一個對象有 N 個屬性，可以引入一個有 N 個字段的結構體」（p.37）
- 反過來推模板：「parent 的結構體定義指定了四個字段，所以模板中有四個表達式」（p.127）
- 這個模板不看輸出，所以可以重複用、而且可以在寫例子之前就寫好
「模板包括函數頭部和主體，主體中列出了所有可能的選擇器表達式。」
「換句話說，模板表示了程序對於輸入的了解，並不涉及輸出。所有輸入相同的函數可以使用相同的模板。另外，由於模板與目的無關，可以在例子之前闡述。」（p.38）圖 6.5 把這條規則壓成一句話：「若參數是複合資料，使用選擇器表達式填寫主體 / 如果函數是條件式的，寫出所有合適的分枝」（p.40）。
規則二：看到「自引用資料定義」→ 模板必然是兩支
1. 資料定義有幾個子句，cond 就有幾支 2. 不含自引用的那一支 = 基本情況（空 / 沒有下一層）→ 直接給答案 3. 含自引用的那一支：先用選擇器把各部分取出來， 再對「自引用的那一欄」呼叫函式自己 然後只剩一個問題：「怎麼把這兩者的值合起來」書用三個小步驟示範這條推導（p.78-79 的
sum）：
- 「第一步，添上 cond 表達式」
- 「第二步，為每個子句添上合適的選擇器表達式」
- 「最後一步，添上遞迴，也就是處理資料定義中的自引用部分」
分支數量不是憑感覺定的：
「自引用的數據定義所描述的是混合數據類型，其中每個子句描述一種子類型……特別地，每個條件子句與一種數據定義相對應，因此 cond 表達式的子句數應該和數據定義的子句數一樣。」（p.76）
遞迴呼叫的位置也不是憑感覺定的——書要你逐條檢查選擇器：
「另外，檢查每一個選擇器表達式，如果某個選擇器表達式的返回值類型與函數的輸入數據類型一致，就用箭頭把它和函數的參數連接起來。最後得到的箭頭數目必然與數據定義中的箭頭數目相同。」（p.76）
書把這種自呼叫命名為**「自然遞迴」**（p.76）。
寫主體的順序也被定死了：「設計主體從不包含自然遞迴的那些 cond 子句開始。這些子句被稱為基本情況，它們所對應的答案一般已由例子給出，或者很容易得到。」 然後才處理自引用那支，而且**「對於那些遞迴調用，我們假設函數已經能夠按照我們指定的用途說明工作，剩下的問題就是把不同的值結合起來」**（p.76）。
那個「合起來」的動作，書也給了選項：「在許多情況下，可以使用 Scheme 的基本操作，如 +，and 或 cons。如果問題描述包含了對第一個元素的處理說明，我們可能還需要使用嵌套的 cond 語句。最後，在某些情況下，可能還需要定義輔助函數。」（p.77）
圖 9.2 的模板列就是這條規則的檢查清單（p.77）：
對於每種可能情況都設計一個 cond 表達式
對於每個子句添加選擇器
將主體標記為遞迴
測試模板中的自引用是否與數據定義匹配規則三：看到「相互引用的資料定義」→ 一次生出一組互相呼叫的函式
有幾個互相引用的資料定義，就同時開幾個模板、幾份合約 每個模板各自照規則一或規則二寫（該有 cond 的才有 cond） 資料定義之間的箭頭 → 模板之間的互相呼叫 資料定義之內的箭頭 → 該模板的自我遞迴 從「既沒有自引用、也沒有相互引用」的那個子句開始填答案書說這只是前兩條規則的一般化，只多兩件事：
「對自引用數據定義的函數設計訣竅一般化，就可得到相互引用數據定義的函數設計訣竅。事實上，為了處理相互引用的數據定義，只需要增加兩條建議。第一條，我們必須同時建立多個模板，每個模板對應一個數據定義；第二條，我們必須用自引用和相互引用來註釋模板，所謂相互引用，就是不同模板之間的相互引用。」（p.129）
函式的數量也由資料定義的數量決定：「要處理數據類型的相互聯繫，需要和數據定義數量一樣多的函數。因此，我們必須並行地給出和數據定義一樣多的合約、用途說明以及頭部。」（p.129）而**「模板須遵循關於複合數據、混合數據以及自引用數據的建議並行建立」**（p.129）——也就是說規則一、規則二沒有被取代，只是被同時套用。
書的示範清楚說明「有沒有 cond」完全看資料定義（p.130）：
「fun-parent 模板中沒有條件，因為 parent 的數據定義中並不包含任何子句，而是包含對第二個模板的相互引用：處理 parent 結構體的 children 字段。按照同樣的規則，fun-children 是一個條件式，第二個 cond 子句中包含了一處自引用，處理表的 rest 部分，以及對表的 first 元素——即 parent 結構體——的一處相互引用。」
寫出來的成品就是一組互相呼叫的函式：「與其他函數群體不同，這兩個函數相互引用，是相互遞迴的。毫不令人驚奇的是，函數定義中的相互引用對應於數據定義中的相互引用。」（p.128）
圖 15.4 的清單（p.130）：
同時開發與數據定義一樣多的模板
·遵照複合數據和/或混合數據的規則正確開發每一個模板
·根據數據定義中的（相互）引用，用遞迴和相互調用註釋模板（主體）給出每一個模板和模板中 cond 子句的 Scheme 表達式
·解釋模板中的每個表達式計算出什麼
·在需要時，使用額外的輔助函數填答案的起點同樣被指定了：「在開始創作最後的定義時，我們要從一個模板或 cond 子句開始，這個模板中應該不包含自引用以及對其他模板的相互引用。對於這樣的模板或 cond 子句，結果一般較為易於給出。」（p.130）
三條規則的共同形狀
資料定義長什麼樣 模板必然長什麼樣 N 個欄位的結構體 N 個選擇器表達式，無 cond 「下列兩者之一」＋其中一支引用自己 cond 兩支；非自引用支＝基本情況；自引用那一欄→遞迴呼叫自己 多個定義互相引用 多個模板同時建立；定義間的引用→函式間的互相呼叫 推完模板之後，永遠只剩同一個問題：把手上這幾個值結合成答案。
🧪 我實際套用的紀錄
- （待填）
⚠️ 注意 / 什麼時候不適用
書中明講的限制：
- 模板不編碼欄位的型別。 書自己點名了這個缺口：「最終的模板幾乎已經包含了數據定義的每一個方面：兩個子句，第二個子句中的 cons 結構，以及第二個子句中的自引用。數據定義中唯一沒有在函數模板中得到反映的部分是，cons 結構的第一個部分是數。」（p.79）→ 模板保證形狀對，不保證你沒把符號當數字用。
- 模板不告訴你輸出。 「模板表示了程序對於輸入的了解，並不涉及輸出。」（p.38）→ 推導只給骨架，答案還是要自己想；也因此**「所有輸入相同的函數可以使用相同的模板」（p.38），而「模板可以被重用多次，這也意味著例子的構造應該在模板設計之後」**（p.39）。
- 遞迴資料定義本身要合法，規則二才有意義。 「要使遞迴的數據定義有意義，必須滿足兩個條件：第一，該定義必須至少含有兩條子句；第二，其中至少有一條子句不能引用定義自身。」（p.76）→ 資料定義寫壞了，推出來的模板也是壞的（沒有基本情況＝沒有出口）。
- 模板只管到骨架，複雜的地方還是要拆。 圖 9.2 與圖 15.4 都留了同一句：「在某些情況下，可能還需要定義輔助函數」（p.77）／「在需要時，使用額外的輔助函數」（p.130）。
- 自引用資料的觸發條件是「任意長」。 「若問題描述涉及任意長的複合信息，就需要使用遞迴或者是自引用數據。」（p.75）→ 長度固定的東西不該套規則二；書處理三個數的表時，用的是三層
first/rest的直線模板而非遞迴（p.71）。我從書中內容直接推出的邊界（非書中原文）：
- 這套推導的前提是你已經先寫出資料定義。書把「資料分析和設計」排在模板之前（圖 6.5 p.40、圖 9.2 p.77、圖 15.4 p.130），資料定義沒寫，就沒有東西可推。
- 資料定義本身是可以被違反的——書的註腳提醒「數據定義事實上只是一份書面意圖聲明，但任何有意或無意違反該聲明的人都將面臨異常的計算結果」（p.36）。所以模板推導的正確性，上限就是資料定義的誠實程度。
🔗 相關工具
- 工具-設計訣竅 —— 本卡是設計訣竅裡「模板」那一步的放大版。書中三張表都是同一份訣竅的精化：圖 6.5 標明是「圖 2.2 中設計訣竅的精化」（p.40），圖 15.4 註明「基本步驟；其他的步驟請參見圖 2.2、圖 6.5 及圖 7.3」（p.131）。合約、例子、測試那幾步請看那張卡。
- 工具-生成遞迴與終止論證 —— 這張卡處理的是由資料定義驅動的結構遞迴（遞迴呼叫的位置由自引用欄位決定，因此不必另外論證會終止）；那張處理的是另一種遞迴。註：本卡的三個來源章節（第 6、9、15 章）並未討論那種遞迴，兩者的關係說明由卡片維護者標注，不出自本卡引用的頁面。
- 回連 程式設計方法
🔁 遞迴的兩種
🎯 什麼情境該想到我
當你的遞迴不是拿輸入的某一部分去遞迴，而是自己算出一份全新的資料再遞迴時（快速排序、輾轉相除法、模擬迴圈都是），你就不能再假設它會自己停下來——這時要想到我。
一句話判別（p.226）：
所有自我引用的結構遞迴函式總是使用當前輸入的某個直接部分作為下一步的輸入，對它進一步處理。……因此，如果某個函式的參數是一個普通的表，而且它並不使用表的其餘部分進行遞迴，那麼這個函式定義就不是結構遞迴的，而是生成遞迴的。
書把這種函式直接叫做演算法：「這種形式的遞迴與數學一樣古老，也被稱為演算法。」（p.216）
⚙️ 怎麼用
為什麼需要多一步
結構遞迴之所以安全，是因為它是「順著資料結構走」的（p.223）：
依據訣竅的本質，每個自然遞迴都直接使用輸入中的某個部分，而不是整個輸入。因為資料是以層次的形式構造的，這意味著在遞迴的每一個階段，輸入都會縮短。因此函式遲早會讀入一個不可分割的資料，從而停止。
生成遞迴沒有這個保證：「內部的遞迴不再讀入輸入的某個直接部分，而是某種新的、由輸入生成的資料。」（p.223）書給的反例是把 quick-sort 的分割條件從「嚴格小於」誤寫成「小於等於」，於是單元素輸入會生成跟原問題一模一樣的子問題，永遠算不出答案（p.224）。結論是：
更一般地說，沒有東西能夠保證遞迴呼叫的輸入比原來的輸入更容易求解。（p.224）
這個例子給我們的教訓是，在設計演算法的訣竅中，還需要另外一個步驟：終止論證。這個步驟解釋對於每種輸入為什麼程式產生輸出，以及函式是怎樣實現這種思想的；或者給出警告，說明在什麼情況下程式可能不會終止。（p.224）
步驟（語言無關）
資料分析與設計——先選定「用什麼資料表示這個問題」。表示法會左右你怎麼想這個問題（p.222）。
合約、用途、頭部——除了寫清楚做什麼，還要多寫一段：「用途說明不僅要指明函式做了什麼，還應該包括一個註釋，用普通的術語解釋它是如何工作的。」（p.223）因為生成步驟跟資料定義的結構無關，讀者沒有別的線索。
例子——跟一般訣竅不同，這裡的例子要示範過程而不只是輸入→輸出：「對於演算法來說，例子應當闡明，對於給定的輸入，演算法是怎樣運行的。」（p.223）圖 26.1 把這階段的任務拆成三件事：構造並顯示平凡可解問題的例子、構造並顯示需要處理的例子、舉例說明如何（完整地）處理例子（p.224）。
模板——所有演算法共用同一個骨架（p.223）：先問「這個問題是不是平凡可解？」是的話直接給解；不是的話，生成一個或多個新問題，各自遞迴，最後把解組合起來（過程中可能還要用到原問題的資訊）。
本體：回答四個關鍵問題（p.223）——模板只是提示，真正要填的是這四題：
- 什麼是平凡可解問題？
- 相應的解是什麼？
- 如何生成新的、比原來的問題更容易解的問題？是生成一個新問題，還是若干個？
- 原問題的解是不是就是（某一個）新問題的解？或者需要把新問題的解連接起來？如果是，還需要原問題中的任何資訊嗎？
測試——照舊，但記得「測試並不能證實函式對所有可能的輸入都能正確工作」（p.223）。這正是為什麼要有第 7 步。
★ 終止論證——圖 26.1 為這一階段列的目標與任務是（p.224）：
階段 目標 任務 終止 證明演算法對於任何可能的輸入都會終止 說明遞迴呼叫的輸入要比原輸入短 書對 quick-sort 給的示範論證（p.225）：
在每一個步驟中，quick-sort 使用 smaller-items 和 larger-items 把表分為兩個部分。這兩個函式都給出一個比輸入（第二個參數）更短的表。因此，quick-sort 的每一步遞迴呼叫都讀入一個比原來輸入嚴格更短的表。最終，quick-sort 會讀入 empty，並返回 empty。
驗收標準很硬：「如果沒有這樣一個論證，我們就認為演算法是不完整的。」（p.225）
額外紅利：好的終止論證會生出新的平凡情況
這是最容易被略過、卻最划算的一點（p.225）：
一個良好的終止論證有時可能會揭示出其他的終止情況。
書的例子：寫 quick-sort 的終止論證時會發現，對任意的 N，把
(list N)拿去分割，比 N 小的和比 N 大的都是空表——所以單元素表的答案就是它自己。把這個觀察補成一條新的終止子句（判斷「其餘部分是不是空的」），演算法就少繞一大圈。寫論證不只是事後補證明，它會回頭改良演算法本身。🧪 我實際套用的紀錄
- （待填）
⚠️ 注意 / 什麼時候不適用
- 預設不要用它。 書的經驗法則是（p.229）：「大部分的函式使用的是結構遞迴；只有少數函式使用生成遞迴。當我們遇到既可以使用結構遞迴，又可以使用生成遞迴的情況，最好的方法通常是先使用結構遞迴，如果這樣得到的程式運行起來太慢，再探究是否可以選用生成遞迴。」
- 不要以為「生成遞迴 = 比較快」。 書給了三個理由潑冷水（p.229）：① 設計得很好的演算法也不總是比較快——quick-sort 只有處理較長的表才有優勢，短表反而是普通的 sort 比較快，而設計得差的演算法「可能會給程式的性能帶來災難」；② 用結構遞迴的訣竅設計總是比較簡單，設計演算法「通常需要深奧的數學知識」；③ 結構遞迴的函式別人一看就懂，演算法「必須有人給你解釋生成的步驟」。
- 設計演算法本來就不是照本宣科。 書說「我們最好稱之為發明一種演算法，而不是設計一種演算法。發明演算法需要一種新的洞察力」（p.216），而且「新的、複雜的演算法通常總是由數學家和理論計算機科學家設計的」——程式設計者的定位是能自己造簡單的、並看得懂科學家造的複雜的。
- 模板本身分辨不出兩者。 演算法模板太一般，把結構遞迴也涵蓋進去了（把「是否平凡可解」換成「是否為空表」、把「生成問題」換成「取其餘部分」，它就退化成一般的表處理模板，p.226）。所以別靠形狀判斷，要靠「遞迴的輸入是從哪來的」判斷。
- 兩者的真正分野（p.226）：「一種設計方法基本上只依賴於系統的資料分析；另一種設計方法需要對問題解決過程本身深刻的——通常是數學上的——洞察力。一種設計方法引導程式設計師給出自然終止的函式；另一種設計方法需要程式進行終止論證。」
- 真的決定用生成遞迴時，交付門檻是兩件事：「使用好的例子來說明問題的生成，並給出正確的終止論證。」（p.229）
🔗 相關工具
- 工具-資料驅動的模板推導 —— 對照組：那張講結構遞迴（模板順著資料定義長出來、自然終止），這張講它不管用的時候。先讀那張再讀這張。
- 工具-設計訣竅 —— 本卡是它的「演算法版」：同樣六個階段，但每階段的內容不同，而且多第七步終止論證。
- 工具-演算法設計策略 —— 出自《演算法圖解》，講選哪種策略（分治／貪婪／DP）；本卡出自 HtDP，講選了之後怎麼把它寫成一個保證會停的函式。互補，不重疊。
- 工具-遞迴式與主定理 —— 出自《演算法導論》，回答「這個遞迴要跑多久」；本卡只回答「這個遞迴會不會停」。要效能分析找那張，要正確性/終止性找這張。
- 程式設計方法 —— 來源書（第 25、26 章）。
🎯 什麼情境該想到我
遞迴函式是與背景無關地設計出來的——它不知道自己是第 1 次被呼叫還是第 100 次被呼叫。這很方便，但也會讓它「不知道」前面發生過什麼事，書上稱為知識的丟失（p.266）。
換一種說法，問題的關鍵所在是，遞迴函式獨立於它們的背景。函式處理表 (cons N L) 中 L 的方法與其處理表 (cons K L) 中 L 的方法完全一樣。（p.268）
丟失知識會造成兩種後果（p.266）：
- 結構遞迴變複雜、變低效。書上例子：把相鄰兩點的相對距離轉成到起點的絕對距離。遞迴回來的結果每個元素都得再加上
(first alon)，於是要多一個「把某數加到表中每個元素」的輔助函式。結果表長 100 要 220、200 要 880、400 要 5090——表長翻倍、時間變四倍（p.267）。- 演算法直接出致命錯誤。書上例子：簡單圖找路徑，函式「不知道」自己這次呼叫跟以前的呼叫是不是完全一樣，於是在有環的圖上用同樣的參數一再呼叫自己，永遠不會終止（p.270）。
兩題的解法一樣：加一個記住知識的額外參數，也就是累積器。第一題累積器是「目前累積的距離」，初值 0；第二題是「迄今已檢查過的節點的表」，初值 empty（p.268、p.270、p.272）。
該想到我的訊號（p.272 的兩個特徵）：
- 函式結構上是遞迴的，而且遞迴呼叫的結果被交給另一個輔助函式處理（書上例子
invert：遞迴倒轉後，還要呼叫make-last-item把第一個元素接到尾巴）。- 函式是生成遞迴，而你懷疑它可能根本產生不出想要的輸出。
⚙️ 怎麼用
大前提：累積器是「事後」加的，不是一開始就設計的。
添加一個累積器，即一個記住知識的參數，是在完成了函式設計之後進行的工作，而不是在設計函式之前。（p.271）
書上的順序永遠是：先用既有的設計訣竅做出一個完整的函式 → 檢查它 → 再修改它（p.271、p.272）。
先把不帶累積器的版本做完整。沒有這一步就沒有可檢查、可比較的對象。
判斷是否真的需要累積器：對照上面兩個特徵。若是結構遞迴那一類，接著手工計算幾個例子，觀察到底丟失了什麼（p.272）。書上手工展開
(rel-2-abs (list 3 2 7))才看出「第二個元素應該是 3+2，但第二層實例沒有任何方法可以『獲知』原表的第一個元素是 3」（p.268）。設立累積器：想清楚要記什麼知識、怎麼記（p.272）。相對距離題記「目前所遇到的總距離」（一個數）；找路徑題記「迄今為止已檢查過的節點」（一個表）。
把帶累積器的輔助函式模板放進 local 定義，並把原函式的參數改名，讓它跟輔助函式的參數區分開（p.273）。書上一律是
alox0（原始參數）vsalox（當前參數）、n0vsn、abt0vsabt。這個改名是關鍵：不變式要講的正是這兩者之間的關係。寫下累積器不變式——整套方法最難也最核心的一步。
這個開發過程的關鍵是要精確地描述 accumulator 的角色。一般來說，累積器不變式描述了函式的參數、當前輔助函式的參數以及帶累積器的函式運行期間必須維持的累積器三者之間的關係。（p.274）
在設計訣竅中，最複雜的部分就是給出累積器不變式。沒有累積器不變式就無法給出帶累積器的函式。給出累積器不變式顯然是一件需要大量練習的技巧性工作。（p.274）
選初值，使不變式一開始就成立。這不是隨便挑的，是被不變式逼出來的。
要使不變式在一開始就保持正確，必須使累積器的初值為 1。（階乘，p.277）
決定每次遞迴怎麼更新累積器，以重新建立不變式。這是維持機制的本體。
必須把 (first alon) 加到 accumulator 之上，使不變式對函式調用保持不變。（累積和，p.275）
在 !-a 遞迴的過程中，必須把累積器的當前值乘以 n，重新建立不變式。（階乘，p.277）
用不變式推出基本情況的答案。「得出了精確的不變式，剩下的工作就簡單了」（p.275）——因為到了終止條件，不變式會直接告訴你累積器代表什麼。
把輔助函式包在 local 裡，由外層函式代入初值（p.268、p.271）。這同時解決兩個次要問題：使用者不會意外傳進一個錯的初值；對外的合約與用途說明跟原函式完全一致。
手工計算檢驗，逐步確認每一次呼叫不變式都成立（p.275、p.277、p.279）。
書中的三個練習例子
例子 累積器不變式 初值 每步更新 基本情況 累積和 sum-a（p.274-275） accumulator 是 alon0 中在 alon 之前的數的總和 0（因為還沒處理過任何數） 把當前第一個數加到累積器上 表空時直接回傳累積器，它就是全部數的和 階乘 !-a（p.276-277） accumulator 是在 n0（包括）和 n（不包括）之間的所有數的乘積 1 把累積器的當前值乘以 n n 為 0 時回傳累積器 樹高 height-a（p.277-279） 「累積器不變式是從 height-a 走到樹 abt 所用的步數」（p.279） 0 走進左/右子樹時累積器加 1 遇到 empty 回傳累積器——但這還不是最終結果，兩邊的高度要再用 max 選大的 「每一次呼叫，不變式都保持不變」這件事是可以看見的：書上
(sum (list 10.23 4.50 5.27))的手工計算，右欄是(sum-a (list 10.23 4.50 5.27) 0)→(sum-a (list 4.50 5.27) 10.23)→(sum-a (list 5.27) 14.73)→(sum-a empty 20.0)→20.0。原版遞迴只是把表一層層拆開、每層擺一個加法留著最後才算；帶累積器的版本則是隨著每一步運行真正把數累加起來，走到底時答案已經成形（p.275）。同理(! 3)：(!-a 3 1)→(!-a 2 3)→(!-a 1 6)→(!-a 0 6)→6，每一次呼叫時累積器都是 3 至 n 的乘積（p.277）。樹高那題也印證了：「在遞迴的每一步，height-a 增加累積器的值，而在路徑頂端，累積器就代表了所經過的直線的數目」（p.280）。
🧪 我實際套用的紀錄
- （待填）
⚠️ 注意 / 什麼時候不適用
累積器版本不一定更好懂、也不一定更快。
第一次遇到帶累積器的函式的人常常產生這樣的印象，帶累積器的函式總是比與之對應的遞迴函式要易於理解，並且運行速度要快，這兩點都是錯誤的。（p.281）
書上量測 1000 次
(! 20)：一般階乘平均 5.806 秒，帶累積器的階乘平均 6.110 秒——帶累積器的版本反而較差（p.281）。沒有不變式就不要動手。「沒有累積器不變式就無法給出帶累積器的函式」（p.274）。只加一個參數是不夠的——找路徑那題加了
accu-seen之後函式照樣不會停，得真的在函式裡用上累積的知識（檢查 orig 是否已在 accu-seen 中）才算解決（p.270-271）。運算順序會改變。 累積器版本把基本運算的順序反過來做：原版 sum 從右加到左，累積器版從左加到右。對精確數沒差，但對非精確數差別是巨大的——書上要你去算
(sum (g-series #i1000))，兩者的差可以是任意大（p.275-276）。改寫後未必與原函式等價。 相對距離那題改寫後與原函式功能等價；但找路徑那題「是對 route-exists? 函式徹底的改進」——原版對某些輸入根本不能運行（p.271）。要分清楚你在做的是等價改寫還是修 bug。
不變式難寫是正常的，書上明說這是「需要大量練習的技巧性工作」（p.274），並為此安排了整整一節的小例子和一長串習題。
帶累積器的函式不限於單一自我引用的資料定義——樹高那題就有兩處自我引用（p.277）。
🔗 相關工具
- 工具-設計訣竅 —— 前置步驟，累積器是在訣竅做完之後才加上去的東西
- 工具-資料驅動的模板推導 —— 第 4 步「放進 local 的模板」就是從資料定義推出來的骨架
- 工具-生成遞迴與終止論證 —— 找路徑那題的不終止，正是生成遞迴缺少終止論證的後果
- 回到 程式設計方法
🧬 消除相似性
🎯 什麼情境該想到我
當你手上有兩個幾乎一模一樣、只差一兩處的定義時 —— 不論那是兩個函式，還是兩份資料定義。
書中一開頭就點名這種味道：符號表的定義和數表的定義「只有兩處不同：一處是資料型別名，另一處是關鍵字 symbol 和 number」（p.170）。同樣地，兩個在表裡找東西的函式「幾乎無法區別」，唯一的差別只是要找的那個符號不同（p.170）。
為什麼要處理它：
許多程式錯誤出現的原因都是重複，所以好的程式設計者總是盡可能避免重複。（p.170）
書把寫函式類比成寫散文 —— 第一稿只是草稿，函式會被很多人讀、被人改，所以我們必須學會「編輯」函式；而編輯程式的過程中，最主要的步驟就是去除重複（p.170）。
好處有三個，都在書裡明講：
- 一個函式同時完成很多任務（p.171）—— 抽象出來的
filter1不只能做 below / above，還能拿去做等於、小於等於、大於等於（p.173）。- 一處修改，所有人受益（p.175）—— 改進實作、修掉一個邏輯錯誤、甚至加新功能，所有用到它的地方都跟著改進。
- 統一了許多輸入的資料型別（p.178）—— 作用在 X 表上就得到 X 表，這種函式書中稱為「多型函式，或者叫做一般的函式」。
⚙️ 怎麼用
語言無關的五步。前三步是第 19 章的做法，第 4、5 步的措辭取自第 22 章那份階段清單（p.195-196）。
1. 並排 —— 比較兩個定義，標記出不同點
把兩個定義排在一起逐行對照。書裡的圖 19.1 就是這樣排的，而且把差異處塗上不同底色：「為了突出這個不同點，在圖中這兩個符號使用了不同的底色。」（p.170）
差異通常小得可疑：
- 只差一個要比對的值（
'doll/'car，p.170）- 只差一個運算子（
</>，p.171）- 只差一個關係算子，連處理的資料型別都可以不同（below 對數、below-ir 對存貨記錄，p.177）
- 資料定義只差型別名（數表 / IR 表，p.176）
- 甚至只差名字 —— 兩個算長度的函式「僅僅是名字不同。如果我們給他們起相同的名字，那麼他們就完全一樣了」（p.178）
2. 把不同之處變成參數
好的程式設計者不會定義多個類似的函式，而是定義單一的、在一個表中既能夠尋找 ‘doll，又能夠尋找 ‘car 的函式。這個更一般的函式需要額外的參數。（p.171）
差異是一個值，就多一個值參數；差異是一個運算子或函式，就多一個函式參數。書中對此有個定名：
將兩個相關的函式結合成一個單獨函式的過程叫做函式抽象。（p.171）
前提是你的語言得允許這件事。第 19 章那些函式「在兩個地方違反了基本的 Scheme 語法」：一是函式和基本操作的名稱被當成參數傳入，二是參數被當成函式使用（出現在呼叫的第一個位置）（p.180）。書的處理是擴充語法、並讓值的集合包含函式名與基本操作名，因為 ——
如果沒有這樣的概念，就不可能對函式進行抽象。（p.180）
3.（替代做法）用 local 把差異「記住」，回傳一個函式
第 22 章給了不同於第 21 章的第二種訣竅：不把差異放進參數表，而是把原來那個具體函式包進 local，用它的名字當 local 的主體，再把差異的名字列成外層的參數表（p.195）。
(define (abs-fun op1 op2) (local ((define (concrete-fun x y z) ... op1 ... op2 ...)) concrete-fun))回傳的函式會永久地記住傳進來的那個差異（p.194-195）。另外書有一條命名提醒：「如果 op1 或者 op2 是個特別的符號，比如
<，我們就在新的環境中給它起一個更有意義的名稱。」（p.195）4. 測試 —— 用抽象函式反過來定義原來那兩個
為了測試抽象函式，我們仍然使用抽象的函式反過來定義原來的函式。（p.195）
(define below2 (filter2 <))、(define above2 (filter2 >))—— 只要把抽象函式作用在「原先具體函式中不同之處的東西」上，就該得回原來的函式（p.196）。第 19 章也是同一招：below1 產生和 below 相同的結果，above1 產生和 above 相同的結果，而且「只使用一行程式碼」（p.173）。5. 改合約 —— 把具體型別換成型別變數
這步是整張卡最容易被跳過、也最該做的。書自己也承認它一開始跳過了：「現在，我們還不知道如何寫出像 filter1 這樣的函式的合約。我們先跳過有關合約的問題」（p.172），到第 20 章才補上。
三個要點：
(a) 函式參數用箭頭型別寫。
(A B -> C)表示「讀入一個 A 型別的元素和一個 B 型別的元素，回傳 C 型別的元素」，即「把 A 和 B 映射到 C」的函式（p.181）。所以 filter1 的第一版合約是(number number -> boolean) lon number -> lon（p.182）—— 它的與眾不同之處在於，第一個參數的型別不是資料定義中引入的名稱，而是用箭頭符號直接定義的（p.182）。(b) 具體資料型別換成型別變數。
記號 ITEM（元素）是一種型別變數，代表任意 Scheme 資料的集合，包括：符號，數，布林值，IR……（p.178）
把 ITEM 換成某個具體資料的名稱，就得到一個具體實例；配合縮寫
(listof ITEM)，於是(listof symbol)是所有符號表、(listof number)是所有數表、(listof (listof number))是由數表構成的表（p.178）。合約裡也可以直接用X：「X 只是一個變數，代表某種資料型別的名字。」（p.179）(c) 同一個變數在所有位置必須被同一樣東西代替。 filter1 的一般化合約是：
;; filter1 : (X number -> boolean) (listof X) number -> (listof X)
我們可以用任何東西代替這個 X，只要三個 X 出現的地方都被同一樣東西代替。（p.182）而且每一個獨立變動的東西都該有自己的變數。當「限值」參數從數變成符號時，合約就矛盾了，解法是給限值再引入一個變數 TH（p.183）：
;; filter1 : (X TH -> boolean) (listof X) TH -> (listof X)書最後把型別收成四類：基本型別；定義的型別；函式型別；以及參數型別 —— 「要麼是定義的型別，要麼是含有型別變數的函式型別」（p.184）。
🧪 我實際套用的紀錄
- （待填）
⚠️ 注意 / 什麼時候不適用
- 合約寫不出來，就是抽象沒站住。 書給了一條明確的收手規則：「如果要使用含有參數型別的函式，我們必須先找到一個（所有函式合約中變數的）替換，使得所有的參數都屬於合適的型別。如果做不到這一點，我們要麼修改函式的合約，要麼認為這個函式不適用於這種情況。」（p.184）—— 兩個出口都是誠實的，不要硬套。
- 這套消除相似性的方法有語言前提。 「這裡消除類似的方法僅針對像 Scheme 這樣的函式式程式設計語言；不過，其他類型的語言，特別是物件導向語言，支持類似去除相似性的機制 —— 有時候這種機制被稱作模式。」（p.170）換語言就換手法，別直接照搬。
- 語言得先讓函式成為值。 見上面第 2 步：沒有「函式名和基本操作名也是一種值」（p.181），這條路走不通。
- 不是每個抽象都值得慶祝。 書自己吐槽：「就 contains-doll? 和 contains-car? 而言，函式抽象一點也不好玩。」（p.171）真正有趣的是差異落在運算子/函式上的那種（圖 19.2），因為抽象出來後能移作它用。
- 抽象完可能還能再抽象一次。 filter1 一開始固定要「拿元素跟第二個參數比」，後來發現關係函式可以忽略它的第二個參數，於是簡化成只讀入一個判斷函式和一個表的 filter（p.174-175）。第一版抽象不是終點。
- 抽象出來的東西效能不會自動變好。 書在習題 19.1.5 直接問：「對於比較長的表，為什麼這兩個函式執行起來非常慢？」並要你引入區域名稱記住自然遞迴的結果來改進（p.176）。抽象是結構問題，效能要另外解。
- 「該抽象什麼」本身沒有訣竅可循。 這是書最誠實的一句話：抽象函式往往比你原本想要的功能廣泛得多，但「不幸的是，並不存在一個通用的訣竅可以指導我們發現這類功能，我們所能做的只是多實踐，並且留心觀察哪裡適合使用抽象函式。」（p.186）—— 上面那套步驟只能在你已經看到兩個相似定義之後幫你；看不看得到，得靠練習。
🔗 相關工具
- 工具-設計訣竅 —— 同一本書的前置步驟。訣竅產出的模板決定了函式的基本結構，所以「讀入相同資料型別的函式看起來很類似」（p.170）；這張卡處理的正是訣竅產出的那一堆相似函式
- 工具-資料驅動的模板推導 —— 相似性的來源。書指出資料定義相似，讀入它們的函式也會相似（p.177），所以資料定義層的抽象（參數資料定義、
(listof ITEM)）和函式層的抽象是同一件事的兩面- 工具-提煉函式 —— 出自《重構》，形狀像但方向不同：提煉函式是把一段內聚的程式碼抽出來命名，處理「太長 / 需要註解解釋」；這張卡是把兩個完整的定義合併成一個，處理「長得太像」，而且多了一步《重構》沒有的功課 —— 合約要改用型別變數
- 程式設計方法 —— 出處，第 19、20、22 章
💾 讓程式記住過去
🎯 什麼情境該想到我
先看純函式做不到什麼：
無論調用一個函式多少次，只要使用相同的參數，總會得到相同的結果。即使是帶累積器的函式，只要累積器相同，返回值也將相同。函式只是不能記住過去的調用結果。（p.295）
可是很多程式必須記住以往呼叫中的某些資料。書上一連舉了三個例子：
- 通訊錄（p.295-296）。標準的通訊錄軟體至少提供兩種服務：查找某人的電話號碼、把某人和號碼加進通訊錄。加進去之後，「與以前完全一樣的 lookup 呼叫現在返回了所需的電話號碼」。過去要產生這種效果，唯一的方法就是編輯定義——但「我們並不希望用戶來編輯程式。事實上，它們應該沒有權力訪問我們的程式」（p.296）。
- 交通號誌（p.296-297）。原本使用者得輸入
(next (next (next (next 'red))))；改成按鈕之後，回呼函式沒有參數，「該回呼函式要以某種方式得知當前信號燈的狀態，並改變之」。要做到這件事，「next 的當前呼叫必須能影響將來的呼叫」（p.297）。- 劊子手遊戲（p.297）。
check讀入一個字母回傳 true/false，「hangman 和 check 必定有一定的記憶，記住『Check』按鈕被使用了多少次，還要記住讀入的猜測有多少次是錯誤的」。書把「何時需要記憶」收斂成兩種情況（p.305），而且說「要辨認出何時程式需要記憶相對來說比較簡單」：
- 程式向使用者提供不止一種服務，每種服務對應一個函式。 通訊錄是經典例子——「『添加服務』的使用影響了『查找服務』的使用，所以程式需要記憶」（p.305）。倉庫管理員的帳簿也是：輸入物品、搜尋帳簿、刪除物品三種服務，「我們不能從倉庫中取出一個不存在的東西，所以程式必須保證兩種服務能正確地互相影響」（p.306）。
- 程式只提供單一服務，但同樣的參數可能返回不同答案。 交通號誌是經典例子：「因為連續兩次計算 (next) 會產生不同的效果，所以這個函式需要記憶」（p.306）。
random也是：「兩次計算 (random 10)，返回值可能相同，也可能不同。因此 random 的實現需要配備有記憶的函式」（p.306）。判準其實在程式的邊界上：
簡而言之，程式與世界的其餘部分之間的界面決定了該程式是否需要記憶，以及它需要何種類型的記憶。（p.305）
不只是 GUI。書說即使要求使用者從互動視窗使用程式，也必須把程式組織成「每一種服務對應一個函式，而函式通過記憶相互合作」；「即使是在物理設備（例如電梯、錄影機等）中運行的函式，也必須以某種方式與設備相結合」（p.305）。
⚙️ 怎麼用
第 0 步：三個重要的步驟
定義記憶函式需要三個重要的步驟：
- 確認確實需要記憶，
- 確定要記憶的資料，
- 理解哪項服務需要修改記憶，那項服務需要使用記憶。（p.305）
書對這三步的說明是：第一步是必須的；一旦知道程式需要記憶，「就必須對記憶進行資料分析，也就是說，必須理解記憶的資料型別是什麼」；最後「必須仔細設計那些改變記憶的函式」——而只使用、不修改記憶的函式，照原本的設計訣竅做就好（p.305）。
第 1 步：畫組織圖
一般說來，在分析問題說明時應該畫出組織圖。（p.306）
圖 36.1「記憶程式的組織圖」給了兩個例子：通訊錄管理程式和交通號誌程式。畫法（p.306）：
圖上的東西 意思 矩形方框 程式所提供的每一個服務 指向方框的箭頭 該服務所需的資料型別 從方框向外的箭頭 服務的輸出 圓圈 記憶 從圓圈到方框的箭頭 該服務使用記憶作為一個參數 從方框到圓圈的箭頭 該服務改變記憶 這兩張圖表明服務通常要使用記憶，並且要修改記憶。（p.306）
第 2 步：把記憶變成狀態變數，並替它寫合約與用途說明
記憶是用變數定義實現的。「原則上，只要一個變數就足夠實現所有需要的記憶了，但是這通常是不方便的。一般來說，從記憶分析可以知道我們需要多少變數，以及哪項服務需要哪個變數。」（p.306）
記憶改變時，「相應的變數就變成了一個新的值，或者換一種說法，變數聲明的狀態改變了，這反映了記憶隨時間變化。因此，我們把實現記憶的變數稱為狀態變數。」（p.306）
「改變程式的記憶的服務由對某個（或某些）狀態變數使用
set!的函式實現。」（p.306）
set!是 Scheme 的賦值表達式（p.298）；換到別的語言，就是「改變一個外部變數的值」的那個動作。關鍵動作：
就像設計函式定義的合約與用途說明一樣，我們必須設計狀態變數的合約與用途說明。（p.306）
通訊錄的狀態變數
address-book合約是「(listof (list symbol number))，保存人名和電話號碼的對」（p.306）；交通號誌的current-color合約是 TL-color（‘red / ‘green / ‘yellow 三者之一），用途是「保存交通號誌當前的顏色」（p.307）。合約立刻拿來當檢查工具。 把
address-book賦值成 5「是沒有意義的」，因為 5 不是一個表，「這個表達式違背了狀態變數的合約」；把它賦值成空表是正確的，因為那是初始值；把新條目 cons 上去也是正確的，因為它「構造了一個更長的、型別正確的表」——「set!表達式正好改變了狀態變數的值，使它代表 (listof (list symbol number)) 型別中的另一個值」（p.307）。賦值的右邊不一定要是現成的值：「在許多情況下，使用一個能夠計算出值的函式也是合理的」——交通號誌就寫一個純函式
next-color，把當前顏色算成下一個顏色，再一次賦值回去（p.307）。第 3 步：寫初始化函式
在完成了程式中狀態變數的合約與用途說明的設計之後，我們應立即定義一個函式，把這些狀態變數設置為合適的初始值。我們把這樣的函式稱為初始化函式。在程式運行時，初始化函式應當是第一個被執行的函式；程式也可以提供其他的方法來調用初始化函式。（p.307）
兩個細節：
- 初值不是隨便挑的。交通號誌初始化成 ‘red，因為「遵從工程上的傳統規則，在啟動設備時將狀態設為最安全」（p.308）。
- 初始化函式通常不只是設值。「很容易看出初始化函式還應當做另外一些有用的工作」——通訊錄的初始化函式應該建立並顯示 GUI，交通號誌的應該建立並顯示畫布（p.308）。
第 4 步：修改過的設計訣竅（本卡的核心）
現在，我們來看看最基本的設計訣竅的各個階段應該如何適應狀態變數：（p.308）
① 資料分析 —— 沒變。「即使是影響變數的狀態的函式，也可以（或可能）讀入並返回資料。因此仍然需要分析如何表示資訊，如果必要的話，還要引入結構和資料的定義。」交通號誌就得益於 TL-color 這個資料定義（p.308）。
② 合約、用途和效果 —— 第一個主要的改變。
除了要說明函式讀入和返回的東西，還必須寫明它影響了那些變數，以及它是怎樣影響這些變數的。函式對狀態變數的效果必須與變數的用途說明一致。（p.308）
所以規格多了一欄「效果」。交通號誌的 next 寫成「效果：改變當前的顏色，從 ‘green 變為 ‘yellow，從 ‘yellow 變為 ‘red，從 ‘red 變為 ‘green」，它不讀入資料也不回傳可見的值。書特別註明：「在傳統意義上，這個函式是沒有意義的，所以它只有一個效果的說明（而沒有其他的說明）」（p.308）。通訊錄那個則是「效果：把 (list name phone) 添加到 address-book 的前部」——「從效果說明中可以看出，address-book 的定義是按照它的用途說明與合約被修改的」（p.308）。
③ 程式例子 —— 例子一樣重要，但變難寫了。
以前，我們必須開發例子，舉例說明輸入和輸出的關係，但是，因為現在函式有了效果，所以我們還需要用例子來說明效果。（p.308）
寫法是「如果狀態變數是 A 時我們執行這個函式，那麼其後狀態變數就是 B」。狀態空間小就窮舉——交通號誌「只能代表三種符號中的一個，所以實際上我們可以用例子來表示其所有可能的效果」；狀態空間無限就挑代表——通訊錄「可以代表無限個值，所以不可能舉出所有的例子。但是，舉出一些例子還是非常重要的，因為例子可以使得以後開發函式的主體更簡單」，書挑的三個是：空表、一個元素的表、以及形如 (list E-1 … E-2) 的一般情形（p.309-310）。
在例子中，我們用到了表示時間的文字，其後，這並奇怪，畢竟，賦值就是要強調時間的概念。（p.310）
警告： 狀態變數永遠不會是某個函式的參數。（p.310）
④ 模板 ——
改變狀態的函式的模板與普通函式的模板很相似，只是其主體中應包含
set!表達式，用來修改狀態變數（p.310）也就是「函式主體 = 一次對狀態變數的賦值」，賦值右邊先留空。書補了兩點：
- 「計算狀態變數下一個值的任務可以被交給一個讀入 x、y 和 z 的輔助函式處理。我們的兩個例子就是這樣的。」（p.310）
- 「有時候，按照函式輸入的定義，我們還需要使用選擇器和 cond 表達式。」交通號誌的輸入資料定義（三種顏色）就暗示要用一個三分支的條件式，每個分支各放一個賦值（p.310）。
⑤ 主體 —— 這一階段的重點只有一個：
對於有效果的函式來說，最需要注意的步驟就是
set!表達式的執行。（p.310）書給了兩種寫法，並各配一個例子（p.310）：
- 賦值右邊直接算出來：「在某些情況下，賦值的右部只是原始操作、函式參數和狀態變數（或者是幾個狀態變數）。」
add-to-address-book屬於這種——右邊只由 address-book 加上兩個基本的表建構操作組成。- 抽一個沒有效果的輔助函式：「對於其他情況，最好設計一個（沒有效果的）輔助函式，讀入狀態變數當前的值以及函式參數，返回新的狀態變數的值。」交通號誌是兩種方法都可以選用的例子：可以照模板寫成三分支各自賦值，也可以寫成一行「把 current-color 賦值成 next-color 算出來的顏色」（p.310）。
⑥ 測試 ——
對於有效果的函式，我們可使用相同的方法，但是證實函式對於某種狀態變數有著預期的效果是一個複雜的任務。（p.310）
書給了兩種方法（p.310-311）：
- 方法一：設好狀態 → 呼叫 → 檢查。「可以把狀態變數設值為所需的狀態，再調用函式，然後檢查函式的結果和效果是不是預期的值。」交通號誌「就很適合使用這種方法」，三個例子直接各轉成一條測試。
- 方法二：先存舊值 → 呼叫 → 比對新舊關係。「我們可以在測試前保存某個狀態變數的值，再調用改變記憶的函式，然後進行合適的測試。」通訊錄的測試就是：計算開始時把舊的 address-book 存起來，計算結束時「檢查特定的條目是否被添加到了狀態變數的前部，而狀態變數的其餘部分保持不變」（p.311）。
- 而且要把測試本身抽成函式：「要對有效果的函式進行測試，特別是進行第二種測試，把測試表達式抽象成一個函式是很效的手段」；抽出來之後就能連跑多次，「並確保每一次測試它的效果都是正確的」。注意連跑時要用一個能保證順序的組合子——書用
and：「其中 and 表達式保證測試表達式按照順序計算，並且全部返回 true」（p.311）。⑦ 將來的重用 ——
一旦得到了完整的、經過測試的函式，我們應當記住它們的存在，記住它們計算了什麼，記住它們的效果是什麼。不過，我們並不需要記住它們是怎樣計算的。（p.311）
完整範本
圖 36.2「狀態變數的設計訣竅：一個完整的例子」（交通號誌，p.309）與圖 36.3「狀態變數的設計訣竅：第二個例子」（電話簿，p.312）把整份文件的欄位列了出來，順序是：
資料定義 → 狀態變數（合約 + 用途）→ 合約 → 用途 → 效果 → 頭部 → 例子 → 模板 → 定義 → 測試
兩個例子的「用途」欄都寫「該函式總是返回 (void)」——全部的資訊都在「效果」那一欄。交通號誌那份的「頭部」被省略了，書說明原因是「就這個特定的例子來說，有用途和效果的說明就足夠了」（p.311）。
🧪 我實際套用的紀錄
- （待填）
⚠️ 注意 / 什麼時候不適用
只使用、不修改記憶的函式不需要這一套。「只使用而不修改記憶的函式只需按照前面介紹過的設計訣竅進行設計就可以了。」（p.305）
狀態變數永遠不會是某個函式的參數。 書把這句獨立標成「警告」（p.310）。
賦值會帶進「時間」，而且會毀掉舊的值。
手工計算還說明，
set!表達式的計算過程帶來了額外的時間約束或時間區間。更具體地說，計算是由兩個部分組成的：賦值前的部分和賦值後的部分，而賦值會影響定義的狀態。在我們介紹賦值語句之前，只要願意，隨時可以把變數替換成它的值，或者把一個函式調用替換成它的定義。現在，我們必須等到真正需要某個變數的值的時候才能執行這樣的替換。（p.300）賦值操作「消滅」了當前的值，除非程式設計者能詳細安排變數的賦值順序，使用
set!可能會帶來災難性的後果（p.300）書的習題 35.2.2 就是這個坑的實例：連著兩次賦值想交換兩個變數，會失敗；要先用一個 local 定義把舊值存下來才對（p.300）。
回傳值不再是全部的資訊。「使用
set!的函式既有返回值，又有效果，不過返回值有可能是不可見的。」（p.302）賦值本身的值是(void)，一個不可見的值——「所有set!表達式的值都是相同的，也是不可見的，因此和計算不相關。與計算相關的是set!表達式的效果。」（p.298、p.299）所以規格書裡真正承載意義的是「效果」欄，不是「用途」欄。測試變成複雜的任務（p.310）；而且要驗的不只是「效果對」，還有「沒有多餘的效果」——書上那個抽出來的測試函式，用途說明寫的是「判斷 add-to-address-book 是否對 address-book 產生了正確的效果，而且沒有多餘的效果」（p.311）。
重用變得比以前困難。
警告：在效果出現了之後。要重用一個函式比在代數程式的世界中要困難得多。（p.311）
狀態變數的合約可能被違反。 把型別不對的值賦給狀態變數「是沒有意義的」，因為它違背了狀態變數的合約（p.307）——合約在這裡是你自己要守的紀律，不是語言幫你擋的。
🔗 相關工具
- 工具-設計訣竅 —— 本卡是它的「有狀態版」。書的原話是「現在，我們來看看最基本的設計訣竅的各個階段應該如何適應狀態變數」（p.308）：資料分析照舊，合約那一步多出「效果」，例子要改寫成「執行前的狀態 → 執行後的狀態」，模板主體多一個賦值，主體階段的重點變成賦值表達式的執行，測試要先擺好狀態或先存舊值。
- 工具-資料驅動的模板推導 —— 狀態變數也要先做資料分析：交通號誌先有 TL-color 的資料定義，模板的三個分支才長得出來（p.308、p.310）。
- 工具-累積器與累積器不變式 —— 同樣是「把資訊往下傳」，但差別在傳的地方不同。累積器是多加一個參數，資訊沿著遞迴呼叫往下走，外面的變數完全沒有被動過——所以書才說「即使是帶累積器的函式，只要累積器相同，返回值也將相同」（p.295）。狀態變數則是改動一個外部的變數定義，資訊留在函式之外、跨越呼叫存活，而且函式因此有了「效果」；書還特別警告狀態變數不可以當參數（p.310）。要記的東西只在這一串遞迴裡有效 → 用累積器；要記的東西要活過整個程式、被不同的服務共用 → 用狀態變數。
- 回到 程式設計方法
🧰 這本書給我的工具
- 工具-設計訣竅 — 面對「不知道怎麼開始寫」時（家族的基本款，其餘六張都是它的變體或前後步驟）
- 工具-資料驅動的模板推導 — 輸入是複合／自引用／相互引用資料，不知道函式骨架該長怎樣時
- 工具-從相似定義提煉抽象 — 兩段程式碼長得好像、複製貼上只改兩個字時
- 工具-生成遞迴與終止論證 — 遞迴不是照著資料結構走，擔心它停不下來時
- 工具-累積器與累積器不變式 — 遞迴到一半發現需要前面的資訊時
- 工具-狀態變數的設計訣竅 — 程式必須記住上次發生過什麼時
- 工具-逐步求精 — 替複雜的真實世界資訊設計資料表示法時（書中稱「反覆精化」）
✨ 關鍵重點（Layer 1–2）
- 訣竅是一個家族，不是一份清單。 前言圖 0.1 的六步驟是骨幹；書中另有圖 2.2（入門版）、圖 6.5（複合資料）、圖 9.2（自引用資料）、圖 15.4（相互引用）、圖 26.1（演算法，多一步終止論證）、圖 36.2/36.3（狀態變數）逐一精化。問題的範疇由資料的型別決定，模板由資料定義推導出來——「函式輸入的資料定義往往在很大程度上決定函式的形狀」（p.79）。
- 模板是機械推導的，不是想出來的。 資料有 N 個欄位 → 模板就有 N 個選擇器；資料定義有幾個子句 → cond 就有幾支；資料定義裡有幾個自引用箭頭 → 模板就有幾個遞迴呼叫（p.76）。推完永遠只剩同一個問題：把手上這幾個值合起來。
- 兩種遞迴要分開對待。 結構遞迴順著資料走，自動終止；生成遞迴自己造子問題，不保證終止，所以設計演算法的訣竅比基本訣竅多一步「終止論證」——「如果沒有這樣一個論證，我們就認為演算法是不完整的」（p.225）。而且好的終止論證會回頭改良演算法本身（p.225）。
- 抽象的難處在合約，不在程式碼。 把兩個相似定義合成一個很容易，難的是合約要改用型別變數（書中的
ITEM／X記法，p.178-184）；「如果做不到這一點，我們要麼修改函式的合約，要麼認為這個函式不適用於這種情況」（p.184）。而「該抽象什麼」本身沒有訣竅可循（p.186）。 - 累積器的關鍵是不變式，不是多一個參數。 「在設計訣竅中，最複雜的部分就是給出累積器不變式。沒有累積器不變式就無法給出帶累積器的函式。」（p.274）而且書明確反駁「累積器版比較快」的直覺，並給了階乘的反例（p.281）。
- 有狀態就多一欄規格。 合約與用途說明之外還要寫「效果」，例子要改寫成「執行前的狀態 → 執行後的狀態」，測試要先擺好狀態或先存舊值再比對（p.308-311）。書獨立標了一條警告：狀態變數永遠不會是某個函式的參數（p.310）。
💬 金句原文（Layer 0）
- 「向兒童傳授程序設計知識與現代教育學相悖。制定計劃、學習教規、注重細節、嚴格自律有何樂趣？」（前言題詞，引艾倫·佩利 1966 年圖靈獎得主《編程警句》，前言 p.I）
- 「每個人都應該學習如何設計程序。」（前言 p.I，全書唯一被獨立置中加粗的一句）
- 「有了設計訣竅，程序設計的初學者就不用再盯著空白的紙張或計算機屏幕發呆了，他們可以自我檢查並核對設計訣竅，使用『問答』方式進行程序設計並取得進步。」（前言 p.II）
- 「設計訣竅並不是核彈，它並不能解決程序設計過程中遇到的所有問題，它提供的是完成程序設計過程中不可避免的步驟的指導。在程序設計中最富有創新性和最困難的一步是程序體的設計。」（2.5 小結，書 p.10）
- 「事實上，我們最好稱之為發明一種算法，而不是設計一種算法。發明算法需要一種新的洞察力。」（第 25 章開篇，書 p.216）