To: seminaire@pauillac.inria.fr From: Francois.Pottier@inria.fr Subject: SEM - INRIA : Moscova - 08/12/04 - Paris - FR Vous pouvez vous abonner à nos annonces de séminaires http://pauillac.inria.fr/seminaires/subscribe.html S E M I N A I R E ___ . / ___ __ /_ _ / /| /| _ __ __ _ _ / / / /_ / __| / ----- / |/ | / \ /_ / / \ | / __| |___ / / __/ |_ |_/ |_ / | |_/__/ |_ |_/ |/ |_/ I N R I A - Rocquencourt Salle de conférences du bâtiment 7 Mercredi 8 decembre, 10h30 --------------- Olivier Tardieu --------------- INRIA ========================================================================== De la sémantique opérationnelle à la spécification formelle de compilateur L'exemple des boucles en Esterel ========================================================================== Esterel est un langage impératif concurrent pour la programmation des systèmes réactifs. A l'exception de l'instruction "pause", les primitives du langage s'exécutent sans consommer de temps logique. L'exécution se décompose donc en une suite d'instants. Dans ce contexte, les boucles peuvent poser deux types de problèmes: d'une part une boucle instantanée peut bloquer l'écoulement du temps; d'autre part un bloc de code peut être traversé plusieurs fois au cours du même instant, conduisant à un comportement du programme dit "schizophrène". Les boucles instantanées sont proscrites par la sémantique. Elles doivent donc être détectées par les compilateurs et les programmes correspondants doivent être rejetés. Par ailleurs, la compilation efficace des programmes schizophrènes est difficile. Ainsi, alors que plusieurs compilateurs pour Esterel sont disponibles, les algorithmes employés pour compiler les boucles ne sont ni portables, ni formellement spécifiés, et encore moins prouvés. Dans ce travail, nous étudions les boucles en Esterel, établissant une correspondance formelle entre la sémantique opérationnelle du langage et l'implémentation concrète d'un compilateur. Après avoir spécifié les problèmes posés par les boucles, nous développons des techniques d'analyse statique efficaces pour les détecter dans un code Esterel quelconque. Puis, de façon à "guérir" la schizophrénie, c'est à dire transformer efficacement les programmes schizophrènes en programmes non-schizophrènes, nous introduisons dans le langage une nouvelle primitive appelée "gotopause". Elle permet de transférer le contrôle d'un point du programme à un autre de façon non-instantanée, mais sans contrainte de localité. Elle préserve le modèle de concurrence synchrone d'Esterel. Nous décrivons un premier algorithme qui, en dépliant les boucles à l'aide de cette nouvelle instruction, produit pour tout programme Esterel correct un programme non-schizophrène équivalent. Enfin, en combinant analyse statique et réécriture, nous obtenons un préprocesseur qui rejette les boucles instantanées et guérit la schizophrénie, à la fois portable et très efficace. Nous l'avons implémenté. De plus, grâce à une approche formelle de bout en bout, nous avons pu prouver la correction de ce préprocesseur.