[Proposal] Conditional Conformance on Protocols/Generic Types


(Dan Zimmerman) #1

Hey,

I was interested in adopting the ability for a type that's generic in some sense (either via generics or via associated types, in the case of protocols) to conform to other protocols conditionally based on its type parameter/associated type. For example:

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

func ==<Collection: CollectionType where Collection.Generator.Element: Equatable>(left: Collection, right: Collection) -> Bool {
  return zip(left, right).reduce(true) { accumulator, tuple in accumulator && (tuple.0 == tuple.1) }
}

If this has already been proposed and knocked out/accepted please direct me to the right place.


(Austin Zheng) #2

Hello Dan,

You'll be pleased to learn that conforming generic types conditionally to protocols is on the roadmap (and is one of the highest priority items for the versions of Swift following 3.0): https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md#conditional-conformances-

However, it's unlikely that protocols will gain conditional conformance: https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md#conditional-conformances-via-protocol-extensions

That document originates from a mailing list post made some time ago, and is a decent overview as to what sorts of type system features the Swift core developers are interested in building.

Best,
Austin

···

On Jun 4, 2016, at 2:12 PM, Dan Zimmerman via swift-evolution <swift-evolution@swift.org> wrote:

Hey,

I was interested in adopting the ability for a type that's generic in some sense (either via generics or via associated types, in the case of protocols) to conform to other protocols conditionally based on its type parameter/associated type. For example:

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

func ==<Collection: CollectionType where Collection.Generator.Element: Equatable>(left: Collection, right: Collection) -> Bool {
 return zip(left, right).reduce(true) { accumulator, tuple in accumulator && (tuple.0 == tuple.1) }
}

If this has already been proposed and knocked out/accepted please direct me to the right place.
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Dan Zimmerman) #3

Hey-
Thanks for the quick response and for pointing me in the right direction!

Dan

···

On Jun 4, 2016, at 4:18 PM, Austin Zheng <austinzheng@gmail.com> wrote:

Hello Dan,

You'll be pleased to learn that conforming generic types conditionally to protocols is on the roadmap (and is one of the highest priority items for the versions of Swift following 3.0): https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md#conditional-conformances-

However, it's unlikely that protocols will gain conditional conformance: https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md#conditional-conformances-via-protocol-extensions

That document originates from a mailing list post made some time ago, and is a decent overview as to what sorts of type system features the Swift core developers are interested in building.

Best,
Austin

On Jun 4, 2016, at 2:12 PM, Dan Zimmerman via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

Hey,

I was interested in adopting the ability for a type that's generic in some sense (either via generics or via associated types, in the case of protocols) to conform to other protocols conditionally based on its type parameter/associated type. For example:

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

func ==<Collection: CollectionType where Collection.Generator.Element: Equatable>(left: Collection, right: Collection) -> Bool {
 return zip(left, right).reduce(true) { accumulator, tuple in accumulator && (tuple.0 == tuple.1) }
}

If this has already been proposed and knocked out/accepted please direct me to the right place.
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution


(Thorsten Seitz) #4

Hello Dan,

You'll be pleased to learn that conforming generic types conditionally to protocols is on the roadmap (and is one of the highest priority items for the versions of Swift following 3.0): https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md#conditional-conformances-

However, it's unlikely that protocols will gain conditional conformance: https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md#conditional-conformances-via-protocol-extensions

"However, similar to private conformances, it puts a major burden on the dynamic-casting runtime to chase down arbitrarily long and potentially cyclic chains of conformances, which makes efficient implementation nearly impossible.“

I’ve been wondering what the problem with the implementation is. I mean instead of using an extension the same conformance could have been declared beforehand, i.e. instead of

protocol P { func foo() }
protocol Q { func bar() }
extension Q : P { func foo() { bar() } }

we could have written the allowed

protocol P { func foo() }
protocol Q : P { func foo() { bar() } }

with the exact same effect.

The only difference would be that the extension might have been in another module than Q.
Is having to cross module boundaries causing the cited problems? Would the same problems exist if in the second example Q would be defined in another module?

-Thorsten

···

Am 04.06.2016 um 23:18 schrieb Austin Zheng via swift-evolution <swift-evolution@swift.org>:

That document originates from a mailing list post made some time ago, and is a decent overview as to what sorts of type system features the Swift core developers are interested in building.

Best,
Austin

On Jun 4, 2016, at 2:12 PM, Dan Zimmerman via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

Hey,

I was interested in adopting the ability for a type that's generic in some sense (either via generics or via associated types, in the case of protocols) to conform to other protocols conditionally based on its type parameter/associated type. For example:

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

func ==<Collection: CollectionType where Collection.Generator.Element: Equatable>(left: Collection, right: Collection) -> Bool {
 return zip(left, right).reduce(true) { accumulator, tuple in accumulator && (tuple.0 == tuple.1) }
}

If this has already been proposed and knocked out/accepted please direct me to the right place.
_______________________________________________
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


(L Mihalkovic) #5

The issue is to decide on the applicability scope. Thinking 'my app/their stuff' is an illusion. To the compiler & runtime there is only code split into modules, some in source code and others as dylibs (.dll, .so, ...). Any extension based conditional refines a protocol everywhere. What's hard is to compute the complete effects of these changes predictably, reliably and fast. Because when we consider 'but look, i have a single small extension', the compiler&runtime must be ready to deal symetrically with anything we throw at it. They can't start building 15 different ways the compute the side effects based on many different scenarios because it will be un-ruly code, and too complex to try to explain to us what we will see.
The circular redefinitions case is one of the knightmares that hides in there... would mean having to assign priority to scopes, when there is no scopes yet. At the moment, the binary conformance table contains records for 3 types of conformances. First step would be to add a new type to match extension based conformance, and then record where it came from, and add some priority scheme to be able to navigate any conformance chain(remember that the pb grows everytime we decide 'oh cool, lets use a Padleft module rather than write my own 15 lines to do it - see the recent pb with nodejs). Not a simple task even with time, which they do not have now.

@core_team i know this is a coarse explanation, but hopefully at least in the right ballpark.

···

On Jun 5, 2016, at 9:49 AM, Thorsten Seitz via swift-evolution <swift-evolution@swift.org> wrote:

Am 04.06.2016 um 23:18 schrieb Austin Zheng via swift-evolution <swift-evolution@swift.org>:

Hello Dan,

You'll be pleased to learn that conforming generic types conditionally to protocols is on the roadmap (and is one of the highest priority items for the versions of Swift following 3.0): https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md#conditional-conformances-

However, it's unlikely that protocols will gain conditional conformance: https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md#conditional-conformances-via-protocol-extensions

"However, similar to private conformances, it puts a major burden on the dynamic-casting runtime to chase down arbitrarily long and potentially cyclic chains of conformances, which makes efficient implementation nearly impossible.“

I’ve been wondering what the problem with the implementation is. I mean instead of using an extension the same conformance could have been declared beforehand, i.e. instead of

protocol P { func foo() }
protocol Q { func bar() }
extension Q : P { func foo() { bar() } }

we could have written the allowed

protocol P { func foo() }
protocol Q : P { func foo() { bar() } }

with the exact same effect.

The only difference would be that the extension might have been in another module than Q.
Is having to cross module boundaries causing the cited problems? Would the same problems exist if in the second example Q would be defined in another module?

-Thorsten

That document originates from a mailing list post made some time ago, and is a decent overview as to what sorts of type system features the Swift core developers are interested in building.

Best,
Austin

On Jun 4, 2016, at 2:12 PM, Dan Zimmerman via swift-evolution <swift-evolution@swift.org> wrote:

Hey,

I was interested in adopting the ability for a type that's generic in some sense (either via generics or via associated types, in the case of protocols) to conform to other protocols conditionally based on its type parameter/associated type. For example:

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

func ==<Collection: CollectionType where Collection.Generator.Element: Equatable>(left: Collection, right: Collection) -> Bool {
 return zip(left, right).reduce(true) { accumulator, tuple in accumulator && (tuple.0 == tuple.1) }
}

If this has already been proposed and knocked out/accepted please direct me to the right place.
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

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

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


(Douglas Gregor) #6

The issue is to decide on the applicability scope. Thinking 'my app/their stuff' is an illusion. To the compiler & runtime there is only code split into modules, some in source code and others as dylibs (.dll, .so, ...). Any extension based conditional refines a protocol everywhere. What's hard is to compute the complete effects of these changes predictably, reliably and fast. Because when we consider 'but look, i have a single small extension', the compiler&runtime must be ready to deal symetrically with anything we throw at it. They can't start building 15 different ways the compute the side effects based on many different scenarios because it will be un-ruly code, and too complex to try to explain to us what we will see.
The circular redefinitions case is one of the knightmares that hides in there... would mean having to assign priority to scopes, when there is no scopes yet. At the moment, the binary conformance table contains records for 3 types of conformances. First step would be to add a new type to match extension based conformance, and then record where it came from, and add some priority scheme to be able to navigate any conformance chain(remember that the pb grows everytime we decide 'oh cool, lets use a Padleft module rather than write my own 15 lines to do it - see the recent pb with nodejs). Not a simple task even with time, which they do not have now.

@core_team i know this is a coarse explanation, but hopefully at least in the right ballpark.

Roughly, yes. The specific problem regards answering the question “where must the runtime look to determine whether a given type X conforms to protocol P?”. Right now, the runtime conceptually needs to look:

  1) Into a list of known protocol conformances for the type X, and
  2) If X is a class type, the list of known protocol conformances for the superclass of X (recursively)

