如何使用带有 Cofree 注释的 AST? [英] How to work with AST with Cofree annotation?

问题描述

我有这个简单的 Expr AST，我可以轻松地将它转换为 String.

I have this simple Expr AST and I can easily convert it to String.

import Prelude hiding (Foldable)
import qualified Prelude
import Data.Foldable as F
import Data.Functor.Foldable
import Data.Monoid
import Control.Comonad.Cofree

data ExprF r = Const Int
              | Add   r r
                deriving ( Show, Eq, Ord, Functor, Prelude.Foldable )

type Expr = Fix ExprF

testExpr = Fix $ Add (Fix (Const 1)) (Fix (Const 2))

convertToString :: Expr -> String
convertToString = cata $ case
  e@(Const x) -> show x
  e@(Add x y) -> unwords [x, "+", y]

现在我想给它添加一个额外的数据.所以我正在尝试使用 Cofree

Now I want to add an additional data to it. So I am trying to use Cofree

type LineNumber = Int
type Expr2 = Cofree ExprF LineNumber

我可以将 Expr 转换为 Expr2

addLineNumbers :: Expr -> Expr2
addLineNumbers = cata $ case
  e@(Const _) -> 1 :< e
  e -> 2 :< e

但我不知道如何将 Expr2 转换为 String

But I cannot figure out how to convert Expr2 to String

convertToString2 :: Expr2 -> String
convertToString2 = cata $ case
  e@(_ :< (Const x)) -> show x
  e@(_ :< (Add x y)) -> unwords [x, "+", y]

另外，Cofree 是解决这个标注问题的最好方法吗?

Also, is Cofree the best way to solve this annotation problem?

推荐答案

注释语法树的另一种方法是将注释组合到基本函子中.

An alternative way of annotating your syntax tree is to compose the annotation into the base functor.

-- constant functor
newtype K c a = K c
    deriving (Eq, Ord, Show, Read, Functor, Foldable, Traversable)

-- functor product
data (f :*: g) a = (:*:) { left :: f a, right :: g a }
    deriving (Eq, Ord, Show, Read, Functor, Foldable, Traversable)

我们将使用函子积将注释(在 K 内)附加到树的每一层.

We're going to use the functor product to attach an annotation (inside a K) to each layer of the tree.

type AnnExpr = Fix (K LineNumber :*: ExprF)

如果您可以在仅检查树的单个层的同时生成注释(也就是说，您的注释生成代码可以表示为自然转换)，那么您可以使用以下机制来修改函子，同时保持固定点结构就位:

If you can generate annotations while only inspecting a single layer of the tree (that is, your annotation-generating code can be expressed as a natural transformation) then you can use the following bit of machinery to modify the functor while keeping the fixpoint structure in place:

hoistFix :: Functor f => (forall a. f a -> g a) -> Fix f -> Fix g
hoistFix f = Fix . f . fmap (hoistFix f) . unFix

不过，这用处有限，因为大多数有趣的注释(例如类型检查)都需要遍历语法树.

This is of limited usefulness, though, as most interesting annotations such as type-checking require traversal of the syntax tree.

您可以通过简单地忽略注释来重用代码来拆除 Expr.给定 ExprF...

You can reuse the code to tear down an Expr by simply ignoring the annotations. Given an algebra for ExprF...

-- instructions for a stack machine
data Inst = PUSH Int | ADD
type Prog = [Inst]

compile_ :: ExprF Prog -> Prog
compile_ (Const x) = [PUSH x]
compile_ (Add x y) = x ++ y ++ [ADD]

...你可以用它来分解一个 Expr 或一个 AnnExpr:

... you can use it to tear down either an Expr or an AnnExpr:

compileE :: Expr -> Prog 
compileE = cata compile_

compileA :: AnnExpr -> Prog
compileA = cata (compile_ . right)

这篇关于如何使用带有 Cofree 注释的 AST?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！