# Bootstrap (compilateur)

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 la complexité des compilateurs, l'auto-amorçage permet de réduire l'effort et leur temps de développement, en utilisant un langage de plus haut niveau que ceux disponibles pour le système cible considéré.

## Histoire

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 et fut l'occasion de présenter les diagrammes de Tombstone (en) qui permettent de la visualiser.
Les méthodes pour distribuer des compilateurs en code source incluent actuellement la fourniture d'un bytecode portable du compilateur, afin de bootstrapper le système de compilation du compilateur avec lui-même.

## Phases
### Amorce

Soit $L$ le langage à traiter, et $X$ un langage disponible : on commence par écrire en $X$ un petit compilateur de $L$, produisant une image dans un langage $A$ exécutable dans le même environnement. Il suffit que ce premier compilateur traduise exactement les programmes n'utilisant qu'un sous-ensemble $L_{0}$ contenant les constructions nécessaires de $L$. Un tel compilateur sera noté symboliquement $L_{0}{\xrightarrow[{\text{X}}]{\text{1}}}A$.
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

Soit un premier compilateur noté $L_{0}{\xrightarrow[{\text{X}}]{\text{1}}}A$, écrit en $L$ et traduisant un sous-ensemble $L_{0}$ de L dans un langage exécutable $A$. En transcrivant son analyse de $X$ en $L_{0}$, nous obtenons un nouveau compilateur $L_{0}{\xrightarrow[{L_{0}}]{2}}A$ . Compilé par le premier, il donne un nouveau $L_{0}{\xrightarrow[{\text{X}}]{\text{3}}}A$.
Soit maintenant $L_{1}{\xrightarrow[{L_{0}}]{4}}A$ une version étendue de (2); compilée par (1), on obtiendra de même $L_{1}{\xrightarrow[{\text{X}}]{\text{5}}}A$.
(5) se présente alors comme une extension de (1) bénéficiant des extensions introduites par (4), et $L_{0}$ peut être oublié au profit de $L_{1}$.
Avec (6) traitant en $L_{1}$ une nouvelle extension $L_{2}$, on obtiendra de même (7), rendant $L_{2}$ utilisable au lieu de $L_{1}$ et $L_{0}$...
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

Supposons que l'on dispose d'un couple $L{\xrightarrow[{\text{X }}]}A,L{\xrightarrow[{\text{L}}]}A$ .
En modifiant la génération de $L{\xrightarrow[{\text{L}}]}A$ on obtient un $L{\xrightarrow[{\text{L}}]}B$; en le compilant dans le premier environnement, on obtient le nouveau compilateur $L{\xrightarrow[{\text{X}}]}B$.
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

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 $L{\xrightarrow[{\text{L }}]}P,L{\xrightarrow[{\text{P}}]}P$ .
* $L{\xrightarrow[{\text{P}}]}P$ 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 à $L{\xrightarrow[{\text{P}}]}P$ un générateur $P{\xrightarrow[{\text{P}}]}Z$, on obtient un compilateur $L{\xrightarrow[{\text{P}}]}Z$, et si nécessaire un compilateur $L{\xrightarrow[{\text{Z}}]}Z$,.
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

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.

## Langages de programmation bootstrappés

Suivant les premiers exemples historiques (Algol 58, C, et Lisp – dont le compilateur original a été produit par un interpréteur puis compilé par ce même compilateur), une large proportion des langages de programmation actuels sont bootstrappés : C, Scheme, Ocaml, Pascal, Modula-2, Oberon, Perl 6, Java, C#...