Haskell中的AST的无锅板标注？ [英] Boilerplate-free annotation of ASTs in Haskell?

问题描述

我想开始对它进行一些优化，并且部分是这涉及遍历AST并向某些节点添加注解，例如尾部调用等。

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

因此，假设我们有一堆AST的代数类型：

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

如果我正在编写样板，我会创建如下新类型：

  data AnnotatedExpr = PlusExpr Expr Expr [Annotation] ... 
 
 data AnnotatedDef = TypeAlias String [String] Type [Annotation ] ... 
  

这是很多可编写的boilderplate，它似乎是避免这个。

我可以这样写：

 数据注释树= Leaf [注解] 
 |内部[AnnotationTree] [Annotation] 
  

然后我只需要一个与AST并行运行的注释树。但是不能保证这些树会有相同的结构，所以我们会失去类型安全。所以我想知道，是否有一个优雅/推荐的解决方案可以避免样板，但仍以类型安全的方式标注树？用相同的替换每个节点，再加上将用于编译的注释列表？

解决方案

如果你离开在您的数据类型中的递归打开您最终遭受额外的构造函数无处不在，但可以自由分层注释，而无需更改大多数骨架树。

 数据Hutton x  - 非递归函子类型
 = Int Int | Plus xx 
派生Functor 
 
 newtype Tie f = Tie（f（Tie f））
 
 data Annotate fa = Annotate {annotation :: a，layer :: （f（Annotate fa））} 
 
 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） - >注释f a  - > x 
 runAnnotated phi（Annotate _f）= phi（fmap（runAnnotated phi）f）
  

还有一点很好，如果你不介意在Haskell层次上让一定数量的绑定（比如中等深度的eDSL），那么 Free Hutton monad非常适合构建AST，而 Cofree Hutton comonad基本上就是 Annotated 是。

这是一种从下往上构建注释的方法。

  annotate :: Functor f => （f b  - > b） - > Tie f  - >注释f b 
注释phi = runUnannotated $ \x  - >注释（phi（fmap注解x））x 
 
 memoize :: Unannotated  - > Annotated Int 
 memoize = annotate interp 
  

使用相应的显示和 Num 实例

 λ> memoize（2 +（2 + 2））
注释6（Plus（Annotate 2（Int 2））（Annotate 4（Plus（Annotate 2（Int 2））（Annotate 2（Int 2））））） 
  

以下是您可以剥离它们的方式

  strip :: Annotated a  - >未注明的
 strip = runAnnotated Tie 
  

---

请参阅这里有关如何使用相互递归的ADT实现这种AST工作的描述，由Gallais的评论保证如下。

I've been fiddling around with the Elm compiler, which is written in Haskell.

I'd like to start implementing some optimizations for it, and part of this involves traversing the AST and adding "annotation" to certain nodes, such as tail-calls, etc.

I know I can use SYB or uniplate to do the traversal, but I'm wondering if there's a boilerplate-free way to deal with the types.

So, suppose we have a bunch of algebraic types for our AST:

data Expr = PlusExpr Expr Expr ...

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

If I were writing the boilerplate, I'd make new types like this:

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

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

This is a lot of boilderplate to write, and it seems like good practice to avoid this.

I could write something like this:

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

Then I'd just have an annotation tree running parallel to the AST. But there is no guarantee that these trees will have the same structure, so we lose type safety.

So I'm wondering, is there an elegant/recommended solution to avoid boilerplate but still annotate a tree in a type-safe way? To replace each node with an equivalent one, plus a list of annotations which will be used in compilation later?

解决方案

If you leave the recursion in your data type open you end up suffering an extra constructor everywhere, but can layer in annotations freely without changing most of your skeletal tree.

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

This style is much easier when you can write most of your computations as Hutton-algebras since they will compose better.

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)

What's also nice is that if you don't mind letting some amount of binding live in the Haskell level (such as in a middling-deep eDSL) then the Free Hutton monad is great for building ASTs and the Cofree Hutton comonad is essentially what Annotated is.

Here's a way to build annotations from the bottom up.

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

such that with the appropriate Show and Num instances

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

And here's how you can strip them

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

---

See here for a description of how you might achieve this kind of AST work with mutually recursive ADTs, insured by Gallais' comment below.

这篇关于Haskell中的AST的无锅板标注？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！