Le programme scientifique de

Didier Parigot

7 avril 1997

Note préliminaire : Pour l’élaboration de mon programme scientifique, l’article Strategic Directions for Research on Programming Languages [HNP96] du groupe de travail de l’acm a été très utile et instructif. Personnellement, je retiens la nécessité d’un effort d’unification des concepts introduits dans les divers paradigmes de programmation. J’ai conçu ce programme comme un outil de travail pour mon équipe. J’ai donc énuméré l’ensemble des sujets de recherche possibles mais je prie le lecteur de se référer au résumé où j’indique plus précisément mes sujets de recherches prioritaires.

1 Introduction

Pour être compréhensible, la lecture de ce document nécessite celle de mes travaux de recherche. En effet, mon programme scientifique est à moyen terme, un prolongement naturel d’un large sous-ensemble de ces travaux. Pour une meilleure cohérence j’ai regroupé mon programme scientifique en six axes mais il existe bien sûr de fortes relations et interconnexions entre ces derniers ;

– Les grammaires attribuées;

– Les grammaires attribuées et la programmation fonctionnelle;

– Les grammaires attribuées et l’interprétation abstraite;

– Les grammaires attribuées et de la sémantique naturelle;

– Les grammaires attribuées et la programmation orientée-objet;

– Les grammaires attribuées : applications et utilisations;

Le premier axe est très souvent une évolution, adaptation ou reformulation des travaux spécifiques aux grammaires attribuées dans le but de répondre aux objectifs des autres axes de recherche. Par exemple, la méta-composition (composition descriptionnelle) devra être adaptée suivant l’évolution et l’avancement de nos travaux sur la comparaison de cette technique avec les techniques de déforestation de la programmation fonctionnelle.

Les axes suivants ont comme double objectif de montrer que d’une part, les travaux de recherche sur les grammaires attribuées peuvent être étendus ou utilisés dans d’autres domaines de recherche et d’autre part, le paradigme de programmation par grammaire attribuée doit être forcément intégré et immergé à d’autre paradigme pour prendre toute sa valeur. Les résultats sur les grammaires attribuées (analyses statiques) sont d’après nos résultats [PRJD96] plus généraux que ne pouvait le faire croire l’historique des GA. Nos travaux sur les grammaires attribuées dynamiques en sont une première démonstration. Le paradigme (langage de programmation) des grammaires attribuées ne se suffit pas à lui-même pour en faire un langage de programmation complet. Il doit s’appuyer sur les divers modèles de calcul proposés par d’autres paradigmes de programmation, sans pour autant altérer le caractère déclaratif des grammaires attribuées. Les GA sont indépendantes du modèle de calcul choisi et ce dernier ne doit pas influencer la forme externe, le langage de spécification, utilisé pour décrire des GA. C’est essentiellement pour cette raison que je rapproche souvent les travaux théoriques sur les grammaires attribuées aux travaux sur l’interprétation abstraite (cf. la section 4). C’est aussi pour cela que, dans la conception de notre système Fnc-2, le langage d’implantation n’est absolument pas figé (plusieurs traducteurs de notre langage d’entrée Olga vers différents langages d’implantation). Actuellement je pousse ce raisonemment encore plus loin, dans le sens que même pour le langage d’entrée, il faudrait avoir cette même indépendance.

2 Les grammaires attribuées

2.1 Les grammaires attribuées dynamiques

L’intérêt des GA dynamiques [PDRJ95, PRJD96] est de redonner aux GA leur expressivité intrinsèque. De plus, elles nous permettent d’envisager de nouveaux axes de recherche en comparant nos techniques d’analyse à celles qui ont été développées dans des formalismes de même expressivité. Dans le contexte pur des GA, cette nouvelle vision n’a été approfondie que dans le cadre de la génération d’évaluateurs classiques. Il serait donc intéressant d’étudier les conséquences pour les versions incrémentale et parallèle des évaluateurs.

De plus, il faudra définir formellement la sémantique des GA dynamiques, mais un choix judicieux du formalisme pour décrire cette sémantique reste à définir. Nous avons une idée assez précise et claire de cette sémantique mais malheureusement en terme de grammaire attribuée (valeur d’attribut) qui ne me semble pas être la meilleure façon de présenter cette dernière. Je vois deux voies possibles, celle introduite dans [vdM94] par schémas récursifs primitif étendus, ou encore suivre l’approche de [GK95].

Pour les GA dynamiques, il reste à montrer que l’ajout de valeurs fonctionnelles (ordre supérieur) n’est nullement incompatible avec les analyses statiques de la théorie des GA. En effet, ceci est le dernier point qui nous reste à traiter pour atteindre la puissance d’expression d’un langage fonctionnel classique. Il faut bien préciser que dans ce cadre, le modèle de calcul utilisé (le langage d’implantation des évaluateurs d’attributs) doit supporter l’ordre supérieur (voir notre approche dans [Le 95]).

2.2 La composition descriptionnelle ou méta-composition

Dans la présentation des travaux effectués, j’ai montré le rôle important que pouvait avoir la méta-composition (composition symbolique). Nous devons étudier plus précisément les diverses améliorations, extensions ou reformulations de cette technique que nos travaux sur les GA dynamiques, sur la programmation fonctionnelle et la programmation orientée-objet vont induire ou provoquer. Les principaux points à étudier sont les suivants :

– Définition de la méta-composition sur des types algébriques (polymorphes) et en terme de théorie des catégories;

– Unification de la notion de production conditionnelle utilisée pour les GA dynamiques et d’expressions conditionnelles;

– Utilisation de la méta-composition en terme d’évaluation partielle (sur un terme fini);

– Utilisation de la méta-composition sur des termes (fonctions) d’ordre supérieur.

Le premier point est une reformulation de la définition de la méta-composition pour permettre de mieux faire comprendre ou comparer les mécanismes de cette transformation, avec les autres formalismes introduit dans la communauté fonctionnelle. En effet, ces travaux de recherche (dans la communauté fonctionnelle) utilisent fortement cette formulation en terme de programmation algébrique (théorie des Catégories) comme par exemple les travaux de Erik Meijer [MFP91] ou [Mee95]. Il serait donc possible de donner le théorème de base de la méta-composition (classe des GA clos par méta-composition) en terme de théorème for free [Wad89].

Le deuxième point permettra de simplifier l’algorithme de méta-composition du moins dans sa présentation (voir la thèse de Gilles Roussel). En effet, l’introduction des productions conditionnelles des GA dynamiques permet de définir une forme normale des GA sans expression conditionnelle dans les règles sémantiques et cela simplifie beaucoup l’algorithme de méta-composition [Rou94b].

Pour le troisième point les mécanismes généraux de la méta-composition peuvent être utilisés dans le cas très particulier où le terme (expression de contruction d’arbre ou de structure) est connu statiquement, de taille fini. En effet, lorsque un bout de structure (d’arbre) est visible à la compilation, il serait possible d’appliquer une forme spécialisée de la méta-composition qui, dans ce cas particulier, serait une évaluation partielle.

2.3 Coupleur statique

La notion de coupleur statique [RPJ94] (voir les travaux de recherche effectués) semble la forme de méta-composition qui se rapproche le plus des techniques employées dans la communauté fonctionnelle (notion de foncteur). Il serait donc intéressant d’étudier plus précisément ce rapprochement. Grâce à la propriété de compilation séparée du coupleur statique, notre approche serait un moyen de proposer une librairie de fonction déjà optimisées comme dans l’approche décrite dans [JJ97].

