Relación entre el sistema de asignación de tipo (TA) y el sistema Hindley-Milner

Recientemente comencé mis estudios en teoría de tipos / sistemas de tipos y cálculo Lambda.

Ya he leído sobre el cálculo simple de Lambda tipificado en estilo Church y Curry. El último también se conoce como sistema de asignación de tipo (TA).

Estoy pensando en las relaciones entre TA y Hindley-Milner (HM), el sistema en lenguajes como ML y Haskell.

El libro Lambda-Calculus and Combinators: An Introduction (Hindley) dice que la TA es polimórfica (pág. 119). ¿Es esa la misma sensación de polimorfismo en sistemas como HM y System-F?

Se dice que TA tiene una fuerte propiedad de normalización, por lo que no está completa. Los idiomas que utilizan el sistema HM están completos, por ejemplo, Haskell. Así debe ser el caso de que el sistema HM permita que términos como el bucle infinito reciban un tipo. ¿Es correcto o me falta algo? $\Omega$

De cualquier manera, me gustaría saber la relación entre TA y HM.

type-theory type-checking type-inference Rafael Castro
fuente

Nunca antes había escuchado sobre el sistema Typed Assignment. Lo busqué en Google y obtuve esta pregunta como la tercera respuesta, lo que significa que debe ser muy nicho. ¿Puedes explicar qué es? Además, ¿qué es un "bucle infinito"? ¿Te refieres a un cálculo sin interrupciones?

cabeza de jardín

La asignación de tipo es una versión del cálculo simple de Lambda tipeado creado por Curry. Debes buscar eso en el libro mencionado. Y sí, es el cálculo de bucle infinito predeterminado o el programa que no se detiene.

Ω

$\Omega$

λ

$\lambda$

Rafael Castro el

Creo que debería hacer esta pregunta en algún otro intercambio de pila más teórico / matemático. ¿Debería?

Rafael Castro

Tu podrías intentar. Dale una oportunidad a cstheory y mathoverflow. Sin embargo, usted dijo que "recientemente comenzó sus estudios", por lo que me sorprendería que su pregunta fuera tan avanzada. Creo que solo está utilizando una terminología poco común para describir conceptos simples (aunque podría estar equivocado). Por ejemplo, el bucle infinito generalmente se denomina tipo inferior (si te entiendo correctamente).

cabeza de jardín

Definitivamente mi pregunta no está en el nivel de investigación. Mi pregunta es más como "hey, entiendo estos conceptos básicos ¿verdad?". Pero lo intentaré, tal vez obtenga una respuesta.

Rafael Castro

Respuestas:

El sistema F y su subsistema HM tienen un tipo anterior para la cuantificación universal:

τ ::= \forall x . τ | . . .

$\tau \quad::=\quad \forall x.\tau \ |\ ...$

que el sistema en Hindley / Seldin no tiene. Esa es la diferencia clave.

Ahora el Sistema F no tiene una inferencia de tipo decidible, y HM es una forma de combinar la inferencia de tipo con polimorfismo paramétrico razonablemente expresivo. HM logra esto permitiendo solo la cuantificación universal más externa, es decir, todos los tipos son de la forma

\forall x_{1} \forall x_{2} . . . \forall x_{n} . τ

$\forall x_1 \forall x_2 ... \forall x_n.\tau$

donde es libre de cuantificador (y ). HM proporciona un sistema de reglas que garantiza que solo los programas que se puedan escribir de esta manera sean admisibles. Esto se logra mediante el "let-polimorfismo". El sistema en Hindley / Seldin no hace nada de eso. Más tarde, en el Capítulo 13, Hindley / Seldin presenta sistemas de tipo puro (PTS), de los cuales el Sistema F es un caso especial. No estoy seguro si HM se puede expresar como PTS. $\tau$ $n \geq 0$

La cuestión de la fuerte normalización es ortogonal. El sistema F y HM se están normalizando fuertemente, pero eso puede remediarse fácilmente mediante la introducción de combinadores de punto fijo o similares. El documento Principales esquemas de tipos para programas funcionales de L. Damas y R. Milner incluso declara esto: " Por ejemplo, la recursión se omite ya que puede introducirse simplemente agregando el operador polimórfico de punto fijo ... " La introducción de puntos fijos , completando el sistema Turing, no plantea problemas desde el punto de vista de la inferencia de tipos.

Martin Berger
fuente

¿Sería correcto pensar que HM = TA + "let-polimorfismo"? El libro Lambda-Calculus and Combinators (Hindley), hasta el momento, no dijo nada sobre la cuantificación universal de los tipos. TA usa variables de tipo, pero no sé nada sobre el rango de estos tipos. Para ser claros, todavía no he estudiado el sistema HM, pero sé para qué sirve.

Rafael Castro

@RafaelCastro Si entrecierra los ojos ... Si tiene experiencia en CS, el libro TAPL de Pierce es probablemente una explicación mucho más accesible de HM y de los sistemas de mecanografía en general. El documento Damas / Milner al que hice referencia es muy fácil de leer, si puede ver más allá de la configuración de tipo antigua. Se lo doy a mis estudiantes de doctorado principiantes. ¡Dale una lectura! Hindley / Seldin es un poco formal.

Martin Berger

@RafaelCastro Las variables de tipo varían sobre los tipos. Todos los tipos. Esta es la razón por la cual el Sistema F es impredecible.

Martin Berger

Gracias. Sí, soy un estudiante universitario en CS, así que intentaré el libro TAPL de Pierce.

Rafael Castro

@RafaelCastro Probablemente no haya una mejor manera de aprender sobre los tipos que leer TAPL e implementar los sistemas de mecanografía que se discuten allí.

Martin Berger