Sistema de tipos 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 lo 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 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 están su completitud y su capacidad para inferir el tipo más general de un programa dado sin anotaciones de tipo proporcionadas por el programador u otras sugerencias. El algoritmo W es un método de inferencia de tipo eficiente en la práctica y se ha aplicado con éxito en bases de código grandes, aunque tiene una alta complejidad teórica . ^{[nota 1]} HM se utiliza preferiblemente 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 extendido de varias maneras, más notablemente 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 tipos. Al ser sensible al alcance , no se limita a derivar los tipos solo de una pequeña parte del código fuente, sino más bien de programas o módulos completos. Al ser capaz de lidiar también con tipos paramétricos , es fundamental para los sistemas de tipos de muchos lenguajes de programación funcional . 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 tipos simples que fue ideado por Haskell Curry y Robert Feys en 1958. ^{[ cita requerida ]} 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, Algorithm 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 vs. polimorfismo

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

3 : Número suma 3 4 : Número añadir: Número -> Número -> Número

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

id ≡ λ x . x

que simplemente devuelve cualquier valor al que se le 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 en la literatura la notación de esquemas de tipos , que enfatiza la naturaleza paramétrica del polimorfismo. Además, las constantes pueden tipificarse con variables de tipo (cuantificadas). Por ejemplo:

contras: para todos a . a -> Lista a -> Lista a nil : para todo a . Lista a id: para todos a . a -> a

Los tipos polimórficos pueden volverse monomórficos mediante la sustitución consistente de sus variables. Algunos 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.

A diferencia 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, a saber, la subtipificación en relación con la programación orientada a objetos y la sobrecarga . Si bien la subtipificación es incompatible con HM, existe una variante de sobrecarga sistemática en el sistema de tipos basado en HM de Haskell.

Let-polimorfismo

Al extender la inferencia de tipos para el cálculo lambda de tipos simples hacia el polimorfismo, uno tiene que decidir si es admisible asignar un tipo polimórfico no solo como tipo de una expresión, sino también como el tipo de una variable con límite λ. Esto permitiría asignar el tipo de identidad genérico a la variable 'id' en:

(λ id . ... (id 3) ... (id "texto") ... ) (λ x . x)

Permitir esto da lugar al cálculo lambda polimórfico ; sin embargo, desafortunadamente, la inferencia de tipos en este sistema no es decidible. ^[6] En cambio, HM distingue las variables que están inmediatamente ligadas a una expresión de las variables ligadas a λ más generales, llamando a las primeras variables ligadas a let, y permite que se asignen tipos polimórficos solo a estas. Esto conduce al polimorfismo let, donde el ejemplo anterior toma la forma

 sea ​​id = λ x . x en ... (id 3) ... (id "texto") ...

que se puede tipificar con un tipo polimórfico para 'id'. Como se indicó, la sintaxis de expresión se extiende para hacer explícitas las variables enlazadas a let y, al restringir el sistema de tipos para permitir que solo las variables enlazadas a let tengan tipos polimórficos, mientras que los parámetros en las abstracciones lambda deben tener un tipo monomórfico, la inferencia de tipos se vuelve decidible.

Descripción general

El resto de este artículo se desarrolla de la siguiente manera:

• Se define el sistema de tipos de HM. Esto se hace describiendo un sistema de deducción que precisa qué expresiones tienen qué tipo, si es que tienen alguno.
• A partir de ahí, se avanza 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, se esboza una implementación eficiente (algoritmo J), que apela principalmente a la intuición metalógica del lector.
• Como sigue abierto si el algoritmo J realmente realiza el sistema de deducción inicial, se introduce una implementación menos eficiente (algoritmo W) y se sugiere su uso en una prueba.
• Finalmente, se discuten otros temas relacionados con el algoritmo.

Se utiliza la misma descripción del sistema de deducción en todo el documento, 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 se puede describir 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, ya que está escrita no para estudiar la gramática superficial , sino más bien la gramática de profundidad , y deja algunos detalles sintácticos abiertos. Esta forma de presentación es habitual. Sobre esta base, se utilizan reglas de tipificación 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 deben escribir son exactamente las del cálculo lambda extendido con una expresión let, como se muestra en la tabla adyacente. Se pueden utilizar paréntesis para desambiguar una expresión. La aplicación se vincula a la izquierda y los vínculos son más fuertes 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 para mayor comodidad. Por ejemplo, una función que asigna números enteros a cadenas tiene tipo . Nuevamente, se pueden usar paréntesis para desambiguar una expresión de tipo. La aplicación vincula más fuerte que la flecha infija, que es vinculante a 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 de tipo se admiten como monotipos. Los monotipos no deben confundirse con los tipos monomórficos, que excluyen las 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, 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 identidad es un valor para este tipo. ${\displaystyle \forall \alpha .\alpha \rightarrow \alpha }$

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

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

