Por que o primeiro compilador foi escrito antes do primeiro intérprete?

72

O primeiro compilador foi escrito por Grace Hopper em 1952, enquanto o intérprete Lisp foi escrito em 1958 pelo aluno de John McCarthy, Steve Russell. Escrever um compilador parece ser um problema muito mais difícil do que um intérprete. Se é assim, por que o primeiro compilador foi escrito seis anos antes do primeiro intérprete?

anguyen
fonte
67
porque havia mais necessidade de um compilador do que de um intérprete na época
ratchet freak
23
Para compilar o primeiro intérprete? : P (apenas parcialmente a língua na bochecha, um intérprete é complexa (mais do que um compilador simples) e seria desagradável para escrever um um eficiente em código de máquina)
Vality
4
Se você pegar sua CPU executando instruções como interpretá-las, que é a maneira que eu as vejo (no entanto implementada via hardware), a alegação de que o primeiro interpretador foi gravado depois que o primeiro compilador não se mantém. Btw, eu sei que isso não ajuda com a pergunta / resposta. É apenas um comentário interessante sobre um ponto de vista diferente.
Pedro Henrique A. Oliveira
11
McCarthy não escreveu o intérprete LISP. McCarthy inventou um formalismo matemático. Steve Russell, um dos estudantes do MIT AI Lab na época, percebeu que poderia escrever um intérprete para executar os voos de fantasia de McCarthy, e o resto é história.
John R. Strohm
5
De fato, ouvi dizer que McCarthy acreditava que o LISP não era implementável. Foi Russell quem percebeu que a função universal de McCarthy do manual LISP a) era um intérprete eb) era implementável.
Jörg W Mittag

Respostas:

97

Escrever um compilador parece ser um problema muito mais difícil do que um intérprete.

Isso pode ser verdade hoje, mas eu diria que não era o caso há 60 anos. Algumas razões pelas quais:

  • Com um intérprete, você deve manter ele e o programa na memória. Numa época em que 1kb de memória era um luxo enorme, manter a pegada de memória em execução baixa era essencial. E a interpretação requer um pouco mais de memória do que executar um programa compilado.
  • As CPUs modernas são extremamente complexas, com enormes catálogos de instruções. Portanto, escrever um bom compilador é realmente um desafio. As CPUs antigas eram muito mais simples, então até a compilação era mais simples.
  • As linguagens modernas são muito mais complexas que as antigas, portanto, mesmo os compiladores são muito mais complexos. Os idiomas antigos teriam, assim, compiladores mais simples.
Eufórico
fonte
65
e sem um compilador que você teria que escrever o intérprete na montagem
catraca aberração
34
Os primeiros compiladores onde as pessoas. (Quando as pessoas são intérpretes, não precisamos de computadores). Então alguém deve ter pensado em escrever um compilador em uma linguagem compilada (as únicas que eles tinham, mas à medida que o tempo compilava meus humanos).
ctrl-alt-Delor
11
Na verdade .... Li recentemente que o Computador de Orientação Apollo usado nos voos lunares dos anos 60 tinha um intérprete: entrada no wiki "... o intérprete forneceu muito mais instruções do que o AGC suportado originalmente ..." Suponho que esse "intérprete" fosse mais como o intérprete "Sweet 16" embutido em computadores Apple II antigos do que algo como LISP.
Calphool
6
@ratchetfreak E foi. Como foram os primeiros compiladores.
RBarryYoung
3
@richard: Quando as pessoas eram intérpretes / calculadoras, seu cargo era chamado de "computador". Então, quando as pessoas eram intérpretes, eram os computadores, literalmente. O projeto de Manhattan empregou milhares de "computadores" (cargo real, seriamente) para os quais os físicos nucleares enviaram seus cálculos por correio para serem executados. Na verdade, o projeto também empregou matemáticos que dividiram os cálculos com os engenheiros que formularam os cálculos a partir das teorias dos físicos para enviar os "computadores".
slebetman
42

