¿Cómo puede compilarse un compilador?

168

Estoy investigando CoffeeScript en el sitio web http://coffeescript.org/ , y tiene el texto

El compilador de CoffeeScript está escrito en CoffeeScript

¿Cómo puede compilarse un compilador, o qué significa esta declaración?

AlexanderRD
fuente
14
Otro término para un compilador que puede compilarse es un self-hostingcompilador. Ver programmers.stackexchange.com/q/263651/6221
o
37
¿Por qué un compilador no debería poder compilarse?
user253751
48
Hay al menos dos copias del compilador involucrado. Una preexistente compila una nueva copia. El nuevo puede o no ser idéntico al anterior.
bdsl
12
También te puede interesar Git: su código fuente se rastrea, por supuesto, en un repositorio de Git.
Greg d'Eon
77
Esto es como preguntar "¿Cómo podría una impresora Xerox imprimir los esquemas en sí misma?" Los compiladores compilan el texto en código de bytes. Si el compilador puede compilar a cualquier código de byte utilizable, puede escribir el código del compilador en el idioma respectivo y luego pasar el código a través del compilador para generar la salida.
RLH

Respuestas:

219

La primera edición de un compilador no se puede generar a máquina a partir de un lenguaje de programación específico para él; Tu confusión es comprensible. El primer compilador podría construir una versión posterior del compilador con más características de lenguaje (con la fuente reescrita en la primera versión del nuevo idioma). Esa versión podría compilar el siguiente compilador, y así sucesivamente. Aquí hay un ejemplo:

  1. El primer compilador de CoffeeScript está escrito en Ruby, produciendo la versión 1 de CoffeeScript
  2. El código fuente del compilador CS se reescribe en CoffeeScript 1
  3. El compilador CS original compila el nuevo código (escrito en CS 1) en la versión 2 del compilador
  4. Se realizan cambios en el código fuente del compilador para agregar nuevas funciones de idioma
  5. El segundo compilador CS (el primero escrito en CS) compila el nuevo código fuente revisado en la versión 3 del compilador
  6. Repita los pasos 4 y 5 para cada iteración.

Nota: No estoy seguro exactamente cómo se numeran las versiones de CoffeeScript, eso fue solo un ejemplo.

Este proceso generalmente se llama bootstrapping . Otro ejemplo de un compilador de arranque es rustc, el compilador para el lenguaje Rust .

Ben N
fuente
55
La otra ruta para iniciar un compilador es escribir un intérprete para (un subconjunto) de su idioma.
Aron
Como una alternativa más al arranque con un compilador o intérprete escrito en otro idioma, la ruta de la vieja escuela sería ensamblar a mano la fuente del compilador. Chuck Moore explica cómo hacer esto para un intérprete de Forth en el capítulo 9, "Programas que arrancan", al final de la programación de un lenguaje orientado a problemas ( web.archive.org/web/20160327044521/www.colorforth.com/POL .htm ), basado en haberlo hecho dos veces antes a mano. La entrada de código aquí se realiza a través de un panel frontal que permite el almacenamiento directo de valores en direcciones de memoria controladas por conmutadores de bits.
Jeremy W. Sherman
59

En el artículo Reflections on Trusting Trust , Ken Thompson, uno de los creadores de Unix, escribe una descripción fascinante (y fácilmente legible) de cómo se compila el compilador de C. Se pueden aplicar conceptos similares a CoffeeScript o cualquier otro lenguaje.

La idea de un compilador que compila su propio código es vagamente similar a una quine : código fuente que, cuando se ejecuta, produce como salida el código fuente original. Aquí hay un ejemplo de una quine de CoffeeScript. Thompson dio este ejemplo de una quine C:

char s[] = {
    '\t',
    '0',
    '\n',
    '}',
    ';',
    '\n',
    '\n',
    '/',
    '*',
    '\n',
    … 213 lines omitted …
    0
};

/*
 * The string s is a representation of the body
 * of this program from '0'
 * to the end.
 */

main()
{
    int i;

    printf("char\ts[] = {\n");
    for(i = 0; s[i]; i++)
        printf("\t%d,\n", s[i]);
    printf("%s", s);
}

