Est-ce que tout dans Haskell est stocké dans des thunks, même des valeurs simples?

Question

À quoi ressemblent les thunks pour la valeur / expression / fonction suivante dans le tas Haskell?

 val = 5                -- is `val` a pointer to a box containing 5?
add x y = x + y        
result = add 2 val     
main = print $ result
 

Ce serait bien d'avoir une image de la façon dont ceux-ci sont représentés dans Haskell, étant donné son mode d'évaluation paresseux.

Answer 1

Réponse officielle

Ce n'est pas de votre entreprise. Strictement détail de l'implémentation de votre compilateur.

Réponse courte

Oui.

Plus de réponse

Pour le Haskell programme lui-même, la réponse est toujours oui, mais le compilateur peut et va faire les choses différemment s'il trouve qu'il peut sortir avec elle, pour des raisons de performances.

Par exemple, pour "'add x y = x + y"', un compilateur peut générer du code qui fonctionne avec les thunks pour x et y et y construit un thunk comme un résultat. Mais considérez les points suivants:

foo :: Int -> Int -> Int
foo x y = x * x + y * y

Ici, une optimisation du compilateur génère un code qui prend d'abord en x et y de sortir de leurs boîtes, puis effectue tous les calculs arithmétiques, puis stocke le résultat dans une boîte.

Avancé répondre

Ce document décrit comment GHC est passé d'un mode de mise en œuvre de thunks à l'autre qui était en fait à la fois plus simple et plus rapide: http://research.microsoft.com/en-us/um/people/simonpj/papers/eval-apply/

Answer 2

En général, même des valeurs primitives en Haskell (par exemple de type Int et Float) sont représentés par des thunks. C'est d'ailleurs exigée par la non-sémantique stricte; considérer le fragment suivant:

bottom :: Int
bottom = div 1 0

Cette définition va générer un div par zéro exception seulement si la valeur de la partie inférieure est inspecté, mais pas si la valeur n'est jamais utilisé.

Considérons maintenant la fonction d'ajout:

add :: Int -> Int -> Int
add x y = x+y

Une implémentation naïve de ajouter devez forcer le thunk x, la force de la thunk pour y ajouter les valeurs et créer un (évalué) thunk pour le résultat. C'est une surcharge énorme pour l'arithmétique par rapport à la stricte langages fonctionnels (pour ne pas dire impératif ceux).

Cependant, un compilateur d'optimisation, tels que GHC peut surtout éviter cette surcharge de travail; c'est une vue simplifiée de la façon dont GHC se traduit par l'ajout d'une fonction:

add :: Int -> Int -> Int
add (I# x) (I# y) = case# (x +# y) of z -> I# z 

En interne, les types de base tels que Int est considéré comme le type de données avec un seul constructeur. Le type Int# est le "raw" type de machine pour les entiers et +# est la primitive de plus sur des types. Opérations sur des types sont mis en œuvre directement sur le bit-modèles (par exemple les registres) --- pas de thunks. Boxing et unboxing sont ensuite traduites en tant que constructeur d'application et le pattern matching.

L'avantage de cette approche (pas visible dans ce simple exemple), c'est que le compilateur est souvent capable de l'in-lining, ces définitions et en supprimant des intermédiaires boxing/unboxing opérations, ne laissant que la ultrapériphériques ceux.

Answer 3

Il serait tout à fait correcte pour envelopper chaque valeur dans un thunk. Mais depuis Haskell est non-stricte, les compilateurs peuvent choisir d'évaluer les thunks/expressions. En particulier, les compilateurs peuvent choisir d'évaluer une expression plus tôt que ce qui est strictement nécessaire, si elle aboutit à un meilleur code.

L'optimisation de Haskell compilateurs (GHC) effectuer la Rigueur de l'analyse de la figure, dont les valeurs seront toujours calculés.

Au début, le compilateur doit assumer, qu'aucun de fonction les arguments ne sont jamais utilisés. Puis il va sur le corps de la fonction et essaie de trouver des fonctions des applications qui 1) sont connus pour être stricte (au moins une partie de) leurs arguments et 2) doivent toujours être évalués afin de calculer le résultat de la fonction.

Dans votre exemple, nous avons la fonction (+) qui est strict dans ses deux arguments. Ainsi, le compilateur sait que les deux x et y , doivent toujours être évalués à ce stade. Maintenant, il se trouve que l'expression x+y est toujours nécessaire de calculer le résultat de la fonction, donc le compilateur peut stocker les informations que la fonction add est stricte dans les deux x et y.

Le code généré pour l' add* va donc s'attendre à des valeurs entières que les paramètres et pas thunks. L'algorithme devient beaucoup plus complexe lorsque la récursivité est impliqué (d'un point fixe de problème), mais l'idée de base reste la même.

