Pergunta, questão:

"Certas propriedades de uma linguagem de programação podem exigir que a única maneira de obter o código escrito seja executada por interpretação. Em outras palavras, a compilação de um código de máquina nativo de uma CPU tradicional não é possível. Quais são essas propriedades?"

Compiladores: Princípios e Prática por Parag H. Dave e Himanshu B. Dave (2 de maio de 2012)

O livro não dá nenhuma pista sobre a resposta. Tentei encontrar a resposta em Conceitos de Linguagens de Programação (SEBESTA), mas sem sucesso. As buscas na Web também foram pouco úteis. Faz alguma ideia?

A distinção entre código interpretado e compilado é provavelmente uma ficção, conforme sublinhado pelo comentário de Raphael :

the claim seems to be trivially wrong without further assumptions: if there is
an interpreter, I can always bundle interpreter and code in one executable ...

O fato é que o código é sempre interpretado, por software, por hardware ou uma combinação de ambos, e o processo de compilação não pode dizer qual será.

O que você percebe como compilação é um processo de tradução de um idioma (para origem) para outro idioma (para destino). E, o intérprete de é geralmente diferente do intérprete para .$S$$T$$S$$T$

O programa compilado é traduzido de uma forma sintática para outra forma sintática , de modo que, dada a semântica pretendida dos idiomas e , e tenham o mesmo comportamento computacional, até algumas coisas que você geralmente está tentando alterar, possivelmente para otimizar, como complexidade ou eficiência simples (tempo, espaço, superfície, consumo de energia). Estou tentando não falar de equivalência funcional, pois exigiria definições precisas.$P_S$$P_T$$S$$T$$P_S$$P_T$

Alguns compiladores foram realmente usados ​​simplesmente para reduzir o tamanho do código, não para "melhorar" a execução. Esse foi o caso da linguagem usada no sistema Platão (embora eles não tenham chamado de compilação).

Você pode considerar o seu código totalmente compilado se, após o processo de compilação, você não precisa mais do intérprete para . Pelo menos, é a única maneira de ler sua pergunta, como uma questão de engenharia, e não teórica (já que, teoricamente, sempre posso reconstruir o intérprete).$S$

Uma coisa que pode suscitar um problema, após um aumento, é a meta-circularidade . É quando um programa manipula estruturas sintáticas em sua própria linguagem de origem , criando um fragmento de programa que é então interpretado como se tivesse sido parte do programa original. Como você pode produzir fragmentos arbitrários de programas na linguagem como resultado da computação arbitrária manipulando fragmentos sintáticos sem sentido, eu acho que você pode tornar quase impossível (do ponto de vista da engenharia) compilar o programa na linguagem , para que agora gerar fragmentos de . Portanto, o intérprete para será necessário, ou pelo menos o compilador de para$S$$S$$T$$T$$S$$S$$T$ para compilação on-the-fly de fragmentos gerados em (consulte também este documento ).$S$

Mas não tenho certeza de como isso pode ser formalizado adequadamente (e não tenho tempo agora para isso). E impossível é uma grande palavra para um problema que não está formalizado.

Outras observações

Adicionado após 36 horas. Você pode pular esta sequência muito longa.

Os muitos comentários a essa pergunta mostram duas visões do problema: uma visão teórica que a considera sem sentido e uma visão de engenharia que, infelizmente, não é tão facilmente formalizada.

Existem muitas maneiras de analisar a interpretação e a compilação, e tentarei esboçar algumas. Vou tentar ser o mais informal que conseguir

O diagrama da lápide

Uma das formalizações iniciais (do início da década de 1960 até o final de 1990) são os diagramas T ou Tombstone . Esses diagramas apresentam em elementos gráficos composíveis a linguagem de implementação do intérprete ou compilador, a linguagem de origem sendo interpretada ou compilada e a linguagem de destino no caso de compiladores. Versões mais elaboradas podem adicionar atributos. Essas representações gráficas podem ser vistas como axiomas, regras de inferência, utilizáveis ​​para derivar mecanicamente a geração de processadores a partir de uma prova de sua existência a partir dos axiomas, à la Curry-Howard (embora não tenha certeza de que isso tenha sido feito nos anos sessenta :).

