How to run event loop when doing nested/recursive computations?

Question

The usual examples of how to break a computation and release using setTimeout() seem to rely on having a shallow (1-deep) call stack. But what about when you are doing a deeply nested or mutually-recursive computation (like a tree search) and you have plenty of context in the stack?

It would be ideal if JavaScript had a function that would encapsulate the 'current continuation' (that is: the current call-stack), put it on the Event Queue and return/throw/call back to the top-level event loop. (so other events would run, and then the computation would be restarted right where it left off). I'm looking for an easy way for a function to voluntarily 'yield' control, let events catch up, and then return control to where we left off. Preferably without re-writing every function in the call-chain.

But I can't find anything that does this...

• As a retired schemer, I'm expecting something like call/cc, but not finding it.
• setTimeout() will return control [but only 1 level up], and restart some other computation (but not the implicit current-continuation, unless we commit the entire application to CPS...)
• 'yield' will box the continuation of the current function/stack-frame, so it can be restarted, but yield only returns one level up. (yield is like: return/cc vs call/cc)
• 'throw' can throw way up the stack, but has no facility to restart the computation from the point of the throw (that I know of; need something like 'throw/cc')

I've built a semi-solution using 'yield', but it is klutzy, requiring every function on the stack to (a) be declared as 'function*' and (b) include boilerplate code around each call down to the next function [to propagate a yield and restart with next()]

Q: Is there a way to achieve this in JavaScript without instrumenting all the functions on the call chain?

Answer 1

I'll add an alternative solution that you seem to not have considered: Promises. Or more specifically the syntax sugar for handling promises: async/await.

Using a Promise it is simple to implement your allowEventLoop() function:

function allowEventLoop () {
    return new Promise((ok,fail) => setTimeout(ok,0));
}

Now whenever you need to suspend the current computation and run the event loop you just need to call:

await allowEventLoop();

Here's an example of a simple recursive descent parser using the above function (note: code in Js but it should be trivial to do this in Ts):

async function drawTree(node, indent) {
    if (!indent) indent = 0;

    let tree = `${'\t'.repeat(indent)}${node.name}\n`;

    await allowEventLoop();

    if (node.children) {
        for (let child of node.children) {
            tree += await drawTree(child, indent+1);
        }
    }

    return tree;
}

As you can see, very little is changed in the logic of the recursive function. It looks almost exactly the same as the plain synchronous version. The main difference is that your function now returns a Promise of the result.

When using async/await you basically skip the call stack. Instead what you are really doing is using a chain of .then() calls. So in reality the call stack is still 1-level deep but you are dynamically constructing a complicated .then() chain. In practice it feels like the usual call stack based recursion.

The queue of functions to execute is handled invisibly by Promises - which is essentially a design pattern for handling Continuation-Passing-Style (CPS) code. This is similar to how the call stack manages the queue of functions to return. This is why it feels the same.