Hindley-Milner algorithme:à l'aide de types d'assurer les liaisons sont appliquées

Question

Je suis la mise en œuvre de la Hindley-Milner algorithme d'inférence de types, suivant les tutoriels de Mark Jones et Oleg Kiselyov.Ces deux ont un "appliquer les liaisons" l'opération avec un type à peu près de la forme

applyBindings :: TyEnv -> Type -> Type

laquelle s'applique l' tyvar -> ty fixations TyEnv à l' Type.J'ai trouvé une erreur commune que dans mon code pour oublier d'appeler applyBindings, et je pas obtenir l'aide de Haskell type de système, depuis ty a le même type que applyBindings tyenv ty.Je suis à la recherche d'une façon d'appliquer la suivante invariant dans le système de type:

quand on fait de l'inférence de type, les liaisons doivent être appliquées avant de retourner une "finale" résultat

Quand on fait de l'inférence de type pour un monomorphe langue d'objet, il est un moyen naturel pour appliquer cette, tel que mis en œuvre dans wren ng thornton unification-fd paquet:nous définissons deux types de données pour Types:

-- | Types not containing unification variables
type Type = ...          -- (Fix TypeF) in wren's package

-- | Types possibly containing unification variables
type MutType = ...       -- (MutTerm IntVar TypeF) in wren's package

et de donner applyBindings le type

-- | Apply all bindings, returning Nothing if there are still free variables
-- otherwise just
applyBindings :: TyEnv -> MutType -> Maybe Type

(cette fonction est en fait freeze . applyBindings dans l'unification-fd).Ceci impose notre invariante si nous oublions de applyBindings, puis nous aurons une erreur de type.

C'est le genre de solution que je recherche, mais pour les langages objets avec le polymorphisme.L'approche ci-dessus, tel qu'il est, ne s'applique pas, puisque notre objet-les types de langues peuvent avoir des variables de type -- en effet, si les variables libres après l'application de liaisons, nous ne voulons pas de retour Nothing, mais nous, nous voulons généraliser sur ces variables.

Est-il une solution le long des lignes que je décris, c'est à direcelui qui donne applyBindings un autre type de const id?Faire du vrai compilateurs utilisent la même beaucoup les jeux de mots (entre l'unification de variables et d'objets de type a de langue variables) qui Marque et Oleg tutoriels faire?

Answer 1

Je vais prendre un coup de poignard dans le noir, parce que je pense qu'il y a peut être d'autres problèmes avec la solution que vous proposez, mais je peux répondre à au moins une difficulté:

• Votre type de vérificateur doit avoir différentes des représentations l'unification des variables de type et objet-langue des variables de type.

Cette variation n'est pas difficile à mettre en œuvre, et en fait je pense que le GHC vérificateur de types travaillé de cette façon, au moins à un moment donné.Vous voudrez peut-être consulter le document Pratique de l'Inférence de Type pour Arbitraire Rang Types;l'annexe contient beaucoup de code utile.