Безотказная аннотация AST в Haskell?

Я возился с компилятором 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]

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

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

4 ответа

Решение

Если вы оставите рекурсию в своем типе данных открытой, вы в конечном итоге будете страдать от дополнительного конструктора повсюду, но сможете свободно размещать аннотации без изменения большей части вашего скелетного дерева.

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

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

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

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

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

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

Другие вопросы по тегам