Compreendendo a prova de forte normalização do cálculo de construções

9

Tenho dificuldades em entender a prova de forte normalização para o cálculo de construções. Tento seguir a prova no artigo de Herman Geuvers "Uma prova curta e flexível de Normalização Forte para o Cálculo de Construções".

Eu posso seguir bem a linha principal de raciocínio. Geuvers constrói para cada tipo uma interpretação base em alguma avaliação das variáveis ​​de tipo \ xi (\ alpha) . E então ele constrói alguma interpretação de termo (\! | M | \!) _ \ Rho com base em alguma avaliação das variáveis ​​de termo \ rho (x) e prova que, para avaliações válidas, a asserção (\! | M | \!) _ \ rho \ in [\! [T] \!] _ \ xi para todos os \ Gamma \ vdash M: T mantém.T[[T]]ξξ(α)(|M|)ρρ(x)(|M|)ρ[[T]]ξΓM:T

Meu problema: para tipos fáceis (como tipos do sistema F), a interpretação do tipo [[T]]ξ é realmente um conjunto de termos, portanto a asserção (|M|)ρ[[T]]ξ faz sentido. Porém, para tipos mais complexos, a interpretação [[T]]ξ não é um conjunto de termos, mas um conjunto de funções de algum espaço funcional apropriado. Eu acho que quase entendo a construção dos espaços funcionais, mas ele não pode atribuir nenhum significado a (|M|)ρ[[T]]ξ para os mais complexos tipos T .

Alguém pode explicar ou fornecer links para algumas apresentações mais compreensíveis da prova?

Edit: Deixe-me tentar esclarecer a questão. Um contexto Γ possui declarações para as variáveis ​​de tipo α:A e variáveis ​​de objeto. Uma avaliação de tipo é válida se, para todos (α:A)Γ com ΓA: então ξ(α)ν(A) for válido. Mas ν(A) pode ser um elemento de (SAT) e não apenas SAT . Portanto, nenhuma avaliação de termo válida pode ser definida para ρ(α) . ρ(α) deve ser um termo e não uma função de um espaço de função.

Edit 2: Exemplo que não funciona

Vamos fazer a seguinte derivação válida:

[]:axiom[α:]α:variable introduction[α:]:weaken[](Πα:.):product formation[β:Πα:.]β:(Πα:.)variable introduction

No último contexto, uma avaliação de tipo válida deve satisfazer . Para esse tipo de avaliação, não há avaliação de termo válida.ξ(β)ν(Πα:.)={f|f:SATSAT}

helmut
fonte
11
Metade das pessoas que lêem isso acham que é SAT. Você deve explicar o que é isso. Além disso, sua derivação parece um pouco estranha. A segunda linha não deve mencionar em sua conclusão, ela deve ler algo como , não deveria? SATα[α:]:
187 Andrej Bauer #
Estou usando a notação de Herman Geuvers (que parece ser padrão nesse domínio). é o conjunto de todos os conjuntos saturados de expressões lambda. Para a segunda linha da minha derivação: É a regra de introdução para variáveis ​​de um sistema de tipo puro. Essa regra diz onde é algum tipo. SATΓT:sΓ,x:Tx:Ts
Helmut
Eu entendo como você conseguiu a segunda linha, mas não é a premissa correta para a formação da terceira linha, é? Qual regra dá a terceira linha.
Andrej Bauer
A regra de formação de produtos do PTS diz cálculo das construções tem a regra . Isso me permite usar a primeira e a segunda linha para derivar a terceira.No entanto, tive um erro de digitação no meu post. na terceira linha tinha sido falta que acrescentei agora.r(s1,s2,s3;ΓA:s1;Γ,x:AB:s2Γ(Πx:A.B):s3r(,,)
Helmut
A primeira linha não deveria ler ? Ou você misturou e algum lugar? A segunda linha não pode ser a segunda premissa da regra de formação de produtos, porque isso significa que você está tentando formar algo como vez de . []:α:.αα:.
21320 Andrej Bauer

Respostas:

6

Infelizmente, não tenho certeza de que existem mais recursos amigáveis ​​para iniciantes do que a conta do Geuvers. Você pode tentar esta nota de Chris Casinghino, que apresenta várias provas com detalhes excruciantes.

Não sei se entendi a essência da sua confusão, mas acho que uma coisa importante a ser observada é o seguinte lema (Corolário 5.2.14), comprovado no texto clássico de Barendregt :

ΓM:T  ΓT: or 

Isso significa que enquanto pode ser uma função complicada, se mantido, então deve ser um conjunto de termos .[[T]]ξ ΓM:T[[T]]ξ

Isso é insinuado no esquema (seção 3.1), onde somente se , o que está de acordo com nossa expectativa, de que a interpretação de um tipo deve ser um conjunto de termos, por exemplo, (de fato, !)(|t|)σ[[T]]ξΓt:T:V()P(Term)V()=SAT

É uma situação comum na teoria dos tipos que, embora apenas estejamos interessados no "tipo base" (aqui ), ainda precisamos definir semântica para coisas de tipos mais altos (daí a necessidade de introduzir ) As coisas funcionam no final, porque apenas o tipo que habita os tipos é (e , mas isso não é realmente importante).SAT

cody
fonte
11
Obrigada pelo esclarecimento. Isso resolve meu problema de não entender as funções usadas na prova de Geuver. Eu já suspeitava de ler e reler o artigo de Geuver, mas você deixou claro.
precisa