divisão de divisão e polaridade dos tipos Pi

18

Em um tópico recente na lista de discussão da Agda, surgiu a questão das leis η , na qual Peter Hancock fez comentários instigantes .

Meu entendimento é que leis vêm com tipos negativos, ie. conectivos cujas regras de introdução são invertíveis. Para desabilitar para funções, Hank sugere o uso de um eliminador personalizado, com divisão de diversão , em vez da regra usual do aplicativo. Eu gostaria de entender a observação de Hank em termos de polaridades.ηη

Por exemplo, há duas apresentações -types. Existe o eliminador de divisão tradicional Martin-Löf , em um estilo positivo:Σ

Γf:(uma:UMA)(b:Buma)C(uma,b)Γp:Σuma:UMA.BΓspeuEutfp:Cp

E há a versão negativa:

Γp:Σuma:UMA.BΓπ0 0p:UMAΓp:Σuma:UMA.BΓπ1p:B[π0 0p/uma]

Esta última apresentação facilita a obtenção de para pares, ie. para qualquer par (onde == representa a igualdade de definição). Em termos de provabilidade, essa diferença não importa: intuicionisticamente, você pode implementar projeções com divisão ou o contrário.( π 0 p , π 1 p ) = = p pη(π0p,π1p)==pp

Agora, os tipos são geralmente (e sem controvérsia, acredito) tomados negativamente:Π

Γf:Πa:A.BΓs:AΓfs:B[s/a]

O que nos fornece para funções: .λ x . f x = = fηλx.fx==f

