In order to facilitate event processing during lengthy, mutually recursive function calls (such as a recursive tree search), we aim to have the ability to pause execution voluntarily after a certain depth or time has been reached. This will allow the top level Event Loop to perform tasks like handling mouse/key events and repainting graphics.
An ideal solution would involve a system-level function called runEventLoop() that could 'yield' the current computation, place its own continuation on the event queue, and pass control to the system EventLoop.
It seems that Javascript only offers partial solutions for this scenario:
- The 'setTimeout()' function can add a function to the event queue, but does not handle the current continuation
- 'yield' can suspend the current continuation without adding it to the event queue. Additionally, 'yield' sends a value back to the Generator's caller one level up the call stack, requiring the caller to already have the 'continuation' in the form of the Generator.
Furthermore, while an uncaught 'throw' can return control to the top-level, there is currently no way in JavaScript to recover and restart the 'thrown' computation from the top level down through the mutually-recursive calls to the voluntary 'yield' point.
Therefore, in order to return control starting from the voluntary yield all the way up through nested or mutually-recursive functions to the system EventLoop, three steps must be taken:
- Each function (both caller and called) must be declared with function* to enable yielding
- The caller function needs to check if its descendant has 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: The second step cannot effectively be encapsulated in a function due to dependencies between functions.
- At the top-level, use
setTimeout(() => genR.next())
to return to the JS EventLoop and then restart the chain of suspended functions.
Prior to making the above steps clear, TypeScript code was written. Now, 'yieldR' has been integrated as outlined.
/** <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: While most documented uses of function* are centered around creating an Iterator where 'yield' provides value and 'return' indicates completion, in this case 'yield' acts as a signal without providing a meaningful value, while 'return' supplies the valuable computational output.
Plea to the JS Gods: We request a user-friendly function named runEventLoop() that seamlessly places the current continuation (full stack) on the event loop and immediately returns control to the top level. This would eliminate the need for other callers and the call stack to be aware of suspension/resumption occurring at lower levels.
Post-Note: Utilizing Generators as shown may introduce notable performance drawbacks. Reducing nested Generators from 4 to 2 resulted in a significant speed improvement by a factor of 10. Consideration of CPS or data-flow design might be advisable for complex or time-sensitive applications, although this approach effectively aided in development and debugging efforts related to keyboard and graphics operations.
Additional Note: Chrome enforces a minimum delay of 4ms for 'setTimeout'. Therefore, executing computations for 1ms followed by a 4ms yield could lead to sluggishness, offering a potential explanation for the aforementioned performance observation. To enhance responsiveness, calculate the time delta between the last yield and Date.now(), and yield only when this duration exceeds a specified threshold (e.g., 20-200 ms).