工具-累積器與累積器不變式

🎯 什麼情境該想到我

遞迴函式是與背景無關地設計出來的——它不知道自己是第 1 次被呼叫還是第 100 次被呼叫。這很方便，但也會讓它「不知道」前面發生過什麼事，書上稱為知識的丟失（p.266）。

換一種說法，問題的關鍵所在是，遞迴函式獨立於它們的背景。函式處理表 (cons N L) 中 L 的方法與其處理表 (cons K L) 中 L 的方法完全一樣。（p.268）

丟失知識會造成兩種後果（p.266）：

1. 結構遞迴變複雜、變低效。書上例子：把相鄰兩點的相對距離轉成到起點的絕對距離。遞迴回來的結果每個元素都得再加上 (first alon)，於是要多一個「把某數加到表中每個元素」的輔助函式。結果表長 100 要 220、200 要 880、400 要 5090——表長翻倍、時間變四倍（p.267）。
2. 演算法直接出致命錯誤。書上例子：簡單圖找路徑，函式「不知道」自己這次呼叫跟以前的呼叫是不是完全一樣，於是在有環的圖上用同樣的參數一再呼叫自己，永遠不會終止（p.270）。

兩題的解法一樣：加一個記住知識的額外參數，也就是累積器。第一題累積器是「目前累積的距離」，初值 0；第二題是「迄今已檢查過的節點的表」，初值 empty（p.268、p.270、p.272）。

該想到我的訊號（p.272 的兩個特徵）：

• 函式結構上是遞迴的，而且遞迴呼叫的結果被交給另一個輔助函式處理（書上例子 invert：遞迴倒轉後，還要呼叫 make-last-item 把第一個元素接到尾巴）。
• 函式是生成遞迴，而你懷疑它可能根本產生不出想要的輸出。

⚙️ 怎麼用

大前提：累積器是「事後」加的，不是一開始就設計的。

添加一個累積器，即一個記住知識的參數，是在完成了函式設計之後進行的工作，而不是在設計函式之前。（p.271）

書上的順序永遠是：先用既有的設計訣竅做出一個完整的函式 → 檢查它 → 再修改它（p.271、p.272）。

1. 先把不帶累積器的版本做完整。沒有這一步就沒有可檢查、可比較的對象。

2. 判斷是否真的需要累積器：對照上面兩個特徵。若是結構遞迴那一類，接著手工計算幾個例子，觀察到底丟失了什麼（p.272）。書上手工展開 (rel-2-abs (list 3 2 7)) 才看出「第二個元素應該是 3+2，但第二層實例沒有任何方法可以『獲知』原表的第一個元素是 3」（p.268）。

3. 設立累積器：想清楚要記什麼知識、怎麼記（p.272）。相對距離題記「目前所遇到的總距離」（一個數）；找路徑題記「迄今為止已檢查過的節點」（一個表）。

4. 把帶累積器的輔助函式模板放進 local 定義，並把原函式的參數改名，讓它跟輔助函式的參數區分開（p.273）。書上一律是 alox0（原始參數）vs alox（當前參數）、n0 vs n、abt0 vs abt。這個改名是關鍵：不變式要講的正是這兩者之間的關係。

5. 寫下累積器不變式——整套方法最難也最核心的一步。

   這個開發過程的關鍵是要精確地描述 accumulator 的角色。一般來說，累積器不變式描述了函式的參數、當前輔助函式的參數以及帶累積器的函式運行期間必須維持的累積器三者之間的關係。（p.274）

   在設計訣竅中，最複雜的部分就是給出累積器不變式。沒有累積器不變式就無法給出帶累積器的函式。給出累積器不變式顯然是一件需要大量練習的技巧性工作。（p.274）

6. 選初值，使不變式一開始就成立。這不是隨便挑的，是被不變式逼出來的。

   要使不變式在一開始就保持正確，必須使累積器的初值為 1。（階乘，p.277）

7. 決定每次遞迴怎麼更新累積器，以重新建立不變式。這是維持機制的本體。

   必須把 (first alon) 加到 accumulator 之上，使不變式對函式調用保持不變。（累積和，p.275）

   在 !-a 遞迴的過程中，必須把累積器的當前值乘以 n，重新建立不變式。（階乘，p.277）

8. 用不變式推出基本情況的答案。「得出了精確的不變式，剩下的工作就簡單了」（p.275）——因為到了終止條件，不變式會直接告訴你累積器代表什麼。

9. 把輔助函式包在 local 裡，由外層函式代入初值（p.268、p.271）。這同時解決兩個次要問題：使用者不會意外傳進一個錯的初值；對外的合約與用途說明跟原函式完全一致。

10. 手工計算檢驗，逐步確認每一次呼叫不變式都成立（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 的模板」就是從資料定義推出來的骨架
• 工具-生成遞迴與終止論證 —— 找路徑那題的不終止，正是生成遞迴缺少終止論證的後果
• 回到 程式設計方法