Est-il possible de créer un interpréteur «bootstrapé» indépendant de l'interpréteur d'origine?

21

Selon Wikipedia, le terme "bootstrap" dans le contexte de l'écriture de compilateurs signifie ceci :

En informatique, le bootstrap est le processus d'écriture d'un compilateur (ou assembleur) dans le langage de programmation source qu'il a l'intention de compiler. L'application de cette technique conduit à un compilateur auto-hébergé.

Et je peux comprendre comment cela fonctionnerait. Cependant, l'histoire semble être un peu différente pour les interprètes. Maintenant, bien sûr, il est possible d'écrire un interprète auto-hébergeant. Ce n'est pas ce que je demande. Ce que je demande en fait, c'est: est-il possible de faire un interprète auto-hébergé indépendant de l'interprète original, premier . Pour expliquer ce que je veux dire, considérons cet exemple:

Vous écrivez votre première version interprète en langue X , et l'interprète est une nouvelle langue que vous créez, appelé Y . Vous utilisez d'abord le compilateur du langage X pour créer un exécutable. Vous pouvez maintenant interpréter les fichiers écrits dans votre nouvelle langue Y en utilisant l'interpréteur écrit en langue X .

Maintenant, pour autant que je comprends, pour être en mesure de « bootstrap » l'interprète que vous avez écrit dans un langage X , vous aurez besoin de réécrire l'interprète en langage Y . Mais voici le hic: même si vous réécrire l'interprète en toute langue Y , vous allez encore avoir besoin de l'original interprète que vous avez écrit dans le langage X . Parce que pour exécuter l'interpréteur dans la langue Y , vous allez devoir interpréter les fichiers source. Mais qu'est-ce qui va exactement interpréter les fichiers source? Eh bien, ça ne peut pas être rien, bien sûr, donc vous êtes obligé de toujours utiliser le premier interprète.

Peu importe le nombre de nouveaux interprètes que vous écrivez dans la langue Y , vous devrez toujours utiliser le premier interprète écrit en X pour interpréter les interprètes suivants. Cela semble être un problème simplement en raison de la nature des interprètes.

Cependant , d'un autre côté, cet article Wikipedia sur les interprètes parle en fait d'interprètes auto-hébergés . Voici un petit extrait qui est pertinent:

Un auto-interprète est un interpréteur de langage de programmation écrit dans un langage de programmation qui peut s'interpréter lui-même; un exemple est un interpréteur BASIC écrit en BASIC. Les auto-interprètes sont liés aux compilateurs auto-hébergeurs.

S'il n'existe aucun compilateur pour le langage à interpréter, la création d'un auto-interprète nécessite l'implémentation du langage dans un langage hôte (qui peut être un autre langage de programmation ou assembleur). En ayant un premier interprète comme celui-ci, le système est démarré et de nouvelles versions de l'interpréteur peuvent être développées dans la langue elle-même

Cependant, je ne sais toujours pas exactement comment cela serait fait. Il semble que, quoi qu'il arrive, vous serez toujours obligé d'utiliser la première version de votre interprète écrite dans la langue hôte.

Maintenant, l'article mentionné ci-dessus renvoie à un autre article dans lequel Wikipedia donne quelques exemples d'interprètes supposés auto-hébergés . Cependant, à y regarder de plus près, il semble que la principale partie "interprétative" de bon nombre de ces interprètes auto-hébergés (en particulier certains des plus courants tels que PyPy ou Rubinius) soit en réalité écrite dans d'autres langages tels que C ++ ou C.

Alors, ce que je décris ci-dessus est-il possible? Un interprète auto-hébergé peut-il être indépendant de son hôte d'origine? Si oui, comment cela se ferait-il exactement?

Christian Dean
la source

Réponses:

24

La réponse courte est: vous avez raison, vous avez toujours besoin d'un autre interprète écrit en X ou d'un compilateur de Y vers une autre langue pour laquelle vous avez déjà un interprète. Les interprètes s'exécutent, les compilateurs ne traduisent que d'une langue à une autre, à un moment donné de votre système, il doit y avoir un interprète… même si ce n'est que le CPU.

