Skip to the content ForoHackers
Log inJoin

Teoría de tipos: por dónde empezar

Type theory
#3408 · · Quote · Report

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

You are not logged in, so this goes up anonymously: no account, no name and no address is stored with it, and it may carry no link and no image. Log in or join to post under your name. Our web server's logs keep the address and time of every request for up to 14 days; to keep yours out of them, use Tor. To reach the staff in confidence, use the drop. Sign as a returning source (a key kept only in this browser)

Sending takes a few seconds here: your browser first works out a proof of work against spam.

Reply