Os tipos dependentes fornecem tudo o que a subtipagem fornece?

Tipos e linguagens de programação se concentra um pouco na subtipagem, mas até onde eu sei, a subtipagem não parece ser fundamental. A subtipagem oferece mais do que os tipos dependentes? Trabalhar com tipos dependentes deve ser mais trabalhoso, para que eu possa entender por que os subtipos podem ser úteis na prática. No entanto, estou mais interessado na teoria dos tipos como base para a matemática do que como base para linguagens de programação, devo prestar muita atenção à subtipagem?

lo.logic pl.programming-languages type-theory John Salvatier
fonte

Respostas:

Subtipagem e tipos dependentes são conceitos ortogonais.

A subtipagem normalmente é equipada com uma noção de subsunção, na qual uma expressão de um tipo pode aparecer no local em que um supertipo é esperado.

É mais provável que a subtipagem seja decidível e mais simples de gerenciar na implementação.

A digitação dependente é muito mais expressiva. Mas se você quiser considerar um grupo também um monóide, precisará de uma noção de subsunção para esquecer a estrutura extra. Freqüentemente, como ao usar o Coq, uma obrigação de prova trivial é gerada para lidar com esse tipo de coerção; portanto, na prática, a subtipagem pode não adicionar nada. O mais importante é ter maneiras de agrupar várias teorias para torná-las reutilizáveis, como reutilizar a teoria dos monoides ao falar sobre grupos. As classes de tipo no Coq são uma inovação recente para fazer essas coisas. Módulos são uma abordagem mais antiga.

Se você faz uma rápida pesquisa no Google sobre "subtipo de tipos dependentes", encontra um monte de trabalho adicionando subtipo a tipos dependentes, principalmente por volta do ano 2000. Imagino que a metateoria seja realmente desafiadora, portanto, nenhuma subtipo de tipos dependentes aparece em assistentes de prova.

Dave Clarke
fonte

Obrigado, é exatamente isso que eu estava procurando. Fiz algumas perguntas noob agora que parecem ter sido um pouco bem recebidas, embora cstheory.SE não seja o lugar certo para essas perguntas. Em uma escala de -5 a +5, você incentivaria ou desencorajaria perguntas semelhantes no futuro? Como uma observação lateral, pelo que entendi (da leitura de Robert Harper), as classes de tipo são uma subcategoria de módulos, certo?

John Salvatier

Esta questão está no lado direito da borda do que é adequado para cstheory.SE. As classes de tipo não são realmente uma subcategoria de módulos. É mais como classes de tipo são módulos + inferência de tipo + encanamento livre.

Dave Clarke

Eu imagino que você sempre pode modelar / simular subtipagem com tipos dependentes com bastante facilidade. No Haskell, o HList (que se baseia apenas na igualdade de tipos determinável) fornece subtipos, por exemplo (cf "Sistema de Objetos Negligenciados do Haskell"). A única parte difícil sobre a subtipagem é a inferência de tipos e, quando você trabalha com tipos dependentes, joga 90% disso de qualquer maneira.

Sclv

(mudou de um comentário a uma resposta)

Neel Krishnaswami

A teoria do subconjunto da teoria dos tipos de Martin-Loef é basicamente o que você precisa para modelar o esquecimento da estrutura, e que remonta à década de 1980. Eu acho que é isso que o @Neel está recebendo em sua resposta.

Charles Stewart

No entanto, estou mais interessado na teoria dos tipos como base para a matemática do que como base para linguagens de programação, devo prestar muita atenção à subtipagem?

Uma coisa extra que a subtipagem fornece é que a subsunção implica que muitas propriedades de coerência são válidas. Uma teoria do tipo dependente também precisa de uma noção de irrelevância da prova para modelar tudo o que você pode fazer com os subtipos. Por exemplo, na teoria dos tipos dependentes, você pode aproximar a formação de um subconjunto com um registro dependente:

{x \in S |; P (x)} vs. Σ x : S . P (x)

$\{x \in S \;|; P(x)\} \mbox{ vs. } \Sigma x:S.\;P(x)$

$S$ $P(x)$ $x:$

$X <: Y$ $x:X$ $x:Y$ $P(x)$ $P(x)$

Depois de ter isso, é possível elaborar sistematicamente a subtipagem na teoria dos tipos dependentes. Veja a tese de William Lovas para um exemplo de adição de subtipagem a uma teoria de tipos dependentes (neste caso, Twelf).

Neel Krishnaswami
fonte