@STRING{acm = "ACM Press" } @STRING{cambridge="Cambridge University Press" } @STRING{cambridge="Cambridge University Press" } @STRING{j-ieee-software="IEEE Software" } @STRING{lncs = "Lect. Notes in Comp. Sci." } @STRING{lncs = "Lect. Notes in Comp. Sci." } @STRING{springer= "Springer-Verlag" } @TechReport{ jourdan88, author = "Martin Jourdan and Didier Parigot", title = "More on Speeding up Circularity Tests for Attribute Grammars", institution = "INRIA", type = "rapport", number = "RR-828", address = "Rocquencourt", month = apr, year = "1988", keywords = "circ", mynote = "Ameliorations au test de non-circularite: stabilite semantique et ordre statique de traitement des non-terminaux. (mj)" } @InProceedings{ jourdan89a, author = "Martin Jourdan and Didier Parigot", editor = "O. M. Tammepuu", title = "The {FNC}-2 System: Advances in Attribute Grammar Technology", booktitle = "Procs. of the Soviet-French Symposium Informatika '89", pages = "94--118", address = "Tallinn", month = may, year = "1989", keywords = "syst.FNC2 eval alloc", mynote = "Resume des travaux de Didier et presentation de FNC-2", note = "See also: rapport RR-834, INRIA, Rocquencourt (April 1988)." } @TechReport{ parigot87, author = "Didier Parigot", title = "Mise en {\oe}uvre des grammaires attribu{\'e}es: transformation, {\'e}valuation incr{\'e}mentale, optimisations", institution = "University de Paris-Sud", type = "th{\`e}se de 3{\`e}me cycle", address = "Orsay", month = sep, year = "1987", keywords = "tag eval incr" } @PhDThesis{ parigot88, author = "Didier Parigot", address = "Orsay", school = "Université de Paris-Sud", title = "Transformations, {\'E}valuation {I}ncrémentale et {O}ptimisations des {G}rammaires {A}ttribués: {L}e {S}ystème {FNC}-2", year = "1988", url = "http://www.inria.fr/RRRT/TU-0044.html", keywords = "tag eval incr syst.FNC2" } @TechReport{ parigot85, author = "Didier Parigot", title = "Un syst{\`e}me interactif de trace des circularit{\'e}s dans une grammaire attribu{\'e}e et optimisation du test de circularit{\'e}", institution = "University de Paris-Sud", type = "rapport de {DEA}", address = "Orsay", month = sep, year = "1985", keywords = "circ", mynote = "Titre explicite. Optimisations tres efficaces. Travail fait dans le cadre du systeme FNC/ERN. (mj)" } @InProceedings{ jourdan90, author = "Martin Jourdan and Didier Parigot and Catherine Juli{\'e} and Olivier Durin and Carole {Le Bellec}", title = "Design, Implementation and Evaluation of the {FNC}-2 Attribute Grammar System", booktitle = "Conf. on Programming Languages Design and Implementation", pages = "209--222", address = "White Plains, NY", month = jun, year = "1990", keywords = "syst.FNC2 eval tag alloc", note = "Published as {\sl ACM SIGPLAN Notices}, 25(6)", url = "ftp://ftp.inria.fr/INRIA/Projects/oscar/FNC-2/publications/sgpln90-t.ps.gz" , postscript = "../../ftp/fnc2/publications/sgpln90-t.ps.gz", abstract = "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." } @InCollection{ jourdan92, author = "Martin Jourdan and Didier Parigot", editor = "Dieter Hammer", title = "Application Development with the {FNC}-2 Attribute Grammar System", booktitle = "Compiler Compilers '90", series = "Lecture Notes in Computer Science", pages = "85--94", publisher = springer, address = "New York--Heidelberg--Berlin", month = oct # " 1990 " # jan, year = "1992", keywords = "syst.FNC2 applic.MC vari.divers applic.MC", note = "Schwerin", postscript = "../../ftp/fnc2/publications/CC90-t.ps.gz", url = "ftp://ftp.inria.fr/INRIA/Projects/oscar/FNC-2/publications/CC90-t.ps.gz" , abstract = "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." } @TechReport{ julie90a, author = "Catherine Juli{\'e} and Didier Parigot", title = "{S}pace {O}ptimization in the {FNC-2} {A}ttribute {G}rammar {S}ystem", institution = "INRIA", year = "1990", type = "Rapport de recherche", number = "1165", abstract = "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." } @InProceedings{ julie90, author = "Catherine Juli{\'e} and Didier Parigot", year = "1990", month = sep, volume = "461", booktitle = "Attribute Grammars and their Applications (WAGA)", editor = "Pierre Deransart and Martin Jourdan", publisher = "Springer-Verlag", pages = "29--45", series = lncs, address = "Paris", title = "{S}pace {O}ptimization in the {FNC-2} {A}ttribute {G}rammar {S}ystem", crossref = "Deransart90", postscript = "../../ftp/fnc2/publications/optim-t.ps.gz", url = "ftp://ftp.inria.fr/INRIA/Projects/oscar/FNC-2/publications/optim-t.ps.gz" , abstract = "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." } @InProceedings{ lebellec93a, author = "Carole Le{ }Bellec and Martin Jourdan and Didier Parigot and Gilles Roussel", address = "Tallinn", booktitle = "Programming Language Implementation and Logic Programming (PLILP '93)", editor = "Maurice Bruynooghe and Jaan Penjam", pages = "123--136", publisher = springer, series = lncs, title = "{S}pecification and {I}mplementation of {G}rammar {C}oupling {U}sing {A}ttribute {G}rammars", volume = "714", month = aug, year = "1993", postscript = "../../ftp/fnc2/publications/couple-AG-plilp93.ps.gz", url = "ftp://ftp.inria.fr/INRIA/Projects/oscar/FNC-2/publications/couple-AG-plilp93.ps.gz" , abstract = "This paper introduces the notion of a {\em 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." } @TechReport{ duris95, author = "Etienne Duris and Didier Parigot and Martin Jourdan", title = "Mises à jour destructives dans les grammaires attribu\'ees", type = "Rapport de recherche", year = "1995", number = "2686", month = oct, institution = "INRIA", postscript = "../../ftp/fnc2/publications/RR-2686.ps.gz", url = "ftp://ftp.inria.fr/INRIA/publication/RR/RR-2686.ps.gz", abstract = "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." } @TechReport{ roussel95, author = "Gilles Roussel and Didier Parigot and Martin Jourdan", title = "{S}tatic and {D}ynamic {C}oupling {A}ttribute {E}valuators", year = "1995", number = "2670", month = oct, type = "Rapport de recherche", institution = "INRIA", postscript = "../../ftp/fnc2/publications/RR-2670.ps.gz", url = "ftp://ftp.inria.fr/INRIA/publication/RR/RR-2670.ps.gz", abstract = "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 {\em 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 {\em separate compilation\/} of AG modules." } @InProceedings{ roussel94, author = "Gilles Roussel and Didier Parigot and Martin Jourdan", address = "Edinburgh", booktitle = "5th Int. Conf. on Compiler Construction (CC' 94)", editor = "Peter A. Fritzson", month = apr, pages = "52--67", series = lncs, publisher = springer, title = "{C}oupling {E}valuators for {A}ttribute {C}oupled {G}rammars", volume = "786", year = "1994", postscript = "../../ftp/fnc2/publications/couplingevaluatorAG.ps.gz", url = "ftp://ftp.inria.fr/INRIA/Projects/oscar/FNC-2/publications/couplingevaluatorAG.ps.gz" , abstract = "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." } @InProceedings{ jourdan90a, author = "Martin Jourdan and Didier Parigot", address = "Copenhague", booktitle = "European Symp. on Programming (ESOP '90)", editor = "Neil Jones", pages = "240--255", publisher = springer, series = lncs, title = "{T}echniques for {I}mproving {G}rammar {F}low {A}nalysis", volume = "432", year = "1990", postscript = "../../ftp/fnc2/publications/esop90-t.ps.gz", url = "ftp://ftp.inria.fr/INRIA/Projects/oscar/FNC-2/publications/esop90-t.ps.gz" , abstract = "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.", keywords = "applic.DFA" } @InProceedings{ parigot95, author = "Didier Parigot and Etienne Duris and Gilles Roussel and Martin Jourdan", address = "Val-Morin, Québec", booktitle = "Journ\'ees Francophones des Langages Applicatifs", title = "Les grammaires attribu\'ees\,: un langage fonctionnel d\'eclaratif", year = "1996", pages = "263--279", month = jan, postscript = "../../ftp/fnc2/publications/jfla96.ps.gz", url = "ftp://ftp.inria.fr/INRIA/Projects/oscar/FNC-2/publications/jfla96.ps.gz" , abstract = "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 {\em schémas de productions\/} et les {\em 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é.", keywords = "functional" } @InProceedings{ parigot95b, author = "Didier Parigot and Etienne Duris and Gilles Roussel and Martin Jourdan", title = "Les grammaires attribu\'ees\,: un langage fonctionnel d\'eclaratif", booktitle = "journées du GDR de programmation", address = "Grenoble", year = "1995", month = nov, postscript = "../../ftp/fnc2/publications/gdr95.ps.gz", url = "ftp://ftp.inria.fr/INRIA/Projects/oscar/FNC-2/publications/gdr95.ps.gz" , abstract = "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 {\em schémas de productions\/} et les {\em 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é." } @TechReport{ attali94, author = "Isabelle Attali and Didier Parigot", institution = "INRIA", number = "2339", title = "{I}ntegrating {N}atural {S}emantics and {A}ttribute {G}rammars: the {M}inotaur {S}ystem", type = "Rapport de recherche", year = "1994", postscript = "../../ftp/fnc2/publications/RR-2339.ps.gz", url = "ftp://ftp.inria.fr/INRIA/publication/RR/RR-2339.ps.gz", abstract = "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.", keywords = "natural semantic vari.NS" } @TechReport{ parigot95a, author = "Didier Parigot and Etienne Duris and Gilles Roussel and Martin Jourdan", title = "Attribute Grammars: a Declarative Functional Language", type = "Rapport de Recherche", number = "2662", year = "1995", month = oct, institution = "INRIA", postscript = "../../ftp/fnc2/publications/RR-2662.ps.gz", url = "ftp://ftp.inria.fr/INRIA/publication/RR/RR-2662.ps.gz", abstract = "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: {\em 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.)", keywords = "Functional programing ML vari.FP" } @TechReport{ parigot96, author = "Didier Parigot and Gilles Roussel and Martin Jourdan and Etienne Duris", title = "Dynamic {A}ttribute {G}rammars", type = "Rapport de recherche", number = "2881", year = "1996", month = may, institution = "INRIA", postscript = "../../ftp/fnc2/publications/RR-2881.ps.gz", url = "ftp://ftp.inria.fr/INRIA/publication/RR/RR-2881.ps.gz", abstract = "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 {\em Dynamic Attribute Grammars} defined on top of {\em 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." } @InProceedings{ parigot96a, author = "Didier Parigot and Gilles Roussel and Martin Jourdan and Etienne Duris", booktitle = "Int. Symp. on Progr. Languages, Implementations, Logics and Programs (PLILP'96)", editor = "Herbert Kuchen and S. Doaitse Swierstra", series = lncs, publisher = springer, title = "Dynamic {A}ttribute {G}rammars", address = "Aachen", volume = "1140", pages = "122--136", month = sep, year = "1996", postscript = "../../ftp/fnc2/publications/plilp96.ps.gz", url = "ftp://ftp.inria.fr/INRIA/Projects/oscar/FNC-2/publications/plilp96.ps.gz" , abstract = "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 {\em Dynamic Attribute Grammars} defined on top of {\em 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)" } @TechReport{ duris96, author = "Etienne Duris and Didier Parigot and Gilles Roussel and Martin Jourdan", title = "Attribute Grammars and Folds: Generic Control Operators", type = "Rapport de recherche", number = "2957", year = "1996", month = aug, institution = "INRIA", postscript = "../../ftp/fnc2/publications/RR-2957.ps.gz", url = "ftp://ftp.inria.fr/INRIA/publication/RR/RR-2957.ps.gz", abstract = "Generic control operators, such as \emph{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." } @InProceedings{ duris96a, author = "Etienne Duris and Didier Parigot and Gilles Roussel and Martin Jourdan", title = "Grammaires Attribuées et Folds: Opérateurs de Contrôle {G}énériques", booktitle = "journées du GDR de programmation", address = "Orléans", year = "1996", postscript = "../../ftp/fnc2/publications/gdr96.ps.gz", url = "ftp://ftp.inria.fr/INRIA/Projects/oscar/FNC-2/publications/gdr96.ps.gz" , abstract = "Les opérateurs de contrôle génériques tels que \emph{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." } @TechReport{ duris97gen, author = "Etienne Duris and Didier Parigot and Gilles Roussel and Martin Jourdan", title = "Structure-directed Genericity in Functional Programming and Attribute Grammars", institution = "INRIA", year = "1997", type = "Rapport de Recherche", number = "3105", month = feb, postscript = "../../ftp/fnc2/publications/RR-3105.ps.gz", url = "ftp://ftp.inria.fr/INRIA/publication/RR/RR-3105.ps.gz", abstract = "Generic control operators, such as \emph{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 \emph{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 \emph{structure-directed genericity}, first devised for attribute grammars with descriptional composition, we show how the \emph{fold} operator with its fusion method allow to transport this concept in the area of functional programming.", keywords = "Functional programing ML vari.FP" } @InProceedings{ duris97, author = "Etienne Duris and Didier Parigot and Gilles Roussel and Martin Jourdan", address = "Dolomieu, France", booktitle = "Journ\'ees Francophones des Langages Applicatifs", title = "Grammaires attribuées et folds : opérateurs de contrôle génériques", year = "1997", month = jan, postscript = "../../ftp/fnc2/publications/jfla97.ps.gz", url = "ftp://ftp.inria.fr/INRIA/Projects/oscar/FNC-2/publications/jfla97.ps.gz" , abstract = "Les opérateurs de contrôle génériques tels que \emph{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 \emph{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 \emph{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", keywords = "functional" } @InProceedings{ correnson97, author = "Loïc Correnson and Etienne Duris and Didier Parigot and Gilles Roussel", booktitle = "Fourth International Static Analysis Symposium -- Poster Session", title = "Attribute Grammars and Functional Programming Deforestation", address = "Paris, France", month = sep, year = "1997", postscript = "../../ftp/fnc2/publications/sas97.ps.gz", url = "ftp://ftp.inria.fr/INRIA/Projects/oscar/FNC-2/publications/sas97.ps.gz" , abstract = "The functional programming community is paying increasing attention to static structure-based transformations. For example, generic control operators, such as \emph{fold}, have been introduced in functional programming to increase the power and applicability of a particular kind of static transformation, called \emph{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.", keywords = "vari.FP deforestation functional program" } @InProceedings{ correnson97-gdr, author = "Loïc Correnson and Etienne Duris and Didier Parigot and Gilles Roussel", title = "Composition Symbolique", booktitle = "journées du GDR de programmation", address = "Rennes", year = "1997", month = nov, postscript = "../../ftp/fnc2/publications/gdr97.ps.gz", url = "ftp://ftp.inria.fr/INRIA/Projects/oscar/FNC-2/publications/gdr97.ps.gz" , abstract = "" } @InProceedings{ correnson98-jfla, author = "Loïc Correnson and Etienne Duris and Didier Parigot and Gilles Roussel", title = "Composition Symbolique", booktitle = "Journées Francophones des Langages Applicatifs", address = "Come, Italie", year = "1998", month = feb, postscript = "../../ftp/fnc2/publications/jfla98.ps.gz", url = "ftp://ftp.inria.fr/INRIA/Projects/oscar/FNC-2/publications/jfla98.ps.gz" , abstract = "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." } @TechReport{ correnson98, author = "Loïc Correnson and Etienne Duris and Didier Parigot and Gilles Roussel", title = "Symbolic Composition", year = "1998", number = "3348", institution = "INRIA", month = jan, url = "ftp://ftp.inria.fr/INRIA/publication/RR/RR-3348.ps.gz", postscript = "../../ftp/fnc2/publications/RR-3348.ps.gz", abstract = "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.", urlrejected = "../../ftp/fnc2/publications/esop98rejected.txt", keywords = "vari.FP deforestation" } @InProceedings{ correnson98a, author = "Loïc Correnson and Etienne Duris and Didier Parigot and Gilles Roussel", title = "Generic Programming by Program Composition (position paper)", booktitle = "Workshop on Generic Programming", year = "1998", address = "Marstrand, Sweden", note = "conjunction with MPC'98", month = jun, url = "ftp://ftp.inria.fr/INRIA/Projects/oscar/FNC-2/publications/Correnson98a.ps.gz" , postscript = "../../ftp/fnc2/publications/Correnson98a.ps.gz", abstract = "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." } @InProceedings{ correnson98b, author = "Loïc Correnson and Etienne Duris and Didier Parigot and Gilles Roussel", booktitle = "Approches Formelles dans l'Assistance au Développement de Logiciel AFADL'98", title = "Schéma générique de développement par composition", year = "1998", postscript = "../../ftp/fnc2/publications/Correnson98b.ps.gz", url = "ftp://ftp.inria.fr/INRIA/Projects/oscar/FNC-2/publications/Correnson98b.ps.gz" , abstract = "Depuis peu, la programmation générique suscite un intérêt grandissant dans différents paradigmes de programmation. Un principe souvent utilisé pour obtenir de la généricité est d'abstraire les calculs d'un programme par rapport à leur structure de données. Cette approche permet à ces spécifications génériques d'être instanciées pour un grand nombre de structures de données voisines. De plus, le programme peut ainsi être automatiquement adapté lorsque les structures de données évoluent. La programmation polytypique, la programmation adaptive et les grammaires attribuées génériques sont des méthodes formelles de programmation génériques qui adoptent cette approche. La comparaison de ces méthodes nous a conduit à proposer un schéma commun de développement de programmes génériques. Cette méthode est basée sur deux concepts fondamentaux\,: la génération automatique de morphismes entre structures de données, et l'instanciation formelle des programmes génériques par composition, assistée par des outils de spécialisation.", address = "Poitiers - futuroscope" } @Unpublished{ correnson98c, author = "Loïc Correnson and Etienne Duris and Didier Parigot and Gilles Roussel", note = "English version of", title = "A Generic Framework for Genericity", year = "1998", postscript = "../../ftp/fnc2/publications/Correnson98c.ps.gz", url = "ftp://ftp.inria.fr/INRIA/Projects/oscar/FNC-2/publications/Correnson98c.ps.gz" , abstract = "Recently, generic programming becomes of a major interest in several programming paradigms. A recurrent idea to achieve genericity is to specify algorithms on their convenient data structure, and to allow these specifications to be instantiated onto a large number of neighboring data structures. Polytypic programming, shapely types and generic attribute grammars are generic programming methods related to this approach. A framework for generic programming is proposed to embed these methods. It consists in tools for automatic generation of morphisms between data structures, and for program composition. Thanks to this compositional approach, the complete specialization of generic programs could be advantageously delegated to a general and powerful mechanism of ``symbolic composition'', which performs deforestation and partial evaluation." } @InProceedings{ jourdan90bb, author = {Martin Jourdan and Carole {Le Bellec} and Didier Parigot}, address = {Paris}, booktitle = {Attribute Grammars and their Applications (WAGA)}, editor = {Pierre Deransart and Martin Jourdan}, pages = {222-237}, publisher = {Springer-Verlag}, series = lncs, title = {The {O}lga {A}ttribute {G}rammar {D}escription {L}anguage: {D}esign, {I}mplementation and {E}valuation}, volume = 461, year = 1990, url = {ftp://ftp.inria.fr/INRIA/Projects/oscar/FNC-2/publications/olga-t.ps.gz} , abstract = {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.} } @InCollection{ jourdan91aa, author = {Martin Jourdan and Didier Parigot}, address = {Prague}, booktitle = {Attribute Grammars, Applications and Systems}, editor = {Henk Alblas and Bo\u{r}ivoj Melichar}, pages = {485-504}, publisher = {Springer-Verlag}, series = lncs, title = {{I}nternals and {E}xternals of the {FNC-2} {A}ttribute {G}rammar {S}ystem}, volume = {545}, year = 1991, url = {ftp://ftp.inria.fr/INRIA/Projects/oscar/FNC-2/publications/fnc2-t.ps.gz} , abstract = {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.} } @InProceedings{ jourdan9191, author = {Martin Jourdan}, editor = "Henk Alblas and Bo{\u{r}}ivoj Melichar", booktitle = "Attribute Grammars, Applications and Systems", series = "Lecture Notes in Computer Science", volume = "545", pages = {234-255}, title = {{A} {S}urvey of {P}arallel {A}ttribute {E}valuation {M}ethods}, publisher = "Springer-Verlag", address = "New York--Heidelberg--Berlin", month = jun, year = "1991", keywords = "class eval", note = "Prague", url = {ftp://ftp.inria.fr/INRIA/Projects/oscar/FNC-2/publications/parev-t.ps.gz} } @TechReport{ correnson97a, author = "Loïc Correnson and Etienne Duris and Didier Parigot and Gilles Roussel", title = "Symbolic Composition", year = "1997", type = "Draft", institution = "INRIA", month = jul, note = "{\tt ftp://ftp.inria.fr/INRIA/Projects/oscar/FNC-2/publications/SC97.ps.gz}" , url = "ftp://ftp.inria.fr/INRIA/Projects/oscar/FNC-2/publications/SC97.ps.gz" , abstract = "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 \emph{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 \emph{fold}, \emph{catamorphisms}, and \emph{hylomorphisms}. In the attribute grammar community there also exists a powerful and well-known deforestation-like transformation called \emph{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 \emph{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." } @TechReport{ correnson97b, author = "Loïc Correnson and Etienne Duris and Didier Parigot and Gilles Roussel", title = "Symbolic Composition", year = "1997", type = "Draft", institution = "INRIA", month = oct, note = "{\tt ftp://ftp.inria.fr/INRIA/Projects/oscar/FNC-2/publications/SC97a.ps.gz}" , url = "ftp://ftp.inria.fr/INRIA/Projects/oscar/FNC-2/publications/SC97a.ps.gz" , abstract = "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." }