This papers describes the principles and the functionalities of the Minotaur system. Minotaur is a generic interactive environment based on the integration of the Centaur system and the FNC-2 system, two systems widely used to specify syntax and semantics of programming languages and generate efficient semantic tools from these specifications. We show how Attribute Grammars techniques can be adequate for evaluation of a quite large subclass of Natural Semantics specifications, including specifications of an arithmetic calculator, a tree transformation, a type-checker for an Algol-like language, ... For this subclass of Natural Semantics specifications, the Minotaur system automatically generates an incremental and efficient (in time and memory) evaluator which gives to Natural Semantics an industrial strength implementation.
The deforestation of a functional program is a transformation which gets rid of intermediate data structures constructions that appear when two functions are composed. The descriptional composition, initially introduced by Ganzinger and Giegerich, is a deforestation method dedicated to the composition of two attribute grammars. This article presents a new functional deforestation technique, called symbolic composition, based on the descriptional composition mechanism, but extending it. An automatic translation from a functional program into an equivalent attribute grammar allows symbolic composition to be applied, and then the result can be translated back into a functional program (for instance, using the Jonhsson's transformation). This yields to a source to source functional program transformation. The resulting deforestation method provides a better deforestation than other existing functional techniques. Symbolic composition, completely dedicated to the declarative and descriptional features of attribute grammars is intrinsically more powerful than categorical-flavored transformations, whose recursion schemes are set by functors. These results lead us to believe that attribute grammars are a simple intermediate representation, particularly well-suited for program transformations.
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. This paper 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.
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.
Recently, generic programming becomes of a major interest in several programming paradigms. A recurrent idea to achieve genericity is to abstract computations from their representative data structures. This allows these generic specifications to be instantiated onto a large number of neighboring data structures. Moreover the program can be adapted when the data structures have to evolve. Polytypic programming, adaptive programming and generic attribute grammars are generic programming methods related to this approach. Their comparison leads us to propose a common framework for generic programming: automatic generation of programs that compute morphisms between data structures, and program composition. Thanks to this compositional approach, the complete specialization of generic programs could be advantageously delegated to some powerful and general deforestation method.
The deforestation of a functional program is a transformation which gets rid of intermediate data structures constructions that appear when two functions are composed. The descriptional composition, initially introduced by Ganzinger and Giegerich, is a deforestation method dedicated to the composition of two attribute grammars. This article presents a new functional deforestation technique, called symbolic composition, based on the descriptional composition mechanism, but extending it. An automatic translation from a functional program into an equivalent attribute grammar allows symbolic composition to be applied, and then the result can be translated back into a functional program. This yields a source to source functional program transformation. The resulting deforestation method provides a better deforestation than other existing functional techniques. Symbolic composition, that uses the declarative and descriptional features of attribute grammars is intrinsically more powerful than categorical-flavored transformations, whose recursion schemes are set by functors. These results tend to show that attribute grammars are a simple intermediate representation, particularly well-suited for program transformations.
La déforestation d'un programme fonctionnel est une transformation qui consiste à éliminer la construction des structures intermédiaires qui sont introduites par les compositions de fonctions. La composition descriptionnelle, initialement introduite par Ganzinger et Giegerich, est une méthode de déforestation spécifique, qui s'applique à la composition de deux grammaires attribuées. Cet article propose une nouvelle technique de déforestation, appelée composition symbolique, qui est une extension et une amélioration de la composition descriptionnelle. En traduisant automatiquement un programme fonctionnel en une grammaire attribuée équivalente, il est possible de lui appliquer la composition symbolique, et de traduire le résultat en un programme fonctionnel (par exemple, en utilisant la transformation de Johnsson). On obtient alors une transformation source à source de programmes fonctionnels. La méthode de déforestation ainsi obtenue donne de meilleurs résultats que les méthodes fonctionnelles existantes. La composition symbolique, complètement dédiée au caractère déclaratif et descriptionnel des grammaires attribuées est intrinsèquement plus puissante que les transformations basées sur les notions catégorielles, dont les schémas de récursions sont figés par des foncteurs. Ces résultats confirment que la notation des grammaires attribuées est une représentation intermédiaire simple et particulièrement adaptée aux transformations de programmes.
In the functional language domain, there exist several works on the problem of garbage collection at compile time. In the context of Attribute Grammars, the memory optimisation problem spawned a number of works on the notion of attribute lifetime. We present a method which, in this context, allows to replace some function calls with their destructive counterpart. If we consider the functional program which is equivalent to a given attribute grammar, our technique can be seen as a static method for its update-in-place transformation. This method uses the results obtained on the attribute lifetime notion. One of its features is that it uses only classical static analysis methods for attribute grammars.
Generic control operators, such as fold, have been introduced in functional programming to increase the power and applicability of data-structure-based transformations. This is achieved by making the structure of the data more explicit in program specifications. We argue that this very important property is one of the original concepts of attribute grammars. In this paper, we informally show the similarities between the fold formalism and attribute grammar specifications. We also compare their respective method to eliminate the intermediate data structures introduced by function composition (notion of deforestation or fusion): the normalization algorithm for programs expressed with folds and the descriptional composition of attribute grammars. Rather than identify the best way to achieve deforestation, the main goal of this paper is merely to intuitively present two programming paradigms to each other's supporting community and provide an unbiased account of their similarities and differences, in the hope that this leads to fruitful cross-fertilization.
Les opérateurs de contrôle génériques tels que fold ont été introduits en programmation fonctionnelle pour augmenter la puissance et le champ d'application des transformations fondées sur la structure des données. Ceci est possible en rendant cette structure plus explicite dans la spécification des programmes. Nous considérons que cette caractéristique fondamentale est l'un des concepts de base des grammaires attribuées. Dans cet article, nous exposons informellement les similitudes qui existent entre le formalisme du fold et la spécification par grammaires attribuées. Nous comparons également leurs méthodes respectives d'élimination des structures intermédiaires introduites lors de la composition de fonctions (notion de déforestation ou de fusion) : l'algorithme de normalisation pour les programmes exprimés à l'aide de folds et la composition descriptionnelle pour les grammaires attribuées. Le but principal de cet article est de présenter intuitivement chacun de ces deux paradigmes, ainsi que leurs similitudes qui offrent des possibilités de fertilisation croisée.
Les opérateurs de contrôle génériques tels que fold ont été introduits en programmation fonctionnelle pour augmenter la puissance et le champ d'application des transformations fondées sur la structure des données. Ceci est possible en rendant cette structure plus explicite dans la spécification des programmes. Nous considérons que cette caractéristique fondamentale est l'un des concepts de base des grammaires attribuées. Dans cet article, nous exposons informellement les similitudes qui existent entre le formalisme du fold et la spécification par grammaires attribuées. Nous comparons également leurs méthodes respectives d'élimination des structures intermédiaires introduites lors de la composition de fonctions (notion de déforestation ou de fusion) : l'algorithme de normalisation pour les programmes exprimés à l'aide de folds et la composition descriptionnelle pour les grammaires attribuées. Le but principal de cet article est de présenter intuitivement chacun de ces deux paradigmes, ainsi que leurs similitudes qui offrent des possibilités de fertilisation croisée
Generic control operators, such as fold, have been introduced in functional programming to increase the power and applicability of data-structure-based transformations. This is achieved by making the structure of the data more explicit in program specifications. We argue that this very important property is one of the original concepts of attribute grammars. In this paper, we present the similarities between the fold formalism and attribute grammars. In particular, we show the equivalence of their respective deforestation methods. Given these results and the fundamental role of deforestation in the concept of structure-directed genericity, first devised for attribute grammars with descriptional composition, we show how the fold operator with its fusion method allow to transport this concept in the area of functional programming.
Dans le domaine des langages fonctionnels, il existe un ensemble de travaux sur les problèmes de récupération de mémoire au moment de la compilation. Dans le domaine des grammaires attribuées, ce problème a donné lieu à l'étude de la notion de durée de vie des attributs. Dans ce rapport, nous étudions la possibilité de construire automatiquement la version ``destructive'' correspondant à une fonction de mise à jour applicative donnée. Par destructive, on entend le fait qu'elle puisse modifier physiquement la structure de son argument mis à jour, évitant ainsi de nombreuses allocations mémoire. D'autre part, nous devons déterminer sous quelles conditions un appel à une fonction de mise à jour applicative dans une grammaire attribuée peut être remplacé par un appel à sa version destructive. Ces optimisations permettent de réutiliser des structures de données complexes au lieu de les dupliquer. Dans ce cadre, nous fournissons des éléments de comparaison entre les travaux de Philip Wadler sur la déforestation et ceux de Gilles Roussel sur la méta-composition. Ces comparaisons sous forme d'observations peuvent constituer une amorce de rapprochement entre la programmation fonctionnelle et les grammaires attribuées.
Grammar Flow Analysis (GFA) is a computation framework that can be applied to a large number of problems expressed on context-free grammars. In this framework, as was done on programs with Data Flow Analysis, those problems are split into a general resolution procedure and a set of specific propagation functions. This paper presents a number of improvement techniques that act on the resolution procedure, and hence apply to every GFA problem: grammar partitioning, non-terminals static ordering, weak stability and semantic stability. Practical experiments using circularity tests for attribute grammars will show the benefit of these improvements.
FNC-2 is a modern attribute grammar processing system aiming at expressive power, efficiency, ease of use and versatility. This paper provides the reader with a brief tour inside FNC-2, presenting the most important features of its ``engine'': efficient sequential exhaustive, parallel exhaustive and sequential incremental evaluation of strongly non-circular AGs. These methods are based on the visit-sequence paradigm; the first one makes use of extensive space optimizations. Then we describe the external features of the system--attribute coupled grammar view of an AG, specially-designed AG-description language, with provisions for true modularity, and complete environment--that make it really usable for developing large-scale applications. Experience with the system is briefly reported.
FNC-2 is an advanced attribute grammar system aiming at production-quality, currently under development at INRIA. After a brief tour through its internals and a short presentation of its input language Olga, the talk will concentrate on how FNC-2 and its companions can be used to develop large language-processing applications. The key feature for enhancing programmers' productivity and supporting teamwork is FNC-2 constructs for modularity. This will be exemplified by the development of FNC-2 itself. Finally we'll present how FNC-2 can be combined with other tools under development at INRIA to form a complete, high-quality compiler production workbench.
Olga is the input language of the FNC-2 attribute grammar processing system, currently under development at INRIA. As such, it is designed for the specification of attribute grammars and is specialized for this purpose. The features of Olga can be classified into those which make it a powerful general-purpose applicative language and those which make it a specialized AG-description language. A remarkable feature of Olga is its strong support for modularity. The paper discusses the design goals for Olga and presents the most important aspects of the language. It also includes comparisons with other existing languages, an overview of the implementation of Olga, namely the FNC-2 system, and an account of the experience gained in using Olga.
FNC-2 is a new attribute grammar processing system aiming at expressive power, efficiency, ease of use and versatility. Its development at INRIA started in 1986, and a first running prototype is available since early 1989. Its most important features are: efficient exhaustive and incremental visit-sequence-based evaluation of strongly (absolutely) non-circular AGs; extensive space optimizations; a specially-designed AG-description language, with provisions for true modularity; portability and versatility of the generated evaluators; complete environment for application development. This paper briefly describes the design and implementation of FNC-2 and its peripherals. Then preliminary experience with the system is reported.
We present a simple but effective method for constructing efficient attribute evaluators for the class of lordattribute grammars that run on tightly-coupled (shared-memory) multi-processor machines. We also give an account of how we implemented this method in practice. Lastly, we give some figures drawn from realistic experiments, i.e.actual implementation of parallel evaluators for meaningful AGs and their runs on meaningful source texts. The results we have obtained are quite satisfactory, since we observe a quasi-linear speedup with a number of processors varying up to a reasonable number, while the performance with one processor is already quite acceptable.
Memory space management for attribute evaluators is a vital requirement in practice. In fact, using attribute grammars (AGs) will very quickly meet the problem of memory space if it isn't taken into special consideration. We consider this problem for evaluators of the simple multi-visit class, also called l-ordered, because it is the largest possible AGs class for which we can find, at construction time, a method for memory space optimization. We present a new algorithm which decides, at generation time, if it is possible to store attribute instances in global stacks or global variables. The purpose of this approach is to reduce not only memory space, but also as much as possible the number of attributes to be stored in the nodes of the tree. This method is implemented in the new attribute grammar processing system, named FNC-2. Finally we present our first practical results which seem very promising.
Memory space management for attribute evaluators is a vital requirement in practice. In fact, using attribute grammars (AGs) will very quickly meet the problem of memory space if it isn't taken into special consideration. We consider this problem for evaluators of the simple multi-visit class, also called l-ordered, because it is the largest possible AGs class for which we can find, at construction time, a method for memory space optimization. We present a new algorithm which decides, at generation time, if it is possible to store attribute instances in global stacks or global variables. The purpose of this approach is to reduce not only memory space, but also as much as possible the number of attributes to be stored in the nodes of the tree. This method is implemented in the new attribute grammar processing system, named FNC-2. Finally we present our first practical results which seem very promising.
This paper introduces the notion of a coupling of two grammars, defined by associations between their non-terminals and terminals. We present an algorithm for automatically producing, from these associations, an attribute grammar which specifies the translation from one grammar to the other. The motivation for, and context of, this algorithm is our work aiming at improving modularity and reusability of attribute grammars. When it is combined with descriptional composition, we obtain what we consider to be the most declarative framework for this to date.
First (as far as I know) real implementation of a parallel attribute evaluator. (mj)
Bien que les Grammaires Attribuées aient été introduites il y a trente ans, leur manque de pouvoir d'expression les a confinées dans le domaine du traitement des langages de programmation. Dans cet article, nous montrons qu'il est possible d'étendre cette expressivité. Nous soutenons que les Grammaires Attribuées peuvent être utilisées pour décrire des calculs sur des structures qui ne sont pas uniquement des arbres, mais aussi des formes abstraites permettant de décrire des structures infinies. Afin d'atteindre cette expressivité, nous avons introduit deux nouvelles notions : les schémas de productions et les productions conditionnelles. Nous obtenons ainsi un langage dont le pouvoir d'expression est comparable à celui de la plupart des langages fonctionnels du premier ordre, avec un côté déclaratif beaucoup plus marqué. Nos extensions ne remettent pas en cause les bases du formalisme des Grammaires Attribuées sur lesquelles reposent la plupart des travaux concernant celles-ci, en particulier l'analyse statique et la génération d'évaluateurs. Ainsi, les résultats existants peuvent être appliqués directement à nos Grammaires Attribuées étendues, entre autre ceux permettant une implantation efficace (dans notre cas, en utilisant notre système FNC-2). L'intérêt de ces extensions est de redonner aux Grammaires Attribuées leur expressivité intrinsèque. De plus, elles nous permettent d'envisager de nouveaux axes de recherche en comparant nos techniques d'analyses à celles qui ont été développées dans des formalismes de même expressivité.
Although Attribute Grammars were introduced thirty years ago, their lack of expressiveness has resulted in limited use outside the domain of static language processing. In this paper we show that it is possible to extend this expressiveness. We claim that Attribute Grammars can be used to describe computations on structures that are not just trees, but also on abstractions allowing for infinite structures. To gain this expressiveness, we introduce two new notions: scheme productions and em conditional productions. The result is a language that is comparable in power to most first-order functional languages, with a distinctive declarative character. Our extensions deal with a different part of the Attribute Grammar formalism than what is used in most works on Attribute Grammars, including global analysis and evaluator generation. Hence, most existing results are directly applicable to our extended Attribute Grammars, including efficient implementation (in our case, using the FNC-2 system http://www-rocq.inria.fr/oscar/www/fnc2/ for more information.)
Bien que les Grammaires Attribuées aient été introduites il y a trente ans, leur manque de pouvoir d'expression les a confinées dans le domaine du traitement des langages de programmation. Dans cet article, nous montrons qu'il est possible d'étendre cette expressivité. Nous soutenons que les Grammaires Attribuées peuvent être utilisées pour décrire des calculs sur des structures qui ne sont pas uniquement des arbres, mais aussi des formes abstraites permettant de décrire des structures infinies. Afin d'atteindre cette expressivité, nous avons introduit deux nouvelles notions : les schémas de productions et les productions conditionnelles. Nous obtenons ainsi un langage dont le pouvoir d'expression est comparable à celui de la plupart des langages fonctionnels du premier ordre, avec un côté déclaratif beaucoup plus marqué. Nos extensions ne remettent pas en cause les bases du formalisme des Grammaires Attribuées sur lesquelles reposent la plupart des travaux concernant celles-ci, en particulier l'analyse statique et la génération d'évaluateurs. Ainsi, les résultats existants peuvent être appliqués directement à nos Attribute Grammars étendues, entre autre ceux permettant une implantation efficace (dans notre cas, en utilisant notre système FNC-2). L'intérêt de ces extensions est de redonner aux Grammaires Attribuées leur expressivité intrinsèque. De plus, elles nous permettent d'envisager de nouveaux axes de recherche en comparant nos techniques d'analyses à celles qui ont été développées dans des formalismes de même expressivité.
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 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. In this paper, we give a formal definition of Dynamic Attribute Grammars and show how to construct efficient visit-sequence-based evaluators for them, using traditional, well-established AG techniques (in our case, using the FNC-2 system)
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 defined on top of Grammar Couples, informally presented in a previous paper, 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. In this paper, we give a formal definition of Dynamic Attribute Grammars and show how to construct efficient visit-sequence-based evaluators for them, using traditional, well-established AG techniques (in our case, using the FNC-2 system). The major contribution of this approach is to restore the intrinsic power of Attribute Grammars and re-emphasize the effectiveness of analysis and implementation techniques developed for them.
Some years ago, the notion of attribute coupled grammars was introduced by Ganzinger and Giegerich, together with descriptional composition. The latter works essentially at the specification level, i.e., it produces an attribute grammar which specifies the composition of two attribute coupled grammars. We introduce a new approach to this composition of attribute coupled grammars. This composition no longer works at the specification level but at the evaluator level. It produces a special kind of attribute evaluator. For this purpose we have introduced the notion of coupling evaluator. The main advantage of this new approach, compared with descriptional composition, is that it is possible to build separately the coupling evaluator of each attribute coupled grammar; in other words it allows real separate compilation of AG modules. Another important advantage is that we do not need to check the attribute grammar class in order to construct the final sequence of evaluators; thus, this construction produces a new sort of evaluator.
Several years ago, the notion of attribute coupled grammars was introduced by Ganzinger and Giegerich, together with their descriptional composition. The latter works essentially at the specification level, i.e., it produces an attribute grammar which specifies the composition of two attribute coupled grammars. We introduce a new approach to this composition of attribute coupled grammars. It no longer works at the specification level but rather at the evaluator level. It produces a special kind of attribute evaluator, called coupling evaluator. We present both a static version and a dynamic version of coupling evaluators. Both versions retain the good property of descriptional composition that intermediate trees are not physically constructed. In addition--and this is the main advantage of our approach, compared with descriptional composition---, it is possible to build separately the dynamic coupling evaluator of each attribute coupled grammar; in other words we achieve real separate compilation of AG modules.