Three steps to Variadic Generics

Variadic generics was referred to in "On the road to Swift 6". I think it may be a good idea to break down it into the following three steps compared to tackle variadic generics directly.

  1. Operations for tuples
  2. Variadic tuples
  3. Variadic generics

1. Operations for tuples

The following examples show two kinds of operations for tuples: map-like operations and reduce-like operations.

// map-like: (T) -> T
func squares<T1: Numeric, T2: Numeric>(of values: (T1, T2)) -> (T1, T2) {
    values.map { $0 * $0 } // the type of `$0` differs for each element
}

squares(of: (3, 5.0)) // (9, 25.0)
// map-like: (T) -> T.AssocType
func firsts<C1: Collection, C2: Collection>(of collections: (C1, C2)) -> (C1.Element?, C2.Element?) {
    collections.map { $0.first }
}

firsts(of: ([2, 3, 5], "XYZ")) // (.some(2), .some("X"))
// map-like: (T) -> U
func descriptions<T1: CustomStringConvertible, T2: CustomStringConvertible>(of values: (T1, T2)) -> (String, String) {
    values.map { $0.description }
}

descriptions(of: (42, true)) // ("42", "true")
// reduce-like
func sum<T1: IntConvertible, T2: IntConvertible>(of values: (T1, T2)) -> Int {
    values.reduce(0) { $0 + $1.asInt() }
}

sum(of: (3, 5.0)) // 8

Those operations can be statically unrolled. For example, the squares function above can be converted as follows:

func squares<T1: Numeric, T2: Numeric>(of values: (T1, T2)) -> (T1, T2) {
    ({ $0 * $0 }(values.0), { $0 * $0 }(values.1))
}

Although map and reduce above are written using method-like syntax, it doesn't necessarily have to employ such syntax. What I want to discuss is semantics rather than syntax. Adding new syntax like below for the purpose is semantically identical.

func squares<T1: Numeric, T2: Numeric>(of values: (T1, T2)) -> (T1, T2) {
    #map element in values { element * element }
}

Also operations as control flow is possible.

func sum<T1: IntConvertible, T2: IntConvertible>(of values: (T1, T2)) -> Int {
    var sum: Int = 0
    for value in values { // the type of `value` differs in each loop
        sum += value.asInt()
    }
    return sum
}

It can be interpreted as follows:

func sum<T1: IntConvertible, T2: IntConvertible>(of values: (T1, T2)) -> Int {
    var sum: Int = 0
    do {
        let value = values.0
        sum += value.asInt()
    }
    do {
        let value = values.1
        sum += value.asInt()
    }
    return sum
}

Useful operations are not limited to map and reduce. For example, count should be useful in some cases.

In those operations, e.g. in closures for map and reduce above, the type of the elements are constrained by the common constraints of all elements. So $0 * $0 is valid in the trailing closure of the map in the square function because $0 is constrained by Numeric.

2. Variadic tuples

We can think about variadic tuples independently from variadic generics. In the following code, (Foo...) works as a placeholder of tuples with any numbers of elements whose types are Foo: (), (Foo), (Foo, Foo), (Foo, Foo, Foo) and so on. While operations for tuples are just shorthand for normal tuples, those operations are necessary to operate on variadic tuples.

// map-like: (T) -> T
func squares(of values: (Int...)) -> (Int...) {
    values.map { $0 * $0 }
}

squares(of: (3, 5))    // (9, 25)
squares(of: (3, 5, 7)) // (9, 25, 49)
// map-like: (T) -> T.AssocType
func firsts<T>(of arrays: ([T]...)) -> (T?...) {
    arrays.map { $0.first }
}

