I came across this mathematical problem the other day:

Consider n points on a circle, labeled clockwise from 0 to n-1. Initially PacMan begins at 0 and there is a dot at each of the remaining n-1 points. PacMan takes a random walk around the circle; at each step, it moves with probability 1/2 to one neighbor and with probability 1/2 to the other neighbor. (Note that points 0 and n-1 are neighbors.) The first time PacMan visits any point it eats the dot that is there. Which dot is most likely to be the last eaten?

(This is edited from the original since the professor who formulated it wants to reuse it in a different class and I’d rather not students find this with a simple search.)

Here’s the game plan then for 10 points around the circle:

My first basic thought was, since the question asks for a single dot, it would make sense from a symmetry point of view for that dot to be directly opposite. In other words: it’s the dot furthest away that gets eaten last most of the time. Seems like a viable proposition, no? But maybe I’m trying to be too clever in reading between the lines of the problem: maybe there is more than one dot that is likely to be the last eaten, say at 1/3 and at 2/3 of the way round the circle. It’s getting a bit complicated now.

Mitzenmacher indicated that many students decided to simulate the problem to find out the answer, and then to reason the proof from the statistical results. I decided to do the same. And because I’m into JavaScript at the moment, I used that as my language. It also gives me an opportunity to expand a little on how to write long-running programs that can run in a browser.

In essence I wrote a program to cycle through game after game, recording the last dot to be eaten. To make it statistically significant, I went for some 90,000 games. Here’s my code:

  var i, 
      gameNumber = 0, 
      totalGames = 90000,
      pointCount = 10,
      stats = [];

  // zero out the stats array
  for (i = 0; i < pointCount; i++) {
    stats[i] = 0;
  }

  var dotsToEat,
      dotsEaten,
      pacManPosition,
      goLeft,
      dotPositions = [false];
            
  for (gameNumber = 0; gameNumber < totalGames; gameNumber++) {

    // reset game
    dotsEaten = 0;
    dotsToEat = pointCount - 1;
    for (i = 1; i < pointCount; i++) {
      dotPositions[i] = true;
    }
    pacManPosition = 0;

    // continue moving PacMan until all dots are eaten
    while (dotsEaten < dotsToEat) {
      // go left or right?
      goLeft = Math.random() < 0.5;

      // move PacMan
      if (goLeft) {
        pacManPosition = pacManPosition - 1;
        if (pacManPosition < 0) {
          pacManPosition = pointCount - 1;
        }
      }
      else {
        pacManPosition = pacManPosition + 1;
        if (pacManPosition === pointCount) {
          pacManPosition = 0;
        }
      }
            
      // if there's a dot, eat it
      if (dotPositions[pacManPosition]) {
        dotPositions[pacManPosition] = false;
        dotsEaten += 1;
      }
    }

    // increment stats for the last position
    stats[pacManPosition] += 1;
  }

  alert(stats);

There’s nothing too difficult here: in essence, I set up a loop to run game after game. For each game I simulate PacMan doing a random walk around the circle, back and forth, eating dots when he gets to them. I make a note of the last dot eaten in a statistics array, before going round again and starting a new game. Finally after 90,000 games I report the stats array.

If you run this in Firebug (like I did) you’ll see that the browser times the script out because it’s taking too long. Time to refactor to use setTimeout.

(I would take a look at a three part series I did a while back on callbacks (one, two, three) since I will be using the same techniques here.)

The first thing to do is to make the code that runs a single game into its own function since it’ll be easier to pass it to the setTimeout function. For simplicity though, I’m going to nest it inside another function so I can take advantage of function scoping for the variables that apply across all games. Here’s the main outer function and its call.

var runSimulation = function () {

  // code goes here

};

runSimulation();

Now for the run-a-single-game function:

  var runGame = function () {
    // reset game
    var dotsEaten = 0,
        dotsToEat = pointCount - 1,
        pacManPosition = 0,
        i, goLeft,
        dotPositions = [false];

    for (i = 1; i < pointCount; i++) {
      dotPositions[i] = true;
    }

    // continue moving PacMan until all dots are eaten
    while (dotsEaten < dotsToEat) {
      // go left or right?
      goLeft = Math.random() < 0.5;

      // move PacMan
      if (goLeft) {
        pacManPosition = pacManPosition - 1;
        if (pacManPosition < 0) {
          pacManPosition = pointCount - 1;
        }
      }
      else {
        pacManPosition = pacManPosition + 1;
        if (pacManPosition === pointCount) {
          pacManPosition = 0;
        }
      }
            
      // if there's a dot, eat it
      if (dotPositions[pacManPosition]) {
        dotPositions[pacManPosition] = false;
        dotsEaten += 1;
      }
    }

    // increment stats for the last position
    stats[pacManPosition] += 1;
  };

