[Manifesto] Completing Generics

Douglas_Gregor · March 3, 2016, 1:22am

Hi all,

Introduction

The “Complete Generics” goal for Swift 3 has been fairly ill-defined thus fair, with just this short blurb in the list of goals:

Complete generics: Generics are used pervasively in a number of Swift libraries, especially the standard library. However, there are a number of generics features the standard library requires to fully realize its vision, including recursive protocol constraints, the ability to make a constrained extension conform to a new protocol (i.e., an array of Equatable elements is Equatable), and so on. Swift 3.0 should provide those generics features needed by the standard library, because they affect the standard library's ABI.
This message expands upon the notion of “completing generics”. It is not a plan for Swift 3, nor an official core team communication, but it collects the results of numerous discussions among the core team and Swift developers, both of the compiler and the standard library. I hope to achieve several things:

Communicate a vision for Swift generics, building on the original generics design document <https://github.com/apple/swift/blob/master/docs/Generics.rst>, so we have something concrete and comprehensive to discuss.
Establish some terminology that the Swift developers have been using for these features, so our discussions can be more productive (“oh, you’re proposing what we refer to as ‘conditional conformances’; go look over at this thread”).
Engage more of the community in discussions of specific generics features, so we can coalesce around designs for public review. And maybe even get some of them implemented.

A message like this can easily turn into a centithread <Urban Dictionary: centithread. To separate concerns in our discussion, I ask that replies to this specific thread be limited to discussions of the vision as a whole: how the pieces fit together, what pieces are missing, whether this is the right long-term vision for Swift, and so on. For discussions of specific language features, e.g., to work out the syntax and semantics of conditional conformances or discuss the implementation in compiler or use in the standard library, please start a new thread based on the feature names I’m using.

This message covers a lot of ground; I’ve attempted a rough categorization of the various features, and kept the descriptions brief to limit the overall length. Most of these aren’t my ideas, and any syntax I’m providing is simply a way to express these ideas in code and is subject to change. Not all of these features will happen, either soon or ever, but they are intended to be a fairly complete whole that should mesh together. I’ve put a * next to features that I think are important in the nearer term vs. being interesting “some day”. Mostly, the *’s reflect features that will have a significant impact on the Swift standard library’s design and implementation.

Enough with the disclaimers; it’s time to talk features.

Removing unnecessary restrictions

There are a number of restrictions to the use of generics that fall out of the implementation in the Swift compiler. Removal of these restrictions is a matter of implementation only; one need not introduce new syntax or semantics to realize them. I’m listing them for two reasons: first, it’s an acknowledgment that these features are intended to exist in the model we have today, and, second, we’d love help with the implementation of these features.

*Recursive protocol constraints

Currently, an associated type cannot be required to conform to its enclosing protocol (or any protocol that inherits that protocol). For example, in the standard library SubSequence type of a Sequence should itself be a Sequence:

protocol Sequence {
  associatedtype Iterator : IteratorProtocol
  …
  associatedtype SubSequence : Sequence // currently ill-formed, but should be possible
}

The compiler currently rejects this protocol, which is unfortunate: it effectively pushes the SubSequence-must-be-a-Sequence requirement into every consumer of SubSequence, and does not communicate the intent of this abstraction well.

Nested generics

Currently, a generic type cannot be nested within another generic type, e.g.

struct X<T> {
struct Y { } // currently ill-formed, but should be possible
}

There isn’t much to say about this: the compiler simply needs to be improved to handle nested generics throughout.

Concrete same-type requirements

Currently, a constrained extension cannot use a same-type constraint to make a type parameter equivalent to a concrete type. For example:

extension Array where Element == String {
  func makeSentence() -> String {
    // uppercase first string, concatenate with spaces, add a period, whatever
  }
}

This is a highly-requested feature that fits into the existing syntax and semantics. Note that one could imagine introducing new syntax, e.g., extending “Array<String>”, which gets into new-feature territory: see the section on “Parameterized extensions”.

Parameterizing other declarations

There are a number of Swift declarations that currently cannot have generic parameters; some of those have fairly natural extensions to generic forms that maintain their current syntax and semantics, but become more powerful when made generic.

Generic typealiases

Typealiases could be allowed to carry generic parameters. They would still be aliases (i.e., they would not introduce new types). For example:

typealias StringDictionary<Value> = Dictionary<String, Value>

var d1 = StringDictionary<Int>()
var d2: Dictionary<String, Int> = d1 // okay: d1 and d2 have the same type, Dictionary<String, Int>

Generic subscripts

Subscripts could be allowed to have generic parameters. For example, we could introduce a generic subscript on a Collection that allows us to pull out the values at an arbitrary set of indices:

extension Collection {
 subscript<Indices: Sequence where Indices.Iterator.Element == Index>(indices: Indices) -> [Iterator.Element] {
 get {
 var result = [Iterator.Element]()
 for index in indices {
 result.append(self[index])
 }

return result
}

    set {
      for (index, value) in zip(indices, newValue) {
        self[index] = value
      }
    }
  }
}

Generic constants

let constants could be allowed to have generic parameters, such that they produce differently-typed values depending on how they are used. For example, this is particularly useful for named literal values, e.g.,

let π<T : FloatLiteralConvertible>: T = 3.141592653589793238462643383279502884197169399

The Clang importer could make particularly good use of this when importing macros.

Parameterized extensions

Extensions themselves could be parameterized, which would allow some structural pattern matching on types. For example, this would permit one to extend an array of optional values, e.g.,

extension<T> Array where Element == T? {
 var someValues: [T] {
 var result = [T]()
 for opt in self {
 if let value = opt { result.append(value) }
 }
 return result
 }
}

We can generalize this to a protocol extensions:

extension<T> Sequence where Element == T? {
 var someValues: [T] {
 var result = [T]()
 for opt in self {
 if let value = opt { result.append(value) }
 }
 return result
 }
}

Note that when one is extending nominal types, we could simplify the syntax somewhat to make the same-type constraint implicit in the syntax:

extension<T> Array<T?> {
 var someValues: [T] {
 var result = [T]()
 for opt in self {
 if let value = opt { result.append(value) }
 }
 return result
 }
}

When we’re working with concrete types, we can use that syntax to improve the extension of concrete versions of generic types (per “Concrete same-type requirements”, above), e.g.,

extension Array<String> {
 func makeSentence() -> String {
 // uppercase first string, concatenate with spaces, add a period, whatever
 }
}

Minor extensions

There are a number of minor extensions we can make to the generics system that don’t fundamentally change what one can express in Swift, but which can improve its expressivity.

*Arbitrary requirements in protocols

Currently, a new protocol can inherit from other protocols, introduce new associated types, and add new conformance constraints to associated types (by redeclaring an associated type from an inherited protocol). However, one cannot express more general constraints. Building on the example from “Recursive protocol constraints”, we really want the element type of a Sequence’s SubSequence to be the same as the element type of the Sequence, e.g.,

protocol Sequence {
  associatedtype Iterator : IteratorProtocol
  …
  associatedtype SubSequence : Sequence where SubSequence.Iterator.Element == Iterator.Element
}

Hanging the where clause off the associated type is protocol not ideal, but that’s a discussion for another thread.

*Typealiases in protocols and protocol extensions

Now that associated types have their own keyword (thanks!), it’s reasonable to bring back “typealias”. Again with the Sequence protocol:

protocol Sequence {
associatedtype Iterator : IteratorProtocol
typealias Element = Iterator.Element // rejoice! now we can refer to SomeSequence.Element rather than SomeSequence.Iterator.Element
}

Default generic arguments

Generic parameters could be given the ability to provide default arguments, which would be used in cases where the type argument is not specified and type inference could not determine the type argument. For example:

public final class Promise<Value, Reason=Error> { … }

func getRandomPromise() -> Promise<Int, ErrorProtocol> { … }

var p1: Promise<Int> = …
var p2: Promise<Int, Error> = p1 // okay: p1 and p2 have the same type Promise<Int, Error>
var p3: Promise = getRandomPromise() // p3 has type Promise<Int, ErrorProtocol> due to type inference

Generalized “class” constraints

The “class” constraint can currently only be used for defining protocols. We could generalize it to associated type and type parameter declarations, e.g.,

protocol P {
associatedtype A : class
}

func foo<T : class>(t: T) { }

As part of this, the magical AnyObject protocol could be replaced with an existential with a class bound, so that it becomes a typealias:

typealias AnyObject = protocol<class>

See the “Existentials” section, particularly “Generalized existentials”, for more information.

*Allowing subclasses to override requirements satisfied by defaults

When a superclass conforms to a protocol and has one of the protocol’s requirements satisfied by a member of a protocol extension, that member currently cannot be overridden by a subclass. For example:

protocol P {
func foo()
}

extension P {
func foo() { print(“P”) }
}

class C : P {
// gets the protocol extension’s
}

class D : C {
/*override not allowed!*/ func foo() { print(“D”) }
}

let p: P = D()
p.foo() // gotcha: prints “P” rather than “D”!

D.foo should be required to specify “override” and should be called dynamically.

Major extensions to the generics model

Unlike the minor extensions, major extensions to the generics model provide more expressivity in the Swift generics system and, generally, have a much more significant design and implementation cost.

*Conditional conformances

Conditional conformances express the notion that a generic type will conform to a particular protocol only under certain circumstances. For example, Array is Equatable only when its elements are Equatable:

extension Array : Equatable where Element : Equatable { }

func ==<T : Equatable>(lhs: Array<T>, rhs: Array<T>) -> Bool { … }

Conditional conformances are a potentially very powerful feature. One important aspect of this feature is how deal with or avoid overlapping conformances. For example, imagine an adaptor over a Sequence that has conditional conformances to Collection and MutableCollection:

struct SequenceAdaptor<S: Sequence> : Sequence { }
extension SequenceAdaptor : Collection where S: Collection { … }
extension SequenceAdaptor : MutableCollection where S: MutableCollection { }

This should almost certainly be permitted, but we need to cope with or reject “overlapping” conformances:

extension SequenceAdaptor : Collection where S: SomeOtherProtocolSimilarToCollection { } // trouble: two ways for SequenceAdaptor to conform to Collection

See the section on “Private conformances” for more about the issues with having the same type conform to the same protocol multiple times.

Variadic generics

Currently, a generic parameter list contains a fixed number of generic parameters. If one has a type that could generalize to any number of generic parameters, the only real way to deal with it today involves creating a set of types. For example, consider the standard library’s “zip” function. It returns one of these when provided with two arguments to zip together:

public struct Zip2Sequence<Sequence1 : Sequence,
Sequence2 : Sequence> : Sequence { … }

public func zip<Sequence1 : Sequence, Sequence2 : Sequence>(
sequence1: Sequence1, _ sequence2: Sequence2)
-> Zip2Sequence<Sequence1, Sequence2> { … }

Supporting three arguments would require copy-paste of those of those:

public struct Zip3Sequence<Sequence1 : Sequence,
Sequence2 : Sequence,
Sequence3 : Sequence> : Sequence { … }

public func zip<Sequence1 : Sequence, Sequence2 : Sequence, Sequence3 : Sequence>(
sequence1: Sequence1, _ sequence2: Sequence2, _ sequence3: sequence3)
-> Zip3Sequence<Sequence1, Sequence2, Sequence3> { … }

Variadic generics would allow us to abstract over a set of generic parameters. The syntax below is hopelessly influenced by C++11 variadic templates <http://www.jot.fm/issues/issue_2008_02/article2/> (sorry), where putting an ellipsis (“…”) to the left of a declaration makes it a “parameter pack” containing zero or more parameters and putting an ellipsis to the right of a type/expression/etc. expands the parameter packs within that type/expression into separate arguments. The important part is that we be able to meaningfully abstract over zero or more generic parameters, e.g.:

public struct ZipIterator<... Iterators : IteratorProtocol> : Iterator { // zero or more type parameters, each of which conforms to IteratorProtocol
public typealias Element = (Iterators.Element...) // a tuple containing the element types of each iterator in Iterators

var (...iterators): (Iterators...) // zero or more stored properties, one for each type in Iterators
var reachedEnd: Bool = false

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

    guard let values = (iterators.next()...) { // call “next” on each of the iterators, put the results into a tuple named “values"
      reachedEnd = true
      return nil
    }

return values
}
}

public struct ZipSequence<...Sequences : Sequence> : Sequence {
public typealias Iterator = ZipIterator<Sequences.Iterator...> // get the zip iterator with the iterator types of our Sequences

var (...sequences): (Sequences...) // zero or more stored properties, one for each type in Sequences

// details ...
}

Such a design could also work for function parameters, so we can pack together multiple function arguments with different types, e.g.,

public func zip<... Sequences : SequenceType>(... sequences: Sequences...)
-> ZipSequence<Sequences...> {
return ZipSequence(sequences...)
}

Finally, this could tie into the discussions about a tuple “splat” operator. For example:

func apply<... Args, Result>(fn: (Args...) -> Result, // function taking some number of arguments and producing Result
args: (Args...)) -> Result { // tuple of arguments
return fn(args...) // expand the arguments in the tuple “args” into separate arguments
}

Extensions of structural types

Currently, only nominal types (classes, structs, enums, protocols) can be extended. One could imagine extending structural types—particularly tuple types—to allow them to, e.g., conform to protocols. For example, pulling together variadic generics, parameterized extensions, and conditional conformances, one could express “a tuple type is Equatable if all of its element types are Equatable”:

extension<...Elements : Equatable> (Elements...) : Equatable { // extending the tuple type “(Elements…)” to be Equatable
}

There are some natural bounds here: one would need to have actual structural types. One would not be able to extend every type:

extension<T> T { // error: neither a structural nor a nominal type
}

And before you think you’re cleverly making it possible to have a conditional conformance that makes every type T that conforms to protocol P also conform to protocol Q, see the section "Conditional conformances via protocol extensions”, below:

extension<T : P> T : Q { // error: neither a structural nor a nominal type
}

Syntactic improvements

There are a number of potential improvements we could make to the generics syntax. Such a list could go on for a very long time, so I’ll only highlight some obvious ones that have been discussed by the Swift developers.

*Default implementations in protocols

Currently, protocol members can never have implementations. We could allow one to provide such implementations to be used as the default if a conforming type does not supply an implementation, e.g.,

protocol Bag {
associatedtype Element : Equatable
func contains(element: Element) -> Bool

func containsAll<S: Sequence where Sequence.Iterator.Element == Element>(elements: S) -> Bool {
 for x in elements {
 if contains(x) { return true }
 }
 return false
 }
}

struct IntBag : Bag {
typealias Element = Int
func contains(element: Int) -> Bool { ... }

// okay: containsAll requirement is satisfied by Bag’s default implementation
}

One can get this effect with protocol extensions today, hence the classification of this feature as a (mostly) syntactic improvement:

protocol Bag {
associatedtype Element : Equatable
func contains(element: Element) -> Bool

func containsAll<S: Sequence where Sequence.Iterator.Element == Element>(elements: S) -> Bool
}

extension Bag {
 func containsAll<S: Sequence where Sequence.Iterator.Element == Element>(elements: S) -> Bool {
 for x in elements {
 if contains(x) { return true }
 }
 return false
 }
}

*Moving the where clause outside of the angle brackets

The “where” clause of generic functions comes very early in the declaration, although it is generally of much less concern to the client than the function parameters and result type that follow it. This is one of the things that contributes to “angle bracket blindness”. For example, consider the containsAll signature above:

func containsAll<S: Sequence where Sequence.Iterator.Element == Element>(elements: S) -> Bool

One could move the “where” clause to the end of the signature, so that the most important parts—name, generic parameter, parameters, result type—precede it:

func containsAll<S: Sequence>(elements: S) -> Bool
where Sequence.Iterator.Element == Element

*Renaming “protocol<…>” to “Any<…>”.

The “protocol<…>” syntax is a bit of an oddity in Swift. It is used to compose protocols together, mostly to create values of existential type, e.g.,

var x: protocol<NSCoding, NSCopying>

It’s weird that it’s a type name that starts with a lowercase letter, and most Swift developers probably never deal with this feature unless they happen to look at the definition of Any:

typealias Any = protocol<>

“Any” might be a better name for this functionality. “Any” without brackets could be a keyword for “any type”, and “Any” followed by brackets could take the role of “protocol<>” today:

var x: Any<NSCoding, NSCopying>

That reads much better: “Any type that conforms to NSCoding and NSCopying”. See the section "Generalized existentials” for additional features in this space.

Maybe

There are a number of features that get discussed from time-to-time, while they could fit into Swift’s generics system, it’s not clear that they belong in Swift at all. The important question for any feature in this category is not “can it be done” or “are there cool things we can express”, but “how can everyday Swift developers benefit from the addition of such a feature?”. Without strong motivating examples, none of these “maybes” will move further along.

Dynamic dispatch for members of protocol extensions

Only the requirements of protocols currently use dynamic dispatch, which can lead to surprises:

protocol P {
func foo()
}

