Amorçage (compilateurs) - Bootstrapping (compilers)

Cet article concerne l'amorçage des compilateurs. Pour le concept général, voir Bootstrapping .

En informatique , l' amorçage est la technique permettant de produire un compilateur auto-compilé , c'est-à-dire un compilateur (ou assembleur ) écrit dans le langage de programmation source qu'il a l'intention de compiler. Une version initiale du noyau du compilateur (le compilateur d'amorçage ) est générée dans un langage différent (qui pourrait être un langage d'assemblage) ; des versions étendues successives du compilateur sont développées en utilisant ce sous-ensemble minimal du langage. Le problème de la compilation d'un compilateur auto-compilé a été appelé le problème de la poule ou de l'œuf dans la conception du compilateur, et l'amorçage est une solution à ce problème.

De nombreux compilateurs pour de nombreux langages de programmation sont amorcés, y compris les compilateurs pour BASIC , ALGOL , C , C# , D , Pascal , PL/I , Factor , Haskell , Modula-2 , Oberon , OCaml , Common Lisp , Scheme , Go , Java , Elixir , Rust , Python , Scala , Nim , Eiffel , Vala , etc.

Traiter

Un processus d'amorçage typique fonctionne en trois ou quatre étapes :

  • Étape 0 : préparation d'un environnement avec lequel le compilateur d'amorçage fonctionnera.
  • Étape 1 : le compilateur bootstrap est produit.
  • Étape 2 : un compilateur complet est produit par le compilateur d'amorçage.
  • Étape 3 : un compilateur complet est produit par le compilateur complet de l'étape 2.

Le compilateur complet est construit deux fois afin de comparer les sorties des deux étapes. S'ils sont différents, le bootstrap ou le compilateur complet contient un bogue.

Avantages

L'amorçage d'un compilateur présente les avantages suivants :

  • c'est un test non trivial du langage en cours de compilation, et en tant que tel, c'est une forme de dogfooding .
  • Les développeurs de compilateurs et les rapporteurs de bogues n'ont besoin de connaître que le langage en cours de compilation.
  • le développement du compilateur peut être effectué dans le langage de niveau supérieur en cours de compilation.
  • les améliorations apportées au back-end du compilateur améliorent non seulement les programmes à usage général mais aussi le compilateur lui-même.
  • il s'agit d'un contrôle de cohérence complet car il doit être capable de reproduire son propre code objet.

Notez que certains de ces points supposent que le language runtime est également écrit dans le même langage.

Méthodes

