Accumulateurs à haskell

En Haskell, si j'écrisAccumulateurs à haskell

fac n = facRec n 1 
    where facRec 0 acc = acc 
     facRec n acc = facRec (n-1) (acc*n)

et compilez avec GHC, le résultat sera différent que si je

fac 0 = 1 
fac n = n * fac (n-1)

Je pourrais facilement faire fac n = product [1..n] et d'éviter la tout, mais je suis intéressé par la façon dont une tentative de récursion de la queue fonctionne dans un langage paresseux. Je comprends que je peux toujours avoir un débordement de pile parce que les thunks se construisent, mais est-ce que quelque chose se passe réellement différemment (en termes de programme compilé) quand j'utilise un accumulateur que lorsque je récapitule simplement la récursivité naïve? Y a-t-il un avantage à omettre la récursivité de la queue autre qu'une amélioration de la lisibilité? Est-ce que la réponse change du tout si j'utilise runhaskell pour exécuter le calcul au lieu de le compiler en premier?

Source

2010-11-26 Inaimathi

Quelle est votre définition de «est-ce que quelque chose se passe réellement différemment»? La réponse triviale est "oui", parce qu'ils sont différents - l'un est récursif et l'autre non. Mais je ne pense pas que c'est ce que vous demandez ..? – lijie

n'entendez-vous pas facRec n acc = facRec (n-1) (acc * n) ???? –

@lijie - Je m'intéresse principalement à savoir si GHC fait l'optimisation des appels de queue (avec ou sans accumulateur), mais je l'ai laissé général parce que je ne sais pas vraiment comment la récursivité de queue interagit avec les langages paresseux. choses basées sur mon utilisation d'une forme par rapport à une autre. Je ne sais pas ce que sont ces autres choses. – Inaimathi

récursion Tail ne sens make dans (GHC) Haskell si votre accumulateur est stricte. Pour illustrer le problème, voici une « trace » de votre récursive définition fac:

fac 4 
~> facRec 4 1 
~> facRec 3 (1*4) 
~> facRec 2 ((1*4)*3) 
~> facRec 1 (((1*4)*3)*2) 
~> facRec 0 ((((1*4)*3)*2)*1) 
~> (((1*4)*3)*2) * 1 
    ~> ((1*4)*3) * 2 
    ~> (1*4) * 3 
     ~> 1*4 
    ~> 4 * 3 
    ~> 12 * 2 
~> 24 * 1 
~> 24

Les correspond au niveau d'indentation (environ) au niveau de la pile. Notez que l'accumulateur n'est évalué qu'à la toute fin, ce qui peut provoquer un débordement de pile. L'astuce, bien sûr, est de rendre l'accumulateur strict. Il est théoriquement possible de montrer que facRec est strict s'il est appelé dans un contexte strict, mais je ne suis au courant d'aucun compilateur qui le fasse, ATM. GHC fait faire l'optimisation d'appel de queue, si bien que les appels facRec utilisent l'espace de pile constant.

Pour la même raison foldl' est généralement préféré à foldl, car le premier est strict dans l'accumulateur. En ce qui concerne votre deuxième partie, runhaskell/runghc est juste une enveloppe sur GHCi. Si GHCi trouve du code compilé, il l'utilisera, sinon il utilisera l'interpréteur bytecode qui effectue peu d'optimisations, donc ne vous attendez pas à des optimisations fantaisistes.

Source

2010-11-26 14:54:37 nominolo

L'indice 'foldl 'vs' fold' m'a aidé, je pense; http://www.haskell.org/haskellwiki/Foldr_Foldl_Foldl%27. En d'autres termes, si je voulais une récursion en queue dans le sens où je suis habitué à Scheme, je devrais dire quelque chose comme 'let acc '= acc * n dans seq acc' $ facRec (n-1) acc'' au lieu de 'facRec (n-1) (acc * n)' sur la dernière ligne de 'facRec'. – Inaimathi

@Inaimathi: Oui; ou, plus simplement, vous pouvez écrire 'fracRec (n-1) $! acc * n', où '$!' est juste une application de fonction stricte ('f $! x = x \' seq \ 'f x'). –

La manière la plus simple d'ajouter la rigueur est d'utiliser '{- # LANGUAGE BangPatterns # -}'. Ensuite, vous avez des correspondances strictes. Par exemple, 'let! X = ... in ...' ou directement dans la définition de la fonction: 'facRec 0! N = ...' – nominolo

Votre question n'est pas complète. Je suppose que vous voulez dire GHC, et au moins sans optimisations la réponse est "oui" parce que la fonction de travail (facRec dans le premier ou fac dans le second) a une arité 2 par rapport à un et l'assemblée le reflétera. Avec des optimisations ou avec JHC la réponse est probablement "non".

Source

2010-11-26 03:54:26

Désolé, oui, je parle du GHC; modifié la question. – Inaimathi

En haskell, il est utile d'écrire votre programme de manière récursive si votre accumulateur est strict et que vous avez besoin d'un résultat complet. Avec runHaskell de ghc, le programme ne sera pas optimisé, donc il n'y aura pas d'analyse de rigueur, donc vous pouvez empiler des débordements; tandis que si vous compilez avec des optimisations, le compilateur peut détecter que l'accumulateur doit être strict et optimiser en conséquence.

Pour voir comment les choses se passent différemment (ou non), le meilleur moyen est d'inspecter le langage de base généré, a good blog post from Don Stewart explains things. Beaucoup de ses articles de blog sont intéressants si vous êtes intéressé par la performance, d'ailleurs.

Source

2010-11-26 10:55:08

Je vais ... devoir le mettre en signet. +1 – Inaimathi

De même, facRec devrait probablement être dans une clause where plutôt que dans une déclaration de niveau supérieur. Ceci est une transformation worker-wrapper et il est plus susceptible d'être remarqué par l'analyseur de rigueur. –

@stephen - fixé dans la question. – Inaimathi

Répondre

Questions connexes