extension P {
func foo() { print(“P.foo()”)
func bar() { print(“P.bar()”)
}

struct X : P {
func foo() { print(“X.foo()”)
func bar() { print(“X.bar()”)
}

let x = X()
x.foo() // X.foo()
x.bar() // X.bar()

let p: P = X()
p.foo() // X.foo()
p.bar() // P.bar()

Swift could adopt a model where members of protocol extensions are dynamically dispatched.

Named generic parameters

When specifying generic arguments for a generic type, the arguments are always positional: Dictionary<String, Int> is a Dictionary whose Key type is String and whose Value type is Int, by convention. One could permit the arguments to be labeled, e.g.,

var d: Dictionary<Key: String, Value: Int>

Such a feature makes more sense if Swift gains default generic arguments, because generic argument labels would allow one to skip defaulted arguments.

Generic value parameters

Currently, Swift’s generic parameters are always types. One could imagine allowing generic parameters that are values, e.g.,

struct MultiArray<T, let Dimensions: Int> { // specify the number of dimensions to the array
 subscript (indices: Int...) -> T {
 get {
 require(indices.count == Dimensions)
 // ...
 }
}

A suitably general feature might allow us to express fixed-length array or vector types as a standard library component, and perhaps also allow one to implement a useful dimensional analysis library. Tackling this feature potentially means determining what it is for an expression to be a “constant expression” and diving into dependent-typing, hence the “maybe”.

Higher-kinded types

Higher-kinded types allow one to express the relationship between two different specializations of the same nominal type within a protocol. For example, if we think of the Self type in a protocol as really being “Self<T>”, it allows us to talk about the relationship between “Self<T>” and “Self” for some other type U. For example, it could allow the “map” operation on a collection to return a collection of the same kind but with a different operation, e.g.,

let intArray: Array<Int> = …
intArray.map { String($0) } // produces Array<String>
let intSet: Set<Int> = …
intSet.map { String($0) } // produces Set<String>

Potential syntax borrowed from one thread on higher-kinded types <https://lists.swift.org/pipermail/swift-evolution/Week-of-Mon-20151214/002736.html> uses ~= as a “similarity” constraint to describe a Functor protocol:

protocol Functor {
associatedtype A
func fmap<FB where FB ~= Self>(f: A -> FB.A) -> FB
}

Specifying type arguments for uses of generic functions

The type arguments of a generic function are always determined via type inference. For example, given:

func f<T>(t: T)

one cannot directly specify T: either one calls “f” (and T is determined via the argument’s type) or one uses “f” in a context where it is given a particular function type (e.g., “let x: (Int) -> Void = f” would infer T = Int). We could permit explicit specialization here, e.g.,

let x = f<Int> // x has type (Int) -> Void

Unlikely

Features in this category have been requested at various times, but they don’t fit well with Swift’s generics system because they cause some part of the model to become overly complicated, have unacceptable implementation limitations, or overlap significantly with existing features.

Generic protocols

One of the most commonly requested features is the ability to parameterize protocols themselves. For example, a protocol that indicates that the Self type can be constructed from some specified type T:

protocol ConstructibleFromValue<T> {
init(_ value: T)
}

Implicit in this feature is the ability for a given type to conform to the protocol in two different ways. A “Real” type might be constructible from both Float and Double, e.g.,

struct Real { … }
extension Real : ConstructibleFrom<Float> {
init(_ value: Float) { … }
}
extension Real : ConstructibleFrom<Double> {
init(_ value: Double) { … }
}

Most of the requests for this feature actually want a different feature. They tend to use a parameterized Sequence as an example, e.g.,

protocol Sequence<Element> { … }

func foo(strings: Sequence<String>) { /// works on any sequence containing Strings
// ...
}

The actual requested feature here is the ability to say “Any type that conforms to Sequence whose Element type is String”, which is covered by the section on “Generalized existentials”, below.

More importantly, modeling Sequence with generic parameters rather than associated types is tantalizing but wrong: you don’t want a type conforming to Sequence in multiple ways, or (among other things) your for..in loops stop working, and you lose the ability to dynamically cast down to an existential “Sequence” without binding the Element type (again, see “Generalized existentials”). Use cases similar to the ConstructibleFromValue protocol above seem too few to justify the potential for confusion between associated types and generic parameters of protocols; we’re better off not having the latter.

Private conformances

Right now, a protocol conformance can be no less visible than the minimum of the conforming type’s access and the protocol’s access. Therefore, a public type conforming to a public protocol must provide the conformance publicly. One could imagine removing that restriction, so that one could introduce a private conformance:

public protocol P { }
public struct X { }
extension X : internal P { … } // X conforms to P, but only within this module

The main problem with private conformances is the interaction with dynamic casting. If I have this code:

func foo(value: Any) {
if let x = value as? P { print(“P”) }
}

foo(X())

Under what circumstances should it print “P”? If foo() is defined within the same module as the conformance of X to P? If the call is defined within the same module as the conformance of X to P? Never? Either of the first two answers requires significant complications in the dynamic casting infrastructure to take into account the module in which a particular dynamic cast occurred (the first option) or where an existential was formed (the second option), while the third answer breaks the link between the static and dynamic type systems—none of which is an acceptable result.

Conditional conformances via protocol extensions

We often get requests to make a protocol conform to another protocol. This is, effectively, the expansion of the notion of “Conditional conformances” to protocol extensions. For example:

protocol P {
func foo()
}

protocol Q {
func bar()
}

extension Q : P { // every type that conforms to Q also conforms to P
  func foo() { // implement “foo” requirement in terms of “bar"
    bar()
  }
}

func f<T: P>(t: T) { … }

struct X : Q {
func bar() { … }
}

f(X()) // okay: X conforms to P through the conformance of Q to P

This is an extremely powerful feature: is allows one to map the abstractions of one domain into another domain (e.g., every Matrix is a Graph). However, similar to private conformances, it puts a major burden on the dynamic-casting runtime to chase down arbitrarily long and potentially cyclic chains of conformances, which makes efficient implementation nearly impossible.

Potential removals

The generics system doesn’t seem like a good candidate for a reduction in scope; most of its features do get used fairly pervasively in the standard library, and few feel overly anachronistic. However...

Associated type inference

Associated type inference is the process by which we infer the type bindings for associated types from other requirements. For example:

protocol IteratorProtocol {
associatedtype Element
mutating func next() -> Element?
}

struct IntIterator : IteratorProtocol {
mutating func next() -> Int? { … } // use this to infer Element = Int
}

Associated type inference is a useful feature. It’s used throughout the standard library, and it helps keep associated types less visible to types that simply want to conform to a protocol. On the other hand, associated type inference is the only place in Swift where we have a global type inference problem: it has historically been a major source of bugs, and implementing it fully and correctly requires a drastically different architecture to the type checker. Is the value of this feature worth keeping global type inference in the Swift language, when we have deliberatively avoided global type inference elsewhere in the language?

Existentials

Existentials aren’t really generics per se, but the two systems are closely intertwined due to their mutable dependence on protocols.

*Generalized existentials

The restrictions on existential types came from an implementation limitation, but it is reasonable to allow a value of protocol type even when the protocol has Self constraints or associated types. For example, consider IteratorProtocol again and how it could be used as an existential:

protocol IteratorProtocol {
associatedtype Element
mutating func next() -> Element?
}

let it: IteratorProtocol = …
it.next() // if this is permitted, it could return an “Any?”, i.e., the existential that wraps the actual element

Additionally, it is reasonable to want to constrain the associated types of an existential, e.g., “a Sequence whose element type is String” could be expressed by putting a where clause into “protocol<…>” or “Any<…>” (per “Renaming protocol<…> to Any<…>”):

let strings: Any<Sequence where .Iterator.Element == String> = [“a”, “b”, “c”]

The leading “.” indicates that we’re talking about the dynamic type, i.e., the “Self” type that’s conforming to the Sequence protocol. There’s no reason why we cannot support arbitrary “where” clauses within the “Any<…>”. This very-general syntax is a bit unwieldy, but common cases can easily be wrapped up in a generic typealias (see the section “Generic typealiases” above):

typealias AnySequence<Element> = Any<Sequence where .Iterator.Element == Element>
let strings: AnySequence<String> = [“a”, “b”, “c”]

Opening existentials

Generalized existentials as described above will still have trouble with protocol requirements that involve Self or associated types in function parameters. For example, let’s try to use Equatable as an existential:

protocol Equatable {
func ==(lhs: Self, rhs: Self) -> Bool
func !=(lhs: Self, rhs: Self) -> Bool
}

let e1: Equatable = …
let e2: Equatable = …
if e1 == e2 { … } // error: e1 and e2 don’t necessarily have the same dynamic type

One explicit way to allow such operations in a type-safe manner is to introduce an “open existential” operation of some sort, which extracts and gives a name to the dynamic type stored inside an existential. For example:

if let storedInE1 = e1 openas T { // T is a the type of storedInE1, a copy of the value stored in e1
  if let storedInE2 = e2 as? T { // is e2 also a T?
    if storedInE1 == storedInE2 { … } // okay: storedInT1 and storedInE2 are both of type T, which we know is Equatable
  }
}

Thoughts?

- Doug

Joe_Groff · March 3, 2016, 1:38am

You don't need private conformances to introduce these coherence problems with dynamic casting. You only need two modules that independently extend a common type to conform to a common protocol. As Jordan discussed in his resilience manifesto, a publicly-subclassable base class that adopts a new protocol has the potential to create a conflicting conformance with external subclasses that may have already adopted that protocol. This seems to me like poor grounds for rejecting the ability to have private conformances. I think they're a really useful feature.

-Joe

···

On Mar 2, 2016, at 5:22 PM, Douglas Gregor via swift-evolution <swift-evolution@swift.org> wrote:

Private conformances

Right now, a protocol conformance can be no less visible than the minimum of the conforming type’s access and the protocol’s access. Therefore, a public type conforming to a public protocol must provide the conformance publicly. One could imagine removing that restriction, so that one could introduce a private conformance:

public protocol P { }
public struct X { }
extension X : internal P { … } // X conforms to P, but only within this module

The main problem with private conformances is the interaction with dynamic casting. If I have this code:

func foo(value: Any) {
if let x = value as? P { print(“P”) }
}

foo(X())

Under what circumstances should it print “P”? If foo() is defined within the same module as the conformance of X to P? If the call is defined within the same module as the conformance of X to P? Never? Either of the first two answers requires significant complications in the dynamic casting infrastructure to take into account the module in which a particular dynamic cast occurred (the first option) or where an existential was formed (the second option), while the third answer breaks the link between the static and dynamic type systems—none of which is an acceptable result.

Joe_Groff · March 3, 2016, 1:50am

*Generalized existentials

The restrictions on existential types came from an implementation limitation, but it is reasonable to allow a value of protocol type even when the protocol has Self constraints or associated types. For example, consider IteratorProtocol again and how it could be used as an existential:

protocol IteratorProtocol {
associatedtype Element
mutating func next() -> Element?
}

let it: IteratorProtocol = …
it.next() // if this is permitted, it could return an “Any?”, i.e., the existential that wraps the actual element

Additionally, it is reasonable to want to constrain the associated types of an existential, e.g., “a Sequence whose element type is String” could be expressed by putting a where clause into “protocol<…>” or “Any<…>” (per “Renaming protocol<…> to Any<…>”):

let strings: Any<Sequence where .Iterator.Element == String> = [“a”, “b”, “c”]

The leading “.” indicates that we’re talking about the dynamic type, i.e., the “Self” type that’s conforming to the Sequence protocol. There’s no reason why we cannot support arbitrary “where” clauses within the “Any<…>”. This very-general syntax is a bit unwieldy, but common cases can easily be wrapped up in a generic typealias (see the section “Generic typealiases” above):

typealias AnySequence<Element> = Any<Sequence where .Iterator.Element == Element>
let strings: AnySequence<String> = [“a”, “b”, “c”]

Something else to consider: Maybe we should require Any<...> to refer to all existential types, including single-protocol existentials (so you'd have to say var x: Any<Drawable> instead of var x: Drawable). Between static method requirements, init requirements, and contravariant self and associated type constraints, there are a lot of ways our protocols can diverge in their capabilities as constraints and dynamic types. And with resilience, *no* public protocol type can be assumed to resilient implicitly conform to its protocol, since new versions may introduce new requirements that break the self-conformance. If protocols are namespaced separately from types, you could still do something like:

typealias Drawable: Drawable = Any<Drawable>

if you intend to use the protocol type primarily as a dynamic type (and assert that it's self-conforming).

Opening existentials

Generalized existentials as described above will still have trouble with protocol requirements that involve Self or associated types in function parameters. For example, let’s try to use Equatable as an existential:

protocol Equatable {
  func ==(lhs: Self, rhs: Self) -> Bool
  func !=(lhs: Self, rhs: Self) -> Bool
}

let e1: Equatable = …
let e2: Equatable = …
if e1 == e2 { … } // error: e1 and e2 don’t necessarily have the same dynamic type

One explicit way to allow such operations in a type-safe manner is to introduce an “open existential” operation of some sort, which extracts and gives a name to the dynamic type stored inside an existential. For example:

if let storedInE1 = e1 openas T { // T is a the type of storedInE1, a copy of the value stored in e1
  if let storedInE2 = e2 as? T { // is e2 also a T?
    if storedInE1 == storedInE2 { … } // okay: storedInT1 and storedInE2 are both of type T, which we know is Equatable
  }
}

Another possibility here is to allow for path-dependent types based on a 'let' binding:

let e1: Any<Equatable> = ...
let e2: Any<Equatable> = ...
// Is e2 the same static type as e1?
if let e3 = e2 as? e1.Self {
return e1 == e3
}

let s1: Any<Sequence> = ...
let s2: Any<Sequence> = ...
// Are the sequences of the same type? If so, concatenate them.
var x: [s1.Element] =
if let s3 = s2 as? Any<Sequence where Element == s1.Element> {
x += s1
x += s3
}

A close kin to angle-bracket blindness is type variable blindness. It'd be nice to avoid having to introduce explicit local type variables.

-Joe

···

On Mar 2, 2016, at 5:22 PM, Douglas Gregor via swift-evolution <swift-evolution@swift.org> wrote:

David_Smith · March 3, 2016, 2:20am

Thanks for sending this out! A lot of the stuff here looks amazingly useful, and I'm excited to see it being discussed.

The choice of Equatable as an example for opening existentials is an interesting one here, because it's one of the few cases I can think of where differing dynamic types is actually fully defined: they're not equal. In ObjC we express that by starting every -isEqual: implementation with if (![other isKindOfClass:[self class]]) { return NO; }, which while clunky and easy to forget, does neatly express the desired semantics with no burden at the callsite.

My first thought for how to express that in Swift was "ok, provide an == for (Any, Any) that just always says false", but that would defeat the ability to say something just doesn't make sense to compare with ==, which is a nice feature and prevents bugs.

Next thought for expressing it cleanly was:

protocol Equatable {
    func ==(lhs: Self, rhs: Self) -> Bool
    func !=(lhs: Self, rhs: Self) -> Bool
    func ==(lhs: Self, rhs: !Self) -> Bool { return false }
    func !=(lhs: Self, rhs: !Self) -> Bool { return true }
}

and I guess another equivalent way of writing it that doesn't require a new syntactic construct would be:

protocol Equatable {
 func ==(lhs: Self, rhs: Self) -> Bool
 func !=(lhs: Self, rhs: Self) -> Bool
 func ==<Other:Equatable where Other != Self>(lhs: Self, rhs: Other) -> Bool { return false }
 func !=<Other:Equatable where Other != Self>(lhs: Self, rhs: Other) -> Bool { return true }
}

which would make this idea a minor extension of the "Concrete Same-Type Requirements" section.

However, this still has a similar flaw to the first idea I had, which is that it introduces a valid == operator for things that never make sense to compare, when what we actually want is one that will only be accepted if there's insufficient information to determine whether it's valid (i.e. Equatable existentials). I suppose there's a relatively obvious syntax to express that directly:

protocol Equatable {
 func ==(lhs: Self, rhs: Self) -> Bool
 func !=(lhs: Self, rhs: Self) -> Bool
 func ==<Other:Equatable where Other ?= Self>(lhs: Self, rhs: Other) -> Bool { return false }
 func !=<Other:Equatable where Other ?= Self>(lhs: Self, rhs: Other) -> Bool { return true }
}

Where "?=" would be read as "might be equal to". It's not clear to me if this sort of "default implementation for non-matching existentials" concept is applicable beyond Equatable though, and if not it seems like a lot of machinery to add for one case.

David

···

On Mar 2, 2016, at 5:22 PM, Douglas Gregor via swift-evolution <swift-evolution@swift.org> wrote:

Hi all,

Introduction

The “Complete Generics” goal for Swift 3 has been fairly ill-defined thus fair, with just this short blurb in the list of goals:

Complete generics: Generics are used pervasively in a number of Swift libraries, especially the standard library. However, there are a number of generics features the standard library requires to fully realize its vision, including recursive protocol constraints, the ability to make a constrained extension conform to a new protocol (i.e., an array of Equatable elements is Equatable), and so on. Swift 3.0 should provide those generics features needed by the standard library, because they affect the standard library's ABI.
This message expands upon the notion of “completing generics”. It is not a plan for Swift 3, nor an official core team communication, but it collects the results of numerous discussions among the core team and Swift developers, both of the compiler and the standard library. I hope to achieve several things:

Communicate a vision for Swift generics, building on the original generics design document <https://github.com/apple/swift/blob/master/docs/Generics.rst>, so we have something concrete and comprehensive to discuss.
Establish some terminology that the Swift developers have been using for these features, so our discussions can be more productive (“oh, you’re proposing what we refer to as ‘conditional conformances’; go look over at this thread”).
Engage more of the community in discussions of specific generics features, so we can coalesce around designs for public review. And maybe even get some of them implemented.

A message like this can easily turn into a centithread <Urban Dictionary: centithread. To separate concerns in our discussion, I ask that replies to this specific thread be limited to discussions of the vision as a whole: how the pieces fit together, what pieces are missing, whether this is the right long-term vision for Swift, and so on. For discussions of specific language features, e.g., to work out the syntax and semantics of conditional conformances or discuss the implementation in compiler or use in the standard library, please start a new thread based on the feature names I’m using.

This message covers a lot of ground; I’ve attempted a rough categorization of the various features, and kept the descriptions brief to limit the overall length. Most of these aren’t my ideas, and any syntax I’m providing is simply a way to express these ideas in code and is subject to change. Not all of these features will happen, either soon or ever, but they are intended to be a fairly complete whole that should mesh together. I’ve put a * next to features that I think are important in the nearer term vs. being interesting “some day”. Mostly, the *’s reflect features that will have a significant impact on the Swift standard library’s design and implementation.

Enough with the disclaimers; it’s time to talk features.

Removing unnecessary restrictions

There are a number of restrictions to the use of generics that fall out of the implementation in the Swift compiler. Removal of these restrictions is a matter of implementation only; one need not introduce new syntax or semantics to realize them. I’m listing them for two reasons: first, it’s an acknowledgment that these features are intended to exist in the model we have today, and, second, we’d love help with the implementation of these features.

*Recursive protocol constraints

Currently, an associated type cannot be required to conform to its enclosing protocol (or any protocol that inherits that protocol). For example, in the standard library SubSequence type of a Sequence should itself be a Sequence:

protocol Sequence {
 associatedtype Iterator : IteratorProtocol
 …
 associatedtype SubSequence : Sequence // currently ill-formed, but should be possible
}

The compiler currently rejects this protocol, which is unfortunate: it effectively pushes the SubSequence-must-be-a-Sequence requirement into every consumer of SubSequence, and does not communicate the intent of this abstraction well.

Nested generics

Currently, a generic type cannot be nested within another generic type, e.g.

struct X<T> {
 struct Y { } // currently ill-formed, but should be possible
}

There isn’t much to say about this: the compiler simply needs to be improved to handle nested generics throughout.

Concrete same-type requirements

Currently, a constrained extension cannot use a same-type constraint to make a type parameter equivalent to a concrete type. For example:

extension Array where Element == String {
 func makeSentence() -> String {
 // uppercase first string, concatenate with spaces, add a period, whatever
 }
}

This is a highly-requested feature that fits into the existing syntax and semantics. Note that one could imagine introducing new syntax, e.g., extending “Array<String>”, which gets into new-feature territory: see the section on “Parameterized extensions”.

Parameterizing other declarations

There are a number of Swift declarations that currently cannot have generic parameters; some of those have fairly natural extensions to generic forms that maintain their current syntax and semantics, but become more powerful when made generic.

Generic typealiases

Typealiases could be allowed to carry generic parameters. They would still be aliases (i.e., they would not introduce new types). For example:

typealias StringDictionary<Value> = Dictionary<String, Value>

var d1 = StringDictionary<Int>()
var d2: Dictionary<String, Int> = d1 // okay: d1 and d2 have the same type, Dictionary<String, Int>

Generic subscripts

Subscripts could be allowed to have generic parameters. For example, we could introduce a generic subscript on a Collection that allows us to pull out the values at an arbitrary set of indices:

extension Collection {
 subscript<Indices: Sequence where Indices.Iterator.Element == Index>(indices: Indices) -> [Iterator.Element] {
 get {
 var result = [Iterator.Element]()
 for index in indices {
 result.append(self[index])
 }

 return result
 }

 set {
 for (index, value) in zip(indices, newValue) {
 self[index] = value
 }
 }
 }
}

Generic constants

let constants could be allowed to have generic parameters, such that they produce differently-typed values depending on how they are used. For example, this is particularly useful for named literal values, e.g.,

let π<T : FloatLiteralConvertible>: T = 3.141592653589793238462643383279502884197169399

The Clang importer could make particularly good use of this when importing macros.

Parameterized extensions

Extensions themselves could be parameterized, which would allow some structural pattern matching on types. For example, this would permit one to extend an array of optional values, e.g.,

extension<T> Array where Element == T? {
 var someValues: [T] {
 var result = [T]()
 for opt in self {
 if let value = opt { result.append(value) }
 }
 return result
 }
}

We can generalize this to a protocol extensions:

extension<T> Sequence where Element == T? {
 var someValues: [T] {
 var result = [T]()
 for opt in self {
 if let value = opt { result.append(value) }
 }
 return result
 }
}

Note that when one is extending nominal types, we could simplify the syntax somewhat to make the same-type constraint implicit in the syntax:

extension<T> Array<T?> {
 var someValues: [T] {
 var result = [T]()
 for opt in self {
 if let value = opt { result.append(value) }
 }
 return result
 }
}

When we’re working with concrete types, we can use that syntax to improve the extension of concrete versions of generic types (per “Concrete same-type requirements”, above), e.g.,

extension Array<String> {
 func makeSentence() -> String {
 // uppercase first string, concatenate with spaces, add a period, whatever
 }
}

Minor extensions

There are a number of minor extensions we can make to the generics system that don’t fundamentally change what one can express in Swift, but which can improve its expressivity.

*Arbitrary requirements in protocols

Currently, a new protocol can inherit from other protocols, introduce new associated types, and add new conformance constraints to associated types (by redeclaring an associated type from an inherited protocol). However, one cannot express more general constraints. Building on the example from “Recursive protocol constraints”, we really want the element type of a Sequence’s SubSequence to be the same as the element type of the Sequence, e.g.,

protocol Sequence {
 associatedtype Iterator : IteratorProtocol
 …
 associatedtype SubSequence : Sequence where SubSequence.Iterator.Element == Iterator.Element
}

Hanging the where clause off the associated type is protocol not ideal, but that’s a discussion for another thread.

*Typealiases in protocols and protocol extensions

Now that associated types have their own keyword (thanks!), it’s reasonable to bring back “typealias”. Again with the Sequence protocol:

protocol Sequence {
 associatedtype Iterator : IteratorProtocol
 typealias Element = Iterator.Element // rejoice! now we can refer to SomeSequence.Element rather than SomeSequence.Iterator.Element
}

Default generic arguments

Generic parameters could be given the ability to provide default arguments, which would be used in cases where the type argument is not specified and type inference could not determine the type argument. For example:

public final class Promise<Value, Reason=Error> { … }

func getRandomPromise() -> Promise<Int, ErrorProtocol> { … }

var p1: Promise<Int> = …
var p2: Promise<Int, Error> = p1 // okay: p1 and p2 have the same type Promise<Int, Error>
var p3: Promise = getRandomPromise() // p3 has type Promise<Int, ErrorProtocol> due to type inference

Generalized “class” constraints

The “class” constraint can currently only be used for defining protocols. We could generalize it to associated type and type parameter declarations, e.g.,

protocol P {
 associatedtype A : class
}

func foo<T : class>(t: T) { }

As part of this, the magical AnyObject protocol could be replaced with an existential with a class bound, so that it becomes a typealias:

typealias AnyObject = protocol<class>

See the “Existentials” section, particularly “Generalized existentials”, for more information.

*Allowing subclasses to override requirements satisfied by defaults

When a superclass conforms to a protocol and has one of the protocol’s requirements satisfied by a member of a protocol extension, that member currently cannot be overridden by a subclass. For example:

protocol P {
 func foo()
}

extension P {
 func foo() { print(“P”) }
}

class C : P {
 // gets the protocol extension’s
}

class D : C {
 /*override not allowed!*/ func foo() { print(“D”) }
}

let p: P = D()
p.foo() // gotcha: prints “P” rather than “D”!

D.foo should be required to specify “override” and should be called dynamically.

Major extensions to the generics model

Unlike the minor extensions, major extensions to the generics model provide more expressivity in the Swift generics system and, generally, have a much more significant design and implementation cost.

*Conditional conformances

Conditional conformances express the notion that a generic type will conform to a particular protocol only under certain circumstances. For example, Array is Equatable only when its elements are Equatable:

extension Array : Equatable where Element : Equatable { }

func ==<T : Equatable>(lhs: Array<T>, rhs: Array<T>) -> Bool { … }

Conditional conformances are a potentially very powerful feature. One important aspect of this feature is how deal with or avoid overlapping conformances. For example, imagine an adaptor over a Sequence that has conditional conformances to Collection and MutableCollection:

struct SequenceAdaptor<S: Sequence> : Sequence { }
extension SequenceAdaptor : Collection where S: Collection { … }
extension SequenceAdaptor : MutableCollection where S: MutableCollection { }

This should almost certainly be permitted, but we need to cope with or reject “overlapping” conformances:

extension SequenceAdaptor : Collection where S: SomeOtherProtocolSimilarToCollection { } // trouble: two ways for SequenceAdaptor to conform to Collection

See the section on “Private conformances” for more about the issues with having the same type conform to the same protocol multiple times.

Variadic generics

Currently, a generic parameter list contains a fixed number of generic parameters. If one has a type that could generalize to any number of generic parameters, the only real way to deal with it today involves creating a set of types. For example, consider the standard library’s “zip” function. It returns one of these when provided with two arguments to zip together:

public struct Zip2Sequence<Sequence1 : Sequence,
 Sequence2 : Sequence> : Sequence { … }

public func zip<Sequence1 : Sequence, Sequence2 : Sequence>(
 sequence1: Sequence1, _ sequence2: Sequence2)
 -> Zip2Sequence<Sequence1, Sequence2> { … }

Supporting three arguments would require copy-paste of those of those:

public struct Zip3Sequence<Sequence1 : Sequence,
 Sequence2 : Sequence,
 Sequence3 : Sequence> : Sequence { … }

public func zip<Sequence1 : Sequence, Sequence2 : Sequence, Sequence3 : Sequence>(
 sequence1: Sequence1, _ sequence2: Sequence2, _ sequence3: sequence3)
 -> Zip3Sequence<Sequence1, Sequence2, Sequence3> { … }

Variadic generics would allow us to abstract over a set of generic parameters. The syntax below is hopelessly influenced by C++11 variadic templates <http://www.jot.fm/issues/issue_2008_02/article2/> (sorry), where putting an ellipsis (“…”) to the left of a declaration makes it a “parameter pack” containing zero or more parameters and putting an ellipsis to the right of a type/expression/etc. expands the parameter packs within that type/expression into separate arguments. The important part is that we be able to meaningfully abstract over zero or more generic parameters, e.g.:

public struct ZipIterator<... Iterators : IteratorProtocol> : Iterator { // zero or more type parameters, each of which conforms to IteratorProtocol
 public typealias Element = (Iterators.Element...) // a tuple containing the element types of each iterator in Iterators

 var (...iterators): (Iterators...) // zero or more stored properties, one for each type in Iterators
 var reachedEnd: Bool = false

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

 guard let values = (iterators.next()...) { // call “next” on each of the iterators, put the results into a tuple named “values"
 reachedEnd = true
 return nil
 }

 return values
 }
}

public struct ZipSequence<...Sequences : Sequence> : Sequence {
 public typealias Iterator = ZipIterator<Sequences.Iterator...> // get the zip iterator with the iterator types of our Sequences

 var (...sequences): (Sequences...) // zero or more stored properties, one for each type in Sequences

 // details ...
}

Such a design could also work for function parameters, so we can pack together multiple function arguments with different types, e.g.,

public func zip<... Sequences : SequenceType>(... sequences: Sequences...)
 -> ZipSequence<Sequences...> {
 return ZipSequence(sequences...)
}

Finally, this could tie into the discussions about a tuple “splat” operator. For example:

func apply<... Args, Result>(fn: (Args...) -> Result, // function taking some number of arguments and producing Result
 args: (Args...)) -> Result { // tuple of arguments
 return fn(args...) // expand the arguments in the tuple “args” into separate arguments
}

Extensions of structural types

Currently, only nominal types (classes, structs, enums, protocols) can be extended. One could imagine extending structural types—particularly tuple types—to allow them to, e.g., conform to protocols. For example, pulling together variadic generics, parameterized extensions, and conditional conformances, one could express “a tuple type is Equatable if all of its element types are Equatable”:

extension<...Elements : Equatable> (Elements...) : Equatable { // extending the tuple type “(Elements…)” to be Equatable
}

There are some natural bounds here: one would need to have actual structural types. One would not be able to extend every type:

extension<T> T { // error: neither a structural nor a nominal type
}

And before you think you’re cleverly making it possible to have a conditional conformance that makes every type T that conforms to protocol P also conform to protocol Q, see the section "Conditional conformances via protocol extensions”, below:

extension<T : P> T : Q { // error: neither a structural nor a nominal type
}

Syntactic improvements

There are a number of potential improvements we could make to the generics syntax. Such a list could go on for a very long time, so I’ll only highlight some obvious ones that have been discussed by the Swift developers.

*Default implementations in protocols

Currently, protocol members can never have implementations. We could allow one to provide such implementations to be used as the default if a conforming type does not supply an implementation, e.g.,

protocol Bag {
 associatedtype Element : Equatable
 func contains(element: Element) -> Bool

 func containsAll<S: Sequence where Sequence.Iterator.Element == Element>(elements: S) -> Bool {
 for x in elements {
 if contains(x) { return true }
 }
 return false
 }
}

struct IntBag : Bag {
 typealias Element = Int
 func contains(element: Int) -> Bool { ... }

 // okay: containsAll requirement is satisfied by Bag’s default implementation
}

One can get this effect with protocol extensions today, hence the classification of this feature as a (mostly) syntactic improvement:

protocol Bag {
 associatedtype Element : Equatable
 func contains(element: Element) -> Bool

 func containsAll<S: Sequence where Sequence.Iterator.Element == Element>(elements: S) -> Bool
}

extension Bag {
 func containsAll<S: Sequence where Sequence.Iterator.Element == Element>(elements: S) -> Bool {
 for x in elements {
 if contains(x) { return true }
 }
 return false
 }
}

*Moving the where clause outside of the angle brackets

The “where” clause of generic functions comes very early in the declaration, although it is generally of much less concern to the client than the function parameters and result type that follow it. This is one of the things that contributes to “angle bracket blindness”. For example, consider the containsAll signature above:

func containsAll<S: Sequence where Sequence.Iterator.Element == Element>(elements: S) -> Bool

One could move the “where” clause to the end of the signature, so that the most important parts—name, generic parameter, parameters, result type—precede it:

func containsAll<S: Sequence>(elements: S) -> Bool
 where Sequence.Iterator.Element == Element

*Renaming “protocol<…>” to “Any<…>”.

The “protocol<…>” syntax is a bit of an oddity in Swift. It is used to compose protocols together, mostly to create values of existential type, e.g.,

var x: protocol<NSCoding, NSCopying>

It’s weird that it’s a type name that starts with a lowercase letter, and most Swift developers probably never deal with this feature unless they happen to look at the definition of Any:

typealias Any = protocol<>

“Any” might be a better name for this functionality. “Any” without brackets could be a keyword for “any type”, and “Any” followed by brackets could take the role of “protocol<>” today:

var x: Any<NSCoding, NSCopying>

That reads much better: “Any type that conforms to NSCoding and NSCopying”. See the section "Generalized existentials” for additional features in this space.

Maybe

There are a number of features that get discussed from time-to-time, while they could fit into Swift’s generics system, it’s not clear that they belong in Swift at all. The important question for any feature in this category is not “can it be done” or “are there cool things we can express”, but “how can everyday Swift developers benefit from the addition of such a feature?”. Without strong motivating examples, none of these “maybes” will move further along.

Dynamic dispatch for members of protocol extensions

Only the requirements of protocols currently use dynamic dispatch, which can lead to surprises:

protocol P {
 func foo()
}

extension P {
 func foo() { print(“P.foo()”)
 func bar() { print(“P.bar()”)
}

struct X : P {
 func foo() { print(“X.foo()”)
 func bar() { print(“X.bar()”)
}

let x = X()
x.foo() // X.foo()
x.bar() // X.bar()

let p: P = X()
p.foo() // X.foo()
p.bar() // P.bar()

Swift could adopt a model where members of protocol extensions are dynamically dispatched.

Named generic parameters

When specifying generic arguments for a generic type, the arguments are always positional: Dictionary<String, Int> is a Dictionary whose Key type is String and whose Value type is Int, by convention. One could permit the arguments to be labeled, e.g.,

var d: Dictionary<Key: String, Value: Int>

Such a feature makes more sense if Swift gains default generic arguments, because generic argument labels would allow one to skip defaulted arguments.

Generic value parameters

Currently, Swift’s generic parameters are always types. One could imagine allowing generic parameters that are values, e.g.,

struct MultiArray<T, let Dimensions: Int> { // specify the number of dimensions to the array
 subscript (indices: Int...) -> T {
 get {
 require(indices.count == Dimensions)
 // ...
 }
}

A suitably general feature might allow us to express fixed-length array or vector types as a standard library component, and perhaps also allow one to implement a useful dimensional analysis library. Tackling this feature potentially means determining what it is for an expression to be a “constant expression” and diving into dependent-typing, hence the “maybe”.

Higher-kinded types

Higher-kinded types allow one to express the relationship between two different specializations of the same nominal type within a protocol. For example, if we think of the Self type in a protocol as really being “Self<T>”, it allows us to talk about the relationship between “Self<T>” and “Self” for some other type U. For example, it could allow the “map” operation on a collection to return a collection of the same kind but with a different operation, e.g.,

let intArray: Array<Int> = …
intArray.map { String($0) } // produces Array<String>
let intSet: Set<Int> = …
intSet.map { String($0) } // produces Set<String>

Potential syntax borrowed from one thread on higher-kinded types <https://lists.swift.org/pipermail/swift-evolution/Week-of-Mon-20151214/002736.html> uses ~= as a “similarity” constraint to describe a Functor protocol:

protocol Functor {
 associatedtype A
 func fmap<FB where FB ~= Self>(f: A -> FB.A) -> FB
}

Specifying type arguments for uses of generic functions

The type arguments of a generic function are always determined via type inference. For example, given:

func f<T>(t: T)

one cannot directly specify T: either one calls “f” (and T is determined via the argument’s type) or one uses “f” in a context where it is given a particular function type (e.g., “let x: (Int) -> Void = f” would infer T = Int). We could permit explicit specialization here, e.g.,

let x = f<Int> // x has type (Int) -> Void

Unlikely

Features in this category have been requested at various times, but they don’t fit well with Swift’s generics system because they cause some part of the model to become overly complicated, have unacceptable implementation limitations, or overlap significantly with existing features.

Generic protocols

One of the most commonly requested features is the ability to parameterize protocols themselves. For example, a protocol that indicates that the Self type can be constructed from some specified type T:

protocol ConstructibleFromValue<T> {
 init(_ value: T)
}

Implicit in this feature is the ability for a given type to conform to the protocol in two different ways. A “Real” type might be constructible from both Float and Double, e.g.,

struct Real { … }
extension Real : ConstructibleFrom<Float> {
 init(_ value: Float) { … }
}
extension Real : ConstructibleFrom<Double> {
 init(_ value: Double) { … }
}

Most of the requests for this feature actually want a different feature. They tend to use a parameterized Sequence as an example, e.g.,

protocol Sequence<Element> { … }

func foo(strings: Sequence<String>) { /// works on any sequence containing Strings
 // ...
}

The actual requested feature here is the ability to say “Any type that conforms to Sequence whose Element type is String”, which is covered by the section on “Generalized existentials”, below.

More importantly, modeling Sequence with generic parameters rather than associated types is tantalizing but wrong: you don’t want a type conforming to Sequence in multiple ways, or (among other things) your for..in loops stop working, and you lose the ability to dynamically cast down to an existential “Sequence” without binding the Element type (again, see “Generalized existentials”). Use cases similar to the ConstructibleFromValue protocol above seem too few to justify the potential for confusion between associated types and generic parameters of protocols; we’re better off not having the latter.

Private conformances

Right now, a protocol conformance can be no less visible than the minimum of the conforming type’s access and the protocol’s access. Therefore, a public type conforming to a public protocol must provide the conformance publicly. One could imagine removing that restriction, so that one could introduce a private conformance:

public protocol P { }
public struct X { }
extension X : internal P { … } // X conforms to P, but only within this module

The main problem with private conformances is the interaction with dynamic casting. If I have this code:

func foo(value: Any) {
 if let x = value as? P { print(“P”) }
}

foo(X())

Under what circumstances should it print “P”? If foo() is defined within the same module as the conformance of X to P? If the call is defined within the same module as the conformance of X to P? Never? Either of the first two answers requires significant complications in the dynamic casting infrastructure to take into account the module in which a particular dynamic cast occurred (the first option) or where an existential was formed (the second option), while the third answer breaks the link between the static and dynamic type systems—none of which is an acceptable result.

Conditional conformances via protocol extensions

We often get requests to make a protocol conform to another protocol. This is, effectively, the expansion of the notion of “Conditional conformances” to protocol extensions. For example:

protocol P {
 func foo()
}

protocol Q {
 func bar()
}

extension Q : P { // every type that conforms to Q also conforms to P
 func foo() { // implement “foo” requirement in terms of “bar"
 bar()
 }
}

func f<T: P>(t: T) { … }

struct X : Q {
 func bar() { … }
}

f(X()) // okay: X conforms to P through the conformance of Q to P

This is an extremely powerful feature: is allows one to map the abstractions of one domain into another domain (e.g., every Matrix is a Graph). However, similar to private conformances, it puts a major burden on the dynamic-casting runtime to chase down arbitrarily long and potentially cyclic chains of conformances, which makes efficient implementation nearly impossible.

Potential removals

The generics system doesn’t seem like a good candidate for a reduction in scope; most of its features do get used fairly pervasively in the standard library, and few feel overly anachronistic. However...

Associated type inference

Associated type inference is the process by which we infer the type bindings for associated types from other requirements. For example:

protocol IteratorProtocol {
 associatedtype Element
 mutating func next() -> Element?
}

struct IntIterator : IteratorProtocol {
 mutating func next() -> Int? { … } // use this to infer Element = Int
}

Associated type inference is a useful feature. It’s used throughout the standard library, and it helps keep associated types less visible to types that simply want to conform to a protocol. On the other hand, associated type inference is the only place in Swift where we have a global type inference problem: it has historically been a major source of bugs, and implementing it fully and correctly requires a drastically different architecture to the type checker. Is the value of this feature worth keeping global type inference in the Swift language, when we have deliberatively avoided global type inference elsewhere in the language?

Existentials

Existentials aren’t really generics per se, but the two systems are closely intertwined due to their mutable dependence on protocols.

*Generalized existentials

The restrictions on existential types came from an implementation limitation, but it is reasonable to allow a value of protocol type even when the protocol has Self constraints or associated types. For example, consider IteratorProtocol again and how it could be used as an existential:

protocol IteratorProtocol {
 associatedtype Element
 mutating func next() -> Element?
}

let it: IteratorProtocol = …
it.next() // if this is permitted, it could return an “Any?”, i.e., the existential that wraps the actual element

Additionally, it is reasonable to want to constrain the associated types of an existential, e.g., “a Sequence whose element type is String” could be expressed by putting a where clause into “protocol<…>” or “Any<…>” (per “Renaming protocol<…> to Any<…>”):

let strings: Any<Sequence where .Iterator.Element == String> = [“a”, “b”, “c”]

The leading “.” indicates that we’re talking about the dynamic type, i.e., the “Self” type that’s conforming to the Sequence protocol. There’s no reason why we cannot support arbitrary “where” clauses within the “Any<…>”. This very-general syntax is a bit unwieldy, but common cases can easily be wrapped up in a generic typealias (see the section “Generic typealiases” above):

typealias AnySequence<Element> = Any<Sequence where .Iterator.Element == Element>
let strings: AnySequence<String> = [“a”, “b”, “c”]

Opening existentials

Generalized existentials as described above will still have trouble with protocol requirements that involve Self or associated types in function parameters. For example, let’s try to use Equatable as an existential:

protocol Equatable {
 func ==(lhs: Self, rhs: Self) -> Bool
 func !=(lhs: Self, rhs: Self) -> Bool
}

let e1: Equatable = …
let e2: Equatable = …
if e1 == e2 { … } // error: e1 and e2 don’t necessarily have the same dynamic type

One explicit way to allow such operations in a type-safe manner is to introduce an “open existential” operation of some sort, which extracts and gives a name to the dynamic type stored inside an existential. For example:

if let storedInE1 = e1 openas T { // T is a the type of storedInE1, a copy of the value stored in e1
 if let storedInE2 = e2 as? T { // is e2 also a T?
 if storedInE1 == storedInE2 { … } // okay: storedInT1 and storedInE2 are both of type T, which we know is Equatable
 }
}

Thoughts?

 - Doug

Joe_Groff · March 3, 2016, 5:15am

Though definitely a "power" feature that should be used sparingly, I think there are legitimate use cases for universal conformances. If nothing else, the language imposes de-facto universal members on things, including T.Type and x.dynamicType, and it would be nice if those could be implemented in the standard library and given back as reserved words.

-Joe

···

On Mar 2, 2016, at 5:22 PM, Douglas Gregor via swift-evolution <swift-evolution@swift.org> wrote:
There are some natural bounds here: one would need to have actual structural types. One would not be able to extend every type:

extension<T> T { // error: neither a structural nor a nominal type
}

And before you think you’re cleverly making it possible to have a conditional conformance that makes every type T that conforms to protocol P also conform to protocol Q, see the section "Conditional conformances via protocol extensions”, below:

extension<T : P> T : Q { // error: neither a structural nor a nominal type
}

Slava_Pestov · March 3, 2016, 5:24am

Hi Doug,

I’m really happy to see this written up. I’m wondering if adding a bit more detail on some of the bigger items would help scope the work.

Nested generics

Currently, a generic type cannot be nested within another generic type, e.g.

struct X<T> {
struct Y { } // currently ill-formed, but should be possible
}

There isn’t much to say about this: the compiler simply needs to be improved to handle nested generics throughout.

Yes! :-)

For nested generic functions, the only limitation today is that nested functions cannot capture values from an outer scope if they also have a generic signature of their own. I have some patches implementing this but I haven’t had a chance to work on them for a while.

Nested generic types require some runtime support but I believe Sema mostly models them correctly — we recently fixed a lot of compiler crashes related to this. Shouldn’t be too much work to get both of these into Swift 3 :)

However there are a crazier things we should figure out:

a) Generic types nested inside generic functions have been a source of compiler_crashers because the inner generic signature has more primary parameters than the bound generic type, due to “captures". For example, if you have something like:

func foo<T>() {
 struct S {
 let p: (T, U)
 }
}

The metatype for S should also “capture” the type parameter T. In particular it seems that invocations of foo() with different concrete types bound to T will produce distinct S types. Sema doesn’t really model this well right now, I think — it just has some hacks to avoid crashing. Also I wonder what this means if S conforms to a protocol. There might be representational issues with the conformance in the runtime, or at least the captured type has to be stashed somewhere.

b) There’s also the case of types nested inside protocols. Do we ever want to allow this (my opinion is ’no’), and if so, what does it mean exactly?

protocol Collection {
associatedtype ElementType

  struct Iterator {
    let e: ElementType
  }
}

c) Protocols nested inside functions and other types should probably never be allowed. There might be some latent crashes because of Sema assumptions that the Self type is at depth 0, or cases where diagnostics are not emitted.

Concrete same-type requirements

Currently, a constrained extension cannot use a same-type constraint to make a type parameter equivalent to a concrete type. For example:

extension Array where Element == String {
 func makeSentence() -> String {
 // uppercase first string, concatenate with spaces, add a period, whatever
 }
}

This is a highly-requested feature that fits into the existing syntax and semantics. Note that one could imagine introducing new syntax, e.g., extending “Array<String>”, which gets into new-feature territory: see the section on “Parameterized extensions”.

Do we already support same-type constraints between two primary generic parameters or should this be added in as well?

*Typealiases in protocols and protocol extensions

Now that associated types have their own keyword (thanks!), it’s reasonable to bring back “typealias”. Again with the Sequence protocol:

protocol Sequence {
associatedtype Iterator : IteratorProtocol
typealias Element = Iterator.Element // rejoice! now we can refer to SomeSequence.Element rather than SomeSequence.Iterator.Element
}

If we decide to pass ‘Element’ as a top-level metadata parameter, this could be used an optimization hint, and would also have resilience implications.

Conditional conformances are a potentially very powerful feature. One important aspect of this feature is how deal with or avoid overlapping conformances. For example, imagine an adaptor over a Sequence that has conditional conformances to Collection and MutableCollection:

Would it be enough to prohibit defining multiple conditional conformances to the same protocol for the same base type but with different ‘where’ clauses?

public struct ZipIterator<... Iterators : IteratorProtocol> : Iterator { // zero or more type parameters, each of which conforms to IteratorProtocol

Would this make sense too:

struct ZipIterator<… Iterators where Iterators : IteratorProtocol>

I’m wondering if we can replace current varargs with a desugaring along the lines of:

func vararg(let a: A…) {

}

func vararg<… T where T == A>(let a: (T…)) { … }

Currently, varargs have a static number of arguments at the call site — instead of constructing an array, they could be passed as a tuple value, which would presumably be stack allocated at the call site. Together with a runtime entry point to get tuple metadata from a single element type repeated N times, this might be more efficient than varargs are now, where as far as I understand the array is allocated on the heap by the caller.

There are some natural bounds here: one would need to have actual structural types. One would not be able to extend every type:

extension<T> T { // error: neither a structural nor a nominal type
}

Extending Any or AnyObject doesn’t seem too far-fetched, though, and almost feels like an artificial restriction at this point. Has nobody ever wanted this?

And before you think you’re cleverly making it possible to have a conditional conformance that makes every type T that conforms to protocol P also conform to protocol Q, see the section "Conditional conformances via protocol extensions”, below:

What about self-conforming protocols? I’m willing to bet most people don’t use static methods in protocols, so it seems unnatural that a protocol type cannot be bound to a generic parameter constrained to that protocol type. Today on Twitter we had someone doing something like this:

protocol BaseProto {}
protocol RefinedProto : BaseProto {}

func doStuff<T : BaseProto>(let a: [T]) {}

getRefined() -> [RefinedProto]

doStuff(getRefined()) // doesn’t type check!

Of course the underlying reason is that BaseProto does not conform to _itself_, which has nothing to do with RefinedProto.

There are tricky representational issues with self-conforming protocols, especially class-constrained ones — we expect an instance of a class-constrained generic parameter to be a single retainable pointer, which is not the case if it is an existential with an associated witness table. But if we can figure this out, it would smooth over a sharp edge in the language that confuses people who are not intimately familiar with how existential types are represented (ie, everybody except for us :) ).

This is different from opening existentials, because here we’re binding T to RefinedProto and cannot simultaneously open everything in the array…

Specifying type arguments for uses of generic functions

The type arguments of a generic function are always determined via type inference. For example, given:

func f<T>(t: T)

one cannot directly specify T: either one calls “f” (and T is determined via the argument’s type) or one uses “f” in a context where it is given a particular function type (e.g., “let x: (Int) -> Void = f” would infer T = Int). We could permit explicit specialization here, e.g.,

let x = f<Int> // x has type (Int) -> Void

Are higher-kinded function values worth discussing too?

if let storedInE1 = e1 openas T { // T is a the type of storedInE1, a copy of the value stored in e1
  if let storedInE2 = e2 as? T { // is e2 also a T?
    if storedInE1 == storedInE2 { … } // okay: storedInT1 and storedInE2 are both of type T, which we know is Equatable
  }
}

I’m worried that this is not really correct with inheritance. If e1 is an instance of SubClass, and e2 is an instance of SuperClass with SubClass : SuperClass, then your operation is no longer symmetric. Heterogeneous equality just seems like a pain in general.

Slava

···

On Mar 2, 2016, at 5:22 PM, Douglas Gregor via swift-evolution <swift-evolution@swift.org> wrote:

codafi · March 3, 2016, 3:57am

Existentials

Opening existentials

Generalized existentials as described above will still have trouble with protocol requirements that involve Self or associated types in function parameters. For example, let’s try to use Equatable as an existential:

protocol Equatable {
  func ==(lhs: Self, rhs: Self) -> Bool
  func !=(lhs: Self, rhs: Self) -> Bool
}

let e1: Equatable = …
let e2: Equatable = …
if e1 == e2 { … } // error: e1 and e2 don’t necessarily have the same dynamic type

One explicit way to allow such operations in a type-safe manner is to introduce an “open existential” operation of some sort, which extracts and gives a name to the dynamic type stored inside an existential. For example:

if let storedInE1 = e1 openas T { // T is a the type of storedInE1, a copy of the value stored in e1
  if let storedInE2 = e2 as? T { // is e2 also a T?
    if storedInE1 == storedInE2 { … } // okay: storedInT1 and storedInE2 are both of type T, which we know is Equatable
  }
}

Isn't "open existential" code for "casting ∃ to ∀"? Dispatch on the underlying type is brittle and anti-modular. I should know, I tried to recover GADTs under the old system! I shudder to think of what further horrors I could concoct with this pattern formalized in the language.

~ Robert Widmann

plx · March 3, 2016, 1:47pm

Thanks for publishing the manifesto; for the most part everything seems reasonable and logical extensions that would “complete" the current system.

I do have a few remarks and I’m going to put them each in a separate email (they don’t relate to each other).

# Comment: Variadic Generics “Need” Structural Union Types

Disclaimer: I’m not 100% sure on the terminology; I’m using “structural union” here to mean an “anonymous enum” (like “A | B | C | D”) wherein both (a) the order matters (e.g. `(A | B | C | D)` and `(D | C | B | A)` are different types) and also (b) types can repeated (e.g. `(Int | Int | Int)` exists and isn’t just `Int`). If that’s not a "structural union” I apologize for the inappropriate terminology.

Content: I think variadic generics will wind up being rather limited in their utility w/out a correspondingly-variadic form of “structural union”; the reason is that for many type-combinators the right representation for some of the resulting associated types is a sum.

Here’s a motivating example: a read-only collection acts as the concatenation of its `n` input collections. Today this requires a family of types (one per `n` you wish to support) and would superficially seem like a good place to use variadic generics...but it’s not so straightforward:

// non-variadic version:
struct ChainCollection3<A:Collection,B:Collection,C:Collection> : Collection {
 let a = A
 let b = B
 let c = C
}

enum ChainCollection3Index<A:Collection,B:Collection,C:Collection> : ForwardIndex {
 case IndexA(A.Index) // <- can’t be just `A` due to name collision!
 case IndexB(B.Index) //
 case IndexC(C.Index) //
}

// showing the index in use:
extension ChainCollection3 {

associatedtype Index = ChainCollection3Index<A,B,C>

var startIndex: Index { return .IndexA(a.startIndex) }
var endIndex: Index { return .IndexC(c.endIndex) }

  // the below isn’t actually correct b/c it doesn’t
  // properly handle the case when one of the constituent
  // collections is empty…also assuming collections-move-indices:
  func successorFor(index: Index) -> Index {
    switch (index) {
      case let .IndexA(aIndex):
        return aIndex == a.endIndex ? .IndexB(b.startIndex) : .IndexA(a.successorFor(aIndex))
      case let .IndexB(bIndex):
        return bIndex == b.endIndex ? .IndexC(c.startIndex) : .IndexB(b.successorFor(bIndex))
      case let .IndexC(cIndex):
        precondition(cIndex != c.endIndex)
        return .IndexC(c.successorFor(cIndex))
    }
  }

// and so on, mostly obvious boilerplate

}

…and although a good variadic generics system could eliminate the need for the family like ChainCollection*, it’s hard to see how you could implement an `Index` type in the variadic setting—without which you are “capped” at the `Sequence` level—w/out also having *variadic* structural unions (I think the best you could *maybe* do is manually implement the equivalent of that enum as e.g. a managed buffer with a type tag and a lot of casting, but you wouldn’t *want* to do that...).

Perhaps I’m missing a trick here, but if I’m not it does seem like the lack of variadic structural unions places a pretty low ceiling on what you could build using variadic generics.

plx · March 3, 2016, 2:04pm

# Missing Idea: Protocols Restricted to Specific Classes

This has come up on the list somewhat often (cf the current abstract class thread).

The idea is being able to write the below:

// expectation is we are defining a protocol that can only be adopted by classes
// that are subclasses of `UIViewController`
protocol SpecializedViewController : UIViewController {
}

…the absence of which is something that *can* be worked-around today, but it’d be nice not to have to work around it (or to have it added to the “unlikely” category if there’s a deep reason this isn’t feasible).

Also, it’s possible that this *may* be addressed already (e.g. perhaps this is implicit in “generic typealiases”?).

plx · March 3, 2016, 2:14pm

# Missing Idea: "Type Predicates”

This is another way of attacking the “where clauses get too long” problem; it may already be implicitly part of “generic typealiases”.

Consider being able to write a declaration like this:

protocol SpecializedContainer {

  associatedtype Element: Comparable

  // potential declaration:
  typepredicate Compatible(S:SequenceType) = S.Generator.Element == Element

// potential use syntaxes (tbd):
 func insertContentsOf<S:SequenceType where Compatible(S)>(elements: S)
 func insertContentsOf<Compatible(S)>(elements: S) // <- potential shorthand

}

…which isn’t the strongest motivating example on its own, but if you start to consider use cases where we will wind up having longer “where” clauses (and I think we will, over time) it may start paying its own way.

This probably falls under “minor feature” (and if added I’d hope the implementation picks a simple semantics for it), but something along these lines may do a decent job of addressing some of the same issues that motivate request to be able to write `Sequence<T>`.

Haravikk3 · March 3, 2016, 8:34am

Nested generic types are definitely a big +1 from me. In particular if I can use them to fulfil associated type requirements, for example:

  protocol FooType {
    typealias Element
    typealias Index
  }

struct Foo<E> : FooType {
 typealias Element = E
 struct Index { … }
 }

The other thing I’d like to see for generics isn’t really a new feature, but I’d like to be able to define protocol generics in the same format as for types, i.e- I could rewrite the above protocol as:

protocol FooType<Element, Index> {}

Likewise when placing constraints on methods etc.:

func myMethod(someFoo:FooType<String, Int>) { … }

Even if behind the scenes these are still unwrapped into associated types and where clauses, it’s just much, much easier to work with in the majority of cases (where clauses would still exist for the more complex ones).

The other capabilities you’ve described all seem very useful, but it’s probably going to take a day or two to get my head around all of them!

···

On 3 Mar 2016, at 01:22, Douglas Gregor via swift-evolution <swift-evolution@swift.org> wrote:

Hi all,

Introduction

The “Complete Generics” goal for Swift 3 has been fairly ill-defined thus fair, with just this short blurb in the list of goals:

Complete generics: Generics are used pervasively in a number of Swift libraries, especially the standard library. However, there are a number of generics features the standard library requires to fully realize its vision, including recursive protocol constraints, the ability to make a constrained extension conform to a new protocol (i.e., an array of Equatable elements is Equatable), and so on. Swift 3.0 should provide those generics features needed by the standard library, because they affect the standard library's ABI.
This message expands upon the notion of “completing generics”. It is not a plan for Swift 3, nor an official core team communication, but it collects the results of numerous discussions among the core team and Swift developers, both of the compiler and the standard library. I hope to achieve several things:

Communicate a vision for Swift generics, building on the original generics design document <https://github.com/apple/swift/blob/master/docs/Generics.rst>, so we have something concrete and comprehensive to discuss.
Establish some terminology that the Swift developers have been using for these features, so our discussions can be more productive (“oh, you’re proposing what we refer to as ‘conditional conformances’; go look over at this thread”).
Engage more of the community in discussions of specific generics features, so we can coalesce around designs for public review. And maybe even get some of them implemented.

A message like this can easily turn into a centithread <Urban Dictionary: centithread. To separate concerns in our discussion, I ask that replies to this specific thread be limited to discussions of the vision as a whole: how the pieces fit together, what pieces are missing, whether this is the right long-term vision for Swift, and so on. For discussions of specific language features, e.g., to work out the syntax and semantics of conditional conformances or discuss the implementation in compiler or use in the standard library, please start a new thread based on the feature names I’m using.

This message covers a lot of ground; I’ve attempted a rough categorization of the various features, and kept the descriptions brief to limit the overall length. Most of these aren’t my ideas, and any syntax I’m providing is simply a way to express these ideas in code and is subject to change. Not all of these features will happen, either soon or ever, but they are intended to be a fairly complete whole that should mesh together. I’ve put a * next to features that I think are important in the nearer term vs. being interesting “some day”. Mostly, the *’s reflect features that will have a significant impact on the Swift standard library’s design and implementation.

Enough with the disclaimers; it’s time to talk features.

Removing unnecessary restrictions

There are a number of restrictions to the use of generics that fall out of the implementation in the Swift compiler. Removal of these restrictions is a matter of implementation only; one need not introduce new syntax or semantics to realize them. I’m listing them for two reasons: first, it’s an acknowledgment that these features are intended to exist in the model we have today, and, second, we’d love help with the implementation of these features.

*Recursive protocol constraints

Currently, an associated type cannot be required to conform to its enclosing protocol (or any protocol that inherits that protocol). For example, in the standard library SubSequence type of a Sequence should itself be a Sequence:

protocol Sequence {
 associatedtype Iterator : IteratorProtocol
 …
 associatedtype SubSequence : Sequence // currently ill-formed, but should be possible
}

The compiler currently rejects this protocol, which is unfortunate: it effectively pushes the SubSequence-must-be-a-Sequence requirement into every consumer of SubSequence, and does not communicate the intent of this abstraction well.

Nested generics

Currently, a generic type cannot be nested within another generic type, e.g.

struct X<T> {
 struct Y { } // currently ill-formed, but should be possible
}

There isn’t much to say about this: the compiler simply needs to be improved to handle nested generics throughout.

Concrete same-type requirements

Currently, a constrained extension cannot use a same-type constraint to make a type parameter equivalent to a concrete type. For example:

extension Array where Element == String {
 func makeSentence() -> String {
 // uppercase first string, concatenate with spaces, add a period, whatever
 }
}

This is a highly-requested feature that fits into the existing syntax and semantics. Note that one could imagine introducing new syntax, e.g., extending “Array<String>”, which gets into new-feature territory: see the section on “Parameterized extensions”.

Parameterizing other declarations

There are a number of Swift declarations that currently cannot have generic parameters; some of those have fairly natural extensions to generic forms that maintain their current syntax and semantics, but become more powerful when made generic.

Generic typealiases

Typealiases could be allowed to carry generic parameters. They would still be aliases (i.e., they would not introduce new types). For example:

typealias StringDictionary<Value> = Dictionary<String, Value>

var d1 = StringDictionary<Int>()
var d2: Dictionary<String, Int> = d1 // okay: d1 and d2 have the same type, Dictionary<String, Int>

Generic subscripts

Subscripts could be allowed to have generic parameters. For example, we could introduce a generic subscript on a Collection that allows us to pull out the values at an arbitrary set of indices:

extension Collection {
 subscript<Indices: Sequence where Indices.Iterator.Element == Index>(indices: Indices) -> [Iterator.Element] {
 get {
 var result = [Iterator.Element]()
 for index in indices {
 result.append(self[index])
 }

 return result
 }

 set {
 for (index, value) in zip(indices, newValue) {
 self[index] = value
 }
 }
 }
}

Generic constants

let constants could be allowed to have generic parameters, such that they produce differently-typed values depending on how they are used. For example, this is particularly useful for named literal values, e.g.,

let π<T : FloatLiteralConvertible>: T = 3.141592653589793238462643383279502884197169399

The Clang importer could make particularly good use of this when importing macros.

Parameterized extensions

Extensions themselves could be parameterized, which would allow some structural pattern matching on types. For example, this would permit one to extend an array of optional values, e.g.,

extension<T> Array where Element == T? {
 var someValues: [T] {
 var result = [T]()
 for opt in self {
 if let value = opt { result.append(value) }
 }
 return result
 }
}

We can generalize this to a protocol extensions:

extension<T> Sequence where Element == T? {
 var someValues: [T] {
 var result = [T]()
 for opt in self {
 if let value = opt { result.append(value) }
 }
 return result
 }
}

Note that when one is extending nominal types, we could simplify the syntax somewhat to make the same-type constraint implicit in the syntax:

extension<T> Array<T?> {
 var someValues: [T] {
 var result = [T]()
 for opt in self {
 if let value = opt { result.append(value) }
 }
 return result
 }
}

When we’re working with concrete types, we can use that syntax to improve the extension of concrete versions of generic types (per “Concrete same-type requirements”, above), e.g.,

extension Array<String> {
 func makeSentence() -> String {
 // uppercase first string, concatenate with spaces, add a period, whatever
 }
}

Minor extensions

There are a number of minor extensions we can make to the generics system that don’t fundamentally change what one can express in Swift, but which can improve its expressivity.

*Arbitrary requirements in protocols

Currently, a new protocol can inherit from other protocols, introduce new associated types, and add new conformance constraints to associated types (by redeclaring an associated type from an inherited protocol). However, one cannot express more general constraints. Building on the example from “Recursive protocol constraints”, we really want the element type of a Sequence’s SubSequence to be the same as the element type of the Sequence, e.g.,

protocol Sequence {
 associatedtype Iterator : IteratorProtocol
 …
 associatedtype SubSequence : Sequence where SubSequence.Iterator.Element == Iterator.Element
}

Hanging the where clause off the associated type is protocol not ideal, but that’s a discussion for another thread.

*Typealiases in protocols and protocol extensions

Now that associated types have their own keyword (thanks!), it’s reasonable to bring back “typealias”. Again with the Sequence protocol:

protocol Sequence {
 associatedtype Iterator : IteratorProtocol
 typealias Element = Iterator.Element // rejoice! now we can refer to SomeSequence.Element rather than SomeSequence.Iterator.Element
}

Default generic arguments

Generic parameters could be given the ability to provide default arguments, which would be used in cases where the type argument is not specified and type inference could not determine the type argument. For example:

public final class Promise<Value, Reason=Error> { … }

func getRandomPromise() -> Promise<Int, ErrorProtocol> { … }

var p1: Promise<Int> = …
var p2: Promise<Int, Error> = p1 // okay: p1 and p2 have the same type Promise<Int, Error>
var p3: Promise = getRandomPromise() // p3 has type Promise<Int, ErrorProtocol> due to type inference

Generalized “class” constraints

The “class” constraint can currently only be used for defining protocols. We could generalize it to associated type and type parameter declarations, e.g.,

protocol P {
 associatedtype A : class
}

func foo<T : class>(t: T) { }

As part of this, the magical AnyObject protocol could be replaced with an existential with a class bound, so that it becomes a typealias:

typealias AnyObject = protocol<class>

See the “Existentials” section, particularly “Generalized existentials”, for more information.

*Allowing subclasses to override requirements satisfied by defaults

When a superclass conforms to a protocol and has one of the protocol’s requirements satisfied by a member of a protocol extension, that member currently cannot be overridden by a subclass. For example:

protocol P {
 func foo()
}

extension P {
 func foo() { print(“P”) }
}

class C : P {
 // gets the protocol extension’s
}

class D : C {
 /*override not allowed!*/ func foo() { print(“D”) }
}

let p: P = D()
p.foo() // gotcha: prints “P” rather than “D”!

D.foo should be required to specify “override” and should be called dynamically.

Major extensions to the generics model

Unlike the minor extensions, major extensions to the generics model provide more expressivity in the Swift generics system and, generally, have a much more significant design and implementation cost.

*Conditional conformances

Conditional conformances express the notion that a generic type will conform to a particular protocol only under certain circumstances. For example, Array is Equatable only when its elements are Equatable:

extension Array : Equatable where Element : Equatable { }

func ==<T : Equatable>(lhs: Array<T>, rhs: Array<T>) -> Bool { … }

Conditional conformances are a potentially very powerful feature. One important aspect of this feature is how deal with or avoid overlapping conformances. For example, imagine an adaptor over a Sequence that has conditional conformances to Collection and MutableCollection:

struct SequenceAdaptor<S: Sequence> : Sequence { }
extension SequenceAdaptor : Collection where S: Collection { … }
extension SequenceAdaptor : MutableCollection where S: MutableCollection { }

This should almost certainly be permitted, but we need to cope with or reject “overlapping” conformances:

extension SequenceAdaptor : Collection where S: SomeOtherProtocolSimilarToCollection { } // trouble: two ways for SequenceAdaptor to conform to Collection

See the section on “Private conformances” for more about the issues with having the same type conform to the same protocol multiple times.

Variadic generics

Currently, a generic parameter list contains a fixed number of generic parameters. If one has a type that could generalize to any number of generic parameters, the only real way to deal with it today involves creating a set of types. For example, consider the standard library’s “zip” function. It returns one of these when provided with two arguments to zip together:

public struct Zip2Sequence<Sequence1 : Sequence,
 Sequence2 : Sequence> : Sequence { … }

public func zip<Sequence1 : Sequence, Sequence2 : Sequence>(
 sequence1: Sequence1, _ sequence2: Sequence2)
 -> Zip2Sequence<Sequence1, Sequence2> { … }

Supporting three arguments would require copy-paste of those of those:

public struct Zip3Sequence<Sequence1 : Sequence,
 Sequence2 : Sequence,
 Sequence3 : Sequence> : Sequence { … }

public func zip<Sequence1 : Sequence, Sequence2 : Sequence, Sequence3 : Sequence>(
 sequence1: Sequence1, _ sequence2: Sequence2, _ sequence3: sequence3)
 -> Zip3Sequence<Sequence1, Sequence2, Sequence3> { … }

Variadic generics would allow us to abstract over a set of generic parameters. The syntax below is hopelessly influenced by C++11 variadic templates <http://www.jot.fm/issues/issue_2008_02/article2/> (sorry), where putting an ellipsis (“…”) to the left of a declaration makes it a “parameter pack” containing zero or more parameters and putting an ellipsis to the right of a type/expression/etc. expands the parameter packs within that type/expression into separate arguments. The important part is that we be able to meaningfully abstract over zero or more generic parameters, e.g.:

public struct ZipIterator<... Iterators : IteratorProtocol> : Iterator { // zero or more type parameters, each of which conforms to IteratorProtocol
 public typealias Element = (Iterators.Element...) // a tuple containing the element types of each iterator in Iterators

 var (...iterators): (Iterators...) // zero or more stored properties, one for each type in Iterators
 var reachedEnd: Bool = false

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

 guard let values = (iterators.next()...) { // call “next” on each of the iterators, put the results into a tuple named “values"
 reachedEnd = true
 return nil
 }

 return values
 }
}

public struct ZipSequence<...Sequences : Sequence> : Sequence {
 public typealias Iterator = ZipIterator<Sequences.Iterator...> // get the zip iterator with the iterator types of our Sequences

 var (...sequences): (Sequences...) // zero or more stored properties, one for each type in Sequences

 // details ...
}

Such a design could also work for function parameters, so we can pack together multiple function arguments with different types, e.g.,

public func zip<... Sequences : SequenceType>(... sequences: Sequences...)
 -> ZipSequence<Sequences...> {
 return ZipSequence(sequences...)
}

Finally, this could tie into the discussions about a tuple “splat” operator. For example:

func apply<... Args, Result>(fn: (Args...) -> Result, // function taking some number of arguments and producing Result
 args: (Args...)) -> Result { // tuple of arguments
 return fn(args...) // expand the arguments in the tuple “args” into separate arguments
}

Extensions of structural types

Currently, only nominal types (classes, structs, enums, protocols) can be extended. One could imagine extending structural types—particularly tuple types—to allow them to, e.g., conform to protocols. For example, pulling together variadic generics, parameterized extensions, and conditional conformances, one could express “a tuple type is Equatable if all of its element types are Equatable”:

extension<...Elements : Equatable> (Elements...) : Equatable { // extending the tuple type “(Elements…)” to be Equatable
}

There are some natural bounds here: one would need to have actual structural types. One would not be able to extend every type:

extension<T> T { // error: neither a structural nor a nominal type
}

And before you think you’re cleverly making it possible to have a conditional conformance that makes every type T that conforms to protocol P also conform to protocol Q, see the section "Conditional conformances via protocol extensions”, below:

extension<T : P> T : Q { // error: neither a structural nor a nominal type
}

Syntactic improvements

There are a number of potential improvements we could make to the generics syntax. Such a list could go on for a very long time, so I’ll only highlight some obvious ones that have been discussed by the Swift developers.

*Default implementations in protocols

Currently, protocol members can never have implementations. We could allow one to provide such implementations to be used as the default if a conforming type does not supply an implementation, e.g.,

protocol Bag {
 associatedtype Element : Equatable
 func contains(element: Element) -> Bool

 func containsAll<S: Sequence where Sequence.Iterator.Element == Element>(elements: S) -> Bool {
 for x in elements {
 if contains(x) { return true }
 }
 return false
 }
}

struct IntBag : Bag {
 typealias Element = Int
 func contains(element: Int) -> Bool { ... }

 // okay: containsAll requirement is satisfied by Bag’s default implementation
}

One can get this effect with protocol extensions today, hence the classification of this feature as a (mostly) syntactic improvement:

protocol Bag {
 associatedtype Element : Equatable
 func contains(element: Element) -> Bool

 func containsAll<S: Sequence where Sequence.Iterator.Element == Element>(elements: S) -> Bool
}

extension Bag {
 func containsAll<S: Sequence where Sequence.Iterator.Element == Element>(elements: S) -> Bool {
 for x in elements {
 if contains(x) { return true }
 }
 return false
 }
}

*Moving the where clause outside of the angle brackets

The “where” clause of generic functions comes very early in the declaration, although it is generally of much less concern to the client than the function parameters and result type that follow it. This is one of the things that contributes to “angle bracket blindness”. For example, consider the containsAll signature above:

func containsAll<S: Sequence where Sequence.Iterator.Element == Element>(elements: S) -> Bool

One could move the “where” clause to the end of the signature, so that the most important parts—name, generic parameter, parameters, result type—precede it:

func containsAll<S: Sequence>(elements: S) -> Bool
 where Sequence.Iterator.Element == Element

*Renaming “protocol<…>” to “Any<…>”.

The “protocol<…>” syntax is a bit of an oddity in Swift. It is used to compose protocols together, mostly to create values of existential type, e.g.,

var x: protocol<NSCoding, NSCopying>

It’s weird that it’s a type name that starts with a lowercase letter, and most Swift developers probably never deal with this feature unless they happen to look at the definition of Any:

typealias Any = protocol<>

“Any” might be a better name for this functionality. “Any” without brackets could be a keyword for “any type”, and “Any” followed by brackets could take the role of “protocol<>” today:

var x: Any<NSCoding, NSCopying>

That reads much better: “Any type that conforms to NSCoding and NSCopying”. See the section "Generalized existentials” for additional features in this space.

Maybe

There are a number of features that get discussed from time-to-time, while they could fit into Swift’s generics system, it’s not clear that they belong in Swift at all. The important question for any feature in this category is not “can it be done” or “are there cool things we can express”, but “how can everyday Swift developers benefit from the addition of such a feature?”. Without strong motivating examples, none of these “maybes” will move further along.

Dynamic dispatch for members of protocol extensions

Only the requirements of protocols currently use dynamic dispatch, which can lead to surprises:

protocol P {
 func foo()
}

extension P {
 func foo() { print(“P.foo()”)
 func bar() { print(“P.bar()”)
}

struct X : P {
 func foo() { print(“X.foo()”)
 func bar() { print(“X.bar()”)
}

let x = X()
x.foo() // X.foo()
x.bar() // X.bar()

let p: P = X()
p.foo() // X.foo()
p.bar() // P.bar()

Swift could adopt a model where members of protocol extensions are dynamically dispatched.

Named generic parameters

When specifying generic arguments for a generic type, the arguments are always positional: Dictionary<String, Int> is a Dictionary whose Key type is String and whose Value type is Int, by convention. One could permit the arguments to be labeled, e.g.,

var d: Dictionary<Key: String, Value: Int>

Such a feature makes more sense if Swift gains default generic arguments, because generic argument labels would allow one to skip defaulted arguments.

Generic value parameters

Currently, Swift’s generic parameters are always types. One could imagine allowing generic parameters that are values, e.g.,

struct MultiArray<T, let Dimensions: Int> { // specify the number of dimensions to the array
 subscript (indices: Int...) -> T {
 get {
 require(indices.count == Dimensions)
 // ...
 }
}

A suitably general feature might allow us to express fixed-length array or vector types as a standard library component, and perhaps also allow one to implement a useful dimensional analysis library. Tackling this feature potentially means determining what it is for an expression to be a “constant expression” and diving into dependent-typing, hence the “maybe”.

Higher-kinded types

Higher-kinded types allow one to express the relationship between two different specializations of the same nominal type within a protocol. For example, if we think of the Self type in a protocol as really being “Self<T>”, it allows us to talk about the relationship between “Self<T>” and “Self” for some other type U. For example, it could allow the “map” operation on a collection to return a collection of the same kind but with a different operation, e.g.,

let intArray: Array<Int> = …
intArray.map { String($0) } // produces Array<String>
let intSet: Set<Int> = …
intSet.map { String($0) } // produces Set<String>

Potential syntax borrowed from one thread on higher-kinded types <https://lists.swift.org/pipermail/swift-evolution/Week-of-Mon-20151214/002736.html> uses ~= as a “similarity” constraint to describe a Functor protocol:

protocol Functor {
 associatedtype A
 func fmap<FB where FB ~= Self>(f: A -> FB.A) -> FB
}

Specifying type arguments for uses of generic functions

The type arguments of a generic function are always determined via type inference. For example, given:

func f<T>(t: T)

one cannot directly specify T: either one calls “f” (and T is determined via the argument’s type) or one uses “f” in a context where it is given a particular function type (e.g., “let x: (Int) -> Void = f” would infer T = Int). We could permit explicit specialization here, e.g.,

let x = f<Int> // x has type (Int) -> Void

Unlikely

Features in this category have been requested at various times, but they don’t fit well with Swift’s generics system because they cause some part of the model to become overly complicated, have unacceptable implementation limitations, or overlap significantly with existing features.

Generic protocols

One of the most commonly requested features is the ability to parameterize protocols themselves. For example, a protocol that indicates that the Self type can be constructed from some specified type T:

protocol ConstructibleFromValue<T> {
 init(_ value: T)
}

Implicit in this feature is the ability for a given type to conform to the protocol in two different ways. A “Real” type might be constructible from both Float and Double, e.g.,

struct Real { … }
extension Real : ConstructibleFrom<Float> {
 init(_ value: Float) { … }
}
extension Real : ConstructibleFrom<Double> {
 init(_ value: Double) { … }
}

Most of the requests for this feature actually want a different feature. They tend to use a parameterized Sequence as an example, e.g.,

protocol Sequence<Element> { … }

func foo(strings: Sequence<String>) { /// works on any sequence containing Strings
 // ...
}

The actual requested feature here is the ability to say “Any type that conforms to Sequence whose Element type is String”, which is covered by the section on “Generalized existentials”, below.

More importantly, modeling Sequence with generic parameters rather than associated types is tantalizing but wrong: you don’t want a type conforming to Sequence in multiple ways, or (among other things) your for..in loops stop working, and you lose the ability to dynamically cast down to an existential “Sequence” without binding the Element type (again, see “Generalized existentials”). Use cases similar to the ConstructibleFromValue protocol above seem too few to justify the potential for confusion between associated types and generic parameters of protocols; we’re better off not having the latter.

Private conformances

Right now, a protocol conformance can be no less visible than the minimum of the conforming type’s access and the protocol’s access. Therefore, a public type conforming to a public protocol must provide the conformance publicly. One could imagine removing that restriction, so that one could introduce a private conformance:

public protocol P { }
public struct X { }
extension X : internal P { … } // X conforms to P, but only within this module

The main problem with private conformances is the interaction with dynamic casting. If I have this code:

func foo(value: Any) {
 if let x = value as? P { print(“P”) }
}

foo(X())

Under what circumstances should it print “P”? If foo() is defined within the same module as the conformance of X to P? If the call is defined within the same module as the conformance of X to P? Never? Either of the first two answers requires significant complications in the dynamic casting infrastructure to take into account the module in which a particular dynamic cast occurred (the first option) or where an existential was formed (the second option), while the third answer breaks the link between the static and dynamic type systems—none of which is an acceptable result.

Conditional conformances via protocol extensions

We often get requests to make a protocol conform to another protocol. This is, effectively, the expansion of the notion of “Conditional conformances” to protocol extensions. For example:

protocol P {
 func foo()
}

protocol Q {
 func bar()
}

extension Q : P { // every type that conforms to Q also conforms to P
 func foo() { // implement “foo” requirement in terms of “bar"
 bar()
 }
}

func f<T: P>(t: T) { … }

struct X : Q {
 func bar() { … }
}

f(X()) // okay: X conforms to P through the conformance of Q to P

This is an extremely powerful feature: is allows one to map the abstractions of one domain into another domain (e.g., every Matrix is a Graph). However, similar to private conformances, it puts a major burden on the dynamic-casting runtime to chase down arbitrarily long and potentially cyclic chains of conformances, which makes efficient implementation nearly impossible.

Potential removals

The generics system doesn’t seem like a good candidate for a reduction in scope; most of its features do get used fairly pervasively in the standard library, and few feel overly anachronistic. However...

Associated type inference

Associated type inference is the process by which we infer the type bindings for associated types from other requirements. For example:

protocol IteratorProtocol {
 associatedtype Element
 mutating func next() -> Element?
}

struct IntIterator : IteratorProtocol {
 mutating func next() -> Int? { … } // use this to infer Element = Int
}

Associated type inference is a useful feature. It’s used throughout the standard library, and it helps keep associated types less visible to types that simply want to conform to a protocol. On the other hand, associated type inference is the only place in Swift where we have a global type inference problem: it has historically been a major source of bugs, and implementing it fully and correctly requires a drastically different architecture to the type checker. Is the value of this feature worth keeping global type inference in the Swift language, when we have deliberatively avoided global type inference elsewhere in the language?

Existentials

Existentials aren’t really generics per se, but the two systems are closely intertwined due to their mutable dependence on protocols.

*Generalized existentials

The restrictions on existential types came from an implementation limitation, but it is reasonable to allow a value of protocol type even when the protocol has Self constraints or associated types. For example, consider IteratorProtocol again and how it could be used as an existential:

protocol IteratorProtocol {
 associatedtype Element
 mutating func next() -> Element?
}

let it: IteratorProtocol = …
it.next() // if this is permitted, it could return an “Any?”, i.e., the existential that wraps the actual element

Additionally, it is reasonable to want to constrain the associated types of an existential, e.g., “a Sequence whose element type is String” could be expressed by putting a where clause into “protocol<…>” or “Any<…>” (per “Renaming protocol<…> to Any<…>”):

let strings: Any<Sequence where .Iterator.Element == String> = [“a”, “b”, “c”]

The leading “.” indicates that we’re talking about the dynamic type, i.e., the “Self” type that’s conforming to the Sequence protocol. There’s no reason why we cannot support arbitrary “where” clauses within the “Any<…>”. This very-general syntax is a bit unwieldy, but common cases can easily be wrapped up in a generic typealias (see the section “Generic typealiases” above):

typealias AnySequence<Element> = Any<Sequence where .Iterator.Element == Element>
let strings: AnySequence<String> = [“a”, “b”, “c”]

Opening existentials

Generalized existentials as described above will still have trouble with protocol requirements that involve Self or associated types in function parameters. For example, let’s try to use Equatable as an existential:

protocol Equatable {
 func ==(lhs: Self, rhs: Self) -> Bool
 func !=(lhs: Self, rhs: Self) -> Bool
}

let e1: Equatable = …
let e2: Equatable = …
if e1 == e2 { … } // error: e1 and e2 don’t necessarily have the same dynamic type

One explicit way to allow such operations in a type-safe manner is to introduce an “open existential” operation of some sort, which extracts and gives a name to the dynamic type stored inside an existential. For example:

if let storedInE1 = e1 openas T { // T is a the type of storedInE1, a copy of the value stored in e1
 if let storedInE2 = e2 as? T { // is e2 also a T?
 if storedInE1 == storedInE2 { … } // okay: storedInT1 and storedInE2 are both of type T, which we know is Equatable
 }
}

Thoughts?

 - Doug

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

dabrahams · March 4, 2016, 12:22am

This message expands upon the notion of “completing generics”. It is
not a plan for Swift 3, nor an official core team communication, but
it collects the results of numerous discussions among the core team
and Swift developers, both of the compiler and the standard library. I
hope to achieve several things:

  * Communicate a vision for Swift generics, building on the original
    generics design document, so we have something concrete and
    comprehensive to discuss.

One thing I'd like to see in here, that I don't, is something about
where generics are supposed to fit into the performance model. In
particular, with the advent of resilience and the coming end of
pervasive automatic inlining and specialization, I worry that generics
will not continue to be a viable way to write highly generalized code
that is also high-performance. I think I know some ways we can avoid
this fate, but as far as I know we have no plans in place to do so.

* Establish some terminology that the Swift developers have been
 using for these features, so our discussions can be more productive
 (“oh, you’re proposing what we refer to as ‘conditional
 conformances’; go look over at this thread”).

 * Engage more of the community in discussions of specific generics
 features, so we can coalesce around designs for public review. And
 maybe even get some of them implemented.

A message like this can easily turn into a centithread. To separate
concerns in our discussion, I ask that replies to this specific thread
be limited to discussions of the vision as a whole: how the pieces fit
together, what pieces are missing, whether this is the right long-term
vision for Swift, and so on. For discussions of specific language
features, e.g., to work out the syntax and semantics of conditional
conformances or discuss the implementation in compiler or use in the
standard library, please start a new thread based on the feature names
I’m using.

This message covers a lot of ground; I’ve attempted a rough
categorization of the various features, and kept the descriptions
brief to limit the overall length. Most of these aren’t my ideas, and
any syntax I’m providing is simply a way to express these ideas in
code and is subject to change. Not all of these features will happen,
either soon or ever, but they are intended to be a fairly complete
whole that should mesh together. I’ve put a * next to features that I
think are important in the nearer term vs. being interesting “some
day”. Mostly, the *’s reflect features that will have a significant
impact on the Swift standard library’s design and implementation.

Enough with the disclaimers; it’s time to talk features.

Removing unnecessary restrictions

There are a number of restrictions to the use of generics that fall
out of the implementation in the Swift compiler. Removal of these
restrictions is a matter of implementation only; one need not
introduce new syntax or semantics to realize them. I’m listing them
for two reasons: first, it’s an acknowledgment that these features are
intended to exist in the model we have today, and, second, we’d love
help with the implementation of these features.

*Recursive protocol constraints

Currently, an associated type cannot be required to conform to its
enclosing protocol (or any protocol that inherits that protocol). For
example, in the standard library SubSequence type of a Sequence should
itself be a Sequence:

 protocol Sequence {
 associatedtype Iterator : IteratorProtocol
 …
 associatedtype SubSequence : Sequence // currently ill-formed, but should be possible
 }

The compiler currently rejects this protocol, which is unfortunate: it
effectively pushes the SubSequence-must-be-a-Sequence requirement into
every consumer of SubSequence, and does not communicate the intent of
this abstraction well.

Nested generics

Currently, a generic type cannot be nested within another generic type, e.g.

 struct X<T> {
 struct Y { } // currently ill-formed, but should be possible
 }

There isn’t much to say about this: the compiler simply needs to be
improved to handle nested generics throughout.

Concrete same-type requirements

Currently, a constrained extension cannot use a same-type constraint
to make a type parameter equivalent to a concrete type. For example:

 extension Array where Element == String {
 func makeSentence() -> String {
 // uppercase first string, concatenate with spaces, add a period, whatever
 }
 }

This is a highly-requested feature that fits into the existing syntax
and semantics. Note that one could imagine introducing new syntax,
e.g., extending “Array<String>”, which gets into new-feature
territory: see the section on “Parameterized extensions”.

Parameterizing other declarations

There are a number of Swift declarations that currently cannot have
generic parameters; some of those have fairly natural extensions to
generic forms that maintain their current syntax and semantics, but
become more powerful when made generic.

Generic typealiases

Typealiases could be allowed to carry generic parameters. They would
still be aliases (i.e., they would not introduce new types). For
example:

 typealias StringDictionary<Value> = Dictionary<String, Value>

 var d1 = StringDictionary<Int>()
 var d2: Dictionary<String, Int> = d1 // okay: d1 and d2 have the same type, Dictionary<String, Int>

Generic subscripts

Subscripts could be allowed to have generic parameters. For example,
we could introduce a generic subscript on a Collection that allows us
to pull out the values at an arbitrary set of indices:

 extension Collection {
 subscript<Indices: Sequence where Indices.Iterator.Element == Index>(indices: Indices) -> [Iterator.Element] {
 get {
 var result = [Iterator.Element]()
 for index in indices {
 result.append(self[index])
 }

 return result
 }

 set {
 for (index, value) in zip(indices, newValue) {
 self[index] = value
 }
 }
 }
 }

Generic constants

let constants could be allowed to have generic parameters, such that
they produce differently-typed values depending on how they are
used. For example, this is particularly useful for named literal
values, e.g.,

 let π<T : FloatLiteralConvertible>: T = 3.141592653589793238462643383279502884197169399

The Clang importer could make particularly good use of this when
importing macros.

Parameterized extensions

Aren't you missing a '*' on this one?

Extensions themselves could be parameterized, which would allow some
structural pattern matching on types. For example, this would permit
one to extend an array of optional values, e.g.,

 extension<T> Array where Element == T? {
 var someValues: [T] {
 var result = [T]()
 for opt in self {
 if let value = opt { result.append(value) }
 }
 return result
 }
 }

We can generalize this to a protocol extensions:

 extension<T> Sequence where Element == T? {
 var someValues: [T] {
 var result = [T]()
 for opt in self {
 if let value = opt { result.append(value) }
 }
 return result
 }
 }

Note that when one is extending nominal types, we could simplify the
syntax somewhat to make the same-type constraint implicit in the
syntax:

 extension<T> Array<T?> {
 var someValues: [T] {
 var result = [T]()
 for opt in self {
 if let value = opt { result.append(value) }
 }
 return result
 }
 }

When we’re working with concrete types, we can use that syntax to
improve the extension of concrete versions of generic types (per
“Concrete same-type requirements”, above), e.g.,

 extension Array<String> {
 func makeSentence() -> String {
 // uppercase first string, concatenate with spaces, add a period, whatever
 }
 }

Minor extensions

There are a number of minor extensions we can make to the generics
system that don’t fundamentally change what one can express in Swift,
but which can improve its expressivity.

*Arbitrary requirements in protocols

I guess I don't see how this can be both something that doesn't
fundamentally change expressivity and something that will have a big
impact on the face of the standard library.

Currently, a new protocol can inherit from other protocols, introduce
new associated types, and add new conformance constraints to
associated types (by redeclaring an associated type from an inherited
protocol). However, one cannot express more general
constraints. Building on the example from “Recursive protocol
constraints”, we really want the element type of a Sequence’s
SubSequence to be the same as the element type of the Sequence, e.g.,

    protocol Sequence {
      associatedtype Iterator : IteratorProtocol
      …
      associatedtype SubSequence : Sequence where SubSequence.Iterator.Element == Iterator.Element
    }

Hanging the where clause off the associated type is protocol not
ideal, but that’s a discussion for another thread.

*Typealiases in protocols and protocol extensions

Now that associated types have their own keyword (thanks!), it’s
reasonable to bring back “typealias”. Again with the Sequence
protocol:

    protocol Sequence {
      associatedtype Iterator : IteratorProtocol
      typealias Element = Iterator.Element // rejoice! now we can refer to SomeSequence.Element rather than
    SomeSequence.Iterator.Element
    }

Is this something you expect to be customizable for a particular
conformance? If not, I'm not sure it belongs in the protocol body (as
opposed to an extension)... or we need to draw a clearer distinction
between implementable requirements and things that are currently in
extensions.

Default generic arguments

Generic parameters could be given the ability to provide default
arguments, which would be used in cases where the type argument is not
specified and type inference could not determine the type
argument. For example:

 public final class Promise<Value, Reason=Error> { … }

 func getRandomPromise() -> Promise<Int, ErrorProtocol> { … }

 var p1: Promise<Int> = …
 var p2: Promise<Int, Error> = p1 // okay: p1 and p2 have the same type Promise<Int, Error>
 var p3: Promise = getRandomPromise() // p3 has type Promise<Int, ErrorProtocol> due to type inference

Generalized “class” constraints

The “class” constraint can currently only be used for defining
protocols. We could generalize it to associated type and type
parameter declarations, e.g.,

 protocol P {
 associatedtype A : class
 }

 func foo<T : class>(t: T) { }

As part of this, the magical AnyObject protocol could be replaced with
an existential with a class bound, so that it becomes a typealias:

 typealias AnyObject = protocol<class>

See the “Existentials” section, particularly “Generalized
existentials”, for more information.

I don't see the “value” constraint mentioned. I realize this has some
larger implications in the language but it seems like the obvious dual
of this one.

*Allowing subclasses to override requirements satisfied by defaults

When a superclass conforms to a protocol and has one of the protocol’s
requirements satisfied by a member of a protocol extension, that
member currently cannot be overridden by a subclass. For example:

 protocol P {
 func foo()
 }

 extension P {
 func foo() { print(“P”) }
 }

 class C : P {
 // gets the protocol extension’s
 }

 class D : C {
 /*override not allowed!*/ func foo() { print(“D”) }
 }

 let p: P = D()
 p.foo() // gotcha: prints “P” rather than “D”!

D.foo should be required to specify “override” and should be called
dynamically.

Major extensions to the generics model

Unlike the minor extensions, major extensions to the generics model
provide more expressivity in the Swift generics system and, generally,
have a much more significant design and implementation cost.

*Conditional conformances

Conditional conformances express the notion that a generic type will
conform to a particular protocol only under certain circumstances. For
example, Array is Equatable only when its elements are Equatable:

 extension Array : Equatable where Element : Equatable { }

 func ==<T : Equatable>(lhs: Array<T>, rhs: Array<T>) -> Bool { … }

Conditional conformances are a potentially very powerful feature. One
important aspect of this feature is how deal with or avoid overlapping
conformances. For example, imagine an adaptor over a Sequence that has
conditional conformances to Collection and MutableCollection:

 struct SequenceAdaptor<S: Sequence> : Sequence { }
 extension SequenceAdaptor : Collection where S: Collection { … }
 extension SequenceAdaptor : MutableCollection where S: MutableCollection { }

This should almost certainly be permitted, but we need to cope with or
reject “overlapping” conformances:

 extension SequenceAdaptor : Collection where S: SomeOtherProtocolSimilarToCollection { } // trouble: two ways

Missing generic parameter list here?

for SequenceAdaptor to conform to Collection

See the section on “Private conformances” for more about the issues
with having the same type conform to the same protocol multiple times.

Variadic generics

Currently, a generic parameter list contains a fixed number of generic
parameters. If one has a type that could generalize to any number of
generic parameters, the only real way to deal with it today involves
creating a set of types. For example, consider the standard library’s
“zip” function. It returns one of these when provided with two
arguments to zip together:

 public struct Zip2Sequence<Sequence1 : Sequence,
 Sequence2 : Sequence> : Sequence { … }

 public func zip<Sequence1 : Sequence, Sequence2 : Sequence>(
 sequence1: Sequence1, _ sequence2: Sequence2)
 -> Zip2Sequence<Sequence1, Sequence2> { … }

Supporting three arguments would require copy-paste of those of those:

 public struct Zip3Sequence<Sequence1 : Sequence,
 Sequence2 : Sequence,
 Sequence3 : Sequence> : Sequence { … }

 public func zip<Sequence1 : Sequence, Sequence2 : Sequence, Sequence3 : Sequence>(
 sequence1: Sequence1, _ sequence2: Sequence2, _ sequence3: sequence3)
 -> Zip3Sequence<Sequence1, Sequence2, Sequence3> { … }

Variadic generics would allow us to abstract over a set of generic
parameters. The syntax below is hopelessly influenced by C++11
variadic templates (sorry), where putting an ellipsis (“…”) to the
left of a declaration makes it a “parameter pack” containing zero or
more parameters and putting an ellipsis to the right of a
type/expression/ etc. expands the parameter packs within that
type/expression into separate arguments. The important part is that we
be able to meaningfully abstract over zero or more generic parameters,
e.g.:

 public struct ZipIterator<... Iterators : IteratorProtocol> : Iterator { // zero or more type parameters, each
 of which conforms to IteratorProtocol
 public typealias Element = (Iterators.Element...) // a tuple containing the element
 types of each iterator in Iterators

 var (...iterators): (Iterators...) // zero or more stored properties, one for each type in Iterators
 var reachedEnd: Bool = false

 public mutating func next() -> Element? {

 if reachedEnd { return nil }

 guard let values = (iterators.next()...) { // call “next” on each of the iterators, put the results into a
 tuple named “values"

 reachedEnd = true

 return nil

 }

 return values

 }
 }

 public struct ZipSequence<...Sequences : Sequence> : Sequence {
 public typealias Iterator = ZipIterator<Sequences.Iterator...> // get the zip iterator with the iterator
 types of our Sequences

 var (...sequences): (Sequences...) // zero or more stored properties, one for each type in Sequences

 // details ...
 }

Such a design could also work for function parameters, so we can pack
together multiple function arguments with different types, e.g.,

 public func zip<... Sequences : SequenceType>(... sequences: Sequences...)
 -> ZipSequence<Sequences...> {
 return ZipSequence(sequences...)
 }

Finally, this could tie into the discussions about a tuple “splat”
operator. For example:

 func apply<... Args, Result>(fn: (Args...) -> Result, // function taking some number of arguments and
 producing Result
 args: (Args...)) -> Result { // tuple of arguments
 return fn(args...) // expand the arguments in the tuple “args” into
 separate arguments
 }

Extensions of structural types

Currently, only nominal types (classes, structs, enums, protocols) can
be extended. One could imagine extending structural types—particularly
tuple types—to allow them to, e.g., conform to protocols. For example,
pulling together variadic generics, parameterized extensions, and
conditional conformances, one could express “a tuple type is Equatable
if all of its element types are Equatable”:

 extension<...Elements : Equatable> (Elements...) : Equatable { // extending the tuple type “(Elements…)” to be
 Equatable
 }

There are some natural bounds here: one would need to have actual
structural types. One would not be able to extend every type:

 extension<T> T { // error: neither a structural nor a nominal type
 }

And before you think you’re cleverly making it possible to have a
conditional conformance that makes every type T that conforms to
protocol P also conform to protocol Q, see the section "Conditional
conformances via protocol extensions”, below:

 extension<T : P> T : Q { // error: neither a structural nor a nominal type
 }

Syntactic improvements

There are a number of potential improvements we could make to the
generics syntax. Such a list could go on for a very long time, so I’ll
only highlight some obvious ones that have been discussed by the Swift
developers.

*Default implementations in protocols

Currently, protocol members can never have implementations. We could
allow one to provide such implementations to be used as the default if
a conforming type does not supply an implementation, e.g.,

 protocol Bag {
 associatedtype Element : Equatable
 func contains(element: Element) -> Bool

 func containsAll<S: Sequence where Sequence.Iterator.Element == Element>(elements: S) -> Bool {
 for x in elements {
 if contains(x) { return true }
 }
 return false
 }
 }

 struct IntBag : Bag {
 typealias Element = Int
 func contains(element: Int) -> Bool { ... }

 // okay: containsAll requirement is satisfied by Bag’s default implementation
 }

One can get this effect with protocol extensions today, hence the
classification of this feature as a (mostly) syntactic improvement:

 protocol Bag {
 associatedtype Element : Equatable
 func contains(element: Element) -> Bool

 func containsAll<S: Sequence where Sequence.Iterator.Element == Element>(elements: S) -> Bool
 }

 extension Bag {
 func containsAll<S: Sequence where Sequence.Iterator.Element == Element>(elements: S) -> Bool {
 for x in elements {
 if contains(x) { return true }
 }
 return false
 }
 }

*Moving the where clause outside of the angle brackets

The “where” clause of generic functions comes very early in the
declaration, although it is generally of much less concern to the
client than the function parameters and result type that follow
it. This is one of the things that contributes to “angle bracket
blindness”. For example, consider the containsAll signature above:

 func containsAll<S: Sequence where Sequence.Iterator.Element == Element>(elements: S) -> Bool

One could move the “where” clause to the end of the signature, so that
the most important parts—name, generic parameter, parameters, result
type—precede it:

 func containsAll<S: Sequence>(elements: S) -> Bool

 where Sequence.Iterator.Element == Element

*Renaming “protocol<…>” to “Any<…>”.

The “protocol<…>” syntax is a bit of an oddity in Swift. It is used to
compose protocols together, mostly to create values of existential
type, e.g.,

 var x: protocol<NSCoding, NSCopying>

It’s weird that it’s a type name that starts with a lowercase letter,
and most Swift developers probably never deal with this feature unless
they happen to look at the definition of Any:

 typealias Any = protocol<>

“Any” might be a better name for this functionality. “Any” without
brackets could be a keyword for “any type”, and “Any” followed by
brackets could take the role of “protocol<>” today:

 var x: Any<NSCoding, NSCopying>

That reads much better: “Any type that conforms to NSCoding and
NSCopying”. See the section "Generalized existentials” for additional
features in this space.

Maybe

There are a number of features that get discussed from time-to-time,
while they could fit into Swift’s generics system, it’s not clear that
they belong in Swift at all. The important question for any feature in
this category is not “can it be done” or “are there cool things we can
express”, but “how can everyday Swift developers benefit from the
addition of such a feature?”. Without strong motivating examples, none
of these “maybes” will move further along.

Dynamic dispatch for members of protocol extensions

Only the requirements of protocols currently use dynamic dispatch,
which can lead to surprises:

 protocol P {
 func foo()
 }

 extension P {
 func foo() { print(“P.foo()”)
 func bar() { print(“P.bar()”)
 }

 struct X : P {
 func foo() { print(“X.foo()”)
 func bar() { print(“X.bar()”)
 }

 let x = X()
 x.foo() // X.foo()
 x.bar() // X.bar()

 let p: P = X()
 p.foo() // X.foo()
 p.bar() // P.bar()

Swift could adopt a model where members of protocol extensions are
dynamically dispatched.

Named generic parameters

When specifying generic arguments for a generic type, the arguments
are always positional: Dictionary<String, Int> is a Dictionary whose
Key type is String and whose Value type is Int, by convention. One
could permit the arguments to be labeled, e.g.,

 var d: Dictionary<Key: String, Value: Int>

Such a feature makes more sense if Swift gains default generic
arguments, because generic argument labels would allow one to skip
defaulted arguments.

Generic value parameters

Currently, Swift’s generic parameters are always types. One could
imagine allowing generic parameters that are values, e.g.,

 struct MultiArray<T, let Dimensions: Int> { // specify the number of dimensions to the array
 subscript (indices: Int...) -> T {
 get {
 require(indices.count == Dimensions)
 // ...
 }
 }

A suitably general feature might allow us to express fixed-length
array or vector types as a standard library component, and perhaps
also allow one to implement a useful dimensional analysis
library. Tackling this feature potentially means determining what it
is for an expression to be a “constant expression” and diving into
dependent-typing, hence the “maybe”.

Higher-kinded types

Higher-kinded types allow one to express the relationship between two
different specializations of the same nominal type within a
protocol. For example, if we think of the Self type in a protocol as
really being “Self<T>”, it allows us to talk about the relationship
between “Self<T>” and “Self” for some other type U. For example, it
could allow the “map” operation on a collection to return a collection
of the same kind but with a different operation, e.g.,

 let intArray: Array<Int> = …
 intArray.map { String($0) } // produces Array<String>
 let intSet: Set<Int> = …
 intSet.map { String($0) } // produces Set<String>

Potential syntax borrowed from one thread on higher-kinded types uses
~= as a “similarity” constraint to describe a Functor protocol:

 protocol Functor {
 associatedtype A
 func fmap<FB where FB ~= Self>(f: A -> FB.A) -> FB
 }

Specifying type arguments for uses of generic functions

The type arguments of a generic function are always determined via
type inference. For example, given:

 func f<T>(t: T)

one cannot directly specify T: either one calls “f” (and T is
determined via the argument’s type) or one uses “f” in a context where
it is given a particular function type (e.g., “let x: (Int) -> Void =
f” would infer T = Int). We could permit explicit specialization here,
e.g.,

 let x = f<Int> // x has type (Int) -> Void

Unlikely

Features in this category have been requested at various times, but
they don’t fit well with Swift’s generics system because they cause
some part of the model to become overly complicated, have unacceptable
implementation limitations, or overlap significantly with existing
features.

Generic protocols

One of the most commonly requested features is the ability to
parameterize protocols themselves. For example, a protocol that
indicates that the Self type can be constructed from some specified
type T:

 protocol ConstructibleFromValue<T> {
 init(_ value: T)
 }

Implicit in this feature is the ability for a given type to conform to
the protocol in two different ways. A “Real” type might be
constructible from both Float and Double, e.g.,

 struct Real { … }
 extension Real : ConstructibleFrom<Float> {
 init(_ value: Float) { … }
 }
 extension Real : ConstructibleFrom<Double> {
 init(_ value: Double) { … }
 }

Most of the requests for this feature actually want a different
feature. They tend to use a parameterized Sequence as an example,
e.g.,

 protocol Sequence<Element> { … }

 func foo(strings: Sequence<String>) { /// works on any sequence containing Strings
 // ...
 }

The actual requested feature here is the ability to say “Any type that
conforms to Sequence whose Element type is String”, which is covered
by the section on “Generalized existentials”, below.

More importantly, modeling Sequence with generic parameters rather
than associated types is tantalizing but wrong: you don’t want a type
conforming to Sequence in multiple ways, or (among other things) your
for..in loops stop working, and you lose the ability to dynamically
cast down to an existential “Sequence” without binding the Element
type (again, see “Generalized existentials”). Use cases similar to the
ConstructibleFromValue protocol above seem too few to justify the
potential for confusion between associated types and generic
parameters of protocols; we’re better off not having the latter.

Private conformances

Right now, a protocol conformance can be no less visible than the
minimum of the conforming type’s access and the protocol’s
access. Therefore, a public type conforming to a public protocol must
provide the conformance publicly. One could imagine removing that
restriction, so that one could introduce a private conformance:

 public protocol P { }
 public struct X { }
 extension X : internal P { … } // X conforms to P, but only within this module

The main problem with private conformances is the interaction with dynamic casting. If I have this code:

 func foo(value: Any) {
 if let x = value as? P { print(“P”) }
 }

 foo(X())

Under what circumstances should it print “P”? If foo() is defined
within the same module as the conformance of X to P? If the call is
defined within the same module as the conformance of X to P? Never?
Either of the first two answers requires significant complications in
the dynamic casting infrastructure to take into account the module in
which a particular dynamic cast occurred (the first option) or where
an existential was formed (the second option), while the third answer
breaks the link between the static and dynamic type systems—none of
which is an acceptable result.

Conditional conformances via protocol extensions

We often get requests to make a protocol conform to another
protocol. This is, effectively, the expansion of the notion of
“Conditional conformances” to protocol extensions. For example:

 protocol P {
 func foo()
 }

 protocol Q {
 func bar()
 }

 extension Q : P { // every type that conforms to Q also conforms to P
 func foo() { // implement “foo” requirement in terms of “bar"
 bar()
 }
 }

 func f<T: P>(t: T) { … }

 struct X : Q {
 func bar() { … }
 }

 f(X()) // okay: X conforms to P through the conformance of Q to P

This is an extremely powerful feature: is allows one to map the
abstractions of one domain into another domain (e.g., every Matrix is
a Graph). However, similar to private conformances, it puts a major
burden on the dynamic-casting runtime to chase down arbitrarily long
and potentially cyclic chains of conformances, which makes efficient
implementation nearly impossible.

Potential removals

The generics system doesn’t seem like a good candidate for a reduction
in scope; most of its features do get used fairly pervasively in the
standard library, and few feel overly anachronistic. However...

Associated type inference

Associated type inference is the process by which we infer the type
bindings for associated types from other requirements. For example:

 protocol IteratorProtocol {
 associatedtype Element
 mutating func next() -> Element?
 }

 struct IntIterator : IteratorProtocol {
 mutating func next() -> Int? { … } // use this to infer Element = Int
 }

Associated type inference is a useful feature. It’s used throughout
the standard library, and it helps keep associated types less visible
to types that simply want to conform to a protocol. On the other hand,
associated type inference is the only place in Swift where we have a
global type inference problem: it has historically been a major source
of bugs, and implementing it fully and correctly requires a
drastically different architecture to the type checker. Is the value
of this feature worth keeping global type inference in the Swift
language, when we have deliberatively avoided global type inference
elsewhere in the language?

Existentials

Existentials aren’t really generics per se, but the two systems are
closely intertwined due to their mutable dependence on protocols.

*Generalized existentials

The restrictions on existential types came from an implementation
limitation, but it is reasonable to allow a value of protocol type
even when the protocol has Self constraints or associated types. For
example, consider IteratorProtocol again and how it could be used as
an existential:

 protocol IteratorProtocol {
 associatedtype Element
 mutating func next() -> Element?
 }

 let it: IteratorProtocol = …
 it.next() // if this is permitted, it could return an “Any?”, i.e., the existential that wraps the actual
 element

Additionally, it is reasonable to want to constrain the associated
types of an existential, e.g., “a Sequence whose element type is
String” could be expressed by putting a where clause into
“protocol<…>” or “Any<…>” (per “Renaming protocol<…> to Any<…>”):

 let strings: Any<Sequence where .Iterator.Element == String> = [“a”, “b”, “c”]

The leading “.” indicates that we’re talking about the dynamic type,
i.e., the “Self” type that’s conforming to the Sequence
protocol. There’s no reason why we cannot support arbitrary “where”
clauses within the “Any<…>”. This very-general syntax is a bit
unwieldy, but common cases can easily be wrapped up in a generic
typealias (see the section “Generic typealiases” above):

 typealias AnySequence<Element> = Any<Sequence where .Iterator.Element == Element>
 let strings: AnySequence<String> = [“a”, “b”, “c”]

Opening existentials

Generalized existentials as described above will still have trouble
with protocol requirements that involve Self or associated types in
function parameters. For example, let’s try to use Equatable as an
existential:

 protocol Equatable {
 func ==(lhs: Self, rhs: Self) -> Bool
 func !=(lhs: Self, rhs: Self) -> Bool
 }

 let e1: Equatable = …
 let e2: Equatable = …
 if e1 == e2 { … } // error: e1 and e2 don’t necessarily have the same dynamic type

One explicit way to allow such operations in a type-safe manner is to
introduce an “open existential” operation of some sort, which extracts
and gives a name to the dynamic type stored inside an existential. For
example:

 if let storedInE1 = e1 openas T { // T is a the type of storedInE1, a copy of the value stored in e1

 if let storedInE2 = e2 as? T { // is e2 also a T?

 if storedInE1 == storedInE2 { … } // okay: storedInT1 and storedInE2 are both of type T, which we know is
 Equatable

 }

 }

Thoughts?

This is certainly... a lot. I've wanted so much from the generics
system over the years that it's hard to remember whether everything
important is in this list. I'll have to give that some more thought.

···

on Wed Mar 02 2016, Douglas Gregor <swift-evolution@swift.org> wrote:

--
-Dave

mwhiteside.dev · March 9, 2016, 1:53am

I’m really looking forward to the features on this list.

The following is one that I’ve come across the need for a couple times already, even with the limited amount of swift I have written:

···

On Mar 2, 2016, at 17:22, Douglas Gregor via swift-evolution <swift-evolution@swift.org> wrote:

extension Array<String> {
 func makeSentence() -> String {
 // uppercase first string, concatenate with spaces, add a period, whatever
 }
}

Tino · March 9, 2016, 11:16am

I proposed adding generic value parameters under the label "compile time parameters", and stopped working on it because it is out of scope for Swift 3 — yet I'm still very eager to see this added in the future.
My draft most likely had no impact on "Completing Generics", but as I favored the same syntax, I take this match as an indication that the choice is somewhat natural.
Introduction

Generics are often seen as "simplified templates": They are not as powerful, but have the benefit of being less complicated and dangerous. The feature illustrated here should not only make Swift more powerful, but also safer by adding basic datatypes like fixed-size arrays.

<Compile time parameters · SwiftInofficialEvolution/Home Wiki · GitHub

Right now, we can have something like let m = Matrix(rows: 3, columns: 4) easily. There's just the problem that the compiler cannot deduce which matrices are "compatible", as there is only one Matrix-type. If we had a way to tell the compiler that "rows" and "columns" have an effect on the type, errors due to dimension mismatches could be eliminated (vector math, but also functions like zip would benefit from this).

Additionally, the proposal would make it possible to create unit systems, so that calculations are checked for matching quantities (so you cannot add a force to a velocity without causing an error).

Currently, there is no elegant way to declare a C-type array of a fixed size; this is a fundamental problem that could be solved with the syntax presented here.

<Compile time parameters · SwiftInofficialEvolution/Home Wiki · GitHub solution

The basic idea is quite simple: We just need a way to tell the compile that there are some parameters that have impact on their type. On possible syntax would be

struct Matrix<T: ScalarType, let rows: UInt, let columns: UInt> {
...
subscript(row: UInt, column: UInt) -> T {
 set(value) {
 if row < rows && column < columns {
 // set the entry
 } else {
 // out of bounds - that is not allowed
 }
 }
...
}
<Compile time parameters · SwiftInofficialEvolution/Home Wiki · GitHub design

I think its easy to grasp with the example: In addition to type parameters, we introduce constants that are defined in a similar way:

let [identifier]: [type]

e.g.

struct FloatVector<let dimensions: UInt>...

Unlike templates, compile-time parameters (as the name already suggests) could live inside libs, without disclosing details about their implementation.

From the inside of the parametrized object, compile-time parameters would be used like normal let-parameters/members.

<Compile time parameters · SwiftInofficialEvolution/Home Wiki · GitHub

The behavior should be similar to generics, so the position of each parameter in the list is fixed. To make things clearer, I suggest to accept (optional) labels, so that the two following statements are valid:

let force: FloatVector<dimensions: 3>

let impulse: FloatVector<3>

<Compile time parameters · SwiftInofficialEvolution/Home Wiki · GitHub for parameter values

Although integer-type parameters are most likely the only ones with a broad use case, any type implementing one of the ...LiteralCovertible protocols could be used. Enums and other entities could make sense as well, but this is beyond the scope of this proposal.

<Compile time parameters · SwiftInofficialEvolution/Home Wiki · GitHub extension: Limitations

It would nice to have where-clauses on the parameters to disallow certain values or value-combinations.

<Compile time parameters · SwiftInofficialEvolution/Home Wiki · GitHub on existing code

None, it's a new feature that does not affect existing code - but it might be a good opportunity to improve the generics syntax as well: There have also been wishes for labeled type parameters, and as far as I can see, those should be allowed, too.

To further increase consistency, the generics-syntax could be changed (struct Array<type T>... or struct Array<T: type where ...>), but that is not coupled with this proposal.

<Compile time parameters · SwiftInofficialEvolution/Home Wiki · GitHub considered

Actually, the let-syntax is not my preferred choice - but there is a collision with generics, and relying on capitalization to distinguish MyClass<size: Int> and MyClass<V: UIView> seems strange. It could still be possible to drop let without confusing the compiler, but I'm concerned about confusing the user:

It makes no sense to declare a generic parameter that is restricted to a subtype of something that is final, but that isn't obvious to a human reader.

<Compile time parameters · SwiftInofficialEvolution/Home Wiki · GitHub parameters

It would be possible to keep the parameters in the initializer (or function) and mark them with a keyword: init(static dimensions: Int) {...

Especially for types, this would be cumbersome, as you can have many initializers.

<Compile time parameters · SwiftInofficialEvolution/Home Wiki · GitHub kind of braces

Instead of grouping value parameters with type parameters, they could be separated:

class Test[Size: Int]<T> or class Test(size: Int)<T>

The benefit would be that let isn't needed anymore, but as compile-time parameters are very similar to generics, it would be nice to resemble that in the syntax. Especially the square-braces have a very different, established meaning (array subscript), so I'd strongly advice not to consider them.

Normal parenthesis don't have that problem at the declaration site, but lack an obvious instantiation syntax that doesn't collide with init parameters.

<Compile time parameters · SwiftInofficialEvolution/Home Wiki · GitHub types

The current "solution" is declaring a type for every case you want to cover.

This approach works good enough in simple situations (e.g. Vector4), but it scales badly:

It is tedious to declare new variants, and the only way to express their tight resemblance is a coherent naming scheme that isn't enforced.

<Compile time parameters · SwiftInofficialEvolution/Home Wiki · GitHub and preprocessors

It is possible to generate distinct types using macros - but as there is no build-in support for those, this is quite cumbersome.

<Compile time parameters · SwiftInofficialEvolution/Home Wiki · GitHub

There has been a discussion about a shorthand to declare tuples with a fixed number of elements.

This solution would have the benefit of automatic compatibility with C-structs - but the downside of not having the power of Swift structs (and classes): Tuples can't have methods, and this is a major drawback.

So, the tuple-extension is no real alternative, but both ideas would fit together without redundancy.

In general, I think a Wiki-Page would be a nice helper to discuss comprehensive topics like generics (things like concurrency and compile-time evaluation imho are good candidates for a Wiki as well).

- Tino

Erik_Verbruggen · March 9, 2016, 12:28pm

Generic constants

let constants could be allowed to have generic parameters, such that they produce differently-typed values depending on how they are used. For example, this is particularly useful for named literal values, e.g.,

let π<T : FloatLiteralConvertible>: T = 3.141592653589793238462643383279502884197169399

The Clang importer could make particularly good use of this when importing macros.

I assume the following will fall under "constant expression":

let 2π = 2 * π

Also, how does the clang-importer handle:

#define M_DOUBLE_PI (2 * M_PI)

Or rephrasing, this is specifically for the case where the initialiser only consists of a single literal token?

-- Erik.

Jonathan_Tang · March 10, 2016, 8:23am

Going through my code comments & notes now to see where the ideas here
could've helped avoid some nasty hacks. I'll try to keep this mostly to
(missing) features I've found problematic but haven't seen mentioned here
and quick votes with comments that I think won't be responded to, and then
fork off deeper discussions into their own threads as suggested.

*Missing feature: How do protocols interact with the package system?*

Javascript had an unfortunate situation a couple years ago where there were
about a dozen competing Promise implementations. The leading libraries all
got together and came up with the Promises/A+ spec. Because Javascript is
dynamically typed, the spec mandates that anything with a then() method is
"Promise-like", and can be chained into existing promises. As a result,
you can take a library that uses Bluebird promises, pass them to a library
that uses the es6-promise Polyfill, and then use the native implementation
of Promise.all and everything will just work.

Swift is not dynamically typed - to indicate a common set of functionality,
you need to define a protocol. What happens when multiple frameworks
define a protocol that other frameworks wish to use? I know of at least 3
different mutually-incompatible Promise implementations for Swift, but
assuming they managed to reconcile their differences and come up with a
common API - how would a library wanting to use this spec ensure that it's
compatible with other libraries using the spec? If I include
promises.swift in my project which defines "public protocol Promise { ...
}", will the compiler know that it's the same protocol as the identical
promises.swift in AlamoFire or RethinkDB? If not - how could it be
packaged up on its own so that everyone can be good citizens and
interoperate with each other? Will app developers using these libraries
need to install a long chain of dependencies, or can they just get their
leaf dependencies and trust that everything will work together? What
happens if there are versioning inconsistencies behind the protocols that
library dependencies use?

*Missing feature: "protocol can only be used as a generic constraint"*

This error message pops up whenever you try to use a protocol that has
associated types or Self (in a non-return position) as a type. Instead of
being able to write "func doSomething(obj: MyProtocol)", you now have to
write "func doSomething<T: MyProtocol>(obj: T)", and you can forget about
being able to store objects of these protocols in data structures. As I
understand it, this is because of conceptional confusion on the part of the
dev: when a protocol has associated types, it's no longer a *type*, but a *type
family*, and so it doesn't make sense to use it as you would a type. The
compiler would have to enforce invariants that it doesn't have the
information to enforce.

That said, is there anyway to reduce the impact of this error message
(which, based on several Google searches and a bunch of encounters with it
myself, seems to happen quite frequently)?

In my experience, this error seems to pop up most often in two common
circumstances:

- Adopting Equatable or Hashable in a protocol

Solved by existentials - the usage of the protocol becomes an existential.
In particular, "opening existentials" is usually what you'd want to do for
==; I'm not really sure I like the syntax proposed here but this thread
isn't for bikeshedding. :-)

- Making a protocol inherit from a collection

Examples of this might include having a Message object behave like
[String:AnyObject], having an Amazon S3 interface behave like
[String:NSData], or having a File behave like [String] (like in Python).
Assume that concrete adopting classes cannot change the associated types.

The interesting thing about this case is that all of the associated types
are nailed down, and their usage can be limited to default method
implementations that don't vary between the concrete types adopting the
protocol. So in such a File, the Generator implementation would always
delegate to self.readLine(), the SubSequence type is always [String], and
the only time these types are referenced is on default methods on File
which themselves delegate to the protocol methods witnessed by adopting
types.

IIUC, the compiler should have enough information available to generate all
code required by a File parameter, right? It knows the associated types of
the collection, and it knows the methods that generate them.

Could this special case be fixed?

*Missing feature: How does toll-free bridging with Foundation interact with
protocol extensions?*

Last time I checked, an Array is-a NSArray and vice versa; they satisfy
is/as checks, they can be used interchangeably, and methods on one are
available on the other. Except for with protocol extensions. When you
extend Array to conform to a protocol, you don't automatically get NSArray
as well. You have to explicitly define a conformance for NSArray as well,
which often has exactly the same code.

This is more a source of head-scratching & annoyance than a fundamental
limitation, since you can always duplicate the code and factor the logic
out to a common helper. But it's one that's likely to be propagated
through the library ecosystem, as library authors who grow up on Swift
forget about NSArray/NSDictionary/etc. and then their code just doesn't
work for people switching over an Objective-C app.

**Conditional conformances*

Big +1. This is necessary for any sort of extensible tree structure.
Think about JSON serialization, for example: an array or dictionary is JSON
serializable only if all of its elements are JSON serializable, and the
algorithm used to serialize it depends on a call to serialize its members.
It comes up in many UI areas as well: a UI component might be Persistable
iff all of its subviews are Persistable.

The lack of this prevents app code from being able to easily extend
functionality provided in a library, eg. I may be able to easily come up
with a JSON serialization of a CLLocation or CNContact, but SwiftyJSON will
be unable to serialize an array of these objects using my mechanism.

*Concrete same-type requirements*

Big +1 on this as well. It seems like it's pretty uncontroversial, but
this is widely applicable across a number of domains. Basically any time
you need to operate on a generic collection with operations that only make
sense on a particular element type.

This would also increase the usefulness of "Generic typealiases" - the two
proposals together let you define new generic types just by adding
extensions to existing generic types. Good way to prototype, and then if
the extension gets too complicated, you can always take what you've learned
and make a real type.

*Parameterized extensions*

**Arbitrary requirements in protocols*

These two both seem nifty, but I'm having trouble thinking of a concrete
use-case where they'd be critical. The "arbitrary requirements in
protocols" in particular seems to be going down the path of "let's embed a
constraint solver in the Swift compiler", which seems like it'd lead to
some fun webpages a la type arithmetics
<http://okmij.org/ftp/Computation/type-arithmetics.html>, but not something
you'd want to see in your coworker's code.

*Default generic arguments *

Is it within Swift's scope to support compile-time polymorphism for high
performance computing? This is a common technique in C++: you want a
generic algorithm that must be specialized in one or two places, but can't
afford the run-time overhead of dynamic dispatch. So you create a template
parameter with a functor type. STL allocators are a good example.

I don't personally do much HPC and dunno if it fits within Apple's vision
for Swift, but there are few other options if you do, and default generic
args make this tactic much more convenient. Also fits well with "Named
generic parameters" and "Generic value parameters". Might combine
awkwardly with "Variadic generics" and "Moving the where clause out of the
angle brackets" (would the default be specified inside the angle brackets
or outside?).

**Allowing subclasses to override requirements satisfied by defaults*

Necessary for "Dynamic dispatch of protocol extensions" and "default
implementations in protocols" to make sense, right? +1 to all three, it
seems like this is a cluster of related improvements that would make things
more uniform & understandable.

*Variadic generics*

I'll fork off a thread on this...I've got some thoughts specifically
related to use with function types.

**Default implementations in protocols*

+1. It's cosmetic only, but the "use an extension to provide default
members of a protocol" idiom can be very confusing to newcomers.

**Renaming “protocol<…>” to “Any<…>”.*

+1. protocol<> always struck me as weird. Any<...> is pretty similar to
equivalent concepts in other languages, like union types in Dylan.

**Moving the where clause outside of the angle brackets*

-1. Haskell does it this way (and pretty much has to because of MPTCs with
fundeps). I found it was one of the hard parts of learning Haskell - I'm
used to thinking of a type as a unit. Adding generics to that unit isn't
too hard to wrap my head around. Adding constraints to those generics
isn't that hard, although at that point the type signatures are getting
really long. (The proposals for "Generic typealiases" and "Typealiases in
protocols and protocol extensions" could help ameliorate this. Is it
possible to typealias constraints as well?) Wondering what the hell this
"where" clause is and how it relates to these generic things and why it's
at the end of the function signature can get pretty confusing.

Also, how does this interact with generic constraints on class/structs?
Would it go after the full struct definition, or just after the class name?

*Dynamic dispatch for members of protocol extensions*

Static dispatch is very confusing here. The whole point of protocols is to
get ad-hoc polymorphism, so when a protocol default message is called
instead of the overridden version just because of the static type signature
of the variable, it's likely to result in much head-scratching.

*Potential removals*

The generics system doesn’t seem like a good candidate for a reduction in
scope; most of its features do get used fairly pervasively in the standard
library, and few feel overly anachronistic. However...

*Associated type inference*

The consequence of its removal is just that classes/structs that conform to
IteratorProtocol will now have to say "associatedtype Element = Int"? I
don't view that as a major hurdle. It's a bit of an annoyance, but if it
makes the typechecker significantly simpler and allows implementation of
some of the other ideas here, I think it's worth it. It would be more
problematic if it required extra declarations at the call site; functions
are called orders of magnitude more times than classes & structs are
declared.

*Existentials*

Existentials aren’t really generics per se, but the two systems are
closely intertwined due to their mutable dependence on protocols.

**Generalized existentials*

*Opening existentials*

+1 on both of these. I remember writing a Haskell tutorial
<https://en.wikibooks.org/wiki/Write_Yourself_a_Scheme_in_48_Hours> several
years ago, and it was amazing how quickly you needed existentials. It's
not uncommon to want a heterogenous collection of objects that all
implement a single protocol; generics don't give you this.

There's an existing thread on this, so I'll send comments on the syntax &
usage of this over that way.

···

On Wed, Mar 2, 2016 at 5:22 PM, Douglas Gregor via swift-evolution < swift-evolution@swift.org> wrote:

Russ_Bishop1 · April 5, 2016, 12:26am

Removing unnecessary restrictions

Concrete same-type requirements

Currently, a constrained extension cannot use a same-type constraint to make a type parameter equivalent to a concrete type. For example:

extension Array where Element == String {
 func makeSentence() -> String {
 // uppercase first string, concatenate with spaces, add a period, whatever
 }
}

This is a highly-requested feature that fits into the existing syntax and semantics. Note that one could imagine introducing new syntax, e.g., extending “Array<String>”, which gets into new-feature territory: see the section on “Parameterized extensions”.

Seems useful.

Parameterizing other declarations

Parameterized extensions

Extensions themselves could be parameterized, which would allow some structural pattern matching on types. For example, this would permit one to extend an array of optional values, e.g.,

extension<T> Array where Element == T? {
 var someValues: [T] {
 var result = [T]()
 for opt in self {
 if let value = opt { result.append(value) }
 }
 return result
 }
}

We can generalize this to a protocol extensions:

extension<T> Sequence where Element == T? {
 var someValues: [T] {
 var result = [T]()
 for opt in self {
 if let value = opt { result.append(value) }
 }
 return result
 }
}

This would be fantastic. I’ve run into it a number of times.

Minor extensions

There are a number of minor extensions we can make to the generics system that don’t fundamentally change what one can express in Swift, but which can improve its expressivity.

*Arbitrary requirements in protocols

Currently, a new protocol can inherit from other protocols, introduce new associated types, and add new conformance constraints to associated types (by redeclaring an associated type from an inherited protocol). However, one cannot express more general constraints. Building on the example from “Recursive protocol constraints”, we really want the element type of a Sequence’s SubSequence to be the same as the element type of the Sequence, e.g.,

protocol Sequence {
  associatedtype Iterator : IteratorProtocol
  …
  associatedtype SubSequence : Sequence where SubSequence.Iterator.Element == Iterator.Element
}

Hanging the where clause off the associated type is protocol not ideal, but that’s a discussion for another thread.

Definitely run into this one before.

Default generic arguments

Generic parameters could be given the ability to provide default arguments, which would be used in cases where the type argument is not specified and type inference could not determine the type argument. For example:

public final class Promise<Value, Reason=Error> { … }

func getRandomPromise() -> Promise<Int, ErrorProtocol> { … }

var p1: Promise<Int> = …
var p2: Promise<Int, Error> = p1 // okay: p1 and p2 have the same type Promise<Int, Error>
var p3: Promise = getRandomPromise() // p3 has type Promise<Int, ErrorProtocol> due to type inference

Also quite useful in eliminating boilerplate.

Generalized “class” constraints

The “class” constraint can currently only be used for defining protocols. We could generalize it to associated type and type parameter declarations, e.g.,

protocol P {
associatedtype A : class
}

func foo<T : class>(t: T) { }

As part of this, the magical AnyObject protocol could be replaced with an existential with a class bound, so that it becomes a typealias:

typealias AnyObject = protocol<class>

See the “Existentials” section, particularly “Generalized existentials”, for more information.

Another +1.

Major extensions to the generics model

Unlike the minor extensions, major extensions to the generics model provide more expressivity in the Swift generics system and, generally, have a much more significant design and implementation cost.

*Conditional conformances

This one seems extremely important and has immediate utility IMHO.

Syntactic improvements

Maybe

Higher-kinded types

Higher-kinded types allow one to express the relationship between two different specializations of the same nominal type within a protocol. For example, if we think of the Self type in a protocol as really being “Self<T>”, it allows us to talk about the relationship between “Self<T>” and “Self” for some other type U. For example, it could allow the “map” operation on a collection to return a collection of the same kind but with a different operation, e.g.,

let intArray: Array<Int> = …
intArray.map { String($0) } // produces Array<String>
let intSet: Set<Int> = …
intSet.map { String($0) } // produces Set<String>

Potential syntax borrowed from one thread on higher-kinded types <https://lists.swift.org/pipermail/swift-evolution/Week-of-Mon-20151214/002736.html> uses ~= as a “similarity” constraint to describe a Functor protocol:

protocol Functor {
associatedtype A
func fmap<FB where FB ~= Self>(f: A -> FB.A) -> FB
}

I don’t think everyday Swift developers will find much use for this feature, but I do think it enables library authors to do some really powerful things with less boilerplate… though your `map` example is actually compelling in and of itself. My own SequenceTypes get map for free, but only the one that returns an array. That’s a bummer.

Specifying type arguments for uses of generic functions

The type arguments of a generic function are always determined via type inference. For example, given:

func f<T>(t: T)

one cannot directly specify T: either one calls “f” (and T is determined via the argument’s type) or one uses “f” in a context where it is given a particular function type (e.g., “let x: (Int) -> Void = f” would infer T = Int). We could permit explicit specialization here, e.g.,

let x = f<Int> // x has type (Int) -> Void

This is one of those annoying little things that can be really helpful and it seems odd that constructors allow specialization but function calls don’t. It’s also a much cleaner way of resolving ambiguity if the compiler is confused.

Potential removals

Associated type inference

Associated type inference is the process by which we infer the type bindings for associated types from other requirements. For example:

protocol IteratorProtocol {
  associatedtype Element
  mutating func next() -> Element?
}

struct IntIterator : IteratorProtocol {
  mutating func next() -> Int? { … } // use this to infer Element = Int
}

Associated type inference is a useful feature. It’s used throughout the standard library, and it helps keep associated types less visible to types that simply want to conform to a protocol. On the other hand, associated type inference is the only place in Swift where we have a global type inference problem: it has historically been a major source of bugs, and implementing it fully and correctly requires a drastically different architecture to the type checker. Is the value of this feature worth keeping global type inference in the Swift language, when we have deliberatively avoided global type inference elsewhere in the language?

I’m totally fine to see it go away. I’ve already gotten into the habit of specifying the types explicitly (due to nonsense errors thrown when the compiler can’t properly infer it). It feels slightly strange because the type inference is spooky action at a distance (especially if the protocol conformance happens in an extension).

Existentials

Existentials aren’t really generics per se, but the two systems are closely intertwined due to their mutable dependence on protocols.

*Generalized existentials

The restrictions on existential types came from an implementation limitation, but it is reasonable to allow a value of protocol type even when the protocol has Self constraints or associated types. For example, consider IteratorProtocol again and how it could be used as an existential:

protocol IteratorProtocol {
associatedtype Element
mutating func next() -> Element?
}

let it: IteratorProtocol = …
it.next() // if this is permitted, it could return an “Any?”, i.e., the existential that wraps the actual element

Additionally, it is reasonable to want to constrain the associated types of an existential, e.g., “a Sequence whose element type is String” could be expressed by putting a where clause into “protocol<…>” or “Any<…>” (per “Renaming protocol<…> to Any<…>”):

let strings: Any<Sequence where .Iterator.Element == String> = [“a”, “b”, “c”]

The leading “.” indicates that we’re talking about the dynamic type, i.e., the “Self” type that’s conforming to the Sequence protocol. There’s no reason why we cannot support arbitrary “where” clauses within the “Any<…>”. This very-general syntax is a bit unwieldy, but common cases can easily be wrapped up in a generic typealias (see the section “Generic typealiases” above):

typealias AnySequence<Element> = Any<Sequence where .Iterator.Element == Element>
let strings: AnySequence<String> = [“a”, “b”, “c”]

Free opinions on the internet are worth what you pay for them, but I’ll just say that if I were in charge of the Swift 3 schedule it wouldn’t ship without this feature. I feel extremely strongly that this is necessary to round out generics support. Trying to write an app that is heavily protocol-oriented and makes use of lots of generics runs into existential (ha!) walls constantly. It forces you to choose 100% anything-goes-dynamic (ala Objective-C) or jump through tons of hoops to get type safety.

Opening existentials

Generalized existentials as described above will still have trouble with protocol requirements that involve Self or associated types in function parameters. For example, let’s try to use Equatable as an existential:

protocol Equatable {
  func ==(lhs: Self, rhs: Self) -> Bool
  func !=(lhs: Self, rhs: Self) -> Bool
}

let e1: Equatable = …
let e2: Equatable = …
if e1 == e2 { … } // error: e1 and e2 don’t necessarily have the same dynamic type

One explicit way to allow such operations in a type-safe manner is to introduce an “open existential” operation of some sort, which extracts and gives a name to the dynamic type stored inside an existential. For example:

if let storedInE1 = e1 openas T { // T is a the type of storedInE1, a copy of the value stored in e1
  if let storedInE2 = e2 as? T { // is e2 also a T?
    if storedInE1 == storedInE2 { … } // okay: storedInT1 and storedInE2 are both of type T, which we know is Equatable
  }
}

Everything on existentials gets a huge +1 from me.

Overall I’d rate conditional conformance, parameterized extensions, and generalized existentials as the highest priority items.

Generalized existentials have no effective workarounds and they have a huge impact on the design of API contracts and even how you use protocols themselves so they are a big pain point for me personally.

Russ

···

On Mar 2, 2016, at 5:22 PM, Douglas Gregor via swift-evolution <swift-evolution@swift.org> wrote:

hartbit · May 2, 2016, 10:58pm

I’d like to continue moving Completing Generics forward for Swift 3 with proposals. Can Douglas, or someone from the core team, tell me if the topics mentioned in Removing unnecessary restrictions require proposals or if bug reports should be opened for them instead?

···

On 03 Mar 2016, at 02:22, Douglas Gregor via swift-evolution <swift-evolution@swift.org> wrote:

Hi all,

Introduction

The “Complete Generics” goal for Swift 3 has been fairly ill-defined thus fair, with just this short blurb in the list of goals:

Complete generics: Generics are used pervasively in a number of Swift libraries, especially the standard library. However, there are a number of generics features the standard library requires to fully realize its vision, including recursive protocol constraints, the ability to make a constrained extension conform to a new protocol (i.e., an array of Equatable elements is Equatable), and so on. Swift 3.0 should provide those generics features needed by the standard library, because they affect the standard library's ABI.
This message expands upon the notion of “completing generics”. It is not a plan for Swift 3, nor an official core team communication, but it collects the results of numerous discussions among the core team and Swift developers, both of the compiler and the standard library. I hope to achieve several things:

Communicate a vision for Swift generics, building on the original generics design document <https://github.com/apple/swift/blob/master/docs/Generics.rst>, so we have something concrete and comprehensive to discuss.
Establish some terminology that the Swift developers have been using for these features, so our discussions can be more productive (“oh, you’re proposing what we refer to as ‘conditional conformances’; go look over at this thread”).
Engage more of the community in discussions of specific generics features, so we can coalesce around designs for public review. And maybe even get some of them implemented.

A message like this can easily turn into a centithread <Urban Dictionary: centithread. To separate concerns in our discussion, I ask that replies to this specific thread be limited to discussions of the vision as a whole: how the pieces fit together, what pieces are missing, whether this is the right long-term vision for Swift, and so on. For discussions of specific language features, e.g., to work out the syntax and semantics of conditional conformances or discuss the implementation in compiler or use in the standard library, please start a new thread based on the feature names I’m using.

This message covers a lot of ground; I’ve attempted a rough categorization of the various features, and kept the descriptions brief to limit the overall length. Most of these aren’t my ideas, and any syntax I’m providing is simply a way to express these ideas in code and is subject to change. Not all of these features will happen, either soon or ever, but they are intended to be a fairly complete whole that should mesh together. I’ve put a * next to features that I think are important in the nearer term vs. being interesting “some day”. Mostly, the *’s reflect features that will have a significant impact on the Swift standard library’s design and implementation.

Enough with the disclaimers; it’s time to talk features.

Removing unnecessary restrictions

There are a number of restrictions to the use of generics that fall out of the implementation in the Swift compiler. Removal of these restrictions is a matter of implementation only; one need not introduce new syntax or semantics to realize them. I’m listing them for two reasons: first, it’s an acknowledgment that these features are intended to exist in the model we have today, and, second, we’d love help with the implementation of these features.

*Recursive protocol constraints

Currently, an associated type cannot be required to conform to its enclosing protocol (or any protocol that inherits that protocol). For example, in the standard library SubSequence type of a Sequence should itself be a Sequence:

protocol Sequence {
 associatedtype Iterator : IteratorProtocol
 …
 associatedtype SubSequence : Sequence // currently ill-formed, but should be possible
}

The compiler currently rejects this protocol, which is unfortunate: it effectively pushes the SubSequence-must-be-a-Sequence requirement into every consumer of SubSequence, and does not communicate the intent of this abstraction well.

Nested generics

Currently, a generic type cannot be nested within another generic type, e.g.

struct X<T> {
 struct Y { } // currently ill-formed, but should be possible
}

There isn’t much to say about this: the compiler simply needs to be improved to handle nested generics throughout.

Concrete same-type requirements

Currently, a constrained extension cannot use a same-type constraint to make a type parameter equivalent to a concrete type. For example:

extension Array where Element == String {
 func makeSentence() -> String {
 // uppercase first string, concatenate with spaces, add a period, whatever
 }
}

This is a highly-requested feature that fits into the existing syntax and semantics. Note that one could imagine introducing new syntax, e.g., extending “Array<String>”, which gets into new-feature territory: see the section on “Parameterized extensions”.

Parameterizing other declarations

There are a number of Swift declarations that currently cannot have generic parameters; some of those have fairly natural extensions to generic forms that maintain their current syntax and semantics, but become more powerful when made generic.

Generic typealiases

Typealiases could be allowed to carry generic parameters. They would still be aliases (i.e., they would not introduce new types). For example:

typealias StringDictionary<Value> = Dictionary<String, Value>

var d1 = StringDictionary<Int>()
var d2: Dictionary<String, Int> = d1 // okay: d1 and d2 have the same type, Dictionary<String, Int>

Generic subscripts

Subscripts could be allowed to have generic parameters. For example, we could introduce a generic subscript on a Collection that allows us to pull out the values at an arbitrary set of indices:

extension Collection {
 subscript<Indices: Sequence where Indices.Iterator.Element == Index>(indices: Indices) -> [Iterator.Element] {
 get {
 var result = [Iterator.Element]()
 for index in indices {
 result.append(self[index])
 }

 return result
 }

 set {
 for (index, value) in zip(indices, newValue) {
 self[index] = value
 }
 }
 }
}

Generic constants

let constants could be allowed to have generic parameters, such that they produce differently-typed values depending on how they are used. For example, this is particularly useful for named literal values, e.g.,

let π<T : FloatLiteralConvertible>: T = 3.141592653589793238462643383279502884197169399

The Clang importer could make particularly good use of this when importing macros.

Parameterized extensions

Extensions themselves could be parameterized, which would allow some structural pattern matching on types. For example, this would permit one to extend an array of optional values, e.g.,

extension<T> Array where Element == T? {
 var someValues: [T] {
 var result = [T]()
 for opt in self {
 if let value = opt { result.append(value) }
 }
 return result
 }
}

We can generalize this to a protocol extensions:

extension<T> Sequence where Element == T? {
 var someValues: [T] {
 var result = [T]()
 for opt in self {
 if let value = opt { result.append(value) }
 }
 return result
 }
}

Note that when one is extending nominal types, we could simplify the syntax somewhat to make the same-type constraint implicit in the syntax:

extension<T> Array<T?> {
 var someValues: [T] {
 var result = [T]()
 for opt in self {
 if let value = opt { result.append(value) }
 }
 return result
 }
}

When we’re working with concrete types, we can use that syntax to improve the extension of concrete versions of generic types (per “Concrete same-type requirements”, above), e.g.,

extension Array<String> {
 func makeSentence() -> String {
 // uppercase first string, concatenate with spaces, add a period, whatever
 }
}

Minor extensions

There are a number of minor extensions we can make to the generics system that don’t fundamentally change what one can express in Swift, but which can improve its expressivity.

*Arbitrary requirements in protocols

Currently, a new protocol can inherit from other protocols, introduce new associated types, and add new conformance constraints to associated types (by redeclaring an associated type from an inherited protocol). However, one cannot express more general constraints. Building on the example from “Recursive protocol constraints”, we really want the element type of a Sequence’s SubSequence to be the same as the element type of the Sequence, e.g.,

protocol Sequence {
 associatedtype Iterator : IteratorProtocol
 …
 associatedtype SubSequence : Sequence where SubSequence.Iterator.Element == Iterator.Element
}

Hanging the where clause off the associated type is protocol not ideal, but that’s a discussion for another thread.

*Typealiases in protocols and protocol extensions

Now that associated types have their own keyword (thanks!), it’s reasonable to bring back “typealias”. Again with the Sequence protocol:

protocol Sequence {
 associatedtype Iterator : IteratorProtocol
 typealias Element = Iterator.Element // rejoice! now we can refer to SomeSequence.Element rather than SomeSequence.Iterator.Element
}

Default generic arguments

Generic parameters could be given the ability to provide default arguments, which would be used in cases where the type argument is not specified and type inference could not determine the type argument. For example:

public final class Promise<Value, Reason=Error> { … }

func getRandomPromise() -> Promise<Int, ErrorProtocol> { … }

var p1: Promise<Int> = …
var p2: Promise<Int, Error> = p1 // okay: p1 and p2 have the same type Promise<Int, Error>
var p3: Promise = getRandomPromise() // p3 has type Promise<Int, ErrorProtocol> due to type inference

Generalized “class” constraints

The “class” constraint can currently only be used for defining protocols. We could generalize it to associated type and type parameter declarations, e.g.,

protocol P {
 associatedtype A : class
}

func foo<T : class>(t: T) { }

As part of this, the magical AnyObject protocol could be replaced with an existential with a class bound, so that it becomes a typealias:

typealias AnyObject = protocol<class>

See the “Existentials” section, particularly “Generalized existentials”, for more information.

*Allowing subclasses to override requirements satisfied by defaults

When a superclass conforms to a protocol and has one of the protocol’s requirements satisfied by a member of a protocol extension, that member currently cannot be overridden by a subclass. For example:

protocol P {
 func foo()
}

extension P {
 func foo() { print(“P”) }
}

class C : P {
 // gets the protocol extension’s
}

class D : C {
 /*override not allowed!*/ func foo() { print(“D”) }
}

let p: P = D()
p.foo() // gotcha: prints “P” rather than “D”!

D.foo should be required to specify “override” and should be called dynamically.

Major extensions to the generics model

Unlike the minor extensions, major extensions to the generics model provide more expressivity in the Swift generics system and, generally, have a much more significant design and implementation cost.

*Conditional conformances

Conditional conformances express the notion that a generic type will conform to a particular protocol only under certain circumstances. For example, Array is Equatable only when its elements are Equatable:

extension Array : Equatable where Element : Equatable { }

func ==<T : Equatable>(lhs: Array<T>, rhs: Array<T>) -> Bool { … }

Conditional conformances are a potentially very powerful feature. One important aspect of this feature is how deal with or avoid overlapping conformances. For example, imagine an adaptor over a Sequence that has conditional conformances to Collection and MutableCollection:

struct SequenceAdaptor<S: Sequence> : Sequence { }
extension SequenceAdaptor : Collection where S: Collection { … }
extension SequenceAdaptor : MutableCollection where S: MutableCollection { }

This should almost certainly be permitted, but we need to cope with or reject “overlapping” conformances:

extension SequenceAdaptor : Collection where S: SomeOtherProtocolSimilarToCollection { } // trouble: two ways for SequenceAdaptor to conform to Collection

See the section on “Private conformances” for more about the issues with having the same type conform to the same protocol multiple times.

Variadic generics

Currently, a generic parameter list contains a fixed number of generic parameters. If one has a type that could generalize to any number of generic parameters, the only real way to deal with it today involves creating a set of types. For example, consider the standard library’s “zip” function. It returns one of these when provided with two arguments to zip together:

public struct Zip2Sequence<Sequence1 : Sequence,
 Sequence2 : Sequence> : Sequence { … }

public func zip<Sequence1 : Sequence, Sequence2 : Sequence>(
 sequence1: Sequence1, _ sequence2: Sequence2)
 -> Zip2Sequence<Sequence1, Sequence2> { … }

Supporting three arguments would require copy-paste of those of those:

public struct Zip3Sequence<Sequence1 : Sequence,
 Sequence2 : Sequence,
 Sequence3 : Sequence> : Sequence { … }

public func zip<Sequence1 : Sequence, Sequence2 : Sequence, Sequence3 : Sequence>(
 sequence1: Sequence1, _ sequence2: Sequence2, _ sequence3: sequence3)
 -> Zip3Sequence<Sequence1, Sequence2, Sequence3> { … }

Variadic generics would allow us to abstract over a set of generic parameters. The syntax below is hopelessly influenced by C++11 variadic templates <http://www.jot.fm/issues/issue_2008_02/article2/> (sorry), where putting an ellipsis (“…”) to the left of a declaration makes it a “parameter pack” containing zero or more parameters and putting an ellipsis to the right of a type/expression/etc. expands the parameter packs within that type/expression into separate arguments. The important part is that we be able to meaningfully abstract over zero or more generic parameters, e.g.:

public struct ZipIterator<... Iterators : IteratorProtocol> : Iterator { // zero or more type parameters, each of which conforms to IteratorProtocol
 public typealias Element = (Iterators.Element...) // a tuple containing the element types of each iterator in Iterators

 var (...iterators): (Iterators...) // zero or more stored properties, one for each type in Iterators
 var reachedEnd: Bool = false

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

 guard let values = (iterators.next()...) { // call “next” on each of the iterators, put the results into a tuple named “values"
 reachedEnd = true
 return nil
 }

 return values
 }
}

public struct ZipSequence<...Sequences : Sequence> : Sequence {
 public typealias Iterator = ZipIterator<Sequences.Iterator...> // get the zip iterator with the iterator types of our Sequences

 var (...sequences): (Sequences...) // zero or more stored properties, one for each type in Sequences

 // details ...
}

Such a design could also work for function parameters, so we can pack together multiple function arguments with different types, e.g.,

public func zip<... Sequences : SequenceType>(... sequences: Sequences...)
 -> ZipSequence<Sequences...> {
 return ZipSequence(sequences...)
}

Finally, this could tie into the discussions about a tuple “splat” operator. For example:

func apply<... Args, Result>(fn: (Args...) -> Result, // function taking some number of arguments and producing Result
 args: (Args...)) -> Result { // tuple of arguments
 return fn(args...) // expand the arguments in the tuple “args” into separate arguments
}

Extensions of structural types

Currently, only nominal types (classes, structs, enums, protocols) can be extended. One could imagine extending structural types—particularly tuple types—to allow them to, e.g., conform to protocols. For example, pulling together variadic generics, parameterized extensions, and conditional conformances, one could express “a tuple type is Equatable if all of its element types are Equatable”:

extension<...Elements : Equatable> (Elements...) : Equatable { // extending the tuple type “(Elements…)” to be Equatable
}

There are some natural bounds here: one would need to have actual structural types. One would not be able to extend every type:

extension<T> T { // error: neither a structural nor a nominal type
}

And before you think you’re cleverly making it possible to have a conditional conformance that makes every type T that conforms to protocol P also conform to protocol Q, see the section "Conditional conformances via protocol extensions”, below:

extension<T : P> T : Q { // error: neither a structural nor a nominal type
}

Syntactic improvements

There are a number of potential improvements we could make to the generics syntax. Such a list could go on for a very long time, so I’ll only highlight some obvious ones that have been discussed by the Swift developers.

*Default implementations in protocols

Currently, protocol members can never have implementations. We could allow one to provide such implementations to be used as the default if a conforming type does not supply an implementation, e.g.,

protocol Bag {
 associatedtype Element : Equatable
 func contains(element: Element) -> Bool

 func containsAll<S: Sequence where Sequence.Iterator.Element == Element>(elements: S) -> Bool {
 for x in elements {
 if contains(x) { return true }
 }
 return false
 }
}

struct IntBag : Bag {
 typealias Element = Int
 func contains(element: Int) -> Bool { ... }

 // okay: containsAll requirement is satisfied by Bag’s default implementation
}

One can get this effect with protocol extensions today, hence the classification of this feature as a (mostly) syntactic improvement:

protocol Bag {
 associatedtype Element : Equatable
 func contains(element: Element) -> Bool

 func containsAll<S: Sequence where Sequence.Iterator.Element == Element>(elements: S) -> Bool
}

extension Bag {
 func containsAll<S: Sequence where Sequence.Iterator.Element == Element>(elements: S) -> Bool {
 for x in elements {
 if contains(x) { return true }
 }
 return false
 }
}

*Moving the where clause outside of the angle brackets

The “where” clause of generic functions comes very early in the declaration, although it is generally of much less concern to the client than the function parameters and result type that follow it. This is one of the things that contributes to “angle bracket blindness”. For example, consider the containsAll signature above:

func containsAll<S: Sequence where Sequence.Iterator.Element == Element>(elements: S) -> Bool

One could move the “where” clause to the end of the signature, so that the most important parts—name, generic parameter, parameters, result type—precede it:

func containsAll<S: Sequence>(elements: S) -> Bool
 where Sequence.Iterator.Element == Element

*Renaming “protocol<…>” to “Any<…>”.

The “protocol<…>” syntax is a bit of an oddity in Swift. It is used to compose protocols together, mostly to create values of existential type, e.g.,

var x: protocol<NSCoding, NSCopying>

It’s weird that it’s a type name that starts with a lowercase letter, and most Swift developers probably never deal with this feature unless they happen to look at the definition of Any:

typealias Any = protocol<>

“Any” might be a better name for this functionality. “Any” without brackets could be a keyword for “any type”, and “Any” followed by brackets could take the role of “protocol<>” today:

var x: Any<NSCoding, NSCopying>

That reads much better: “Any type that conforms to NSCoding and NSCopying”. See the section "Generalized existentials” for additional features in this space.

Maybe

There are a number of features that get discussed from time-to-time, while they could fit into Swift’s generics system, it’s not clear that they belong in Swift at all. The important question for any feature in this category is not “can it be done” or “are there cool things we can express”, but “how can everyday Swift developers benefit from the addition of such a feature?”. Without strong motivating examples, none of these “maybes” will move further along.

Dynamic dispatch for members of protocol extensions

Only the requirements of protocols currently use dynamic dispatch, which can lead to surprises:

protocol P {
 func foo()
}

extension P {
 func foo() { print(“P.foo()”)
 func bar() { print(“P.bar()”)
}

struct X : P {
 func foo() { print(“X.foo()”)
 func bar() { print(“X.bar()”)
}

let x = X()
x.foo() // X.foo()
x.bar() // X.bar()

let p: P = X()
p.foo() // X.foo()
p.bar() // P.bar()

Swift could adopt a model where members of protocol extensions are dynamically dispatched.

Named generic parameters

When specifying generic arguments for a generic type, the arguments are always positional: Dictionary<String, Int> is a Dictionary whose Key type is String and whose Value type is Int, by convention. One could permit the arguments to be labeled, e.g.,

var d: Dictionary<Key: String, Value: Int>

Such a feature makes more sense if Swift gains default generic arguments, because generic argument labels would allow one to skip defaulted arguments.

Generic value parameters

Currently, Swift’s generic parameters are always types. One could imagine allowing generic parameters that are values, e.g.,

struct MultiArray<T, let Dimensions: Int> { // specify the number of dimensions to the array
 subscript (indices: Int...) -> T {
 get {
 require(indices.count == Dimensions)
 // ...
 }
}

A suitably general feature might allow us to express fixed-length array or vector types as a standard library component, and perhaps also allow one to implement a useful dimensional analysis library. Tackling this feature potentially means determining what it is for an expression to be a “constant expression” and diving into dependent-typing, hence the “maybe”.

Higher-kinded types

Higher-kinded types allow one to express the relationship between two different specializations of the same nominal type within a protocol. For example, if we think of the Self type in a protocol as really being “Self<T>”, it allows us to talk about the relationship between “Self<T>” and “Self” for some other type U. For example, it could allow the “map” operation on a collection to return a collection of the same kind but with a different operation, e.g.,

let intArray: Array<Int> = …
intArray.map { String($0) } // produces Array<String>
let intSet: Set<Int> = …
intSet.map { String($0) } // produces Set<String>

Potential syntax borrowed from one thread on higher-kinded types <https://lists.swift.org/pipermail/swift-evolution/Week-of-Mon-20151214/002736.html> uses ~= as a “similarity” constraint to describe a Functor protocol:

protocol Functor {
 associatedtype A
 func fmap<FB where FB ~= Self>(f: A -> FB.A) -> FB
}

Specifying type arguments for uses of generic functions

The type arguments of a generic function are always determined via type inference. For example, given:

func f<T>(t: T)

one cannot directly specify T: either one calls “f” (and T is determined via the argument’s type) or one uses “f” in a context where it is given a particular function type (e.g., “let x: (Int) -> Void = f” would infer T = Int). We could permit explicit specialization here, e.g.,

let x = f<Int> // x has type (Int) -> Void

Unlikely

Features in this category have been requested at various times, but they don’t fit well with Swift’s generics system because they cause some part of the model to become overly complicated, have unacceptable implementation limitations, or overlap significantly with existing features.

Generic protocols

One of the most commonly requested features is the ability to parameterize protocols themselves. For example, a protocol that indicates that the Self type can be constructed from some specified type T:

protocol ConstructibleFromValue<T> {
 init(_ value: T)
}

Implicit in this feature is the ability for a given type to conform to the protocol in two different ways. A “Real” type might be constructible from both Float and Double, e.g.,

struct Real { … }
extension Real : ConstructibleFrom<Float> {
 init(_ value: Float) { … }
}
extension Real : ConstructibleFrom<Double> {
 init(_ value: Double) { … }
}

Most of the requests for this feature actually want a different feature. They tend to use a parameterized Sequence as an example, e.g.,

protocol Sequence<Element> { … }

func foo(strings: Sequence<String>) { /// works on any sequence containing Strings
 // ...
}

The actual requested feature here is the ability to say “Any type that conforms to Sequence whose Element type is String”, which is covered by the section on “Generalized existentials”, below.

More importantly, modeling Sequence with generic parameters rather than associated types is tantalizing but wrong: you don’t want a type conforming to Sequence in multiple ways, or (among other things) your for..in loops stop working, and you lose the ability to dynamically cast down to an existential “Sequence” without binding the Element type (again, see “Generalized existentials”). Use cases similar to the ConstructibleFromValue protocol above seem too few to justify the potential for confusion between associated types and generic parameters of protocols; we’re better off not having the latter.

Private conformances

Right now, a protocol conformance can be no less visible than the minimum of the conforming type’s access and the protocol’s access. Therefore, a public type conforming to a public protocol must provide the conformance publicly. One could imagine removing that restriction, so that one could introduce a private conformance:

public protocol P { }
public struct X { }
extension X : internal P { … } // X conforms to P, but only within this module

The main problem with private conformances is the interaction with dynamic casting. If I have this code:

func foo(value: Any) {
 if let x = value as? P { print(“P”) }
}

foo(X())

Under what circumstances should it print “P”? If foo() is defined within the same module as the conformance of X to P? If the call is defined within the same module as the conformance of X to P? Never? Either of the first two answers requires significant complications in the dynamic casting infrastructure to take into account the module in which a particular dynamic cast occurred (the first option) or where an existential was formed (the second option), while the third answer breaks the link between the static and dynamic type systems—none of which is an acceptable result.

Conditional conformances via protocol extensions

We often get requests to make a protocol conform to another protocol. This is, effectively, the expansion of the notion of “Conditional conformances” to protocol extensions. For example:

protocol P {
 func foo()
}

protocol Q {
 func bar()
}

extension Q : P { // every type that conforms to Q also conforms to P
 func foo() { // implement “foo” requirement in terms of “bar"
 bar()
 }
}

func f<T: P>(t: T) { … }

struct X : Q {
 func bar() { … }
}

f(X()) // okay: X conforms to P through the conformance of Q to P

This is an extremely powerful feature: is allows one to map the abstractions of one domain into another domain (e.g., every Matrix is a Graph). However, similar to private conformances, it puts a major burden on the dynamic-casting runtime to chase down arbitrarily long and potentially cyclic chains of conformances, which makes efficient implementation nearly impossible.

Potential removals

The generics system doesn’t seem like a good candidate for a reduction in scope; most of its features do get used fairly pervasively in the standard library, and few feel overly anachronistic. However...

Associated type inference

Associated type inference is the process by which we infer the type bindings for associated types from other requirements. For example:

protocol IteratorProtocol {
 associatedtype Element
 mutating func next() -> Element?
}

struct IntIterator : IteratorProtocol {
 mutating func next() -> Int? { … } // use this to infer Element = Int
}

Associated type inference is a useful feature. It’s used throughout the standard library, and it helps keep associated types less visible to types that simply want to conform to a protocol. On the other hand, associated type inference is the only place in Swift where we have a global type inference problem: it has historically been a major source of bugs, and implementing it fully and correctly requires a drastically different architecture to the type checker. Is the value of this feature worth keeping global type inference in the Swift language, when we have deliberatively avoided global type inference elsewhere in the language?

Existentials

Existentials aren’t really generics per se, but the two systems are closely intertwined due to their mutable dependence on protocols.

*Generalized existentials

The restrictions on existential types came from an implementation limitation, but it is reasonable to allow a value of protocol type even when the protocol has Self constraints or associated types. For example, consider IteratorProtocol again and how it could be used as an existential:

protocol IteratorProtocol {
 associatedtype Element
 mutating func next() -> Element?
}

let it: IteratorProtocol = …
it.next() // if this is permitted, it could return an “Any?”, i.e., the existential that wraps the actual element

Additionally, it is reasonable to want to constrain the associated types of an existential, e.g., “a Sequence whose element type is String” could be expressed by putting a where clause into “protocol<…>” or “Any<…>” (per “Renaming protocol<…> to Any<…>”):

let strings: Any<Sequence where .Iterator.Element == String> = [“a”, “b”, “c”]

The leading “.” indicates that we’re talking about the dynamic type, i.e., the “Self” type that’s conforming to the Sequence protocol. There’s no reason why we cannot support arbitrary “where” clauses within the “Any<…>”. This very-general syntax is a bit unwieldy, but common cases can easily be wrapped up in a generic typealias (see the section “Generic typealiases” above):

typealias AnySequence<Element> = Any<Sequence where .Iterator.Element == Element>
let strings: AnySequence<String> = [“a”, “b”, “c”]

Opening existentials

Generalized existentials as described above will still have trouble with protocol requirements that involve Self or associated types in function parameters. For example, let’s try to use Equatable as an existential:

protocol Equatable {
 func ==(lhs: Self, rhs: Self) -> Bool
 func !=(lhs: Self, rhs: Self) -> Bool
}

let e1: Equatable = …
let e2: Equatable = …
if e1 == e2 { … } // error: e1 and e2 don’t necessarily have the same dynamic type

One explicit way to allow such operations in a type-safe manner is to introduce an “open existential” operation of some sort, which extracts and gives a name to the dynamic type stored inside an existential. For example:

if let storedInE1 = e1 openas T { // T is a the type of storedInE1, a copy of the value stored in e1
 if let storedInE2 = e2 as? T { // is e2 also a T?
 if storedInE1 == storedInE2 { … } // okay: storedInT1 and storedInE2 are both of type T, which we know is Equatable
 }
}

Thoughts?

 - Doug

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Joe_Groff · March 3, 2016, 2:06am

…and along similar lines, you might also want to extend an existential type to conform to itself (or other protocols) when it doesn't naturally do so by type erasure. For instance, the `Any*Collection` want to type-erase their contained collection's associated Index type; this is statically unsound since the Index requirement in Collection is contravariant, but is allowed by the dynamic semantics of Index, which require as a precondition that indexes only be applied to their originating collection. There's also our oft-lamented inability to have heterogeneous Sets of protocol type; if you could extend an existential to conform to Hashable, instead of forcing the protocol to refine Hashable, that would give you the ability to use it with Set in the obvious way.

-Joe

···

On Mar 2, 2016, at 5:50 PM, Joe Groff via swift-evolution <swift-evolution@swift.org> wrote:

If protocols are namespaced separately from types, you could still do something like:

typealias Drawable: Drawable = Any<Drawable>

if you intend to use the protocol type primarily as a dynamic type (and assert that it's self-conforming).

Joe_Groff · March 3, 2016, 4:19am

Hi all,

Introduction

The “Complete Generics” goal for Swift 3 has been fairly ill-defined thus fair, with just this short blurb in the list of goals:

Complete generics: Generics are used pervasively in a number of Swift libraries, especially the standard library. However, there are a number of generics features the standard library requires to fully realize its vision, including recursive protocol constraints, the ability to make a constrained extension conform to a new protocol (i.e., an array of Equatable elements is Equatable), and so on. Swift 3.0 should provide those generics features needed by the standard library, because they affect the standard library's ABI.
This message expands upon the notion of “completing generics”. It is not a plan for Swift 3, nor an official core team communication, but it collects the results of numerous discussions among the core team and Swift developers, both of the compiler and the standard library. I hope to achieve several things:

Communicate a vision for Swift generics, building on the original generics design document <https://github.com/apple/swift/blob/master/docs/Generics.rst>, so we have something concrete and comprehensive to discuss.
Establish some terminology that the Swift developers have been using for these features, so our discussions can be more productive (“oh, you’re proposing what we refer to as ‘conditional conformances’; go look over at this thread”).
Engage more of the community in discussions of specific generics features, so we can coalesce around designs for public review. And maybe even get some of them implemented.

A message like this can easily turn into a centithread <Urban Dictionary: centithread. To separate concerns in our discussion, I ask that replies to this specific thread be limited to discussions of the vision as a whole: how the pieces fit together, what pieces are missing, whether this is the right long-term vision for Swift, and so on. For discussions of specific language features, e.g., to work out the syntax and semantics of conditional conformances or discuss the implementation in compiler or use in the standard library, please start a new thread based on the feature names I’m using.

This message covers a lot of ground; I’ve attempted a rough categorization of the various features, and kept the descriptions brief to limit the overall length. Most of these aren’t my ideas, and any syntax I’m providing is simply a way to express these ideas in code and is subject to change. Not all of these features will happen, either soon or ever, but they are intended to be a fairly complete whole that should mesh together. I’ve put a * next to features that I think are important in the nearer term vs. being interesting “some day”. Mostly, the *’s reflect features that will have a significant impact on the Swift standard library’s design and implementation.

Enough with the disclaimers; it’s time to talk features.

Removing unnecessary restrictions

There are a number of restrictions to the use of generics that fall out of the implementation in the Swift compiler. Removal of these restrictions is a matter of implementation only; one need not introduce new syntax or semantics to realize them. I’m listing them for two reasons: first, it’s an acknowledgment that these features are intended to exist in the model we have today, and, second, we’d love help with the implementation of these features.

*Recursive protocol constraints

Currently, an associated type cannot be required to conform to its enclosing protocol (or any protocol that inherits that protocol). For example, in the standard library SubSequence type of a Sequence should itself be a Sequence:

protocol Sequence {
 associatedtype Iterator : IteratorProtocol
 …
 associatedtype SubSequence : Sequence // currently ill-formed, but should be possible
}

The compiler currently rejects this protocol, which is unfortunate: it effectively pushes the SubSequence-must-be-a-Sequence requirement into every consumer of SubSequence, and does not communicate the intent of this abstraction well.

Nested generics

Currently, a generic type cannot be nested within another generic type, e.g.

struct X<T> {
 struct Y { } // currently ill-formed, but should be possible
}

There isn’t much to say about this: the compiler simply needs to be improved to handle nested generics throughout.

Concrete same-type requirements

Currently, a constrained extension cannot use a same-type constraint to make a type parameter equivalent to a concrete type. For example:

extension Array where Element == String {
 func makeSentence() -> String {
 // uppercase first string, concatenate with spaces, add a period, whatever
 }
}

This is a highly-requested feature that fits into the existing syntax and semantics. Note that one could imagine introducing new syntax, e.g., extending “Array<String>”, which gets into new-feature territory: see the section on “Parameterized extensions”.

Parameterizing other declarations

There are a number of Swift declarations that currently cannot have generic parameters; some of those have fairly natural extensions to generic forms that maintain their current syntax and semantics, but become more powerful when made generic.

Generic typealiases

Typealiases could be allowed to carry generic parameters. They would still be aliases (i.e., they would not introduce new types). For example:

typealias StringDictionary<Value> = Dictionary<String, Value>

var d1 = StringDictionary<Int>()
var d2: Dictionary<String, Int> = d1 // okay: d1 and d2 have the same type, Dictionary<String, Int>

Generic subscripts

Subscripts could be allowed to have generic parameters. For example, we could introduce a generic subscript on a Collection that allows us to pull out the values at an arbitrary set of indices:

extension Collection {
 subscript<Indices: Sequence where Indices.Iterator.Element == Index>(indices: Indices) -> [Iterator.Element] {
 get {
 var result = [Iterator.Element]()
 for index in indices {
 result.append(self[index])
 }

 return result
 }

 set {
 for (index, value) in zip(indices, newValue) {
 self[index] = value
 }
 }
 }
}

Generic constants

let constants could be allowed to have generic parameters, such that they produce differently-typed values depending on how they are used. For example, this is particularly useful for named literal values, e.g.,

let π<T : FloatLiteralConvertible>: T = 3.141592653589793238462643383279502884197169399

The Clang importer could make particularly good use of this when importing macros.

Parameterized extensions

Extensions themselves could be parameterized, which would allow some structural pattern matching on types. For example, this would permit one to extend an array of optional values, e.g.,

extension<T> Array where Element == T? {
 var someValues: [T] {
 var result = [T]()
 for opt in self {
 if let value = opt { result.append(value) }
 }
 return result
 }
}

We can generalize this to a protocol extensions:

extension<T> Sequence where Element == T? {
 var someValues: [T] {
 var result = [T]()
 for opt in self {
 if let value = opt { result.append(value) }
 }
 return result
 }
}

Note that when one is extending nominal types, we could simplify the syntax somewhat to make the same-type constraint implicit in the syntax:

extension<T> Array<T?> {
 var someValues: [T] {
 var result = [T]()
 for opt in self {
 if let value = opt { result.append(value) }
 }
 return result
 }
}

When we’re working with concrete types, we can use that syntax to improve the extension of concrete versions of generic types (per “Concrete same-type requirements”, above), e.g.,

extension Array<String> {
 func makeSentence() -> String {
 // uppercase first string, concatenate with spaces, add a period, whatever
 }
}

Minor extensions

There are a number of minor extensions we can make to the generics system that don’t fundamentally change what one can express in Swift, but which can improve its expressivity.

*Arbitrary requirements in protocols

Currently, a new protocol can inherit from other protocols, introduce new associated types, and add new conformance constraints to associated types (by redeclaring an associated type from an inherited protocol). However, one cannot express more general constraints. Building on the example from “Recursive protocol constraints”, we really want the element type of a Sequence’s SubSequence to be the same as the element type of the Sequence, e.g.,

protocol Sequence {
 associatedtype Iterator : IteratorProtocol
 …
 associatedtype SubSequence : Sequence where SubSequence.Iterator.Element == Iterator.Element
}

Hanging the where clause off the associated type is protocol not ideal, but that’s a discussion for another thread.

*Typealiases in protocols and protocol extensions

Now that associated types have their own keyword (thanks!), it’s reasonable to bring back “typealias”. Again with the Sequence protocol:

protocol Sequence {
 associatedtype Iterator : IteratorProtocol
 typealias Element = Iterator.Element // rejoice! now we can refer to SomeSequence.Element rather than SomeSequence.Iterator.Element
}

Default generic arguments

Generic parameters could be given the ability to provide default arguments, which would be used in cases where the type argument is not specified and type inference could not determine the type argument. For example:

public final class Promise<Value, Reason=Error> { … }

func getRandomPromise() -> Promise<Int, ErrorProtocol> { … }

var p1: Promise<Int> = …
var p2: Promise<Int, Error> = p1 // okay: p1 and p2 have the same type Promise<Int, Error>
var p3: Promise = getRandomPromise() // p3 has type Promise<Int, ErrorProtocol> due to type inference

Generalized “class” constraints

The “class” constraint can currently only be used for defining protocols. We could generalize it to associated type and type parameter declarations, e.g.,

protocol P {
 associatedtype A : class
}

func foo<T : class>(t: T) { }

As part of this, the magical AnyObject protocol could be replaced with an existential with a class bound, so that it becomes a typealias:

typealias AnyObject = protocol<class>

See the “Existentials” section, particularly “Generalized existentials”, for more information.

*Allowing subclasses to override requirements satisfied by defaults

When a superclass conforms to a protocol and has one of the protocol’s requirements satisfied by a member of a protocol extension, that member currently cannot be overridden by a subclass. For example:

protocol P {
 func foo()
}

extension P {
 func foo() { print(“P”) }
}

class C : P {
 // gets the protocol extension’s
}

class D : C {
 /*override not allowed!*/ func foo() { print(“D”) }
}

let p: P = D()
p.foo() // gotcha: prints “P” rather than “D”!

D.foo should be required to specify “override” and should be called dynamically.

Major extensions to the generics model

Unlike the minor extensions, major extensions to the generics model provide more expressivity in the Swift generics system and, generally, have a much more significant design and implementation cost.

*Conditional conformances

Conditional conformances express the notion that a generic type will conform to a particular protocol only under certain circumstances. For example, Array is Equatable only when its elements are Equatable:

extension Array : Equatable where Element : Equatable { }

func ==<T : Equatable>(lhs: Array<T>, rhs: Array<T>) -> Bool { … }

Conditional conformances are a potentially very powerful feature. One important aspect of this feature is how deal with or avoid overlapping conformances. For example, imagine an adaptor over a Sequence that has conditional conformances to Collection and MutableCollection:

struct SequenceAdaptor<S: Sequence> : Sequence { }
extension SequenceAdaptor : Collection where S: Collection { … }
extension SequenceAdaptor : MutableCollection where S: MutableCollection { }

This should almost certainly be permitted, but we need to cope with or reject “overlapping” conformances:

extension SequenceAdaptor : Collection where S: SomeOtherProtocolSimilarToCollection { } // trouble: two ways for SequenceAdaptor to conform to Collection

See the section on “Private conformances” for more about the issues with having the same type conform to the same protocol multiple times.

Variadic generics

Currently, a generic parameter list contains a fixed number of generic parameters. If one has a type that could generalize to any number of generic parameters, the only real way to deal with it today involves creating a set of types. For example, consider the standard library’s “zip” function. It returns one of these when provided with two arguments to zip together:

public struct Zip2Sequence<Sequence1 : Sequence,
 Sequence2 : Sequence> : Sequence { … }

public func zip<Sequence1 : Sequence, Sequence2 : Sequence>(
 sequence1: Sequence1, _ sequence2: Sequence2)
 -> Zip2Sequence<Sequence1, Sequence2> { … }

Supporting three arguments would require copy-paste of those of those:

public struct Zip3Sequence<Sequence1 : Sequence,
 Sequence2 : Sequence,
 Sequence3 : Sequence> : Sequence { … }

public func zip<Sequence1 : Sequence, Sequence2 : Sequence, Sequence3 : Sequence>(
 sequence1: Sequence1, _ sequence2: Sequence2, _ sequence3: sequence3)
 -> Zip3Sequence<Sequence1, Sequence2, Sequence3> { … }

Variadic generics would allow us to abstract over a set of generic parameters. The syntax below is hopelessly influenced by C++11 variadic templates <http://www.jot.fm/issues/issue_2008_02/article2/> (sorry), where putting an ellipsis (“…”) to the left of a declaration makes it a “parameter pack” containing zero or more parameters and putting an ellipsis to the right of a type/expression/etc. expands the parameter packs within that type/expression into separate arguments. The important part is that we be able to meaningfully abstract over zero or more generic parameters, e.g.:

public struct ZipIterator<... Iterators : IteratorProtocol> : Iterator { // zero or more type parameters, each of which conforms to IteratorProtocol
 public typealias Element = (Iterators.Element...) // a tuple containing the element types of each iterator in Iterators

 var (...iterators): (Iterators...) // zero or more stored properties, one for each type in Iterators
 var reachedEnd: Bool = false

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

 guard let values = (iterators.next()...) { // call “next” on each of the iterators, put the results into a tuple named “values"
 reachedEnd = true
 return nil
 }

 return values
 }
}

public struct ZipSequence<...Sequences : Sequence> : Sequence {
 public typealias Iterator = ZipIterator<Sequences.Iterator...> // get the zip iterator with the iterator types of our Sequences

 var (...sequences): (Sequences...) // zero or more stored properties, one for each type in Sequences

 // details ...
}

Such a design could also work for function parameters, so we can pack together multiple function arguments with different types, e.g.,

public func zip<... Sequences : SequenceType>(... sequences: Sequences...)
 -> ZipSequence<Sequences...> {
 return ZipSequence(sequences...)
}

Finally, this could tie into the discussions about a tuple “splat” operator. For example:

func apply<... Args, Result>(fn: (Args...) -> Result, // function taking some number of arguments and producing Result
 args: (Args...)) -> Result { // tuple of arguments
 return fn(args...) // expand the arguments in the tuple “args” into separate arguments
}

Extensions of structural types

Currently, only nominal types (classes, structs, enums, protocols) can be extended. One could imagine extending structural types—particularly tuple types—to allow them to, e.g., conform to protocols. For example, pulling together variadic generics, parameterized extensions, and conditional conformances, one could express “a tuple type is Equatable if all of its element types are Equatable”:

extension<...Elements : Equatable> (Elements...) : Equatable { // extending the tuple type “(Elements…)” to be Equatable
}

There are some natural bounds here: one would need to have actual structural types. One would not be able to extend every type:

extension<T> T { // error: neither a structural nor a nominal type
}

And before you think you’re cleverly making it possible to have a conditional conformance that makes every type T that conforms to protocol P also conform to protocol Q, see the section "Conditional conformances via protocol extensions”, below:

extension<T : P> T : Q { // error: neither a structural nor a nominal type
}

Syntactic improvements

There are a number of potential improvements we could make to the generics syntax. Such a list could go on for a very long time, so I’ll only highlight some obvious ones that have been discussed by the Swift developers.

*Default implementations in protocols

Currently, protocol members can never have implementations. We could allow one to provide such implementations to be used as the default if a conforming type does not supply an implementation, e.g.,

protocol Bag {
 associatedtype Element : Equatable
 func contains(element: Element) -> Bool

 func containsAll<S: Sequence where Sequence.Iterator.Element == Element>(elements: S) -> Bool {
 for x in elements {
 if contains(x) { return true }
 }
 return false
 }
}

struct IntBag : Bag {
 typealias Element = Int
 func contains(element: Int) -> Bool { ... }

 // okay: containsAll requirement is satisfied by Bag’s default implementation
}

One can get this effect with protocol extensions today, hence the classification of this feature as a (mostly) syntactic improvement:

protocol Bag {
 associatedtype Element : Equatable
 func contains(element: Element) -> Bool

 func containsAll<S: Sequence where Sequence.Iterator.Element == Element>(elements: S) -> Bool
}

extension Bag {
 func containsAll<S: Sequence where Sequence.Iterator.Element == Element>(elements: S) -> Bool {
 for x in elements {
 if contains(x) { return true }
 }
 return false
 }
}

*Moving the where clause outside of the angle brackets

The “where” clause of generic functions comes very early in the declaration, although it is generally of much less concern to the client than the function parameters and result type that follow it. This is one of the things that contributes to “angle bracket blindness”. For example, consider the containsAll signature above:

func containsAll<S: Sequence where Sequence.Iterator.Element == Element>(elements: S) -> Bool

One could move the “where” clause to the end of the signature, so that the most important parts—name, generic parameter, parameters, result type—precede it:

func containsAll<S: Sequence>(elements: S) -> Bool
 where Sequence.Iterator.Element == Element

*Renaming “protocol<…>” to “Any<…>”.

The “protocol<…>” syntax is a bit of an oddity in Swift. It is used to compose protocols together, mostly to create values of existential type, e.g.,

var x: protocol<NSCoding, NSCopying>

It’s weird that it’s a type name that starts with a lowercase letter, and most Swift developers probably never deal with this feature unless they happen to look at the definition of Any:

typealias Any = protocol<>

“Any” might be a better name for this functionality. “Any” without brackets could be a keyword for “any type”, and “Any” followed by brackets could take the role of “protocol<>” today:

var x: Any<NSCoding, NSCopying>

That reads much better: “Any type that conforms to NSCoding and NSCopying”. See the section "Generalized existentials” for additional features in this space.

Maybe

There are a number of features that get discussed from time-to-time, while they could fit into Swift’s generics system, it’s not clear that they belong in Swift at all. The important question for any feature in this category is not “can it be done” or “are there cool things we can express”, but “how can everyday Swift developers benefit from the addition of such a feature?”. Without strong motivating examples, none of these “maybes” will move further along.

Dynamic dispatch for members of protocol extensions

Only the requirements of protocols currently use dynamic dispatch, which can lead to surprises:

protocol P {
 func foo()
}

extension P {
 func foo() { print(“P.foo()”)
 func bar() { print(“P.bar()”)
}

struct X : P {
 func foo() { print(“X.foo()”)
 func bar() { print(“X.bar()”)
}

let x = X()
x.foo() // X.foo()
x.bar() // X.bar()

let p: P = X()
p.foo() // X.foo()
p.bar() // P.bar()

Swift could adopt a model where members of protocol extensions are dynamically dispatched.

Named generic parameters

When specifying generic arguments for a generic type, the arguments are always positional: Dictionary<String, Int> is a Dictionary whose Key type is String and whose Value type is Int, by convention. One could permit the arguments to be labeled, e.g.,

var d: Dictionary<Key: String, Value: Int>

Such a feature makes more sense if Swift gains default generic arguments, because generic argument labels would allow one to skip defaulted arguments.

Generic value parameters

Currently, Swift’s generic parameters are always types. One could imagine allowing generic parameters that are values, e.g.,

struct MultiArray<T, let Dimensions: Int> { // specify the number of dimensions to the array
 subscript (indices: Int...) -> T {
 get {
 require(indices.count == Dimensions)
 // ...
 }
}

A suitably general feature might allow us to express fixed-length array or vector types as a standard library component, and perhaps also allow one to implement a useful dimensional analysis library. Tackling this feature potentially means determining what it is for an expression to be a “constant expression” and diving into dependent-typing, hence the “maybe”.

Higher-kinded types

Higher-kinded types allow one to express the relationship between two different specializations of the same nominal type within a protocol. For example, if we think of the Self type in a protocol as really being “Self<T>”, it allows us to talk about the relationship between “Self<T>” and “Self” for some other type U. For example, it could allow the “map” operation on a collection to return a collection of the same kind but with a different operation, e.g.,

let intArray: Array<Int> = …
intArray.map { String($0) } // produces Array<String>
let intSet: Set<Int> = …
intSet.map { String($0) } // produces Set<String>

Potential syntax borrowed from one thread on higher-kinded types <https://lists.swift.org/pipermail/swift-evolution/Week-of-Mon-20151214/002736.html> uses ~= as a “similarity” constraint to describe a Functor protocol:

protocol Functor {
 associatedtype A
 func fmap<FB where FB ~= Self>(f: A -> FB.A) -> FB
}

Specifying type arguments for uses of generic functions

The type arguments of a generic function are always determined via type inference. For example, given:

func f<T>(t: T)

one cannot directly specify T: either one calls “f” (and T is determined via the argument’s type) or one uses “f” in a context where it is given a particular function type (e.g., “let x: (Int) -> Void = f” would infer T = Int). We could permit explicit specialization here, e.g.,

let x = f<Int> // x has type (Int) -> Void

Unlikely

Features in this category have been requested at various times, but they don’t fit well with Swift’s generics system because they cause some part of the model to become overly complicated, have unacceptable implementation limitations, or overlap significantly with existing features.

Generic protocols

One of the most commonly requested features is the ability to parameterize protocols themselves. For example, a protocol that indicates that the Self type can be constructed from some specified type T:

protocol ConstructibleFromValue<T> {
 init(_ value: T)
}

Implicit in this feature is the ability for a given type to conform to the protocol in two different ways. A “Real” type might be constructible from both Float and Double, e.g.,

struct Real { … }
extension Real : ConstructibleFrom<Float> {
 init(_ value: Float) { … }
}
extension Real : ConstructibleFrom<Double> {
 init(_ value: Double) { … }
}

Most of the requests for this feature actually want a different feature. They tend to use a parameterized Sequence as an example, e.g.,

protocol Sequence<Element> { … }

func foo(strings: Sequence<String>) { /// works on any sequence containing Strings
 // ...
}

The actual requested feature here is the ability to say “Any type that conforms to Sequence whose Element type is String”, which is covered by the section on “Generalized existentials”, below.

More importantly, modeling Sequence with generic parameters rather than associated types is tantalizing but wrong: you don’t want a type conforming to Sequence in multiple ways, or (among other things) your for..in loops stop working, and you lose the ability to dynamically cast down to an existential “Sequence” without binding the Element type (again, see “Generalized existentials”). Use cases similar to the ConstructibleFromValue protocol above seem too few to justify the potential for confusion between associated types and generic parameters of protocols; we’re better off not having the latter.

Private conformances

Right now, a protocol conformance can be no less visible than the minimum of the conforming type’s access and the protocol’s access. Therefore, a public type conforming to a public protocol must provide the conformance publicly. One could imagine removing that restriction, so that one could introduce a private conformance:

public protocol P { }
public struct X { }
extension X : internal P { … } // X conforms to P, but only within this module

The main problem with private conformances is the interaction with dynamic casting. If I have this code:

func foo(value: Any) {
 if let x = value as? P { print(“P”) }
}

foo(X())

Under what circumstances should it print “P”? If foo() is defined within the same module as the conformance of X to P? If the call is defined within the same module as the conformance of X to P? Never? Either of the first two answers requires significant complications in the dynamic casting infrastructure to take into account the module in which a particular dynamic cast occurred (the first option) or where an existential was formed (the second option), while the third answer breaks the link between the static and dynamic type systems—none of which is an acceptable result.

Conditional conformances via protocol extensions

We often get requests to make a protocol conform to another protocol. This is, effectively, the expansion of the notion of “Conditional conformances” to protocol extensions. For example:

protocol P {
 func foo()
}

protocol Q {
 func bar()
}

extension Q : P { // every type that conforms to Q also conforms to P
 func foo() { // implement “foo” requirement in terms of “bar"
 bar()
 }
}

func f<T: P>(t: T) { … }

struct X : Q {
 func bar() { … }
}

f(X()) // okay: X conforms to P through the conformance of Q to P

This is an extremely powerful feature: is allows one to map the abstractions of one domain into another domain (e.g., every Matrix is a Graph). However, similar to private conformances, it puts a major burden on the dynamic-casting runtime to chase down arbitrarily long and potentially cyclic chains of conformances, which makes efficient implementation nearly impossible.

Potential removals

The generics system doesn’t seem like a good candidate for a reduction in scope; most of its features do get used fairly pervasively in the standard library, and few feel overly anachronistic. However...

Associated type inference

Associated type inference is the process by which we infer the type bindings for associated types from other requirements. For example:

protocol IteratorProtocol {
 associatedtype Element
 mutating func next() -> Element?
}

struct IntIterator : IteratorProtocol {
 mutating func next() -> Int? { … } // use this to infer Element = Int
}

Associated type inference is a useful feature. It’s used throughout the standard library, and it helps keep associated types less visible to types that simply want to conform to a protocol. On the other hand, associated type inference is the only place in Swift where we have a global type inference problem: it has historically been a major source of bugs, and implementing it fully and correctly requires a drastically different architecture to the type checker. Is the value of this feature worth keeping global type inference in the Swift language, when we have deliberatively avoided global type inference elsewhere in the language?

Existentials

Existentials aren’t really generics per se, but the two systems are closely intertwined due to their mutable dependence on protocols.

*Generalized existentials

The restrictions on existential types came from an implementation limitation, but it is reasonable to allow a value of protocol type even when the protocol has Self constraints or associated types. For example, consider IteratorProtocol again and how it could be used as an existential:

protocol IteratorProtocol {
 associatedtype Element
 mutating func next() -> Element?
}

let it: IteratorProtocol = …
it.next() // if this is permitted, it could return an “Any?”, i.e., the existential that wraps the actual element

Additionally, it is reasonable to want to constrain the associated types of an existential, e.g., “a Sequence whose element type is String” could be expressed by putting a where clause into “protocol<…>” or “Any<…>” (per “Renaming protocol<…> to Any<…>”):

let strings: Any<Sequence where .Iterator.Element == String> = [“a”, “b”, “c”]

The leading “.” indicates that we’re talking about the dynamic type, i.e., the “Self” type that’s conforming to the Sequence protocol. There’s no reason why we cannot support arbitrary “where” clauses within the “Any<…>”. This very-general syntax is a bit unwieldy, but common cases can easily be wrapped up in a generic typealias (see the section “Generic typealiases” above):

typealias AnySequence<Element> = Any<Sequence where .Iterator.Element == Element>
let strings: AnySequence<String> = [“a”, “b”, “c”]

Opening existentials

Generalized existentials as described above will still have trouble with protocol requirements that involve Self or associated types in function parameters. For example, let’s try to use Equatable as an existential:

protocol Equatable {
 func ==(lhs: Self, rhs: Self) -> Bool
 func !=(lhs: Self, rhs: Self) -> Bool
}

let e1: Equatable = …
let e2: Equatable = …
if e1 == e2 { … } // error: e1 and e2 don’t necessarily have the same dynamic type

One explicit way to allow such operations in a type-safe manner is to introduce an “open existential” operation of some sort, which extracts and gives a name to the dynamic type stored inside an existential. For example:

if let storedInE1 = e1 openas T { // T is a the type of storedInE1, a copy of the value stored in e1
 if let storedInE2 = e2 as? T { // is e2 also a T?
 if storedInE1 == storedInE2 { … } // okay: storedInT1 and storedInE2 are both of type T, which we know is Equatable
 }
}

Thoughts?

 - Doug

Thanks for sending this out! A lot of the stuff here looks amazingly useful, and I'm excited to see it being discussed.

The choice of Equatable as an example for opening existentials is an interesting one here, because it's one of the few cases I can think of where differing dynamic types is actually fully defined: they're not equal. In ObjC we express that by starting every -isEqual: implementation with if (![other isKindOfClass:[self class]]) { return NO; }, which while clunky and easy to forget, does neatly express the desired semantics with no burden at the callsite.

My first thought for how to express that in Swift was "ok, provide an == for (Any, Any) that just always says false", but that would defeat the ability to say something just doesn't make sense to compare with ==, which is a nice feature and prevents bugs.

Next thought for expressing it cleanly was:

protocol Equatable {
 func ==(lhs: Self, rhs: Self) -> Bool
 func !=(lhs: Self, rhs: Self) -> Bool
 func ==(lhs: Self, rhs: !Self) -> Bool { return false }
 func !=(lhs: Self, rhs: !Self) -> Bool { return true }
}

and I guess another equivalent way of writing it that doesn't require a new syntactic construct would be:

protocol Equatable {
 func ==(lhs: Self, rhs: Self) -> Bool
 func !=(lhs: Self, rhs: Self) -> Bool
 func ==<Other:Equatable where Other != Self>(lhs: Self, rhs: Other) -> Bool { return false }
 func !=<Other:Equatable where Other != Self>(lhs: Self, rhs: Other) -> Bool { return true }
}

My thinking is that this could be expressed as extending the existential type to conform to the protocol:

extension Any<Equatable>: Equatable {
 func ==(lhs: Any<Equatable>, rhs: Any<Equatable>) -> Bool {
 if let lrhs = rhs as? lhs.Self {
 return lhs == rlhs
 }
 return false
 }
}

which would make this idea a minor extension of the "Concrete Same-Type Requirements" section.

However, this still has a similar flaw to the first idea I had, which is that it introduces a valid == operator for things that never make sense to compare, when what we actually want is one that will only be accepted if there's insufficient information to determine whether it's valid (i.e. Equatable existentials). I suppose there's a relatively obvious syntax to express that directly:

protocol Equatable {
 func ==(lhs: Self, rhs: Self) -> Bool
 func !=(lhs: Self, rhs: Self) -> Bool
 func ==<Other:Equatable where Other ?= Self>(lhs: Self, rhs: Other) -> Bool { return false }
 func !=<Other:Equatable where Other ?= Self>(lhs: Self, rhs: Other) -> Bool { return true }
}

Where "?=" would be read as "might be equal to". It's not clear to me if this sort of "default implementation for non-matching existentials" concept is applicable beyond Equatable though, and if not it seems like a lot of machinery to add for one case.

The "introducing an == operator for things that never make sense to compare" problem could be avoided by a type system rule that, when we bind a generic parameter from multiple value parameter, we don't upconvert to a type that neither parameter statically has. Since `==` is `<Self> (Self, Self) -> Bool`, that would prevent us from picking `Self == Any<Equatable>` if you called `Int == Float`, but would allow it if one or the other parameter was already Any<Equatable>.

-Joe

···

On Mar 2, 2016, at 6:20 PM, David Smith via swift-evolution <swift-evolution@swift.org> wrote:

On Mar 2, 2016, at 5:22 PM, Douglas Gregor via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote: