Somos capazes de provar um teorema de parametridade livre sobre funções como ? Supõe-se que pega uma lista e sempre retorna uma permutação dela.
Outro exemplo: prove que a função sempre retornará uma lista permutada com exatamente um elemento copiado.
linear-logic
parametricity
Łukasz Lew
fonte
fonte
Respostas:
Várias pessoas estão interessadas em provar esse tipo de coisa. Neel Krishnaswami mencionou esse teorema em particular aqui . Também vi Frank Pfenning dar alguns exemplos interessantes de lógicas ordenadas. Por exemplo, se você tiver , em um sistema de tipos ordenados, deve anexar as listas e .A,x:[A],y:[A]⊢e:[A] e x y
A resposta curta é que sim, podemos provar seu primeiro exemplo. No contexto do cálculo lambda, uma abordagem lógica baseada em relações é descrita neste artigo . Eles provariam seu teorema em duas etapas:
Porém, esses tipos de teoremas ficam mais interessantes quando analisamos uma linguagem com efeitos e nossa capacidade de prová-los para essas linguagens é tristemente limitada. Por exemplo, considere o isomorfismo do Sistema F. Em uma configuração de chamada por valor, esse isomorfismo é interrompido quando adicionamos não terminação. Porém, devemos recuperar um isomorfismo semelhante com tipos lineares: . Infelizmente, não temos relações lógicas operacionais que possam provar isso.τ≅∀A.(τ→A)→A τ≅∀A.(τ→A)⊸A
Dito isto, também existem métodos sintáticos que podem provar esse isomorfismo e seu teorema. Essa parece ser uma abordagem particularmente útil em um cenário linear e é muito menos onerosa do que estabelecer uma relação lógica para provar teoremas simples.
Edit: Desde que você perguntou, aqui está um exemplo de uma prova sintática de um teorema livre para o tipo em uma configuração com um termo que fica em loop para sempre e é bem digitado em qualquer contexto e tipo. A idéia é encontrar um conjunto de termos canônicos de um tipo e usá-lo para determinar quais são os possíveis valores de retorno para uma função. Começamos com um teorema da solidez para termos bem digitados.∀A.(A⊗A)⊸A ⊥
Aqui, é sua noção favorita de equivalência para o idioma e é um ambiente que contém variáveis de tipo livre. Considerarei variáveis livres como valores. Para linguagens simples, um argumento direto de progresso e preservação pode ser feito para justificar esse teorema.≈ Δ x
Agora, com um valor , sabemos que onde . Do tipo de e, temos alguns casos possíveis:⊢f:∀A.(A⊗A)⊸A f≈λx.e A;x:(A⊗A)⊢e:A
Como o segundo caso é o único que resta, assumimos onde . Até agora na prova, estabelecemos que . Finalmente, aplicamos nosso teorema de canonicidade mais uma vez e descobrimos que deve divergir: os únicos valores do tipo são variáveis, mas temos duas variáveis no contexto, portanto não pode ser o caso que .e≈ let(x1,x2)=x in e′ A;x1:A,x2:A⊢e′:A f≈λx.let (x1,x2)=x in e′ e′ A e′≈xi
Portanto, temos que o único habitante de todos é é .∀A.(A⊗A)⊸A λx.⊥≈λx.let (x1,x2)=x in ⊥
Você pediu uma referência para esse tipo de prova, mas não tenho certeza de uma boa. Esse tipo de raciocínio é bem conhecido em certos círculos e remonta talvez até Gentzen. Disseram-me que é uma reminiscência da pesquisa de provas focada em cálculo sequencial, mas não sei exatamente qual é a conexão.
Dito isto, não conheço nenhum trabalho publicado moderno que explique bem esse método relativamente simples. É certo que é um pouco limitado em sua aplicabilidade a idiomas mais simples. Por outro lado, acho que foi ofuscado por "Teoremas de graça!" et al. e, como resultado, muitos pesquisadores seniores imediatamente pensam em relações lógicas quando ouvem a frase "teorema livre", sem saber que técnicas como essa podem ser uma abordagem alternativa mais simples a essas provas (especialmente no contexto de sistemas de tipos lineares).
Quanto ao seu segundo exemplo, não acho que o teorema livre que você deseja tenha. Eu poderia, por exemplo, instanciar com o tipo inteiro e depois passar uma função que retorna números inteiros que não estão na lista que dou para . Talvez esteja mais próximo do tipo que você tinha em mente. Mas, mesmo assim, nenhuma função do tipo existe, pois ela teria que duplicar sua entrada.A f ∀A.(∀B.B⊸(B,B))⊸[A]⊸[A] ∀B.B⊸(B,B)
fonte