3

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

有一件事让我感到困惑，a 如何在f(x)给定 a 的情况下直接触发另一个内部调用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仍然可以炸毁堆栈。这就是我在这里问它的原因。

4

1 回答 1

0

它在纸上给出了答案：

这里还有一个极端情况需要考虑。现在，如果 FlatMaps 的左斜塔比调用堆栈高，resume 可能会溢出堆栈。然后调用 f(v) 将调用 g(x)，这将调用另一个内部调用，等等......

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

于 2017-07-13T15:25:28.887 回答