Regras gerais para gravar um compilador X em Z em Y

Suponha que X é o idioma de entrada, Z é o idioma de saída e f é o compilador, escrito no idioma Y.

f = X -> Z

Como f é apenas um programa, acho que Y pode ser qualquer idioma, certo? Portanto, podemos ter os compiladores f1, f2, cada um escrito em Y1, Y2.

f1 = f Y1    
f2 = f Y2

g = Z -> M
h = g . f    # We get a compiler X -> M

Tomemos o compilador cpython, por exemplo, X é Python, Z é o código da VM Python, Y é C.

cpython = Python -> PythonVMCode C
interpreter = PythonVMCode -> Nothing
interpreter2 = PythonVMCode -> MachineCode

As fontes Python são compiladas no código da VM Python, nos arquivos .pyc, e depois interpretadas pelo intérprete. Parece que é possível que exista um compilador que possa executar diretamente o Python -> MachineCode, embora seja muito difícil de implementar:

   hardpython = interpreter2 . cpython 

Também podemos escrever outro compilador para o trabalho Python -> PythonVMCode, em outra linguagem, como o próprio Python.

mypython = Python -> PythonVMCode Python
mypython2 = Python -> PythonVMCode Ruby

Agora, aqui está o exemplo complicado de PyPy. Sou apenas um novato no PyPy, me corrija se estiver errado:

Doc PyPy http://doc.pypy.org/en/latest/architecture.html#pypy-the-translation-framework

Nosso objetivo é fornecer uma possível solução para o problema dos implementadores de linguagem: ter que escrever intérpretes l * o * p para l linguagens dinâmicas ep plataformas sem decisões cruciais de design.

Podemos pensar que eu sou X, p é Y. Existe um programa que traduz todos os programas RPython para C:

 rpython_compiler = RPython -> C  Python

 pypy = Python -> Nothing RPython

 translate = compile the program pypy written in RPython using rpython_compiler

 py2rpy = Python -> RPython  Python
 py2c = Python -> C Python 
 py2c = rpython_compiler . py2rpy

Os programas RPython são exatamente como as instruções da VM, rpython_compiler é a VM.

q1. pypy é o intérprete, um programa RPython que pode interpretar o código Python; não há linguagem de saída; portanto, não podemos considerá-lo um compilador, certo?

Adicionado:

• Acabei de descobrir que, mesmo após a tradução, pypy ainda é um intérprete, só que desta vez escrito em C.
• Se olharmos profundamente para o interpretador pypy, acredito que deve existir algum tipo de compilador, que compila as fontes do Python para algum AST e execute

como isso:

compiler_inside_pypy = Python -> AST_or_so

q2. O compilador py2rpy pode existir, transformando todos os programas Python em RPython? Em que idioma está escrito é irrelevante. Se sim, obtemos outro compilador py2c. Qual é a diferença entre pypy e py2rpy na natureza? Py2rpy é muito mais difícil de escrever do que pypy?

q3. Existe alguma regra ou teoria geral disponível sobre isso?

Mais compiladores:

gcc_c = C -> asm? C  # not sure, gimple or rtl?
g++ =   C++ -> asm? C
clang = C -> LLVM_IR  C++
jython = Python -> JVMCode java
ironpython = Python -> CLI C#

q4. Dado f = X -> Z, um programa P escrito em X. Quando queremos acelerar P, o que podemos fazer? Maneiras possíveis:

• reescrever P em algoritmo mais eficiente

• reescreva f para gerar Z melhor

• se Z for interpretado, escreva um interpretador Z melhor (o PyPy está aqui?)

• acelerar programas escritos em Z recursivamente

• consiga uma máquina melhor

ps. Esta questão não é sobre os aspectos técnicos de como escrever um compilador, mas a viabilidade e complexidade de escrever um determinado tipo de compilador.

q1. pypy é o intérprete, um programa RPython que pode interpretar o código Python; não há linguagem de saída; portanto, não podemos considerá-lo um compilador, certo?

O PyPy é semelhante ao CPython, ambos possuem um compilador + intérprete. O CPython possui um compilador escrito em C que compila o bytecode do Python para o Python VM e, em seguida, executa o bytecode em um intérprete escrito em C. O PyPy possui um compilador escrito em RPython que compila o Python no bytecode da VM do Python e o executa no PyPy Interpreter escrito em RPython.

