Minimal delta for evaluating nominal types

[titzer]

After much reflection, and after many offline discussions with people involved here, I think the best way forward to start undoing the schism between structural and nominal types is to gather empirical data with a true apples-to-apples comparison.

I think we should work together, here, in this issue, to define the minimal extension to the Wasm GC MVP, which currently has equi-recursive structural types, to add a nominal types mechanism. Note, by minimal, I mean, the tiniest possible addition, not a radical design change or throwing away what we have. We need to keep forward momentum and not circle back.

As I mentioned in #232 (comment), our technical discussions have a tendency to either go off the rails or get dragged into the same divisive grooves. At times they have actually been negative progress. In contrast, the positive developments we have enjoyed recently have all be centered around implementing things and trying them out, both in the reference interpreter, tools, engines, and with languages targeting the current proposal.

There are many perspectives on what this means, but most importantly I believe doing this will turn schism-like discussions into empirically-evaluable programs to be written. The mode of argument can be code that can be typechecked and run. Fewer discussions about hypothetical alternatives. Performance costs can be quantified, tools can be adjusted, languages targeted differently. Doing things together in the same reference interpreter, engines, with the same text and binary format, even if that is literally (the smallest possible) union of two seemingly different ways of doing the same thing, makes it possible to have the clearest and fairest comparison. I think that would be hugely healthy for our collaboration for us all to work together on this path forward.

Let's please also do this without committing to a particular outcome, though we might have strong opinions on what that might be. For example. if it does turn out in the end that we need to ship the "union", then I say, in all seriousness, so be it. If it turns out that that we can't ship structural types, then so be it. If we can't ship nominal types, so be it. That means that we probably might end up ripping out one or the other...and, again, so be it. At least we'll have the work done, and we will have arrived at that decision via a chain of trial and error and not exasperated submission (which unfortunately, seems to be the only outcome of protracted technical digression could ever produce). I think this path is the most efficient, fairest, and respectful way to get not only useful data, but an almost-done system we can ship with confidence.

[RossTate]

Thanks for your efforts in the offline discussions! I am definitely happy to do this. Unfortunately at the moment I'm swamped with a big deadline due next Friday, so I don't have time at the moment to write up my thoughts on what such a delta is. But maybe that's a good thing, as it seems like the first thing to do is really to gauge or establish consensus on the overall change in process and maybe flesh out how that would work in more detail (e.g. should we first have a meeting where we discuss the high-level considerations, prior to writing up possible designs?; are we keeping everything in this issue, or is it for developing a starting point to be pulled/unioned in and then iterated upon?; what are the thoughts of generators and engines on how best to handle variations on a proposal?). I have to get back to my deadline, but I'm interested to hear everyone's thoughts. Thanks for working to make room to explore!

[jakobkummerow]

Binaryen has already started experimenting: #226,
J2CL has started emitting matching extends clauses: google/j2cl@908af91,
and V8 is following suit (as a first step, accepting but ignoring explicit supertypes): https://chromium-review.googlesource.com/c/v8/v8/+/3071406.

---

I agree that it would be good to keep the delta to the existing proposal minimal.
That said, a difficulty I see is that diverging a little more could have/unlock/demonstrate benefits as well (example: replacing RTTs with static types could enable check/cast elimination).
I don't have a concrete suggestion how to find a balance there. Roughly speaking, I think we should (together) think through possible designs, e.g. by drafting a specification (maybe in the style of the prototype specification we've been working with in the past), implementing (or attempting to implement) it when it looks good enough, and then iterating on both steps as needed.

[titzer]

Yep, thanks for sharing those @jakobkummerow. I knew this work was already happening and this issue is about getting alignment to do this together. Let's see if we can use this issue to get these experiments aligned and into common agreement. @RossTate I think we don't need a heavyweight design process, but should be able to make progress here in this issue.

[RossTate]

I was going to suggest we spend some of the remaining time in the next meeting to coordinate this a bit, but I see that @tlively is on vacation, and I think his thoughts would be particularly valuable in that effort, so maybe waiting until the following meeting would work better?

[tlively]

