Semântica formal do OCaml no Coq

14

A semântica de um grande subconjunto de OCaml, chamado OCamllight , foi formalizada na HOL por Owens há vários anos. Mais recentemente, uma semântica teórica do tipo de um subconjunto menor de OCaml foi implementada no Nuprl por Kreitz, Hayden e Hickey .

Existe algum desenvolvimento semelhante no Coq?

coq program-verification ocaml Andrea Asperti
fonte
Você pode estar interessado em CakeML: cakeml.org . Mas não sou o OCaml especificamente.
jmite

Respostas:

12

Você já viu a tese de doutorado de Arthur Charguéraud, fórmulas características para verificação mecanizada de programas ?

Em vez de construir o sistema de tipos e a semântica de pequenos passos como relações indutivas, ele fornece uma técnica para converter programas Caml em fórmulas características. Isso é basicamente uma generalização da semântica do transformador de predicado para suportar um subconjunto muito grande de Ocaml - principalmente, incluindo elencos inseguros como Obj.magic. Para citar sua tese:

Eu me concentrei em um subconjunto da linguagem de programação OCaml, que é uma linguagem de programação seqüencial, de chamada por valor e de alto nível. A implementação atual do CFML suporta o λ-cálculo básico, incluindo funções de ordem superior, recursão, recursão mútua e recursão polimórfica. Ele suporta tuplas, construtores de dados, correspondência de padrões, células de referência, registros e matrizes. Eu forneço uma biblioteca Caml adicional que adiciona suporte a ponteiros nulos e atualizações fortes.

É uma abordagem muito atraente se você quiser provar que um determinado programa Caml está correto (menos ainda, se você estiver interessado em sua metateoria).

Neel Krishnaswami
fonte
Então, se eu entendi direito, a especificação da semântica do Ocaml está embutida no sistema. É possível interpretar a fórmula característica de (alguma função essencial do) sistema como tal especificação? Além disso, presumo que o sistema esteja escrito em OCaml. É possível especificar e provar sua correção no próprio sistema?
Andrea Asperti
Para um determinado programa OCaml, sua fórmula característica pode ser pensada em uma semântica denotacional, uma especificação "menos geral" que pode ser usada para provar quaisquer propriedades desejáveis ​​do programa. Se você fala da "correção" da própria CFML, a pergunta é: com relação a qual semântica formal alternativa?
Gasche
Estranho ter um programa que é suposto software certificar e cujo comportamento não pode ser specififed :)
Andrea Asperti
@AndreaAsperti O que você quer dizer com "incorporado no sistema"? A idéia por trás das fórmulas características (CFs) é bastante direta: mapeie programas para fórmulas lógicas (geralmente pré e pós-condição), de modo que as fórmulas descrevam com precisão a semântica dos programas. Em outras palavras, dois programas satisfazem os mesmos CFs se forem contextualmente indistinguíveis. O mapa do programa para os CFs é feito por indução da estrutura do programa e pode ter como alvo qualquer lógica suficientemente expressiva. A. A lógica de Coq do alvo de Charguéraud, mas é uma escolha contingente.
Martin Berger
1
@MartinBerger: o artigo de Guéneau e cols. Prova apenas a solidez, porque os pré / posts derivados não caracterizam os programas dos quais derivam. Seus CFs são derivados da semântica sem tipo do CakeML, mas a linguagem digitada tem uma equivalência observacional diferente. (Para verificação prática, isso não é muito importante, e é mais fácil.)
Neel Krishnaswami
8

Você poderia estar interessado no Uma Implementação Certificada de ML com Polimorfismo Estrutural e Tipos Recursivos de Jacques Garrigue , que estabelece a solidez da semântica estática e dinâmica e das propriedades da inferência de tipo para uma linguagem ML com polimorfismo estrutural (recursão e), formalizando assim um dos cantos mais avançados do OCaml (variantes polimórficas e tipos de objetos).

Dito isto, este trabalho tem como objetivo verificar a consistência de partes mais avançadas do sistema de tipos do que cobrir o conjunto de recursos dos programas OCaml existentes. Penso que, em termos de tentar provar a exatidão de um programa OCaml existente, a CFML seria uma escolha melhor.

gasche
fonte