在Haskell中无样板的AST注释？

Question

在Haskell中无样板的AST注释？

haskellghcgeneric-programmingtemplate-haskellscrap-your-boilerplate

28

我一直在尝试使用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 并行的注释树。但是，这些树没有保证具有相同的结构，因此我们会失去类型安全性。

所以我在思考，是否有一种优雅/推荐的解决方案，既避免样板代码，又以类型安全的方式注释树？是否可以用等效节点及其后编译中使用的注释列表替换每个节点？

- jmite

4个回答

6

这个问题与之前一个关于源位置特定注释的问题类似。我认为最优雅的解决方案是重新定义Expr和 Def并提供一个包含注释的构造函数:

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

- Thomas M. DuBuisson

4

您也可以使用属性文法来进行注释。如果需要多种不同的注释，文法方法会更好地扩展。在Hackage上有一些AG库和预处理器，其中一个是uuagc，它被用来构建UHC/EHC Haskell编译器。

- nponeccop

2

同时，也可以编写一个 Template Haskell 宏来将数据类型转换为带注释的数据类型。

- Yuuri

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- J. Abrahamson · Accepted Answer

如果您在数据类型中保留递归，则会导致额外的构造函数出现在每个地方，但可以自由添加注释，而不改变大部分骨架树。

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-代数，那么这种风格会更容易，因为它们会更好地组合在一起。

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 Hutton单子很适合构建AST，Cofree Hutton余单本质上就是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以及Gallais的下方评论所保证的AST操作方式的描述。