memory - Recursión de Haskell y uso de memoria.

recursion functional-programming

Question

Me siento cómodo con la idea de reemplazar los bucles con recursión. Estoy jugueteando con un proyecto favorito, y quería probar algunas funciones de entrada de texto, así que escribí una pequeña interfaz de línea de comandos que solicita información en varias ocasiones hasta que recibe un comando específico para salir.

Se ve algo como esto:

getCommandsFromUser = do
    putStrLn "Enter command: "
    keyboardInput <- getLine
    let command = map toLower keyboardInput
    if command == "quit"
        then 
            putStrLn "Good-bye!"
        else do
            -- stuff
            -- more stuff
            putStrLn ("Sending command: " ++ commandURI)
            simpleHTTP $ getRequest commandURI
            getCommandsFromUser

main = do
    getCommandsFromUser

Esto funciona exactamente como se esperaba, pero al provenir de un fondo C / Java todavía me hace cosquillas en las partes profundas, oscuras e inconscientes de mi cerebro y me dan ganas de estallar en colmenas porque no puedo sacudir la idea de que cada llamada recursiva de getCommandsFromUser se está creando creando un nuevo marco de pila.

Ahora, no sé nada de IO, mónadas, estado, flechas, etc. todavía. Todavía estoy trabajando en Real World Haskell, todavía no he llegado a esa parte, y parte de este código es un patrón que se corresponde con las cosas que encontré en Google.

Además, sé que el punto central de GHC es que se trata de un compilador enloquecedoramente optimizado que está diseñado para hacer cosas increíbles, como el hermoso desenrollado de funciones recursivas de la cola y similares.

Entonces, ¿alguien puede explicar si esta implementación es "correcta" o no, y si es así, me explica qué sucede detrás de escena que evitaría que este programa explotara si se pusiera en manos de un número infinito de monos?

Sé lo que es la optimización de la llamada de cola. Me preocupa más cómo funciona en este caso, qué sucede con las acciones y la impureza funcional general.

Esta pregunta no se basaba tanto en la idea de que estaba confundido acerca de cómo Haskell usaba la pila y que esperaba que funcionara como un lenguaje imperativo; se basaba en el hecho de que no tenía idea de cómo Haskell manejaba la pila y quería saber qué estaba haciendo de manera diferente a los lenguajes tradicionales tipo C.

Answer 1

Como lo entiendo, debería olvidarse del TCO: en lugar de preguntar si una llamada recursiva está en una posición de cola, piense en términos de recursión protegida . Esta respuesta creo que tiene razón. También puede consultar la publicación sobre Datos y Codata en el siempre interesante y desafiante blog "Neighborhood of Infinity". Finalmente echa un vistazo al zoológico de fugas espaciales .

EDITAR : Lamento que lo anterior no aborde su pregunta sobre acciones monádicas directamente; Me interesa ver otras respuestas como la de Daniel Wagner que tratan específicamente sobre la mónada IO.

Answer 2

Esta implementación es correcta.

No creo que la optimización de llamadas de cola sea realmente lo que hace que esto funcione de manera eficiente. En cambio, lo que le permite trabajar de manera eficiente es, lo crea o no, la inmutabilidad de las acciones de IO. ¿Te sorprende que las acciones de IO sean inmutables? ¡Estaba al principio! Lo que eso significa es esto: getCommandsFromUser es una receta para "cosas que hacer"; y cada vez que getCommandsFromUser , se evalúa la misma receta . (Aunque, por supuesto, no cada vez que sigues la receta, ¡obtienes el mismo resultado! Pero esa es una fase completamente diferente de la ejecución).

El resultado de esto es que todas las evaluaciones de getCommandsFromUser se pueden compartir. GHC solo guarda una copia de la receta en la memoria, y parte de esa receta incluye un puntero al principio de la receta.

Answer 3

No importa que IO esté involucrado. Puedes leerlo en el wiki de Haskell:

IO en el interior

O, para una experiencia más profunda con el IO de Haskell:

Enfrentando al escuadrón torpe: entrada / salida monádica, concurrencia, excepciones y llamadas a idiomas extranjeros en Haskell

Answer 4