O ponto fundamental é que o ambiente de hardware de computação da década de 1950 tornou tal apenas um compilador viável, dado o processamento de computadores orientado a lotes.

Naquela época, as melhores interfaces de usuário eram limitadas principalmente a cartões perfurados e impressoras de teletipo . Em 1961, o sistema SAGE se tornou o primeiro monitor de tubo de raios catódicos (CRT) em um computador. Portanto, a natureza interativa de um intérprete não era preferível ou natural até muito mais tarde.

Numerosos computadores na década de 1950 usavam interruptores do painel frontal para carregar instruções, e a saída era simplesmente filas de lâmpadas / LEDs, e os amadores até usavam interruptores e LEDs do painel frontal na década de 1970. Talvez você esteja familiarizado com o infame Altair 8800 .

Outras limitações de hardware também inviabilizaram os intérpretes. Havia uma disponibilidade extremamente limitada de memória primária (por exemplo, RAM) em computadores na década de 1950. Antes do circuito integrado de semicondutores (que não veio até 1958), a memória era limitada à memória do núcleo magnético ou à memória da linha de atraso, medida em bits ou palavras , sem prefixo. Combinado com a lentidão da memória de armazenamento secundário (por exemplo, disco ou fita), seria considerado um desperdício, se não inviável, ter grande parte da memória usada para o intérprete, mesmo antes do carregamento do programa.

As limitações de memória ainda eram um fator importante quando o líder da equipe John Backus na IBM criou o compilador FORTRAN em 1954-57. Este compilador inovador foi bem-sucedido apenas porque era um compilador de otimização .

A maioria dos computadores na década de 1950 mal possuía um sistema operacional, sem falar em recursos modernos, como vínculo dinâmico e gerenciamento de memória virtual; portanto, a ideia de um intérprete era radical demais e impraticável na época.

Termo aditivo

As línguas da década de 1950 eram primitivas. Eles incluíam apenas um pequeno punhado de operações, muitas vezes influenciadas pelas instruções do hardware subjacente ou pela definição do problema do uso direcionado.

Naquela época, os computadores raramente eram computadores de uso geral no sentido em que pensamos nos computadores hoje. O fato de serem reprogramáveis ​​sem a necessidade de reconstrução foi considerado um conceito revolucionário - anteriormente as pessoas usavam máquinas eletromecânicas (normalmente calculadoras) para calcular ou calcular respostas (a maioria das aplicações na década de 1950 era de natureza numérica).

Do ponto de vista da ciência da computação, compiladores e intérpretes são tradutores e têm aproximadamente a mesma complexidade em sua implementação.

mctylr
fonte
Os computadores usavam teletipos antes do advento do compartilhamento de tempo? Eu esperava que eles usassem impressoras de linha ou enrolassem em fita. Caso contrário, os 1-8 segundos que o computador teria que esperar após cada linha de texto representariam 1-8 segundos que o computador poderia estar - mas não estava - fazendo algo útil.
Supercat
2
@ supercat - sim, foram utilizados teletipos, mas estavam longe de ser "interativos". O primeiro computador que programei tinha uma memória composta por palavras de 18 bits - 1K delas. A memória em si era um tambor rotativo ; portanto, quando você ligou o computador, teve que esperar até que a memória acelerasse. Tinha um teletipo anexado e você podia A) ler um caractere digitado no teclado ou lido pelo leitor de fita de papel (do ponto de vista do computador, ambos eram iguais), B) escrever um caractere na "impressora" "do teletipo. Ah, ótimos dias - ótimos dias ..! MEU GRUEL ESTÁ AQUECIDO?!?!? :-)
Bob Jarvis
@ BobJarvis: Em que ano teria sido?
Supercat 29/07
11
@supercat - 1973 - mas o computador em questão (um EDP-18, da Educational Data Products) ainda era relativamente antigo. Ainda assim, era o que tínhamos (e ter qualquer computador para mexer na escola no início dos anos 70 era incomum), por isso achamos que era incrível. :-)
Bob Jarvis
2
Esta é uma resposta muito melhor e completa do que a aceita.
21419 Jim Garrison
12

