O que ganhamos por ter "tipos dependentes"?

Eu pensei ter entendido a digitação dependente (DT) corretamente, mas a resposta a esta pergunta: /cstheory/30651/why-was-there-a-need-for-martin-l%C3% A teoria do tipo B6f para criar intuicionista me fez pensar o contrário.

Depois de ler sobre a TD e tentar entender o que são, estou tentando imaginar o que ganhamos com essa noção de TD. Eles parecem ser mais flexíveis e poderosos do que simplesmente o cálculo lambda digitado (STLC), embora eu não possa entender exatamente "como / por que".

O que podemos fazer com DTs que não podem ser feitas com STLC? Parece que adicionar DTs torna a teoria mais complicada, mas qual é o benefício?

Da resposta à pergunta acima:

Os tipos dependentes foram propostos por De Bruijn e Howard, que queriam estender a correspondência de Curry-Howard da lógica proposicional para a lógica de primeira ordem.

Isso parece fazer sentido em algum nível, mas ainda não consigo entender o panorama geral de "como / por que"? Talvez um exemplo mostre explicitamente que essa extensão da correspondência do CH com a lógica do FO possa ajudar a entender o que é o grande problema das TDs? Não tenho certeza se compreendo isso também.

logic type-theory intuition Doutorado
fonte

Você os pesquisou no Google? Você já ouviu falar de Coq, um provador de teoremas construído com tipos dependentes? Você sabia que o teorema das 4 cores foi comprovado usando Coq?

Dave Clarke

Na verdade eu fiz. O que é difícil para o Google é o que é esse "poder" extra (por falta de uma palavra melhor) que as DTs emprestam à teoria do tipo, falando intuitivamente?

PhD

Por quê? Os tipos dependentes permitem digitar mais programas enquanto ainda são seguros para o tipo. Quão? Parametrizando tipos com programas.

Martin Berger

@MartinBerger - Você pode elaborar "mais programas"? O que "mais" posso fazer ou precisar, do ponto de vista teórico?

PhD

@DaveClarke That Coq, com seus tipos extravagantes, tem sido usado para fazer coisas extravagantes não implica que essas coisas extravagantes exijam esses tipos extravagantes. Por exemplo, o Twelf teve grandes sucessos (como uma prova de correção do SML) e é apenas de segunda ordem, não de ordem superior. Eu já vi alguns sistemas muito grandes provados apenas com lógica de primeira ordem.

Gilles 'SO- stop be evil'

Respostas:

Expandindo meu comentário: Tipos dependentes podem digitar mais programas. "Mais" significa simplesmente que o conjunto de programas tipificáveis com tipos dependentes é um superconjunto adequado dos programas tipificáveis no calccul (STLC) de tipo simples. Um exemplo seria , as listas de comprimento , contendo elementos do tipo . A expressão é ao mesmo tempo um programa e parte de um tipo. Você não pode fazer isso no STLC. $\lambda$ $List_{2*3+4}(\alpha)$ $10$ $\alpha$ $2*3+4$

A regra principal que distingue os tipos dependentes dos não dependentes é a aplicação:

\frac{Γ ⊢ M : A \to B Γ ⊢ N : A}{Γ ⊢ M N : B} \frac{Γ ⊢ M : Π x^{A} . B Γ ⊢ N : A}{Γ ⊢ M N : B {N / x}}

$\newcommand{\TYPES}[3]{#1 \vdash #2 : #3} \newcommand{\SUBST}[2]{\{#1/#2\}} \frac{ \TYPES{\Gamma}{\color{red}{M}}{A \rightarrow B} \qquad \TYPES{\Gamma}{\color{red}{N}}{A} }{ \TYPES{\Gamma}{\color{red}{MN}}{B} } \qquad \frac{ \TYPES{\Gamma}{{\color{red}M}}{\Pi x^A. B} \qquad \TYPES{\Gamma}{\color{red}{N}}{A} }{ \TYPES{\Gamma}{{\color{red}{MN}}}{B\SUBST{{\color{red}N}}{x}} }$

À esquerda, você tem o STLC, onde os programas nas instalações 'fluem' apenas para o programa da conclusão. Por outro lado, na regra de aplicação dependente à direita, o programa da premissa certa 'flui' para o tipo na conclusão . $N$ $^1$

Para poder parametrizar tipos por programas, a sintaxe dos tipos dependentes deve ser mais rica e, para garantir que os tipos sejam bem formados, usamos um segundo 'sistema de digitação' chamado tipos que restringe os tipos. Este sistema de classificação é essencialmente o STLC, mas "um nível acima".

Existem muitas explicações sobre os tipos dependentes. Alguns exemplos.

Tipos dependentes no trabalho , de Bove e Dybjer.
Tipos dependentes, de Aspinall e Hofmann.
Programação dependente digitada na Agda , por Norell e Chapman.
Cálculos lambda com tipos , de Barendregt.

$^1$

Martin Berger
fonte

Agora, isso faz muito sentido. Pode ter sido óbvio, mas por alguma razão eu não pude colocar um dedo nela. Aprecie a transição do comentário para a resposta. Infelizmente, a questão tem sido votado para fechar, mas estou feliz pela resposta :)

PhD

A r r n

$\mathrm{Arr}\ n$

A r r 0 = n a t

$\mathrm{Arr}\ 0 = \mathrm{nat}$

A r r (n + 1) = n a t \to A r r n

$\mathrm{Arr}\ (n+1) = \mathrm{nat}\rightarrow\mathrm{Arr}\ n$

P ⇓ V

$P\Downarrow V$

e r a s e (P) ⇓ e r a s e (V)

$erase(P)\Downarrow erase(V)$

⇓

$\Downarrow$

F_{ω}

$F_\omega$

C o C

$\mathrm{CoC}$

@ Cody Eu acho incomum chamar esse tipo de apagamento. Qual o melhor nome? Talvez simplificação de tipo?

27515 Martin Specker

Pense nas declarações de tipo como nada além de asserções. Atualmente, tudo o que você pode dizer são coisas como isInt32 (), isCharPtr (), etc. Essas várias asserções são escolhidas para serem verificáveis em tempo de compilação. Mas esse conceito pode ser expandido para coisas como: isCharPtr () && isNotNull (). Ponteiros anuláveis são um grande problema. Os ponteiros não devem ser anuláveis como a postura padrão, com os ponteiros anuláveis sendo um tipo que não é referenciável sem saber se é nulo ou não. Problemas semelhantes são: isPositiveInteger () ou isEvenNaturalNumber ().

Roubar
fonte