Como você obtém o Cálculo de Construções dos outros pontos do Cubo Lambda?

Diz-se que o CoC é o culminar de todas as três dimensões do cubo Lambda. Isso não é aparente para mim. Acho que entendo as dimensões individuais, e a combinação de duas parece resultar em uma união relativamente direta (talvez esteja faltando alguma coisa?). Mas quando olho para o CoC, em vez de parecer uma combinação dos três, parece uma coisa completamente diferente. De qual dimensão Tipo, Prop e tipos pequeno / grande vêm? Para onde desapareceram os produtos dependentes? E por que há um foco em proposições e provas em vez de tipos e programas? Existe algo equivalente focado em tipos e programas?

Edit: Caso não esteja claro, estou pedindo uma explicação de como o CoC é equivalente à união direta das dimensões do cubo Lambda. E existe uma união real dos três por aí em algum lugar que eu possa estudar (ou seja, em termos de programas e tipos, não de provas e proposições)? Isso é uma resposta a comentários sobre a pergunta, não a respostas atuais.

lambda-calculus type-systems typed-lambda-calculus calculus-of-constructions indil
fonte

No mínimo, isso deve ser um soft-question. Não vejo uma pergunta técnica aqui. Talvez você possa ser um pouco mais específico quanto ao que está perguntando?

Andrej Bauer

@AndrejBauer Não é a pergunta: qual é a relação entre a apresentação do CoC em Barendregt-cubo / PTS e a apresentação original de Coquand & Huet?

Martin Berger

@AndrejBauer: A pergunta também parece estar se perguntando sobre a diferença na apresentação do CoC (de qualquer forma) e a ênfase em determinados recursos na prática. É verdade que a versão do CoC orientada ao PTS enfatiza alguns recursos como importantes, enquanto a prática do Coq enfatiza outros. Eu concordo que ele deveria ter a etiqueta da pergunta suave.

Jacques Carette

Fico feliz em ver que alguém será capaz de responder a isso.

Andrej Bauer

Respostas:

Primeiro, para reiterar um dos pontos de Cody, o Cálculo de Construções Indutivas (no qual o núcleo de Coq se baseia) é muito diferente do Cálculo de Construções. É melhor pensar em começar na teoria de tipos de Martin-Löf com universos e, em seguida, adicionar um tipo Prop na parte inferior da hierarquia de tipos. Este é um animal muito diferente do CoC original, que é melhor pensado como uma versão dependente do F-ômega. (Por exemplo, a CiC possui modelos teóricos e o CoC não.)

Dito isto, o cubo lambda (do qual o CoC é membro) é normalmente apresentado como um sistema de tipo puro por razões de economia no número de regras de digitação. Ao tratar tipos, tipos e termos como elementos da mesma categoria sintática, você pode escrever muito menos regras e suas provas também ficam um pouco menos redundantes.

No entanto, para entender, pode ser útil separar as diferentes categorias explicitamente. Podemos introduzir três categorias sintáticas, tipos (variados pelo metavariável k), tipos (variados pelo metavariável A) e termos (variados pelo metavariável e). Todos os oito sistemas podem ser entendidos como variações do que é permitido em cada um dos três níveis.

λ → (cálculo lambda de digitação simples)

 k ::= ∗
 A ::= p | A → B
 e ::= x | λx:A.e | e e

Este é o cálculo lambda básico digitado. Existe um único tipo ∗, que é o tipo de tipos. Os próprios tipos são tipos atômicos pe tipos de função A → B. Termos são variáveis, abstrações ou aplicativos.

λω_ (STLC + operadores do tipo superior)

 k ::= ∗ | k → k
 A ::= a | p | A → B | λa:k.A | A B
 e ::= x | λx:A.e | e e

O STLC permite apenas abstração no nível dos termos. Se o adicionarmos no nível dos tipos, adicionaremos um novo tipo, k → kque é o tipo de funções no nível do tipo, e abstração λa:k.Ae aplicação A Bno nível do tipo. Então agora não temos polimorfismo, mas temos operadores de tipo.

