Make funcref not a subtype of anyref

[RossTate]

(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.

[lukewagner]

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.

[rossberg]

@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).

[RossTate]

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.

[rossberg]

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.

[RossTate]

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.)

[rossberg]

@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.

[RossTate]

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?

[rossberg]

@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.)

[RossTate]

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.

[rossberg]

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.

[lukewagner]

@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.

[rossberg]

@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.

[lukewagner]

@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.