As primeiras linguagens de programação eram bastante simples (sem recursão, por exemplo) e próximas à arquitetura da máquina, que por si só era simples. A tradução foi então um processo direto .

Um compilador era mais simples como um programa do que um intérprete que precisaria manter juntos os dados para a execução do programa e as tabelas para interpretar o código-fonte. E o intérprete ocuparia mais espaço , por si só, para o código-fonte do programa e para tabelas simbólicas.

A memória pode ser tão escassa (por razões de custo quanto de arquitetura) que os compiladores podem ser programas independentes que substituem o sistema operacional (usei um deles). O sistema operacional teve que ser recarregado após a compilação para executar o programa compilado. ... o que deixa claro que executar um intérprete para trabalho real simplesmente não era uma opção .

Para ser verdade, a simplicidade exigida dos compiladores era tal que os compiladores não eram muito bons (a otimização do código ainda estava na infância, quando considerada). O código de máquina escrito à mão tinha, pelo menos até o final dos anos sessenta em alguns lugares, a reputação de ser significativamente mais eficiente que o código gerado pelo compilador. Havia até um conceito de taxa de expansão de código que comparava o tamanho do código compilado ao trabalho de um programador muito bom. Geralmente era maior que 1 para a maioria dos compiladores (todos?), O que significava programas mais lentos e, muito mais importante, programas maiores que exigem mais memória. Isso ainda era um problema nos anos sessenta.

O interesse do compilador estava na facilidade de programação, especialmente para usuários que não eram especialistas em computação, como cientistas em vários campos. Esse interesse não era o desempenho do código. Mas, ainda assim, o tempo do programador era considerado um recurso barato. O custo foi no tempo do computador, até 1975-1980, quando o custo passou do hardware para o software. O que significa que mesmo o compilador não foi levado a sério por alguns profissionais .

O custo muito alto do tempo do computador foi mais um motivo para desqualificar os intérpretes , a tal ponto que a própria idéia teria sido ridícula para a maioria das pessoas.

O caso do Lisp é muito especial, porque era uma linguagem extremamente simples que o tornava viável (e o computador havia se tornado um pouco maior em 58). Mais importante, o intérprete Lisp era uma prova de conceito em relação à autodefinibilidade do Lisp ( meta-circularidade ), independentemente de qualquer questão de usabilidade.

O sucesso do Lisp é devido, em grande parte, ao fato de que essa autodefinibilidade o tornou um excelente banco de testes para estudar estruturas de programação e projetar novas linguagens (e também por sua conveniência para computação simbólica).

babou
fonte
3
Meu, que corajoso .
Pharap
@Pharap Esse estilo é impróprio? Meu objetivo é facilitar a localização de informações importantes, permitindo um estilo mais livre do que a simples enumeração de fatos. Devo confessar que realmente não parece muito eficaz neste site SE.
babou 30/07/2014
@ anonymous-downvoter A votação sem votos explicativos mostra que alguém pode ser estúpido. No entanto, não diz quem.
babou 30/07/2014
4

Eu discordo da premissa da pergunta.

O primeiro compilador do Adm. Hopper (o A-0) era mais como um vinculador ou uma linguagem macro. Ela armazenou sub-rotinas em uma fita (cada uma atribuiu um número) e seus programas seriam escritos como uma lista de sub-rotinas e argumentos. O compilador copiava as sub-rotinas solicitadas da fita e as reordena em um programa completo.

Ela usou a palavra "compilar" no mesmo sentido em que se compila uma antologia de poemas: coletando vários itens em um único volume.

Esse primeiro compilador não tinha um lexer ou analisador, tanto quanto posso dizer, o que o torna um ancestral distante de um compilador moderno. Mais tarde, ela criou outro compilador (o B-0, também conhecido como FLOW-MATIC) com o objetivo de uma sintaxe mais parecida com o inglês, mas não foi concluída até 1958 ou 1959 - na mesma época que o intérprete Lisp.

