Research projects

Didier PARIGOT

Dynamic Attribute Grammar

Although Attribute Grammars were introduced long ago, their lack of expressiveness has resulted in limited use outside the domain of static language processing. With the new notion of Dynamic Attribute Grammars[11] defined on top of Grammar Couples, we show that it is possible to extend this expressiveness and to describe computations on structures that are not just trees, but also on abstractions allowing for infinite structures. The result is a language that is comparable in power to most first-order functional languages, with a distinctive declarative character

Attribute grammars and structure-directed functional programming

Proof of the similarity between attribute grammars and the fold operator and other catamorphisms. On this ground, application to functional programming of concepts and analysis and implementation techniques developed, with great success, for attribute grammars: deforestation [5, 3], structure-directed genericity, evaluation of lenient programs, memory optimization, etc.

Symbolic Composition [4]

To be modular, functional programming widely uses function compositions. Usually, these compositions introduce intermediate data structures that could be discarded for efficiency. Transformations achieving these eliminations are called deforestation.

To improve the power and the effectiveness of deforestation, several intermediate representations have been introduced, such as generic control operators and algebraic programming with fold, catamorphisms, and hylomorphisms. In the attribute grammar community there also exists a powerful and well-known deforestation-like transformation called descriptional composition[8].

This work [4] show that descriptional composition forms the core of a new and a more efficient functional programming deforestation method. For this purpose, a translation from functional programs into attribute grammars is introduced. Descriptional composition combined with a kind of symbolic evaluation defines a powerful tool called symbolic composition. This new transformation deforests some programs for which functional deforestations fail.

Finally, these results lead us to believe that attribute grammar notation is a simple and well-suited intermediate representation for data-structure-based transformations. (See also student suject)

Generic Attribute grammars

We study the notion of genericity, which is the possibility to reuse algorithms specified on a certain data structure on other structures. Although not a new concept by far, genericity raises a lot of interest in the programming and software engineering community, because it opens a way to lower software costs. The spectrum stands structure-directed genericity, devised a few years ago in the context of AGs by Farrow et al. and ourselves [6, 9, 12, 1]. It is based on the observation that you can instantiate (reuse) onto type any function f defined on type if you write a coupling function that transforms every structure of type into the ``equivalent'' structure of type . For instance, to reuse the list-length function to count the number of leaves of a tree, you write a function which returns the list of leaves of a tree and compose it with the list length function. Thanks to descriptional composition, the result of the composition, i.e. the function which counts the number of leaves of a tree, works directly on the tree without constructing the intermediate list. It is clear that, with this approach, instantiation is much less easy than with polymorphism, because you have to write the coupling function by hand, but on the other hand you have much more flexibility in defining the ``equivalence'' of two structures.

Structure-directed genericity is popular in AGs because it's easy to write structure translations with AGs (and because most grammars are so complex that superficial polymorphism is insufficient).Trying to automate structure-directed genericity lead to our own work on automatic generation of coupling AGs [9, 13, 12, 14, 2] (See also student suject)

Attribute grammars and object-oriented programming

Study of the similarities between attribute grammars and some features of object-oriented languages. Adaptation to these languages of the concept of structure-directed programming, especially for genericity. (See also student suject [7]). First we developped a very simple attribute grammar system CHOCOLAT above the language JAVA

Code composition in a software component system

Procope proposition Software should be composed from components in a simple way (LEGO principle). To extend entire systems easily, it is required that components can be adapted flexibly. An important sub-problem here is how to determine the control flow of a software system. Normally this is user-specified; however within an intelligent component system it should be generated automatically, at least in part. Then, when a new component is embedded into such a software system, the control flow can be adapted automatically. This enables that components can be integrated into systems very easily, and that the extension of systems becomes very simple. This enlarges the degree of reuse and diminishes the cost for software development.

Aim

Generation of software control flow from attribute grammars. Application of this technique to component systems in order to achieve extensible and flexible component technology.

Effect

Software becomes easily extensible because control-flow is not user-specified, but generated. Better reuse beyond black-box reuse because systems are adapted automatically when they are extended. The aim of this research is to use attribute grammar technology (in particular CHOCOLAT language [7]) to develop the basic mechanism for code composition in a software component system.

Transforming Denotational Semantics into Dynamic Attribute Grammars

[10]

• References