Make funcref not a subtype of anyref

(This idea came up after yesterday's discussion about the GC extension. I have tried to describe it here in a self-contained matter, but let me know if there are any terms I forgot to define or motivations I forgot to provide.)

Having funcref be a subtype of anyref forces the two to have the same register-level representation. Yet there are good reasons why an engine might want to represent a function reference differently than an arbitrary reference. For example, function references might always be an assembly-code pointer paired with a module-instance pointer, effectively representing the assembly code compiled from a wasm module closed over the global state of the specific instance the function reference was created from. If so, it might make sense for an engine to use a fat pointer for a function reference. But if funcref is a subtype of anyref, and if it overall makes sense for arbitrary references to be implemented with normal-width pointers, then that forces function references to be implemented with normal-width pointers as well, causing an otherwise-avoidable additional memory-indirection in every indirect function call.

Regardless of the reason, by making funcref not a subtype of anyref, we give engines the flexibility to represent these two types differently (including the option to represent them the same). Instead of subtyping, we could have a convert instruction that could take a function reference and convert it into an anyref representation, or more generally could convert between "convertible" types. The only main benefit of subtyping over conversion in a low-level type system is its behavior with respect to variance, such as co/contravariance of function types, but I see no such application for funcref and anyref. And in the worst case, we could always making funcref a subtype of anyref later if such a compelling need arises.

To add to this, one change in my understanding of the constraint space is that, in earlier design thinking, there was an expectation that anyref would serve as the universal representation of reference types in the presence of source language polymorphism that got erased when compiling down to wasm, and this necessarily required anyref to be the (non-coercive) supertype of all reference types. This design included the ability to downcast from anyref directly to any other type (given the appropriate type tag; all of this in the context of the GC proposal). However, more recent thinking wrt how best to support dynamic downcast suggests that anyref probably isn't the right universal representation type and that, instead, the universal representation type for a particular language/toolchain should be some ABI-defined wasm type that explicitly declared more details of what was downcastable and how. There are multiple ideas in flight here, which I expect will be hashed out over the coming months, but the common theme seems to be moving away from anyref as the universal representation.

Thus, in the short term, I think we should avoid unnecessarily committing to funcref <: anyref in the reference-types proposal, which is nearing stage 4 and shipping. Implementation-wise, this should be a fairly simple change to make, I believe.

The win from not unnecessarily requiring funcref <: anyref is that, as Ross explained, it buys us more implementation freedom. I actually think an AOT compilation model of type imports will require all references to be pointer-width (otherwise a VM would have to wait until instantiation time to know the number of bytes to shuffle around for a (ref $TypeImport)). However, what I think dropping funcref <: anyref would buy us is the ability to have different word-sized representations of funcref vs. anyref that didn't require them to share a single boxing format. (This assumes that the GC can either use arena or instance data to trace (ref $TypeImport) words in the generically-compiled module code.) In particular, some recent (and I think essential for a high-performance function-reference implementation) ABI changes we're planning for SM would be simpler and more efficient if funcref could have a pointer-sized, but completely different representation from anyref.

@lukewagner

@lukewagner, can you explain under which scenario you would be able to allow different tagging strategies for function references but not different sizes?

Because I see only two possibilities: either the universes of funcrefs and other refs are always statically distinguishable, in which case they can also have different sizes. Or there are cases where you cannot tell them apart statically, in which case you'll also need compatible tagging schemes.

So, AFAICS, to allow different representations you have to create two properly disjoint type hierarchies. That is certainly possible, but is a less trivial change than just removing the funcref <: anyref rule. You would need to make sure that there are no common super types, but also no common subtypes and values. One immediate implication, for example, is that you'd need to distinguish different null values and types, and thus modify or complement the ref.null instruction. That in turn would not just affect the reftype proposal but also the bulk memory proposal. There may be other such implications, we'd have to think it through carefully.

Another question is how this interacts with the host. You can pass Wasm functions to JS and JS functions to Wasm. Both would necessarily become a coercive operation. That works in the first-order case, but does not compose. E.g. once you want to allow Typed Values over functions in JS you'd have to distinguish e.g. arrays of JS functions from arrays of Wasm functions. That is, you would need to introduce two disjoint universes of function types for Typed Values. (Maybe you're already assuming this?)

The last time separating funcrefs from anyref was discussed (I think at the Lyon meeting) the consensus was that the added language complexity was not worth it for the time being, and that we can always add a second form of funcref type later if there is evidence that it is sufficiently useful.

