TypeSequences.md

Motivation

Swift’s type system supports a number of different ways of taking a function or type and abstracting it. Usually, this is done by adding a generic parameter and an associated set of constraints. Similarly, a function that takes a particular type of argument can be abstracted to any number of those arguments by making it variadic with triple-dot (...) syntax. Today, both of these features are permitted separately: you can define a generic function that takes a variable number of arguments, such as

func debugPrint<T>(_ items: T...) 
  where T: CustomDebugStringConvertible
{   
  for (item: T) in items {
    stdout.write(item.debugDescription)
  }
}

However, this does not have the intended effect of allowing a function to accept a variable number of arguments of variable type, instead it allows you to accept a variable number of arguments at a single, fixed type. So, the following call is illegal:

debugPrint("Macs say Hello in ", 39, " languages!") 
// error: Conflicting arguments to generic parameter 'T' ('Int' vs 'String')

To take a less contrived example, SwiftUI’s primary result builder is a type called ViewBuilder. Today, ViewBuilder is artificially constrained to accept between 0 and 10 sub- View elements of differing types. What’s more, for each given arity, a fresh declaration of buildBlock must be given, which leads to an explosion in the amount of boilerplate necessary to build the strongly-typed API that such a library desires.

Finally, tuples have always held a special place in the Swift language, but working with arbitrary tuples remains a challenge today. In particular, there is no way to extend tuples, and so clients like the Swift Standard Library must take a similarly boilerplate-heavy approach and define special overloads at each arity for the comparison operators. There, the Standard Library chooses to artificially limit its overload set to tuples of length between 2 and 7, with each additional overload placing ever more strain on the type checker. Of particular note: This pitch lays the ground work for non-nominal conformances, but syntax for such conformances are out of scope.

Lifting these restrictions requires extending the Swift language’s generics system to support abstractions over groups of types, with a careful eye towards Swift’s traditional answer to grouping values as tuples. Historically, these have been referred to as variadic generics as an homage to the original implementation in C++ of variadic templates. In Swift, however, our generics system bears only a passing resemblance to C++‘s template metaprogramming system. In particular, the full slate of features envisioned here could not be implemented as a purely syntactic transformation of the AST.

To that end, this pitch proposes a new path towards implementing a generics system that allows both type and arity abstraction. I collectively refer to these features throughout the rest of this paper as Type Sequences. This is to distinguish them from variadic parameters in the Swift sense, and variadic templates in the C++ sense. As will be made clear, I also want to cast off the implication that there is a user-visible notion of “pack expansion” and “pack construction” as in C++, since these operations have a separate semantic meaning in Swift.

Packing Light

To address the concept of a function with parameters that are abstracted over both arity and type, a new kind of generic parameter is required. A type sequence parameter (spelled T... in the generic parameter clause) serves as a way to spell a type sequence in source and provides a user-defined handle to the abstract sequence itself. For example, the debugPrint function defined above should be amended to take a type sequence parameter instead of a plain type parameter

func debugPrint<T...>(_ items: T...) 
  where T: CustomDebugStringConvertible
{   
  for (item: T) in items {
    stdout.write(item.debugDescription)
  }
}

Here, T... internally refers to the Type Sequence Archetype (referred to less redundantly as a “Sequence Archetype”) whose elements are a heterogeneous ordered collection of opened archetypes T that each have a (possibly distinct) conformance to CustomDebugStringConvertible.

Note that the redundancy in spelling T... in the generics clause and T... in the parameter clause is intentional given the proposed syntax here. Consider this third alternative spelling of the debugPrint function:

func debugPrint<T...>(_ items: T) where T: CustomDebugStringConvertible { /.../ }

Here, T refers to a particular opened archetype of an element of the type sequence T..., however this function does not accept a T... anywhere as input anywhere. The type of this function is not semantically well-formed, and should be rejected with a note to mark the parameter as variadic.

As an ordered sequence of values, it is natural to expect that the usual operations on Swift Sequence types apply. As such, we aim to support three built-in operations on sequence archetypes,

