Sistema tipo Hindley-Milner

Sistema de tipos utilizado en programación informática y matemáticas.

Un sistema de tipos Hindley-Milner ( HM ) es un sistema de tipos 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 posteriormente redescubierto por Robin Milner . ^[2] Luis Damas contribuyó con 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 determinado sin anotaciones de tipo proporcionadas por el programador ni otras sugerencias. El algoritmo W es un método de inferencia de tipos eficiente 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 utiliza preferentemente para lenguajes funcionales . Se implementó por primera vez como parte del sistema de tipos del lenguaje de programación ML . Desde entonces, HM se ha ampliado 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 puede deducir los tipos de variables, expresiones y funciones a partir 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 porción del código fuente, sino de programas o módulos completos. 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 . Se aplicó por primera vez de esta manera en el lenguaje de programación ML .

El origen 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 el tipo más general. . En 1978, Robin Milner , ^[5] independientemente del trabajo de Hindley, proporcionó un algoritmo equivalente, el Algoritmo W. En 1982, Luis Damas ^[4] finalmente demostró que el algoritmo de Milner está completo y lo extendió para soportar sistemas con referencias polimórficas.

Monomorfismo versus polimorfismo

En el cálculo lambda de tipo simple , los tipos T son constantes de tipo atómico o tipos de función de forma . Estos tipos son monomórficos . Ejemplos típicos son los tipos utilizados en valores aritméticos: ${\displaystyle T\rightarrow T}$

3 : Número sumar 3 4 : Número agregar: Número -> Número -> Número

Por el contrario, el cálculo lambda sin tipo es neutral a la escritura y muchas de sus funciones se pueden aplicar de manera significativa a todo tipo de argumentos. El ejemplo trivial es la función identidad.

identificación ≡ λ x . X

que simplemente devuelve cualquier valor al que se aplica. 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 tipográficos 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 -> Listar a -> Listar a nil: para todos a. Listar un id: para todos a. un -> un

Los tipos polimórficos pueden volverse monomórficos mediante la sustitución constante de sus variables. Ejemplos de instancias monomórficas son:

id': Cadena -> Cadenanil': 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.

Al contrario de los sistemas de tipos utilizados, por ejemplo, en Pascal (1970) o C (1972), que sólo 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, concretamente en el caso de la programación orientada a objetos, la subtipificación y la sobrecarga . Si bien la subtipificación es incompatible con HM, hay disponible una variante de sobrecarga sistemática en el sistema de tipos basado en HM de Haskell.

polimorfismo let

Al extender la inferencia de tipos para el cálculo lambda de tipo simple hacia el polimorfismo, se debe definir cuándo es admisible derivar una instancia de un valor. Idealmente, esto se permitiría 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")...

restringiendo el mecanismo de vinculación en una extensión de la sintaxis de expresión. Sólo los valores vinculados en una construcción let están sujetos a instanciación, es decir, son polimórficos, mientras que los parámetros en abstracciones lambda se tratan como monomórficos.

Descripción general

El resto de este artículo procede de la siguiente manera:

• El sistema de tipos HM está definido. Esto se hace describiendo un sistema de deducción que precisa qué expresiones tienen qué tipo, si corresponde.
• A partir de ahí, se trabaja hacia la 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 más temas relacionados con el algoritmo.

Se utiliza en todo momento la misma descripción del sistema de deducción, incluso para los dos algoritmos, para hacer directamente comparables las diversas formas en que se presenta el método HM.

El sistema de tipos Hindley-Milner

El sistema de tipos puede describirse formalmente mediante reglas de sintaxis que fijan un lenguaje para las expresiones, tipos, etc. La presentación aquí de dicha sintaxis no es demasiado formal, en el sentido de que no está escrita para estudiar la gramática superficial , sino más bien la gramática profunda y deja abiertos algunos detalles sintácticos. Esta forma de presentación es habitual. A partir de esto, se utilizan reglas de escritura para definir cómo se relacionan las expresiones y los tipos. Como antes, la forma utilizada es un poco liberal.

Sintaxis

Las expresiones que se escribirán 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 let-in.

Los tipos se dividen sintácticamente en dos grupos, monotipos y politipos. ^{[nota 2]}

Monotipos

Los monotipos siempre designan un tipo particular. Los monotipos se representan sintácticamente como términos . ${\displaystyle \tau }$

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 tipo es 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 números 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 se vincula más fuerte que la flecha infija, que se vincula hacia la derecha. ${\displaystyle {\mathtt {int}}}$ ${\displaystyle {\mathtt {string}}}$ ${\displaystyle {\mathtt {Map\ (Set\ string)\ int}}}$ ${\displaystyle \{{\mathtt {Map^{2},\ Set^{1},\ string^{0},\ int^{0}}},\ \rightarrow ^{2}\}}$ ${\displaystyle C}$ ${\displaystyle \rightarrow ^{2}}$ ${\displaystyle {\mathtt {int}}\rightarrow {\mathtt {string}}}$

Las variables tipo se admiten como monotipos. Los monotipos no deben confundirse con los tipos monomórficos, que excluyen variables y sólo 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 vinculadas por cero o más cuantificadores para todos, por ejemplo . ${\displaystyle \forall \alpha .\alpha \rightarrow \alpha }$

Una función con politipo puede asignar cualquier valor del mismo tipo a sí misma, y ​​la función de identidad es un valor para este tipo. ${\displaystyle \forall \alpha .\alpha \rightarrow \alpha }$

Como otro ejemplo, es el tipo de función que asigna todos los conjuntos finitos a números enteros. Una función que devuelva la cardinalidad de un conjunto sería un valor de este tipo. ${\displaystyle \forall \alpha .({\mathtt {Set}}\ \alpha )\rightarrow {\mathtt {int}}}$