2.4 Coupleur dynamique

La notion de coupleur dynamique [RPJ94] est une forme de déforestation dynamique lors de l’évaluation (à l’exécution). Nous n’avons pas eu encore le temps d’étudier plus précisément cette possibilité. Il reste beaucoup d’inconnues sur cette approche en terme l’efficacité en temps et en place mémoire même si cette dernière semble assez simple dans sa réalisation (implantation).

2.5 La généricité structurelle dans les grammaires attribuées: le couplage

L’un de mes objectifs à court terme est de montrer que la notion de généricité structurelle [DPRJ97a] peut être utilisée hors du contexte strict des grammaires attribuées (voir la section 3.1 et 6). Les travaux de recherche sur le mécanisme de couplage [LJPR93, Le 93, Cor96] sont les suivants:

– formulation simplifiée de la notion de syntaxe abstraite attribuée asx [JP]; (type algébrique extensible);

– formulation en terme de morphisme d’algèbre pour exprimer formellement l’idée de la forme normale d’une fonction de couplage (algèbre initiale);

– étudier grâce aux grammaires attribuées dynamiques des formes plus complexe de fonction de couplage);

Le premier point suit notre volonté de simplification des notions introduites (record, constructeur, attributs etc). Pour deuxième point, je suis convaincu qu’une formulation plus générale de notre notion de couplage de syntaxe abstraite attribuée sera un atout pour une meilleure diffusion de nos résultats. Il faudra certainement poursuivre sur notre idée de forme normale [Cor96] en relation avec les travaux sur les shapely types and shape polymorphism [JC94], Polytypic programming [JJ97], et aussi notre notion d’extraction de gène décrite dans [Rou94b]. En effet, le couplage de ces deux notions permettra d’appliquer cette notion de généricité structurelle à des programmes déjà écrits.

Enfin, il sera certainement nécessaire d’étudier des formes plus complexes de couplage, tout en respectant la contrainte qu’elles soient toujours exprimable en terme de grammaire attribuée.

Dans le cadre du projet Compare, lors de la réalisation du méta-générateur de code Pagode, j’ai pu m’apercevoir que j’avais là, un exemple très réaliste de taille des spécifications de cette notion de généricité structurelle. Sans entrer dans les détails, quasiment toutes les grammaires attribuées développées dans ce cadre peuvent être considérées comme des grammaires attribuées de couplage. Donc elles auraient pu être générées automatiquement à partir d’une relation de couplage. J’ai retrouvé quasiment la même approche dans [Con96] pour le même cadre “générateur de compilateur”, mais ils utilisent le mécanisme d’évaluation partielle.

2.5.1 Modularité dans les grammaires attribuées

Références : [DC90, LJ89]

Au cours de la thèse de Gilles Roussel nous avons développée la notion de grammaires attribuées ouvertes. Il faudra certainement poursuivre ce travail en relation avec les travaux de Kastens [KW94].

2.6 Optimisation mémoire

Depuis nos travaux sur l’optimisation mémoire [JP90b] d’autre travaux ont vu le jour, en particulier la notion de ”binding” [SV] ou les travaux de Engelfriet [EdJ90]. J’aimerais faire une étude de synthèse sur ces différentes approches car je suis assez persuadé quelles sont complémentaires. De plus, j’aimerais mieux comprendre les implications de cette analyse des durées de vie des attributs (variables) dans le monde fonctionnelle [Ses89], comme dans [KS86b, KS86a] . En effet, les GA dynamiques permettent d’appliquer ces techniques à un plus large sous-ensemble de programme fonctionnel. Le rôle de notre transformation FNC-l-ordonnée est la pièce maîtresse de cette analyse (voir aussi la section 2.9).

2.7 Évaluation incrémentale

Toujours dans le rapprochement grammaire attribuée et programmation fonctionnelle, j’aimerais étudier l’utilisation des techniques d’évaluation incrémentale pour les attributs et je sais qu’il existe des travaux dans ce sens [EMSR97] avec le langage AML (notation grammaire attribuée pour ML) ou les auteurs utilisent quasiment les mêmes techniques d’évaluation incrémentale que les nôtres [Fil86, Par88] (basées sur la classe Doublement Non-Circulaire). Dans le domaine de la compilation, je pense que cette technique a très vite trouvé ces limites (manipulation d’objets trop complexes comme les tables de symboles) mais elle pourra trouver son utilité dans bien d’autres domaines de l’informatique (voir par exemple [DCB94]).

2.8 Évaluation parallèle

Références : [Jou]

Avec la thèse de Bruno Marmol [Mar94, JMP94], nous avons vraiment expérimenté nos techniques d’évaluation parallèle sur différents types de machines. J’aimerais utiliser cette approche non plus dans le sens d’une parallélisation implicite, mais comme moyen de vérification d’une approche de parallélisation explicite : fournir à l’utilisateur (l’écrivain) un moyen de décrire des applications parallèles. De plus, dans [SCG95], l’exemple de base et l’abstraction employée pour leurs analyses de programmes fonctionnels (graphe de dépendance) montre assez clairement qu’il doit exister de grandes similitudes entre les méthodes de parallélisation implicite de programmes fonctionnels et celles introduites pour les grammaires attribuées. Sur l’exemple de base de cet article, notre transformation FNC- l-ordonnée effectue une transformation du programme fonctionnel qui semble être l’information recherchée par leurs analyses [SCG95] (voir aussi la section 2.9).

2.9 Transformation de grammaires attribuées

Dans la théorie des grammaires attribuées, il existe donc toute une terminologie de classes de grammaires attribuées (Non-circulaire, Fortement Noncirculaire, Doublement Non-circulaire, l-ordonnée, etc). J’aimerais étudier si cette classification à un sens pour la programmation fonctionnelle en terme de système de réécriture, surtout si on utilise le résultat bien connu de [CFZ82] par schémas récursifs primitifs et l’extension décrite dans [vdM94] avec des règles de réécriture conditionnelles. En effet, une grammaire attribuée peut s’exprimée sous certaines conditions en un système de règles réécriture mais l’introduction des grammaires attribuée dynamiques éliminent l’une des contraintes les plus contraignantes (règles strictement décroissantes). En d’autre terme, il serait possible d’exprimer les transformations de grammaires attribuées en terme de transformation de système de réécriture, comme la transformation FNC-L ordonnées décrite dans ma thèse [Par88] ou l’élimination des règles de copie décrite par Gilles Roussel [Rou94b]. Il est important de placer cette étude dans le contexte de nos travaux de la section 3.1. J’ai discuté de cela avec Robert Strandh qui travaille sur un langage équationnel “The Equation Compiler” et sa réaction a été relativement positive.

2.10 Les grammaires attribuées et les transducteurs d’arbre

Je regarde également les travaux sur les transducteurs d’arbres [KV94a, KV94b, MV95] car j’aimerais préciser dans ce contexte l’impact de notre notion de grammaire attribuée dynamique. Je suis en contact avec Heiko Vogler pour éventuellement étudier plus précisément cette relation d’autant plus qu’ils ont défini tout un ensemble de transformations [MV95] qui peuvent avoir un sens pour nous.

2.11 Les grammaires attribuées et les transformations d’arbre attribués

Nous avons travaillé sur ce thème, mais je dois l’avouer, depuis la thèse d’Azis Souah [Sou90], nous avons un peu délaissé ce thème.

3 Les grammaires attribuées et la programmation fonctionnelle

3.1 déforestation et la composition descriptionnelle