Avaliação parcial

Outra visão interessante é o paradigma de avaliação parcial . Estou adotando uma visão simples dos programas como um tipo de implementação de função que calcula uma resposta, considerando alguns dados de entrada. Em seguida, um intérprete para a linguagem é um programa que ter um programa escritos em e os dados para esse programa, e calcula o resultado de acordo com a semântica de . A avaliação parcial é uma técnica para especializar um programa de dois argumentos e , quando apenas um argumento, digamos , é conhecido. A intenção é ter uma avaliação mais rápida quando você finalmente obtiver o segundo argumento$I_S$$S$$p_S$$S$$d$$S$$a_1$$a_2$$a_1$$a_2$ . É especialmente útil se mudar com mais frequência que pois o custo da avaliação parcial com pode ser amortizado em todos os cálculos em que apenas está sendo alterado.$a_2$$a_1$$a_1$$a_2$

Essa é uma situação frequente no design de algoritmos (geralmente o tópico do primeiro comentário no SE-CS), quando parte mais estática dos dados é pré-processada, para que o custo do pré-processamento possa ser amortizado em todos os aplicativos do algoritmo com partes mais variáveis ​​dos dados de entrada.

Essa também é a própria situação dos intérpretes, pois o primeiro argumento é o programa a ser executado e geralmente é executado várias vezes com dados diferentes (ou as subpartes são executadas várias vezes com dados diferentes). Portanto, tornou-se uma idéia natural especializar um intérprete para uma avaliação mais rápida de um determinado programa, avaliando-o parcialmente neste programa como primeiro argumento. Isso pode ser visto como uma maneira de compilar o programa, e houve um trabalho de pesquisa significativo sobre a compilação por avaliação parcial de um intérprete em seu primeiro argumento (programa).

O teorema de Smn

O ponto positivo da abordagem da avaliação parcial é que ela tem suas raízes na teoria (embora a teoria possa ser uma mentirosa), principalmente no teorema Smn de Kleene . Eu estou tentando aqui fazer uma apresentação intuitiva, esperando que isso não perturbe os teóricos puros.

Dada a numeração Gödel de funções recursivas, você pode visualizar como seu hardware, de modo que, dado o número Gödel ( código de objeto de leitura ) de um programa seja a função definida por (isto é, calculada pelo código de objeto em seu hardware).$\varphi$$\varphi$$p$$\varphi_p$$p$

Na sua forma mais simples, o teorema é declarado na Wikipedia da seguinte forma (até uma pequena alteração na notação):

Dado um número de Gödel de funções recursivas, existe uma função recursiva primitiva de dois argumentos com a seguinte propriedade: para todo número de Gödel de uma função parcial computável com dois argumentos, as expressões e são definidos para as mesmas combinações de números naturais e , e os seus valores são iguais para qualquer tal combinação. Em outras palavras, a seguinte igualdade extensional de funções é válida para todo : $\varphi$$\sigma$$q$$f$$\varphi_{\sigma(q,x)}(y)$$f(x,y)$$x$$y$$x$$\;\;\varphi_{\sigma(q,x)} \simeq \lambda y.\varphi_q(x,y).\,$

Agora, considerando como intérprete , como código-fonte de um programa e como dados para esse programa, podemos escrever: $q$$I_S$$x$$p_S$$y$$d$$\;\;\varphi_{\sigma(I_S,p_S)} \simeq \lambda d.\varphi_{I_S}(p_S,d).\,$

I S$\varphi_{I_S}$ pode ser visto como a execução do intérprete no hardware, ou seja, como uma caixa-preta pronto para interpretar programas escritos em linguagem .$I_S$$S$

