haskell - Haskell中AST的无样板注释？

Question

我一直在摆弄用 Haskell 编写的 Elm 编译器。

我想开始对其进行一些优化，其中一部分涉及遍历 AST 并向某些节点添加“注释”，例如尾调用等。

我知道我可以使用 SYB 或 uniplate 进行遍历，但我想知道是否有一种无样板的方式来处理这些类型。

所以，假设我们的 AST 有一堆代数类型：

data Expr = PlusExpr Expr Expr ...

data Def = TypeAlias String [String] Type ...

如果我正在编写样板文件，我会创建这样的新类型：

data AnnotatedExpr = PlusExpr Expr Expr [Annotation] ...

data AnnotatedDef = TypeAlias String [String] Type [Annotation] ...

这是要编写的大量样板代码，避免这种情况似乎是一种好习惯。

我可以写这样的东西：

Data AnnotationTree =  Leaf  [Annotation]
     | Internal [AnnotationTree] [Annotation]

然后我就会有一个与 AST 并行运行的注释树。但是不能保证这些树会有相同的结构，所以我们失去了类型安全。

所以我想知道，是否有一种优雅/推荐的解决方案来避免样板，但仍然以类型安全的方式注释树？用等效的节点替换每个节点，加上稍后将在编译中使用的注释列表？

Answer 1

如果您将数据类型中的递归保持打开状态，您最终会在任何地方都遭受额外的构造函数，但可以在注释中自由分层，而无需更改大部分骨架树。

data Hutton x    -- non-recursive functor type
  = Int Int | Plus x x
  deriving Functor

newtype Tie f = Tie (f (Tie f))

data Annotate f a = Annotate { annotation :: a, layer :: (f (Annotate f a)) }

type Unannotated = Tie      Hutton
type Annotated a = Annotate Hutton a

当您可以将大部分计算编写为Hutton-algebras 时，这种风格会容易得多，因为它们会更好地组合。

interp :: Hutton Int -> Int
interp (Int i)    = i
interp (Plus a b) = a + b

runUnannotated :: Functor f => (f x -> x) -> Tie f -> x
runUnannotated phi (Tie f) = phi (fmap (runUnannotated phi) f)    

runAnnotated :: Functor f => (f x -> x) -> Annotate f a -> x
runAnnotated phi (Annotate _ f) = phi (fmap (runAnnotated phi) f)

另一个好处是，如果您不介意让一些绑定存在于 Haskell 级别（例如在中深度 eDSL 中），那么Free Huttonmonad 非常适合构建 AST，Cofree Huttoncomonad 本质上Annotated就是这样。

这是一种自下而上构建注释的方法。

annotate :: Functor f => (f b -> b) -> Tie f -> Annotate f b
annotate phi = runUnannotated $ \x -> Annotate (phi (fmap annotation x)) x

memoize :: Unannotated -> Annotated Int
memoize = annotate interp

这样与适当的Show和Num实例

λ> memoize (2 + (2 + 2))
Annotate 6 (Plus (Annotate 2 (Int 2)) (Annotate 4 (Plus (Annotate 2 (Int 2)) (Annotate 2 (Int 2)))))

这里是你如何剥离它们

strip :: Annotated a -> Unannotated
strip = runAnnotated Tie

---

有关如何使用相互递归的 ADT 来实现这种 AST 工作的描述，请参见此处，由 Gallais 在下面的评论中提供保障。

Answer 2

这个问题与过去谈论源位置的特定注释的问题非常相似。我发现最优雅的解决方案是重新定义Expr并Def提供一个包含注释的构造函数：

data Expr = PlusExpr Expr Expr
          | AnnotatedExpr Annotation Expr
          ...

Answer 3

您还可以将属性语法用于注释。如果您需要许多不同的注释，语法方法会更好地扩展。Hackage 上的 AG 库和预处理器很少，一种是uuagc用于构建 UHC/EHC Haskell 编译器。

Answer 4

也可以编写一个模板 Haskell 宏，将数据类型转换为带注释的。