TypeScript / JavaScript Programming

Writing Interactive Compute-Intensive Programs for Web Browsers

Making Single-Threaded TypeScript / JavaScript Programs Responsive

I recently rewrote some decades-old algorithm demonstration programs from Java Web Applets to JavaScript. For the youngsters in the audience, back in the early days of the World Wide Web, web scripting meant writing Java, not JavaScript. Problems with security and performance led to Java being deprecated as a web page scripting language.

I had never programmed in JavaScript, but figured, how hard can it be? All interpreted languages are pretty much LISP with different syntax, and I cut my programming teeth on LISP!

The first thing I learned is that much of JavaScript is weird, confusing, and bad, but almost all of the bad parts are hidden and much new goodness is added by TypeScript. Microsoft Visual Studio Code makes it a snap to program in TypeScript, compile to JavaScript, and then debug code executing in Chrome. Very nifty!

The second thing I learned is that web browsers run JavaScript as a single thread. The desktop JavaScript interpreter, Node.js, supports “worker” threads, but multi-threading is not supported by Chrome. This meant that I could not adopt the approach used in the original Java versions of the programs where one thread ran the algorithm to be demonstrated and another thread handled interaction with the user. Everything had to be handled by a single thread.

This created a problem: the algorithms to be demonstrated were compute-intensive and needed to run to many minutes. If the code simply ran the original algorithm when a start button was clicked then the browser window would freeze until the algorithm completed. The demo could be viewed, but it could not be interacted with in any way — not even to allow a Halt button to be clicked. It would be the opposite of a responsive interactive program!

Multi-threading makes it easier to write interactive programs but is not absolutely necessary. In fact, the original Apple Macintosh operating system lacked any multi-processing or multi-threading! There are two basic approaches to writing interactive programs in a single-threaded environment. The first is for the main program to frequently make a system call that handles events such as mouse and keyboard clicks. The second is for the main program to be written in such a way that it runs for only a few milliseconds before returning control to the operating system along with a request to be executed by the operating system again in the near future. The second approach is the one we will illustrate with a demonstration program for backtracking and local search using the N-Queens problem.

Download my code from GitLab to follow along: https://gitlab.com/HenryKautz/n-queens.

You can run the demos from my university website: https://www.cs.rochester.edu/u/kautz/tsQueens/tsQueens.html.

The task is to place N queens on an NxN chessboard so that no two queens attack each other or determine that it is not possible to do so. In order to make the problem harder, one can optionally pre-place some of the queens in fixed positions on the board. This second version, called N-Queens Completion, can be shown to be NP-hard, which means there most likely exists no algorithm for the task that scales non-exponentially with N. N-Queens thus makes a good domain for demonstration heuristic search algorithms. After optionally resizing the board and fixing some of the queens, the user can select a backtracking search algorithm or a local search algorithm.

The local search algorithm is easy to make responsive to interaction. The high-level algorithm is to put a queen on each row in a random position, and then while there are attacking queens, try to move a queen to reduce the number of attacks.

We can turn this into a single-threaded interactive algorithm by replacing the while loop with an event handler. Here are the key parts of the code, where “. . .” indicates places where the code has been omitted for clarity. When the user clicks a button labeled “Local Search” its handler

function localSearchButtonHandler() {
    nqueens.StartLocalSearchSolver();
}

calls a method of the class nQueen

    StartLocalSearchSolver() {
        . . .
        this.RandomlyPlaceQueens();
        this.step = 0;
        HaltFlag = false;
        Schedule(LocalSearchSolverStepper);
        . . .
    }

which schedules the first iteration of the search. Schedule is just a utility function that uses window.setTimeout to set its argument to be run some number of milliseconds in the future. The value of the delay is controlled by other button handlers.

function Schedule(fn) {
    . . .
    window.setTimeout(fn, delay);
}

When LocalSearchSolverStepper runs it simply calls the nQueens method that makes one iteration of local search. It is needed because setTimeout requires its first argument to be a function, not a method.

