La inferencia de tipos , a veces llamada reconstrucción de tipos , [1] : 320 se refiere a la detección automática del tipo de una expresión en un lenguaje formal . Estos incluyen lenguajes de programación y sistemas de tipos matemáticos , pero también lenguajes naturales en algunas ramas de la informática y la lingüística .
En un lenguaje mecanografiado, el tipo de un término determina las formas en que puede y no puede usarse en ese lenguaje. Por ejemplo, considere el idioma inglés y los términos que podrían llenar el espacio en blanco en la frase "sing _". El término "una canción" es de tipo cantable, por lo que podría colocarse en el espacio en blanco para formar una frase significativa: "cantar una canción". Por otro lado, el término “un amigo” no tiene el tipo cantable, por lo que “cantar un amigo” es una tontería. En el mejor de los casos, podría ser una metáfora; Flexionar las reglas tipográficas es una característica del lenguaje poético.
El tipo de un término también puede afectar la interpretación de las operaciones que involucran ese término. Por ejemplo, "una canción" es de tipo componible, por lo que la interpretamos como lo creado en la frase "escribir una canción". Por otro lado, “un amigo” es de tipo destinatario, por lo que lo interpretamos como el destinatario en la frase “escribe a un amigo”. En el lenguaje normal, nos sorprendería que "escribir una canción" significara dirigir una carta a una canción o "escribir a un amigo" significara redactar un borrador de un amigo en un papel.
Términos con diferentes tipos pueden incluso referirse materialmente a la misma cosa. Por ejemplo, interpretaríamos "colgar el tendedero" como ponerlo en uso, pero "colgar la correa" como guardarlo, aunque, en contexto, tanto "tendedero" como "correa" podrían referirse la misma cuerda, sólo que en diferentes momentos.
Los tipos se utilizan a menudo para evitar que un objeto se considere de forma demasiado general. Por ejemplo, si el sistema de tipos trata todos los números como iguales, entonces un programador que accidentalmente escribe código donde 4se supone que significa "4 segundos" pero se interpreta como "4 metros" no sería advertido de su error hasta que causara problemas en tiempo de ejecución. Al incorporar unidades al sistema de tipos, estos errores se pueden detectar mucho antes. Como otro ejemplo, la paradoja de Russell surge cuando cualquier cosa puede ser un elemento de conjunto y cualquier predicado puede definir un conjunto, pero una escritura más cuidadosa ofrece varias formas de resolver la paradoja. De hecho, la paradoja de Russell provocó las primeras versiones de la teoría de tipos.
Hay varias formas en que un término puede obtener su tipo:
delay: seconds := 4en su código, donde los dos puntos son el símbolo matemático convencional para marcar un término con su tipo. Es decir, esta declaración no solo establece delayel valor 4, sino que la delay: secondsparte también indica que delayel tipo es una cantidad de tiempo en segundos.Especialmente en los lenguajes de programación, es posible que no haya muchos conocimientos previos compartidos disponibles para la computadora. En lenguajes manifiestamente tipados , esto significa que la mayoría de los tipos deben declararse explícitamente. La inferencia de tipos tiene como objetivo aliviar esta carga, liberando al autor de declarar tipos que la computadora debería poder deducir del contexto.
En una tipificación, una expresión E se opone a un tipo T, escrito formalmente como E : T. Por lo general, una tipificación sólo tiene sentido dentro de algún contexto, que se omite aquí.
En este contexto, las siguientes preguntas son de particular interés:
Para el cálculo lambda escrito simplemente , las tres preguntas son decidibles . La situación no es tan cómoda cuando se permiten tipos más expresivos .
Los tipos son una característica presente en algunos lenguajes fuertemente tipados estáticamente . Suele ser característico de los lenguajes de programación funcionales en general. Algunos lenguajes que incluyen inferencia de tipos incluyen C23 , [2] C++11 , [3] C# (a partir de la versión 3.0), Chapel , Clean , Crystal , D , F# , [4] FreeBASIC , Go , Haskell , Java (a partir de con la versión 10), Julia , [5] Kotlin , [6] ML , Nim , OCaml , Opa , Q#, RPython , Rust , [7] Scala , [8] Swift , [9] TypeScript , [10] Vala , [11] Dart , [12] y Visual Basic [13] (a partir de la versión 9.0). La mayoría de ellos utilizan una forma simple de inferencia de tipos; El sistema de tipos Hindley-Milner puede proporcionar una inferencia de tipos más completa. La capacidad de inferir tipos automáticamente facilita muchas tareas de programación, dejando al programador la libertad de omitir anotaciones de tipo y al mismo tiempo permitir la verificación de tipos.
En algunos lenguajes de programación, todos los valores tienen un tipo de datos declarado explícitamente en tiempo de compilación , lo que limita los valores que una expresión particular puede tomar en tiempo de ejecución . Cada vez más, la compilación justo a tiempo desdibuja la distinción entre tiempo de ejecución y tiempo de compilación. Sin embargo, históricamente, si el tipo de un valor se conoce sólo en tiempo de ejecución, estos lenguajes se escriben dinámicamente . En otros lenguajes, el tipo de expresión sólo se conoce en el momento de la compilación ; Estos lenguajes están tipificados estáticamente . En la mayoría de los lenguajes de tipo estático, los tipos de entrada y salida de funciones y variables locales normalmente deben proporcionarse explícitamente mediante anotaciones de tipo. Por ejemplo, en ANSI C :
int add_one ( int x ) { int resultado ; /* declarar resultado entero */ resultado = x + 1 ; resultado de retorno ; } La firma de esta definición de función, int add_one(int x)declara que add_onees una función que toma un argumento, un número entero , y devuelve un número entero. int result;declara que la variable local resultes un número entero. En un lenguaje hipotético que admita la inferencia de tipos, el código podría escribirse así:
add_one ( x ) { var resultado ; /* resultado de variable de tipo inferido */ var resultado2 ; /* resultado variable de tipo inferido #2 */ resultado = x + 1 ; resultado2 = x + 1,0 ; /* esta línea no funcionará (en el idioma propuesto) */ devuelve resultado ; } Esto es idéntico a cómo se escribe el código en el lenguaje Dart , excepto que está sujeto a algunas restricciones adicionales, como se describe a continuación. Sería posible inferir los tipos de todas las variables en el momento de la compilación. En el ejemplo anterior, el compilador inferiría eso resulty xtendría un tipo entero ya que la constante 1es de tipo entero y, por lo tanto, add_onees una función int -> int. La variable result2no se usa de manera legal, por lo que no tendría un tipo.
En el lenguaje imaginario en el que está escrito el último ejemplo, el compilador supondría que, en ausencia de información en contrario, +toma dos números enteros y devuelve un número entero. (Así es como funciona, por ejemplo, OCaml ). A partir de esto, el inferenciador de tipos puede inferir que el tipo de x + 1es un número entero, lo que significa resultque es un número entero y, por lo tanto, el valor de retorno de add_onees un número entero. De manera similar, dado que +requiere que ambos argumentos sean del mismo tipo, xdebe ser un número entero y, por lo tanto, add_oneacepta un número entero como argumento.
Sin embargo, en la línea siguiente, result2 se calcula sumando un decimal 1.0con aritmética de punto flotante , lo que provoca un conflicto en el uso de xexpresiones tanto enteras como de punto flotante. El algoritmo de inferencia de tipos correcto para tal situación se conoce desde 1958 y se sabe que es correcto desde 1982. Revisa las inferencias anteriores y utiliza el tipo más general desde el principio: en este caso, punto flotante. Sin embargo, esto puede tener implicaciones perjudiciales, por ejemplo, usar un punto flotante desde el principio puede introducir problemas de precisión que no habrían existido con un tipo entero.
Sin embargo, con frecuencia se utilizan algoritmos de inferencia de tipos degenerados que no pueden retroceder y, en cambio, generan un mensaje de error en tal situación. Este comportamiento puede ser preferible ya que la inferencia de tipos puede no siempre ser algorítmicamente neutral, como lo ilustra el problema anterior de precisión de punto flotante.
Un algoritmo de generalidad intermedia declara implícitamente resultado2 como una variable de punto flotante, y la suma se convierte implícitamente xen una variable de punto flotante. Esto puede ser correcto si los contextos de llamada nunca proporcionan un argumento de punto flotante. Esta situación muestra la diferencia entre la inferencia de tipos , que no implica conversión de tipos , y la conversión de tipos implícita , que fuerza los datos a un tipo de datos diferente, a menudo sin restricciones.
Finalmente, una desventaja significativa del algoritmo complejo de inferencia de tipos es que la resolución de inferencia de tipos resultante no será obvia para los humanos (especialmente debido al retroceso), lo que puede ser perjudicial ya que el código está destinado principalmente a ser comprensible para los humanos.
La reciente aparición de la compilación justo a tiempo permite enfoques híbridos en los que el tipo de argumentos proporcionados por los distintos contextos de llamada se conoce en el momento de la compilación y puede generar una gran cantidad de versiones compiladas de la misma función. Luego, cada versión compilada se puede optimizar para un conjunto diferente de tipos. Por ejemplo, la compilación JIT permite que haya al menos dos versiones compiladas de add_one :
La inferencia de tipos es la capacidad de deducir automáticamente, parcial o totalmente, el tipo de una expresión en tiempo de compilación. El compilador a menudo puede inferir el tipo de una variable o la firma de tipo de una función, sin que se hayan proporcionado anotaciones de tipo explícitas. En muchos casos, es posible omitir completamente las anotaciones de tipo de un programa si el sistema de inferencia de tipos es lo suficientemente sólido o el programa o lenguaje es lo suficientemente simple.
Para obtener la información necesaria para inferir el tipo de una expresión, el compilador recopila esta información como un agregado y una reducción posterior de las anotaciones de tipo dadas para sus subexpresiones, o mediante una comprensión implícita del tipo de varios valores atómicos (por ejemplo, verdadero: Bool; 42: Entero; 3,14159: Real, etc.). Es a través del reconocimiento de la eventual reducción de expresiones a valores atómicos tipificados implícitamente que el compilador de un lenguaje de inferencia de tipos puede compilar un programa completamente sin anotaciones de tipo.
En formas complejas de polimorfismo y programación de orden superior , no siempre es posible que el compilador infiera tanto y, en ocasiones, las anotaciones de tipo son necesarias para la desambiguación. Por ejemplo, se sabe que la inferencia de tipos con recursividad polimórfica es indecidible. Además, se pueden utilizar anotaciones de tipo explícitas para optimizar el código obligando al compilador a utilizar un tipo más específico (más rápido/más pequeño) del que había inferido. [14]
Algunos métodos de inferencia de tipos se basan en la satisfacción de restricciones [15] o en teorías del módulo de satisfacibilidad . [dieciséis]
Como ejemplo, la función de Haskellmap aplica una función a cada elemento de una lista y puede definirse como:
mapa f [] = [] mapa f ( primero : resto ) = f primero : mapa f resto (Recuerde que :en Haskell denota contras , estructurar un elemento principal y una cola de lista en una lista más grande o desestructurar una lista no vacía en su elemento principal y su cola. No denota "de tipo" como en matemáticas y en otras partes de este artículo; en Haskell, en su lugar se escribe el operador "de tipo" ::.)
La inferencia de tipos en la mapfunción se realiza de la siguiente manera. mapes una función de dos argumentos, por lo que su tipo está restringido a tener la forma . En Haskell, los patrones y siempre coinciden con las listas, por lo que el segundo argumento debe ser un tipo de lista: for some type . Su primer argumento se aplica al argumento , que debe tener un tipo correspondiente al tipo en el argumento de la lista, por lo que ( significa "es de tipo") para algún tipo . El valor de retorno de , finalmente, es una lista de todo lo que produce, por lo que .a -> b -> c[](first:rest)b = [d]dffirstdf :: d -> e::emap ff[e]
Juntar las piezas conduce a . No hay nada especial en las variables de tipo, por lo que se pueden reetiquetar comomap :: (d -> e) -> [d] -> [e]
mapa :: ( a -> b ) -> [ a ] -> [ b ] Resulta que éste es también el tipo más general, ya que no se aplican más restricciones. Como el tipo inferido de mapes paramétricamente polimórfico , el tipo de argumentos y resultados de fno se infieren, sino que se dejan como variables de tipo, por lo que mapse pueden aplicar a funciones y listas de varios tipos, siempre que los tipos reales coincidan en cada invocación. .
Los algoritmos utilizados por programas como los compiladores son equivalentes al razonamiento estructurado informalmente anterior, pero un poco más detallado y metódico. Los detalles exactos dependen del algoritmo de inferencia elegido (consulte la siguiente sección para conocer el algoritmo más conocido), pero el siguiente ejemplo da una idea general. Comenzamos nuevamente con la definición de map:
mapa f [] = [] mapa f ( primero : resto ) = f primero : mapa f resto (Nuevamente, recuerde que :aquí está el constructor de listas de Haskell, no el operador "de tipo", que Haskell escribe ::).
Primero, creamos nuevas variables de tipo para cada término individual:
αdenotará el tipo de mapque queremos inferir.βdenotará el tipo de fen la primera ecuación.[γ]denotará el tipo de []en el lado izquierdo de la primera ecuación.[δ]denotará el tipo de []en el lado derecho de la primera ecuación.εdenotará el tipo de fen la segunda ecuación.ζ -> [ζ] -> [ζ]denotará el tipo de :en el lado izquierdo de la primera ecuación. (Este patrón se conoce por su definición).ηindicará el tipo de first.θindicará el tipo de rest.ι -> [ι] -> [ι]denotará el tipo de :en el lado derecho de la primera ecuación.Luego creamos nuevas variables de tipo para subexpresiones creadas a partir de estos términos, restringiendo el tipo de función que se invoca en consecuencia:
κindicará el tipo de . Concluimos que donde el símbolo "similar" significa "unifica con"; estamos diciendo que el tipo de debe ser compatible con el tipo de una función que toma a y una lista de sy devuelve a .map f []α ~ β -> [γ] -> κ~αmapβγκλindicará el tipo de . Concluimos que .(first:rest)ζ -> [ζ] -> [ζ] ~ η -> θ -> λμindicará el tipo de . Concluimos que .map f (first:rest)α ~ ε -> λ -> μνindicará el tipo de . Concluimos que .f firstε ~ η -> νξindicará el tipo de . Concluimos que .map f restα ~ ε -> θ -> ξοindicará el tipo de . Concluimos que .f first : map f restι -> [ι] -> [ι] ~ ν -> ξ -> οTambién restringimos los lados izquierdo y derecho de cada ecuación para que se unifiquen entre sí: κ ~ [δ]y μ ~ ο. En total el sistema de unificaciones a resolver es:
α ~ β -> [γ] -> κζ -> [ζ] -> [ζ] ~ η -> θ -> λα ~ ε -> λ -> µε ~ η -> να ~ ε -> θ -> ξι -> [ι] -> [ι] ~ ν -> ξ -> οκ ~ [δ]μ ~ ο
Luego sustituimos hasta que no se puedan eliminar más variables. El orden exacto es irrelevante; Si el código es correcto, cualquier pedido conducirá al mismo formulario final. Comencemos sustituyendo οpor μy [δ]por κ:
α ~ β -> [γ] -> [δ]ζ -> [ζ] -> [ζ] ~ η -> θ -> λα ~ ε -> λ -> οε ~ η -> να ~ ε -> θ -> ξι -> [ι] -> [ι] ~ ν -> ξ -> ο
Sustituyendo ζfor η, [ζ]for θand λ, ιfor ν, y [ι]for ξand ο, todo es posible porque un constructor de tipos como es invertible en sus argumentos:· -> ·
α ~ β -> [γ] -> [δ]α ~ ε -> [ζ] -> [ι]ε ~ ζ -> ι
Sustituyendo ζ -> ιfor εy β -> [γ] -> [δ]for α, manteniendo la segunda restricción para que podamos recuperarla αal final:
α ~ (ζ -> ι) -> [ζ] -> [ι]β -> [γ] -> [δ] ~ (ζ -> ι) -> [ζ] -> [ι]
Y, finalmente, sustituir (ζ -> ι)for βy ζfor porque un constructor de tipos como γes invertible ιelimina todas las variables específicas de la segunda restricción:δ[·]
α ~ (ζ -> ι) -> [ζ] -> [ι]
No son posibles más sustituciones y el reetiquetado nos da lo mismo que encontramos sin entrar en estos detalles.map :: (a -> b) -> [a] -> [b]
El algoritmo utilizado por primera vez para realizar la inferencia de tipos ahora se denomina informalmente algoritmo de Hindley-Milner, aunque el algoritmo debería atribuirse correctamente a Damas y Milner. [17] También se le llama tradicionalmente reconstrucción de tipos . [1] : 320 Si un término está bien tipificado de acuerdo con las reglas de tipificación de Hindley-Milner, entonces las reglas generan una tipificación principal para el término. El proceso de descubrimiento de esta tipificación principal es el proceso de "reconstrucción".
El origen de este algoritmo es el algoritmo de inferencia de tipos para el cálculo lambda de tipo simple que fue ideado por Haskell Curry y Robert Feys en 1958. [ cita necesaria ] En 1969, J. Roger Hindley amplió este trabajo y demostró que su algoritmo siempre infería más tipo generales. En 1978, Robin Milner , [18] independientemente del trabajo de Hindley, proporcionó un algoritmo equivalente, el Algoritmo W. En 1982 Luis Damas [17] finalmente demostró que el algoritmo de Milner es completo y lo extendió para soportar sistemas con referencias polimórficas.
Por diseño, la inferencia de tipos inferirá el tipo más general apropiado. Sin embargo, muchos lenguajes, especialmente los lenguajes de programación más antiguos, tienen sistemas de tipos ligeramente incorrectos, donde el uso de tipos más generales puede no siempre ser algorítmicamente neutral. Los casos típicos incluyen:
+operador puede sumar números enteros pero puede concatenar variantes como cadenas, incluso si esas variantes contienen números enteros.Los algoritmos de inferencia de tipos se han utilizado para analizar lenguajes naturales y lenguajes de programación. [19] [20] [21] Los algoritmos de inferencia de tipos también se utilizan en algunas inducciones gramaticales [22] [23] y sistemas gramaticales basados en restricciones para lenguajes naturales. [24]