把 RNA folding 偷進 GHC——ApplicativeDo 排程的 Nussinov DP 重寫

ApplicativeDo 是 GHC 一個聽起來很無害的優化——把 do-block 裡互不依賴的 statement 從 >>= 自動降級成 <*>， 讓有 Applicative instance 的型別（比如 query 多個遠端資料的 Haxl、需要 batch 的 IO 套件） 能並行而不必使用者手動拆。 但這個降級不是「把 statement 排成樹」這麼直白—— 它要解的真正問題是「在所有合法的 sequential/parallel 樹排列裡找最少 round-trip 的那棵」。 Duncan 接手時，optimal 演算法已經寫好、語意正確， 唯獨慢到不能預設啟用：1,000 個 statement 要跑 55 秒，比編譯整個 module 都久。 修這個演算法把他帶到一個意料之外的地方——Nussinov 1978 的 RNA 二級結構摺疊動態規劃。

這篇文章順著 Duncan 的 hand-off 路線往下挖。 先看為什麼一個「正確但太慢」的優化會成為 GHC ticket 上常見的擱置物—— 這是 compiler 工程裡一類被低估的負債。 然後看 Nussinov 1978 為何能成為 DP 範本， Bringmann FOCS 2016 的 subcubic 為何在實務上用不上， longest-chain bound 如何把那個被「無關鄰居」拖垮的搜尋空間剪短， 並對照三種視角（生物學、Haskell、抽象 recurrence）下的同一棵樹。 最後一個 section 列舉這個技巧能搬走到哪些其他語言、不能搬走到哪些 whole-program 場景， 以及這個 flag 從 disabled 升級成預設的下游影響。

這個故事的價值不在「Haskell 又快了幾秒」—— 它真正有趣的地方是揭示了一個結構同構： do-block 排程跟 RNA 二級結構摺疊在拓樸上是同一個問題。 一旦看到這層對應， 1978 年的 Nussinov 演算法、 2016 年 FOCS 的 Bringmann subcubic 結果、 甚至 1975 年 Valiant 的 boolean matrix multiplication parser， 全都變成 GHC 編譯器這條技術藤蔓上能直接攀附的果實。

Duncan 的 punchline 寫得克制—— 「An optimization that's correct but disabled for being slow is the kind of thing you fix in an afternoon, I figured. It wasn't; it turned out to be a properly hard problem.」 這句話裡有兩個事實值得拆開。 第一，「正確但慢」的優化是 compiler 工程裡常見但被忽視的一類負債—— 它能進 mainline 是因為單元測試說語意對， 但永遠待在 -fdisabled flag 後面， 成為「文獻裡記載的能力」而不是「實際 ship 給使用者的能力」。 第二，這個 properly hard problem 之所以難， 是因為它的 search space 是組合爆炸的， naive 演算法是 O(n⁴) 量級—— 這不是 constant factor 的問題、 是 problem complexity 本身的問題， 所以單純加 memoisation 無法救它。

為何「正確但慢」的優化會被擱置

GHC 的優化 flag 體系裡有兩類截然不同的住客。 一類像 -O、-fspec-constr、-fworker-wrapper， 預設開啟、隨 release 一路演化、benchmarked 到每個 minor 版本。 另一類像 -foptimal-applicative-do， flag 名字裡有 optimal 兩個字、卻只能手動啟用， 因為演算法太慢，預設啟用會讓使用者感覺整個 compiler 變遲鈍。 使用者體驗的隱性合約是：「-O 可以慢，但慢得有道理； 任何讓編譯時間翻倍的 flag 都該 opt-in」。