Peu importe le nombre de nouveaux interprètes que vous écrivez dans la langue Y , vous devrez toujours utiliser le premier interprète écrit en X pour interpréter les interprètes suivants. Cela semble être un problème simplement en raison de la nature des interprètes.

Correct. Ce que vous pouvez faire est d' écrire un compilateur de Y à X (ou une autre langue pour laquelle vous avez un interprète), et vous pouvez même le faire en Y . Ensuite, vous pouvez exécuter votre compilateur Y écrit en Y sur l' interpréteur Y écrit en X (ou sur l' interpréteur Y écrit en Y en cours d'exécution sur l' interpréteur Y écrit en X , ou sur l' interpréteur Y écrit en Y en cours d'exécution sur l' interpréteur Y écrit en Y courant sur le Yinterprète écrit en X , ou… à l'infini) pour compiler votre interprète Y écrit en Y vers X , afin de pouvoir ensuite l'exécuter sur un interpréteur X. De cette façon, vous vous êtes débarrassé de votre interprète Y écrit en X , mais maintenant vous avez besoin de l' interprète X (nous savons que nous en avons déjà un, cependant, car sinon nous ne pourrions pas exécuter l' interprète X écrit en Y ), et vous a dû d'abord écrire un compilateur Y- to- X .

Cependant , d'un autre côté, l'article de Wikipedia sur les interprètes parle en fait d'interprètes auto-hébergés. Voici un petit extrait qui est pertinent:

Un auto-interprète est un interpréteur de langage de programmation écrit dans un langage de programmation qui peut s'interpréter lui-même; un exemple est un interpréteur BASIC écrit en BASIC. Les auto-interprètes sont liés aux compilateurs auto-hébergeurs.

S'il n'existe aucun compilateur pour le langage à interpréter, la création d'un auto-interprète nécessite l'implémentation du langage dans un langage hôte (qui peut être un autre langage de programmation ou assembleur). En ayant un premier interprète comme celui-ci, le système est démarré et de nouvelles versions de l'interpréteur peuvent être développées dans la langue elle-même

Cependant, je ne sais toujours pas exactement comment cela serait fait. Il semble que, quoi qu'il arrive, vous serez toujours obligé d'utiliser la première version de votre interprète écrite dans la langue hôte.

Correct. Notez que l'article Wikipedia dit explicitement que vous avez besoin d'une deuxième implémentation de votre langue, et il ne dit pas que vous pouvez vous débarrasser de la première.

Maintenant, l'article mentionné ci-dessus renvoie à un autre article dans lequel Wikipedia donne quelques exemples d'interprètes supposés auto-hébergés. Cependant, à y regarder de plus près, il semble que la principale partie "interprétative" de bon nombre de ces interprètes auto-hébergés (en particulier certains des plus courants tels que PyPy ou Rubinius) soit en réalité écrite dans d'autres langages tels que C ++ ou C.

Encore une fois, c'est exact. Ce sont vraiment de mauvais exemples. Prenez Rubinius, par exemple. Oui, c'est vrai que la partie Ruby de Rubinius est auto-hébergée, mais c'est un compilateur, pas un interprète: il compile en code source Ruby en bytecode Rubinius. La partie interpréteur OTOH n'est pas auto-hébergée: elle interprète le bytecode Rubinius, mais elle est écrite en C ++. Donc, appeler Rubinius un "interprète auto-hébergé" est faux: la partie auto-hébergée n'est pas un interprète , et la partie interprète n'est pas auto-hébergée .

PyPy est similaire, mais encore plus incorrect: il n'est même pas écrit en Python en premier lieu, il est écrit en RPython, qui est un langage différent. Il est syntaxiquement similaire à Python, sémantiquement un "sous-ensemble étendu", mais il s'agit en fait d'un langage de type statique à peu près au même niveau d'abstraction que Java, et son implémentation est un compilateur avec plusieurs backends qui compile RPython en code source C, ECMAScript code source, code d'octet CIL, code d'octet JVM ou code source Python.

