La teoría de tipos estudia sistemas que clasifican los valores en tipos para que los programas sin sentido se rechacen antes de ejecutarse. Nació como fundamento de las matemáticas y se convirtió en la teoría detrás de los lenguajes tipados y los asistentes de demostración. Su idea central es que un programa y una demostración son el mismo tipo de objeto.
Conceptos clave
- Cálculo lambda simplemente tipado: el lenguaje tipado más pequeño, donde todo término bien tipado termina.
- Polimorfismo: una definición que sirve para muchos tipos, mediante genéricos paramétricos o clases de tipos.
- Tipos de datos algebraicos: sumas y productos que construyen datos estructurados y hacen comprobable el reconocimiento de patrones.
- Correspondencia de Curry-Howard: los tipos son proposiciones, los programas son demostraciones y ejecutar un programa simplifica una demostración.
- Tipos dependientes: tipos que mencionan valores, como vectores de longitud n, de modo que se comprueban más propiedades de forma estática.
Vocabulario
- Juicio de tipado: un enunciado de que un término tiene un tipo en un contexto, escrito con un símbolo de derivación.
- Seguridad de tipos: los programas bien tipados no se atascan, lo que se prueba con progreso y preservación.
- Inferencia de tipos: el compilador deduce los tipos que omitiste.
- Subtipado: un tipo puede ocupar el lugar de otro esperado, por ser más específico.
Qué estudiar, en orden
- El cálculo lambda sin tipos: escribe a mano la reducción y los numerales de Church.
- Implementa un verificador de tipos para el cálculo lambda simplemente tipado en unas pocas decenas de líneas.
- Añade polimorfismo e inferencia de tipos, y lee cómo funciona la unificación de Hindley-Milner.
- Demuestra en papel el progreso y la preservación para un lenguaje diminuto.
- Usa un asistente de demostración con tipos dependientes para probar que una función sobre listas es correcta.
Etiquetas relacionadas
#logic #functional-programming #haskell #formal-methods #language-design