18

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

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

  1. 如果是这样，这意味着必须在以后重新计算记忆值，并且记忆化的好处并不是那么退出恕我直言。
  2. 如果不是，那么好吧，这很聪明，可以缓存所有内容......但这是否意味着程序 - 如果运行足够长的时间 - 总是会消耗越来越多的内存？

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

每次程序评估具有特定实数的数学函数时，结果都会被记忆。但是在算法过程中再次出现完全相同的实数的可能性很小，从而导致内存泄漏（或者至少是非常糟糕的使用）。

我的想法是，记忆值可能只是“限定”到程序中的某些内容（例如，当前延续、调用堆栈等），但我无法找到关于该主题的实用内容。

我承认我没有深入研究 Haskell 编译器的实现（懒惰？），但是请有人向我解释一下它在实践中是如何工作的？

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

我认为网络上的一些文章对此具有误导性，因为从初学者的角度来看，Referential Transparency 属性似乎很酷，因为它允许隐式记忆。

4

2 回答 2

20

Haskell 不会自动记忆函数调用，正是因为这会很快消耗大量内存。如果你自己做 memoziation，你可以选择函数被 memoized 的范围。例如，假设您有这样定义的斐波那契函数：

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

这里的记忆只在一次调用内完成fib，而如果你离开fibs顶层

fib n = fibs !! n

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

然后保留记忆列表，直到垃圾收集器可以确定没有更多方法可以fibs从程序的任何部分访问。

于 2011-05-05T13:23:42.030 回答
5

我的想法是，记忆值可能只是“限定”到程序中的某些内容（例如，当前延续、调用堆栈等），但我无法找到关于该主题的实用内容。

这是对的。具体来说，当您看到类似以下内容时：

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

或等效的 where 子句，在实际使用之前可能不会计算值 a、b 和 c（或者它们可能会立即计算，因为严格性分析器可以证明这些值无论如何都会在以后评估）。但是当这些值取决于当前函数参数（这里是 x 和 y）时，运行时很可能不会记住 x 和 y 的每个组合以及结果 a、b 和 c。

另请注意，在纯语言中，根本不记住这些值也是可以的——这仅在内存比 CPU 时间便宜的情况下才实用。

所以你的问题的答案是：在 Haskell 中没有中间结果的生命周期。只能说，评估值将在需要时出现。

于 2011-05-05T13:24:21.967 回答