Swift 3 Generics


(Matthew Johnson) #1

One of the stated focus areas for Swift 3 is to complete the generics system.

How far along is the design for the “complete” generics system? Is there appetite among the core team to involve the community in evaluating planned features or submitting proposals to complement existing plans?

Also, is there any documentation other than https://github.com/apple/swift/blob/master/docs/Generics.rst describing in detail what the complete vision for the generics system is and what new features will be added in Swift 3 (as well as any generics features that have been decided against for Swift or version 3 specifically)?

Thanks,
Matthew


(Austin Zheng) #2

+1 to this. I would really like to see what is and isn't in scope for Swift
3's generics system. Among other things, it would help focus the
community's proposals and ideas for the evolution of the type system. An
example, people have expressed interest in HKTs, and perhaps a discussion
can be opened on how Swift 3's type system can lay the foundation for
further changes.

Austin

···

On Thu, Dec 10, 2015 at 3:45 PM, Matthew Johnson via swift-evolution < swift-evolution@swift.org> wrote:

One of the stated focus areas for Swift 3 is to complete the generics
system.

How far along is the design for the “complete” generics system? Is there
appetite among the core team to involve the community in evaluating planned
features or submitting proposals to complement existing plans?

Also, is there any documentation other than
https://github.com/apple/swift/blob/master/docs/Generics.rst describing
in detail what the complete vision for the generics system is and what new
features will be added in Swift 3 (as well as any generics features that
have been decided against for Swift or version 3 specifically)?

Thanks,
Matthew

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


(Dmitri Gribenko) #3

As far as I understand, the first priority is not fixing issues in the
current type checker and runtime for existing generics features (e.g.,
implement recursive generic constraints to eliminate protocol Indexable
from the standard library), and incremental improvements for the current
generics system that allow the standard library to properly express and
constrain existing concepts -- like 'where' constraints on associated types.

Dmitri

···

On Thu, Dec 10, 2015 at 4:14 PM, Austin Zheng via swift-evolution < swift-evolution@swift.org> wrote:

+1 to this. I would really like to see what is and isn't in scope for
Swift 3's generics system. Among other things, it would help focus the
community's proposals and ideas for the evolution of the type system. An
example, people have expressed interest in HKTs, and perhaps a discussion
can be opened on how Swift 3's type system can lay the foundation for
further changes.

