What is the best method for managing an event loop during nested or recursive calculations?

When it comes to breaking a computation and releasing using setTimeout(), most examples seen involve having a shallow call stack. But what about scenarios where the computation is deeply nested or mutually-recursive, like in a tree search, with plenty of context in the stack?

It would be perfect if JavaScript had a function that could encapsulate the 'current continuation' (the current call-stack), place it on the Event Queue, and return/throw/call back to the top-level event loop. This way, other events could run, and then the computation could pick up right where it left off. I'm looking for a simple way for a function to voluntarily 'yield' control, allow events to catch up, and then resume from where it paused. Ideally, this would not require rewriting every function in the call-chain.

However, it seems like such a feature does not exist...

  • As someone familiar with Scheme, I anticipated something similar to call/cc, but haven't come across it.
  • setTimeout() returns control [but only 1 level up] and restarts some other computation (without continuing the implicit current-continuation unless we fully commit the application to CPS...)
  • 'yield' boxes the continuation of the current function/stack-frame for possible restarting, but only goes one level up. (yield is comparable to: return/cc instead of call/cc)
  • 'throw' can throw far up the stack but lacks a way to restart the computation from the throw point (as far as I know; something akin to 'throw/cc' might be needed)

I have attempted to create a partial solution using 'yield', but it's awkward, necessitating every function on the stack to (a) be declared as 'function*' and (b) contain boilerplate code around each downward call to propagate a yield and resume with next()

Q: Is there a method to accomplish this in JavaScript without modifying all functions in the call chain?

Answer №1

Let's explore an alternative solution that may not have been considered: utilizing Promises, specifically the syntax sugar for managing promises known as async/await.

Implementing your allowEventLoop() function is straightforward with a Promise:

function allowEventLoop () {
    return new Promise((resolve,reject) => setTimeout(resolve, 0));
}

When you need to pause the current execution and trigger the event loop, simply call:

await allowEventLoop();

Below is an example of a basic recursive descent parser using this function (please note the code is in JavaScript but can be easily adapted to TypeScript):

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;
}

The logic of the recursive function remains largely unchanged. The key difference is that the function now returns a Promise of the result.

By using async/await, you essentially bypass the call stack and instead create a chain of .then() calls. Although the call stack appears shallow, it actually constructs a complex .then() chain dynamically. This approach mimics traditional call stack recursion.

Promises handle the queue of functions invisibly, serving as a design pattern for managing Continuation-Passing-Style (CPS) code. This mirrors how the call stack organizes the function queue for return. Hence, the experience feels familiar.

Answer №2

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:

  1. Each function (both caller and called) must be declared with function* to enable yielding
  2. 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.

  1. 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).

Answer №3

To illustrate a different approach, let's consider the following alternative method combining data-flow and function-queue concepts: To ensure a concise call-stack, break down the application into tasks (functions that do not involve recursion). When faced with a recursive call, opt for using:

callLater(()=>recursiveTask(arg1, arg2, ...))
and then simply return. By employing callLater, the closure [data and continuation] is placed on the queue for orderly processing by the top-level.

For example, in a tree search scenario, at level N, tasks are queued to handle nodes at level N+1, along with a task to gather and merge outcomes before returning. The ultimate task in the queue should produce the final result. This 'final' task may contain logic such as:

if (queue.length > 0) callLater(finalTask)
to place itself at the end of the queue until all subsidiary tasks have been executed and ceased adding new tasks to the queue. [Alternatively, one could utilize Promises and trigger the finalTask via Promise.all(...)]

Moreover, the provided code snippet includes a timer within the loop to execute multiple tasks until reaching a specified threshold (and then returning 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))
}

Similar questions

If you have not found the answer to your question or you are interested in this topic, then look at other similar questions below or use the search

npm fails during the build process due to webpack issues

I find myself lost in trying to pinpoint the right question to ask, but I am encountering a failure while running npm run build. > <a href="/cdn-cgi/l/email-protection" class="__cf_email__" data-cfemail="395a5655564b14564b5e585750435c4b790817091709" ...

The OutlinedInput component from Material-UI seems to be struggling to display the startAdornment

Below is the code snippet. The start adornment is not displaying in the textfield, and there is no text appearing on the label. <InputLabel>Mobile Number</InputLabel> <OutlinedInput variant="outlined" ...

"Enhance your website with a sleek Bootstrap navigation system featuring dividers and

Need help with creating a Bootstrap nav menu similar to this design made in Photoshop? Wondering about the best way to position the logo and create dividers between menu items like shown in this image. Here's the HTML code currently being used: & ...

Whenever I attempt to trim my integer within a for loop, my browser consistently becomes unresponsive and freezes