ApplicativeDo 本身（不帶 optimal）是 2016 年合進 GHC 8.0 的， 背後是 Marlow、Brandy、Coutts、Vassena 等人的 ICFP 論文， 並負責產出一棵正確、但不保證 round-trip 最少的排程樹—— 大家叫它「greedy」變體。 greedy 走的是區域決策：在 statement 鏈上由左至右掃描， 遇到無依賴的相鄰 statement 就嘗試合併成 Par、有依賴就接 Seq。 速度極快（線性掃描），對多數實務 do-block 也已足夠好—— 但「足夠好」跟「最佳」之間存在 gap， 特別在那些有「中間綁定彼此互依、但首尾無依」這種交錯結構的 do-block 上。

-foptimal-applicative-do 是後來加上的「保證最少 round-trip」版本， 邏輯上更純粹、效果更好—— 在 Haxl 這種「每個 round-trip 都是一次跨網路 query」的場景， optimal 與 greedy 的差距可以是 2x 以上， 意味著每秒 query 數加倍、整個 SLA 都會跟著鬆動。 但 1,000 個 statement 的 worst-case 要 55 秒。 對單檔可能不致命， 但 production codebase 裡有不少幾百 statement 的 do-block—— 大致是 Haxl 開大型查詢、或測試裡塞長 fixture—— 這時 55 秒就會卡住 build pipeline。

結果就是 GHC ticket 裡躺著這個演算法： 正確、有測試、有 PR、但 flag 預設關。 Duncan 接手時的判斷是： 「正確但慢」聽起來只是 constant factor 問題、加個 memoisation 應該就能解決； 結果挖下去發現 naive 的 cut-check 是真實的 O(n⁴) 量級—— 每個 [i, j] 區間都要試所有 split 點， 且每個 split 點都要做 dependency 檢查、檢查本身也是 O(n) 的。 把 1,000 代進去： 1,000⁴ = 10¹² 次 elementary operation， 照 modern CPU 大致 10⁹ ops/s 算， 55 秒對得起這個量級。 memoisation 不能直接解決—— 問題出在 search space 本身的 cardinality。

下面這個小工具讓你親自感覺 N 增加時兩條曲線拉開的速度。 把滑桿拉到 50 跟 200 看左右兩個讀數的差距， 比看任何漸進記號都直觀—— 這正是 Tufte 所謂的「let the data speak」： 用一個沿著 N 軸刷過去的滑桿， 比任何「O(n⁴) vs O(n²) 是天差地別」的口語論證都精確。

滑桿拉到尾端的物理意義是： 原始演算法不是「在某個 input 大小開始變慢」的算法， 它是「不論多小都比必要多做幾百倍工作」的算法—— 只是在小 N 時被快速 CPU 吸收掉了。 對 50 statement，naive 跑 20,825 次 cut-check，optimised 跑 1,225—— 這已經是 17× 差距， 只是兩個都還在毫秒級沒人在意。

到了 200 statement， 1,333,300 vs 19,900 = 67×， 加上每個 cut-check 自己也有成本， 整體編譯時間就跨進「使用者會感覺到」的區段。 Duncan 真正解決的問題是這個 cut-check 數量本身—— 不是把每個 check 變快， 而是讓多數 check 根本不必發生。 這是兩種完全不同的優化哲學： 前者是「make each op cheap」（intrinsic、micro-optimisation）， 後者是「avoid the op」（algorithmic、structural）。 在 search problem 上，後者永遠勝過前者。

Nussinov 1978 ——RNA 摺疊如何成為 DP 範本

要看清楚為何這個演算法能被搬走， 得先理解 Nussinov 在 1978 年原本要解的問題。 RNA 是一條由 A、U、G、C 四種鹼基組成的單股鏈， 跟 DNA 的雙股不同—— 它會自己折回來、互補鹼基（A↔U、G↔C）形成氫鍵 bond， 整條鏈摺疊成像髮夾、像三葉草的二級結構。

摺疊是 free-energy 最小化的物理過程； 計算上的近似是「找一個 bond 集合，讓總 bond 數最大化」—— bond 越多、結構越穩定。 這個近似在熱力學上叫 Watson-Crick 配對能量主導假設， 對許多功能性 RNA（tRNA、rRNA 的二級結構）已足夠精確。 約束有兩條： 第一，每個鹼基最多參與一個 bond； 第二，bond 不能交叉 （pseudoknot 例外，但需要更貴的演算法處理）。 這兩條約束直接決定了「合法的摺疊結構是一棵樹」—— 第一條讓每個位置度數 ≤ 1， 第二條確保任兩 bond 之間是 nested 或 disjoint， 兩條合起來是 forest / tree 的拓樸特徵。

Nussinov 寫下這個 recurrence——對鹼基鏈 S[1..n]，定義 B(i, j) 為 i 到 j 區間內最大 bond 數：

// Nussinov 1978 RNA secondary structure DP
B(i, j) = max of:
  B(i+1, j)                                   // i 不配對
  B(i, j-1)                                   // j 不配對
  B(i+1, j-1) + δ(S[i], S[j])                 // i 跟 j 直接配對
  max over k ∈ (i, j): B(i, k) + B(k+1, j)    // 在 k 處切兩半

// δ = 1 if (S[i], S[j]) ∈ {(A,U), (U,A), (G,C), (C,G)}, else 0
// base case: B(i, j) = 0 when j ≤ i
// 時間 O(n³)：n² 個 cell × O(n) 的 k 掃描
// 空間 O(n²)：上三角矩陣

這個 recurrence 有個被生物學家視為理所當然、 但對 compiler 工程師應該叫作豁然開朗的性質： 它是一個「在區間上分治」的最小 / 最大成本問題， 唯一的約束是 non-crossing。 任何能寫成「對線性序列在 non-crossing 約束下尋找最佳組合結構」的問題， 都可以塞進同一個 recurrence 框架—— 只要重新定義 δ（i 跟 j 「配對」的成本/收益）跟 base case。

ApplicativeDo 排程恰好就是這個形狀。 do-block 是線性 statement 鏈， 「i 跟 j 並行」是它們之間沒有 transitive dependency（類似 δ=1）， non-crossing 對應「statement i 跟 j 並行時， i 跟 j 之間的所有 statement 必須形成一個閉合的子排程」—— 這正是 Nussinov 的 split 規則。 換言之，ApplicativeDo 排程不只是「借用」RNA 摺疊的 idea， 它是 RNA 摺疊的同一個組合問題的不同 instance， DP recurrence 不需要重寫、只需要重新解釋。

Duncan 把它 carry 過來的時候細節需要小心。 RNA 的 base case 是 B(i, i) = 0， 因為單一鹼基不能跟自己配對； ApplicativeDo 的 base case 是 cost(i, i) = 1， 因為單一 statement 永遠需要 1 個 round-trip。 RNA 的目標是 max bond 數； ApplicativeDo 的目標是 min round-trip。 RNA 的「在 k 處切」對應排程樹的 Seq 節點； RNA 的「i 跟 j 配對」對應排程樹的 Par 節點（外層 Par 包住內層子樹）。 兩個世界的對稱性夠齊整，幾乎是一一對應的型別轉換。

難的不是借用，難的是接下來要面對的 worst-case。 當 do-block 是一條 1,000 statement 都依賴前一個的「鏈」 （n statement 全部串成 a → b → c → … → z）， DP 表的每個 cell 都要老老實實掃 n 個 split—— 所以理論上的 O(n³) 在這個 input 形狀上是真實 worst-case。 要避免這個 worst-case， 要嘛改 asymptotics、要嘛找一個 input-specific 的 prune。 前者帶你進入 Bringmann FOCS 2016 的世界， 後者就是 Duncan 最終走的 longest-chain bound 路徑。

Bringmann FOCS 2016 ——subcubic 為何用不上

