Consistent parameter order between cont.bind and switch tags

[rossberg]

The explainer currently proposes to change the order in which cont.bind binds arguments. However, it needs to remain possible to use cont.bind to supply the (regular) arguments to a continuation used with switch, otherwise certain usage patterns that use cont.bind to unify continuation argument types would break (see comment for some context).

If we keep the changed order of cont.bind, we hence need to consistently change the position of the continuation parameter to a switch tag from last to first:

   - and `C.types[$ct1] ~~ cont $ft1`
   - and `C.types[$ft1] ~~ [(ref null? $ct2) t1*] -> [te1*]`

[tlively]

IMO the most important desugaring is of cont.bind into a resume that sends the bound arguments to a wrapped version of the continuation that stores the bound parameters, suspends back to the point of binding, then calls into the original continuation function the next time it is resumed.

For that desugaring you want the continuation operand to cont.bind to come last to match its position in resume. This lets you rewrite (op1) ... (opN) (cont.new $ct $f) (cont.bind $ct $ct') (resume $ct') to (op1) ... (opN) (cont.new $init_ct' $wrapped_f) (resume $init_ct') (resume $ct')

[tlively]

Also, unless I'm mistaken, your motivating use case of desugaring switch to cont.bind + suspend also works best when the continuation reference is the last operand:

(op1) ... (opN) (cont.new $ct $f) (switch $ct $e) Rewrites to (op1) ... (opN) (cont.new $ct $f) (cont.bind $ct $ct_empty) (suspend $e).

When binding from right to left, this rewriting works for binding any number operands, not just when binding all of them.

[fgmccabe]

I am not sure that I fully buy the desugaring argument for cont.bind.

My reasoning is that that desugaring (into a resume followed by a suspend) requires changing the operand.

A similar argument would allow us to claim that int32.mul was a sugared version of f32.mul.

[tlively]

Yes, the desugaring is nontrivial and requires more than local changes, but it's still worth it to make it as simple as possible despite that. The simpler desugaring is, the simpler re-sugaring is, and the re-sugarings might be useful optimizations that we actually want to do in e.g. Binaryen.

[rossberg]

To be clear, something that cannot be performed locally and requires global knowledge is not a desugaring but a general transformation. That is a qualitative difference: desugarings are compositional with the rest of the language and can hence e.g. be used in an interpreter or to define semantics, whereas a general transformation requires a global transformation pass over the entire module/program, which only works in a proper compiler or tool pipeline.

(And of course, a construct being expressible by global transformation generally is a vacuous statement, because it ultimately is universally true for Turing-complete languages.)

For the purposes we are interested in here it is hence relevant that this is a proper desugaring. Concretely, the expression of cont.bind via suspend/resume that you allude to is not of that nature afaics, for example because it would need to add tag definitions depending on all uses of cont.bind.

On-topic, re parameter order: the relevant pattern is one where stack switches of different type need to be funnelled through a single common handler or abstraction, which requires all the continuations to have a unified type. Once you start implementing various examples, that quickly emerges as a common pattern. It can be expressed by cont-binding the differing arguments at the code site initiating the switch/suspend, only leaving the common ones. The target continuation always is common, naturally — otherwise the handler/abstraction couldn't do anything — so must be the last to be affected by cont.bind.

[tlively]

Sure, instead of "desugaring" I should have used "rewriting." I agree that these non-local rewritings are not useful for interpreters or specification, but they are useful for optimizers, and it is not vacuous to try to make the design as optimizable as possible.

So if I understand correctly, you want to be able to desugar or rewrite (op1) ... (opN) (ref.cont a) (switch $ct $e) to (op1) ... (opN) (ref.cont a) (cont.bind $ct $ct_nullary) (resume $e'). Is that right? If so, I don't see why that requires switch to take the continuation reference first. In fact, it seems that this rewriting only works when cont.bind, switch, and resume all agree that the continuation reference comes last.

[rossberg]

The scenario is more like having an abstraction, e.g., a function, to perform the actual switch (and perhaps some house-keeping) but having to use that with continuations of conceptually heterogeneous type. To make that work, you'll have to replace, say, multiple sites like

(op11) ... (op1N) (ref.cont a1) (call $yield)

and

(op21) ... (op2M) (ref.cont a2) (call $yield)

(note the different number of ops), but in a type-correct way, which requires that the continuations passed to $yield all have the same type and fixed parameters. The way to do that is e.g. by changing the above to

(op11) ... (op1N) (ref.cont a1) (cont.bind $ct1 $ct) (call $yield)

and

(op21) ... (op2M) (ref.cont a2) (cont.bind $ct2 $ct) (call $yield)

such that $yield takes a continuation of uniform type $ct. If $yield is implemented by switch, then this $ct still receives the continuation parameter. So for these cont.bind's to work, that parameter must be the last to bind.

FWIW, this is a pattern very familiar from languages with currying, where you typically structure functions such that the least varying parameter comes first.

[titzer]

I think it's more consistent with the rest of Wasm to keep the continuation as the last argument. I have a slight preference for left-to-right binding for cont.bind because that is most consistent with how the value stack is laid out naturally[1] in memory for in-place interpretation and baseline compile that is compatible with in-place.

At the implementation level, with left-to-right binding, a continuation has a value stack that just grows normally by pushing more arguments onto it. If we have right-to-left continuation binding, then the value stack has a reserved range (i.e. a "hole") that gets filled top-to-bottom, with value entries in the middle being uninitialized.

Left to right, suspended continuation:

cont: | frame | frame | frame | v1 v2 v3 |
                                         ^ top of stack

After binding:

cont: | frame | frame | frame | v1 v2 v3 |
                                         | v4 v5 v6 |     cont.bind
                                                    ^ new top of stack

Then resuming:

cont: | frame | frame | frame | v1 v2 v3 v4 v5 v6 |
                                                  | v7 v8 |     resume
                                                          ^ new top of stack

In contrast, a suspended continuation with right-to-left has a hole where values will go, right to-left:

                                                        v hole
cont: | frame | frame | frame | v1 v2 v3 __ __ __ __ __ |
                                                        ^ end of stack

After binding:

                                                        v hole
cont: | frame | frame | frame | v1 v2 v3 __ __ __ __ __ |
                                                        ^ end of stack
                                                 |v7 v8| cont.bind
                                                 ^ new hole

Then resuming:

                                                 v hole
cont: | frame | frame | frame | v1 v2 v3 __ __ __ v7 v8 |
                                                        ^ end of stack becomes top of stack
                                        |v4 v5 v6| resume
                                        ^ hole filled completely

[1] I say naturally, because it wouldn't matter except that we made a choice with how locals are numbered at function calls that ended up making "value stack grows towards higher addresses" a smidgen more efficient. For an N argument call, the deepest argument becomes local 0.

[tlively]

@rossberg, your desired rewriting makes perfect sense, but I don't see how it requires that the continuation reference for switch comes first. switch doesn't even appear in your example.

[rossberg]

@tlively, switch will occur inside the $yield function, but the continuation passed to $yield must already have a type suitable for switch — in particular, that receives the suspended continuation in the last position. Hence, if at the same time cont.bind works right-to-left, then you can't meaningfully use it for any sort of continuation also used with switch.

@titzer, I'd also prefer keeping cont.bind as is. But if we change it, then we must change the switch continuation accordingly.

[tlively]

@rossberg Oh, I see, thanks. It is unfortunate that cont.bind must bake in a policy decision about binding order (cc @fgmccabe, I know you have opinions about this!). Binding right-to-left is easier and plays more nicely with calling conventions in an optimizing tier, but I believe @titzer's claim that binding left-to-right is easier and more efficient in some interpreters and baseline tiers. To rewrite a sequence of cont.binds into a single cont.bind or fold it into a subsequent resume, it's simplest if cont.bind binds right-to-left, but for use with the formulation of switch we prefer, it needs to bind left-to-right.

This all reinforces my belief that we should just leave cont.bind out, at least initially, and let it be implemented in userspace as necessary. That's what we decided to do for func.bind, and that seems to have been a reasonable decision. If experiments with early users show that the absence of cont.bind is a performance issue, I'd be happy to add it back in.

If it comes down to a choice between having right-to-left binding cont.bind and having switch continuation take the return continuation as their last parameter, I would prefer to give up the latter and make the change @rossberg is suggesting.

[fgmccabe]

I would push back against the 'do it later' argument. This is (IMO) a potentially critical optimization for Kotlin & Swift (for different reasons). Remember that, in the best case, in V8, a switch it likely to cost of the order of 10 function calls. (Certainly not less than five, currently more like 20).

[tlively]

If we move the continuation produced by a switch before the other received values, how about we move the continuation produced by a suspend before the other received values as well to keep the orders consistent?

[rossberg]

I would also push back strongly on dropping cont.bind. It was needed in at least half the use cases we looked at, and there is no efficient alternative. Moreover, that would just increase the likelihood of making a forward-incompatible decision elsewhere.

If we move the continuation produced by a switch before the other received values, how about we move the continuation produced by a suspend before the other received values as well to keep the orders consistent?

Not sure I follow — suspend does not produce a continuation. Suspend handlers do, but those do not have a built-in continuation parameter.

[tlively]

If we move the continuation produced by a switch before the other received values, how about we move the continuation produced by a suspend before the other received values as well to keep the orders consistent?

Not sure I follow — suspend does not produce a continuation. Suspend handlers do, but those do not have a built-in continuation parameter.

I'm thinking of the label types. We can make the label types receive the suspended continuation before other values for consistency with switched-to continuations receiving the switched-from continuation before other values.

[tlively]

What if we had cont.bind take a bitvector specifying which arguments should be bound? Obviously that's more complicated to implement, but it avoids baking in any policy and lets each use case do whatever it needs without forcing us to make other changes we don't want to make.

[rossberg]

I'm thinking of the label types. We can make the label types receive the suspended continuation before other values for consistency with switched-to continuations receiving the switched-from continuation before other values.

Ah, I see. Yes, that should probably change in the same way.

What if we had cont.bind take a bitvector specifying which arguments should be bound?

Given that the only argument for changing the order was to avoid shuffling registers in some implementations, how would that help? Then we can just as well keep the natural left-to-right.

[tlively]

It’s also worth noting that all the usual methods of implementing partial application for functions in user space (i.e passing bound context as a parameter) are also still available for continuations, and would be much more efficient than implementing partial application with stack switching.

I’m still not convinced that real-world producers would have enough trouble with user space solutions to merit cont.bind, although it’s clear that it is helpful when crafting examples by hand. Can we spec it for now to make sure it is compatible with the rest of the design, but plan to drop it if early toolchain partners don’t turn out to need it?

[rossberg]

I'd expect explicit passing of context parameters to be more expensive, because you usually have extra allocations and indirections, and you have to lose type information and recover it with casts (when using GC types). In contrast, cont.bind is statically type-safe and can be implemented allocation-free, which is possible thanks to the linearity of continuations.

We can always revisit any part of a proposal. That said, I doubt we can easily get away without cont.bind, primarily using as an effective way to work around the limitations of the type system.

[tlively]

I previously wrote,

If it comes down to a choice between having right-to-left binding cont.bind and having switch continuation take the return continuation as their last parameter, I would prefer to give up the latter and make the change @rossberg is suggesting.

With the new understanding that right-to-left binding would come along with received continuations coming before passed arguments for both switches and suspend handlers, I'm switching my preference to left-to-right binding, assuming we do have to have cont.bind. Having the received continuations come last makes the order of receiver-side parameters the same as the order of sender-side arguments, and we definitely don't want to change the order of arguments on the sender side because that would break consistency with e.g. call_ref.

[conrad-watt]

Should we switch the explainer to use left-to-right binding then?

[tlively]

I think that makes sense for now, but we should make sure @fgmccabe is on board.

[fgmccabe]

I am 'ok' with keeping the left-to-right ordering. Just know that you are baking in additional complexity and performance costs for the foreseeable future.