The variables for this nested function that come from the outer function are stats[] and pointCount.

We’ll also write a self-delaying function to run all the games:

  var runAsync = function () {
    runGame();
    gameNumber += 1;
    if (gameNumber < totalGames)
      setTimeout(runAsync, 10);
    else 
      alert(stats);
  };

In other words, run a game, after it completes and there are more games to run, queue up the next one with setTimeout, otherwise display the stats array. The full code now looks like this:

var runSimulation = function () {

  var i, 
      gameNumber = 0, 
      totalGames = 90000,
      pointCount = 10,
      stats = [];

  var runGame = function () {
    // code above
  };

  var runAsync = function () {
    // code above
  };

  // zero out the stats array
  for (i = 0; i < pointCount; i++) {
    stats[i] = 0;
  }

  runAsync();
};

Way cool. Except that, since it runs one game every 10 milliseconds, it takes 900+ seconds (90,000 games * 10 ms) to give an answer. That’s a quarter of an hour. I’m sorry but, although I’d like to know the answer, 15 minutes to see it is a little too long. Let’s refactor the runAsync function to batch up the games. It should try and run as many games as it can during 50 milliseconds (say) before queuing up another batch. Replace the old runAsync function with this new one (plus a little helper function):

  var now = function () {
    return +new Date();
  };

  var runAsync = function () {
    var start = now();

    do {
      runGame();
      gameNumber += 1;
    } while ((gameNumber < totalGames) && ((now() - start) < 50));

    if (gameNumber < totalGames)
      setTimeout(runAsync, 10);
    else 
      alert(stats);
  };

Now we’re really rocking. On my machine just now, this runs 90,000 games and produces an answer in about 3 seconds. The answer just now?

0,9994,10079,10039,9919,10004,9879,10073,10027,9986

Wow. In other words, any dot is just as likely to be the last one eaten as any other. (If you like, the probability of any dot being the last one eaten is 1/9.)  My initial guess of the opposite dot is dead wrong.

To prove this mathematically involves rather more knowledge about random walks and Markov processes than I now know (it’s been a while since I did probability at University). It’s also linked to the Gambler’s Ruin problem.

I can’t believe that I haven’t posted an article on how to call functions in JavaScript and what this gets set to for each of the various invocation patterns. It’s one of those things that catches people out periodically, so it’s well worth discussing at length.

There are four different ways to call or invoke a JavaScript function: method invocation, function invocation, constructor invocation, and apply invocation. Each of these invocation patterns results in this being set to a different object inside the function. In C#, there is never any doubt what this refers to: it’s the object (the instance) on which the method is called. Using this is entirely optional, unless you are trying to resolve some possible ambiguity in the code (say, a parameter to the instance method has the same name as a field of the instance: in this case, to refer to the field you would have to use this). Of course, for a static method rather than an instance method, using this is an error and will be caught at compile-time.

Method invocation

Back to JavaScript. We’ll first talk about the equivalent to C#’s calling of an instance method: method invocation. This is just like the C# case: you’ve got some object and you call a method of that object. The this variable inside the function will be set to point to the object you’re calling the method on. In essence, pretty much exactly the same as C#.

Let’s look at a simple object called printer. When you call the log method of printer passing in some other object, it will print the object passed in as well as the number of times the printer object has been used.

var printer = {
  callCount : 0,

  log : function(obj) {
    console.log("---");
    console.log(obj);
    this.callCount += 1;
    console.log("--- (log number: " + this.callCount + ")");
  }
};

As you can see, a very simple object with one field (callCount) and a log method. The log method will print the object, increment the field, and then print a line showing how many times it has been called. The use of this is not optional as in C#; it must be used, otherwise the interpreter will try to resolve it by walking up the scope chain to the Global Object (which in browser JavaScript is window). If you like, this bypasses the normal scoping rules in JavaScript.

