Bootstrap (compilateur)
Pour les articles homonymes, voir Bootstrap.
Le bootstrapping ou auto-amorçage est, en informatique, une technique consistant à créer un compilateur (ou un programme assembleur) en utilisant le langage de programmation qu'il doit compiler (ou assembler). Pour cela, on part d'un premier compilateur minimal, appelé Amorce, écrit de façon classique, permettant de traduire un sous-ensemble réduit du langage; le compilateur définitif est alors écrit dans ce sous-langage et compilé avec l'amorce. Cette technique s'applique aussi bien sur un même système qu'en portage d'un système à l'autre. Vu leur complexité, l'auto-amorçage permet de réduire l'effort et le temps de développement des compilateurs, en utilisant un langage de plus haut niveau que ceux disponibles pour le système cible considéré[1].
Histoire
[modifier | modifier le code]NELIAC (en), un dialecte d'Algol 58, a été le premier langage à fournir un bootstrap.
Au début des années 1960, l'Algol du Burroughs 5 000, permit à Burroughs de développer ses futurs systèmes d'exploitation sur la base d'Algols étendus : Grands systèmes Burroughs (en) .
En 1962, Hart et Levin écrivent un compilateur Lisp en Lisp. Ils le testèrent à l'aide d'un interprète Lisp, assimilant tout programme à une expression Lisp .
En 1968-1969, PL1 Multics est développé ainsi chez GE.
Une présentation générale de la stratégie de bootstrapping a été faite en 1971[2] et fut l'occasion de présenter les diagrammes de Tombstone (en) qui permettent de la visualiser.
Phases
[modifier | modifier le code]Amorce
[modifier | modifier le code]Soit le langage à traiter, et un langage disponible : on commence par écrire en un petit compilateur de , produisant une image dans un langage exécutable dans le même environnement. Il suffit que ce premier compilateur traduise exactement les programmes n'utilisant qu'un sous-ensemble contenant les constructions nécessaires de . Un tel compilateur sera noté symboliquement .
![{\displaystyle L_{0}{\xrightarrow[{\text{X}}]{\text{1}}}A}](https://wikimedia.org/api/rest_v1/media/math/render/svg/725b0bd9aacba5acb73ac43d54c99f9352945803)
De tels compilateurs furent longtemps développés en assembleur. Les premiers compilateurs peuvent être maintenant écrits en C ou dans un langage spécialisé dans l'écriture de compilateurs.
Améliorations
[modifier | modifier le code]Soit un premier compilateur noté , écrit en et traduisant un sous-ensemble de L dans un langage exécutable [3]. En transcrivant son analyse de en , nous obtenons un nouveau compilateur . Compilé par le premier, il donne un nouveau .
![{\displaystyle L_{0}{\xrightarrow[{L_{0}}]{2}}A}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0f271b33846d39e581331cac32224fc64172dd05)
![{\displaystyle L_{0}{\xrightarrow[{\text{X}}]{\text{3}}}A}](https://wikimedia.org/api/rest_v1/media/math/render/svg/66ed90b746d2ceb3ba1d13fef730b340e4d99505)
Soit maintenant une version étendue de (2); compilée par (1), on obtiendra de même .
![{\displaystyle L_{1}{\xrightarrow[{L_{0}}]{4}}A}](https://wikimedia.org/api/rest_v1/media/math/render/svg/af2eb50ad907b46a31944865c1cda7f8de918945)
![{\displaystyle L_{1}{\xrightarrow[{\text{X}}]{\text{5}}}A}](https://wikimedia.org/api/rest_v1/media/math/render/svg/53d6fdfdbb6fc40cbc3b78fa665e1436f94dc040)
(5) se présente alors comme une extension de (1) bénéficiant des extensions introduites par (4), et peut être oublié au profit de .
Avec (6) traitant en une nouvelle extension , on obtiendra de même (7), rendant utilisable au lieu de et ...
Cette stratégie de prototypage évolutif (en) permet d'étendre la puissance du langage effectif, d'abord réduit au strict nécessaire (par exemple, la forme itérative la plus générale), puis étendu aux constructions "de confort" (comme les formes itératives secondaires), voire à d'éventuelles extensions ; c'est ainsi que des sur-ensembles de Java sont bootstrappés.
D'une version à l'autre, les développeurs du compilateur devenant leurs propres utilisateurs, les améliorations peuvent également porter sur la qualité de la détection d'erreurs et du code engendré.
L'équipe de Niklaus Wirth tenta de réaliser le premier compilateur Pascal en Fortran, qui se révéla insuffisant. Elle fit une nouvelle tentative en utilisant Pascal comme notation algorithmique du nouveau compilateur, et traduisit à la main cette spécification détaillée. Elle obtint ainsi un compilateur de type natif pour CDC 6600, et un compilateur auto-porteur qui lui permirent une succession d'améliorations.
Portage
[modifier | modifier le code]Supposons que l'on dispose d'un couple .
![{\displaystyle L{\xrightarrow[{\text{X }}]{}}A,L{\xrightarrow[{\text{L}}]{}}A}](https://wikimedia.org/api/rest_v1/media/math/render/svg/97bf31751ff73d618726a29be85c7a5fb4fdcd95)
En modifiant la génération de on obtient un ; en le compilant dans le premier environnement, on obtient le nouveau compilateur .
![{\displaystyle L{\xrightarrow[{\text{L}}]{}}A}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ffc7a4c7f5c342981264dbdc62f12b84289db010)
![{\displaystyle L{\xrightarrow[{\text{L}}]{}}B}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ee59f48a7d4e24870f89ab3dbddb4f7c7b2b120e)
![{\displaystyle L{\xrightarrow[{\text{X}}]{}}B}](https://wikimedia.org/api/rest_v1/media/math/render/svg/464f80288ec1f7f2458caffe17fc8adcff4681c0)
En 1975, H.H. Nägeli écrivit un trunk compiler pour faciliter le portage de Pascal. C'était un compilateur de Pascal écrit en Pascal, séparant nettement les parties indépendantes des parties dépendantes de la machine-cible, comme les séquences de génération ; un commentaire détaillé pour ces dernières permettait à un compiliste de les adapter à une nouvelle machine. C'est ainsi que l'INRIA put faire en 9 mois-hommes un compilateur croisé, tournant sur CDC mais traduisant Pascal en code pour l'Iris 80 ainsi qu'un compilateur Pascal, fonctionnant pour et sur l'Iris 80. Ce dernier, écrit en Pascal, étant de ce fait facile à maintenir et à améliorer.
Cas de la semi-compilation
[modifier | modifier le code]On parle de semi-compilation quand le compilateur produit non un code machine natif (propre à l'environnement visé) mais un pseudo-code (ou bytecode ) P relatif à une machine virtuelle pouvant exécuter le langage au mieux.
Le produit générique est alors un couple .
![{\displaystyle L{\xrightarrow[{\text{L }}]{}}P,L{\xrightarrow[{\text{P}}]{}}P}](https://wikimedia.org/api/rest_v1/media/math/render/svg/eda486e5b342b65fc9357480b4673707020ec6c1)
- est exécutable dès que P l'est dans l'environnement donné ; un interprète de P est alors suffisant pour la programmation exploratoire ;
- au-delà, si on adjoint à un générateur , on obtient un compilateur , et si nécessaire un compilateur ,.
![{\displaystyle L{\xrightarrow[{\text{P}}]{}}P}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5952f50a8f5091291ac9c3bb1d2767eee583f920)
![{\displaystyle P{\xrightarrow[{\text{P}}]{}}Z}](https://wikimedia.org/api/rest_v1/media/math/render/svg/38b16077a68924ecac20d1a7e548eb7192ed3235)
![{\displaystyle L{\xrightarrow[{\text{P}}]{}}Z}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4d6810458b37a8927774cfc7d8ba8d59ae654745)
![{\displaystyle L{\xrightarrow[{\text{Z}}]{}}Z}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c4b15962403c0f617c1e20410a71122626b264fb)
Cette technique a pu utiliser un P-code (Pascal), un M-code (Modula), un S-code (Simula), un J-code (Java) etc.
Intérêt
[modifier | modifier le code]Cette approche peut être à la fois le support d'un compilateur multi-cible, ayant un analyseur et un générateur d'un pseudo-code commun P, puis autant de générateurs finaux que de machines cibles.
Elle peut être au cœur d'un atelier logiciel dont les langages partageraient le même pseudo-code P, surtout si celui-ci reste réversible.
Exemples de langages informatiques bootstrappés
[modifier | modifier le code]- Algol 58,
- C,
- Lisp, dont le compilateur original a été produit par un interpréteur (première occurrence de ce genre de bootstrap), puis compilé par ce même compilateur[4].
Emplois
[modifier | modifier le code]Les méthodes pour distribuer des compilateurs en code source incluent la fourniture d'un bytecode portable du compilateur, afin de bootstrapper le système de compilation du compilateur avec lui-même.
Aujourd'hui, une large proportion des langages de programmation sont bootstrappés : C, Scheme, Ocaml, Pascal, Modula-2, Oberon, Perl 6, Java, C#.
Notes
[modifier | modifier le code]- Alfred Aho, Compilateurs. Principes, techniques et outils, Paris, InterEditions, , 877 p. (ISBN 2-7296-0295-X), p. 789-793
- (en) William Marshall McKeeman, James J. Horning et David B. Wortman, A Compiler Generator, Prentice Hall, , 527 p. (ISBN 978-0131550773).
- code machine par exemple
- (en) Tim Hart, AI Memo 39 - The New Compiler (lire en ligne)
