Haskell中自頂向下的類型類實例導出

多年前在讀SPJ的syb系列論文時，需要定義一系列的複合類型，藉助syb中提供的函數可以很漂亮地操作複合類型中的節點，包括變換、查詢等等。但是等我真正想用的時候，發現自己定義的類型類需要每一條都寫deriving，有多少條寫多少條。當然，為了解決這個問題你可以這麼干：

#define DERIVINGS deriving (Typeable, Data ,Show, Eq,Generic)ndata Company = C [Dept] DERIVINGSndata Dept = D Name Manager [SubUnit] DERIVINGSndata SubUnit = PU Employee | DU Dept DERIVINGSndata Employee = E Person Salary DERIVINGSndata Person = P Name Address DERIVINGSndata Salary = S Float DERIVINGSntype Manager = Employeentype Name = String ntype Address = Stringn#undef DERIVINGSn

在GHC7.8時，想在TH上做一些generic的事情，那裡的TH中的類型還沒有默認給Generic類型類，所以你要用StandaloneDeriving語言擴展這樣干：

deriving instance Generic FixityDirectionnderiving instance Generic Inlinenderiving instance Generic RuleBndrnderiving instance Generic Matchnderiving instance Generic Namenderiving instance Generic RuleMatchnderiving instance Generic Prednderiving instance Generic Phasesnderiving instance Generic Connderiving instance Generic Modulenderiving instance Generic AnnTargetnderiving instance Generic Typenderiving instance Generic TyVarBndrnderiving instance Generic TyLitnderiving instance Generic Expnderiving instance Generic Litnderiving instance Generic Patnderiving instance Generic Decnderiving instance Generic Clausenderiving instance Generic FunDepnderiving instance Generic Foreignnderiving instance Generic Fixitynderiving instance Generic Pragmanderiving instance Generic FamFlavourn...n

然後如果你想做任何Generic上的事你需要寫同樣多的空instance，這就已經不是蛋疼的問題了，而是語言讓表達羅嗦了。

除此之外新的base標準里Word、Word8、Int16、Ratio等類型不是Generic，Set、Map、ByteString、Text都不是Generic，做起事來就更煩了（不過這是另外一個問題了，我已經用自己寫的庫解決了，就是把它們實現為Generic，也許理論上不那麼正確，但是解決問題就好，比如讓Set與List同構這種，如果只把Set轉為List再轉回來其實不會有任何問題，anyway打算過段時間發布一系列庫）

後來又想要用codec-jvm包在JVM上做一個toy語言，但是其中定義的類型需要比較漂亮的列印出來，藉助GenericPretty應該比較容易，應該沒有多少行代碼，然後事情就發展成了這個樣子：

