Quelles sont les limites de l'inférence de type?

Question

Quelles sont les limites de l'inférence de type? Quels sont les systèmes de type ont aucun algorithme d'inférence générale?

Answer 1

Joe Wells a montré que l'inférence de type est indécidable pour système F, qui est la lambda-calcul polymorphe le plus élémentaire, indépendamment découvert par Girard et Reynolds. Ceci est le résultat le plus important montrant les limites de l'inférence de type.

Voici un problème important qui est encore ouvert: quelle est la meilleure façon d'intégrer Généralisée types de données en Algebraic inférence de type Hindley-Milner? Chaque année, Simon Peyton Jones arrive avec une nouvelle réponse, qui est censé être mieux que la réponse de l'année précédente. Je n'ai pas lu la version Mars 2009 et ne peut donc pas dire si je crois que ce sera définitif.

Answer 2

Un système de valeur de type dépendant (ou dans le système de type dépendant court,) peut décrire les types qui disent des choses comme: « Au moment de l'évaluation (d'exécution), la valeur de cette variable sera toujours égale à la valeur de cette variable , qui est calculée avec un procédé d'évaluation différent ». déduisant automatiquement ce type à partir du code implique des preuves automatiques de théorèmes. Si l'ensemble des théorèmes, vous pouvez exprimer est limitée à ceux automatiquement démontrable, qui ne serait pas un problème, mais dans le cas des langues dépendamment typées, ce qui est généralement le cas.

Dépendamment systèmes dactylographié ne peuvent pas avoir en général (et complet) inférence de type.

Je suis sûr que quelqu'un peut fournir une réponse formelle et complète morale ...