Les erreurs de débordement de pile se produisent-elles en Haskell ?

Question

En tant que langage de programmation fonctionnel pur, Haskell utilise intensivement la récursion. Les erreurs de débordement de pile se produisent-elles en Haskell, comme en Java ? Pourquoi, ou pourquoi pas ?

Answer 1

Haskell utilise la pile différemment de Java, par paresse.

En Java, un cadre de pile est créé lorsqu'une méthode est appelée, et libéré lorsque la méthode revient. Ainsi, si f() est une méthode récursive, chaque appel récursif à la méthode f() génère un cadre de pile, et ces cadres sont strictement imbriqués. Vous pouvez obtenir un débordement de pile lorsque vous avez une chaîne profonde d'appels récursifs, comme par exemple f() -> f() -> f() -> … .

Alors qu'en Haskell, un jeté est créé lorsqu'une fonction est appelée. Un cadre de pile est créé lorsqu'un thunk est forcé en utilisant la correspondance de motifs (par ex. case ), et libéré lorsque l'évaluation du thunk est suffisamment complète pour retourner une valeur (qui peut contenir d'autres thunks non évalués).

Donc si f est une fonction récursive, chaque appel à f génère un thunk, et case sur le résultat de cette opération génère une trame de pile, mais ces trames sont uniquement imbriqués lorsqu'il y a une dépendance entre les thunks. Et en fait, c'est ce que le seq primitif le fait : a `seq` b signifie "évaluer a avant b en retournant b ", mais vous pouvez aussi considérer que c'est l'ajout d'une dépendance de b sur a Ainsi, lorsque b est évaluée, a est également forcée.

Vous pouvez obtenir un débordement de pile lorsque vous avez une chaîne profonde de thunks à évaluer, par exemple dans l'outil excessivement paresseux foldl fonction :

foldl (+) 0 [1..5]
==
foldl (+) 0 (1 : 2 : 3 : 4 : 5 : [])
==
((((0 + 1) + 2) + 3) + 4) + 5

Cela génère une chaîne de thunks comme suit :

((+)
    ((+)
        ((+)
            ((+)
                ((+)
                    0
                    1)
                2)
            3)
        4)
    5)

Lorsque nous forçons le résultat (par exemple, en l'imprimant), nous devons descendre tout au long de cette chaîne afin de pouvoir commencer en l'évaluant, au (+) 0 1 jeté.

Alors foldl produit souvent des débordements de pile pour les entrées importantes, c'est pourquoi la plupart du temps, vous devriez utiliser foldl' (qui est strict) quand on veut un pliage associatif à gauche. Au lieu de construire une chaîne de thunks imbriqués, foldl' évalue les résultats intermédiaires immédiatement ( 0+1 = 1 , 1+2 = 3 , 3+3 = 6 , ).

Answer 2

Les débordements de pile ne se produiront pas en Haskell comme ils le feraient en Java, etc., car l'évaluation et les appels de fonction se déroulent différemment.

En Java, en C et dans d'autres langages similaires, les appels de fonction sont mis en œuvre à l'aide d'une pile d'appels. Lorsque vous appelez une fonction, toutes les variables locales de la fonction sont allouées sur une pile d'appels, et lorsque la fonction se termine, la fonction est retirée de la pile. Si les appels imbriqués sont trop nombreux, la pile d'appels débordera.

En Haskell, ce n'est pas forcément comme ça que les appels de fonction fonctionnent. Dans la plupart des compilateurs, comme GHC, les appels de fonction Haskell sont pas mis en œuvre à l'aide de piles d'appels. Ils sont mis en œuvre à l'aide d'un processus complètement différent, utilisant l'allocation de thunks sur le tas.

Ainsi, la plupart des implémentations haskell n'implémentent pas de pile d'appel pour les appels de fonction en premier lieu, donc l'idée d'un débordement de pile n'a pas de sens. Ce serait comme parler de baignoires qui débordent dans un vestiaire où il n'y a que des douches.

(GHC utilise une pile d'appel pour les évaluations de thunk, mais pas pour les appels de fonction. Ainsi, les débordements de pile qui peuvent se produire sont d'une nature complètement différente et sans rapport avec les débordements de pile de Java, C, etc).