Introduction

For decades, ECMAScript (JavaScript) was the only programming language that was universally supported by all major web browsers. There are now several, high-performance Ja-vaScript implementations that make it possible to run large programs, such as spreadsheets, IDEs, and video editors on the Web. In fact, many contemporary desktop applications, such as Slack and Visual Studio Code, are now built with JavaScript and other web technologies [2].

Since web browsers, and thus JavaScript, are ubiquitous, there are now scores of programming languages with compilers that emit JavaScript to run on the Web. However, compiling to JavaScript has two serious drawbacks: 1) programs may perform poorly when compiled to JavaScript, and 2) a variety of language features, such as threads, are hard to compile to JavaScript.

However, there is now an alternative to JavaScript. Web-Assembly [18] is a recently introduced low-level language that aims to be a better compiler target language than Java-Script. All modern web browsers support WebAssembly, and despite its name, there are several WebAssembly runtime systems that are not embedded in browsers. When programs written in C/C++ are compiled to WebAssembly, they run 1.3× faster on average than when they are compiled to Ja-vaScript [18,20]. However, given WebAssembly as it exists today, it remains difficult to compile a variety of language features, including green threads, coroutines, and continuations. In fact, many languages that support these features natively, either do not support them in WebAssembly, or produce slow code. For example, the Go compiler has a Web-Assembly backend. However, it struggles to support green threads (Goroutines), which makes the compiler difficult to maintain, and produces code that performs poorly [5][6][7]9].

Safety is a key design goal of WebAssembly, which is necessary for web browsers to run untrusted code in a trustworthy manner. Toward this end, WebAssembly programs are isolated from the browser, and cannot directly alter the lowlevel state of the WebAssembly runtime. In particular, the WebAssembly stack is not stored on the WebAssembly heap. Moreover, WebAssembly only supports structured controlflow and does not support exceptionsfoot_0 , goto, and longjmp. These restrictions make WebAssembly validation straightforward and fast. However, they make it difficult to implement non-local control flow. For example, Goroutines and green threads require low-level support for switching between stacks, which WebAssembly does not directly support.

State of the art. To workaround the restrictions of WebAssembly, the Go compiler performs a global program transformation, which 1) builds a copy of the WebAssembly stack in the heap to store local variables, and 2) simulates nonlocal jumps via an elaborate state machine in each function. Asyncify [27] uses a similar approach to add virtual instructions that save and restore stacks to WebAssembly. Prior benchmarks indicate that Asyncify has a performance overhead of 20%-100%, and a similar increase in code size [27]. Moreover, since these tools use a global transformation to achieve non-local control flow, programmers are forced to pay a steep cost for such features, even when their code uses them minimally.

Our contributions. In this paper, we present Wasm/k, an extension to WebAssembly that adds support for first-class, delimited continuations, which are sufficient to implement a wide variety of language features, including green threads, coroutines, and exceptions. Our extension has only a handful of new instructions, is designed to support efficient implementation, and is designed to work well when WebAssembly programs interact with other languages (e.g., JavaScript).

Although first-class continuations are a well-known abstraction, they are typically found in higher-level programming languages (e.g., Scheme and Racket). These languages are compiled to low-level native code that does not support first-class continuations. Our work inverts this tradition and instead adds first-class continuations directly to a low-level language. In doing so, our design tackles unique challenges imposed by the low-level setting, such as the lack of firstclass functions, lack of garbage collection, and the requirement that WebAssembly support safe interoperability with host languages (e.g., JavaScript).

Another goal of our work is to ensure that our new instructions align with with WebAssembly's performance, portability, and safety objectives. We considered the following design goals: 1) Common language features, such as green threads, should be able to compile to efficient Wasm/k code.

2) The extension should lend itself to simple type checking (validation). 3) The extension should lend itself to highperformance implementation in existing WebAssembly JITs. 4) The extension must be safe. 5) Existing WebAssembly instructions and code should suffer no performance penalty. And 6) the performance of new instructions should be fast and predictable.

Since the goal of Wasm/k is to provide a better compiler target language, we also prototyped C/k, an extension to C/C++ that adds support for delimited continuations. C/k uses the Emscripten compiler that compiles from C/C++ to Wasm/k, and we use it to implement programs with a variety of features, including green threads. We then evaluate the performance of green threads when implemented with C/k against the state-of-the-art approach Asyncify [27].

