Epistrophy: cooperative multithreading for the browser

In the previous article, we described an abstract timing and synchronization model that we now propose to implement in the browser using vanilla JS and no dependency. This implementation, named Epistrophy, has multiple goals: it is a proof of concept for the model (it should follow its evolution closely, so that additions and changes are reflected in the implementation) and a testbed for extensions and extrapolations; but should also be actually useful for authoring complex applications with non-trivial timing behaviour, with a particular focus on graphical user interfaces and other kinds of visuals, such as games or multimedia presentations.

Following the description that we gave of the model itself, we will structure the implementation around a tight, minimal kernel and a an extensible shell where features can be added without having to make changes to the internals: the kernel will implement the scheduler and the fibers, as well as the synchronization primitives Delay, Spawn and Join, plus a few others necessary for interfacing with the Web platform. The shell will build additional instructions such as Repeat on top of the kernel, and provide utilities and more complex timing patterns to improve the developer experience. The previous article was light on concrete details, so let’s begin with a live example:

This is an implementation of our old friend ABRO using Epistrophy. Before we explain all the details, here is the complete source code for this demo:

// Use the Epistrophy shell.
import { run, First } from "../lib/shell.js";

// Inputs and outputs.
const [A, B, R] = document.querySelectorAll("button");
const O = document.querySelector("span.O");

// This starts the scheduler with a main fiber.
run().

    // Add instructions to the fiber, starting with the outer loop.
    repeat(fiber => fiber.

        // Spawn the “AB” fiber: listen to events from buttons A
        // and B, then light up O. Reset all elements to their
        // initial state when the fiber ends.
        spawn(fiber => fiber.

            // Wait for A to be pressed and disable it.
            spawn(fiber => fiber.
                event(A, "click").
                call(() => { A.disabled = true; })
            ).

            // Wait for B to be pressed and disable it.
            spawn(fiber => fiber.
                event(B, "click").
                call(() => { B.disabled = true; })
            ).

            // Resume when both buttons have been pressed.
            join().

            // Light up O and wait indefinitely.
            call(() => { O.classList.add("on"); }).
            ramp(Infinity).

            // When the fiber is cancelled, reset all elements
            // their initial state.
            ever(fiber => fiber.
                call(() => {
                    A.disabled = false;
                    B.disabled = false;
                    O.classList.remove("on");
                })
            )
        ).

        // Spawn the “R” fiber: wait for button R to be pressed.
        spawn(fiber => fiber.event(R, "click")).

        // End as soon as the first fiber ends (which will be R)
        // and repeat immediately.
        join(First)
    );

In Epistrophy, what was called a computation in the model maps naturally to a JS synchronous function. A fiber can be represented as a Fiber object, with methods for adding instructions. The scheduler is likewise a Scheduler object, with methods to schedule or cancel fibers. These are kernel functionalities that are not used directly in the example above: the shell has some additional facilities to work with fibers and the scheduler. At the beginning of the program, the run() shell function creates a scheduler and a main fiber, schedules that fiber to run immediately, starts the scheduler, and return the fiber. What remains to be done is then to add instructions to that main fiber.

The rest of the program shows the instructions being added to fibers. repeat() adds a Repeat instruction; since it is really a combination of Spawn and Join under the hood, it does spawn a new fiber, which itself spawns two child fibers (the “AB” and “R” fibers) and joins using the First argument (an object imported from the shell). Within these fibers, other instructions like event(), call() and ramp() are added. Some of the designs decision should become apparent now: many instructions take functions as arguments, either for wrapping computations (call()), or for adding instructions to a fiber (repeat(), spawn(), ever()). Methods that add instructions to a fiber return the fiber, so that instructions can be chained, and methods that create fibers call their function argument with the newly created fiber to add instructions to it. The aim is to mimick a DSL (domain-specific language) looking a bit like a structured assembly, with sequences of instructions and nesting to represent the tree structures of the fibers.

The kernel follows the model closely, but also provides additional primitives to interface with the underlying platform:

• call wraps a synchronous JS function into a computation.
• ramp is a delay that can also perform a computation at the beginning, the end, and during the ramp.
• spawn spawns a new child fiber.
• join joins previously spawned fibers.
• await is a JS-specific instruction to call asynchronous functions (such as async functions and functions returning a Promise).
• event is a browser-specific instruction to handle DOM events.