No te preocupes tanto por la pila. No hay nada fundamental que diga que las llamadas a funciones deben implementarse utilizando marcos de pila; Esa es simplemente una técnica posible para implementarlas.

Incluso cuando tiene "la pila", ciertamente no hay nada que diga que la pila debe limitarse a una pequeña fracción de la memoria disponible. Eso es esencialmente una heurística sintonizada con la programación imperativa; donde no utiliza la recursión como una técnica de resolución de problemas, las acumulaciones de llamadas muy profundas tienden a ser el resultado de errores de recursión infinita, y limitar el tamaño de la pila a algo bastante pequeño significa que tales programas mueren rápidamente en lugar de consumir toda la memoria disponible, intercambiar y luego moribundo.

Para un programador funcional, tener un programa que termine "se agote" la memoria para realizar más llamadas de función cuando la computadora aún tiene gigabytes de RAM disponibles es un defecto ridículo en el diseño del lenguaje. Sería como que C limita los bucles a un número arbitrario de iteraciones. Entonces, incluso si un lenguaje funcional está implementando llamadas de función utilizando una pila, habría una fuerte motivación para evitar usar la pila pequeña estándar que conocemos de C si es posible.

De hecho, Haskell tiene una pila que puede desbordarse, pero no es la pila de llamadas con la que está familiarizado desde C. Es muy posible escribir funciones no recursivas sin cola que se repitan infinitamente y consumirán toda la memoria disponible sin golpear una límite en la profundidad de la llamada. La pila que tiene Haskell se usa para rastrear los valores "pendientes" que deben evaluarse un poco más para tomar una decisión (veré esto un poco más adelante). Puede leer más detalladamente sobre este tipo de desbordamiento de pila here .

Veamos un ejemplo para ver cómo se puede evaluar su código. ¹ Usaré un ejemplo aún más simple que el tuyo, sin embargo:

main = do
    input <- getLine
    if input == "quit"
        then
            putStrLn "Good-bye!"
        else do
            putStrLn $ "You typed: " ++ input
            main

La evaluación de Haskell es perezosa ² . De manera simplista, eso significa que solo se molestará en evaluar un término cuando necesite el valor de ese término para tomar una decisión. Por ejemplo, si calculo 1 + 1 y luego antepago el resultado al principio de una lista, se puede dejar como un 1 + 1 "pendiente" en la lista ³ . Pero si uso para probar si el resultado fue igual a 3, entonces Haskell tendrá que hacer el trabajo de convertir 1 + 1 en 2 .

Pero si eso es todo, nada pasaría. Todo el programa se dejaría como un valor "pendiente". Pero hay un controlador externo que necesita saber qué evalúa la acción de IO para poder ejecutarlo.

Volver al ejemplo. main es igual al bloque do . Para IO , un bloque do hace una gran acción IO de una serie de más pequeños, que deben ejecutarse en orden. Por lo tanto, el tiempo de ejecución de Haskell ve la evaluación main para input <- getLine seguido de algunas cosas no evaluadas que aún no necesitan. Eso es suficiente para saber leer desde el teclado y llamar a la input String resultante. Digamos que escribí "foo". Eso deja a Haskell con algo como lo siguiente como su "próxima" acción IO :

if "foo" == "quit"
    then
        putStrLn "Good-bye!"
    else do
        putStrLn $ "You typed: " ++ "foo"
        main

Haskell solo está mirando lo más externo, así que esto se parece bastante a " si bla bla bla bla ...". if no es algo con lo que el ejecutor de E / S pueda hacer nada, debe evaluarse para ver qué devuelve. if solo se evalúa a la rama then o else , pero para saber qué decisión tomar Haskell se requiere para evaluar la condición. Así obtenemos:

if False
    then
        putStrLn "Good-bye!"
    else do
        putStrLn $ "You typed: " ++ "foo"
        main

Lo que permite que todo se reduzca a:

do
    putStrLn $ "You typed: " ++ "foo"
    main

Y nuevamente, do nos da una acción IO que consiste en una secuencia ordenada de subacciones. Así que lo siguiente que tiene que hacer el ejecutor de E / S es el putStrLn $ "You typed: " ++ "foo" . Pero eso tampoco es una acción de IO (es un cálculo no evaluado que debería resultar en uno). Así que tenemos que evaluarla.