To summarize, we make the following contributions:

1. We design Wasm/k, and present its semantics, validation, and safety properties. 2. We implement Wasm/k as a modest extension to Wasmtime, which is a real-world WebAssembly JIT. 3. Using Wasm/k and the Emscripten compiler from C/C++ to WebAssembly, we present C/k, which adds delimited continuations to C/C++. 4. We evaluate the performance of our Wasm/k implementation by comparing it to a third-party tool that implements continuations by source-to-source transformation.

The Wasm/k Approach

We start by illustrating the basics of WebAssembly and sketch the compilation strategy that the Go compiler uses to support Goroutines in WebAssembly (Section 2.1). We then present Wasm/k, which extends WebAssembly with first-class continuations (Section 2.2), and C/k, which extends C/C++ with first-class continuations (Section 2.3). We use C/k to present green threads, generators, and probabilistic programming in WebAssembly (Section 2.4).

WebAssembly

WebAssembly is a stack machine with a conceptually independent control stack and value stack. For example, the (i64.const 2) instruction pushes the integer 2 onto the value stack, and the i64.mul instruction pops two integers off the stack, and pushes their product onto the stack. Similarly, functions receive their arguments and return their result on the value stack too. Each function has a collection of local variables, and can use (local.get $𝑥) to push a local variable's or an argument's value onto the value stack, and (local.set $𝑥) to pop a value off the stack and update the variable. Similarly to local variables in C, registers will be allocated for local variables during JIT compilation. For example, the $quadruple function (Figure 2a) quadruples its argument by calling $helper to first double the argument, and then doubles the result produced by $helper.

In addition to storing data on the stack and in local variables, data can also be stored in linear memory (WebAssembly's heap), which is a byte-addressable region of memory. Linear memory can be read and written via i32.load and i32.store respectively, for, e.g., the i32 type. Unlike local variables, using linear memory will always incur hardware loads and stores.

Compiling Go to WebAssembly. Goroutines, which are similar to green threads (or, user-space threads), are the primary concurrency abstraction of the Go programming language. When compiled to native code, the Go runtime manages a pool of physical threads and uses them to run several Goroutines on a single thread (a so-called 𝑀:𝑁 threading model). This involves using low-level instructions to save and restore the stack and registers' values, during a (user-space) context-switch from one Goroutine to another. A contextswitch may occur for a number of reasons, e.g., when the active Goroutine is blocked on I/O or simply periodically.

While physical threads are discussed in the threading proposal [8] and are available in some WebAssembly runtimes (e.g. Chrome), switching between goroutines within a single physical thread in WebAssembly is far more difficult compared to native code, since the WebAssembly stack is not allocated in linear memory and thus cannot be saved or restored. 2 Instead, the compiler generates code that maintains a heap-allocated copy of the stack residing in linear memory. Figure 1a shows an example of a simple function foo in Go. The function computes a partial sum of a series, and calls the function bar on each iteration. Since bar may trigger a thread switch (Go inserts a yield at the start of every function), the compiler has to generate code to save and restore foo's stack.

We sketch the generated code in Figure 1b. Before the call to bar, the generated code saves the local variables (f and k) onto the copy of the stack in linear memory (bottom of Figure 1b). Thus if bar switches to a new Goroutine, the local variables of foo can be safely discarded. Conversely, foo reads the values of its local variables from the heapallocated stack (top of Figure 1b). Note that no such load or store instructions need to be emitted when compiling Go to native code directly, because in native code the Go runtime can freely manipulate the machine stack.

It is instructive to consider how code generation works for simpler languages, such as C. Given the C equivalent of foo, the Emscripten compiler from C to WebAssembly generates much simpler code (Figure 1c), without any loads and stores to linear memory. Since the code uses WebAssembly local variables exclusively, a WebAssembly JIT can easily allocate them to machine registers. (Emscripten does not support setjmp and longjmp, which can be used to build green threads in C.)

The additional loads and stores in Go have a cost. In a call to foo(2 30 ), the perf tool shows the Go program executes 2.5× more instructions, 3.0× more branches, 1.9× more loads, and 1.5× more stores than the equivalent C program, when we compile both to WebAssembly (compiled with optimizations and run with node v14.4.0). Overall, the Go program takes 1.8× longer than the C program. However, when compiled to native code, the performance of the C and Go code is nearly identical.

Wasm/k

Wasm/k adds five new instructions to WebAssembly. 1) The (control ℎ) instruction captures the current continuation, stores it a region of memory called the continuation table, assigns it a new continuation ID (𝜅), and invokes the function (ℎ) with a fresh stack, passing the continuation ID and a user-provided argument. 2) restore receives a continuation ID as its argument, and restores the associated continuation, discarding the current continuation in the process. It is a runtime error to restore the same continuation multiple times. 3) The continuation_copy instruction creates a copy of a continuation. 4) The continuation_delete instruction deletes a continuation without restoring it. 5) The prompt 𝑒 * end instruction wraps a block of instructions (𝑒 * ), and serves as a delimiter for continuation capture: all continuations captured by 𝑒 * do not extend beyond the call to prompt.