Dans [Dur94, DPJ95, DPRJ96, DPRJ97b, DPRJ97a] nous avons commencé à montrer la forte relation qui pouvait exister entre les mécanismes de déforestation introduits dans la programmation fonctionnelle [Wad88] et la composition descriptionnelle [GG84]. Il existe dans la communauté fonctionnelle plusieurs approches pour ce même problème ([KR93] pour ADL,[OHIT97] pour HYLO,

[MH95] pour Bananas), mais elles ont toutes en commun, le même principe de transformation locale, sur chaque constructeur. Ainsi ces diverses approches définissent pour un programme fonctionnel une forme intermédiaire très similaire où sur laquelle divers algorithmes de transformation (déforestation) sont appliqués. Je suis de plus en plus convaincu que cette forme intermédiaire se rapproche fortement d’une spécification par grammaire attribuée abstraite (indépendante du modèle de calcul choisi).

Ainsi nos travaux futurs sur cette comparaison vont nous permettre de valoriser et de démontrer les avantages de l’approche (de programmation ou d’analyse) par grammaire attribuée sur les points essentiels suivants :

– la notation par grammaire attribuée contient par définition la propriété de programmation structurelle nécessaire pour effectuer ce type transformation de programme (voir les introductions des papiers) ;

– notre technique de transformation (élimination des structures intermédiaires) est indépendante de toute sémantique opérationnelle. La métacomposition n’utilise pas l’ordre d’évaluation des attributs alors que les techniques de fusion sont essentiellement basées sur la connaissance préalable du schéma de calcul (notion de foncteur).

– la puissance d’expression induite par la possibilité d’avoir des programmes d’ordre supérieur est gênante pour ce type de transformation (voir l’exemple de l’inversion du liste [DPRJ97b]). En d’autres termes, dans l’approche par grammaire attribuée, l’ordre supérieur est très avantageusement remplacé par l’utilisation des attributs hérités.

– l’utilisation de cette technique pour la généricité structurelle, dans la communauté des grammaires attribuées, peut facilement être transférée vers la programmation fonctionnelle.

– si la propriété de programmation structurelle est une bonne propriété pour effectuer ce type de transformation (déforestation), alors elle peut aussi être une bonne propriété pour la programmation. Ainsi nous pensons que la description par grammaire attribuée offre à l’écrivain toutes les avantages de cette programmation structurelle.

Je ne suis pas le seuls à penser à ce dernier point, jcela. En effet, dans l’article [She94] de présentation générale de Tim Sheard, qui n’est pas de la communauté des grammaires attribuées, il est écrit que la programmation par grammaire attribuée est plus claire, concise et maintenable que la programmation fonctionnelle. On peut aussi faire référence aux polytypic programmning de Johan Jeuring [JJ96] surtout si l’on s’appuie sur le fait qu’une grammaire attribuée peut être transformée en un catamorphisme [FJMM91]. Notre notion de grammaire attribuée dynamique permettra d’étendre encore plus cette comparaison (aux hylomorphismes)

Les divers travaux que nous devons poursuivre sont les suivants :

– décrire formellement la transformation d’un programme fonctionnel en une grammaire attribuée. Cette transformation s’appuie bien évidement sur les travaux du contexte fonctionnel comme [OHIT97], mais utilise quasiment les même principes de base que la transformation de la sémantique dénotationnelle vers les grammaires attribuées [Gan80, Lei96] et à l’aide les extensions introduites par les grammaires attribuées dynamiques (cf les sections 2.1 et 3.5). Cette transformation utilise fortement les informations de type ; par exemple, dans [OHIT97], cette transformation contient un mécanisme d’inférence de type ;

– immerger plus fortement notre mécanisme de composition descriptionnelle dans le monde fonctionnel ;

– avec les travaux décrits dans la section 2.2.

Après cela, il sera certainement utile d’insérer ce mécanisme dans une chaîne complète de compilation de programmes fonctionnels. Mais nous préférons, dans un premier temps, faire cette étude indépendament d’un langage fonctionnel donné pour garder le plus possible toute la généralité (abstraction) de notre approche. En effet, lors de l’instantiation de ce mécanisme pour un compilateur donné, il sera certainement nécessaire d’effectuer certaines adaptations en fonction des particularités du langage d’entrée. De plus, nos travaux sur l’optimisation mémoire (cf la section 2.6), mise à jour destructives (cf la section 3.2), évaluation indulgente (cf la section 3.3) et enfin sur l’évaluation parallèle (cf la section 2.8) pourront être aussi incorporés, si la forme intermédiaire, “les grammaires attribuées” conserve toujours les mêmes avantages.

Pour nous, l’objectif de ces travaux n’est pas exclusivement motivé par l’optimisation (élimination des structures intermédiaires) de programme, mais surtout par son utilisation dans le mécanisme de généricité structurelle avec notre notion de couplage (cf la section 2.5). Le polymorphisme est souvent décrit comme un moyen de favoriser la réutilisation du code, nous pensons que la généricité structurelle permettra une plus grande réutilisation. En effet le mécanisme de polymorphisme est limité dans le sens qu’il ne permet pas de s’affranchir de la structure. Elle reste figée, d’une utilisation à l’autre. Ce ne sont que les feuilles de la structure (le type de base) qui sont les paramètres de la réutilisation. D’après nos premières études, l’approche décrite dans [JJ97] semble proche de notre notion de coupleur statique (cf la section 2.3) décrite dans [RPJ94].

3.2 Analyse statique pour la mise à jour destructive

Dans [Dur94], nous avons étudié le problème de la mise à jour destructive en nous plaçant résolument dans le cadre des grammaires attribuées. J’espère qu’avec Étienne Duris nous pourrons poursuivre ce travail et pouvoir élargir notre champs d’investigation avec l’approche par grammaire attribuée dynamique et si nous arrivons à trouver le bon cadre, “chaîne de compilation fonctionnelle” pour instancier ces techniques. Ce travail doit être considéré comme une contribution à nos travaux de la section 4 sur l’analyse de flot de données.

3.3 Évaluation indulgente et analyse statique dans les GA

Références : [FK93],[vdBFAvG93],[KS86b] D’après l’étude de Guy Tramblay

[Tre94, TG95], l’évaluation indulgente (une forme particulière de l’évaluation paresseuse) semble être une forme très courante en pratique. En effet, il montre que quasiment, tous les programmes décrits comme étant paresseuses dans la litérature, ne sont en rèalité que des programmes indulgents. Il est important de faire le parallèle avec nos travaux [AP94] sur la compilation efficace de Typol que nous avons poursuivi avec Isabelle Attali. En effet, cela montre que les grammaires attribuées sont une forme abstraite pour deux modèles de programmation (de calcul) bien différent (d’un point de vue externe). Les travaux sur l’évaluation indulgente (sur le Langage Id^{1} [SG95] ou encore Hp^{2} de [SCG95]) sont souvent liés à l’évaluation parallèle. Il serait donc intéressant de relier ici nos travaux sur l’évaluation parallèle d’attributs (cf la section 2.8) et nos algorithmes de transformation de grammaires attribuées (cf la section 2.9).

