在 Haskell 中以通用方式扩充复杂数据类型

Question

我一直在使用Language.C library to modify C programs using generic transformations of SYB library的抽象语法树（AST）。这个 AST 有不同类型的节点（数据类型），每个节点代表一个 C 结构，即表达式、语句、定义等。我现在需要以某种方式增加语句携带的信息，即注释它们。我假设（也许我错了）我不能修改或重新定义原始数据类型，所以我想要这样的东西：

annotateAST anns =
   everywhere (mkT (annotateAST_ anns))

annotateAST_ astnode anns 
  | isStmt astnode = AnnStmt astnode (getAnn astnode anns)
  | otherwise = astnode

通过这种方式，我将得到一个带有注释语句的新 ast，而不是原来的。当然，GHC 会抱怨，因为 everywhere 应该 return 它得到的类型相同，而这不是这里发生的事情。

最后，我需要在不修改原始数据类型的情况下对 AST 进行通用注释，并且以一种易于 return 原始数据结构的方式。对于这个问题，我一直在思考不同的解决方案，但都不相信任何一种，所以我决定在这里分享。

P.S。有人告诉我 SYB 库效率不高。考虑到 Language.C 的 AST 只导出数据，我是否有更有效的替代方法来对 AST 进行通用遍历和修改？

Answer 1

我不是那个库的专家，但它的设计似乎允许用户定义装饰。

这是因为所有主要数据类型都在 NodeInfo 上进行了参数化，标准注释（仅携带位置和名称信息）。例如。图书馆提供

type CTranslUnit = CTranslationUnit NodeInfo

允许您定义

type MyTransUnit = CTranslationUnit MyNodeInfo
data MyNodeInfo = MNI NodeInfo AdditionalStuffHere

所以按照你的意愿装饰AST。

该库提供 Functor 可以影响此类装饰的实例，以及 Annotated 类型 class 以从任何 AST 节点检索（可能是用户定义的）注释。

我会尝试采用这种方法。

设计看起来不错。我能看到的唯一缺点是节点上所有类型的注释类型必须相同，这基本上迫使人们将其定义为内部可能包含的各种注释的巨大总和。例如：

-- AST library for a simple lambda-calculus
data AST n
    = Fun n String (AST n)
    | Var n String
    | App n (AST n) (AST n)

-- user code
data Annotation
    = AnnVar ... | AnnFun ... | AnnApp ...
type AnnotatedAST = AST Annotation

并且我们不对使用 AnnFun 修饰的函数提供静态保证，仅。

人们可能希望利用 GADT 进行更高级的库设计，例如：

-- AST library for a simple lambda-calculus
data Tag = TagFun | TagVar | TagApp
data AST (n :: Tag -> *)
    = Fun (n 'TagFun) String (AST n)
    | Var (n 'TagVar) String
    | App (n 'TagApp) (AST n) (AST n)

-- user code
data Annotation (n :: Tag) where
   AnnFun :: String -> Annotation 'TagFun
   AnnVar :: Int    -> Annotation 'TagVar
   AnnApp :: Bool   -> Annotation 'TagApp
type AnnotatedAST = AST Annotation

这保证了每个节点中的正确注释。 AST 将不再是 Functor，但至少可以定义类似 Functor 的 class。

不过——至少库允许某种形式的用户定义注释，我将不胜感激。

在 Haskell 中以通用方式扩充复杂数据类型

Augment a complex data type in a generic way in Haskell

haskell

generics

data-structures

types

abstract-syntax-tree