firsts(of: ([2, 3], [5, 7])           // (.some(2), .some(5))
firsts(of: ([2, 3], [5, 7], [11, 13]) // (.some(2), .some(5), .some(11))
// map-like: (T) -> U
func descriptions(of values: (Int...)) -> (String...) {
    values.map { $0.description }
}

descriptions(of: (2, 3))    // ("2", "3")
descriptions(of: (2, 3, 5)) // ("2", "3", "5")
// reduce-like
func sum(of values: (Int...)) -> Int {
    values.reduce(0) { $0 + $1.asInt() }
}

sum(of: (3, 5))    // 8
sum(of: (3, 5, 7)) // 15

The syntax above have some problems in detail. For example, a way to specify relations between tuples is lacked. (Int...) and (String...) in the descriptions function above must be a counterpart. But I do not go into detail of syntax here.

Because we gave up the arguments-are-a-single-tuple model, we need a way to flatten variadic tuples as arguments. Although it is desirable that variadic tuples and variadic arguments are united, I think it is hard without large-scale source-breaking changes.

// Ideal but collides with variadic arguments

func squares(of values: Int...) -> (Int...) { // Not `(Int...)` but `Int...`
    // the type of `values` is `(Int...)`
    values.map { $0 * $0 } // Not `Array.map` but a map-like operation for tuples
}

func sum(of values: Int...) -> Int {
    // If the type of `values` is `(Int...)`, it is faster than `[Int]`
    values.reduce(0) { $0 + $1.asInt() }
}

// When we want to handle variadic arguments as arrays
func foo(_ xs: Int...) {
    // the type of `xs` is `(Int...)`
    let ys: [Int] = [Int](xs)
    ...
}

Spreading tuple elements into a tuple can be also useful.

func tupleFrom<T>(head: T, tail: (T...)) -> (T, T...) {
    (head, tail...)
}

let a: Int = 2
let b: (Int, Int) = (3, 5)
let c: (Int, Int, Int) = tupleFrom(head: a, tail: b) // (2, 3, 5)

3. Variadic generics

variadic generics can be realized by the combination of "1. Operations for tuples" and "2. Variadic tuples". The former realizes operations for elements with different types. The latter realizes handling tuples with the unfixed number of elements. Variadic generics has both characteristics.

Examples are here.

// map-like: (T) -> T
func squares<(T: Numeric)...>(of values: (T...)) -> (T...) {
    values.map { $0 * $0 }
}

squares(of: (3, 5.0))    // (9, 25.0)
squares(of: (3, 5.0, i)) // (9, 25.0, -1.0)
// map-like: (T) -> T.AssocType
func firsts<(C: Collection)...>(of collections: (C...)) -> ((C.Element?)...) {
    collections.map { $0.first }
}

firsts(of: ([2, 3, 5], "XYZ"))         // (.some(2), .some("X"))
firsts(of: ([2, 3, 5], "XYZ", 0...42)) // (.some(2), .some("X"), .some(0))
// map-like: (T) -> U
func descriptions<(T: CustomStringConvertible)...>(of values: (T...)) -> (String...) {
    values.map { $0.description }
}

descriptions(of: (42, true))        // ("42", "true")
descriptions(of: (42, true, "XYZ")) // ("42", "true", "XYZ")
// reduce-like
func sum<(T: IntConvertible)...>(of values: (T...)) -> Int {
    values.reduce(0) { $0 + $1.asInt() }
}

sum(of: (3, 5.0))      // 8
sum(of: (3, 5.0, "7")) // 15

If those APIs using variadic generics are ABI-public or used from the same module, they can be specialized by unrolling in the same way as the operations for normal tuples.

square(of: (3, 5.0))
// then the specialized `square` function works like this
func squares(of values: (Int, Double)) -> (Int, Double) {
    ({ $0 * $0 }(values.0), { $0 * $0 }(values.1))
}

Without specializations, it can be handled at runtime and require some additions to ABI to represent something like generic closure objects. Although Swift does not support generic closure objects, it is a similar case to a runtime form of values whose types are specified by type parameters. Those values work similarly to values of generalized existentials, which are not supported.

It is remarkable that those variadic type parameters can be used only in the operations for tuples.

func foo<(T: AdditiveArithmetic)...>(_ xs: (T...)) {
    let x: T = T.zero      // ⛔ Compilation error
    
    _ = xs.map { (x: T) in // ✅ OK
        let y: T = x + x   // ✅ OK
        ...
    }
}

Summary

I proposed to break down variadic generics into three steps. Operations for tuples and variadic tuples can be discussed independently from variadic generics. I think they can be bases to discuss variadic generics. Because this is a rough sketch, it has a lot of issues, especially, syntactically. However, I think the semantics introduced here may be useful.

16 Likes

No offense but you completely ignored the effort done here: Variadic Generics

@DevAndArtist No. Before I created this thread, I discussed the proposal of the thread with my colleague and during the discussion I noticed that variadic generics can be broken down into small steps.

It was just an idea and I was not sure if it was a good approach. It is also composed of independent parts from variadic generics. So I created this thread as a pitch to gather opinions about the idea of this approach, not for concrete syntax and implementation about variadic generics.

Maybe I should have referred to it and linked to the thread. Sorry.

1 Like

Don‘t worry, this is a very complex topic and I think there are a lot of issues that needs to be solved. However I think we shouldn‘t defragment this topic and try to keep it in one place so everyone can follow the same evolution and fine tune the same first design.


And as I recently wrote in the other thread, I don‘t like the variadic 'packs' to automatically be collections, this is just a hack to avoid the general statically safe solution that still needs to be designed and defined.

I think topics in this thread are too apart from the ones in the thread you referred. It seems adequate for me that the threads are linked each other.

None of the operations in three steps handle tuples as collections. Because they are not collections but tuples, all operations are checked statically. Type safety fully remains.

func squares<T1: Numeric, T2: Numeric>(of values: (T1, T2)) -> (T1, T2) {
    values.map { $0 * $0 }
}

and

func squares<T1: Numeric, T2: Numeric>(of values: (T1, T2)) -> (T1, T2) {
    ({ $0 * $0 }(values.0), { $0 * $0 }(values.1))
}

are same.

map and reduce in the examples are semantically different from collections'.

And that‘s my point. You‘re proposing to push the topic forward, yet you have your own vision of this whole feature and do not consider that you could block further generalized designs. No offense though. ;)

I agree it’s worth linking to the other thread in this OP, but I disagree that “this town is too small for all of these threads” or that we as a community need to put all of our eggs in one basket or else never make any progress.

I have been following the other thread and I still welcome this view on how to break down the feature conceptually.

8 Likes

I really really really don't like the idea of using tuples as sequences. A tuple of type (T, U, V, ...) feels much more like a point in the space T*U*V*... to me than like an ordered collection of objects. The only sequence-y thing you should be able to do with them is compare them lexicographically (which, for tuples of a given length, isn't even really sequence-y because when there are a known number of elements you can just write the list of comparisons out by hand). If you want sequence-y behavior, you should use a real Sequence.