q2. O compilador py2rpy pode existir, transformando todos os programas Python em RPython? Em que idioma está escrito é irrelevante. Se sim, obtemos outro compilador py2c. Qual é a diferença entre pypy e py2rpy na natureza? Py2rpy é muito mais difícil de escrever do que pypy?

Pode existir um compilador py2rpy? Teoricamente sim. Turing completude garante isso.

Um método a construir py2rpyé simplesmente incluir o código fonte de um intérprete Python escrito em RPython no código fonte gerado. Um exemplo de compilador py2rpy, escrito em Bash:

// suppose that /pypy/source/ contains the source code for pypy (i.e. Python -> Nothing RPython)
cp /pypy/source/ /tmp/py2rpy/pypy/

// suppose $inputfile contains an arbitrary Python source code
cp $inputfile /tmp/py2rpy/prog.py

// generate the main.rpy
echo "import pypy; pypy.execfile('prog.py')" > /tmp/py2rpy/main.rpy

cp /tmp/py2rpy/ $outputdir

Agora, sempre que você precisar converter um código Python em código RPython, chame esse script, que produz - no $ outputdir - um RPython main.rpy, o código-fonte Python Interpreter do RPython e um blob binário prog.py. E então você pode executar o script RPython gerado chamando rpython main.rpy.

(observação: como não estou familiarizado com o projeto rpython, a sintaxe para chamar o interpretador rpython, a capacidade de importar pypy e executar pypy.execfile e a extensão .rpy são puramente inventadas, mas acho que você entendeu bem)

q3. Existe alguma regra ou teoria geral disponível sobre isso?

Sim, qualquer idioma do Turing Complete pode teoricamente ser traduzido para qualquer idioma do Turing Complete. Alguns idiomas podem ser muito mais difíceis de traduzir do que outros, mas se a pergunta for "é possível?", A resposta é "sim"

q4. ...

Não há dúvida aqui.

Para responder apenas ao q2, há um livro de compilador de William McKeeman no qual a teoria dos compiladores para a linguagem X escrita na linguagem Y produzindo a linguagem de saída Z é explorada por meio de um sistema de diagramas-T. Publicado na década de 1970, o título não está à mão, desculpe.

q1. Geralmente, um intérprete não é um compilador. A principal diferença entre um compilador e um intérprete é que um intérprete é iniciado novamente, com código-fonte no idioma de origem, sempre. Se, em vez disso, seu pypy fosse pyAST ou código pyP e você tivesse um interpretador de código AST ou P, poderia chamar o pyAST de compilador. Foi assim que o antigo compilador UCSD PASCAL funcionou (assim como alguns outros): eles compilaram com algum código P, que foi interpretado quando o programa foi executado. (Mesmo o .NET fornece algo assim, quando a compactação do código do objeto gerado é muito mais importante que a velocidade).

q2. Sim, claro. Veja UCSD PASCAL (e muitos outros).

q3. Vasculhe os textos clássicos em ciência da computação. Leia sobre Concurrent PASCAL, de Per Brinch-Hansen (se a memória me servir). Muito foi escrito sobre compiladores e geração de código. Gerar um pseudocódigo independente de máquina geralmente é muito mais fácil do que gerar código de máquina: o pseudocódigo geralmente está livre das peculiaridades que máquinas reais contêm invariavelmente.

q4. Se você deseja que seu objeto gerado seja executado mais rapidamente, torne o compilador mais inteligente, para otimizar melhor. Se seu objeto for interpretado, considere colocar operações mais complexas em pseudoinstruções primitivas (CISC vs. RISC é a analogia), e faça o possível para otimizar o frack do seu intérprete.