Figure 2b shows an alternate implementation of $quadruple, using continuations in a trivial way. The function captures its continuation and passes it to $handler (line 9), which runs 1 (func $helper (param $x i64) (result i64) in the empty continuation. The $handler function receives two arguments: $k is the captured continuation ID, and $x is the original argument to $quadruple2, passed through to $handler. The $handler function doubles its argument and restores $k, passing the doubled value along. At this point, the captured continuation will execute (line 10), with the doubled valued pushed onto the stack. Execution completes as before by doubling again.

C/k: Continuations for C/C++

Writing and reading substantial examples in WebAssembly is tedious. Therefore, the rest of this paper presents examples using C/C++. We use the Emscripten compiler from C/C++ to WebAssembly, and export the new Wasm/k instructions to C/C++ programs using the API defined in Figure 3. Each of these functions call their corresponding instructions in Wasm/k to manipulate the WebAssembly stack.

However, it is not enough to directly expose the Wasm/k primitives to C++ code. A program written in C/C++ can get the memory address of a local variable, which WebAssembly does not support. Emscripten uses a heap-allocated portion of the stack to support these programs. Therefore, C/k has to carefully manage this portion of the stack as well (Section 4).

Adding first-class continuations in this manner to C/C++ is unusual, as typically first-class continuations are a feature in high-level languages such as Racket, and need to be compiled to low-level code which does not support first-class continuations. By going in the opposite direction, we get them almost for free in a higher-level language.

Using Continuations in Wasm/k and C/k

We now present several applications of Wasm/k, using C/k to write our code.

Green threads. Green threads (or cooperative threads), are a simple example of an abstraction that is easy to build with continuations. Figure 4b shows an implementation of green threads in C/k, which provides functions to create new threads, wait on threads to complete, and suspend the running thread and yield control to another thread (thread_yield). Figure 4a is a small program that uses this threading library.

The key insight is that thread_yield can be accomplished by capturing the current continuation of the thread via control (Figure 4b line 37), storing the continuation ID in a queue (Figure 4b line 33), and dequeue-ing and restoring another continuation ID (Figure 4b line 34). Since green threads do not need to pass data between threads, we do not utilize the data arguments to control and restore.

Generators. Generators are a programming abstraction that are found in a variety of languages, including Python and JavaScript. Although C does not support generators, we can build them using control and restore. Figure 5a shows a program in C/k that prints the numbers 0 through 9, using a generator function. The generator contains what appears to be an infinite loop, but each iteration suspends execution in the generator (gen_yield) and resumes execution in main.

Figure 5b presents the implementation of generators using C/k. The primary difference between our implementation and canonical implementations (e.g., in Racket [4]), is that C does not support first-class functions. Therefore, we represent a generator as an object (struct) with fields that hold 1) the ID of the continuation where the generator was invoked (after_next), 2) the ID of the continuation where the generator was last suspended (after_yield), and 3) the next value to return from the generator (value).

