O compilador para o tipo dependente é muito mais difícil do que um intérprete?

11

Eu tenho aprendido algo sobre a implementação de tipos dependentes, como este tutorial , mas a maioria deles está implementando intérpretes. Minha pergunta é: parece que implementar um compilador para o tipo dependente é muito mais difícil do que um compilador, porque você pode realmente avaliar os argumentos do tipo dependente para a verificação do tipo.

então

  • Minha impressão ingênua está certa?
  • Se estiver certo, algum exemplo / recurso sobre a implementação de uma linguagem verificada estaticamente suportando o tipo dependente?
type-systems compilers dependent-type molikto
fonte
Não, como você pode reduzir o problema de compilação de tipos dependentes a um problema conhecido: (1) digite check the program usando um intérprete; (2) extrair o programa para OCaml / Haskell / qualquer que seja; (3) compile usando ocamloptou GHC :-) (a propósito, esta é a abordagem Coq e Agda.)
xrq

Respostas:

12

Esta é uma pergunta interessante! Como a resposta de Anthony sugere, é possível usar as abordagens usuais para compilar uma linguagem funcional não dependente, desde que você já tenha um intérprete para avaliar os termos da verificação de tipo .

Essa é a abordagem adotada por Edwin Brady. Agora isso é conceitualmente mais simples, mas perde as vantagens de velocidade da compilação ao executar a verificação de tipo. Isso foi tratado de várias maneiras.

Primeiro, é possível implementar uma máquina virtual que compila termos para código de bytes em tempo real para executar a verificação de conversão. Esta é a idéia por trás vm_computeimplementada no Coq por Benjamin Gregoire . Aparentemente, há também essa tese de Dirk Kleeblatt sobre esse assunto exato, mas abaixo do código de máquina real, em vez de uma máquina virtual.

Segundo, pode-se gerar código em uma linguagem mais convencional que, após a execução, verifica todas as conversões necessárias para verificar um programa digitado de forma digitada. Isso significa que podemos usar Haskell, digamos, para verificar um tipo de módulo Agda. O código pode ser compilado e executado e, se aceitar, pode ser assumido que o código na linguagem do tipo dependente seja bem digitado (exceto erros de implementação e compilador). Eu ouvi pela primeira vez essa abordagem sugerida por Mathieu Boesflug .

∗

cody
fonte
1
Um pouco explícito: por que você se incomodaria em escrever um compilador se você tem um intérprete fazendo a verificação de tipo? Afinal, a maioria (todos?) Dos usuários sérios das linguagens de programação tipicamente dependentes se preocupa apenas com o verificador de tipos, usando a linguagem como assistente de prova. Certamente nunca realmente executei nenhum dos meus programas Agda ou Coq. Portanto, se você se preocupa com a velocidade, não deseja compilar as conversões de tipo?
Martin Berger
2
As soluções 2 e 3 abordam esse problema: você compila código que verifica a boa digitação (e, em particular, realiza conversões de tipo). Minha segunda observação é que você realmente deseja executar código digitado de forma confiável em algumas situações (consulte Idris, Ur / Web).
Cody
1
Além disso: até certo ponto, a solução 1 também a aborda, desfocando as linhas entre intérprete e compilador.
Cody
1
Gostaria de saber se a técnica de projeções de futurama poderia ser usada para acelerar o intérprete, terminando efetivamente com um compilador?
Steven Shaw
1
A única coisa que eu vi é Unison unisonweb.org/2017-10-13/scala-world.html
Steven Shaw
10

A tese de doutorado de Edwin Brady descreve como construir um compilador para uma linguagem de programação tipicamente dependente. Não sou especialista, mas diria que não é extremamente difícil do que implementar um compilador do tipo System F. Muitos dos princípios são bastante semelhantes e alguns são os mesmos (por exemplo, compilação de supercombinadores). A tese cobre muitas outras preocupações.

Anthony
fonte