Lift recursion groups to function-references proposal?

[titzer]

I noticed in the current MVP text it says that deftypes that are not within a recursion group are interpreted as being in a recursion group only containing themselves. As the GC proposal is based on function-references, but function-references does not contain the recursion group concept, that would imply a breaking change to how recursive functions work in that proposal.

In general, the function-references proposal needs to be updated in light of the landing of iso-recursive types in this proposal.

[titzer]

Also, if we lift recursion groups to function-references, then we might as well eliminate the concept and just allow repeating the type section, treating each as a recursion group. A justification for them given in #243 was the possibility of retroactively reinterpreting previous definitions as part of a large recursion group. But we had no possibly recursive definitions before function-references, and if we have to push up the concept we might as well do it a simpler way.

I find it significantly more elegant to just allow repeating the type section, only allowing types can to be recursive within their own declared section. (That was the cleanest thing I could think of when I implemented relaxed sections in Wizard to support Jawa and Pywa.)

[tlively]

In general, the function-references proposal needs to be updated in light of the landing of iso-recursive types in this proposal.

Another option is to prevent recursion in that proposal entirely: WebAssembly/function-references#41 (comment). Whichever one is simpler is fine with me since the end result will be the same. (And I remain amenable to merging the proposals if that ever seems like simplest path forward.)

Also, if we lift recursion groups to function-references, then we might as well eliminate the concept and just allow repeating the type section, treating each as a recursion group.

When it previously came up, another reason not to have one rec group per repeated type section was that it would make the section boundaries semantically meaningful, while some folks had assumed that all repeated sections would be semantically equivalent to their concatenation (henceforth "the concatenation property). Of course we don't have repeating sections yet, so this is more or less a stylistic argument either way.

But since we need to bikeshed and resolve this at some point anyway:

Personally, my feeling is that maintaining that concatenation property is cleaner because it has more separation of concerns; the encoding of the type section(s) remains independent of their semantics.

@titzer, could you say a little bit about why you find reusing section boundaries as rec group boundaries cleaner than maintaining the concatenation property?

(Also happy to take this bikeshed to a different issue if you'd rather keep the discussions separate)

[titzer]

Upon further reflection, I think we do need recursion groups because I forgot that we have a structural equivalence check already built-in to call_indirect. It would be weird to have two functions be considered interchangeable for call_indirect but not for first-class function references. So I'll withdraw my second comment.

(Personally I found it more elegant because it didn't introduce any new concepts. I didn't consider the concatenation property, which I suppose is useful for toolchains. As I implemented repeated sections in Wizard, my implementation just keeps track of the maximum legal forward index when parsing deftypes, and as the beginning of a type section has a count, it was easy to check legal/illegal forward references. A pass at the end of parsing a type section eliminated forward references. I'll adapt it to recursion groups.)

I don't think we should disallow recursion in the function-references proposal (by way of leaving out the concept of recursion groups). If we consider each deftype its own recursion group, it'd still be possible to write self-recursive functions (there is exactly 1 possibly recursive index in the group), but not more complex ones. We'd have to explicitly ban self-recursive types.

[rossberg]

@tlively, I think simply not allowing recursive types in the funcref proposal, as per my comment you already referenced, is forward-compatible and the simplest solution. But thanks for reminding me that I still need to implement that change. :)

@titzer, self-recursive function types are of very limited utility on their own, as far as I can see, unless you are desperate to encode the untyped lambda calculus in Wasm. But then you'd need closures, too. :) Technically, there is no need for extra rules to prevent them – whether validation allows the recursion or not comes down to when the environment (or index counter) is updated, before or after checking the r.h.s. (though the meta-theory definitely is simpler without recursion).

@titzer, in case you missed my earlier reply, I described why using type sections as recursion groups turns out not to be a simplification here. In particular, as you also discovered, it has adverse effects on call_indirect, unless we e.g. introduce a new kind of type section.

[rossberg]

thanks for reminding me that I still need to implement that change. :)

Please see WebAssembly/function-references#56.

[titzer]

Closing this, since we're just disallowing recursion in function-references.