Haskell a-t-il une optimisation récursive de la queue?

J'ai découvert la commande "time" sous Unix aujourd'hui et j'ai pensé l'utiliser pour vérifier la différence de temps d'exécution entre les fonctions récursives de queue et récursives normales dans Haskell.

J'ai écrit les fonctions suivantes:

--tail recursive
fac :: (Integral a) => a -> a
fac x = fac' x 1 where
    fac' 1 y = y
    fac' x y = fac' (x-1) (x*y) 

--normal recursive
facSlow :: (Integral a) => a -> a
facSlow 1 = 1
facSlow x = x * facSlow (x-1)

Ceux-ci sont valides en gardant à l'esprit qu'ils étaient uniquement à utiliser avec ce projet, donc je n'ai pas pris la peine de vérifier les zéros ou les nombres négatifs.

Cependant, en écrivant une méthode principale pour chacun, en les compilant et en les exécutant avec la commande "time", les deux avaient des temps d'exécution similaires avec la fonction récursive normale bordant la dernière récursive. Ceci est contraire à ce que j'avais entendu en ce qui concerne l'optimisation récursive de queue dans lisp. Quelle en est la raison?

Haskell utilise l'évaluation paresseuse pour implémenter la récursivité, donc traite tout comme une promesse de fournir une valeur en cas de besoin (c'est ce qu'on appelle un thunk). Les thunks ne sont réduits que dans la mesure nécessaire pour continuer, pas plus. Cela ressemble à la façon dont vous simplifiez mathématiquement une expression, il est donc utile de la penser de cette façon. Le fait que l'ordre d'évaluation ne soit pas spécifié par votre code permet au compilateur de faire beaucoup d'optimisations encore plus intelligentes que la simple élimination des appels de fin à laquelle vous êtes habitué. Compilez avec -O2si vous voulez une optimisation!

Voyons comment nous évaluons en facSlow 5tant qu'étude de cas:

facSlow 5
5 * facSlow 4            -- Note that the `5-1` only got evaluated to 4
5 * (4 * facSlow 3)       -- because it has to be checked against 1 to see
5 * (4 * (3 * facSlow 2))  -- which definition of `facSlow` to apply.
5 * (4 * (3 * (2 * facSlow 1)))
5 * (4 * (3 * (2 * 1)))
5 * (4 * (3 * 2))
5 * (4 * 6)
5 * 24
120

