Bootstrapping (compiladores)

En informática, bootstrapping es la técnica para producir un compilador autocompilador, es decir, un compilador (o ensamblador) escrito en el lenguaje de programación fuente que pretende compilar. Se genera una versión central inicial del compilador (el compilador de arranque) en un lenguaje diferente (que podría ser un lenguaje ensamblador); Se desarrollan sucesivas versiones ampliadas del compilador utilizando este subconjunto mínimo del lenguaje. El problema de compilar un compilador autocompilador se ha denominado el problema del huevo o la gallina en el diseño de compiladores, y el arranque es una solución a este problema.

El arranque es una práctica bastante común al crear un lenguaje de programación. Se arrancan muchos compiladores para muchos lenguajes de programación, incluidos compiladores para BASIC, ALGOL, C, C#, D, Pascal, PL/I, Haskell, Modula-2, Oberon, OCaml, Common Lisp, Scheme, Go, Java, Elixir, Rust. , Python, Scala, Nim, Eiffel, TypeScript, Vala, Zig y más.

Proceso

Un proceso de arranque típico funciona en tres o cuatro etapas:

• Etapa 0: preparación de un ambiente para el bootstrap compilador para trabajar con. Aquí es donde se elige el lenguaje fuente y el lenguaje de salida del compilador de bootstrap. En el caso de una "máquina mala" (una donde no existe un compilador para cualquier idioma) la fuente y la salida se escriben como código de máquina binario, o puede ser creado por compilación cruzada en otra máquina que el objetivo. De lo contrario, el compilador de arranque se escribirá en uno de los idiomas de programación que existe en la máquina de destino, y que el compilador generará algo que pueda ejecutar en el objetivo, incluyendo un lenguaje de programación de alto nivel, un lenguaje de montaje, un archivo de objeto, o incluso código de máquina.
• Etapa 1: se produce el compilador de arranque. Este compilador es suficiente para traducir su propia fuente en un programa que se puede ejecutar en la máquina de destino. En este punto, todo desarrollo se realiza utilizando el lenguaje definido por el compilador de bootstrap, y comienza la etapa 2.
• Etapa 2: un compilador completo es producido por el compilador de arranque. Esto se hace normalmente en las etapas que sea necesario, por ejemplo, compilador para la versión X del idioma será capaz de compilar características de la versión X+1, pero que el compilador no utiliza realmente esas características. Una vez que este compilador ha sido probado y puede compilarse, ahora las características de la versión X+1 pueden ser utilizadas por versiones posteriores del compilador.
• Etapa 3: un compilador completo es producido por el compilador completo etapa 2. Si se van a añadir más características, se reanudará el trabajo en la etapa 2, con el compilador completo de la etapa actual 3 que reemplaza al compilador de arranque.

El compilador completo se construye dos veces para comparar las salidas de las dos etapas. Si son diferentes, ya sea el bootstrap o el compilador completo contiene un error.

Ventajas

Arrancar un compilador tiene las siguientes ventajas:

• Es una prueba no-trivial del lenguaje que se está compilando, y como tal es una forma de comida para perros.
• Los desarrolladores informáticos y reporteros de errores sólo necesitan saber el idioma que se está compilando.
• El desarrollo de los compiladores se puede realizar en el lenguaje de alto nivel que se está recopilando.
• Las mejoras en el back-end del compilador mejoran no sólo los programas generales sino también el compilador mismo.
• Es un control de consistencia integral ya que debe ser capaz de reproducir su propio código de objeto.

Tenga en cuenta que algunos de estos puntos suponen que el tiempo de ejecución del lenguaje también está escrito en el mismo idioma.

Métodos

Si uno necesita compilar un compilador para el lenguaje X escrito en el lenguaje X, existe la cuestión de cómo se puede compilar el primer compilador. Los diferentes métodos que se utilizan en la práctica incluyen:

• Implementando un intérprete o compilador para el lenguaje X en el lenguaje Y. Niklaus Wirth informó que escribió el primer compilador Pascal en Fortran.
• Otro intérprete o compilador de X ya ha sido escrito en otro idioma Y; así es como Scheme es a menudo arrancado.
• Las versiones anteriores del compilador fueron escritas en un subconjunto de X para el cual existió algún otro compilador; así es como algunos superconjuntos de Java, Haskell, y el compilador Pascal libre inicial son arrancados.
• Se puede escribir un compilador que admite extensiones de idioma no estándar o características de lenguaje opcional sin utilizar esas extensiones y características, para que pueda ser compilado con otro compilador que apoye el mismo idioma base pero un conjunto diferente de extensiones y características. Las partes principales del grupo compilador C++ fueron escritas en un subconjunto de C++ que puede ser compilado tanto por g++ como por Microsoft Visual C+++. Las características avanzadas están escritas con algunas extensiones GCC.
• El compilador para X se compila de otra arquitectura donde existe un compilador para X; así es como los compiladores para C son generalmente portados a otras plataformas. También este es el método utilizado para Free Pascal después del arranque inicial.
• Escribir el compilador en X; luego compilarlo de la fuente (probablemente de manera no optimizada) y ejecutarlo en el código para obtener un compilador optimizado. Donald Knuth utilizó esto para su sistema de programación de literatos WEB.

Los métodos para distribuir compiladores en el código fuente incluyen proporcionar una versión de código de bytes portátil del compilador, para iniciar el proceso de compilación del compilador consigo mismo. El diagrama T es una notación que se utiliza para explicar estas técnicas de arranque del compilador. En algunos casos, la forma más conveniente de ejecutar un compilador complicado en un sistema que tiene poco o ningún software implica una serie de ensambladores y compiladores cada vez más sofisticados.

Historia

Los ensambladores fueron las herramientas de primer idioma para arrancarse.

El primer lenguaje de alto nivel que proporcionó dicho arranque fue NELIAC en 1958. Los primeros lenguajes ampliamente utilizados en hacerlo fueron Burroughs B5000 Algol en 1961 y LISP en 1962.

Hart y Levin escribieron un compilador LISP en LISP en el MIT en 1962, probándolo dentro de un intérprete LISP existente. Una vez que mejoraron el compilador hasta el punto en que podía compilar su propio código fuente, se autohospedó.

El compilador como existe en la cinta de compilador estándar es un programa de lenguaje de máquina que se obtuvo al tener la definición de S-expresión del compilador en sí mismo a través del intérprete.

—AI Memo 39

Esta técnica sólo es posible cuando ya existe un intérprete para el mismo lenguaje que se va a compilar. Toma prestado directamente de la noción de ejecutar un programa sobre sí mismo como entrada, que también se utiliza en varias pruebas en informática teórica, como la variación de la prueba de que el problema de detención es indecidible que utiliza el teorema de Rice.

Esfuerzos actuales

Debido a preocupaciones de seguridad relacionadas con el Trusting Trust Attack (que implica que un compilador sea modificado maliciosamente para introducir puertas traseras encubiertas en los programas que compila o incluso replicar aún más la modificación maliciosa en versiones futuras del propio compilador, creando un ciclo perpetuo de desconfianza) y varios ataques contra la confiabilidad binaria, varios proyectos están trabajando para reducir el esfuerzo no solo para arrancar desde la fuente, sino también para permitir que todos verifiquen que la fuente y el ejecutable corresponden. Estos incluyen el proyecto de compilaciones Bootstrappable y el proyecto de compilaciones reproducibles.