¿Cuál es la duración de un valor memorable en un lenguaje funcional como Haskell?

Question

En un lenguaje funcional puro con semántica perezosa (como Haskell), los resultados de los cálculos se memorizan para que las evaluaciones posteriores de una función con las mismas entradas no vuelvan a calcular el valor, sino que lo obtienen directamente del caché de valores memorizados.

Me pregunto si estos valores memoizados se reciclan en algún momento.

1. Si es así, significa que los valores memorizados se deben volver a calcular en otro momento, y los beneficios de la memorización no están saliendo de mi humilde opinión.
2. Si no, entonces bien, esto es inteligente para almacenar en caché todo ... pero ¿significa que un programa, si se ejecuta durante un período de tiempo suficientemente largo, siempre consumirá más y más memoria?

imaginar un programa que realiza el análisis numérico intensivo: por ejemplo, para encontrar las raíces de una lista de cientos de miles de funciones matemáticas utilizando un algoritmo dicotomía.

Cada vez que el programa evalúa una función matemática con un número real específico, el resultado será memorizado. Pero solo existe una probabilidad muy pequeña de de que exactamente el mismo número real aparezca de nuevo durante el algoritmo, dando lugar a una pérdida de memoria (o al menos, un mal uso).

Mi idea es que los valores tal vez memoized son simplemente "scoped" a algo en el programa (por ejemplo, para la continuación actual, la pila de llamadas, etc.), pero fue incapaz de encontrar algo práctico sobre el tema.

Admito que no he analizado detenidamente la implementación del compilador Haskell (¿perezoso?), Pero, por favor, ¿podría alguien explicarme cómo funciona en la práctica?

---

EDIT: Ok, entiendo que mi error desde las primeras respuestas: pura semántica implica Referencial Transparencia que a su vez no implica memoization automática, pero sólo garantiza que no habrá ningún problema con él.

Creo que algunos artículos en la web son engañosos acerca de esto, porque desde el punto de vista de un principiante, parece que la propiedad de Transparencia Referencial es tan buena porque permite la memorización implícita.

Answer 1

Haskell does not memoriza automáticamente las llamadas a funciones, precisamente porque esto consumiría rápidamente toneladas de memoria. Si haces memoziation tú mismo, puedes elegir en qué alcance se memoriza la función. Por ejemplo, digamos que usted tiene la función de Fibonacci se define así:

fib n = fibs !! n 
    where fibs = 0 : 1 : zipWith (+) fibs (tail fibs) 

Aquí el memoization sólo se realiza dentro de una llamada a fib, mientras que si se deja fibs en el nivel superior

fib n = fibs !! n 

fibs = 0 : 1 : zipWith (+) fibs (tail fibs) 

entonces la lista memorada se mantiene hasta que el recolector de basura puede determinar que no hay más formas de llegar al fibs desde cualquier parte de su programa.

Answer 2

Mi idea es que los valores tal vez memoized son simplemente "scoped" a algo en el programa (por ejemplo, para la continuación actual, la pila de llamadas, etc.), pero no pude encontrar algo práctico sobre el tema.

Esto es correcto. En concreto, cuando se ve algo como:

fun x y = let 
    a = ..... 
    b = .... 
    c = .... 
in .... 

o un equivalente cláusula where, los valores a, byc no puede ser calculada hasta que se usó en realidad (o pueden ser calculados de inmediato porque el analizador de rigurosidad puede proove que los valores se evaluarían más tarde de todos modos). Pero cuando esos valores dependen de los parámetros de función actuales (aquí x e y), es muy probable que el tiempo de ejecución no recuerde todas las combinaciones de x e y y a, b y c resultantes.

Tenga en cuenta también que, en un lenguaje puro, también está bien no recordar los valores en absoluto, esto solo es práctico en la medida en que la memoria es más barata que el tiempo de la CPU.

Así que la respuesta a su pregunta es: no existe la vida de los resultados intermedios en Haskell. Todo lo que uno puede decir es que el valor evaluado estará allí cuando sea necesario.