1978 之後的四十年， RNA 摺疊的演算法社群持續在問：能不能突破 O(n³)？ 2016 年 Bringmann、Grandoni、Saha、Vassilevska Williams 在 FOCS 發了一篇叫做 「Truly Sub-cubic Algorithms for Language Edit Distance and RNA Folding via Fast Bounded-Difference Min-Plus Product」的論文， 做到 Õ(n^2.8244) 隨機演算法—— 把 RNA folding reduce 成 tropical semiring（min-plus）矩陣乘法， 再用 fast matrix multiplication 的技巧加速。 理論上是個很漂亮的結果，破了長期的 cubic barrier。

這個 reduction 本身值得多看幾眼—— 它的關鍵是把「在 [i, j] 區間裡找最佳分割點 k」這個操作 重新表達成 min-plus 矩陣的單元計算： (A ⊕ B)[i][j] = min_k (A[i][k] + B[k][j])。 在熱帶半環（min, +）上，這個運算長得跟標準矩陣乘法 (A · B)[i][j] = Σ_k A[i][k] × B[k][j] 一模一樣，只是 + 換成 min、× 換成 +。 一旦寫成矩陣乘法， Strassen 那條提升 matrix multiplication 速度的技術藤蔓就全部可借—— 這是 algebraic 結構轉換的力量。

實務上 Duncan 評估之後決定不採用。 原因是兩條。 第一，subcubic 演算法的 constant factor 巨大—— 文獻上的講法是「enormous constant factors」， 要 n ≈ 10⁵ 以上才能贏 cubic baseline； ApplicativeDo 的 n 是 do-block 的 statement 數， 1,000 已經是極端， 10⁵ 在實務上不存在。 第二，subcubic 演算法是隨機的、需要 boolean matrix multiplication 的 worst-case 假設—— 把這套搬進 GHC 等於把編譯器決定論減弱， 這是一個工程上不可接受的 trade。 Compiler 該是 deterministic 的： 同一 source 編兩次該得到 bit-identical 的 binary， 這是 reproducible build、bisect、cache 命中率的基礎。

於是 Duncan 走了另一條路： 留在 O(n³) 不動 asymptotics， 但找一個 input-specific 的上界把多數 cell 直接 prune 掉。 這個上界叫做 longest-chain bound—— 對任何區間 [i, j]， 那段 statement 構成的依賴 DAG 的最長 chain 長度給出了「這段 round-trip 數的下界」 （這條 chain 必須串行）。

在 DP recurrence 裡， 當我們從 cost(i, k) + cost(k+1, j) 跟 1 + cost(i+1, j-1) 兩個 candidate 取 min 時， 可以先算 longest-chain([i, j])—— 如果這個下界已經 ≥ 目前 best candidate， 整段子問題不必展開。 對「現實 codebase 中的 do-block」這個 input 分布—— 多數依賴是區域性的、長 chain 不多—— 這個剪枝兇猛得令人吃驚。 把它套上去， realistic input 上的 cut-check 數從 1,550 / 4,544 掉到 322 / 1,426（N=50 / N=100）， worst-case 從 55 秒掉進秒級。

值得指出的事： 這條路不是 Duncan 從 Bringmann 論文裡直接搬， 而是 RNA 摺疊社群多年來累積的另一支「實務優化」傳統的同類想法—— branch-and-bound、profile-guided pruning—— 換個 cost function 就能跑。 這是 cross-disciplinary borrowing 的一個微妙之處： 一個領域的「最新論文」未必是最該借的—— 很多時候是某個領域累積的「實務常識」更值得搬， 因為它已經被多年的工程使用打磨過。

longest-chain bound ——一個被無關鄰居打敗的搜尋

longest-chain bound 是這個故事的技術核心。 要理解它為何有效，先看 naive DP 為何浪費。 對 [i, j] 區間， 演算法窮舉所有 split 點 k， 計算 cost(i, k) + cost(k+1, j)， 再跟「i 跟 j 並行」的 candidate 比。

