stack-switching
stack-switching copied to clipboard
WebAssembly
Optional Support for Multi-Shot Continuations
This Stack Switching Proposal introduces one-shot continuations, which are efficient and align with a contiguous stack model. However, languages like Scheme, Racket, and other functional or dynamic languages rely on multi-shot continuations (e.g., call/cc), which can be invoked multiple times and require capturing and restoring the stack.
Would it be feasible to optionally support multi-shot continuations in this proposal? This could allow languages that depend on full continuation support to target WebAssembly without losing core features. Even if there’s a performance trade-off (e.g., using a linked-list stack or stack copying), having the option would broaden WebAssembly’s applicability.
Note : Racket supports both one shot and reusable continuations, both delimited. Scheme only supports undelinited reusable continuations, but they can be implemented over delimited ones
In principle, that is a possible future extension, which we envision would most likely be introduced through a clone instruction.
In practice, though, the problem is that most of the major Wasm implementations (especially Web engines), are fundamentally built on the assumption that stacks aren't movable, as they tend to be interleaved with native (C++) frames that may be pointed into, e.g., to stack-allocated GC roots. So introducing multi-shot would potentially require major design changes for these engines, with possible performance implications. That's why we very consciously left it out of the current design. And although I sympathise, it might be a tough sell in the future, too. But who knows, never say never.
most of the major Wasm implementations (especially Web engines), are fundamentally built on the assumption that stacks aren't movable, as they tend to be interleaved with native (C++) frames that may be pointed into, e.g., to stack-allocated GC roots
I'm not sure about that. For instance, V8 switches to a central stack when calling C++ functions.
V8 does indeed switch to the central stack; furthermore, suspended computations may only contain wasm frames.
However, there are other issues. For example, CFI mitigation schemes based on shadow stacks are not compatible with cloning stack memories.
Overall, V8 is likely to be extremely skeptical of stack cloning.
Reusable continuations are typically implemented as linked lists. As persistent data structures, they eliminate the need for cloning, but this approach introduces its own complexities and trade-offs.
This method of implementing reusable continuations could be integrated as an extension to the Stack Switching Proposal, or achieved independently by generating CPS (Continuation-Passing Style) WebAssembly code—an approach that also works for one-shot continuations.
Alternatives like cloning a contiguous stack, using an additional linked list stack for reusable continuations, or leaving continuation management to the user each come with their own trade-offs in terms of performance, complexity, and memory usage.
Perhaps @wingo could offer insights here, given his work on a WebAssembly Scheme compiler.
Wasm implementations indeed use chained segmented stacks to represent continuations. But unfortunately, that does not eliminate the need for copying. As soon as you have stack-allocated mutable state, which is omnipresent in Wasm, e.g., due to locals, you cannot reenter a continuation without copying the respective stack chain. Reentrance would also wreak havoc with resource handles and other linear entities that implementations like to place on the stack.
A language runtime needs to make very different and careful design choices if it wants to support such reentrance. The problem is somewhat similar to introducing thread-safety after the fact.
I talked to @wingo about this briefly. He challenged me to think of a time when I resumed a continuation more than once in a real world program. I couldn't think of an example. So, I think we feel that multi-shot is not a must-have for delimited continuations in the Hoot project. The more important thing is for the Wasm stack to be growable because Guile does not have a stack size limit and many Guile programs rely on this feature.
In summary, I think that one-shot continuations + growable stack would be sufficient for our needs and maybe even for some other functional languages that use a lot of recursion. (There's a question of how we'd handle showing Scheme backtraces if we moved from our own explicit stack made from tables to a Wasm stack but that's neither here nor there.)
+1 to growable stacks. Also, implicit should be some expectation for scale: e.g., how many suspended computations is reasonable to expect in a 'reasonable' resource. For me, any 64bit system should be able to support 1million suspended computations, and a 32bit system should be able to support >10K suspended computations.
Wizard's implementation places all host->wasm calls onto a new stack segment, so Wasm code is always on the bottom of a stack segment. Its host call API forces callers to deal with suspensions, so it's not possible to suspend host frames. When Wasm code calls out to host code, the host code cannot suspend the calling stack. Thus suspended Wasm stacks in Wizard's design only contain Wasm frames. That would admit stack copying somewhat easily.
That said, I think to the other concerns (e.g. linear use of resources) make multi-shot continuations something that would have to be opted-into.
@titzer, isn't that assuming that no host function ever calls back into Wasm?
They always get a fresh stack when they do so. That also means that a return from Wasm to host can always recycle the stack back to a linked list, so usually getting a fresh stack is just taking an item from a linked list.
Re @davexunit:
I talked to @wingo about this briefly. He challenged me to think of a time when I resumed a continuation more than once in a real world program. I couldn't think of an example. So, I think we feel that multi-shot is not a must-have for delimited continuations in the Hoot project.
Racket comes with a continuation-based web server framework that makes extensive use of resuming continuations multiple times.
Here's a miniature but concrete example: running this program will start the server on an ephemeral port and open it in your browser.
#lang web-server/insta
;; "Add Two Numbers" web application
(require web-server/formlets)
(define (ask-for-number message-html)
(send/formlet
(formlet (#%# ,{=> input-string the-string}
(input ([type "submit"])))
(string->number (string-trim the-string)))
#:method "GET"
#:wrap (λ (form-html)
`(html (head (title "Add Two Numbers"))
(body (h1 "Add Two Numbers")
,message-html
,form-html)))))
(define (start request)
(define first-number
(ask-for-number `(p "Enter the first number.")))
(define second-number
(ask-for-number `(p "Enter a number to add it to "
(b ,(number->string first-number))
".")))
(response/xexpr
`(html (head (title "Add Two Numbers"))
(body (h1 "Add Two Numbers")
(p ,(number->string first-number)
" + "
,(number->string second-number)
" = "
,(number->string (+ first-number second-number)))))))
Here, send/formlet is an abstraction over call/cc. It stores the continuation and embeds a handle to it into the URL it uses as the action for the form-html. It then sends the response to the user and aborts to a prompt. When a request is received for a URL that references a continuation handle, the framework retrieves the stored continuation and resumes it with the request object.
Obviously, using the "refresh" button, "duplicate tab", etc. all involve invoking the continuation in the page's URL multiple times. More interestingly, imagine you have gone through the interactions to the result page, then use the "back" button and supply a different second-number. When you submit the form, you are resuming the continuation in its action a second time with a different value.