If we add the ability for a protocol extension to add a conformance to another protocol, add to that:

  3) Into the list of protocol extensions of other protocols Q that provide conformance to P

That’s a fairly significant expansion, and for each of the protocol extensions in (3), we need to evaluate whether X conforms to the extended protocol Q (and any additional constraints placed on that protocol extension).

  - Doug

···

On Jun 5, 2016, at 3:24 AM, L. Mihalkovic via swift-evolution <swift-evolution@swift.org> wrote:

On Jun 5, 2016, at 9:49 AM, Thorsten Seitz via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

Am 04.06.2016 um 23:18 schrieb Austin Zheng via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>>:

Hello Dan,

You'll be pleased to learn that conforming generic types conditionally to protocols is on the roadmap (and is one of the highest priority items for the versions of Swift following 3.0): https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md#conditional-conformances-

However, it's unlikely that protocols will gain conditional conformance: https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md#conditional-conformances-via-protocol-extensions

"However, similar to private conformances, it puts a major burden on the dynamic-casting runtime to chase down arbitrarily long and potentially cyclic chains of conformances, which makes efficient implementation nearly impossible.“

I’ve been wondering what the problem with the implementation is. I mean instead of using an extension the same conformance could have been declared beforehand, i.e. instead of

protocol P { func foo() }
protocol Q { func bar() }
extension Q : P { func foo() { bar() } }

we could have written the allowed

protocol P { func foo() }
protocol Q : P { func foo() { bar() } }

with the exact same effect.

The only difference would be that the extension might have been in another module than Q.
Is having to cross module boundaries causing the cited problems? Would the same problems exist if in the second example Q would be defined in another module?

-Thorsten

That document originates from a mailing list post made some time ago, and is a decent overview as to what sorts of type system features the Swift core developers are interested in building.

Best,
Austin

On Jun 4, 2016, at 2:12 PM, Dan Zimmerman via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

Hey,

I was interested in adopting the ability for a type that's generic in some sense (either via generics or via associated types, in the case of protocols) to conform to other protocols conditionally based on its type parameter/associated type. For example:

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

func ==<Collection: CollectionType where Collection.Generator.Element: Equatable>(left: Collection, right: Collection) -> Bool {
 return zip(left, right).reduce(true) { accumulator, tuple in accumulator && (tuple.0 == tuple.1) }
}

If this has already been proposed and knocked out/accepted please direct me to the right place.
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution

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

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <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


(Thorsten Seitz) #7

The issue is to decide on the applicability scope. Thinking 'my app/their stuff' is an illusion. To the compiler & runtime there is only code split into modules, some in source code and others as dylibs (.dll, .so, ...). Any extension based conditional refines a protocol everywhere. What's hard is to compute the complete effects of these changes predictably, reliably and fast. Because when we consider 'but look, i have a single small extension', the compiler&runtime must be ready to deal symetrically with anything we throw at it. They can't start building 15 different ways the compute the side effects based on many different scenarios because it will be un-ruly code, and too complex to try to explain to us what we will see.
The circular redefinitions case is one of the knightmares that hides in there... would mean having to assign priority to scopes, when there is no scopes yet. At the moment, the binary conformance table contains records for 3 types of conformances. First step would be to add a new type to match extension based conformance, and then record where it came from, and add some priority scheme to be able to navigate any conformance chain(remember that the pb grows everytime we decide 'oh cool, lets use a Padleft module rather than write my own 15 lines to do it - see the recent pb with nodejs). Not a simple task even with time, which they do not have now.

@core_team i know this is a coarse explanation, but hopefully at least in the right ballpark.

Roughly, yes. The specific problem regards answering the question “where must the runtime look to determine whether a given type X conforms to protocol P?”. Right now, the runtime conceptually needs to look:

  1) Into a list of known protocol conformances for the type X, and
  2) If X is a class type, the list of known protocol conformances for the superclass of X (recursively)

If we add the ability for a protocol extension to add a conformance to another protocol, add to that:

  3) Into the list of protocol extensions of other protocols Q that provide conformance to P

So, the difference is that in the case

protocol P { ... }
protocol Q : P { ... }
struct X : Q {...}

X's list of known protocol conformances already contains Q and P,
whereas in the case

protocol P { ... }
protocol Q { ... }
struct X : Q {...}
extension Q : P

X's list of known protocol conformances just contains Q and is not extended by P as a result of the extension?
Did I understand this right? Is that (not being able to extend the conformance lists of all types as a result of an extension) a restriction of having module boundaries? Or is it simply not feasible for other reasons?

-Thorsten

···

Am 06.06.2016 um 18:51 schrieb Douglas Gregor <dgregor@apple.com>:

On Jun 5, 2016, at 3:24 AM, L. Mihalkovic via swift-evolution <swift-evolution@swift.org> wrote:

That’s a fairly significant expansion, and for each of the protocol extensions in (3), we need to evaluate whether X conforms to the extended protocol Q (and any additional constraints placed on that protocol extension).

  - Doug

On Jun 5, 2016, at 9:49 AM, Thorsten Seitz via swift-evolution <swift-evolution@swift.org> wrote:

Am 04.06.2016 um 23:18 schrieb Austin Zheng via swift-evolution <swift-evolution@swift.org>:

Hello Dan,

You'll be pleased to learn that conforming generic types conditionally to protocols is on the roadmap (and is one of the highest priority items for the versions of Swift following 3.0): https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md#conditional-conformances-

However, it's unlikely that protocols will gain conditional conformance: https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md#conditional-conformances-via-protocol-extensions

"However, similar to private conformances, it puts a major burden on the dynamic-casting runtime to chase down arbitrarily long and potentially cyclic chains of conformances, which makes efficient implementation nearly impossible.“

I’ve been wondering what the problem with the implementation is. I mean instead of using an extension the same conformance could have been declared beforehand, i.e. instead of

protocol P { func foo() }
protocol Q { func bar() }
extension Q : P { func foo() { bar() } }

we could have written the allowed

protocol P { func foo() }
protocol Q : P { func foo() { bar() } }

with the exact same effect.

The only difference would be that the extension might have been in another module than Q.
Is having to cross module boundaries causing the cited problems? Would the same problems exist if in the second example Q would be defined in another module?

-Thorsten

That document originates from a mailing list post made some time ago, and is a decent overview as to what sorts of type system features the Swift core developers are interested in building.

Best,
Austin

On Jun 4, 2016, at 2:12 PM, Dan Zimmerman via swift-evolution <swift-evolution@swift.org> wrote:

Hey,

I was interested in adopting the ability for a type that's generic in some sense (either via generics or via associated types, in the case of protocols) to conform to other protocols conditionally based on its type parameter/associated type. For example:

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

func ==<Collection: CollectionType where Collection.Generator.Element: Equatable>(left: Collection, right: Collection) -> Bool {
 return zip(left, right).reduce(true) { accumulator, tuple in accumulator && (tuple.0 == tuple.1) }
}

If this has already been proposed and knocked out/accepted please direct me to the right place.
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

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

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

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


(L Mihalkovic) #8

The issue is to decide on the applicability scope. Thinking 'my app/their stuff' is an illusion. To the compiler & runtime there is only code split into modules, some in source code and others as dylibs (.dll, .so, ...). Any extension based conditional refines a protocol everywhere. What's hard is to compute the complete effects of these changes predictably, reliably and fast. Because when we consider 'but look, i have a single small extension', the compiler&runtime must be ready to deal symetrically with anything we throw at it. They can't start building 15 different ways the compute the side effects based on many different scenarios because it will be un-ruly code, and too complex to try to explain to us what we will see.
The circular redefinitions case is one of the knightmares that hides in there... would mean having to assign priority to scopes, when there is no scopes yet. At the moment, the binary conformance table contains records for 3 types of conformances. First step would be to add a new type to match extension based conformance, and then record where it came from, and add some priority scheme to be able to navigate any conformance chain(remember that the pb grows everytime we decide 'oh cool, lets use a Padleft module rather than write my own 15 lines to do it - see the recent pb with nodejs). Not a simple task even with time, which they do not have now.

@core_team i know this is a coarse explanation, but hopefully at least in the right ballpark.

Roughly, yes. The specific problem regards answering the question “where must the runtime look to determine whether a given type X conforms to protocol P?”. Right now, the runtime conceptually needs to look:

  1) Into a list of known protocol conformances for the type X, and
  2) If X is a class type, the list of known protocol conformances for the superclass of X (recursively)

If we add the ability for a protocol extension to add a conformance to another protocol, add to that:

I was under the impression that extension defined conformance would fit neither NormalProtocolConformance (nominal) nor SpecializedProtocolConformance (generic) and that a StrawmanExtensionProtocolConformance would then be required.

  3) Into the list of protocol extensions of other protocols Q that provide conformance to P

That’s a fairly significant expansion, and for each of the protocol extensions in (3), we need to evaluate whether X conforms to the extended protocol Q (and any additional constraints placed on that protocol extension).

because of the potential for contradictory definitions or redefinitions, I was under the impression that it might be useful to define some sort of prioritization for deciding which should be applied first. But that’s probably because I don’t understand the topic as much as you do. That is also why I was thinking that aside from priority, the structures might also have to be tagged with something to tell where they come from (maybe priority is just how these scope source are read). I guess this is also a requirement that would stem from supporting private/local conformance.