問題是： 很多 split 點之間根本沒有任何 dependency， 把它們區分成不同子問題只是製造組合數目—— 這就是標題裡那個「被無關鄰居打敗的優化」—— naive 演算法被那些跟核心 chain 無關、 卻佔據 split-point 列表的「鄰居」拖垮。 用直覺的講法： DP 的搜尋空間裡有「真正會改變最佳解的決策」， 也有「不論怎麼選都不影響最佳值的決策」； naive 演算法把兩種一起窮舉， longest-chain bound 把後者剪掉。

longest-chain bound 用一個 cheap-to-compute 的下界， 把「不可能比現有 candidate 好」的 split 早早砍掉。 重要的是這個 bound 必須是「可信的下界」—— 它報告的數字必須 ≤ 真實最少 round-trip 數， 不然 prune 會剪錯。 longest-chain 之所以是合法下界， 來自一個簡單事實： 依賴 DAG 上的最長 chain 必須串行， 沒有 schedule 能讓 chain 上的 statement 並行。 具體形式是：

// 走過區間 [i, j] 時的 prune
function cost(i, j):
  if memo[i][j] is set: return memo[i][j]
  lower = longestChain(i, j)         // 區間內 dep-DAG 最長 chain
  best  = ∞
  for k in (i, j):
    if lower ≥ best: break           // 剩下的 split 不可能再好
    candidate = cost(i, k) + cost(k+1, j)
    best = min(best, candidate)
  // 並行 candidate（兩端可以摺進同一 Par 包住的子樹）
  if noDep(i, j):
    best = min(best, 1 + cost(i+1, j-1))
  memo[i][j] = best
  return best

// longestChain 本身是 O(n) per 區間，但跨區間可以 amortise
// 整體：worst-case 仍是 O(n³)，realistic 在 O(n² log n) 左右

「無關鄰居」這個說法值得多停一下。 生物學裡的同類觀察是： RNA 摺疊時， 未配對的鹼基（loop region）不會影響周邊已配對 stem 的能量計算—— 只要 stem 的兩端確定， loop 內的細節在那一輪可以忽略。 Nussinov DP 把這個性質編碼成「split at k」的可分性。

Duncan 在 ApplicativeDo 上看到了對應： 那些不參與長依賴鏈的「孤立 statement」對排程樹的整體形狀貢獻有限—— 它們只能夾在某個並行袋子裡或某個 sequential 鏈之間， 不會自己改變主結構。 longest-chain bound 把這個直覺量化成 prune 條件。 更精確地講： longest-chain bound 在每個區間給出一個「locality-aware」的下界， 讓 DP 演算法早早識別「這段不會比已知更好」並退出。 下面這張表是 Duncan post 裡的核心數據—— naive 跟 optimised 在三組 input 上的 cut-check 數， 加上 realistic / adversarial 兩種類別的對比：

看這張表的時候有兩件事值得注意。 第一，realistic 跟 adversarial 的「提升倍數」走向完全不同—— adversarial 上隨 N 從 17× 漲到 67×（趨近於 N 量級的線性提升）， realistic 上反而從 4.8× 微跌到 3.2×。

原因不是優化在 realistic 上變差， 而是 realistic 的 naive 本來就沒那麼 explode—— 它的 effective complexity 更接近 O(n²) 而非 O(n⁴)， 因為短 chain、稀疏依賴讓 DP 表本來就有大片可以剪。 優化在這裡的角色是「把那個本來就溫和的成本再 prune 掉一些」—— 絕對值有意義，倍數不會驚人。 這也是讀 benchmark 表的一個常見陷阱： 「倍數」會被 baseline 的高低扭曲， 對 realistic 來說 3.2× 的提升比對 adversarial 的 67× 提升更有現實意義， 因為它影響的是日常編譯路徑。

