Para quais idiomas já existe uma teoria da equivalência observacional?

Para uma prova de correção, estou procurando uma noção utilizável de equivalência de programa para os sistemas de tipo puro (PTSs) de Barendregt; falta isso, para sistemas de tipos específicos suficientes. Meu objetivo é simplesmente usar a noção, não investigá-la por si mesma. $\cong$

Essa noção deve ser " extensional " - em particular, para provar que , deve ser suficiente para provar que $t_1 \cong t_2$ para todos os valores do tipo apropriado. $t_1\; v \cong t_2\; v$ $v$

Equivalência denotacional

A equivalência denotacional satisfaz facilmente todos os lemas certos, mas uma semântica denotacional para PTS arbitrário parece bastante desafiadora - já pareceria difícil para o Sistema F.

Equivalência contextual / observacional

A alternativa óbvia são então várias formas de equivalência contextual (dois termos são equivalentes se nenhum contexto básico puder distingui-los), mas sua definição não é imediatamente utilizável; os vários lemas não são triviais para provar. Eles foram provados para PTS? Como alternativa, a teoria seria uma "extensão óbvia" ou há razões para acreditar que a teoria seria significativamente diferente?

Edição: Eu não disse o que é difícil acima.

Parte fácil: a definição

Definir a equivalência não é muito difícil, e a definição aparece em muitos artigos (começando pelo menos no estudo de Plotkin 1975 sobre o PCF, se não antes - a fonte pode ser a tese de doutorado de Morris de 1968). Nós se, para todos os contextos de terra , - ou seja, e derem o mesmo resultado $t_1 \cong t_2$ $C$ $C[t_1] \simeq C[t_2]$ $C[t_1]$ $C[t_2]$ . Você tem algumas opções aqui com muitas alternativas: Por exemplo, em uma linguagem fortemente normalizando, se você tem um tipo de terreno de naturais, você pode dizer que os contextos de terra são os que naturais de retorno, em seguida, significa que e avaliar para o mesmo número. Com o não término, para linguagens razoáveis, basta usar "X termina" como observação, porque se dois programas são equivalentes ao observar a terminação, eles também são equivalentes ao observar o resultado. $a \simeq b$ $a$ $b$

Parte difícil: as provas

No entanto, esses documentos geralmente não explicam o quão difícil é realmente usar essa definição. Todas as referências abaixo mostram como lidar com esse problema, mas a teoria necessária é mais difícil do que se pensa. Como provamos que ? Realmente fazemos análise de casos e indução em contextos? Você não quer fazer isso. $t_1 \cong t_2$

Como Martin Berger aponta, você deseja usar a bisimulação (como feita por Pitts) ou uma relação de equivalência lógica (que Harper chama simplesmente de "equivalência lógica").

Finalmente, como você prova a extensionalidade conforme definido acima?

Harper resolve essas questões em 10 páginas para o Sistema T, através de considerável inteligência e relações lógicas. Pitts leva mais. Alguns idiomas são ainda mais complexos.

Como lidar com isso

Na verdade, estou tentado a fazer minhas provas condicionalmente em uma teoria conjecturada da equivalência para o PTS, mas as teorias atuais exigem argumentos não triviais, portanto, não tenho certeza da probabilidade de tal conjectura ser mantida.

Estou ciente (embora não em detalhes) dos seguintes trabalhos:

Andrew Pitts (por exemplo, na ATTAPL para um Sistema F estendido, e em alguns artigos, como as "Teorias de Equivalência de Programas com Base Operacional de 58 páginas").
Fundamentos práticos de linguagens de programação (capítulos 47-48), inspirados em Pitts (mas que afirma ter provas mais simples).
Um estudo lógico da equivalência de programas . Não consigo encontrar um resumo em inglês, mas parece gastar muito esforço com efeitos colaterais (referências), o que parece uma complicação ortogonal.

pl.programming-languages type-theory operational-semantics Blaisorblade
fonte

Para teorias de tipos, definir uma congruência contextual operacional deve ser fácil, uma vez que todos os programas terminam. Defina uma noção de observação em um tipo base (por exemplo, terminação, escrita

, no tipo Unidade) e, em seguida, diga

para todos os contextos bem digitados e de fechamento

do tipo base, temos

iff

. Com os PTSs, é um pouco mais complicado, pois pode haver interrupção.

⇓

$\Downarrow$

P ≅ Q

$P \cong Q$

C [\cdot]

$C[\cdot]$

C [P] ⇓

$C[P] \Downarrow$

C [Q] ⇓

$C[Q] \Downarrow$

9788 Martin-Berger

@MartinBerger: é a ideia que estou sugerindo, mas provar isso diretamente é surpreendentemente difícil, porque você precisa fazer provas para todos os C (vou explicar melhor isso na pergunta). Além disso, se todos os programas terminarem, a definição que você usa, conforme fornecido, identifica todos os programas.

Blaisorblade

Seu PTS possui apenas funções como tipos computacionais? Nesse caso, essa excelente pergunta (e respostas) parece indicar que a equivalência