Finally, the generator API includes a function to delete a generator object (free_generator). This function deletes the continuation within the generator (g->after_yield) using continuation_delete (line 38). Note that since the other continuation (g->after_next) was restored to during the most recent yield (line 22), it is currently unallocated and does not need to be deleted. The need for a continuation_delete instruction is subtle, but is required for natural use cases of 1 void thread_main() { 2 std::cout << "A" << std::endl; Probabilistic programming. A more involved example is the implementation of an embedded probabilistic programming language in C++. Probabilistic programming languages allow probabilistic models to be implemented declaratively in general purpose languages. One common approach to implement a probabilistic programming language is to relate sampling from a probability distribution to sampling from a distribution of program executions [21]. Performing this 1 void example_generator(Generator *g) { 2 uint64_t i = 0; sampling requires some use of control operators which can essentially fork execution to allow it to be re-executed (i.e., sampled from) multiple times. While the implementation of a proper probabilistic programming language with modern sampling algorithms is out of the scope of this paper, we can nevertheless demonstrate how to implement a probabilistic programming language allowing for finite distributions embedded in C++. An example usage of the embedded probabilistic programming language is shown in Figure 6a. sum_d6 computes the sum of two independent dice rolls. The call to driver(sum_d6) will run the sampling algorithm, eventually returning a map that represents the probability mass function (PMF) of sum_d6. The proposed API consists of just a uniform function which represents the uniform distribution over a discrete set of values (the vector argument) and the driver function which conducts the sampling to obtain the final PMF. This API can be easily expanded in this framework to allow for different distributions and conditioning, but these are omitted for brevity.

The implementation of the API is shown in Figure 6b. The core idea is that each sample from a distribution will correspond to forking the execution for each sampled value. For example, if sampling from uniform(1, 2, 3) the execution would be forked into 3 executions, one with each sampled value. The various execution forks are stored in the to_execute state, in the format of a vector of Continuation-Thunks (lines 1-6), which keep track of the continuation to restore to, and the sampled value to pass to the continuation upon restoring.

The implementation of driver (lines 8-16) keeps a vector of final sampled values, and proceeds by first running the given function argument (body()) and saving the result, and then dequeuing a thunk to execute and restoring it. Supposing that body forked its execution into thunks, then the call to restore (line 13) will jump back into the execution of somewhere in body, eventually returning yet again to the push_back (line 10). Thus, driver will continue to push results and dequeue a new thunk, until all thunks (samples) are exhausted. Finally, count_probs computes the desired map.

With driver worked out, the implementation of uniform is conceptually straightforward: uniform(args) should fork the execution for each value in args. This is accomplished by first immediately calling control (line 28) to capture the current continuation. Then, for every element except the first element of args a new thunk is queued, where the continuation is a copy of the current continuation k (line 22). An explicit copy of k is required because all of these thunks will eventually be restored to, and under one-shot continuation semantics it is invalid to restore to a single continuation (k) multiple times. Finally, the current continuation is restored immediately with the first sampled value rather than saved in a thunk (line 25).

Semantics of Wasm/k

This section presents 1) an overview of WebAssembly's operational semantics, 2) extends the operational semantics to support continuations, 3) presents type-checking (known as validation) for this extension, and 4) proves that the extension is sound.

WebAssembly Semantics

WebAssembly is formalized as a stack-based, small-step reduction semantics. This section introduces a small fragment of the WebAssembly semantics, using the example program in Figure 7a. For a more detailed account, we refer the reader to Haas et al. [18] and the WebAssembly specification [11].

The WebAssembly stack machine contains both instructions (𝑒) that are pending evaluation and values (𝑣) that were produced by instructions that have already been evaluated. The values are a subset of instructions. For example, the instruction (i64.const 𝑛) pushes the 64-bit value 𝑛 onto the stack. Moreover, the semantics represents the 64-bit value 𝑛 as (i64.const 𝑛). In the absence of control flow and function calls, a configuration of the WebAssembly stack machine has a sequence of evaluated values (𝑣 * ) and a sequence of instructions (𝑒 * ) in succession (𝑣 * 𝑒 * ), and we always evaluate the first non-value instruction in the sequence. The boundary WebAssembly has structured control flow, and does not have goto-style instructions. Instead, the language has structured control flow blocks (e.g., block . . . end and loop . . . end). The WebAssembly semantics turns all kinds of blocks into labelled blocks (label{𝑒 * } . . . end), which are an administrative instruction. 3 The nested structure of labelled blocks is defined by local contexts of depth 𝑘 (𝐿 𝑘 [_]). A local context of depth 0 (𝐿 0 [_]) matches a stack of the form 𝑣 * 𝑒 * , and a local context of depth 𝑘 + 1 matches a local context of depth 𝑘 nested inside a labelled block. For example, Figure 7a has four instructions within an 𝐿 1 context.

A WebAssembly program is organized as a collection of modules that import and export code and data. An instantiated module with no unresolved imports is called an instance. The global execution state of all instances is called the store. We present Wasm/k as an extension to the WebAssembly formal semantics, which includes the machinery needed to support multiple instances. However, for the purpose of this paper, it is sufficient to consider programs with just one instance.

The WebAssembly stack, nested control flow, the store, and instances are the elements of WebAssembly that are relevant to Wasm/k. With these defined, WebAssembly has a small-step semantics that updates the stack, and possibly the store (𝑠) and local variables (𝑣 Thus evaluation always occurs in the innermost local context, unless no such evaluation is possible. When an instruction does not read or write from the store, we omit the store for brevity. Figure 7b shows the execution trace of our example.

Design and Semantics of Wasm/k

We first describe the new values and types of Wasm/k, then present necessary changes to WebAssembly instances, and finally present the new reduction rules of Wasm/k.

The continuation table and continuation IDs. In a language that supports first-class continuations, a continuation 3 The 𝑒 * is only needed to encode loops, and can be ignored in this paper.

Continuation IDs

𝜿 _𝒊𝒅 ::= i64 Wasm/k has delimited continuations, which are needed to safely interoperate with host languages such as Java-Script (Section 3.4). Thus Wasm/k includes a prompt instruction, and we modify instances to track a stack of dynamic prompt scopes. Formally, we extend instances as follows (highlighted in Figure 8). Each instance (inst) contains a stack of dynamically nested prompt contexts. Each prompt context (pinst) is a record containing a continuation table and a continuation ID of the root continuation, defined to be the continuation associated with the stack which initialized the WebAssembly execution or most recent prompt. The continuation table consists of an array of entries, where each entry is either nil or a captured continuation, with all entries initialized to nil. 4A continuation saved in a continuation table is a record that contains the values of local variables (across all stack frames), and the entire evaluation context at the point of capture. However, WebAssembly's local context (𝐿 𝑘 ) only capture a stack with 𝑘 nested blocks. Therefore, we define full-stack contexts (𝐿 max ) as evaluation contexts that match a stack with arbitrary control block depth, and a continuation stores a full-stack context.

Finally, the root continuation ID in a continuation table is maintained such that if the root continuation is currently executing, root will be set to nil, otherwise root will be set to the index 𝜅 𝑅 of the root continuation in the continuation table . New reduction rules. The semantics of WebAssembly define a reduction relation (↩→) that is congruent with local contexts ([Cong] in Figure 9). However, full congruence with local contexts does not hold in the presence of first-class continuations. Therefore, Wasm/k introduces a new reduction relation (⇝) for programs that contain (control ℎ) and restore instructions (Figure 9). The extended semantics refer to the original WebAssembly reduction relation (↩→), using the [Cong] rule, but there is no equivalent rule for ⇝. If there is a reduction which involves no use of (control ℎ) or restore, then it is also a valid reduction which might make use of (control ℎ) or restore, as given in the [No-Ctrl] rule.

The (control ℎ) instruction receives a single argument (𝑣) and calls the function ℎ, passing it a new continuation ID (𝜅) and the argument 𝑣. The continuation ID is bound to the current continuation (𝐿 max ) and local variables (𝑣 * 𝑙 ), and the call to ℎ is followed by a trap: i.e., it is a runtime error to return normally from ℎ. For simplicity, (control ℎ) makes a direct call to a function ℎ. However, when an indirect call is necessary, it is possible to use 𝑣 to pass the index of a function to ℎ.

The restore instruction receives a continuation ID (𝜅) and a restore value (𝑣). The instruction dynamically checks that 𝜅 is a valid continuation ID. If 𝜅 is valid, it restores the local variables (𝑣 * 𝑙 ′ ) and the stack (𝐿 max ′ ) that is associated with 𝜅, and returns 𝑣 to the stack. The restore instruction also marks the continuation ID (𝜅) as nil in the continuation table, which allows it to be reused by subsequent calls to (control ℎ). Finally, when restoring the root continuation, restore sets the root ID back to nil, and leaves it untouched otherwise. Note that restore is abortive rather than functional, in the sense that restore aborts the current continuation and instructions following restore will never be executed. It is a runtime error to call restore on a continuation ID (𝜅) that is un-allocated, or to invoke restore within the root continuation. In either case, a trap occurs.

We need the continuation_copy instruction to create a copy of a saved continuation, so that a program can restore a continuation several times if needed. This instruction assigns a new continuation ID to the copy. A trap occurs if the provided continuation ID is mapped to nil. The continuation_delete instruction deallocates an continuation without restoring it, and may be needed to avoid memory leaks in certain applications.

In the presence of first-class continuations, a function 𝑓 may now never return to the call site or may return multiple times. Motivated by a need for safe FFI, the goal of a prompt tf 𝑒 * end instructionfoot_3 is to evaluate the body 𝑒 * such that 𝑒 * is guaranteed to finish evaluation exactly once (or trap/diverge), and trap otherwise. Note that this is similar to Felleisen's prompt [15], but in cases where Felleisen's prompt alters the control flow, Wasm/k's prompt traps. This design is due to the fact that our restore operator is abortive rather than functional. Evaluation of prompt tf 𝑒 * end involves first pushing a prompt context onto the prompt stack with a blank continuation table and the root ID set to nil, then executing 𝑒 * inside a scoped block, and finally executing the administrative non-user accessible instruction prompt_end. Note that if 𝑒 * were to contain branches to labels outside of the prompt, the execution of prompt_end could be skipped. The validation rules discussed below outlaw such branches. The safety properties of prompt during FFI is discussed in Section 3.4. Evaluating a prompt_end instruction pops and discards the top prompt context from the prompt stack.

Validation

Validation (type checking) is accomplished in WebAssembly by assigning each instruction a type describing the values it pops from the stack and the values it pushes onto the stack. For example, the type of an add instruction (i32.add) is

. Type Checking of Wasm/k.

[Root]

Figure 11. Typing delimited instructions.

𝐶, label(𝑡 * ) used in previous WebAssembly type checking rules to mean that the label (𝑡 * ) is pushed onto the top-most stack in 𝐶 (or in a new stack if none exist), and likewise the notation 𝐶 label(𝑖) we define to mean indexing by 𝑖 into the top-most stack in 𝐶. These implicit re-definitions allow all the other WebAssembly type checking rules to remain untouched. With this machinery in place, the type checking rule for prompt can be given, which closely mirrors the type checking rule of block, except that an entire new label stack is pushed into the context and the return label is invalidated.

An alternative approach could be to modify the semantics to force the prompt_end instruction to be run even when branching past it. However, this would require significant changes to how branch instructions are specified in the Web-Assembly semantics, and would significantly impact code generation.

Safety Properties of Wasm/k

We first prove the safety of Wasm/k, building on the safety of WebAssembly. We then consider safe interoperation with a host language.

Safety of standalone Wasm/k. WebAssembly is equipped with a syntactic type soundness theorem [18,19,25], which we build on.

WebAssembly's instruction typing relation (⊢ 𝑖 𝑒 * ; 𝑡 * ) calculates a sequence of types (𝑡 * ), which specify the types of the values that are left on the stack by the instructions (𝑒 * ). These types are preserved by each step of evaluation (↩→). However, if a step captures or restores a continuation (⇝), the type of the current instruction sequence may change.

To address this, we introduce a new typing relation (⊢ 𝑘 𝑖 ) which extracts the type of the unique stack nested most deeply in prompts which has been invoked through a chain of root stacks (Figure 11). We call this stack the primary root stack. There are two cases to this relation: 1) when the current instruction sequence is the primary root stack, we return its type ([Root]), and 2) if not, we extract the type of the saved primary root stack from the store ([Non-Root]). Using this typing relation, we prove progress and preservation for Wasm/k.

