34 votes

Que manque-t-il à Haskell pour la vérification de la totalité?

Total (fonctionnelle) de la langue est celui dans lequel tout peut être montré à la fin. De toute évidence, il ya beaucoup d'endroits où je ne veux pas ce lancer des exceptions est parfois à portée de main, un serveur web n'est pas censé pour terminer, etc. Mais parfois, j'aimerais un local totalité cochez la case pour activer certaines optimisations. Par exemple, si j'ai un prouvable-total fonction

commutativity :: forall (n :: Nat) (m :: Nat). n + m :~: m + n
commutativity = ...

ensuite, depuis :~: a exactement un habitant (Refl), GHC pourrait optimiser

gcastWith (commutativity @n @m) someExpression
  ==>
someExpression

Et ma preuve de commutativité va avoir un O(n) d'exécution coût pour être libre. Alors, maintenant, pour ma question:

Quelles sont les difficultés subtiles dans la réalisation d'un ensemble checker pour Haskell?

Bien évidemment, une telle checker est conservateur et donc à chaque fois GHC n'est pas sûr que quelque chose est totale (ou la flemme de vérifier). on pourrait supposer qu'il ne l'est pas... me Semble qu'il pourrait ne pas être trop difficile de bricoler un pas intelligents vérificateur qui serait encore être très utile (au moins il devrait être très simple pour éliminer tous mes arithmétique des épreuves). Pourtant, je n'arrive pas à trouver tous les efforts pour construire une telle chose dans GHC, donc évidemment, je suis en manque de quelques très grandes contraintes. Allez-y ALORS, écraser mes rêves. :)


Pertinent, mais pas récente: sans faille Haskell par Neil Mitchell, 2005.

18voto

Christopher Done Points 2699

Liquide Haskell a la totalité de la vérification: https://github.com/ucsd-progsys/liquidhaskell#termination-check

Screenshot from homepage

Par défaut, un contrôle de l'arrêt est effectué sur l'ensemble des fonctions récursives.

Utiliser le pas-de résiliation de l'option pour désactiver la case à

liquide --no-résiliation de test.hs

Dans les fonctions récursives la première algébrique ou argument entier devrait être à la baisse.

La valeur par défaut de mesure décroissante pour les listes de la longueur et les Entiers de sa valeur.

(J'ai inclus capture d'écran et devis pour la postérité.)

Semblables à Agda ou d'autres langues, avec la totalité de la vérification, les arguments de la fonction doit devenir structurellement plus petit plus de temps pour atteindre la base de cas. Combiné avec un ensemble de vérificateur, ce qui rend pour un contrôle fiable pour un certain nombre de fonctions. LH prend également en charge d'aider le vérificateur de long en indiquant comment les choses baisse, ce qui peut se faire avec un type abstrait de données qui est opaque ou d'une institution financière étrangère. C'est vraiment très pratique.

Prograide.com

Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.

Powered by:

X