Saltar al contenido ForoHackers

Teoría de tipos: por dónde empezar

Teoría de tipos
#3408 · · Citar · 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

No has iniciado sesión, así que esto se publica como anónimo: no se guarda con ello ninguna cuenta, nombre ni dirección, y no puede llevar enlaces ni imágenes. Inicia sesión o únete para publicar con tu nombre. Los registros de nuestro servidor web guardan la dirección y la hora de cada petición hasta 14 días; para que la tuya no quede en ellos, usa Tor. Para escribir al equipo de forma confidencial, usa el buzón. Firmar como fuente habitual (una clave guardada solo en este navegador)

Enviar tarda unos segundos aquí: tu navegador resuelve antes una prueba de trabajo contra el spam.

Responder