Tipos dependientes y subestructurales

Los tipos dependientes permiten que los tipos dependan de los valores, lo que posibilita especificaciones precisas, mientras que los tipos subestructurales, como los tipos lineales y afines, controlan cómo se utilizan los recursos.

Definition

Los tipos dependientes son tipos que dependen de valores, lo que permite establecer y verificar propiedades precisas a nivel de tipo; los sistemas de tipos subestructurales restringen cómo las variables (recursos) pueden duplicarse o descartarse, y los tipos lineales requieren que cada una se use exactamente una vez.

Scope

Este tema abarca disciplinas de tipado avanzadas que van más allá de los sistemas convencionales: los tipos dependientes, en los que los tipos pueden mencionar valores de programa, permitiendo que los tipos expresen especificaciones completas y sirvan como pruebas; y los tipos subestructurales (lineales, afines, de propiedad), que restringen las reglas estructurales de contracción y debilitamiento para rastrear el uso de recursos, el aliasing y las vidas útiles. Se conecta con la correspondencia de Curry-Howard y con los asistentes de prueba.

Core questions

• ¿Cómo pueden los tipos depender de los valores para expresar especificaciones completas del programa?
• ¿Cuál es la correspondencia entre los tipos dependientes y las pruebas constructivas?
• ¿Cómo modelan los tipos lineales y afines los recursos, la propiedad y la seguridad de la memoria?
• ¿Cuáles son las compensaciones en la decidibilidad y la usabilidad de estos ricos sistemas?

Key theories

Teoría de tipos intuicionista (dependiente)

La teoría de tipos de Martin-Löf unifica la programación y la lógica constructiva de modo que los tipos son proposiciones y los programas son pruebas, proporcionando la base para lenguajes con tipos dependientes y asistentes de prueba.

Lógica lineal y tipos lineales

La lógica lineal de Girard refina la lógica clásica e intuicionista controlando las reglas estructurales, y Wadler demostró cómo los tipos lineales basados en ella pueden gestionar de forma segura la actualización in situ y el uso de recursos.

Estática para sistemas subestructurales

Harper desarrolla la metateoría de los sistemas de tipos subestructurales y otros avanzados dentro de un marco uniforme de estática y dinámica, aclarando su solidez e interpretación de recursos.

Clinical relevance

Los tipos dependientes impulsan los asistentes de prueba y el software verificado, donde los programas vienen con garantías de corrección verificadas por máquina. Los tipos subestructurales y de propiedad sustentan los lenguajes de sistemas seguros para la memoria y la concurrencia, lo que permite una gestión manual segura de los recursos sin un recolector de basura.

History

La teoría de tipos intuicionista de Martin-Löf (décadas de 1970-1980) estableció los tipos dependientes y la visión de proposiciones como tipos, lo que llevó a asistentes de prueba como Coq, Agda y Lean. La lógica lineal de Girard de 1987 introdujo el razonamiento sensible a los recursos; los tipos lineales de Wadler lo incorporaron al diseño de lenguajes, y las disciplinas de propiedad y verificación de préstamos hicieron que las ideas subestructurales se generalizaran en la programación de sistemas.

Debates

Expresividad versus usabilidad y decidibilidad

Los sistemas con tipos dependientes y subestructurales pueden expresar garantías muy sólidas, pero aumentan la carga para los programadores y pueden hacer que la verificación de tipos sea indecidible u onerosa, lo que impulsa el debate sobre cuánto poder vale la pena el costo.

Key figures

• Per Martin-Löf
• Jean-Yves Girard
• Philip Wadler
• Robert Harper

Seminal works

• martinlof1984
• girard1987
• wadler1990
• harper2016

Frequently asked questions

¿Qué es un tipo dependiente?

Un tipo dependiente es un tipo cuya definición depende de un valor, como el tipo de vectores de una longitud específica, lo que permite que el sistema de tipos imponga invariantes ricos que los tipos ordinarios no pueden expresar.

¿Qué garantizan los tipos lineales?

Los tipos lineales requieren que cada valor se use exactamente una vez, lo que permite que un compilador permita de forma segura la actualización in situ, gestione los recursos y prevenga errores relacionados con el aliasing sin recolección de basura en tiempo de ejecución.