Safe interoperation.

A WebAssembly runtime environment is typically embedded in a host language, and offers an API that allows function calls from either language to the other. For example, Wasmtime supports interoperability with Rust, and web browsers support interoperability with Java-Script. Neither Rust nor JavaScript support continuations, and require foreign function calls to return exactly once. The prompt operator allows us to enforce this dynamically. Wasm/k automatically inserts a prompt block around a foreign call into Wasm/k. This design is similar to Scheme / Racket, but differs in two regards. First, Scheme / Racket allow FFI to be unsafe as they do not forcibly wrap every FFI call in a prompt, while Wasm/k prioritizes safety over some flexibility. Second, Scheme / Racket will not abort the program upon control flow which violates the exactly-once semantics of prompt, but will instead alter the control flow [15]. In keeping with using prompt strictly to enforce FFI safety, Wasm/k considers it a programmer error to attempt to violate such safety.

Leveraging Wasm/k in Existing Compilers

Since Wasm/k does not alter the semantics of existing Web-Assembly instructions, it ought to be easy to use Wasm/k to implement continuations in an existing compiler. However, today's compilers use code generation techniques that require a little extra care.

For example, consider Emscripten, which compiles C to WebAssembly. A typical C compiler would allocate local variables on the machine stack, and Emscripten is no exception. However, whereas a C program can obtain a pointer to a local, stack-allocated variable-a common operation in C programs-it is not possible to do so in WebAssembly. The WebAssembly stack is not stored in linear memory, and programs can only obtain pointers to values in linear memory. Therefore, to support these programs, Emscripten allocates local variables on the WebAssembly stack when possible, but uses linear memory when necessary. Emscripten generates code that reserves a block of memory to store the heap-allocated portion of the stack, and uses global variables that emulate stack and frame pointers.

