Sommaire
Qu’est-ce qu’un compilateur ?
La naissance des compilateurs
Le premier compilateur, il s’appelait « translator » (traducteur) à l’époque, a été inventé par Grace Murray Hopper pour l’UNIVAC 1 en 1951, l’A-O System. Soit après la sortie de l’IBM 604 (1948), avant celle de l’IBM 650 (1954) et un peu avant le FORTRAN, langage compilé, créé vers 1953 par John Backus pour l’IBM 701 et lancé en 1957. La même année où IBM embauche Frances Allen pour former des scientifiques et des ingénieurs réticents à l’utilisation du langage. Elle sera, en 2006, la première femme à obtenir un prix Turing. Elle raconte, dans les Annals of History of Computing (Volume 6, N°1, janvier 1984) que :
L’une des façons dont le laboratoire de recherche a convaincu les gens à utiliser ce langage a été d’imposer son utilisation via un règlement.
Elle ajoutera :
le compilateur FORTRAN a établi la norme en matière d’efficacité du code objet. Mais surtout, il a démontré la faisabilité de l’utilisation des langages de haut niveau. Lorsque j’ai enseigné le FORTRAN en 1957, l’utilisation de ce langage a rencontré une forte résistance. Cette résistance a rapidement été érodée par le type de code produit par le compilateur.
John Backus, qui trouvait par ailleurs que Grace Murray Hopper était difficile à égaler, détaillait dans ces mêmes annales les auteurs et l’autrice du compilateur. Peter Sheridan avait écrit la section 1 qui analysait les expressions algébriques, les traduisait en code et optimisait ce code. Pour la section 2, Harlan Herrick avait inventé l’instruction DO, rédigé : « la partie de la section 1 qui regroupe toutes les informations sources non utilisées dans les expressions algébriques dans des tableaux nécessaires aux sections suivantes. ».
C’est également à Herrick que l’on doit l’introduction des mots clés GO TO ! Roy Nutt a conçu la majeure partie du langage d’entrée/sortie et rédigé la partie de la section 1 qui traduisait les instructions d’E/S en boucles DO. Il a également rédigé la section 6, qui assemblait le programme symbolique final et complétait le traitement des instructions d’E/S. C’est également à Nutt que l’on doit l’introduction de l’instruction FORMAT. Bob Nelson et Irv Ziller ont rédigé la section 2, qui s’est avérée être la plus grande section du compilateur. Elle analysait les références aux tableaux dans les boucles DO et produisait un code hautement optimisé pour le reste du programme source. Leur travail a eu un impact important sur le niveau global d’optimisation que j’ai mentionné précédemment. Dick Goldberg a rédigé la section 3, qui rassemblait le code compilé par les sections 1 et 2 et produisait d'autres informations nécessaires aux sections suivantes. Les gens continuaient à se concerter et à demander aux auteurs des sections précédentes de produire un peu plus, quelques tableaux supplémentaires dont ils avaient finalement besoin. Dick a également joué un rôle important dans le débogage de la section 5. Lois Haibt (en) a rédigé la section 4, qui effectuait une analyse statistique de la fréquence d'exécution […] Ici, la section 4 a également préparé de nombreux tableaux pour la section 5, si je comprends bien. Sheldon Best a écrit la section 5, qui a converti le programme utilisant de nombreux registres d'index en un programme en utilisant trois. Ses méthodes ont eu un impact considérable sur les travaux ultérieurs dans ce domaine et ont eu un effet majeur sur le niveau d'optimisation du compilateur. Enfin, David Sayre a rédigé un manuel du programmeur exceptionnellement clair et concis et a aidé Dick Goldberg à déboguer la section 5.
Schéma de la structure du compilateur de l’ordinateur IBM 704 adapté de celui fait par Frances Allen dans les « Annals of History of Computing », Volume 6, N°1, janvier 1984 (page 24).
De leur côté, les Soviétiques, qui fabriquaient aussi des ordinateurs, utilisaient également des compilateurs. Dans son article sur les ordinateurs soviétiques, Yves Logé rapporte qu’ils utilisaient, en 1955, les langages de compilation : PP2 – PP et BESM. Le BESM étant un ordinateur sorti en 1953. La fondatrice de la programmation théorique en Ukraine, Katerina Yushchenko (en), y a fort probablement contribué.
À quoi ça sert ?
En août 2001, dans un entretien (en) avec Janet Abbate qui lui demandait comment elle définirait une compilateur, Frances Allen répondait :
Je pense qu’un compilateur sert à traduire ce que l’utilisateur de l’application […] demande […] à la machine de manière à obtenir la bonne réponse, mais aussi à utiliser au mieux les ressources de la machine. C’est ça, l’optimisation. On peut se contenter de transposer les choses sans tirer parti des registres et de nombreuses autres unités de calcul, mais cela ne serait pas aussi efficace. L’optimisation consiste donc à tirer parti des ressources de la machine et à très bien connaître cette dernière. C’est en quelque sorte combler un fossé, afin que l’utilisateur n’ait pas besoin de tout savoir !
Plus généralement, un compilateur est décrit comme un programme dans un langage de haut niveau qui traduit le code-source en code objet pour le rendre exécutable en détectant les erreurs et en l’optimisant par la même occasion.
Le code source est envoyé au compilateur qui le traduit en langage machine.
Les compilateurs sont des outils essentiels et très complexes qui interviennent dans tous les programmes, notamment des logiciels très critiques :
Par exemple, les programmes embarqués dans les systèmes bancaires, dans les systèmes de contrôle de vol des avions, ou même dans la chirurgie assistée par ordinateur ou les centrales nucléaires […] : la présence d’erreur durant leur exécution pourrait avoir des conséquences désastreuses, que ce soit en termes de vies humaines, de dégâts écologiques, ou de coût financier. (Delphine Demange, Semantic foundations of intermediate program representations, Thèse soutenue le 19 octobre 2012.)
Comment ça marche ?
Réponse rapide : avec beaucoup de mathématiques. Réponse un peu plus détaillée : à partir de différents types d’analyses après une phase de pré-traitement qui permet de déterminer comment traiter les informations.
- L’analyse lexicale : découpe le code en unités lexicales ou « tokens » qui va pouvoir traiter par la suite. Ce faisant le compilateur sépare les différents types d’éléments : variables, opérateurs, séparateurs, mots-clés, etc.
- L’analyse syntaxique : vérifie que le programme source ne contient pas d’erreur de syntaxe et que le code source est correct et, évidemment le compilateur signale les erreurs qu’il a pu trouver à ce stade.
- L’analyse sémantique : après la syntaxe, c’est le sens du code qui est examiné. Le compilateur va ainsi vérifier s’il y a des erreurs de logique, passant, que le code fait bien ce qu’il est censé faire. À ce stade, le compilateur va aussi signaler les erreurs, voire, rejeter un code incorrect.
- L’optimisation : permet de nettoyer le code pour le rendre plus rapide à exécuter. À l’heure actuelle avec des processus très gourmands en ressources, c’est une étape-clé, ça n’a pas toujours été forcément le cas.
- La génération du code final : c’est la dernière phase dont le résultat est le code exécutable.
Delphine Demange : comment vérifier que les compilateurs font leur travail correctement
Parcours
Delphine Demande entre en licence d’informatique à l’université de Rennes 1 en 2004. Elle y obtiendra un magistère Informatique et télécommunications en 2006 puis fera le mastère de recherche en informatique de la même université en 2008. Elle achèvera cette partie de ses études par un stage de master à l’IRISA (équipe Celtique), en vérification de programme. Au bout des cinq mois de stage, en 2009, elle s’inscrira en thèse. Une thèse, Fondements sémantiques des représentations intermédiaires de programmes (en), soutenue en 2012 et qui lui vaudra le prix de thèse Gilles Kahn 2013 de la SIF, et qui porte sur :
la vérification formelle de logiciel, c’est-à-dire à l’ensemble des techniques et d’outils scientifiques qui permettent d’assurer qu’un logiciel remplit ces exigences [de qualité des systèmes critiques]. (Résumé étendu de sa thèse).
Elle part ensuite pour les USA, à l’Université de Pennsylvanie pour une année de post-doctorat. Là, elle travaillera sur un projet alliant vérification et sécurité. De retour en France, elle passe des concours. Elle est, depuis 2013, maîtresse de conférence à l’université Rennes 1.
En février 2024, elle donnait un cours au Collège de France : Représentations intermédiaires pour la compilation : s’affranchir du graphe de flot de contrôle.
On peut retrouver ses communications et articles ainsi que sa thèse, toutes en anglais, sur HAL science ouverte.
La vérification des logiciels
Comme elle le dit en résumé de sa thèse :
Nos vies quotidiennes dépendent de plus en plus, sans même parfois que nous nous en rendions compte, de l’utilisation de programmes informatiques. Ces programmes n’ont toutefois pas tous le même niveau de criticité. Par exemple, les programmes embarqués dans les systèmes bancaires, dans les systèmes de contrôle de vol des avions, ou même dans la chirurgie assistée par ordinateur ou les centrales nucléaires sont appelés systèmes critiques : la présence d’erreur durant leur exécution pourrait avoir des conséquences désastreuses, que ce soit en termes de vies humaines, de dégâts écologiques, ou de coût financier. Ce type de programme requiert donc de fortes garanties : leur exécution ne devrait pas échouer, et leur correction fonctionnelle devrait être garantie.
Elle ajoute plus loin que les compilateurs étant des logiciels, ils sont à leur tour susceptibles d’avoir des bugs comme n’importe quel autre programme. Il est donc nécessaire qu’ils répondent aux mêmes exigences infaillibilité que les systèmes critiques sur lesquels ils travaillent.
Dans un entretien accordé au site de l’université de Rennes en 2014, elle précise que son travail a pour but final :
d’assurer, par une preuve mathématique et assistée par ordinateur, que les compilateurs compilent correctement les programmes (i.e. ils n’ajoutent pas de nouveaux comportements aux programmes), et que les vérifieurs calculent des propriétés sur des modèles corrects des programmes (si le modèle du programme ne comporte pas d’erreur, alors le programme d’origine n’en comporte pas non plus).
Ses travaux de thèse portant les représentations intermédiaires (IR) des programmes sur lesquels travaillent les compilateurs et vérificateurs. Ces IR simplifient les analyses de ces outils qui peuvent analyser des programmes très complexes. Elle continue, depuis, ses recherches dans le même domaine avec :
la vérification des techniques de compilation optimisantes pour les langages de haut-niveau, en y incluant les aspects les plus difficiles des langages modernes, comme la gestion de la mémoire, la concurrence et les modèles de mémoire faibles. (entretien, Université de Rennes).
Tout cela demande beaucoup de mathématique, parfait pour quelqu’un qui a hésité entre les maths et l’informatique.
Quelques autres sources d’information
Sur les compilateurs, internet est bien pourvu en ressources en français sur le sujet, par exemple :
— Compilation informatique : définition concrète et rôle, Journal du net, 2016,
— Comment fonctionnent les compilateurs, IBM, [sd],
— Qu’est-ce qu’une conception de compilateur ? Types, outils de construction, exemple, Kaia Céruléen, GURU99, [septembre 2025 ?],
— Cours de compilation, [sd],
— Compilation, pdf à télécharger,
— Langages de programmation et compilation, Jean-Christophe Filliâtre, septembre 2016,
— Représentations intermédiaires pour la compilation : s’affranchir du graphe de flot de contrôle, cours au Collège de France, 15 février 2024
— Fondements sémantiques des représentations intermédiaires de programmes, thèse, en anglais, de Delphine Demange.
Sinon on peut aussi lire ou relire l’hommage à France Allen sur LinuxFr. Il y a aussi, en anglais, cet article Early Computers and Computing Institutions (en) qui raconte les débuts de FORTRAN. C’est très intéressant. Mais il faut soit l’acheter (15,50 dollars pour les membres ou 30 dollars pour les non-membres) ou faire partie d’une structure adhérente.
Questions et remerciements
Compte de tenu de l’importance des compilateurs, la question se pose de la raison pour laquelle la personne qui a été à l’origine du premier compilateur et du COBOL, Grace Murray Hopper (1906-1992) n’a pas reçu le prix Turing pourtant créé de son vivant, en 1966, et à une époque où elle était encore active. Le récipiendaire du prix Turing 1966 ayant d’ailleurs été Alan J. Perlis pour la construction de compilateurs.
Question complémentaire, pourquoi France Allen n’a reçu son prix Turing qu’en 2006 « pour ses contributions pionnières à la théorie et à la pratique des techniques utilisés par les compilateurs optimiseurs qui ont jeté les bases des compilateurs optimiseurs modernes et de l’exécution parallèle automatique. » Frances (“Fran“) Elizabeth Allen. A.M. Turing Award 2006 (en), alors qu’elle avait pris sa retraite depuis 2002. Elle reste toujours aussi importante : un de ses textes de 1970 fait partie de la bibliographie de la thèse de Delphine Demande.
Dernière question, dans son discours de remise du prix Turing en 2007, Frances Allen disait qu’après une phase de stagnation des compilateurs, on devrait avoir une phase de progrès significatifs dans le domaine. Est-ce que vous avez une idée de ce à quoi elle aurait pu penser ?
Un très grand merci à vmagnin pour son aide et les documents qu’il m’a envoyés pour m’aider à rédiger cette dépêche.
Connexion