La parte "más externa" de putStrLn $ "You typed: " ++ "foo" es en realidad $ . Deshacerse de la sintaxis del operador infijo para que pueda verlo de la misma manera que lo hace el runtiem de Haskell, se vería así:

($) putStrLn ((++) "You typed: " "foo")

Pero el operador $ simplemente definido por ($) fx = fx , por lo que sustituir el lado derecho inmediatamente nos da:

putStrLn ((++) "You typed: " "foo")`

Ahora normalmente evaluamos esto sustituyendo en la definición de putStrLn , pero es una función primitiva "mágica" que no se puede expresar directamente en el código de Haskell. Así que en realidad no se evalúa de esta manera; El ejecutor externo de E / S simplemente sabe qué hacer con él. Pero requiere que el argumento de putStrLn se evalúe completamente, por lo que no podemos dejarlo como (++) "You typed: " "foo" .

En realidad, hay una serie de pasos para evaluar completamente esa expresión, pasando por la definición de ++ en términos de operaciones de lista, pero simplemente saltémosla y digamos que se evalúa como "You typed: foo" . Entonces, el ejecutor de IO puede ejecutar putStrLn (escribir el texto en la consola) y pasar a la segunda parte del bloque do , que es simplemente:

`main`

Lo que no es algo que pueda ejecutarse inmediatamente como una acción de IO (no está integrado en Haskell como putStrLn y getLine ), por lo que lo evaluamos utilizando el lado derecho de la definición de main para obtener:

do
    input <- getLine
    if input == "quit"
        then
            putStrLn "Good-bye!"
        else do
            putStrLn $ "You typed: " ++ input
            main

Y estoy seguro de que puedes ver a dónde va el resto.

Tenga en cuenta que no he dicho nada sobre ningún tipo de pila. Todo esto es simplemente construir una estructura de datos que describa la acción de IO que es main , para que el controlador externo pueda ejecutarla. Ni siquiera es una estructura de datos particularmente especial; Desde el punto de vista del sistema de evaluación, es como cualquier otra estructura de datos, por lo que no hay limitaciones arbitrarias en su tamaño.

En este caso, la evaluación perezosa significa que la generación de esta estructura de datos se intercala con su consumo (y la generación de partes posteriores de la misma puede depender de lo que sucedió como resultado del consumo de partes anteriores de la misma), y por lo tanto este programa puede ejecutarse una cantidad constante de espacio. Pero como se observó en el comentario de shachaf sobre la pregunta, esta no es realmente una optimización para eliminar marcos de pila innecesarios; Es justo lo que sucede automáticamente con la evaluación perezosa.

Así que espero que haya sido lo suficientemente útil para que veas lo que está pasando. Básicamente, en el momento en que Haskell evalúa la llamada recursiva a getCommandsFromUser , ya está hecho con todos los datos generados en la iteración anterior, y así se recolecta la basura. Por lo tanto, puede seguir ejecutando este programa indefinidamente sin necesitar más que una cantidad fija de memoria. Esto es solo una consecuencia directa de la evaluación perezosa, y no es sustancialmente diferente cuando se trata de IO .

¹ Voy a rechazar por adelantado que no sé mucho en detalle sobre la implementación actual actual de Haskell. Sin embargo, sí conozco técnicas generales para implementar lenguajes puros perezosos como Haskell. También voy a tratar de evitar sumergirme demasiado en los detalles y solo explicar cómo funcionan las cosas de una manera intuitiva. Entonces, esta cuenta puede ser incorrecta en algunos de los detalles de lo que realmente está sucediendo dentro de su computadora, pero debería mostrarle cómo pueden funcionar estas cosas.

² La especificación de lenguaje técnicamente solo dice que la evaluación debe ser "no estricta". La evaluación que voy a describir, que se conoce como "perezosa" de manera informal, es realmente solo una posible estrategia de evaluación "no estricta", pero es lo que se obtiene en la práctica.

³ Y la nueva lista puede, de hecho, dejarse como un resultado "pendiente" de (1 + 1) : originalList hasta que alguien necesite saber si está vacía o no.