Le bootstrapping nécessite toujours un soutien extérieur

Question

J'ai entendu parler de l'idée de démarrer un langage, c'est-à-dire d'écrire un compilateur/interprète pour le langage lui-même.Je me demandais comment cela pourrait être accompli et j'ai regardé un peu autour de moi et j'ai vu quelqu'un dire que cela ne pouvait être fait que par l'un ou l'autre.

• écrire un compilateur initial dans un langage différent.
• coder manuellement un compilateur initial dans Assembly, ce qui semble être un cas particulier du premier

Pour moi, aucun de ces éléments ne semble réellement être amorçage une langue dans le sens où ils nécessitent tous deux un soutien extérieur.Existe-t-il un moyen d'écrire un compilateur dans son propre langage ?

Answer 1

Existe-t-il un moyen d'écrire un compilateur dans son propre langage ?

Toi avoir avoir un langage existant dans lequel écrire votre nouveau compilateur.Si vous écriviez un nouveau compilateur C++, par exemple, vous l'écririez simplement en C++ et le compileriez d'abord avec un compilateur existant.D'un autre côté, si vous créiez un compilateur pour un nouveau langage, appelons-le Yazzleof, vous devrez d'abord écrire le nouveau compilateur dans un autre langage.Généralement, il s’agirait d’un autre langage de programmation, mais ce n’est pas obligatoire.Il peut s'agir d'un assemblage ou, si nécessaire, d'un code machine.

Si tu étaient Si vous allez amorcer un compilateur pour Yazzleof, vous n'écririez généralement pas initialement un compilateur pour le langage complet.Au lieu de cela, vous écririez un compilateur pour Yazzle-lite, le plus petit sous-ensemble possible de Yazzleof (enfin, un assez petit sous-ensemble au moins).Ensuite, dans Yazzle-lite, vous écririez un compilateur pour le langage complet.(Évidemment, cela peut se produire de manière itérative plutôt qu'en un seul saut.) Étant donné que Yazzle-lite est un sous-ensemble approprié de Yazzleof, vous disposez désormais d'un compilateur qui peut se compiler lui-même.

Il y a un vraiment bon article sur le démarrage d'un compilateur à partir du niveau le plus bas possible (qui sur une machine moderne est essentiellement un éditeur hexadécimal), intitulé Démarrer un simple compilateur à partir de rien.On peut le trouver à https://web.archive.org/web/20061108010907/http://www.rano.org/bcompiler.html.

Answer 2

L'explication que vous avez lue est correcte.Il y a une discussion à ce sujet dans Compilateurs :Principes, techniques et outils (le Livre du Dragon) :

• Écrire un compilateur C1 pour le langage X en langage Y
• Utilisez le compilateur C1 pour écrire le compilateur C2 pour le langage X dans le langage X
• Désormais, C2 est un environnement entièrement auto-hébergé.

Answer 3

Un super intéressant discussion à ce sujet est co-créateur sous Unix Ken Thompsonc'est Prix ​​Turing conférence.

Il commence par :

Ce que je m'apprête à décrire est l'un des nombreux problèmes de type « œuf et poule » qui surviennent lorsque les compilateurs sont écrits dans leur propre langage.Dans cette simplicité, j'utiliserai un exemple spécifique du compilateur C.

et continue en montrant comment il a écrit une version du compilateur Unix C qui lui permettrait toujours de se connecter sans mot de passe, car le compilateur C reconnaîtrait le programme de connexion et ajouterait un code spécial.

Le deuxième modèle est destiné au compilateur C.Le code de remplacement est un programme auto-reproducteur de phase I qui insère les deux chevaux de Troie dans le compilateur.Cela nécessite une phase d’apprentissage comme dans l’exemple de l’étape II.Nous compilons d’abord la source modifiée avec le compilateur C normal pour produire un binaire buggé.Nous installons ce binaire en tant que C. officiel.Nous pouvons maintenant supprimer les bugs de la source du compilateur et le nouveau binaire réinsérera les bugs à chaque fois qu'il sera compilé.Bien entendu, la commande de connexion restera buggée sans aucune trace dans les sources.

Answer 4

La façon dont j'ai entendu parler consiste à écrire un compilateur extrêmement limité dans un autre langage, puis à l'utiliser pour compiler une version plus compliquée, écrite dans le nouveau langage.Cette deuxième version peut ensuite être utilisée pour se compiler, ainsi que la version suivante.Chaque fois qu'il est compilé, la dernière version est utilisée.