Alors, ce que je décris ci-dessus est-il possible? Un interprète auto-hôte peut-il être indépendant de son hôte d'origine? Si oui, comment cela se ferait-il exactement?

Non, pas tout seul. Vous devrez soit conserver l'interpréteur d'origine, soit écrire un compilateur et compiler votre auto-interprète.

Il existe des machines virtuelles méta-circulaires, telles que Klein (écrit en Self ) et Maxine (écrit en Java). Notez, cependant, qu'ici la définition de "méta-circulaire" est encore différente: ces VMs ne sont pas écrites dans le langage qu'elles exécutent: Klein exécute Self bytecode mais est écrit en Self, Maxine exécute JVM bytecode mais est écrit en Java. Cependant, le code source Self / Java de la machine virtuelle est en fait compilé en bytecode Self / JVM puis exécuté par la machine virtuelle, donc au moment où la machine virtuelle est exécutée, elle est dans le langage qu'elle exécute. Phew.

Notez également que cela est différent des machines virtuelles telles que SqueakVM et Jikes RVM . Jikes est écrit en Java et SqueakVM est écrit en Slang (un sous-ensemble syntaxique et sémantique typé de Smalltalk à peu près au même niveau d'abstraction qu'un assembleur de haut niveau), et les deux sont compilés statiquement en code natif avant d'être exécutés. Ils ne courent pas à l'intérieur d'eux-mêmes. Vous pouvez cependant les exécuter par -dessus eux-mêmes (ou par-dessus une autre VM / JVM Smalltalk). Mais ce n'est pas "méta-circulaire" dans ce sens.

Maxine et Klein, OTOH fontcourir à l'intérieur d'eux-mêmes; ils exécutent leur propre bytecode en utilisant leur propre implémentation. C'est vraiment époustouflant! Il permet des opportunités d'optimisation intéressantes, par exemple, puisque la machine virtuelle s'exécute avec le programme utilisateur, elle peut incorporer les appels du programme utilisateur à la machine virtuelle et vice versa, par exemple, appeler le garbage collector ou l'allocateur de mémoire peut être intégré à l'utilisateur et les rappels réfléchis dans le code utilisateur peuvent être intégrés dans la machine virtuelle. En outre, toutes les astuces d'optimisation intelligentes que les machines virtuelles modernes font, où elles regardent le programme d'exécution et l'optimisent en fonction de la charge de travail et des données réelles, la machine virtuelle peut appliquer ces mêmes astuces à elle-même pendant l'exécution du programme utilisateur pendant que le programme utilisateur exécute la charge de travail spécifique. En d'autres termes, la VM s'est hautement spécialisée pour celaprogramme particulier exécutant cette charge de travail particulière.

Cependant, remarquez que j'ai contourné l'utilisation du mot "interprète" ci-dessus et que j'ai toujours utilisé "exécuter"? Eh bien, ces machines virtuelles ne sont pas construites autour d'interprètes, elles sont construites autour de compilateurs (JIT). Un interprète a été ajouté à Maxine plus tard, mais vous avez toujours besoin du compilateur: vous devez exécuter la machine virtuelle une fois sur une autre machine virtuelle (par exemple, Oracle HotSpot dans le cas de Maxine), afin que la machine virtuelle puisse (JIT) se compiler elle-même. Dans le cas de Maxine, il compilera JIT sa propre phase de démarrage, puis sérialisera ce code natif compilé sur une image de VM d'amorçage et collera un chargeur de démarrage très simple devant (le seul composant de la machine virtuelle écrit en C, bien que ce soit juste pour plus de commodité). , cela pourrait aussi être en Java). Vous pouvez maintenant utiliser Maxine pour s'exécuter.

