Adnotacja AST bez tabliczki rejestracyjnej w Haskell?

Question

Błądziłem przy kompilatorze wiązów, który jest napisany w Haskell.

Chciałbym rozpocząć wdrażanie pewne optymalizacje dla niego, a część wymaga to przemierzając AST i dodawanie adnotacji „do” niektórych węzłów, takich jak ogon-zaproszeń itp

wiem, że mogę używać SYB lub uniplate, aby wykonać traversal, ale zastanawiam się, czy istnieje sposób, w jaki nie można łączyć z typami.

Więc załóżmy, że mamy kilka typów algebraicznych dla naszego AST:

data Expr = PlusExpr Expr Expr ... 

data Def = TypeAlias String [String] Type ... 

Gdybym pisanie boilerplate, że zrobię nowe typy tak:

data AnnotatedExpr = PlusExpr Expr Expr [Annotation] ... 

data AnnotatedDef = TypeAlias String [String] Type [Annotation] ... 

To jest dużo boilderplate do pisania i wydaje się, że dobrą praktyką jest unikanie tego.

mógłbym napisać coś takiego:

Data AnnotationTree = Leaf [Annotation] 
    | Internal [AnnotationTree] [Annotation] 

Wtedy mam tylko drzewa adnotacji biegnącej równolegle do AST. Ale nie ma gwarancji, że drzewa te będą miały taką samą strukturę, więc stracimy bezpieczeństwo typu.

Zastanawiam się, czy istnieje eleganckie/zalecane rozwiązanie, aby uniknąć szablonu, ale nadal opisywać drzewo w sposób bezpieczny dla typu? Aby zastąpić każdy węzeł równoważnym, a także listę adnotacji, które później zostaną użyte w kompilacji?

Answer 1

Jeśli zostawisz rekursji w swoim rodzaju danych otworzyć skończyć cierpienie dodatkowy konstruktora wszędzie, ale może swobodnie warstwować adnotacje, nie zmieniając większości szkieletu drzewa.

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 

Ten styl jest o wiele łatwiejsze, kiedy można napisać większość swoich obliczeniach jako Hutton -algebras ponieważ będą komponować lepiej.

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) 

Co znajduje się również miłe jest to, że jeśli nie przeszkadza pozwalając pewną ilość wiążące żywo w poziomie Haskell (takie jak w średnio-głębokiego eDSL) wtedy Free Hutton monada jest dobre dla ASTs budowlanych i Cofree Hutton Komonad jest w istocie tym, czym jest Annotated.

Oto sposób na tworzenie adnotacji od podstaw.

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 

taki sposób, że z odpowiednimi Show i Num przypadkach

λ> memoize (2 + (2 + 2)) 
Annotate 6 (Plus (Annotate 2 (Int 2)) (Annotate 4 (Plus (Annotate 2 (Int 2)) (Annotate 2 (Int 2))))) 

A oto jak można pozbawić je

strip :: Annotated a -> Unannotated 
strip = runAnnotated Tie 

---

Zobacz here dla opisu, jak można osiągnąć ten rodzaj pracy AST z wzajemnie rekursywnymi e ADTs, ubezpieczone przez komentarz Gallais poniżej.

Answer 2

To pytanie jest bardzo podobne do past one mówiącego o konkretnej adnotacji lokalizacji źródłowej. Rozwiązanie znajdę najbardziej elegancki jest ponowne zdefiniowanie Expr i Def dostarczenie konstruktora, który zawiera adnotację:

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

Answer 3

Możliwe jest również napisanie makr szablonów Haskell, które konwertują typ danych na anotowany.

Answer 4

Do adnotacji można również używać atrybutów gramatycznych. Jeśli potrzebujesz wielu różnych adnotacji, podejście gramatyczne będzie się skalować lepiej. Istnieje niewiele bibliotek AG i preprocesorów w Hackage, jeden to uuagc, który służy do kompilowania kompilatora UHC/EHC Haskell.