为什么 Haskell 中的 `forever` 是这样实现的？

Question

Haskell 提供了一个方便的函数 forever 可以无限期地重复一个单子效果。可以定义如下：

forever :: Monad m => m a -> m b
forever ma = ma >> forever ma

但是，在标准库中，该函数 defined 不同：

forever :: Monad m => m a -> m b
forever a = let a' = a *> a' in a'

let 绑定用于强制“在此处显式共享，因为无论优化如何，它都可以防止 space 泄漏”（来自对实现的评论）。

您能解释一下为什么第一个定义可能存在 space 漏洞吗？

Answer 1

执行引擎从指向循环的指针开始，并在需要找出下一步要执行的 IO 操作时懒惰地扩展它。根据您对 forever 的定义，以下是循环的几次迭代，例如“存储在内存中的对象”：

1.
  PC
   |
   v
forever
   |
   v
  ma

2. 
PC
 |
 v
(>>) --> forever
 |         /
 v L------/
ma

3.
           PC
            |
            v
(>>) --> forever
 |         /
 v  L-----/
ma

4.
         PC
          |
          v
(>>) --> (>>) --> forever
 |        /          /
 v L-----/----------/
ma

5 and 6.
                  PC
                   |
                   v
(>>) --> (>>) --> (>>) --> forever
 |        /        /          /
 v L-----/--------/----------/
ma

结果是，随着执行的继续，您会得到越来越多的 (>>) 单元格副本。在正常情况下，这没什么大不了的；没有对第一个单元格的引用，因此当垃圾收集发生时， already-executed 前缀被丢弃。但是，如果我们不小心将无限循环传递为 ma 怎么办？

1.
  PC
   |
   v
forever
   |
   v
forever
   |
   v
  ma

2.
  PC
   |
   v
  (>>) -> forever
   |         /
   v L------/
forever
   |
   v
  ma

3.
                 return here
                 when done
                     |
                     v
         (>>) --> forever
          |          /
          v L-------/
PC --> forever
          |
          v
         ma

4.
               return here
                   |
                   v
       (>>) --> forever
        |          /
        v L-------/
PC --> (>>) --> forever
        |          /
        v L-------/
       ma

like, 12ish.
       return here
            |
            v
(>>) --> forever
 |          /
 v L-------/
(>>) --> (>>) --> (>>) --> (>>) --> (>>) --> forever <-- PC
 |        /        /        /        /          /
 v L-----/--------/--------/--------/----------/
ma

这次我们不能对前缀进行垃圾回收，因为一个“堆栈帧”向上，我们有一个指向 top-level forever 的指针，它仍然指向第一个 [=15] =]！哎呀。更高级的定义通过 in-memory 循环来解决这个问题。在那里，forever ma 的对象看起来更像这样：

  /----\
 v     |
(*>) --/
 |
 v
ma

现在，随着执行的进行，不再需要分配额外的 (*>)（也不需要收集垃圾）——即使我们嵌套它们。执行指针将简单地在该图中四处移动。

为什么 Haskell 中的 `forever` 是这样实现的？

Why is `forever` in Haskell implemented this way?

monads

haskell

functional-programming

lazy-evaluation