Too Lazy to Recurse

If a tree doesn't fall in the forest, but instead you record some instructions (which you might or might not carry out later) on how to make the tree fall, does the Scala compiler make a sound?

The answer appears to be yes, at least when you're trying to use the @tailrec annotation (which complains about recursive calls when they don't appear in tail position).

For example, consider this completely useless function, which computes a value equal to its (nonnegative) argument by recursing in nontail position:

  def foo (i: Int): Int = if (i == 0) 0 else 1 + foo(i - 1)

If you mark this declaration @tailrec, the Scala compiler complains, as expected; the call to foo(i - 1) is not the last thing evaluated in foo, because the 1 + remains to be done after foo returns.

Now consider:

  case class Later1 (deferredI: () => Int) {
    lazy val i = deferredI()
    override def toString: String = i.toString
  }

  def foo1 (i: Int): Later1 =
    if (i == 0) Later1(() => 0) else Later1(() => 1 + foo1(i - 1).i)

Like foo, foo1 contains (textually) a call to itself. But foo1 doesn't actually call itself during an invocation of itself; it just computes and stores a function that would call foo1 later, if anyone bothered to invoke it. It's clear that such a call to foo1 isn't tail-recursive—you could never replace it with a goto—but then you would never expect it to be, since it's not called from foo1.

So is the Scala compiler being too picky about @tailrec? To be fair, you might want it to complain if instead you did something like:

  def foo1a (i: Int): Int =
    if (i == 0) 0 else Later1(() => 1 + foo1a(i - 1)).i

foo1a defers the call to itself only long enough to wrap the call in a Later1, then goes ahead and forces the call to complete anyway before returning. Even if you didn't want a warning for the foo1 case, you might want one here.

And even in the previous case, although foo1 returns a Later1 without ever reinvoking foo1, the computation captured in the Later1 will recurse, if it's ever carried out. Later1.i calls the deferredI created by foo1, and that deferredI calls Later1.i (where the latter Later1 results from calling foo1 again, although there are never two calls to foo1 on the stack at the same time).

As an aside, Scala does provide a more succinct way to express a deferred call to a function with no arguments. Although by-name vals are illegal, so that this won't compile:

  // BAD: case class pararameter i is a val:
  case class Later2 (i: => Int) {
    override def toString: String = i.toString
  }

you can trade some added boilerplate at the declaration of Later2 for some reduced boilerplate when you construct a Later2:

  class Later2 (deferredI: => Int) {
    lazy val i = deferredI
    override def toString: String = i.toString
  }

  object Later2 {
    def apply (i: => Int) = new Later2(i)
  }

  def foo2 (i: Int): Later2 =
    if (i == 0) Later2(0) else Later2(1 + foo2(i - 1).i)

Note that there's no need for “() =>” in the arguments to Later2.

The version using Later2 works as expected, but foo2 still provokes the compiler's wrath if you annotate it with @tailrec.