···

On Jun 6, 2016, at 6:51 PM, Douglas Gregor <dgregor@apple.com> wrote:

On Jun 5, 2016, at 3:24 AM, L. Mihalkovic via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

  - Doug

On Jun 5, 2016, at 9:49 AM, Thorsten Seitz via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

Am 04.06.2016 um 23:18 schrieb Austin Zheng via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>>:

Hello Dan,

You'll be pleased to learn that conforming generic types conditionally to protocols is on the roadmap (and is one of the highest priority items for the versions of Swift following 3.0): https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md#conditional-conformances-

However, it's unlikely that protocols will gain conditional conformance: https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md#conditional-conformances-via-protocol-extensions

"However, similar to private conformances, it puts a major burden on the dynamic-casting runtime to chase down arbitrarily long and potentially cyclic chains of conformances, which makes efficient implementation nearly impossible.“

I’ve been wondering what the problem with the implementation is. I mean instead of using an extension the same conformance could have been declared beforehand, i.e. instead of

protocol P { func foo() }
protocol Q { func bar() }
extension Q : P { func foo() { bar() } }

we could have written the allowed

protocol P { func foo() }
protocol Q : P { func foo() { bar() } }

with the exact same effect.

The only difference would be that the extension might have been in another module than Q.
Is having to cross module boundaries causing the cited problems? Would the same problems exist if in the second example Q would be defined in another module?

-Thorsten

That document originates from a mailing list post made some time ago, and is a decent overview as to what sorts of type system features the Swift core developers are interested in building.

Best,
Austin

On Jun 4, 2016, at 2:12 PM, Dan Zimmerman via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

Hey,

I was interested in adopting the ability for a type that's generic in some sense (either via generics or via associated types, in the case of protocols) to conform to other protocols conditionally based on its type parameter/associated type. For example:

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

func ==<Collection: CollectionType where Collection.Generator.Element: Equatable>(left: Collection, right: Collection) -> Bool {
 return zip(left, right).reduce(true) { accumulator, tuple in accumulator && (tuple.0 == tuple.1) }
}

If this has already been proposed and knocked out/accepted please direct me to the right place.
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution

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

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

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


(Douglas Gregor) #9

The issue is to decide on the applicability scope. Thinking 'my app/their stuff' is an illusion. To the compiler & runtime there is only code split into modules, some in source code and others as dylibs (.dll, .so, ...). Any extension based conditional refines a protocol everywhere. What's hard is to compute the complete effects of these changes predictably, reliably and fast. Because when we consider 'but look, i have a single small extension', the compiler&runtime must be ready to deal symetrically with anything we throw at it. They can't start building 15 different ways the compute the side effects based on many different scenarios because it will be un-ruly code, and too complex to try to explain to us what we will see.
The circular redefinitions case is one of the knightmares that hides in there... would mean having to assign priority to scopes, when there is no scopes yet. At the moment, the binary conformance table contains records for 3 types of conformances. First step would be to add a new type to match extension based conformance, and then record where it came from, and add some priority scheme to be able to navigate any conformance chain(remember that the pb grows everytime we decide 'oh cool, lets use a Padleft module rather than write my own 15 lines to do it - see the recent pb with nodejs). Not a simple task even with time, which they do not have now.

@core_team i know this is a coarse explanation, but hopefully at least in the right ballpark.

Roughly, yes. The specific problem regards answering the question “where must the runtime look to determine whether a given type X conforms to protocol P?”. Right now, the runtime conceptually needs to look:

  1) Into a list of known protocol conformances for the type X, and
  2) If X is a class type, the list of known protocol conformances for the superclass of X (recursively)

If we add the ability for a protocol extension to add a conformance to another protocol, add to that:

  3) Into the list of protocol extensions of other protocols Q that provide conformance to P

So, the difference is that in the case

protocol P { ... }
protocol Q : P { ... }
struct X : Q {...}

X's list of known protocol conformances already contains Q and P,
whereas in the case

protocol P { ... }
protocol Q { ... }
struct X : Q {...}
extension Q : P

X's list of known protocol conformances just contains Q and is not extended by P as a result of the extension?
Did I understand this right?

Yes, that’s correct.

Is that (not being able to extend the conformance lists of all types as a result of an extension) a restriction of having module boundaries?

Effectively, yes: you can’t simply enumerate all of the cases because some other module might add a new types/protocol extensions/conformances. It has to be dynamically discoverable.

Or is it simply not feasible for other reasons?

It’s feasible, in the sense that it can be implemented. The concern is that it’s potentially very expensive, and is very likely to introduce ambiguities where there are two different protocol conformances to satisfy the query “X conforms to P”.

  - Doug

···

On Jun 6, 2016, at 12:12 PM, Thorsten Seitz <tseitz42@icloud.com> wrote:
Am 06.06.2016 um 18:51 schrieb Douglas Gregor <dgregor@apple.com <mailto:dgregor@apple.com>>:

On Jun 5, 2016, at 3:24 AM, L. Mihalkovic via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

-Thorsten

That’s a fairly significant expansion, and for each of the protocol extensions in (3), we need to evaluate whether X conforms to the extended protocol Q (and any additional constraints placed on that protocol extension).

  - Doug

On Jun 5, 2016, at 9:49 AM, Thorsten Seitz via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

Am 04.06.2016 um 23:18 schrieb Austin Zheng via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>>:

Hello Dan,

You'll be pleased to learn that conforming generic types conditionally to protocols is on the roadmap (and is one of the highest priority items for the versions of Swift following 3.0): https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md#conditional-conformances-

However, it's unlikely that protocols will gain conditional conformance: https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md#conditional-conformances-via-protocol-extensions

"However, similar to private conformances, it puts a major burden on the dynamic-casting runtime to chase down arbitrarily long and potentially cyclic chains of conformances, which makes efficient implementation nearly impossible.“

I’ve been wondering what the problem with the implementation is. I mean instead of using an extension the same conformance could have been declared beforehand, i.e. instead of

protocol P { func foo() }
protocol Q { func bar() }
extension Q : P { func foo() { bar() } }

we could have written the allowed

protocol P { func foo() }
protocol Q : P { func foo() { bar() } }

with the exact same effect.

The only difference would be that the extension might have been in another module than Q.
Is having to cross module boundaries causing the cited problems? Would the same problems exist if in the second example Q would be defined in another module?

-Thorsten

That document originates from a mailing list post made some time ago, and is a decent overview as to what sorts of type system features the Swift core developers are interested in building.

Best,
Austin

On Jun 4, 2016, at 2:12 PM, Dan Zimmerman via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

Hey,

I was interested in adopting the ability for a type that's generic in some sense (either via generics or via associated types, in the case of protocols) to conform to other protocols conditionally based on its type parameter/associated type. For example:

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

func ==<Collection: CollectionType where Collection.Generator.Element: Equatable>(left: Collection, right: Collection) -> Bool {
 return zip(left, right).reduce(true) { accumulator, tuple in accumulator && (tuple.0 == tuple.1) }
}

If this has already been proposed and knocked out/accepted please direct me to the right place.
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution

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

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

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


(Douglas Gregor) #10

The issue is to decide on the applicability scope. Thinking 'my app/their stuff' is an illusion. To the compiler & runtime there is only code split into modules, some in source code and others as dylibs (.dll, .so, ...). Any extension based conditional refines a protocol everywhere. What's hard is to compute the complete effects of these changes predictably, reliably and fast. Because when we consider 'but look, i have a single small extension', the compiler&runtime must be ready to deal symetrically with anything we throw at it. They can't start building 15 different ways the compute the side effects based on many different scenarios because it will be un-ruly code, and too complex to try to explain to us what we will see.
The circular redefinitions case is one of the knightmares that hides in there... would mean having to assign priority to scopes, when there is no scopes yet. At the moment, the binary conformance table contains records for 3 types of conformances. First step would be to add a new type to match extension based conformance, and then record where it came from, and add some priority scheme to be able to navigate any conformance chain(remember that the pb grows everytime we decide 'oh cool, lets use a Padleft module rather than write my own 15 lines to do it - see the recent pb with nodejs). Not a simple task even with time, which they do not have now.

@core_team i know this is a coarse explanation, but hopefully at least in the right ballpark.

Roughly, yes. The specific problem regards answering the question “where must the runtime look to determine whether a given type X conforms to protocol P?”. Right now, the runtime conceptually needs to look:

  1) Into a list of known protocol conformances for the type X, and
  2) If X is a class type, the list of known protocol conformances for the superclass of X (recursively)

If we add the ability for a protocol extension to add a conformance to another protocol, add to that:

I was under the impression that extension defined conformance would fit neither NormalProtocolConformance (nominal) nor SpecializedProtocolConformance (generic) and that a StrawmanExtensionProtocolConformance would then be required.

Well, that’s an implementation detail of the AST itself. We’d probably be able to leverage NormalProtocolConformance for this.

  3) Into the list of protocol extensions of other protocols Q that provide conformance to P

That’s a fairly significant expansion, and for each of the protocol extensions in (3), we need to evaluate whether X conforms to the extended protocol Q (and any additional constraints placed on that protocol extension).