Se você deseja que seu compilador seja executado mais rapidamente, é necessário analisar TUDO, incluindo repensar o código-fonte. Depois de carregar o próprio compilador, a parte mais demorada da compilação é SEMPRE lendo o código-fonte no compilador. (Considere C ++, por exemplo. Todas as outras coisas são relativamente iguais, um compilador que precisa compilar 9.000 (ou talvez 50.000) linhas de #include arquivos para compilar um simples programa "Olá, Mundo" nunca será tão rápido quanto um só precisa ler quatro ou cinco linhas.)

Não me lembro de onde li, mas o compilador Oberon original da ETH-Zurique tinha um mecanismo de tabela de símbolos muito sofisticado, bastante elegante. O benchmark de Wirth para o desempenho do compilador foi o tempo que levou para o compilador se compilar. Certa manhã, ele entrou, arrancou a linda mesa de símbolos de ultra árvores com ligações múltiplas e a substituiu por uma matriz linear simples e pesquisas lineares diretas. Os alunos de pós-graduação em seu grupo ficaram chocados. Após a mudança, o compilador foi mais rápido, porque os módulos que ele estava compilando eram sempre pequenos o suficiente para que o monstro elegante impusesse mais sobrecarga total do que a matriz linear e a pesquisa linear.

Suas perguntas, como indicado, me levam a acreditar que o que você realmente deseja / precisa é uma explicação do que é um compilador, o que é um intérprete e as diferenças entre os dois.

Um compilador mapeia um programa escrito na linguagem X para um programa funcionalmente equivalente, escrito na linguagem Y. Como exemplo, um compilador de Pascal a C pode compilar

function Square(i: Integer)
begin
    Square := i * i
end

para

int Square(int i)
{
    return i * i;
}

A maioria dos compiladores compila 'para baixo'; portanto, compila linguagens de programação de nível superior em linguagens de nível inferior, sendo a linguagem de nível inferior o código da máquina.

A maioria dos compiladores é compilada diretamente no código da máquina, mas alguns (principalmente nas linguagens Java e .NET) são compilados no 'bytecode' ( Java bytecode e CIL ). Pense no bytecode como código de máquina para um computador hipotético. Esse bytecode é então interpretado ou JITted quando executado (mais sobre isso posteriormente).

Um intérprete executa um programa escrito em algum idioma Z. Um intérprete lê um programa pouco a pouco, executando-o à medida que avança. Por exemplo:

int i = 0;
while (i < 1)
{
    i++
}
return i;

Imagine o intérprete olhando para a linha de programa em busca de linha, examinando a linha, executando o que faz, olhando para a próxima linha e assim por diante.

O melhor exemplo de intérprete é a CPU do seu computador. Ele interpreta o código da máquina e o executa. Como a CPU funciona é especificada pela forma como é construída fisicamente. O funcionamento de um programa de intérpretes é especificado pela aparência do seu código. A CPU, portanto, interpreta e executa o programa de intérpretes, que por sua vez interpreta e executa sua entrada. Você pode encadear intérpretes dessa maneira.

Um JITter é um compilador Just-In-Time. Um JITter é um compilador. A única diferença é o tempo em que é executado: a maioria dos programas é gravada, compilada, enviada aos usuários e, em seguida, executada, mas o bytecode Java e o CIL são enviados aos usuários primeiro e, logo antes de serem executados, são compilados na máquina código de seus usuários.

C # -> (compilação) -> CIL -> enviado ao cliente -> (compilação imediatamente antes da execução) -> código de máquina -> (execução)

A última coisa que você vai querer saber é a integridade de Turing ( link ). Uma linguagem de programação é Turing Complete se puder computar tudo o que uma ' máquina de Turing ' pode, ou seja, é pelo menos tão 'poderosa' quanto uma máquina de Turing. A tese de Church-Turing afirma que uma máquina de Turing é pelo menos tão poderosa quanto qualquer outra máquina que possamos construir. Segue-se que toda linguagem completa de Turing é exatamente tão poderosa quanto a máquina de Turing e, portanto, todas as línguas completas de Turing são igualmente poderosas.

Em outras palavras, desde que sua linguagem de programação seja Turing completa (quase todas elas são), não importa qual linguagem você escolher, pois todas elas podem calcular as mesmas coisas. Isso também significa que não é muito relevante qual linguagem de programação você escolhe para escrever seu compilador ou seu intérprete. Por último, mas não menos importante, significa que você sempre pode escrever um compilador do idioma X para Y se X e Y estiverem ambos concluídos em Turing.

Observe que a conclusão de Turing não diz nada sobre se seu idioma é eficiente, nem sobre todos os detalhes de implementação de sua CPU e outro hardware, ou sobre a qualidade do compilador usado para o idioma. Além disso, seu sistema operacional pode decidir que seu programa não tem o direito de abrir um arquivo, mas isso não impede sua capacidade de calcular nada - eu deliberadamente não defini a computação, pois isso exigiria outra parede de texto.