Variadic Generics

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

Head is always safe as it isn't splatted.

Unfortunately, yes.
As in the last call of Recursive no arguments are provided but at least one argument is required.
At the last call, Tail is an array of types with length zero: Array<Type,0>. Splatting such an array into comma separated string sequence of type names results into an empty string.

Solutions would be:

  1. Type errors can be reinterpretet. So treating the error as an end marker would be natural but not very idiomatic.
    I think most users will overlook this fact and don't think about it except those who think too much in general.
  2. Specialization:
struct Recursive<Head, variadic Tail> {
  var head: Head
  var tail: Recursive<Tail...>
}

struct Recursive<Head> {
  var head: Head
}
  1. Conditional compilation
struct Recursive<Head, variadic Tail> {
  var head: Head
  var tail: Recursive<Tail...> includeIf Tail.nonEmpty() //includeIf == ifdef in c
}

From the linked paper, at section 3 you can see how it is handled for recursive type definitions:

In Swift it could be something on those lines, with type overloadings based on the number of generic parameters.

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

struct Recursive<Head> {
    var head: Head
}

Alternatively, to avoid redeclarations of types, you may introduce a condition to check if the variadic generic type is empty and use it in a where clause:

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

extension Recursive where nonempty Tail {  // Tail != () maybe?
    var tail: Recursive<Tail...>
}
1 Like

But today Swift does not allow for this: two types with the same name and different generic parameters cause an error: invalid redeclaration of ‘Recursive’, so this would need to be special-cased :pensive:

Edit: the extension idea can be an interesting starting point to explore!

I thought about yet another problem. In the current git repo for the proposal, it is mentioned that the variadic type should conform to Collection. But what the hell would MyVariadicType.Element be? This describes a single type, what we want are different types.

My approach here would be to just give variadic types an interface that looks very similar to Collection but acts in a unique way. Swift already has a some keyword to describe opaque types and there's a discussion on an any keyword for existentials. Why not have yet another one to denote the individual types in the variadic "collection"? For instance, we could use each. Any method accessing the elements of a static collecion would then provide each MyConstraintOnVarArgs.

That means that if we want to have a map or even a reduce method, the closures that we provide have to accept each Something as parameters. The only thinkable semantics really is that the closures are "somewhat" generic so they can be specialized ahead of time. I say "somewhat" generic, because functions consuming each Element don't actually need to be able to deal with, e.g., all CustomStringConvertible types, even if we say our generic types should be CustomStringConvertible.

Regarding the variadic type variables themselves: maybe a less invasive and/or ambigous solution than any of the so far discussed ones would be to constrain variadic types to a special Variadic protocol. Conforming to this protocol would be a syntax error, only certain builtin literals can conform to Variadic. The return type of Variadic.map (which may make sense if, e.g., you want to map to some associatedtype that in turn has been constrained to yet another protocol) would again conform to variadic.

The desired variadic code could then maybe look something like this:

struct Foo<V : Variadic> where each V.Element : MyProtocol {...}

func foo<V : Variadic>(list: V) -> String where each V.Element : CustomStringConvertible {
   //V.Element is a type constraint in this scope that can only be satisfied
   //by each V.Element
   list.reduce(into: ""){(str: inout String, next: each V.Element) in
      //in this scope, V.Element has been specialized to a statically knowable
      //list of concrete types
      str += next.description
   }
}

No, I often use Collection as a constraint but only in the #head, #tail, #length, #reduce, #ifempty section I suggest to explore (not super convinced) what can happen, what we gain and what can go wrong if a variadic generic conformed to Collection.

It's a super essential feature. If no one can take it over we need help from the core team, don't we? Can we help with prioritization or something? We're about to have Swift 6 and so sad to see than modern programming language is lack of common features

It seems @xAlien95 has proposed to do it over extensions so overloading with the same name isn't necessary, I think?

If Swift is going to evolve this way, something similar to SFINAE has to be introduced, and it would increase the complexity significantly.

I spent some time playing with different applications of the variadic usage, and I think there should exist some set of operations defined on the variadic type. For example, it is essential to compare the size of packed types, something like:

struct Variadics<variadic T, variadic U> where T.count == U.count { }

Moreover, there should be possible to operate on the variadic type like it is a collection of types:

struct Variadic<variadic T> where T.count > 0 {
  var value: T[0]
  var tail: T[1..<T.count]
}

The main question I am not able to solve, what is an empty variadic? @technicated, in your proposal you declare an empty variadic syntax - "<>" and show it is possible to define a variable

let vg6: SimpleVariadic<>

But in the example, the struct SimpleVariadic contains no properties, which is not really close to real example. How is it supposed to look like if there is at least a single property? What is the value of this property if variadic list is empty? I reckon, if we get to the idea on how to operate with empty variadic, we might end up with the conclusion on what the variadic type is. What do you think?

1 Like

I think the opposite it's truth, if we automatically convert errors to properly working code we end up with a lot of ambiguous meanings over time.

Okay I understand a bit what you mean but SFINAE means you can leave out some additional constraints if they are implicitly inferrable.

For instance T[0] is wrong when an empty variadic is given, SFINAE would transform that to where ... && T.nonEmpty()