Here’s a quick example of how to call it.

var someObj = {a:42};

printer.log(someObj); // prints 1 as log number
printer.log(someObj); // prints 2 as log number

The fun thing about JavaScript is that functions are objects. We can pass them around at will. Here’s a new (empty) printer object that I then create the same field for. I can then create a log method by copying the printer.log function.

newPrinter = {};
newPrinter.callCount = 41;
newPrinter.log = printer.log;

newPrinter.log(someObj); // prints 42 as log number

Function invocation

The next way of calling a function is using function invocation. This is easy in concept – just call the bare function, not using an object – but it is the invocation pattern that causes the most problems and bugs. The reason is that the this variable gets set to the Global Object. Let’s take a look at a couple of examples. Firstly though, let’s define a simple function that returns true if the passed in object is the Global Object.

var isGlobalObject = function(obj) {
  return (function() {return this === obj;}());
};

What? Did he say simple? Let’s take it slowly. First of all, isGlobalObject takes in an object and returns something. What it returns is the result of automatically calling an anonymous function. This anonymous function is called using the function invocation pattern we’re currently discussing and checks to see if this is equal to the outer obj parameter. In other words, this anonymous function makes use of the pattern we’re trying to demonstrate. (Note: because I did not hard-code window, this function will also work on node.js, where the Global Object is called something else.)

Before making moving on, let me emphasize a point. Automatically calling an anonymous function is one of the great patterns of modern JavaScript and hence in one of these types of functions this will point to the Global Object.

Now we can make up some example function and show that calling it using the function invocation sets this to the Global Object.

var doSomething = function (arg) {
  isGlobalObject(this) ?
    console.log("In this function, 'this' is the Global Object") :
    console.log("In this function, 'this' is something else");
};

doSomething(); // prints that 'this' is the Global Object

There is another common JavaScript coding pattern that can throw up bugs because people assume this points to the enclosing object rather than the Global Object, and that’s with callbacks. Let’s illustrate with setTimeout. I’ll write a ticker object that outputs an asterisk once a second.

var ticker = {
  show : function() {
    console.log("*");
  },
  start : function() {
    this.show();
    setTimeout(function() { this.start(); }, 1000);
  }
};

ticker.start();

If you run this code, you should see an asterisk, and then after a second you should get an error saying “this.start is not a function”. The reason is that the callback to the setTimeout function is an anonymous function and setTimeout’s code will call it using the function invocation pattern. The this variable will be set to the Global Object and not the ticker object, despite what a quick glance at the code might imply. Since window.start does not exist, you get the error message.

To solve this bug, we shall have to save the value of the this variable in the start method, and then use that local variable inside the anonymous function. Because in JavaScript scope is defined by function, the anonymous function will ‘see’ this local variable in its parent function.

var ticker = {
  show : function() {
    console.log("*");
  },
  start : function() {
    var self = this;
    self.show();
    setTimeout(function() { self.start(); }, 1000);
  }
};

ticker.start();

Notice that every time start is called, it is called using the method invocation pattern and we always save the object it’s called on in a local variable called self.

Constructor invocation

The third way of calling a function is using the constructor invocation pattern. The first point to make here is that you must use the new keyword when calling the function.

var Person = function(lastName, firstName) {
  this.firstName = firstName;
  this.lastName = lastName;
};

Person.prototype.print = function() {
  var name = this.lastName + ", " + this.firstName;
  console.log(name);
};

var me = new Person("Bucknall", "Julian");
me.print();

Here I’ve declared a function called Person, created a method via its prototype object, and then called the function using new. What this does is similar to C#: it creates a new object based on the template I gave. Person is not a class, even though creating a Person object looks like you’re creating an instance of a class. In essence, the new keyword will create a brand new empty object, set its constructor to the function, and then call the constructor. The this variable will be set to this new empty object.

The final unusual thing about constructor invocations is that the newly created and initialized object is returned by default; you don’t have to code up a return statement explicitly.

The big problem about the constructor invocation pattern is that you sometimes forget to use the new keyword. Constructors are normal functions, there’s nothing in the language that marks them as being anything special, and so suddenly the call turns into a function invocation. And we know all about those: this points to the Global Object. In my example: calling Person without new will create a two new properties on the Global Object (firstName and lastName), return and set me to undefined, and then crash on the next statement since undefined certainly has no method called print.

There is a bit of a hack that can get round this for you. Define your constructors like this, and you’ll avoid the problem of forgetting to use new.

var Person = function(lastName, firstName) {
  if (!(this instanceof Person)) {
    return new Person(lastName, firstName);
  }
  
  this.firstName = firstName;
  this.lastName = lastName;
};

In other words, if the this parameter is not an instance of Person assume that the caller forgot the new keyword and construct a new object properly and return it. If not, just proceed as normal for a constructor.

Apply invocation

The final way to call a function is to use the function’s apply or call methods. This is known as apply invocation. Yes, a function is an object, so it can have (and has) properties and methods of its own. Both apply and call work by calling the function on an explicit object that you supply. Arguments to the function are either passed one-by-one (call) or as an array (apply). (The way I remember which is which is to say Apply uses an Array because they both start with A.) The this variable is set to the first parameter of the call to call or apply. Here it is in action with our printer object from above:

var anotherPrinter = { callCount : 23 };
var someObj = { foo : 42 };

printer.log.call(anotherPrinter, someObj);
printer.log.apply(anotherPrinter, [someObj]);

All that’s happening here is that I’ve created an object (anotherPrinter) with a callCount field, and then applied the printer.log method to it, passing in some object to log.

Now playing:
Jarre, Jean Michel - Pleasure Principle
(from Geometry Of Love)

I was answering a JavaScript question on stackoverflow when a common usage scenario presented itself, one with a subtle gotcha that could catch you out. Perfect for a quick blog post. (Note: you could also view this post as an adjunct to my popular JavaScript callback posts (I, II, III).)

photo © 2006 Judson Dunn | more info (via: Wylio)My solution to the problem involved adding some extra precondition code to an existing event handler. The event was the plotclick event of the jQuery Flot charting library, so the original event handler code looked like this:

  $("#chart").bind("plotclick", function (event, pos, item) {
    // respond to the click 
  });

Pretty easy stuff. However in my solution I wanted to enhance the event handler so that some preconditions were checked and, if they passed, the original code could be executed. Simple enough: just add the preconditions to the code – which is what I did for the answer.

  $("#chart").bind("plotclick", function (event, pos, item) {
    if (item) {
      var dataPoint = item.series.data[item.dataIndex];
      if (dataPoint[2]) {
        // respond to the click 
      }
    }
  });

For one chart, meh, not a problem. Make the change and move on. For several, it gets a little clunky; all those complicated bits of cut-n-paste. What would be better would be to wrap the original function – somehow – and then call the wrapper. In other words, in my mind I was thinking of something like this:

  $("#chart").bind("plotclick", wrap(function (event, pos, item) {
    // respond to the click 
  }));

So that the minimal amount of change would be required. This would also work if the event handler were not an anonymous function.

What would this wrap function look like? Well, it takes a function with the required signature (that is, takes three parameters) and returns another function, the event handler, that is also of the required signature and that calls the original function. (Call these the wrapper and the wrapped.)

  var wrap = function (originalHandler) {
    return function (event, pos, item) {
      // extra stuff
      originalHandler(event, pos, item);
    };
  };

There is, however, one small problem with this code. I will admit that the first time I wrote it I missed the issue, and it was only through testing that I discovered the bug, so it’s not glaringly obvious.

I’ll stop a moment for you to think about it.

Found it? Give yourself a bonus point if you did. The problem is the this variable, the context of the wrapper, is not passed on to the wrapped. As written, the call to originalHandler is a function invocation, and the this variable inside the function will be the global object, not the context passed in for the wrapper function. With jQuery, the context will be the DOM element for which the event was triggered, and my code just blithely throws that away.

Let’s rectify that right now:

  var wrap = function (originalHandler) {
    return function (event, pos, item) {
      // extra stuff 
      originalHandler.call(this, event, pos, item);
    };
  };

So, going back to my particular case, I’d have:

  var wrap = function (originalHandler) {
    return function (event, pos, item) {
      if (item) {
        var dataPoint = item.series.data[item.dataIndex];
        if (dataPoint[2]) {
          originalHandler.call(this, event, pos, item);
        }
      }
    };
  };

So, I’d say the takeaway from this blog post is that—yet again—the fundamental concept that functions are objects (that is, you can pass them around, and create functions that return functions), and that you should be careful if you do so that you take care of the this variable, if needed.

In the previous two installments (one, two) we explored the use of callbacks through creating a mapp function for arrays (so called because the latest JavaScripts have a native map method already), and through creating a mapAsync function where the work is done asynchronously rather than serially. The reason for this was so that we could avoid triggering the browser’s “script running a long time” warning and, also, more importantly, provide the user with a responsive UI.

photo © 2007 sputnik | more info (via: Wylio)In this final part I just want to tidy up the mapAsync method. When I left it last time,the function would process each element using a delay. This is, in all probability, way too much work and way too slow. We could potentially do more work each cycle without inconveniencing the user and thereby reduce the number of delays we have to go through. But how much work? How long do we have? Jakob Nielsen says that

“0.1 second is about the limit for having the user feel that the system is reacting instantaneously, meaning that no special feedback is necessary except to display the result.”

OK, then, 100 milliseconds it is. Actually, thinking about it, that leaves no time for maneuver and so I’ll go for half that for the mapAsync method.

So, what we’d like to do is process as many elements as we can in 50 milliseconds (instead of just processing the one) and then recurse using a delay for the next batch. We therefore need the ability to time our processing.

JavaScript comes with the Date class. If you new up a Date, what you get is a variable containing the current date/time, much as DateTime.Now does in C# and .NET. What we’ll do is get the start time and then start processing as many elements as possible. For each element we’ll process it, then get the current time. If the current time minus the start time is less than 50ms, round the loop we go again. Unfortunately, we can’t just subtract one Date from another, the minus operator only works for numbers. However all is not lost: if we convert a Date to a number, we get the number of milliseconds from some base Date. And to convert? Just use the unary plus operator. Here’s an example:

var start = +new Date();
do {
  // work
} while ((+new Date() - start) < 50);

We get the current date/time as the number of milliseconds by newing up a Date and then converting it to a number by use of the unary plus. We then enter a do..while loop, and continue round doing work while the current date/time minus the start time is less than 50. Pretty easy, no?

Incorporating it into the current version of mapAsync is fairly mundane:

Array.prototype.mapAsync = function (process, done, context) {
  var i = 0,
      result = [],
      last = this.length,
      self = this,
      processAsync = function () {
        var start = +new Date();
        do {
          if (i in self) {
            result[i] = process.call(context, self[i], i);
          }
          i++;
        } while ((i < last) && (+new Date() - start) < 50);
        console.log("*"); // just for showing progress
        if (i === last) {
          done.call(context, result);
        }
        else {
          processAsync.delay(10);
        }
      };
  processAsync();
};

Of course, there’s a bit more to that inner loop condition since we also want to break out if we manage to process the final element. I’ve thrown in a logging statement after the loop for now, just to show that we’re nicely chunking the work and still performing several delayed calls to processAsync. We’ll delete it when we’ve shown it working.

Of course, my little example of an 8-element array just isn’t going to cut the mustard with this new code, so let’s go for broke and use a 100,000 element array:

var myArray = [];
for (var i = 0; i < 100000; i++) {
  myArray[i] = i;
}

myArray.mapAsync(function (element, index) {
  return "<" + index.toString() + ": " + element.toString() + ">";
}, function (a) {
  console.log("done");
  delete myArray;
});

All the completion callback does this time is to log “done” (printing the array will overload the console – I know because I did it) and delete the original array – it is fairly big after all. When I run this code in Firebug, I get this:

*
undefined
*
*
*
*
*
*
*
*
*
done

Again, the “undefined” at the top is Firebug printing the return value of calling mapAsync. As you can see, it chunked the 100,000 element array into 10 delayed calls, roughly 10,000 elements per call. Or, if you like, I managed to process 10,000 elements in 50 milliseconds, which ain’t too shabby.

That’s it for this series on callbacks. I hope it proved useful. Remember: if you want to use this mapArray method (I use an MIT license, so go for it), do take out the logging statement in the middle.

(This JavaScript callback series: part I, part II, part III.)

Last time, we wrote a map method for arrays (which I had to call mapp, so that we didn’t clash with the native version present in many browsers). To use the map method, you have to provide a callback function that would be called for every element in the array.