because of the potential for contradictory definitions or redefinitions, I was under the impression that it might be useful to define some sort of prioritization for deciding which should be applied first. But that’s probably because I don’t understand the topic as much as you do. That is also why I was thinking that aside from priority, the structures might also have to be tagged with something to tell where they come from (maybe priority is just how these scope source are read). I guess this is also a requirement that would stem from supporting private/local conformance.

Yes, if we admit multiple conformances of the same type X to a protocol P, we need some way to resolve the ambiguity *at runtime*. That has a cost, which could be significant depending on the chosen scheme. Personally, I don’t think we ever want to admit multiple/private/local conformances.

  - Doug

···

On Jun 6, 2016, at 12:37 PM, L Mihalkovic <laurent.mihalkovic@gmail.com> wrote:

On Jun 6, 2016, at 6:51 PM, Douglas Gregor <dgregor@apple.com <mailto:dgregor@apple.com>> wrote:

On Jun 5, 2016, at 3:24 AM, L. Mihalkovic via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

  - Doug

On Jun 5, 2016, at 9:49 AM, Thorsten Seitz via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

Am 04.06.2016 um 23:18 schrieb Austin Zheng via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>>:

Hello Dan,

You'll be pleased to learn that conforming generic types conditionally to protocols is on the roadmap (and is one of the highest priority items for the versions of Swift following 3.0): https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md#conditional-conformances-

However, it's unlikely that protocols will gain conditional conformance: https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md#conditional-conformances-via-protocol-extensions

"However, similar to private conformances, it puts a major burden on the dynamic-casting runtime to chase down arbitrarily long and potentially cyclic chains of conformances, which makes efficient implementation nearly impossible.“

I’ve been wondering what the problem with the implementation is. I mean instead of using an extension the same conformance could have been declared beforehand, i.e. instead of

protocol P { func foo() }
protocol Q { func bar() }
extension Q : P { func foo() { bar() } }

we could have written the allowed

protocol P { func foo() }
protocol Q : P { func foo() { bar() } }

with the exact same effect.

The only difference would be that the extension might have been in another module than Q.
Is having to cross module boundaries causing the cited problems? Would the same problems exist if in the second example Q would be defined in another module?

-Thorsten

That document originates from a mailing list post made some time ago, and is a decent overview as to what sorts of type system features the Swift core developers are interested in building.

Best,
Austin

On Jun 4, 2016, at 2:12 PM, Dan Zimmerman via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

Hey,

I was interested in adopting the ability for a type that's generic in some sense (either via generics or via associated types, in the case of protocols) to conform to other protocols conditionally based on its type parameter/associated type. For example:

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

func ==<Collection: CollectionType where Collection.Generator.Element: Equatable>(left: Collection, right: Collection) -> Bool {
 return zip(left, right).reduce(true) { accumulator, tuple in accumulator && (tuple.0 == tuple.1) }
}

If this has already been proposed and knocked out/accepted please direct me to the right place.
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution

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

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

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


(L Mihalkovic) #11

The issue is to decide on the applicability scope. Thinking 'my app/their stuff' is an illusion. To the compiler & runtime there is only code split into modules, some in source code and others as dylibs (.dll, .so, ...). Any extension based conditional refines a protocol everywhere. What's hard is to compute the complete effects of these changes predictably, reliably and fast. Because when we consider 'but look, i have a single small extension', the compiler&runtime must be ready to deal symetrically with anything we throw at it. They can't start building 15 different ways the compute the side effects based on many different scenarios because it will be un-ruly code, and too complex to try to explain to us what we will see.
The circular redefinitions case is one of the knightmares that hides in there... would mean having to assign priority to scopes, when there is no scopes yet. At the moment, the binary conformance table contains records for 3 types of conformances. First step would be to add a new type to match extension based conformance, and then record where it came from, and add some priority scheme to be able to navigate any conformance chain(remember that the pb grows everytime we decide 'oh cool, lets use a Padleft module rather than write my own 15 lines to do it - see the recent pb with nodejs). Not a simple task even with time, which they do not have now.

@core_team i know this is a coarse explanation, but hopefully at least in the right ballpark.

Roughly, yes. The specific problem regards answering the question “where must the runtime look to determine whether a given type X conforms to protocol P?”. Right now, the runtime conceptually needs to look:

  1) Into a list of known protocol conformances for the type X, and
  2) If X is a class type, the list of known protocol conformances for the superclass of X (recursively)

If we add the ability for a protocol extension to add a conformance to another protocol, add to that:

  3) Into the list of protocol extensions of other protocols Q that provide conformance to P

So, the difference is that in the case

protocol P { ... }
protocol Q : P { ... }
struct X : Q {...}

X's list of known protocol conformances already contains Q and P,
whereas in the case

protocol P { ... }
protocol Q { ... }
struct X : Q {...}
extension Q : P

X's list of known protocol conformances just contains Q and is not extended by P as a result of the extension?
Did I understand this right?

Yes, that’s correct.

Is that (not being able to extend the conformance lists of all types as a result of an extension) a restriction of having module boundaries?

Effectively, yes: you can’t simply enumerate all of the cases because some other module might add a new types/protocol extensions/conformances. It has to be dynamically discoverable.

yes… for each new module added to a known mix, the final conformances list can be completely different.

Or is it simply not feasible for other reasons?

It’s feasible, in the sense that it can be implemented. The concern is that it’s potentially very expensive, and is very likely to introduce ambiguities where there are two different protocol conformances to satisfy the query “X conforms to P”.

that’s what I thought would motivate some sort of prioritization scheme.. but I guess (or judge from experience with the static/dynsmic dispatch story with extensions, or the so called ‘defender’ methods in java) anytime one scheme is picked, there are people to question that it is the right one. Then I keep circling back to the idea of being able to subdivide a module into separate sections (call-em namespace or submodule) which would limit the scope of conformance baring extensions. From a 10mile high view, I thought the the current TEXT segments could be duplicated (one per namespace/submodule), leaving the current one to be the de-facto module’s namespace. Granted it would complicate the loading code, it would not destroy whole-module optimization. Alternatively it would be nice if Xcode was retrofitted with a simple support for creating quartz-like module-inside-module structures. But either way, we circle back to defining a type hierarchy to simplify the problem… which is usually summarized by layers as “do not ask a question for which you do not know the answer”… chasing a compliance chain can be a open-ended problem as people would become more daring with the feature and projects would rely on more and more pre-canned modules.

thank you for your patient explanations.

···

On Jun 6, 2016, at 9:34 PM, Douglas Gregor <dgregor@apple.com> wrote:

On Jun 6, 2016, at 12:12 PM, Thorsten Seitz <tseitz42@icloud.com <mailto:tseitz42@icloud.com>> wrote:
Am 06.06.2016 um 18:51 schrieb Douglas Gregor <dgregor@apple.com <mailto:dgregor@apple.com>>:

On Jun 5, 2016, at 3:24 AM, L. Mihalkovic via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

  - Doug

-Thorsten

That’s a fairly significant expansion, and for each of the protocol extensions in (3), we need to evaluate whether X conforms to the extended protocol Q (and any additional constraints placed on that protocol extension).

  - Doug

On Jun 5, 2016, at 9:49 AM, Thorsten Seitz via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

Am 04.06.2016 um 23:18 schrieb Austin Zheng via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>>:

Hello Dan,

You'll be pleased to learn that conforming generic types conditionally to protocols is on the roadmap (and is one of the highest priority items for the versions of Swift following 3.0): https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md#conditional-conformances-

However, it's unlikely that protocols will gain conditional conformance: https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md#conditional-conformances-via-protocol-extensions

"However, similar to private conformances, it puts a major burden on the dynamic-casting runtime to chase down arbitrarily long and potentially cyclic chains of conformances, which makes efficient implementation nearly impossible.“

I’ve been wondering what the problem with the implementation is. I mean instead of using an extension the same conformance could have been declared beforehand, i.e. instead of

protocol P { func foo() }
protocol Q { func bar() }
extension Q : P { func foo() { bar() } }

we could have written the allowed

protocol P { func foo() }
protocol Q : P { func foo() { bar() } }

with the exact same effect.

The only difference would be that the extension might have been in another module than Q.
Is having to cross module boundaries causing the cited problems? Would the same problems exist if in the second example Q would be defined in another module?

-Thorsten

That document originates from a mailing list post made some time ago, and is a decent overview as to what sorts of type system features the Swift core developers are interested in building.

Best,
Austin


(Thorsten Seitz) #12

The issue is to decide on the applicability scope. Thinking 'my app/their stuff' is an illusion. To the compiler & runtime there is only code split into modules, some in source code and others as dylibs (.dll, .so, ...). Any extension based conditional refines a protocol everywhere. What's hard is to compute the complete effects of these changes predictably, reliably and fast. Because when we consider 'but look, i have a single small extension', the compiler&runtime must be ready to deal symetrically with anything we throw at it. They can't start building 15 different ways the compute the side effects based on many different scenarios because it will be un-ruly code, and too complex to try to explain to us what we will see.
The circular redefinitions case is one of the knightmares that hides in there... would mean having to assign priority to scopes, when there is no scopes yet. At the moment, the binary conformance table contains records for 3 types of conformances. First step would be to add a new type to match extension based conformance, and then record where it came from, and add some priority scheme to be able to navigate any conformance chain(remember that the pb grows everytime we decide 'oh cool, lets use a Padleft module rather than write my own 15 lines to do it - see the recent pb with nodejs). Not a simple task even with time, which they do not have now.

@core_team i know this is a coarse explanation, but hopefully at least in the right ballpark.

Roughly, yes. The specific problem regards answering the question “where must the runtime look to determine whether a given type X conforms to protocol P?”. Right now, the runtime conceptually needs to look:

  1) Into a list of known protocol conformances for the type X, and
  2) If X is a class type, the list of known protocol conformances for the superclass of X (recursively)

