¿Es posible crear un intérprete "bootstrapped" independiente del intérprete original?

21

Según Wikipedia, el término "bootstrapping" en el contexto de escribir compiladores significa esto :

En informática, el bootstrapping es el proceso de escribir un compilador (o ensamblador) en el lenguaje de programación fuente que pretende compilar. La aplicación de esta técnica lleva a un compilador de alojamiento propio.

Y puedo entender cómo funcionaría eso. Sin embargo, la historia parece ser un poco diferente para los intérpretes. Ahora, por supuesto, es posible escribir un intérprete de alojamiento propio. Eso no es lo que estoy preguntando. Lo que realmente estoy preguntando es: ¿es posible hacer que un intérprete autohospedado sea independiente del primer intérprete original ? Para explicar lo que quiero decir, considere este ejemplo:

Usted escribe su primera versión intérprete en lenguaje X , y el intérprete trata de una nueva lengua que está creando, llamada S . Primero usa el compilador del lenguaje X para crear un ejecutable. Ahora puede interpretar los archivos escritos en su nuevo idioma Y usando el intérprete escrito en lenguaje X .

Ahora, por lo que yo entiendo, para ser capaz de "arranque" el intérprete que escribió en lengua X , que había necesidad de reescribir el intérprete en lenguaje Y . Pero aquí está el problema: incluso si lo hace volver a escribir toda la intérprete en lenguaje Y , usted todavía va a necesitar el original intérprete que escribió en lenguaje X . Debido a que para ejecutar el intérprete en el lenguaje Y , tendrá que interpretar los archivos de origen. Pero, ¿qué va a interpretar exactamente los archivos de origen? Bueno, no puede ser nada, por supuesto, por lo que te ves obligado a usar el primer intérprete.

No importa cuántos intérpretes nuevos escriba en el lenguaje Y , siempre tendrá que usar el primer intérprete escrito en X para interpretar a los intérpretes posteriores. Esto parece ser un problema simplemente debido a la naturaleza de los intérpretes.

Sin embargo , por otro lado, este artículo de Wikipedia sobre intérpretes en realidad habla sobre intérpretes independientes . Aquí hay un pequeño extracto que es relevante:

Un autointerpretador es un intérprete de lenguaje de programación escrito en un lenguaje de programación que puede interpretarse a sí mismo; Un ejemplo es un intérprete BASIC escrito en BASIC. Los autointerpretadores están relacionados con los compiladores de autohospedaje.

Si no existe un compilador para que el lenguaje sea interpretado, la creación de un autointerpretador requiere la implementación del lenguaje en un lenguaje anfitrión (que puede ser otro lenguaje de programación o ensamblador). Al tener un primer intérprete como este, el sistema se inicia y se pueden desarrollar nuevas versiones del intérprete en el lenguaje mismo.

Sin embargo, todavía no me queda claro cómo se haría exactamente esto. Parece que pase lo que pase, siempre se verá obligado a utilizar la primera versión de su intérprete escrita en el idioma del host.

Ahora, el artículo mencionado anteriormente enlaza con otro artículo en el que Wikipedia da algunos ejemplos de supuestos intérpretes de alojamiento propio . Sin embargo, después de una inspección más cercana, parece que la parte principal de "interpretación" de muchos de esos intérpretes independientes (especialmente algunos de los más comunes como PyPy o Rubinius) en realidad están escritos en otros lenguajes como C ++ o C.

Entonces, ¿es posible lo que describo anteriormente? ¿Puede un intérprete autohospedado ser independiente de su anfitrión original? Si es así, ¿cómo se haría esto exactamente?

Christian Dean
fuente

Respuestas:

24

La respuesta breve es: tiene razón en sus sospechas, siempre necesita otro intérprete escrito en X o un compilador de Y en algún otro idioma para el que ya tenga un intérprete. Los intérpretes se ejecutan, los compiladores solo traducen de un idioma a otro, en algún punto de su sistema, debe haber un intérprete ... incluso es solo la CPU.

