Безотказная аннотация 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, который преобразует тип данных в аннотированный.