## Questions on an improved CPS mechanism for JavaScript

To get right to the point, my main question is:

Is there any guarantee that setTimeout() calls will be executed in the order in which they are requested?

Discussion:

I believe I have made two improvements to the general CPS mechanism that was described in this forum by Anton van Straaten some time ago here. My main questions involve the 2nd adaption that I describe below.

As an amusement, I've been working on a JavaScript-based, client-side maze generator. In order to support very large mazes I've avoided recursion and adapted the aforementioned CPS mechanism in order to maintain responsiveness.

1. Using iteration instead of recursion in the loop() function. I found that the Safari browser allows such a small stack that the level of recursion made necessary caused the algorithm to run unacceptably slow.

2. To support nesting of continuations, the continuation function k() is called in the context of a setTimeout(). My implementation of the maze generator involves several passes across a multidimensional array (e.g., initialization, generation, rendering) each of which is a continuation of the previous step. I found the original example did not allow nested continuations since the hand-off to k() would normally be done before the previous stage had truly completed (i.e., before most of the setTimeout() requests had been handled).

The idea behind this change is that the setTimeout("k()", 0) would cause k() to be executed only after all the previous setTimeout requests had been handled. I'm making a huge assumption here I realize, which is that the calls to setTimeout are in essence serialized by the processor. Given the nature of the algorithm, it's guaranteed that the call to setTimeout for k() will happen after all the other setTimeouts requested by a particular stage, but does that actually guarantee that it will be *handled* after all the other requests? In my particular case it works well, but I don't know if this is just pure luck.

If there is a more general way to handle nested continuations (that does not rely on this potentially invalid assumption) I would appreciated hearing about it.

A somewhat simplified version of the iteration function I have employed in my code is shown here:

/*
* f    - a function that takes a state parameter and returns an updated state
* initial - the initial state
* done - the final state that indicates that iteration is complete
* k   - an optional continuation function that is called when processing is complete
*/
function iter(f, initial, done, k)
{
var max   = 50; // a reasonable number
var count = 0;

/* define the loop function that will manage the calls to f() */
var loop = function (state)
{
while((state = f(state)) != done) {
if (count < max) {
count++;
}
else {
count = 0;
setTimeout(function() { loop(state) }, 0);
break;
}
}

if(k && (state == done)) {
setTimeout(function() { k() }, 0);
}
}

/* call the loop function with the initial state */
loop(initial);
}


## Comment viewing options

### setTimeouts are properly serialized in all browsers

But if I read the code correctly, you don't need that. Each call to loop results in only one setTimeout, so you can only get a new setTimeout when the previous one is being handled.

### Damn, you're right...

Testing on a much slower machine exposes the real issue. Nesting the iter() calls is the fundamental issue (and is the case with the original mechanism).

In the example below assuming rows and columns are larger than the iteration size defined in iter(), the outer iter() will have returned and the continuation called while the inner iter() is still handling the setTimeout() calls.

/* Initialize 2D Array */
function initialize(2Darray)
{
iter( function(column) { return rowInit(2Darray, column) }, columns, k);
}

/* Initialize a row */
function rowInit(2Darray, x)
{
2Darray.cells[x] = new Array(columns);

iter( function(row) { return cellInit(2Darray, x, row) }, rows);

return x + 1;
}

/* Create a cell*/
function cellInit(2Darray, x, y)
{
2Darray.cells[x][y] = new cell();

return y + 1;
}
 By Jeffrey Winter at Mon, 2007-07-23 13:11 | login or register to post comments 
 
 
 Logs: Hack The Planet ; JavaLobby ; Daily Python-URL ; Daily WTF ; PHP everywhere ; (more) Wikis: WikiWiki ; Erlang ; Common Lisp ; Haskell ; Squeak ; Tcl ; Program Transformation