3 Likes

I think variadic generics is related to tuples, and "sequence-y thing" is required to handle them.

For example, please think about how do you implement the following squares function using variadic generics without "sequence-y thing"?

// This `T...` is not a variadic arguments here. It is pseudo syntax.
func squares<(T: Numeric)...>(of values: T...) -> (T...) { ... }

squares(of: 3, 5.0)               // (9, 25.0)
squares(of: 3, 5.0, 7.0 as Float) // (9, 25.0, 49.0 as Float)

The type of the argument values should be (Int, Double) when the squares function is called like squares(of: 3, 5.0). In the same way, (Int, Double, Float) for squares(of: 3, 5.0, 7.0 as Float). Do you prefer converting the arguments to a collection, calculating squares of elements and converting the result back to a tuple?

  • It is much slower. The type of the collection must be [Numeric] and it requires existentials which uses existential containers with comparatively huge overhead.
  • When the values have constrained by protocols with associated types or self-requirements, generalized existentials are required to handle the values as a collection.
    • e.g. How about when the values are constrained by SwiftUI.View? View cannot be a type because it has an associated type Body, and it means that making [View] instances is also impossible.
  • It still requires "sequence-y thing" for conversions between collections and tuples.
  • Conversions back to tuples from collections are type-unsafe because collections loses concrete types of each elements.