第二，1,000 statement 的 worst-case 從 55 秒掉到「秒級」這個落差， 意味著 ApplicativeDo 的 optimal 版本終於有機會從 -foptimal-applicative-do 升級到預設啟用—— 這個 flag 多年來只有少數知道並手動開啟的人在用， 自動化之後對 Haxl、batched IO library 這類庫的使用者來說等於白賺 query batching。 從 GHC release notes 的角度看， 這條 line item 不會很長——可能只是「-foptimal-applicative-do is now enabled by default」一句話—— 但背後是一整篇 cross-disciplinary 借鑑的故事在支撐。

三種視角下的同一棵樹

到這裡值得把三個世界並排看一次。 同一個遞迴結構在生物學裡是 RNA 二級結構樹、 在 Haskell 裡是 ApplicativeDo 排程樹、 在 DP 框架裡是區間切分的決策樹。 三個視角看的是同一棵樹的三種影子—— 切換 tab 看實際對應：

-- 原始 do-block （以 Haxl batched IO 為例）
haxlQuery = do
  a <- fetchUserName 1     -- 依賴 user-1
  b <- fetchUserName 8     -- 依賴 user-8
  c <- fetchUserName 2     -- 依賴 user-2
  d <- fetchUserName 7     -- 依賴 user-7
  e <- fetchUserName 3
  f <- fetchUserName 6
  g <- fetchUserName 4
  h <- fetchUserName 5
  return (a, b, c, d, e, f, g, h)

-- ApplicativeDo（optimal）desugar 出來的等價形式
haxlQuery =
  (,,,,,,,) <$> fetchUserName 1
            <*> fetchUserName 8
            <*> fetchUserName 2
            <*> fetchUserName 7
            <*> fetchUserName 3
            <*> fetchUserName 6
            <*> fetchUserName 4
            <*> fetchUserName 5
-- ⇒ Haxl runtime 把 8 個 fetch 合併成 1 次 batched query

// 共享的 recurrence——只差 cost function 跟 max/min
cost(i, j) =
  combine of:
    cost(i+1, j)                       // i 留在左、不參與
    cost(i, j-1)                       // j 留在右、不參與
    base(i, j) + cost(i+1, j-1)        // i 跟 j 「配對」
    cost(i, k) + cost(k+1, j)          // 切兩段，k ∈ (i, j)

// RNA：base(i, j) = 1 if 互補 else 0，combine = max
// Haskell：base(i, j) = 1 if noDep else ∞，combine = min
// 兩邊的型別都是 Tree = Leaf | Seq Tree Tree | Par Tree Tree

三個 tab 共用同一棵概念樹只是表象， 重點在於： 型別系統一旦看穿這層同構， 1978 年的 paper 就不只是「靈感來源」， 而是可以直接 cite 的形式化基礎。

Duncan 的 GHC patch 在註解裡引 Nussinov 1978， 等於在程式碼倉庫裡明白告訴未來的維護者： 「這段 DP 不是從零想出來的， 它是某個已被生物資訊學家研究四十年的演算法在新領域的應用—— 對應規則寫在這裡， 原始 paper 與後續優化文獻指過去就能看。」 這是科學-工程之間最健康的借用方式： 不是 metaphor，是 isomorphism。 Metaphor 在程式碼裡很危險， 因為它讓讀者以為「有點像」就行； isomorphism 則精確—— 對應的細節都有名字、都可以對表查證。

能搬走的、不能搬走的

同樣的剪枝想法在哪些 compiler / 排程器上能起作用？ 凡是有「在線性序列上、找最佳 non-crossing 樹結構」形狀的問題， 理論上都能套用。 Duncan 文章末尾零星提及幾個方向， 這裡可以展開列：

第一，任何 do-like 語法的 desugaring。 Idris 的 !-bang notation、 PureScript 的 do、 Scala 的 for-comprehension—— 這些都是同一個 monadic context 排程問題， 差別只在語法皮膚。 如果它們的 stdlib 裡有可以 batch 的 Applicative effect （HTTP client、DB driver）， 同一套 longest-chain prune 過的 Nussinov DP 都能直接放進對應 compiler。 PureScript 已有部分的 ApplicativeDo 變體， Scala 3 的 effect system 也在朝同方向移動， 對這些社群來說 Duncan 的工作是現成的 reference implementation。