function LocalSearchSolverStepper() {
    nqueens.LocalSearchSolver();
}

Now we turn to the nQueens method that does the work of local search. It first checks to see if the number of steps has exceeded a given cutoff, and if so, notifies the user that the search failed and returns. Otherwise, it creates a list of rows containing attacking queens. If there are none, it notifies the user that the search has succeeded and returns. If neither condition held, it moves one of the queens.

LocalSearchSolver() {
        if (this.step > this.cutoff) {
            // Failed to find solution before reaching cutoff
            TellUser('Local search failed after ' + this.step + 
                     ' flips.');
            return;
        }
        // Set R to a list of rows containing attacking queens
        . . .
        if (R.length == 0) {
            TellUser('Local search succeeded using ' + this.step + 
                     ' flips.')
            return;
        }
        // Randomly pick a row containing an attacking queen and
        // move the queen to a best possible column
        . . .
        // Get ready for next step
        if (HaltFlag) {
            TellUser('Local search solver halted at step ' + 
                     this.step + '.');
            return;
        }
        Schedule(LocalSearchSolverStepper);
    }

We saw HaltFlag in StartLocalSearchSolver where it was initialized to false. The handler for a button labeled “Halt” sets it to true if the user clicks on it. If at this point in the code HaltFlag has been changed to true, the user is notified that the search has been halted and the method returns. If HaltFlag remains false, Schedule is called to schedule the next iteration of the search.

This general pattern can be used for any algorithm that naturally takes the form of one long-running loop. You may prefer stylistic variations on the pattern, such as moving the test for HaltFlag to Schedule. The key elements are:

• A function runs one iteration of the main loop
• Using window.SetTimeout to schedule or reschedule execution of that function
• A global variable that can be used to halt the algorithm before it completes.

What if the algorithm does not take the form of a single loop? For example, suppose it is a recursive algorithm. Do we need to manually rewrite it to replace recursion by iteration? The happy answer is that we do not. We can use concept called a “generator” to make any algorithm run in short bursts. A generator is a special kind of object whose primary function produces not a single result but a series of results over time. A generator is initialized by being called just as one would call a function or method. Instead of returning a value, however, it yields a value. The yield statement suspends, rather than exits, the generator after saving its internal state. The next method of the generator then resumes execution until a yield is encountered again. Programmers familiar with the concept of an iterator in JavaScript will recognize that generators are a way to write iterators without the need to explicitly save the object’s state between iterators. Generators can also be viewed as a kind of continuation for readers familiar with that concept.

Generators have one additional feature that is special to their TypeScript implementation: they can also be called and return values just like ordinary functions! We will use this dual nature of generators in our code.

Let’s explore what happens when the user clicks the Backtracking Search button. The following bit of code

function backtrackingButtonHandler() {
    nqueens.StartBacktrackingSolver();
}

calls the StartBacktrackingSolver method in nQueens.

StartBacktrackingSolver() {
        HaltFlag = false;
        DoneFlag = false;
        . . .
        this.step = 0;
        . . .
        BacktrackGenerator = this.BacktrackSolver(0);
        Schedule(BacktrackingSolverStepper);
        . . .
    }

This time we are using two global flags, HaltFlag to indicate that the search has come to an end in any manner (success, failure, exceeding the backtracking limit, or the user clicking the Halt button) and DoneFlag to indicate that the search ended in success. The generator method BacktrackSolver is initialized and stored in the global variable BacktrackGenerator. Then, just as in the local search algorithm, a “stepper” function is scheduled to run. The stepper function is a bit more complicated than the one for local search because we choose to make it responsible for determining whether or not to reschedule itself to continue the search.

function BacktrackingSolverStepper() {
    BacktrackGenerator.next();
    if (HaltFlag) {
        if (!DoneFlag) {
            TellUser('Backtracking search halted after ' + 
                     nqueens.step + ' backtracks.')
        }
    }
    else {
        Schedule(BacktrackingSolverStepper);
    }
}

