Inferencia de tipos
La inferencia de tipos reconstruye automáticamente los tipos de las expresiones, lo que permite a los programadores omitir anotaciones mientras el compilador calcula una tipificación más general.
Definition
La inferencia de tipos (reconstrucción de tipos) es el proceso de deducir un tipo válido y más general para una expresión a partir de su estructura y uso, sin requerir que el programador proporcione todas las anotaciones de tipo.
Scope
Este tema abarca algoritmos y teoría para inferir tipos sin anotaciones explícitas, centrándose en el sistema Hindley-Milner y el Algoritmo W con su uso de unificación y polimorfismo let. Aborda los tipos principales, la decidibilidad y la complejidad, y las dificultades de extender la inferencia a sistemas más ricos con subtipado, polimorfismo de orden superior o tipos dependientes.
Core questions
- ¿Cómo puede un compilador reconstruir tipos cuando no se han escrito?
- ¿Qué es un tipo principal y cuándo existe siempre uno?
- ¿Cómo impulsa la unificación la inferencia Hindley-Milner?
- ¿Por qué la inferencia se vuelve indecidible o incompleta en sistemas de tipos más ricos?
Key theories
- Inferencia de tipos Hindley-Milner
- La disciplina de tipos polimórficos de Milner, con el Algoritmo W, infiere tipos para un cálculo lambda con polimorfismo ligado por let utilizando unificación, formando la base de la inferencia en los lenguajes de la familia ML.
- Esquemas de tipos principales
- Damas y Milner demostraron que toda expresión tipificable tiene un esquema de tipo principal, el tipo más general del cual todas sus instancias de tipos válidos son, y que el Algoritmo W lo calcula.
- Tipos principales en lógica combinatoria
- Hindley estableció la existencia de tipos principales para términos tipificables, un resultado antecedente que subyace a la inferencia de tipos de lenguajes de programación posteriores.
Clinical relevance
La inferencia de tipos hace que los lenguajes tipados estáticamente sean mucho más convenientes al eliminar la carga de anotaciones mientras se preserva la seguridad, y potencia las características de los editores modernos como las sugerencias de tipo y el autocompletado. Sus límites en sistemas expresivos determinan dónde los programadores aún deben proporcionar anotaciones.
History
El trabajo de Hindley de 1969 sobre tipos principales en lógica combinatoria anticipó la inferencia práctica. El artículo de Milner de 1978 introdujo el sistema de tipos polimórficos y el Algoritmo W para ML, y el artículo de Damas y Milner de 1982 demostró la principalidad. El sistema Hindley-Milner se convirtió en el estándar para ML, Haskell y muchos lenguajes posteriores, con investigación continua que extiende la inferencia a entornos más ricos.
Debates
- Cuánto inferir versus anotar
- A medida que los sistemas de tipos se vuelven más expresivos, la inferencia completa se vuelve indecidible, lo que provoca un debate sobre cuánto debe inferirse automáticamente versus lo que se requiere como anotaciones explícitas para mantener la inferencia manejable y predecible.
Key figures
- Robin Milner
- Luis Damas
- Roger Hindley
- Benjamin Pierce
Related topics
Seminal works
- milner1978
- damas1982
- hindley1969
- pierce2002
Frequently asked questions
- ¿Qué es un tipo principal?
- Un tipo principal es el tipo más general de una expresión, de modo que cualquier otro tipo válido para esa expresión es una instancia de sustitución del mismo; la inferencia Hindley-Milner siempre calcula un tipo principal cuando existe uno.
- ¿Por qué no todos los sistemas de tipos pueden inferir tipos automáticamente?
- La inferencia se basa en restricciones resolubles; en sistemas expresivos como los que tienen tipos de orden superior o dependientes, la inferencia completa se vuelve indecidible, por lo que el programador debe proporcionar algunas anotaciones.