haskell - significado - stack overflow error que significa

¿Por qué s++ t no conduce a un desbordamiento de pila para s grandes?

Question

Me pregunto porque

Prelude> head $ reverse $ [1..10000000] ++ [99]
99

no conduce a un error de desbordamiento de pila. El ++ en el preludio parece directo y no recursivo de cola:

(++) :: [a] -> [a] -> [a]
(++) []     ys = ys
(++) (x:xs) ys = x : xs ++ ys

EDITAR: Inicialmente, pensé que el problema tiene algo que ver con la forma en que se define ++ en el preludio, especialmente con las reglas de reescritura, por lo que la pregunta continúa como se muestra a continuación. La discusión me mostró que este no es el caso. Ahora creo que un efecto de evaluación perezoso hace que el código se ejecute sin un desbordamiento de pila, pero no entiendo cómo.

Así que solo con esto, debería ejecutarse en un desbordamiento de pila, ¿verdad? Así que me imagino que probablemente tenga algo que ver con la magia ghc que sigue la definición de ++:

{- # REGLAS "++" [~ 1] para todas las xs ys. xs ++ ys = augment (/ cn -> foldr cn xs) ys # -}

* ¿Es eso lo que ayuda a evitar el desbordamiento de pila? ¿Alguien podría dar una pista sobre lo que está pasando en este fragmento de código? **

Answer 1

El ++ en el preludio parece directo y no recursivo de cola ... Así que solo con esto, debería funcionar en un desbordamiento de pila, ¿verdad?

La cola no recursiva suele ser mejor que la cola recursiva en Haskell, porque las cosas no recursivas cola pueden ser perezosas. La definición que incluye allí es mucho mejor que una cola recursiva, porque una cola recursiva seguiría siendo recurrente y generaría la lista completa, incluso si solo necesita el primer elemento; mientras que una recursiva sin cola haría solo el trabajo que fuera necesario.

Answer 2

Esto no desborda la pila, incluso en el intérprete, donde no hay optimizaciones ni reglas de reescritura, porque no usa la pila.

Mira la definición de (++), por ejemplo ,:

(++) :: [a] -> [a] -> [a]
(++) []     ys = ys
(++) (x:xs) ys = x : xs ++ ys

La clave es x : (xs ++ ys) - es decir, es una recursión protegida por el constructor (:) "contras". Debido a que Haskell es perezoso, asigna un thunk para la operación de contras, y la llamada recursiva pasa a este thunk (asignado por el montón). Por lo tanto, su asignación de pila ahora es asignación de pila, que puede expandirse un poco. Así que todo esto es recorrer la gran lista, asignando nuevos objetos contras en el montón para reemplazar los que está atravesando. ¡Fácil!

"Invertir" es un poco diferente:

reverse l =  rev l []
  where
    rev []     a = a
    rev (x:xs) a = rev xs (x:a)

Es una función recursiva de cola, de estilo acumulador, por lo que, de nuevo, se asignará al montón.

Como puede ver, las funciones se basan en el uso de celdas de contras en el montón, en lugar de en la pila, por lo tanto, no hay desbordamiento de pila.

Para realmente definir esto, mire las estadísticas de tiempo de ejecución de GC vm:

$ time ./B +RTS -s
99

         833 MB total memory in use (13 MB lost due to fragmentation)
         Generation 0:  3054 collections,     0 parallel,  0.99s,  1.00s elapsed
         %GC time      82.2%  (85.8% elapsed)

Ahí está su gran lista: se asigna en el montón, y dedicamos el 80% del tiempo a limpiar los nodos de contras creados por (++).

Lección: a menudo se puede intercambiar pila por montón.

Answer 3

EDITAR : La respuesta a continuación es completamente irrelevante, si no está totalmente equivocada. Don Stewart, quien demuestra que en realidad entiende la evaluación perezosa, tiene la explicación correcta.

Si ejecuta ghc -ddump-simpl , verá que las funciones que se utilizan son GHC.Base.++ y GHC.List.reverse . Estas funciones están diseñadas para no desbordar la pila en listas grandes. Lo que se ve en Prelude es una "implementación de referencia", no el código que realmente se compila.

Aquí hay un código que saqué de la distribución de fuentes de GHC:

reverse                 :: [a] -> [a]
#ifdef USE_REPORT_PRELUDE
reverse                 =  foldl (flip (:)) []
#else
reverse l =  rev l []
  where
    rev []     a = a
    rev (x:xs) a = rev xs (x:a)
#endif

Y esto:

(++) :: [a] -> [a] -> [a]
(++) []     ys = ys
(++) (x:xs) ys = x : xs ++ ys

{-# RULES
"++"    [~1] forall xs ys. xs ++ ys = augment (/c n -> foldr c n xs)     ys
  #-}

En el primer caso, debe quedar claro lo que está pasando. En el segundo, estoy un poco confuso en las reglas de reescritura ...