La igualdad de politipos depende de la reordenación de la cuantificación y del cambio de nombre de las variables cuantificadas ( conversión). Además, las variables cuantificadas que no aparecen en el monotipo pueden eliminarse. ${\displaystyle \alpha }$

Contexto y tipificación

Para unir de manera significativa las partes aún disjuntas (expresiones de sintaxis y tipos) se necesita una tercera parte: el contexto. Sintácticamente, un contexto es una lista de pares , llamados asignaciones , suposiciones o enlaces , 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 ocurrencia de una variable de tipo cuantificada en se denomina vinculada y todas las variables de tipo no vinculadas en se denominan libres . Además de la cuantificación en politipos, las variables de tipo también pueden vincularse al aparecer en el contexto, pero con el efecto inverso en el lado derecho de . Dichas variables se comportan entonces como constantes de tipo allí. Finalmente, una variable de tipo puede aparecer legalmente no vinculada en un tipado, en cuyo caso se cuantifican todas implícitamente. ${\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 ligadas y no ligadas es un poco poco común en los lenguajes de programación. A menudo, todas las variables de tipo se tratan implícitamente como cuantificadas. Por ejemplo, no hay cláusulas con variables libres en Prolog . Lo mismo ocurre en Haskell, ^{[nota 4]} donde todas las variables de tipo aparecen cuantificadas implícitamente, es decir, un tipo Haskell a -> asignifica aquí. Relacionado y también muy poco común es el efecto de ligadura del lado derecho de las asignaciones. ${\displaystyle \forall \alpha .\alpha \rightarrow \alpha }$ ${\displaystyle \sigma }$

Por lo general, la mezcla de variables de tipo ligadas y no ligadas 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 la variable ligada en el ámbito circundante. tiene el tipo . Se podría imaginar que la variable de tipo libre en el tipo de esté ligada por la en el tipo de . Pero tal alcance no se puede expresar en HM. En cambio, la vinculación se realiza mediante 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

El polimorfismo significa que una misma expresión puede tener (quizás una cantidad infinita) de tipos. Pero en este sistema de tipos, estos tipos no están completamente desconectados, sino que 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 para esta función es , mientras que los otros son más específicos y pueden derivarse del general reemplazando consistentemente otro tipo por 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 en se sustituye de manera consistente de modo que se obtenga lo que 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 un tipo monomórfico (base) por una variable cuantificada es sencillo, sustituir un politipo tiene algunas dificultades causadas por la presencia de variables libres. En particular, las variables no ligadas no deben reemplazarse. Aquí se las trata como constantes. Además, las cuantificaciones solo pueden ocurrir en el nivel superior. Para sustituir un tipo paramétrico, uno debe levantar sus cuantificadores. La tabla de la derecha muestra la regla con precisión.

Como alternativa, se puede considerar 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 dicha notación, la especialización se reduce a un simple reemplazo consistente de dichas 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 de tipos es un uso del orden, este desempeña un papel secundario 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. El orden garantiza que dicho resumen exista como el tipo más general de la 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:

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

A diferencia de la regla de especialización, esto no forma 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 definidas a continuación. Las variables de tipo libre en una tipificación 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 de lo que prohíbe su sustitución en la regla de especialización es nuevamente que un reemplazo debe ser consistente y debería incluir toda la tipificación. ${\displaystyle \vdash }$

En este artículo se analizarán 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 , utilizando las tipificaciones como juicios . Cada una de las reglas define qué conclusión se puede extraer de qué premisas. Además de los juicios, algunas condiciones adicionales introducidas anteriormente también se pueden utilizar como premisas.

Una demostración que utiliza las reglas es una secuencia de juicios de modo que todas las premisas se enumeran antes de una conclusión. Los ejemplos siguientes muestran un posible formato de demostración. 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

Véase también Reglas de mecanografía

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

Las primeras cuatro reglas (acceso a 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 subexpresiones y finalmente combinan los tipos individuales encontrados en las premisas con el tipo en 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 . Se ocupan de la especialización y generalización de tipos. Si bien la regla debería quedar clara a partir de la sección sobre especialización anterior, complementa a la anterior, trabajando en la dirección opuesta. Permite la generalización, es decir, cuantificar variables monotípicas no ligadas en el 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 proporcionan tanto la expresión como el tipo, se trata de un uso de las reglas para la verificación de tipos.

Ejemplo : Una prueba de donde , podría escribirse ${\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}}}$