Donc, tout comme vous vous inquiétez, nous avons une accumulation de nombres avant que les calculs ne se produisent, mais contrairement à ce que vous craigniez, il n'y a pas de pile d' facSlowappels de fonction qui attendent de se terminer - chaque réduction est appliquée et disparaît, laissant un cadre de pile dans son wake (c'est parce qu'il (*)est strict et déclenche ainsi l'évaluation de son deuxième argument).

Les fonctions récursives de Haskell ne sont pas évaluées de manière très récursive! La seule pile d'appels qui traîne sont les multiplications elles-mêmes. Si (*)est considéré comme un constructeur de données strict, c'est ce que l'on appelle la récursivité protégée (bien qu'elle soit généralement appelée comme telle avec les constructeurs de données non restreints, où ce qui reste dans son sillage sont les constructeurs de données - lorsqu'ils sont forcés par un accès supplémentaire).

Regardons maintenant la queue-récursive fac 5:

fac 5
fac' 5 1
fac' 4 {5*1}       -- Note that the `5-1` only got evaluated to 4
fac' 3 {4*{5*1}}    -- because it has to be checked against 1 to see
fac' 2 {3*{4*{5*1}}} -- which definition of `fac'` to apply.
fac' 1 {2*{3*{4*{5*1}}}}
{2*{3*{4*{5*1}}}}        -- the thunk "{...}" 
(2*{3*{4*{5*1}}})        -- is retraced 
(2*(3*{4*{5*1}}))        -- to create
(2*(3*(4*{5*1})))        -- the computation
(2*(3*(4*(5*1))))        -- on the stack
(2*(3*(4*5)))
(2*(3*20))
(2*60)
120

Vous pouvez donc voir comment la récursivité de queue en elle-même ne vous a pas fait gagner du temps ni de l'espace. Non seulement cela prend plus de pas dans l'ensemble facSlow 5, mais il construit également un thunk imbriqué (montré ici comme {...}) - nécessitant un espace supplémentaire pour cela - qui décrit le calcul futur, les multiplications imbriquées à effectuer.

Cette thunk est ensuite démêlé en traversant ce vers le bas, de recréer le calcul sur la pile. Il y a aussi ici un risque de provoquer un débordement de pile avec des calculs très longs, pour les deux versions.

Si nous voulons optimiser cela manuellement, tout ce que nous devons faire est de le rendre strict. Vous pouvez utiliser l'opérateur d'application strict $!pour définir

facSlim :: (Integral a) => a -> a
facSlim x = facS' x 1 where
    facS' 1 y = y
    facS' x y = facS' (x-1) $! (x*y) 

Cela oblige facS'à être strict dans son deuxième argument. (C'est déjà strict dans son premier argument car cela doit être évalué pour décider quelle définition de facS'appliquer.)

Parfois, la rigueur peut aider énormément, parfois c'est une grosse erreur car la paresse est plus efficace. Ici c'est une bonne idée:

facSlim 5
facS' 5 1
facS' 4 5 
facS' 3 20
facS' 2 60
facS' 1 120
120

C'est ce que vous vouliez réaliser je pense.

Résumé

• Si vous souhaitez optimiser votre code, la première étape consiste à compiler avec -O2
• La récursivité de queue n'est bonne que lorsqu'il n'y a pas d'accumulation de thunk, et l'ajout de rigueur aide généralement à l'empêcher, si et où cela est approprié. Cela se produit lorsque vous créez un résultat qui sera nécessaire plus tard en une seule fois.
• Parfois, la récursivité de queue est un mauvais plan et la récursivité protégée est un meilleur ajustement, c'est-à-dire quand le résultat que vous construisez sera nécessaire petit à petit, par portions. Consultez cette question sur foldret foldlpar exemple, et testez-les les uns par rapport aux autres.

Essayez ces deux:

length $ foldl1 (++) $ replicate 1000 
    "The size of intermediate expressions is more important than tail recursion."
length $ foldr1 (++) $ replicate 1000 
    "The number of reductions performed is more important than tail recursion!!!"

foldl1est récursif en queue, alors qu'il foldr1effectue une récursivité protégée de sorte que le premier élément soit immédiatement présenté pour un traitement / accès ultérieur. _{(Le premier "met entre parenthèses" à gauche à la fois, (...((s+s)+s)+...)+sforçant sa liste d'entrée complètement à sa fin et créant un gros bruit de calcul futur beaucoup plus tôt que ses résultats complets ne sont nécessaires; le second entre parenthèses vers la droite progressivement s+(s+(...+(s+s)...)), consommant l'entrée listez petit à petit, donc le tout est capable de fonctionner dans un espace constant, avec des optimisations).}

Vous devrez peut-être ajuster le nombre de zéros en fonction du matériel que vous utilisez.

Il convient de mentionner que la facfonction n'est pas un bon candidat pour la récursivité protégée. La récursivité de la queue est la voie à suivre ici. En raison de la paresse, vous n'obtenez pas l'effet du TCO dans votre fac'fonction car les arguments de l'accumulateur continuent de créer de gros thunks, qui, lorsqu'ils sont évalués, nécessiteront une énorme pile. Pour éviter cela et obtenir l'effet désiré du TCO, vous devez rendre ces arguments d'accumulateur stricts.

{-# LANGUAGE BangPatterns #-}

fac :: (Integral a) => a -> a
fac x = fac' x 1 where
  fac' 1  y = y
  fac' x !y = fac' (x-1) (x*y)

Si vous compilez en utilisant -O2(ou juste -O) GHC le fera probablement seul dans le phase d' analyse de rigueur .

Vous devriez consulter l'article du wiki sur la récursion des queues dans Haskell . En particulier, en raison de l'évaluation des expressions, le type de récursivité que vous souhaitez est la récursivité protégée . Si vous travaillez sur les détails de ce qui se passe sous le capot (dans la machine abstraite pour Haskell), vous obtenez le même genre de chose qu'avec la récursivité de queue dans des langages stricts. Parallèlement à cela, vous avez une syntaxe uniforme pour les fonctions paresseuses (la récursivité de queue vous liera à une évaluation stricte, alors que la récursivité surveillée fonctionne plus naturellement).

(Et en apprenant Haskell, le reste de ces pages wiki est également génial!)

Si je me souviens bien, GHC optimise automatiquement les fonctions récursives simples en fonctions optimisées récursives de queue.