Recursion

Recursion is a powerful technique for implementing an inverted loop and does not have the drawbacks of the implementation previously discussed. There is one problem with recursion--your stack can grow quite large. Fortunately, the Scala language provides tail recursion optimization to address this. With tail recursion optimization, the recursion is transformed into a simple goto.

The Scala compiler also supports a tailrec annotation for confirming that the code is being optimized for tail recursion. But it places 3 requirements on the annotated function.

1. The function must be private or final.
2. The function must end with a call to itself. And
3. The function must only have one call to itself.

You can write code that meets these three conditions, and which performs equally well for synchronous and asynchronous responses, but it needs to check to see how it has received the responses to its requests. Time now to look at some code.

We will again address the problem of printing a range of numbers and a lot of the code will be the same.

case class Loop(n: Int)
case class I(i: Int)

class P extends Actor {
  bind (classOf[I], ifunc)
  def ifunc(msg: AnyRef, rf: Any => Unit) {
    println(msg.asInstanceOf[I].i)
    rf(null)
  }
}

The test code will be the same too.

val mb = new ReactorMailbox
val p = new P
println("synchronous test")
val sl = new L(p)
sl.setMailbox(mb)
Future(sl, Loop(3))
println("asynchronous test")
val al = new L(p)
al.setMailbox(new ReactorMailbox)
Future(al, Loop(3))

It is only the L class which changes, which is where we implement the inverted loop.

class L(a: Actor) extends Actor {
  bind(classOf[Loop], lfunc)
  def lfunc(msg: AnyRef, rf: Any => Unit) {
    val n = msg.asInstanceOf[Loop].n
    if (n < 1) {
      rf(null)
      return
    }
    lrec(n, 0, rf)
  }

  @tailrec private def lrec(n: Int, _i: Int, rf: Any => Unit) {
    var async = false
    var sync = false
    val i = _i + 1
    a(I(i)) {rsp =>
      if (i == n) rf(null)
      else if (async) _lrec(n, i, rf)
      else sync = true
    }
    if (!sync) {
      async = true
      return
    }
    lrec(n, i, rf)
  }

  def _lrec(n: Int, i: Int, rf: Any => Unit) {lrec(n, i, rf)}
}

The lfunc function begins, as before, by validating n and responding with a null if n < 1. It then calls lrec. The lrec function implements what we are calling the conditional tailrec pattern. Yes, it looks a bit strange, but most of that is boilerplate to meet the requirements of the tailrec annotation.

The lrec function simply sends a request and, on receipt of a response it returns a null if it is done or calls itself to do it all again. The complication here is in how it calls itself. And that depends on how it received that response.

We use two flags, sync and async, to help us determine if the response was received synchronously or asynchronously. In the anonymous response function we set the sync flag only if the async flag has not been set. This makes sense because the anonymous response function executes before the send function returns only when the response is received synchronously. Conversly, after sending I to a, we set the async flag only if the sync flag has not been set. Again, this is because control is returned immediately after the send without yet having gotten a response only when the response is received asynchronously. This is all kind of tautological without being the least bit obvious. But it is part of the pattern which makes it a little easier, eventually.

Now when the response is received synchronously, we just do what we always do in synchronous code and have the function call itself as the last thing it does. This is pretty clean.

@tailrec private def lrec(n: Int, _i: Int, rf: Any => Unit) {
  val i = _i + 1
  a(I(i)) {rsp => 
    if (i == n) {
      rf(null)
      return
      }
  }
  lrec(n, i, rf)
}

Similarly, when the response is received asynchronously, we just have the function call itself from within the anonymous response function. Again, the code is pretty clean.

def lrec(n: Int, _i: Int, rf: Any => Unit) {
  val i = _i + 1
  a(I(i)) {rsp =>
    if (i == n) rf(null)
    _lrec(n, i, rf)
  }
}

It only gets messy when you look at the whole thing, which checks to see how the response was received and which satisfies all the conditions of the tailrec annotation--like having to call itself indirectly via _lrec from within the anonymous response function. But that is why patterns are so important, hmm?

Now there is an alternate form which avoids recursion completely--we just optimize the code ourselves rather than letting the Scala compiler do the work. Lets look at the pure synchronous form first, which is the part that is transformed.

def lrec(n: Int, _i: Int, rf: Any => Unit) {
  var i = _i
  while (true) {
    i += 1
    a(I(i)) {rsp =>
      if (i == n) {
        rf(null)
        return
      }
    }
    lrec(n, i, rf)
  }
}

Now we recombine the synchronous and asynchronous forms.

def lrec(n: Int, _i: Int, rf: Any => Unit) {
  var i = _i
  while (true) {
    var async = false
    var sync = false
    i += 1
    a(I(i)) {rsp =>
      if (i == n) rf(null)
      else if (async) lrec(n, i, rf)
      else sync = true
    }
    if (!sync) {
      async = true
      return
    }
  }
}

This alternate form is probably less clear than what we had before, though it does show what tail recursion optimization does.

The conditional tailrec pattern is used extensively in the Sequence actor to implement operations like loop, fold and filter.

Code

Tutorial