One thing to note about the current Binaryen implementation is that you can run it in nominal mode or in equirecursive mode, but you can't do both at the same time. For a new prototype spec, it would be best to allow both to coexist and leave the choice of which to target (or how to best target a mix of the two) to front ends. That would also give us the freedom to add new cast instructions removing RTTs for nominal types without breaking producers currently using RTTs. This wouldn't quite be the minimal addition, but I think it would fulfill the goal of apples-to-apples comparison.

I also think it would be great for this to be discussed in the upcoming meeting. I look forward to seeing the progress you've all made when I get back :)

[lukewagner]

I know the equi-recursive approach is fraught with peril and, before the last presentation, the iso-recursive approach had limited subtyping expressiveness, but, with the revised iso-recursive approach to subtyping presented at the last meeting, are there any known remaining practical problems with iso-recursion? If not, then it seems like iso-recursion is simple and cheap to consume and roughly equivalent to nominal typing to produce (in the simple cases; in the fancy modularity cases, I think the iso-recursive approach wins out by avoiding the need for name mangling approach we discussed last time). Thus, testing out the revised iso-recursive approach by practical experimentation seems like the right next step to me, not forking off a new line of work to experiment with nominal typing.

My reasoning for why is this:

If we take a step back and forget all the madness caused by cyclic types, every other type in wasm is structural and if we were to add any new non-acyclic type, we wouldn't even be asking this nominal-vs-structural question; we'd simply define the new type in the same way that we've defined every other type. For example, let's say we added a non-recursive immutable tuple type (which might be a good idea, btw; it could have a different cost model from struct aimed at hash-consing runtime impl...). The "obvious" way it would look is (something) like:

(module
  (func (export "pair") (param i32 i32) (result (ref (tuple i32 i32)))
    (tuple.new (local.get 0) (local.get 1))
  )
)

That way, any module could import pair and call it without having to worry about "who owns the tuple i32 i32 type?". Sure, we could force them to do that (and require either whole-program knowledge to hoist all the tuple types or exciting runtime name mangling/parsing schemes for the separate-compilation cases), but what would be the benefit, in exchange for all this complexity we were foisting on the ecosystem and breaking asymmetry with the rest of wasm?

• At instantiation-time, the hash-consing we already need to do for cross-module call_indirect can be extended to include tuple param/result types relatively easily. With that, rtt.canon (tuple ...) (assuming tuple adopted the rtt scheme for downcasts in this hypothetical scenario) could reuse the same hash-consing logic.
• At validation-time, optimizing producers would naturally de-duplicate tuple types and thus a type-index-equality fast-path check would cover the 99% case of type-equality testing during validation. Thus, assuming we had reasonable implementation limits on tuple type size, I don't think we'd even need to do any extra hash-consing at validation time; we'd just fall back to a simple structural comparison like we currently do for function types at call sites.

The other motivation for nominal typing I've heard is along the lines of data hiding and encapsulation: what if one module wants to hand out a (ref (tuple i32 i32)) to other modules but know that they can't observe the internal i32 i32 pair? This is definitely a valid use case, but I think the important thing to realize is that there is no reason we'd only want to do this for tuple types. Assuming we eventually get first-class ref types for functions, memories, tables, modules, instances, continuations, etc, we'd naturally want to do the same for them. Thus, while this is definitely a valid use case, it seems clear we shouldn't couple the solution to data hiding to tuples: it's simply an orthogonal use case which deserves an orthogonal feature addition that works for all these reference-able types.

Thus, I think if we were talking about adding any new acyclic type like tuple, there would be no question, we'd simply define it structurally like everything else, and then, separately, define a mechanism for data hiding that integrated with type imports+exports.

So returning to struct and array types, which are cyclic, I think it's pragmatic to say that if the only available approach was equi-recursion, then the implementation burden and performance cost is indeed high enough that it would be worth breaking the above reasoning and handling these types asymmetrically. But if the iso-recursive approach can indeed work and offer us the same implementation and complexity envelope as tuple, I don't see why we wouldn't just do that.

Thus, my vote would be against forking off a wholly new nominal investigation at this point in time, but mostly in the interest of conserving limited engineering resources (a point which @fgmccabe also made in the last meeting). Echoing what others said above, effectively this experimentation already happened (with particular kudos to @tlively for a full due diligence implementation of equi-recursion!). Moreover, echoing what @rossberg said at the end of his presentation, the resulting iso-recursive proposal is effectively already a compromise, adopting the relevant desirable properties of nominal typing, so I think we should view this revised iso-recursive proposal as a "joining" of the fork that takes into account a lot of hard work by a lot of folks.