第二，更寬廣地， 任何「在 ordered stream 上找最佳 parallel/sequential 排程」的場景。 Build system 是個典型—— Bazel 的 BUILD graph 一旦定下 target 順序（比如 lexicographic）， target 之間的並行可能性與 ApplicativeDo 的 statement 並行可能性形式上同構； 可惜實務上 Bazel 的問題規模通常更大、 會優先用 graph clustering 而非 interval DP。 但對「在 monorepo 內的單一 module 的 BUILD 子集」這類中等規模問題， interval DP 仍可能比 ad-hoc heuristic 好。

第三，硬體相關的指令排程。 CPU 編譯器後端在 basic block 內做 instruction scheduling 時， 本質是同一個「線性指令序列 + dependency edge → 最少 cycle 排程」問題； 但這邊已有四十年的成熟工具 （list scheduling、software pipelining）， 重新引入 Nussinov-style DP 不太可能勝過已調校的啟發式。 同類觀察適用於 GPU shader 編譯。 這也提醒一件事： 跨領域借用要看「目標領域是否已有成熟解」—— 有時候對方的工具箱已經比你帶來的好。

而不能搬走的場景同樣值得列清楚—— 避免讀者把這個技巧無差別地推銷。 第一，whole-program optimisation。 Nussinov-style DP 是 interval-local 的： 它假設線性順序的 statement 集合與外界邊界清楚。 WPO 工具 （LLVM 的 LTO、GHC 的 cross-module specialiser） 的 search space 是整個程式的 call graph， 沒有 interval 概念， 這個 DP 框架無法直接套用。

第二，沒有 separate compilation 的語言。 對動態語言或 monolithic JIT， 「do-block 排程」的位置可能在 runtime 而不是 compile-time—— 演算法是同一個， 但時間預算從「秒級」收縮成「微秒級」， 55-秒-降-秒級的優化在這裡頭沒有等價意義。 JIT 場景下， 通常會選 greedy + 統計 hot path 再 specialise 的路徑， 而不是花預算找全域最佳。

第三，cross-block applicative。 ApplicativeDo 只看單一 do-block； 跨 block 的 Applicative 並行需要使用者重寫 （用 monad transformer 或 explicit applicative builder）。 這不是演算法限制、是 GHC 設計選擇—— 但讀者應該知道這條邊界， 不要以為打開 flag 就會自動 batch 所有 query。 跨 block 的依賴分析牽涉 closure conversion 與 effect tracking， 複雜度比 single-block 高一個數量級。

第四個值得提的限制—— 也是 Duncan 自己沒明說但讀者該意識到的—— 是 input 分布。 longest-chain bound 在 realistic codebase 上之所以好用， 是因為實務 do-block 短 chain 多、長 chain 少。 如果未來某個 codebase 走向「為了 Haxl batching 而把 100 個 statement 寫進同一個 do-block」的反模式， longest-chain bound 的 prune 效果會逐漸退化—— 因為 input 分布漂移向 adversarial 端。 優化生效需要 input 分布配合， 這是任何 input-specific prune 都吃的稅。

還有一個讀者該知道的工程細節： 這個改動沒有改 ApplicativeDo 的語意—— 同樣的 do-block 編譯前後產出語意相同的 desugared Core， 只是 round-trip 數最少。 對下游的 Core simplifier、worker-wrapper、constructor specialisation 等 pass 完全透明—— 他們看到的是 desugar 後的 Core AST， 不在乎這棵樹是 greedy 還是 optimal 演算法產出的。