• iteration - spelled for item in items
• length measurement - spelled, suggestively, _countTypeSequence(items)
• element-wise mapping - spelled, suggestively, _mapTypeSequence(_:transform:)

Plus one more distinguished operation on type sequences:

• explicit forwarding of parameters of type T... to other parameters of type T... - spelled _forwardTypeSequence(_:)

func measure<T...>(_ xs: T...) -> Int { return _countTypeSequence(xs) }

These preliminary names serve as a staging ground. I believe that there is enough overlap with normal sequences that we could spell these operations the “obvious” way of .count and .map respectively. But I want to be considerate of reserving names for magical operations that may conflict with user-defined syntax later. Further, the formal type of _mapTypeSequence is inexpressible in Swift as it requires the type checker to construct special archetypes to represent the sequence elements that are fed to the transformation function - akin to the _openExistential primitive.

At applies of arguments to functions with type sequence parameters, Swift will transparently convert those argument values to type sequences. This is intended to mirror the existing case where Swift converts normal variadic argument values to [T]. As in,

debugPrint("Macs say Hello in ", 39, " languages!") 

Crucially, we have the ability to statically measure the arity and type of a particular call to these functions. This means we have the ability to construct generic functions that don’t just take type sequences, but return them as well. Take the type of an identity function on type sequences:

func tuple<T...>(_ xs: T...) -> (T...) { return xs } 

While the definition of this function is maximally abstract, a call to this function has a fixed number and type of arguments. In much the same way a plain generic function resolves to a concrete type when applied, so too does this function resolve to a concrete tuple when applied to more than one argument, a single value when applied to one argument, and the empty tuple when fixed to no arguments:

tuple("Hi", 42, 3.14) // : (String, Int, Double)
tuple("Hi") // : String
tuple() // ()

Generic Nominal Types

In order to address the SwiftUI case, I propose that type sequences be allowed in generic position in nominal types. However, because we lack the ability to label generic parameters, we must restrict them to a single parameter. Thus

struct TypeSequenceView<Views...> where Views: View { /**/ }
struct Head<H, Tail...> { /**/ }
struct Tail<Init..., T> { /**/ }

Are legal, but

struct Zip<Xs..., Ys...> { /**/ }

Is not, as there is no way to distinguish which types T, U, V of Zip<T, U, V, ...> bind to which type parameter.

This also allows for stored properties of type sequence type within these nominal types.

struct Last<Head, L...> { 
  var value: L...
  init(_ : Head, rest: L...) { value = rest }
}
struct Init<I..., Tail> { 
  var value: I...
  init(_ : I..., last: Tail) { value = init }  
}

As with functions, stored properties in specializations of these types canonicalize to tuples:

Last<String, Int, Double>("Hello", rest: 42, 3.14).value // (42, 3.14)
Init<String, Int, Double>("Hello", 42, last: 3.14).value // ("Hello", 42)

Arity Constraints

Type sequences allow a new kind of generic requirement to be expressed in source: arity constraints. Consider the following function that takes a variable number of haystacks and needles:

func allPresent<T..., U...>(haystacks: T..., needles: U...) -> Bool
  where 
    T == Set<U>
{
  for (haystack, needle) in zip(haystacks, needles) {
    guard haystack.contains(needle) else { return false }
  }
  return true
}

The constraint T.Element == Set<U> expresses that each element of a needle-and-haystack pair sent to allPresent is coherent - that the contains operation is well-typed, but also that there are an equal number of arguments given to both the haystacks and the needles. For example,

allPresent(
  hayStacks: ["Hello"], ["Hi"], ["How are you?"],
  needles: "Hello", "there")
  // error! conflicting arguments in call:
  //   'hayStacks' is a sequence of 3 Sets, 
  //   'needles' is a sequence of 2 Strings
  // note: the same-type constraint T == Set<U> requires that 'hayStacks' and `needles` have the same number of elements

Arity constraints also propagate along direct references to the element type T in variadic position. So, the following is equivalent:

func allPresent2<T...>(haystacks: Set<T>..., needles: T...) -> Bool { /**/ }

