[swift-evolution] [Manifesto] Completing Generics

[Russ Bishop]

> On Mar 2, 2016, at 5:22 PM, Douglas Gregor via swift-evolution <swift-evolution at swift.org> wrote:
> 
> 
> Removing unnecessary restrictions
> 
> Concrete same-type requirements
> 
> Currently, a constrained extension cannot use a same-type constraint to make a type parameter equivalent to a concrete type. For example:
> 
> extension Array where Element == String {
>   func makeSentence() -> String {
>     // uppercase first string, concatenate with spaces, add a period, whatever
>   }
> }
> 
> This is a highly-requested feature that fits into the existing syntax and semantics. Note that one could imagine introducing new syntax, e.g., extending “Array<String>”, which gets into new-feature territory: see the section on “Parameterized extensions”.

Seems useful.


> 
> Parameterizing other declarations
> 
> 
> Parameterized extensions
> 
> Extensions themselves could be parameterized, which would allow some structural pattern matching on types. For example, this would permit one to extend an array of optional values, e.g.,
> 
> extension<T> Array where Element == T? {
>   var someValues: [T] {
>     var result = [T]()
>     for opt in self {
>       if let value = opt { result.append(value) }
>     }
>    return result
>   }
> }
> 
> We can generalize this to a protocol extensions:
> 
> extension<T> Sequence where Element == T? {
>   var someValues: [T] {
>     var result = [T]()
>     for opt in self {
>       if let value = opt { result.append(value) }
>     }
>    return result
>   }
> }

This would be fantastic. I’ve run into it a number of times.



> 
> Minor extensions
> 
> There are a number of minor extensions we can make to the generics system that don’t fundamentally change what one can express in Swift, but which can improve its expressivity.
> 
> *Arbitrary requirements in protocols
> 
> Currently, a new protocol can inherit from other protocols, introduce new associated types, and add new conformance constraints to associated types (by redeclaring an associated type from an inherited protocol). However, one cannot express more general constraints. Building on the example from “Recursive protocol constraints”, we really want the element type of a Sequence’s SubSequence to be the same as the element type of the Sequence, e.g.,
> 
> protocol Sequence {
>   associatedtype Iterator : IteratorProtocol
>   …
>   associatedtype SubSequence : Sequence where SubSequence.Iterator.Element == Iterator.Element
> }
> 
> Hanging the where clause off the associated type is protocol not ideal, but that’s a discussion for another thread.

Definitely run into this one before.


> 
> 
> Default generic arguments 
> 
> Generic parameters could be given the ability to provide default arguments, which would be used in cases where the type argument is not specified and type inference could not determine the type argument. For example:
> 
> public final class Promise<Value, Reason=Error> { … }
> 
> func getRandomPromise() -> Promise<Int, ErrorProtocol> { … }
> 
> var p1: Promise<Int> = …
> var p2: Promise<Int, Error> = p1     // okay: p1 and p2 have the same type Promise<Int, Error>
> var p3: Promise = getRandomPromise() // p3 has type Promise<Int, ErrorProtocol> due to type inference
> 

Also quite useful in eliminating boilerplate.


> 
> Generalized “class” constraints
> 
> The “class” constraint can currently only be used for defining protocols. We could generalize it to associated type and type parameter declarations, e.g.,
> 
> protocol P {
>   associatedtype A : class
> }
> 
> func foo<T : class>(t: T) { }
> 
> As part of this, the magical AnyObject protocol could be replaced with an existential with a class bound, so that it becomes a typealias:
> 
> typealias AnyObject = protocol<class>
> 
> See the “Existentials” section, particularly “Generalized existentials”, for more information.

Another +1. 


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

This one seems extremely important and has immediate utility IMHO.


> 
> Syntactic improvements
> 
> 
> 
> Maybe
> 
> 
> Higher-kinded types
> 
> Higher-kinded types allow one to express the relationship between two different specializations of the same nominal type within a protocol. For example, if we think of the Self type in a protocol as really being “Self<T>”, it allows us to talk about the relationship between “Self<T>” and “Self<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
> }
> 

I don’t think everyday Swift developers will find much use for this feature, but I do think it enables library authors to do some really powerful things with less boilerplate… though your `map` example is actually compelling in and of itself. My own SequenceTypes get map for free, but only the one that returns an array. That’s a bummer.


> 
> Specifying type arguments for uses of generic functions
> 
> The type arguments of a generic function are always determined via type inference. For example, given:
> 
> func f<T>(t: T)
> 
> one cannot directly specify T: either one calls “f” (and T is determined via the argument’s type) or one uses “f” in a context where it is given a particular function type (e.g., “let x: (Int) -> Void = f”  would infer T = Int). We could permit explicit specialization here, e.g.,
> 
> let x = f<Int> // x has type (Int) -> Void

