[Manifesto] Completing Generics

Brent_Royal-Gordon · March 10, 2016, 2:11am

I assume the following will fall under "constant expression":

let 2π = 2 * π

That would involve inferring that 2π is a generic constant… could certainly be something to explore, but it’s somewhat new territory.

It seems to me that the same logic would make this:

let range = 1.0...5.0

Into something like this:

let range<T: Comparable, FloatLiteralType>: ClosedInterval<T> = 1.0...5.0

Which strikes me as a bridge too far.

···

--
Brent Royal-Gordon
Architechies

hartbit · May 8, 2016, 9:17pm

I created two bug requests for Recursive protocol constraints and Nested generics and will write a proposal for Concrete same-type requirements.

[SR-1445] Recursive protocol constraints <Issues · apple/swift-issues · GitHub;

[SR-1446] Nested generics <Issues · apple/swift-issues · GitHub;

···

On 03 May 2016, at 09:58, Douglas Gregor <dgregor@apple.com> wrote:

Sent from my iPhone

On May 2, 2016, at 3:58 PM, David Hart <david@hartbit.com <mailto:david@hartbit.com>> wrote:

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?

I'd classify everything in that section as a bug, so long as we're restricting ourselves to the syntax already present in the language. Syntactic improvements (e.g., for same-type-to-concrete constraints) would require a proposal.

  - Doug

On 03 Mar 2016, at 02:22, Douglas Gregor via swift-evolution <swift-evolution@swift.org <mailto: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<U> { } // 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<U>” 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 <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution

Slava_Pestov · March 3, 2016, 5:26am

Yeah, I suspect the overlap of dynamic casting and use cases for private conformances is small, so it seems unfortunate to me to hobble the language around the needs of dynamic casts. A workable rule might be to say that private or internal conformances aren't exposed to runtime lookup, so are never found by as? casts. We could then statically reject the `as? X<Y>` cast here since the X<Y> instantiation depends on a runtime-invisible conformance.

I feel like we talked about this in person a while back but I don’t remember the conclusion. What if dynamic cast lookup was lexically scoped to the conformances visible from the lookup location? I’m not quite sure how you would represent this at runtime but it seems feasible.

···

On Mar 2, 2016, at 9:12 PM, Joe Groff via swift-evolution <swift-evolution@swift.org> wrote:

-Joe

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

Douglas_Gregor · March 3, 2016, 5:32am

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.

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.

Right, multiple conformances do happen in our current model. Personally, I think that the occurrence of multiple conformances should effectively be an error at runtime unless the conformances are effectively identical (same type witnesses with the same conformances may be a reasonable approximation), and even then it’s worthy of a diagnostic as early as we can produce one, because the amount of infrastructure one needs to handle multiple conformances is significant.

If it's a runtime error, that's a huge resilience liability, since any library adding a conformance would potentially be causing its users to start crashing at load time.

My hope is that we could limit the failure mode to the case where the conflicting conformances are different in a way that affects soundness, e.g., different type witnesses for the same associated type. I certainly agree that we’re creating both a resilience liability and a liability when composing libraries (the author of library E below did nothing wrong, but observes weird behavior), but the alternatives seem so much worse.

This seems to me like poor grounds for rejecting the ability to have private conformances. I think they're a really useful feature.

With what semantics? Truly embracing private and multiple conformances means embedding it in type identity:

// Module A
public protocol P {
  associatedtype A
}
public struct X<T : P> { }

// Module B
struct Y { }

// Module C
import A
import B
extension Y : private P {
  typealias A = Int
}

public func f() -> Any { return X<Y>() }

// Module D
import A
import B
extension Y : private P {
  typealias A = Double
}

public func g(x: Any) {
  if let y = x as? X<Y> { /* do we get here? */ }
}

// Module E
import A
import B
import C
import D
g(f())

It’s not that we can’t make this behave correctly—the answer is “no”, we don’t get into the “then” block, because modules D and E effectively have different types X<Y> due to the differing conformances—but that making this behave correctly has a nontrivial runtime cost (uniquing via protocol conformances) and can cause major confusion (wait, X<Y> isn’t a single thing?), for what I suspect is a fairly rare occurrence.

Yeah, I suspect the overlap of dynamic casting and use cases for private conformances is small, so it seems unfortunate to me to hobble the language around the needs of dynamic casts. A workable rule might be to say that private or internal conformances aren't exposed to runtime lookup, so are never found by as? casts. We could then statically reject the `as? X<Y>` cast here since the X<Y> instantiation depends on a runtime-invisible conformance.

It’s a workable rule. However, to me, it feels like the use cases for private conformances are sparse enough that I’d rather ban it than give it semantics that are different from those of non-private conformances. However, I’ve thought far more about the implementation challenges than about the use cases for private conformances [*].

- Doug

[*] In my defense, that’s because I tend to think more about the other sources of multiple conformances.

···

On Mar 2, 2016, at 9:12 PM, Joe Groff <jgroff@apple.com> wrote:

On Mar 2, 2016, at 8:26 PM, Douglas Gregor <dgregor@apple.com <mailto:dgregor@apple.com>> wrote:

On Mar 2, 2016, at 5:38 PM, Joe Groff <jgroff@apple.com <mailto:jgroff@apple.com>> wrote:

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

Joe_Groff · March 3, 2016, 5:04pm

And then we introduce higher-order 'protocol' constraints, and implement 'Any' in the library!

enum Any<Constraints: protocol> {
case Value<T: Constraints>(T)
}

-Joe

···

On Mar 2, 2016, at 10:59 PM, Slava Pestov via swift-evolution <swift-evolution@swift.org> wrote:

On Mar 2, 2016, at 10:45 PM, Brent Royal-Gordon <brent@architechies.com> wrote:

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.

Following from the generic constants mentioned earlier, perhaps this is expressed with some kind of generic `if let`?

  func == (e1: Any<Equatable>, e2: Any<Equatable>) -> Bool {
    guard let concreteE1<T: Equatable> = e1 as? T, concreteE2 = e2 as? T else {

I think here the generic signature should really come first before any patterns, so more like ‘guard let <T : Equatable> …'.

But this is rather complicated. I fear. Perhaps a well-crafted one-off language feature to handle heterogeneous equality is better.

Here’s a really not-serious proposal: it seems we could implement GADTs if we allowed enum cases to have generic parameter lists, and extended pattern matching as above.

enum Foo {
  case Something<T>(T)
  case Nothing
}

let a: [Foo] // could contain many different Something types

trs · March 4, 2016, 6:15am

If I understand you right you are describing multiple dynamic dispatch as it was used e.g. in the Cecil language or Dylan and I think Clojure has it, too.

That would certainly be a nice and powerful addition to Swift but we would have to think carefully how to mesh this with single dispatch from OOP and POP.
Maybe we could introduce global multimethods.

-Thorsten

···

Am 04.03.2016 um 05:48 schrieb Brent Royal-Gordon via swift-evolution <swift-evolution@swift.org>:

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.

It's a reasonable default, but it's not necessarily the right
implementation for every type. One could imagine Polygons comparing
equal to Squares, for example.

If the "open" operation is sophisticated enough, when it's faced with mismatched concrete types but they both conform to a protocol with a existential that meets the requirements, it could return that existential.

That would mean that, in this scenario:

   protocol Shape: Equatable { ...}

   protocol Polygonal: Shape {
       var vertices: [Vertex]
   }
   struct Square: Polygonal { ... }
   struct Polygon: Polygonal { ... }

You could add this:

   extension Any<Polygonal>: Equatable {}

   func == (lhs: Any<Polygonal>, rhs: Any<Polygonal>) -> Bool {
       for (lhsVertex, rhsVertex) in zip(lhs.vertices, rhs.vertices) {
           if lhsVertex != rhsVertex {
               return false
           }
       }
       return true
   }

And then, if `==(_: Any<Equatable>, _: Any<Equatable>)` were passed a Square and a Polygon, opening the `Any<Equatable>`s would give you a pair of `Any<Polygonal>`s.

This is obviously more complex than simply opening the existential, matching its concrete type against a requirement, and extracting the original value if it matches—it's looking at the concrete types of N existentials, simultaneously matching them *all* against a requirement to find a more specific type they can all be cast to, and then performing that cast. To do its job, it would need to see all of the operands at the same time and evaluate them together to find a type that would fit all of them.

That's what I was trying to get at when I wrote this example earlier in the thread:

   func == (e1: Any<Equatable>, e2: Any<Equatable>) -> Bool {
       guard let concreteE1<T: Equatable> = e1 as? T, concreteE2 = e2 as? T else {
           return false
       }

       return concreteE1 == concreteE2
   }

If both parameters were `Square`s, then `T` would be a `Square`. But if one was a `Square` and the other a `Polygon`, `T` could be an `Any<Polygonal>`. Because you are simultaneously matching both values, you don't have to try the match both ways, and the operation is free to return a more specific protocol existential if that's the best it can do.

(And if there was no `Equatable` type they could be cast to that was more specific than `Any<Equatable>`, `T` would at least notionally be the bottom type and, since neither existential contains a value of the bottom type, both `as?` casts would return `nil`. `guard let` would then see those `nil`s and send you down the `else` branch.)

--
Brent Royal-Gordon
Architechies

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

dabrahams · March 4, 2016, 4:09pm

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.

It's a reasonable default, but it's not necessarily the right
implementation for every type. One could imagine Polygons comparing
equal to Squares, for example.

If the "open" operation is sophisticated enough, when it's faced with
mismatched concrete types but they both conform to a protocol with a
existential that meets the requirements, it could return that
existential.

That would mean that, in this scenario:

  protocol Shape: Equatable { ...}

  protocol Polygonal: Shape {
    var vertices: [Vertex]
  }
  struct Square: Polygonal { ... }
  struct Polygon: Polygonal { ... }

You could add this:

  extension Any<Polygonal>: Equatable {}

If you could extend just the existential, yes, that could work. I don't
think this requires any “opening” though, and it's not taking advantage
of the default behavior for equatables of different types, which is my
point.

  func == (lhs: Any<Polygonal>, rhs: Any<Polygonal>) -> Bool {
    for (lhsVertex, rhsVertex) in zip(lhs.vertices,
rhs.vertices) {
      if lhsVertex != rhsVertex {
        return false
      }
    }
    return true

I think you'd need to sort the vertices or something, but I get the point.

  }

And then, if `==(_: Any<Equatable>, _: Any<Equatable>)` were passed a
Square and a Polygon, opening the `Any<Equatable>`s would give you a
pair of `Any<Polygonal>`s.

This is obviously more complex than simply opening the existential,
matching its concrete type against a requirement, and extracting the
original value if it matches—it's looking at the concrete types of N
existentials, simultaneously matching them *all* against a requirement
to find a more specific type they can all be cast to, and then
performing that cast. To do its job, it would need to see all of the
operands at the same time and evaluate them together to find a type
that would fit all of them.

That's what I was trying to get at when I wrote this example earlier
in the thread:

  func == (e1: Any<Equatable>, e2: Any<Equatable>) -> Bool {
    guard let concreteE1<T: Equatable> = e1 as? T,
concreteE2 = e2 as? T else {
      return false
    }

    return concreteE1 == concreteE2
  }

If both parameters were `Square`s, then `T` would be a `Square`. But
if one was a `Square` and the other a `Polygon`, `T` could be an
`Any<Polygonal>`. Because you are simultaneously matching both values,
you don't have to try the match both ways, and the operation is free
to return a more specific protocol existential if that's the best it
can do.

Ah... finding a unique possible common equatable type sounds both
inefficient and like it could fail at runtime due to ambiguity. I'd be
at least very cautious about creating a system like that.

···

on Thu Mar 03 2016, Brent Royal-Gordon <swift-evolution@swift.org> wrote:

--
-Dave

Joe_Groff · March 8, 2016, 5:48pm

Another area I have seen a problem is trying to return protocols with associated types, e.g. given:

protocol LazyNextableCollection {
    associated type Element

    @warn_unused_result mutating func next() throws -> Element?

    mutating func map<Mapped, Output: LazyNextableCollection where Output.Element == Mapped>(mapper: (Element) throws -> Mapped) -> Output
}

and

struct AsLazyNextable<Element>: LazyNextableCollection {
    private let nextable: () throws -> Element?

    @warn_unused_result mutating func next() throws -> Element? {
        return try nextable()
    }
}

The following fails:

extension LazyNextableCollection {
    mutating func map<Mapped, Output: LazyNextableCollection where Output.Element == Mapped>(mapper: (Element) throws -> Mapped) -> Output {
        return AsLazyNextable<Mapped> {
            let element = try self.next()
            guard let e = element else { return nil }
            return try mapper(e)
        }
    }
}

The compiler says that AsLazyNextable<Mapped> is not the same type as Output.

That's because it isn't. You're claiming that `map` is able to return *all* `Output` types a caller might ask for, when really you want to say it might return *any* LazyNextableCollection, but the caller doesn't get to know what it is. You'd use an existential type for this:

mutating func map<Mapped>(mapper: (Element) throws -> Mapped) -> Any<LazyNextableCollection where Element == Mapped> { ... }

-Joe

···

On Mar 7, 2016, at 9:02 PM, Howard Lovatt via swift-evolution <swift-evolution@swift.org> wrote:

  -- Howard.

On 8 March 2016 at 11:18, Howard Lovatt <howard.lovatt@gmail.com <mailto:howard.lovatt@gmail.com>> wrote:
I have seen a couple of areas where generics seem lacking to me:

  1. Declaring associated types with where clauses
  2. Declaring generic arguments for calculated properties
  3. Similar to above, declaring generic properties for subscripts

Examples of 1 and 2:

protocol IterableCollection {
    associated type Element

    /// ...

    /// Would prefer:
    /// `var lazy<L: LazyNextableCollection where L.Element == Element>: L { get }` // Point 2 above
    /// Or:
    /// `associatedtype L: LazyNextableCollection where L.Element == Element` // Point 1 above
    /// `var lazy: L { get }`
    /// But nearest possible is a function :(.
    func lazy<L: LazyNextableCollection where L.Element == Element>() -> L // Best I seem to be able to do
}

Example of 3:

protocol SubstriptableCollection {
    associatedtype Index: Rangeable
    associatedtype Element

    /// ...

    /// Ideally would write:
    /// `subscript<S: SubstriptableCollection, R: SubstriptableCollection where S.Element == Element, R.Element == Index>(range: R) -> S { get set }` // Point 3 above
    /// However nearest in Swift is seperate get and set methods :(.
    func getSubscript<S: SubstriptableCollection, R: SubstriptableCollection where S.Element == Element, R.Element == Index>(range: R) -> S
}

  -- Howard.

On 3 March 2016 at 19:34, Haravikk via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:
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 <mailto: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<U> { } // 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<U>” 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 <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution

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

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

hlovatt · March 10, 2016, 2:02am

Wow, I would never have guessed that syntax :)

It makes no sense to me to interpret a generic constraint as meaning all
instead of any. How could anything either accept or return all possible
implementations of something simultaneously, surely it only ever accepts or
returns one of all the possible implementations at a time.

If the interpretation for output is that at time 1 it returns one of all
the possible implementations at at time 2 returns another - then that is
what I want. However I would describe that as returning one of the possible
implementations, not all.

But no doubt you are correct, since you probably wrote that bit of the
compiler :(

More practical points

1. My compiler, 7.3 beta (7D152p), rejects the syntax, it doesn't like
where inside Any<> saying it expects > to complete generic argument list.
When will this be available, so that I can try it out?
2. Will the declarations inside protocols also change to the Any<...> form
or will all the generics remain following the function name rather in a
returned Any<...>? Currently -> Any<...> doesn't work in protocols for me.
3. In the construct Any<Protocol where Type == Type>, i.e. same type name
used in protocol and enclosing struct/class/extension, does the left Type
refer to the protocol or the enclosing struct/class/extension?
4. Is there any documentation of all of this?

-- Howard.

···

On 9 March 2016 at 04:48, Joe Groff <jgroff@apple.com> wrote:

On Mar 7, 2016, at 9:02 PM, Howard Lovatt via swift-evolution < > swift-evolution@swift.org> wrote:

Another area I have seen a problem is trying to return protocols with
associated types, e.g. given:

protocol LazyNextableCollection {
    associated type Element

    @warn_unused_result mutating func next() throws -> Element?

    mutating func map<Mapped, Output: LazyNextableCollection where Output.Element
== Mapped>(mapper: (Element) throws -> Mapped) -> Output
}

and

struct AsLazyNextable<Element>: LazyNextableCollection {
    private let nextable: () throws -> Element?

    @warn_unused_result mutating func next() throws -> Element? {
        return try nextable()
    }
}

The following fails:

extension LazyNextableCollection {
    mutating func map<Mapped, Output: LazyNextableCollection where Output.Element
== Mapped>(mapper: (Element) throws -> Mapped) -> Output {
        return AsLazyNextable<Mapped> {
            let element = try self.next()
            guard let e = element else { return nil }
            return try mapper(e)
        }
    }
}

The compiler says that AsLazyNextable<Mapped> is not the same type as
Output.

That's because it isn't. You're claiming that `map` is able to return
*all* `Output` types a caller might ask for, when really you want to say it
might return *any* LazyNextableCollection, but the caller doesn't get to
know what it is. You'd use an existential type for this:

mutating func map<Mapped>(mapper: (Element) throws -> Mapped) ->
Any<LazyNextableCollection where Element == Mapped> { ... }

-Joe

  -- Howard.

On 8 March 2016 at 11:18, Howard Lovatt <howard.lovatt@gmail.com> wrote:

I have seen a couple of areas where generics seem lacking to me:

  1. Declaring associated types with where clauses
  2. Declaring generic arguments for calculated properties
  3. Similar to above, declaring generic properties for subscripts

Examples of 1 and 2:

protocol IterableCollection {
    associated type Element

    /// ...

    /// Would prefer:
    /// `var lazy<L: LazyNextableCollection where L.Element ==
>: L { get }` // Point 2 above
    /// Or:
    /// `associatedtype L: LazyNextableCollection where L.Element ==
Element` // Point 1 above
    /// `var lazy: L { get }`
    /// But nearest possible is a function :(.
    func lazy<L: LazyNextableCollection where L.Element == Element>() ->
L // Best I seem to be able to do
}

Example of 3:

protocol SubstriptableCollection {
    associatedtype Index: Rangeable
    associatedtype Element

    /// ...

    /// Ideally would write:
    /// `subscript<S: SubstriptableCollection, R:
SubstriptableCollection where S.Element == Element, R.Element ==
>(range: R) -> S { get set }` // Point 3 above
    /// However nearest in Swift is seperate get and set methods :(.
    func getSubscript<S: SubstriptableCollection, R:
SubstriptableCollection where S.Element == Element, R.Element ==
>(range: R) -> S
}

  -- Howard.

On 3 March 2016 at 19:34, Haravikk via swift-evolution < >> swift-evolution@swift.org> wrote:

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<U> { } *// 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,
> 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 :
>(
              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 ==
>(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 ==
>(elements: S) -> Bool
}

extension Bag {
  func containsAll<S: Sequence where Sequence.Iterator.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 ==
>(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<U>” 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

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

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

hartbit · May 8, 2016, 9:37pm

Sorry, I misunderstood that you meant that the version of Concrete same-type requirement that does not introduce new syntax could be sent through as a bug request. It’s now done:

[SR-1447] Concrete same-type requirements <Issues · apple/swift-issues · GitHub;

···

On 08 May 2016, at 23:17, David Hart via swift-evolution <swift-evolution@swift.org> wrote:

I created two bug requests for Recursive protocol constraints and Nested generics and will write a proposal for Concrete same-type requirements.

[SR-1445] Recursive protocol constraints <Issues · apple/swift-issues · GitHub;

[SR-1446] Nested generics <Issues · apple/swift-issues · GitHub;

On 03 May 2016, at 09:58, Douglas Gregor <dgregor@apple.com <mailto:dgregor@apple.com>> wrote:

Sent from my iPhone

On May 2, 2016, at 3:58 PM, David Hart <david@hartbit.com <mailto:david@hartbit.com>> wrote:

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?

I'd classify everything in that section as a bug, so long as we're restricting ourselves to the syntax already present in the language. Syntactic improvements (e.g., for same-type-to-concrete constraints) would require a proposal.

  - Doug

On 03 Mar 2016, at 02:22, Douglas Gregor via swift-evolution <swift-evolution@swift.org <mailto: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<U> { } // 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<U>” 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 <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution

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

Joe_Groff · March 3, 2016, 5:42am

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.

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.

Right, multiple conformances do happen in our current model. Personally, I think that the occurrence of multiple conformances should effectively be an error at runtime unless the conformances are effectively identical (same type witnesses with the same conformances may be a reasonable approximation), and even then it’s worthy of a diagnostic as early as we can produce one, because the amount of infrastructure one needs to handle multiple conformances is significant.

If it's a runtime error, that's a huge resilience liability, since any library adding a conformance would potentially be causing its users to start crashing at load time.

My hope is that we could limit the failure mode to the case where the conflicting conformances are different in a way that affects soundness, e.g., different type witnesses for the same associated type.

I don't think we can reliably tell. As currently implemented, we generate a fresh set of witness thunks for every conformance, so the function pointers in the two modules' conformances would look different to the runtime.

I certainly agree that we’re creating both a resilience liability and a liability when composing libraries (the author of library E below did nothing wrong, but observes weird behavior), but the alternatives seem so much worse.

The only place I can see where we rely on coherence is in the runtime, as you've mentioned. We're pretty good about statically maintaining conformance identity through the stack, so we ought to be able to catch static conformance mismatches in types and maybe even give reasonable error messages. It wouldn't be hard for the runtime to notice when it has a key collision in its conformance table and log a warning either—that would be consistent with what the ObjC runtime does with class or category collisions between images.

-Joe

···

On Mar 2, 2016, at 9:32 PM, Douglas Gregor <dgregor@apple.com> wrote:

On Mar 2, 2016, at 9:12 PM, Joe Groff <jgroff@apple.com <mailto:jgroff@apple.com>> wrote:

On Mar 2, 2016, at 8:26 PM, Douglas Gregor <dgregor@apple.com <mailto:dgregor@apple.com>> wrote:

On Mar 2, 2016, at 5:38 PM, Joe Groff <jgroff@apple.com <mailto:jgroff@apple.com>> wrote:

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

Joe_Groff · March 10, 2016, 2:07am

Wow, I would never have guessed that syntax :)

It makes no sense to me to interpret a generic constraint as meaning all instead of any. How could anything either accept or return all possible implementations of something simultaneously, surely it only ever accepts or returns one of all the possible implementations at a time.

A type variable in angle brackets always means "all". It's like a function parameter, but at type level—it's in the caller's hands what it gets bound to. You couldn't write a function `func foo<Input, Output>(Input) -> Output` unless that function was able to generate a value of every possible type a caller might pass in for Output, just like you couldn't write e.g. 'absolute value' as taking its result as a second parameter.

If the interpretation for output is that at time 1 it returns one of all the possible implementations at at time 2 returns another - then that is what I want. However I would describe that as returning one of the possible implementations, not all.

But no doubt you are correct, since you probably wrote that bit of the compiler :(

More practical points

1. My compiler, 7.3 beta (7D152p), rejects the syntax, it doesn't like where inside Any<> saying it expects > to complete generic argument list. When will this be available, so that I can try it out?
2. Will the declarations inside protocols also change to the Any<...> form or will all the generics remain following the function name rather in a returned Any<...>? Currently -> Any<...> doesn't work in protocols for me.
3. In the construct Any<Protocol where Type == Type>, i.e. same type name used in protocol and enclosing struct/class/extension, does the left Type refer to the protocol or the enclosing struct/class/extension?
4. Is there any documentation of all of this?

Sorry, this is all possible future syntax and features. It's not implemented today. You'd need to write your own equivalent of the "Any" wrapper by hand right now.

-Joe

···

On Mar 9, 2016, at 6:02 PM, Howard Lovatt <howard.lovatt@gmail.com> wrote:

hlovatt · March 10, 2016, 4:35am

I am sure you know the answer for Swift; but in other languages it doesn't,
e.g. Java.

With Java semantics:

func foo<Input, Output>(input: Input) -> Output

Would be the same as:

func foo(input: Any) -> Any

Because the only constraint on both Input and Output is Any. Since the Java
compiler erases generics, the two would literally be the same to the JVM!

Since Swift doesn't allow overloading on return type and therefore as it
stands `func foo<Input, Output>(input: Input) -> Output` cannot
be implemented, it would be nice if the compiler flagged this as an error
and suggested that you meant `func foo(input: Any) -> Any`.

-- Howard.

···

On 10 March 2016 at 13:07, Joe Groff <jgroff@apple.com> wrote:

> On Mar 9, 2016, at 6:02 PM, Howard Lovatt <howard.lovatt@gmail.com> > wrote:
>
> Wow, I would never have guessed that syntax :)
>
> It makes no sense to me to interpret a generic constraint as meaning all
instead of any. How could anything either accept or return all possible
implementations of something simultaneously, surely it only ever accepts or
returns one of all the possible implementations at a time.

A type variable in angle brackets always means "all". It's like a function
parameter, but at type level—it's in the caller's hands what it gets bound
to. You couldn't write a function `func foo<Input, Output>(Input) ->
Output` unless that function was able to generate a value of every possible
type a caller might pass in for Output, just like you couldn't write e.g.
'absolute value' as taking its result as a second parameter.

>
> If the interpretation for output is that at time 1 it returns one of all
the possible implementations at at time 2 returns another - then that is
what I want. However I would describe that as returning one of the possible
implementations, not all.
>
> But no doubt you are correct, since you probably wrote that bit of the
compiler :(
>
> More practical points
>
> 1. My compiler, 7.3 beta (7D152p), rejects the syntax, it doesn't like
where inside Any<> saying it expects > to complete generic argument list.
When will this be available, so that I can try it out?
> 2. Will the declarations inside protocols also change to the Any<...>
form or will all the generics remain following the function name rather in
a returned Any<...>? Currently -> Any<...> doesn't work in protocols for me.
> 3. In the construct Any<Protocol where Type == Type>, i.e. same type
name used in protocol and enclosing struct/class/extension, does the left
Type refer to the protocol or the enclosing struct/class/extension?
> 4. Is there any documentation of all of this?

Sorry, this is all possible future syntax and features. It's not
implemented today. You'd need to write your own equivalent of the "Any"
wrapper by hand right now.

-Joe

Austin · May 8, 2016, 10:38pm

Is the plan to eventually support "multiple" forms of concrete same-type
requirement syntax - the existing "where Element == SomeConcreteType" and
the generic parameterized extensions described elsewhere? If not, the
syntax should probably be discussed as part of a pre-proposal thread before
anything else happens.

Also, I think it would be valuable to add "covariant and contravariant
generic parameters" to the "unlikely" list (there's now a copy in the docs/
directory), as those have come up several times in the past and the core
team has expressed that they are pretty dead set against that feature.

Best,
Austin

···

On Sun, May 8, 2016 at 2:37 PM, David Hart via swift-evolution < swift-evolution@swift.org> wrote:

Sorry, I misunderstood that you meant that the version of Concrete
same-type requirement that does not introduce new syntax could be sent
through as a bug request. It’s now done:

[SR-1447] Concrete same-type requirements
<Issues · apple/swift-issues · GitHub;

On 08 May 2016, at 23:17, David Hart via swift-evolution < > swift-evolution@swift.org> wrote:

I created two bug requests for Recursive protocol constraints and Nested
generics and will write a proposal for Concrete same-type requirements.

[SR-1445] Recursive protocol constraints
<Issues · apple/swift-issues · GitHub;

[SR-1446] Nested generics <Issues · apple/swift-issues · GitHub;

On 03 May 2016, at 09:58, Douglas Gregor <dgregor@apple.com> wrote:

Sent from my iPhone

On May 2, 2016, at 3:58 PM, David Hart <david@hartbit.com> wrote:

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?

I'd classify everything in that section as a bug, so long as we're
restricting ourselves to the syntax already present in the language.
Syntactic improvements (e.g., for same-type-to-concrete constraints) would
require a proposal.

  - Doug

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<U> { } *// 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,
> 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 :
>(
              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 ==
>(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 ==
>(elements: S) -> Bool
}

extension Bag {
  func containsAll<S: Sequence where Sequence.Iterator.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 ==
>(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<U>” 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 ==
>*
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

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

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

hartbit · May 8, 2016, 10:46pm

The way modifications have gone through swift-evolution, it seems like it would be more logical to implement it with no syntax change first and only then propose and discuss generic parameterised extensions.

···

On 09 May 2016, at 00:38, Austin Zheng <austinzheng@gmail.com> wrote:

Is the plan to eventually support "multiple" forms of concrete same-type requirement syntax - the existing "where Element == SomeConcreteType" and the generic parameterized extensions described elsewhere? If not, the syntax should probably be discussed as part of a pre-proposal thread before anything else happens.

Douglas_Gregor · March 3, 2016, 6:10am

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.

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.

Right, multiple conformances do happen in our current model. Personally, I think that the occurrence of multiple conformances should effectively be an error at runtime unless the conformances are effectively identical (same type witnesses with the same conformances may be a reasonable approximation), and even then it’s worthy of a diagnostic as early as we can produce one, because the amount of infrastructure one needs to handle multiple conformances is significant.

If it's a runtime error, that's a huge resilience liability, since any library adding a conformance would potentially be causing its users to start crashing at load time.

My hope is that we could limit the failure mode to the case where the conflicting conformances are different in a way that affects soundness, e.g., different type witnesses for the same associated type.

I don't think we can reliably tell. As currently implemented, we generate a fresh set of witness thunks for every conformance, so the function pointers in the two modules' conformances would look different to the runtime.

I was thinking we only “have” to compare the type witnesses and any conformances they carry with them, because that’s what we need to ensure type soundness.

I certainly agree that we’re creating both a resilience liability and a liability when composing libraries (the author of library E below did nothing wrong, but observes weird behavior), but the alternatives seem so much worse.

The only place I can see where we rely on coherence is in the runtime, as you've mentioned. We're pretty good about statically maintaining conformance identity through the stack, so we ought to be able to catch static conformance mismatches in types and maybe even give reasonable error messages. It wouldn't be hard for the runtime to notice when it has a key collision in its conformance table and log a warning either—that would be consistent with what the ObjC runtime does with class or category collisions between images.

Right. My concern is that, in the case where we’ve lost soundness, we need to trap to avoid introducing undefined behavior. Perhaps I’m worrying overmuch.

- Doug

···

On Mar 2, 2016, at 9:42 PM, Joe Groff <jgroff@apple.com> wrote:

On Mar 2, 2016, at 9:32 PM, Douglas Gregor <dgregor@apple.com <mailto:dgregor@apple.com>> wrote:

On Mar 2, 2016, at 9:12 PM, Joe Groff <jgroff@apple.com <mailto:jgroff@apple.com>> wrote:

On Mar 2, 2016, at 8:26 PM, Douglas Gregor <dgregor@apple.com <mailto:dgregor@apple.com>> wrote:

On Mar 2, 2016, at 5:38 PM, Joe Groff <jgroff@apple.com <mailto:jgroff@apple.com>> wrote:

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

griotspeak · March 10, 2016, 4:05pm

Since Swift doesn't allow overloading on return type

Swift definitely allows overloading on return type.

···

On 10 March 2016 at 13:07, Joe Groff <jgroff@apple.com> wrote:

> On Mar 9, 2016, at 6:02 PM, Howard Lovatt <howard.lovatt@gmail.com> >> wrote:
>
> Wow, I would never have guessed that syntax :)
>
> It makes no sense to me to interpret a generic constraint as meaning
all instead of any. How could anything either accept or return all possible
implementations of something simultaneously, surely it only ever accepts or
returns one of all the possible implementations at a time.

A type variable in angle brackets always means "all". It's like a
function parameter, but at type level—it's in the caller's hands what it
gets bound to. You couldn't write a function `func foo<Input,
>(Input) -> Output` unless that function was able to generate a value
of every possible type a caller might pass in for Output, just like you
couldn't write e.g. 'absolute value' as taking its result as a second
parameter.

>
> If the interpretation for output is that at time 1 it returns one of
all the possible implementations at at time 2 returns another - then that
is what I want. However I would describe that as returning one of the
possible implementations, not all.
>
> But no doubt you are correct, since you probably wrote that bit of the
compiler :(
>
> More practical points
>
> 1. My compiler, 7.3 beta (7D152p), rejects the syntax, it doesn't like
where inside Any<> saying it expects > to complete generic argument list.
When will this be available, so that I can try it out?
> 2. Will the declarations inside protocols also change to the Any<...>
form or will all the generics remain following the function name rather in
a returned Any<...>? Currently -> Any<...> doesn't work in protocols for me.
> 3. In the construct Any<Protocol where Type == Type>, i.e. same type
name used in protocol and enclosing struct/class/extension, does the left
Type refer to the protocol or the enclosing struct/class/extension?
> 4. Is there any documentation of all of this?

Sorry, this is all possible future syntax and features. It's not
implemented today. You'd need to write your own equivalent of the "Any"
wrapper by hand right now.

-Joe

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

trs · March 10, 2016, 3:18pm

I am sure you know the answer for Swift; but in other languages it doesn't, e.g. Java.

With Java semantics:

func foo<Input, Output>(input: Input) -> Output

Would be the same as:

func foo(input: Any) -> Any

Because the only constraint on both Input and Output is Any. Since the Java compiler erases generics, the two would literally be the same to the JVM!

To the JVM at runtime, but not to the typechecker at compile time. There it works just as in Swift.

-Thorsten

···

Am 10.03.2016 um 05:35 schrieb Howard Lovatt via swift-evolution <swift-evolution@swift.org>:

Since Swift doesn't allow overloading on return type and therefore as it stands `func foo<Input, Output>(input: Input) -> Output` cannot be implemented, it would be nice if the compiler flagged this as an error and suggested that you meant `func foo(input: Any) -> Any`.

-- Howard.

On 10 March 2016 at 13:07, Joe Groff <jgroff@apple.com> wrote:

> On Mar 9, 2016, at 6:02 PM, Howard Lovatt <howard.lovatt@gmail.com> wrote:
>
> Wow, I would never have guessed that syntax :)
>
> It makes no sense to me to interpret a generic constraint as meaning all instead of any. How could anything either accept or return all possible implementations of something simultaneously, surely it only ever accepts or returns one of all the possible implementations at a time.

A type variable in angle brackets always means "all". It's like a function parameter, but at type level—it's in the caller's hands what it gets bound to. You couldn't write a function `func foo<Input, Output>(Input) -> Output` unless that function was able to generate a value of every possible type a caller might pass in for Output, just like you couldn't write e.g. 'absolute value' as taking its result as a second parameter.

>
> If the interpretation for output is that at time 1 it returns one of all the possible implementations at at time 2 returns another - then that is what I want. However I would describe that as returning one of the possible implementations, not all.
>
> But no doubt you are correct, since you probably wrote that bit of the compiler :(
>
> More practical points
>
> 1. My compiler, 7.3 beta (7D152p), rejects the syntax, it doesn't like where inside Any<> saying it expects > to complete generic argument list. When will this be available, so that I can try it out?
> 2. Will the declarations inside protocols also change to the Any<...> form or will all the generics remain following the function name rather in a returned Any<...>? Currently -> Any<...> doesn't work in protocols for me.
> 3. In the construct Any<Protocol where Type == Type>, i.e. same type name used in protocol and enclosing struct/class/extension, does the left Type refer to the protocol or the enclosing struct/class/extension?
> 4. Is there any documentation of all of this?

Sorry, this is all possible future syntax and features. It's not implemented today. You'd need to write your own equivalent of the "Any" wrapper by hand right now.

-Joe

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

hlovatt · March 10, 2016, 9:43pm

@T.J.,

Swift does not allow overloading on return type. You cannot write:

func f() -> Int

func f() -> String

This is different than Scala, which does allow the equivalent of the above,
and the type signatures above in Scala would be:

f():Int

f():String

respectively (note how type signatures retain their return type) and
therefore you could write:

let i: Int = f()

let s: String = f()

and the compiler would call the correct versions.

It is not that useful in Scala, more a by product of their type inference
(carried over from Haskell), and therefore I am not suggesting that it
should be added to Swift.

-- Howard.

···

On 11 March 2016 at 03:05, T.J. Usiyan <griotspeak@gmail.com> wrote:

Since Swift doesn't allow overloading on return type

Swift definitely allows overloading on return type.

On 10 March 2016 at 13:07, Joe Groff <jgroff@apple.com> wrote:

> On Mar 9, 2016, at 6:02 PM, Howard Lovatt <howard.lovatt@gmail.com> >>> wrote:
>
> Wow, I would never have guessed that syntax :)
>
> It makes no sense to me to interpret a generic constraint as meaning
all instead of any. How could anything either accept or return all possible
implementations of something simultaneously, surely it only ever accepts or
returns one of all the possible implementations at a time.

A type variable in angle brackets always means "all". It's like a
function parameter, but at type level—it's in the caller's hands what it
gets bound to. You couldn't write a function `func foo<Input,
>(Input) -> Output` unless that function was able to generate a value
of every possible type a caller might pass in for Output, just like you
couldn't write e.g. 'absolute value' as taking its result as a second
parameter.

>
> If the interpretation for output is that at time 1 it returns one of
all the possible implementations at at time 2 returns another - then that
is what I want. However I would describe that as returning one of the
possible implementations, not all.
>
> But no doubt you are correct, since you probably wrote that bit of the
compiler :(
>
> More practical points
>
> 1. My compiler, 7.3 beta (7D152p), rejects the syntax, it doesn't
like where inside Any<> saying it expects > to complete generic argument
list. When will this be available, so that I can try it out?
> 2. Will the declarations inside protocols also change to the Any<...>
form or will all the generics remain following the function name rather in
a returned Any<...>? Currently -> Any<...> doesn't work in protocols for me.
> 3. In the construct Any<Protocol where Type == Type>, i.e. same type
name used in protocol and enclosing struct/class/extension, does the left
Type refer to the protocol or the enclosing struct/class/extension?
> 4. Is there any documentation of all of this?

Sorry, this is all possible future syntax and features. It's not
implemented today. You'd need to write your own equivalent of the "Any"
wrapper by hand right now.

-Joe

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

Austin · May 8, 2016, 10:50pm

That seems reasonable. Onward ho!

···

On Sun, May 8, 2016 at 3:46 PM, David Hart <david@hartbit.com> wrote:

On 09 May 2016, at 00:38, Austin Zheng <austinzheng@gmail.com> wrote:

Is the plan to eventually support "multiple" forms of concrete same-type
requirement syntax - the existing "where Element == SomeConcreteType" and
the generic parameterized extensions described elsewhere? If not, the
syntax should probably be discussed as part of a pre-proposal thread before
anything else happens.

The way modifications have gone through swift-evolution, it seems like it
would be more logical to implement it with no syntax change first and only
then propose and discuss generic parameterised extensions.