The first change I want to make today is to allow for missing elements in the array. In that case, the callback shouldn’t be called. Here’s the obvious way of implementing this change:

Array.prototype.mapp = function (process, context) {
  var i,
      result = [],
      last = this.length;
  for (i = 0; i < last; i++) {
    if (this[i]) {
      result[i] = process.call(context, this[i], i);
    }
  }
  return result;
};

var myArray = [2, 3, 5, 7, 11, 13];
myArray[7] = 19; // missing out myArray[6]
console.log(myArray); 

var newArray = myArray.mapp(function (element, index) {
  return "<" + index.toString() + ": " + element.toString() + ">";
});
console.log(newArray);

Since the seventh element is missing the expression this[6] will resolve as false and the if block won’t be executed. Unfortunately there are five other values that an existing element could have that will also evaluate as false: false, 0, NaN, the empty string, and null, all of which might appear in a real array. So this first cut just won’t work.

Another way is to expressly compare to undefined, like this:

    if (this[i] !== undefined) {
      result[i] = process.call(context, this[i], i);
    }

This works with the usual caveat that someone could have set undefined to some actual value. In which case we could use (void 0) instead (the void operator returns undefined for any operand), or we could enter (typeof this[i] !== "undefined") as an alternative.

Yuk, how about some proper JavaScript idiom? We’ll use the in keyword, it’s not just for the for..in statement:

    if (i in this) {
      result[i] = process.call(context, this[i], i);
    }

There. Much more legible.

Now we’ve got that sorted out, suppose that the array we’re mapping is large or that the processing for each element of the array is lengthy. We could be in danger of triggering the browser’s “script is taking too long” warning if we just blithely used the mapp method no matter what. What should we do?

photo © 2005 Jason | more info (via: Wylio)Let’s explore how we can split up the work done by the mapp method. First, though, it behooves us to understand why the browser might put up a warning dialog saying a script is taking too long. In essence, all of the JavaScript code on a page executes in one thread. Indeed JavaScript doesn’t have any way of spinning off other threads to do work. Since the one and only thread is also the UI thread, it means that a long-running piece of code would freeze the entire UI of the page. Not a good experience at all, which is why the browsers have a monitor to check that events are still flowing through the message pump. If a piece of code takes too long, the events are no longer being processed and after a given length of time, the browser interrupts the interpreter and puts up the warning dialog.

So, given all that, how can we split up our code so that the message pump still gets processing time? The answer is to use setTimeout. What this function does is to set a function executing after a certain length of time has passed. You pass both the function to execute (it’s a callback, of course) and the time to wait to setTimeout. What happens under the hood is that these requests are queued and some process pushes the callback onto the message loop after the timeout period has expired. At which point, of course, the function executes. (The same kind of thing happens with AJAX calls: when the AJAX call returns, it pushes the callback onto the message loop to get executed.)

What we would like to do is to split up our processing into “chunks”, each of which won’t take long to execute at all. After each chunk completes it queues up the next chunk to execute using setTimeout. However, the timeout used is going to be very short; not a large time like a second, but in the order of a few milliseconds at most. Essentially we are executing the chunks asynchronously rather than sequentially or synchronously. In between each there’s a bit of breathing room for the message loop to do other stuff.

Here’s a new function that will help us.

Function.prototype.delay = function () {
  setTimeout(this, 10);
};

It’s defined as a method on the function prototype, so it’s available to all functions. All it does is to delay the execution of the function it’s called on by 10 milliseconds. Here’s a silly example of it in action:

var o = {
  count: 10,
  tick: function () {
    if (o.count--) {
      console.log("*");
      o.tick.delay();
    }
  }
};

o.tick();

What we have here is an object with a count property initially set to 10, and a method called tick. This method outputs an asterisk to the console and then it calls itself using the delay method we just wrote, delaying for 10 milliseconds. It does this 10 times by decrementing count down to zero. If you run this, you’ll get 10 asterisks one after the other really quickly. Nice.

Note though that the initial call to o.tick returns immediately. If you ran it in Firebug you would actually get this result:

*
undefined
*
*
*
*
*
*
*
*
*