A continuación, puede preguntarse cómo se le enseña al compilador que una secuencia de escape como '\n'representa el código ASCII 10. La respuesta es que en algún lugar del compilador C, hay una rutina que interpreta los literales de caracteres, que contiene algunas condiciones como esta para reconocer secuencias de barra invertida:

…
c = next();
if (c != '\\') return c;        /* A normal character */
c = next();
if (c == '\\') return '\\';     /* Two backslashes in the code means one backslash */
if (c == 'r')  return '\r';     /* '\r' is a carriage return */
…

Entonces, podemos agregar una condición al código anterior ...

if (c == 'n')  return 10;       /* '\n' is a newline */

... para producir un compilador que sepa que '\n'representa ASCII 10. Curiosamente, ese compilador, y todos los compiladores posteriores compilados por él , "conocen" esa asignación, por lo que en la próxima generación del código fuente, puede cambiar esa última línea en

if (c == 'n')  return '\n';

... y hará lo correcto! El 10viene del compilador, y ya no necesita ser definido explícitamente en el código fuente del compilador. 1

Ese es un ejemplo de una característica del lenguaje C que se implementó en el código C. Ahora, repita ese proceso para cada característica de lenguaje individual, y tiene un compilador de "autohospedaje": un compilador de C que está escrito en C.


1 El giro de la trama descrito en el documento es que, dado que al compilador se le pueden "enseñar" hechos como este, también se puede enseñar mal a generar ejecutables troyanados de una manera que sea difícil de detectar, y tal acto de sabotaje puede persistir en todos los compiladores producidos por el compilador contaminado.

200_success
fuente
77
Si bien esta es una información interesante, no creo que responda la pregunta. Sus ejemplos suponen que ya tiene un compilador de arranque, o ¿en qué lenguaje está escrito el compilador de C?
Arturo Torres Sánchez
9
@ ArturoTorresSánchez Diferentes explicaciones funcionan bien para diferentes personas. No pretendo reiterar lo que se ha dicho en otras respuestas. Más bien, encuentro que las otras respuestas hablan a un nivel más alto de lo que me gusta pensar. Personalmente, prefiero una ilustración concreta de cómo se agrega una sola característica, y dejar que el lector extrapole de eso, en lugar de una descripción superficial.
200_success
55
OK, entiendo tu perspectiva. Es solo que la pregunta es más "cómo puede compilarse un compilador si el compilador para compilar el compilador no existe" y menos "cómo agregar nuevas características a un compilador de arranque".
Arturo Torres Sánchez
17
La pregunta en sí es ambigua y abierta. Parece que algunas personas lo interpretan en el sentido de "¿cómo puede compilarse un compilador CoffeeScript?". La respuesta flippant, como se da en un comentario, es "¿por qué no debería ser capaz de compilarse, al igual que compila cualquier código?" Lo interpreto como "¿cómo puede existir un compilador de alojamiento propio?", Y he dado una ilustración de cómo se le puede enseñar a un compilador sobre una de sus características de lenguaje. Responde a la pregunta de una manera diferente, proporcionando una ilustración de bajo nivel de cómo se implementa.
200_success
1
@ ArturoTorresSánchez: "¿En qué lenguaje está escrito el compilador de C?" Hace mucho tiempo mantuve el compilador de C original anotado en el antiguo apéndice de K&R (el de IBM 360). Muchas personas saben que primero hubo BCPL, luego B, y que C era una versión mejorada de B. De hecho, había muchos partes de ese antiguo compilador que todavía estaban escritas en B y nunca se habían reescrito en C. Las variables tenían la forma de una sola letra / dígito, no se suponía que la aritmética del puntero se escalara automáticamente, etc. Ese antiguo código testificaba bootstrapping de B a C. El primer compilador "C" fue escrito en B.
Eliyahu Skoczylas
29

Ya ha recibido una muy buena respuesta, sin embargo, quiero ofrecerle una perspectiva diferente, que espero sea esclarecedora. Primero establezcamos dos hechos en los que ambos podemos estar de acuerdo:

  1. El compilador CoffeeScript es un programa que puede compilar programas escritos en CoffeeScript.
  2. El compilador CoffeeScript es un programa escrito en CoffeeScript.

Estoy seguro de que puede aceptar que tanto el número 1 como el número 2 son ciertos. Ahora, mira las dos declaraciones. ¿Ves ahora que es completamente normal que el compilador CoffeeScript pueda compilar el compilador CoffeeScript?

