Speak my true name, summon my constructor

01-28

眾所周知，Haskell 有選擇性 export 的機制，可以用來隱藏一個數據類型的定義。大多數時候這個特性是好的，它是 modularity 的關鍵——庫作者只提供一個數據類型的名字和 kind signatures，以及一些能夠操作該數據類型的函數（比如 smart constructors），則其他用戶只用關心這些函數如何使用，不用（也不能）操心數據類型的實現方式、對應的構造器如何去模式匹配等細節。

這個機制偶爾也會成為絆腳石——要是庫作者沒有考慮到我的 use case，該給的函數或者 instance 沒給，我自己也沒法實現，那就很尷尬了……最近剛碰到這樣的一個例子：GHC 的 codebase 里，所有的 IR 類型都支持 pretty-print，生成的 dump 確實很好看，然而我想要的是 ugly-print，也就是 GHC 默認 derive 機制生成的 Show instance。以下是一段 Cmm dump 的 pretty 版本：

cCVB: // globaln I64[Sp - 16] = stg_upd_frame_info;n P64[Sp - 8] = _sCUu::P64;n _sCUp::P64 = P64[_sCUu::P64 + 16];n I64[Hp - 16] = sat_sCUt_info;n P64[Hp] = _sCUp::P64;n _cCVr::P64 = Hp - 16;n R2 = _cCVr::P64;n Sp = Sp - 16;n call fact_info(R2) args: 24, res: 0, upd: 24;n

和它的 ugly 版本：

( 7133701809755015307 , BlockCC (CmmEntry L7133701809755015307 GlobalScope) (BSnoc (BCons (CmmStore (CmmRegOff (CmmGlobal Sp) (-16)) (CmmLit (CmmLabel "stg_upd_frame_info"))) (BCons (CmmStore (CmmRegOff (CmmGlobal Sp) (-8)) (CmmReg (CmmLocal (LocalReg sCUu "P64")))) (BCons (CmmAssign (CmmLocal (LocalReg sCUp "P64")) (CmmLoad (CmmRegOff (CmmLocal (LocalReg sCUu "P64")) 16) "P64")) (BCons (CmmStore (CmmRegOff (CmmGlobal Hp) (-16)) (CmmLit (CmmLabel "sat_sCUt_info"))) (BCons (CmmStore (CmmReg (CmmGlobal Hp)) (CmmReg (CmmLocal (LocalReg sCUp "P64")))) (BCons (CmmAssign (CmmLocal (LocalReg cCVr "P64")) (CmmRegOff (CmmGlobal Hp) (-16))) (BCons (CmmAssign (CmmGlobal (VanillaReg 2 VGcPtr)) (CmmReg (CmmLocal (LocalReg cCVr "P64")))) BNil))))))) (CmmAssign (CmmGlobal Sp) (CmmRegOff (CmmGlobal Sp) (-16)))) CmmCall { cml_target = CmmLit (CmmLabel "fact_info") , cml_cont = Nothing , cml_args_regs = [ VanillaReg 2 VGcPtr ] , cml_args = 24 , cml_ret_args = 0 , cml_ret_off = 24 } )n

為了使用 GHC API 寫編譯器，需要完全掌握各種 IR 的數據類型的含義，一個很重要的方法就是編譯一些小的例子，然後導出 dump 來學習。與 pretty-print 的 dump 相比，顯然 ugly-print 的 dump 能夠直接對應到數據類型的定義上，兩者結合閱讀就不用在看到 pretty-print 版本里不認識的語法特性時手動去查 GHC codebase 里相應的 print 邏輯如何實現了。

通過 GHC 的 standalone deriving 擴展，我們可以在自己的 module 里去為別人的 datatype 去 derive 一些 Show instance。當然，這需要別人把該 datatype （及其依賴的所有 datatype）的完整定義給 export 出來，才能夠 derive。在為這些 IR types 實現 Show instance 時，屢屢碰到一些 GHC team 故意藏起來定義的 datatype，如果該 datatype 起碼實現了 pretty-print 的話，我可以用 pretty-print 的結果轉為字元串糊弄一下，但少數的 datatype 既沒有 Show instance，也不支持 pretty-print，還把定義給藏起來了，連手動去模式匹配一下都辦不到……

好了，背景故事就扯到這為止。Haskeller 在需要對被隱藏定義的 datatype 進行模式匹配時，有 2 種方法：

給那個庫發 pull request 騷擾作者
使用黑魔法召喚這個 datatype 的 constructor

所以本文宗旨就是介紹如何施法召喚一個 datatype 的 constructor，並將其用於模式匹配：Speak my true name, summon my constructor.

