¿Los tipos dependientes le dan todo lo que hace el subtipo?

Tipos y lenguajes de programación se enfoca bastante en el subtipo, pero por lo que puedo decir, el subtipo no parece especialmente fundamental. ¿El subtipo le da algo más que los tipos dependientes? Trabajar con tipos dependientes seguramente será más trabajo, por lo que puedo entender por qué los subtipos pueden ser útiles en la práctica. Sin embargo, estoy más interesado en la teoría de tipos como base para las matemáticas que como base para los lenguajes de programación, ¿debería prestar mucha atención al subtipo?

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

Respuestas:

Los subtipos y los tipos dependientes son conceptos ortogonales.

El subtipo generalmente está equipado con una noción de subsunción, por lo que una expresión de un tipo puede aparecer en el lugar donde se espera un supertipo.

La subtipificación es más probable que sea decidible y es más simple de administrar en la implementación.

La escritura dependiente es mucho más expresiva. Pero si alguna vez quiere considerar que un grupo también es un monoide, entonces necesita una noción de subsunción para olvidar la estructura adicional. A menudo, como cuando se usa Coq, se genera una obligación de prueba trivial para lidiar con este tipo de coerción, por lo que en la práctica el subtipo puede no agregar nada. Lo que es más importante es tener formas de agrupar varias teorías para hacerlas reutilizables, como reutilizar la teoría de los monoides cuando se habla de grupos. Las clases de tipos en Coq son una innovación reciente para hacer tales cosas. Los módulos son un enfoque más antiguo.

Si realiza una búsqueda rápida en Google de "subtipos de tipos dependientes", encontrará un montón de trabajo agregando subtipos a tipos dependientes, principalmente a partir del año 2000. Me imagino que la metateoría es realmente desafiante, por lo que no aparece ningún subtipo de tipos dependientes en asistentes de prueba.

Dave Clarke
fuente

Gracias, esto es exactamente lo que estaba buscando. He hecho un par de preguntas novatas ahora que parecen haber sido bien recibidas a pesar de que cstheory.SE no es el lugar adecuado para tales preguntas. En una escala de -5 a +5, ¿alentarías o desalentarías preguntas similares en el futuro? Como nota al margen, según tengo entendido (de la lectura de Robert Harper), las clases de tipos son una subcategoría de módulos, ¿no es así?

John Salvatier

Esta pregunta está en el lado derecho del borde de lo que es adecuado para cstheory.SE. Las clases de tipos no son realmente una subcategoría de módulos. Es más como que las clases de tipos son módulos + inferencia de tipos + free_plumbing.

Dave Clarke

Me imagino que siempre puedes modelar / simular subtítulos con tipos dependientes con bastante facilidad. En Haskell, HList (que se basa en la igualdad de tipos decidible) le ofrece subtipos, por ejemplo (cf "Sistema de objetos ignorados de Haskell"). La única parte difícil de los subtítulos es la inferencia de tipos, y una vez que trabajas con tipos dependientes, de todas formas descartas el 90%.

sclv

(cambiado de un comentario a una respuesta)

Neel Krishnaswami

La teoría de subconjuntos de la teoría de tipos de Martin-Loef es básicamente lo que necesita para modelar el olvido de estructuras, y eso se remonta a la década de 1980. Creo que esto es algo a lo que @Neel se refiere en su respuesta.

Charles Stewart

Sin embargo, estoy más interesado en la teoría de tipos como base para las matemáticas que como base para los lenguajes de programación, ¿debería prestar mucha atención al subtipo?

Una cosa adicional que le da el subtipo es que la subsunción implica que se mantienen muchas propiedades de coherencia. Una teoría de tipo dependiente también necesita una noción de irrelevancia de prueba para modelar todo lo que puede hacer con subtipos. Por ejemplo, en la teoría del tipo dependiente puede aproximarse formando un subconjunto con un registro dependiente:

{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)$

Una vez que tenga eso, puede elaborar sistemáticamente el subtipo en la teoría del tipo dependiente. Ver la tesis de William Lovas para un ejemplo de agregar subtipos a una teoría de tipo dependiente (en este caso, Twelf).

Neel Krishnaswami
fuente