No importa cuántos intérpretes nuevos escriba en el lenguaje Y , siempre tendrá que usar el primer intérprete escrito en X para interpretar a los intérpretes posteriores. Esto parece ser un problema simplemente debido a la naturaleza de los intérpretes.

Correcto. Lo que puede hacer es escribir un compilador desde Y al intérprete escrito en X X (u otro idioma para el que tenga un intérprete), e incluso se puede hacer eso en Y . Luego puede ejecutar su compilador Y escrito en Y en el intérprete Y escrito en X (o en el intérprete Y escrito en Y ejecutado en el intérprete Y escrito en X , o en el intérprete Y escrito en Y ejecutado en el intérprete Y escrito en Y corriendo en la Y , o ... hasta el infinito) para compilar su intérprete Y escrito en Y a X , para que luego pueda ejecutarlo en un intérprete X. De esa manera, se ha deshecho de su intérprete Y escrito en X , pero ahora necesita el intérprete X (sabemos que ya tenemos uno, ya que de lo contrario no podríamos ejecutar el intérprete X escrito en Y ), y usted tuvo que escribir un compilador Y -a- X primero.

Sin embargo , por otro lado, el artículo de Wikipedia sobre intérpretes en realidad habla sobre intérpretes independientes. Aquí hay un pequeño extracto que es relevante:

Un autointerpretador es un intérprete de lenguaje de programación escrito en un lenguaje de programación que puede interpretarse a sí mismo; Un ejemplo es un intérprete BASIC escrito en BASIC. Los autointerpretadores están relacionados con los compiladores de autohospedaje.

Si no existe un compilador para que el lenguaje sea interpretado, la creación de un autointerpretador requiere la implementación del lenguaje en un lenguaje anfitrión (que puede ser otro lenguaje de programación o ensamblador). Al tener un primer intérprete como este, el sistema se inicia y se pueden desarrollar nuevas versiones del intérprete en el lenguaje mismo.

Sin embargo, todavía no me queda claro cómo se haría exactamente esto. Parece que pase lo que pase, siempre se verá obligado a utilizar la primera versión de su intérprete escrita en el idioma del host.

Correcto. Tenga en cuenta que el artículo de Wikipedia dice explícitamente que necesita una segunda implementación de su idioma, y ​​no dice que puede deshacerse de la primera.

Ahora, el artículo mencionado anteriormente enlaza con otro artículo en el que Wikipedia da algunos ejemplos de supuestos intérpretes independientes. Sin embargo, después de una inspección más cercana, parece que la parte principal de "interpretación" de muchos de esos intérpretes independientes (especialmente algunos de los más comunes como PyPy o Rubinius) en realidad están escritos en otros lenguajes como C ++ o C.

De nuevo, correcto. Esos son realmente malos ejemplos. Tome Rubinius, por ejemplo. Sí, es cierto que la parte Ruby de Rubinius es autohospedada, pero es un compilador, no un intérprete: compila el código fuente de Ruby en el código de bytes de Rubinius. La parte del intérprete OTOH no está autohospedada: interpreta el código de bytes de Rubinius, pero está escrito en C ++. Por lo tanto, llamar a Rubinius un "intérprete alojado en sí mismo" es incorrecto: la auto-organizada parte no es un intérprete y el intérprete pieza no está alojado en sí mismo .

PyPy es similar, pero aún más incorrecto: ni siquiera está escrito en Python en primer lugar, está escrito en RPython, que es un lenguaje diferente. Es sintácticamente similar a Python, semánticamente un "subconjunto extendido", pero en realidad es un lenguaje de tipo estático aproximadamente en el mismo nivel de abstracción que Java, y su implementación es un compilador con múltiples backends que compila RPython en código fuente C, ECMAScript código fuente, código de bytes CIL, código de bytes JVM o código fuente Python.