首先給項目加上 template-haskell 依賴。以下是召喚一個 constructor，並將其用於 pattern matching 的術式：

summon :: Name -> String -> (Name -> Pat) -> Q Patnsummon t c mp = don info <- reify tn case info ofn TyConI dec -> don let dec2cons dec =n case dec ofn DataD _ _ _ _ cons _ -> consn NewtypeD _ _ _ _ con _ -> [con]n _ ->n error $n show dec ++n " is not a data or newtype declaration."n con2name con =n case con ofn NormalC name _ -> namen RecC name _ -> namen InfixC _ name _ -> namen ForallC _ _ con -> con2name conn _ -> error $ show con ++ " is unsupported by con2name."n cnames = map con2name $ dec2cons decn case find ((== c) . nameBase) cnames ofn Just n -> pure $ mp nn _ ->n fail $n c ++ " is not among the constructors of " ++ nameBase tn _ -> fail $ nameBase t ++ " is not a plain type constructor."n

介紹一下 Template Haskell 相關的幾個類型。首先是 Q Monad —— 每一個黑魔法術式，不對，Template Haskell splice 的類型可以分為 Q Exp、Q Pat、Q Type、Q [Dec]，分別代表生成表達式、模式、類型和聲明。Q Monad 用於管理代碼生成相關的一些狀態（比如生成 fresh identifier），同時可以 lift IO action。這裡，我們需要用召喚出的 constructor 實現模式匹配，所以 splice 的類型為 Q Pat。

接下來是 reify 函數。reify 函數能夠在 Q Monad 中查詢一個 Name 對應的信息。我們在調用 summon 時，當前 scope 里能用的 Name 只有某個 datatype 自身的名字，所以先將這個名字進行 reify，然後查看查詢結果，我們關心的是 TyConI，也就是普通的 type constructor。這裡我們匹配到了一個 Dec 類型的值，前面說過 Dec 對應 declaration，也就是說我們通過一個 datatype 的名字獲取了它的完整定義。

直接將這個 Dec 重新導出相當於重新定義一個相同的 datatype，會與當前 scope 中已有的版本發生衝突，所以我們退而求其次，遍歷這個 Dec，獲取所有的 constructor 的 Name，在其中查找是否有 Name 匹配 summon 函數中 String 參數指定的 constructor 名字，有則將其提取出來——到這一步，召喚術成功了一大半，我們打破了 module barrier，獲取了 constructor 的 Name，這個 Name 可以用來生成各種代碼。沒有經過 reify 的過程，直接將 String 轉換成 Name 是不能實施召喚的。我們需要用這個 Name 來模式匹配某一個 constructor。所以 summon 的另一個參數是類型為 Name -> Pat 的回調函數，這個函數用於組裝出我們需要的 pattern 代碼。

Template Haskell splices 的 definition site 和 use site 需要分開在不同 module 中。在這個 splice 定義好以後，在需要用到它的 module 中，import 該 splice 的定義 module，打開 TemplateHaskell 擴展，然後可以這樣用：

showStgBinderInfo :: GHC.StgBinderInfo -> StringnshowStgBinderInfo x = case x ofn $(summon GHC.StgBinderInfo "NoStgBinderInfo" (n -> ConP n [])) -> "NoStgBinderInfo"n $(summon GHC.StgBinderInfo "SatCallsOnly" (n -> ConP n [])) -> "SatCallsOnly"n

在 case expression 中，需要提供一個 pattern 的地方，我們用 $(....) 代替，括弧內是一個類型為 Q Pat 的表達式，GHC 在編譯該 module 時會運行 Q Monad 中的計算，生成一個 pattern。給 summon 傳遞參數時，需要傳遞特定 datatype 的 Name，我們可以有 2 種方法獲取它：

傳遞一個 String，然後手動通過 lookupTypeName / lookupValueName 在 type/value 的 namespace 中查找該 Name
直接通過 Template Haskell 的特殊語法來構造，比如 f 在當前 scope 的 value 中查找 f，而 T 在當前 scope 的 type 中查找 T

現在，使用 summon，我們即可在知道一個 datatype 的名字與它的 constructor 名字的前提下，召喚它的 constructor，用於（庫作者不希望你做的）模式匹配。

以上是 Template Haskell 的一個簡單的 use case。這個擴展還可以做許多其他有趣的事，展開來講的話也許要開個 Deep Dark Haskell 系列坑了，專門講各種不優雅、不安全的 Haskell 編程技巧（逃

參考資料：

9.26. Template Haskell

template-haskell-2.12.0.0: Support library for Template Haskell