Quais são os desafios relacionados à digitação ao escrever um compilador para um idioma digitado dinamicamente?

Em essa conversa , Guido van Rossum está falando (27:30) sobre tentativas de escrever um compilador para o código Python, comentá-la dizendo:

Acontece que não é tão fácil escrever um compilador que mantenha todas as boas propriedades dinâmicas de digitação e também mantenha a correção semântica do seu programa, para que ele realmente faça a mesma coisa, independentemente do tipo de estranheza que você faça em algum lugar sob as cobertas e realmente execute mais rápido

Quais são os (possíveis) desafios relacionados à digitação na escrita de um compilador para uma linguagem de tipo dinâmico como Python?

Você simplificou demais a declaração de Guido ao formular sua pergunta. O problema não é escrever um compilador para um idioma digitado dinamicamente. O problema é escrever um que esteja (critério 1) sempre correto, (critério 2) mantenha a digitação dinâmica e (critério 3) seja visivelmente mais rápido para uma quantidade significativa de código.

É fácil implementar 90% (falha do critério 1) do Python e ser consistentemente rápido nisso. Da mesma forma, é fácil criar uma variante Python mais rápida com tipagem estática (falha no critério 2). A implementação de 100% também é fácil (na medida em que é fácil implementar uma linguagem complexa), mas até agora todas as maneiras fáceis de implementá-la acabam sendo relativamente lentas (falha nos critérios 3).

A implementação de um intérprete mais o JIT correto, implementa o idioma inteiro e é mais rápido, pois alguns códigos são viáveis, embora significativamente mais difíceis (cf. PyPy) e somente se você automatizar a criação do compilador JIT (a Psyco fez sem ele , mas era muito limitado em qual código poderia acelerar). Mas observe que isso está explicitamente fora do escopo, pois estamos falando de estática(aka antecipadamente) compiladores. Menciono apenas isso para explicar por que sua abordagem não funciona para compiladores estáticos (ou pelo menos não há contraexemplo): primeiro ele precisa interpretar e observar o programa e gerar código para uma iteração específica de um loop (ou outro código linear). path) e, em seguida, otimize o inferno com base em suposições válidas apenas para essa iteração específica (ou pelo menos para todas as iterações possíveis). A expectativa é que muitas execuções posteriores desse código também correspondam à expectativa e, portanto, se beneficiem das otimizações. Algumas verificações (relativamente baratas) são adicionadas para garantir a correção. Para fazer tudo isso, você precisa ter uma idéia do que se especializar e uma implementação lenta, mas geral, para a qual voltar. Os compiladores AOT não têm. Eles não podem se especializar em tudocom base no código que eles não podem ver (por exemplo, código carregado dinamicamente) e especializar-se descuidadamente significa gerar mais código, o que apresenta vários problemas (utilização do icache, tamanho binário, tempo de compilação, ramificações adicionais).

A implementação de um compilador AOT que implemente corretamente o idioma inteiro também é relativamente fácil: Gere código que chama no tempo de execução para fazer o que o intérprete faria quando alimentado com esse código. Nuitka (principalmente) faz isso. No entanto, isso não gera muitos benefícios de desempenho (falha no critério 3), pois você ainda precisa fazer o mesmo trabalho desnecessário que um intérprete, exceto para despachar o bytecode para o bloco de código C que faz o que você compilou. esse é apenas um custo bastante pequeno - significativo o suficiente para valer a pena otimizar em um intérprete existente, mas não significativo o suficiente para justificar uma implementação totalmente nova com seus próprios problemas.

O que seria necessário para cumprir todos os três critérios? Nós não temos ideia. Existem alguns esquemas de análise estática que podem extrair algumas informações sobre tipos concretos, fluxo de controle etc. dos programas Python. Os que produzem dados precisos além do escopo de um único bloco básico são extremamente lentos e precisam ver o programa inteiro, ou pelo menos a maior parte dele. Ainda assim, você não pode fazer muito com essas informações, além de talvez otimizar algumas operações nos tipos internos.

Por que isso? Para ser franco, um compilador remove a capacidade de executar o código Python carregado no tempo de execução (falha no critério 1) ou não faz nenhuma suposição que possa ser invalidada por qualquer código Python. Infelizmente, isso inclui praticamente tudo útil para otimizar programas: Globals incluindo funções podem ser rebote, classes podem ser mutado ou inteiramente substituídos, os módulos podem ser modificadas arbitrariamente também, a importação pode ser sequestrado em diversas maneiras, etc. A única corda passada para eval, exec, __import__ou inúmeras outras funções, pode fazer nada disso. Com efeito, isso significa que quase nenhuma otimização grande pode ser aplicada, gerando pouco benefício de desempenho (critérios com falha 3). Voltar ao parágrafo acima.

O problema mais difícil é descobrir que tipo tudo tem a qualquer momento.

Em uma linguagem estática como C ou Java, depois de ver a declaração de tipo, você sabe o que é esse objeto e o que ele pode fazer. Se uma variável é declarada int, é um número inteiro. Não é, por exemplo, uma referência de função que pode ser chamada.

Em Python, pode ser. Isso é horrível Python, mas legal:

i = 2
x = 3 + i

def prn(s):
    print(s)

i = prn
i(x)

Agora, este exemplo é bem estúpido, mas ilustra a ideia geral.

Mais realisticamente, você pode substituir uma função interna por uma função definida pelo usuário que faz algo ligeiramente diferente (como uma versão que registra seus argumentos quando você a chama).

O PyPy usa a compilação Just-In-Time depois de observar o que o código realmente faz, e isso permite que o PyPy acelere bastante as coisas. O PyPy pode assistir a um loop e verificar se toda vez que o loop é executado, a variável fooé sempre um número inteiro; então, o PyPy pode otimizar o código que consulta o tipo fooem todas as passagens do loop e, com frequência, pode se livrar do objeto Python que representa um número inteiro e foopode se tornar um número sentado em um registro na CPU. É assim que o PyPy pode ser mais rápido que o CPython; O CPython faz a pesquisa de tipo o mais rápido possível, mas nem mesmo a pesquisa é ainda mais rápida.

Não conheço os detalhes, mas lembro que havia um projeto chamado Unladen Swallow que estava tentando aplicar a tecnologia de compilador estático para acelerar o Python (usando LLVM). Você pode pesquisar no Google por Unladen Swallow e ver se consegue encontrar uma discussão sobre por que não funcionou como eles esperavam.

Como a outra resposta diz, o principal problema é descobrir informações de tipo. Na medida em que você pode fazer isso estaticamente, pode gerar diretamente um bom código.

Mas mesmo que você não possa fazer isso estaticamente, ainda poderá gerar um código razoável, apenas em tempo de execução, quando obter informações de tipo reais . Essas informações geralmente são estáveis ​​ou têm no máximo alguns valores diferentes para qualquer entidade específica em um ponto de código específico. A linguagem de programação SELF foi pioneira em muitas das idéias de coleta agressiva de tipos de tempo de execução e geração de código de tempo de execução. Suas idéias são amplamente usadas em compiladores modernos baseados em JIT, como Java e C #.