Portanto, acho que a pergunta em si está um pouco equivocada. Parece que compiladores e intérpretes co-evoluíram quase exatamente ao mesmo tempo, sem dúvida devido ao compartilhamento de idéias que teriam muitos cientistas pensando da mesma maneira naqueles dias.

Uma resposta melhor com citações aqui: https://stackoverflow.com/a/7719098/122763 .

Mark E. Haase
fonte
3

A outra parte da equação é que os compiladores eram uma abstração de etapa acima de um montador. Primeiro, tivemos o código da máquina codificado. "Nós" éramos o montador. Cada salto e deslocamento, etc., eram calculados manualmente em hexadecimal (ou octal) e depois perfurados em fita ou cartões de papel. Então, quando as montadoras entraram em cena, foi uma enorme economia de tempo. O próximo passo foram os montadores de macro. Isso deu a capacidade de escrever uma macro que se expandisse em um conjunto de instruções da máquina. Então Fortran e Cobol foram um grande passo à frente. A falta de recursos (armazenamento, memória e ciclos de CPU) significava que os intérpretes de uso geral tinham que esperar o crescimento da tecnologia. A maioria dos primeiros intérpretes eram mecanismos de código de bytes (como Java ou CLR de hoje, mas com muito menos capacidade). O UCSD Pascal era uma linguagem muito popular (e rápida). O MS Basic era um mecanismo de código de bytes oculto.

Em termos de sobrecarga de instruções, dependia totalmente de qual processador estava sendo executado. A indústria passou por um grande tumulto entre RISC e CISC por um tempo. Eu, pessoalmente, escrevi assembler para IBM, Data General, Motorola, Intel (quando eles apareceram), TI e vários outros. Havia uma diferença bastante significativa nos conjuntos de instruções, registradores etc. que influenciaria o que era necessário para "interpretar" um código-p.

Como referência temporal, comecei a programar na companhia telefônica por volta de 1972.

Bill Brothers
fonte
2

Se você não está mantendo tudo na memória, o código compilado é muito mais rápido. Não se esqueça, que nesses tempos as funções estavam associadas ao código compilado. Se você não está compilando, não sabe de que funções precisará. Então, você está chamando funções de ... Ah, ainda não do disco, estamos no início dos 50 laços, mas dos cartões! Em tempo de execução!

Obviamente, é possível encontrar soluções alternativas, mas elas ainda não foram encontradas, pois os idiomas eram muito simples e não muito distantes do código da máquina. E compilar foi fácil e suficiente.

Gangnus
fonte
1

Antes da criação do primeiro compilador, as pessoas escreviam o código do assembler, o que era um enorme progresso em comparação com o código binário comum. Na época, havia um forte argumento de que o código compilado por um compilador seria menos eficiente que o código do assembler - naquele momento, a relação de (custo do computador) e (custo do programador) era muito, muito diferente da atual. Portanto, houve forte resistência contra os compiladores desse ponto de vista.

Mas os compiladores são muito mais eficientes que os intérpretes. Se você tivesse sugerido escrever um intérprete naquele momento, as pessoas pensariam que você é louco. Você pode imaginar comprar um computador de um milhão de dólares e depois desperdiçar 90% de seu poder para interpretar código?

