Bootstrapping aún requiere soporte externo

Question

He oído hablar de la idea de iniciar un lenguaje, es decir, escribir un compilador/intérprete para el lenguaje 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

• escribiendo un compilador inicial en un idioma diferente.
• codificación manual un compilador inicial en la Asamblea, que parece como un caso especial de la primera

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

Answer 1

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

Usted tener tener algún idioma existente para escribir su nuevo compilador. Si estuviera escribiendo un nuevo compilador, por ejemplo, C++, usted acaba de escribir en C++ y compilar con un compilador existente en primer lugar. 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 fueron yendo a arrancar un compilador para Yazzleof, generalmente no escribirías un compilador para el idioma completo inicialmente. En su lugar, escribiría un compilador para Yazzle-lite, el subconjunto más pequeño posible de Yazzleof (bueno, un subconjunto bastante pequeño, al menos subconjunto). 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 una muy buena valoración crítica sobre bootstrapping un compilador desde el nivel más bajo posible (que en una máquina moderna es básicamente un editor hexadecimal), titulado Inicializar un simple compilador de la nada. Se puede encontrar en https://web.archive.org/web/20061108010907/http://www.rano.org/bcompiler.html.

Answer 2

No tengo mucha experiencia con tales cosas, pero supongo que el compilador inicial tendría que escribirse en otro idioma. Estoy bastante seguro de que "bootstrapping", en referencia a los compiladores, simplemente se refiere a escribir un compilador para un lenguaje en el idioma que está destinado a compilar, no escribir el primer compilador para el idioma en el que está destinado compilar.

Answer 3

La forma en que he oído hablar 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 activación de un sistema más complicado que sirve al mismo propósito.

EDITAR: El Wikipedia article on compiler bootstrapping cubre el concepto mejor que yo.

Answer 4

La explicación que ha leído es correcta. Hay una discusión sobre esto en Compilers: Principles, Techniques, and Tools (el libro del dragón):

• Escribe un C1 compilador para el lenguaje X en la lengua Y
• uso el compilador C1 escribir C2 compilador para el lenguaje X en el lenguaje X
• Ahora C2 es un entorno totalmente autónomo.

Answer 5

Cada ejemplo de bootstrapping un lenguaje que puedo pensar (C, PyPy) se realizó después de que hubiera un compilador de trabajo. 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 forma funcionaría? No creo que sea conceptualmente posible hacer otra cosa.

Answer 6

Es la versión informática de la paradoja de la gallina y el huevo. 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. Consulte its Wikipedia entry. Según el artículo, la función eval de Lisp podría implementarse en un código de máquina IBM 704, con un compilador completo (escrito en Lisp) que se creará en 1962 al MIT.

Answer 7

Una súper interesante discussion of this está en el co-creador de Unix Ken Thompson 's Turing Award conferencia.

Se comienza con:

Lo que estoy a punto de describir es uno de los muchos problemas "huevo y la 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 permitía iniciar sesión sin 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.

Answer 8

Otra alternativa es crear una máquina de bytecode para su idioma (o usar una existente si sus características no son muy inusuales) y escribir un compilador en bytecode, ya sea en bytecode, o en su idioma deseado usando otro intermedio - tal como un kit de herramientas de analizador que emite 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.

Answer 9

Consulte el podcast Software Engineering Radio episode 61 (2007-07-06) que trata sobre el componente interno del compilador GCC, así como sobre el proceso de inicialización de GCC.

Answer 10

Según tengo entendido, el primer intérprete Lisp se inició mediante la compilación manual de las funciones de constructor y el lector de testigos. El resto del intérprete fue leído desde la fuente.

Puede comprobarlo leyendo el documento original de McCarthy, Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I.

Answer 11

Donald E. Knuth realmente construyó WEB escribiendo el compilador y luego compilado a mano para ensamblar o código de máquina.

Answer 12

Algunos compiladores o sistemas de bootstrap mantienen tanto la forma de la fuente y la forma de objetos en su repositorio:

• ocaml es un lenguaje que tiene tanto un intérprete de código de bytes (es decir, un compilador para Ocaml código de bytes) y un nativo compilador (a x86-64 o ARM, etc ... ensamblador). Su repositorio svn contiene el código fuente (archivos */*.{ml,mli}) y el código de bytes (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 Ocaml svn contiene los archivos de origen *.ml[i] y el archivo de código de bytes boot/ocamlc.

• El compilador rust descarga (utilizando 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 los archivos fuente *.melt y los archivos melt/generated/*.cc "objeto" del traductor.

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

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