Protocol Requirements

To simplify the implementation, type sequences may not appear in associated type requirements in protocols.

protocol P { associatedtype Ts... } // error!

However, this does not preclude implementing a protocol with a type sequence for a type requirement. In fact, doing so is crucial for generalizing a number of operations in the standard library. Consider a sketch of an implementation for a variadic ZipSequence type:

public func zip<Sequences...>(_ seqs: Sequences...) -> ZipSequence<Sequences...> 
  where Sequences: Sequence
{
    return ZipSequence(_forwardTypeSequence(seqs))
}

public struct ZipSequence<Sequences...>: Sequence
  where Sequences: Sequence 
{

  private let seqs: (Sequences...)
  
  public init(_ seqs: Sequences...) {
      self.seqs = seqs  
  }
  
  public func makeIterator() -> Self.Iterator {
    return Self.Iterator(_forwardTypeSequence(self.sequences))
  }
  
  public struct Iterator : IteratorProtocol {
    private enum Stop { case iterating }
    
    public typealias Element = (Sequences.Element...)
    
    var iterators: (Sequences.Iterator...)
    private var reachedEnd = false
    
    init(_ iterators: Sequences...) {
      self.iterators = _mapTypeSequence(_forwardTypeSequence(iterators), transform: { 
        $0.makeIterator() 
      })
    }

    public mutating func next() -> Element? {
      if reachedEnd { return nil }

      guard 
        let values = try? _mapTypeSequence(_forwardTypeSequence(iterators), transform: { 
          guard let next = $0.next() else { throw Stop.iterating } 
          return next
        }) 
      else {
        reachedEnd = true
        return nil
      }
      return values
    }
  }
}

The Future of Non-Nominal Conformances

This kind of internal harmony with tuple types makes type sequences an ideal place to start when reasoning about non-nominal conformances to types. As mentioned before, we consider the user-visible syntax for such conformances out of scope, but with the combined powers given by parameterized extensions, there is now a natural syntax for this:

extension<T...> (T...): Equatable where T: Equatable {
  public static func == (lhs: T..., rhs: T...) -> Bool { 
    for (l, r) in zip(lhs, rhs) {
      guard l == r else { return false }
    }
    return true
  }
}

As a first step towards this effort, and to prove out the runtime components of type sequences, I am exploring an implementation of SE-0283 based on great work done by Alejandro Alonso in this area. Currently, built-in conformances are used to implement structural Sendable checking, and carry no runtime heft. This would be the test of using them to bootstrap our way towards non-nominal conformances in general.

One particularly important note is that we do not want the semantics of extensions of type sequences to allow for the mythical ur-extension of all types:

extension T { ... }

Open Questions

• Does the spelling <T...> make sense in light of the duplication (or, semantic overlap if you prefer) with f(x: T...)? Triple-dots already play many distinct roles in Swift’s grammar given that they are the spelling for variadics, a user-defined operator part, partial ranges, etc. It may make sense to adopt a different delimiter. We want to avoid needing a turbofish.
  • There are some concerning examples where this syntax composes poorly:
    • func matrix<T...>(_ xss: (T...)...) - a function that takes an arbitrary number of a fixed kind of tuples. It is polymorphic over the kind of tuples as indicated by (T...), it is variadic, but it (perhaps surprisingly) must fail to be both: you cannot call matrix with e.g. a tuple of type (Int, String) and a tuple of type (String, Int).
• Are there additional built-in operations we could provide to make type sequences look and behave more like normal sequences - but with an eye towards the idea that eventually they will probably implement Sequence formally? On the other hand, having a more builtin-flavored spelling a la arity(of: T...) may also be desired.
• On implementing Sequence: the type of (T...).Element is an opened archetype T for which there is currently no spelling in the language.
• Sequence forwarding requires a special operation because Swift currently does not allow variadic parameters to forward to other variadic parameters. This is the oft-discussed splat operation. We should probably find a suitable way to syntax-ize splatting that is harmonious with this proposal. C++ offers us one avenue with leading ..., but Swift has already claimed that syntax for partial ranges.