Variadic Generics

After some time, it seems to me that people (included myself) prefers Variadic Generics to be a "static" feature and not a "dynamic" one, and that variadic vales are not Collections but some other different type with some map / project / for ... in support...

With that in mind, please consider the following question:

// =============================================================================
// What should the type of the following statement be? And why should that be
// the case?
// =============================================================================

struct S<variadic Params1, variadic Params2> {
  let p1: Params1
  let p2: Params2
}

let s = S(p1: 1, "hello", p2: 42.42)

// Case 1: Flattened - no explicit binding
// s: S<Int, String, Float>
//
// Case 2: Flattened - explicit binding
// s: S<Params1: <Int, String>, Params2: <Float>>
//
// Case 3: Grouped - automatic transform(-ation?) into tuples
// s: S<(Int, String), (Float)>

It cannot be case one, because that would not distinguish between:

let s = S(p1: 1, "hello", p2: 42.42)

and

let s = S(p1: 1, p2: "hello" , 42.42)

but they must have different types. In fact, because variadics are greed, S<Int, String, Float> would have to bind all of the type parameters to Params1, leaving Params2 with no types.

It cannot be your third option because variadic value packs and tuples are not the same. The third option would be the case only if the type was unpacked as p1: (Params1...).

Adjacent variadics that have potentially overlapping bindings would require a label at least for the second parameter in order to associate the type arguments with the second type parameter.

4 Likes

That's exactly what I thought!

I have an update!

In this round I rollbacked the idea of VGs being solely dynamic and restored their static-ness, but I retained the Collection interface at the value level. Please note that the preamble of the document is not up-to-date, only the "Detailed Design" section is.

I tried to be more specific, without going too deep into it, about VG's representation in the compiler and in the type system.

I feel this time we have something more interesting to talk about!

#lovingswift :orange_heart:

12 Likes

Just gave the latest version of the document a read. Looks great! I love the idea of this being a STATIC feature. I hope we are all on the same page how this limits expressiveness. For instance, you can't express infinte lists like (0...). Also, one can't exchange the underyling type of an element of the list (with dynamic existential types, you could). But these are small prices to pay for the optimizations that the compiler can do if this is a static feature.

There's one thing I would like to add to the discussion. Suppose, you want to build (for whatever reason) a function composer with a similar syntax like the view builder. Function composition requires that the input of the next function in the list is equal to the output of the current function. So, in order to write code like

Chain {
f //(A) -> B
g //(B) -> C
h // (C) -> D
}

with arbitrarily many arguments, we would need some syntax to establish relations between successive elements in the variadic list.

If we had all that plus the ability to constrain associatedtypes of opaque return types, that could solve a looot of problems :smiley:

So... when will that come? :smiley:

5 Likes

Ok, I thought about my above example and now I think that it would actually be a bad idea - at least if you do it naively.

Writing some kind of chain would look something like this:

func chain<variadic T>(_ list: T...)
-> Function<T....First.Input,T....Last.Output> 
where T : Applicable, T.Sucessor.Input == T.Output

Applicable being a protocol implemented by Function.

We see here, that we need to refer to some First, Last and Successor types. These would inevitably be some meta-optional types, i.e. types that can be there or not (as opposed to values that can be there or not). Ok, that's not a big deal, we could find ways to handle that.

Now, Function<T....First.Input, T....Last.Output> requires that the last and the first type are actually there. Ok, still not a big deal: we could create some Nonempty protocol ensuring that those types are there and having our variadic type (not the individual types) conform to this protocol.

Here's the major problem: T.Successor would inevitably stay optional. That means that the last type equality constraint would compare T.Output to a nonexisting type. In order for the above code to compile, we would need an overload for == between types that evaluates to true if one of the types isn't there. This is exactly the opposite behaviour of the overload for T? where T is equatable. This may be unexpected. Hence, a less naive approach is needed if we want to make my example work.

Hi @Anachron, unfortunately I’ve not worked on this since my last post... A lot of things have changed in my life that absorbed me “full time”, so there are no updates on VGs.

I started to implement the basics of the feature but this was almost a year ago and so much has changed in Swift since then! The code is not up-to-date and I don’t think I have the ability today to start a new implementation, and this is really unfortunate because we need to try this feature in code and not only on paper to fully grasp what’s possible and how to shape this correctly :confused:

