Arranque (compiladores)

Proceso de escritura de un compilador autocompilador

En informática , el bootstrap 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 básica inicial del compilador (el compilador bootstrap ) en un lenguaje diferente (que podría ser lenguaje ensamblador); se desarrollan versiones expandidas sucesivas del compilador utilizando este subconjunto mínimo del lenguaje. El problema de compilar un compilador autocompilador se ha denominado el problema del huevo y la gallina en el diseño de compiladores, y el bootstrap es una solución a este problema. ^{[1] [2]}

El bootstrap es una práctica bastante común al crear un lenguaje de programación . Muchos compiladores para muchos lenguajes de programación son bootstrap, 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: ^{[3] [4] [5]}

• Etapa 0: preparación de un entorno con el que trabajará el compilador bootstrap . Aquí es donde se eligen el lenguaje fuente y el lenguaje de salida del compilador bootstrap. En el caso de una " máquina desnuda " (una que no tiene compilador para ningún lenguaje), el código fuente y el de salida se escriben como código binario de máquina o pueden crearse mediante una compilación cruzada en alguna otra máquina que no sea la de destino. De lo contrario, el compilador bootstrap se debe escribir en uno de los lenguajes de programación que existen en la máquina de destino y ese compilador generará algo que se pueda ejecutar en el destino, incluido un lenguaje de programación de alto nivel , un lenguaje ensamblador , un archivo de objeto o incluso código de máquina.
• Etapa 1: se produce el compilador bootstrap. Este compilador es suficiente para traducir su propio código fuente a un programa que se pueda ejecutar en la máquina de destino. En este punto, todo el desarrollo posterior se realiza utilizando el lenguaje definido por el compilador bootstrap y comienza la etapa 2.
• Etapa 2: el compilador de arranque produce un compilador completo. Esto se hace normalmente en etapas según sea necesario, por ejemplo, el compilador para la versión X del lenguaje podrá compilar características de la versión X+1, pero ese compilador en realidad no las usa. Una vez que se haya probado este compilador y pueda compilarse a sí mismo, 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 deben agregar más funciones, el trabajo se reanuda en la etapa 2, y el compilador completo actual de la etapa 3 reemplaza al compilador de arranque.

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

Ventajas

El arranque de 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 prueba documental .
• Los desarrolladores de compiladores y los informantes de errores solo necesitan saber 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 compilador mismo.
• Es una comprobación de coherencia exhaustiva, ya que debería poder reproducir su propio código objeto.

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

Métodos

Si se necesita compilar un compilador para el lenguaje X escrito en lenguaje X, se plantea el problema 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 lenguaje 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 inician algunos superconjuntos de Java , Haskell y el compilador inicial de Free Pascal .
• Se puede escribir un compilador que admita extensiones de lenguaje no estándar o características opcionales del lenguaje sin utilizar dichas extensiones y características, para que se pueda compilar con otro compilador que admita el mismo lenguaje base pero un conjunto diferente de extensiones y características. Las partes principales del compilador de C++ clang se escribieron en un subconjunto de C++ que se puede compilar tanto con g++ como con Microsoft Visual C++ . Las características avanzadas se escriben con algunas extensiones de GCC.
• El compilador para X se compila de forma cruzada a partir de otra arquitectura en la que ya existe un compilador para X; así es como los compiladores para C suelen trasladarse a otras plataformas. Este es también el método utilizado para Free Pascal después del arranque inicial.
• Escribir el compilador en X, luego compilarlo manualmente desde el código fuente (probablemente de una manera no optimizada) y ejecutarlo en el código para obtener un compilador optimizado. Donald Knuth utilizó esto para su sistema de programación basado en la WEB .

Los métodos para distribuir compiladores en código fuente incluyen proporcionar una versión portable del compilador en bytecode , de modo de iniciar el proceso de compilación del compilador con él mismo. El diagrama T es una notación que se utiliza para explicar estas técnicas de inicio del compilador. ^[6] En algunos casos, la forma más conveniente de hacer funcionar 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 del lenguaje que se auto-iniciaron.

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

Hart y Levin escribieron un compilador 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, pasó a ser autoalojado. ^[9]

El compilador tal como existe en la cinta del compilador estándar es un programa en lenguaje máquina que se obtuvo haciendo que la definición de expresión S del compilador trabajara sobre sí misma a través del intérprete.

—  Memorándum de la IA 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 prestada directamente la noción de ejecutar un programa sobre sí mismo como entrada, que también se utiliza en varias demostraciones en informática teórica , como la variación de la demostración de que el problema de parada es indecidible que utiliza el teorema de Rice .

Esfuerzos actuales

Debido a las preocupaciones de seguridad relacionadas con el ataque Trusting Trust (que implica que un compilador se modifique maliciosamente para introducir puertas traseras encubiertas en los programas que compila o incluso replicar la modificación maliciosa en futuras versiones del compilador mismo, 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 se corresponden. Estos incluyen el proyecto Bootstrappable builds ^{[10] y el proyecto Reproducible builds [11]} .

Véase también

• Hospedaje propio
• Auto-intérprete
• Automodificación indirecta
• Diagrama de lápida
• Metacompilador

Referencias

1. Reynolds, John H. (diciembre de 2003). "Bootstrapping a self-compiling compiler from machine X to machine Y". CCSC: Conferencia del Este. Journal of Computing Sciences in Colleges . 19 (2): 175–181. La idea de un compilador escrito en el lenguaje que compila plantea el viejo dilema del "huevo o la gallina": ¿de dónde viene el primero?
2. Glück, Robert (2012). "Bootstrapping de generadores de compiladores a partir de evaluadores parciales". En Clarke, Edmund; Virbitskaite, Irina; Voronkov, Andrei (eds.). Perspectivas de la informática de sistemas: 8.ª conferencia internacional en memoria de Andrei Ershov, PSI 2011, Novosibirsk, Rusia, 27 de junio – 1 de julio de 2011, Documentos revisados ​​seleccionados . Notas de clase en informática. Vol. 7162. Springer. págs. 125–141. doi :10.1007/978-3-642-29709-0_13. ISBN . 978-3-642-29708-3Comenzar presenta el problema del huevo y la gallina, familiar en la construcción de compiladores: se necesita un compilador para iniciar un compilador, y iniciar generadores de compiladores no es una excepción .
3. "Instalación de GCC: compilación". Proyecto GNU - Free Software Foundation (FSF) .
4. "rust-lang/rust: arranque". GitHub .
5. "Configuraciones de compilación avanzadas: documentación de LLVM 10". llvm.org .
6. Patrick D. Terry (1997). "3. Construcción de compiladores y arranque". Compiladores y generadores de compiladores: una introducción a C++ . International Thomson Computer Press. ISBN 1-85032-298-8. Archivado desde el original el 23 de noviembre de 2009.
7. Wirth, Niklaus (22 de febrero de 2021). "50 años de Pascal". Comunicaciones de la ACM . 64 (3). Association for Computing Machinery (ACM): 39–41. doi :10.1145/3447525. ISSN  0001-0782. S2CID  231991096.
8. Edmund Grimley-Evans (23 de abril de 2003). "Arrancando un compilador simple desde cero". homepage.ntlworld.com . Archivado desde el original el 3 de marzo de 2010.
9. 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 .
10. "Compilaciones que se pueden arrancar con bootstrappable". bootstrappable.org .
11. "Compilaciones reproducibles: un conjunto de prácticas de desarrollo de software que crean una ruta verificable de forma independiente desde el código fuente hasta el código binario". reproducible-builds.org .