[swift-evolution] [Manifesto] Completing Generics

[Douglas Gregor]

> On Mar 2, 2016, at 9:24 PM, Slava Pestov <spestov at apple.com> wrote:
> 
> 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 <mailto: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.

Right. Our modeling for this is to essentially pretend that T isn’t part of the generic signature of S, which is wrong. Rather, we want T to be part of the generic signature, but that it’s bound to a particular type within the context.

> 
> 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
> 	}
> }

Presumably you get a different Iterator for each type that conforms to Collection, but I agree that we probably don’t want this.

> 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.

Agreed. Protocols nested within anything should be banned.


> 
>> 
>> 
>> 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?

That could also be added as part of this.

>> *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.

By top-level metadata parameter, you mean create an entry for Element in the witness table? That would eliminate one hop when accessing the metadata,

>> 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?

It’s more nuanced than that, because we need to consider the implied conformances as well.

protocol A { }
protocol B : A { }
protocol C : A { }

struct X<T> { }
extension X : B where T : B { } // implies a conformance to A
extension X : C where T : C { } // problem: also implies a conformance to A

Neither conformance to A is clearly “better”, because these constrained extensions are disjoint. The fix for this is actually to *add* an explicit conformance:

extension X : A where T : A { } // okay: here’s where the conformance to A lives

The important part here is that both the “”B” and “C” extensions have requirements that subsume the requirements of A, so rather than introduce their own implied conformances to A, they leverage the existing conformance from the less-specialized constrained extension.

>> 
>> 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…)) { … }

We could treat it that way.

> 
> 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.

We could just decide that the “array” we get in the callee is only really materialized to the heap if it’s going to escape somewhere, and optimize for the common case where we can do stack allocation in the caller and the callee just directly consumes the result. In other words, I suspect we can optimize this case well (possibly better) without the desugaring. And it might affect our calling convention, so I’d want to make that decision long before we would get variadic generics.

>> 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?

It’s been requested. Perhaps I shouldn’t be so quick to dismiss it.

> 
>> 
>> 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…

Right. 

> 
>> 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?

I’m not particularly motivated by them.

>> 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.

Indeed, this is a problem with my example! We would have to check in both directions: e1 could contain a subclass of e2 or vice versa.

	- Doug


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