Pitch: Variadic generic types abstracting over packs

Evolution Pitches
21

Just as you can write:

struct ThreeSequences<Element, T: Sequence, U: Sequence, V: Sequence>
  where T.Element == Element,
            U.Element == Element,
            V.Element == Element {}

ThreeSequences<Int, Array, Set, ArraySlice>()

this would be

ChainSequences<[_], Set, ArraySlice, Int>

And to @xwu's point, if you must support the empty sequence then you'll have to parameterize on the element type, otherwise you couldn't give a coherent conformance of ChainSequence to Sequence itself (what is the (fixed) Sequence.Element type of ChainSequence<>?)

ETA:

Perhaps someday we could allow default generic parameters so that: ChainSequence<Int> would be the empty-chain ChainSequence with element type Int (since Int doesn't conform to sequence) and ChainSequence<[Int]> would be the ChainSequence consisting of just an Int array. Though without the ability to label generic arguments the latter might have to be ambiguous. :confused:

2 Likes
22

So despite what SE-0393 says, same-element requirements are not yet designed or implemented. There are a number of interesting open questions. For example, consider a pair of same-type requirements T == U, U == V in a generic signature. Together these two requirements imply the “derived requirement” T == V, which is “true” despite not being written down explicitly.

Now consider a pair of requirements (each T).Element == E and E == (each S).Element should imply a third requirement of some kind, but it’s not (each T).Element == (each S).Element! In fact, that would be wrong in two ways. It would imply that T and S have the same length. However, the first two requirements do not restrict the length of T and S at all; they merely say that all Element types are the same.

So a same-element requirement between a pack and non-pack, as defined in SE-0393, does two things: it makes all types in the pack identically equal to each other, and then it makes then equal the right hand side. It seems that at least in the implementation, we want to consider these as separate independent concepts, so that a same-element requirement really breaks down into two simpler pieces.

In your case, you want to apply the unary same-element “half-requirement” to (each S).Element without equating it to anything else. I can’t suggest any kind of intuitive spelling for this feature though, if we were to surface it in the language, but it certainly makes sense.

2 Likes
23

We already have, for SIMD types, the "point-wise" operator .== where the analogous "derived" equivalence doesn't hold.

That is to say, given a value x = SIMD3<Int>(42, 42, 42) and a value y = SIMD4<Int>(42, 42, 42, 42), even as all(x .== 42) and all(y .== 42), one can't evaluate x .== y.

24

Ok I understand now, thanks for the patient explanations. I still think that would have been a very good tradeoff - I mean we could still use the same syntax for all these things, without them being the same thing.

Also so far, I can't see the usefulness of the ability for packs to expand in the context of a list. I mean, the idea that (Int, each T) could mean (Int, String, Bool) instead of (Int, (String, Bool)) is cool, but I haven't been able to imagine a scenario where it's all that useful.

As it is, I found the variadic generics feature extremely hard to understand, even though I'm very comfortable with generics, vector math etc, because packs are so abstractly defined.

Hopefully there is a way to introduce this to users that is more concrete.

1 Like
25

Hold on, you mentioned that this is forbidden because there is way to write a concrete version of this, but in the original proposal we have this:

func variadic<each T, each U>() {}

Wouldn't that suffer from the same problem?

1 Like
26

In the fullness of time, it should hopefully be possible to redefine tuples as a generic type constructed from a pack that happens to have a special literal syntax like Array and Dictionary do.

struct Builtin.Tuple<each T> {
  // Like Builtin.Int and other primitive types,
  // you probably can’t _implement_ Tuple in Swift,
  // but at least you can now _name_ it.
}

At that point, packs become the more primitive concept, and tuples are a higher level thing built atop them. It would be counterproductive to “share” a syntax.

27

Tuples still have the magic (and IMO desirable) property that the single element case (T) canonicalizes to the same type as the one element T, so they can't be completely replaced by an off-the-shelf type definition. Or if they could, it would have to be something like a concrete Void type for the zero-element case, and Tuple<A, B, each Rest...> for the two-or-more case.

2 Likes
28

No, because type arguments to functions cannot be specified in angle-brackets; they are always inferred. There are other restrictions on functions to prevent similar problems, e.g. this is banned:

error: a parameter following a parameter pack requires a label
func variadic<each T, each U>(_ t: repeat each T, _ u: repeat each U) {}
                                                    ^

The restrictions on types with parameter packs can always be lifted later, e.g. if we add pack literals or if we enable labeling type arguments in angle-brackets.

1 Like
29

I think this is a great approach because it solves a real problem (making tuples a nominal, extensible type) by composing existing language concepts in a straightforward fashion while sacrificing nothing about the existing semantics. The only downside is that in addition to the concrete Void type, there would probably need to be new language semantics about Void conversion.

30

Sure, it can't be specified explicitly, but when the compiler infers it and you option click it, the popup will have to say something. But then I suppose the issue is just that you want to be able to specify the generic type unambiguously, not necessarily display it.

Also, it is sort of possible to specialise it explicitly:

func generic<T>(value: T) { }

func specialise() {
    let concrete: (Int) -> Void = generic
}

So that case wouldn't work for doubly variadic functions I guess.

1 Like
31

We should be able to make tuples (and our other non-nominal types) extensible regardless of their being nominal. With variadic type parameters, and generic extensions, you should ultimately be able to write extension <each T: P> (repeat each T): P { ... }, for instance.

5 Likes
32

In addition to the one-element edge case Joe already mentioned, tuples can also have labels. While we could go on and introduce "label packs" or something, such a feature probably does not carry its weight if the only purpose is to allow us to pretend that tuples are just magic syntax sugar for a nominal variadic type.

3 Likes
33

And, though I know there are many detractors, tuples can still do the tuple shuffle :man_dancing: :dancer: and that is most delightful to me:

let x: (foo: Int, bar: Int) = (42, 21)
var y: (bar: Int, foo: Int)
y = x
print(y) // (bar: 21, foo: 42)
2 Likes
34

Thanks for explaining the difficulty here, that makes sense. But just so I'm clear about what you're saying, does this imply that the following snippet from SE-0393 is flat out incorrect, in terms of what the implementation actually allows?

func variadic<each S: Sequence, T>(_: repeat each S) where repeat (each S).Element == T {}

This is called a same-element requirement.

A valid substitution for the above might replace S with {Array<Int>, Set<Int>}, and T with Int.

This seems pretty unequivocal to me that variadic([1, 2, 3], [4, 5, 6] as Set) should be allowed, but based on what you're saying this is wrong because the types in the pack S are not all "identically equal to each other." Am I understanding correctly?

1 Like
35

The current SE-0393 implementation does not allow same-element requirements only because they're not implemented yet. The text is correct. Same-element requirements are "not designed" in terms of the implementation approach for requirement minimization, not in terms of the surface language semantics.

EDIT: I should probably answer the whole question :slightly_smiling_face:

In this case, the pack where all elements are the same is the dependent pack (each S).Element. It's perfectly fine that the base pack elements are different.

2 Likes
36

Thank you for elaborating! I think I am still missing something though. I took Slava's post:

to be implying that the desired ChainSequence signature that supports each pack member having (potentially) different concrete types agreeing only in their respective Element types has no spelling, i.e., that this definition:

would not support ChainSequence<[Int], Set, _> as I wrote above. I read the SE-0393 language about same-element requirements to be precisely the sort of "half-requirement" that Slava says there is no designed spelling for, but that you're saying is simply a present implementation limitation. What am I not getting?

1 Like
37

I interpreted Slava's comment as only meaning there's no way to spell the desired (each S).Element requirements on ChainCollection without an intermediate scalar type parameter, i.e. the Element type parameter in <each S: Sequence, Element>. It would be nice if that weren't necessary, e.g. if you could write a "unary same-element 'half-requirement'" that involves only (each S).Element. Strawman: <each S: Sequence> where unify (each S).Element. The unary requirement here is unify and the subject is (each S).Element; no need for a separate Element type parameter on ChainCollection.

EDIT: Further, the full same-element requirement repeat (each S).Element == Element already implies the unary requirement on (each S).Element. I believe Slava is suggesting we might already need this concept in the requirement machine implementation, there's just no way to spell it explicitly without equating the pack to an intermediate type parameter.

2 Likes
38

Ahhh got it, rereading with that in mind helps things click. I'm still having a bit of trouble picturing how such a constraint would actually be useful in practice—as mentioned above it seems like such a setup for ChainSequence would be overly restrictive since it would either disallow the empty chain ChainSequence<> or force ChainSequence to admit a Sequence conformance which is not parameterized on the element types of the chained sequences—but I see the distinction you're getting at.

ETA:

I guess one such use would be a function/type which operates internally on chained elements without necessarily exposing the element itself, so you could have, like,

func shiftBoundariesRight<each C: RangeReplaceableCollection>(_: repeat each C) -> (repeat each C) where unify (each C).Element {}

which would transform [1, 2], [3], [], [4, 5] into [1, 2, 3], [], [4], [5]—the 'empty' implementation is trivial and agnostic to the Element type, but it's potentially still useful to implement the totally generic rather than the version that requires a firstCollection argument so that clients can use it generically without themselves restructuring their own generic parameters.

1 Like
39

Yeah. I apologize for the confusion. I think intuitively we all understand the expected behavior of same-element requirements as specified in SE-0393. This will give us the ability to unify the elements, as you're calling it, with the help of an intermediate non-pack type parameter. I think for the user-visible part, this suffices. To realize this, there are three primary missing pieces:

  • we need to define the rewrite rule for a same-element requirement which gives us the expected behavior with derived requirements/minimization.
  • we need a generic signature query which given a generic signature and type parameter pack, returns the pack's "unified" element type, if there is one.
  • when building the element environment for a pack expansion, if some type parameter pack has an element type, instead of instantiating the element archetype we map its element type into context.

I would say the first one is a "design" question, even though it's not user-visible. The second two are straightforward (I hope) matter of "implementation" ;-)

What I was getting at with the discussion of derived requirements was that internally we might need to model the "weird" kinds of same-element requirements and this might inform the rewrite system changes, but I'm not sure yet. It would be certainly nice if we could avoid it, just from a simplicity standpoint.

EDIT: if there was some way to write the moral equivalent of (each S).Element .== (each T).Element (collapsing the element types of two packs into a single scalar, without an intermediate parameter), then what is the element type of (each S).Element (or (each T).Element)?

Can we avoid this entirely? With requirement inference, you can do some odd things:

typealias G<each T: Sequence, E: Sequence> = E
    where (each T).Element == E.Element

func foo<each U, each V>(_: each U,
                         _: repeat G<repeat each U, each V>)

Note that the second parameter's type desugars to repeat each V because the type alias is trivial, but it introduces an inferred requirement! Requirement inference is defined by applying a substitution map to the requirements of G. The substitution map replaces the non-pack type E with the pack reference each V because G appears inside of another pack expansion. It's not even completely clear to me what this means in the general case.

It seems the generic signature of foo would have this weird requirement:

<each U, each V where each U: Sequence, each V: Sequence, (each U).Element .== (each V).Element>

But we could also just ban this. This interaction between requirement inference and nested pack expansions seems very magical, and difficult to "prove" correctness of.

2 Likes
40

(Taking our offline discussion here, partially so that it's written down and I won't forget the details next week :slightly_smiling_face:)

The problem here seems to be that, without additional restrictions, requirement inference can introduce nested requirement expansions where packs appearing in the subject types are captured by requirement expansions at different depths. Given the example that you wrote (syntax updated for the SE-0393 revision):

typealias G<each T: Sequence, E: Sequence> = E
    where repeat (each T).Element == E.Element

func foo<each U, each V>(_: each U,
                         _: repeat G<repeat each U, each V>)

T is bound to repeat each U and E is bound to each V. Because the requirement expansion repeat (each T).Element == E.Element is inferred inside of a pack expansion, you end up with nested requirement expansions. This is how I visualize the inferred requirement using made-up syntax/notation:

// Substituting `repeat (each T).Element == E.Element` with `each T := repeat each U, E := each V`
repeat <V' = each V> (repeat <U' = each U> (U').Element == (V').Element)

In the above notation, repeat is explicitly parameterized over the packs it captures with a named binding. So, V' is the outer pack iteration over each V while U' is the inner pack iteration over each U. The shapes of V' and U' are not equivalent, but their element types are. I think, in the short term, we should ban requirement expansion inference inside of pack expansions because that's what gets us into this nested requirement expansion situation.

In any case, we should totally document requirement expansion inference behavior in the proposal text!

1 Like