Entonces, ¿es posible lo que describo anteriormente? ¿Puede un intérprete de host propio ser independiente de su host original? Si es así, ¿cómo se haría esto exactamente?

No, no solo. Debería conservar el intérprete original o escribir un compilador y compilar su propio intérprete.

No son algunos meta-circular de máquinas virtuales, tales como Klein (escrito en auto ) y Maxine (escrito en Java). Sin embargo, tenga en cuenta que aquí la definición de "meta-circular" es aún diferente: estas máquinas virtuales no están escritas en el lenguaje que ejecutan: Klein ejecuta Self bytecode pero está escrito en Self, Maxine ejecuta JVM bytecode pero está escrito en Java. Sin embargo, el código fuente Self / Java de la VM en realidad se compila en el código de bytes Self / JVM y luego se ejecuta por la VM, por lo que para cuando se ejecuta la VM, está en el idioma en que se ejecuta. Uf.

Tenga en cuenta también que esto es diferente de las máquinas virtuales como SqueakVM y Jikes RVM . Jikes está escrito en Java, y el SqueakVM está escrito en Slang (un subconjunto semántico y sintáctico de Smalltalk de tipo estático aproximadamente en el mismo nivel de abstracción que un ensamblador de alto nivel), y ambos se compilan estáticamente en código nativo antes de ejecutarse. No corren dentro de sí mismos. Usted puede , sin embargo, ejecutarlos en la parte superior de sí mismos (o encima de otro Smalltalk VM / JVM). Pero eso no es "meta-circular" en este sentido.

Maxine y Klein, OTOH hacencorrer dentro de ellos mismos; ejecutan su propio código de bytes utilizando su propia implementación. ¡Esto es realmente alucinante! Permite algunas oportunidades de optimización geniales, por ejemplo, dado que la VM se ejecuta junto con el programa del usuario, puede alinear las llamadas del programa del usuario a la VM y viceversa, por ejemplo, la llamada al recolector de basura o el asignador de memoria se pueden incorporar al usuario código, y las devoluciones de llamada reflexivas en el código de usuario pueden integrarse en la VM. Además, todos los trucos de optimización inteligentes que hacen las máquinas virtuales modernas, donde miran el programa en ejecución y lo optimizan dependiendo de la carga de trabajo y los datos reales, la máquina virtual puede aplicar esos mismos trucos a sí misma mientras ejecuta el programa de usuario mientras el programa de usuario está ejecutando la carga de trabajo específica. En otras palabras, la VM se especializó altamente para esoprograma particular que ejecuta esa carga de trabajo particular.

Sin embargo, ¿noté que eludí el uso de la palabra "intérprete" anterior y siempre usé "ejecutar"? Bueno, esas máquinas virtuales no se basan en intérpretes, sino en compiladores (JIT). Posteriormente, se agregó un intérprete a Maxine, pero siempre se necesita el compilador: debe ejecutar la VM una vez encima de otra VM (por ejemplo, Oracle HotSpot en el caso de Maxine), para que la VM pueda compilarse (JIT). En el caso de Maxine, JIT compilará su propia fase de arranque, luego serializará ese código nativo compilado en una imagen VM de arranque y pegará un cargador de arranque muy simple en el frente (el único componente de la VM escrito en C, aunque eso es solo por conveniencia , podría estar en Java también). Ahora puedes usar Maxine para ejecutarse.