What’s that “undefined” doing in there? It’s Firebug telling us that the initial call to o.tick has completed and it returned undefined. Then we get the asterisks from the setTimeout followed by setTimeout, followed by setTimeout, etc, etc, each one firing off the other. The point I want to get across is that the initial function call completes before the delays fire. Delaying like this means that we have to be careful and not assume that all of the work we’re trying to do is completed straightaway. If we are concerned about knowing when a chained asynchronous process like this completes, we shall have to provide a completion callback so it can be fired when all’s done.

Back to the next version of our mapp function. We’ll create a new map function, call it mapAsync, that will process the array in chunks. To make it easy to begin with, we’ll make each chunk big enough to process a single element. First of all, we shall have to add a new parameter: the completion callback, as I mentioned above (it would be nice to know when the function had mapped the entire array). Then we shall have to define an internal function that will be the equivalent of our tick method above, and we shall have to make sure it knows how far we’ve got into the array.

Enter a closure. Of course. I’m sure you were expecting it. Here’s the code:

Array.prototype.mapAsync = function (process, done, context) {
  var i = 0,
      result = [],
      last = this.length,
      self = this,
      processAsync = function () {
        if (i in self) {
          result[i] = process.call(context, self[i], i);
        }
        if (++i === last) {
          done.call(context, result);
        }
        else {
          processAsync.delay();
        }
      };
  processAsync();
};

Let’s take this slowly. First of all we declare the same three locals as before. Then I save the value of the this variable, that is, the array this method is acting on. (I like using the name self for this purpose.) Then I’ve declared a function and it is this function that’s going to be called through our delay mechanism. If you notice at the end of the mapAsync method, I kick it all off by calling processAsync() for the first time.

I want to stop here and ask you to consider that call. It’s known as a function invocation. I’m not calling processAsync on an object (there’s none to be seen), in which case it would have been a method invocation call. Since there’s no object on which it’s called, JavaScript will call it using the global object. Inside the function the this variable will be bound to the global object. And that’s why, when you now look at the implementation of processAsync, you can see why we need to save the value of the this variable from the outer function – we would have no other way to get at the array.

So, let’s take a look at that inner function. First of all it processes the current element, determined by the captured value of i. Yes, we’ve created a closure with the mapAsync function and all its local variables have been captured and are available to the inner processAsync function. Now we increment the counter and if we’ve reached the end of the original array, we can call the done callback, setting up the right context (that is, the this variable for done), and passing the resulting, mapped array. If we haven’t reached the end of the array, we call processArray again, but delaying it slightly.

Here’s the code that’ll test it:

var myArray = [2, 3, 5, 7, 11, 13];
myArray[7] = 19; // missing out myArray[6]
console.log(myArray);

myArray.mapAsync(function (element, index) {
  return "<" + index.toString() + ": " + element.toString() + ">";
}, function (a) {
  console.log(a);
});

Notice that we now have two anonymous functions acting as callbacks: the first will process each element and the second will log the value of the mapped array passed in, once all the elements of the array have been processed. In Firebug, I get this:

[2, 3, 5, 7, 11, 13, undefined, 19]
undefined
["<0: 2>", "<1: 3>", "<2: 5>", "<3: 7>", "<4: 11>", "<5: 13>", undefined, "<7: 19>"]

Again notice that the result of the call to mapAsync (that is, “undefined”) is logged before the mapped array is logged.

If you think about it, this mapAsync code is showing the use of many callbacks: there’s process, done, and there’s processAsync, which is passed as a callback to the setTimeout function. Yep, callbacks in JavaScript are used everywhere. Get used to them and the use of anonymous functions to define them.

Next time we’ll work on refining the chunks of code we execute at one time. Processing every element through a delay is a little too granular.

(This JavaScript callback series: part I, part II, part III.)

Now playing:
Erasure - Chorus
(from Pop!: The First 20 Hits)

As I’ve said pretty much from the very start of this series: functions are objects. You can pass them around in variables, pass them into functions as parameters, return them from functions, the whole nine yards. When you pass a function into another where it will be called, it’s generally known as a callback.

photo © 2007 Nonie | more info (via: Wylio)(Note: as usual I’m using Firebug in Firefox to run these examples. All browsers have similar development tools built-in or that are available as a download.)

Here’s a simple example. There’s nothing too complicated going on here: all we’re doing is passing a callback into the function that’ll get called once the function’s real work is done.

var printDone = function () {
  console.log("done");
};

