像Haskell这样的函数式语言的存储值的寿命是多少？ [英] What is the lifetime of a memoized value in a functional language like Haskell?

问题描述

在具有惰性语义的纯函数式语言（如Haskell）中，计算结果会被记忆，以便对具有相同输入的函数的进一步评估不会重新计算该值，而是直接从memoized值的缓存中获取该值。 / p>

我想知道这些记忆值是否会在某个时间点回收？

1. 如果是这样，这意味着memoized值必须在稍后重新计算，并且memoization的好处不会退出恕我直言。


2. 如果不是，那么好吧，这是聪明的缓存一切......但这是否意味着一个程序 - 如果运行足够长的时间 -
   总是会消耗越来越多的内存吗？
   
   
   

   想象一个执行密集数值分析的程序：例如使用二分法算法找到数以万计数学函数列表的根。
   
   

   每次程序使用特定实数评估数学函数时，结果都将被记忆。但是在算法期间再次出现完全相同的实数，导致内存泄漏（或者至少是非常糟糕的使用），只有非常小的概率
   。
   
   

   我的想法是，也许memoized值只是作用域到程序中的某些东西（例如当前的继续，调用堆栈等），但我无法找到有关该主题的实用信息。

   
   
   

   我承认我没有深入研究Haskell编译器实现（懒惰？），但请问，有人可以向我解释它在实践中的工作原理吗？

   
   
   

   ---

   
   
   

   编辑：好吧，我从前几个答案理解我的错误：纯语义意味着参照透明度这反过来并不意味着自动Memoization，但只是保证它会没有问题。

   
   
   

   我认为网络上的一些文章会误导这一点，因为从初学者的角度来看，参考透明属性看起来非常酷，因为它允许隐式记忆。

   解决方案

   Haskell不会自动记忆函数调用，因为这会很快消耗大量内存。如果你自己做记忆，你可以选择记忆功能的范围。例如，假设你有如下定义的fibonacci函数：
   
   

     fib n = fibs !! n 
   其中fibs = 0：1：zipWith（+）fibs（tail fibs）
     

   在这里，memoization只在一个调用 fib 的过程中完成，而如果在顶层保留 fibs

     fib n = fibs !! n 
    
    fibs = 0：1：zipWith（+）fibs（尾纤）
     

   然后保存memoized列表，直到垃圾收集器可以确定没有其他方法可以从程序的任何部分到达 fibs 。

   
   

   In a pure functional language with lazy semantics (such as Haskell), results of computations are memoized so that further evaluations of a function with the same inputs do not recompute the value but get it directly from the cache of memoized values.

   I am wondering if these memoized values get recycled at some point in time?

   1. If so, it means that the memoized values must be recomputed at a later time, and the benefits of memoization are not so exiting IMHO.
   2. If not, then ok, this is clever to cache everything... but does it mean that a program - if run for a sufficient long period of time - will always consume more and more memory ?

   Imagine a program performing intensive numerical analysis: for example to find roots of a list of hundred of thousands mathematical functions using a dichotomy algorithm.

   Every time the program evaluates a mathematical function with a specific Real Number, the result will be memoized. But there is only a really small probability that exactly the same Real Number will appear again during the algorithm, leading to memory leakage (or at least, really bad usage).

   My idea is that maybe memoized values are simply "scoped" to something in the program (for example to the current continuation, call stack, etc.), but I was unable to find something practical on the subject.

   I admit I don't have looked deeply at the Haskell compiler implementation (lazy?), but please, could someone explain to me how it works in practice?

   ---

   EDIT: Ok, I understand my mistake from the first few answers: Pure semantics implies Referential Transparency which in turn does not imply automatic Memoization, but just guarantees that there will be no problem with it.

   I think that a few articles on the web are misleading about this, because from a beginner's point of view, it seems that the Referential Transparency property is so cool because it allows implicit memoization.

   解决方案

   Haskell does not automatically memoize function calls, precisely because this would quickly consume tons of memory. If you do memoziation yourself, you get to choose at what scope the function is memoized. For example, let's say you have the fibonacci function defined like this:

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

   Here the memoization is only done within one call to fib, whereas if you leave fibs at the top level

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

   then the memoized list is kept until the garbage collector can determine that there are no more ways to reach fibs from any part of your program.

   这篇关于像Haskell这样的函数式语言的存储值的寿命是多少？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！