If we add the ability for a protocol extension to add a conformance to another protocol, add to that:

  3) Into the list of protocol extensions of other protocols Q that provide conformance to P

So, the difference is that in the case

protocol P { ... }
protocol Q : P { ... }
struct X : Q {...}

X's list of known protocol conformances already contains Q and P,
whereas in the case

protocol P { ... }
protocol Q { ... }
struct X : Q {...}
extension Q : P

X's list of known protocol conformances just contains Q and is not extended by P as a result of the extension?
Did I understand this right?

Yes, that’s correct.

Is that (not being able to extend the conformance lists of all types as a result of an extension) a restriction of having module boundaries?

Effectively, yes: you can’t simply enumerate all of the cases because some other module might add a new types/protocol extensions/conformances. It has to be dynamically discoverable.

yes… for each new module added to a known mix, the final conformances list can be completely different.

But this is information known at compile time and does not have to be determined at runtime.
An extension should be only effective in the module in which it is defined and in modules using that module. All of these get to know the extension at compile time.
There should be no need to have extensions affect modules that do not see them. This should be similar to the Classboxes module system proposed for Smalltalk (http://scg.unibe.ch/research/classboxes) AFAIR.

Or is it simply not feasible for other reasons?

It’s feasible, in the sense that it can be implemented. The concern is that it’s potentially very expensive, and is very likely to introduce ambiguities where there are two different protocol conformances to satisfy the query “X conforms to P”.

Ambiguities should have to be solved at compile time by the programmer. I'm not a fan of fancy ordering schemes e.g. for Mixins but prefer manual resolvement which makes it understandable what happens. Cecil from the University of Washington did that well (http://www.cs.washington.edu/research/projects/cecil/pubs/).

that’s what I thought would motivate some sort of prioritization scheme.. but I guess (or judge from experience with the static/dynsmic dispatch story with extensions, or the so called ‘defender’ methods in java) anytime one scheme is picked, there are people to question that it is the right one. Then I keep circling back to the idea of being able to subdivide a module into separate sections (call-em namespace or submodule) which would limit the scope of conformance baring extensions. From a 10mile high view, I thought the the current TEXT segments could be duplicated (one per namespace/submodule), leaving the current one to be the de-facto module’s namespace. Granted it would complicate the loading code, it would not destroy whole-module optimization. Alternatively it would be nice if Xcode was retrofitted with a simple support for creating quartz-like module-inside-module structures. But either way, we circle back to defining a type hierarchy to simplify the problem… which is usually summarized by layers as “do not ask a question for which you do not know the answer”… chasing a compliance chain can be a open-ended problem as people would become more daring with the feature and projects would rely on more and more pre-canned modules.

thank you for your patient explanations.

Many thanks from me as well. I, too, appreciate that very much!

-Thorsten

···

Am 06.06.2016 um 22:13 schrieb L Mihalkovic <laurent.mihalkovic@gmail.com>:

On Jun 6, 2016, at 9:34 PM, Douglas Gregor <dgregor@apple.com> wrote:
On Jun 6, 2016, at 12:12 PM, Thorsten Seitz <tseitz42@icloud.com> wrote:
Am 06.06.2016 um 18:51 schrieb Douglas Gregor <dgregor@apple.com>:

On Jun 5, 2016, at 3:24 AM, L. Mihalkovic via swift-evolution <swift-evolution@swift.org> wrote:

  - Doug

-Thorsten

That’s a fairly significant expansion, and for each of the protocol extensions in (3), we need to evaluate whether X conforms to the extended protocol Q (and any additional constraints placed on that protocol extension).

  - Doug

On Jun 5, 2016, at 9:49 AM, Thorsten Seitz via swift-evolution <swift-evolution@swift.org> wrote:

Am 04.06.2016 um 23:18 schrieb Austin Zheng via swift-evolution <swift-evolution@swift.org>:

Hello Dan,

You'll be pleased to learn that conforming generic types conditionally to protocols is on the roadmap (and is one of the highest priority items for the versions of Swift following 3.0): https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md#conditional-conformances-

However, it's unlikely that protocols will gain conditional conformance: https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md#conditional-conformances-via-protocol-extensions

"However, similar to private conformances, it puts a major burden on the dynamic-casting runtime to chase down arbitrarily long and potentially cyclic chains of conformances, which makes efficient implementation nearly impossible.“

I’ve been wondering what the problem with the implementation is. I mean instead of using an extension the same conformance could have been declared beforehand, i.e. instead of

protocol P { func foo() }
protocol Q { func bar() }
extension Q : P { func foo() { bar() } }

we could have written the allowed

protocol P { func foo() }
protocol Q : P { func foo() { bar() } }

with the exact same effect.

The only difference would be that the extension might have been in another module than Q.
Is having to cross module boundaries causing the cited problems? Would the same problems exist if in the second example Q would be defined in another module?

-Thorsten

That document originates from a mailing list post made some time ago, and is a decent overview as to what sorts of type system features the Swift core developers are interested in building.

Best,
Austin


(Douglas Gregor) #13

The issue is to decide on the applicability scope. Thinking 'my app/their stuff' is an illusion. To the compiler & runtime there is only code split into modules, some in source code and others as dylibs (.dll, .so, ...). Any extension based conditional refines a protocol everywhere. What's hard is to compute the complete effects of these changes predictably, reliably and fast. Because when we consider 'but look, i have a single small extension', the compiler&runtime must be ready to deal symetrically with anything we throw at it. They can't start building 15 different ways the compute the side effects based on many different scenarios because it will be un-ruly code, and too complex to try to explain to us what we will see.
The circular redefinitions case is one of the knightmares that hides in there... would mean having to assign priority to scopes, when there is no scopes yet. At the moment, the binary conformance table contains records for 3 types of conformances. First step would be to add a new type to match extension based conformance, and then record where it came from, and add some priority scheme to be able to navigate any conformance chain(remember that the pb grows everytime we decide 'oh cool, lets use a Padleft module rather than write my own 15 lines to do it - see the recent pb with nodejs). Not a simple task even with time, which they do not have now.

@core_team i know this is a coarse explanation, but hopefully at least in the right ballpark.

Roughly, yes. The specific problem regards answering the question “where must the runtime look to determine whether a given type X conforms to protocol P?”. Right now, the runtime conceptually needs to look:

  1) Into a list of known protocol conformances for the type X, and
  2) If X is a class type, the list of known protocol conformances for the superclass of X (recursively)

If we add the ability for a protocol extension to add a conformance to another protocol, add to that:

  3) Into the list of protocol extensions of other protocols Q that provide conformance to P

So, the difference is that in the case

protocol P { ... }
protocol Q : P { ... }
struct X : Q {...}

X's list of known protocol conformances already contains Q and P,
whereas in the case

protocol P { ... }
protocol Q { ... }
struct X : Q {...}
extension Q : P

X's list of known protocol conformances just contains Q and is not extended by P as a result of the extension?
Did I understand this right?

Yes, that’s correct.

Is that (not being able to extend the conformance lists of all types as a result of an extension) a restriction of having module boundaries?

Effectively, yes: you can’t simply enumerate all of the cases because some other module might add a new types/protocol extensions/conformances. It has to be dynamically discoverable.

yes… for each new module added to a known mix, the final conformances list can be completely different.

But this is information known at compile time and does not have to be determined at runtime.
An extension should be only effective in the module in which it is defined and in modules using that module. All of these get to know the extension at compile time.

That’s not the model that Swift uses today. You can discover protocol conformances introduce by modules—whether you knew about those modules at compile time (but at launch time you end up with newer versions) or whether those modules were unknown, you see the conformances. The standard library’s “print” facility depends on this behavior to find CustomStringConvertible conformances.

Yes, we could make it all statically determined, but IMO that’s not the direction that Swift has been going.

  - Doug

···

On Jun 6, 2016, at 10:08 PM, Thorsten Seitz <tseitz42@icloud.com> wrote:
Am 06.06.2016 um 22:13 schrieb L Mihalkovic <laurent.mihalkovic@gmail.com <mailto:laurent.mihalkovic@gmail.com>>:

On Jun 6, 2016, at 9:34 PM, Douglas Gregor <dgregor@apple.com <mailto:dgregor@apple.com>> wrote:

On Jun 6, 2016, at 12:12 PM, Thorsten Seitz <tseitz42@icloud.com <mailto:tseitz42@icloud.com>> wrote:
Am 06.06.2016 um 18:51 schrieb Douglas Gregor <dgregor@apple.com <mailto:dgregor@apple.com>>:

On Jun 5, 2016, at 3:24 AM, L. Mihalkovic via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

  - Doug

-Thorsten

That’s a fairly significant expansion, and for each of the protocol extensions in (3), we need to evaluate whether X conforms to the extended protocol Q (and any additional constraints placed on that protocol extension).

  - Doug

On Jun 5, 2016, at 9:49 AM, Thorsten Seitz via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

