compiler-construction bootstrapping

compiler construction - Bootstrapping todavía requiere soporte externo



compiler-construction (11)

He oído hablar de la idea de iniciar un lenguaje, es decir, escribir un compilador / intérprete para el idioma en sí mismo. Me preguntaba cómo se podría lograr esto y miré un poco, y vi a alguien decir que solo podía hacerlo cualquiera

  • escribiendo un compilador inicial en un idioma diferente.
  • codificar manualmente un compilador inicial en Assembly, que parece ser un caso especial del primero

Para mí, ninguno de estos parece ser en realidad el arranque de un lenguaje en el sentido de que ambos requieren apoyo externo. ¿Hay alguna manera de escribir realmente un compilador en su propio idioma?

¿Hay alguna manera de escribir realmente un compilador en su propio idioma?

Tienes que tener algún lenguaje existente para escribir tu nuevo compilador. Si estuvieras escribiendo un nuevo compilador de C ++, por ejemplo, simplemente escríbelo en C ++ y compíralo primero con un compilador existente. Por otro lado, si estuviera creando un compilador para un nuevo idioma, llamémoslo Yazzleof, primero tendría que escribir el nuevo compilador en otro idioma. En general, este sería otro lenguaje de programación, pero no tiene por qué serlo. Puede ser ensamblado, o si es necesario, código de máquina.

Si fuera a cargar un compilador para Yazzleof, generalmente no escribiría un compilador para el idioma completo inicialmente. En cambio, escribirías un compilador para Yazzle-lite, el subconjunto más pequeño posible de Yazzleof (bueno, un subconjunto bastante pequeño al menos). Luego, en Yazzle-lite, escribirías un compilador para el idioma completo. (Obviamente, esto puede ocurrir iterativamente en lugar de en un salto.) Yazzle-lite es un subconjunto propio de Yazzleof, ahora tiene un compilador que puede compilarse a sí mismo.

Hay un muy buen informe sobre el arranque de un compilador desde el nivel más bajo posible (que en una máquina moderna es básicamente un editor hexadecimal), titulado Bootstrapping de un compilador simple de la nada . Se puede encontrar en https://web.archive.org/web/20061108010907/http://www.rano.org/bcompiler.html .

Algunos compiladores o sistemas arrancados mantienen el formulario de origen y el formulario de objeto en su repositorio:

  • ocaml es un lenguaje que tiene un intérprete de ocaml (es decir, un compilador de ocaml Ocaml) y un compilador nativo (ensamblador x86-64 o ARM, etc ...). Su repositorio svn contiene el código fuente (archivos */*.{ml,mli} ) y el código de */*.{ml,mli} (archivo boot/ocamlc ) del compilador. Entonces, cuando lo compila, primero usa su bytecode (de una versión anterior del compilador) para compilarse. Más tarde, el bytecode recién compilado puede compilar el compilador nativo. Así que el repositorio de Ocaml svn contiene tanto los archivos fuente *.ml[i] archivo de código de boot/ocamlc .

  • El compilador de rust descarga (usando wget , por lo que necesita una conexión a Internet que funcione) una versión anterior de su binario para compilarse.

  • MELT es un lenguaje similar a Lisp para personalizar y ampliar GCC . Se traduce al código C ++ por un traductor bootstrapped. El código C ++ generado del traductor se distribuye, por lo que el repositorio svn contiene tanto los archivos fuente *.melt archivos melt/generated/*.cc "object" del traductor.

  • El sistema de inteligencia artificial CAIA de J.Pitrat es completamente autogenerado. Está disponible como una colección de miles de archivos generados [AZ]*.c (también con un archivo de encabezado dx.h generado) con una colección de miles de _[0-9]* archivos de datos.

  • Varios compiladores Scheme también son bootstrapped. Scheme48, Chicken Scheme, ...

Cada ejemplo de arranque de un lenguaje que puedo pensar ( C , PyPy ) se hizo después de que hubiera un compilador en funcionamiento. Tienes que empezar en alguna parte, y volver a implementar un idioma en sí mismo requiere primero escribir un compilador en otro idioma.

¿De qué otra manera podría funcionar? No creo que sea conceptualmente posible hacer otra cosa.

Es la versión informática de la paradoja del huevo y la gallina. No puedo pensar en una forma de no escribir el compilador inicial en ensamblador o en otro idioma. Si se hubiera podido hacer, debería haberlo hecho Lisp.

En realidad, creo que Lisp casi califica. Echa un vistazo a su entrada de Wikipedia . Según el artículo, la función eval de Lisp podría implementarse en una IBM 704 en código máquina, con un compilador completo (escrito en Lisp) que se crearía en 1962 en MIT .

La explicación que has leído es correcta. Hay una discusión sobre esto en Compiladores: Principios, técnicas y herramientas (el Libro del Dragón):

  • Escribir un compilador C1 para el lenguaje X en el lenguaje Y
  • Utilice el compilador C1 para escribir el compilador C2 para el lenguaje X en el lenguaje X
  • Ahora C2 es un entorno totalmente autónomo.

La forma en que he escuchado es escribir un compilador extremadamente limitado en otro idioma, luego usarlo para compilar una versión más complicada, escrita en el nuevo idioma. Esta segunda versión se puede usar para compilarse y la próxima versión. Cada vez que se compila, se utiliza la última versión.

Esta es la definición de bootstrapping:

el proceso de un sistema simple que activa un sistema más complicado que sirve para el mismo propósito.

EDITAR: El artículo de Wikipedia sobre el arranque del compilador cubre el concepto mejor que yo.

Otra alternativa es crear una máquina de códigos de bytes para su idioma (o utilizar una existente si sus características no son muy inusuales) y escribir un compilador en bytecode, ya sea en el bytecode, o en su idioma deseado utilizando otro intermedio, como un Paralizador de herramientas que da salida al AST como XML, luego compila el código XML a byte usando XSLT (u otro lenguaje de coincidencia de patrones y representación basada en árbol). No elimina la dependencia de otro idioma, pero podría significar que más del trabajo de arranque termina en el sistema final.

Una discusión muy interesante de esto es en la conferencia del Premio Turing del co-creador de Unix Ken Thompson .

Él comienza con:

Lo que voy a describir es uno de los muchos problemas de "huevo y gallina" que surgen cuando los compiladores se escriben en su propio idioma. En esta facilidad, usaré un ejemplo específico del compilador de C.

y procede a mostrar cómo escribió una versión del compilador de Unix C que siempre le permitiría iniciar sesión sin una contraseña, porque el compilador de C reconocería el programa de inicio de sesión y agregaría un código especial.

El segundo patrón está dirigido al compilador de C. El código de reemplazo es un programa de autorreproducción de la Etapa I que inserta ambos caballos de Troya en el compilador. Esto requiere una fase de aprendizaje como en el ejemplo de la Etapa II. Primero compilamos la fuente modificada con el compilador normal de C para producir un binario con errores. Instalamos este binario como el oficial C. Ahora podemos eliminar los errores del origen del compilador y el nuevo binario reinserta los errores cada vez que se compila. Por supuesto, el comando de inicio de sesión permanecerá con errores sin rastro en la fuente en cualquier lugar.

Donald E. Knuth en realidad creó WEB escribiendo el compilador y luego compiló a mano el código ensamblador o máquina.