(Lastly, just for completeness, I also think giving an ergonomic JS API to wasm GC objects should be a high priority, but I think the right solution there is fully in the JS API; in particular letting the JS API configure property names, property visibility, and prototypes via a JS API constructor for creating rtt values that can be passed into wasm and set as the "hidden class"/"shape" of wasm GC objects via struct.new_with_rtt. Thus, like data hiding, I think this feature is orthogonal to the present structural-vs-nominal discussion.)

[tlively]

Thanks for your thoughts, @lukewagner! I agree that structural typing would be the clear choice in the absence of cyclic types and that we shouldn't need to address type layout ecapsulation in the MVP. I also agree that the JS API should be a separate concern from the type system question, although we do have to settle the type system question first to know what the JS API will be working with on the Wasm side.

Thus, my vote would be against forking off a wholly new nominal investigation at this point in time, but mostly in the interest of conserving limited engineering resources...

I wouldn't view the nominal prototyping work as detracting from an investigation of the new isorecursive proposal. We've already done quite a bit of work on the Binaryen side to investigate a nominal system, so the engineering cost is already largely paid. In particular, @kripken has had great results from implementing devirtualization and other optimizations that benefit from the statically declared subtyping in our nominal prototype. The new isorecursive proposal also has statically declared subtyping, so all of those benefits we're realizing with the nominal prototype will transfer.

Another question we hope to answer experimentally with the nominal prototype is whether we can realize performance wins by removing first-class RTTs in the presence of statically declared subtyping. We haven't done this work yet, but again, the results should still transfer to any other system with statically declared subtyping, so this work will not be wasted.

Moreover, echoing what @rossberg said at the end of his presentation, the resulting iso-recursive proposal is effectively already a compromise, adopting the relevant desirable properties of nominal typing, so I think we should view this revised iso-recursive proposal as a "joining" of the fork that takes into account a lot of hard work by a lot of folks.

It would be nice to be able to ship one system that has the benefits of both structural and nominal typing, so I am excited about this development. The only thing holding us back from prototyping the new proposal is a lack of detailed understanding. After reading @rossberg's presentation and the meeting notes, I am not solid enough on the details to be able to implement the new system. It would be great if we could get a detailed write up of the proposed abstract syntax and typing rules so we could discuss the proposal further and put a prototype together.

[RossTate]

It's worth noting that the current MVP already plans to add nominal types before it adds structural types. The GC proposal depends on the type-imports proposal, and the "private" types in that proposal are fundamentally nominal types. Critical to them working is the fact that another module cannot simply get the same type by redeclaring the same definition. Of course, they are extremely weak, and as such seem unlikely to be able serve many use cases for privacy (especially if one cares about efficiency). To address such use cases, we could extend them with support for subtyping, extension, and partial encapsulation (i.e. some fields private and some fields public), at which point we have recreated the nominal types that we're suggesting exploring here.

So privacy/encapsulation is tangled with this issue.