Am 04.06.2016 um 23:18 schrieb Austin Zheng via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>>:

Hello Dan,

You'll be pleased to learn that conforming generic types conditionally to protocols is on the roadmap (and is one of the highest priority items for the versions of Swift following 3.0): https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md#conditional-conformances-

However, it's unlikely that protocols will gain conditional conformance: https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md#conditional-conformances-via-protocol-extensions

"However, similar to private conformances, it puts a major burden on the dynamic-casting runtime to chase down arbitrarily long and potentially cyclic chains of conformances, which makes efficient implementation nearly impossible.“

I’ve been wondering what the problem with the implementation is. I mean instead of using an extension the same conformance could have been declared beforehand, i.e. instead of

protocol P { func foo() }
protocol Q { func bar() }
extension Q : P { func foo() { bar() } }

we could have written the allowed

protocol P { func foo() }
protocol Q : P { func foo() { bar() } }

with the exact same effect.

The only difference would be that the extension might have been in another module than Q.
Is having to cross module boundaries causing the cited problems? Would the same problems exist if in the second example Q would be defined in another module?

-Thorsten

That document originates from a mailing list post made some time ago, and is a decent overview as to what sorts of type system features the Swift core developers are interested in building.

Best,
Austin


(L Mihalkovic) #14

The issue is to decide on the applicability scope. Thinking 'my app/their stuff' is an illusion. To the compiler & runtime there is only code split into modules, some in source code and others as dylibs (.dll, .so, ...). Any extension based conditional refines a protocol everywhere. What's hard is to compute the complete effects of these changes predictably, reliably and fast. Because when we consider 'but look, i have a single small extension', the compiler&runtime must be ready to deal symetrically with anything we throw at it. They can't start building 15 different ways the compute the side effects based on many different scenarios because it will be un-ruly code, and too complex to try to explain to us what we will see.
The circular redefinitions case is one of the knightmares that hides in there... would mean having to assign priority to scopes, when there is no scopes yet. At the moment, the binary conformance table contains records for 3 types of conformances. First step would be to add a new type to match extension based conformance, and then record where it came from, and add some priority scheme to be able to navigate any conformance chain(remember that the pb grows everytime we decide 'oh cool, lets use a Padleft module rather than write my own 15 lines to do it - see the recent pb with nodejs). Not a simple task even with time, which they do not have now.

@core_team i know this is a coarse explanation, but hopefully at least in the right ballpark.

Roughly, yes. The specific problem regards answering the question “where must the runtime look to determine whether a given type X conforms to protocol P?”. Right now, the runtime conceptually needs to look:

  1) Into a list of known protocol conformances for the type X, and
  2) If X is a class type, the list of known protocol conformances for the superclass of X (recursively)

If we add the ability for a protocol extension to add a conformance to another protocol, add to that:

  3) Into the list of protocol extensions of other protocols Q that provide conformance to P

So, the difference is that in the case

protocol P { ... }
protocol Q : P { ... }
struct X : Q {...}

X's list of known protocol conformances already contains Q and P,
whereas in the case

protocol P { ... }
protocol Q { ... }
struct X : Q {...}
extension Q : P

X's list of known protocol conformances just contains Q and is not extended by P as a result of the extension?
Did I understand this right?

Yes, that’s correct.

Is that (not being able to extend the conformance lists of all types as a result of an extension) a restriction of having module boundaries?

Effectively, yes: you can’t simply enumerate all of the cases because some other module might add a new types/protocol extensions/conformances. It has to be dynamically discoverable.

yes… for each new module added to a known mix, the final conformances list can be completely different.

But this is information known at compile time and does not have to be determined at runtime.
An extension should be only effective in the module in which it is defined and in modules using that module. All of these get to know the extension at compile time.

The idea of swift 3/4 is that the stdlib ABI should be stable enough that it will be in the system rather than embedded in each app. Which means that the conformance table must be runtime discoverable from the module exporting it (in a section of the text segment), and its final effects computed by the runtime when the module gets loaded (again coarse grained expl) by each binary using it. This also lets them define new module boundaries in the system that we can transitively inherit.

Baking the final conformance statically into the module would leave us wondering why our code might seem to be 'frozen' and not using newer system defined conformances. Mind you... this may not be a stupid idea at all, as it might align better with the practice of linking against specific SDKs to get a predictable level of behavior.

As for scope, my limited understanding of the loader is that there is no 'source' field in these conformance records that would allow the runtime to treat them hierarchically.

···

On Jun 7, 2016, at 7:14 AM, Douglas Gregor <dgregor@apple.com> wrote:

On Jun 6, 2016, at 10:08 PM, Thorsten Seitz <tseitz42@icloud.com> wrote:

Am 06.06.2016 um 22:13 schrieb L Mihalkovic <laurent.mihalkovic@gmail.com>:

On Jun 6, 2016, at 9:34 PM, Douglas Gregor <dgregor@apple.com> wrote:
On Jun 6, 2016, at 12:12 PM, Thorsten Seitz <tseitz42@icloud.com> wrote:
Am 06.06.2016 um 18:51 schrieb Douglas Gregor <dgregor@apple.com>:

On Jun 5, 2016, at 3:24 AM, L. Mihalkovic via swift-evolution <swift-evolution@swift.org> wrote:

That’s not the model that Swift uses today. You can discover protocol conformances introduce by modules—whether you knew about those modules at compile time (but at launch time you end up with newer versions) or whether those modules were unknown, you see the conformances. The standard library’s “print” facility depends on this behavior to find CustomStringConvertible conformances.

Yes, we could make it all statically determined, but IMO that’s not the direction that Swift has been going.

  - Doug

  - Doug

-Thorsten

That’s a fairly significant expansion, and for each of the protocol extensions in (3), we need to evaluate whether X conforms to the extended protocol Q (and any additional constraints placed on that protocol extension).

  - Doug

On Jun 5, 2016, at 9:49 AM, Thorsten Seitz via swift-evolution <swift-evolution@swift.org> wrote:

Am 04.06.2016 um 23:18 schrieb Austin Zheng via swift-evolution <swift-evolution@swift.org>:

Hello Dan,

You'll be pleased to learn that conforming generic types conditionally to protocols is on the roadmap (and is one of the highest priority items for the versions of Swift following 3.0): https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md#conditional-conformances-

However, it's unlikely that protocols will gain conditional conformance: https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md#conditional-conformances-via-protocol-extensions

"However, similar to private conformances, it puts a major burden on the dynamic-casting runtime to chase down arbitrarily long and potentially cyclic chains of conformances, which makes efficient implementation nearly impossible.“

I’ve been wondering what the problem with the implementation is. I mean instead of using an extension the same conformance could have been declared beforehand, i.e. instead of

protocol P { func foo() }
protocol Q { func bar() }
extension Q : P { func foo() { bar() } }

we could have written the allowed

protocol P { func foo() }
protocol Q : P { func foo() { bar() } }

with the exact same effect.

The only difference would be that the extension might have been in another module than Q.
Is having to cross module boundaries causing the cited problems? Would the same problems exist if in the second example Q would be defined in another module?

-Thorsten

That document originates from a mailing list post made some time ago, and is a decent overview as to what sorts of type system features the Swift core developers are interested in building.

Best,
Austin


(Thorsten Seitz) #15

The issue is to decide on the applicability scope. Thinking 'my app/their stuff' is an illusion. To the compiler & runtime there is only code split into modules, some in source code and others as dylibs (.dll, .so, ...). Any extension based conditional refines a protocol everywhere. What's hard is to compute the complete effects of these changes predictably, reliably and fast. Because when we consider 'but look, i have a single small extension', the compiler&runtime must be ready to deal symetrically with anything we throw at it. They can't start building 15 different ways the compute the side effects based on many different scenarios because it will be un-ruly code, and too complex to try to explain to us what we will see.
The circular redefinitions case is one of the knightmares that hides in there... would mean having to assign priority to scopes, when there is no scopes yet. At the moment, the binary conformance table contains records for 3 types of conformances. First step would be to add a new type to match extension based conformance, and then record where it came from, and add some priority scheme to be able to navigate any conformance chain(remember that the pb grows everytime we decide 'oh cool, lets use a Padleft module rather than write my own 15 lines to do it - see the recent pb with nodejs). Not a simple task even with time, which they do not have now.

@core_team i know this is a coarse explanation, but hopefully at least in the right ballpark.

Roughly, yes. The specific problem regards answering the question “where must the runtime look to determine whether a given type X conforms to protocol P?”. Right now, the runtime conceptually needs to look:

  1) Into a list of known protocol conformances for the type X, and
  2) If X is a class type, the list of known protocol conformances for the superclass of X (recursively)

If we add the ability for a protocol extension to add a conformance to another protocol, add to that:

  3) Into the list of protocol extensions of other protocols Q that provide conformance to P

So, the difference is that in the case

protocol P { ... }
protocol Q : P { ... }
struct X : Q {...}

X's list of known protocol conformances already contains Q and P,
whereas in the case

protocol P { ... }
protocol Q { ... }
struct X : Q {...}
extension Q : P

X's list of known protocol conformances just contains Q and is not extended by P as a result of the extension?
Did I understand this right?

Yes, that’s correct.

Is that (not being able to extend the conformance lists of all types as a result of an extension) a restriction of having module boundaries?

