Je travaille sur un langage d'expression de la généalogie ML, il a donc naturellement besoin d'une inférence de type> :)
Maintenant, j'essaie d'étendre une solution basée sur des contraintes au problème de l'inférence des types, basée sur une implémentation simple en EOPL (Friedman et Wand), mais ils décalent élégamment les types de données algébriques.
Ce que j'ai jusqu'à présent fonctionne bien; si une expression eest a + b, e : Int, a : Intet b : Int. Si ec'est un match,
match n with
| 0 -> 1
| n' -> n' * fac(n - 1)`,
Je peux à juste titre déduire que t(e) = t(the whole match expression), t(n) = t(0) = t(n'), t(match) = t(1) = t(n' * fac(n - 1)et ainsi de suite ...
Mais je ne suis pas très sûr en ce qui concerne les types de données algébriques. Supposons une fonction comme un filtre:
let filter pred list =
match list with
| Empty -> Empty
| Cons(e, ls') when pred e -> Cons (e, filter ls')
| Cons(_, ls') -> filter
Pour que le type de liste reste polymorphe, Cons doit être de type a * a list -> a list. Donc, en établissant ces contraintes, j'ai évidemment besoin de rechercher ces types de mes constructeurs algébriques - le problème que j'ai maintenant est la `` sensibilité au contexte '' des utilisations multiples des constructeurs algébriques - comment puis-je exprimer dans mes équations de contraintes que le adans chaque cas doit être le même?
J'ai du mal à trouver une solution générale à ce problème et je ne trouve pas beaucoup de documentation à ce sujet. Chaque fois que je trouve quelque chose de similaire - un langage basé sur l'expression avec une inférence de type basée sur des contraintes - ils s'arrêtent juste avant les types de données algébriques et le polymorphisme.
Toute contribution est très appréciée!
Réponses:
Voir: Mini ML spécifiquement la section d'inférence de type.
Il contient un exemple de code en F # pour un analyseur complet d'un langage fonctionnel simple. Plus important encore, la section Inférence de type implémente l'algorithme Hindley-Milner, qui se trouve dans la plupart des systèmes d'inférence de type. L'auteur fournit également des liens vers deux autres documents importants pour aider à comprendre Hindley-Milner; l'un étant une sorte d'introduction de haut niveau et l'autre étant un document qui décrit la mise en œuvre de l'algorithme dans le code.
la source