Al compilador no le importa lo que compila. Mientras sea un programa escrito en CoffeeScript, puede compilarlo. Y el compilador de CoffeeScript en sí mismo es un programa de este tipo. Al compilador CoffeeScript no le importa que sea el compilador CoffeeScript lo que está compilando. Todo lo que ve es un código CoffeeScript. Período.

¿Cómo puede compilarse un compilador, o qué significa esta declaración?

Sí, eso es exactamente lo que significa esa declaración, y espero que puedan ver ahora cómo esa declaración es verdadera.

Jörg W Mittag
fuente
2
No sé mucho sobre la secuencia de comandos de café, pero podría aclarar el punto 2 al afirmar que se escribió en la secuencia de comandos de café, pero desde entonces se compiló y luego es código de máquina. Y de todos modos, ¿podría explicar el problema del huevo y la gallina entonces? Si el compilador se escribió en un idioma para el que aún no se había escrito, ¿cómo puede incluso ejecutarse o compilarse?
barlop
66
Su declaración 2 es incompleta / inexacta y muy engañosa. ya que como dice la primera respuesta, la primera no fue escrita en un script de café ... Eso es tan relevante para su pregunta. Y en cuanto a "¿Cómo puede compilarse un compilador, o qué significa esta declaración?" Dices "Sí", supongo que sí (aunque mi mente es un poco pequeña), veo que se usa para compilar versiones anteriores de sí mismo, en lugar de hacerlo. ¿Pero se usa también para compilarse? Supuse que sería inútil.
barlop
2
@barlop: cambie la declaración 2 a " Hoy , el compilador CoffeeScript es un programa escrito en CoffeeScript". ¿Eso te ayuda a entenderlo mejor? Un compilador es "simplemente" un programa que traduce una entrada (código) en una salida (programa). Entonces, si tiene un compilador para el lenguaje Foo, entonces escriba el código fuente para un compilador Foo en el lenguaje Foo mismo, y alimente esa fuente a su primer compilador Foo, obtendrá un segundo compilador Foo como salida. Esto lo hacen muchos lenguajes (por ejemplo, todos los compiladores de C que conozco están escritos en ... C).
DarkDust
3
El compilador no puede compilarse a sí mismo. El archivo de salida no es la misma instancia que el compilador que produce el archivo de salida. Espero que puedan ver ahora cómo esa afirmación es falsa.
pabrams
3
@pabrams ¿Por qué asumes eso? El resultado podría ser idéntico al compilador utilizado para producirlo. Por ejemplo, si compilo GCC 6.1 con GCC 6.1, obtengo una versión de GCC 6.1 compilada con GCC 6.1. Y luego, si lo uso para compilar GCC 6.1, también obtengo una versión de GCC 6.1 compilada con GCC 6.1, que debería ser idéntica (ignorando cosas como las marcas de tiempo).
user253751
9

¿Cómo puede compilarse un compilador, o qué significa esta declaración?

Significa exactamente eso. En primer lugar, algunas cosas a tener en cuenta. Hay cuatro objetos que debemos mirar:

  • El código fuente de cualquier programa arbitrario de CoffeScript
  • El ensamblado (generado) de cualquier programa arbitrario de CoffeScript
  • El código fuente del compilador CoffeScript.
  • El ensamblado (generado) del compilador CoffeScript

Ahora, debería ser obvio que puede usar el ensamblado generado (el ejecutable) del compilador CoffeScript para compilar cualquier programa arbitrario de CoffeScript y generar el ensamblado para ese programa.

Ahora, el compilador de CoffeScript en sí mismo es solo un programa arbitrario de CoffeScript y, por lo tanto, puede ser compilado por el compilador de CoffeScript.

Parece que su confusión se debe al hecho de que cuando crea su propio idioma nuevo, aún no tiene un compilador que puede usar para compilarlo. Esto seguramente parece un problema de huevo de gallina , ¿verdad?

Introduce el proceso llamado bootstrapping .

  1. Usted escribe un compilador en un lenguaje ya existente (en el caso de CoffeScript, el compilador original fue escrito en Ruby) que puede compilar un subconjunto del nuevo lenguaje
  2. Usted escribe un compilador que puede compilar un subconjunto del nuevo idioma en el nuevo idioma. Solo puede usar funciones de lenguaje que el compilador del paso anterior puede compilar.
  3. Utiliza el compilador del paso 1 para compilar el compilador del paso 2. Esto te deja con un ensamblado que se escribió originalmente en un subconjunto del nuevo idioma y que es capaz de compilar un subconjunto del nuevo idioma.