Effectively, yes: you can’t simply enumerate all of the cases because some other module might add a new types/protocol extensions/conformances. It has to be dynamically discoverable.

yes… for each new module added to a known mix, the final conformances list can be completely different.

But this is information known at compile time and does not have to be determined at runtime.
An extension should be only effective in the module in which it is defined and in modules using that module. All of these get to know the extension at compile time.

The idea of swift 3/4 is that the stdlib ABI should be stable enough that it will be in the system rather than embedded in each app. Which means that the conformance table must be runtime discoverable from the module exporting it (in a section of the text segment), and its final effects computed by the runtime when the module gets loaded (again coarse grained expl) by each binary using it. This also lets them define new module boundaries in the system that we can transitively inherit.

Baking the final conformance statically into the module would leave us wondering why our code might seem to be 'frozen' and not using newer system defined conformances.

Good argument. So that would mean that the analysis would have to be done at linking time. This (like doing it at runtime) does open a can of worms about ambiguity, though: what happens when the new system version of a library suddenly defines an extension that conflicts with an extension in our module? Seems like that such a change should be confined to the system module unless doing a recompile, so we are back to my suggestion of resolving extensions at compile time?

-Thorsten

···

Am 07.06.2016 um 07:55 schrieb LM <laurent.mihalkovic@gmail.com>:
On Jun 7, 2016, at 7:14 AM, Douglas Gregor <dgregor@apple.com <mailto:dgregor@apple.com>> wrote:

On Jun 6, 2016, at 10:08 PM, Thorsten Seitz <tseitz42@icloud.com <mailto:tseitz42@icloud.com>> wrote:
Am 06.06.2016 um 22:13 schrieb L Mihalkovic <laurent.mihalkovic@gmail.com <mailto:laurent.mihalkovic@gmail.com>>:

On Jun 6, 2016, at 9:34 PM, Douglas Gregor <dgregor@apple.com <mailto:dgregor@apple.com>> wrote:

On Jun 6, 2016, at 12:12 PM, Thorsten Seitz <tseitz42@icloud.com <mailto:tseitz42@icloud.com>> wrote:
Am 06.06.2016 um 18:51 schrieb Douglas Gregor <dgregor@apple.com <mailto:dgregor@apple.com>>:

On Jun 5, 2016, at 3:24 AM, L. Mihalkovic via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

Mind you... this may not be a stupid idea at all, as it might align better with the practice of linking against specific SDKs to get a predictable level of behavior.

As for scope, my limited understanding of the loader is that there is no 'source' field in these conformance records that would allow the runtime to treat them hierarchically.

That’s not the model that Swift uses today. You can discover protocol conformances introduce by modules—whether you knew about those modules at compile time (but at launch time you end up with newer versions) or whether those modules were unknown, you see the conformances. The standard library’s “print” facility depends on this behavior to find CustomStringConvertible conformances.

Yes, we could make it all statically determined, but IMO that’s not the direction that Swift has been going.

  - Doug

  - Doug

-Thorsten

That’s a fairly significant expansion, and for each of the protocol extensions in (3), we need to evaluate whether X conforms to the extended protocol Q (and any additional constraints placed on that protocol extension).

  - Doug

On Jun 5, 2016, at 9:49 AM, Thorsten Seitz via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

Am 04.06.2016 um 23:18 schrieb Austin Zheng via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>>:

Hello Dan,

You'll be pleased to learn that conforming generic types conditionally to protocols is on the roadmap (and is one of the highest priority items for the versions of Swift following 3.0): https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md#conditional-conformances-

However, it's unlikely that protocols will gain conditional conformance: https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md#conditional-conformances-via-protocol-extensions

"However, similar to private conformances, it puts a major burden on the dynamic-casting runtime to chase down arbitrarily long and potentially cyclic chains of conformances, which makes efficient implementation nearly impossible.“

I’ve been wondering what the problem with the implementation is. I mean instead of using an extension the same conformance could have been declared beforehand, i.e. instead of

protocol P { func foo() }
protocol Q { func bar() }
extension Q : P { func foo() { bar() } }

we could have written the allowed

protocol P { func foo() }
protocol Q : P { func foo() { bar() } }

with the exact same effect.

The only difference would be that the extension might have been in another module than Q.
Is having to cross module boundaries causing the cited problems? Would the same problems exist if in the second example Q would be defined in another module?

-Thorsten

That document originates from a mailing list post made some time ago, and is a decent overview as to what sorts of type system features the Swift core developers are interested in building.

Best,
Austin


(Douglas Gregor) #16

The issue is to decide on the applicability scope. Thinking 'my app/their stuff' is an illusion. To the compiler & runtime there is only code split into modules, some in source code and others as dylibs (.dll, .so, ...). Any extension based conditional refines a protocol everywhere. What's hard is to compute the complete effects of these changes predictably, reliably and fast. Because when we consider 'but look, i have a single small extension', the compiler&runtime must be ready to deal symetrically with anything we throw at it. They can't start building 15 different ways the compute the side effects based on many different scenarios because it will be un-ruly code, and too complex to try to explain to us what we will see.
The circular redefinitions case is one of the knightmares that hides in there... would mean having to assign priority to scopes, when there is no scopes yet. At the moment, the binary conformance table contains records for 3 types of conformances. First step would be to add a new type to match extension based conformance, and then record where it came from, and add some priority scheme to be able to navigate any conformance chain(remember that the pb grows everytime we decide 'oh cool, lets use a Padleft module rather than write my own 15 lines to do it - see the recent pb with nodejs). Not a simple task even with time, which they do not have now.

@core_team i know this is a coarse explanation, but hopefully at least in the right ballpark.

Roughly, yes. The specific problem regards answering the question “where must the runtime look to determine whether a given type X conforms to protocol P?”. Right now, the runtime conceptually needs to look:

  1) Into a list of known protocol conformances for the type X, and
  2) If X is a class type, the list of known protocol conformances for the superclass of X (recursively)

If we add the ability for a protocol extension to add a conformance to another protocol, add to that:

  3) Into the list of protocol extensions of other protocols Q that provide conformance to P

So, the difference is that in the case

protocol P { ... }
protocol Q : P { ... }
struct X : Q {...}

X's list of known protocol conformances already contains Q and P,
whereas in the case

protocol P { ... }
protocol Q { ... }
struct X : Q {...}
extension Q : P

X's list of known protocol conformances just contains Q and is not extended by P as a result of the extension?
Did I understand this right?

Yes, that’s correct.

Is that (not being able to extend the conformance lists of all types as a result of an extension) a restriction of having module boundaries?

Effectively, yes: you can’t simply enumerate all of the cases because some other module might add a new types/protocol extensions/conformances. It has to be dynamically discoverable.

yes… for each new module added to a known mix, the final conformances list can be completely different.

But this is information known at compile time and does not have to be determined at runtime.
An extension should be only effective in the module in which it is defined and in modules using that module. All of these get to know the extension at compile time.

The idea of swift 3/4 is that the stdlib ABI should be stable enough that it will be in the system rather than embedded in each app. Which means that the conformance table must be runtime discoverable from the module exporting it (in a section of the text segment), and its final effects computed by the runtime when the module gets loaded (again coarse grained expl) by each binary using it. This also lets them define new module boundaries in the system that we can transitively inherit.

Baking the final conformance statically into the module would leave us wondering why our code might seem to be 'frozen' and not using newer system defined conformances.

Good argument. So that would mean that the analysis would have to be done at linking time. This (like doing it at runtime) does open a can of worms about ambiguity, though: what happens when the new system version of a library suddenly defines an extension that conflicts with an extension in our module? Seems like that such a change should be confined to the system module unless doing a recompile, so we are back to my suggestion of resolving extensions at compile time?

There isn’t likely to be a perfect answer here. Resolving extensions at compile time cuts of various opportunities for dynamic discovery (e.g., the standard library’s print() looking for various conformances) that I, personally, am not willing to give up. Load-time resolution introduces the possibility of ambiguities—which we will likely need to detect or resolve in some way.

  - Doug

···

On Jun 8, 2016, at 11:52 AM, Thorsten Seitz <tseitz42@icloud.com> wrote:

Am 07.06.2016 um 07:55 schrieb LM <laurent.mihalkovic@gmail.com <mailto:laurent.mihalkovic@gmail.com>>:
On Jun 7, 2016, at 7:14 AM, Douglas Gregor <dgregor@apple.com <mailto:dgregor@apple.com>> wrote:

On Jun 6, 2016, at 10:08 PM, Thorsten Seitz <tseitz42@icloud.com <mailto:tseitz42@icloud.com>> wrote:
Am 06.06.2016 um 22:13 schrieb L Mihalkovic <laurent.mihalkovic@gmail.com <mailto:laurent.mihalkovic@gmail.com>>:

On Jun 6, 2016, at 9:34 PM, Douglas Gregor <dgregor@apple.com <mailto:dgregor@apple.com>> wrote:

On Jun 6, 2016, at 12:12 PM, Thorsten Seitz <tseitz42@icloud.com <mailto:tseitz42@icloud.com>> wrote:
Am 06.06.2016 um 18:51 schrieb Douglas Gregor <dgregor@apple.com <mailto:dgregor@apple.com>>:

On Jun 5, 2016, at 3:24 AM, L. Mihalkovic via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

-Thorsten

Mind you... this may not be a stupid idea at all, as it might align better with the practice of linking against specific SDKs to get a predictable level of behavior.