Btw, regarding uniform representations, I think we have thrown up some vague ideas for possible alternatives, but AFAICT nobody has worked them out and they'll likely be beyond MVP level. It seems premature to assume that we won't need anyref. If we divorced funcrefs then additional boxing may become necessary in client code (which may not be a problem, however).

Yeah, we discussed the issue with null too, concretely discussing how a universal nullref type would block engines out of using fat pointers where appropriate. I also mentioned here that we were finding, contrary to our original expectations, that nullref should be parameterized.

I guess it boils down to the question: do we reconsider "fat function refs" to be an MVP feature or can we add it later as a separate type? If the former, I agree that we should do so quickly, so that we can move forward at the meeting.

Well, there's another question: what are the pressing use cases of having funcref be a subtype of anyref in the MVP? (Use cases that aren't addressed by having funcref be convertible to anyref.)

@RossTate

@RossTate, I don't know about pressing, but I can think of a number of softer reasons: it makes for a somewhat simpler language, gives more seamless host interop (at least on the web and in the C API), avoids redundant annotations in element segments (for which we may want to come up with a solution otherwise), and of course, avoids late phase churn for a number of implementations.

I disagree on the simpler language argument. People argued for F-bounded polymorphism on the same basis that having everything be done through subtyping would be simpler. Instead they got undecidability and unnecessary complexity that crippled tooling.

As for late-phase churn, this should only require a change in the type-checker, and I imagine removing a subtyping is fairly straightforward.

Can you go into more depth on one of the other reasons?

@RossTate

@RossTate, it requires changes/extensions to the instruction set, see ref.null, and the type language, see nullref. It also requires observable changes to current APIs, where some of these are reflected. For the C API, for example, the changes would go deeper, because that currently models a simple uniform ref space, and externval's are just refs. Removing that possibility (as opposed to just complementing it) requires a redesign of that part, replacing it with something more complicated.

Can all be done, no question. But clearly not free or cheap. I'd be interested in hearing from @lukewagner how important he considers having this for the first version, and whether it should fully replace or merely amend the current design.

