Ferramenta de prototipagem de semântica da linguagem de programação

11

Existe alguma ferramenta para prototipar uma semântica da linguagem de programação e um sistema de tipos que também permita algum tipo de verificação de modelo de propriedades padrão, como a solidez do tipo?

Estou perguntando isso, porque estou lendo um livro sobre o Alloy e ele fornece a funcionalidade exata que eu quero, mas para modelos expressos usando lógica relacional.

Estou ciente do Ott , mas ele não possui esse tipo de recurso de "verificação de modelo", pois está focado na geração de código para sistemas assistentes de prova.

Qualquer referência à existência dessa ferramenta seria legal.

reference-request programming-languages semantics model-checking Rodrigo Ribeiro
fonte
1
Como o Ott é o primeiro passo, você faz a verificação do modelo no seu assistente de prova favorito.
Gilles 'SO- stop be evil' em
@ Gilles: Ok, mas um ponto de uma ferramenta de verificação de modelo é que ela gera todo um conjunto de elementos de um determinado tamanho para verificar se a propriedade é realmente válida para eles. Dessa forma, precisarei codificar essa parte da geração para todos os idiomas definidos. Você sabia se existe alguma maneira de automatizar essa etapa da geração?
Rodrigo Ribeiro
Tecnicamente, você pode fazer isso em um assistente de prova (pelo menos em um como Coq), mas provavelmente será muito lento. Os assistentes de prova são voltados para provas assistidas por humanos, em vez de tentar automaticamente milhões de maneiras de resolver o problema. Se você quiser reutilizar o Ott, poderá adicionar um back-end para o seu verificador de modelos favorito.
Gilles 'SO- stop be evil'

Respostas:

8

Embora existam estruturas criadas especificamente para a finalidade de prototipar linguagens de programação (incluindo semântica, sistemas de tipos, avaliação e verificação de propriedades sobre elas), a melhor opção depende do seu caso particular e das necessidades específicas.

Dito isso, existem várias alternativas (talvez não tão distintas) que você pode adotar (incluindo as que você já mencionou):

  • usando uma linguagem / estrutura específica projetada para criar e criar protótipos de novas linguagens: como exemplo, Redex [1], uma linguagem específica de domínio incorporada no Racket para especificar e verificar a semântica (operacional) das linguagens de programação, que, dada uma definição de fornece fácil manuseio de tarefas como tipografia (em Latex), inspeção de vestígios de redução, testes de unidade e testes aleatórios (por exemplo, para verificar a digitação)
  • usando linguagens de modelagem gerais que oferecem a definição e a execução de determinadas análises facilmente, desde que possam capturar o idioma específico em questão na extensão necessária; Alloy [2] é um exemplo de tal abordagem: embora bastante geral e flexível, as linguagens podem ser modeladas como relações entre estados, enquanto o suporte para a verificação de modelos (por exemplo, avaliação dentro dessa linguagem) é gratuito após a semântica ser expressa com um modelo de relação (por exemplo, algumas idéias para modelar semântica de uma linguagem podem ser encontradas em [3])
  • incorporar a linguagem para verificar suas propriedades usando um comprovador de teoremas; um exemplo definiria a linguagem, bem como sua semântica, incorporando-a em um sistema de prova como o Coq [4] (mais detalhes sobre essa abordagem, além de discussão e demonstração da diferença entre incorporação profunda e superficial no Coq, são fornecidas em [ 5])
  • usando Ott (como já mencionado, com espírito semelhante ao Redex, mas fornecendo uma nova linguagem de definição em vez de ser incorporada); Ott permite definir a linguagem de programação em uma notação conveniente e produzir tipografia e definições em um sistema de prova (geralmente com incorporação profunda), onde a maior parte da verificação (ou seja, prova) precisa ser realizada manualmente
  • desenvolver a linguagem e sua semântica, bem como verificações apropriadas (por exemplo, testes) "do zero" em uma linguagem de programação de uso geral e tradução para outros sistemas, se necessário, para fins de verificação (algumas linguagens, como Leon [6], incluem verificadores internos, que permitem provar automaticamente certas propriedades e tornam essa abordagem semelhante à incorporação em um sistema de prova)

Observe que existe o compromisso entre a facilidade de uso da estrutura / ferramenta (por exemplo, tão fácil quanto a definição da definição no papel ou no Latex) e a potência dos mecanismos para verificar as propriedades do idioma (por exemplo, incorporar o linguagem em um provador de teoremas pode permitir a verificação de propriedades muito elaboradas).

[1] Casey Klein, John Clements, Christos Dimoulas, Carl Eastlund, Matthias Felleisen, Matthew Flatt, Jay A. McCarthy, Jon Rafkind, Sam Tobin-Hochstadt e Robert Bruce Findler. Execute sua pesquisa: sobre a eficácia da mecanização leve. POPL, 2012.

[2] Daniel Jackson. Liga: uma notação leve de modelagem de objetos. TOSEM, 2002.

[3] Greg Dennis, Felix Chang e Daniel Jackson. Verificação modular de código com SAT. ISSTA, 2006

[4] Sistema formal de gestão de provas Coq

[5] raciocínio formal Sobre Programas. Adam Chlipala, 2016

[6] Sistema automatizado Leon para verificar, reparar e sintetizar programas Scala funcionais.

ivcha
fonte