¿Anotación gratuita de AST en Haskell?

ghc generic-programming

Question

He estado jugando con el compilador Elm, que está escrito en Haskell.

Me gustaría comenzar a implementar algunas optimizaciones para ello, y parte de esto implica atravesar el AST y agregar "anotaciones" a ciertos nodos, como llamadas de cola, etc.

Sé que puedo usar SYB o Uniplate para hacer el recorrido, pero me pregunto si hay una forma gratuita de lidiar con los tipos.

Entonces, supongamos que tenemos un montón de tipos algebraicos para nuestro AST:

data Expr = PlusExpr Expr Expr ...

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

Si estuviera escribiendo la placa de repetición, haría nuevos tipos como este:

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

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

Esta es una gran cantidad de cosas que escribir, y parece una buena práctica evitar esto.

Podría escribir algo como esto:

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

Entonces solo tendría un árbol de anotación paralelo al AST. Pero no hay garantía de que estos árboles tengan la misma estructura, por lo que perdemos la seguridad de tipo.

Así que me pregunto, ¿existe una solución elegante / recomendada para evitar la repetición, pero aún así anotar un árbol de una manera segura? ¿Para reemplazar cada nodo con uno equivalente, más una lista de anotaciones que se usarán en la compilación más adelante?

Answer 1

Esta pregunta es muy similar a una anterior que habla sobre la anotación particular de la ubicación de origen. La solución que encuentro más elegante es volver a definir Expr y Def para proporcionar un constructor que contenga una anotación:

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

Answer 2

Si deja abierta la recursión en su tipo de datos, terminará sufriendo un constructor adicional en todas partes, pero podrá colocar anotaciones libremente sin cambiar la mayor parte de su árbol esquelético.

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

Este estilo es mucho más fácil cuando puedes escribir la mayoría de tus cálculos como Hutton -algebras, ya que se compondrán mejor.

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)

Lo que también es bueno es que si no te importa dejar cierta cantidad de enlaces en vivo en el nivel de Haskell (como en una eDSL de profundidad media), entonces la mónada Free Hutton es ideal para crear AST y la Cofree Hutton es esencialmente lo que se ha Annotated es.

Aquí hay una manera de construir anotaciones de abajo hacia arriba.

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

de tal manera que con las instancias de Show y Num apropiadas

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

Y así es como puedes despojarlos.

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

Vea here una descripción de cómo podría lograr este tipo de trabajo AST con TDA recursivas recíprocas, aseguradas por el comentario de Gallais a continuación.

Answer 3

También es posible escribir una plantilla de macros de Haskell que convierte un tipo de datos en uno anotado.

Answer 4

También puede utilizar las gramáticas de atributo para las anotaciones. Si necesita muchas anotaciones diferentes, el enfoque de las gramáticas se escalará mejor. Hay pocas bibliotecas y preprocesadores AG en Hackage, una es uuagc que se usa para compilar el compilador Haskell UHC / EHC.