Bootstrap (compilateur)

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Pour les articles homonymes, voir Bootstrap.

Le bootstrapping décrit en informatique les techniques basées sur l'écriture d'un compilateur (ou d'un assembleur) dans le langage de programmation cible qu'il doit compiler.

Ce paradoxe de l'œuf et de la poule pose 2 questions : pourquoi le faire ? comment le faire ?

De fait, il s'agit d'une technique de développement (sur un même système) ou de portage (d'un système à l'autre), qui part d'un premier compilateur minimal écrit de façon classique, amorçant une suite de versions, chacune préférable à la précédente. Cette technique se révèle plus facile et plus rapide que l'écriture directe d'un produit final ambitieux.

Histoire[modifier | modifier le code]

NELIAC (en), un dialecte d'Algol 58, a été le premier langage à fournir un tel bootstrap.

Les premiers langages répandus à faire de même furent :

  • Au début des années 1960, l'Algol du Burroughs 5000, qui permit à Burroughs de développer ses futurs systèmes d'exploitation sur la base d'Algols étendus : Grands systèmes Burroughs (en) ;
  • Lisp en 1962 : Hart et Levin ayant écrit un compilateur LISP en Lisp, ils le testèrent à l'aide d'un interprète LISP, assimilant tout programme à une expression LISP ;
  • PL1 Multics, développé ainsi chez GE en 1968-1969.

Une présentation générale de la stratégie a été faite en 1971[1] 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 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 suffira que ce premier compilateur traduise exactement les programmes n'utilisant qu'un sous-ensemble contenant les constructions nécessaires de L. Un tel compilateur sera noté symboliquement .

De tels compilateurs furent longtemps développés en assembleur, un langage symbolique est souvent plus commode et plus sûr. 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]

Supposons un premier compilateur noté , écrit en X et traduisant un sous-ensemble de L dans un langage exécutable A [2]. En transcrivant son analyse de X en , nous obtenons un nouveau compilateur . Compilé par le premier, il donne un nouveau .

Soit maintenant une version étendue de (2); compilée par (1), on obtiendra de même .

(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 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 .

En modifiant la génération de on obtient un ; en le compilant dans le premier environnement, on obtient le nouveau compilateur .

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 hommes-mois (1) un compilateur croisé, tournant sur CDC mais traduisant Pascal en code pour l'Iris 80 et (2) 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 .

  • 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 ,.

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 multicible, ayant un analyseur et un générateur d'un pseudo-code commun P, puis autant de générateurs finaux que de machines-cible.

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.

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 .

Notes[modifier | modifier le code]

  1. (en) William Marshall McKeeman, James J. Horning et David B. Wortman, A Compiler Generator, Prentice Hall, , 527 p. (ISBN 978-0131550773).
  2. code machine par exemple

Voir aussi[modifier | modifier le code]

Liens externes[modifier | modifier le code]