L’autre intérêt de notre approche est de fournir à l’utilisateur une puissance d’expression comparable à celle que procure le style de programmation paresseux, sans pour autant avoir tous les désavantages de l’efficacité du code produits, surtout en terme d’espace mémoire. En effet, nos premières expériences, en utilisant le langage Haskell ont bien mis en évidence ce gain d’espace mémoire. Il est important de remarquer que nous avons les mêmes motivations, en terme d’occupation mémoire, que pour la compilation efficace de Typol (voir la section 5). Mais, pour faire des comparaisons qui ont un sens, il est nécessaire (hélas) d’insérer cette analyse dans une chaîne complète d’un compilateur fonctionnel. En effet, lors de ces expériences (même pour la compilation efficace de Typol [AP94]), il est très difficile de valider correctement le gain de notre approche, d’autant plus lorsque le modèle de calcul change. Il est nécessaire de se ramener toujours au même modèle d’exécution et de comparer la forme non optimisée à la forme optimisée dans ce même modèle de calcul.

3.4 Typage et inférence de type : notation grammaire attribuée au-dessus de ML

Références : [Wal89]

Depuis quelque temps, il existe des travaux [Rus92, EMR93, FK93, Fro94, EMSR97] de recherche qui introduisent la notation des grammaires attribuées dans la famille des langages ML. Ces travaux sont basés essentiellement sur l’article de Johnsson [Joh87]. L’approche que nous avons prise dans [Le 95] arrive rapidement à ses limites.

À ma connaissance actuelle, le mécanisme d’inférence de type sur de telle spécification est résolument simplifié : le type des attributs est donné explicitement. J’aimerais donc étudier plus précisément ce problème d’inférence de type sur une spécification par grammaire attribuée. Pour les travaux de la section 3.1, il est important de mieux comprendre ce mécanisme d’inférence sur de telles spécifications. Tout ceci nous permettra de proposer un langage de description de grammaire attribuée de la famille des langages ML.

1. langage fonctionnel paresseux

2. Haskell parallèle et paresseux

Mais l’intérêt de ces travaux est d’expliciter plus clairement les divers problèmes de typages que j’ai pu rencontrer lors de mes travaux d’intégration de Fnc-2 dans Centaur (inclusion de phyla) et dans la plate-forme Cosy (le projet Compare) avec le langage de description de structure fSDL [Con94].

3.5 Les grammaires attribuées et la sémantique dénotationnelle

Références : [CM86]

Lors du stage de [Lei96], nous avons juste vérifié que l’introduction des grammaires attribuées dynamiques était la bonne approche pour cette transformation [Gan80]. J’aimerais pousser plus loin cette étude, d’une part en utilisant nos travaux de la section 3.1 pour préciser formellement la transformation et surtout regarder si les mécanismes de preuves de la sémantique dénotationnelle s’expriment aussi naturellement sur la spécification en grammaire attribuée résultante.

4 Les grammaires attribuées et l’interprétation abstraite

Références : [BM94]

Depuis fort longtemps, je suis convaincu qu’il existe une relation entre les grammaires attribuées et l’interprétation abstraite. Dans la littérature, seul Mads Rosendahl [Ros90, Ros91, Ros92] a vraiment étudié ce rapprochement. L’une des raisons qui me pousse à dire cela, et que pour moi les grammaires attribuées n’ont pas, à priori, un modèle de calcul spécifique. Bien sur, les développements autour des grammaires attribuées ont proposés des modèles de calcul comme, par exemple, par automate (séquence de visite) ou par graphe de dépendance. Au cours du développement de Fnc-2 je me suis toujours résolument placé dans l’approche où le modèle de calcul pouvait être choisi parmi des modèles autres que ceux proposés initialement par les travaux sur les grammaires attribuées, comme le modèle de calcul fonctionnel et même le modèle logique.

4.1 Analyse de flot de données

Références : [Son87]

Nos travaux sur l’analyse de flot de grammaire [JP90a] (grammar flow) et de Reinhard Wilhelm [MW91], permettent de généraliser les analyses statique de la théorie des grammaires attribuées. Les grammaires attribuées dynamiques, qui permettent de spécifier des grammaires attribuées circulaires, seront, si l’on se réfère à l’article [SEFR89], un bon moyen pour spécifier des points fixes. En effet, les grammaires attribuées sont un moyen naturel pour décrire des problèmes d’analyse de flot de données (AFD) mais ces grammaires attribuées sont généralement circulaires. Dans [SEFR89] les auteurs transforment ces grammaires attribuées circulaires en des GA non-circulaires.

De plus dans [Ruf97], nos techniques de partionnement (décomposition de la grammaire en classe d’équivalence) sont comparées (équivalentes) à leurs techniques de partionnement utilisant l’information de types pour des programmes impératifs, et dans [SH94] les auteurs transposent cette technique de flot de grammaires pour l’analyse de programmes impératifs.

Donc, étant donné notre expérience, il me semble possible pour une souscatégorie de problèmes d’analyse statique (flot de données), de définir enfin un vrai outil (langage) pour décrire et implanter diverses analyses. J’aimerais aussi utiliser dans ce contexte notre opérateur de généricité structurelle. Je noterais juste que Uwe Assmann a participé à cette idée d’utilisation de notre généricité structurelle pour les techniques d’analyse de flot de données, lors de son passage chez nous. J’espère pourvoir poursuivre notre collaboration d’autant plus que son dernier “draft” [Asm97] est proche de nos motivations sur la notion de généricité structurelle.

5 Les grammaires attribuées et la sémantique naturelle

Références : [Tav88]

Avec Isabelle Attali nous n’avons pas encore étudié plus précisément les avantages de l’approche par grammaires attribuées dynamiques dans le contexte de la traduction de la sémantique naturelle (Typol) vers des grammaires attribuées. Dans [Pet95], Mikael Pettersson prend l’optique d’une programmation fonctionnelle pour implanter son langage de programmation rml pour la sémantique naturelle avec du non-déterminisme, mais il compile dans un langage fonctionnel strict (voir la thèse d’habilitation d’Isabelle Attali [Att96]). Il me semble donc qu’en rajoutant du non-déterminisme aux grammaires attribuées nous pourrions fournir à la sémantique naturelle une alternative intéressante avec en plus la possibilité du choix du langage d’implantation (de la famille ML). En d’autres termes, j’aimerais faire la synthèse de nos travaux sur les GA dynamiques, de ceux d’Isabelle Attali sur l’évaluation fonctionnelle de Typol [AC90] et enfin les travaux de Mikael Pettersson pour arriver à définir la plus large sous-classe de la sémantique naturelle exécutable sur le modèle de calcul fonctionnel. Nos algorithmes de transformation (cf la section 2.9) jouent encore ici un grand rôle, comme dans [Paa94].

6 Les grammaires attribuées et la programmation orientée-objet

Dans les grammaires attribuées il existe un ensemble [KP87, LSK90, SV90, TCl90, Hed91, Kos91, Gro92, GK93] de travaux portant sur ce thème (orientéeobjet), mais l’approche que je souhaite suivre est relativement différente dans le sens que je recherche une vraie intégration de la notation grammaire attribuée dans la programmation orientée-objet. Je vais énumérer un ensemble d’arguments qui, depuis quelques temps, me pousse fortement à envisager de concevoir une forme externe (langage d’entrée) aux grammaires attribuées, la plus proche possible d’une écriture par programmation orientée-objet (en particulier proche de langage java ).

Au cours du développement de Fnc-2, écriture de grammaire attribuée de taille raisonnable, je me suis rendu-compte que la programmation par grammaire attribuée est une forme de programmation par objets (par attributs) graçe à ses qualités suivantes :

– de programmation structurée (locale à chaque constructeur) ;

– et de séparation entre le contrôle (le filtrage sur la structure) et la définition du calcul (les règles sémantiques).

