Annotazione Boilerplate di AST in Haskell?

Question

Ho giocato con il compilatore Elm, che è scritto in Haskell.

mi piacerebbe iniziare ad attuare alcune ottimizzazioni per esso, e parte di questo comporta che attraversa l'AST e l'aggiunta di "annotazione" di alcuni nodi, come ad esempio coda le chiamate, ecc

So che posso usare SYB o uniplate per fare il traversal, ma mi chiedo se c'è un modo senza accordi per affrontare i tipi.

Così, supponiamo di avere un sacco di tipi algebrici per la nostra AST:

data Expr = PlusExpr Expr Expr ... 

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

Se dovessi scrivere il testo standard, mi piacerebbe fare nuove tipologie come questo:

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

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

Questo è un sacco di boilderplate da scrivere, e sembra una buona pratica evitare questo.

potrei scrivere qualcosa di simile:

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

Poi avevo appena hanno un albero di annotazione che corre parallela alla AST. Ma non vi è alcuna garanzia che questi alberi abbiano la stessa struttura, quindi perdiamo la sicurezza del tipo.

Quindi mi chiedo, c'è una soluzione elegante/consigliata per evitare lo standard di stampa, ma annotare ancora un albero in un modo sicuro? Per sostituire ciascun nodo con uno equivalente, oltre a un elenco di annotazioni che verranno utilizzate in seguito nella compilazione?

Answer 1

Se si lascia la ricorsione nel vostro tipo open data si finisce per soffrire un costruttore in più in tutto il mondo, ma può fare uno strato di annotazioni liberamente senza cambiare la maggior parte dell'albero scheletrico.

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 

Questo stile è molto più facile quando si può scrivere la maggior parte dei vostri calcoli come Hutton -algebre dal momento che comporranno meglio.

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) 

Qual è anche bello è che se non ti dispiace lasciare una certa quantità di legame vivo nel livello Haskell (ad esempio in un medio-profonda EDSL) quindi la monade Free Hutton è grande per AST costruzione e la Cofree Hutton comonad è essenzialmente ciò che è Annotated.

Ecco un modo per creare annotazioni dal basso verso l'alto.

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 

tale che con le opportune Show e Num casi

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

Ed ecco come si può spogliarli

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

---

Vedere here per una descrizione di come si potrebbe ottenere questo tipo di AST funziona con reciprocamente ricorsivo e ADT, assicurati dal commento di Gallais qui sotto.

Answer 2

Questa domanda è molto simile a un past one che parla della particolare annotazione della posizione di origine. La soluzione che trovo più elegante è quello di ridefinire Expr e Def per fornire un costruttore che contiene un'annotazione:

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

Answer 3

È anche possibile scrivere un modello di macro Haskell che converte un tipo di dati in uno annotato.

Answer 4

È inoltre possibile utilizzare grammatiche degli attributi per le annotazioni. Se hai bisogno di molte annotazioni diverse, l'approccio grammaticale scalerà meglio. Ci sono poche librerie e preelaboratori AG su Hackage, uno è uuagc che viene utilizzato per compilare il compilatore UHC/EHC Haskell.