Section 2.3 presented C/k, which extends Emscripten with continuations. Our extension adds new library functions that each correspond to a Wasm/k instruction, which manage saving and restoring the WebAssembly stack. However, we need to ensure that these operations correctly save and restore the heap-allocated portion of the stack (Wasm/k cannot do this automatically, since it is source-language neutral). Therefore, we insert code at the call site for each C/k operation to manipulate Emscripten's global stack pointer values. For example, at a call site of control, we insert code that saves the current heap-allocated portion of the stack and the value of the stack pointer into a table. Similarly, at a call site of restore, we insert code that restores the heap-allocated portion of the stack and stack pointer from the table.

This problem is not unique to Emscripten. For example, the Go compiler's WebAssembly backend creates a copy of the WebAssembly stack in linear memory to support garbage collection and Goroutines. We speculate that Wasm/k would allow the Go compiler to store non-pointer variables on the WebAssembly stack, which may improve the performance of numeric code. However, GC roots would still have to be stored in linear memory.

Implementation

We implement Wasm/k as an extension to Wasmtime, which is a standalone, JIT-based runtime system for WebAssembly. 6 Wasmtime is written in Rust and primarily developed by Mozilla. Wasmtime, and other WebAssembly JITs, use the native machine stack to store both values and return addresses. Wasmtime also performs register allocation to avoid using the stack when possible. Therefore, our Wasm/k implementation has to manage the native stack and registers, and take care to follow the calling convention that Wasmtime employs.