Once a fiber was created with a sequence of instructions, it needs to be scheduled in order to run. In the previous article, we sketched how the scheduler is expected to work, and the current implementation naturally follows from there. The scheduler manages fiber objects, keeping them in a priority queue (implemented as a min-heap) using the begin time as the priority, and periodically executes the fibers in a given open interval [begin, end[ (where begin and end are times (implemented as JS numbers, i.e., 64-bit floats, as an approximation of real numbers) such that begin < end) by removing fibers from the priority queue one at a time while their begin time falls within the interval and running their instructions until they end or they yield, in which case they are inserted in the priority queue with their new resume time, if it is resolved.

The correct execution of a program then consists of calling the scheduler’s update function for a continuous succession of intervals, where each interval uses the end time of the previous one as its begin time, and starting at time 0. The Epistrophy Scheduler object has an internal Clock object, calling this update function repeatedly, using the browser window’s window.requestAnimationFrame() method. This is well suited for graphical applications, so that all updates happen between visual refreshes, and ensures that even if logical times are not perfectly matched to real-world durations, and will not be the same from one execution to the next, fibers will always execute in the same order for the same inputs. The clock can also be started or stopped at any time so that overall execution can paused or resumed. It is even possible to bypass the clock altogether and call the scheduler’s update function directly to simulate arbitrary amounts of time passing. This is one of the benefits of logical time, and will be explored further in later installments.

Scheduling a fiber means inserting the fiber in the scheduler’s priority queue. But what gets really inserted in the queue is a ScheduledFiber object, representing an instance of a fiber at runtime. Indeed, the same fiber can run multiple times (think of Repeat), maybe even at the same time (it is possible to spawn the same fiber in the same instant more than once). A ScheduledFiber maintains some state properties during execution:

• its parent ScheduledFiber, which is the fiber instance that it was spawned from;
• its children ScheduledFiber objects, which where created from spawned fibers;
• an instruction pointer, starting at zero, and pointing to the next instruction to be executed;
• a value, which is initially the same as the parent’s value but may change during execution;
• an error, which is defined only when an error occured and the fiber is failing.

When the scheduler executes a fiber, it really executes the fiber’s instruction indicated by the instruction pointer, the increments it to move to the next instruction. The fiber ends when the instruction pointer points past the end of the list of instruction. If the instruction represents a simple computation execution keeps going; otherwise, the fiber yields and its execution is suspended. The simplest instruction is call(f) which calls the binary, synchronous function f(fiber, scheduler) with the instance of the fiber and the scheduler object as parameters, and updates the fiber’s value property with the return value of the function (if any; otherwise, the value is unchanged). Functions given as parameters to call can examine their environment at runtime through their two arguments: a simple example is call(fiber => fiber.value + 1), which increments the current value of the fiber by one. In general, we are only interested in one or a few properties of the fiber, so idiomatic Epistrophy makes use of object destructuring: another way to increment the fiber value is call(({ value }) => value + 1).

ramp(dur, f) is not just a delay but represents a value that ramps from 0 to 1 over a given duration. dur is a JS number representing a duration in milliseconds, or a binary function dur(fiber, scheduler) that can return a duration in milliseconds at runtime (for dynamic delays). The second, optional parameter, f, is a callback that executes when the ramp begins, when it ends, and when the scheduler is updating in between these two times. The callback defaults to a no-op, in which case a ramp is just a delay; when provided, it should be a binary function f(fiber, scheduler), called with the fiber instance and the scheduler. During a ramp, the ScheduledFiber object has an additional p property which represents the progress of the current ramp. Its value is 0 when the ramp begins, 1 when the ramp ends, and a monotonically increasing value between 0 and 1 during updates. The ramp instruction is not a simple computation, so the fiber yields immediately after calling f once with p = 0. If the duration is definite, the fiber can be rescheduled, and will resume execution by calling f one last time with p = 1. Otherwise, because the ramp duration is infinite, the callback will just keep being called with p = 0 on every scheduler update. As mentioned above, ramps can be used for animation. Let’s give two examples:

1. because the clock ticks using requestAnimationFrame, a ramp effectively provides a callback suitable for animations at the browser’s own refresh rate, e.g., using an infinite ramp: ramp(Infinity, fiber => { draw(fiber.value); });
2. but a flipbook-style animation, where individual animation frames are expected to be shown at a fixed rate, can also be achieved by repeatedly drawing an image, and waiting for a fixed duration using a ramp instruction as a delay:

spawn(f) creates a new fiber and calls f(fiber) with the newly created child fiber (enabling the nesting pattern seen in the example code). At runtime, an instance of the child fiber is scheduled to begin in the same instant, but the parent fiber does not yield; its exection continues before the child fiber can begin. The ABRO example at the top shows multiple uses of spawn.

join(delegate) is the counterpart to spawn: when executed, it simply yields (unless no children have been previously spawned), so that the child fibers actually begin execution. The delegate parameter is an optional object that may provide a fiberWillJoin(fiber, scheduler) method that executes just before yielding (in case some initialization step is necessary to handle the child fibers joining), and a childFiberDidEnd(child, scheduler) method that gets called with the child fiber instance that ended and the scheduler when that instance ends. This allows the parent fiber (which can be accessed within the delegate methode with child.parent) to inspect the value or error with which the fiber ended (more on errors later) and react appropriately. For example, the join delegate may want to collect the values of its child fibers in the order in which they ended, or in which they were spawned; or it may want to end as soon as one fiber ends, which can be achieved by cancelling all other children as soon as the first one ends. Because these are common use cases, the shell provides some ready-made delegates such as First (used in ABRO) and other fiber methods that make use of spawn and join (we already know about repeat and will see others below).

await(f, delegate) and event(target, type, delegate) are very similar as they also yield for an unresolved duration before resuming. In the former case, an async JS function f(fiber, scheduler) is called and the fiber yields. The scheduler monitors the promise that the async function returns, and schedules the fiber again when the promise is resolved or rejected, and handles the case where the fiber was cancelled while the promise was still pending. A delegate method can also be called with the eventual result (value or error) once the fiber is about to resume. In the latter case, the scheduler registers a DOM event handler on the target for a given type of event (both parameters may be, respectively, a DOM EventTarget and a string, or functions that return the appropriate value to be evaluated when executing the instruction, like the ramp duration) and yields; it resumes the fiber once an event notification is received, and handles cancellation of the fiber by removing the event handler. The delegate object allows additional handling of the actual event value, such as calling event.preventDefault() or rejecting the event, suspending the fiber again until a new event notification is received (e.g., to listen to keyboard events from a specific set of keys). A simple example can be seen in ABRO: event(A, "click") is used to listen to click events on the A button.

Errors can happen whenever user code is called, and are automatically caught by the scheduler (including inside event handlers and when promises from async calls are rejected). The error property of the running ScheduledFiber object is set, and the fiber enters failure mode, during which instructions are skipped, as mandated by the model. By default, an error causes a fiber to end immediately. Error handling and recovery is however possible. First off, when a child fails, its parent may handle the error through its join delegate. It is also possible to wrap instructions in an ever block to ensure that these instructions run even when the fiber is failing; this is the implementation of the protection mechanism of the model.

ever is used in ABRO around the last call instruction of the AB fiber: when the user presses the R button, the R fiber ends, and because the parent’s join delegate is First, the AB fiber is cancelled. Whatever the state of the cancelled fiber, its instructions are skipped until the end, except for the last one, which is protected by ever and restores the the DOM elements to their initial state. This ensures that pressing R does indeed reset the state of the system correctly in all situations. Notice that the preceding instruction is ramp(Infinity), which means that if both A and B have been clicked, then O stays on forever. Cancelling the fiber immediately terminates this ramp however (as specified by the model), and execution moves on to the last instruction.

We know enough about Epistrophy now to show the code for the tomato animation shown above:

import { loadImage } from "./util.js";
import { TransportBar } from "./shell.js";

const div = document.querySelector("div.tomato");

// Create a new transport bar and add it to the demo.
const transport = new TransportBar();
div.appendChild(transport.element);

// Schedule a fiber to run the demo when the play button is pressed.
transport.schedule(fiber => fiber.

    // Generate image URLs (tomato01.png to tomato18.png).
    call(() => new Array(18).fill().map(
        (_, i) => `../tomato${(i + 1).toString().padStart(2, "0")}.png`)
    ).

    // Load all 18 images in parallel and gather them in order.
    maporder(fiber => fiber.
        await(async ({ value: url }) => loadImage(url))
    ).

    // Animation loop, showing the image in the div at the current index
    // and waiting for a 9th of a second before showing the image at the
    // next index.
    repeat(fiber => fiber.
        each(fiber => fiber.
            call(({ value: image }) => {
                div.replaceChild(image, div.firstChild);
            }).
            ramp(1000 / 9)
        )
    )
);

This example uses a few more features from the shell, which extend the expressivity of the model by encapsulating common timing and synchronization patterns, and even introduce some useful tools: here, a transport bar. It is rather stripped down at the moment, with only a play button, a pause button, and a time display, but it will become more capable in the future and already gives us a pause feature for the cost of one line of code: adding the transport bar element to the page.

The transport bar comes with its own scheduler, so we schedule the main fiber at the top with it. The first two instructions set up the animation loop and are followed by a repeat to run the loop itself. The call generates a list of image URLs from a pattern, setting the initial value of the fiber. Then the shell instruction maporder is called to actuall load the images (by creating an image element for every URL). maporder is the concurrent equivalent of the JS Array.map method and works as follows: instead of spawning one instance of a fiber with the parent’s value as its initial value, it spawns an instance of the same fiber for every element of the parent’s value, which must be a JS Array, and uses the element as the initial value. Here, eighteen instances of the same fiber are spawned, each with a different image URL. Then, the parent fiber joins and collects the eventual values of the child fibers into a new array, maintaining the original order (there is the similar map instruction which collects the value in the order in which the children end). The child fiber consists of a call to the loadImage async utility function that creates an image element, sets its src property, and handles load and error events. When the maporder ends, all image URLs have been mapped to actual image elements that are fully loaded and ready to be displayed.

The animation loop consists of showing an image and waiting for a short period before showing the next image. This can be achieved with the shell instruction each which, similarly to map and maporder, is a concurrent version of the JS Array.each method: we show each image in order, waiting for 1/9s (effectively playing the animation at 9 frames per second), and repeat until the sequence is exhausted. The outer repeat shell instruction repeats this cycle for ever. ⚃⚅

You can follow the development of Epistrophy on Mastodon.