¿Por qué se escribió el primer compilador antes que el primer intérprete?

72

El primer compilador fue escrito por Grace Hopper en 1952, mientras que el intérprete Lisp fue escrito en 1958 por el estudiante de John McCarthy Steve Russell. Escribir un compilador parece un problema mucho más difícil que un intérprete. Si es así, ¿por qué se escribió el primer compilador seis años antes que el primer intérprete?

anguyen
fuente
67
porque había más necesidad de un compilador de un intérprete en el momento
trinquete monstruo
23
¿Para compilar el primer intérprete? : P (solo parcialmente en la mejilla, un intérprete es complejo (más que un simple compilador) y sería desagradable escribir uno eficiente en código máquina)
Vality
44
Si toma las instrucciones de ejecución de su CPU como interpretándolas, tal como lo veo (sin embargo, implementado a través del hardware), entonces la afirmación de que el primer intérprete fue escrito después del primer compilador no se cumple. Por cierto, sé que esto no ayuda con la pregunta / respuesta. Solo pretende ser un comentario interesante en un punto de vista diferente.
Pedro Henrique A. Oliveira
11
McCarthy no escribió el intérprete de LISP. McCarthy inventó un formalismo matemático. Steve Russell, uno de los estudiantes en el MIT AI Lab en ese momento, se dio cuenta de que podía escribir un intérprete para ejecutar los vuelos de fantasía de McCarthy, y el resto es historia.
John R. Strohm
55
De hecho, escuché que McCarthy creía que LISP no era implementable. Fue Russell quien se dio cuenta de que la función universal de McCarthy del manual LISP a) era un intérprete yb) era implementable.
Jörg W Mittag

Respuestas:

97

Escribir un compilador parece un problema mucho más difícil que un intérprete.

Eso podría ser cierto hoy, pero diría que no fue así hace unos 60 años. Algunas razones por las cuales:

  • Con un intérprete, debe mantenerlo tanto él como el programa en la memoria. En una era en la que 1kb de memoria era un lujo masivo, mantener baja la huella de memoria era clave. E interpretar requiere un poco más de memoria que ejecutar un programa compilado.
  • Las CPU modernas son extremadamente complejas con enormes catálogos de instrucciones. Así que escribir un buen compilador es realmente un desafío. Las CPU antiguas eran mucho más simples, por lo que incluso la compilación era más simple.
  • Los lenguajes modernos son mucho más complejos que los antiguos, por lo que incluso los compiladores son mucho más complejos. Los idiomas antiguos tendrían así compiladores más simples.
Eufórico
fuente
65
y sin un compilador, tendrías que escribir el intérprete en la asamblea
ratchet freak
34
Los primeros compiladores donde la gente. (Cuando las personas son intérpretes no necesitamos computadoras). Entonces alguien debe haber considerado escribir un compilador en un lenguaje compilado (los únicos que tenían, pero a medida que el tiempo compilaba a mis humanos).
ctrl-alt-delor
1
En realidad ... Hace poco leí que la computadora de orientación Apollo utilizada en los vuelos lunares de los años 60 tenía un intérprete: entrada de wiki "... el intérprete proporcionó muchas más instrucciones de las que AGC admitía de forma nativa ..." Supongo que este "intérprete" era más parecido al intérprete "Sweet 16" integrado en las viejas computadoras Apple II que algo como LISP.
Calphool
66
@ratchetfreak Y así fue. Como fueron los primeros compiladores.
RBarryYoung
3
@richard: Cuando las personas eran intérpretes / calculadoras, su título de trabajo se llamaba "computadora". Entonces, cuando las personas eran intérpretes, eran las computadoras, literalmente. El proyecto de Manhattan empleó miles de "computadoras" (título de trabajo real, en serio) a las cuales los físicos nucleares enviaron sus cálculos por correo para ser ejecutados. En realidad, el proyecto también empleó matemáticos que desglosaron los cálculos de los ingenieros que formularon los cálculos a partir de las teorías de los físicos para enviar las "computadoras".
slebetman
42

El punto fundamental es que el entorno de hardware informático de la década de 1950 lo hizo de tal manera que solo un compilador era factible dado el procesamiento orientado a lotes de las computadoras en ese entonces.