Now we turn to the search algorithm proper. The * in front of the method name tells the TypeScript compiler that we are defining a generator. The input parameter is the row number (starting with 0) where queens are to be placed. The method returns true if it succeeds in placing queens on that and all subsequent rows such that there are no attacks. The method yields true if it ready to suspend its execution to allow system events to be handled. The importance difference between return and yield is that return exits from the possibly recursive execution of the generator, while yield simply pauses the generator. The method returns false if cannot complete placing the queens or reaches a limit on the number of search steps to perform.

* BacktrackSolver(rowToPlace: number) {
        let status: boolean;
        if (rowToPlace >= this.Dim) {
            HaltFlag = true;
            DoneFlag = true;
            return true;
        }
        . . .
        yield true;
        // Try each column in this row, return true if any succeed
        for (let col = 0; col < this.Dim; col++) {
            if ( // A queen can be placed in this column 
                 // without attacks 
                . . . ) {
                // Put a queen in this column of rowToPlace 
                . . . 
                // Recursively fill out the rest of the board 
                status = yield* this.BacktrackSolver(rowToPlace + 
                                                     1);
                if (status) {
                    return true;
                }
                // That didn’t work, so remove the queen from col
                . . .
                this.step += 1;
                if (this.step >= this.cutoff) {
                    DoneFlag = false;
                    HaltFlag = true;
                    return false;
                }
            }
        }
        // All columns failed so return 
        if (rowToPlace == 0) {
            HaltFlag = true;
            DoneFlag = true;
            TellUser('Backtracking proves no solution exists.');
        }
        return false;
    }

The first thing the generator does is to check if it has solved the the puzzle. If rowToPlace is not less than N, then all of the rows must have been successfully filled out. Both DoneFlag and HaltFlag are set to true and the generator returns true.

Next, the generator yields true. This suspends its execution and makes it ready to continue when BacktrackGenerator.next() is called.

The generator then tries each column of the rowToPlace to see if it can put a non-attacking queen there. If so, it places the queen and then calls itself recursively. The call is made using yield *, which means that the ability to yield is delegated to the recursive invocation of BacktrackSolver. Therefore the yield true statement in the recursive invocation will save the state of the entire recursive call stack before suspending itself, and when BacktrackGenerator.next() is called, execution will continue from this innermost invocation of BacktrackSolver.

If this recursive call returns true, then the problem has been solved and the algorithm immediately returns true. Note that this true status will be passed up through all the recursive invocations of BacktrackSolver until BacktrackSolver(0) is reached. If the recursive call returns false, then the queen is removed and the counter this.steps is incremented; if this.steps reaches a maximum limit set by the user, the generator sets HaltFlag to true and DoneFlag to false and returns false. If the limit is not reached, the algorithm tries to place the queen in a different column. If none of the columns for RowToPlace succeed, then the algorithm returns false. Before returning, it checks if it is executing the top-level invocation BacktrackSolver(0); if so, then it must be the case that the queens problem has no solution, so a message is printed to that effect.

As with the local search algorithm, there are other ways one might organize the code of a compute-intensive recursive function to make it responsive. The key ideas are:

• The function is turned into a generator. The generator can be invoked as a generator proper or as an ordinary function or method.
• One or more yield statements should be inserted wherever the code would like to allow itself to be suspended.
• Recursive calls to itself are made by yield * commands. This uses the generator nature of the generator.
• Possibly recursive invocations of the function are exited by return, not by yield. This uses the function nature of the generator.
• The generator object is stored in a global variable, and its next() method called by a function that is scheduled to be executed by window.setTimeout
• A global variable can be used to stop the (function calling the) next method of the generator from being rescheduled

Here is a screen shot of the nQueens program in mid-flight:

If you found this post useful or have a better or cleaner way to achieve the same effects, please leave a comment!