Fundeps et GADT :Quand la vérification de type est-elle décidable ?

Question

Je lisais un document de recherche sur Haskell et comment HList est implémenté et je me demandais quand les techniques décrites sont ou non décidables pour le vérificateur de type.De plus, comme vous pouvez faire des choses similaires avec les GADT, je me demandais si la vérification du type GADT était toujours décidable.

Je préférerais les citations si vous en avez pour pouvoir lire/comprendre les explications.

Merci!

Answer 1

Je crois que la vérification de type GADT est toujours décidable ;c'est une inférence qui est indécidable, car elle nécessite une unification d'ordre supérieur.Mais un vérificateur de type GADT est une forme restreinte des vérificateurs de preuves que vous voyez par exemple.Coq, où les constructeurs construisent le terme de preuve.Par exemple, l'exemple classique d'intégration du calcul lambda dans les GADT a un constructeur pour chaque règle de réduction, donc si vous voulez trouver la forme normale d'un terme, vous devez lui indiquer quels constructeurs vous y amèneront.Le problème d'arrêt a été transféré entre les mains de l'utilisateur :-)

Answer 2

Vous l'avez probablement déjà vu, mais il existe une collection d'articles sur cette question dans Microsoft Research : Type Vérification des papiers.Le premier décrit l’algorithme décidable actuellement utilisé dans le compilateur Glasgow Haskell.