4 ms·

Ask HN: What is the name for this pattern?

I've found myself using this pattern in Javascript a lot lately (simplified to show its essential characteristics.) worker = function () { doSomeWork(); if (isDone()) finishUp(); else window.setTimeout(worker, 0); } The basic idea is to use window.setTimeout to schedule another execution of the worker function at the end of the current command queue. While it's not threaded, per se, if your "doSomeWork" functions are small enough, it may as well be for many applications. It allows you to write recursive operations in Javascript, without throwing the "too much recursion" error when the data gets big. And, while it's generally not as fast as straight iteration, it will avoid the "Script on this page is taking too long" error, and it doesn't lock the browser, so it "feels" faster. For operations that you can expect to be slow, or for doing a lot of different actions on a busy page, this pattern is great. The only problem is that I don't know what it's called, or if it even has a name. I saw a page by Douglas Crockford calling this "eteration", but I think that also means something else, and it never stuck anyhow. It's sort of like tail recursion, in that it is a sort of recursion that doesn't tie up the call stack, but unlike tail recursion, it doesn't track a return value, and it doesn't block the program while it's running. The closest analogy I can think of is putting sleep(0) in a loop so that the OS can step in. Does it already have a name? If not, got a suggestion?

senko 17y ago
I don't know if the pattern has a name, but equivalent of this in GTK+ (and QT, IIRC) desktop world would be called an idle callback (function scheduled to be run at the next iteration of the event loop). More info here: http://developer.gnome.org/doc/GGAD/sec-mainloop.html#Z63 http://developer.gnome.org/doc/GGAD/sec-mainloop.html#Z63
- IsaacSchlueter 17y ago
  That's interesting. Perhaps it could be called "idle recursion"?
  - jrockway 17y ago
    It's not really recursion. It is just a hack around not having a proper event loop. (Note that the function doesn't call itself, it merely adds itself to the event loop's to-do queue. This is a common pattern -- when writing IO watchers, for example, a watcher will often reactivate itself after it is done processing a chunk of input if it expects more input. If it doesn't expect more input, it simply doesn't add itself back.)
    - IsaacSchlueter 17y ago
      I see the distinction. It's not a blocking call, and can't return a value to the original caller, so it might not be correct to call it recursion. (Also, I'm using "recursion" rather loosely here—as we've seen in the recent Guido-vs-TCO debate, not all tail calls are tail recursion. Often when I'm using this pattern, the function isn't calling itself, but rather some other function, such as an event that fires another event when it's done.) So, maybe you're suggesting that the name should not include "recursion"? Still, it would be worthwhile to have a name for this pattern, no? What would you call it?
astrodust 17y ago
That's essentially re-queuing a repeating task, and the task is to process blocks of work incrementally until completion. This is not unlike what happens in an operating system that uses cooperative multitasking. You might consider a refinement of the pattern where doSomeWork() returns true if the work queue still has things left, or false if it is finished. As a matter of convenience, doSomeWork() should handle finishing as a final task to avoid the redundant isDone() check. A slight refactoring could be: processor = function() { if (processWork()) window.setTimer(processor, 0); }
- IsaacSchlueter 17y ago
  As I said, I simplified the expression to show all the relevant parts of the pattern in a single function. In a real application, either all the features of the pattern might be inline, or some might be delegated to other functions, or some might be omitted. Also, you can make it slightly more powerful by wrapping an object around it. I did this recently: var queue = (function () { var q = []; return { run : function run () { var fn = q.shift(); if (fn) setTimeout(function () { fn(); run(); }, 0); return this; }, push : function (fn) { q.push(fn); return this; } }; })(); so you can do stuff like this: queue.push( function () {...} ).push( function(){...} ).start();

senko 17y ago

I don't know if the pattern has a name, but equivalent of this in GTK+ (and QT, IIRC) desktop world would be called an idle callback (function scheduled to be run at the next iteration of the event loop). More info here: http://developer.gnome.org/doc/GGAD/sec-mainloop.html#Z63 http://developer.gnome.org/doc/GGAD/sec-mainloop.html#Z63

IsaacSchlueter 17y ago
That's interesting. Perhaps it could be called "idle recursion"?
- jrockway 17y ago
  It's not really recursion. It is just a hack around not having a proper event loop. (Note that the function doesn't call itself, it merely adds itself to the event loop's to-do queue. This is a common pattern -- when writing IO watchers, for example, a watcher will often reactivate itself after it is done processing a chunk of input if it expects more input. If it doesn't expect more input, it simply doesn't add itself back.)
  - IsaacSchlueter 17y ago
    I see the distinction. It's not a blocking call, and can't return a value to the original caller, so it might not be correct to call it recursion. (Also, I'm using "recursion" rather loosely here—as we've seen in the recent Guido-vs-TCO debate, not all tail calls are tail recursion. Often when I'm using this pattern, the function isn't calling itself, but rather some other function, such as an event that fires another event when it's done.) So, maybe you're suggesting that the name should not include "recursion"? Still, it would be worthwhile to have a name for this pattern, no? What would you call it?

astrodust 17y ago

That's essentially re-queuing a repeating task, and the task is to process blocks of work incrementally until completion. This is not unlike what happens in an operating system that uses cooperative multitasking. You might consider a refinement of the pattern where doSomeWork() returns true if the work queue still has things left, or false if it is finished. As a matter of convenience, doSomeWork() should handle finishing as a final task to avoid the redundant isDone() check. A slight refactoring could be: processor = function() { if (processWork()) window.setTimer(processor, 0); }

IsaacSchlueter 17y ago
As I said, I simplified the expression to show all the relevant parts of the pattern in a single function. In a real application, either all the features of the pattern might be inline, or some might be delegated to other functions, or some might be omitted. Also, you can make it slightly more powerful by wrapping an object around it. I did this recently: var queue = (function () { var q = []; return { run : function run () { var fn = q.shift(); if (fn) setTimeout(function () { fn(); run(); }, 0); return this; }, push : function (fn) { q.push(fn); return this; } }; })(); so you can do stuff like this: queue.push( function () {...} ).push( function(){...} ).start();