En ese momento, las mejores interfaces de usuario se limitaban principalmente a tarjetas perforadas e impresoras de teletipo . En 1961, el sistema SAGE se convirtió en la primera pantalla de tubo de rayos catódicos (CRT) en una computadora. Por lo tanto, la naturaleza interactiva de un intérprete no era preferible o natural hasta mucho más tarde.

Numerosas computadoras en la década de 1950 usaban interruptores del panel frontal para cargar instrucciones, y la salida era simplemente filas de lámparas / LED, y los aficionados incluso usaban interruptores y LED del panel frontal en la década de 1970. Tal vez estés familiarizado con el infame Altair 8800 .

Otras limitaciones de hardware también hicieron que los intérpretes fueran inviables. Hubo una disponibilidad extremadamente limitada de memoria primaria (por ejemplo, RAM) en las computadoras en la década de 1950. Antes del circuito integrado de semiconductores (que no llegó hasta 1958) la memoria se limitaba a la memoria de núcleo magnético o la memoria de línea de retardo que se medía en bits o palabras , sin prefijo. Combinado con la lentitud de la memoria de almacenamiento secundaria (p. Ej., Disco o cinta), se consideraría un desperdicio, si no inviable, tener mucha de la memoria utilizada para el intérprete, incluso antes de que se cargara el programa que se está interpretando.

Las limitaciones de memoria seguían siendo un factor importante cuando el equipo liderado por John Backus en IBM creó el compilador FORTRAN en 1954-57. Este innovador compilador tuvo éxito solo porque era un compilador optimizador .

La mayoría de las computadoras en la década de 1950 apenas tenían un sistema operativo, y mucho menos características modernas como el enlace dinámico y la administración de memoria virtual, por lo que la idea de un intérprete era demasiado radical y poco práctica en ese momento.

Apéndice

Los idiomas de la década de 1950 eran primitivos. Incluían solo un pequeño puñado de operaciones, a menudo influenciadas por las instrucciones del hardware subyacente o la definición del problema de su uso específico.

En ese momento, las computadoras rara vez eran computadoras de propósito general en el sentido en que pensamos en las computadoras de hoy. El hecho de que fueran reprogramables sin tener que reconstruirlo se consideraba un concepto revolucionario: anteriormente las personas habían estado utilizando máquinas electromecánicas (típicamente calculadoras) para calcular o calcular respuestas (la mayoría de las aplicaciones en la década de 1950 eran de naturaleza numérica).

Desde el punto de vista de la informática, los compiladores e intérpretes son traductores y tienen una complejidad aproximadamente igual de implementada.

mctylr
fuente
¿Las computadoras usaban teletipos antes de la llegada del tiempo compartido? Hubiera esperado que usaran impresoras de línea o carretes para grabar. De lo contrario, los 1-8 segundos que la computadora tendría que esperar después de cada línea de texto representaría un 1-8 segundos que la computadora podría haber estado, pero no estaba, haciendo algo útil.
supercat
2
@supercat: sí, se usaron teletipos, pero estaban lejos de ser "interactivos". La primera computadora que programé tenía una memoria que constaba de palabras de 18 bits, 1K de ellas. La memoria en sí era un tambor giratorio , así que cuando encendiste la computadora tenías que esperar hasta que la memoria se acelerara. Tenía un teletipo adjunto y usted podía A) leer un carácter escrito desde el teclado o el lector de cinta de papel (desde el punto de vista de la computadora, ambos eran iguales), B) escribir un carácter en la "impresora "del teletipo. Ah, buenos días, ¡GRANDES días ...! ¿ES MI GRUEL CÁLIDO AÚN?!?!? :-)
Bob Jarvis
@BobJarvis: ¿En qué año habría sido eso?
supercat
1
@supercat - 1973 - pero la computadora en cuestión (un EDP-18, de Educational Data Products) era relativamente mayor incluso entonces. Aún así, era lo que teníamos (y tener una computadora con la que meterse en la escuela secundaria a principios de mediados de los 70 era inusual), así que pensamos que era bastante sorprendente. :-)
Bob Jarvis
2
Esta es una respuesta mucho mejor y completa que la aceptada.
Jim Garrison
12

