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:
- Each function [caller & called] must be declared as function* (so it can yield)
- 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
- 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).
async/awaitandPromise.all()– Amosamount