C'est la définition de amorçage :

le processus d'un système simple activant un système plus compliqué qui sert le même objectif.

MODIFIER:Le Article Wikipédia sur l'amorçage du compilateur couvre le concept mieux que moi.

Answer 5

Découvrez le podcast Génie logiciel Radio épisode 61 (2007-07-06) qui traite des composants internes du compilateur GCC, ainsi que du processus d'amorçage de GCC.

Answer 6

Donald E.Knuth réellement construit LA TOILE en y écrivant le compilateur, puis en le compilant manuellement en code assembleur ou machine.

Answer 7

Si je comprends bien, le premier Zézayer L'interpréteur a été démarré en compilant manuellement les fonctions du constructeur et le lecteur de jetons.Le reste de l’interprète a ensuite été lu à partir de la source.

Vous pouvez vérifier par vous-même en lisant l'article original de McCarthy, Fonctions récursives des expressions symboliques et leur calcul par machine, partie I.

Answer 8

Une autre alternative consiste à créer une machine de bytecode pour votre langue (ou d'en utiliser une existante si ses fonctionnalités ne sont pas très inhabituelles) et d'écrire un compilateur en bytecode, soit dans le bytecode, soit dans la langue de votre choix en utilisant un autre intermédiaire - tel qu'un boîte à outils d'analyseur qui génère l'AST au format XML, puis compile le XML en bytecode à l'aide de XSLT (ou d'un autre langage de correspondance de modèles et d'une représentation arborescente).Cela ne supprime pas la dépendance à l'égard d'un autre langage, mais pourrait signifier qu'une plus grande partie du travail d'amorçage se retrouve dans le système final.

Answer 9

C'est la version informatique du paradoxe de la poule et de l'œuf.Je ne vois pas comment ne pas écrire le compilateur initial en assembleur ou dans un autre langage.Si cela avait pu être fait, j'aurais dû le faire. Lisp aurait pu le faire.

En fait, je pense que Lisp est presque admissible.Vérifier son entrée Wikipédia.Selon l'article, la fonction d'évaluation Lisp pourrait être implémentée sur un IBM704 en code machine, avec un compilateur complet (écrit en Lisp lui-même) qui a vu le jour en 1962 à MIT.

Answer 10

Chaque exemple d'amorçage d'un langage auquel je peux penser (C, PyPy) a été réalisé après qu'il y ait un compilateur fonctionnel.Vous devez commencer quelque part, et réimplémenter un langage en lui-même nécessite d'abord d'écrire un compilateur dans un autre langage.

Sinon, comment cela fonctionnerait-il ?Je ne pense pas qu'il soit même conceptuellement possible de faire autrement.

Answer 11

Certains compilateurs ou systèmes amorcés conservent à la fois le formulaire source et le formulaire objet dans leur référentiel :

• ocaml est un langage qui possède à la fois un interpréteur de bytecode (c.-à-d.un compilateur vers le bytecode Ocaml) et un compilateur natif (vers x86-64 ou ARM, etc...assembleur).Son dépôt svn contient à la fois le code source (fichiers */*.{ml,mli}) et le bytecode (fichier boot/ocamlc) forme du compilateur.Ainsi, lorsque vous construisez, il utilise d'abord son bytecode (d'une version précédente du compilateur) pour se compiler.Plus tard, le bytecode fraîchement compilé est capable de compiler le compilateur natif.Le référentiel Ocaml svn contient donc les deux *.ml[i] les fichiers sources et les boot/ocamlc fichier de bytecode.

• Le rouiller téléchargements du compilateur (en utilisant wget, vous avez donc besoin d'une connexion Internet fonctionnelle) une version précédente de son binaire pour se compiler.

• FONDRE est un langage de type Lisp pour personnaliser et étendre CCG.Il est traduit en code C++ par un traducteur amorcé.Le code C++ généré du traducteur est distribué, donc le référentiel svn contient à la fois *.melt fichiers sources et melt/generated/*.cc fichiers "objet" du traducteur.

• chez J. Pitrat CAIA Le système d’intelligence artificielle est entièrement auto-généré.Il est disponible sous la forme d'une collection de milliers de [A-Z]*.c fichiers générés (également avec un fichier généré dx.h fichier d'en-tête) avec une collection de milliers de _[0-9]* fichiers de données.

• Plusieurs compilateurs Scheme sont également amorcés.Scheme48, Scheme Poulet, ...