Let-polimorfismo

No visible inmediatamente, el conjunto de reglas codifica una regulación bajo qué circunstancias un tipo puede ser generalizado o no mediante un uso ligeramente diferente de mono- y politipos en las reglas y . Recuerde que y denotan poli- y monotipos respectivamente. ${\displaystyle [{\mathtt {Abs}}]}$ ${\displaystyle [{\mathtt {Let}}]}$ ${\displaystyle \sigma }$ ${\displaystyle \tau }$

En la regla , la variable valor del parámetro de la función se añade al contexto con un tipo monomórfico a través de la premisa , mientras que en la regla , la variable entra 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 let-expresión, la variable podría introducirse polimórfica, 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 tipificar, 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 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 merece la pena examinar más detenidamente la regla de generalización. En este caso, la cuantificación total implícita en la premisa se desplaza simplemente al lado derecho de la conclusión, limitada por un cuantificador universal explícito. Esto es posible, ya que no se da libremente en el contexto. De nuevo, si bien esto hace que la regla de generalización sea plausible, 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á a la mano, se podría presentar un algoritmo y validarlo con respecto a las reglas. Alternativamente, podría ser posible derivarlo analizando 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, centrándose en las posibles decisiones que se pueden tomar al probar una tipificación.

Grados de libertad al elegir las reglas

Aislando los puntos de una demostración, donde no es posible tomar ninguna decisión, el primer grupo de reglas centradas en la sintaxis no deja opción, ya que a cada regla sintáctica corresponde una regla de tipificación única, que determina una parte de la demostración, mientras que entre la conclusión y las premisas de estas partes fijas podrían darse cadenas de y . Tal cadena también podría existir entre la conclusión de la demostración y la regla de expresión superior. Todas las demostraciones deben tener la forma así esbozada. ${\displaystyle [{\mathtt {Inst}}]}$ ${\displaystyle [{\mathtt {Gen}}]}$

Como 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, en casos en que estas cadenas podrían no ser necesarias. Esto es de hecho posible y conduce a una variante del sistema de reglas sin tales reglas. ${\displaystyle [{\mathtt {Inst}}]}$ ${\displaystyle [{\mathtt {Gen}}]}$

Sistema de reglas dirigidas por la sintaxis

