Un sistema de tipo Hindley-Milner ( HM ) es un sistema de tipo clásico para el cálculo lambda con polimorfismo paramétrico . También se le conoce como Damas – Milner o Damas – Hindley – Milner . Fue descrito por primera vez por J. Roger Hindley [1] y luego redescubierto por Robin Milner . [2] Luis Damas aportó un análisis formal detallado y una prueba del método en su tesis doctoral. [3] [4]
Entre las propiedades más notables de HM se encuentran su integridad y su capacidad para inferir el tipo más general de un programa dado sin anotaciones de tipo u otras sugerencias proporcionadas por el programador. El algoritmo W es un método de inferencia de tipos eficaz en la práctica y se ha aplicado con éxito en grandes bases de código, aunque tiene una alta complejidad teórica . [nota 1] HM se usa preferiblemente para lenguajes funcionales . Primero se implementó como parte del sistema de tipos del lenguaje de programación ML . Desde entonces, HM se ha extendido de varias maneras, sobre todo con restricciones de clase de tipo como las de Haskell..
Introducción
Como método de inferencia de tipos, Hindley-Milner es capaz de deducir los tipos de variables, expresiones y funciones de programas escritos en un estilo completamente sin tipo. Al ser sensible al alcance , no se limita a derivar los tipos solo de una pequeña parte del código fuente, sino de programas o módulos completos. Al ser capaz de hacer frente a tipos paramétricos también, es fundamental para los sistemas de tipos de muchos lenguajes de programación funcionales . Primero se aplicó de esta manera en el lenguaje de programación ML .
El origen es el algoritmo de inferencia de tipo para el cálculo lambda simplemente tipado que fue ideado por Haskell Curry y Robert Feys en 1958. [ cita requerida ] En 1969 J. Roger Hindley extendió este trabajo y demostró que su algoritmo siempre infiere el tipo más general. En 1978 Robin Milner , [5] independientemente del trabajo de Hindley, proporcionan un algoritmo equivalente, Algoritmo W . En 1982 Luis Damas [4] finalmente demostró que el algoritmo de Milner es completo y lo extendió para soportar sistemas con referencias polimórficas.
Monomorfismo versus polimorfismo
En el cálculo lambda simplemente tipado , los tipos son constantes de tipo atómico o tipos de función de forma . Estos tipos son monomórficos . Los ejemplos típicos son los tipos utilizados en valores aritméticos:
3: Número sumar 3 4: Número agregar: Número -> Número -> Número
Contrariamente a esto, el cálculo lambda sin tipo es neutral para escribir, y muchas de sus funciones se pueden aplicar de manera significativa a todo tipo de argumentos. El ejemplo trivial es la función de identidad
- identificación X . X
que simplemente devuelve cualquier valor al que se aplica. Los ejemplos menos triviales incluyen tipos paramétricos como listas .
Si bien el polimorfismo en general significa que las operaciones aceptan valores de más de un tipo, el polimorfismo utilizado aquí es paramétrico. También se encuentra la notación de esquemas de tipos en la literatura, enfatizando la naturaleza paramétrica del polimorfismo. Además, las constantes se pueden escribir con variables de tipo (cuantificadas). P.ej:
contras: para todos a. a -> Lista a -> Lista a nil: para todos a. Enumere a. id: para todos a. a -> a
Los tipos polimórficos pueden volverse monomórficos mediante la sustitución constante de sus variables. Ejemplos de instancias monomórficas son:
id ': String -> Stringnil ': Número de lista
De manera más general, los tipos son polimórficos cuando contienen variables de tipo, mientras que los tipos sin ellas son monomórficos.
A diferencia de los sistemas de tipos utilizados, por ejemplo, en Pascal (1970) o C (1972), que solo admiten tipos monomórficos, HM está diseñado con énfasis en el polimorfismo paramétrico. Los sucesores de los lenguajes mencionados, como C ++ (1985), se centraron en diferentes tipos de polimorfismo, a saber, la subtipificación en relación con la programación orientada a objetos y la sobrecarga . Si bien el subtipo es incompatible con HM, una variante de sobrecarga sistemática está disponible en el sistema de tipos basado en HM de Haskell.
Let-polimorfismo
Al extender la inferencia de tipo para el cálculo lambda simplemente tipado hacia el polimorfismo, uno tiene que definir cuándo es admisible derivar una instancia de un valor. Idealmente, esto estaría permitido con cualquier uso de una variable vinculada, como en:
(λ id. ... (id 3) ... (id "texto") ...) (λ x. x)
Desafortunadamente, la inferencia de tipos en el cálculo lambda polimórfico no es decidible. [6] En cambio, HM proporciona un polimorfismo let de la forma
sea id = λ x. x en ... (id 3) ... (id "texto") ...
restringir el mecanismo de enlace en una extensión de la sintaxis de la expresión. Solo los valores enlazados en una construcción let están sujetos a instanciación, es decir, son polimórficos, mientras que los parámetros en las abstracciones lambda se tratan como monomórficos.
Descripción general
El resto de este artículo procede de la siguiente manera:
- Se define el sistema de tipo HM. Esto se hace describiendo un sistema de deducción que precisa qué expresiones tienen qué tipo, si es que hay alguno.
- A partir de ahí, trabaja hacia una implementación del método de inferencia de tipos. Después de introducir una variante basada en la sintaxis del sistema deductivo anterior, esboza una implementación eficiente (algoritmo J), apelando principalmente a la intuición metalógica del lector.
- Debido a que permanece abierto si el algoritmo J realmente realiza el sistema de deducción inicial, se introduce una implementación menos eficiente (algoritmo W) y se insinúa su uso en una prueba.
- Finalmente, se discuten otros temas relacionados con el algoritmo.
La misma descripción del sistema de deducción se utiliza en todas partes, incluso para los dos algoritmos, para hacer que las diversas formas en las que se presenta el método HM sean directamente comparables.
El sistema de tipos Hindley-Milner
El sistema de tipos se puede describir formalmente mediante reglas de sintaxis que fijan un lenguaje para las expresiones, tipos, etc. La presentación aquí de tal sintaxis no es demasiado formal, ya que está escrita no para estudiar la gramática superficial , sino más bien la gramática profunda , y deja algunos detalles sintácticos abiertos. Esta forma de presentación es habitual. Sobre esta base, se utilizan reglas de tipos para definir cómo se relacionan las expresiones y los tipos. Como antes, la forma utilizada es un poco liberal.
Sintaxis
Expresiones |
Tipos |
Contexto y escritura |
Variables de tipo libre |
Las expresiones a escribir son exactamente las del cálculo lambda extendido con una expresión let como se muestra en la tabla adyacente. Los paréntesis se pueden utilizar para eliminar la ambigüedad de una expresión. La aplicación se vincula a la izquierda y se vincula más fuerte que la abstracción o la construcción de entrada.
Los tipos se dividen sintácticamente en dos grupos, monotipos y politipos. [nota 2]
Monotipos
Los monotipos siempre designan un tipo particular. Monotiposse representan sintácticamente como términos .
Los ejemplos de monotipos incluyen constantes de tipo como o y tipos paramétricos como . Los últimos tipos son ejemplos de aplicaciones de funciones de tipo, por ejemplo, del conjunto, donde el superíndice indica el número de parámetros de tipo. El conjunto completo de funciones de tipoes arbitrario en HM, [nota 3] excepto que debe contener al menos, el tipo de funciones. A menudo se escribe en notación infija por conveniencia. Por ejemplo, una función que asigna enteros a cadenas tiene el tipo. Nuevamente, se pueden usar paréntesis para eliminar la ambigüedad de una expresión de tipo. La aplicación enlaza más fuerte que la flecha infija, que se enlaza a la derecha.
Las variables de tipo se admiten como monotipos. Los monotipos no deben confundirse con los tipos monomórficos, que excluyen variables y solo permiten términos básicos.
Dos monotipos son iguales si tienen términos idénticos.
Politipos
Los politipos (o esquemas de tipos) son tipos que contienen variables limitadas por cero o más cuantificadores para todos, p. Ej..
Una función con politipo puede mapear cualquier valor del mismo tipo a sí mismo, y la función de identidad es un valor para este tipo.
Como otro ejemplo, es el tipo de función que asigna todos los conjuntos finitos a enteros. Una función que devuelve la cardinalidad de un conjunto sería un valor de este tipo.
Los cuantificadores solo pueden aparecer de nivel superior. Por ejemplo, un tipoestá excluido por la sintaxis de tipos. También los monotipos se incluyen en los politipos, por lo que un tipo tiene la forma general, dónde es un monotipo.
La igualdad de politipos depende de reordenar la cuantificación y cambiar el nombre de las variables cuantificadas (-conversión). Además, se pueden descartar las variables cuantificadas que no ocurren en el monotipo.
Contexto y mecanografía
Para unir de manera significativa las partes aún disjuntas (expresiones sintácticas y tipos) se necesita una tercera parte: el contexto. Sintácticamente, un contexto es una lista de pares, denominadas asignaciones , suposiciones o vinculaciones , cada par indica esa variable de valortiene tipo . Las tres partes combinadas dan un juicio mecanografiado del formulario., indicando que bajo supuestos , la expresion tiene tipo .
Variables de tipo libre
En un tipo , el símbolo es el cuantificador que une las variables de tipo en el monotipo . Las variablesse denominan cuantificados y cualquier ocurrencia de una variable de tipo cuantificada ense llama dependiente y todas las variables de tipo no enlazado ense llaman gratis . Además de la cuantificación En politipos, las variables de tipo también se pueden vincular al ocurrir en el contexto, pero con el efecto inverso en el lado derecho de la . Estas variables se comportan como constantes de tipo allí. Finalmente, una variable de tipo puede ocurrir legalmente sin unir en una tipificación, en cuyo caso están implícitamente cuantificadas por completo.
La presencia de variables de tipo vinculadas y no vinculadas es un poco poco común en los lenguajes de programación. A menudo, todas las variables de tipo se tratan implícitamente como totalmente cuantificadas. Por ejemplo, uno no tiene cláusulas con variables libres en Prolog . Probablemente en Haskell, [nota 4] donde todas las variables de tipo ocurren implícitamente cuantificadas, es decir, un tipo de Haskell a -> a
significaaquí. Relacionado y también muy poco común es el efecto vinculante del lado derecho de las asignaciones.
Normalmente, la combinación de variables de tipo vinculadas y no vinculadas se origina a partir del uso de variables libres en una expresión. La función constante K =proporciona un ejemplo. Tiene el monotipo. Uno puede forzar el polimorfismo por. Aquí en, tiene el tipo . La variable monotipo libre se origina en el tipo de variable atado en el alcance circundante. tiene el tipo . Uno podría imaginar la variable de tipo libre en el tipo de estar obligado por el en el tipo de . Pero ese alcance no se puede expresar en HM. Más bien, la vinculación se realiza mediante el contexto.
Orden de tipo
Polimorfismo significa que una misma expresión puede tener (quizás infinitamente) muchos tipos. Pero en este sistema de tipos, estos tipos no están completamente desvinculados, sino que están orquestados por el polimorfismo paramétrico.
Como ejemplo, la identidad puede tener como su tipo así como o y muchos otros, pero no . El tipo más general de esta función es, mientras que los otros son más específicos y pueden derivarse del general reemplazando consistentemente otro tipo para el parámetro de tipo , es decir, la variable cuantificada. El contraejemplo falla porque el reemplazo no es consistente.
El reemplazo consistente se puede formalizar aplicando una sustitución al término de un tipo , escrito . Como sugiere el ejemplo, la sustitución no solo está fuertemente relacionada con un orden, que expresa que un tipo es más o menos especial, sino también con la cuantificación total que permite aplicar la sustitución.
Regla de especialización |
Formalmente, en HM, un tipo es más general que , formalmente , si alguna variable cuantificada en se sustituye consistentemente de tal manera que uno gana como se muestra en la barra lateral. Este orden es parte de la definición de tipo del sistema de tipos.
En nuestro ejemplo anterior, aplicando la sustitución resultaría en .
Si bien la sustitución de un tipo monomórfico (suelo) por una variable cuantificada es sencilla, la sustitución de un politipo tiene algunos inconvenientes causados por la presencia de variables libres. Más particularmente, las variables no consolidadas no deben reemplazarse. Aquí se tratan como constantes. Además, las cuantificaciones solo pueden ocurrir en el nivel superior. Sustituyendo un tipo paramétrico, hay que levantar sus cuantificadores. La tabla de la derecha hace que la regla sea precisa.
Alternativamente, considere una notación equivalente para los politipos sin cuantificadores en la que las variables cuantificadas están representadas por un conjunto diferente de símbolos. En tal notación, la especialización se reduce a un reemplazo simple y consistente de tales variables.
La relación es una orden parcial y es su elemento más pequeño.
Tipo principal
Si bien la especialización de un esquema de tipos es un uso del orden, juega un segundo papel crucial en el sistema de tipos. La inferencia de tipos con polimorfismo se enfrenta al desafío de resumir todos los tipos posibles que puede tener una expresión. La orden garantiza que dicho resumen existe como el tipo más general de expresión.
Sustitución en tipificaciones
El orden de tipos definido anteriormente se puede extender a las tipificaciones porque la cuantificación total implícita de las tipificaciones permite un reemplazo consistente:
Contrariamente a la regla de especialización, esto no es parte de la definición, pero como la cuantificación total implícita más bien una consecuencia de las reglas de tipo definidas a continuación. Las variables de tipo libre en una escritura sirven como marcadores de posición para un posible refinamiento. El efecto vinculante del entorno a las variables de tipo libre en el lado derecho de que prohíbe su sustitución en la regla de especialización es nuevamente que un reemplazo debe ser consistente y debería incluir todo el mecanografiado.
Este artículo discutirá cuatro conjuntos de reglas diferentes:
- sistema declarativo
- sistema sintáctico
- algoritmo J
- algoritmo W
Sistema deductivo
La sintaxis de las reglas |
La sintaxis de HM se traslada a la sintaxis de las reglas de inferencia que forman el cuerpo del sistema formal , utilizando las tipificaciones como juicios . Cada una de las reglas define qué conclusión se puede extraer de qué premisas. Además de las sentencias, algunas condiciones adicionales introducidas anteriormente también podrían usarse como premisas.
Una prueba que usa las reglas es una secuencia de juicios tal que todas las premisas se enumeran antes de una conclusión. Los ejemplos siguientes muestran un posible formato de pruebas. De izquierda a derecha, cada línea muestra la conclusión, el de la regla aplicada y las premisas, ya sea refiriéndose a una línea anterior (número) si la premisa es un juicio o haciendo explícito el predicado.
Reglas de escritura
Sistema de reglas declarativas |
El recuadro lateral muestra las reglas de deducción del sistema de tipo HM. Se pueden dividir aproximadamente las reglas en dos grupos:
Las primeras cuatro reglas (acceso variable o función), ( aplicación , es decir, llamada a función con un parámetro),( abstracción , es decir, declaración de función) y(declaración de variable) se centran en la sintaxis, presentando una regla para cada una de las formas de expresión. Su significado es obvio a primera vista, ya que descomponen cada expresión, prueban sus sub-expresiones y finalmente combinan los tipos individuales encontrados en las premisas con el tipo en la conclusión.
El segundo grupo está formado por las dos reglas restantes y . Manejan la especialización y generalización de tipos. Mientras que la regladebe quedar claro en la sección sobre especialización anterior ,complementa al primero, trabajando en sentido contrario. Permite la generalización, es decir, cuantificar variables monotípicas no limitadas en el contexto.
Los siguientes dos ejemplos ejercitan el sistema de reglas en acción. Dado que se dan tanto la expresión como el tipo, son un uso de verificación de tipos de las reglas.
Ejemplo : una prueba de dónde , podría ser escrito
Ejemplo : para demostrar la generalización, se muestra a continuación:
Let-polimorfismo
No visible de inmediato, el conjunto de reglas codifica una regulación bajo las cuales un tipo puede ser generalizado o no por un uso ligeramente variable de mono y politipos en las reglas. y . Recuérdalo y denotan poli- y monotipos respectivamente.
En regla , la variable de valor del parámetro de la función se agrega al contexto con un tipo monomórfico a través de la premisa , mientras que en la regla , la variable ingresa al medio ambiente en forma polimórfica . Aunque en ambos casos la presencia de en el contexto impide el uso de la regla de generalización para cualquier variable libre en la asignación, esta regulación fuerza el tipo de parámetro en un -expression para permanecer monomórfica, mientras que en una let-expression, la variable podría introducirse polimórfica, haciendo posibles las especializaciones.
Como consecuencia de este reglamento, no se puede escribir, ya que el parámetro está en una posición monomórfica, mientras que tiene tipo , porque se ha introducido en una expresión let y, por lo tanto, se trata como polimórfico.
Regla de generalización
La regla de generalización también merece una mirada más cercana. Aquí, la cuantificación total implícita en la premisa simplemente se mueve al lado derecho de en la conclusión. Esto es posible, ya queno ocurre gratis en el contexto. Una vez más, si bien esto hace plausible la regla de generalización, en realidad no es una consecuencia. A la inversa, la regla de generalización es parte de la definición del sistema de tipos de HM y la cuantificación total implícita es una consecuencia.
Un algoritmo de inferencia
Ahora que el sistema de deducción de HM está a la mano, se podría presentar un algoritmo y validarlo con respecto a las reglas. Alternativamente, podría ser posible derivarlo observando más de cerca cómo interactúan las reglas y cómo se forman las pruebas. Esto se hace en el resto de este artículo enfocándose en las posibles decisiones que uno puede tomar mientras prueba una mecanografía.
Grados de libertad eligiendo las reglas
Aislando los puntos en una prueba, donde no es posible ninguna decisión en absoluto, el primer grupo de reglas centradas en la sintaxis no deja elección, ya que a cada regla sintáctica le corresponde una regla de escritura única, que determina una parte de la prueba, mientras que entre la conclusión y las premisas de estas cadenas de piezas fijas de y podría ocurrir. Tal cadena también podría existir entre la conclusión de la prueba y la regla para la máxima expresión. Todas las pruebas deben tener la forma así esbozada.
Debido a que la única opción en una prueba con respecto a la selección de reglas son las y cadenas, la forma de la prueba sugiere la cuestión de si se puede hacer más precisa, donde estas cadenas podrían no ser necesarias. De hecho, esto es posible y conduce a una variante del sistema de reglas sin tales reglas.
Sistema de reglas dirigido por sintaxis
Sistema de reglas sintácticas |
Generalización |
Un tratamiento contemporáneo de HM utiliza un sistema de reglas puramente dirigido por la sintaxis debido a Clement [7] como un paso intermedio. En este sistema, la especialización se encuentra directamente después de la original. regla y se fusiona con ella, mientras que la generalizacin se convierte en parte de la regla. Allí también se determina la generalización para producir siempre el tipo más general introduciendo la función, que cuantifica todas las variables monotipo no limitadas en .
Formalmente, para validar que este nuevo sistema de reglas es equivalente al original , hay que demostrar que , que se descompone en dos subpruebas:
- ( Consistencia )
- ( Integridad )
Si bien la consistencia se puede ver descomponiendo las reglas y de en pruebas en , es probable que sea visible está incompleto, como no se puede mostrar en , por ejemplo, pero solo . Sin embargo, se puede demostrar una versión ligeramente más débil de la completitud [8] , a saber
implicando, uno puede derivar el tipo principal para una expresión en permitiéndonos generalizar la prueba al final.
Comparando y , ahora solo aparecen monotipos en los juicios de todas las reglas. Además, la forma de cualquier prueba posible con el sistema de deducción ahora es idéntica a la forma de la expresión (ambas vistas como árboles ). Por tanto, la expresión determina completamente la forma de la prueba. En la forma probablemente se determinaría con respecto a todas las reglas excepto y , que permiten construir ramas (cadenas) arbitrariamente largas entre los otros nodos.
Grados de libertad instanciando las reglas
Ahora que se conoce la forma de la prueba, uno ya está cerca de formular un algoritmo de inferencia de tipos. Debido a que cualquier prueba para una expresión dada debe tener la misma forma, uno puede asumir que los monotipos en los juicios de la prueba son indeterminados y considerar cómo determinarlos.
Aquí entra en juego el orden de sustitución (especialización). Aunque a primera vista no se pueden determinar los tipos localmente, la esperanza es que sea posible refinarlos con la ayuda del orden mientras se recorre el árbol de prueba, asumiendo además, debido a que el algoritmo resultante se convertirá en un método de inferencia, que el El tipo en cualquier premisa se determinará como el mejor posible. Y de hecho, uno puede, al mirar las reglas de sugiere:
- : La elección crítica es . En este punto, no se sabe nada sobre, por lo que solo se puede asumir el tipo más general, que es . El plan es especializar el tipo si fuera necesario. Desafortunadamente, no se permite un politipo en este lugar, por lo que algunostiene que hacer por el momento. Para evitar capturas no deseadas, una variable de tipo que aún no esté en la prueba es una opción segura. Además, hay que tener en cuenta que este monotipo aún no se ha corregido, pero podría perfeccionarse aún más.
- : La elección es cómo perfeccionar . Porque cualquier elección de un tipoaquí depende del uso de la variable, que no se conoce localmente, la apuesta más segura es la más general. Usando el mismo método que el anterior, uno puede instanciar todas las variables cuantificadas en con nuevas variables monotipo, de nuevo manteniéndolas abiertas a un mayor refinamiento.
- : La regla no deja opción. Hecho.
- : Solo la regla de la aplicación puede forzar un refinamiento de las variables "abiertas" hasta el momento.
La primera premisa obliga al resultado de la inferencia a ser de la forma .
- Si es así, entonces está bien. Más tarde se puede elegir su por el resultado.
- De lo contrario, podría ser una variable abierta. Luego, esto se puede refinar a la forma requerida con dos nuevas variables como antes.
- De lo contrario, la verificación de tipos falla porque la primera premisa infirió un tipo que no es y no puede convertirse en un tipo de función.
La segunda premisa requiere que el tipo inferido sea igual a de la primera premisa. Ahora hay dos tipos posiblemente diferentes, quizás con variables de tipo abierto, a la mano para comparar y igualar si es posible. Si es así, se encuentra un refinamiento y, en caso contrario, se detecta nuevamente un error de tipo. Se conoce un método eficaz para "igualar dos términos" por sustitución, la Unificación de Robinson en combinación con el llamado algoritmo Union-Find .
Para resumir brevemente el algoritmo de búsqueda de unión, dado el conjunto de todos los tipos en una demostración, permite agruparlos en clases de equivalencia por medio de un procedimiento y elegir un representante para cada clase utilizando un procedimiento. Al enfatizar la palabra procedimiento en el sentido de efecto secundario , claramente estamos dejando el reino de la lógica para preparar un algoritmo efectivo. El representante de un se determina de tal manera que, si ambos y son variables de tipo, entonces el representante es arbitrariamente una de ellas, pero al unir una variable y un término, el término se convierte en el representante. Suponiendo una implementación de union-find a mano, se puede formular la unificación de dos monotipos de la siguiente manera:
unificar (ta, tb): ta = encontrar (ta) tb = buscar (tb) si ambos ta, tb son términos de la forma D p1..pn con D idéntico, n entonces unifique (ta [i], tb [i]) para cada parámetro i- ésimo correspondiente, de lo contrario si al menos uno de ta, tb es un escriba la variable entonces unión (ta, tb) demás error 'los tipos no coinciden'
Ahora, teniendo a mano un bosquejo de un algoritmo de inferencia, en la siguiente sección se ofrece una presentación más formal. Se describe en Milner [2] p. 370 y sigs. como algoritmo J.
Algoritmo J
Algoritmo J |
La presentación del algoritmo J es un mal uso de la notación de reglas lógicas, ya que incluye efectos secundarios pero permite una comparación directa con expresando al mismo tiempo una implementación eficiente. Las reglas ahora especifican un procedimiento con parámetros. flexible en la conclusión donde la ejecución del local procede de izquierda a derecha.
El procedimiento se especializa en el politipo copiando el término y reemplazando las variables de tipo enlazado consistentemente por nuevas variables monotipo. ''produce una nueva variable monotipo. Probable,Tiene que copiar el tipo introduciendo nuevas variables para la cuantificación para evitar capturas no deseadas. En general, el algoritmo procede ahora haciendo siempre la elección más general dejando la especialización a la unificación, que por sí misma produce el resultado más general. Como se señaló anteriormente , el resultado final tiene que generalizarse a al final, para obtener el tipo más general para una expresión determinada.
Debido a que los procedimientos usados en el algoritmo tienen un costo cercano a O (1), el costo total del algoritmo es casi lineal en el tamaño de la expresión para la cual se infiere un tipo. Esto contrasta fuertemente con muchos otros intentos de derivar algoritmos de inferencia de tipo, que a menudo resultaron ser NP-hard , si no indecidibles con respecto a la terminación. Por lo tanto, el HM funciona tan bien como los algoritmos de verificación de tipo mejor informados. La verificación de tipo aquí significa que un algoritmo no tiene que encontrar una prueba, sino solo para validar una determinada.
La eficiencia se reduce ligeramente porque la vinculación de las variables de tipo en el contexto debe mantenerse para permitir el cálculo de y habilitar una comprobación de ocurre para evitar la construcción de tipos recursivos durante. Un ejemplo de tal caso es, para el cual no se puede derivar ningún tipo usando HM. Prácticamente, los tipos son solo términos pequeños y no construyen estructuras en expansión. Por lo tanto, en el análisis de complejidad, se puede tratar compararlos como una constante, reteniendo los costos O (1).
Demostrando el algoritmo
En la sección anterior, mientras se esbozaba el algoritmo, se insinuaba su demostración con argumentación metalógica. Si bien esto conduce a un algoritmo J eficiente, no está claro si el algoritmo refleja adecuadamente los sistemas de deducción D o S que sirven como línea de base semántica.
El punto más crítico de la argumentación anterior es el refinamiento de las variables monotípicas ligadas al contexto. Por ejemplo, el algoritmo cambia audazmente el contexto mientras infiere, por ejemplo,, porque la variable monotype agregada al contexto del parámetro luego necesita ser refinado para al manipular la aplicación. El problema es que las reglas de deducción no permiten tal refinamiento. Argumentar que el tipo refinado podría haberse agregado antes en lugar de la variable monotipo es, en el mejor de los casos, un recurso.
La clave para llegar a un argumento formalmente satisfactorio es incluir adecuadamente el contexto dentro del refinamiento. Formalmente, la mecanografía es compatible con la sustitución de variables de tipo libre.
Por lo tanto, refinar las variables libres significa refinar todo el tipo.
Algoritmo W
Algoritmo W |
A partir de ahí, una prueba del algoritmo J conduce al algoritmo W, que solo hace que los efectos secundarios impuestos por el procedimiento explícito al expresar su composición serial mediante las sustituciones . La presentación del algoritmo W en la barra lateral todavía hace uso de efectos secundarios en las operaciones en cursiva, pero ahora se limitan a generar nuevos símbolos. La forma de juicio es, que denota una función con un contexto y una expresión como parámetro que produce un monotipo junto con una sustitución. es una versión sin efectos secundarios de produciendo una sustitución que es el unificador más general .
Si bien el algoritmo W normalmente se considera el algoritmo HM y a menudo se presenta directamente después del sistema de reglas en la literatura, Milner [2] describe su propósito en la página 369 de la siguiente manera:
- En su forma actual, W no es un algoritmo eficiente; las sustituciones se aplican con demasiada frecuencia. Fue formulado para ayudar a la prueba de solidez. Ahora presentamos un algoritmo J más simple que simula W en un sentido preciso.
Si bien consideraba que W era más complicado y menos eficiente, lo presentó en su publicación antes de J. Tiene sus méritos cuando los efectos secundarios no están disponibles o no son deseados. Por cierto, W también es necesario para demostrar que está completo, lo que él incluye en la prueba de solidez.
Obligaciones de prueba
Antes de formular las obligaciones de prueba, es necesario enfatizar una desviación entre los sistemas de reglas D y S y los algoritmos presentados.
Si bien el desarrollo anterior hizo un uso indebido de los monotipos como variables de prueba "abiertas", la posibilidad de que las variables de monotipo adecuadas se dañen se evitó al introducir nuevas variables y esperar lo mejor. Pero hay un problema: una de las promesas que se hicieron fue que estas nuevas variables se "tendrían en cuenta" como tales. El algoritmo no cumple esta promesa.
Tener un contexto , la expresion no se puede escribir tampoco o , pero los algoritmos dan con el tipo , donde W además ofrece la sustitución , lo que significa que el algoritmo no detecta todos los errores de tipo. Esta omisión se puede solucionar fácilmente distinguiendo con más cuidado las variables de prueba y las variables de monotipo.
Los autores conocían bien el problema, pero decidieron no solucionarlo. Se podría suponer una razón pragmática detrás de esto. Si bien una implementación más adecuada de la inferencia de tipos habría permitido que el algoritmo manejara monotipos abstractos, no eran necesarios para la aplicación prevista donde ninguno de los elementos en un contexto preexistente tiene variables libres. En este sentido, la complicación innecesaria se abandonó en favor de un algoritmo más simple. La desventaja restante es que la prueba del algoritmo con respecto al sistema de reglas es menos general y solo se puede hacer para contextos con como condición secundaria.
La condición secundaria en la obligación de integridad aborda cómo la deducción puede dar muchos tipos, mientras que el algoritmo siempre produce uno. Al mismo tiempo, la condición secundaria exige que el tipo inferido sea en realidad el más general.
Para probar adecuadamente las obligaciones, es necesario fortalecerlas primero para permitir la activación del lema de sustitución enhebrando la sustitución. mediante y . A partir de ahí, las demostraciones son por inducción sobre la expresión.
Otra obligación de prueba es el lema de sustitución en sí, es decir, la sustitución de la tipificación, que finalmente establece la cuantificación total. Lo último no puede probarse formalmente, ya que no se dispone de tal sintaxis.
Extensiones
Definiciones recursivas
Para que la programación sea práctica , se necesitan funciones recursivas. Una propiedad central del cálculo lambda es que las definiciones recursivas no están disponibles directamente, sino que pueden expresarse con un combinador de punto fijo . Pero desafortunadamente, el combinador de punto fijo no se puede formular en una versión escrita del cálculo lambda sin tener un efecto desastroso en el sistema como se describe a continuación.
Regla de escritura
El artículo original [4] muestra que la recursividad se puede realizar mediante un combinador.. Por tanto, una posible definición recursiva podría formularse como.
Alternativamente, es posible una extensión de la sintaxis de la expresión y una regla de escritura adicional:
dónde
básicamente fusionando y mientras se incluyen las variables definidas de forma recursiva en posiciones de monotipo donde ocurren a la izquierda de la pero como politipos a su derecha.
Consecuencias
Si bien lo anterior es sencillo, tiene un precio.
La teoría de tipos conecta el cálculo lambda con la computación y la lógica. La fácil modificación anterior tiene efectos en ambos:
- La propiedad de normalización fuerte se invalida, porque se pueden formular términos no terminantes.
- La lógica colapsa porque el tipose vuelve habitado .
Sobrecarga
Sobrecarga significa que aún se pueden definir y utilizar diferentes funciones con el mismo nombre. La mayoría de los lenguajes de programación al menos proporcionan una sobrecarga con las operaciones aritméticas integradas (+, <, etc.), para permitir al programador escribir expresiones aritméticas en la misma forma, incluso para diferentes tipos numéricos como int
o real
. Debido a que una mezcla de estos tipos diferentes dentro de la misma expresión también exige una conversión implícita, la sobrecarga, especialmente para estas operaciones, a menudo se integra en el lenguaje de programación mismo. En algunos lenguajes, esta característica se generaliza y se pone a disposición del usuario, por ejemplo, en C ++.
Si bien se ha evitado la sobrecarga ad hoc en la programación funcional para los costos de cálculo tanto en la verificación de tipos como en la inferencia [ cita requerida ] , se ha introducido un medio para sistematizar la sobrecarga que se asemeja tanto en la forma como en el nombre a la programación orientada a objetos, pero funciona un nivel hacia arriba . Las "instancias" en esta sistemática no son objetos (es decir, a nivel de valor), sino tipos. El ejemplo de ordenación rápida mencionado en la introducción utiliza la sobrecarga en los pedidos, con el siguiente tipo de anotación en Haskell:
quickSort :: Ord a => [ a ] -> [ a ]
Aquí, el tipo a
no solo es polimórfico, sino que también está restringido a ser una instancia de alguna clase de tipo Ord
, que proporciona los predicados de orden <
y se >=
usa en el cuerpo de funciones. Las implementaciones adecuadas de estos predicados se pasan a quicksorts como parámetros adicionales, tan pronto como se utiliza quicksort en tipos más concretos, se proporciona una implementación única de la función sobrecargada quickSort.
Debido a que las "clases" solo permiten un tipo único como argumento, el sistema de tipos resultante aún puede proporcionar inferencias. Además, las clases de tipos se pueden equipar con algún tipo de orden de sobrecarga que permite organizar las clases como una celosía .
Tipos de orden superior
El polimorfismo paramétrico implica que los propios tipos se pasan como parámetros como si fueran valores propios. Pasados como argumentos a funciones adecuadas, pero también a "funciones de tipo" como en las constantes de tipo "paramétricas", lleva a la pregunta de cómo escribir los tipos de manera más adecuada. Se utilizan tipos de orden superior para crear un sistema de tipos aún más expresivo.
Desafortunadamente, solo la unificación ya no es decidible en presencia de metatipos, lo que hace imposible la inferencia de tipos en esta extensión de generalidad. Además, asumir un tipo de todos los tipos que se incluye a sí mismo como tipo conduce a una paradoja, como en el conjunto de todos los conjuntos, por lo que uno debe proceder en pasos de niveles de abstracción. La investigación en el cálculo lambda de segundo orden , un paso hacia arriba, mostró que la inferencia de tipos es indecidible en esta generalidad.
Se han introducido partes de un nivel adicional en Haskell named kind , donde se usa para ayudar a escribir mónadas . Los tipos quedan implícitos, trabajando detrás de escena en la mecánica interna del sistema de tipos extendido.
Subtipado
Los intentos de combinar subtipos e inferencia de tipos han causado bastante frustración. Sistemas de tipos con subtipos que permiten un estilo orientado a objetos, como por ejemplo, Cardelli [9] es system , falta inferencia de tipo. Hasta cierto punto, el HM se puede modificar para hacer frente a los registros. [10] La idea es extender un registro dado por una etiqueta de campo y un valor a un nuevo registro usando la sintaxis . El orden de tipo HM se puede aplicar a dichas extensiones como si fueran pares., si el sistema de tipos restringe adicionalmente en esta sintaxis para ser un registro.
Notas
- ^ La inferencia de tipo Hindley-Milner es DEXPTIME -completa. De hecho, simplemente decidir si un programa de AA se puede escribir (sin tener que inferir un tipo) es en sí mismo DEXPTIME -completo. El comportamiento no lineal se manifiesta por sí mismo, pero sobre todo enentradas patológicas . Así, las pruebas teóricas de la complejidad de Mairson (1990) y Kfoury, Tiuryn y Urzyczyn (1990) fueron una sorpresa para la comunidad investigadora.
- ^ Los politipos se denominan "esquemas de tipos" en el artículo original.
- ^ Los tipos paramétricosno estaban presentes en el artículo original sobre HM y no son necesarios para presentar el método. Ninguna de las siguientes reglas de inferencia se ocupará de ellas ni las tendrá en cuenta. Lo mismo vale para los "tipos primitivos" no paramétricos en dicho documento. Toda la maquinaria para la inferencia de tipos polimórficos se puede definir sin ellos. Se han incluido aquí por ejemplo, pero también porque la naturaleza de HM tiene que ver con los tipos paramétricos. Esto proviene del tipo de función, cableado en las reglas de inferencia, a continuación, que ya tiene dos parámetros y se ha presentado aquí solo como un caso especial.
- ^ Haskell proporciona la extensión de lenguaje ScopedTypeVariables que permite incorporar todas las variables de tipo cuantificadas al alcance.
Referencias
- ^ Hindley, J. Roger (1969). "El esquema de tipos principal de un objeto en lógica combinatoria". Transacciones de la American Mathematical Society . 146 : 29–60. doi : 10.2307 / 1995158 . JSTOR 1995158 .
- ^ a b c Milner, Robin (1978). "Una teoría del polimorfismo de tipos en la programación". Revista de Ciencias de la Computación y Sistemas . 17 (3): 348–374. CiteSeerX 10.1.1.67.5276 . doi : 10.1016 / 0022-0000 (78) 90014-4 .
- ^ Damas, Luis (1985). Asignación de tipo en lenguajes de programación (tesis doctoral). Universidad de Edimburgo. hdl : 1842/13555 . CST-33-85.
- ^ a b c Damas, Luis; Milner, Robin (1982). Esquemas de tipos principales para programas funcionales (PDF) . IX Simposio sobre Principios de los lenguajes de programación (POPL'82). ACM. págs. 207–212. doi : 10.1145 / 582153.582176 . ISBN 978-0-89791-065-1.
- ^ Milner, Robin (1978), "A Theory of Type Polymorphism in Programming", Journal of Computer and System Sciences , 17 (3): 348–375, doi : 10.1016 / 0022-0000 (78) 90014-4
- ^ Wells, JB (1994). "La tipificación y la verificación de tipos en el cálculo lambda de segundo orden son equivalentes e indecidibles" . Actas del 9º Simposio Anual de IEEE sobre Lógica en Ciencias de la Computación (LICS) . págs. 176-185. doi : 10.1109 / LICS.1994.316068 . ISBN 0-8186-6310-3. S2CID 15078292 .
- ^ Clemente (1986). Un lenguaje aplicativo simple: Mini-ML . LFP'86. ACM. doi : 10.1145 / 319838.319847 . ISBN 978-0-89791-200-6.
- ^ Vaughan, Jeff (23 de julio de 2008) [5 de mayo de 2005]. "Una prueba de corrección para el algoritmo de inferencia de tipo Hindley-Milner" (PDF) . Archivado desde el original (PDF) el 24 de marzo de 2012. Cite journal requiere
|journal=
( ayuda ) - ^ Cardelli, Luca; Martini, Simone; Mitchell, John C .; Scedrov, Andre (1994). "Una extensión del sistema F con subtipificación". Información y Computación, vol. 9 . Holanda Septentrional, Amsterdam. págs. 4-56. doi : 10.1006 / inco.1994.1013 .
- ^ Daan Leijen, Registros extensibles con etiquetas de alcance , Instituto de Ciencias de la Información y la Computación, Universidad de Utrecht, Borrador, Revisión: 76, 23 de julio de 2005
- Mairson, Harry G. (1990). "Decidir la tipificación de ML está completo para un tiempo exponencial determinista". Actas del 17º simposio ACM SIGPLAN-SIGACT sobre Principios de lenguajes de programación - POPL '90 . Actas del 17º Simposio ACM SIGPLAN-SIGACT sobre principios de lenguajes de programación . POPL '90. ACM. págs. 382–401. doi : 10.1145 / 96709.96748 . ISBN 978-0-89791-343-0. S2CID 75336 .
- Kfoury, AJ; Tiuryn, J .; Urzyczyn, P. (1990). La tipificación de ML es dexptime-complete . Apuntes de conferencias en Ciencias de la Computación . CAAP '90. 431 . págs. 206–220. doi : 10.1007 / 3-540-52590-4_50 . ISBN 978-3-540-52590-5.
enlaces externos
- Una implementación alfabetizada de Haskell del algoritmo W junto con su código fuente en GitHub .
- Una implementación simple del algoritmo Hindley-Milner en Python .