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.

Answer 2

We want to enable event processing during long-running, mutually recursive function calls. (for example, a recursive tree search) After a certain depth or time, the search wants to voluntarily suspend execution to allow the top level Event Loop to run (handle mouse/key events, repaint graphics, etc)

The ideal would be a system-level function to runEventLoop() which 'yield' the current computation, put its own continuation on the event queue, and throw control to the system EventLoop.

It seems that Javascript provides only partial solutions for this:

• 'setTimeout()' will put a function on the event queue [but not the current continuation]
• 'yield' will suspend the current continuation, but not put it on the event queue. And 'yield' returns a value to the Generator's caller one level up the call stack. So that caller must already have the 'continuation' in form of the Generator.

We also note that although an uncaught 'throw' will return control to the top-level, there is no way (TIKO) in JS to recover & restart the 'thrown' computation. (from top level through the mutually-recursive calls to the voluntary 'yield')

So: to return control from the voluntary yield, up through the nested or mutually-recursive functions, all the way to the system EventLoop, we do 3 things:

1. Each function [caller & called] must be declared as function* (so it can yield)
2. Each function [caller] must test whether its [called] descendant suspended, and if so, yield itself to propagate the 'yield' to the top level:

    let result, genR = calledStarFunction(args);
       while (result = genR.next(), !result.done) yield;
       use (result.value)

Note: #2 cannot usefully be wrapped in a function... because that function would be subject to #1, and the caller of that function is subject to #2

3. At the top-level, use setTimeout(() => genR.next()) return to the JS EventLoop and then restart the chain of suspended functions.

[before #2 was obvious, I wrote this typescript code, now 'yieldR' is inlined, as shown above]

    /** <yield: void, return: TReturn, yield-in: unknown> */
    export type YieldR<TReturn> = Generator<void, TReturn, unknown>
    /**
     * Top-level function to give control to JS Event Loop, and then restart the stack of suspended functions.
     * 'genR' will restart the first/outermost suspended block, which will have code like *yieldR()
     * that loops to retry/restart the next/inner suspended function.
     * @param genR 
     * @param done 
     */
    export function allowEventLoop<T>(genR: YieldR<T>, done?: (result: T) => void): void  {
      let result = genR.next()
      if (result.done) done && done(result.value)
      else setTimeout(() => allowEventLoop(genR, done))
    }
    /** 
     * Return next result from genR. 
     * If genR returns an actual value, return that value
     * If genR yields<void> then propagate a 'yield' to each yieldR up to allowEventLoop(); 
     * 
     * This shows the canonical form of the code.
     * It's not useful to actually *call* this code since it also returns a Generator,
     * and the calling code must then write a while loop to handle the yield-vs-return!
     */
    export function* yieldR<T extends object> (genR: YieldR<T>, log?:string) {
      let result: IteratorResult<void, T>
      while (result = genR.next(), !result.done) yield
      return result.value
    }

Note: most documented usage of function* are to create a Iterator, a case where 'yield' provides the interesting/useful value, and 'return' signals when done. In this use-case that is inverted: yield gives a signal, but no interesting value, and 'return' supplies the interesting computational value.

Appeal to the JS Gods: Provide a function: runEventLoop() That transparently puts the current continuation (the full stack) on the event loop and returns control directly to the top-level. so all the other callers and the call stack do not need to be aware of the suspend/resume being done at the lower level.

After note: looks like there is a significant performance hit for using Generators like this. After inlining code to reduce nested Generators from 4 to 2, the code ran 10X faster. So maybe CPS or data-flow design may be indicated for complex/time-sensitive apps. (but still, it worked during dev/debug to get the kbd/graphics going)

Another note: Chrome imposes a minimum 'setTimeout' delay of 4ms; so if you compute for 1ms and then yield for 4ms that is slow and may explain the note above. It helps to compute the delta from last yield until Date.now() and yield only when that is greater than [20 -- 200 ms?] (depending on degree of responsiveness you need).

Answer 3

To reify the alternative (data-flow/function-queue) approach, consider this: To keep the call-stack short, divide the application into tasks (functions that return without recursion). If you would make a recursive call, then instead use: callLater(()=>recursiveTask(arg1, arg2, ...)) and simply return. callLater puts the closure [data and continuation] on the queue where the top-level can process it in turn.

So for a tree search, at layer N, you enqueue tasks to process the nodes at layer N+1, PLUS a task to gather and combine the results, then return. The final task enqueued should return the final result. That 'final' task will likely include something like: if (queue.length > 0) callLater(finalTask) so it puts itself to the end of the queue until all the other subtasks have been computed and have stopped adding tasks to the queue. [or maybe you use some Promises and trigger the finalTask with Promise.all(...)]

The code below also includes a timer in the loop, so as to run a number of tasks until a threshold is exceeded (and the return to the JavaScript Event Loop)

type FUNC<T> = ()=>T
const callQueue: Array<FUNC<any>> = []
function callLater(fun: FUNC<any>) {
  callQueue.push(fun)
}
function topLevel<T>(start: FUNC<T>, done?: (value: T) => void, threshold = 30, ms0 = Date.now()) {
  var dms: number
  while ((dms = Date.now() - ms0) < threshold) {
    let value = start()    // which may invoke callLater() to enqueue more tasks
    if (callQueue.length == 0) return done && done(value)
  }
  setTimeout(() => topLevel(callQueue.shift(), done, threshold))
}