Venho programando há vários anos, mas não estou familiarizado com o CS teórico. Recentemente, tenho tentado estudar linguagens de programação e, como parte disso, verificação de tipo e inferência.
Minha pergunta é: se eu tentar escrever um programa de inferência e verificação de tipo para uma linguagem de programação e desejar provar que meu datilógrafo funciona, qual é exatamente a prova que estou procurando?
Em linguagem simples, desejo que meu verificador de tipos consiga identificar quaisquer erros em um pedaço de código que possam ocorrer no tempo de execução. Se eu usasse algo como Coq para tentar provar que minha implementação está correta, o que exatamente essa "prova de correção" tentará mostrar?
coq
type-inference
proof-assistants
Vivek Ghaisas
fonte
fonte
2 + "hello"
esse são 'presos'). Depois que isso for formalizado, você poderá provar o teorema da solidez do tipo. Isso significa que nenhum programa tipável pode evoluir para um erro de tipo imediato. Formalmente, você prova que, se um programa for digitado, e para qualquer n ≥ : se M executar n etapas para se tornar N , N não terá um erro de tipo imediato. (1/2)Respostas:
A questão pode ser interpretada de duas maneiras:
O primeiro é realmente uma questão de verificação de programa e tem pouco a ver com digitação. Só precisa mostrar que sua implementação atende às suas especificações, veja a resposta de Andrej.
Primeiro, você define formalmente o que significa para um programa ter um erro de digitação imediato . Há muitas maneiras de definir isso - depende de você. Normalmente, queremos impedir programas como o
2 + "hello"
. Em outras palavras, você precisa definir um subconjunto de programas, chamado Bad , que contém exatamente os programas com erro de digitação imediato.Como provar esse teorema depende dos detalhes do idioma, do sistema de digitação e da sua escolha de Mau .
Observe que nem todos os sistemas de digitação têm "redução de assunto", por exemplo, tipos de sessão. Nesse caso, são necessárias técnicas de prova mais sofisticadas.
fonte
Esta é uma boa pergunta! Ele pergunta o que esperamos dos tipos em um idioma digitado.
Primeiro, observe que podemos digitar qualquer linguagem de programação com o unitype : basta escolher uma letra, digamos
U
e dizer que todo programa tem tipoU
. Isso não é muito útil, mas faz um ponto.int
Não há fim para quão expressivos seus tipos podem ser. Em princípio, eles podem ser qualquer tipo de afirmação lógica, podem usar teoria das categorias e outros enfeites etc. Por exemplo, tipos dependentes permitem expressar coisas como "essa função mapeia listas para listar, de modo que a saída seja uma entrada classificada". Você pode ir além, no momento, estou ouvindo uma palestra sobre "lógicas de separação simultâneas", que permite falar sobre como os programas simultâneos funcionam com o estado compartilhado. Coisa chique.
A arte dos tipos no design da linguagem de programação é a de equilibrar expressividade e simplicidade :
A simplicidade não deve ser subestimada, pois nem todo programador possui um doutorado em teoria das linguagens de programação.
Então, voltemos à sua pergunta: como você sabe que seu sistema de tipos é bom ? Bem, prove os teoremas que mostram que seus tipos estão equilibrados. Haverá dois tipos de teoremas:
Teoremas que dizem que seus tipos são úteis . Saber que um programa tem um tipo deve implicar algumas garantias, por exemplo, que o programa não ficará preso (isso seria um teorema de Segurança ). Outra família de teoremas conectaria os tipos a modelos semânticos, para que possamos começar a usar matemática real para provar coisas sobre nossos programas (esses seriam os teoremas da adequação e muitos outros). A unidade acima é ruim porque não possui teoremas úteis.
Teoremas que dizem que seus tipos são simples . Um básico seria que é decidível se uma determinada expressão tem um determinado tipo. Outro recurso de simplicidade é fornecer um algoritmo para inferir um tipo. Outros teoremas sobre simplicidade seriam: que uma expressão tem no máximo um tipo ou que uma expressão tem um tipo principal (isto é, o "melhor" entre todos os tipos que possui).
É difícil ser mais específico porque os tipos são um mecanismo muito geral. Mas espero que você veja o que deve filmar. Como a maioria dos aspectos do design da linguagem de programação, não há medida absoluta de sucesso. Em vez disso, existe um espaço de possibilidades de design, e o importante é entender onde você está ou deseja estar no espaço.
fonte
Existem algumas coisas diferentes que você poderia dizer com "provar que meu datilógrafo funciona". O que, suponho, faz parte do que sua pergunta está fazendo;)
Metade desta questão está provando que sua teoria de tipos é boa o suficiente para provar quaisquer propriedades sobre a linguagem. A resposta de Andrej aborda muito bem essa área. A outra metade da questão é - supondo que o idioma e seu sistema de tipos já estejam corrigidos - como você pode provar que seu verificador de tipos específico realmente implementa o sistema de tipos corretamente? Existem duas perspectivas principais que posso ver aqui.
Uma é: como podemos confiar que alguma implementação específica corresponde à sua especificação? Dependendo do grau de garantia que você deseja, você pode ficar satisfeito com uma grande suíte de testes ou com algum tipo de verificação formal ou, mais provavelmente, com uma mistura de ambos . O lado positivo dessa perspectiva é que ela realmente destaca a importância de estabelecer limites nas reivindicações que você está fazendo: o que exatamente "correto" significa? qual parte do código é verificada versus qual parte é o TCB correto assumido? etc. A desvantagem é que pensar demais sobre isso leva a um buraco de coelho filosófico - bem, "desvantagem" se você não gosta desses buracos de coelho.
A segunda perspectiva é uma abordagem mais matemática da correção. Ao lidar com linguagens em matemática, geralmente criamos "modelos" para nossas "teorias" (ou vice-versa) e tentamos provar: (a) tudo o que podemos fazer na teoria que podemos fazer no modelo; e (b) tudo o que podemos fazer no modelo que podemos fazer na teoria. (Estes são Solidez e Completudeteoremas. Qual deles depende se você "partiu" da teoria sintática ou do modelo semântico.) Com essa mentalidade, podemos pensar na sua implementação de verificação de tipo como sendo um modelo específico para a teoria de tipos em questão. Portanto, você deseja provar essa correspondência bidirecional entre o que sua implementação pode fazer e o que a teoria diz que você deve fazer. A vantagem dessa perspectiva é que ela realmente se concentra em saber se você cobriu todos os casos principais, se sua implementação está completa no sentido de não deixar de fora nenhum programa que deve aceitar como seguro para o tipo e se sua implementação é sólida. a sensação de não deixar entrar nenhum programa que deveria rejeitar como incorreto. A desvantagem é que sua prova de correspondência provavelmente será bastante separada da própria implementação,
fonte