Dans [JPJ^{+}90], nous avons défendu cette idée de développement incrémental, par touches successives (attributs) qui permet de faire évoluer facilement une application spécifiée en grammaire attribuée.

Avant de poursuivre, je vais énumérer les avantages d’une génération de code (pour Fnc-2) vers le langage java par rapport à une génération en C ou à C++:

– Les avantages liés au langage lui-même :

– un glaneur de cellule ;

– un traitement des exceptions ;

– Les avantages liés à la programmation orientée-objet : cela va nous permettre de valider notre point de vue sur la programmation par attributs (grammaire attribuée) dans un cadre peut-être plus familié à nos concepts.

– Les avantages liées aux outils pour la parallélisation, indépendants de la machine : je pense que dans ce contexte, nos travaux sur l’évaluation parallèle seront largement facilités et trouveront peut-être un meilleur écho, moyen de diffusion.

– Les avantages liés à la grande facilité pour la spécification d’interfaces graphiques ; nos techniques d’évaluation incrémentale trouveront certainement des champs d’application. Je ne citerais que le travail que nous avons déjà effectué avec Christophe Roudet [Rou94a] sur PPML en utilisant nos technique d’évaluation incrémentale. En particulier, notre langage Ppat trouvera peut être ici un champ d’application dans le “pretty pritting” des langages comme HTML.

– Les avantages liés aux très grand degré de portabilité, accentué par l’ouverture sur l’internet ;

– Les avantages liés à la très forte visibilité ; cette forte visibilité sera, pour nous le meilleur moyen pour rechercher d’autres applications aux grammaires attribuées. En effet, les grammaires attribuées sont restées beaucoup trop confinées au domaine d’application de la compilation.

Pour conclure, je pense que les arguments de l’approche de Philip Wadler dans [OW97] sont certainement très proche des miens, surtout dans le sens qu’il est nécessaire pour une meilleure diffusions de nos idées et concepts de les incorporer dans des langages de grandes audience comme java.

L’un de nos plus importants arguments, est que notre notion de généricité structurelle (cf la section 2.5) trouvera dans la programmation orientée-objet, un autre champ d’application. J’ai commencé à investiguer dans ce sens, et je suis de plus en plus convaincu que cette voie de recherche est très porteuse. En effet, je ne suis rendu compte que cette notion de réutilisation (Adaptative Programming [Lie92, LL95], Reflection [CM96]) était une approche très nouvelle dans le monde des objets. En effet la réutilisation par le mécanisme d’héritage, à travers la hiérarchie des classes, est parfois insuffisante.

L’une des premières étapes que l’on envisage, sera de définir une réelle intégration (langage) de la notation par grammaire attribuée au-dessus d’un langage objet avec la même approche que pizza [OW97]. Nous avons démomé ce langage chocolat. Actuellement, avec Gilles Roussel et l’équipe de Reinhard Wilhelm nous avons soumis une pré-proposition pour un projet visage : Visualization and Animation Generation for Educational Sofware. Ce projet propose de construire un support Multimédia pour l’enseignement d’un cours sur les langages de programmation et compilation, basé essentiellement sur le livre [WM94, WM95] de Reinhard Wilhelm. Ainsi l’une des premières applications de chocolat sera d’être le prototype (générateur d’évaluateur d’attributs) pour ce projet visage.

7 Utilisations et applications

Après la participation à un gros projet Esprit Compare, il était vital pour moi, de réactiver ma recherche sur les grammaires attribuées avec comme objectif principal de trouver d’autres champs d’applications aux GA que son domaine initial “la compilation”. À la fin de Compare il était nécessaire de ne pas rechercher tout de suite un même type de financement sur le même type d’application.

7.1 Utilisation et valorisation du système de grammaire attribuée : Fnc-2

Actuellement les perspectives d’utilisation à court terme de notre système sont les suivantes :

– Nous utiliserons Fnc-2 en interne pour nos futurs travaux ;

– Martin Jourdan qui a quitté l’INRIA pour aller dans l’industrie pourra certainement trouver une application d’Fnc-2 intéressante chez “Métaware”, son entreprise,en complément de leurs outils de transformation de programme;

– Il serait dommage de ne pas valoriser le travail sur l’adaptation de Fnc-2 à Cosymais je ne souhaite pas trop investir dans cette voie ; – Actuellement Fnc-2 est utilisé dansl’équipe de Hubert Garavel à l’In-

rialpes pour décrire un “frond-end” pour le langage E-lotos ;

– Il est vrai que le projet Compare ne m’a pas assez laissé de temps pour poursuivre notre collaboration avec Isabelle Attali autour de Centaur et Fnc-2. Nos deux projets (croap et l’axe Compilation de projet ChLoE) ont participé à de gros projets esprits (GIPE pour croap et Compare pour nous) et la phase de transition (fin de gros contrats) n’a pas été propice à notre collaborations. En effet les deux systèmes ont évolués vers des directions un peu différentes. Je reste persuadé que l’on trouvera dans l’avenir de futures collaborations, par exemple sur l’utilisation de nos outils de transformation de programme (déforestation) si je me réfère à un sujet de stage de DEA proposé cette année par le projet croap.

7.2 Quelques autres applications des grammaires attribuées

Je ne ferai ici que d’énumérer un ensemble d’applications pour les grammaires attribuées que j’ai un peu étudié dans le but de savoir si notre approche de grammaire attribuée dynamique apporterait un plus aux approches initiales.

– Les grammaires attribuées et le langage naturel [FS90] ;

– Les grammaires attribuées et la mise en page de documents ([FZA89] tex) ([AW94] SGML) ;

– Les grammaires attribuées et les protocoles de communication [And95, AS96, AS95] ;

– Les grammaires attribuées et la musique [DCB94] ;

8 Diffusion des résultats et relations internationales

Je poursuivrai mon effort de publicité sur le WEB, en particulier sur les points suivants :

– Maintenance de notre bibliographie sur les grammaires attribuées, en essayant le plus possible d’ajouter les résumés (abstracts) et les adresses url pour les rapports de recherche;

– Page d’accueil sur la recherche sur les Grammaires Attribuées. En particulier, j’espère trouver un outil permettant de construire automatiquement une bibliographie classée par thème (en utilisant le champ keywords) ;

– Éventuellement, initier un “WorkShop” électronique sur le WEB pour une meilleure diffusion, visibilité des travaux de recherche effectués sur une année.

9 Conclusion

Bien sur, je ne pourrai pas envisager de traiter l’ensemble des sujets de mon programme scientifique (tous seul). Il me semble pourtant important d’avoir à sa disposition une telle liste car, lors d’une étude approfondie d’un sujet donné on peut éventuellement découvrir des articles en relation avec un tout autre sujet répertorié dans cette liste. J’ai conçu ce programme scientifique pour qu’il puisse devenir un outil de travail pour mon équipe.

Références

[AC90] Isabelle Attali and Jacques Chazarain. Functional evaluation of strongly non-circular typol specifications. In Pierre Deransart and Martin Jourdan, editors, Attribute Grammars and their Applications (WAGA), volume 461 of Lecture Notes in Computer Science, pages 157–176. Springer-Verlag, New York–Heidelberg– Berlin, September 1990. Paris.

[And95] Laurent Andrey. Protocoles de communication et grammaires attribuées. PhD thesis, Université de Mancy, 1995.

[AP94] Isabelle Attali and Didier Parigot. Integrating Natural Semantics and Attribute Grammars: the Minotaur System. Rapport de recherche 2339, INRIA, 1994.