é suficiente para terminar sistemas de tipo puro - e explica bem como definir equivalência contextual para terminar cálculos. Eu acho que usar valores fundamentais é o caminho certo para definir equivalência contextual, e terminar é apenas um atalho conveniente de mérito duvidoso.

β η

$\beta\eta$

Gasche

@ Blaisorblade Desculpe sim, se você usar a rescisão como observável, então você está certo. Desculpe, eu estava cortando e colando a definição para pesquisar linguagens determinísticas completas. Se você tiver funções de encerramento, poderá usar um observável básico diferente. Por exemplo, em booleanos: ...

sse

. A quantificação em todos os contextos é sempre um problema. A forma padrão de lidar com ele é para definir uma segunda relação de que (1) é som wrt

C [P] ⇓ t r u e

$C[P] \Downarrow true$

C [Q] ⇓ t r u e

$C[Q] \Downarrow true$

≅

$\cong$ e (2) fácil de manusear, por exemplo, alguma noção de bisimilaridade ou relação lógica. Depende do aplicativo.

Martin Berger

@Blaisorblade Provavelmente. Os teóricos da concorrência vêm fazendo isso intensivamente há muito tempo, porque com processos simultâneos fica muito menos claro que noção de equivalência usar. Isso levou a uma divisão do trabalho: use uma semântica baseada em redução com quantificação em contextos para definir a noção de equivalência e, em seguida, use bisimulações ou traços em transições rotuladas para provar a equivalência (ou a ausência dela). Uma grande questão de pesquisa aberta na teoria da concorrência é como passar de um para o outro por algoritmo.

Martin Berger

Respostas:

Uma semântica denotacional composicional de uma linguagem de programação (teórica de domínio ou teórica de jogo, por exemplo) éadequadase termos semanticamente iguais implicarem que são observacionalmente equivalentes: $[\![ {-} ]\!]$ Muitas vezes acontece que é muito mais fácil calcular denotações que provar a equivalência observacional. Essa é uma técnica comum com muitas variantes conhecidas. Adequação já está definida no documento PCF de Plotkin.

[[t_{1}]] = [[t_{2}]] ⟹ t_{1} ≅ t_{2} .

$[\![ t_1 ]\!] = [\![ t_2 ]\!] \implies t_1 \cong t_2.$

Andrej Bauer
fonte

≅

$\cong$

Obrigado pela resposta, mas -1: Embora eu concorde, a pergunta menciona sistemas de tipo puro - AFAICS, uma semântica denotacional para sistemas de tipo puro é um problema em aberto, então acho que uma resposta deve apontar para uma semântica denotacional. (De fato, se eu tivesse uma semântica denotacional, prescindiria totalmente da operacional, como mencionado na pergunta). (. Mas desculpe pela excessivamente longa pergunta)

Blaisorblade

@ MartinBerger, eu não entendo suas críticas. O OP pede métodos para mostrar equivalência observacional, eu menciono um comum, e então você objeta que existem outras maneiras que evitam o método?

Andrej Bauer

@ Blaisorblade, bem, então você terá que inventar uma semântica denotacional para sistemas de tipo puro, não é? :-) Mas, mais a sério, perguntarei a Alex Simpson, ele saberia melhor sobre semântica denotacional para essas coisas.

Andrej Bauer

@AndrejBauer Não era para ser uma crítica, mas um adendo.

Martin Berger

$\eta$

cody
fonte

Não acho que o doutorado de Streicher seja sobre PTS. Trata-se da semântica dos resultados do Cálculo de Construções e da independência via semântica de confiabilidade. Veja aqui .

Martin Berger

Obrigado pelo esclarecimento! Receio que o link esteja quebrado (e difícil de corrigir com o link minificado).

Cody

O link foi para a tabela de conteúdo do livro aqui . Espero que este funcione melhor.

Martin Berger

λ^{*}

$\lambda^*$

@MartinBerger: você quer dizer semântica de realização?

Dominique Devriese

Esta resposta sugere uma abordagem para o problema. (Comentários são bem-vindos).

O capítulo 49 da PFPL discute, ao mesmo tempo, as noções equivalentes de equivalência observacional e equivalência lógica. A equivalência lógica é a mesma relação usada para declarar a parametridade; portanto, o núcleo do capítulo é uma prova de parametridade para o Sistema F.

O trabalho sobre parametridade para PTS, AFAICT, não discute a relação com equivalência observacional. De fato, para definir a equivalência observacional, a menos que você não tenha terminação, você precisa de algum tipo de terreno positivo (natural, booleano) para usar nas observações.

No entanto, o teorema chave (PFPL 47.6, 48.3, 49.2) para relacionar as duas relações é comprovado independentemente do idioma específico:

A equivalência observacional é a congruência consistente mais grosseira nas expressões.

Então, para mostrar que a equivalência lógica implica equivalência observacional, basta mostrar que a equivalência lógica é uma congruência consistente. No entanto, a outra direção exige mais trabalho: em particular, para mostrar que a equivalência lógica é uma congruência, procede-se por indução em contextos.

n + 1 = 1 + nVecN nnVecNVecN $n + 1 = 1 + n$ Vec (n + 1)Vec (1 + n)n + 11 + n

Blaisorblade
fonte