Los cuantificadores sólo pueden aparecer en el nivel superior. Por ejemplo, un tipo queda excluido por la sintaxis de tipos. También los monotipos se incluyen en los politipos, por lo que un tipo tiene la forma general , donde es un monotipo. ${\displaystyle \forall \alpha .\alpha \rightarrow \forall \alpha .\alpha }$ ${\displaystyle \forall \alpha _{1}\dots \forall \alpha _{n}.\tau ,n\geq 0}$ ${\displaystyle \tau }$

La igualdad de politipos depende de reordenar la cuantificación y renombrar las variables cuantificadas ( -conversión). Además, se pueden eliminar las variables cuantificadas que no aparecen en el monotipo. ${\displaystyle \alpha }$

Contexto y escritura

Para reunir de manera significativa las partes aún separadas (tipos y expresiones de sintaxis) se necesita una tercera parte: el contexto. Sintácticamente, un contexto es una lista de pares , llamados asignaciones , suposiciones o vinculaciones , cada par indica que la variable valor tiene tipo. Las tres partes combinadas dan un juicio de tipificación de la forma , indicando que bajo suposiciones , la expresión tiene tipo . ${\displaystyle x:\sigma }$ ${\displaystyle x_{i}}$ ${\displaystyle \sigma _{i}.}$ ${\displaystyle \Gamma \ \vdash \ e:\sigma }$ ${\displaystyle \Gamma }$ ${\displaystyle e}$ ${\displaystyle \sigma }$

variables de tipo libre

En un tipo , el símbolo es el cuantificador que vincula las variables de tipo en el monotipo . Las variables se denominan cuantificadas y cualquier aparición de una variable de tipo cuantificada se denomina vinculada y todas las variables de tipo no vinculada se denominan libres . Además de la cuantificación en politipos, las variables de tipo también se pueden vincular al aparecer en el contexto, pero con el efecto inverso en el lado derecho del . Estas variables se comportan allí como constantes de tipo. Finalmente, una variable de tipo puede aparecer legalmente sin consolidar en un tipado, en cuyo caso están implícitamente cuantificadas en su totalidad. ${\displaystyle \forall \alpha _{1}\dots \forall \alpha _{n}.\tau }$ ${\displaystyle \forall }$ ${\displaystyle \alpha _{i}}$ ${\displaystyle \tau }$ ${\displaystyle \alpha _{i}}$ ${\displaystyle \tau }$ ${\displaystyle \tau }$ ${\displaystyle \forall }$ ${\displaystyle \vdash }$

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 y están totalmente cuantificadas. Por ejemplo, no hay cláusulas con variables libres en Prolog . Del mismo modo, en Haskell, ^{[nota 4]} donde todas las variables de tipo aparecen implícitamente cuantificadas, es decir, un tipo de Haskell a -> asignifica aquí. Relacionado y también muy poco común es el efecto vinculante del lado derecho de las asignaciones. ${\displaystyle \forall \alpha .\alpha \rightarrow \alpha }$ ${\displaystyle \sigma }$

Normalmente, la combinación de variables de tipo enlazadas y no enlazadas se origina a partir del uso de variables libres en una expresión. La función constante K = proporciona un ejemplo. Tiene el monotipo . Se puede forzar el polimorfismo mediante . Aquí, tiene el tipo . La variable monotipo libre se origina a partir del tipo de variable vinculada en el ámbito circundante. tiene el tipo . Uno podría imaginar que la variable de tipo libre en el tipo de esté vinculada por la en el tipo de . Pero tal alcance no puede expresarse en HM. Más bien, la vinculación se realiza por el contexto. ${\displaystyle \lambda x.\lambda y.x}$ ${\displaystyle \alpha \rightarrow \beta \rightarrow \alpha }$ ${\displaystyle \mathbf {let} \ k=\lambda x.(\mathbf {let} \ f=\lambda y.x\ \mathbf {in} \ f)\ \mathbf {in} \ k}$ ${\displaystyle f}$ ${\displaystyle \forall \gamma .\gamma \rightarrow \alpha }$ ${\displaystyle \alpha }$ ${\displaystyle x}$ ${\displaystyle k}$ ${\displaystyle \forall \alpha \forall \beta .\alpha \rightarrow \beta \rightarrow \alpha }$ ${\displaystyle \alpha }$ ${\displaystyle f}$ ${\displaystyle \forall \alpha }$ ${\displaystyle k}$

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 más bien están orquestados por el polimorfismo paramétrico.

Por ejemplo, la identidad puede tener como tipo así como o y muchos otros, pero no . El tipo más general de esta función es , mientras que los demás 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. ${\displaystyle \lambda x.x}$ ${\displaystyle \forall \alpha .\alpha \rightarrow \alpha }$ ${\displaystyle {\texttt {string}}\rightarrow {\texttt {string}}}$ ${\displaystyle {\texttt {int}}\rightarrow {\texttt {int}}}$ ${\displaystyle {\texttt {int}}\rightarrow {\texttt {string}}}$ ${\displaystyle \forall \alpha .\alpha \rightarrow \alpha }$ ${\displaystyle \alpha }$

La sustitución consistente puede formalizarse aplicando una sustitución al término de un tipo , escrito . Como sugiere el ejemplo, la sustitución no sólo 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. ${\displaystyle S=\left\{\ a_{i}\mapsto \tau _{i},\ \dots \ \right\}}$ ${\displaystyle \tau }$ ${\displaystyle S\tau }$