No entanto, nesse e-mail, Hank lembra do eliminador de divisões simples (Programação na teoria do tipo ML, [http://www.cse.chalmers.se/research/group/logic/book/], p.56). É descrito na estrutura lógica por:

fΠ(UMA,B)C(v)Set[vΠ(UMA,B)]d(y)C(λ(y))[y(x)B(x)[xUMA]]fvocênspeuEut(f,d)C(f)

Curiosamente, Nordstrom et al. motive esta definição dizendo que "[esta] forma não canônica alternativa se baseia no princípio da indução estrutural". Há um forte cheiro de positividade nessa declaração: as funções seriam 'definidas' pelo construtor .λ

No entanto, não consigo definir uma apresentação satisfatória dessa regra na dedução natural (ou, melhor ainda, no cálculo sequencial). O (ab) uso da estrutura lógica para introduzir parece crucial aqui.y

Então, é divertida uma apresentação positiva do tipo ? Também temos algo semelhante no cálculo sequencial (não dependente)? Como seria?Π

Quão comum / curioso é isso para os teóricos da prova em campo?

pedagand
fonte

Respostas:

12

A apresentação da eliminação funcional usando definitivamente não é uma ocorrência comum na maioria dos tratamentos da teoria dos tipos. No entanto, acredito que esta forma é realmente a apresentação "positiva" da eliminação de tipos funcionais. A questão aqui é que você precisa de uma forma de correspondência de padrões de ordem superior, veja, por exemplo, Dale Miller .fvocênspeuEut

Permita-me reformular sua regra de uma maneira mais clara para mim:

Γf:Πx:A.BΓ,z:Πx:A.BC:SetΓ,[x:A]F(x):Be:C{λx:A.F(x)/z}match f with λx:A.F(x)e:C{f/z}

Onde é um meta-variável do tipo no contexto .B x : AFBx:A

A regra de reescrita se torna:

mumatch λx:UMA.t WEuth λx:UMA.F(x)ee{t{você/x}/F(você)}

Isso permite que você defina o aplicativo como:

app(t,u)=match t with λx:A.F(x)F(u)

Além do fato de que isso exige que um sistema de tipos "estilo lógico de estrutura" seja válido, o aborrecimento (e a necessidade limitada) da unificação de ordem superior torna essa formulação impopular.

No entanto, existe um local em que a distinção positiva / negativa está presente na literatura: a formulação de predicados de relações lógicas . As duas definições possíveis (no caso unário) são

[[Πx:A.B]]={tu[[A]],tu[[B]]xu}

e

[[Πx:A.B]]={ttλx.t,u[[A]],t{u/x}[[B]]xu}

A segunda versão é menos comum, mas pode ser encontrada, por exemplo, em Dowek e Werner .

cody
fonte
1
Isso parece estar relacionado à sintaxe abstrata de ordem superior, amplamente utilizada no Logical Framework. Em particular, o aqui parece ser a meta-função. F
dia
13

Aqui está uma perspectiva um pouco diferente da resposta de Fredrik. Geralmente, as codificações impredicativas dos tipos da Igreja satisfarão as leis relevantes , mas não as leis .ηβη

Portanto, isso significa que podemos definir um par dependente da seguinte maneira:

x:X.Y[x]α:.(Πx:X.Y[x]α)α
Agora, observe que é facilmente definível: No entanto, você não pode definir a segunda projeção - experimente! Você só pode definir um eliminador fraco para isso, e é por isso que escrevi com um existencial.π 1 : x : X .π1pi 2 : Π p : ( x : X .
π1:x:X.Y[x]Xλp:(x:X.Y[x]).pX(λxy.x)
π2:Πp:(x:X.Y[x]).Y[π1p]

No entanto, a segunda projeção é realizável e, em um modelo paramétrico, você pode mostrar que também possui o comportamento correto. (Veja meu rascunho recente com Derek Dreyer sobre parametridade no Cálculo de construções para mais informações.) Então, acho que a projeção exige fundamentalmente algumas propriedades de extensionalidade fortes para que faça sentido.π2

Em termos de cálculo sequencial, o eliminador fraco possui uma regra que se parece um pouco com:

Γ,x:X,y:Y[x],Γe:CΓ,p:x:X.Y[x],Γlet(x,y)=pine:C
Aqui, as condições implícitas de boa formação implicam que não pode ocorrer gratuitamente emΓ 'pΓ ou . Se relaxarmos essa condição, obteremos a regra de divisão, que tem uma regra à esquerda que se parece com Essa substituição me lembra muito a regra de eliminação de Girard / Schroeder-Heister quanto à igualdade. Eu fiz uma perguntaC
Γ,x:X,y:Y[x],[(x,y)/p]Γe:[(x,y)/p]CΓ,p:x:X.Y[x],Γeuet(x,y)=pEune:C
sobre essa regra há um tempo, e David Baelde e Gopalan Nadathur apresentam a versão mais avançada em seu artigo sobre o LICS 2012, Combinando módulo de dedução e lógica de definições de ponto fixo . Acho que Conor McBride passou algum tempo pensando sobre a relação entre o tipo de identidade e a igualdade Schroeder-Heister, então você pode querer ver o que ele pensa.
Neel Krishnaswami
fonte
1
Estou gostando muito de todas essas respostas! Sinto que existe alguma noção de "introspecção" (a capacidade de saber que um termo tem um valor) implícita na resposta de Fredrik, que é o verdadeiro problema com eta: a parametridade implica introspecção implica eta.
Cody
10

Richard Garner escreveu um bom artigo sobre application vs funsplit, Sobre a força dos produtos dependentes na teoria dos tipos de Martin-Löf (APAL 160 (2009)), que também discute a natureza de ordem superior da regra do funsplit (com uma referência a Uma extensão natural da dedução natural de Peter Schroeder-Heister (JSL 49 (1984))).

Richard mostra que, na presença de tipos de identidade (e regras de formação e introdução para os tipos ), o funsplit é interderível com a regra de aplicação acima + eta proposicional, ou seja, as duas regras a seguir: Π

m:Π(UMA,B)η(m):EudΠ(UMA,B)(m,λx.mx)(Π-Suporte-η)
x:UMAf(x):B(x)η(λ(f))=refeu(λ(f)):EudΠ(UMA,B)(λ(f),λ(f))(Π-Suporte-η-Comp)

Ou seja, se você tiver uma divisão simples, poderá definir application e como acima, para que válido. Mais interessante, se você tiver aplicação e as regras eta proposicionais, poderá definir divisão simples.η(Π-Suporte-η-Comp)

Além disso, o funsplit é estritamente mais forte que a aplicação: as regras eta proposicionais não são definíveis em uma teoria com apenas aplicação - portanto, o funsplit não é definível, pois as regras eta proposicionais também seriam. Intuitivamente, isso ocorre porque as regras do aplicativo oferecem um pouco mais de folga: diferentemente do funsplit (e eta), eles não informam o que são funções, apenas que podem ser aplicadas aos argumentos. Acredito que o argumento de Richard também possa ser repetido para os tipos , para mostrar o mesmo resultado paraΣspeuEut projeções vs.

Observe que se você tivesse regras eta definicionais, certamente as teria proposicionalmente também (com ). Portanto, acho que suas afirmações "[...] que nos dão para funções" e "[...] esta última apresentação facilitam a obtenção de para pares" estão erradas. A Agda, no entanto, implementa para funções e pares (se for definido como um registro), mas isso não ocorre apenas no aplicativo.η(m): =refeu(m)ηηηΣ

Fredrik Nordvall Forsberg
fonte