Attribute Grammars as Recursion Schemes over Cyclic Representations of Zippers
Résumé
Evaluation of attributes w.r.t. an attribute grammar can be obtained by inductively computing a function expressing the dependencies of the synthesized attributes on inherited attributes. This higher-order functional approach to attribute grammars leads to a straightforward implementation using a higher-order lazy functional language like Haskell. The resulting evaluation functions are, however, not easily amenable to optimization rules. We present an alternative first-order functional interpretation of attribute grammars where the input tree is replaced with an extended cyclic tree each node of which is aware of its context viewed as an additional child tree. By the way, we demonstrate that these cyclic representations of zippers (trees with their context) are natural generalizations of doubly-linked lists to trees over an arbitrary signature.
L'évaluation des attributs d'une grammaire attribuées peut s'obtenir inductivement à l'aide d'une fonction exprimant les dépendances entre les attributs synthétisés et les attributs hérités. Cette interprétation d'ordre supérieure s'implémente de façon immédiate dans un langage fonctionnel paresseux tel que Haskell. Néanmoins cette interprétation n'est pas compatible avec les techniques usuelles d'optimisation et nous présentons par conséquent une interprésentation alternative du premier ordre. Cette dernière requière de remplacer l'arbre d'origine par une version cyclique du zipper (arbre dans son contexte) dans laquelle chaque noeud admet un fils supplémentaire donnant accès à son contexte. Nous montrons comment ces représentations cycliques de zippers sont les généralisations naturelles à des signatures arbitraires des représentations des listes avec double chaînage.