如何删除 Trees That Grow 引入的所有样板？

问：

我正在尝试在Haskell中定义一种编程语言。我希望使 AST 可扩展：AST 模块的用户（例如漂亮的打印机、解释器、编译器、类型系统、语言服务器等）应该能够通过添加新功能和新数据（用于扩展语法的新数据类型以及用于存储各种组件所需数据的当前数据构造函数的新字段）来扩展它。

我试图通过使用 Trees That Grow （TTG） 来实现这一目标。它有效，但它会导致太多的样板。我的最小原型在代码行数方面变得大了 10 倍，这个数字按 AST 大小乘以扩展的数量增长。更改一些小内容需要更改 AST 模块的几行，而更改扩展性实现方式的某些内容则需要重写其中的大部分内容。

有没有办法减少所需的样板数量，或者理想情况下完全删除它？

我目前所拥有的代码示例

“基础”AST

这只是 AST 的一小部分。它与JSON非常相似，因为我决定从一个小原型开始。

module AST ( KeyValue(..), Data(..) ) where

data KeyValue = KV String Data deriving (Show, Eq, Ord)

data Data =
    Null |
    Int Int |
    Num Double |
    Bool Bool |
    String String |
    Array [Data] |
    Object [KeyValue] deriving (Show, Eq, Ord)

可扩展的 AST，通过生长的树

为了通过 TTG 扩展它，数据类型变为如下：

data KeyValueX x =
    KVX (XKV x) String (DataX x) |
    KeyValueX (XKeyValue x)
 
data DataX x =
    NullX (XNull x) |
    IntX (XInt x) Int |
    NumX (XNum x) Double |
    BoolX (XBool x) Bool |
    StringX (XString x) String |
    ArrayX (XArray x) [DataX x] |
    ObjectX (XObject x) [KeyValueX x] |
    DataX (XData x)

名称以 开头的每种类型都是：Xtype family

type family XKV x
type family XKeyValue x
type family XNull x
type family XInt x
type family XNum x
type family XBool x
type family XString x
type family XArray x
type family XObject x
type family XData x

此外，它们中的每一个都需要在类型中列出，以便更容易派生类：

type ForallX (c :: Type -> Constraint) x = (
    c (XKV x), c (XKeyValue x),
    c (XNull x), c (XInt x), c (XNum x), c (XBool x),
    c (XString x), c (XArray x), c (XObject x), c (XData x)
    )

-- now we can do:
deriving instance ForallX Show x => Show (KeyValueX x)
deriving instance ForallX Show x => Show (DataX x)
deriving instance ForallX Eq x => Eq (KeyValueX x)
deriving instance ForallX Eq x => Eq (DataX x)
deriving instance ForallX Ord x => Ord (KeyValueX x)
deriving instance ForallX Ord x => Ord (DataX x)

当然，一切都需要导出：

module AST ( KeyValueX(..), DataX(..),
             XKV, XKeyValue,
             XNull, XNum, XBool, XString, XArray, XObject, XData,
             ForallX
           ) where

AST 的扩展

这是创建扩展所需的内容。甚至只是需要提供的“身份”扩展（UnDecorated）。

对于每个实例，您需要为每个类型和数据构造函数的类型系列实现一个类型类：

data UD  -- UnDecorated, identity extension
 
type instance XKV UD = ()
type instance XKeyValue UD = Void
 
type instance XData UD = Void
type instance XNull UD = ()
type instance XInt UD = ()
type instance XNum UD = ()
type instance XBool UD = ()
type instance XString UD = ()
type instance XArray UD = ()
type instance XObject UD = ()

然后，为了正确地为用户做事并符合人体工程学，您需要为每个数据构造函数和数据类型提供模式和类型别名：

type KeyValue = KeyValueX UD
pattern KV :: String -> Data -> KeyValue
pattern KV x y <- KVX _ x y where KV x y = KVX () x y
 
type Data = DataX UD
pattern Null :: Data
pattern Null <- NullX _ where Null = NullX ()
pattern DInt :: Int -> Data
pattern DInt x <- IntX _ x where DInt x = IntX () x
pattern DNum :: Double -> Data
pattern DNum x <- NumX _ x where DNum x = NumX () x
pattern DBool :: Bool -> Data
pattern DBool x <- BoolX _ x where DBool x = BoolX () x
pattern DString :: String -> Data
pattern DString x <- StringX _ x where DString x = StringX () x
pattern Array :: [Data] -> Data
pattern Array x <- ArrayX _ x where Array x = ArrayX () x
pattern Object :: [KeyValue] -> Data
pattern Object x <- ObjectX _ x where Object x = ObjectX () x

当然，所有这些东西也应该导出：

module AST ( ...,
              UD,
              KeyValue, Data,
              pattern KV,
              pattern Null, pattern Num, pattern Bool,
              pattern String, pattern Array, pattern Object
           ) where

总结

TTG 将我简单的 10 行模块变成了一个 100 多行的模块，其中 90% 的代码是无聊的、难以维护的样板：

• 最初的（不可扩展的）AST 模块大约需要 10 行。
• 可扩展版本的 AST 最终需要大约 50 行，每个数据构造函数（包括其相关类型系列）被提及大约 4 次。
  • 最重要的是，每个 AST 扩展（包括所需的“标识”扩展）都需要另外 50 行，并再提及每个数据构造函数 3 次。

我估计整个语言可以采用几十种类型，总共有一百多个数据构造函数。然后，我需要定义一些对 AST 的扩展。不可扩展的 AST 大约需要 100 行（一个数量级），而通过 TTG 扩展的 AST 大约需要 10,000 行。所有必需的样板都会使所有这些对我来说都无法管理。

问题

有没有办法减少所需的样板数量，或者理想情况下完全删除它？

否则，是否有其他方法可以使我的 AST 可扩展，而无需做这么多工作？