I am facing an issue with my code that generates alcohol percentage, resulting in values like 43.000004 which I need to trim down to 43.0, 45.3, etc. However, whenever I try to use any trim/parse functions in JavaScript, my browser ends up freezing. Below ...

SonarLint versus SonarTS: A Comparison of Code Quality Tools

I'm feeling pretty lost when it comes to understanding the difference between SonarLint and SonarTS. I've been using SonarLint in Visual Studio, but now my client wants me to switch to the SonarTS plugin. SonarLint is for analyzing overall pr ...

Alter the entity type when passing it as a parameter

Trying to alter the Entity type, I am invoking a function that requires two parameters - one being the entity and the other a location. However, when trying to assign a Type for the first entity, it throws an error: Error: Argument of type 'Node<En ...

Updating text color with Ajax response value

I need assistance with updating the text color of a sensor value displayed using html/ajax. Currently, the sensor value is being displayed successfully, but I want the text color to change based on the value. Here's an example: if value < 50 then f ...

Deactivating PrimeNG checkbox

I am currently facing an issue with disabling a PrimeNG checkbox under certain conditions by setting the disabled property to true. However, whenever I click on the disabled checkbox, it refreshes the page and redirects me to the rootpage /#. To troublesh ...

File or directory does not exist: ENOENT error encountered when attempting to access 'distrowserindex.html'

Upon executing ng deploy --preview, an error is encountered: Error: ENOENT: no such file or directory, open 'dist\index.html' at Object.openSync (fs.js:457:3) at readFileSync (fs.js:359:35) Despite attempting various online tutorial ...

The WebSocket function is returning undefined even though it successfully fetches the user; however, the user is

I've been experimenting with a websocket to retrieve user information. When I establish the connection and send messages to receive the data, it returns undefined when I try to use that information elsewhere. However, if I run console.log within the ...

PHP cannot be utilized within the script tag

I'm currently using JavaScript to display an error message If a user inputs incorrect information and I add the following code: <?php $_POST["usernamereg"] ?> = usernamereg; the alert function stops working. However, if I remove this code, t ...

The rendering of the input dropdown control in Angular JS is experiencing difficulties

I am currently using your Angular JS Input Dropdown control, and I have followed the code example provided on your demo page in order to implement the control on a specific page of my website built with PHP Laravel. However, I have encountered an issue dur ...

The elegant scroll-bar (whether directive-based or not) seems to be having trouble functioning within the ng-view

I am looking to add a stylish scroll bar to a paragraph that is located within the ng-view. My module code appears as follows: var myweb = angular.module('myweb' , ['ngRoute', 'perfect_scrollbar']); myweb.config(function($ro ...

Using JavaScript, what is the process for getting the value of a child node within Firebase

var ref = firebase.database().ref("games/" + gameId + "/patterns"); ref.on("child_changed", function(snapshot){ var pattern = snapshot.key; console.log(pattern); }); Currently, the code snippet above only logs the key. But how can I extract the player ...

Tips for displaying JSON data by formatting it into separate div elements for the result object

Having recently started using the Amadeus REST API, I've been making AJAX calls to retrieve data. However, I'm facing a challenge when it comes to representing this data in a specific format and looping through it effectively. function showdataf ...

Setting key-value pairs in TypeScript objects explained

I encountered an issue with setting key/value pairs on a plain object. type getAObjectFn = <K extends string, V>(k: K, v: V) => Record<K, V> const getAObject: getAObjectFn = (k, v) => { return { [k]: v } } console.log(getAObject ...

Creating code for both the PC and mobile website by utilizing the user agent

I need to customize the CSS for my website, and I have a specific question: If a user is accessing my web page via a computer, the CSS should be as follows: <link rel="stylesheet" href="/pc.css" type="text/css" media="all" /> However, if they are ...

What could be causing my CSS and Bootstrap.css styles not to be implemented on my webpage?

While working on my Ruby on Rails application, I am trying to customize the design to resemble (which can be downloaded from ). However, I am facing an issue where the style sheets are not being applied. I have moved the style sheets from the bootstrap/c ...

Encountering difficulties with installing bootstrap-vue

While attempting to integrate Bootstrap-Vue into my project that includes Vuex, Vue-Router, TypeScript, and Babel, I encounter an error in the browser. To replicate docker run -it --rm -p 8080:8080 node:17.7.2-alpine yarn global add @vue/cli vue create ...

Jquery plugin experiencing a malfunction

I am encountering an issue with my custom plugin as I am relatively new to this. My goal is to modify the properties of div elements on a webpage. Here is the JavaScript code I am using: (function($) { $.fn.changeDiv = function( options ) { var sett ...