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

Question

我正在尝试用 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，来自 Trees That Grow

为了通过 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)

每个名称以 开头的类型X都是type 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 的扩展

这是创建扩展所需要的。即使只是需要提供的“身份”扩展（UnDecolated）。

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

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 可扩展，而不需要这么多工作？

Answer 1

您可以将所有类型族合并为一个由符号索引的类型族：

data KeyValueX x =
    KVX (X "KVX" x) String (DataX x) |
    KeyValueX (X "KeyValueX" x)
  deriving Generic
 
data DataX x =
    NullX (X "NullX" x) |
    IntX (X "IntX" x) Int |
    NumX (X "NumX" x) Double |
    BoolX (X "BoolX" x) Bool |
    StringX (X "StringX" x) String |
    ArrayX (X "ArrayX" x) [DataX x] |
    ObjectX (X "ObjectX" x) [KeyValueX x] |
    DataX (X "DataX" x)
  deriving Generic

--

type family X (s :: k) (x :: l) :: Type

使用泛型获取所有构造函数名称：

type ForAllX c x = (AllX c (CNames (DataX x)) x, AllX c (CNames (KeyValueX x)) x)

deriving instance ForAllX Eq x => Eq (DataX x)
deriving instance ForAllX Eq x => Eq (KeyValueX x)

-- CNames defined using generics, below

到那时为止的所有样板也可以使用 Template Haskell 从“基本 AST”生成。

只有一种类型族可以轻松地使用包罗万象的子句定义扩展：

data UD

type instance X s UD = XUD s

type family XUD (s :: Symbol) :: Type where
  XUD "KeyValueX" = Void
  XUD "DataX" = Void
  XUD _ = ()

至于模式，也许仅仅暴露构造函数还不错？GHC 就是这么做的。

导入和泛型代码使这个答案独立：

{-# LANGUAGE
  DataKinds,
  DeriveGeneric,
  PolyKinds,
  StandaloneDeriving,
  TypeFamilies,
  UndecidableInstances #-}
module T where

import Data.Kind (Constraint, Type)
import Data.Void
import GHC.Generics
import GHC.TypeLits

type CNames a = GCNames (Rep a)

type family GCNames (f :: Type -> Type) :: [Symbol] where
  GCNames (M1 D c f) = GCNames f
  GCNames (f :+: g) = GCNames f ++ GCNames g
  GCNames (M1 C (MetaCons name _ _) f) = '[name]

type family (xs :: [k]) ++ (ys :: [k]) :: [k] where
  '[] ++ ys = ys
  (x ': xs) ++ ys = x ': (xs ++ ys)

type family AllX (c :: Type -> Constraint) (xs :: [Symbol]) (x :: l) :: Constraint where
  AllX c '[] x = ()
  AllX c (s ': ss) x = (c (X s x), AllX c ss x)

要点：https://gist.github.com/Lysxia/3f6781b3a307a7e0c564920d6277bee2