Los primeros lenguajes de programación fueron bastante simples (sin recurrencia, por ejemplo) y cercanos a la arquitectura de la máquina, que en sí era simple. La traducción fue entonces un proceso sencillo .

Un compilador era más simple como programa que un intérprete que tendría que mantener juntos tanto los datos para la ejecución del programa como las tablas para interpretar el código fuente. Y el intérprete ocuparía más espacio , por sí mismo, para el código fuente del programa y para las tablas simbólicas.

La memoria podría ser tan escasa (tanto por razones de costo como arquitectónicas) que los compiladores podrían ser programas independientes que sobrescribieron el sistema operativo (utilicé uno de estos). El sistema operativo tuvo que volver a cargarse después de compilar para ejecutar el programa compilado. ... lo que deja en claro que ejecutar un intérprete para trabajo real simplemente no era una opción .

Para ser verdad, la simplicidad requerida de los compiladores era tal que los compiladores no eran muy buenos (la optimización del código todavía estaba en la infancia, cuando se consideraba). El código de máquina escrito a mano tenía, al menos hasta finales de los años sesenta en algunos lugares, la reputación de ser significativamente más eficiente que el código generado por el compilador. Incluso había un concepto de relación de expansión de código , que comparaba el tamaño del código compilado con el trabajo de un muy buen programador. Por lo general, era mayor que 1 para la mayoría de los compiladores (¿todos?), Lo que significaba programas más lentos y, mucho más importante, programas más grandes que requerían más memoria. Esto seguía siendo un problema en los años sesenta.

El interés del compilador era la facilidad de programación, especialmente para los usuarios que no eran especialistas en computación, como los científicos en varios campos. Este interés no era el rendimiento del código. Pero aún así, el tiempo del programador se consideraba un recurso barato. El costo fue en tiempo de computadora, hasta 1975-1980, cuando el costo cambió de hardware a software. Lo que significa que incluso el compilador no fue tomado en serio por algunos profesionales .

El costo muy alto del tiempo de computadora fue otra razón para descalificar a los intérpretes , hasta el punto de que la idea misma habría sido ridícula para la mayoría de las personas.

El caso de Lisp es muy especial, porque era un lenguaje extremadamente simple que lo hacía factible (y la computadora se había vuelto un poco más grande en 58). Más importante aún, el intérprete de Lisp fue una prueba de concepto con respecto a la autodefinición de Lisp ( meta-circularidad ), independientemente de cualquier problema de usabilidad.

El éxito de Lisp se debe en gran parte al hecho de que esta autodefinición lo convirtió en un excelente banco de pruebas para estudiar estructuras de programación y diseñar nuevos lenguajes (y también por su conveniencia para la computación simbólica).

babou
fuente
3
Dios mío, qué audaz .
Pharap
@Pharap ¿Es ese estilo incorrecto? Mi propósito es hacer que la información clave sea más fácil de encontrar, al tiempo que permite un estilo más libre que la simple enumeración de hechos. Debo confesar que en realidad no parece muy efectivo en este sitio SE.
babou
@ anonymous-downvoter El voto negativo sin un comentario explicativo muestra que alguien puede ser estúpido. Sin embargo, no dice quién.
babou
4

No estoy de acuerdo con la premisa de la pregunta.

El primer compilador del Adm. Hopper (el A-0) se parecía más a un enlazador o un lenguaje macro. Ella almacenaba subrutinas en una cinta (a cada una se le asignaba un número) y sus programas se escribirían como una lista de subrutinas y argumentos. El compilador copiará las subrutinas solicitadas de la cinta y las volverá a ordenar en un programa completo.

Ella usó la palabra "compilar" en el mismo sentido que compila una antología de poemas: reunir varios artículos en un solo volumen.

Ese primer compilador no tenía un lexer o analizador, por lo que puedo decir, lo que lo convierte en un ancestro lejano de un compilador moderno. Más tarde creó otro compilador (el B-0, también conocido como FLOW-MATIC) con el objetivo de una sintaxis más parecida al inglés, pero no se completó hasta 1958 o 1959, casi al mismo tiempo que el intérprete Lisp.

