¿Anotación sin repeticiones de ASTs en Haskell?

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

Me gustaría comenzar a implementar algunas optimizaciones para él, y parte de esto implica atravesar el AST y agregar "anotación" 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 libre de repeticiones para lidiar con los tipos.

Por lo tanto, 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 el boilerplate, haría nuevos tipos como este: 

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

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

Esto es un montón de burilderplate para escribir, y parece una buena práctica para evitar esto.

Podría escribir algo como esto: 

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

Entonces tendría un árbol de anotaciones 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, ¿hay una solución elegante / recomendada para evitar repeticiones, pero aún así anotar un árbol de una manera segura de tipo? Para reemplazar cada nodo con uno equivalente, más una lista de anotaciones que se utilizarán en la compilación más adelante?

Author: jmite, 2014-11-26
Source

4 answers

Si deja abierta la recursión en su tipo de datos, terminará sufriendo un constructor adicional en todas partes, pero puede superponer 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 puede escribir la mayoría de sus cálculos como Hutton-álgebras, 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 que cierta cantidad de encuadernación viva en el nivel Haskell (como en un eDSL de profundidad media), entonces el Free Hutton la mónada es genial para construir ASTs y la Cofree Hutton comonada es esencialmente lo que 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

Tal que con las instancias 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 aquí para una descripción de cómo podría lograr este tipo de trabajo de AST con ADT mutuamente recursivos, asegurado por el comentario de Gallais a continuación.

 25
Author: J. Abrahamson,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2014-11-27 20:09:38

Esta pregunta es muy similar a una anterior que habla de la anotación particular de la ubicación de la fuente. La solución que me parece más elegante es redefinir Expr y Def para proporcionar un constructor que contiene una anotación: 

data Expr = PlusExpr Expr Expr
          | AnnotatedExpr Annotation Expr
          ...
 6
Author: Thomas M. DuBuisson,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2017-05-23 12:24:37

También puede usar gramáticas de atributos para anotaciones. Si necesita muchas anotaciones diferentes, el enfoque gramatical escalará mejor. Hay pocas bibliotecas AG y preprocesadores en Hackage, uno es uuagc que se utiliza para construir UHC/EHC Haskell compiler.

 4
Author: nponeccop,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2014-11-27 21:25:09

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

 2
Author: Yuuri,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2014-11-27 14:36:06