Se a memória servir, este sistema não terá mais poder computacional que o STLC; apenas oferece a capacidade de abreviar tipos.

λ2 (Sistema F)

 k ::= ∗
 A ::= a | p | A → B  | ∀a:k. A 
 e ::= x | λx:A.e | e e | Λa:k. e | e [A]

Em vez de adicionar operadores de tipo, poderíamos ter adicionado polimorfismo. No nível de tipo, adicionamos ∀a:k. Aqual é um antigo tipo polimórfico e, no nível de termo, adicionamos abstração sobre tipos Λa:k. ee aplicação de tipo e [A].

Este sistema é muito mais poderoso que o STLC - é tão forte quanto a aritmética de segunda ordem.

λω (Sistema F-ômega)

 k ::= ∗ | k → k 
 A ::= a | p | A → B  | ∀a:k. A | λa:k.A | A B
 e ::= x | λx:A.e | e e | Λa:k. e | e [A]

Se tivermos operadores de tipo e polimorfismo, obteremos o F-ômega. Este sistema é mais ou menos a teoria do tipo de kernel da maioria das linguagens funcionais modernas (como ML e Haskell). Também é muito mais poderoso que o Sistema F - é equivalente em força à aritmética de ordem superior.

λP (LF)

 k ::= ∗ | Πx:A. k 
 A ::= a | p | Πx:A. B | Λx:A.B | A [e]
 e ::= x | λx:A.e | e e

Em vez de polimorfismo, poderíamos ter ido na direção da dependência do cálculo lambda de tipo simples. Se você permitiu que o tipo de função deixasse seu argumento ser usado no tipo de retorno (ou seja, escreva em Πx:A. B(x)vez de A → B), você obtém λP. Para tornar isso realmente útil, precisamos estender o conjunto de tipos com um tipo de operador de tipo que aceita termos como argumentos Πx:A. ke, portanto, precisamos adicionar uma abstração Λx:A.Be aplicação correspondentes A [e]no nível de tipo.

Às vezes, esse sistema é chamado LF, ou Edinburgh Logical Framework.

Ele tem a mesma força computacional do cálculo lambda de tipo simples.

λP2 (sem nome especial)

 k ::= ∗ | Πx:A. k 
 A ::= a | p | Πx:A. B | ∀a:k.A | Λx:A.B | A [e]
 e ::= x | λx:A.e | e e | Λa:k. e | e [A]

Também podemos adicionar polimorfismo a λP, para obter λP2. Este sistema não é usado com frequência, portanto, não possui um nome específico. (O artigo que li que a utilizou é a indução de Herman Geuvers não é derivável na teoria de tipos dependentes de segunda ordem .)

Este sistema tem a mesma força que o sistema F.

λPω_ (sem nome especial)

 k ::= ∗ | Πx:A. k | Πa:k. k'
 A ::= a | p | Πx:A. B | Λx:A.B | A [e] | λa:k.A | A B 
 e ::= x | λx:A.e | e e

Também poderíamos adicionar operadores de tipo a λP, para obter λPω_. Isso envolve adicionar um tipo Πa:k. k'para operadores de tipo e abstração Λx:A.Be aplicativo de nível de tipo correspondente A [e].

Como novamente não há salto na força computacional sobre o STLC, esse sistema também deve ser uma boa base para uma estrutura lógica, mas ninguém conseguiu.

λPω (o cálculo de construções)

 k ::= ∗ | Πx:A. k | Πa:k. k'
 A ::= a | p | Πx:A. B | ∀a:k.A | Λx:A.B | A [e] | λa:k.A | A B 
 e ::= x | λx:A.e | e e | Λa:k. e | e [A]

Finalmente, chegamos ao λPω, o Cálculo de Construções, pegando λPω_ e adicionando uma abstração do tipo polimórfico ∀a:k.Ae uma abstração em nível de termo Λa:k. ee aplicação e [A]para ele.

Os tipos desse sistema são muito mais expressivos que no F-ômega, mas têm a mesma força computacional.

