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.