Nous savons tous (ou devrions savoir) que Haskell est paresseux par défaut. Rien n'est évalué tant qu'il n'a pas été évalué. Alors, quand faut-il évaluer quelque chose? Il y a des points où Haskell doit être strict. J'appelle ces «points de rigueur», bien que ce terme particulier ne soit pas aussi répandu que je l'avais pensé. Selon moi:
La réduction (ou évaluation) dans Haskell ne se produit qu'aux points de rigueur.
La question est donc: quels sont précisément les points de rigueur de Haskell? Mon intuition dit que main
, seq
/ modèles bang, pattern matching, ainsi que toute IO
action effectuée par main
les points de strictness primaires, mais je ne sais pas vraiment pourquoi je sais.
( De plus, si elles ne sont pas ce qui appelle des « points », de strictness sont ils appelés?)
J'imagine qu'une bonne réponse inclura une discussion sur WHNF et ainsi de suite. J'imagine aussi que cela pourrait toucher le calcul lambda.
Edit: 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 des profondeurs variables (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 son contexte environnant est évalué ou réduit».
Alors, laissez-moi essayer de vous lancer sur le genre de réponse que je veux. 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
le contexte du programme) est évalué, le point de rigueur de main est activé. La profondeur de Main est maximale: elle doit être pleinement évaluée. Main est généralement composé d'actions IO, qui sont également des points de rigueur, dont le contexte est main
.
Maintenant, vous essayez: discuter seq
et faire correspondre les modèles en ces termes. Expliquez les nuances de l'application des fonctions: en quoi est-elle stricte? Comment n'est-ce pas? Et quoi deepseq
? let
et 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 seq seulement ou de correspondance de motifs?
la source
seq
la correspondance des motifs est suffisante, le reste étant défini en fonction de ces éléments. Je pense que la correspondance de motifs assure la rigueur desIO
actions, par exemple.+
les types numériques intégrés, forcent également la rigueur, et je suppose que la même chose s'applique aux appels FFI purs.Réponses:
Un bon point de départ est de comprendre cet article: A Natural Semantics for Lazy Evalution (Launchbury). Cela vous dira quand les expressions sont évaluées pour un petit langage similaire au Core de GHC. Ensuite, la question restante est de savoir comment mapper 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 "désucre", car il supprime le sucre syntaxique.
Eh bien, ce n'est pas toute l'histoire, car GHC comprend toute une série d'optimisations entre le désugarage et la génération de code, et beaucoup de ces transformations réorganiseront le Core afin que les choses soient évaluées à des moments différents (l'analyse de rigueur en particulier entraînera l'évaluation des choses plus tôt). Donc, pour vraiment comprendre comment votre programme sera évalué, vous devez vous pencher sur le Core produit par GHC.
Peut-être que cette réponse vous semble un peu abstraite (je n'ai pas mentionné spécifiquement les motifs de bang ou seq), mais vous avez demandé quelque chose de précis , et c'est à peu près le mieux que nous puissions faire.
la source
Je reformulerais probablement cette question comme suit : Dans quelles circonstances Haskell évaluera-t-il une expression? (Peut-être clouer sur une "forme normale de tête faible.")
Pour une première approximation, nous pouvons spécifier ceci comme suit:
À partir de votre liste intuitive, les actions principales et IO entrent dans la première catégorie, et la correspondance séquentielle et la correspondance de modèles entrent dans la deuxième catégorie. Mais je pense que la première catégorie correspond davantage à votre idée de "point de rigueur", car c'est en fait ainsi que nous faisons en sorte que l'évaluation dans Haskell devienne des effets observables pour les utilisateurs.
Donner tous les détails spécifiquement est une tâche importante, car Haskell est un langage de grande taille. C'est aussi assez subtil, car Concurrent Haskell peut évaluer les choses de manière spéculative, même si nous finissons par ne pas utiliser le résultat à la fin: c'est une troisième génération de choses qui provoquent l'évaluation. La deuxième catégorie est assez bien étudiée: vous voulez regarder la rigueur des fonctions impliquées. La première catégorie peut aussi être considérée comme une sorte de «rigueur», bien que ce soit un peu douteux car
evaluate x
et ceseq 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 (passer explicitement unRealWorld#
jeton 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.la source
C a le concept 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 peut-être point de force ) est plus conforme à la pensée de Haskell.
Donc, votre réflexion sur
!
/$!
etseq
est essentiellement juste, mais la correspondance de modèles est soumise à des règles plus subtiles. Vous pouvez toujours utiliser~
pour forcer la correspondance de modèle paresseux, bien sûr. Un point intéressant de ce même article:Continuons dans le terrier du lapin et regardons la documentation pour les optimisations effectuées par GHC:
En d'autres termes, un code strict peut être généré n'importe où en tant qu'optimisation, car la création de thunks est inutilement coûteuse lorsque les données seront toujours nécessaires (et / ou ne peuvent être utilisées qu'une seule fois).
(Un terme est en forme normale de tête s'il n'y a pas de beta-redex en position de tête 1. Un redex est un redex de tête s'il est précédé uniquement par des abstraits lambda de non-redexes 2. ) Donc, quand vous commencez à forcer un thunk, vous travaillez pour WHNF; quand il n'y a plus de thunks à forcer, vous êtes en forme normale. Autre point intéressant:
Ce qui implique naturellement que, en effet, toute l'
IO
action réalisée à partirmain
fait l' évaluation de la force, ce qui devrait être évident compte tenu que les programmes Haskell faire, en fait, faire des choses. Tout ce qui doit passer par la séquence définie dansmain
doit être dans une forme normale et est donc soumis à une évaluation stricte.Cependant, CA McCann a bien compris dans les commentaires: la seule chose qui a de la particularité
main
est qu'ellemain
est définie comme spéciale; la correspondance de motifs sur le constructeur est suffisante pour assurer la séquence imposée par laIO
monade. À cet égard uniquementseq
et le pattern-matching sont fondamentaux.la source
Show
instance de la valeur imprimée.Haskell n'est pas un langage paresseux purement AFAIK, 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 «paresseux» de haskell peut être trouvée 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.
Ma compréhension est que haskell tire les calculs à l'envers par rapport aux langages impératifs. Ce que cela signifie, c'est qu'en l'absence de schémas «seq» et bang, ce sera finalement une sorte d'effet secondaire qui force l'évaluation d'un thunk, ce qui peut à son tour provoquer des évaluations préalables (véritable paresse).
Comme cela conduirait à 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 ensuite prendre en charge 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 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 une ressource.
Quelques ressources supplémentaires:
http://www.haskell.org/haskellwiki/Performance/Laziness
http://www.haskell.org/haskellwiki/Haskell/Lazy_Evaluation
la source
Paresseux ne veut pas dire ne rien faire. Chaque fois que votre modèle de programme correspond à une
case
expression, il évalue quelque chose - juste assez de toute façon. Sinon, il ne peut pas déterminer quel RHS utiliser. Vous ne voyez aucune expression case dans votre code? Ne vous inquiétez pas, le compilateur traduit votre code en une forme simplifiée de Haskell où ils sont difficiles à éviter.Pour un débutant, une règle de base est qu'il
let
est paresseux,case
moins paresseux.la source
case
force toujours l'évaluation dans GHC Core, il ne le fait pas dans Haskell normal. Par exemple, essayezcase undefined of _ -> 42
.case
dans GHC Core évalue son argument à WHNF, tandis quecase
dans Haskell évalue son argument autant que nécessaire pour sélectionner la branche appropriée. Dans l'exemple de hammar, ce n'est pas du tout, mais danscase 1:undefined of x:y:z -> 42
, il évalue plus profondément que WHNF.case something of (y,x) -> (x,y)
ne doit pas évaluersomething
du tout. Cela est vrai pour tous les types de produits.something
devrait être évalué à WHNF pour atteindre le constructeur de tuple.Ce n'est pas une réponse complète visant le karma, mais juste une pièce du puzzle - dans la mesure où il s'agit de sémantique, gardez à l'esprit qu'il existe plusieurs stratégies d'évaluation qui fournissent la même sémantique. Un bon exemple ici - et le projet parle également de la façon dont nous pensons généralement à la sémantique Haskell - était le projet Eager Haskell, qui a radicalement modifié les stratégies d'évaluation tout en conservant la même sémantique: http://csg.csail.mit.edu/ pubs / haskell.html
la source
Le compilateur Glasgow Haskell traduit votre code en un langage de type Lambda-calcul appelé core . Dans ce langage, quelque chose va être évalué, chaque fois que vous le
case
modélisez par une déclaration-. Ainsi, si une fonction est appelée, le constructeur le plus extérieur et seulement lui (s'il n'y a pas de champs forcés) va être évalué. Tout le reste est mis en conserve dans un bruit sourd. (Les thunks sont introduits parlet
liaisons).Bien sûr, ce n'est pas exactement ce qui se passe dans la vraie langue. Le compilateur convertit Haskell en Core d'une manière très sophistiquée, rendant paresseux autant de choses que possible et tout ce qui est toujours nécessaire. En outre, il existe des valeurs non encadrées et des tuples toujours stricts.
Si vous essayez d'évaluer une fonction à la main, vous pouvez essentiellement penser:
la source