Por lo tanto, creo que la pregunta en sí está un poco equivocada. Parece que los compiladores e intérpretes co-evolucionaron casi exactamente al mismo tiempo, sin duda debido al intercambio de ideas que habrían tenido muchos científicos pensando en la misma línea en esos días.

Una mejor respuesta con citas aquí: https://stackoverflow.com/a/7719098/122763 .

Mark E. Haase
fuente
3

La otra parte de la ecuación es que los compiladores eran una abstracción escalonada por encima de un ensamblador. Primero teníamos un código de máquina codificado. "Nosotros" éramos el ensamblador. Cada salto y desplazamiento, etc. se calcularon a mano en hexadecimal (u octal) y luego se perforaron en cinta de papel o tarjetas. Entonces, cuando los ensambladores llegaron a la escena, fue un gran ahorro de tiempo. El siguiente paso fueron los macro ensambladores. Eso le dio la capacidad de escribir una macro que se expandiría en un conjunto de instrucciones de máquina. Así que Fortran y Cobol fueron un gran paso adelante. La falta de recursos (almacenamiento, memoria y ciclos de CPU) significaba que los intérpretes de uso general tenían que esperar a que la tecnología creciera. La mayoría de los primeros intérpretes eran motores de código de bytes (como Java o CLR de hoy, pero con mucha menos capacidad). UCSD Pascal era un lenguaje muy popular (y rápido). MS Basic era un motor de código de bytes bajo el capó.

En términos de sobrecarga de instrucciones, dependía totalmente de qué procesador se estaba ejecutando. La industria pasó por una gran crisis RISC vs CISC por un tiempo. Personalmente escribí ensamblador para IBM, Data General, Motorola, Intel (cuando aparecieron), TI y muchos otros. Hubo una diferencia bastante significativa en los conjuntos de instrucciones, registros, etc. que influirían en lo que se requería para "interpretar" un código p.

Como referencia de tiempo, comencé a programar en la compañía telefónica alrededor de 1972.

Bill Brothers
fuente
2

Si no tiene todo en la memoria, el código compilado es mucho más rápido. No olvide que en estos tiempos las funciones se unieron al código compilado. Si no está compilando, no sabe qué funciones necesitará. Entonces, estás llamando a funciones desde ... ¡Oh, no desde el disco todavía, estamos en los primeros 50 lazos, sino desde las tarjetas! En tiempo de ejecución!

Por supuesto, es posible encontrar soluciones alternativas, pero aún no se encontraron, ya que los idiomas eran muy simples y no estaban tan lejos del código de máquina. Y compilar fue fácil y suficiente.

Gangnus
fuente
1

Antes de que se escribiera el primer compilador, la gente escribía código de ensamblador que era un gran progreso en comparación con el código binario simple. En ese momento, había un fuerte argumento de que el código compilado por un compilador sería menos eficiente que el código ensamblador; en ese momento, la relación de (costo de la computadora) con (costo del programador) era muy, muy diferente a la actual. Entonces hubo una fuerte resistencia contra los compiladores desde ese punto de vista.

Pero los compiladores son muchísimo más eficientes que los intérpretes. Si hubieras sugerido escribir un intérprete en ese momento, la gente hubiera pensado que estás loco. ¿Te imaginas comprar una computadora de un millón de dólares y luego desperdiciar el 90% de su poder para interpretar el código?