這也是為什麼 flag 預設啟用的 cost 是純 compile-time、 沒有 runtime regression 風險。 對 Haxl 這類 framework 的使用者來說， 這是純白賺： 手寫 do-block 自動拿到 optimal batching， 無需修改任何 user code、 無需重新 design effect 結構。 Runtime 行為跟 greedy 的差別在 round-trip 數變少、 而非語意改變—— 這是 optimisation 該有的特性。

故事的另一層收穫是 cross-disciplinary 借鑑本身的可操作框架。 Duncan 沒有在 Nussinov paper 之外讀完整個生物資訊學文獻， 他做的事是「看到一個 search 問題， 問『誰花了幾十年研究過這個結構』」—— RNA 摺疊社群的答案恰好是「我們」， 而且他們的工具箱（區間 DP、branch-and-bound prune、近似算法） 跟 compiler 工程師的工具箱在抽象層完全可以對接。

同樣的策略對其他問題可能會指向不同社群： 圖論社群處理排版與 register allocation， 物理社群處理 simulated annealing 與隨機優化， 運籌學社群處理 cutting plane 與 LP。 重要的不是把每個 paper 都讀， 而是建立「這個問題有沒有別人花過四十年思考」這個反射—— 一旦反射建立， 工具借用會變得相當系統。

把 -foptimal-applicative-do 預設啟用， 看起來是一個「flag 切換」的小改動， 實際上有幾層下游影響值得拆開。 第一層是直接的： 所有用 Haxl、Servant、persistent、Squeal 這類有 batched Applicative instance 的庫的使用者， 會在下個 GHC 版本自動拿到 query 合併。 沒有人需要改一行 user code、 沒有人需要 import 新 module—— 這是「不引入 breaking change 的純收益」這類罕見變更。

第二層是教學上的： 之前許多 Haskell 教材把「想用 batched query 嗎？開 -foptimal-applicative-do」當成 advanced topic， 因為使用者需要評估慢編譯的成本。 flag 變成 default 之後， 這個教學負擔消失—— batched query 變成 do-block 的自然能力、 不需要 flag dance。 長期看， 這降低了 Haxl 這類 framework 的學習曲線， 可能會反過來推動更多庫加上 Applicative instance。 當「寫 do-block 就會 batch」是 baseline 預期， library author 自然會把 Applicative instance 列入 must-have。

第三層是 compiler 社群的： 「正確但慢」的優化被解封是個 morale boost， 因為 GHC 裡還躺著其他這類 flag—— -fhalo-...、-flate-spec-constr、 某些 SIMD 路徑—— 它們的存在告訴使用者「我們知道有更好的演算法、但不能預設給你」。 Duncan 這個改動的 meta-訊息是： 這類 flag 不是宿命， 是邀請—— 邀請有時間、有跨領域知識的人去看看別人有沒有解過同形狀的問題。

第四層、也是最遠的一層， 是這個案例本身會被 cite。 GHC 社群有引用先例的傳統—— 很多 compiler pass 的註解裡寫「see PaperX 1995」或「see PaperY 2003」。 Nussinov 1978 進入 GHC source tree 註解， 等於把一個生物資訊學的經典演算法跟一個系統語言的核心優化綁定起來； 下次有 compiler 工程師面對某個被 disabled 的優化、 需要去翻別的領域的工具時， 這個案例會作為「這條路真的可行」的證據被列出來。 Cross-disciplinary borrowing 之所以稀有， 不是因為沒人想做， 是因為大家不知道從哪裡開始； 多一個成功案例，下次起步就容易一些。

What this enables：當 compiler 工程師看到「在線性序列上找最佳並行排程」這類問題，可以直接借用四十年來生物資訊學家在 RNA 摺疊上累積的 DP 工具——Nussinov 1978 的 O(n³) 區間遞迴提供基礎、longest-chain bound 提供實務 prune、Bringmann FOCS 2016 的 subcubic 結果界定理論上界——讓那些「正確但慢、預設關閉」的優化 flag 終於有機會升級成 default，給使用者白賺一輪沒有 breaking change 的效能。