As for scope, my limited understanding of the loader is that there is no 'source' field in these conformance records that would allow the runtime to treat them hierarchically.

That’s not the model that Swift uses today. You can discover protocol conformances introduce by modules—whether you knew about those modules at compile time (but at launch time you end up with newer versions) or whether those modules were unknown, you see the conformances. The standard library’s “print” facility depends on this behavior to find CustomStringConvertible conformances.

Yes, we could make it all statically determined, but IMO that’s not the direction that Swift has been going.

  - Doug

  - Doug

-Thorsten

That’s a fairly significant expansion, and for each of the protocol extensions in (3), we need to evaluate whether X conforms to the extended protocol Q (and any additional constraints placed on that protocol extension).

  - Doug

On Jun 5, 2016, at 9:49 AM, Thorsten Seitz via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

Am 04.06.2016 um 23:18 schrieb Austin Zheng via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>>:

Hello Dan,

You'll be pleased to learn that conforming generic types conditionally to protocols is on the roadmap (and is one of the highest priority items for the versions of Swift following 3.0): https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md#conditional-conformances-

However, it's unlikely that protocols will gain conditional conformance: https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md#conditional-conformances-via-protocol-extensions

"However, similar to private conformances, it puts a major burden on the dynamic-casting runtime to chase down arbitrarily long and potentially cyclic chains of conformances, which makes efficient implementation nearly impossible.“

I’ve been wondering what the problem with the implementation is. I mean instead of using an extension the same conformance could have been declared beforehand, i.e. instead of

protocol P { func foo() }
protocol Q { func bar() }
extension Q : P { func foo() { bar() } }

we could have written the allowed

protocol P { func foo() }
protocol Q : P { func foo() { bar() } }

with the exact same effect.

The only difference would be that the extension might have been in another module than Q.
Is having to cross module boundaries causing the cited problems? Would the same problems exist if in the second example Q would be defined in another module?

-Thorsten

That document originates from a mailing list post made some time ago, and is a decent overview as to what sorts of type system features the Swift core developers are interested in building.

Best,
Austin


(L Mihalkovic) #17

The issue is to decide on the applicability scope. Thinking 'my app/their stuff' is an illusion. To the compiler & runtime there is only code split into modules, some in source code and others as dylibs (.dll, .so, ...). Any extension based conditional refines a protocol everywhere. What's hard is to compute the complete effects of these changes predictably, reliably and fast. Because when we consider 'but look, i have a single small extension', the compiler&runtime must be ready to deal symetrically with anything we throw at it. They can't start building 15 different ways the compute the side effects based on many different scenarios because it will be un-ruly code, and too complex to try to explain to us what we will see.
The circular redefinitions case is one of the knightmares that hides in there... would mean having to assign priority to scopes, when there is no scopes yet. At the moment, the binary conformance table contains records for 3 types of conformances. First step would be to add a new type to match extension based conformance, and then record where it came from, and add some priority scheme to be able to navigate any conformance chain(remember that the pb grows everytime we decide 'oh cool, lets use a Padleft module rather than write my own 15 lines to do it - see the recent pb with nodejs). Not a simple task even with time, which they do not have now.

@core_team i know this is a coarse explanation, but hopefully at least in the right ballpark.

Roughly, yes. The specific problem regards answering the question “where must the runtime look to determine whether a given type X conforms to protocol P?”. Right now, the runtime conceptually needs to look:

  1) Into a list of known protocol conformances for the type X, and
  2) If X is a class type, the list of known protocol conformances for the superclass of X (recursively)

If we add the ability for a protocol extension to add a conformance to another protocol, add to that:

  3) Into the list of protocol extensions of other protocols Q that provide conformance to P

So, the difference is that in the case

protocol P { ... }
protocol Q : P { ... }
struct X : Q {...}

X's list of known protocol conformances already contains Q and P,
whereas in the case

protocol P { ... }
protocol Q { ... }
struct X : Q {...}
extension Q : P

X's list of known protocol conformances just contains Q and is not extended by P as a result of the extension?
Did I understand this right?

Yes, that’s correct.

Is that (not being able to extend the conformance lists of all types as a result of an extension) a restriction of having module boundaries?

Effectively, yes: you can’t simply enumerate all of the cases because some other module might add a new types/protocol extensions/conformances. It has to be dynamically discoverable.

yes… for each new module added to a known mix, the final conformances list can be completely different.

But this is information known at compile time and does not have to be determined at runtime.
An extension should be only effective in the module in which it is defined and in modules using that module. All of these get to know the extension at compile time.

The idea of swift 3/4 is that the stdlib ABI should be stable enough that it will be in the system rather than embedded in each app. Which means that the conformance table must be runtime discoverable from the module exporting it (in a section of the text segment), and its final effects computed by the runtime when the module gets loaded (again coarse grained expl) by each binary using it. This also lets them define new module boundaries in the system that we can transitively inherit.

Baking the final conformance statically into the module would leave us wondering why our code might seem to be 'frozen' and not using newer system defined conformances.

Good argument. So that would mean that the analysis would have to be done at linking time.
This (like doing it at runtime) does open a can of worms about ambiguity, though: what happens when the new system version of a library suddenly defines an extension that conflicts with an extension in our module? Seems like that such a change should be confined to the system module unless doing a recompile, so we are back to my suggestion of resolving extensions at compile time?

What u call link is mostly a particular subcase of dynamic, so the choices are basically compile or dynamic. Doug has explained what the cost of compile would be. And it is not even something that macros would solve, because we would still have a whole for dynamically formed format patterns.

In the end, I think that compile time without a better scoping story (currently module or nothing, global conformance only, ...) is not much of a step either.

···

On Jun 8, 2016, at 10:34 PM, Douglas Gregor <dgregor@apple.com> wrote:

On Jun 8, 2016, at 11:52 AM, Thorsten Seitz <tseitz42@icloud.com> wrote:
Am 07.06.2016 um 07:55 schrieb LM <laurent.mihalkovic@gmail.com>:
On Jun 7, 2016, at 7:14 AM, Douglas Gregor <dgregor@apple.com> wrote:

On Jun 6, 2016, at 10:08 PM, Thorsten Seitz <tseitz42@icloud.com> wrote:

Am 06.06.2016 um 22:13 schrieb L Mihalkovic <laurent.mihalkovic@gmail.com>:

On Jun 6, 2016, at 9:34 PM, Douglas Gregor <dgregor@apple.com> wrote:
On Jun 6, 2016, at 12:12 PM, Thorsten Seitz <tseitz42@icloud.com> wrote:
Am 06.06.2016 um 18:51 schrieb Douglas Gregor <dgregor@apple.com>:

On Jun 5, 2016, at 3:24 AM, L. Mihalkovic via swift-evolution <swift-evolution@swift.org> wrote:

There isn’t likely to be a perfect answer here. Resolving extensions at compile time cuts of various opportunities for dynamic discovery (e.g., the standard library’s print() looking for various conformances) that I, personally, am not willing to give up. Load-time resolution introduces the possibility of ambiguities—which we will likely need to detect or resolve in some way.

  - Doug

-Thorsten

Mind you... this may not be a stupid idea at all, as it might align better with the practice of linking against specific SDKs to get a predictable level of behavior.

As for scope, my limited understanding of the loader is that there is no 'source' field in these conformance records that would allow the runtime to treat them hierarchically.

That’s not the model that Swift uses today. You can discover protocol conformances introduce by modules—whether you knew about those modules at compile time (but at launch time you end up with newer versions) or whether those modules were unknown, you see the conformances. The standard library’s “print” facility depends on this behavior to find CustomStringConvertible conformances.

Yes, we could make it all statically determined, but IMO that’s not the direction that Swift has been going.

  - Doug

  - Doug

-Thorsten

That’s a fairly significant expansion, and for each of the protocol extensions in (3), we need to evaluate whether X conforms to the extended protocol Q (and any additional constraints placed on that protocol extension).

  - Doug

On Jun 5, 2016, at 9:49 AM, Thorsten Seitz via swift-evolution <swift-evolution@swift.org> wrote:

Am 04.06.2016 um 23:18 schrieb Austin Zheng via swift-evolution <swift-evolution@swift.org>:

Hello Dan,

You'll be pleased to learn that conforming generic types conditionally to protocols is on the roadmap (and is one of the highest priority items for the versions of Swift following 3.0): https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md#conditional-conformances-

However, it's unlikely that protocols will gain conditional conformance: https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md#conditional-conformances-via-protocol-extensions

"However, similar to private conformances, it puts a major burden on the dynamic-casting runtime to chase down arbitrarily long and potentially cyclic chains of conformances, which makes efficient implementation nearly impossible.“

I’ve been wondering what the problem with the implementation is. I mean instead of using an extension the same conformance could have been declared beforehand, i.e. instead of

protocol P { func foo() }
protocol Q { func bar() }
extension Q : P { func foo() { bar() } }

we could have written the allowed

protocol P { func foo() }
protocol Q : P { func foo() { bar() } }

with the exact same effect.

The only difference would be that the extension might have been in another module than Q.
Is having to cross module boundaries causing the cited problems? Would the same problems exist if in the second example Q would be defined in another module?

-Thorsten

That document originates from a mailing list post made some time ago, and is a decent overview as to what sorts of type system features the Swift core developers are interested in building.

Best,
Austin