Qual foi a principal inovação entre a lógica de Hoare-Floyd e a semântica de Scott-Strachey?

8

Estou lendo um comentário sobre Milner, "O uso de máquinas para ajudar em provas rigorosas", de Mike Gordon. Neste artigo, ele explica como LCF nasceu das idéias da semântica denotacional de Dana Scott e Strachey.

Parece-me que a lógica Floyd-Hoare não foi suficiente para o desenvolvimento da LCF, mas não sei por que esse é o caso. No final, na lógica de Hoare, lidamos com estados de programa que satisfazem alguma pré-condição e que, através de uma relação está de acordo com alguma pós-condição e eu posso fornecer uma fórmula para isso. A Wikipedia afirma que a semântica denotacional:PrQ

é uma abordagem para formalizar os significados das linguagens de programação, construindo objetos matemáticos (chamados de denotações) que descrevem os significados das expressões das linguagens.

Estou familiarizado com algumas intuições sobre como, por exemplo, a recursão é modelada nessa abordagem como um ponto fixo de alguma relação, enquanto na lógica Hoare não me lembrava realmente de lidar com a recursão. Ainda assim, ambas as abordagens parecem tentar descrever as relações entre entradas e saídas usando relações matemáticas.

Questão

Então, o que fez a diferença entre a lógica de Hoare e a semântica denotacional? A semântica denotacional gerencia melhor algumas complexidades de programas? Nesse caso, ilustre com um exemplo.

Talvez a seguinte citação de Milner referente à semântica denotacional seja interessante para guiar sua resposta:

Eu poderia escrever a sintaxe de uma linguagem de programação nessa lógica e escrever a semântica na lógica.

hoare-logic automated-theorem-proving denotational-semantics Rodrigo
fonte
11
Eu acho que, no mundo funcional, a abordagem denotacional é bastante natural. É bem composicional, diferentemente da semântica operacional (especialmente se for pequena). Devo confessar que nunca vi uma lógica Hoare para programas funcionais - suspeito que uma, se existir, possa ser complicada, pois no FP puro não há uma construção de "atualização do estado" como a atribuição na programação imperativa.
Chi
4
@chi Claro que existem muitas lógicas Hoare para os FPs. O trabalho pioneiro foi Uma lógica de programa composicional para funções polimórficas de ordem superior da Honda / Yoshida, que foi estendida em, por exemplo: * Uma lógica de programa observacionalmente completa para funções imperativas de ordem superior ". Foi estendida de várias maneiras.
Martin Berger
@MartinBerger Ah, interessante. Obrigado pela referência.
chi
Acho as referências à FP perturbadoras do ponto principal da pergunta. A diferença entre a lógica de Hoare e a semântica denotacional é que o primeiro se preocupa em atribuir sintaxe propriedades de programas (novamente, dado sintaticamente), enquanto o último se preocupa em associar programas a objetos matemáticos que se assemelham ao seu significado. Em outras palavras, os dois são muito diferentes.
Kai

Respostas:

10

Não sei por que as pessoas não desenvolveram lógicas Hoare para lambda-calculi anteriormente. O primeiro trabalho para acertar foi Honda e cols.

Uma lógica de programa de composição para funções polimórficas de ordem superior

Houve algumas tentativas anteriores antes disso, mas elas não resolveram o problema, por exemplo: como você denota o valor de um programa funcional? Que parte da sintaxe corresponde ao construtor do espaço de funções? Há algumas pequenas coisas que precisam ser acertadas.

Deixe-me especular: talvez a questão principal seja que a lógica de Hoare geralmente se preocupa com a computação com estado. Se você combinar funções de estado e de ordem superior, precisará imediatamente lidar com o alias, por exemplo, programas como

λxRef(Numat).λyRef(Numat).(x: =!x+1 1;y: =!y+1 1),
bem como loja local e recursão pela loja. Estes foram resolvidos apenas no início dos anos 2000 em trabalhos como Uma lógica de programa observacionalmente completa para funções imperativas de ordem superior (recursão pela loja); Uma análise lógica do aliasing em funções imperativas de ordem superior (aliasing), raciocínio lógico para funções de ordem superior com estado local (armazenamento local completo). Ao mesmo tempo, a lógica de separação abordou o problema de aliasing de um ângulo diferente.

Este trabalho foi implementado no Coq por A. Charguéraud em seu trabalho , e que também é usado na semântica do Javascript agora.

Martin Berger
fonte