It seems more straightforward for me to handle them as tuples directly with special "sequence-y" operations provided for tuples.

When I thought about it, I had a question. That "sequence-y" operation should be available for normal tuples independently from variadic generics and introducing it in advance may make it easier to think about variadic generics.

3 Likes

At the moment, I think that variadic tuple spreading/merging would be the primitive operation:

// as pseudo syntax.
func squares<(T: Numeric)...>(of values: T...) -> (T...) {
  switch values {
  case (): return ()
  case let (t, ts...):
    return (t * t, squares(ts)...)
  }
}
3 Likes

It is simple and looks nice. But it may be hard to specialize without performance degradation. At least recursive inlining is required. Also branching should be removed. My understanding is that one goal of variadic generics is to unite APIs like this without performance degradation.

2 Likes

I put my hand last time into the fire. Variadic generics are basically some small part static metaprogramming facilities, which means it won‘t scale if you try to build it with existing features as we don‘t have any static metaprogramming features yet (besides property wrappers maybe). Variadic packs (basically variadic values variadic T), are similar to tuples but they are not tuples at all.

For variadic generics we would need an ability to iterate on variadic packs and also on the variadic type and tell the compiler statically how to generate type safe (boilerplate) code for us.

6 Likes

Indeed features like template metaprogramming in C++ are a measure way to realize variadic generics, but I think it is also possible to handle variadic generics at runtime. It is similar to the relation between templates in C++ and generics in Swift. Templates in C++ are expanded at compile time while generics in Swift can be handled at both compile time (specialization) and runtime. If it can be handled at runtime, it makes it possible to declare ABI-private public APIs with variadic generics. It also helps to keep binaries small.

3 Likes

I thought recursive inlining was not supported, but it seems to be supported in some cases.

Before my post, I checked LLVM-IR of the following code and the function was not inlined.

@inline(__always)
func factorial(of n: Int) -> Int {
    if n <= 1 { return 1 }
    else { return n * factorial(of: n - 1) }
}

print(factorial(of: 5)) // 120

However, a person told me that they checked similar code with a tail call had made it possible.

@inline(__always)
func factorial(of n: Int) -> Int {
    func f(_ n: Int, _ r: Int) -> Int {
        n <= 1 ? r : f(n - 1, r * n)
    }
    return f(n, 1)
}

print(factorial(of: 5)) // 120

120 is expanded into LLVM-IR.

...
define i32 @main(i32, i8** nocapture readnone) local_unnamed_addr #0 {
entry:
  ...
  %._value = bitcast %swift.refcounted* %13 to i64*
  store i64 120, i64* %._value, align 8
  ...
  ret i32 0
}
...

As someone who has a use-case waiting for variadic generics I consider it essential to be able to iterate over the variadic elements in a defined order. If we’re going to store those elements in a tuple, which admittedly feels quite natural to me, then we need to be able to do map/iteration on tuples.

@DevAndArtist Could you elaborate on why a variadic pack isn’t/shouldn’t be a tuple? Or to put it another way, why shouldn’t we extend tuples with all the operation we would want on a variadic pack?

I would encourage you to check the other thread. Variadic generics are not to make just tuples nice, there are more use cases which cannot be solved through tuples. :wink:

With respect, I’ve been following the other thread you linked and it doesn’t answer my question. I did however eventually find the related thread in the compiler development forum where tuples vs variadic pack was discussed so thanks :wink:

Edit: Here is the discussion of variadic tuples vs a new variadic pack type

4 Likes

@wiresoft Could you give a link? For those following along.

Looking at that link and the post yours replied to, we need to have variadic constraint checking too:

func sums<T: Collection, (U: Collection)...>(of first: T, _ others: U...) -> (T, U...) where U.Element == T.Element, T.Element: Numeric {
    switch others {
    case (): return first.reduce(0, +)
    case let (u, v...):
        return (first.reduce(0, +), #explode(sums(u, v...)))
    }
}
2 Likes
Terms of Service

Privacy Policy

Cookie Policy