Haskell中不含Boilerplate的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] ...

这是很多写的boilderplate,并且似乎是避免这种做法的好习惯.

我可以这样写:

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
          ...