var doSomeWork = function (whenDone) {
  // do some work here
  whenDone();
};

doSomeWork(printDone);

So, we’re declaring a function doSomeWork that takes a callback called whenDone as parameter. Once the function has completed, it calls the callback. In the statement at the end, I’m calling doSomeWork passing in the printDone function.

Now, I totally agree that this is a somewhat daft example. After all I could have just added a call to printDone after the call to doSomeWork, but at least it shows the basics. Many times, if not most times, developers won’t formally give the callback function a name like I just did, but instead use an anonymous function declared right there in the call.

var doSomeWork = function (whenDone) {
  // do some work here
  whenDone();
};

doSomeWork(function () {
  console.log("done");
});

Exactly the same effect, but this time we declare the function anonymously as a function literal. You should get used to this style: it’s used universally in all kinds of code.

Now that we’re used to how to declare and use callbacks, let’s up the ante a little. We’re going to write a map method for arrays. A map is a function that applies some kind of operation to each element of an array and returns the resulting values as another array. First of all, let’s write some code that’s specific but works, and then refactor it to make it more general. We’ll start off by writing a function that doubles every element in an array (which we’ll assume to contain just numbers) and returns the resulting array.

var doubler = function (a) {
  var i;
  var result = [];
  for (i = 0; i < a.length; i++) {
    result[i] = 2 * a[i];
  }
  return result;
};

var myArray = [2, 3, 5, 7, 11, 13];
console.log(myArray);

var newArray = doubler(myArray);
console.log(newArray);

Now we’ll refactor it into a method on all arrays. (Note: the JavaScript version in Firefox 4 already has a map method defined on arrays, so I’m calling mine —unimaginatively, perhaps – mapp().)

Array.prototype.mapp = function () {
  var i;
  var result = [];
  for (i = 0; i < this.length; i++) {
    result[i] = 2 * this[i];
  }
  return result;
};

var newArray = myArray.mapp();
console.log(newArray);

Notice that the call to mapp() uses the method pattern of function invocation, and therefore the this variable inside the method points to the array it was called on.

Now, for a generic map method, this is still very specific to doubling elements. But consider the code: we have the stuff that iterates through the array and we have the statement that gets called for each element. It’s this latter part we want to genericize. So, create a special local (nested) function that does the work:

Array.prototype.mapp = function () {
  var i;
  var result = [];

  var process = function (element) {
    return 2 * element;
  };

  for (i = 0; i < this.length; i++) {
    result[i] = process(this[i]);
  }
  return result;
};

And now we see that we can promote this local function into a parameter of the outer function: that is, a callback. And it gives us the form of that callback too: it takes one parameter and returns a new value.

Array.prototype.mapp = function (process) {
  var i;
  var result = [];
  for (i = 0; i < this.length; i++) {
    result[i] = process(this[i]);
  }
  return result;
};

var newArray = myArray.mapp(function (element) {
  return 2 * element;
});
console.log(newArray);

With this last step, the introduction of the callback, the mapp method has become general and we can use it for other transformations or mappings. Supply a callback that does the work, and invoke the mapp method.

var newArray = myArray.mapp(function (element) {
  return "<" + element.toString() + ">";
});
console.log(newArray);

Of course, now that we have a generic mapp() method we can add sanity checks, start to optimize it, or maybe alter the signature of the callback function we accept. For now, let’s make the callback function not only get called with the element in question, but also its index. I also want to call it in such a way that we can pass in the value that the this variable inside the callback should point to.

Array.prototype.mapp = function (process, context) {
  var i, 
      result = [],
      last = this.length;
  for (i = 0; i < last; i++) {
    result[i] = process.call(context, this[i], i);
  }
  return result;
};

var newArray = myArray.mapp(function (element, index) {
  return "<" + index.toString() + ": " + element.toString() + ">";
});
console.log(newArray);

A quick note on the code is in order. I’m calling mapp() without a second parameter. JavaScript will then set the context parameter to undefined. If context is null/undefined, it will default to the global object in the call to call(). (Recall the call method calls the function and sets its this variable to the first parameter.) Also I’m moving the repeated access to the length property out of the loop and saved its value to a local variable: it’s slightly faster.

Next time, we’ll make a slightly different version of the mapp() method to continue our exploration of callbacks.

(This JavaScript callback series: part I, part II, part III.)