Add a draft "canonical ABI"

[alexcrichton]

This PR proposes a "canonical ABI" for interface types. This feature was alluded to in Luke's recent presentation to the CG, and this PR intends to flesh it out more and get a more formal specification of what it might be.

The idea of a canonical ABI is that the adapter language for interface types is one of the most complicated parts of the proposal, but with a canonical ABI we might be able to separate out the adapter language to a future proposal so we can get the goodness of interface types on a smaller time-scale.

The ABI proposed here is not intended to be a "one size fits all" ABI. It does not express the full power of interface types as-proposed today (intentionally). It's hoped, though, that the adapter language as proposed in this repository right now can be seen as largely just an optimization over what the canonical ABI specifies. This way languages and tooling can work with the canonical ABI by default, and if necessary for performance a custom ABI can be used with custom adapters in the future. One way to think about this canonical ABI is that it's a generalization of the current list.lift_canon into encompassing entire function signatures in addition to lists.

This PR describes the canonical ABI with a large amount of Python-like pseudo-code which describes the lift and lower operations for types, culminating in a fuse function which shows precisely how lifting/lowering happens when modules call each other.

[programmerjake]

one issue with passing string and other types: there should be a way for the caller to indicate that they're passing a buffer that they don't want to free, because they're going to still use it after the function call.

[alexcrichton]

@programmerjake that'll definitely be supported with the full power of interface types and adapter instructions, but I think for the canonical ABI it may not be included. That's ok though in that the canonical ABI is just a stepping stone to get to the final interface types adapter instructions world in the end, so any performance issues (like reusing buffers and such) will all be enabled once the canonical abi isn't the only one you have to adhere to.

[RossTate]

Wow, this is some impressive work! Although I haven't had a chance to work through the details of the newer interface types yet, this looks like it should be forwards compatible with the more advanced kinds of adapters that have come up in discussions. Thanks for putting this together!

One technical observation I should make is that the canonical representation of an interface type defined here does not respect subtyping. In particular, a variant with fewer cases is a subtype of a variant with more cases, but their representations will differ. I don't know the usage scenarios y'all have in mind well enough to say whether this is a problem or not, so I'm just noting the fact for those who do.

One concern I have is that, if the data you want to exchange is not aligned with the canonical representation, then this involves a lot of copying (supposing the data is in a list). I understand that the need for a canonical ABI comes from time pressure and the fact that more advanced adapters have more technical details to flesh out. However, there is a middle ground that would be more flexible while avoiding complicated types and fusion algorithms. The complications of the fusion algorithm come from the fact that lifting/lowering instructions can be arbitrarily mixed with wasm instructions and, more problematically, control flow. While that can enable some really cool and efficient data exchanges, it's too much for now. So, instead, a "simple" adapter could simply specify, for each "interface type" input/output, the lift/lower instruction to use (which are treated orthogonally rather than sequentially, so no control-flow dependencies). That would be enough to enable things like calling an interface import to get a list of data and filtering/aggregating over that data while it's being generated without having to copy it into linear memory (and without the exporter having to copy it into canonical form in its own linear memory). And it could still support bulk lift/lower operations that enable various optimizations when things do happen to be represented canonically in memory.

If that sounds helpful, feel free to follow up with me.

[lukewagner]

@RossTate Good catch with the variant subtyping; the proposed tweaks above should fix that.

The really useful thing about the canonical ABI is that it presents a clear target for toolchains analogous to a normal native ABI, without requiring them to think about any more-esoteric "adapter" concepts at all. Even once we have full adapter functions, the canonical ABI will be valuable for this purpose for toolchains that aren't able to invest time in fancier adaptation. There is potential de(serialization) on both sides, but that's what you'd expect with a fixed ABI and matches what people are doing today with wasm+gRPC and the other RPC/message-passing schemes.

[RossTate]

@RossTate Good catch with the variant subtyping; the proposed tweaks above should fix that.

Oh, actually I was referring to something else, but those tweaks are important too!

What I was referring to was that there are subtypes ty1 <: ty2 for which lift(direction, src, ty1, values) differs from lift(direction, src, ty2, values) (regardless of the tweaks). Likewise for lower.

Even once we have full adapter functions, the canonical ABI will be valuable for this purpose for toolchains that aren't able to invest time in fancier adaptation.

I understand that. I was just pointing out that there's a way to specify simple (i.e. easy-to-fuse) adapter functions that support this ABI, albeit without baking the convention into the specification, as well as a number of other use cases.

For example, suppose someone wanted to implement a search for the first file in a directory matching a given regex via a file system whose interface is "get_contained_files : [(handle File)] -> [(list (handle File))]" and "get_file_name : [(handle File)] -> [string]". With the canonical ABI, this will involve a lot of copying. The file system will have to create each list of contained files in ABI form in order to lift it. Then the searcher will have to allocate space to lower that list (and create handles for files its search may never reach), and then the fuser will have to copy the list over. Likewise each file's name will have to be allocated in the searcher and copied over. But with even simple adapter functions, you can avoid all those copies (and only have handles for files you're actively using).

With advanced adapter functions, you can do some especially expressive and high-performance things. I'm just pointing out that simple adapter functions can still be very useful/flexible/efficient without demanding engine complexity.

[lukewagner]

What I was referring to was that there are subtypes ty1 <: ty2 for which lift(direction, src, ty1, values) differs from lift(direction, src, ty2, values) (regardless of the tweaks).

Could you be more specific so we can fix it? Above you say that a "variant with fewer cases is a subtype of a variant with more cases, but their representations will differ." but note that the lifted representation can be completely different than the lowered representation due to the fact that (with the above tweaks) lifting semantically produces representation-independent abstract values and lowering semantically consumes these abstract values and thus the net result of the fuse() function is to transform representations.

