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 时，这种风格会容易得多。 -代数，因为它们会更好地组成。

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)

还有一个好处是，如果您不介意让一些绑定(bind)存在于 Haskell 级别(例如在中深度 eDSL 中)，那么 Free Hutton monad 非常适合构建 AST 和 Cofree Hutton comonad 本质上是 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

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