Why can nested FlatMaps explode the stack in Scala?

I am learning the Trampoline trick in Scala by reading this article Stackless Scala with Free Monad by Rúnar Bjarnason. But I am stuck in section 4.3 "Easy Thing to Wrong".

One thing confuses me how f(x)

can directly initiate another internal call given FlatMap(x, f)

. resume

is already tail recursion, so it must happen in one call resume

. But all wrapped functions in resume

should result in a Trampoline instance. So I cannot find a case where the stack can be blown up.

Anyone can give an example to explain the "corner case"? Thank.

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

This is the backstory if you haven't seen the amazing paper:

Scala compiler can only apply TCO in local / endpoint function. Thus, it is Trampoline

used to convert the stack to the heap. Thus, the article Trampoline

declares three instances for different use cases. Done

- for the final result. More

represents the next step for the calculation. And FlatMap

indicates that after the next step of the calculation, one more thing needs to be done. Therefore, after defining the operation bind

, Trampoline

it becomes a monad. See the code below (from the article):

``,

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]

      

        
        
        
      

    

``,

It all makes sense to me until he said that a nested one FlatMap

might still blow up the stack. And that's why I am asking this here.