jducoeur

[For the programmers -- this is a pretty technical intermediate-level "mistakes to avoid" lesson. Likely useful to folks who are learning programming, and ruefully amusing in a headdesk way to the experienced programmers.]

Today's fire-drill for Querki was a bug report (from alexx_kay, who has my deepest thanks for pointing it out) that, under certain circumstances, his browser window was hanging. Not showing an error, not popping up alerts -- just becoming completely unresponsive. There was a 30 minute hunt to figure out what the heck was going on, and a quick release to get the fix out. Here's what happened, and the lesson to learn from it.

As you get into Functional Programming, one of the lessons you quickly learn is to think recursively -- to solve a problem, you break it down into slightly smaller versions of the same problem. A canonical example is this naive implementation of map():

def map[T, U](list:List[T], f:T => U):List[U] = {
  list match {
    case Nil => Nil
    case head :: tail => f(head) :: map(tail, f)
  }
}

That is, given a List of T, and a function that goes from T to U, you first check whether the list is empty, in which case the result is also empty. Otherwise, grab the head, apply the function to that, and recurse onto the next element.

That works fine, but has one problem in a conventional language like Scala: each time it recurses, you're going one stack frame deeper, and the stack is a limited resource. How limited depends on the machine, but suffice it to say, if you've got ten thousand elements in your list, your program is going to go *kaboom* before you get to the end.

The way you deal with that is with tail recursion. Basically, if the very last function call your function makes is to itself, then the compiler can (and automatically does) turn that into a *loop* instead of a function call. (It's not quite technically a loop IIUC, but that's an easy way to think about it.) That way, you're not consuming stack with each of those recursive function calls, because they're actually looping in the same function call. The Scala compiler provides an annotation, @tailrec, which means, "I intend for this function to be tail-recursive -- complain to me if it's not".

Our map() function above isn't actually tail-recursive, even though it looks like it at first glance: the last thing it doesn't isn't to call itself, it's to call "::" to add the List pieces together. We can redo the function as tail-recursive, with a little bit of adjustment to that timing:

def map[T, U](fullList:List[T], f:T => U):List[U] = {
  @tailrec
  def mapRec(list:List[T], result:List[U]):List[U] = {
    list match {
      case Nil => Nil
      case head :: tail => mapRec(tail, result :: f(head))
    }
  }
 
  mapRec(fullList, Nil)
}

We're now keeping track of the result list, and building it up *before* we call mapRec() recursively, so it should be tail-recursive.

(NB: I'm typing these examples off the top of my head, and they're not tested -- I believe they work, but don't be surprised at errors. Also, this definition of map() is actually quite inefficient for other reasons, but those don't matter for purposes of this lesson.)

Anyway...

The function that caused today's headache was intended to go from an HTML node, looking up the tree to find the parent that matched a particular criterion; this gets called frequently, so I went for tail recursion. In very rough and simplified pseudocode, it looked something like:

  @tailrec def findParentRec(node:JQuery, predicate:JQuery => Boolean):Option[JQuery] = {
    if (node.length == 0)
      None
 
    node.find(predicate(_)) match {
      case Some(result) => Some(node)
      case None => findParentGadgetRec(node.parent(), pred)
    }
  }

A JQuery node contains one or more HTML elements. If it doesn't contain anything, then we've gotten to the top, and we give up. Otherwise, if this node contains an element that fits the predicate, we have our answer. Otherwise, tail-recurse up to its parent.

See the bug?

This one is "for lack of an else, the Kingdom was lost", and it's a reminder that Scala is *not* pure-functional, so it doesn't complain when you have a pointless expression. The problem is that the if clause returns None when you get to the top -- and then the function keeps right on going, because we're missing the "else" before node.find(). (Scala has to allow this, since it allows side-effects. A pure-functional language would say, "Hey, there's no reason to have done that, so this must be an error".) And of course, the parent() of an empty node is an empty node, so we just keep recursing with that empty node.

And this is where tail recursion can bite you on the ass if you're not careful. *Normally*, this infinite recursion bug would quickly cause the stack to explode, and you'd get a nice clear error. But since the compiler has optimized away the recursion, it just turns into a beautifully tight infinite loop, efficiently eating one of your CPUs.

So the lesson for today is: tail recursion is powerful, useful and efficient. But be *very* careful to make sure that recursion will terminate, because you won't get saved by a stack-overflow exception if it doesn't...