gnasher729
fonte
Não sei muito sobre os computadores dos anos 50, mas pelo menos para as máquinas simples de von Neumann das décadas posteriores, a sobrecarga do intérprete seria de duas a cinco instruções (talvez quatro a dez ciclos no total) por instrução interpretada: decodificação, salto indireto, talvez decodificação argumentos adicionais. Se você definir o conjunto de instruções interpretadas em nível suficientemente alto (para executar várias instruções da máquina por instrução do intérprete), isso seria menor que 90% e talvez até aceitável. Veja também: Adiante.
3
Antes da criação do primeiro compilador, a maioria dos programas era realmente escrita em código de máquina real, não em linguagem assembly (mnemônica de códigos op).
mctylr
2
@delnan Esses sistemas funcionavam com relógios no kiloHertz, portanto, desperdiçar uma redução de 3-5 vezes no desempenho provavelmente seria a diferença entre a conclusão do programa com sucesso antes que o sistema falhe devido a uma falha de hardware (ou seja, tubo de vácuo queimado) ou não. Falhas de hardware eram uma ocorrência diária nos anos 50, se bem me lembro.
Mctylr
delnan: mostre-me um intérprete que possa interpretar com uma sobrecarga de cinco instruções. E adiante não é uma linguagem interpretada, é uma abominação :-). Desculpe, quero dizer uma linguagem encadeada. Algo como o BASIC leva bilhões de instruções para interpretar uma afirmação.
gnasher729
@gnasher: Em 1974, construí um interpretador BASIC de alto desempenho para Keronix (ahem, clones Data General Nova) que usava um código P orientado a bytes para codificar a instrução BASIC. Foram necessárias cerca de 25 a 50 instruções da máquina para "interpretar" um pCode, 10 deles para o próprio byte buscar. (Eu fiz um baseado em token em 1969 que levou mais tempo porque precisou analisar novamente as expressões). Mas não era e nem "gazilhões".
Ira Baxter
1

Antes que um programa de loop possa ser interpretado, ele deve ser armazenado em uma mídia que pode ser lida repetidamente. Na maioria dos casos, o único meio adequado seria a RAM. Como o código normalmente é inserido em cartões perfurados que - para idiomas legíveis por humanos - provavelmente estão vazios, algum tipo de processamento deve ser executado no código antes que ele seja armazenado na RAM. Em muitos casos, processar o texto do cartão perfurado em um formato adequado para execução direta pelo processador não é realmente mais difícil do que processá-lo em um formato que possa ser tratado com eficiência por meio de um intérprete.

Observe que o objetivo dos primeiros compiladores não era produzir um arquivo de linguagem de montagem ou código de objeto em disco, mas terminar o código na RAM que estava pronto para ser executado. Isso é surpreendentemente fácil quando não há sistema operacional para atrapalhar. Um compilador pode gerar código começando em uma extremidade da memória e alocar variáveis ​​e destinos de ramificação começando na outra. Se uma instrução estiver marcada com o rótulo "1234", o compilador armazenará na variável chamada "1234" uma instrução para pular para o endereço de geração de código atual, criando essa variável se ela não existir. Uma instrução "goto 1234" criará uma variável "1234" se ela não existir e, em seguida, saltará para a variável [que esperamos ter um salto para o local apropriado armazenado nela antes da execução da instrução].gotoum rótulo que ainda não foi definido, pois sabe quando as gotocompilações para onde vai pular - para uma variável. Essa pode não ser a maneira mais eficiente de gerar código, mas é adequada para os tamanhos de programas que os computadores deveriam manipular.

supercat
fonte
11
Disco? Ummmm ... não. Fita. Fitas grandes, lentas, bobina a bobina. E muitos deles. Lembro-me de ir a uma palestra proferida por Grace Murray Hopper (duplamente interessante para mim porque eu era especialista em análise de sistemas E um soldado de marinha no destacamento da Marinha ROTC no campus, e o CAPT Hopper era um oficial da Marinha). Ela contou uma história em que, segundo ela, teve a idéia de gravar partes não utilizadas de um programa em fita - ela chamou de "usando armazenamento auxiliar". "Mas", ela disse, "a idéia não se concretizou até que a IBM fez a mesma coisa e a chamou de Memória Virtual". CAPT Hopper realmente não gostava IBM ... :-)
Bob Jarvis
@ BobJarvis: eu não tinha considerado esse aspecto, mas o mesmo design geral de uma passagem que seria usado para compilar código pronto para executar na RAM poderia funcionar bem com uma unidade de fita; a saída do compilador iria para a fita, depois a fita seria rebobinada e lida em endereços de memória seqüencial e executada diretamente, sem a necessidade de ter nenhuma parte do compilador na memória ao mesmo tempo.
Supercat 31/07
0

Porque intérpretes precisam de compiladores para funcionar.