Formalmente, en HM, un tipo es más general que , formalmente , si alguna variable cuantificada se sustituye consistentemente de manera que se gane como se muestra en la barra lateral. Este orden es parte de la definición de tipo del sistema de tipos. ${\displaystyle \sigma '}$ ${\displaystyle \sigma }$ ${\displaystyle \sigma '\sqsubseteq \sigma }$ ${\displaystyle \sigma '}$ ${\displaystyle \sigma }$

En nuestro ejemplo anterior, aplicar la sustitución daría como resultado . ${\displaystyle S=\left\{\alpha \mapsto {\texttt {string}}\right\}}$ ${\displaystyle \forall \alpha .\alpha \rightarrow \alpha \sqsubseteq {\texttt {string}}\rightarrow {\texttt {string}}}$

Si bien sustituir una variable cuantificada por un tipo monomórfico (básico) es sencillo, sustituir un politipo tiene algunos inconvenientes causados ​​por la presencia de variables libres. En particular, las variables no consolidadas no deben reemplazarse. Aquí se los trata como constantes. Además, las cuantificaciones sólo pueden realizarse en el nivel superior. Al sustituir un tipo paramétrico, hay que eliminar sus cuantificadores. La tabla de la derecha aclara la regla.

Alternativamente, considere una notación equivalente para los politipos sin cuantificadores en la que las variables cuantificadas se representan mediante un conjunto diferente de símbolos. En tal notación, la especialización se reduce a un simple reemplazo consistente de tales variables.

La relación es un orden parcial y es su elemento más pequeño. ${\displaystyle \sqsubseteq }$ ${\displaystyle \forall \alpha .\alpha }$

tipo principal

Si bien la especialización de un esquema tipográfico es un uso del orden, desempeña un segundo papel crucial en el sistema tipográfico. La inferencia de tipos con polimorfismo enfrenta el desafío de resumir todos los tipos posibles que puede tener una expresión. El orden garantiza que dicho resumen exista como el tipo más general de expresión.

Sustitución en mecanografías

El orden de tipos definido anteriormente se puede extender a los tipos porque la cuantificación implícita de todos los tipos permite un reemplazo consistente:

${\displaystyle \Gamma \vdash e:\sigma \quad \Longrightarrow \quad S\Gamma \vdash e:S\sigma }$

Al contrario de la regla de especialización, esto no es parte de la definición, sino que, al igual que la cuantificación total implícita, es más bien una consecuencia de las reglas de tipo que se definen 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 para las variables de tipo libre en el lado derecho 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 tipo. ${\displaystyle \vdash }$

Este artículo analizará cuatro conjuntos de reglas diferentes:

1. ${\displaystyle \vdash _{D}}$sistema declarativo
2. ${\displaystyle \vdash _{S}}$sistema sintáctico
3. ${\displaystyle \vdash _{J}}$algoritmo J
4. ${\displaystyle \vdash _{W}}$algoritmo W

sistema deductivo

La sintaxis de HM se traslada a la sintaxis de las reglas de inferencia que forman el cuerpo del sistema formal , mediante el uso de tipificaciones como juicios . Cada una de las reglas define qué conclusión se puede sacar de qué premisas. Además de las sentencias, algunas condiciones adicionales presentadas anteriormente también podrían usarse como premisas.

Una prueba que utiliza las reglas es una secuencia de juicios tales 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 significado de la regla aplicada y las premisas, ya sea haciendo referencia a una línea anterior (número) si la premisa es un juicio o haciendo explícito el predicado. ${\displaystyle [{\mathtt {Name}}]}$

Reglas de mecanografía

Ver también Reglas de escritura

El cuadro lateral muestra las reglas de deducción del sistema tipo HM. Se pueden dividir aproximadamente las reglas en dos grupos:

Las primeras cuatro reglas (acceso a variables o funciones), ( 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 y presentan 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 subexpresiones y finalmente combinan los tipos individuales encontrados en las premisas con el tipo de la conclusión. ${\displaystyle [{\mathtt {Var}}]}$ ${\displaystyle [{\mathtt {App}}]}$ ${\displaystyle [{\mathtt {Abs}}]}$ ${\displaystyle [{\mathtt {Let}}]}$

El segundo grupo está formado por las dos reglas restantes y . Manejan la especialización y generalización de tipos. Si bien la norma debería quedar clara en el apartado sobre especialización anterior, complementa la anterior, trabajando en sentido contrario. Permite la generalización, es decir, cuantificar variables monotipo no ligadas al contexto. ${\displaystyle [{\mathtt {Inst}}]}$ ${\displaystyle [{\mathtt {Gen}}]}$ ${\displaystyle [{\mathtt {Inst}}]}$ ${\displaystyle [{\mathtt {Gen}}]}$

Los dos ejemplos siguientes ponen en práctica el sistema de reglas. Dado que se dan tanto la expresión como el tipo, son un uso de las reglas para verificar el tipo.

Ejemplo : se podría escribir una prueba de dónde ${\displaystyle \Gamma \vdash _{D}id(n):int}$ ${\displaystyle \Gamma =id:\forall \alpha .\alpha \rightarrow \alpha ,\ n:int}$

${\displaystyle {\begin{array}{llll}1:&\Gamma \vdash _{D}id:\forall \alpha .\alpha \rightarrow \alpha &[{\mathtt {Var}}]&(id:\forall \alpha .\alpha \rightarrow \alpha \in \Gamma )\\2:&\Gamma \vdash _{D}id:int\rightarrow int&[{\mathtt {Inst}}]&(1),\ (\forall \alpha .\alpha \rightarrow \alpha \sqsubseteq int\rightarrow int)\\3:&\Gamma \vdash _{D}n:int&[{\mathtt {Var}}]&(n:int\in \Gamma )\\4:&\Gamma \vdash _{D}id(n):int&[{\mathtt {App}}]&(2),\ (3)\\\end{array}}}$

Ejemplo : para demostrar la generalización, se muestra a continuación: ${\displaystyle \vdash _{D}\ {\textbf {let}}\,id=\lambda x.x\ {\textbf {in}}\ id\,:\,\forall \alpha .\alpha \rightarrow \alpha }$

${\displaystyle {\begin{array}{llll}1:&x:\alpha \vdash _{D}x:\alpha &[{\mathtt {Var}}]&(x:\alpha \in \left\{x:\alpha \right\})\\2:&\vdash _{D}\lambda x.x:\alpha \rightarrow \alpha &[{\mathtt {Abs}}]&(1)\\3:&id:\alpha \rightarrow \alpha \vdash _{D}id:\alpha \rightarrow \alpha &[{\mathtt {Var}}]&(id:\alpha \rightarrow \alpha \in \left\{id:\alpha \rightarrow \alpha \right\})\\4:&\vdash _{D}{\textbf {let}}\,id=\lambda x.x\ {\textbf {in}}\ id\,:\,\alpha \rightarrow \alpha &[{\mathtt {Let}}]&(2),\ (3)\\5:&\vdash _{D}{\textbf {let}}\,id=\lambda x.x\ {\textbf {in}}\ id\,:\,\forall \alpha .\alpha \rightarrow \alpha &[{\mathtt {Gen}}]&(4),\ (\alpha \not \in free(\epsilon ))\\\end{array}}}$

polimorfismo let

No visible de inmediato, el conjunto de reglas codifica una regulación bajo las cuales circunstancias un tipo podría generalizarse o no mediante un uso ligeramente variable de monotipos y politipos en las reglas y . Recuerde eso y denote politipos y monotipos respectivamente. ${\displaystyle [{\mathtt {Abs}}]}$ ${\displaystyle [{\mathtt {Let}}]}$ ${\displaystyle \sigma }$ ${\displaystyle \tau }$

En regla , la variable 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 regla , la variable ingresa al entorno 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 obliga al tipo de parámetro en una expresión a permanecer monomórfico, mientras que en una expresión let, la variable podría introducirse polimórficos, haciendo posibles las especializaciones. ${\displaystyle [{\mathtt {Abs}}]}$ ${\displaystyle \lambda x.e}$ ${\displaystyle \Gamma ,\ x:\tau \vdash _{D}e:\tau '}$ ${\displaystyle [{\mathtt {Let}}]}$ ${\displaystyle \Gamma ,\ x:\sigma \vdash _{D}e_{1}:\tau }$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle \lambda }$

Como consecuencia de esta regulación, 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. ${\displaystyle \lambda f.(f\,{\textrm {true}},f\,{\textrm {0}})}$ ${\displaystyle f}$ ${\displaystyle {\textbf {let}}\ f=\lambda x.x\,{\textbf {in}}\,(f\,{\textrm {true}},f\,{\textrm {0}})}$ ${\displaystyle (bool,int)}$ ${\displaystyle f}$

Regla de generalización

También vale la pena examinar más de cerca la regla de generalización. Aquí, la cuantificación total implícita en la premisa simplemente se mueve al lado derecho de la conclusión, limitada por un cuantificador universal explícito. Esto es posible, ya que no ocurre de forma gratuita en el contexto. Nuevamente, si bien esto hace plausible la regla de generalización, en realidad no es una consecuencia. Por el contrario, 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. ${\displaystyle \Gamma \vdash _{D}e:\sigma }$ ${\displaystyle \vdash _{D}}$ ${\displaystyle \alpha }$

Un algoritmo de inferencia

Ahora que el sistema de deducción de HM está disponible, 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 se forman las pruebas. Esto se hará en el resto de este artículo, enfocándose en las posibles decisiones que uno puede tomar al probar una mecanografía.

Grados de libertad para elegir las reglas.

Aislando los puntos de una prueba, donde no es posible ninguna decisión, el primer grupo de reglas centradas en torno a la sintaxis no deja opción ya que a cada regla sintáctica le corresponde una regla de tipificación única, que determina una parte de la prueba, mientras que entre la conclusión y las instalaciones de estas cadenas de piezas fijas y podrían ocurrir. Tal cadena también podría existir entre la conclusión de la prueba y la regla de expresión máxima. Todas las pruebas deben tener la forma dibujada. ${\displaystyle [{\mathtt {Inst}}]}$ ${\displaystyle [{\mathtt {Gen}}]}$

Debido a que la única opción en una prueba con respecto a la selección de reglas son las cadenas y , la forma de la prueba sugiere la pregunta de si se puede hacer más precisa, cuando estas cadenas podrían no ser necesarias. De hecho, esto es posible y conduce a una variante del sistema de reglas sin tales reglas. ${\displaystyle [{\mathtt {Inst}}]}$ ${\displaystyle [{\mathtt {Gen}}]}$

Sistema de reglas dirigido por la sintaxis

Un tratamiento contemporáneo de HM utiliza un sistema de reglas puramente dirigido por la sintaxis debido a Clemente ^[7] como paso intermedio. En este sistema, la especialización se ubica directamente después de la regla original y se fusiona con ella, mientras que la generalización pasa a formar parte de la regla. Allí también se determina la generalización para producir siempre el tipo más general mediante la introducción de la función , que cuantifica todas las variables monotipo no vinculadas . ${\displaystyle [{\mathtt {Var}}]}$ ${\displaystyle [{\mathtt {Let}}]}$ ${\displaystyle {\bar {\Gamma }}(\tau )}$ ${\displaystyle \Gamma }$

Formalmente, para validar que este nuevo sistema de reglas es equivalente al original , hay que demostrar que , que se descompone en dos subpruebas: ${\displaystyle \vdash _{S}}$ ${\displaystyle \vdash _{D}}$ ${\displaystyle \Gamma \vdash _{D}\ e:\sigma \Leftrightarrow \Gamma \vdash _{S}\ e:\sigma }$

• ${\displaystyle \Gamma \vdash _{D}\ e:\sigma \Leftarrow \Gamma \vdash _{S}\ e:\sigma }$( Consistencia )
• ${\displaystyle \Gamma \vdash _{D}\ e:\sigma \Rightarrow \Gamma \vdash _{S}\ e:\sigma }$( Integridad )

Si bien la coherencia se puede ver descomponiendo las reglas y en pruebas en , es probable que sea visible que esté incompleta, ya que no se puede mostrar en , por ejemplo, sino solo en . Sin embargo, se puede demostrar una versión ligeramente más débil de integridad ^[8] , a saber ${\displaystyle [{\mathtt {Let}}]}$ ${\displaystyle [{\mathtt {Var}}]}$ ${\displaystyle \vdash _{S}}$ ${\displaystyle \vdash _{D}}$ ${\displaystyle \vdash _{S}}$ ${\displaystyle \lambda \ x.x:\forall \alpha .\alpha \rightarrow \alpha }$ ${\displaystyle \vdash _{S}}$ ${\displaystyle \lambda \ x.x:\alpha \rightarrow \alpha }$

• ${\displaystyle \Gamma \vdash _{D}\ e:\sigma \Rightarrow \Gamma \vdash _{S}\ e:\tau \wedge {\bar {\Gamma }}(\tau )\sqsubseteq \sigma }$

lo que implica que se puede derivar el tipo principal de una expresión para permitirnos generalizar la prueba al final. ${\displaystyle \vdash _{S}}$

Comparando y , ahora solo aparecen monotipos en los juicios de todas las reglas. Además, la forma de cualquier posible prueba 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 plenamente la forma de la prueba. 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. ${\displaystyle \vdash _{D}}$ ${\displaystyle \vdash _{S}}$ ${\displaystyle \vdash _{D}}$ ${\displaystyle [{\mathtt {Inst}}]}$ ${\displaystyle [{\mathtt {Gen}}]}$

Grados de libertad para instanciar las reglas.

Ahora que se conoce la forma de la prueba, ya estamos cerca de formular un algoritmo de inferencia de tipos. Debido a que cualquier prueba para una expresión dada debe tener la misma forma, se puede suponer 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, se espera 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 tipo en cualquier local se determinará como el mejor posible. Y de hecho, uno puede, como sugiere la observación de las reglas de: ${\displaystyle \vdash _{S}}$

• [ Abs ] : La elección crítica es τ . En este punto, no se sabe nada sobre τ , por lo que sólo se puede suponer el tipo más general, que es . El plan es especializar el tipo si fuera necesario. Desafortunadamente, un politipo no está permitido en este lugar, por lo que algo de α tiene que ser suficiente 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 está arreglado, pero podría perfeccionarse aún más. ${\displaystyle \forall \alpha .\alpha }$
• [ Var ] : La elección es cómo refinar σ . Debido a que cualquier elección de un tipo τ aquí 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 anterior, se pueden crear instancias de todas las variables cuantificadas en σ con variables monotipo nuevas , manteniéndolas nuevamente abiertas a un mayor refinamiento.
• [ Let ] : La regla no deja elección. Hecho.
• [ App ] : Sólo la regla de aplicación podría forzar un refinamiento de las variables "abiertas" hasta el momento, como lo exigen ambas premisas.
  1. La primera premisa obliga a que el resultado de la inferencia sea de la forma . ${\displaystyle \tau \rightarrow \tau '}$
     • Si es así, entonces está bien. Posteriormente se puede elegir su τ' para 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 tipo falla porque la primera premisa infirió un tipo que no es ni puede convertirse en un tipo de función.
  2. 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 mano para comparar e igualar si es posible. Si es así, se encuentra un refinamiento y, si no, se detecta nuevamente un error de tipo. Se conoce un método eficaz para "igualar dos términos" mediante sustitución: la Unificación de Robinson en combinación con el llamado algoritmo Union-Find . ^{[ cita necesaria ]}

Para resumir brevemente el algoritmo de búsqueda de unión, dado el conjunto de todos los tipos en una prueba, permite agruparlos en clases de equivalencia mediante un procedimiento de unión y elegir un representante para cada clase utilizando un procedimiento de búsqueda . Al enfatizar la palabra procedimiento en el sentido de efecto secundario , claramente salimos del ámbito de la lógica para preparar un algoritmo eficaz. El representante de a se determina de tal manera que, si tanto a como b son variables de tipo, entonces el representante es arbitrariamente uno de ellos, pero al unir una variable y un término, el término se convierte en el representante. Suponiendo que se tenga a mano una implementación de union-find, se puede formular la unificación de dos monotipos de la siguiente manera: ${\displaystyle {\mathtt {union}}(a,b)}$

unificar(ta, tb): ta = encontrar(ta) tb = encontrar(tb) si ambos ta,tb son términos de la forma D p1..pn con D,n idéntico, entonces unifique(ta[i], tb[i]) para cada i- ésimo parámetro 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 que tenemos a mano un esbozo 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

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 y al mismo tiempo expresa una implementación eficiente. Las reglas ahora especifican un procedimiento con parámetros que conducen a la conclusión donde la ejecución de las premisas se realiza de izquierda a derecha. ${\displaystyle \vdash _{S}}$ ${\displaystyle \Gamma ,e}$ ${\displaystyle \tau }$

El procedimiento especializa el politipo copiando el término y reemplazando las variables de tipo enlazadas consistentemente por nuevas variables monotipo. ' ' produce una nueva variable monotipo. Probablemente, se tenga 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í sola produce el resultado más general. Como se señaló anteriormente, el resultado final debe generalizarse al final para obtener el tipo más general para una expresión determinada. ${\displaystyle inst(\sigma )}$ ${\displaystyle \sigma }$ ${\displaystyle newvar}$ ${\displaystyle {\bar {\Gamma }}(\tau )}$ ${\displaystyle \tau }$ ${\displaystyle {\bar {\Gamma }}(\tau )}$

Debido a que los procedimientos utilizados 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 va a inferir un tipo. Esto contrasta fuertemente con muchos otros intentos de derivar algoritmos de inferencia de tipos, que a menudo resultaron ser NP-difíciles , si no indecidibles con respecto a la terminación. Por lo tanto, el HM funciona tan bien como lo pueden hacer los mejores algoritmos de verificación de tipos completamente informados. La verificación de tipos aquí significa que un algoritmo no tiene que encontrar una prueba, sino solo validar una determinada.

La eficiencia se reduce ligeramente porque la vinculación de variables de tipo en el contexto debe mantenerse para permitir el cálculo y permitir una verificación de ocurrencia para evitar la creación de tipos recursivos durante . Un ejemplo de tal caso es , para el cual no se puede derivar ningún tipo usando HM. En la práctica, los tipos son sólo términos pequeños y no construyen estructuras en expansión. Por lo tanto, en el análisis de complejidad, se puede compararlos como costos constantes y retener O(1). ${\displaystyle {\bar {\Gamma }}(\tau )}$ ${\displaystyle {\mathit {unify}}(\alpha ,\tau )}$ ${\displaystyle \lambda \ x.(x\ x)}$

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 base semántica.

El punto más crítico en la argumentación anterior es el refinamiento de las variables monotipo limitadas por el contexto. Por ejemplo, el algoritmo cambia audazmente el contexto mientras infiere, por ejemplo , porque la variable monotipo agregada al contexto para el parámetro posteriormente debe refinarse al manejar la aplicación. El problema es que las normas de deducción no permiten tal precisión. Argumentar que el tipo refinado podría haberse agregado antes en lugar de la variable monotipo es, en el mejor de los casos, una solución. ${\displaystyle \lambda f.(f\ 1)}$ ${\displaystyle f}$ ${\displaystyle int\rightarrow \beta }$

La clave para alcanzar un argumento formalmente satisfactorio es incluir adecuadamente el contexto dentro del refinamiento. Formalmente, la tipificación es compatible con la sustitución de variables de tipo libre.

${\displaystyle \Gamma \vdash _{S}e:\tau \quad \Longrightarrow \quad S\Gamma \vdash _{S}e:S\tau }$

Refinar las variables libres significa refinar toda la tipificación.

Algoritmo W

A partir de ahí, una prueba del algoritmo J conduce al algoritmo W, que sólo hace explícitos los efectos secundarios impuestos por el procedimiento expresando su composición serial mediante las sustituciones . La presentación del algoritmo W en la barra lateral todavía utiliza efectos secundarios en las operaciones en cursiva, pero ahora se limitan a generar símbolos nuevos. 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 libre de efectos secundarios de producir una sustitución que es el unificador más general . ${\displaystyle {\textit {union}}}$ ${\displaystyle S_{i}}$ ${\displaystyle \Gamma \vdash e:\tau ,S}$ ${\displaystyle {\textsf {mgu}}}$ ${\displaystyle {\textit {union}}}$

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:

Tal como está, W no es un algoritmo eficiente; las sustituciones se aplican con demasiada frecuencia. Fue formulado para ayudar en 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 que J. Tiene sus ventajas cuando los efectos secundarios no están disponibles o son no deseados. W también es necesario para demostrar la integridad, que él tiene en cuenta 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 mal uso de los monotipos como variables de prueba "abiertas", la posibilidad de que las variables monotipo adecuadas pudieran verse perjudicadas se eludió al introducir nuevas variables y esperar lo mejor. Pero hay un problema: una de las promesas hechas fue que estas nuevas variables se "tendrían en cuenta" como tales. Esta promesa no la cumple el algoritmo.

Al tener un contexto , la expresión no se puede escribir en ni o , pero los algoritmos generan el tipo , donde W además entrega 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 más cuidadosamente las variables de prueba y las variables monotipo. ${\displaystyle 1:int,\ f:\alpha }$ ${\displaystyle f\ 1}$ ${\displaystyle \vdash _{D}}$ ${\displaystyle \vdash _{S}}$ ${\displaystyle \beta }$ ${\displaystyle \left\{\alpha \mapsto int\rightarrow \beta \right\}}$

Los autores eran muy conscientes del problema pero decidieron no solucionarlo. Se podría suponer que detrás de esto hay una razón pragmática. Si bien una implementación más adecuada de la inferencia de tipos habría permitido que el algoritmo tratara con 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, se abandonó la complicación innecesaria 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 puede realizarse para contextos con una condición secundaria. ${\displaystyle free(\Gamma )=\emptyset }$

${\displaystyle {\begin{array}{lll}{\text{(Correctness)}}&\Gamma \vdash _{W}e:\tau ,S&\quad \Longrightarrow \quad \Gamma \vdash _{S}e:\tau \\{\text{(Completeness)}}&\Gamma \vdash _{S}e:\tau &\quad \Longrightarrow \quad \Gamma \vdash _{W}e:\tau ',S\quad \quad {\text{forall}}\ \tau \ {\text{where}}\ {\overline {\emptyset }}(\tau ')\sqsubseteq \tau \end{array}}}$

La condición secundaria de 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 activar el lema de sustitución que atraviesa la sustitución y . A partir de ahí las pruebas son por inducción sobre la expresión. ${\displaystyle S}$ ${\displaystyle \vdash _{S}}$ ${\displaystyle \vdash _{W}}$

Otra obligación de prueba es el propio lema de sustitución, es decir, la sustitución de la tipificación, que finalmente establece la cuantificación total. Esto último no puede demostrarse 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 mecanografiada 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 . ${\displaystyle {\mathit {fix}}:\forall \alpha .(\alpha \rightarrow \alpha )\rightarrow \alpha }$ ${\displaystyle {\mathtt {rec}}\ v=e_{1}\ {\mathtt {in}}\ e_{2}\ ::={\mathtt {let}}\ v={\mathit {fix}}(\lambda v.e_{1})\ {\mathtt {in}}\ e_{2}}$

Alternativamente, es posible una extensión de la sintaxis de la expresión y una regla de escritura adicional:

${\displaystyle \displaystyle {\frac {\Gamma ,\Gamma '\vdash e_{1}:\tau _{1}\quad \dots \quad \Gamma ,\Gamma '\vdash e_{n}:\tau _{n}\quad \Gamma ,\Gamma ''\vdash e:\tau }{\Gamma \ \vdash \ {\mathtt {rec}}\ v_{1}=e_{1}\ {\mathtt {and}}\ \dots \ {\mathtt {and}}\ v_{n}=e_{n}\ {\mathtt {in}}\ e:\tau }}\quad [{\mathtt {Rec}}]}$

dónde

• ${\displaystyle \Gamma '=v_{1}:\tau _{1},\ \dots ,\ v_{n}:\tau _{n}}$
• ${\displaystyle \Gamma ''=v_{1}:{\bar {\Gamma }}(\ \tau _{1}\ ),\ \dots ,\ v_{n}:{\bar {\Gamma }}(\ \tau _{n}\ )}$

básicamente fusionando y al mismo tiempo incluyendo las variables definidas recursivamente en posiciones monotipo donde aparecen a la izquierda del pero como politipos a la derecha del mismo. ${\displaystyle [{\mathtt {Abs}}]}$ ${\displaystyle [{\mathtt {Let}}]}$ ${\displaystyle {\mathtt {in}}}$

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 sencilla modificación anterior tiene efectos en ambos:

• La propiedad de normalización fuerte queda invalidada porque se pueden formular términos no terminantes.
• La lógica colapsa porque el tipo se vuelve habitado . ${\displaystyle \forall a.a}$

Sobrecarga

La sobrecarga significa que se pueden definir y utilizar diferentes funciones con el mismo nombre. La mayoría de los lenguajes de programación al menos proporcionan 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 into real. Debido a que una mezcla de estos diferentes tipos dentro de la misma expresión también exige una conversión implícita, la sobrecarga, especialmente para estas operaciones, a menudo está integrada en el propio lenguaje de programación. En algunos lenguajes, esta característica está generalizada y puesta 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 necesaria ]} , se ha introducido un medio para sistematizar la sobrecarga que se asemeja tanto en forma como en 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 las órdenes, teniendo la siguiente anotación de tipo en Haskell:

clasificación rápida :: Ordenar a => [ a ] ​​-> [ a ]       

Aquí, el tipo ano 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 las funciones. Las implementaciones adecuadas de estos predicados luego se pasan a Quicksorts como parámetros adicionales, tan pronto como Quicksort se utiliza en tipos más concretos que proporcionan una implementación única de la función sobrecargada QuickSort.

Debido a que las "clases" sólo permiten un único tipo como argumento, el sistema de tipos resultante aún puede proporcionar inferencia. Además, las clases de tipos pueden equiparse con algún tipo de orden de sobrecarga que permita 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 adecuados. 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 mismos de forma más adecuada. Los tipos de orden superior se utilizan para crear un sistema de tipos aún más expresivo.

Desafortunadamente, 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 hay que proceder en pasos de niveles de abstracción. La investigación en cálculo lambda de segundo orden , un paso adelante, demostró que la inferencia de tipos es indecidible en esta generalidad.

Haskell introduce un nivel superior llamado kind . En Haskell estándar, los tipos se infieren y se utilizan para poco más que describir la aridad de los constructores de tipos. por ejemplo, se considera que un constructor de tipos de lista asigna un tipo (el tipo de sus elementos) a otro tipo (el tipo de lista que contiene dichos elementos); notacionalmente esto se expresa como . Hay extensiones de idioma disponibles que amplían los tipos para emular características de un sistema de tipos dependiente . ^[9] ${\displaystyle *\to *}$

Subtipificación

Los intentos de combinar subtipos e inferencia de tipos han causado bastante frustración. Es sencillo acumular y propagar restricciones de subtipificación (a diferencia de las restricciones de igualdad de tipos), haciendo que las restricciones resultantes formen parte de los esquemas de tipificación inferidos, por ejemplo , donde hay una restricción en la variable de tipo . Sin embargo, debido a que las variables de tipo ya no se unifican con entusiasmo en este enfoque, tiende a generar esquemas de tipificación grandes y difíciles de manejar que contienen muchas variables de tipo y restricciones inútiles, lo que los hace difíciles de leer y comprender. Por lo tanto, se dedicó un esfuerzo considerable a simplificar dichos esquemas de tipificación y sus restricciones, utilizando técnicas similares a las de la simplificación no determinista de autómatas finitos (NFA) (útil en presencia de tipos recursivos inferidos). ^[10] Más recientemente, Dolan y Mycroft ^[11] formalizaron la relación entre la simplificación del esquema de tipificación y la simplificación de NFA y demostraron que una versión algebraica de la formalización de la subtipificación permitió generar esquemas de tipificación principales compactos para un lenguaje similar a ML (llamado MLsub). En particular, el esquema de tipificación propuesto utilizó una forma restringida de tipos de unión e intersección en lugar de restricciones explícitas. Parreaux afirmó más tarde ^[12] que esta formulación algebraica era equivalente a un algoritmo relativamente simple parecido al Algoritmo W, y que el uso de tipos de unión e intersección no era esencial. ${\displaystyle \forall \alpha .\ (\alpha \leq T)\Rightarrow \alpha \rightarrow \alpha }$ ${\displaystyle \alpha \leq T}$ ${\displaystyle \alpha }$

Por otro lado, la inferencia de tipos ha resultado más difícil en el contexto de los lenguajes de programación orientados a objetos, porque los métodos de objetos tienden a requerir polimorfismo de primera clase al estilo del Sistema F (donde la inferencia de tipos es indecidible) y debido a características como F -polimorfismo acotado . En consecuencia, los sistemas de tipos con subtipos que permiten la programación orientada a objetos, como el sistema de Cardelli , ^[13] no admiten la inferencia de tipos de estilo HM. ${\displaystyle F_{<:}}$

El polimorfismo de filas se puede utilizar como alternativa a la subtipificación para respaldar características del lenguaje como registros estructurales. ^[14] Si bien este estilo de polimorfismo es menos flexible que la subtipificación en algunos aspectos, en particular requiere más polimorfismo del estrictamente necesario para hacer frente a la falta de direccionalidad en las restricciones de tipo, tiene la ventaja de que puede integrarse bastante con los algoritmos HM estándar. fácilmente.

Notas

1. La inferencia de tipo Hindley-Milner es DEXPTIME completa. De hecho, simplemente decidir si un programa ML se puede escribir (sin tener que inferir un tipo) es en sí mismo DEXPTIME completo. El comportamiento no lineal se manifiesta, aunque principalmente a través de estímulos patológicos . Así, las pruebas teóricas de la complejidad de Mairson (1990) y Kfoury, Tiuryn ​​y Urzyczyn (1990) sorprendieron a la comunidad investigadora. ^{[ cita necesaria ]}
2. Los politipos se denominan "esquemas de tipos" en el artículo original.
3. Los tipos paramétricos no estaban presentes en el artículo original sobre HM y no son necesarios para presentar el método. Ninguna de las reglas de inferencia siguientes se ocupará de ellas ni siquiera las anotará. Lo mismo se aplica a los "tipos primitivos" no paramétricos en dicho artículo. Toda la maquinaria para la inferencia de tipos polimórficos se puede definir sin ellos. Se han incluido aquí a modo de ejemplos, pero también porque la naturaleza de HM tiene que ver con 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. ${\displaystyle C\ \tau \dots \tau }$ ${\displaystyle \tau \rightarrow \tau }$
4. Haskell proporciona la extensión de lenguaje ScopedTypeVariables que permite incluir variables de tipo totalmente cuantificadas en el alcance.

Referencias

1. Hindley, J. Roger (1969). "El esquema tipográfico principal de un objeto en lógica combinatoria". Transacciones de la Sociedad Matemática Estadounidense . 146 : 29–60. doi :10.2307/1995158. JSTOR  1995158.
2. Milner, Robin (1978). "Una teoría del polimorfismo de tipos en programación". Revista de Ciencias de la Computación y de Sistemas . 17 (3): 348–374. CiteSeerX 10.1.1.67.5276 . doi :10.1016/0022-0000(78)90014-4. S2CID  388583. 
3. Damas, Luis (1985). Trabajo de tipo en lenguajes de programación (tesis doctoral). Universidad de Edimburgo. hdl :1842/13555. CST-33-85.
4. Damas, Luis; Milner, Robin (1982). Esquemas de tipos principales para programas funcionales (PDF) . IX Simposio sobre Principios de lenguajes de programación (POPL'82). ACM. págs. 207–212. doi :10.1145/582153.582176. ISBN 978-0-89791-065-1.
5. Milner, Robin (1978), "Una teoría del polimorfismo de tipos en la programación", Journal of Computer and System Sciences , 17 (3): 348–375, doi : 10.1016/0022-0000(78)90014-4 , hdl : 20.500.11820/d16745d7-f113-44f0-a7a3-687c2b709f66
6. 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 noveno simposio anual del IEEE sobre lógica en informática (LICS) . págs. 176–185. doi :10.1109/LICS.1994.316068. ISBN 0-8186-6310-3. S2CID  15078292.
7. Clemente (1986). Un lenguaje aplicativo simple: Mini-ML (PDF) . LFP'86. ACM. doi :10.1145/319838.319847. ISBN 978-0-89791-200-6.
8. Vaughan, Jeff (23 de julio de 2008) [5 de mayo de 2005]. "Una prueba de corrección del algoritmo de inferencia de tipo Hindley-Milner" (PDF) . Archivado desde el original (PDF) el 24 de marzo de 2012. {{cite journal}}: Citar diario requiere |journal=( ayuda )
9. Yorgey; Brent; Weirich; Estefanía; Cretino; julián; Peyton Jones; Simín; Vytiniotis; Dimitrios; Magalhaes; José Pedro (enero 2012). "Darle un ascenso a Haskell". Actas de TLDI'12 : 53–66. doi :10.1145/2103786.2103795. ISBN 978-1-4503-1120-5.
10. Pottier, François (1998). Inferencia de tipos en presencia de subtipos: de la teoría a la práctica (tesis) . Consultado el 10 de agosto de 2021 .
11. Dolan, Stephen; Mycroft, Alan (2017). "Polimorfismo, subtipos e inferencia de tipos en MLsub" (PDF) . POPL 2017: Actas del 44º Simposio ACM SIGPLAN sobre principios de lenguajes de programación . doi :10.1145/3009837.3009882.
12. Parreaux, Lionel (2020). "La esencia simple de la subtipificación algebraica: inferencia de tipos principales con subtipificación simplificada". 25.a Conferencia internacional ACM SIGPLAN sobre programación funcional - ICFP 2020, [evento en línea], 24 al 26 de agosto de 2020 . doi : 10.1145/3409006 .
13. Cardelli, Luca; Martini, Simone; Mitchell, John C.; Scedrov, André (1994). "Una extensión del sistema F con subtipos". Información y Computación, vol. 9 . Holanda del Norte, Ámsterdam. págs. 4–56. doi : 10.1006/inco.1994.1013 .
14. Daan Leijen, Registros extensibles con etiquetas de ámbito , 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). "La decisión sobre la tipificación de ML se completa para el tiempo exponencial determinista". 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 completa en tiempo de expansión". Caap'90 . Apuntes de conferencias sobre informática. vol. 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.