Neel Krishnaswami
fonte

É claro que tecnicamente o CoC (sem axiomas) tem pelo menos tantos modelos de teoria de conjuntos quanto o CiC, eles simplesmente não são muito bons em modelar a situação que queremos, que é o CoC com axiomas para os números naturais (digamos,

0 \neq 1

$0 \neq 1$

Cody

Eu também aprecio muito uma referência sobre a conservatividade de

sobre o STLC. Isso parece não óbvio.

λ ω_

$\lambda\omega\_$

Cody

@cody: Eu não sei uma referência - Kevin Watkins esboçou a prova para mim em um quadro branco! A idéia é que você use um termo digitado em λω_, coloque todos os tipos na forma beta longa normal e a incorpore ao STLC, introduzindo um novo tipo atômico para cada forma normal distinta no programa original. Então é óbvio que as seqüências de redução devem ser alinhadas individualmente.

Neel Krishnaswami

@ user833970 o fato de

não ser derivável é realmente muito mais simples do que os outros fatos mencionados, e não tem nada a ver com a codificação de

: vem do fato de que existe um modelo irrelevante de CC , em que tipos têm no máximo um elemento . Essa é uma propriedade ruim se você deseja uma lógica na qual existe um tipo com mais de um elemento (por exemplo, nat). Uma referência é: O modelo irrelevante de CC , não tão simples , de Miquel e Werner.

0 \neq 1

$0\neq 1$

n a t

$\mathrm{nat}$

Cody

Você diz que o Fw é "muito mais poderoso" que o Sistema F. Você tem uma referência para isso? Em particular, existe uma função nos números naturais que é comprovável total em Fw, mas não em F?

Thorsten Altenkirch

Eu sempre quis tentar resumir cada dimensão do cubo- e o que eles representam, então vou dar uma chance a este. $\lambda$

Mas, primeiro, deve-se tentar desembaraçar várias questões. O provador de teoremas interativos da Coq é baseado em uma teoria de tipos subjacente, às vezes chamada amorosamente de cálculo de construções indutivas com universos . Você notará que isso é mais emocionante do que simplesmente "Cálculo de Construções" e, de fato, há muito mais coisas além do CoC. Em particular, acho que você está confuso sobre exatamente quais recursos estão em CoC apropriados. Em particular, a distinção Set / Prop e universos não aparecem no CoC.

Não darei uma visão completa dos sistemas Pure Type aqui, mas a regra importante (para PTSes funcionais como o CoC) é a seguinte

\frac{Γ ⊢ A : s Γ, x : A ⊢ B : k}{Γ ⊢ Π x : A . B : k} (s, k) \in R

$\frac{\Gamma\vdash A:s\qquad \Gamma,x:A\vdash B:k}{\Gamma\vdash \Pi x:A.B\ :\ k}\ (s,k)\in R$

onde são elementos de um conjunto fixo das sortes e o par está em um conjunto fixo de pares de , chamados de regras . $s,k$ $S$ $(s,k)$ $R$ $S$

O insight crucial é que as escolhas cuidadosas de e fazer grandes diferenças no que o tipo de produto realmente representa! $S$ $R$ $\Pi x:A.B$

Em particular, no cálculo das construções, o conjunto de tipos é Freqüentemente chamado Prop e Type (embora essa terminologia seja um pouco confusa para um usuário de Coq por razões de que falarei mais adiante), e a descrição completa conjunto de regras: $S$

{*, ◻}

$\{*, \square\}$

R = {(*, *), (◻, ◻), (◻, *), (*, ◻)}

$R=\{(*,*),(\square,\square),(\square,*),(*,\square)\}$

E, portanto, temos 4 regras que correspondem a 4 propósitos diferentes:

: Tipos de funções $(*,*)$
$(\square,\square)$
$(\square,*)$
$(*,\square)$

Explicarei cada uma delas com mais detalhes.

$A\rightarrow B$ $\Pi x:A.B$ $x$ $B$

$*$ $\mathrm{nat}$ $\mathrm{bool}$ $x=y$ $x$ $y$ $*$

$\mathrm{list}$ $\mathrm{list}:*\rightarrow *$ $\mathrm{list}_{\mathrm{nat}}, \mathrm{list}_{\mathrm{bool}}$ $*\rightarrow *$ $(\square,\square)$

Π t : * . t \to t

$\Pi t:*.\ t\rightarrow t$

λ (t : *) (x : t) . x

$\lambda (t:*)(x:t).x$

Π t : * ._

$\Pi t:*.\_$

(◻, *)

$(\square, *)$

t \to t

$t\rightarrow t$

(*, *)

$(*,*)$

A \land B := Π t : * . (A \to B \to t) \to t

$A\wedge B := \Pi t:*.\ (A \rightarrow B\rightarrow t)\rightarrow t$

UMA \lor B : = Π t : * . (UMA \to t) \to (B \to t) \to t

$A\vee B := \Pi t:*.\ (A \rightarrow t)\rightarrow(B\rightarrow t)\rightarrow t$

⊥ : = Π t : * . t

$\bot := \Pi t:*.\ t$

⊤ : = Π t : * . t \to t

$\top := \Pi t:*.\ t\rightarrow t$

\exists x : A . P (x) := Π t : * . (Π y : A . P (y) \to t) \to t

$\exists x:A.\ P(x):= \Pi t:*.\ (\Pi y: A.\ P(y)\rightarrow t)\rightarrow t$

(*, ◻)

$(*,\square)$

$*$ $*$ $(\square, *)$

$(\square,\square)$

Π c : * \to * . c n a t \to c n a t

$\Pi c:*\rightarrow *.\ \ c\ \mathrm{nat}\rightarrow c\ \mathrm{nat}$

$0=1$

= : n a t \to n a t \to *

$=\ :\ \mathrm{nat}\rightarrow\mathrm{nat}\rightarrow *$

= : Π t : * . t \to t \to *

$=\ :\ \Pi t:*.\ t\rightarrow t\rightarrow *$

n a t \to n a t \to *

$\mathrm{nat}\rightarrow\mathrm{nat}\rightarrow *$

(*, ◻)

$(*,\square)$

$\square \rightarrow \square$ $\square$ $\square$ $\square_i$ $i=1,2,3,\ldots$ $\square_i:\square_{i+1}$

$(\square_i, \square_i)$

\frac{Γ ⊢ A : ◻_{i}}{Γ ⊢ A : ◻_{j}} i \leq j

$\frac{\Gamma\vdash A:\square_i}{\Gamma\vdash A:\square_j}\ i\leq j$

Com esses tipos e regras extras, você obtém algo que não é um PTS, mas algo próximo. Este é (quase) o Cálculo Estendido de Construções , que está mais próximo da base da Coq. A grande peça que falta aqui são os tipos indutivos, que não discutirei aqui.

Editar: há uma referência bastante interessante que descreve vários recursos das linguagens de programação no âmbito do PTSes, descrevendo um PTS que é um bom candidato para uma representação intermediária de uma linguagem de programação funcional:

Henk: uma linguagem intermediária digitada , SP Jones e E. Meijer.

cody
fonte

Tópicos avançados em Tipos e linguagens de programação, S2.6 e S2.7 .

precisa

BTW "Famílias de tipos" também são chamadas de tipos de classe superior.

Martin Berger

O PTS era uma boa ideia há 20 anos, mas as coisas mudaram desde então.

Thorsten Altenkirch

@ThorstenAltenkirch não há necessidade de exclusionismo, Thorsten! Ainda há algumas coisas divertidas a serem consideradas envolvendo PTSes, por exemplo, o trabalho de Bernardy sobre parametridade internalizada vem à mente.

cody

@cody Sem exclusionismo, mas não devemos ficar presos no passado da teoria dos tipos sintáticos. O trabalho de Bernardi é excelente e pode ser feito melhor usando universos.

Thorsten Altenkirch