gnasher729
fuente
No sé mucho acerca de las computadoras de la década de 1950, pero al menos para las máquinas simples de von Neumann de las últimas décadas, la sobrecarga del intérprete sería de dos a cinco instrucciones (tal vez de cuatro a diez ciclos en total) por instrucción interpretada: decodificación, salto indirecto, tal vez decodificación argumentos adicionales Si hace que el conjunto de instrucciones interpretadas sea lo suficientemente alto (por lo que ejecuta varias instrucciones de máquina por instrucción de intérprete), esto sería inferior al 90% y quizás incluso aceptable. Ver también: Forth.
3
Antes de que se escribiera el primer compilador, la mayoría de los programas se escribían realmente en código de máquina real, no en lenguaje ensamblador (mnemónicos de códigos operativos).
mctylr
2
@delnan Esos sistemas funcionaron con relojes en el kiloHertz, por lo que desperdiciar una reducción de 3-5 veces en el rendimiento probablemente sea la diferencia entre que el programa se complete con éxito antes de que el sistema falle debido a una falla de hardware (es decir, un tubo de vacío roto) o no. Las fallas de hardware ocurrieron a diario en la década de 1950 si no recuerdo mal.
mctylr
delnan: muéstrame un intérprete que pueda interpretar con una sobrecarga de cinco instrucciones. Y Forth no es un lenguaje interpretado, es una abominación :-). Lo siento, me refiero a un lenguaje enhebrado. Algo así como BASIC toma miles de millones de instrucciones para interpretar una declaración.
gnasher729
@gnasher: En 1974, construí un intérprete BASIC de alto rendimiento para Keronix (ejem, clones de Data General Nova) que utilizaba un código P orientado a bytes para codificar la instrucción BASIC. Tomó alrededor de 25-50 instrucciones de máquina para "interpretar" un código p, 10 de ellos para la búsqueda de bytes en sí. (Hice un token basado en 1969 que tomó más porque tenía que volver a analizar las expresiones). Pero no fue y no es "gazillions".
Ira Baxter
1

Antes de que un programa de bucle pueda ser interpretado, debe almacenarse en un medio que pueda leerse repetidamente. En la mayoría de los casos, el único medio adecuado sería RAM. Dado que el código generalmente se ingresará en tarjetas perforadas que, para los idiomas legibles por humanos, es probable que estén en gran parte vacías, se debe realizar algún tipo de procesamiento sobre el código antes de que se almacene en la RAM. En muchos casos, procesar el texto de la tarjeta perforada en un formulario que sea adecuado para la ejecución directa por parte del procesador no es realmente más difícil que procesarlo en un formulario que pueda manejarse eficientemente a través de un intérprete.

Tenga en cuenta que el objetivo de los primeros compiladores no era producir un archivo de lenguaje de ensamblaje o código de objeto en el disco, sino más bien terminar el código en la RAM que estaba listo para ejecutarse. En realidad, esto es sorprendentemente fácil cuando no hay un sistema operativo que se interponga en el camino. Un compilador puede generar código a partir de un extremo de la memoria y asignar variables y objetivos de ramificación a partir del otro. Si una declaración está marcada con la etiqueta "1234", el compilador almacenará en la variable llamada "1234" una instrucción para saltar a la dirección de generación de código actual, creando esa variable si no existe. Una declaración "goto 1234" creará una variable "1234" si no existe, y luego saltará a esa variable [que con suerte tendrá un salto a la ubicación correcta almacenada antes de que se ejecute esa declaración].gotouna etiqueta que aún no se ha definido, ya que sabe cuándo gotocompila hacia dónde va a saltar: a una variable. Puede que esa no sea la forma más eficiente de generar código, pero es adecuada para el tamaño de los programas que se esperaba que manejaran las computadoras.

Super gato
fuente
1
¿Disco? Ummmm ... no. Cinta. Cintas grandes, lentas, de carrete a carrete. Y muchos de ellos. Recuerdo haber asistido a una conferencia dada por Grace Murray Hopper (doblemente interesante para mí porque yo era un especialista en análisis de sistemas Y un guardiamarina en el destacamento de la Marina ROTC en el campus, y CAPT Hopper era un oficial naval en servicio). Ella contó una historia en la que, dijo, se le ocurrió la idea de escribir partes no utilizadas de un programa para grabarlas, lo llamó "usar almacenamiento auxiliar". "Pero", dijo, "la idea no tuvo éxito hasta que IBM hizo lo mismo y lo llamó Memoria virtual". A CAPT Hopper realmente no le gustó IBM ... :-)
Bob Jarvis
@BobJarvis: No había considerado ese aspecto, pero el mismo diseño general de una pasada que se utilizaría para compilar código listo para ejecutar en RAM podría funcionar bien con una unidad de cinta; la salida del compilador iría a la cinta, luego la cinta se rebobinaría y leería en direcciones de memoria secuenciales y se ejecutaría directamente, sin necesidad de tener ninguna parte del compilador en la memoria al mismo tiempo.
supercat
0

