Describir el tipo de inferencia Damas-Milner de manera que el estudiante pueda entender CS101

Question

Hindley-Milner es un sistema del tipo que es la base de los sistemas de tipo de muchos lenguajes de programación funcionales conocidas. Damas-Milner es un algoritmo que infiere (deduce?) Tipos en un sistema de tipo Hindley-Milner.

Wikipedia da una descripción del algoritmo que, como lo que puedo decir, que equivale a una sola palabra: "unificación". Eso es todo? Si es así, eso significa que la parte interesante es el sistema de tipos en sí no es el sistema de inferencia de tipos.

Si Damas-Milner es más de la unificación, me gustaría una descripción de Damas-Milner, que incluye un ejemplo sencillo y, a ser posible, algo de código.

Además, este algoritmo se dice a menudo que hacer la inferencia de tipos. ¿Es realmente un sistema de inferencia? Pensé que sólo estaba deduciendo los tipos.

preguntas relacionadas:

• Lo que es Hindley Miller?
• La inferencia de tipos de problema de la unificación

Answer 1

Damas Milner es sólo un uso estructurado de la unificación.

Cuando se recursivamente en una expresión lambda se conforma un nuevo nombre de la variable. Cuando, en una sub-plazo, encuentra que la variable utilizada de una manera que requeriría un tipo determinado, se registra la unificación de esa variable y ese tipo. Si alguna vez se trata de unificar dos tipos que no tienen sentido, como decir que una variable individual es a la vez un Int y una función de un -.> B, entonces te grita por hacer algo mal

  

Además, este algoritmo se dice a menudo que hacer la inferencia de tipos. ¿Es realmente un sistema de inferencia? Pensé que sólo estaba deduciendo los tipos.

Deduciendo los tipos es la inferencia de tipos. Comprobación para ver que tipo de anotaciones son válidos por un período dado es la verificación de tipos. Son diferentes problemas.

  

Si es así, eso significa que la parte interesante es el sistema de tipos en sí no es el sistema de inferencia de tipos.

Se dice comúnmente que los sistemas de tipo de estilo Hindley-Milner están equilibrados en una cúspide. Si añade más funcionalidad se hace imposible inferir los tipos. Así escribir extensiones del sistema que puede capa en la parte superior de un sistema de tipos Hindley-Milner estilo sin destruir sus propiedades de inferencia son realmente las partes interesantes de los lenguajes funcionales modernos. En algunos casos, mezclamos la inferencia de tipos y el tipo de cheques, por ejemplo, en Haskell una gran cantidad de extensiones modernas no puede deducirse, pero se puede comprobar, por lo que requieren anotaciones de tipos de características avanzadas, como la repetición polimórfica.

Answer 2

  

Wikipedia da una descripción del algoritmo que, por lo que yo puedo decir, equivale a una sola palabra: "unificación". Eso es todo? Si es así, eso significa que la parte interesante es el sistema de tipos en sí no es el sistema de inferencia de tipos.

IIRC, la parte interesante de la inferencia de tipos Damas-Milner Algoritmo W es que se infiere de los tipos más generales posible.