Saltar al contenido ForoHackers

Teoría de tipos: por dónde empezar

Teoría de tipos
#902 · Ophuscado · · Denunciar

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

  1. El cálculo lambda sin tipos: escribe a mano la reducción y los numerales de Church.
  2. Implementa un verificador de tipos para el cálculo lambda simplemente tipado en unas pocas decenas de líneas.
  3. Añade polimorfismo e inferencia de tipos, y lee cómo funciona la unificación de Hindley-Milner.
  4. Demuestra en papel el progreso y la preservación para un lenguaje diminuto.
  5. 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

Inicia sesión o únete para responder.