You may be right that we might need to be forced to specify this explicitly, but this can bloat up where constraints a bit.

Empty variadics is an empty tuple/empty array of types, you can't index such a thing as every index is invalid. An instance of such a type is impossible as it is the empty set, I think we can say that a zero sized tuple/array of types is equal to Bottom.

Edit:
We may need to differentiate between * and + variadics with index intervals of [0,\infty) and [1,\infty), respectively.

These two different kinds of Variadics exist in Ceylon

1 Like

Shouldn‘t this be

enum Variadic<variadic T> {
  case nil
  case cons(value: T[0], tail: T[1...]
}

to be able to model both cases?

Let's look at the Variadic Generics at the value level section. Here I say that values of variadic type are called Variadic Values and have their unique set of API, extending that of Collection; more specifically, a Variadic Value is a RandomActionCollection.

So a value of type is akin to an empty collection.

I don't know if it has already been told, but in the Variadic Values subsection it is stated:

A variadic value can never leave a generic context ⏤ it must always be transformed in something else to do so.

In the provided example, however, you define properties having as type a variadic type:

extension SimpleVariadic {
  var someTs: T { /* ... */ }

  func testCollection() -> (T...) {
    // All your `map`, `filter`, etc are here!
    let arr1: [String] = someTs.map { "\($0)" }
    let arr2: [P1] = someTs.filter { $0 is Int }
    let first: P1? = someTs.first
    
    return (someTs...)
  }
}

let v: SimpleVariadic<Int, String> = /* ... */

// `v.som` shows `Collection | someTs`
v.som

for elem in v.someTs {
  print(type(of: elem))
}

Wouldn't .someTs be unaccessible due to being a variadic value? (T...) tuple type would be usable, but T variadic type would not, am I correct? If so, and if .someTs effectively is a tuple, we would need .map, .filter, .reduce, .allSatisfy, .first, etc. to be available on tuples themselves.

I'm re-evaluating @Joe_Groff's suggestion to keep tuples as structural types and as building blocks for generic variadics:

On the other hand, we have @Chris_Lattner3 goal of explicitly addressing non-nominal types conformances:

Did you introduce structural variadic types <A, B, ...> in order to let tuples become nominal types?
If so, a variadic generic primitive interface may not be enough: tuples do require parameter type labels and unfortunately not in the way addressed in this pitch.
You suggest explicit parameter type labels as described in the Generics Manifesto: Named generic parameters subsection, but tuple type labels are different in that regard:

// different type labels lead to different types
(a: Int, b: Double).self != (Int, Double).self
Tuple<a: Int, b: Double>.self != Tuple<Int, Double>.self

// with your syntax
struct Tuple<A, B> { ... }
Tuple<A: Int, B: Double>.self == Tuple<Int, Double>.self

// with explicit parameter type labels (strawman syntax ahead)
struct Tuple<a A, b B> { ... }
Tuple<a: A = Int, b: B = Double>.self == (a: Int, b: Double).self
struct Tuple<_ A, _ B> { ... }  // equivalent to struct Tuple<A, B>
Tuple<_: A = Int, _: B = Double>.self == (Int, Double).self

Tuple<a: A = Int, b: B = Double>.self != Tuple<A = Int, B = Double>.self

// note: "A = Int" and "B = Double" are there just for clarity
// you would use the type as Tuple<a: Int, b: Double> directly
// mirroring how functions work (almost)

// note: redeclaration of Tuple is there just for clarity

This is a minor and trivial problem to solve. The real problem surfaces when you want to actually declare a Tuple structure in the standard library. Tuples not only require an indefinite amount of types, but also variable type parameter labels. In the past has been suggested something like the following (sorry, I failed to find the actual post... searching in these forums is quite hard):

struct Tuple<...labels: T...> { ... }

For each label and type you would need to create an index property (i.e. .0, .1, .2, etc. up to the number of types involved in the tuple, which are not valid identifier names for struct properties) and a property named as the label, all statically available.

These suggest that:

  • your variadic generic structural interface type would need to handle/store optional labels, just like tuples already do;
  • tuples would still need some hardcoded properties (.0, .1, .2, etc.) not declarable in a standard library struct.

So, if tuples are special, why not use them as the de-facto interface for variadic generics?

1 Like

I now understand where some misconceptions and incomprehensions come from, and it’s all my fault!

I have two documents for Variadic Generics, one labeled XXXX and the other YYYY. For reasons that I don’t remember now I used to work on both documents in parallel. When a “stable” version of one document was ready, I posted a direct link to the commit in this thread, be it the XXXX or the YYYY.

That said, the latest valid version that I wrote and updated is the YYYY one and can be found here on GitHub (link to the original post in this thread). I hope that this post shines some light on the topic! Sorry for the confusion :pensive:

1 Like

What is the status of variadic generics?

Is anyone in the Swift Core Team working on it?

Is it on any roadmap? Expected to be released 2022? 2023? :)

5 Likes

I really like this idea. How can we do something like this:

func foo<T..., U...>(keypaths: KeyPath<T_n, U_n>...)

...?

An updated pitch is over here: Variadic Generics

2 Likes