(I don't follow which similarity to F-bounded quantification you see.)

F-bounded polymorphism is essentially a way of encoding a limited form of type classes into subtyping. In particular, X <: Comparable<X> ensures via subtyping that values of X have a compareTo(X) method. This was considered "simple" because it repurposed the existing subtyping feature. However, because subtyping is an extremely critical feature that interacts heavily with other features of the language, this "simplicity" made much of type-checking, even subtyping itself, undecidable, and broke much of the tooling for languages that added this feature.

Of course, the actual use case this was meant to address, i.e. the binary-method problem, could have just as easily been addressed by introducing a new kind of type constraint. X satisfies Comparable<X> similarly ensures that X has all the methods of Comparable<X> but without making X a subtype of Comparable<X>. Although this design adds a new kind of constraint, it also obliviates the need for recursive subtyping and recursive class/interface hierarchies, keeping the language as a whole much simpler.

This satisfies design is theoretically less expressive than the F-bounded design. That is because subtyping interacts with things like variance of functions and data structures. But it turns out there are not actually real use cases for that difference in functionality. So in practice, the two designs are equivalently expressive, with one being much simpler to implement even if its grammar is slightly more complex. The satisfies design also turns out to be more flexible in what kinds of implementations and extensions it permits.

So the analogy is that the subtyping funcref <: anyref seems to have been added because it was the way to make funcref convertible to anyref requiring the fewest changes to the grammar. But you have yet to give me a use case where the additional expressiveness this provides over just a conversion instruction actually enables more useful WebAssembly programs. So I worry that you are permanently saddling the type system with additional complexity and limiting flexibility in the implementation strategies without any real benefit (besides the fact that it will take a relatively small amount of effort to correct the design) due to a faulty sense of simplicity, much like what happened with F-bounded polymorphism.

I'm aware of the risks of F-bounded quantification if taken too far, but come on, there is no similarity with the issue at hand. Its impact on the type system and its meta theory is negligible either way. If anything, establishing disjoint type hierarchies is a marginal complication to the meta theory, since you'd be under obligation to prove a little lemma that verifies that property.

I have given you reasons above, like fewer and simpler instructions, simpler and more uniform host APIs, etc. Nothing earth-shattering, but arguably an appropriate default for an MVP, unless there are crucial problems that the MVP has to address or it precludes later addition. Evidence for the former would be it being a roadblock for engines.

@rossberg

@rossberg (sorry for the slow reply) If a type is imported with no bounds:

(module
  (import "file" "handle" (type $Handle))
  (func $f (param (ref $Handle)) ...)
)

then $Handle can be either anyref or funcref and so if we want to compile $f AOT (and never recompile), we need all ref's to have the same byte width because we don't yet know whether we have an anyref subtype or a funcref subtype. However, because there is no bound, there are no explicit operations in $f that need to dynamically distinguish an anyref from a funcref, so they don't need to share a boxing/tagging format. (There is still, however, the implicit operation of marking a (ref $Handle) value found on the stack during GC, but that can be a somewhat slower operation (which, e.g., determines $Handle using the frame's containing instance's import table, which will take 10s of cycles) compared to a the core wasm GC instructions where every cycle counts.)

On a side note: if we wanted to allow different byte widths without recompilation, we could perhaps always require type imports to have a bound, and so you'd always know if you had an anyref subtype or a funcref subtype, and then they could have distinct byte-widths. I don't have a good sense of the pros/cons of this yet option, though.

@lukewagner

@lukewagner, not sure that could work in general. Depending on how much code generation in a given engine has to know about GC, it probably will need to know what kind of tagging e.g. a local of that type uses, e.g., to generate suitable stack frame descriptors, or inlined bits of GC code, etc. It's safer to assume that a compiler always needs to know the representational interpretation of any value it has to handle.

But in any case, the type import proposal already defines what you suggest: all imports have a bound -- given subtyping, there's no advantage in having an unbounded form.

@rossberg

@rossberg Ah, in that case, then I agree that, if funcref is not a subtype of anyref, it would allow funcrefs to have a completely different representation (including byte width) than anyrefs.

We discussed this in the Feb 2020 CG meeting. We didn't come to any conclusion, but there was some agreement that breaking the subtype relationship between anyref and funcref would be more conservative.

@fitzgen

Given that multiple ecosystems (Emscripten, Rust, WASI) eagerly want anyref support but don't particularly need funcref right now, I would like to either resolve the subtype question quickly or revisit @fitzgen's idea of splitting the proposal so that anyref can move forward alone without being held back by this issue. I understand that the semantics would be ugly in the interim, but it would be shame to hold up these ecosystems for a temporary cosmetic issue.

Of course, there would be much less overhead if we could agree to a solution to the subtype question soon and not have to split the proposal. I lean heavily toward not having a subtype relationship between funcref and anyref right now since it is both the simpler conservative option and because I do not know of any immediate usecase for that subtype relationship. Having type-parameterized nullrefs sounds perfectly acceptable to me, since it will make the tooling simpler anyway. I am also not too worried about the size impact for table initialization since a sequence of identical parameterized nullrefs sounds like it will compress easily.

@rossberg

@rossberg If we remove subtyping we know exactly what the consequences are; it's hard to call them "risks", they're just fixed "costs". "Risk" refers to the fact that we do not have a complete picture of subtyping at this point, and we won't until we've put "pressure" on subtyping via Type Imports and Function References.

@lukewagner

@lukewagner:

If we remove subtyping we know exactly what the consequences are

A bold statement. ;) I for one don't. How can we adapt the C API? What design implications will type-indexed null values, which are uncommon, have in the future? Do we get the format of the new immediates right? It's folklore wisdom that last minute design changes are a favourite source of errors and unforeseen consequences.

I think we should hold off on committing to a stable C API until we know more about subtyping. Until then, embeddings are already doing something now and can keep doing so. I've got to chuckle a bit at comparing the unknowns for the ref.null immediate binary format to something as cross-cutting (and hazardous in folklore wisdom) as subtyping.

One down side to removing subtyping is that it creates the need for two instructions, funcref.null and anyref.null (or externref.null). But it occurs to me there might be a better solution. These instructions exist because types need default values (for a while). It seems likely that wasm will need to add more types over time. So rather than coming up with a new instruction each time, what if we just had a single instruction default $t : [] -> [t] that produces the default value for the defaultable type t? One nice thing is that this would work even for imported types (by the way, Type Imports has no discussion of defaultability, which is a type constraint that is not expressible with upper-bound constraints). Another nice thing is that it naturally extends to defaults t* : [] -> [t*], which would pair nicely with things like the upcoming let construct as observed in WebAssembly/function-references#20 (comment). Similarly, we could have a single instruction is_default : [t] -> [i32] (no type annotation necessary), which indicates whether or not the given t value is the default value for a defaultable type t. Hopefully that would address concerns about "warts" caused by removing subtyping. But maybe y'all have already discussed this option before?

There will be an infinite set of different nullable types and hence null values. Consequently, it would not scale to add multiple null instructions. Instead, we'd add one type-indexed null. That's still a wart, because it doesn't mesh well with subtyping on that index type. For example, although technically different, null $T and null $U will have to be considered the same value if $T <: $U, which will require identifying multiple values. From that perspective, type-indexing null is not natural in the presence of subtyping and creates artificial complication.