Jörg W Mittag
fuente
Yeesh . ¡Nunca supe que el mundo de los intérpretes independientes era tan difícil! Gracias por dar una buena visión general sin embargo.
Christian Dean
1
Jaja, bueno, ¿por qué el mundo debería ser menos alucinante que el concepto? ;-)
Jörg W Mittag
3
Supongo que uno de los problemas es que las personas a menudo juegan rápido y suelto con los idiomas involucrados. Por ejemplo, Rubinius generalmente se llama "Ruby in Ruby", pero eso es solo la mitad de la historia. Sí, estrictamente hablando , el compilador de Ruby en Rubinius está escrito en Ruby, pero la VM que ejecuta el código de bytes no lo está. Y aún peor: PyPy a menudo se llama "Python en Python", excepto que en realidad no hay una sola línea de Python allí. Todo está escrito en RPython, que está diseñado para ser familiar para los programadores de Python, pero no es Python . Del mismo modo SqueakVM: no está escrito en Smalltalk, es ...
Jörg W Mittag
... está escrito en argot, que según las personas que realmente lo han codificado, es aún peor que C en sus capacidades de abstracción. La única ventaja que tiene Slang es que es un subconjunto adecuado de Smalltalk, lo que significa que puede desarrollarlo (y ejecutar y, lo más importante, depurar la VM) un poderoso IDE de Smalltalk.
Jörg W Mittag
2
Solo para agregar otra complicación: algunos lenguajes interpretados (por ejemplo, FORTH y posiblemente TeX) son capaces de escribir una imagen de memoria cargable del sistema en ejecución, como un archivo ejecutable. En ese sentido, dichos sistemas pueden ejecutarse sin el intérprete original. Por ejemplo, una vez escribí un intérprete FORTH usando una versión de FORTH de 16 bits para "interpretar de manera cruzada" una versión de 32 bits para una CPU diferente y para ejecutarla en un sistema operativo diferente. (Nota, el idioma ADELANTE incluye su propio ensamblador, por lo que el "ADELANTE VM" (que es normalmente sólo 10 o 20 instrucciones de código máquina) se puede escribir en Forth sí mismo.)
alephzero
7

Tiene razón al señalar que un intérprete de alojamiento propio todavía requiere un intérprete para ejecutarse, y no se puede arrancar en el mismo sentido que un compilador.

Sin embargo, un lenguaje autohospedado no es lo mismo que un intérprete autohospedado. Generalmente es más fácil construir un intérprete que construir un compilador. Por lo tanto, para implementar un nuevo lenguaje, primero podemos implementar un intérprete en un idioma no relacionado. Entonces podemos usar ese intérprete para desarrollar un compilador para nuestro lenguaje. El lenguaje se autohospeda, ya que se interpreta el compilador. El compilador puede entonces compilarse a sí mismo, y luego puede considerarse totalmente bootstrap.

Un caso especial de esto es un tiempo de ejecución de compilación JIT de alojamiento propio. Puede comenzar con un intérprete en un lenguaje host, que luego usa el nuevo lenguaje para implementar la compilación JIT, después de lo cual el compilador JIT puede compilarse. Esto se siente como un intérprete de alojamiento propio, pero evita el problema de los intérpretes infinitos. Se utiliza este enfoque, pero aún no es muy común.

Otra técnica relacionada es un intérprete extensible, donde podemos crear extensiones en el lenguaje que se está interpretando. Por ejemplo, podríamos implementar nuevos códigos de operación en el lenguaje. Esto puede convertir un intérprete básico en un intérprete rico en funciones, siempre que evitemos dependencias circulares.

Un caso que en realidad ocurre con bastante frecuencia es la capacidad del lenguaje para influir en su propio análisis, por ejemplo, como macros evaluadas en tiempo de análisis. Dado que el lenguaje macro es el mismo que el lenguaje que se procesa, tiende a ser mucho más rico en funciones que los lenguajes macro dedicados o restringidos. Sin embargo, es correcto notar que el idioma que realiza la extensión es un idioma ligeramente diferente al idioma después de la extensión.

Cuando se utilizan intérpretes autohospedados "reales", esto generalmente se hace por razones de educación o investigación. Por ejemplo, implementar un intérprete para Scheme dentro de Scheme es una forma genial de enseñar lenguajes de programación (ver SICP).

amon
fuente