This is one of those annoying little things that can be really helpful and it seems odd that constructors allow specialization but function calls don’t. It’s also a much cleaner way of resolving ambiguity if the compiler is confused.



> 
> Potential removals
> 
> Associated type inference
> 
> Associated type inference is the process by which we infer the type bindings for associated types from other requirements. For example:
> 
> protocol IteratorProtocol {
>   associatedtype Element
>   mutating func next() -> Element?
> }
> 
> struct IntIterator : IteratorProtocol {
>   mutating func next() -> Int? { … }  // use this to infer Element = Int
> }
> 
> Associated type inference is a useful feature. It’s used throughout the standard library, and it helps keep associated types less visible to types that simply want to conform to a protocol. On the other hand, associated type inference is the only place in Swift where we have a global type inference problem: it has historically been a major source of bugs, and implementing it fully and correctly requires a drastically different architecture to the type checker. Is the value of this feature worth keeping global type inference in the Swift language, when we have deliberatively avoided global type inference elsewhere in the language?

I’m totally fine to see it go away. I’ve already gotten into the habit of specifying the types explicitly (due to nonsense errors thrown when the compiler can’t properly infer it). It feels slightly strange because the type inference is spooky action at a distance (especially if the protocol conformance happens in an extension).


> 
> Existentials
> 
> Existentials aren’t really generics per se, but the two systems are closely intertwined due to their mutable dependence on protocols.
> 
> *Generalized existentials
> 
> The restrictions on existential types came from an implementation limitation, but it is reasonable to allow a value of protocol type even when the protocol has Self constraints or associated types. For example, consider IteratorProtocol again and how it could be used as an existential:
> 
> protocol IteratorProtocol {
>   associatedtype Element
>   mutating func next() -> Element?
> }
> 
> let it: IteratorProtocol = …
> it.next()   // if this is permitted, it could return an “Any?”, i.e., the existential that wraps the actual element
> 
> Additionally, it is reasonable to want to constrain the associated types of an existential, e.g., “a Sequence whose element type is String” could be expressed by putting a where clause into “protocol<…>” or “Any<…>” (per “Renaming protocol<…> to Any<…>”):
> 
> let strings: Any<Sequence where .Iterator.Element == String> = [“a”, “b”, “c”]
> 
> The leading “.” indicates that we’re talking about the dynamic type, i.e., the “Self” type that’s conforming to the Sequence protocol. There’s no reason why we cannot support arbitrary “where” clauses within the “Any<…>”. This very-general syntax is a bit unwieldy, but common cases can easily be wrapped up in a generic typealias (see the section “Generic typealiases” above):
> 
> typealias AnySequence<Element> = Any<Sequence where .Iterator.Element == Element>
> let strings: AnySequence<String> = [“a”, “b”, “c”]
> 

Free opinions on the internet are worth what you pay for them, but I’ll just say that if I were in charge of the Swift 3 schedule it wouldn’t ship without this feature. I feel extremely strongly that this is necessary to round out generics support. Trying to write an app that is heavily protocol-oriented and makes use of lots of generics runs into existential (ha!) walls constantly. It forces you to choose 100% anything-goes-dynamic (ala Objective-C) or jump through tons of hoops to get type safety.


> 
> Opening existentials
> 
> Generalized existentials as described above will still have trouble with protocol requirements that involve Self or associated types in function parameters. For example, let’s try to use Equatable as an existential:
> 
> protocol Equatable {
>   func ==(lhs: Self, rhs: Self) -> Bool
>   func !=(lhs: Self, rhs: Self) -> Bool
> }
> 
> let e1: Equatable = …
> let e2: Equatable = …
> if e1 == e2 { … } // error: e1 and e2 don’t necessarily have the same dynamic type
> 
> One explicit way to allow such operations in a type-safe manner is to introduce an “open existential” operation of some sort, which extracts and gives a name to the dynamic type stored inside an existential. For example:
> 
> 	 
> if let storedInE1 = e1 openas T {     // T is a the type of storedInE1, a copy of the value stored in e1
>   if let storedInE2 = e2 as? T {      // is e2 also a T?
>     if storedInE1 == storedInE2 { … } // okay: storedInT1 and storedInE2 are both of type T, which we know is Equatable
>   }
> }

Everything on existentials gets a huge +1 from me.



Overall I’d rate conditional conformance, parameterized extensions, and generalized existentials as the highest priority items. 

Generalized existentials have no effective workarounds and they have a huge impact on the design of API contracts and even how you use protocols themselves so they are a big pain point for me personally.


Russ

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20160404/0a22d55b/attachment.html>