[AS95] Laurent Andrey and André Schaff. Description and prototyping of OSI protocol entities using attribute grammars. Technical Report 95-R-271, Centre de recherche en Informatique de Mancy, 1995.

[AS96] Laurent Andrey and André Schaff. Description et prototypage d’entité de protocole OSI par grammaire attribuées. Technical report, Centre de recherche en Informatique de Mancy, 1996.

[Asm97] Uwe Asmann. Software cocktail bars: A model of extensible software. Technical report, University of Karlsruh, IPD, January 1997.

[Att96] Isabelle Attali. Sémantique Naturelle: Evaluation et Expressivité. Mémoire d’habilitation, Université de Nice Sophia Antipolis, 1996.

[AW94] An Feng An and Toshiro Wakayama. SIMON: A grammar-based transformation system for structured documents. In Fifth International Conference on Electronic Publishing, pages 361–372, Darmstadt, Germany, 1994. Origination, Dissemination, and Design (EPODD) EP ’94.

[BM94] K. Barbar and K. Musumbu. Implementation of Abstract Interpretation Algorithm by means of Attribute Grammars. In Proceedings of the 26th Southeastern Symposium on System Theory, pages 87–93. IEEE Computer Society, March 1994.

[CFZ82] Bruno Courcelle and Paul Franchi-Zannettacci. Attribute grammars and recursive program schemes. Theoretical Computer Science, 17(2 and 3):163–191 and 235–257, 1982. part I and II See also: rapport 8008, University de Bordeaux I (April 1980).

[CM86] Laurian M. Chirica and David F. Martin. Toward compiler implementation correctness proofs. ACM Trans. Progr. Languages and Systems, 8(2):185–214, April 1986.

[CM96] Pierre Cointe and Jacques Malenfant. Aspect-oriented programming versus reflection. Technical report, École des Mines de Nantes, 1996.

[Con94] The COMPARE Consortium. fsdl. draft, Compare Consortium, novembre 1994. confidential.

[Con96] Charles Consel. A framework of application generator design. Technical Report 3005, INRIA, 1996.

[Cor96] Loïc Correnson. Généricité dans les grammaires attribuées. Rapport de stage d’option, École Polytechnique, 1996.

[DC90] Gerald D. P. Dueck and Gordon V. Cormack. Modular attribute grammars. The Computer Journal, 33:164–172, 1990. See also: research report CS-88-19, University of Waterloo (May 1988).

[DCB94] M. Desainte-Catherine and K. Barbar. Using attribute grammars to find solutions for musical equational programs. ACM SIG-PLAN Notices, 29(9):56–63, September 1994.

[DPJ95] Etienne Duris, Didier Parigot, and Martin Jourdan. Mises à jour destructives dans les grammaires attribuées. Rapport de recherche 2686, INRIA, October 1995.

[DPRJ96] Etienne Duris, Didier Parigot, Gilles Roussel, and Martin Jourdan. Grammaires attribuées et folds: Opérateurs de contrôle Génériques. In journées du GDR de programmation, Orléans, 1996.

[DPRJ97a] Etienne Duris, Didier Parigot, Gilles Roussel, and Martin Jourdan. Grammaires attribuées et folds : opérateurs de contrôle génériques. In Journées Francophones des Langages Applicatifs, , France, January 1997. ftp://ftp.inria.fr/INRIA/Projects/oscar/FNC-2/publications/jfla97.ps.gz.

[DPRJ97b] Etienne Duris, Didier Parigot, Gilles Roussel, and Martin Jourdan. Structure-directed genericity in functional programming and attribute grammars. Rapport de Recherche 3105, INRIA, February 1997.

[Dur94] Etienne Duris. Transformation de grammaires attribuées pour des mises à jour destructives. Rapport de DEA, Université d’Orléans, September 1994.

[EdJ90] Joost Engelfriet and Willem de Jong. Attribute storage optimization by stacks. Acta Informatica, 27:567–581, 1990. Preliminary version: rapport 88-30, Vakgroep Informatica, Rijksuniv. te Leiden (December 1988).

[EMR93] Sofoklis G. Efremidis, Khalid A. Mughal, and John H. Reppy. AML: Attribute grammars in ML. Technical Report TR93-1401, Cornell University, Computer Science Department, December 1993.

[EMSR97] Sofoklis Efremidis, Khalid A. Mughal, Lars Søraas, and John Reppy. AML: Attribute grammars in ML. Nordic Journal of Computing, March 1997.

[Fil86] Gilberto Filé. Classical and incremental attribute evaluation by means of recursive procedures. In Paul Franchi-Zannettacci, editor, 11th Coll. on Trees in Algebra and Programming (CAAP ’86), volume 214 of Lecture Notes in Computer Science, pages 112–126. Springer-Verlag, New York–Heidelberg–Berlin, March 1986. Nice.

[FJMM91] M. M. Fokkinga, J. Jeuring, L. Meertens, and E. Meijer. A translation from attribute grammars to catamorphisms. The Squiggolist, 2(1):20–26, 1991.

[FK93] R. A. Frost and S. Karamatos. Supporting the Attribute Grammar Programming Paradigm in a Lazy Functional Programming Language, volume 693 of Lecture Notes in Computer Science, pages 278–295. Springer Verlag, 1993.

[Fro94] Richard A. Frost. W/AGE : The windsor attribute grammar programming environment. Technical report, Winsdor University,

May 1994. ftp://ftp.cs.uwindsor.ca/pub/wage.

[FS90] R. A. Frost and W. S. Saba. A database interface based on montague’s approach to the interpretation of natural language. International Journal of Man-Machine Studies, 33(2):149–176, 1990.

[FZA89] Paul Franchi-Zannettacci and Dennis S. Arnon. Contextsensitive semantics as a basis for processing structured documents. BIGRE, 63–64:135–146, May 1989.

[Gan80] Harald Ganzinger. Some principles for the development of compiler from denotational language definitions. Bericht TUM-INFO-8006, Institut für Informatik, Tech. University München, May 1980.

[GG84] Harald Ganzinger and Robert Giegerich. Attribute coupled grammars. In ACM SIGPLAN ’84 Symp. on Compiler Construction, pages 157–170, Montréal, June 1984. Published as ACM SIGPLAN Notices, 19(6).

[GK93] Katsuhiko Gondow and Takuya Katayama. Attribute grammars as record calculus. Technical Report 93TR-0047, Tokyo Institute of Technology, 1993.

[GK95] Katsuhiko Gondow and Takuya Katayama. On formalization of object oriented attribute grammars OOAG and higher order attribute grammars using record calculus. Technical Report 95TR-0020, Tokyo Institute of Technology, 1995.

[Gro92] Josef Grosch. Multiple inheritance in object-oriented attribute grammars. Technical Report 28, GMD, Karlsruhe University, 1992.

[Hed91] Görel Hedin. Incremental static-semantics analysis for objectoriented languages using door attribute grammars. In Henk Alblas and Bor̆ivoj Melichar, editors, Attribute Grammars, Applications and Systems, volume 545 of Lecture Notes in Computer Science, pages 374–379. Springer-Verlag, New York–Heidelberg– Berlin, June 1991. Prague.

[HNP96] Chris Hankin, Hanne Riis Nielson, and Jens Palsberg. Strategic directions for research on programming languages. In Computing Surveys. December 1996.

[JC94] C. Barry Jay and J. R. B Cockett. Shapely types and shape polymorphism. In Donald Sannella, editor, European Symp. on Programming (ESOP ’94), volume 788 of Lect. Notes in Comp. Sci., pages 302–316. Springer-Verlag, April 1994.