{-# LANGUAGE FlexibleInstances #-}n{-# LANGUAGE UndecidableInstances #-}n{-# LANGUAGE StandaloneDeriving , CPP#-}n{-# LANGUAGE DeriveGeneric, DeriveAnyClass #-}nmodule Codec.JVM.Pretty n (module Text.PrettyPrint.GenericPretty)n wherennimport Codec.JVMnimport Codec.JVM.ASM.Code.Instrnimport Codec.JVM.ConstPoolnimport Codec.JVM.Constnimport Codec.JVM.Methodnimport Codec.JVM.Fieldnimport Codec.JVM.Attrnimport Codec.JVM.ASM.Code.CtrlFlownnimport GHC.Genericsnimport Text.PrettyPrint.GenericPrettynimport Text.PrettyPrintnimport Codec.JVM.Pretty.GenericOutnn#define DERIVE_INSTANCE(T) deriving instance Generic (T); deriving instance Out (T)nDERIVE_INSTANCE(ClassFile)nDERIVE_INSTANCE(Version)nDERIVE_INSTANCE(IClassName)nDERIVE_INSTANCE(Const)nDERIVE_INSTANCE(MethodInfo)nDERIVE_INSTANCE(FieldInfo)nDERIVE_INSTANCE(AccessFlag)nDERIVE_INSTANCE(Attr)nDERIVE_INSTANCE(NameAndDesc)nDERIVE_INSTANCE(MethodRef)nDERIVE_INSTANCE(FieldRef)nDERIVE_INSTANCE(ConstVal)nDERIVE_INSTANCE(UName)nDERIVE_INSTANCE(Desc)nDERIVE_INSTANCE(Code)nDERIVE_INSTANCE(Offset)nDERIVE_INSTANCE(FieldType)nDERIVE_INSTANCE(PrimType)nDERIVE_INSTANCE(StackMapFrame)nDERIVE_INSTANCE(InnerClassMap)nDERIVE_INSTANCE(InnerClass)nDERIVE_INSTANCE(VerifType)nDERIVE_INSTANCE(MethodDef)nDERIVE_INSTANCE(MethodDesc)n#undef DERIVE_INSTANCEnnderiving instance Generic (Signature a)nderiving instance Out a => Out (Signature a)nnderiving instance Generic (MethodSignature a)nderiving instance Out a => Out (MethodSignature a)nnderiving instance Generic (FieldSignature a)nderiving instance Out a => Out (FieldSignature a)nnderiving instance Generic (ClassSignature a)nderiving instance Out a => Out (ClassSignature a)nnderiving instance Generic (TypeVariableDeclaration a)nderiving instance Out a => Out (TypeVariableDeclaration a)nnderiving instance Generic (ReferenceParameter a)nderiving instance Out a => Out (ReferenceParameter a)nnderiving instance Generic (Parameter a)nderiving instance Out a => Out (Parameter a)nnderiving instance Generic (TypeParameter a)nderiving instance Out a => Out (TypeParameter a)nnderiving instance Generic (Bound a)nderiving instance Out a => Out (Bound a)nninstance Out Instr wheren docPrec n x = parens $ text (show x)n doc = docPrec 0 n

略略無助了一下，所以我就在GHC上提了這個議案Auto derive from top to bottom

並在日本奈良的Haskell Implementor Workshop 2016上給了一個不到5分鐘的talk，描述了這一問題，演示了一下我那個很挫很naive的實現，然後不久，也就20分鐘吧，最後一個lightening talk是fitspec，https://www.youtube.com/watch?v=LnucHlW7924&list=PLnqUlCo055hX1F0PCi9FjdllYQMwCQvps&index=19 ，會場上我就看見了如下的代碼，大家看一下這畫風是不是很熟悉：

Edward Yang對我笑了一下，表示我也很無奈啊～，你剛剛講完的deriving instances top down，後面就有人遇到了。

以Show類型類為例，當我們對父類型A導出Show時，GHCi當然會提示A複合用到的類型B,C...沒有實現Show類型類，可以用deriving導出或者用instance實現，然後當我們為B,C...寫好了，GHCi又會提示這些類型下面的類型需要實現Show，顯然，GHCi是知道問題的，並且能給出提示，可是就是不幫助我們把事情給幹了。於是我便有了兩個思路，一個是藉助GHCi的提示把事兒辦了，雖然可以做成第三方工具，但是不好，另一個就是用TemplateHaskell。

當時2016年有很多問題不知道如何解決，所以原型實現得還不好，在多態類型還有類型的別名上不工作，但是在ICFP2016上認識了Richard Esonburg還有Ryan Scott兩位大神以後對很多很多問題有了思路，於是到現在我認為已經比較完美地解決了我的這一痛點，就是用我在hackage上的derive-topdown: Help Haskellers derive class instances for composited data types.包

對於syb中的例子，我們只需要寫一行就可以導出所有的類型類了。

derivings [Eq, Ord, Generic] Companyn

對於其他使用TemplateHaskell才能導出的類型類，比如fitspec中的deriveMutable，我提供了這個介面：

deriving_th :: (Name, Name -> Q [Dec]) -> Name -> Q [Dec]n

對於視頻中fitsepc那位小哥的代碼，這裡只需要寫成一行就可以了：

deriving_th (Mutable, deriveMutable) HsModulen

再藉助Neil Mitchell的derive庫，搞定各種煩人的QuickCheck類型類實例不再是問題了。還有用aeson中需要把一堆類型導出成FomJSON與ToJSON都是一行的事兒。

我做了測試，對於，haskell-src這種語法樹不是Generic的傻問題一行就可以解決，更早一些的版本連Typeable與Data都不是，在此我也覺得作者沒提供這個的確是他的疏忽。藉助-ddump-splices可以看到代碼是如何生成的，實際上自底向上的，但是這不是重點：

deriving_with_breaks Generic HsModule [Ratio]n ======>n deriving instance Generic SrcLocn deriving instance Generic Modulen deriving instance Generic HsNamen deriving instance Generic HsSpecialConn deriving instance Generic HsQNamen deriving instance Generic HsCNamen deriving instance Generic HsExportSpecn deriving instance Generic HsImportSpecn deriving instance Generic HsImportDecln deriving instance Generic HsTypen deriving instance Generic HsBangTypen deriving instance Generic HsConDecln deriving instance Generic HsAssocn deriving instance Generic HsOpn deriving instance Generic HsQualTypen deriving instance Generic HsLiteraln deriving instance Generic HsPatFieldn deriving instance Generic HsPatn deriving instance Generic HsQOpn deriving instance Generic HsGuardedAltn deriving instance Generic HsGuardedAltsn deriving instance Generic HsAltn deriving instance Generic HsStmtn deriving instance Generic HsFieldUpdaten deriving instance Generic HsExpn deriving instance Generic HsGuardedRhsn deriving instance Generic HsRhsn deriving instance Generic HsMatchn deriving instance Generic HsSafetyn deriving instance Generic HsDecln deriving instance Generic HsModulen

這裡我們需要在[Ratio]類型上停止向下生成，這就是我前面說的base，container，bytestring中一堆類型不是Generic類型類實現的問題，不知道GHC實現者怎麼想的（反正我是無法理解為什麼Ratio竟然不是Generic，但Complex類型竟然是！）。

另外就是如果我想對TemplateHaskell中的類型使用Generic，可以這樣干：

strategy_derivings anyclass [Binary] Infon ======>n deriving anyclass instance Binary NameSpacen deriving anyclass instance Binary NameFlavourn deriving anyclass instance Binary Namen deriving anyclass instance Binary Litn deriving anyclass instance Binary TyVarBndrn deriving anyclass instance Binary TyLitn deriving anyclass instance Binary Typen deriving anyclass instance Binary Stmtn deriving anyclass instance Binary Guardn deriving anyclass instance Binary Bodyn deriving anyclass instance Binary Matchn deriving anyclass instance Binary Rangen deriving anyclass instance Binary Expn deriving anyclass instance Binary Patn deriving anyclass instance Binary Clausen deriving anyclass instance Binary Language.Haskell.TH.Syntax.SourceUnpackednessn deriving anyclass instance Binary Language.Haskell.TH.Syntax.SourceStrictnessn deriving anyclass instance Binary Bangn deriving anyclass instance Binary Conn deriving anyclass instance Binary DerivStrategyn deriving anyclass instance Binary DerivClausen deriving anyclass instance Binary FunDepn deriving anyclass instance Binary Overlapn deriving anyclass instance Binary Callconvn deriving anyclass instance Binary Safetyn deriving anyclass instance Binary Foreignn deriving anyclass instance Binary FixityDirectionn deriving anyclass instance Binary Language.Haskell.TH.Syntax.Fixityn deriving anyclass instance Binary Inlinen deriving anyclass instance Binary RuleMatchn deriving anyclass instance Binary Phasesn

我在實現的時候也考慮了8.2的deriving strategies。有興趣大家可以看看這個問題，視頻可以見Taming deriving zoo。

deriving-topdown的思路很容易，主要用了下面的類型

StateT [Type] Q [Dec]n

StateT記錄當然哪些類型已經被聲明了，Q來生成實例的聲明。有興趣的可以參閱一下源碼，雖然我寫得略難看。

至此，希望不要再有人再寫我文章開頭還有視頻中那樣的代碼了，以後擼AST感覺在導出類型類這一問題上清爽了許多。下一步我要強烈推薦把這一功能加到GHC里，然後開始為GHC貢獻點兒代碼。