Аннотирование АСТ в анкете в Хаскелле?

Я играл с компилятором Elm, который написан в Haskell.

Я хотел бы начать реализацию некоторых оптимизаций для него, а часть этого включает в себя обход 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]

Тогда у меня просто будет дерево аннотаций, идущее параллельно АСТ. Но нет никакой гарантии, что эти деревья будут иметь одинаковую структуру, поэтому мы теряем безопасность типов.

Итак, мне интересно, есть ли элегантное/рекомендуемое решение, чтобы избежать шаблона, но все же аннотировать дерево безопасным типом? Чтобы заменить каждый node на эквивалентный, плюс список аннотаций, которые будут использоваться позже в компиляции?

Ответ 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 Hutton отлично подходит для создания АСТ и 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

См. здесь для описания того, как вы можете достичь такого рода работы АСТ с помощью взаимно рекурсивных ADT, застрахованных комментарием Галласа ниже.

Ответ 2

Этот вопрос очень похож на прошлый, говорящий о конкретной аннотации местоположения источника. Решение, которое я нахожу наиболее элегантным, - это переопределить Expr и Def, чтобы предоставить конструктор, содержащий аннотацию:

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

Ответ 3

Вы также можете использовать атрибутные грамматики для аннотаций. Если вам нужно много разных аннотаций, подход грамматик будет лучше масштабироваться. В Hackage имеется несколько библиотек AG и препроцессоров, один из которых - uuagc, который используется для сборки компилятора UHC/EHC Haskell.

Ответ 4

Также можно написать макросы Template Haskell, которые преобразуют тип данных в аннотированный.