像Haskell这样的函数式语言中，记忆化值的生命周期是多久？

Question

在具有惰性语义（例如Haskell）的纯函数式语言中，计算结果会被缓存，以便使用相同输入再次调用函数时不会重新计算该值，而是直接从缓存的缓存值中获取。

我想知道这些备忘录值是否会在某个时间点被回收利用？

如果是这样，那么备忘录值必须在稍后的时间重新计算，备忘录化的好处在我的看法中并没有那么令人兴奋。

如果不是，那么好吧，这很聪明地缓存了一切...但这是否意味着程序 - 如果运行足够长的时间 - 将始终消耗越来越多的内存？

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

每次程序使用特定实数评估数学函数时，结果将被备忘录。 但是，在算法期间几乎不可能再次出现完全相同的实数，导致内存泄漏（或至少非常糟糕的使用）。

我的想法是，备忘录值可能只是“作用域”于程序中的某些东西（例如当前连续、调用堆栈等），但我无法找到有关此主题的实用信息。

我承认我没有深入研究Haskell编译器实现（惰性？），但请问有人能向我解释它在实践中如何工作吗？

编辑：好吧，我从前几个答案中了解了我的错误：纯语义意味着参考透明度，这又不意味着自动备忘录，但仅保证不会出现问题。

我认为网上的一些文章对此存在误导，因为从初学者的角度来看，参考透明度属性似乎很酷，因为它允许隐式备忘录化。

- Gabriel Cuvillier

---

请参见 https://dev59.com/8m865IYBdhLWcg3wKLX6。 - Don Stewart

Answer 1

Haskell并没有自动地缓存函数调用，因为这样会迅速消耗大量内存。如果您自己进行记忆化，则可以选择在哪个范围内对函数进行记忆化。例如，假设您定义了以下斐波那契函数：

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 为止。

- hammar

---

对于这个有启发性的例子点赞，尽管我敢打赌在这种情况下编译器会看到fibs不需要是一个本地值，并将其悄悄地提升到顶部。 - Ingo

@Ingo：我认为编译器不会将let浮动到lambda之外，正是因为这可能对内存使用产生重大影响，但我可能是错的。 - hammar

@Ingo：似乎有一种叫做“完全惰性”的优化方法可以实现这个功能，但我不确定它是否适用于这种情况。 - hammar

请注意，即使在上述备忘录化斐波那契数例子中，当函数fib不再可达时，fib的值也可能被垃圾回收（ghc会这样做）。 - augustss

你们要找的词是CAF，另请参见这个问题。 - barsoap

这种行为是由Haskell标准规定的吗？还是仅仅是GHC做事情的方式巧合而已？ - Paul Merrill

Answer 2

我的想法是，记忆化的值可能只是在程序中“作用域”（例如当前 continuation、调用堆栈等）中，但我无法找到有关该主题的实际内容。

这是正确的。具体来说，当您看到以下内容时：

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

如果有一个等价的where子句，变量a、b和c可能不会在实际使用之前计算（或者它们可能会立即计算，因为严格性分析器可以证明这些值稍后将被评估）。但是当这些值依赖于当前函数参数（这里是x和y）时，运行时很可能不会记住每个x和y的组合以及相应的a、b和c。

还要注意，在纯语言中，也可以完全不记住这些值——只要内存比CPU时间便宜就可以了。

所以，对于你的问题，答案是：Haskell中不存在中间结果的生命周期。所有我们能说的就是，当需要时已经计算好了。

- Ingo