Last modified: Mon Dec 2 1996
Les Grammaires Attribuées (GA) sont un paradigme de programmation déclaratif et dirigé par la syntaxe qui a prouvé sa valeur sur de grosses applications comme les compilateurs. Nous étudions les GA depuis de nombreuses années dans le projet Oscar de l'INRIARocquencourt. La concrétisation de ces travaux est le système Fnc-2, destiné à traiter des applications industrielles mais qui est aussi le support de tous nos travaux de recherche.
Depuis quelques années, un certain nombre de travaux de recherches ont montré les fortes relations existant entre la programmation fonctionnelle et les grammaires attribuées. Notre groupe s'est particulièrement intéressé aux équivalences entre les transformations de programmes fonctionnels et de grammaires attribuées (notion de fusion), ainsi qu'à la notion de généricité structurelle Duris97. En effet, il existe depuis quelques années un intense effort de recherche sur une formalisation rigoureuse de la programmation fonctionnelle dirigée par la structure (catamorphismes) et des transformations de programmes qu'elle autorise. Cette formalisation nous a permit d'établir plus solidement les liens avec la programmation par grammaire attribuée, intrinsèquement dirigée par la structure.
Sur cette base, plusieurs extensions de langages fonctionnels (SML, Haskell) ont été proposées pour y introduire le style de programmation par grammaire attribuées. À notre avis, leur défaut commun est qu'elles imposent de typer explicitement les attributs, ce qui est contraire à l'esprit de l'inférence de types et du polymorphisme qui caractérise ces langages de base. Par ailleurs, lors de la réalisation d'un générateur de code CAML pour notre système Fnc-2, nous avons constaté qu'effectuer l'inférence de types sur le code CAML produit ne permet pas d'obtenir le type le plus général dans certain cas impliquant des attributs de type fonctionnel.
L'objectif du stage proposé sera donc d'étudier comment effectuer l'inférence de type directement sur la grammaire attribuée d'entrée. En première approche, le langage considéré sera très simple, en permettant seulement d'exprimer des grammaires attribuées sur des types concrets polymorphes.
En fonction du rythme d'avancement des travaux, on pourra envisager des extensions comme, d'une part, étendre le langage initial pour en faire un ``vrai'' langage (en particulier au niveau du système de modules), puis surtout d'étudier comment exprimer le style de programmation dirigé par la structure, en particulier au niveau des transformations de programmes (fusion) et de la généricité.
Généralités et autres sujets de stage sur les grammaires attribuées proposés par le projet Oscar