Ahora necesita agregar nuevas funciones. Digamos que solo ha implementado while-loops, pero también quiere for-loops. Esto no es un problema, ya que puede reescribir cualquier forbucle de tal manera que sea un whilebucle. Esto significa que solo puede usar while-loops en el código fuente de su compilador, ya que el ensamblado que tiene a mano solo puede compilarlos. Pero puede crear funciones dentro de su compilador que pueden pasar y compilar forbucles con él. Luego, usa el ensamblaje que ya tiene y compila la nueva versión del compilador. ¡Y ahora tiene un ensamblaje de un compilador que también puede analizar y compilar forbucles! Ahora puede volver al archivo fuente de su compilador y reescribir cualquier whilebucle que no quiera en forbucles.

Enjuague y repita hasta que se puedan compilar todas las características de idioma que desee con el compilador.

whiley forobviamente solo fueron ejemplos, pero esto funciona para cualquier nueva función de idioma que desee. Y entonces estás en la situación en la que se encuentra CoffeScript ahora: el compilador se compila solo.

Hay mucha literatura por ahí. Reflexiones sobre confiar en la confianza es un clásico que todos los interesados ​​en ese tema deben leer al menos una vez.

Poligoma
fuente
55
(La oración "El compilador CoffeeScript está escrito en CoffeeScript", es verdadera, pero "Un compilador puede compilarse a sí mismo" es falsa.)
pabrams
44
No, es completamente cierto. El compilador puede compilarse a sí mismo. Simplemente no tiene sentido. Digamos que tiene el ejecutable que puede compilar la versión X del idioma. Usted escribe un compilador que puede compilar la Versión X + 1, y compílelo con el compilador que tiene (que es la versión X). Terminas con un ejecutable que puede compilar la versión X + 1 del lenguaje. Ahora podría ir y usar ese nuevo ejecutable para volver a compilar el compilador. ¿Pero con qué fin? Ya tienes el ejecutable que hace lo que quieres. El compilador puede compilar cualquier programa válido, por lo que puede compilarse completamente.
Polygnome
1
De hecho, no es extraño construir varias veces, iirc modern freepascal construye el compilador un total de 5 veces.
plugwash
1
@pabrams Escribir "No tocar" y "Objeto caliente. No tocar" no influye en el mensaje deseado de la frase. Mientras la audiencia prevista del mensaje (Programadores) entienda el mensaje previsto de la frase (Una compilación del compilador puede compilar su fuente) independientemente de cómo esté escrito, esta discusión no tiene sentido. Tal como está ahora, su argumento no es válido. A menos que pueda demostrar que la audiencia del mensaje no son programadores, entonces, y solo entonces, está en lo correcto.
DarkDestry
2
@pabrams 'Good English' es un inglés que comunica ideas claramente a la audiencia destinataria, y de la manera en que lo hizo el escritor o el orador. Si la audiencia prevista son programadores, y los programadores lo entienden, es un buen inglés. Decir "La luz existe como partículas y ondas" es fundamentalmente equivalente a "La luz existe como fotones y ondas electromagnéticas". Para un físico, significan literalmente lo mismo. ¿Eso significa que siempre debemos usar la sesión más larga y clara? ¡No! Porque complica la lectura cuando el significado ya está claro para la audiencia prevista.
DarkDestry
7

Una pequeña pero importante aclaración.

Aquí el término compilador pasa por alto el hecho de que hay dos archivos involucrados. Uno es un ejecutable que toma como archivos de entrada escritos en CoffeScript y produce como archivo de salida otro ejecutable, un archivo de objeto enlazable o una biblioteca compartida. El otro es un archivo fuente de CoffeeScript que describe el procedimiento para compilar CoffeeScript.

Aplica el primer archivo al segundo, produciendo un tercero que es capaz de realizar el mismo acto de compilación que el primero (posiblemente más, si el segundo archivo define características no implementadas por el primero), por lo que puede reemplazar el primero si entonces deseo.

