Attribute Grammars and Functional Programming Deforestation
Fourth International Static Analysis Symposium -- Poster Session, Paris, France, (September 1997)Abstract
The functional programming community is paying increasing attention
to static structure-based transformations. For example, generic control
operators, such as fold, have been introduced in functional
programming to increase the power and applicability of a particular
kind of static transformation, called deforestation, which
prevents the construction of useless intermediate data structures
in function composition. This is achieved by making the structure
of the data more explicit in program specifications. We argue that
one of the original concepts of Attribute Grammars is precisely to
make data structures explicit in program specifications. Furthermore,
there exists a powerful static deforestation-like transformation
in their context. In this paper, we present similarities between
deforestation methods, on the one hand with the functional approach,
and on the other hand with the Attribute Grammars approach. In order
to gain a grasp of these similarities, we first make a simple comparison:
purely-synthesized Attribute Grammars and first order folds. In this
context, deforestation transformations are equivalent. This allows
us to highlight the limitations of the fold formalism and to present
how the hylomorphism approach generalizes it; hylomorphisms and attribute
grammars are surprisingly alike. Finally, we show how the inherited
attribute notion in Attribute Grammars solves some transformation
problems in higher order functional programs.
Description
Attribute Grammar