Quels sont les points de rigueur de Haskell ?

Question

Nous savons tous (ou devrions savoir) que Haskell est paresseux par défaut. Rien n'est évalué tant qu'il ne doit pas l'être. Mais quand doit-on évaluer quelque chose ? Il y a des moments où Haskell doit être strict. Je les appelle "points de rigueur", bien que ce terme particulier ne soit pas aussi répandu que je le pensais. Selon moi :

Réduction (ou évaluation) en Haskell seulement se produit aux points de rigueur.

La question est donc la suivante : quoi, précisément Quels sont les points de rigueur de Haskell ? Mon intuition me dit que main , seq / bang patterns, pattern matching, and any IO action réalisée par l'intermédiaire de main sont les principaux points de rigueur, mais je ne sais pas vraiment pourquoi je sais cela.

(Par ailleurs, s'ils ne s'appellent pas "points de rigueur", qu'est-ce que l'on entend par "points de rigueur" ? son ont-ils appelé ?)

J'imagine qu'une bonne réponse comprendra une discussion sur le WHNF, etc. J'imagine également qu'elle pourrait aborder le lambda calcul.

---

Édition : réflexions supplémentaires sur cette question.

En réfléchissant à cette question, je pense qu'il serait plus clair d'ajouter quelque chose à la définition d'un point de rigueur. Les points de rigueur peuvent avoir des contextes et en faisant varier profondeur (ou rigueur). Revenant à ma définition selon laquelle "la réduction en Haskell ne se produit qu'aux points de rigueur", ajoutons à cette définition cette clause : "un point de rigueur n'est déclenché que lorsque le contexte qui l'entoure est évalué ou réduit".

Permettez-moi donc d'essayer de vous donner le genre de réponse que je souhaite. main est un point de rigueur. Il est spécialement désigné comme le premier point de rigueur de son contexte : le programme. Lorsque le programme ( main ) est évalué, le point de rigueur de main est activé. La profondeur de main est maximale : elle doit être entièrement évaluée. Main est généralement composé d'actions IO, qui sont également des points de rigueur, dont le contexte est main .

Essayez maintenant : discutez seq et le filtrage dans ces termes. Expliquez les nuances de l'application des fonctions : comment est-elle stricte ? En quoi n'est-elle pas stricte ? Qu'en est-il de l'application d'une fonction ? deepseq ? let y case déclarations ? unsafePerformIO ? Debug.Trace ? Définitions de premier niveau ? Types de données stricts ? Modèles de Bang ? Etc. Combien de ces éléments peuvent être décrits en termes de séquences ou de modèles ?

Answer 1

Un bon point de départ est de comprendre ce document : Une sémantique naturelle pour l'évaluation paresseuse (Launchbury). Cela vous permettra de savoir quand les expressions sont évaluées pour un petit langage similaire au Core de GHC. La question restante est alors de savoir comment faire correspondre le langage Haskell complet à Core, et la plupart de cette traduction est donnée par le rapport Haskell lui-même. Dans GHC, nous appelons ce processus "desugaring", parce qu'il élimine le sucre syntaxique.

Ce n'est pas tout, car GHC inclut toute une série d'optimisations entre le désucrage et la génération de code, et beaucoup de ces transformations vont réorganiser le Core de façon à ce que les choses soient évaluées à des moments différents (l'analyse de la rigueur, en particulier, va faire en sorte que certaines choses soient évaluées plus tôt). Ainsi, pour vraiment comprendre comment votre sera évalué, il faut regarder le Core produit par GHC.

Cette réponse vous semble peut-être un peu abstraite (je n'ai pas mentionné spécifiquement les bang patterns ou les seq), mais vous avez demandé quelque chose précis et c'est à peu près le mieux que nous puissions faire.

Answer 2

Je reformulerais probablement cette question comme suit, Dans quelles circonstances Haskell évalue-t-il une expression ? (Peut-être ajouter "à la forme normale de la tête faible").

En première approximation, nous pouvons le spécifier comme suit :

• L'exécution des actions IO évalue toutes les expressions dont elle a besoin. (Vous devez donc savoir si l'action IO est exécutée, par exemple si son nom est main, ou si elle est appelée depuis main ET vous devez savoir ce dont l'action a besoin).
• Une expression en cours d'évaluation (hé, c'est une définition récursive !) évaluera toutes les expressions dont elle a besoin.

D'après votre liste intuitive, les actions principales et les actions IO entrent dans la première catégorie, et les séquences et la recherche de motifs dans la deuxième catégorie. Mais je pense que la première catégorie est plus conforme à votre idée de "point de rigueur", parce que c'est en fait la façon dont nous faisons en sorte que l'évaluation en Haskell devienne observable les effets pour les utilisateurs.

Donner tous les détails spécifiques est une tâche importante, car Haskell est un grand langage. C'est également assez subtil, car Concurrent Haskell peut évaluer des choses de manière spéculative, même si nous finissons par ne pas utiliser le résultat à la fin : il s'agit d'une troisième catégorie de choses qui provoquent l'évaluation. La deuxième catégorie est assez bien étudiée : vous voulez regarder le programme rigueur des fonctions concernées. La première catégorie peut également être considérée comme une sorte de "rigueur", bien que cela soit un peu douteux parce que evaluate x y seq x $ return () sont en fait des choses différentes ! Vous pouvez le traiter correctement si vous donnez une sorte de sémantique à la monade IO (en passant explicitement un RealWorld# fonctionne pour les cas simples), mais je ne sais pas s'il existe un nom pour ce type d'analyse de rigueur stratifiée en général.

Answer 3

C a la notion de points de séquence qui sont des garanties pour des opérations particulières qu'un opérande sera évalué avant l'autre. Je pense que c'est le concept existant le plus proche, mais le terme essentiellement équivalent point de rigueur (ou éventuellement point de force ) est plus conforme à la pensée Haskell.

En pratique, Haskell n'est pas un langage purement paresseux : par exemple, la recherche de motifs est généralement stricte (essayer une recherche de motifs force l'évaluation à aller au moins assez loin pour accepter ou rejeter la recherche).

Les programmeurs peuvent également utiliser la fonction seq pour forcer l'évaluation d'une expression, que le résultat soit ou non utilisé.

$! est défini en termes de seq .

_- Paresseux ou non ._

Vous pensez donc à ! / $! y seq est essentiellement correcte, mais la recherche de motifs est soumise à des règles plus subtiles. Vous pouvez toujours utiliser ~ pour forcer le filtrage paresseux, bien sûr. Un point intéressant de ce même article :

L'analyseur de rigueur recherche également les cas où les sous-expressions sont toujours requises par l'expression extérieure et les convertit en évaluation anticipée. Il peut le faire parce que la sémantique (en termes de "bas") ne change pas.

Continuons à descendre dans le trou du lapin et regardons la documentation sur les optimisations effectuées par GHC :

L'analyse de rigueur est un processus par lequel GHC tente de déterminer, à la compilation, quelles sont les données qui seront "toujours nécessaires". GHC peut alors construire du code pour calculer simplement ces données, plutôt que le processus normal (plus coûteux) de stockage du calcul et de son exécution ultérieure.

_- Optimisations GHC : Analyse de la rigueur ._

En d'autres termes, un code strict peut être généré n'importe où à titre d'optimisation, car la création de thunks est inutilement coûteuse lorsque les données seront toujours nécessaires (et/ou ne seront peut-être utilisées qu'une seule fois).