nbro
fuente
4
  1. El compilador de CoffeeScript se escribió por primera vez en Ruby.
  2. El compilador de CoffeeScript fue reescrito en CoffeeScript.

Como la versión Ruby del compilador CoffeeScript ya existía, se utilizó para crear la versión CoffeeScript del compilador CoffeeScript.

ingrese la descripción de la imagen aquí Esto se conoce como un compilador de alojamiento propio .

Es extremadamente común, y generalmente resulta del deseo de un autor de usar su propio idioma para mantener el crecimiento de ese idioma.

Trevor Hickey
fuente
3

No se trata de compiladores aquí, sino de expresividad del lenguaje, ya que un compilador es solo un programa escrito en algún idioma.

Cuando decimos que "un idioma está escrito / implementado" en realidad queremos decir que se implementa un compilador o intérprete para ese idioma. Hay lenguajes de programación en los que puede escribir programas que implementan el lenguaje (son compiladores / intérpretes para el mismo lenguaje). Estos idiomas se llaman idiomas universales .

Para poder entender esto, piense en un torno de metal. Es una herramienta utilizada para dar forma al metal. Es posible, usando solo esa herramienta, crear otra herramienta idéntica, creando sus partes. Por lo tanto, esa herramienta es una máquina universal. Por supuesto, el primero se creó utilizando otros medios (otras herramientas) y probablemente fue de menor calidad. Pero el primero se usó para construir otros nuevos con mayor precisión.

Una impresora 3D es casi una máquina universal. Puede imprimir toda la impresora 3D con una impresora 3D (no puede construir la punta que derrite el plástico).

Paul92
fuente
Me gusta la analogía del torno. Sin embargo, a diferencia de la analogía del torno, las imperfecciones en la primera iteración del compilador se pasan a todos los compiladores posteriores. Por ejemplo, una respuesta anterior menciona agregar una función de bucle for donde el compilador original solo usa bucles while. La salida comprende los bucles for, pero la implementación es con bucles while. Si la implementación original del ciclo while es defectuosa o ineficiente, ¡siempre lo será!
@ Física: calcule eso simplemente está mal. En ausencia de defectos de malicia, generalmente no se propagan al compilar un compilador.
plugwash
Las traducciones de ensamblaje ciertamente pasan de iteración a iteración hasta que la traducción de ensamblaje se arregle. Las nuevas características que se basan en características antiguas no cambian la implementación subyacente. Piénsalo un momento.
@plugwash Vea "Reflexiones sobre la confianza en la confianza" por Ken Thompson - ece.cmu.edu/~ganger/712.fall02/papers/p761-thompson.pdf
3

Prueba por inducción

Paso inductivo

La versión n + 1 del compilador está escrita en X.

Por lo tanto, puede ser compilado por la enésima versión del compilador (también escrita en X).

Caso base

Pero la primera versión del compilador escrita en X debe ser compilada por un compilador para X que esté escrito en un lenguaje que no sea X. Este paso se denomina bootstrapping del compilador.

Guy Argo
fuente
1
El primer compilador compilador para el lenguaje X se puede escribir fácilmente en X. Cómo es posible es que este primer compilador se pueda interpretar . (Por un intérprete de X escrito en un idioma que no sea X).
Kaz
0

Los compiladores toman una especificación de alto nivel y la convierten en una implementación de bajo nivel, como la que se puede ejecutar en hardware. Por lo tanto, no existe una relación entre el formato de la especificación y la ejecución real, además de la semántica del lenguaje objetivo.

Los compiladores cruzados se mueven de un sistema a otro, los compiladores entre idiomas compilan una especificación de idioma en otra especificación de idioma.

Básicamente, la compilación es una traducción justa, y el nivel suele ser de un nivel de lenguaje superior al de lenguaje inferior, pero hay muchas variantes.

Los compiladores de bootstrapping son los más confusos, por supuesto, porque compilan el lenguaje en el que están escritos. No olvide el paso inicial en bootstrapping que requiere al menos una versión mínima existente que sea ejecutable. Muchos compiladores de arranque trabajan primero en las características mínimas de un lenguaje de programación y agregan características adicionales de lenguaje complejo en adelante, siempre y cuando la nueva característica se pueda expresar usando las características anteriores. Si ese no fuera el caso, sería necesario que esa parte del "compilador" se desarrollara en otro idioma de antemano.

nbro
fuente