Un tratamiento contemporáneo de HM utiliza un sistema de reglas puramente dirigido por la sintaxis debido a Clement ^[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 se vuelve parte de la regla. Allí, la generalización también se determina para producir siempre el tipo más general mediante la introducción de la función , que cuantifica todas las variables monotipo no limitadas en . ${\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 }$( Completitud )

Si bien la consistencia se puede ver al descomponer las reglas y de en pruebas en , es probable que sea visible que es incompleta, ya que no se puede demostrar en , por ejemplo, sino solo en . Sin embargo, solo se puede demostrar una versión ligeramente más débil de completitud ^[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, lo que nos permite generalizar la prueba al final. ${\displaystyle \vdash _{S}}$

Comparando y , ahora sólo aparecen monotipos en los juicios de todas las reglas. Además, la forma de cualquier prueba posible con el sistema de deducción es ahora idéntica a la forma de la expresión (ambas vistas como árboles ). Por lo 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. ${\displaystyle \vdash _{D}}$ ${\displaystyle \vdash _{S}}$ ${\displaystyle \vdash _{D}}$ ${\displaystyle [{\mathtt {Inst}}]}$ ${\displaystyle [{\mathtt {Gen}}]}$

Grados de libertad que instancian las reglas

Ahora que se conoce la forma de la prueba, ya estamos cerca de formular un algoritmo de inferencia de tipos. Como 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 pruebas, suponiendo además, dado que el algoritmo resultante se convertirá en un método de inferencia, que el tipo en cualquier premisa se determinará como el mejor posible. Y de hecho, se puede, como sugiere el análisis 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 solo se puede asumir 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 un poco de α tiene que funcionar 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á fijado, pero podría refinarse 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 que arriba, uno puede instanciar todas las variables cuantificadas en σ con nuevas variables monotipo, manteniéndolas nuevamente abiertas a un mayor refinamiento.
• [ Let ] : La regla no deja ninguna opción. Hecho.
• [ App ] : Sólo la regla de aplicación podría forzar un refinamiento de las variables "abiertas" hasta el momento, como lo requieren ambas premisas.
  1. La primera premisa obliga a que el resultado de la inferencia tenga la forma . ${\displaystyle \tau \rightarrow \tau '}$
     • Si es así, entonces está bien. Más tarde se puede elegir su τ' como resultado.
     • En caso contrario, podría ser una variable abierta. Luego, se puede refinar hasta obtener 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.
  2. La segunda premisa requiere que el tipo inferido sea igual a τ de la primera premisa. Ahora hay dos tipos posiblemente diferentes, tal vez con variables de tipo abiertas, a mano para comparar y hacer que sean iguales 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 efectivo para "hacer que dos términos sean iguales" por sustitución, la Unificación de Robinson en combinación con el llamado algoritmo Union-Find . ^{[ cita requerida ]}

Para resumir brevemente el algoritmo de unión-búsqueda, 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 una de esas clases mediante un procedimiento de búsqueda . Si enfatizamos la palabra procedimiento en el sentido de efecto secundario , claramente estamos abandonando el ámbito de la lógica para preparar un algoritmo efectivo. 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 una implementación de unión-búsqueda a mano, 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 unificar(ta[i], tb[i]) para cada parámetro i correspondiente de lo contrario  si al menos uno de ta,tb es una variable de tipo 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ág. 370 y siguientes 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 ceden en la conclusión donde la ejecución de las premisas procede 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 ligado consistentemente por nuevas variables monotipo. ' ' produce una nueva variable monotipo. Probablemente, tiene que copiar el tipo introduciendo nuevas variables para la cuantificación para evitar capturas no deseadas. En general, el algoritmo ahora procede 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 al final, para obtener el tipo más general para una expresión dada. ${\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 debe inferir un tipo. Esto contrasta fuertemente con muchos otros intentos de derivar algoritmos de inferencia de tipos, 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 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 dada.

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 verificación de ocurrencia 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 utilizando HM. En la práctica, 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 la comparación como una constante, reteniendo costos O(1). ${\displaystyle {\bar {\Gamma }}(\tau )}$ ${\displaystyle {\mathit {unify}}(\alpha ,\tau )}$ ${\displaystyle \lambda \ x.(x\ x)}$

Probando el algoritmo

En la sección anterior, al esbozar el algoritmo, se insinuó su demostración mediante una argumentación metalógica. Si bien esto conduce a un algoritmo eficiente J, no queda 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 en la argumentación anterior es el refinamiento de las variables monotipo ligadas por el contexto. Por ejemplo, el algoritmo cambia audazmente el contexto mientras infiere eg , porque la variable monotipo agregada al contexto para el parámetro necesita ser refinada más tarde para cuando se maneja 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 expediente. ${\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, por tanto, 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 al expresar su composición serial por medio de las sustituciones . La presentación del algoritmo W en la barra lateral todavía hace uso de efectos secundarios en las operaciones establecidas en cursiva, pero estos ahora se limitan a generar símbolos nuevos. La forma del 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, su propósito es descrito por Milner ^[2] 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 a demostrar la solidez. Ahora presentamos un algoritmo más simple J que simula W en un sentido preciso.

Aunque consideró que W era más complicado y menos eficiente, lo presentó en su publicación antes de J. Tiene sus méritos cuando no hay efectos secundarios o no se los desea. W también es necesaria para demostrar la integridad, 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 mal uso de los monotipos como variables de prueba "abiertas", se evitó la posibilidad de que las variables de monotipo adecuadas pudieran verse perjudicadas al introducir nuevas variables y esperar que todo saliera bien. Pero hay un problema: una de las promesas hechas fue que estas nuevas variables se "tendrían en cuenta" como tales. El algoritmo no cumple esta promesa.

Al tener un contexto , la expresión no se puede escribir en ni ni , pero los algoritmos dan con el tipo , donde W además proporciona la sustitución , lo que significa que el algoritmo no detecta todos los errores de tipo. Esta omisión se puede corregir fácilmente distinguiendo con más cuidado 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 hay 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 se ocupara de monotipos abstractos, no eran necesarios para la aplicación prevista, en la que ninguno de los elementos de un contexto preexistente tiene variables libres. En vista de esto, se eliminó la complicación innecesaria en favor de un algoritmo más simple. El inconveniente restante es que la prueba del algoritmo con respecto al sistema de reglas es menos general y solo se puede realizar para contextos con como 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 completitud se refiere a que 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 demostrar adecuadamente las obligaciones, primero es necesario fortalecerlas para permitir la activación del lema de sustitución, enhebrando la sustitución a través de y . A partir de allí, las demostraciones se hacen 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 establece finalmente la cuantificación total. Esto último no se puede demostrar formalmente, ya que no se dispone de una sintaxis de ese tipo.

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 se pueden expresar con un combinador de punto fijo . Pero, lamentablemente, el combinador de punto fijo no se puede formular en una versión tipificada del cálculo lambda sin tener un efecto desastroso en el sistema, como se describe a continuación.

Regla de mecanografía

El artículo original ^[4] muestra que la recursión se puede realizar mediante un combinador . Por lo 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 extender la sintaxis de la expresión y aplicar una regla de tipificación 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 de monotipo donde ocurren 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 se invalida porque se pueden formular términos no terminantes.
• La lógica se derrumba porque el tipo queda habitado . ${\displaystyle \forall a.a}$

Sobrecarga

La sobrecarga significa que se pueden definir y utilizar distintas funciones con el mismo nombre. La mayoría de los lenguajes de programación al menos proporcionan la sobrecarga con las operaciones aritméticas integradas (+, <, etc.), para permitir que el programador escriba expresiones aritméticas en la misma forma, incluso para distintos tipos numéricos como into real. Debido a que una mezcla de estos distintos tipos dentro de la misma expresión también exige una conversión implícita, la sobrecarga, especialmente para estas operaciones, suele estar integrada en el propio lenguaje de programación. En algunos lenguajes, esta característica está generalizada 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 debido a los costos computacionales 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 forma como en nombre a la programación orientada a objetos, pero funciona un nivel superior. Las "instancias" en esta sistemática no son objetos (es decir, en el nivel de valor), sino tipos. El ejemplo de ordenación rápida mencionado en la introducción utiliza la sobrecarga en los pedidos, y tiene la siguiente anotación de tipo en Haskell:

Ordenación rápida :: Orden a => [ a ] ​​-> [ a ]       

En este caso, 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 utiliza en el cuerpo de las funciones. Las implementaciones adecuadas de estos predicados se pasan a quicksorts como parámetros adicionales tan pronto como quicksort se utiliza en tipos más concretos, lo que proporciona una única implementación de la función sobrecargada quickSort.

Dado que las "clases" solo permiten un único tipo como argumento, el sistema de tipos resultante puede proporcionar inferencias. Además, las clases de tipos pueden equiparse con algún tipo de orden de sobrecarga que permita organizar las clases como un entramado .

Tipos de orden superior

El polimorfismo paramétrico implica que los tipos mismos se pasan como parámetros como si fueran valores propios. Pasarlos como argumentos a funciones propias, pero también a "funciones de tipos" como en las constantes de tipos "paramétricas", lleva a la pregunta de cómo tipificar de forma más adecuada los tipos mismos. Se utilizan tipos de orden superior 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 que la inferencia de tipos sea imposible en este grado de generalidad. Además, suponer 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 se debe proceder en pasos de niveles de abstracción. La investigación en cálculo lambda de segundo orden , un paso hacia arriba, mostró que la inferencia de tipos es indecidible en esta generalidad.

Haskell introduce un nivel superior denominado 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 piensa que un constructor de tipo de lista asigna un tipo (el tipo de sus elementos) a otro tipo (el tipo de la lista que contiene dichos elementos); en notación, esto se expresa como . Hay extensiones de lenguaje disponibles que extienden los tipos para emular las características de un sistema de tipos dependiente . ^[9] ${\displaystyle *\to *}$

Subtipificación

Los intentos de combinar la subtipificación y la 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 es 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 las hace difíciles de leer y entender. Por lo tanto, se puso un esfuerzo considerable en simplificar dichos esquemas de tipificación y sus restricciones, utilizando técnicas similares a las de la simplificación de autómatas finitos no deterministas (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 principal compactos para un lenguaje similar a ML (llamado MLsub). Cabe destacar que su esquema de tipificación propuesto utilizaba una forma restringida de tipos de unión e intersección en lugar de restricciones explícitas. Parreaux afirmó posteriormente ^[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 otra parte, la inferencia de tipos ha demostrado ser 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 el polimorfismo acotado por F. En consecuencia, los sistemas de tipos con subtipificación que permiten la programación orientada a objetos, como el sistema de Cardelli , ^[13] no admiten la inferencia de tipos al estilo HM. ${\displaystyle F_{<:}}$

El polimorfismo de filas se puede utilizar como una 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 porque 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 se puede integrar con los algoritmos HM estándar con bastante facilidad.

Notas

1. La inferencia de tipos de Hindley-Milner es DEXPTIME -completa. De hecho, el mero hecho de decidir si un programa ML es tipificable (sin tener que inferir un tipo) es en sí mismo DEXPTIME -completo. El comportamiento no lineal se manifiesta, pero sobre todo en entradas patológicas . Por ello, las pruebas teóricas de la complejidad de Mairson (1990) y Kfoury, Tiuryn ​​y Urzyczyn (1990) resultaron una sorpresa para la comunidad de investigación. ^{[ cita requerida ]}
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 que se indican a continuación se ocupará de ellos ni los mencionará. Lo mismo se aplica a los "tipos primitivos" no paramétricos de 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 ejemplo, pero también porque la naturaleza de HM tiene que ver con los tipos paramétricos. Esto proviene del tipo de función , integrado en las reglas de inferencia que se indican 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 incorporar todas las variables de tipo cuantificadas al alcance.

Referencias

1. Hindley, J. Roger (1969). "El esquema de tipos principal de un objeto en lógica combinatoria". Transactions of the American Mathematical Society . 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). Asignaturas de tipo en lenguajes de programación (tesis doctoral). Universidad de Edimburgo. hdl :1842/13555. CST-33-85.
4. Damas, Luis; Milner, Robin (1982). Principales esquemas de tipos para programas funcionales (PDF) . IX Simposio sobre principios de lenguajes de programación (POPL'82). ACM. pp. 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 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 tipabilidad y la comprobación de tipos en el cálculo lambda de segundo orden son equivalentes e indecidibles". Actas del 9.º Simposio anual IEEE sobre lógica en informática (LICS) . pp. 176–185. doi :10.1109/LICS.1994.316068. ISBN . 0-8186-6310-3. Número de identificación del sujeto  15078292.
7. Clement (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 tipos Hindley-Milner" (PDF) . Archivado desde el original (PDF) el 24 de marzo de 2012. {{cite journal}}: Requiere citar revista |journal=( ayuda )
9. Yorgey; Brent; Weirich; Stephanie; Cretin; Julien; Peyton Jones; Simin; Vytiniotis; Dmitrios; Magalhaes; José Pedro (enero de 2012). "Dando a Haskell una promoción". Actas del 8º taller ACM SIGPLAN sobre tipos en el diseño e implementación de lenguajes . pp. 53–66. doi :10.1145/2103786.2103795. ISBN 978-1-4503-1120-5.
10. Pottier, François (1998). Inferencia de tipos en presencia de subtipificación: de la teoría a la práctica (Tesis) . Consultado el 10 de agosto de 2021 .
11. Dolan, Stephen; Mycroft, Alan (2017). "Polimorfismo, subtipificación e inferencia de tipos en MLsub" (PDF) . POPL 2017: Actas del 44.º Simposio SIGPLAN de la ACM 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.ª 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, Andre (1994). "Una extensión del sistema F con subtipificación". Información y Computación, vol. 9 . Holanda Septentrional, Ámsterdam. págs. 4–56. doi : 10.1006/inco.1994.1013 .
14. Daan Leijen, Registros extensibles con etiquetas con á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). "Decidir si la tipabilidad de ML es 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 tipabilidad del aprendizaje automático es completa en tiempo dexp". Caap '90 . Apuntes de clase en 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.