Jörg W Mittag
la source
Yeesh . Je n'ai jamais su que le monde des interprètes auto-hébergés était si collant! Merci d'avoir donné un bon aperçu.
Christian Dean
1
Haha, eh bien, pourquoi le monde devrait-il être moins hallucinant que le concept? ;-)
Jörg W Mittag
3
Je suppose que l'un des problèmes est que les gens jouent souvent vite et avec les langues impliquées. Par exemple, Rubinius est généralement appelé "Ruby in Ruby", mais ce n'est que la moitié de l'histoire. Oui, à proprement parler , le compilateur Ruby dans Rubinius est écrit en Ruby, mais la VM qui exécute le bytecode ne l'est pas. Et pire encore: PyPy est souvent appelé "Python en Python", sauf qu'il n'y a en fait pas une seule ligne de Python là-dedans. Le tout est écrit en RPython, qui est conçu pour être familier aux programmeurs Python, mais n'est pas Python . De même SqueakVM: il n'est pas écrit en Smalltalk, il…
Jörg W Mittag
… Est écrit en argot, ce qui, selon les personnes qui l'ont réellement codé, est encore pire que C dans ses capacités d'abstraction. Le seul avantage de Slang est qu'il s'agit d'un sous-ensemble approprié de Smalltalk, ce qui signifie que vous pouvez le développer (et exécuter et surtout déboguer la machine virtuelle) sur un puissant IDE Smalltalk.
Jörg W Mittag
2
Juste pour ajouter une autre complication: certains langages interprétés (par exemple FORTH, et éventuellement TeX) sont capables d'écrire une image mémoire chargeable du système en cours d'exécution, sous forme de fichier exécutable. En ce sens, ces systèmes peuvent alors fonctionner sans l'interpréteur d'origine. Par exemple, j'ai écrit une fois un interpréteur FORTH en utilisant une version 16 bits de FORTH pour «interpréter de manière croisée» une version 32 bits pour un processeur différent et pour l'exécuter sur un système d'exploitation différent. (Remarque, le langage FORTH inclut son propre assembleur, de sorte que la "FORTH VM" (qui ne contient généralement que 10 ou 20 instructions de code machine) peut être écrite dans FORTH elle-même.)
alephzero
7

Vous avez raison de noter qu'un interprète auto-hébergé nécessite toujours un interprète pour s'exécuter lui-même et ne peut pas être démarré dans le même sens qu'un compilateur.

Cependant, une langue auto-hébergée n'est pas la même chose qu'un interprète auto-hébergé. Il est généralement plus facile de construire un interpréteur que de construire un compilateur. Par conséquent, pour implémenter une nouvelle langue, nous pouvons d'abord implémenter un interpréteur dans une langue non liée. Ensuite, nous pouvons utiliser cet interpréteur pour développer un compilateur pour notre langage. Le langage est alors auto-hébergé, puisque le compilateur est interprété. Le compilateur peut alors se compiler lui-même et peut alors être considéré comme entièrement amorcé.

Un cas particulier de ceci est un runtime auto-hébergeant de compilation JIT. Il peut commencer par un interpréteur dans un langage hôte, qui utilise ensuite le nouveau langage pour implémenter la compilation JIT, après quoi le compilateur JIT peut se compiler lui-même. Cela ressemble à un interprète auto-hébergé, mais évite le problème des interprètes infinis. Cette approche est utilisée, mais n'est pas encore très courante.

Une autre technique connexe est un interpréteur extensible, où nous pouvons créer des extensions dans la langue en cours d'interprétation. Par exemple, nous pouvons implémenter de nouveaux opcodes dans la langue. Cela peut transformer un interpréteur bare-bones en un interprète riche en fonctionnalités, tant que nous évitons les dépendances circulaires.

Un cas qui se produit en fait assez fréquemment est la capacité du langage à influencer sa propre analyse, par exemple en tant que macros évaluées au moment de l'analyse. Étant donné que le langage de macro est le même que le langage en cours de traitement, il a tendance à être beaucoup plus riche en fonctionnalités que les langages de macro dédiés ou restreints. Cependant, il est correct de noter que la langue effectuant l'extension est une langue légèrement différente de la langue après l'extension.

Lorsque de «vrais» interprètes auto-hébergés sont utilisés, cela se fait généralement pour des raisons d'éducation ou de recherche. Par exemple, l'implémentation d'un interpréteur pour Scheme à l'intérieur de Scheme est une bonne façon d'enseigner les langages de programmation (voir SICP).

amon
la source