Extending Javascript: Tail Recursion

Posted Sun, Nov 18, 2007 in:

• Entertainment

Javascript is a very powerful, yet underrated, programming language. Despite its name, it is neither Java-like nor “just a scripting language.” It uses a generally unfamiliar concept known as Prototype-based Programming, which is object-oriented, but without classes.

A couple of common questions about Javascript are “How can I run multiple threads?” and “How do I pause execution of my program for X seconds?”

The common answer is “You can’t, but you can do something similar with setTimeout.”

If you want to wait for X milliseconds before doing something, you simply setup a callback with

    setTimeout('something', X);

However, any callbacks will have to wait until the current function finished executing before executing, because Javascript is single threaded, and setTimeout simply puts its function call on a queue of things to be done later. After each function is finished running, the queue is checked for scheduled tasks, and any task whose timeout has expired will be run. Firefox even seems to defer updating of page content until after the currently running Javascript function returns. This is why on some pages with poorly crafted Javascript browsers will give warnings aboout scripts running for too long or consuming too much processor time.

So what do you do if you want to do large amounts of calculations, perhaps in loops that will run for many seconds or minutes? Once again, setTimeout is the way to go. As long as each function only runs for a very short period of time, you can run several different tasks “simultaneously” without killing your browser.

There is one thing, however, that bothers me about using setTimeout: It makes for some ugly code, and usually requires you to either wrap a string or anonymous function around your callbacks. Worse, it requires you to think about callbacks at all. So something as simple as running a loop that won’t hijack your browser becomes a pain. For example, here’s a simple function to count between two numbers within an element on the page:

    //(the se() function sets the innerHTML of an element on the page)
        // Simple loop version
        //--------------------
        function do_loop(start, end) {
          for (i=start; i <= end; i++) 
            se('taildemo_val', i);
        }

It’s simple, it’s straightforward, and it mostly does what you would expect. The problem is that you only ever see the final number (at least in FF and IE), because the browser is too busy looping away to update the page. Also, any other Javascript on the page will not run until this loop is finished.

Here’s a simple recursive version:

    // Basic recursive version
        //------------------------
        function do_recurse(i, stop)
        {
          se('taildemo_val', i);
          if (i == stop)
            return;
          else
            do_recurse(i+1, stop);
        }

This version is even worse than the last! Not only does it lock up the page, but it crashes with a “Too much recursion” error if you give it too big a range of numbers. I’ve included this because this is the way you have to look at the problem if you want to make it work with setTimeout.

The next step, then, is the setTimeout version:

    // setTimeout version
        //-------------------
        function do_settimeout(i, stop)
        {
          se('taildemo_val', i);
          if (i == stop)
            se('taildemo_status', 'done');
          else
            setTimeout('do_settimeout('+(i+1)+','+ stop+')', 0);
          // this would also work: 
          //setTimeout(function() {do_settimeout(i+1, stop) }, 0);
        }

This version is almost the same, except that it has to handle whatever must be done upon finishing, since the calling function will be returned to immediately. In a more serious example, a callback would be passed in as a third parameter, to be executed at the end of the “recursion”. The 0 passed to setTimeout indicates that the callback should be run as soon as possible. When running this version, the browser actually updates between calls of the function. This actually slows down the code a bit, but since seeing the numbers increment was the goal in this exercise, that’s okay. The main advantage here is that the page is still usable as this code is running.

Still, the call to setTimeout is kinda ugly. I’d like it to look more like the call in the recursive version. With a bit of delving into some of the less-used portions of Javascript, I managed to write a function called “tail,” which allowed my code to look like this:

    // tail() version
        //---------------
        function do_tail(i, stop)
        {
          se('taildemo_val', i);
          if (i == stop)
            se('taildemo_status', 'done');
          else
            tail(i+1, stop);
        }

It’s almost exactly like the recursive version, but with tail instead of the recursive call. The details of the call to setTimeout are taken care of elsewhere, and there’s the added bonus of not having the name of the function there. I could change the name of the function in just one place, or I could even call tail from an anonymous function without having to resort to using arguments.callee.

Here’s the basic implementation of tail:

    function tail() {
          var fn = tail.caller;
          var args = arguments;
          setTimeout(function() {fn.apply(this, args)}, 0);
        };

Note that I had to bind tail.caller and arguments to new variables before putting them in my anonymous function. That’s because they are both special variables which will have different values by the time the callback is actually called. arguments is always bound to the arguments of the current function, which in the case of the callback; tail.caller, which is a reference to the function that tail was called from, only exists from within the tail function.

This isn’t strictly tail recursion, but it has the same basic effect: keeping the stack from overflowing. In this version, it also has the added bonus of adding a simple method of multi-tasking and/or concurrent programming. In most functional programming languages you can count on being able to use tail recursion without worrying about the stack, since those languages tend to detect tail recursion and replace it with a loop of some sort.

Here’s a demo of this in action. Click on loop, recursive, setTimeout, and tail, respectively to view that demo. Click reset to reset. Note how when you use the loop or recursive version the bouncing box pauses until it is done. 2000 as an ending number seems to demonstrate this effect pretty well.

See taildemo.js and tail.js for the rest of the code, and taildemo.html for a standalone version of the demo.