It's also worth noting that @lukewagner and @tlively have made opposing suggestions. @lukewagner suggests constructing RTTs in the JS API in order to support JS interop, whereas @tlively is suggesting removing RTTs altogether. Furthermore, the MVP JS-API is unsound (from JS-typed-objects' perspective) specifically due to having to encode a nominal type system in a structural type system (it's easy to write a wasm program that puts a non-Point value in the Point field of a Rect).

There are various ways to address these problems, but regardless they show that JS interop is also tangled with this issue.

And yes, there are still substantial costs and potential issues to what @rossberg just presented (plus the need for it to be fleshed out). For example, it still requires engines to implement type canonicalization, something no engine has done yet. It also turns subtyping from constant time to super-linear time, the impact of which is hard to predict. And some of the open issues about the current MVP still apply to that design.

But rather than go into more depth, a meta-point of this issue was that we should make room for exploring so that we do not have to keep diving into such technical discussions. We know we need some form of nominal types (due to privacy, at the least), and we also know that—compared to structural types—its relatively easy to implement and prototype nominal types (based on the prototype generators and engines already developed). So let's make room to explore how nominal types can contribute to this project—how they might express privacy, interop, separate compilation, and even functional languages.

Making room does not mean eliminating other options. But it does help us get to a point where we can evaluate options more concretely, rather than always having to resort to hypothetical scenarios, which was another meta-point of this issue.

Of course, we should be mindful that exploration costs resources, and I would hope we would address that by the means most such decisions are made: developing a preliminary cost-benefit analysis and then discussing as a group whether the costs seem likely enough to by outweighed by the benefits to merit exploring (and then revisiting after collecting preliminary results). Arguably that's what Tuesday's poll is: do the costs of designing and implementing nominal types seem likely enough to be worth the benefits they might provide to merit officially exploring them (while not necessarily exploring only them)?

[tlively]

It's worth noting that the current MVP already plans to add nominal types before it adds structural types. The GC proposal depends on the type-imports proposal, and the "private" types in that proposal are fundamentally nominal types... So privacy/encapsulation is tangled with this issue.

That part of the proposal has not been discussed or investigated as much as the critical type system question. I would expect the final design of type imports and any final privacy/encapsulation designs to build on top of the final type system we decide on rather than factor into the decision of what type system to use. For the MVP, I would like to choose a type system solely based on performance, ease of production, and code size, i.e factors we can determine from prototypes.

It's also worth noting that @lukewagner and @tlively have made opposing suggestions. @lukewagner suggests constructing RTTs in the JS API in order to support JS interop, whereas @tlively is suggesting removing RTTs altogether... There are various ways to address these problems, but regardless they show that JS interop is also tangled with this issue.

My understanding of @lukewagner's broader point was that he similarly would like the design of the JS API to be built on top of whatever type system we end up with rather than factor into the decision of what type system to use. I agree with that.

[lukewagner]

@tlively Ah interesting; I hadn't seen the 'removing first-class RTTs in the presence of statically declared subtyping' idea yet and I'm definitely interested to hear more about that and later see the experimental results. So what you're saying makes sense to me given that it sounds like yall are actively interested in prototyping this facet of the design. My hope would be that, as with the last few rounds of design iteration, any observed fundamental performance differences could be incorporated by further "nominalizing" the iso-recursive approach, but of course we'll have to see.

[RossTate]

The optimization techniques @kripken is exploring rely on nominal types being able to pragmatically capture invariants beyond their structural description, such as guaranteeing that a certain field necessarily contains only a certain value. At present, this requires whole-program analysis, but directly integrating nominal types into the design would obviate that need. However, an iso-recursive approximation of nominal types would not be able to provide such guarantees (as another module could define the same type but with different values for the relevant fields). So if such optimization techniques are considered by the group to be a valid influencing factor on the design, then it seems likely we would need true nominal types—not just iso-recursive approximations—to accommodate those techniques.

[titzer]

I see the exploration of nominal types as a critical safeguard that we understand the tradeoffs properly. As in, making a good case for posterity that we understood what we were doing when we settled on the design we ship. It's work, but like @tlively says, I believe a lot of it is transferrable. Even though I find Luke's summary of the advantages of some form of structural types is pretty compelling, as it's pretty much what I've thought all the way along, I think @RossTate's meta point about having the proper official blessing to seriously explore the possibility is healthy for this subgroup's working relationships and discussion footing.

Other than the RTT question, I believe the delta between nominal types as being prototyped in Binaryen and @rossberg's new proposal isn't that big, so I feel comfortable that we can (temporarily) manage the union of these two things. I did implement the GC proposal in Wizard up to type canonicalization, and after I get back to catching up to the changes from ~year ago, I'd like to also prototype the nominal version. I don't see it being a big burden, TBH.

[jakobkummerow]

As promised, here is the updated prototype spec that we (=V8, Binaryen) have been working on, adding nominal types on top of what's already there: https://docs.google.com/document/d/1afthjsL_B9UaMqCA5ekgVmOm75BVFu6duHNsN9-gnXw/edit#

We consider this a near-final draft version. If you have comments, please comment on the doc. We'd like to give about a week of time for discussion before considering it "final" (until the next milestone, of course). Implementation is already ongoing.

The latest "iso-recursive with explicit supertypes" proposal will be the subject of a future prototype spec. If you are eager to see this, you can help by starting to write it! (Especially writing down the exact behavior with an implementation-ready level of detail.)