A função pode ser vista como uma função especializada no intérprete para o programa , como na avaliação parcial. Assim, o número de Gödel pode ser visto como código de objeto que é a versão compilada do programa .I $\sigma$$I_S$ σ ( I S , p S ) p $P_S$$\sigma(I_S,p_S)$$p_S$

Portanto, a função pode ser vista como uma função que toma como argumento o código fonte de um programa escrito na linguagem e retorna a versão do código do objeto para esse programa Então, é o que geralmente é chamado de compilador.q S S C $\;C_S = \lambda q_S.\sigma((I_S,q_S)$$q_S$$S$$C_S$

Algumas conclusões

No entanto, como eu disse: "a teoria pode ser uma mentirosa", ou na verdade parece ser uma. O problema é que não sabemos nada da função . Na verdade, existem muitas dessas funções, e meu palpite é que a prova do teorema pode usar uma definição muito simples para ele, o que pode não ser melhor, do ponto de vista da engenharia, do que a solução proposta por Raphael: simplesmente agrupar o código fonte com o intérprete . Isso sempre pode ser feito, para que possamos dizer: a compilação é sempre possível.q S I $\sigma$$q_S$$I_S$

Formalizar uma noção mais restritiva do que é um compilador exigiria uma abordagem teórica mais sutil. Não sei o que pode ter sido feito nessa direção. O trabalho muito real realizado na avaliação parcial é mais realista do ponto de vista da engenharia. E, claro, existem outras técnicas para escrever compiladores, incluindo extração de programas a partir da prova de suas especificações, conforme desenvolvido no contexto da teoria de tipos, com base no isomorfismo de Curry-Howard (mas estou saindo do meu domínio de competência) .

Meu objetivo aqui foi mostrar que a observação de Raphael não é "louca", mas um lembrete sensato de que as coisas não são óbvias e nem mesmo simples. Dizer que algo é impossível é uma afirmação forte que exige definições precisas e uma prova, apenas para ter uma compreensão precisa de como e por que é impossível . Mas construir uma formalização adequada para expressar essa prova pode ser bastante difícil.

Dito isto, mesmo que um recurso específico não seja compilável, no sentido entendido pelos engenheiros, as técnicas de compilação padrão sempre podem ser aplicadas a partes dos programas que não usam esse recurso, conforme observado pela resposta de Gilles.

Para seguir as principais observações de Gilles, que, dependendo do idioma, algo pode ser feito em tempo de compilação, enquanto outros precisam ser feitos em tempo de execução, exigindo código específico, e podemos ver que o conceito de compilação é realmente mal definido e provavelmente não é definível de maneira satisfatória. A compilação é apenas um processo de otimização, como tentei mostrar na seção de avaliação parcial , quando a comparei com o pré-processamento de dados estáticos em alguns algoritmos.

Como um processo de otimização complexo, o conceito de compilação na verdade pertence a um continuum. Dependendo da característica do idioma ou do programa, algumas informações podem estar disponíveis estaticamente e permitir uma melhor otimização. Outras coisas precisam ser adiadas para o tempo de execução. Quando as coisas ficam realmente ruins, tudo deve ser feito em tempo de execução, pelo menos em algumas partes do programa, e agrupar o código-fonte com o intérprete é tudo o que você pode fazer. Portanto, esse pacote é apenas o ponto mais baixo deste continuum de compilação. Grande parte da pesquisa sobre compiladores é sobre como encontrar maneiras de fazer estaticamente o que costumava ser feito dinamicamente. A coleta de lixo em tempo de compilação parece um bom exemplo.

Observe que dizer que o processo de compilação deve produzir código de máquina não ajuda. É exatamente isso que o agrupamento pode fazer como intérprete é o código da máquina (bem, as coisas podem ficar um pouco mais complexas com a compilação cruzada).

A questão não é realmente sobre a compilação ser impossível . Se um idioma puder ser interpretado¹, ele poderá ser compilado de maneira trivial, agrupando o intérprete com o código-fonte. A questão é perguntar quais recursos de linguagem tornam isso essencialmente o único caminho.

Um intérprete é um programa que recebe o código fonte como entrada e se comporta conforme especificado pela semântica desse código fonte. Se um intérprete for necessário, isso significa que o idioma inclui uma maneira de interpretar o código-fonte. Esse recurso é chamado eval. Se um intérprete for necessário como parte do ambiente de tempo de execução do idioma, significa que o idioma inclui eval: evalexiste como um primitivo ou pode ser codificado de alguma maneira. Os idiomas conhecidos como linguagens de script geralmente incluem um evalrecurso, assim como a maioria dos dialetos Lisp .

Só porque um idioma inclui evalnão significa que a maior parte dele não possa ser compilada no código nativo. Por exemplo, existem otimizadores de compilador Lisp, que geram um bom código nativo e, mesmo assim, suportam eval; evalcódigo ed pode ser interpretado ou compilado em tempo real.

evalé o recurso de necessidades e intérpretes, mas há outros recursos que exigem algo menos que um intérprete. Considere algumas fases típicas de um compilador:

1. Análise
2. Verificação de tipo
3. Geração de código
4. Linking

evalsignifica que todas essas fases precisam ser executadas em tempo de execução. Existem outros recursos que dificultam a compilação nativa. Partindo do fundo, alguns idiomas incentivam a ligação tardia, fornecendo maneiras pelas quais funções (métodos, procedimentos, etc.) e variáveis ​​(objetos, referências, etc.) podem depender de alterações de código não locais. Isso torna difícil (mas não impossível) gerar código nativo eficiente: é mais fácil manter as referências de objetos como chamadas em uma máquina virtual e deixar o mecanismo da VM manipular as ligações rapidamente.

De um modo geral, a reflexão tende a dificultar a compilação de idiomas no código nativo. Um primitivo eval é um caso extremo de reflexão; muitas linguagens não vão tão longe, mas, no entanto, possuem uma semântica definida em termos de uma máquina virtual, permitindo, por exemplo, código recuperar uma classe por nome, inspecionar sua herança, listar seus métodos, chamar métodos, etc. Java with JVM e C # com .NET são dois exemplos famosos. A maneira mais direta de implementar essas linguagens é compilando-as no bytecode , mas ainda assim existem compiladores nativos (muitos just-in-time ) que compilam pelo menos fragmentos de programa que não usam recursos avançados de reflexão.

A verificação de tipo determina se um programa é válido. Idiomas diferentes têm padrões diferentes para quanta análise é executada em tempo de compilação versus tempo de execução: um idioma é conhecido como "estaticamente digitado" se executar muitas verificações antes de começar a executar o código e "dinamicamente digitado" se não o fizer. Alguns idiomas incluem um recurso de transmissão dinâmica ou um recurso de verificação não ordenada e tipográfica; esses recursos exigem a incorporação de um typechecker no ambiente de tempo de execução. Isso é ortogonal aos requisitos de inclusão de um gerador de código ou intérprete no ambiente de tempo de execução.

¹ _{Exercício: defina um idioma que não possa ser interpretado.}

Eu acho que os autores estão assumindo que compilação significa

• o programa de origem não precisa estar presente no tempo de execução e
• nenhum compilador ou intérprete precisa estar presente no tempo de execução.

Aqui estão alguns exemplos de recursos que o tornariam problemático se não "impossível" para esse esquema:

1. Se você puder interrogar o valor de uma variável no tempo de execução, referindo-se à variável pelo nome (que é uma string), será necessário que os nomes das variáveis ​​existam no tempo de execução.

2. Se você pode chamar uma função / procedimento no tempo de execução, consultando-o pelo nome (que é uma sequência), precisará dos nomes da função / procedimento no tempo de execução.

3. Se você pode construir um programa em tempo de execução (como uma seqüência de caracteres), digamos executando outro programa ou lendo-o em uma conexão de rede etc., precisará de um intérprete ou um compilador em tempo de execução para execute este pedaço de programa.

Lisp tem todos os três recursos. Portanto, os sistemas Lisp sempre têm um intérprete carregado em tempo de execução. Idiomas Java e C # têm nomes de funções disponíveis em tempo de execução e tabelas para procurar o que significam. Provavelmente linguagens como Basic e Python também têm nomes de variáveis ​​em tempo de execução. (Não tenho 100% de certeza disso).

é possível que as respostas atuais estejam "pensando demais" na declaração / respostas. possivelmente o que os autores estão se referindo é o seguinte fenômeno. muitas línguas têm um comando semelhante a "eval"; por exemplo, veja javascript eval e seu comportamento é comumente estudado como uma parte especial da teoria de CS (por exemplo, digamos Lisp). a função deste comando é avaliar a sequência no contexto da definição de idioma. portanto, na verdade, tem uma semelhança com um "compilador incorporado". o compilador não pode conhecer o conteúdo da sequência até o tempo de execução. portanto, não é possível compilar o resultado da avaliação no código da máquina no momento da compilação.

outras respostas apontam que a distinção entre linguagens interpretadas e compiladas pode se confundir significativamente em muitos casos, especialmente com linguagens mais modernas, como Java com um "compilador just-in-time", conhecido como "Hotspot" (mecanismos javascript, por exemplo, V8, usam cada vez mais essa mesma técnica). A funcionalidade "eval-like" é certamente uma delas.

O LISP é um exemplo terrível, pois foi concebido como uma espécie de linguagem "máquina" de nível superior como base para uma linguagem "real". A linguagem "real" nunca se materializou. As máquinas LISP foram construídas com a idéia de fazer (grande parte) LISP em hardware. Como um intérprete LISP é apenas um programa, é possível, em princípio, implementá-lo em circuitos. Não é prático, talvez; mas longe de ser impossível.

Além disso, existem muitos intérpretes programados em silício, normalmente chamados de "CPU". E muitas vezes é útil interpretar (ainda não existente, não disponível) códigos de máquina. Por exemplo, o x86_64 do Linux foi escrito e testado em emuladores. Havia distribuições completas disponíveis quando os chips chegaram ao mercado, mesmo apenas para os primeiros usuários / testadores. O Java geralmente é compilado no código da JVM, que é um intérprete que não seria muito difícil de escrever em silício.

A maioria das linguagens "interpretadas" é compilada em um formulário interno, que é otimizado e, em seguida, interpretado. Por exemplo, o que Perl e Python fazem. Também existem compiladores para linguagens interpretadas, como o shell Unix. Por outro lado, é possível interpretar linguagens tradicionalmente compiladas. Um exemplo um tanto extremo que vi foi um editor que usou C interpretado como linguagem de extensão. É C poderia executar programas normais, mas simples, sem problemas.

Por outro lado, as CPUs modernas até pegam a entrada "linguagem de máquina" e a traduzem em instruções de nível inferior, que são reordenadas e otimizadas (isto é, "compiladas") antes de serem entregues para execução.

Toda essa distinção "compilador" vs "intérprete" é realmente discutível, em algum lugar da pilha existe um intérprete final que pega "código" e o executa "diretamente". A entrada do programador sofre transformações ao longo da linha, a qual é chamada de "compilação", apenas desenhando uma linha arbitrária na areia.

A realidade é que há uma grande diferença entre interpretar algum programa Basic e executar o assembler. E há áreas intermediárias com código P / código de bytes com ou sem compiladores (just-in-time). Então, tentarei resumir alguns pontos no contexto dessa realidade.

• Se a forma como o código-fonte é analisado depende das condições de tempo de execução, a criação de um compilador pode se tornar impossível ou tão difícil que ninguém se incomodará.

• Código que se modifica é geralmente impossível de compilar.

• Um programa que usa uma função semelhante a avaliação geralmente não pode ser completamente compilado com antecedência (se você considerar a string fornecida como parte do programa), embora se você deseja executar o código avaliado repetidamente, ainda pode ser É útil fazer com que sua função eval chame o compilador. Alguns idiomas fornecem uma API para o compilador para facilitar isso.

• A capacidade de se referir às coisas pelo nome não impede a compilação, mas você precisa de tabelas (como mencionado). Chamar funções por nome (como IDispatch) requer muito encanamento, a tal ponto que acho que a maioria das pessoas concorda que estamos falando efetivamente de um intérprete de chamada de função.

• A digitação fraca (qualquer que seja sua definição) dificulta a compilação e, talvez, o resultado seja menos eficiente, mas muitas vezes não impossível, a menos que valores diferentes disparem análises diferentes. Há uma escala móvel aqui: se o compilador não puder deduzir o tipo real, ele precisará emitir ramificações, chamadas de função e outras que não estariam lá, incorporando efetivamente bits de intérprete no executável.

eu presumiria que o principal recurso de uma linguagem de programação que impossibilite um compilador para a linguagem (em sentido estrito, veja também auto-hospedagem ) é o recurso de auto-modificação . Significando que o idioma permite alterar o código-fonte durante o tempo de execução (sth que um compilador gera, fixo e estático, o código do objeto não pode fazer). Um exemplo clássico é o Lisp (veja também Homoiconicidade ). Funcionalidade semelhante é fornecida usando uma construção de linguagem como eval , incluída em muitas línguas (por exemplo, javaScript). Eval realmente chama o intérprete (como uma função) em tempo de execução .

Em outras palavras, a linguagem pode representar seu próprio meta-sistema (veja também Metaprogramação )

Observe que a reflexão da linguagem , no sentido de consultar metadados de um determinado código-fonte e possivelmente modificar apenas os metadados (sth como o mecanismo de reflexão de Java ou PHP) não é problemática para um compilador, pois ele já os possui. metadados no momento da compilação e pode disponibilizá-los para o programa compilado, conforme necessário, se necessário.

Outro recurso que dificulta ou não a compilação é a melhor opção (mas não impossível) é o esquema de digitação usado no idioma (ou seja, digitação dinâmica versus digitação estática e digitação forte versus digitação solta). Isso torna difícil para o compilador ter toda a semântica em tempo de compilação; assim, efetivamente uma parte do compilador (em outras palavras, um intérprete) se torna parte do código gerado que lida com a semântica em tempo de execução . Em outras palavras, isso não é compilação, mas interpretação .

Eu sinto que a pergunta original não está bem formada. Os autores da pergunta podem ter pretendido fazer uma pergunta um pouco diferente: Quais propriedades de uma linguagem de programação facilitam a criação de um compilador para ela?

Por exemplo, é mais fácil escrever um compilador para uma linguagem livre de contexto do que uma linguagem sensível ao contexto. A gramática que define um idioma também pode ter problemas que dificultam a compilação, como ambiguidades. Esses problemas podem ser resolvidos, mas requerem um esforço extra. Da mesma forma, idiomas definidos por gramáticas irrestritas são mais difíceis de analisar do que idiomas sensíveis ao contexto (consulte Hierarquia de Chomsky ). Que eu saiba, as linguagens de programação procedurais mais usadas são quase livres de contexto, mas possuem alguns elementos sensíveis ao contexto, tornando-os relativamente fáceis de compilar.

A pergunta tem uma resposta correta tão óbvia que geralmente é negligenciada como trivial. Mas isso importa em muitos contextos e é a principal razão pela qual as linguagens interpretadas existem:

Compilar o código fonte no código da máquina é impossível se você ainda não possui o código fonte.

Os intérpretes adicionam flexibilidade e, em particular, adicionam a flexibilidade da execução de código que não estava disponível quando o projeto subjacente foi compilado.