I was just pointing out that there's a way to specify simple (i.e. easy-to-fuse) adapter functions that support this ABI, albeit without baking the convention into the specification, as well as a number of other use cases.

What you're describing sounds like exactly where we started with this proposal, back when it was named "Host Bindings", so it's not a bad idea ;-) We moved away from this design b/c it ultimately only avoids (de)serialization in a small subset of cases (particularly once you consider non-trivial type nesting). Specifying a canonical ABI simply accepts (de)serialization, just like every other cross-wasm-instance communication framework that we're seeing people use today (e.g., gRPC/protobufs, waPC), so the canonical ABI seems to perfectly fit the definition of "MVP".

Moreover, once we do have full adapter functions (which I very much think we should have, so we can categorically eliminate unnecessary intermediate (de)serialization), it would be unfortunate to have two distinct ways to adapt. (Trying to design the per-parameter/result combinators as a "subset" of the final adapter functions would imply that we know the design of adapter functions, which we don't.) In contrast, a canonical ABI is already a valuable complement to full adapter functions for the reasons described in list.lift_canon and for the abovementioned reason that it gives toolchains that don't want to mess with this novel "adapter" concept a simple "C ABI" they can target like normal. Thus, specifying a canonical ABI wouldn't lead to redundancy or wasted effort.

[RossTate]

What I was referring to was that there are subtypes ty1 <: ty2 for which lift(direction, src, ty1, values) differs from lift(direction, src, ty2, values) (regardless of the tweaks).

Could you be more specific so we can fix it?

What I'm trying to point out is that the canonical representation in linear memory of a type does not respect subtyping. For example, adding more cases makes the representation of an existing case in linear memory larger. Reordering cases changes the numbering used in linear memory. You can fix the former issue, but not the latter issue. It's still not clear on how precisely this canonical ABI will be used, so I can't say whether or not this will matter. I just wanted to ensure there was awareness of it.

We moved away from this design b/c it ultimately only avoids (de)serialization in a small subset of cases (particularly once you consider non-trivial type nesting).

I'm not sure why you say this. Simple adapter functions can do arbitrarily nested lists. For example, given an arbitrary nesting of std::vectors (e.g. vector<vector<vector<uint32_t> > >, simple adapters could lift it to an corresponding nesting of list (e.g. list (list (list u32))), and simple adapters could lower that to a corresponding nesting of std.vectors. Same goes for a variety of other common data structures. They're expressive enough to lift/lower to the canonical ABI presented here.

it would be unfortunate to have two distinct ways to adapt.

Well the simple ones would desugar to the advanced ones. More specifically, a simple lifter would desugar to an advanced adapter "producing" just one channel, and a simple lowerer would desugar to an advanced adapter "consuming" just one channel.

[lukewagner]

@RossTate Ah hah, I see what you're getting at. I was thinking about subtyping when one component calls another (where there is no problem since each component states its own type which determines its own private canonical ABI). But, separately, it's a good question whether we want to have a single core module compiled against the canonical ABI of a function type FT be able to call the canonical ABI of any subtype of FT. I can see how that would be useful, so maybe we do want to update the canonical ABI to have that property? (The trickier cases to consider are future subtyping additions like optional record fields or function parameters.)

[RossTate]

In order to handle reordering of cases, you'd need lift_from_memory/lower_from_memory to encode/decode the name of the case, not just the number. Note that it's not just subtyping that's not respected but even equivalence. That is, unless you do (something like) this, the representation will not be canonical for the type—tooling will have to track not just what type is being used but also what particular syntactic encoding of the type is being used. (You'll have to be more specific about the additions you're considering for me to offer suggestions there.)

As for simple adapters, another advantage of them is that, rather than importing/exporting various name-mangled "intrinsics", you can specify the relevant functions as part of the adapters themselves. Same goes for tables and memories.

[fitzgen]

Adding support for subtypes in the canonical ABI seems like a lot of additional complexity. It isn't clear to me that the benefit we get from adding that support is worth this additional complexity.

[lukewagner]

Hmm, yes, there seems to be a direct tension between the flexible subtyping we want to allow at the inter-component level (where it's basically "free"), and allowing subtyping at the canonical ABI level where it adds real cost. Observing that syscall ABIs tend not to support flexible subtyping either (when changing a signature, they either are very careful to only extend in binary-compatible ways or else they define a new *2 or *Ex version), I suppose this is fine.

[RossTate]

Sounds good. I was going to suggest that you could use variable-sized encodings of the case number to at least let you add arbitrary cases, but then I realized that could introduce a data dependency between record fields (i.e. the offset of one field depends on the contents of another field) that would be problematic for some of the extensions you've said you're hoping to have (such as not requiring fields to be accessed in strictly left-to-right order). So we just have to take incompatibility between subtyping and standardized encoding as a (reasonable) loss and make sure tooling takes that into account (e.g. doesn't represent variant types as simply name->type dictionaries).

[RossTate]

I just realized that the lowering of lists for the canonical ABI seems to assume that the length of the list is always available up front, whereas the list.lower instruction in the explainer does not (and the list.lift function provides no such guarantee). Was this an intentional change to lists? If so, how are y'all expecting to accommodate and enforce it in the full version?

[lukewagner]

That's what the realloc is for.

[lukewagner]

Sorry, I borked the master-to-main rename and deleted the branch this PR which I guess closes the PR. We'll create a new PR and link to it from here shortly.

[sbc100]

Sorry, I borked the master-to-main rename and deleted the branch this PR which I guess closes the PR. We'll create a new PR and link to it from here shortly.

I think you can just re-open an re-target to main?

[lukewagner]

I must've pressed delete too hard, because I couldn't find a way to resurrect the branch. In the meantime, Alex just opened #140. Sorry again for the hassle!