A afirmação acima não é realmente verdadeira. A rigor, você pode criar um intérprete sem nunca usar ou interagir com um compilador. Mas os resultados de fazer isso não se pareceriam muito com o que eu acho que você quer dizer com esses termos.

No sentido estrito, compiladores e intérpretes fazem coisas totalmente diferentes. Um compilador lê o texto de alguma fonte e o transforma em outro formato: linguagem assembly, código de máquina, outra linguagem de alto nível, estrutura de dados ou qualquer outra coisa. Enquanto isso, um intérprete recolhe algum tipo de estrutura de dados e executa instruções com base nela.

Atualmente, o que pensamos como um "compilador" é na verdade um compilador que foi emparelhado com um gerador de código : um programa que coleta dados de alguma fonte e gera código em algum formato com base no que vê. Esse é um uso bastante intuitivo para compiladores e foi uma das primeiras coisas para as quais os compiladores foram criados. Mas se você olhar de outra maneira, isso parece muito semelhante ao que um intérprete faz. Ele sempre gera código em vez de executar operações mais gerais, mas o princípio é o mesmo.

Se olharmos para o outro lado, um intérprete precisa obter seus dados de algum lugar . São apenas dados, para que você possa construí-lo da mesma maneira que qualquer outro tipo de dados. Como estamos falando de interpretação, parece natural que você possa construir seus dados com base nas instruções em um arquivo de texto. Mas, para fazer isso, você precisa ler algo no texto e criar sua estrutura de dados, e isso é um compilador . Ele está ligado ao intérprete em vez de a um gerador de código, mas é um compilador da mesma forma.

É por isso que os compiladores foram escritos primeiro. A idéia de interpretar estruturas de dados não era nova, mesmo quando os compiladores foram concebidos, mas os compiladores eram o "elo perdido" que permitia aos programadores construir essas estruturas a partir de texto.

The Spooniest
fonte
O intérprete básico original para a Apple] [foi, pelo que entendi, traduzido à mão em código de máquina e nunca existiu no formato de código-fonte legível por máquina. Não tenho certeza de qual "compilador" você diria que foi usado para produzi-lo.
supercat
@ supercat: Não sei como o interpretador Basic que você mencionou foi produzido, mas não estou falando de compiladores usados ​​para produzir intérpretes. Estou falando dos compiladores que fazem parte dos intérpretes. Como parte de seu código, o intérprete [BASIC da Apple] precisa de alguma maneira de ler os arquivos de texto que contêm o código BASIC e criar uma árvore de sintaxe a partir desse texto, que ele executa. O código que faz isso é um compilador; ele não gera código de máquina, mas ainda executa as tarefas de leitura e conversão do código para outro formulário.
The Spooniest
Os intérpretes típicos do microcomputador BASIC não produzem nada nem remotamente parecido com uma árvore de sintaxe. Não estou familiarizado com o intérprete Apple BASIC original (chamado "inteiro BASIC"), mas o interpretador BASIC implementado pela Microsoft para Apple ("Applesoft BASIC"), Commodore e várias outras empresas armazenou o texto do programa como está, exceto por duas coisas : (1) cada linha foi precedida por um número de linha de 16 bits e o endereço de 16 bits da próxima linha e seguido por um byte zero; (2) cada palavra-chave foi substituída por um único byte com o bit alto definido. Fora isso, as expressões foram analisadas ... #
308
... caractere por caractere, da esquerda para a direita; uma instrução como A = 1234" seria converter os algarismos 1, 2, 3, e 4 em um número de ponto flutuante no tempo de execução.
supercat
@ supercat: Isso soa mais próximo de um bytecode do que de uma árvore de sintaxe; portanto, estou errado nesse particular. Mas o ponto principal ainda permanece: o pseudo-bytecode ainda deve ser construído a partir do texto, e o código que faz isso é um compilador.
The Spooniest
-1

Outro fator: quando os primeiros compiladores foram escritos, o custo do tempo da máquina era muito maior do que é agora. Os intérpretes usam muito mais tempo na máquina.

Loren Pechtel
fonte