Un autre exemple:

mkList x y = 
    if x then y : []
         else []

Cette fonction prendra x dans évalué forme (comme un booléen) et y comme un thunk. L'expression x doit être évalué dans chaque chemin d'exécution par le biais mkList, on peut donc demander à l'appelant de l'évaluer. L'expression y, d'autre part, n'est jamais utilisé dans n'importe quelle fonction de l'application qui est strict dans ses arguments. Le contre-la fonction : jamais regarde y il juste le stocke dans une liste. Ainsi, y doit être passé comme un thunk, afin de satisfaire les paresseux Haskell sémantique.

mkList False undefined -- absolutely legal

*: add est bien sûr polymorphes et le type exact de l' x et y dépend de l'instanciation.

Answer 4

Réponse courte: Oui.

Réponse longue:

val = 5

Ce doit être stockée dans un thunk, parce que, imaginez si nous avons écrit ce n'importe où dans notre code (comme, dans une bibliothèque, nous avons importé ou quelque chose):

val = undefined

Si cela doit être évaluée au moment de notre programme démarre, il se bloque, droit? Si nous utilisons en fait que la valeur de quelque chose, ce serait ce que nous voulons, mais si nous ne l'utilisons pas, il ne devrait pas être en mesure d'influencer notre programme afin de catastrophique.

Pour votre deuxième exemple, permettez-moi de changer un peu:

div x y = x / y

Cette valeur doit être stockée dans un thunk ainsi, parce que, imaginez un peu de code comme ceci:

average list =
  if null list
     then 0
     else div (sum list) (length list)

Si div a été strictes ici, il serait évaluée, même lorsque la liste est null (aka. vide), ce qui signifie que l'écriture de la fonction comme ceci ne marcherait pas, parce qu'il n'y aurait pas une chance de revenir 0 quand la liste est vide, même si c'est ce que nous voulons dans ce cas.

Votre dernier exemple est juste une variante de l'exemple 1, et il doit être paresseux pour les mêmes raisons.

Tout cela étant dit, il est possible de forcer le compilateur à faire certaines valeurs strictes, mais qui va au-delà de la portée de cette question.

Answer 5

Je pense que les autres ont répondu à votre question bien, mais juste pour être complet, l'amour de permettez-moi d'ajouter que GHC vous offre la possibilité d'utiliser des "unboxed" valeurs directement. C'est ce que Haskell Wiki dit à ce sujet:

Lorsque vous êtes vraiment désespéré pour la vitesse, et vous souhaitez obtenir le droit à la "raw bits." Veuillez voir GHC Primitives pour des informations sur l'utilisation de unboxed types.

Ce devrait être un dernier recours, cependant, depuis unboxed types et les primitives sont non-portable. Heureusement, il n'est généralement pas nécessaire de recourir à l'utilisation explicite unboxed et types primitifs, parce que GHC l'optimiseur peut faire le travail pour vous par l'in-lining, il sait à ce sujet, et unboxing stricte des arguments de la fonction. Stricte et décompressé constructeur de champs peut aussi aider beaucoup. Parfois GHC a besoin d'un peu d'aide pour générer le bon code, de sorte que vous pourriez avoir à regarder dans le Noyau de la sortie pour voir si vos réglages sont fait avoir l'effet désiré.

Une chose qui peut être dit pour l'utilisation de unboxed et types de primitives, c'est que vous savez que vous êtes en train de rédiger un code efficace, plutôt que de compter sur GHC l'optimiseur de faire la bonne chose, et être à la merci de changements dans GHC optimiseur du bas de la ligne. C'est peut-être important pour vous, dans ce cas aller pour elle.

Comme mentionné, il est non-portable, donc vous avez besoin d'un GHC extension du langage. Voir ici pour de leurs docs.