Pensé que entendía el tipeo dependiente (DT) correctamente, pero la respuesta a esta pregunta: /cstheory/30651/why-was-there-a-need-for-martin-l%C3% B6f-to-create-intuitionistic-type-theory me ha hecho pensar lo contrario.
Después de leer sobre DT y tratar de entender lo que son, intento preguntarme, ¿qué ganamos con esta noción de DT? Parecen ser más flexibles y poderosos que simplemente el cálculo lambda mecanografiado (STLC), aunque no puedo entender exactamente "cómo / por qué".
¿Qué es lo que podemos hacer con DT que no se pueden hacer con STLC? Parece que agregar DT hace que la teoría sea más complicada, pero ¿cuál es el beneficio?
De la respuesta a la pregunta anterior:
De Bruijn y Howard propusieron tipos dependientes que querían extender la correspondencia de Curry-Howard de la lógica proposicional a la de primer orden.
Esto parece tener sentido en algún nivel, pero todavía soy incapaz de comprender el panorama general de "cómo / por qué"? ¿Quizás un ejemplo explícitamente muestre que esta extensión de la correspondencia CH a la lógica FO podría ayudar a dar en el blanco para entender cuál es el problema con los DT? No estoy seguro de comprender esto tan bien como debería.
fuente
Respuestas:
Ampliando mi comentario: los tipos dependientes pueden escribir más programas. "Más" simplemente significa que el conjunto de programas tipificables con tipos dependientes es un superconjunto adecuado de los programas tipificables en el cálculo tipo simple (STLC). Un ejemplo sería L i s t 2 ∗ 3 + 4 ( α ) , las listas de longitud 10 , que llevan elementos de tipo α . La expresión 2 ∗ 3 + 4 es al mismo tiempo un programa y parte de un tipo. No puede hacer esto en el STLC.λ List2∗3+4(α) 10 α 2∗3+4
La regla clave que distingue los tipos dependientes de los no dependientes es la aplicación:
A la izquierda tiene el STLC, donde los programas en las premisas 'fluyen' solo al programa de la conclusión. En contraste, en la regla de aplicación dependiente de la derecha, el programa de la premisa derecha 'fluye' al tipo en la conclusión .1N 1
Para poder parametrizar los tipos por programas, la sintaxis de los tipos dependientes debe ser más rica, y para garantizar que los tipos estén bien formados, utilizamos un segundo 'sistema de tipeo' llamado clases que restringe los tipos. Este sistema de clasificación es esencialmente el STLC, pero "un nivel más".
Hay muchas explicaciones de los tipos dependientes. Algunos ejemplos.
fuente
Piense en las declaraciones de tipo como nada más que afirmaciones. Actualmente, todo lo que puede decir es cosas como isInt32 (), isCharPtr (), etc. Estas diversas afirmaciones se eligen para que se puedan verificar en tiempo de compilación. Pero este concepto se puede ampliar a cosas como: isCharPtr () && isNotNull (). Los punteros anulables son un gran problema. Los punteros no deben ser anulables como la posición predeterminada, ya que los punteros anulables son un tipo que no puede ser desreferenciable sin saber si es nulo o no. Problemas similares son cosas como: isPositiveInteger () o isEvenNaturalNumber ().
fuente