scala - 为什么嵌套的 FlatMaps 会在 Scala 中炸毁堆栈？

Question

我正在通过阅读这篇论文来学习 Scala 中的 Trampoline 技巧 Stackless Scala with Free Monad ，作者:Rúnar Bjarnason。但是我陷入了第 4.3 节“容易出错的事情”。

让我感到困惑的是 f(x) 是如何在给定 FlatMap(x, f) 的情况下直接触发另一个内部调用的。 resume 已经是一个尾递归，因此它必须在一次 resume 调用中发生。但是 resume 中的所有包装函数都应该生成一个 Trampoline 实例。所以我找不到堆栈仍然会被炸毁的情况。

任何人都可以举个例子来解释“极端情况”吗？谢谢。

=============

如果您还没有看到这篇很棒的论文，这是背景:

Scala 编译器只能应用一个TCO在本地/最终尾部位置自调用函数上。所以 Trampoline 被带来了，用于将堆栈转换为堆。因此在论文中，针对不同的用途声明了三个 Trampoline 实例。 Done 用于包装最终结果。 More 表示下一步要计算。而FlatMap表示下一步计算之后还有一件事要做。因此，在为其定义了一个bind 操作之后，Trampoline 就变成了一个Monad。请参阅下面的代码(来自论文):

```

sealed trait Trampoline[+A] {
    final def resume: A = this match {
      case Done(v) => v
      case More(k) => k().resume
      case FlatMap(a, f) => a match {
        case Done(v) => f(v).resume
        case More(k) => (FlatMap(k(), f): Trampoline[A]).resume
        case FlatMap(b, g) => (FlatMap(b, (x: Any) => FlatMap(g(x), f)): Trampoline[A]).resume
      }
    }
  }

  case class More[+A](k: () => Trampoline[A])
    extends Trampoline[A]

  case class Done[+A](v: A)
    extends Trampoline[A]

  case class FlatMap[A, +B](sub: Trampoline[A], k: A => Trampoline[B]) extends Trampoline[B]

```

一切对我来说都很有意义，直到它说嵌套的 FlatMap 仍然可以炸毁堆栈。这就是我在这里问的原因。

Answer 1

它在纸上给出了答案:

There is one more corner case to consider here. It’s now possible for resume to overflow the stack if the left-leaning tower of FlatMaps is taller than the call stack. Then the call f(v) will make the call g(x), which will make another inner call, etc...

注意构造函数 FlatMap (b , x => FlatMap (g( x), f )) 立即调用该函数