--
main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if
(j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr@gmail.com>*/


(Slava Pestov) #4

+1 to this. I would really like to see what is and isn't in scope for Swift 3's generics system. Among other things, it would help focus the community's proposals and ideas for the evolution of the type system. An example, people have expressed interest in HKTs, and perhaps a discussion can be opened on how Swift 3's type system can lay the foundation for further changes.

Off the top of my head, the following are not currently supported and are requirements for any kind of ‘complete’ generics system:

- Generic types nested inside generic functions
- Generic types nested inside generic types
- Generic functions nested inside generic functions which capture values or outer generic types

All of these would be easier once we rip out PolymorphicFunctionType and GenericParamList in favor of consistently using GenericFunctionType and GenericSignature everywhere. This is what Sema’s “getType()” vs “getInterfaceType()” business on ValueDecls is all about. Once the old “contextual” types are gone, some tricky parallel code paths for building up the two representations of generic function signatures will be much simpler and more robust, and the missing functionality added easier. This is blocked on a number of architectural changes, for example SIL type lowering has to be able to associate a GenericTypeParamType with the GenericSignature that contains it, and right now it can’t really do that except for one distinguished GenericSignature, which forces us to use non-interface types when forming calls and such.

A large number of compiler_crashers are instances of the above three unsupported constructs which trip Sema bugs — even though we have diagnostics that catch most of these, the fact that the type checker doesn’t just stop after diagnosing once means that internal inconsistencies resulting an incomplete implementation of generics can trigger assertions down the road.

Slava

···

On Dec 10, 2015, at 4:14 PM, Austin Zheng via swift-evolution <swift-evolution@swift.org> wrote:

Austin

On Thu, Dec 10, 2015 at 3:45 PM, Matthew Johnson via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:
One of the stated focus areas for Swift 3 is to complete the generics system.

How far along is the design for the “complete” generics system? Is there appetite among the core team to involve the community in evaluating planned features or submitting proposals to complement existing plans?

Also, is there any documentation other than https://github.com/apple/swift/blob/master/docs/Generics.rst describing in detail what the complete vision for the generics system is and what new features will be added in Swift 3 (as well as any generics features that have been decided against for Swift or version 3 specifically)?

Thanks,
Matthew

_______________________________________________
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


(Douglas Gregor) #5

One of the stated focus areas for Swift 3 is to complete the generics system.

How far along is the design for the “complete” generics system?

There’s a loose shared understanding of the pieces we need among the compiler and standard library developers that have been co-evolving the generics system, but it’s not written down in any single place.

Is there appetite among the core team to involve the community in evaluating planned features or submitting proposals to complement existing plans?

Yes, absolutely. I feel like we (the core team) need to articulate our vision here—what we feel we need to accomplish (in features, in the standard library API, in the implementation) in Swift 3 vs. what we believe we can introduce later on, how the pieces all fit together, etc.—to help facilitate those discussions.

Also, is there any documentation other than https://github.com/apple/swift/blob/master/docs/Generics.rst describing in detail what the complete vision for the generics system is and what new features will be added in Swift 3 (as well as any generics features that have been decided against for Swift or version 3 specifically)?

No, that document is the best overall documentation for the vision of the generics system, despite being mostly untouched for more than two years and lacking newer features (protocol extensions, anyone?).

So, we need to write up a document describing our vision here. It’s going to take a little time, both because it’s a nontrivial task and because the likely principal authors are also engaged in other large Swift 3 tasks (e.g., https://github.com/apple/swift-evolution/blob/master/proposals/0005-objective-c-name-translation.md)

  - Doug

···

On Dec 10, 2015, at 3:45 PM, Matthew Johnson via swift-evolution <swift-evolution@swift.org> wrote:


(Matthew Johnson) #6

Dmitri, Slava and Doug thank you for taking the time to respond. I apologize for not thanking you sooner.

Since the core team has a loosely shared understanding of the goals but hasn't had time to write it down yet I thought it might be helpful if I put together a summary of the features that seem to me like obvious candidates for completing the current generic system. If I have missed anything significant please point that out.

I'm placing a "**" next to items that I beleive I have seen mentioned by the core team as desired features. This is based on memory and may be innacurate or may be based on desires expressed, but not necessarily pinned to the Swift 3 timeline.

I'm hoping the core team might be able to indicate which items are likely to be part of the work you're doing on Swift 3, which items you might be interested in the community contributing to, and which items are unliekly to be considered during the Swift 3 timeframe even with community involvement. This could help interested contributors start thinking about what they might be interested in working on while we wait for a more complete document describing the vision.

- ** generic typealias

- allow protocols to specify a non-covarying Self in static method declarations (a possible solution to the problem of conforming non-final classes in Cocoa to protocols containing factory methods)

- extensions
  - ** allow same type constraints
  - ** allow protocol conformance in constrained extensions
  - allow protocol conformance in protocol extensions

- associated type constraints
  - use of Self as a superclass constraint
  - ** where clause constraining inidividual associated types
  - ** where clause relating multiple assocated types

- existentials for protocols with associated types
  - protocol existentials don't conform to the protocol itself
  - ** fully bound: protocol<GeneratorType where Element == Int>
  - ** fully constrained: protocol<GeneratorType where Element: CustomStringConvertible>
  - partially bound / constrained - allow access to members only mentioning constrained associated types
  - ** unbound - allow access to members not mentioning Self or associated types
  - composition: protocol<P1, P2 where P1.Associated: P3, P2.Associated == Int, P1.Other == P2.Other>

- nesting (per Slava's email)
  - ** Generic types nested inside generic functions
  - ** Generic types nested inside generic types
  - ** Generic functions nested inside generic functions which capture values or outer generic types

Some things that I expect are out of scope for Swift 3 but am mentioning for completeness / confirmation of that:

- variadic generics
- higher kinded types
- higher rank types

Thanks,
Matthew

···

On Dec 11, 2015, at 11:24 PM, Douglas Gregor <dgregor@apple.com> wrote:

On Dec 10, 2015, at 3:45 PM, Matthew Johnson via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

One of the stated focus areas for Swift 3 is to complete the generics system.

How far along is the design for the “complete” generics system?

There’s a loose shared understanding of the pieces we need among the compiler and standard library developers that have been co-evolving the generics system, but it’s not written down in any single place.

Is there appetite among the core team to involve the community in evaluating planned features or submitting proposals to complement existing plans?

Yes, absolutely. I feel like we (the core team) need to articulate our vision here—what we feel we need to accomplish (in features, in the standard library API, in the implementation) in Swift 3 vs. what we believe we can introduce later on, how the pieces all fit together, etc.—to help facilitate those discussions.

Also, is there any documentation other than https://github.com/apple/swift/blob/master/docs/Generics.rst describing in detail what the complete vision for the generics system is and what new features will be added in Swift 3 (as well as any generics features that have been decided against for Swift or version 3 specifically)?

No, that document is the best overall documentation for the vision of the generics system, despite being mostly untouched for more than two years and lacking newer features (protocol extensions, anyone?).

So, we need to write up a document describing our vision here. It’s going to take a little time, both because it’s a nontrivial task and because the likely principal authors are also engaged in other large Swift 3 tasks (e.g., https://github.com/apple/swift-evolution/blob/master/proposals/0005-objective-c-name-translation.md)

  - Doug


(Dmitri Gribenko) #7

Hi Matthew,

Thank you for putting together this list. I will be answering from the
standard library perspective.

- ** generic typealias

I don't know of a usecase in the standard library.

- allow protocols to specify a non-covarying Self in static method

declarations (a possible solution to the problem of conforming non-final
classes in Cocoa to protocols containing factory methods)

I don't know of a usecase in the standard library.

- extensions
- ** allow same type constraints
- ** allow protocol conformance in constrained extensions
- allow protocol conformance in protocol extensions

Yes, the standard library needs all of these.

- associated type constraints
- use of Self as a superclass constraint
- ** where clause constraining inidividual associated types
- ** where clause relating multiple assocated types

The standard library needs the 'where' clauses, but not the 'Self'
superclass constraint.

- existentials for protocols with associated types
- protocol existentials don't conform to the protocol itself
- ** fully bound: protocol<GeneratorType where Element == Int>
- ** fully constrained: protocol<GeneratorType where Element:
>
- partially bound / constrained - allow access to members only mentioning
constrained associated types
- ** unbound - allow access to members not mentioning Self or associated
types
- composition: protocol<P1, P2 where P1.Associated: P3, P2.Associated ==
Int, P1.Other == P2.Other>

Depending on the details, this might replace AnySequence / AnyCollection.

- nesting (per Slava's email)
- ** Generic types nested inside generic functions
- ** Generic types nested inside generic types
- ** Generic functions nested inside generic functions which capture
values or outer generic types

The standard library needs generic types nested inside generic types to
move types from the top level, like moving DictionaryIndex into Dictionary.

Another thing that we need is recursive associated type constraints:

protocol CollectionType {
  typealias SubSequence : CollectionType
}

Dmitri

···

On Tue, Dec 15, 2015 at 7:25 PM, Matthew Johnson via swift-evolution < swift-evolution@swift.org> wrote:

--
main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if
(j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr@gmail.com>*/


(Douglas Gregor) #8

Hi Matthew,

Dmitri, Slava and Doug thank you for taking the time to respond. I apologize for not thanking you sooner.

Since the core team has a loosely shared understanding of the goals but hasn't had time to write it down yet I thought it might be helpful if I put together a summary of the features that seem to me like obvious candidates for completing the current generic system. If I have missed anything significant please point that out.

This is helpful, thank you!

Lots of comments below. An overarching theme here is that I'm trying to scope down the list to what we need to achieve ABI stability and an expressive library fewer features means we're more likely to succeed with better quality.

I'm placing a "**" next to items that I beleive I have seen mentioned by the core team as desired features. This is based on memory and may be innacurate or may be based on desires expressed, but not necessarily pinned to the Swift 3 timeline.

I'm hoping the core team might be able to indicate which items are likely to be part of the work you're doing on Swift 3, which items you might be interested in the community contributing to, and which items are unliekly to be considered during the Swift 3 timeframe even with community involvement. This could help interested contributors start thinking about what they might be interested in working on while we wait for a more complete document describing the vision.

- ** generic typealias

This isn't high on my list. It's a good feature, and I want it someday, but introducing generic typealiases won't have any impact on the ABI and therefore can wait IMO.

- allow protocols to specify a non-covarying Self in static method declarations (a possible solution to the problem of conforming non-final classes in Cocoa to protocols containing factory methods)

Maybe. This isn't terribly high on my list, but in also behind on the discussion.

- extensions
  - ** allow same type constraints

I'm assuming you mean an extension like

  extension Array where Element == String {}

Yes, it's something we want to support

  - ** allow protocol conformance in constrained extensions

This is something like:

  extension Array : Equatable where Element : Equatable {}

It is very very high priority for Swift 3.

  - allow protocol conformance in protocol extensions

This is something like:

  extension CollectionType : Equatable where Generator.Element : Equatable {}

This is probably not a priority for Swift 3. It seems very cool, and I've advocated for similar features in the past (in more static generics systems), but the potential for ambiguities with such definitions is very high and the runtime cost for asking questions such as "is this T Equatable?" can be very high when this feature is in play.

- associated type constraints
  - use of Self as a superclass constraint

This wasn't on my list at all. Care to elaborate on why this is important?

  - ** where clause constraining inidividual associated types
  - ** where clause relating multiple assocated types

Yes to both. We need the to properly express some relationships in the standard library types, such as a SubSequence's Element type matching the Element type of the sequence itself.

- existentials for protocols with associated types
  - protocol existentials don't conform to the protocol itself
  - ** fully bound: protocol<GeneratorType where Element == Int>
  - ** fully constrained: protocol<GeneratorType where Element: CustomStringConvertible>
  - partially bound / constrained - allow access to members only mentioning constrained associated types
  - ** unbound - allow access to members not mentioning Self or associated types
  - composition: protocol<P1, P2 where P1.Associated: P3, P2.Associated == Int, P1.Other == P2.Other>

This one is tough. It is a very, very common user request and existentials are painfully under implemented in Swift. On the other hand, it's an additive feature that isn't likely (IMO!) to be important for ABI stabilization in the language or library. So, I would put it out of scope for Swift 3.

- nesting (per Slava's email)
  - ** Generic types nested inside generic functions
  - ** Generic types nested inside generic types
  - ** Generic functions nested inside generic functions which capture values or outer generic types

I think Slava and I disagree on this one :wink:

I don't consider this critical for Swift 3. The compiler will greatly improve simply by making this work (because the dumb assumptions that block this feature likely trigger additional bugs), but we don't need to allow it for ABI stability. There are a handful of places in the standard library where we've had to promote a type that would normally be nested to the top level to work around this, but we could live with that as a smallish ABI wart in the long term and introduce generic typealiases to clean up the syntax once those features become available.

Some things that I expect are out of scope for Swift 3 but am mentioning for completeness / confirmation of that:

- variadic generics
- higher kinded types
- higher rank types

Agreed that all are out of scope for Swift 3. The first is a feature of particular interest to me... But absolutely is out of scope. I also want to eventually use variadic generics to extend arbitrary length tuples of Equatable types to make them Equatable, for example :wink:

A couple features you didn't mention that I consider in scope for Swift 3 generics:

- generic subscripts (the standard library might need these), e.g.,

  subscript<C : SequenceType where C.Generator.Element == Index> (indices: C) -> [Index]

- recursive protocol constraints, where an associated type can be stated to conform to its enclosing protocol (directly or indirectly), eg,

  protocol SequenceType {
    typealias SubSequence : SequenceType
  }

- operators defined in types (only indirectly related to generics):

  extension Array where Element : Equatable {
    func ==(lhs: Array, rhs: Array) -> Bool { ... }
  }

- "real" default implementations in protocols. It looks like a syntactic simplification from
Putting the definition in an extension, but putting the default implementation in the protocol itself has an important effect on resilience: one should be able to add requirements to a protocol without breaking ABI so long as those requirements have a default implementation.

Several of these (recursive constraints, where clauses placing requirements on associated types in protocols, etc) are partly aimed at eliminated many of the underscored protocols in the standard library, because we don't want them to be part of the library ABI.

I suspect I'll remember other small things, but that's the "big" list... and it's size perhaps illustrates why we need to choose carefully to maintain focus.

  - Doug

···

Sent from my iPhone

On Dec 15, 2015, at 7:25 PM, Matthew Johnson <matthew@anandabits.com> wrote:

Thanks,
Matthew

On Dec 11, 2015, at 11:24 PM, Douglas Gregor <dgregor@apple.com> wrote:

On Dec 10, 2015, at 3:45 PM, Matthew Johnson via swift-evolution <swift-evolution@swift.org> wrote:

One of the stated focus areas for Swift 3 is to complete the generics system.

How far along is the design for the “complete” generics system?

There’s a loose shared understanding of the pieces we need among the compiler and standard library developers that have been co-evolving the generics system, but it’s not written down in any single place.

Is there appetite among the core team to involve the community in evaluating planned features or submitting proposals to complement existing plans?

Yes, absolutely. I feel like we (the core team) need to articulate our vision here—what we feel we need to accomplish (in features, in the standard library API, in the implementation) in Swift 3 vs. what we believe we can introduce later on, how the pieces all fit together, etc.—to help facilitate those discussions.

Also, is there any documentation other than https://github.com/apple/swift/blob/master/docs/Generics.rst describing in detail what the complete vision for the generics system is and what new features will be added in Swift 3 (as well as any generics features that have been decided against for Swift or version 3 specifically)?

No, that document is the best overall documentation for the vision of the generics system, despite being mostly untouched for more than two years and lacking newer features (protocol extensions, anyone?).

So, we need to write up a document describing our vision here. It’s going to take a little time, both because it’s a nontrivial task and because the likely principal authors are also engaged in other large Swift 3 tasks (e.g., https://github.com/apple/swift-evolution/blob/master/proposals/0005-objective-c-name-translation.md)

  - Doug


(Joe Groff) #9

It could be important to stabilizing the standard library, since existentials ought to replace the ad-hoc type-erased AnySequence etc. wrappers that are currently hand-written in the standard library.

-Joe

···

On Dec 15, 2015, at 8:45 PM, Douglas Gregor via swift-evolution <swift-evolution@swift.org> wrote:

This one is tough. It is a very, very common user request and existentials are painfully under implemented in Swift. On the other hand, it's an additive feature that isn't likely (IMO!) to be important for ABI stabilization in the language or library. So, I would put it out of scope for Swift 3.


(David Waite) #10

I’m not sure about the runtime cost of non-“existential" protocols like Equatable, which can’t be casted to at runtime today. Of course, this makes that there are multiple ‘kinds’ of protocols with different usage that are declared in the same way more complex than it is today.

-DW

···

On Dec 15, 2015, at 9:45 PM, Douglas Gregor via swift-evolution <swift-evolution@swift.org> wrote:

This is something like:

  extension CollectionType : Equatable where Generator.Element : Equatable {}

This is probably not a priority for Swift 3. It seems very cool, and I've advocated for similar features in the past (in more static generics systems), but the potential for ambiguities with such definitions is very high and the runtime cost for asking questions such as "is this T Equatable?" can be very high when this feature is in play.


(Matthew Johnson) #11

Hi Matthew,

Sent from my iPhone

Dmitri, Slava and Doug thank you for taking the time to respond. I apologize for not thanking you sooner.

Since the core team has a loosely shared understanding of the goals but hasn't had time to write it down yet I thought it might be helpful if I put together a summary of the features that seem to me like obvious candidates for completing the current generic system. If I have missed anything significant please point that out.

This is helpful, thank you!

You’re welcome! I appreciate the responses as well. Thank you!

Lots of comments below. An overarching theme here is that I'm trying to scope down the list to what we need to achieve ABI stability and an expressive library fewer features means we're more likely to succeed with better quality.

I'm placing a "**" next to items that I beleive I have seen mentioned by the core team as desired features. This is based on memory and may be innacurate or may be based on desires expressed, but not necessarily pinned to the Swift 3 timeline.

I'm hoping the core team might be able to indicate which items are likely to be part of the work you're doing on Swift 3, which items you might be interested in the community contributing to, and which items are unliekly to be considered during the Swift 3 timeframe even with community involvement. This could help interested contributors start thinking about what they might be interested in working on while we wait for a more complete document describing the vision.

- ** generic typealias

This isn't high on my list. It's a good feature, and I want it someday, but introducing generic typealiases won't have any impact on the ABI and therefore can wait IMO.

- allow protocols to specify a non-covarying Self in static method declarations (a possible solution to the problem of conforming non-final classes in Cocoa to protocols containing factory methods)

Maybe. This isn't terribly high on my list, but in also behind on the discussion.

This is related to the thread Joe started on “Making protocol conformance inheritance controllable”. It would solve some (probably not all) of the use cases that prompted that idea. Of course it solves the ones I have run into which is part of the reason I included it here. Any solution to this problem would be extremely useful - it doesn’t need to be this specific solution.

- extensions
  - ** allow same type constraints

I'm assuming you mean an extension like

  extension Array where Element == String {}

Yes, it's something we want to support

Yep, that’s what I meant.

  - ** allow protocol conformance in constrained extensions

This is something like:

  extension Array : Equatable where Element : Equatable {}

It is very very high priority for Swift 3.

  - allow protocol conformance in protocol extensions

This is something like:

  extension CollectionType : Equatable where Generator.Element : Equatable {}

This is probably not a priority for Swift 3. It seems very cool, and I've advocated for similar features in the past (in more static generics systems), but the potential for ambiguities with such definitions is very high and the runtime cost for asking questions such as "is this T Equatable?" can be very high when this feature is in play.

- associated type constraints
  - use of Self as a superclass constraint

This wasn't on my list at all. Care to elaborate on why this is important?

I included this one primarily because I know it isn’t possible but other superclass constraints are. Removing this limitation seems like a natural part of “completing” the current generics system. But I don’t have concrete uses for it and if implementation is complex I wouldn’t consider it a priority.

  - ** where clause constraining inidividual associated types
  - ** where clause relating multiple assocated types

Yes to both. We need the to properly express some relationships in the standard library types, such as a SubSequence's Element type matching the Element type of the sequence itself.

- existentials for protocols with associated types
  - protocol existentials don't conform to the protocol itself
  - ** fully bound: protocol<GeneratorType where Element == Int>
  - ** fully constrained: protocol<GeneratorType where Element: CustomStringConvertible>
  - partially bound / constrained - allow access to members only mentioning constrained associated types
  - ** unbound - allow access to members not mentioning Self or associated types
  - composition: protocol<P1, P2 where P1.Associated: P3, P2.Associated == Int, P1.Other == P2.Other>

This one is tough. It is a very, very common user request and existentials are painfully under implemented in Swift. On the other hand, it's an additive feature that isn't likely (IMO!) to be important for ABI stabilization in the language or library. So, I would put it out of scope for Swift 3.

I’m going to hope Joe’s comments about stabilizing the standard library win out. Ad-hoc type erasure is painful enough that it influences design decisions. It would be great to see existentials see at least enough improvement to cover the standard library cases.

If this is an area that could be impacted by community involvement please let us know! I think you would find people willing to help out. As you noted, it’s one of the bigger gripes people seem to have about Swift.

- nesting (per Slava's email)
  - ** Generic types nested inside generic functions
  - ** Generic types nested inside generic types
  - ** Generic functions nested inside generic functions which capture values or outer generic types

I think Slava and I disagree on this one :wink:

I don't consider this critical for Swift 3. The compiler will greatly improve simply by making this work (because the dumb assumptions that block this feature likely trigger additional bugs), but we don't need to allow it for ABI stability. There are a handful of places in the standard library where we've had to promote a type that would normally be nested to the top level to work around this, but we could live with that as a smallish ABI wart in the long term and introduce generic typealiases to clean up the syntax once those features become available.

Some things that I expect are out of scope for Swift 3 but am mentioning for completeness / confirmation of that:

- variadic generics
- higher kinded types
- higher rank types

Agreed that all are out of scope for Swift 3. The first is a feature of particular interest to me... But absolutely is out of scope. I also want to eventually use variadic generics to extend arbitrary length tuples of Equatable types to make them Equatable, for example :wink:

A couple features you didn't mention that I consider in scope for Swift 3 generics:

- generic subscripts (the standard library might need these), e.g.,

  subscript<C : SequenceType where C.Generator.Element == Index> (indices: C) -> [Index]

Thanks for mentioning this. I really want to see this one. I have use cases for it. Not sure how I forgot to include it in my list.

- recursive protocol constraints, where an associated type can be stated to conform to its enclosing protocol (directly or indirectly), eg,

  protocol SequenceType {
    typealias SubSequence : SequenceType
  }

- operators defined in types (only indirectly related to generics):

  extension Array where Element : Equatable {
    func ==(lhs: Array, rhs: Array) -> Bool { ... }
  }

- "real" default implementations in protocols. It looks like a syntactic simplification from
Putting the definition in an extension, but putting the default implementation in the protocol itself has an important effect on resilience: one should be able to add requirements to a protocol without breaking ABI so long as those requirements have a default implementation.

I appreciate your adding additional items in addition to commenting on my list! Thank you!

···

On Dec 15, 2015, at 10:45 PM, Douglas Gregor <dgregor@apple.com> wrote:
On Dec 15, 2015, at 7:25 PM, Matthew Johnson <matthew@anandabits.com <mailto:matthew@anandabits.com>> wrote:

Several of these (recursive constraints, where clauses placing requirements on associated types in protocols, etc) are partly aimed at eliminated many of the underscored protocols in the standard library, because we don't want them to be part of the library ABI.

I suspect I'll remember other small things, but that's the "big" list... and it's size perhaps illustrates why we need to choose carefully to maintain focus.

  - Doug

Thanks,
Matthew

On Dec 11, 2015, at 11:24 PM, Douglas Gregor <dgregor@apple.com <mailto:dgregor@apple.com>> wrote:

On Dec 10, 2015, at 3:45 PM, Matthew Johnson via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

One of the stated focus areas for Swift 3 is to complete the generics system.

How far along is the design for the “complete” generics system?

There’s a loose shared understanding of the pieces we need among the compiler and standard library developers that have been co-evolving the generics system, but it’s not written down in any single place.

Is there appetite among the core team to involve the community in evaluating planned features or submitting proposals to complement existing plans?

Yes, absolutely. I feel like we (the core team) need to articulate our vision here—what we feel we need to accomplish (in features, in the standard library API, in the implementation) in Swift 3 vs. what we believe we can introduce later on, how the pieces all fit together, etc.—to help facilitate those discussions.

Also, is there any documentation other than https://github.com/apple/swift/blob/master/docs/Generics.rst describing in detail what the complete vision for the generics system is and what new features will be added in Swift 3 (as well as any generics features that have been decided against for Swift or version 3 specifically)?

No, that document is the best overall documentation for the vision of the generics system, despite being mostly untouched for more than two years and lacking newer features (protocol extensions, anyone?).

So, we need to write up a document describing our vision here. It’s going to take a little time, both because it’s a nontrivial task and because the likely principal authors are also engaged in other large Swift 3 tasks (e.g., https://github.com/apple/swift-evolution/blob/master/proposals/0005-objective-c-name-translation.md)

  - Doug


(Matthew Johnson) #12

I’ve been going through some notes and realized I missed a couple of things when I put my list together:

* access control for extensions declaring protocol conformances
* memberwise deriving of protocol implementations

I also found an example of the “same type constraints” item I mentioned and it is different than discussed so far:

struct S<T, U> {}
extension S where T == U {} // error

Are you considering any of these for Swift 3?

Access control for extensions declaring protocol conformances seems is the highest priority out of this group IMO.

Matthew

···

On Dec 15, 2015, at 10:45 PM, Douglas Gregor <dgregor@apple.com> wrote:

Hi Matthew,

Sent from my iPhone

On Dec 15, 2015, at 7:25 PM, Matthew Johnson <matthew@anandabits.com <mailto:matthew@anandabits.com>> wrote:

Dmitri, Slava and Doug thank you for taking the time to respond. I apologize for not thanking you sooner.

Since the core team has a loosely shared understanding of the goals but hasn't had time to write it down yet I thought it might be helpful if I put together a summary of the features that seem to me like obvious candidates for completing the current generic system. If I have missed anything significant please point that out.

This is helpful, thank you!

Lots of comments below. An overarching theme here is that I'm trying to scope down the list to what we need to achieve ABI stability and an expressive library fewer features means we're more likely to succeed with better quality.

I'm placing a "**" next to items that I beleive I have seen mentioned by the core team as desired features. This is based on memory and may be innacurate or may be based on desires expressed, but not necessarily pinned to the Swift 3 timeline.

I'm hoping the core team might be able to indicate which items are likely to be part of the work you're doing on Swift 3, which items you might be interested in the community contributing to, and which items are unliekly to be considered during the Swift 3 timeframe even with community involvement. This could help interested contributors start thinking about what they might be interested in working on while we wait for a more complete document describing the vision.

- ** generic typealias

This isn't high on my list. It's a good feature, and I want it someday, but introducing generic typealiases won't have any impact on the ABI and therefore can wait IMO.

- allow protocols to specify a non-covarying Self in static method declarations (a possible solution to the problem of conforming non-final classes in Cocoa to protocols containing factory methods)

Maybe. This isn't terribly high on my list, but in also behind on the discussion.

- extensions
  - ** allow same type constraints

I'm assuming you mean an extension like

  extension Array where Element == String {}

Yes, it's something we want to support

  - ** allow protocol conformance in constrained extensions

This is something like:

  extension Array : Equatable where Element : Equatable {}

It is very very high priority for Swift 3.

  - allow protocol conformance in protocol extensions

This is something like:

  extension CollectionType : Equatable where Generator.Element : Equatable {}

This is probably not a priority for Swift 3. It seems very cool, and I've advocated for similar features in the past (in more static generics systems), but the potential for ambiguities with such definitions is very high and the runtime cost for asking questions such as "is this T Equatable?" can be very high when this feature is in play.

- associated type constraints
  - use of Self as a superclass constraint

This wasn't on my list at all. Care to elaborate on why this is important?

  - ** where clause constraining inidividual associated types
  - ** where clause relating multiple assocated types

Yes to both. We need the to properly express some relationships in the standard library types, such as a SubSequence's Element type matching the Element type of the sequence itself.

- existentials for protocols with associated types
  - protocol existentials don't conform to the protocol itself
  - ** fully bound: protocol<GeneratorType where Element == Int>
  - ** fully constrained: protocol<GeneratorType where Element: CustomStringConvertible>
  - partially bound / constrained - allow access to members only mentioning constrained associated types
  - ** unbound - allow access to members not mentioning Self or associated types
  - composition: protocol<P1, P2 where P1.Associated: P3, P2.Associated == Int, P1.Other == P2.Other>

This one is tough. It is a very, very common user request and existentials are painfully under implemented in Swift. On the other hand, it's an additive feature that isn't likely (IMO!) to be important for ABI stabilization in the language or library. So, I would put it out of scope for Swift 3.

- nesting (per Slava's email)
  - ** Generic types nested inside generic functions
  - ** Generic types nested inside generic types
  - ** Generic functions nested inside generic functions which capture values or outer generic types

I think Slava and I disagree on this one :wink:

I don't consider this critical for Swift 3. The compiler will greatly improve simply by making this work (because the dumb assumptions that block this feature likely trigger additional bugs), but we don't need to allow it for ABI stability. There are a handful of places in the standard library where we've had to promote a type that would normally be nested to the top level to work around this, but we could live with that as a smallish ABI wart in the long term and introduce generic typealiases to clean up the syntax once those features become available.

Some things that I expect are out of scope for Swift 3 but am mentioning for completeness / confirmation of that:

- variadic generics
- higher kinded types
- higher rank types

Agreed that all are out of scope for Swift 3. The first is a feature of particular interest to me... But absolutely is out of scope. I also want to eventually use variadic generics to extend arbitrary length tuples of Equatable types to make them Equatable, for example :wink:

A couple features you didn't mention that I consider in scope for Swift 3 generics:

- generic subscripts (the standard library might need these), e.g.,

  subscript<C : SequenceType where C.Generator.Element == Index> (indices: C) -> [Index]

- recursive protocol constraints, where an associated type can be stated to conform to its enclosing protocol (directly or indirectly), eg,

  protocol SequenceType {
    typealias SubSequence : SequenceType
  }

- operators defined in types (only indirectly related to generics):

  extension Array where Element : Equatable {
    func ==(lhs: Array, rhs: Array) -> Bool { ... }
  }

- "real" default implementations in protocols. It looks like a syntactic simplification from
Putting the definition in an extension, but putting the default implementation in the protocol itself has an important effect on resilience: one should be able to add requirements to a protocol without breaking ABI so long as those requirements have a default implementation.

Several of these (recursive constraints, where clauses placing requirements on associated types in protocols, etc) are partly aimed at eliminated many of the underscored protocols in the standard library, because we don't want them to be part of the library ABI.

I suspect I'll remember other small things, but that's the "big" list... and it's size perhaps illustrates why we need to choose carefully to maintain focus.

  - Doug

Thanks,
Matthew

On Dec 11, 2015, at 11:24 PM, Douglas Gregor <dgregor@apple.com <mailto:dgregor@apple.com>> wrote:

On Dec 10, 2015, at 3:45 PM, Matthew Johnson via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

One of the stated focus areas for Swift 3 is to complete the generics system.

How far along is the design for the “complete” generics system?

There’s a loose shared understanding of the pieces we need among the compiler and standard library developers that have been co-evolving the generics system, but it’s not written down in any single place.

Is there appetite among the core team to involve the community in evaluating planned features or submitting proposals to complement existing plans?

Yes, absolutely. I feel like we (the core team) need to articulate our vision here—what we feel we need to accomplish (in features, in the standard library API, in the implementation) in Swift 3 vs. what we believe we can introduce later on, how the pieces all fit together, etc.—to help facilitate those discussions.

Also, is there any documentation other than https://github.com/apple/swift/blob/master/docs/Generics.rst describing in detail what the complete vision for the generics system is and what new features will be added in Swift 3 (as well as any generics features that have been decided against for Swift or version 3 specifically)?

No, that document is the best overall documentation for the vision of the generics system, despite being mostly untouched for more than two years and lacking newer features (protocol extensions, anyone?).

So, we need to write up a document describing our vision here. It’s going to take a little time, both because it’s a nontrivial task and because the likely principal authors are also engaged in other large Swift 3 tasks (e.g., https://github.com/apple/swift-evolution/blob/master/proposals/0005-objective-c-name-translation.md)

  - Doug


(Slava Pestov) #13

- nesting (per Slava's email)
  - ** Generic types nested inside generic functions
  - ** Generic types nested inside generic types
  - ** Generic functions nested inside generic functions which capture values or outer generic types

I think Slava and I disagree on this one :wink:

I think mostly we agree actually. :slight_smile: Your list of generics ABI tasks makes sense to me.

I don’t have any strong opinions about specific features going in now or later to be honest. I think in the long term we will likely end up implementing most of the features on Matthew's list, in one form or another. To keep things manageable we need to keep simplifying the conceptual model and paying off technical debt along the way.

So what I’d like to contribute to this effort is helping brainstorm what refactoring work needs to be done, and how to break down into manageable chunks since we can’t realistically fix everything. Also, in general I feel we haven’t nailed down the full conceptual model for the implementation of generics yet, but this is hard to quantify.

I don't consider this critical for Swift 3. The compiler will greatly improve simply by making this work (because the dumb assumptions that block this feature likely trigger additional bugs), but we don't need to allow it for ABI stability.

I’m just happy now that nested generics don’t crash as much in Sema. It always bothered me when forgetting a ‘}’ could make the compiler crash just because you accidentally introduced nested generic context. :slight_smile:

I suspect I'll remember other small things, but that's the "big" list... and it's size perhaps illustrates why we need to choose carefully to maintain focus.

Not ABI obviously, but what are your thoughts of adding a new ‘assoctype’ keyword instead of overloading ‘typealias’ in protocols? This has come up several times on this list and on Twitter. I’m quite like the idea.

Also, a frequent user request is self-conforming protocols. Personally I have mixed feelings about this — the implementation Joe and I came up with would require double-dispatching through a per-protocol witness table that opened existentials, which creates some conceptual difficulties which may or may not be possible to fix with some hacks, eg if T : P and T is bound to P, existential erasure of T to P would produce a double-wrapped existential P, which would create problems for casts among other things. I haven’t thought about if this impacts the ABI or not.

Slava

···

On Dec 15, 2015, at 8:45 PM, Douglas Gregor via swift-evolution <swift-evolution@swift.org> wrote:

  - Doug

Thanks,
Matthew

On Dec 11, 2015, at 11:24 PM, Douglas Gregor <dgregor@apple.com <mailto:dgregor@apple.com>> wrote:

On Dec 10, 2015, at 3:45 PM, Matthew Johnson via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

One of the stated focus areas for Swift 3 is to complete the generics system.

How far along is the design for the “complete” generics system?

There’s a loose shared understanding of the pieces we need among the compiler and standard library developers that have been co-evolving the generics system, but it’s not written down in any single place.

Is there appetite among the core team to involve the community in evaluating planned features or submitting proposals to complement existing plans?

Yes, absolutely. I feel like we (the core team) need to articulate our vision here—what we feel we need to accomplish (in features, in the standard library API, in the implementation) in Swift 3 vs. what we believe we can introduce later on, how the pieces all fit together, etc.—to help facilitate those discussions.

Also, is there any documentation other than https://github.com/apple/swift/blob/master/docs/Generics.rst describing in detail what the complete vision for the generics system is and what new features will be added in Swift 3 (as well as any generics features that have been decided against for Swift or version 3 specifically)?

No, that document is the best overall documentation for the vision of the generics system, despite being mostly untouched for more than two years and lacking newer features (protocol extensions, anyone?).

So, we need to write up a document describing our vision here. It’s going to take a little time, both because it’s a nontrivial task and because the likely principal authors are also engaged in other large Swift 3 tasks (e.g., https://github.com/apple/swift-evolution/blob/master/proposals/0005-objective-c-name-translation.md)

  - Doug

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


(Douglas Gregor) #14

The non-“existential” protocol issue is actually separate. We can illustrate the issues with far simpler protocols:

  protocol P { }
  protocol Q : P { }
  protocol R { }
  protocol S { }

  extension P : R { } // #1: every P is also an R
  extension R : S { } // #2: every R is also an S

if I then ask the question “is some Any value an S?":

  func f(x: Any) {
    if let xs = x as? S { … }
  }

what does it take to make that code produce the right answer for, e.g.,

  struct MyStruct : Q { }
  f(MyStruct())

?

Well, at runtime, you start by asking “is MyStruct an S?” It is not directly an S, but...
  - we know from #2 that every R is an S. “Is MyStruct an R?” It is not directly an R, but…
  - we know from #1 that every P is an R. “Is MyStruct a P?” Ah hah! It is a P because MyStruct declares conformance to Q, and every Q is a P.

So now we need to pull together a “MyStruct as an S” representation—at runtime—and cache it so we don’t have to go through all of that work the next time one asks that question. It’s absolutely implementable, but having to do that potentially-slow search at runtime is a major concern, particularly because adding a new extension that makes one protocol conform to another at any point in the system can cause widespread performance effects.

  - Doug

···

On Dec 17, 2015, at 12:37 AM, David Waite <david@alkaline-solutions.com> wrote:

On Dec 15, 2015, at 9:45 PM, Douglas Gregor via swift-evolution <swift-evolution@swift.org> wrote:

This is something like:

extension CollectionType : Equatable where Generator.Element : Equatable {}

This is probably not a priority for Swift 3. It seems very cool, and I've advocated for similar features in the past (in more static generics systems), but the potential for ambiguities with such definitions is very high and the runtime cost for asking questions such as "is this T Equatable?" can be very high when this feature is in play.

I’m not sure about the runtime cost of non-“existential" protocols like Equatable, which can’t be casted to at runtime today. Of course, this makes that there are multiple ‘kinds’ of protocols with different usage that are declared in the same way more complex than it is today.


(Slava Pestov) #15

I’ve been going through some notes and realized I missed a couple of things when I put my list together:

* access control for extensions declaring protocol conformances
* memberwise deriving of protocol implementations

I also found an example of the “same type constraints” item I mentioned and it is different than discussed so far:

struct S<T, U> {}
extension S where T == U {} // error

Are you considering any of these for Swift 3?

I’ve been picking Doug’s brain about this kind of stuff lately.

This one is somewhat similar to a same type requirement making a generic type parameter concrete, in the sense that the number of ‘primary archetypes’ becomes smaller than the number of generic parameters, which isn’t handled everywhere yet. For example, SIL walks the list of primary archetypes in order to map a generic type parameter’s depth/index to an archetype in several places.

With ‘secondary archetypes’, things are more flexible so this works:

protocol P { typealias X }
func foo<T : P, U : P where T.X == U.X>()

However, as Doug explained to me in person today, we’re still not doing a great job here. The list of requirements in a generic signature line up with the lists of primary and secondary archetypes in a tricky way. Also, type sugar allowing us to distinguish T.X from U.X is lost here since both types are mapped to the same identical type while building the generic signature, which you can imagine leads to poor diagnostics in more complex examples. Instead they need to have the same canonical type but still print differently, much like (X) and X, or [X] and Array<X>.

Slava

···

On Dec 17, 2015, at 7:57 PM, Matthew Johnson via swift-evolution <swift-evolution@swift.org> wrote:

Access control for extensions declaring protocol conformances seems is the highest priority out of this group IMO.

Matthew

On Dec 15, 2015, at 10:45 PM, Douglas Gregor <dgregor@apple.com <mailto:dgregor@apple.com>> wrote:

Hi Matthew,

Sent from my iPhone

On Dec 15, 2015, at 7:25 PM, Matthew Johnson <matthew@anandabits.com <mailto:matthew@anandabits.com>> wrote:

Dmitri, Slava and Doug thank you for taking the time to respond. I apologize for not thanking you sooner.

Since the core team has a loosely shared understanding of the goals but hasn't had time to write it down yet I thought it might be helpful if I put together a summary of the features that seem to me like obvious candidates for completing the current generic system. If I have missed anything significant please point that out.

This is helpful, thank you!

Lots of comments below. An overarching theme here is that I'm trying to scope down the list to what we need to achieve ABI stability and an expressive library fewer features means we're more likely to succeed with better quality.

I'm placing a "**" next to items that I beleive I have seen mentioned by the core team as desired features. This is based on memory and may be innacurate or may be based on desires expressed, but not necessarily pinned to the Swift 3 timeline.

I'm hoping the core team might be able to indicate which items are likely to be part of the work you're doing on Swift 3, which items you might be interested in the community contributing to, and which items are unliekly to be considered during the Swift 3 timeframe even with community involvement. This could help interested contributors start thinking about what they might be interested in working on while we wait for a more complete document describing the vision.

- ** generic typealias

This isn't high on my list. It's a good feature, and I want it someday, but introducing generic typealiases won't have any impact on the ABI and therefore can wait IMO.

- allow protocols to specify a non-covarying Self in static method declarations (a possible solution to the problem of conforming non-final classes in Cocoa to protocols containing factory methods)

Maybe. This isn't terribly high on my list, but in also behind on the discussion.

- extensions
  - ** allow same type constraints

I'm assuming you mean an extension like

  extension Array where Element == String {}

Yes, it's something we want to support

  - ** allow protocol conformance in constrained extensions

This is something like:

  extension Array : Equatable where Element : Equatable {}

It is very very high priority for Swift 3.

  - allow protocol conformance in protocol extensions

This is something like:

  extension CollectionType : Equatable where Generator.Element : Equatable {}

This is probably not a priority for Swift 3. It seems very cool, and I've advocated for similar features in the past (in more static generics systems), but the potential for ambiguities with such definitions is very high and the runtime cost for asking questions such as "is this T Equatable?" can be very high when this feature is in play.

- associated type constraints
  - use of Self as a superclass constraint

This wasn't on my list at all. Care to elaborate on why this is important?

  - ** where clause constraining inidividual associated types
  - ** where clause relating multiple assocated types

Yes to both. We need the to properly express some relationships in the standard library types, such as a SubSequence's Element type matching the Element type of the sequence itself.

- existentials for protocols with associated types
  - protocol existentials don't conform to the protocol itself
  - ** fully bound: protocol<GeneratorType where Element == Int>
  - ** fully constrained: protocol<GeneratorType where Element: CustomStringConvertible>
  - partially bound / constrained - allow access to members only mentioning constrained associated types
  - ** unbound - allow access to members not mentioning Self or associated types
  - composition: protocol<P1, P2 where P1.Associated: P3, P2.Associated == Int, P1.Other == P2.Other>

This one is tough. It is a very, very common user request and existentials are painfully under implemented in Swift. On the other hand, it's an additive feature that isn't likely (IMO!) to be important for ABI stabilization in the language or library. So, I would put it out of scope for Swift 3.

- nesting (per Slava's email)
  - ** Generic types nested inside generic functions
  - ** Generic types nested inside generic types
  - ** Generic functions nested inside generic functions which capture values or outer generic types

I think Slava and I disagree on this one :wink:

I don't consider this critical for Swift 3. The compiler will greatly improve simply by making this work (because the dumb assumptions that block this feature likely trigger additional bugs), but we don't need to allow it for ABI stability. There are a handful of places in the standard library where we've had to promote a type that would normally be nested to the top level to work around this, but we could live with that as a smallish ABI wart in the long term and introduce generic typealiases to clean up the syntax once those features become available.

Some things that I expect are out of scope for Swift 3 but am mentioning for completeness / confirmation of that:

- variadic generics
- higher kinded types
- higher rank types

Agreed that all are out of scope for Swift 3. The first is a feature of particular interest to me... But absolutely is out of scope. I also want to eventually use variadic generics to extend arbitrary length tuples of Equatable types to make them Equatable, for example :wink:

A couple features you didn't mention that I consider in scope for Swift 3 generics:

- generic subscripts (the standard library might need these), e.g.,

  subscript<C : SequenceType where C.Generator.Element == Index> (indices: C) -> [Index]

- recursive protocol constraints, where an associated type can be stated to conform to its enclosing protocol (directly or indirectly), eg,

  protocol SequenceType {
    typealias SubSequence : SequenceType
  }

- operators defined in types (only indirectly related to generics):

  extension Array where Element : Equatable {
    func ==(lhs: Array, rhs: Array) -> Bool { ... }
  }

- "real" default implementations in protocols. It looks like a syntactic simplification from
Putting the definition in an extension, but putting the default implementation in the protocol itself has an important effect on resilience: one should be able to add requirements to a protocol without breaking ABI so long as those requirements have a default implementation.

Several of these (recursive constraints, where clauses placing requirements on associated types in protocols, etc) are partly aimed at eliminated many of the underscored protocols in the standard library, because we don't want them to be part of the library ABI.

I suspect I'll remember other small things, but that's the "big" list... and it's size perhaps illustrates why we need to choose carefully to maintain focus.

  - Doug

Thanks,
Matthew

On Dec 11, 2015, at 11:24 PM, Douglas Gregor <dgregor@apple.com <mailto:dgregor@apple.com>> wrote:

On Dec 10, 2015, at 3:45 PM, Matthew Johnson via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

One of the stated focus areas for Swift 3 is to complete the generics system.

How far along is the design for the “complete” generics system?

There’s a loose shared understanding of the pieces we need among the compiler and standard library developers that have been co-evolving the generics system, but it’s not written down in any single place.

Is there appetite among the core team to involve the community in evaluating planned features or submitting proposals to complement existing plans?

Yes, absolutely. I feel like we (the core team) need to articulate our vision here—what we feel we need to accomplish (in features, in the standard library API, in the implementation) in Swift 3 vs. what we believe we can introduce later on, how the pieces all fit together, etc.—to help facilitate those discussions.

Also, is there any documentation other than https://github.com/apple/swift/blob/master/docs/Generics.rst describing in detail what the complete vision for the generics system is and what new features will be added in Swift 3 (as well as any generics features that have been decided against for Swift or version 3 specifically)?

No, that document is the best overall documentation for the vision of the generics system, despite being mostly untouched for more than two years and lacking newer features (protocol extensions, anyone?).

So, we need to write up a document describing our vision here. It’s going to take a little time, both because it’s a nontrivial task and because the likely principal authors are also engaged in other large Swift 3 tasks (e.g., https://github.com/apple/swift-evolution/blob/master/proposals/0005-objective-c-name-translation.md)

  - Doug

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


(Matthew Johnson) #16

Couldn’t this work theoretically be done as part of whole program optimization at some point in the future? Would that add too much potentially unnecessary metadata to the binary? Is there some other reason that wouldn’t be possible?

Matthew

···

On Dec 17, 2015, at 11:54 AM, Douglas Gregor <dgregor@apple.com> wrote:

On Dec 17, 2015, at 12:37 AM, David Waite <david@alkaline-solutions.com> wrote:

On Dec 15, 2015, at 9:45 PM, Douglas Gregor via swift-evolution <swift-evolution@swift.org> wrote:

This is something like:

extension CollectionType : Equatable where Generator.Element : Equatable {}

This is probably not a priority for Swift 3. It seems very cool, and I've advocated for similar features in the past (in more static generics systems), but the potential for ambiguities with such definitions is very high and the runtime cost for asking questions such as "is this T Equatable?" can be very high when this feature is in play.

I’m not sure about the runtime cost of non-“existential" protocols like Equatable, which can’t be casted to at runtime today. Of course, this makes that there are multiple ‘kinds’ of protocols with different usage that are declared in the same way more complex than it is today.

The non-“existential” protocol issue is actually separate. We can illustrate the issues with far simpler protocols:

  protocol P { }
  protocol Q : P { }
  protocol R { }
  protocol S { }

  extension P : R { } // #1: every P is also an R
  extension R : S { } // #2: every R is also an S

if I then ask the question “is some Any value an S?":

  func f(x: Any) {
    if let xs = x as? S { … }
  }

what does it take to make that code produce the right answer for, e.g.,

  struct MyStruct : Q { }
  f(MyStruct())

?

Well, at runtime, you start by asking “is MyStruct an S?” It is not directly an S, but...
  - we know from #2 that every R is an S. “Is MyStruct an R?” It is not directly an R, but…
  - we know from #1 that every P is an R. “Is MyStruct a P?” Ah hah! It is a P because MyStruct declares conformance to Q, and every Q is a P.

So now we need to pull together a “MyStruct as an S” representation—at runtime—and cache it so we don’t have to go through all of that work the next time one asks that question. It’s absolutely implementable, but having to do that potentially-slow search at runtime is a major concern, particularly because adding a new extension that makes one protocol conform to another at any point in the system can cause widespread performance effects.


(Douglas Gregor) #17

Yes, we could certainly improve this with whole-program optimization, but the potential performance cliff from adding some simple “every Foo is a Bar” declaration anywhere in the program is terrifying.

Do recall that I’m saying “not now” rather than “not ever” for this feature. I think it’s very, very cool, but it’s complicated and we need a while to understand its overall effects.

  - Doug

···

On Dec 17, 2015, at 10:03 AM, Matthew Johnson <matthew@anandabits.com> wrote:

On Dec 17, 2015, at 11:54 AM, Douglas Gregor <dgregor@apple.com <mailto:dgregor@apple.com>> wrote:

On Dec 17, 2015, at 12:37 AM, David Waite <david@alkaline-solutions.com <mailto:david@alkaline-solutions.com>> wrote:

On Dec 15, 2015, at 9:45 PM, Douglas Gregor via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

This is something like:

extension CollectionType : Equatable where Generator.Element : Equatable {}

This is probably not a priority for Swift 3. It seems very cool, and I've advocated for similar features in the past (in more static generics systems), but the potential for ambiguities with such definitions is very high and the runtime cost for asking questions such as "is this T Equatable?" can be very high when this feature is in play.

I’m not sure about the runtime cost of non-“existential" protocols like Equatable, which can’t be casted to at runtime today. Of course, this makes that there are multiple ‘kinds’ of protocols with different usage that are declared in the same way more complex than it is today.

The non-“existential” protocol issue is actually separate. We can illustrate the issues with far simpler protocols:

  protocol P { }
  protocol Q : P { }
  protocol R { }
  protocol S { }

  extension P : R { } // #1: every P is also an R
  extension R : S { } // #2: every R is also an S

if I then ask the question “is some Any value an S?":

  func f(x: Any) {
    if let xs = x as? S { … }
  }

what does it take to make that code produce the right answer for, e.g.,

  struct MyStruct : Q { }
  f(MyStruct())

?

Well, at runtime, you start by asking “is MyStruct an S?” It is not directly an S, but...
  - we know from #2 that every R is an S. “Is MyStruct an R?” It is not directly an R, but…
  - we know from #1 that every P is an R. “Is MyStruct a P?” Ah hah! It is a P because MyStruct declares conformance to Q, and every Q is a P.

So now we need to pull together a “MyStruct as an S” representation—at runtime—and cache it so we don’t have to go through all of that work the next time one asks that question. It’s absolutely implementable, but having to do that potentially-slow search at runtime is a major concern, particularly because adding a new extension that makes one protocol conform to another at any point in the system can cause widespread performance effects.

Couldn’t this work theoretically be done as part of whole program optimization at some point in the future? Would that add too much potentially unnecessary metadata to the binary? Is there some other reason that wouldn’t be possible?


(Matthew Johnson) #18

Do recall that I’m saying “not now” rather than “not ever” for this feature. I think it’s very, very cool, but it’s complicated and we need a while to understand its overall effects.

Sure, that makes sense!