None of this is related to defaulting. As for the default instruction, there is some confusion here on multiple levels. First, it cannot change anything about imports. You can already emulate its behaviour via auxiliary functions that return their default-initialised locals, so it wouldn't add any new expressiveness that magically provides something new for imports. But I also don't see any problem with imports. Nullability is a property of ref types, not type definitions: a local of type ref $t can never be defaulted, you'll need to type it ref null $t (previously called optref). That's completely independent of what $t is or whether it was imported.

Your first paragraph seems to be about formalization/specification. The formalization research community offers multiple ways to specify this pattern. The one you give is one of them, and is not considered to be particularly unnatural (it just says that values are (co)variant with respect to subtyping, the natural analog to type-level considerations). But if you don't like the idea of the same constant having multiple representations, which I understand, then you can say that null $T is only valid if $T is minimal with respect to subtyping. (You already have the requirement that $T is a "reference type".) At the moment there are only two such minimal types though, so having distinct constants funcref.null and anyref.null is not unreasonable.

As for the second paragraph, I realized I missed a step. From my earlier comment, I still had in my mind type imports rather than just reference type imports. So yeah, filling in that disconnect, it makes sense why reference type imports has no discussion of defaultability; sorry for being confusing there. But if ever wasm does add true type imports, then it will need a notion of defaultability (since types like ref $t are not defaultable), and that's a simple example of a type constraint that is not expressible via subtyping. Who knows if that'll ever happen though, so at this point it's just a thought to keep in mind.

But focusing on the here and now, do the default(s) and is_default instructions seem useful?

How is there a minimal type in an open subtype hierarchy?

The type ref $t wouldn't even make sense if $t was not a referable type, so I don't quite follow what you are saying in the second paragraph.

IDK if there is any good use case for a default instruction. Arguably, defaulting is primarily a hack for initialisation, out of necessity, not a particularly desirable feature in general. At least I have never heard anybody asking for it.

At least I have never heard anybody asking for it.

In investigating the rationale of the design, I have had multiple people explain that they wanted a direct way to construct and test for the default value. That seems to be the general pattern. Right now that pattern is being served by providing separate instructions for each type with a default value. But given that default values are a core feature of WebAssembly, whether just out of necessity or not, it seems another reasonable way to address that pattern would be to have general-purpose instructions for constructing and testing for default values.

Adding link to most recent discussion for reference: April 21

We had a poll at the Apr 28th meeting, with the following results (where SF represents strongly in favor of removing subtyping, and SA represents strongly against removing subtyping):

SF: 7
F: 9
N: 8
A: 2
SA: 5

At least one member of the group voted SA because there was no discussion during the meeting. We had discussed this topic at previous meetings, but none at this meeting.

Because the poll was at the end of the meeting, we weren't able to succinctly state a conclusion. I think this poll does offer some clarity, still. We should take this to mean that the group as a whole slightly favors removing subtyping, and we should proceed accordingly.

I apologize that this poll was a little haphazard. Please feel free to reach out to me to discuss any concerns you have about this decision.

Remove subtyping (#87)

Update `ref.null` encoding after subtyping change

Update `ref.null` encoding after subtyping change (#149)

[test] Minor cleanup to generated output (#69)

Navigation Menu

Repository navigation

Make funcref not a subtype of anyref #69

40 remaining items

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Make funcref not a subtype of anyref #69

Description

Activity

lukewagner commented on Dec 23, 2019

rossberg commented on Jan 8, 2020

RossTate commented on Jan 9, 2020

rossberg commented on Jan 13, 2020

RossTate commented on Jan 13, 2020

rossberg commented on Jan 13, 2020

RossTate commented on Jan 13, 2020

rossberg commented on Jan 14, 2020

RossTate commented on Jan 14, 2020

rossberg commented on Jan 15, 2020

lukewagner commented on Jan 20, 2020

rossberg commented on Feb 3, 2020

lukewagner commented on Feb 3, 2020

binji commented on Feb 13, 2020

tlively commented on Feb 14, 2020

40 remaining items

lukewagner commented on Apr 22, 2020

rossberg commented on Apr 22, 2020

lukewagner commented on Apr 23, 2020

RossTate commented on Apr 25, 2020

rossberg commented on Apr 27, 2020

RossTate commented on Apr 27, 2020

rossberg commented on Apr 27, 2020

RossTate commented on Apr 27, 2020

RossTate commented on Apr 28, 2020

binji commented on Apr 28, 2020

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions