haskell - reservadas - paradigma funcional historia

¿Cuál es la vida útil de un valor memorizado 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 de modo que las evaluaciones adicionales de una función con las mismas entradas no vuelvan a calcular el valor, sino que lo obtengan directamente de la memoria caché de los valores memorizados.

Me pregunto si estos valores memorizados se reciclarán en algún momento.

1. Si es así, significa que los valores memorizados deben volver a calcularse en un momento posterior, y los beneficios de la memorización no son tan importantes como IMHO.
2. Si no, entonces está bien, esto es inteligente para guardar 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?

Imagine un programa que realiza un 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 de dicotomía.

Cada vez que el programa evalúa una función matemática con un número real específico, el resultado se memorizará. Pero hay una probabilidad muy pequeña de que vuelva a aparecer exactamente el mismo Número Real durante el algoritmo, lo que dará lugar a una pérdida de memoria (o al menos, un uso realmente malo).

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

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

EDIT: Ok, entiendo mi error de las primeras respuestas: la semántica pura implica una transparencia referencial que a su vez no implica una memorización automática, sino que simplemente garantiza que no habrá ningún problema con ella.

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

Answer 1

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

Esto es correcto. Específicamente, cuando ves algo como:

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

o una cláusula donde el equivalente, los valores a, byc pueden no calcularse hasta que realmente se usen (o pueden calcularse de inmediato porque el analizador de rigor puede demostrar que los valores se evaluarían más adelante de todos modos). Pero cuando esos valores dependen de los parámetros de la función actual (aquí, x e y), el tiempo de ejecución probablemente no recordará todas las combinaciones de x e y y las resultantes a, b y c.

También tenga en cuenta 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 sea más barata que el tiempo de CPU.

Entonces, la respuesta a su pregunta es: no hay resultados intermedios en Haskell. Todo lo que se puede decir es que el valor evaluado estará allí cuando sea necesario.

Answer 2

Haskell no memoriza automáticamente las llamadas a funciones, precisamente porque esto consumiría rápidamente toneladas de memoria. Si usted mismo toma la decisión, puede elegir en qué alcance se memoriza la función. Por ejemplo, digamos que tiene la función de fibonacci definida de esta manera:

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

Aquí la memorización solo se realiza dentro de una llamada a fib , mientras que si deja fibs en el nivel superior

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

luego, la lista memorizada se conserva hasta que el recolector de basura pueda determinar que no hay más formas de llegar a los fibs desde cualquier parte de su programa.