[JJ96] J. Jeuring and P. Jansson. Polytypic programming. In J. Launchbury, E. Meijer, and T. Sheard, editors, Advanced Functional Programming, volume 1129 of Lect. Notes in Comp. Sci., pages 68–114. Springer-Verlag, 1996.

[JJ97] P. Jansson and J. Jeuring. PolyP - a polytypic programming language extension. In 24th ACM Symp. on Principles of Programming Languages, 1997.

[JMP94] Martin Jourdan, Bruno Marmol, and Didier Parigot. Experiments with a Real Parallel Attribute Evaluator. En préparation pour soumission, 1994.

[Joh87] Thomas Johnsson. Attribute grammars as a functional programming paradigm. In Gilles Kahn, editor, Func. Prog. Languages and Computer Architecture, volume 274 of Lecture Notes in Computer Science, pages 154–173. Springer-Verlag, New York– Heidelberg–Berlin, September 1987. Portland.

[Jou] Martin Jourdan. A Survey of Parallel Attribute Evaluation Methods. pages 234–255.

[JP] Martin Jourdan and Didier Parigot. The FNC-2 System User’s Guide and Reference Manual. INRIA, Rocquencourt, 1.9 edition.

[JP90a] Martin Jourdan and Didier Parigot. Techniques for Improving Grammar Flow Analysis. In Neil Jones, editor, European Symp. on Programming (ESOP ’90), volume 432 of Lect. Notes in Comp. Sci., pages 240–255, Copenhague, 1990. Springer-Verlag.

[JP90b] Catherine Julié and Didier Parigot. Space Optimization in the FNC-2 Attribute Grammar System. In Pierre Deransart and Martin Jourdan, editors, Attribute Grammars and their Applications (WAGA), volume 461 of Lect. Notes in Comp. Sci., pages 29–45, Paris, September 1990. Springer-Verlag.

[JPJ^{+}90] Martin Jourdan, Didier Parigot, Catherine Julié, Olivier Durin, and Carole Le Bellec. Design, implementation and evaluation of the FNC-2 attribute grammar system. In Conf. on Programming Languages Design and Implementation, pages 209–222, White Plains, NY, June 1990. Published as ACM SIGPLAN Notices, 25(6).

[Kos91] Kai Koskimies. Object-orientation in attribute grammars. In Henk Alblas and Bor̆ivoj Melichar, editors, Attribute Grammars, Applications and Systems, volume 545 of Lecture Notes in Computer Science, pages 297–329. Springer-Verlag, New York– Heidelberg–Berlin, June 1991. Prague.

[KP87] Kai Koskimies and Jukka Paakki. TOOLS: a unifying approach to object-oriented language interpretation. In ACM SIGPLAN ’87 Symp. on Interpreters and Interpretetive Techniques, pages 153–164. St. Paul, MN, June 1987. Published as ACM SIGPLAN Notices, volume 22, number 7.

[KR93] Richard Kieburtz and Jeffrey R. Programming with algebras. Technical report, Oregon Graduate Institute, 1993.

[KS86a] Uwe Kastens and M. Schmidt. Lifetime analysis for procedure parameters. In B. Robinet and Reinhard Wilhelm, editors, European Symp. on Programming (ESOP ’86), volume 213 of Lecture Notes in Computer Science, pages 53–69. Springer-Verlag, New York–Heidelberg–Berlin, March 1986. Saarbrücken.

[KS86b] Matthijs F. Kuiper and S. Doaitse Swierstra. Using Attribute Grammars to Derive Efficient Functional Programs. Report RUU–CS–86–16, Utrecht University, 1986.

[KV94a] A. Kühnemann and H. Vogler. A pumping lemma for output languages of attributed tree transducers. Acta Cybernetica, 11:261– 305, 1994.

[KV94b] A. Kühnemann and H. Vogler. Synthesized and inherited functions - a new computational model for syntax-directed semantics. Acta Informatica, 31:431–477, 1994.

[KW94] Uwe Kastens and William M. Waite. Modularity and Reusability in Attribute Grammars. Acta Informatica, 31:601–627, 1994.

[Le 93] Carole Le Bellec. La généricité et les grammaires attribuées. PhD thesis, Département de Mathématiques et d’Informatique, Université d’Orléans, 1993.

[Le 95] Gilles Le Bâtard. Réalisation dans le système FNC-2 d’un traducteur vers ML. rapport de stage de maîtrise, IFI, Université de Marne-la-Vallée, July 1995.

[Lei96] Stéphane Leibovitsch. Relations entre la sémantique dénotationnelle et les grammaires attribuées. Rapport de DEA, Université de Paris VII, September 1996.

[Lie92] Karl J. Lieberherr. Component enhancement: An adaptive reusability mechanism for groups of collaborating classes. In J. van Leeuwen, editor, Information Processing ’92, 12th World Computer Congress, pages 179–185, Madrid, Spain, 1992. Elsevier.

[LJ89] Sying-Syang Liu and Kurt R. Johmann. A tool specification language for software maintenance: Part I language design. Technical Report SERC-TR-36-F, Software Engineering Research Centre, November 1989.

[LJPR93] Carole Le Bellec, Martin Jourdan, Didier Parigot, and Gilles Roussel. Specification and Implementation of Grammar Coupling Using Attribute Grammars. In Maurice Bruynooghe and Jaan Penjam, editors, Programming Language Implementation and Logic Programming (PLILP ’93), volume 714 of Lect. Notes in Comp. Sci., pages 123–136, Tallinn, August 1993. Springer-Verlag.

[LL95] Cristina Videira Lopes and Karl J. Lieberherr. AP/S++: A CASE-study of a MOP for purposes of software evolution. Technical Report NU-CCS-95-?, Xerox PARC and Northeastern University, November 1995. ftp://ftp.ccs.neu.edu/pub/people/lieber/reflection-adaptive.ps.

[LSK90] Tan. Lichao, Y. Shinoda, and T. Katayama. Coping with Changes in an Object Management System based on Attribute Grammars. In Proceedings of the Fourth ACM SIGSOFT ’90 Symposium on Software Development Environments, pages 56– 65, December 1990. Published as SIGSOFT Software Engineering Notes, volume 15, number 6.

[Mar94] Bruno Marmol. La parallélisation et l’optimisation mémoire dans l’évaluation des grammaires attribuées. PhD thesis, Université d’Orléans, 1994.

[Mee95] Lambert Meertens. Category theory for program construction by calculation, 1995.

[MFP91] E. Meijer, M. M. Fokkinga, and R. Paterson. Functional programming with bananas, lenses, envelopes and barbed wire. In Conf. on Functional Programming and Computer Architecture (FPCA’91), volume 523 of Lect. Notes in Comp. Sci., pages 124– 144, Cambridge, September 1991. Springer-Verlag.

[MH95] Erik Meijer and Graham Hutton. Bananas in space: Extending fold and unfold to exponential types. In FPCA’95, 1995.

[MV95] Andrea Mößle and Heiko Vogler. Efficient call-by-value evaluation strategy of primitive recursive program schemes. In Proceedings of the Fuji International Workshop in Functional and Logic Programming. World Scientific Publishing Co. Pte Ltd., 1995.

