En informática , bootstrapping es la técnica para producir un compilador autocompilable , es decir, un compilador (o ensamblador ) escrito en el lenguaje de programación fuente que pretende compilar. Se genera una versión del núcleo inicial del compilador (el compilador bootstrap ) en un lenguaje diferente (que podría ser lenguaje ensamblador); Las sucesivas versiones ampliadas del compilador se desarrollan utilizando este subconjunto mínimo del lenguaje. El problema de compilar un compilador autocompilable se ha denominado el problema del huevo o la gallina en el diseño del compilador, y el bootstrapping es una solución a este problema. [1] [2]
Muchos compiladores para muchos lenguajes de programación son bootstrap, incluidos compiladores para BASIC , ALGOL , C , C # , D , Pascal , PL / I , Factor , Haskell , Modula-2 , Oberon , OCaml , Common Lisp , Scheme , Go , Java , Elixir , Rust , Python , Scala , Nim , Eiffel , Vala y más.
Proceso
Un proceso típico de arranque funciona en tres o cuatro etapas: [3] [4] [5]
- Etapa 0: preparación de un entorno para que trabaje el compilador de arranque .
- Etapa 1: se produce el compilador bootstrap.
- Etapa 2: el compilador de arranque produce un compilador completo.
- Etapa 3: el compilador completo de la etapa 2 produce un compilador completo.
El compilador completo se construye dos veces para comparar los resultados de las dos etapas. Si son diferentes, el bootstrap o el compilador completo contienen un error. [3]
Ventajas
Bootstrapping un compilador tiene las siguientes ventajas: [6] [7]
- es una prueba no trivial del lenguaje que se está compilando y, como tal, es una forma de prueba interna .
- Los desarrolladores de compiladores y los informadores de errores solo 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 solo los programas de propósito general, sino también el compilador mismo.
- es una comprobación de coherencia completa, ya que debería poder reproducir su propio código objeto.
Tenga en cuenta que algunos de estos puntos asumen que el tiempo de ejecución del idioma 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 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 . [ cita requerida ]
- Ya se ha escrito otro intérprete o compilador para X en otro lenguaje Y; así es como Scheme suele iniciarse.
- Las versiones anteriores del compilador se escribieron en un subconjunto de X para el que existía algún otro compilador; así es como se arrancan algunos superconjuntos de Java , Haskell y el compilador Free Pascal inicial .
- Se puede escribir un compilador que admita extensiones de lenguaje no estándar o características de lenguaje opcionales sin usar esas extensiones y características, para permitir que se compile con otro compilador que admita el mismo lenguaje base pero con un conjunto diferente de extensiones y características. Las partes principales del clang del compilador de C ++ se escribieron en un subconjunto de C ++ que puede ser compilado tanto por g ++ como por Microsoft Visual C ++ . Las funciones avanzadas están escritas con algunas extensiones de GCC.
- El compilador para X se compila de forma cruzada a partir de otra arquitectura donde existe un compilador para X; así es como los compiladores de C generalmente se trasladan a otras plataformas. Además, este es el método utilizado para Free Pascal después del bootstrap inicial.
- Escribiendo el compilador en X; luego compílelo manualmente desde la fuente (probablemente de una manera no optimizada) y ejecútelo en el código para obtener un compilador optimizado. Donald Knuth usó esto para su sistema de programación literaria WEB .
Los métodos para distribuir compiladores en 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. [7] En algunos casos, la forma más conveniente de hacer que un compilador complicado se ejecute 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 de lenguaje en iniciarse.
El primer lenguaje de alto nivel que proporcionó tal bootstrap fue NELIAC en 1958. Los primeros lenguajes ampliamente utilizados para 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 habían mejorado el compilador hasta el punto en que podía compilar su propio código fuente, se autohospedaba. [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 trabaje sobre sí mismo a través del intérprete.
- AI Memo 39 [9]
Esta técnica solo es posible cuando ya existe un intérprete para el mismo idioma que se va a compilar. Toma prestada directamente de la noción de ejecutar un programa en sí mismo como entrada, que también se utiliza en varias pruebas de la informática teórica , como la prueba de que el problema de la detención es indecidible.
Esfuerzos actuales
Debido a preocupaciones de seguridad con respecto al ataque de confianza 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 de compilaciones Bootstrappable [10] y el proyecto de compilaciones Reproducible. [11]
Ver también
- Autohospedaje
- Auto-intérprete
- Diagrama de lápida
- Metacompilador
Referencias
- ^ Reynolds, John H. (diciembre de 2003). "Bootstrapping de un compilador autocompilante 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 acertijo del "huevo o la gallina": ¿De dónde viene el primero?
- ^ Glück, Robert (2012). "Bootstrapping generadores de compiladores de evaluadores parciales". En Clarke, Edmund; 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 al 1 de julio de 2011, artículos seleccionados revisados . Apuntes de conferencias en Ciencias de la Computación. 7162 . Saltador. págs. 125-141. doi : 10.1007 / 978-3-642-29709-0_13 .
Comenzar presenta el problema del huevo y la gallina familiar de la construcción de compiladores: se necesita un compilador para iniciar un compilador, y los generadores de compiladores de arranque no son una excepción.
- ^ a b "Instalación de GCC: Edificio" . Proyecto GNU - Free Software Foundation (FSF) .
- ^ "rust-lang / rust: bootstrap" . GitHub .
- ^ "Configuraciones de compilación avanzadas - documentación LLVM 10" . llvm.org .
- ^ Compiladores y generadores de compiladores: una introducción con C ++. Patrick D. Terry 1997. International Thomson Computer Press. ISBN 1-85032-298-8
- ^ a b "Construcción y arranque del compilador" por PDTerry 2000. HTML Archivado el 23 de noviembre de 2009 en la Wayback Machine . PDF Archivado el 14 de diciembre de 2010 en Wayback Machine .
- ↑ "Bootstrapping a simple compiler from nothing" Archivado el 3 de marzo de 2010 en la Wayback Machine por Edmund GRIMLEY EVANS 2001
- ^ a b Tim Hart y Mike Levin. "AI Memo 39-El nuevo compilador" (PDF) . Archivado desde el original (PDF) el 24 de febrero de 2011 . Consultado el 23 de mayo de 2008 .
- ^ http://bootstrappable.org/
- ^ https://reproducible-builds.org/