aucune autre évaluation ne peut être effectuée sur la valeur ; elle est considérée comme étant en forme normale . Si nous nous trouvons à l'une des étapes intermédiaires, c'est-à-dire si nous avons effectué au moins une certaine évaluation sur une valeur, celle-ci se trouve dans la catégorie forme normale de la tête faible (WHNF). (Il existe également une "forme normale en tête", mais elle n'est pas utilisée en Haskell.) L'évaluation complète d'une chose en WHNF la réduit à une chose en forme normale

- Wikibooks Haskell : La paresse

(Un terme est en forme normale de tête s'il n'y a pas de bêta-redex en position de tête 1 . Une redx est une redx de tête si elle est précédée uniquement d'abstracteurs de lambda de non-rédex 2 .) Ainsi, lorsque vous commencez à forcer un thunk, vous travaillez en WHNF ; lorsqu'il n'y a plus de thunks à forcer, vous êtes en forme normale. Autre point intéressant :

si, à un moment donné, nous devions, disons, imprimer z pour l'utilisateur, nous aurions besoin de l'évaluer complètement

Ce qui implique naturellement qu'en effet, tout IO action réalisée à partir de main fait forcent l'évaluation, ce qui devrait être évident si l'on considère que les programmes Haskell font, en fait, des choses. Tout ce qui doit passer par la séquence définie dans main doit être de forme normale et est donc soumis à une évaluation stricte.

C. A. McCann a raison dans les commentaires : la seule chose qui est spéciale à propos de la main est que main est définie comme spéciale ; la recherche de motifs sur le constructeur est suffisante pour assurer la séquence imposée par la directive IO monade. À cet égard, seule la seq et la recherche de motifs sont fondamentales.

Answer 4

Haskell n'est AFAIK pas un langage purement paresseux, mais plutôt un langage non strict. Cela signifie qu'il n'évalue pas nécessairement les termes au dernier moment possible.

Une bonne source pour le modèle de "paresse" d'Haskell se trouve ici : http://en.wikibooks.org/wiki/Haskell/Laziness

Fondamentalement, il est important de comprendre la différence entre un thunk et la forme normale d'en-tête faible WHNF.

Si j'ai bien compris, haskell effectue les calculs à l'envers par rapport aux langages impératifs. Cela signifie qu'en l'absence de "seq" et de "bang patterns", ce sera finalement une sorte d'effet secondaire qui forcera l'évaluation d'un "thunk", ce qui peut provoquer des évaluations préalables à son tour (véritable paresse).

Comme cela entraînerait une horrible fuite d'espace, le compilateur détermine alors comment et quand évaluer les thunks à l'avance pour économiser de l'espace. Le programmeur peut alors soutenir ce processus en donnant des annotations de rigueur (en.wikibooks.org/wiki/Haskell/Strictness , www.haskell.org/haskellwiki/Performance/Strictness) pour réduire davantage l'utilisation de l'espace sous la forme de thunks imbriqués.

Je ne suis pas un expert de la sémantique opérationnelle de haskell, je vais donc laisser le lien comme ressource.

Quelques ressources supplémentaires :

http://www.haskell.org/haskellwiki/Performance/Laziness

http://www.haskell.org/haskellwiki/Haskell/Lazy_Evaluation

Answer 5

Paresseux ne veut pas dire ne rien faire. Chaque fois que le motif de votre programme correspond à un case il évalue quelque chose - juste assez en tout cas. Sinon, il ne peut pas savoir quel RHS utiliser. Vous ne voyez pas d'expressions de cas dans votre code ? Ne vous inquiétez pas, le compilateur traduit votre code dans une forme simplifiée de Haskell où il est difficile de ne pas les utiliser.

Pour un débutant, la règle de base est la suivante let est paresseux, case est moins paresseux.