Sleep sort in JavaScript and closures

JavaScript GuideThere is this "genius" sorting algorithm called "sleep sort". I don't know what came to my mind, but I decided "let's do it in javascript!". I thought that it won't take more than 2 minutes. Starting with such wrong and over confident assumption, it was a journey into the details of javascript which I had never bothered to pay much attention to. I learnt quite a few things on the way and will share the same in this blog.

Here is the code which I wrote off :

1
2
3
4
5
array = [1, 9, 4, 8, 2, 3, 6];

for (i = 0; i < array.length; i++) {
    window.setTimeout ("console.log(array[i])", array[i]*1000);
}  


What the code was supposed to do was, for each integer in the array, wait for those many seconds and then print that integer. So, the integer 9 will be logged into the console after 9 seconds while the code will log 2 into the console after 2 seconds.     

Here is what it logged into the console :
undefined
undefined
undefined
undefined
undefined
undefined
undefined
What?! said I, totally baffled and and taken by surprise. I thought that there is some problem with the array so, in the for loop, I changed array.length to array.length - 1. Now, all the undefineds in the output were replaced by 6s.

What was happening here? The line 4 in the code was telling the javascript engine that after array[i] number of seconds, evaluate the javascript code console.log(array[i]). So it was here, that all the logic was going for the toss then! In two shakes of a duck's tail, the for loop would come to a stop. Then, after a comparatively long time (1 second) the first timeout will get over and the code console.log(array[i]) will get evaluated. But wait! by this time, the value of i is 7 and each of those timeouts will end up evaluating console.log(array[7]). And we know that as the array contains only 7 elements and array[7] means the 8th element in the array, there is no doubt that undefined will be logged into the console! Mystery solved!

I read up a bit on the web about the setTimeout function and came to know that it is a bad practice to use a string as the first parameter of setTimeout for various reasons - mostly the association with eval . The syntax of setTimeout as given there is :
setTimeout (function_object, timeout_in_milliseconds, param1, param2, param3.....)
where the arguments after timeout_in_milliseconds are all optional. For example,
window.setTimeout(foo, 5*1000, 99, 42)
will make a function call to foo as foo(99, 42) after 5 seconds.

So I changed the code to following :
1
2
3
4
5
6
7
8
9
array = [1, 9, 4, 8, 2, 3, 6];

function log_value_in_console (value) {
    console.log (value);
}

for (i = 0; i < array.length; i++) {
    window.setTimeout (log_value_in_console, array[i]*1000, array[i]);
}
Here, right at the time of setting the timeout, line 8 was telling the javascript engine. "After array[i] seconds, execute the function log_value_in_console with array[i] as its parameter". Mind you, the value of array[i] will be calculated at the same time when the timeout is set. (after all, they are parameters passed to the function window.setTimeout and as usual, they will be evaluated when you are passing them).

Quite as expected, this is what it logged into the console :
1
2
3
4
6
8
9
Yey! It worked! But on the same page where I read about setTimeout, there was a note saying "passing additional parameters to the function does not work in Internet Explorer." Alas! Why did you guys at mozilla even add that then? Whatever...

So now the problem was to do sleep sort with just two parameters to the setTimeout function. Basically, first argument needed to be a function which somehow knows what to log. Enter closures!

What is this closure anyway? Frankly, I don't know :P. What I understand is "a closure is like a zombie, a भूत!" closure is formed when a function returns (gets done with its execution) but still its scope, that is its internal variables and arguments passed to it (think of it as kind of a stack frame of that function) are not cleaned by the garbage collector. Such a scenario typically happens when the function returns another function and returned function needs to access the internal variables / arguments of the outer function. Apart from the fancy name which notoriously is name of a mathematical property also, there is nothing complex or voodoo about closures.

Using closures, I rewrote the code in following way, and as you might have guessed, it worked! :P
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
array = [1, 9, 4, 8, 2, 3, 6];

function make_logger_function (value) {
    function log_value_in_console () {
        console.log (value);
    }
    return log_value_in_console;
}

for (i = 0; i < array.length; i++) {
    window.setTimeout (make_logger_function(array[i]), array[i]*1000);
}
When the execution comes to line 11, it evaluates both its arguments, the second, as we all know returns  the number of milliseconds timeout after which, the first argument (which is function) should be executed. So what does the first argument evaluate to? It returns a function, which knows what value it has to log. Here, we can see closure playing its role. The function make_logger_function takes a value to be logged into the console and returns a function which, upon called, logs that value in the console.

8 comments :

  1. The thing with closures is that you create a new function by changing the environment around. You can think of a closure function as something made on the fly. So you can rewrite your code like this:

    array = [1, 9, 4, 8, 2, 3, 6];
    for (i = 0; i < array.length; i++) {
    window.setTimeout(function() { return console.log(array[i]); }, array[i]*1000);
    }


    It is like you are creating a new function each time. Using closures with setTimeout is pretty common I think.

    Also, I suggest you post these to our hackers' group also :). Just copy paste and put the banner 'Hack a day' :D. I am sure lot of people will benefit and you too will learn from them.

    Reply Delete
  2. yeah I could have done stuff directly in the call to window.setTimeout as you pointed out. But that would have turned very ugly.
    The code you showed, as it is, unfortunately does not work. The expression you are passing as first argument to setTimeout _is_ a function. There is no closure involved. It will try to log array[i] at the time of the actual call (after the timeout) and by that time, array[i] will always evaluate to undefined.
    If at all you want to do it in the same line, you _still_ have to do two functions, which will simply end up making it ugly. Here is what it will look like :
    window.setTimeout(function (val){return (function() { console.log(val); });}(array[i]), array[i]*1000);
    All we ended up doing is make the named functions into lambda functions.
    If you are fine with me posting a link with brief description of what it is all about, I will send this to hackers' group under "Hack a day", because the thing looks pretty ugly when i put it in the mail.

    Reply Delete
  3. And yeah, about closures being used in setTimeout, I haven't done any serious coding in javascript. And whatever I had done, the setTimeout("string_to_eval", millisecs) format was sufficient. I would blame w3schools (and myself obviously) for this x-(. They never mentioned that it is not the preferred way and there are other, better, more powerful and faster methods of doing setTimeouts. And I guess I am not alone here, a lot of people use w3schools as one stop reference for all stuff related html, css, js, json and what not.

    Reply Delete
  4. Yes, you are right. Anyway, check this page:
    setTimeout with Function References

    It talks about the same thing you wrote.

    Reply Delete
  5. http://api.jquery.com/jQuery.each/ would've solved the issue cleanly :)

    And re: w3schools: http://w3fools.com/

    Reply Delete
  6. You really need to find better ways of spending your time... :P

    Reply Delete
  7. @Pavan : Guidance will be highly appreciated... :P

    Reply Delete

Post a Comment

Note: Only a member of this blog may post a comment.