Oh NO! Really bad news...

It seems we can't get VG full implementation even Swift 7. :stuck_out_tongue_winking_eye:

Otherwise, if there're NO updates out of one year whether VG needs to be re-proposed and reviewed again?

I am surprised no Apple engineer from the SwiftUI team has taken up a proposal for variadic generics, since the framework limits you to 10 subviews due to this. It seems most proposals need an internal Apple use case to get them across the line.

2 Likes

In that case, how can I help? I have absolutely no experience working on the compiler, but I'm an ok programmer and I'd love to learn this and this particular feature is interesting to me.

Well chains could be handled by some kind of Previous and Next keyword that could only be used in a where clause but would have to apply to all successive pairs of types, plus the possibility to require T to be a nonempty list. Perhaps the pairwise requirement seems very niche, but I'm not so sure. In a variadic list comparing successive elements is pretty much the only thing you could do.

func chain<variadic non-empty T>(_ list: T...) -> Function<T.First.Input, T.Last.Output> where T: Applicable, Next.Input == Previous.Output

Yes, this is more or less what I wrote. The Next.Input == Previous.Output however is problematic, because even in a nonempt list, Next will not exist for the last element of the type list. In that case, we obviously want the NonExistant.Input == Previous.Output to evaluate to true, but that would be the opposite bahaviour as in nil == equatable. That's the objection I have to this.

One could implement another operator though: ?=. That could have the described semantics.

Ah, but my idea is not that they are properties of T, as in "the one after T". They would be global to the whole variadic list and evaluated pairwise, not "for each T". I should have named them LHS and RHS or something like that. I guess it would be a bit unusual.

Or just T.Successor?.Input ?= T.Output as you suggest. "equal if present".

But if it makes sense to define a First and Last on the chain, I guess it's not so far fetched to also have a kind of Zip-comparison. What else could you really compare other than all T, and neighbouring Ts?

Making Previous and Next global would mean that you can't distinguish if a function or type has more than one variadic argument ;)

Uhm, one can imagine other comparisons, but I think the comparison of successive arguments is probably the most useful.

1 Like

Here there are some informations about what can / should be done to implement this, but I don’t know if the information is stale as of today.

The key is to proceed step by step, implementing one piece after the other and only after some infrastructure is set up. For a feature this big a single giant PR with everything inside is not worth it. Pieces of the infrastructure could even be merged to main before the feature lands if that helps the compiler to be more organized / flexible / simple / structured!

1 Like

@technicated the proposal is great!
The cool thing about variadic generics is building recursive types and data structures, something like

struct Recursive<Head, variadic Tail> {
  var head: Head
  var tail: Recursive<Tail...>
}

The problem is, there should exist a terminal type defined or some kind of condition ti stop the recursion. How would you suggest to handle this?

1 Like

If you cannot initialize a value of type Recursive<...> with an infinite number of generic parameters, then there should be no problems, right? The recursion ends when the finite amount of generic parameters ends.

I've just thrown out an idea in the thread mentioned by @technicated . A basic idea could be that variadic types are always declared in terms of at least two types, like this:

@variadic(S,T)
func foo<S,T>(arg: (S,T)) {...}

It is already possible to call foo in today's Swift like this:

foo(arg: (("bla", 42), "1337"))

So this could serve both as the base case for recursion and the recursion itself. We only need a variadic annotation to create some syntactic sugar for us. If you want allow for single types or an empty list of types, you would have to handle this independently. You may also want to review the other problems I mentioned in the other thread. But it's just how I would approach this, it diverges very much from the design so far.

There is always a finite number of generic parameters, isn't it? Yet recursion always needs a terminal condition. The value of variadic generics is doubtful if there is no support for recursion.

2 Likes

This is something I thought about and could not find a solution i.e. what happens when Tail is emptied going down into the recursion? What is Head going to be? This kind of code should be a compile error? Should we introduce a keyword / magic syntax to handle this scenario (=> increased complexity)?
Aside of all this, what is a programmer expecting when writing this (potentially invalid) code? What was his / her expectation? Maybe understanding this we can come closer to a solution!

1 Like