[MW91] Ulrich Möncke and Reinhard Wilhelm. Grammar flow analysis. In Henk Alblas and Bor̆ivoj Melichar, editors, Attribute Grammars, Applications and Systems, volume 545 of Lecture Notes in Computer Science, pages 151–186. Springer-Verlag, New York– Heidelberg–Berlin, June 1991. Prague.

[OHIT97] Y. Onoue, Z. Hu, H. Iwasaki, and M. Takeichi. A calculational fusion system HYLO. In In Proc. IFIP TC 2 Working Conference on Algorithmic Languages and Calculi, Le Bischenberg, France, February 1997.

[OW97] Martin Odersky and Philip Wadler. Pizza into java: Translating theory into practice. In 24th ACM Symp. on Principles of Programming Languages, 1997.

[Paa94] J. Paakki. Multi-pass execution of functional logic programs. In Conference record of POPL ’94, 21st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages: papers presented at the Symposium: Portland, Oregon, January 17–21, 1994, pages 361–374, New York, NY, USA, 1994. ACM Press.

[Par88] Didier Parigot. Transformations, Évaluation Incrémentale et Optimisations des Grammaires Attribués: Le Système FNC-2. PhD thesis, Université de Paris-Sud, Orsay, 1988.

[PDRJ95] Didier Parigot, Etienne Duris, Gilles Roussel, and Martin Jourdan. Attribute grammars: a declarative functional language. rapport de recherche 2662, INRIA, October 1995.

ftp://ftp.inria.fr/INRIA/publication/RR/RR-2662.ps.gz.

[Pet95] Mikael Pettersson. Compiling Natural Semantics. Ph.d. dissertation, Linköping University, December 1995.

[PRJD96] Didier Parigot, Gilles Roussel, Martin Jourdan, and Etienne Duris. Dynamic Attribute Grammars. In Herbert Kuchen and S. Doaitse Swierstra, editors, Int. Symp. on Progr. Languages, Implementations, Logics and Programs (PLILP’96), volume 1140 of Lect. Notes in Comp. Sci., pages 122–136, Aachen, September 1996. Springer-Verlag.

[Ros90] Mads Rosendahl. Abstract interpretation using attribute grammars. In Pierre Deransart and Martin Jourdan, editors, Attribute Grammars and their Applications (WAGA), volume 461 of Lecture Notes in Computer Science, pages 143–156. Springer-Verlag, New York–Heidelberg–Berlin, September 1990. Paris.

[Ros91] Mads Rosendahl. Abstract Interpretation and Attribute Grammars. PhD thesis, Cambridge University, 1991.

[Ros92] Mads Rosendahl. Strictness analysis for attribute grammars. In Programming Language Implementation and Logic Programming (PLILP ’92), volume 631 of LNCS, pages 145–157. Springer-Verlag, 1992.

[Rou94a] Christophe Roudet. Visualisation graphique incrémentale par évaluation d’attributs. Stage de DEA informatique de l’ESSI, Université NICE, 1994.

[Rou94b] Gilles Roussel. Algorithmes de base pour la modularité et la réutilisabilité des grammaires attribuées. PhD thesis, Département d’Informatique, Université de Paris 6, March 1994.

[RPJ94] Gilles Roussel, Didier Parigot, and Martin Jourdan. Coupling Evaluators for Attribute Coupled Grammars. In Peter A. Fritzson, editor, 5th Int. Conf. on Compiler Construction (CC’ 94), volume 786 of Lect. Notes in Comp. Sci., pages 52–67, Edinburgh, April 1994. Springer-Verlag.

[Ruf97] Erik Ruf. Partitioning dataflow analyses using types. In 24th ACM Symp. on Principles of Programming Languages, 1997.

[Rus92] David Rushall. An attribute evaluator in haskell. Technical report, Manchester University, September 1992.

[SCG95] K. E. Schauser, D. E. Culler, and S. C. Goldstein. Separation constraint partitioning - A new algorithm for partitioning nonstrict programs into sequential threads. In In Proc. Principles of Programming Languages (POPL’95), San Francisco, CA, January 1995.

[SEFR89] S. Sagiv, O. Edelstein, Nissim Francez, and M. Rodeh. Resolving circularity in attribute grammars with applications to data flow analysis. In 16th ACM Symp. on Principles of Progr. Languages, pages 36–48. Austin, TX, January 1989.

[Ses89] Peter Sestoft. Replacing function parameters by global variables. In Conf. on Func. Prog. Languages and Computer Architecture., pages 39–53, London, September 1989. ACM Press.

[SG95] Klaus E. Schauser and Seth C. Goldstein. How much nonstrictness do lenient programs require? In Conf. on Func. Prog. Languages and Computer Architecture, pages 216–225, La Jolla, CA, USA, June 1995. ACM Press.

[She94] Tim Sheard. Meta programming tools for ML. Technical report, Oregon Graduate Institute, 1994.

[Son87] M. Sonnenschein. Graph translation schemes to generate compiler parts. ACM Transactions on Programming Languages and Systems, 9(4):473–490, October 1987.

[Sou90] Aziz Souah. Contribution à la sémantique déclarative des systèmes de transformation d’arbres attribués. PhD thesis, Université d’Orléans, November 1990.

[SV] S. Doaitse Swierstra and Harald H. Vogt. Higher Order Attribute Grammars. pages 256–296.

[SV90] S. Doaitse Swierstra and Harald H. Vogt. Higher order attribute grammars: a merge between functional and object oriented programming. report RUU–CS–90–12, Utrecht University, March 1990.

[Tav88] Victor E. Tavernini. Translating natural semantic specifications to attribute grammars. report UIUCDCS-R-88-1407, Department of Comp. Sc., University of Illinois at Urbana-Champaign, May 1988.

[TCl90] L Thomas and S. Cruz-lara. A concurrent object-oriented paradigm for attribute grammars. Technical report, Centre de recherche en Informatique de Mancy, 1990.

[TG95] G. Tremblay and G. R. Gao. The impact of laziness on parallelism and the limits of strictness analysis. In High Performance Functional Computing, pages 119–133, April 1995.

[Tre94] Guy Tremblay. Parallel implementation of lazy functional languages using abstract demand propagation. Phd thesis, McGill University, Montreal Canada, November 1994.

[UH94] James S. Uhl and Nigel Horspool. Flow grammars - a flow analysis methodology. In Peter A. Fritzson, editor, 5th Int. Conf. on Compiler Construction (CC’ 94), volume 786 of Lect. Notes in Comp. Sci., pages 203–217, Edinburgh, April 1994. Springer-Verlag.

[vdBFAvG93] P. M. van den Broek F. A. van Gilst. A new programming methodology for lazy functional languages. Technical report, University of Twente, 1993.

[vdM94] E. A. van der Meulen. Incremental Rewriting. PhD thesis, University of Amsterdam, 1994.

[Wad88] Philip Wadler. Deforestation: Transforming Programs to Eliminate Trees. In Harald Ganzinger, editor, European Symposium on Programming (ESOP ’88), volume 300 of Lect. Notes in Comp. Sci., pages 344–358, Nancy, March 1988. Springer-Verlag.

[Wad89] Philip Wadler. Theorems for free! In Conf. on Func. Prog. Languages and Computer Architecture, London, September 1989.

[Wal89] Janet A. Walz. Extending Attribute Grammar and Type Inference Algorithms. Ph.D. thesis, Cornell University, February 1989.

[WM94] Reinhard Wilhelm and R. Maurer. Les compilateurs - theorie, construction, generation. Masson, 1994.

[WM95] Reinhard Wilhelm and R. Maurer. Compiler Design. Addison Wesley, 1995.