How is lazy interpreted in recursive context?

Question

Here's the code from FPIS

object test2 {

  //a naive IO monad
  sealed trait IO[A] { self =>
    def run: A
    def map[B](f: A => B): IO[B] = new IO[B] { def run = f(self.run) }
    def flatMap[B](f: A => IO[B]): IO[B] = {
      println("calling IO.flatMap")
      new IO[B] {
        def run = {
            println("calling run from flatMap result")
            f(self.run).run
        }
     }
    }
  }

  object IO {
    def unit[A](a: => A): IO[A] = new IO[A] { def run = a }
    def apply[A](a: => A): IO[A] = unit(a) // syntax for IO { .. }
  }

  //composer in question
  def forever[A,B](a: IO[A]): IO[B] = {
    lazy val t: IO[B] = a flatMap (_ => t)
    t
  }

  def PrintLine(msg: String) = IO { println(msg) }

  def say = forever(PrintLine("Still Going..")).run
}

test2.say will print thousands of "Still Going" before stack overflows. But I don't know exactly how that happens.

The output looks like this:
scala> test2.say
calling IO.flatMap //only once
calling run from flatMap result
Still Going..
calling run from flatMap result
Still Going..

... //repeating until stack overflows

When function forever returns, is the lazy val t fully computed (cached)? And, the flatMap method seems to be called only once (I add print statements) which counters the recursive definition of forever. Why?

===========
Another thing I find interesting is that the B type in forever[A, B] could be anything. Scala actually can run with it being opaque.

I manually tried forever[Unit, Double], forever[Unit, String] etc and it all worked. This feels smart.

Answer 1

What forever method does is, as the name suggests, makes the monadic instance a run forever. To be more precise, it gives us an infinite chain of monadic operations.

Its value t is defined recursively as:

t = a flatMap (_ => t)

which expands to

t = a flatMap (_ => a flatMap (_ => t))

which expands to

t = a flatMap (_ => a flatMap (_ => a flatMap (_ => t)))

and so on.

Lazy gives us the ability to define something like this. If we removed the lazy part we would either get a "forward reference" error (in case the recursive value is contained within some method) or it would simply be initialized with a default value and not used recursively (if contained within a class, which makes it a class field with a behind-the-scenes getter and setter).

Demo:

val rec: Int = 1 + rec
println(rec) // prints 1, "rec" in the body is initialized to default value 0


def foo() = {
  val rec: Int = 1 + rec // ERROR: forward reference extends over definition of value rec
  println(rec)
}

However, this alone is not the reason why the whole stack overflow thing happens. There is another recursive part, and this one is actually responsible for the stack overflow. It is hidden here:

def run = {
  println("calling run from flatMap result")
  f(self.run).run
}

Method run calls itself (see that self.run). When we define it like this, we don't evaluate self.run on the spot because f hasn't been invoked yet; we are just stating that it will be invoked once run() is invoked.

But when we create the value t in forever, we are creating an IO monad that flatMaps into itself (the function it provides to flatMap is "evaluate into yourself"). This will trigger the run and therefore the evaluation and invocation of f. We never really leave the flatMap context (hence only one printed statement for the flatMap part) because as soon as we try to flatMap, run starts evaluating the function f which returns the IO on which we call run which invokes the function f which returns the IO on which we call run which invokes the function f which returns the IO on which we call run...

Answer 2

I'd like to know when function forever returns, is the lazy val t fully computed (cached)?

Yes

If so then why need the lazy keyword?

It's no use in your case. It can be useful in situation like:

def repeat(n: Int): Seq[Int] {
  lazy val expensive = "some expensive computation"
  Seq.fill(n)(expensive)
  // when n == 0, the 'expensive' computation will be skipped
  // when n > 1, the 'expensive' computation will only be computed once
}

The other thing I don't understand is that the flatMap method seems to be called only once (I add print statements) which counters the recursive definition of forever. Why?

Not possible to comment until you can provide a Minimal, Complete, and Verifiable example, like @Yuval Itzchakov said

Updated 19/04/2017

Alright, I need to correct myself :-) In your case the lazy val is required due to the recursive reference back to itself.

To explain your observation, let's try to expand the forever(a).run call:

1. forever(a) expands to

2. { lazy val t = a flatMap(_ => t) } expands to

3. { lazy val t = new IO[B] { def run() = { ... t.run } }

Because t is lazy, flatMap and new IO[B] in 2 and 3 are invoked only once and then 'cached' for reuse.

On invoking run() on 3, you start a recursion on t.run and thus the result you observed.

Not exactly sure about your requirement, but a non-stack-blowing version of forever can be implemented like:

  def forever[A, B](a: IO[A]): IO[B] = {
    new IO[B] {
      @tailrec
      override def run: B = {
        a.run
        run
      }
    }
  }