Si l'on a besoin de compiler un compilateur pour le langage X écrit en langage X, se pose la question de savoir comment le premier compilateur peut être compilé. Les différentes méthodes utilisées dans la pratique comprennent :

  • Implémentation d'un interpréteur ou d'un compilateur pour le langage X dans le langage Y. Niklaus Wirth a indiqué qu'il a écrit le premier compilateur Pascal en Fortran .
  • Un autre interpréteur ou compilateur pour X a déjà été écrit dans un autre langage Y ; c'est ainsi que Scheme est souvent amorcé.
  • Les versions antérieures du compilateur étaient écrites dans un sous-ensemble de X pour lequel il existait un autre compilateur ; c'est ainsi que certains sur-ensembles de Java , Haskell et le compilateur Free Pascal initial sont amorcés.
  • Un compilateur prenant en charge des extensions de langage non standard ou des fonctionnalités de langage facultatives peut être écrit sans utiliser ces extensions et fonctionnalités, pour permettre sa compilation avec un autre compilateur prenant en charge le même langage de base mais un ensemble différent d'extensions et de fonctionnalités. Les principales parties du clang du compilateur C++ ont été écrites dans un sous-ensemble de C++ qui peut être compilé à la fois par g++ et Microsoft Visual C++ . Les fonctionnalités avancées sont écrites avec certaines extensions GCC.
  • Le compilateur pour X est compilé de manière croisée à partir d'une autre architecture où il existe un compilateur pour X ; c'est ainsi que les compilateurs pour C sont généralement portés sur d'autres plates-formes. C'est également la méthode utilisée pour Free Pascal après le démarrage initial.
  • Écriture du compilateur en X ; puis compilez-le à la main à partir de la source (très probablement d'une manière non optimisée) et exécutez-le sur le code pour obtenir un compilateur optimisé. Donald Knuth l'a utilisé pour son système de programmation Web .

Les méthodes de distribution des compilateurs dans le code source incluent la fourniture d'une version portable du bytecode du compilateur, de manière à amorcer le processus de compilation du compilateur avec lui-même. Le diagramme en T est une notation utilisée pour expliquer ces techniques d'amorçage du compilateur. Dans certains cas, le moyen le plus pratique d'exécuter un compilateur compliqué sur un système qui n'a que peu ou pas de logiciel implique une série d'assembleurs et de compilateurs de plus en plus sophistiqués.

Histoire

Article principal: Histoire de la construction du compilateur

Les assembleurs ont été les premiers outils de langage à s'amorcer.

Le premier langage de haut niveau à fournir un tel bootstrap était NELIAC en 1958. Les premiers langages largement utilisés à le faire étaient Burroughs B5000 Algol en 1961 et LISP en 1962.

Hart et Levin ont écrit un compilateur LISP en LISP au MIT en 1962, le testant dans un interpréteur LISP existant. Une fois qu'ils avaient amélioré le compilateur au point où il pouvait compiler son propre code source, il s'auto-hébergeait.

Le compilateur tel qu'il existe sur la bande de compilation standard est un programme en langage machine qui a été obtenu en faisant fonctionner la définition de l' expression S du compilateur sur elle-même via l'interpréteur.

—  Mémo IA 39

Cette technique n'est possible que lorsqu'un interpréteur existe déjà pour le même langage qui doit être compilé. Il emprunte directement à la notion d'exécution d'un programme sur lui-même en entrée, qui est également utilisée dans diverses preuves en informatique théorique , comme la preuve que le problème d'arrêt est indécidable.

Efforts en cours

En raison de problèmes de sécurité concernant l' attaque Trusting Trust et diverses attaques contre la fiabilité binaire, plusieurs projets s'efforcent de réduire les efforts non seulement pour l'amorçage à partir de la source, mais également pour permettre à tout le monde de vérifier que la source et l'exécutable correspondent. Ceux-ci incluent le projet de builds Bootstrapable et le projet de builds reproductibles.

Voir également

Les références

  1. ^ Reynolds, John H. (décembre 2003). "Amorçage d'un compilateur auto-compilé de la machine X vers la machine Y" . CCSC : Conférence de l'Est. Journal des sciences de l'informatique dans les collèges . 19 (2) : 175-181. L'idée d'un compilateur écrit dans le langage qu'il compile soulève la vieille énigme de la « poule ou de l'œuf » : d'où vient le premier ?
  2. ^ Glück, Robert (2012). « Amorçage des générateurs de compilateur à partir d'évaluateurs partiels ». Dans Clarke, Edmund; Virbitskaïte, Irina ; Voronkov, Andrei (éd.). Perspectives of Systems Informatics: 8th International Andrei Ershov Memorial Conference, PSI 2011, Novosibirsk, Russie, 27 juin-1er juillet 2011, Documents sélectionnés révisés . Notes de cours en informatique. 7162 . Springer. p. 125-141. doi : 10.1007/978-3-642-29709-0_13 . La mise en route présente le problème de la poule et de l'œuf familier de la construction du compilateur : il faut un compilateur pour amorcer un compilateur, et l'amorçage des générateurs de compilateur ne fait pas exception.
  3. ^ un b "Installation de GCC : Bâtiment" . Projet GNU - Free Software Foundation (FSF) .
  4. ^ "rouille-lang/rouille: bootstrap" . GitHub .
  5. ^ "Configurations de construction avancées — documentation LLVM 10" . llvm.org .
  6. ^ Compilateurs et générateurs de compilateurs : Une introduction avec C++. Patrick D. Terry 1997. Presse informatique internationale Thomson. ISBN  1-85032-298-8
  7. ^ un b "Compiler Construction and Bootstrapping" par PDTerry 2000. HTML Archivé le 23/11/2009 à la Wayback Machine . PDF Archivé le 14 décembre 2010 à la Wayback Machine .
  8. ^ Niklaus Wirth. 2021. 50 ans de Pascal. Commun. ACM 64, 3 (mars 2021), 39-41. DOI : https://doi.org/10.1145/3447525
  9. ^ "Amorçage d'un simple compilateur à partir de rien" Archivé le 3 mars 2010, à la Wayback Machine par Edmund GRIMLEY EVANS 2001
  10. ^ un b Tim Hart et Mike Levin. "AI Memo 39-Le nouveau compilateur" (PDF) . Archivé de l'original (PDF) le 2020-12-13 . Récupéré le 23-05-2008 .
  11. ^ http://bootstrapable.org/
  12. ^ https://reproductible-builds.org/