Porque los intérpretes necesitan compiladores para funcionar.

La declaración anterior no es realmente cierta. Hablando estrictamente, puede hacer un intérprete sin usar o interactuar con un compilador. Pero los resultados de hacer esto no se parecerían mucho a lo que creo que quieres decir con esos términos.

En sentido estricto, los compiladores e intérpretes hacen cosas completamente diferentes. Un compilador lee el texto de alguna fuente y lo transforma en otro formato: lenguaje ensamblador, código de máquina, otro lenguaje de alto nivel, una estructura de datos o cualquier otra cosa. Mientras tanto, un intérprete toma una estructura de datos de algún tipo y realiza instrucciones basadas en ella.

Lo que tendemos a pensar como un "compilador" hoy en día es en realidad un compilador que se ha emparejado con un generador de código : un programa que toma datos de alguna fuente y emite código en algún formato según lo que ve. Es un uso bastante intuitivo para los compiladores, y fue una de las primeras cosas para las que se crearon los compiladores. Pero si lo miras de otra manera, esto parece muy similar a lo que hace un intérprete. Siempre genera código en lugar de realizar operaciones más generales, pero el principio es el mismo.

Si lo miramos desde el otro lado, un intérprete necesita obtener sus datos de alguna parte . Estos son solo datos, por lo que puede construirlos de la misma manera que construiría cualquier otro tipo de datos. Como estamos hablando de interpretación, parece natural que pueda construir sus datos según las instrucciones en un archivo de texto. Pero para hacer eso, necesitaría algo para leer en el texto y crear su estructura de datos, y eso es un compilador . Está conectado al intérprete en lugar de a un generador de código, pero de todos modos es un compilador.

Es por eso que los compiladores se escribieron primero. La idea de interpretar las estructuras de datos no era nueva incluso cuando se concibieron los compiladores, pero los compiladores eran el "eslabón perdido" que permitía a los programadores construir esas estructuras a partir del texto.

El más cuchara
fuente
El intérprete básico original para Apple] [fue, por lo que entiendo, traducido a mano al código de máquina y nunca existió en formato de código fuente legible por máquina. No estoy seguro de qué "compilador" dirías que se usó para producirlo.
supercat
@supercat: No sé cómo se produjo el intérprete básico que mencionas, pero no estoy hablando de compiladores utilizados para producir intérpretes. Estoy hablando de los compiladores que forman parte de los intérpretes. Como parte de su código, el intérprete de Apple] [BASIC necesita alguna forma de leer los archivos de texto que contienen código BASIC y crear un árbol de sintaxis a partir de ese texto, que luego se ejecuta. El código que hace esto es un compilador; no genera código de máquina, pero aún realiza las tareas de leer el código y traducirlo a otra forma.
The Spooniest
Los intérpretes típicos de microcomputadoras BASIC no producen nada ni remotamente parecido a un árbol de sintaxis. No estoy familiarizado con el intérprete BASIC original de Apple (llamado "integer BASIC") pero el intérprete BASIC implementado por Microsoft para Apple ("Applesoft BASIC"), Commodore y otras compañías almacenaron el texto del programa tal como está, excepto por dos cosas : (1) cada línea fue precedida por un número de línea de 16 bits y la dirección de 16 bits de la siguiente línea, y seguido por un byte cero; (2) cada palabra clave se reemplazó con un solo byte que tenía el bit alto establecido. Aparte de eso, las expresiones se analizaron ...
supercat
... carácter por carácter, de izquierda a derecha; una declaración como A = 1234 "convertiría los dígitos 1, 2, 3 y 4 en un número de coma flotante en tiempo de ejecución.
supercat
@supercat: Eso suena más cercano a un bytecode que a un árbol de sintaxis, entonces, estoy equivocado en ese particular. Pero el punto principal sigue en pie: el pseudo-bytecode aún debe construirse a partir de texto, y el código que hace esto es un compilador.
The Spooniest
-1

Otro factor: cuando se escribieron los primeros compiladores, el costo del tiempo de máquina era mucho más alto de lo que es ahora. Los intérpretes usan mucho más tiempo de máquina.

Loren Pechtel
fuente