What is meant by "effectively tail recursive"?

user_5751675 0
Viewed 124

Chapter 7 in FP in Scala deals with creating a purely functional library for handling concurrency. To that end, it defines a type

type Par[A] = ExecutorService => Future[A]

and a set of useful functions such as fork

def fork[A] (a: => Par[A]): Par[A] = 
 es => es.submit(new Callable[A] {
  def call = a(es).get
 })

One of the exercises is about the function sequence with the following signature

def sequence[A](ps: List[Par[A]]): Par[List[A]]

The solution using foldRight is straightforward. However the authors included two other versions as answers, one of which states the following

// This implementation forks the recursive step off to a new logical thread,
// making it effectively tail-recursive. However, we are constructing
// a right-nested parallel program, and we can get better performance by 
// dividing the list in half, and running both halves in parallel. 
// See `sequenceBalanced` below.
def sequenceRight[A](as: List[Par[A]]): Par[List[A]] = 
  as match {
    case Nil => unit(Nil)
    case h :: t => map2(h, fork(sequenceRight(t)))(_ :: _)
  }

I am not quite sure what is meant by "effectively tail recursive". From the definition of fork it is clear that it accepts a by name parameter and so map2(h, fork(sequenceRight(t)))(_ :: _) will not evaluate the second parameter (until the executor service is provided). But that doesn't tell me how and why it is "effectively tail recursive".

scala functional-programming
2 Answers

Let's take some List(a, b, c). After passing it into sequenceRight it will turn into:

map2(
  a,
  fork(
    map2(
      b,
      fork(
        map2(
          c,
          fork(unit(Nil)
        )(_ :: _)
      )
    )(_ :: _)
  )
)(_ :: _)

This isn't tail recursive at all and compiler cannot treat it as one. However, when you would evaluate how it would be executed:

  • fork would make whatever you pass to it async, so it would return immediately,
  • map2 implementation will not block the execution until fork is executed to apply the function passed to map2, instead it would asynchronously transform the result calculated in fork to prepend the value
  • since recursion is done asynchronously, posting things to ExecutorService and appending operation to Future let you treat ExecutorService+Future like a trampoline

As a result what actually happens is:

  • sequenceRight(List(a, b, c)) call `map2(a, fork(sequenceRight(List(b, c))(_ :: _)
    • a will complete when it will complete but we can hold it as value even now
    • fork(sequenceRight(List(b, c)) is scheduled, but we aren't waiting until it complete, we can pass it around already
    • we can create a Future that will combine the result of the 2 above (and return it) without waiting for any of them completing!
  • as a result, this Future is returned immediately! It still runs, but this one call is finished!
  • same is true for recursively created Futures
  • once c and fork(unit(Nil)) completes, rResult :: Nil is computed
  • this allows completion of bResult :: cResult :: Nil
  • and this finally allows computation of the final result

In other words tail-recursive refers to recursive calls being rewritten into while loop to avoid stack overflow. But stack overflow is only an issue if recursive calls are being made synchronously. If you are returning something async, then the backtracing is shoved to ExecutionServices and Futures' observers, so they are hidden in a heap. From that point of view they solve the same issue of stack-overflow as tail-recursive calls, so "in spirit" they could be considered somewhat similar.

user_13051210

This is certainly not tail-recursion, and I think, they know it – that's why they added "effectively" :).

What they must mean is that this implementation does not create additional frames on stack for recursive invocations, which is true, since those invocations happen asynchronously, as you noted.

Now, whether this situation is even deserves to be called a "recursion" at all is a good question. I don't think there is a single accepted answer to that. I personally lean toward "yes", because the definition of recursion as "referencing itself" definitely includes this situation, and I don't really know how else to define it so that async invocations are excluded, but tail-recursion is not.

BTW, I am not much of an expert in Javascript, but I hear that the term "asynchronous recursion" is used fairly widely there.

user_42545170
Related