Capture and restore. The implementation of (control ℎ) involves several steps. 1) It uses a free list to allocate an unused continuation ID. 2) It associates this continuation ID with a new continuation object, which holds the values of machine registers that are not caller-saved, which includes the stack and instruction pointers. 3) It allocates a new block of memory to hold subsequent stack frames, and sets the 6 Our implementation is available at https://wasmk.github.io. stack pointer to point to this block of memory. 4) It jumps to the WebAssembly function ℎ, which receives the new continuation ID. To further improve performance, we preallocate a pool of memory to hold new stacks.

The implementation of restore is straightforward, since its principal task is to restore the registers saved by control in the continuation object. To ensure safety, we 1) ensure that the continuation ID is associated with a valid continuation object, 2) delete the continuation object so that it cannot be restored again, and 3) reclaim the memory used by the current stack.

Copying continuations. To copy a continuation, we allocate a new continuation ID, and duplicate a continuation object, but have to carefully tackle all pointers within the continuation object. The continuation object stores an instruction pointer, which can be freely copied. However, we have to update the saved stack pointer to point to the duplicate copy of the saved stack. This is sufficient for Wasmtime, but other implementations may require extra work. For example, if an implementation stores pointers into the stack in registers or on the stack itself, they must be updated to point to the copy.

Evaluation

In this section we compare Wasm/k to the natural alternative: which is to implement continuations using a whole program transformation that doesn't require any change to WebAssembly.

Asyncify [27] is a tool that simulates non-blocking I/O in WebAssembly. It extends WebAssembly with control operators that are similar to one-shot continuations, and outputs standard WebAssembly that simulates control flow. We use both Wasm/k and Asyncify to implement a green threading library (Section 2.4), which allows us to directly compare the performance of threaded programs.

As a benchmark, we use C-Ray [1], which is a ray tracer implemented in approximately 9,500 lines of C. Ray tracers are compute-intensive, and take a long time to render the final, full-quality image. However, because they can compute lower quality rendering approximations incrementally, it should be possible to display incremental rendering results, to appear more responsive to the user. C-Ray performs rendering computations on background threads (using pthreads), while the main thread periodically displays the current scene. We ported C-Ray to use our green threading library, and inserted thread yields in the main rendering loop, which yielded approximately once every 25 ms.

