Bootstrapping (compiladores)

En informática , el 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. ^[1]^[2]

El bootstrapping es una práctica bastante común a la hora de crear un lenguaje de programación . Se arrancan muchos compiladores para muchos lenguajes de programación, incluidos los 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: ^[3]^[4]^[5]

Etapa 0: preparar un entorno para que funcione el compilador bootstrap . Aquí es donde se eligen el idioma de origen y el idioma de salida del compilador de arranque. En el caso de una " máquina básica " (una en la que no existe un compilador para ningún lenguaje), el origen y la salida se escriben como código de máquina binario , o pueden crearse mediante compilación cruzada en alguna otra máquina que no sea la de destino. De lo contrario, el compilador de arranque debe escribirse en uno de los lenguajes de programación que existen en la máquina de destino, y ese compilador generará algo que pueda ejecutarse en la máquina de destino, incluido un lenguaje de programación de alto nivel , un lenguaje ensamblador , un objeto. archivo , o incluso código de máquina.
Etapa 1: se produce el compilador bootstrap. Este compilador es suficiente para traducir su propia fuente en un programa que pueda ejecutarse en la máquina de destino. En este punto, todo el desarrollo posterior se realiza utilizando el lenguaje definido por el compilador de arranque y comienza la etapa 2.
Etapa 2: el compilador bootstrap produce un compilador completo. Por lo general, esto se hace en etapas según sea necesario; por ejemplo, el compilador de la versión X del lenguaje podrá compilar características de la versión X+1, pero ese compilador en realidad no usa esas características. Una vez que este compilador haya sido probado y pueda compilarse solo, ahora las características de la versión X+1 podrán usarse en versiones posteriores del compilador.
Etapa 3: el compilador completo de la etapa 2 produce un compilador completo. Si se van a agregar más funciones, el trabajo se reanuda en la etapa 2, con el compilador completo de la etapa 3 actual reemplazando al compilador de arranque.

El compilador completo se construye dos veces para comparar los resultados de las dos etapas. Si son diferentes, el programa de arranque o el compilador completo contienen un error. ^[3]

Ventajas

Arrancar un compilador tiene las siguientes ventajas: ^[6]

Es una prueba no trivial del lenguaje que se está compilando y, como tal, es una forma de dogfooding .
Los desarrolladores de compiladores y los que informan de errores sólo necesitan conocer el lenguaje que se está compilando.
El desarrollo del compilador se puede realizar en el lenguaje de nivel superior que se está compilando.
Las mejoras en el back-end del compilador mejoran no sólo los programas de propósito general sino también el propio compilador.
Es una verificación de coherencia integral, ya que debería poder reproducir su propio código 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 lenguaje.

Métodos

Si es necesario 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:

Implementación de un intérprete o compilador para el lenguaje X en el lenguaje Y. Niklaus Wirth informó que escribió el primer compilador de Pascal en Fortran . ^[7]
Ya se ha escrito otro intérprete o compilador para X en otro idioma Y; así es como a menudo se inicia Scheme .
Las versiones anteriores del compilador se escribieron en un subconjunto de X para el cual existía algún otro compilador; así es como se arrancan algunos superconjuntos de Java , Haskell y el compilador inicial de Free Pascal .
Un compilador que admita extensiones de lenguaje no estándar o características de lenguaje opcionales se puede escribir sin usar esas extensiones y características, para permitir su compilación con otro compilador que admita el mismo lenguaje base pero con un conjunto diferente de extensiones y características. Las partes principales del sonido metálico del compilador de C++ se escribieron en un subconjunto de C++ que puede compilarse tanto con g++ como con Microsoft Visual C++ . Las funciones avanzadas están escritas con algunas extensiones GCC.
El compilador para X se compila de forma cruzada desde otra arquitectura donde existe un compilador para X; Así es como los compiladores para C suelen trasladarse a otras plataformas. Además, este es el método utilizado para Free Pascal después del arranque inicial.
Escribiendo el compilador en X; luego, compílelo manualmente desde la fuente (probablemente de forma no optimizada) y ejecútelo en el código para obtener un compilador optimizado. Donald Knuth usó esto para su sistema de programación alfabetizado 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. ^[6] 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. ^[8]

Historia

Los ensambladores fueron las primeras herramientas lingüísticas que se iniciaron por sí mismas.

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ó. ^[9]

El compilador tal como existe en la cinta del compilador estándar es un programa en lenguaje de máquina que se obtuvo haciendo que la definición de expresión S del compilador funcione sobre sí mismo a través del intérprete.
- Memorándum AI 39 ^[9]

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. En contra de la confiabilidad binaria, varios proyectos están trabajando para reducir el esfuerzo no solo para arrancar desde el código fuente, sino también para permitir que todos verifiquen que el código fuente y el ejecutable corresponden. Estos incluyen el proyecto de compilaciones Bootstrappable ^[10] y el proyecto de compilaciones reproducibles. ^[11]

Ver también

Referencias

^ Reynolds, John H. (diciembre de 2003). "Arrancar un compilador autocompilador de la máquina X a la máquina Y". CCSC: Conferencia Este. Revista de Ciencias de la Computación en las Universidades . 19 (2): 175–181. La idea de un compilador escrito en el lenguaje que compila despierta el viejo enigma del "huevo o la gallina": ¿de dónde viene el primero?
^ Glück, Robert (2012). "Arranque de generadores de compiladores a partir de evaluadores parciales". En Clarke, Edmundo; Virbitskaite, Irina; Voronkov, Andrei (eds.). Perspectivas de la informática de sistemas: octava conferencia internacional en memoria de Andrei Ershov, PSI 2011, Novosibirsk, Rusia, 27 de junio - 1 de julio de 2011, artículos seleccionados revisados . Apuntes de conferencias sobre informática. vol. 7162. Saltador. págs. 125-141. doi :10.1007/978-3-642-29709-0_13. Comenzar presenta el problema del huevo y la gallina que resulta familiar en la construcción de compiladores: se necesita un compilador para arrancar un compilador, y arrancar generadores de compiladores no es una excepción.
^ ab "Instalación de GCC: Construcción". Proyecto GNU - Fundación para el Software Libre (FSF) .
^ "rust-lang/rust: arranque". GitHub .
^ "Configuraciones de compilación avanzadas: documentación de LLVM 10". llvm.org .
^ ab Patrick D. Terry (1997). "3. Construcción y arranque del compilador". Compiladores y generadores de compiladores: una introducción a C++ . Prensa informática internacional Thomson. ISBN 1-85032-298-8. Archivado desde el original el 23 de noviembre de 2009.
^ Wirth, Niklaus (22 de febrero de 2021). "50 años de Pascal". Comunicaciones de la ACM . Asociación de Maquinaria de Computación (ACM). 64 (3): 39–41. doi :10.1145/3447525. ISSN 0001-0782. S2CID 231991096.
^ Edmund Grimley-Evans (23 de abril de 2003). "Arrancar un compilador simple desde la nada". página de inicio.ntlworld.com . Archivado desde el original el 3 de marzo de 2010.
^ ab Tim Hart y Mike Levin. "AI Memo 39-El nuevo compilador" (PDF) . Archivado desde el original (PDF) el 13 de diciembre de 2020 . Consultado el 23 de mayo de 2008 .
^ "Compilaciones con arranque". bootstrappable.org .
^ "Compilaciones reproducibles: un conjunto de prácticas de desarrollo de software que crean una ruta verificable de forma independiente desde el código fuente al binario". reproducible-builds.org .