[swift-evolution] [Manifesto] Completing Generics

[Slava Pestov]

Hi Doug,

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

> On Mar 2, 2016, at 5:22 PM, Douglas Gregor via swift-evolution <swift-evolution at swift.org> wrote:
> 
> 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.

Yes! :-)

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

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

However there are a crazier things we should figure out:

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

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

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

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

protocol Collection {
	associatedtype ElementType

	struct Iterator {
		let e: ElementType
	}
}

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

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

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

> *Typealiases in protocols and protocol extensions
> 
> Now that associated types have their own keyword (thanks!), it’s reasonable to bring back “typealias”. Again with the Sequence protocol:
> 
> protocol Sequence {
>   associatedtype Iterator : IteratorProtocol
>   typealias Element = Iterator.Element   // rejoice! now we can refer to SomeSequence.Element rather than SomeSequence.Iterator.Element
> }

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

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

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

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

Would this make sense too:

struct ZipIterator<… Iterators where Iterators : IteratorProtocol>

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

func vararg(let a: A…) {

}

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

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


> There are some natural bounds here: one would need to have actual structural types. One would not be able to extend every type:
> 
> extension<T> T { // error: neither a structural nor a nominal type
> }

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

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

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

protocol BaseProto {}
protocol RefinedProto : BaseProto {}

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

getRefined() -> [RefinedProto]

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

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

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

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

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

Are higher-kinded function values worth discussing too?

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

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

Slava


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20160302/c4fcb2cb/attachment-0001.html>