Décrire l'inférence de type-Milner damas de manière qu'un étudiant peut comprendre CS101

Question

Hindley-Milner est un système de type qui est à la base des systèmes de type de nombreux langages de programmation fonctionnels bien connus. Damas-Milner est un algorithme qui infère (?) Types déduit dans un système de type Hindley-Milner.

Wikipédia donne une description de l'algorithme qui, ce que je peux dire, revient à un seul mot: « unification ». Est-ce tout ce qu'il ya à elle? Si oui, cela signifie que la partie intéressante est le système de type lui-même pas le système d'inférence de type.

Si Milner est-damas plus que l'unification, je voudrais une description de Damas-Milner qui comprend un exemple simple et, idéalement, un code.

En outre, cet algorithme est dit souvent faire l'inférence de type. Est-il vraiment un système d'inférence? Je pensais que ce n'était déduisant les types.

Questions connexes:

• Qu'est-ce que Hindley Miller?
• à problème unification

Answer 1

Milner est juste damas une utilisation structurée de l'unification.

Quand il récursif dans une expression lambda, il fait un nouveau nom de variable. Lorsque vous, dans un sous-terme, trouver cette variable utilisée d'une manière qui nécessiterait un type donné, il enregistre l'unification de cette variable et ce type. Si elle essaie toujours d'unifier deux types qui ne font pas de sens, comme dire qu'une variable individuelle est à la fois un Int et une fonction d'un -.> B, il hurle à vous pour faire quelque chose de mauvais

  

En outre, cet algorithme est dit souvent faire l'inférence de type. Est-il vraiment un système d'inférence? Je pensais que ce n'était déduisant les types.

Déduire les types est inférence de type. Vérification de voir que les annotations de type sont valables pour une période donnée est le type de vérification. Ils sont différents problèmes.

  

Si oui, cela signifie que la partie intéressante est le système de type lui-même pas le système d'inférence de type.

On dit communément que les systèmes de type de style Hindley-Milner sont en équilibre sur un point de rebroussement. Si vous ajoutez beaucoup plus de fonctionnalités, il devient impossible de déduire les types. Ainsi, les extensions de type de système que vous pouvez couche au-dessus d'un système de type de style Hindley-Milner sans détruire ses propriétés d'inférence sont vraiment les parties intéressantes de langues modernes et fonctionnelles. Dans certains cas, nous l'inférence de type mélangeons et la vérification de type, par exemple dans Haskell beaucoup d'extensions modernes ne peut pas être déduit, mais peut être vérifié, ils ont donc besoin d'annotations de type pour les fonctions avancées, comme la récursivité polymorphes.

Answer 2

  

Wikipedia donne une description de l'algorithme qui, pour autant que je peux dire, revient à un seul mot: « unification ». Est-ce tout ce qu'il ya à elle? Si oui, cela signifie que la partie intéressante est le système de type lui-même pas le système d'inférence de type.

IIRC, la partie intéressante de l'inférence de type-Milner algorithme damas W est qu'il infère les types les plus généraux possible.