3

I am learning the Trampoline trick in Scala by reading this paper Stackless Scala with Free Monad, by Rúnar Bjarnason. But I got stuck in section 4.3 "An easy thing to get wrong".

One thing makes me confused is how a f(x) could directly trigger another inner call given a FlatMap(x, f). The resume is already a tail recursion so it must happens in one resume call. But all the wrapped functions in resume should result a Trampoline instance. So I cannot find a case that the stack could still be blowed up.

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

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

This is the background in case you haven't seen the awesome paper:

Scala compiler can only apply a TCO on a local/final tail position self-call function. So Trampoline is brought for transforming the stack to the heap. So in the paper, three instances of Trampoline are declared for different usages. Done is for wrapping the final result. More represents the next step to calculate. And FlatMap indicates that there is one more thing to do after the next step calculate. So after defining a bind operation to it, Trampoline becomes a Monad. See the code below (from the paper) :

```

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]

```

Everything makes sense to me until it said that the nested FlatMap could still blow up the stack. And this is why I ask it here.

SanCoder
  • 51
  • 4
  • 2
    This is an interesting question and I think a [MCVE] of the problem illustrated in the paper might help provide an answer (I don't assume people are going to read a 8 page PDF just to answer the question, if they haven't read it already). – Yuval Itzchakov Jul 13 '17 at 15:23
  • @YuvalItzchakov you are right. I was using my mobile to post the question. Will update the details once I get back to my keyboard. Thanks. – SanCoder Jul 13 '17 at 15:32

1 Answers1

0

It gives the answer on the paper:

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...

Notice the constructor FlatMap (b , x => FlatMap (g( x), f )) calls the function immediately

raam86
  • 6,785
  • 2
  • 31
  • 46
  • Thanks for the reply. From my understanding, the `x=>FlatMap(g(x),f)` would not be evaluated immediately. And how could disallowing the FlatMap constructor fix the problem if calling `g` would cause stack overflow? – SanCoder Jul 13 '17 at 15:45
  • Thank you for the thought provoking question. `k: A => Trampoline[B]` is deferred to when it's called but `sub: Trampoline[A]` is left leaning tower of flatMaps from the paper – raam86 Jul 14 '17 at 10:46