Code size. Code size is particularly important for web browsers, which download code on demand, and a key factor of Web-Assembly's design is that it has a compact binary file format. The size of the C-Ray WebAssembly program is 1.3× larger with Asyncify than it is with Wasm/k.

Performance. Figure 12 shows the time needed to complete ray tracing on five different visual scenes using Wasm/k and Asyncify, with the geometric mean over all scenes shown in the last two columns on the right. As a baseline, we use C-Ray running in WebAssembly with no threading. Note that the baseline has limited utility, since it cannot show intermediate results. However, it does illustrate the overhead that both Wasm/k and Asyncify introduce. The mean running time of Wasm/k is 1.1× the running time without threads. In contrast, the mean running time of Asyncify is 1.3× the running time without threads. Asyncify is slower, since it introduces several loads, stores, and branches to the compiled code. The smaller slowdown that Wasm/k introduces is the cost of checking whether it is time to switch threads.

Related Work

WebAssembly. Wasm/k extends the formal semantics of Web-Assembly 1.0 [18]. There are several proposed extensions to WebAssembly 1.0, not all of which have been implemented in production web browsers. The threading proposal [8] extends WebAssembly with support for atomic memory operations and synchronization primitives, but leaves the API for thread creation up to each WebAssembly runtime implementation. Thus far, the pthread API has been supported in some browsers. Watt et al. build on the threading proposal by formalizing a semantics and memory model for concurrent WebAssembly [26]. This work on robust support for concurrency via physical threads is an important step for WebAssembly, and is orthogonal and complimentary to Wasm/k: both aspects are needed for efficient implementations of goroutines which can utilize all CPU cores.

Another proposal extends WebAssembly with support for exception handling [3], which is a form of limited stack manipulation. An interesting question of semantics not addressed in this work is how Wasm/k would interact with exception handling. In this direction, there is prior work on supporting both delimited continuations and exception handling [16].

An alternative to supporting continuations natively is to implement them by source-to-source transformation [12,22]. Asyncify [27] does so for WebAssembly, and the Go compiler uses a similar approach to support Goroutines. Our evaluation (Section 6) shows that Wasm/k is significantly faster than source-to-source transformation, and produces smaller programs.

A recent discussion sketched an alternative design for WebAssembly continuations [23] that is based on extending exception handlers with general effect handlers. Our design is orthogonal to exception handling and makes fewer changes to the WebAssembly 1.0 type system. To the best of our knowledge, this alternative design has not been implemented at this time.

Finally, there exist related strategies of program execution control. Existing interpreters or virtual machines which feature execution control mechanisms can be compiled to WebAssembly, such as the Lua VM (implemented in C) [10] which features coroutines. This is certainly a viable and straightforward strategy to allow stack-manipulating code to run in a WebAssembly environment, but may not be able to achieve performance comparable to compiling to Web-Assembly. In addition, debuggers can be seen as a form of execution control, as code can be paused and resumed, but unlike with first-class continuations, the program control is not internally observable. Debugger support for WebAssembly has recently been explored in the context of microcontrollers [17].

Continuations. We adapt Sitaram and Felleisen's control operator [24] for WebAssembly. Our design accounts for the fact that WebAssembly has neither first-class functions, nor garbage collection: programs must explicitly delete unused continuations, and our new control operators take additional arguments that are not necessary in languages that support closures. We rely on control delimiters to ensure that Web-Assembly programs always safely interoperate with host languages that do not support continuations, such as Java-Script. However, it should be possible to adapt other control operators as well [13,15].

A goal of Wasm/k is to show that delimited continuations can be implemented efficiently in a modern WebAssembly JIT. Our implementation uses a contiguous stack, since it does not require global changes to code generation. However, there are a variety of other implementation strategies with different tradeoffs [14].

Conclusion

We have presented Wasm/k, an extension to WebAssembly that adds support for delimited one-shot continuations with explicit copying. We have prototyped all phases of Wasm/k, with examples in C/C++, code generation from C/C++ to Wasm/k, formal semantics of Wasm/k, and an efficient implementation of Wasm/k in an existing JIT. We hope that Wasm/k is a step toward helping WebAssembly be an effective compilation target for a large variety of high-level languages.