PITCH: New :== operator for generic constraints


(Charles Srstka) #1

MOTIVATION:

Suppose we have a bunch of peppers, and we’d like to make a function to pick them. We could just take an array, but Swift supports many types of sequence types beyond a simple array, and it would be nice to support those as well, particularly since we have this one client who stores his peppers in a custom sequence type called “Peck”, and we like to prevent him from having to convert to arrays all the time. We can do this with generic functions:

protocol Pepper {}

func pick<PepperType:Sequence>(peppers: PepperType) where PepperType.Iterator.Element == Pepper {
    // pick a peck of peppers
}

let peck: [Pepper] = ...

pick(peppers: peck)

However, this convenience method falls down as soon as we have a peck of *pickled* peppers:

struct PickledPepper: Pepper {}

let peck = [PickledPepper()]

pick(peppers: peck) // error: Generic parameter ‘PepperType’ could not be inferred

We can fix that by declaring the generic constraint to take any type that conforms to Pepper, instead of Pepper itself:

protocol Pepper {}

struct PickledPepper: Pepper {}

func pick<PepperType:Sequence>(peppers: PepperType) where PepperType.Iterator.Element: Pepper {
    // pick a peck of peppers
}

let peck = [PickledPepper()]

pick(peppers: peck) // works :slight_smile:

However, this now fails if we try to pass in a collection of items still typed as Peppers:

let peck: [Pepper] = [PickledPepper()]

pick(peppers: peck) // error: Generic parameter ‘PepperType’ could not be inferred

The workaround is to declare the convenience method twice:

func pick<PepperType:Sequence>(peppers: PepperType) where PepperType.Iterator.Element == Pepper {
    // pick a peck of peppers
}

func pick<PepperType:Sequence>(peppers: PepperType) where PepperType.Iterator.Element: Pepper {
    // do the same exact thing!
}

This leads to a lot of copy-paste code, the non-ideal nature of which should be clear. Unfortunately, when this has come up on the list in the past, it has been mentioned that there are some cases where an existential of a protocol does not conform to the protocol itself, so it is impossible to make : always match items that are typed to the protocol.

PROPOSED SOLUTION:

I propose for Swift 4 a new operator, :==, which would match not only a protocol, but any type that conforms to the protocol, like so:

func pick<PepperType:Sequence>(peppers: PepperType) where PepperType.Iterator.Element :== Pepper {
    // promptly pick a peck of plain or possibly pickled peppers
}

let peckOfPeppers: [Pepper] = [PickledPepper()]
pick(peppers: peckOfPeppers)

let peckOfPickledPeppers = [PickledPepper()]
pick(peppers: peckOfPickledPeppers)

DETAILED DESIGN:

1. We introduce a new operator :== which works in generic and associated type constraints.

2. The new operator matches anything that == would match.

3. The new operator also matches anything that : would match.

4. If we are in a case where either : or == cannot apply to the protocol on the right of the :== operator, throw an error.

ALTERNATIVES CONSIDERED:

Put down our peck of pickled peppers picking procedure, then repeat our peck of pickled peppers picking procedure, permuted to preserve the potentiality of protocol passing. Pah.

Charles


(Daniel Resnick) #2

It's weird to me that protocol-typed objects aren't seen as conforming to
that protocol. I would intuitively expect this function to work for both a
sequence of Pepper types and other types that conform to Pepper:
func pick<PepperType:Sequence>(peppers: PepperType) where
PepperType.Iterator.Element:
Pepper {
    // pick a peck of peppers
}


(David Sweeris) #3

Any proposal that expands the power of generic programming gets an almost automatic +1 from me.

I can't think of any circumstances in which I wouldn't want to use ":==" instead of ":". Are there any downsides to expanding ":" to mean what ":==" does?

Incidentally, I kinda thought things either already worked like this, or would work like this after generics were "completed", but I can't tell you why I thought that.

- Dave Sweeris

···

On Aug 16, 2016, at 16:49, Charles Srstka via swift-evolution <swift-evolution@swift.org> wrote:

MOTIVATION:

Suppose we have a bunch of peppers, and we’d like to make a function to pick them. We could just take an array, but Swift supports many types of sequence types beyond a simple array, and it would be nice to support those as well, particularly since we have this one client who stores his peppers in a custom sequence type called “Peck”, and we like to prevent him from having to convert to arrays all the time. We can do this with generic functions:

protocol Pepper {}

func pick<PepperType:Sequence>(peppers: PepperType) where PepperType.Iterator.Element == Pepper {
    // pick a peck of peppers
}

let peck: [Pepper] = ...

pick(peppers: peck)

However, this convenience method falls down as soon as we have a peck of *pickled* peppers:

struct PickledPepper: Pepper {}

let peck = [PickledPepper()]

pick(peppers: peck) // error: Generic parameter ‘PepperType’ could not be inferred

We can fix that by declaring the generic constraint to take any type that conforms to Pepper, instead of Pepper itself:

protocol Pepper {}

struct PickledPepper: Pepper {}

func pick<PepperType:Sequence>(peppers: PepperType) where PepperType.Iterator.Element: Pepper {
    // pick a peck of peppers
}

let peck = [PickledPepper()]

pick(peppers: peck) // works :slight_smile:

However, this now fails if we try to pass in a collection of items still typed as Peppers:

let peck: [Pepper] = [PickledPepper()]

pick(peppers: peck) // error: Generic parameter ‘PepperType’ could not be inferred

The workaround is to declare the convenience method twice:

func pick<PepperType:Sequence>(peppers: PepperType) where PepperType.Iterator.Element == Pepper {
    // pick a peck of peppers
}

func pick<PepperType:Sequence>(peppers: PepperType) where PepperType.Iterator.Element: Pepper {
    // do the same exact thing!
}

This leads to a lot of copy-paste code, the non-ideal nature of which should be clear. Unfortunately, when this has come up on the list in the past, it has been mentioned that there are some cases where an existential of a protocol does not conform to the protocol itself, so it is impossible to make : always match items that are typed to the protocol.

PROPOSED SOLUTION:

I propose for Swift 4 a new operator, :==, which would match not only a protocol, but any type that conforms to the protocol, like so:

func pick<PepperType:Sequence>(peppers: PepperType) where PepperType.Iterator.Element :== Pepper {
    // promptly pick a peck of plain or possibly pickled peppers
}

let peckOfPeppers: [Pepper] = [PickledPepper()]
pick(peppers: peckOfPeppers)

let peckOfPickledPeppers = [PickledPepper()]
pick(peppers: peckOfPickledPeppers)

DETAILED DESIGN:

1. We introduce a new operator :== which works in generic and associated type constraints.

2. The new operator matches anything that == would match.

3. The new operator also matches anything that : would match.

4. If we are in a case where either : or == cannot apply to the protocol on the right of the :== operator, throw an error.

ALTERNATIVES CONSIDERED:

Put down our peck of pickled peppers picking procedure, then repeat our peck of pickled peppers picking procedure, permuted to preserve the potentiality of protocol passing. Pah.

Charles

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


(Joe Groff) #4

This only makes sense as a constraint if P is a model of P, in which case we should just accept 'P: P'. You'd only need ':' at that point.

-Joe

···

On Aug 16, 2016, at 2:49 PM, Charles Srstka via swift-evolution <swift-evolution@swift.org> wrote:

MOTIVATION:

Suppose we have a bunch of peppers, and we’d like to make a function to pick them. We could just take an array, but Swift supports many types of sequence types beyond a simple array, and it would be nice to support those as well, particularly since we have this one client who stores his peppers in a custom sequence type called “Peck”, and we like to prevent him from having to convert to arrays all the time. We can do this with generic functions:

protocol Pepper {}

func pick<PepperType:Sequence>(peppers: PepperType) where PepperType.Iterator.Element == Pepper {
    // pick a peck of peppers
}

let peck: [Pepper] = ...

pick(peppers: peck)

However, this convenience method falls down as soon as we have a peck of *pickled* peppers:

struct PickledPepper: Pepper {}

let peck = [PickledPepper()]

pick(peppers: peck) // error: Generic parameter ‘PepperType’ could not be inferred

We can fix that by declaring the generic constraint to take any type that conforms to Pepper, instead of Pepper itself:

protocol Pepper {}

struct PickledPepper: Pepper {}

func pick<PepperType:Sequence>(peppers: PepperType) where PepperType.Iterator.Element: Pepper {
    // pick a peck of peppers
}

let peck = [PickledPepper()]

pick(peppers: peck) // works :slight_smile:

However, this now fails if we try to pass in a collection of items still typed as Peppers:

let peck: [Pepper] = [PickledPepper()]

pick(peppers: peck) // error: Generic parameter ‘PepperType’ could not be inferred

The workaround is to declare the convenience method twice:

func pick<PepperType:Sequence>(peppers: PepperType) where PepperType.Iterator.Element == Pepper {
    // pick a peck of peppers
}

func pick<PepperType:Sequence>(peppers: PepperType) where PepperType.Iterator.Element: Pepper {
    // do the same exact thing!
}

This leads to a lot of copy-paste code, the non-ideal nature of which should be clear. Unfortunately, when this has come up on the list in the past, it has been mentioned that there are some cases where an existential of a protocol does not conform to the protocol itself, so it is impossible to make : always match items that are typed to the protocol.

PROPOSED SOLUTION:

I propose for Swift 4 a new operator, :==, which would match not only a protocol, but any type that conforms to the protocol, like so:

func pick<PepperType:Sequence>(peppers: PepperType) where PepperType.Iterator.Element :== Pepper {
    // promptly pick a peck of plain or possibly pickled peppers
}

let peckOfPeppers: [Pepper] = [PickledPepper()]
pick(peppers: peckOfPeppers)

let peckOfPickledPeppers = [PickledPepper()]
pick(peppers: peckOfPickledPeppers)

DETAILED DESIGN:

1. We introduce a new operator :== which works in generic and associated type constraints.

2. The new operator matches anything that == would match.

3. The new operator also matches anything that : would match.

4. If we are in a case where either : or == cannot apply to the protocol on the right of the :== operator, throw an error.

ALTERNATIVES CONSIDERED:

Put down our peck of pickled peppers picking procedure, then repeat our peck of pickled peppers picking procedure, permuted to preserve the potentiality of protocol passing. Pah.


(Slava Pestov) #5

-1 — this adds a new syntax with little gain, and potentially a lot of additional complexity.

Unfortunately, when this has come up on the list in the past, it has been mentioned that there are some cases where an existential of a protocol does not conform to the protocol itself, so it is impossible to make : always match items that are typed to the protocol.

Indeed, the best solution IMHO would be to implement self-conforming protocols, so that what you’re describing can be expressed without any additional syntax.

The condition for a protocol to be able to conform to itself is the following:

- it must not have any associated type requirements, or contravariant Self in requirement signatures; eg, this rules out the following:

  protocol P { func foo(s: Self) }

- it must not have any static method or initializer requirements

With these conditions met, it would be possible to allow a generic parameter ’T : P’ to bind to a concrete type ’P’.

Note that the type checker work required for this is not very difficult. Indeed, we already allow @objc protocols that don’t have static requirements to self-conform. The real issue is the runtime representation gets tricky, if you want to allow a generic parameter to contain both a concrete type conforming to P, and an existential of P. Basically a generic parameter is passed as three values behind the scenes, the actual value, type metadata for the concrete type, and a witness table for the conformance. To allow the parameter to be bound to an existential type we would need to pass in a special witness table that unpacks the existential and calls the witness table contained in the existential.

It’s even worse if the protocol that self-conforms is a class-bound protocol. A generic parameter conforming to a class-bound protocol is passed as a reference counted pointer and witness table. Unfortunately, a class-bound existential is *not* a reference counted pointer — it has the witness table ‘inside’ the value.

Probably my explanation isn’t great, but really what’s bothering you here isn’t a language limitation, it’s an implementation limitation — once we figure out how to represent protocol existentials efficiently in a way allowing them to self-conform, we should be able to address these use-cases without new syntax.

Cheers,

Slava

···

On Aug 16, 2016, at 2:49 PM, Charles Srstka via swift-evolution <swift-evolution@swift.org> wrote:


(Charles Srstka) #6

Me neither, but the last time I proposed that, people stated that there were some cases where this could not work. No concrete examples were given, but I assume it probably has something to do with associated type wackiness. :== seems like a workable compromise to me.

https://lists.swift.org/pipermail/swift-evolution/Week-of-Mon-20160523/019510.html

Charles

···

On Aug 16, 2016, at 5:13 PM, David Sweeris <davesweeris@mac.com> wrote:

Any proposal that expands the power of generic programming gets an almost automatic +1 from me.

I can't think of any circumstances in which I wouldn't want to use ":==" instead of ":". Are there any downsides to expanding ":" to mean what ":==" does?

Incidentally, I kinda thought things either already worked like this, or would work like this after generics were "completed", but I can't tell you why I thought that.


(Charles Srstka) #7

-1 — this adds a new syntax with little gain, and potentially a lot of additional complexity.

Unfortunately, when this has come up on the list in the past, it has been mentioned that there are some cases where an existential of a protocol does not conform to the protocol itself, so it is impossible to make : always match items that are typed to the protocol.

Indeed, the best solution IMHO would be to implement self-conforming protocols, so that what you’re describing can be expressed without any additional syntax.

The condition for a protocol to be able to conform to itself is the following:

- it must not have any associated type requirements, or contravariant Self in requirement signatures; eg, this rules out the following:

protocol P { func foo(s: Self) }

- it must not have any static method or initializer requirements

With these conditions met, it would be possible to allow a generic parameter ’T : P’ to bind to a concrete type ’P’.

Well if it can be done, then that’s great. The reason I thought of a new modifier is because the last time I suggested extending : to include the protocol itself, the reaction was quite negative, suggesting that the amount of work necessary to do that would be outside the bounds of what could be considered reasonable.

I am a little concerned about the second requirement. Protocols that include static methods and initializers work perfectly well inside arrays, and restricting them from generic collections will further discourage use of the latter in favor of the former.

Note that the type checker work required for this is not very difficult. Indeed, we already allow @objc protocols that don’t have static requirements to self-conform. The real issue is the runtime representation gets tricky, if you want to allow a generic parameter to contain both a concrete type conforming to P, and an existential of P. Basically a generic parameter is passed as three values behind the scenes, the actual value, type metadata for the concrete type, and a witness table for the conformance. To allow the parameter to be bound to an existential type we would need to pass in a special witness table that unpacks the existential and calls the witness table contained in the existential.

It’s even worse if the protocol that self-conforms is a class-bound protocol. A generic parameter conforming to a class-bound protocol is passed as a reference counted pointer and witness table. Unfortunately, a class-bound existential is *not* a reference counted pointer — it has the witness table ‘inside’ the value.

Probably my explanation isn’t great, but really what’s bothering you here isn’t a language limitation, it’s an implementation limitation — once we figure out how to represent protocol existentials efficiently in a way allowing them to self-conform, we should be able to address these use-cases without new syntax.

What I’ve long wondered is why we don’t have this problem with arrays.

protocol MyProto {
    func baz()
    
    // Includes static and initializer requirements
    static func qux()
    init()
}

struct MyStruct: MyProto {
    func baz() {
        print("baz")
    }
    
    static func qux() {
        print("qux")
    }
    
    init() {
        print("init")
    }
}

func foo(bar: [MyProto]) {
    for eachMyProto in bar {
        eachMyProto.baz()
    }
}

let x = [MyStruct()]
let y = x as [MyProto]

foo(bar: x)
foo(bar: y)

This compiles and runs fine. Why is that?

Charles

···

On Aug 16, 2016, at 8:13 PM, Slava Pestov <spestov@apple.com> wrote:

On Aug 16, 2016, at 2:49 PM, Charles Srstka via swift-evolution <swift-evolution@swift.org> wrote:


(Xiaodi Wu) #8

Any proposal that expands the power of generic programming gets an almost
automatic +1 from me.

I can't think of any circumstances in which I wouldn't want to use ":=="
instead of ":". Are there any downsides to expanding ":" to mean what ":=="
does?

Incidentally, I kinda thought things either already worked like this, or
would work like this after generics were "completed", but I can't tell you
why I thought that.

Me neither, but the last time I proposed that, people stated that there
were some cases where this could not work. No concrete examples were given,
but I assume it probably has something to do with associated type
wackiness. :== seems like a workable compromise to me.

If an existential of a protocol P doesn't conform to itself, what can you
do inside the body of a generic function that has a generic constraint
specified with `:==`? In other words, what would we know about what's in
common between such an existential of a protocol and types that conform to
the protocol?

https://lists.swift.org/pipermail/swift-evolution/

···

On Tue, Aug 16, 2016 at 5:19 PM, Charles Srstka via swift-evolution < swift-evolution@swift.org> wrote:

On Aug 16, 2016, at 5:13 PM, David Sweeris <davesweeris@mac.com> wrote:
Week-of-Mon-20160523/019510.html

Charles

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


(Slava Pestov) #9

-1 — this adds a new syntax with little gain, and potentially a lot of additional complexity.

Unfortunately, when this has come up on the list in the past, it has been mentioned that there are some cases where an existential of a protocol does not conform to the protocol itself, so it is impossible to make : always match items that are typed to the protocol.

Indeed, the best solution IMHO would be to implement self-conforming protocols, so that what you’re describing can be expressed without any additional syntax.

The condition for a protocol to be able to conform to itself is the following:

- it must not have any associated type requirements, or contravariant Self in requirement signatures; eg, this rules out the following:

protocol P { func foo(s: Self) }

- it must not have any static method or initializer requirements

With these conditions met, it would be possible to allow a generic parameter ’T : P’ to bind to a concrete type ’P’.

Well if it can be done, then that’s great. The reason I thought of a new modifier is because the last time I suggested extending : to include the protocol itself, the reaction was quite negative, suggesting that the amount of work necessary to do that would be outside the bounds of what could be considered reasonable.

The amount of work is certainly not trivial, but this feature request comes up often enough that I think we should try to tackle it at some point.

I am a little concerned about the second requirement. Protocols that include static methods and initializers work perfectly well inside arrays, and restricting them from generic collections will further discourage use of the latter in favor of the former.

Here is why we must have that requirement. Consider the following code:

protocol P {
  init()
}

struct A : P {
  init() {}
}

struct B : P {
  init() {}
}

func makeIt<T : P>() -> T {
  return T()
}

I can use this function as follows:

let a: A = makeIt() // Creates a new ‘A'
let a: B = makeIt() // Creates a new ‘B’

Now suppose we allow P to self-conform. Then the following becomes valid:

let p: P = makeIt()

What exactly would makeIt() do in this case? There’s no concrete type passed in, or any way of getting one, so there’s nothing to construct. The same issue would come up with static methods here.

Note that the type checker work required for this is not very difficult. Indeed, we already allow @objc protocols that don’t have static requirements to self-conform. The real issue is the runtime representation gets tricky, if you want to allow a generic parameter to contain both a concrete type conforming to P, and an existential of P. Basically a generic parameter is passed as three values behind the scenes, the actual value, type metadata for the concrete type, and a witness table for the conformance. To allow the parameter to be bound to an existential type we would need to pass in a special witness table that unpacks the existential and calls the witness table contained in the existential.

It’s even worse if the protocol that self-conforms is a class-bound protocol. A generic parameter conforming to a class-bound protocol is passed as a reference counted pointer and witness table. Unfortunately, a class-bound existential is *not* a reference counted pointer — it has the witness table ‘inside’ the value.

Probably my explanation isn’t great, but really what’s bothering you here isn’t a language limitation, it’s an implementation limitation — once we figure out how to represent protocol existentials efficiently in a way allowing them to self-conform, we should be able to address these use-cases without new syntax.

What I’ve long wondered is why we don’t have this problem with arrays.

protocol MyProto {
    func baz()
    
    // Includes static and initializer requirements
    static func qux()
    init()
}

struct MyStruct: MyProto {
    func baz() {
        print("baz")
    }
    
    static func qux() {
        print("qux")
    }
    
    init() {
        print("init")
    }
}

func foo(bar: [MyProto]) {
    for eachMyProto in bar {
        eachMyProto.baz()
    }
}

let x = [MyStruct()]
let y = x as [MyProto]

foo(bar: x)
foo(bar: y)

This compiles and runs fine. Why is that?

Recall that an Array is just a (very complex) generic struct in Swift:

struct Array<Element> {
  …
}

The key here is that there are *no generic requirements* placed on the parameter ‘Element’.

So both Array<MyStruct> and Array<MyProto> are perfectly reasonable types, because ‘Element’ can be bound to any type, since there’s nothing you can *do* with an ‘Element’, except for what you can do with all values, which is assign it into a location, load it from a location, or cast it to something.

So binding Element to a protocol type is fine — there’s no witness table of operations passed behind the scenes, because there are no requirements. The representational issue I detailed in my previous e-mail only comes up if additional requirements are placed on the generic parameter.

Hopefully this clarifies things!

Slava

···

On Aug 16, 2016, at 6:40 PM, Charles Srstka <cocoadev@charlessoft.com> wrote:

On Aug 16, 2016, at 8:13 PM, Slava Pestov <spestov@apple.com <mailto:spestov@apple.com>> wrote:

On Aug 16, 2016, at 2:49 PM, Charles Srstka via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

Charles


(Slava Pestov) #10

-1 — this adds a new syntax with little gain, and potentially a lot of additional complexity.

Unfortunately, when this has come up on the list in the past, it has been mentioned that there are some cases where an existential of a protocol does not conform to the protocol itself, so it is impossible to make : always match items that are typed to the protocol.

Indeed, the best solution IMHO would be to implement self-conforming protocols, so that what you’re describing can be expressed without any additional syntax.

The condition for a protocol to be able to conform to itself is the following:

- it must not have any associated type requirements, or contravariant Self in requirement signatures; eg, this rules out the following:

protocol P { func foo(s: Self) }

- it must not have any static method or initializer requirements

With these conditions met, it would be possible to allow a generic parameter ’T : P’ to bind to a concrete type ’P’.

Well if it can be done, then that’s great. The reason I thought of a new modifier is because the last time I suggested extending : to include the protocol itself, the reaction was quite negative, suggesting that the amount of work necessary to do that would be outside the bounds of what could be considered reasonable.

The amount of work is certainly not trivial, but this feature request comes up often enough that I think we should try to tackle it at some point.

I am a little concerned about the second requirement. Protocols that include static methods and initializers work perfectly well inside arrays, and restricting them from generic collections will further discourage use of the latter in favor of the former.

Here is why we must have that requirement. Consider the following code:

protocol P {
  init()
}

struct A : P {
  init() {}
}

struct B : P {
  init() {}
}

func makeIt<T : P>() -> T {
  return T()
}

I can use this function as follows:

let a: A = makeIt() // Creates a new ‘A'
let a: B = makeIt() // Creates a new ‘B’

Now suppose we allow P to self-conform. Then the following becomes valid:

let p: P = makeIt()

What exactly would makeIt() do in this case? There’s no concrete type passed in, or any way of getting one, so there’s nothing to construct. The same issue would come up with static methods here.

Yeah, so I should add one way around this is to factor your protocol into two — Q can be a self-conforming base protocol, and P can refine Q with additional requirements such as initializers. This means that forming a type Array<P> and passing it around is totally fine; you just can’t pass an Array<P> to a function with type <T : P> Array<T> -> …, because P cannot bind to <T : P>. You’d be able to pass an Array<P> to a functio nwith type <T : Q> Array<T> -> … though — the substitution T := P would be permitted in this case, since there are no static requirements visible on ’T’.

Slava

···

On Aug 16, 2016, at 6:51 PM, Slava Pestov <spestov@apple.com> wrote:

On Aug 16, 2016, at 6:40 PM, Charles Srstka <cocoadev@charlessoft.com <mailto:cocoadev@charlessoft.com>> wrote:

On Aug 16, 2016, at 8:13 PM, Slava Pestov <spestov@apple.com <mailto:spestov@apple.com>> wrote:

On Aug 16, 2016, at 2:49 PM, Charles Srstka via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

Note that the type checker work required for this is not very difficult. Indeed, we already allow @objc protocols that don’t have static requirements to self-conform. The real issue is the runtime representation gets tricky, if you want to allow a generic parameter to contain both a concrete type conforming to P, and an existential of P. Basically a generic parameter is passed as three values behind the scenes, the actual value, type metadata for the concrete type, and a witness table for the conformance. To allow the parameter to be bound to an existential type we would need to pass in a special witness table that unpacks the existential and calls the witness table contained in the existential.

It’s even worse if the protocol that self-conforms is a class-bound protocol. A generic parameter conforming to a class-bound protocol is passed as a reference counted pointer and witness table. Unfortunately, a class-bound existential is *not* a reference counted pointer — it has the witness table ‘inside’ the value.

Probably my explanation isn’t great, but really what’s bothering you here isn’t a language limitation, it’s an implementation limitation — once we figure out how to represent protocol existentials efficiently in a way allowing them to self-conform, we should be able to address these use-cases without new syntax.

What I’ve long wondered is why we don’t have this problem with arrays.

protocol MyProto {
    func baz()
    
    // Includes static and initializer requirements
    static func qux()
    init()
}

struct MyStruct: MyProto {
    func baz() {
        print("baz")
    }
    
    static func qux() {
        print("qux")
    }
    
    init() {
        print("init")
    }
}

func foo(bar: [MyProto]) {
    for eachMyProto in bar {
        eachMyProto.baz()
    }
}

let x = [MyStruct()]
let y = x as [MyProto]

foo(bar: x)
foo(bar: y)

This compiles and runs fine. Why is that?

Recall that an Array is just a (very complex) generic struct in Swift:

struct Array<Element> {
  …
}

The key here is that there are *no generic requirements* placed on the parameter ‘Element’.

So both Array<MyStruct> and Array<MyProto> are perfectly reasonable types, because ‘Element’ can be bound to any type, since there’s nothing you can *do* with an ‘Element’, except for what you can do with all values, which is assign it into a location, load it from a location, or cast it to something.

So binding Element to a protocol type is fine — there’s no witness table of operations passed behind the scenes, because there are no requirements. The representational issue I detailed in my previous e-mail only comes up if additional requirements are placed on the generic parameter.

Hopefully this clarifies things!

Slava

Charles


(Charles Srstka) #11

Argh, that’s particularly frustrating since in something like ‘func foo<T : P>(t: T)’ or ‘func foo<S : Sequence>(s: S) where S.IteratorElement: P’, you’re only ever getting instances anyway since the parameter is in the input, so calling initializers or static functions isn’t something you can even do (unless you call .dynamicType, at which point you *do* have a concrete type at runtime thanks to the dynamic check).

I wish there were a way to have partial conformance in cases like these. Like how this causes what’s probably Swift’s most confusing compiler error (certainly one of its most asked about):

protocol P: Equatable {
    static func ==(l: Self, r: Self) -> Bool
    
    func foo()
}

struct S: P {
    static func ==(l: S, r: S) -> Bool {
        return true
    }
    
    func foo() {
        print("foo")
    }
}

let s = S()
let p = s as P // error: Protocol ‘P’ can only be used as a generic constraint because it has Self or associated type requirements

It would make using protocols so much less teeth-grinding if the compiler *did* allow you to type the variable as P, but then would just throw an error if you tried to call one of the “problem” methods (in this case, using the ‘==' operator would be an error, but calling ‘foo’ would be fine). If this were possible, the conformance for a variable typed P would just not pick up “illegal” things like initializers, and would also leave out conformance for things like 'makeIt()' above which return the generic parameter in the output, rather than the input, necessitating a concrete type. I’m probably dreaming, I know.

Actually, what I wish is that Swift had an equivalent of the 'id <P>’ type in Objective-C. That notation always stood for an instance of something that conformed to P, rather than "maybe P itself, and maybe something that conforms to it”. If we could do that, we could just pass sequences of 'id <P>’ (in whatever syntax we gave it in Swift) to a sequence where Element: P, and it’d work fine regardless of anything that prevented P from conforming to P.

Charles

···

On Aug 16, 2016, at 8:51 PM, Slava Pestov <spestov@apple.com> wrote:

Here is why we must have that requirement. Consider the following code:

protocol P {
  init()
}

struct A : P {
  init() {}
}

struct B : P {
  init() {}
}

func makeIt<T : P>() -> T {
  return T()
}

I can use this function as follows:

let a: A = makeIt() // Creates a new ‘A'
let a: B = makeIt() // Creates a new ‘B’

Now suppose we allow P to self-conform. Then the following becomes valid:

let p: P = makeIt()

What exactly would makeIt() do in this case? There’s no concrete type passed in, or any way of getting one, so there’s nothing to construct. The same issue would come up with static methods here.


(Brent Royal-Gordon) #12

Could we mark the generic parameter with an attribute which basically means "I will not call static members of this type except through a `type(of:)` call"?

For that matter, should we just do that by default? It seems like in most cases where we don't somehow pass an instance of the type, we end up passing an instance of its metatype anyway. See, for instance, `unsafeBitCast(_:to:)`, which takes an instance of the metatype which is technically redundant, but helps pin down the return type. Anything you might need to do with `U.self` could instead be done with `to`.

···

On Aug 16, 2016, at 6:51 PM, Slava Pestov via swift-evolution <swift-evolution@swift.org> wrote:

I am a little concerned about the second requirement. Protocols that include static methods and initializers work perfectly well inside arrays, and restricting them from generic collections will further discourage use of the latter in favor of the former.

Here is why we must have that requirement. Consider the following code:

protocol P {
  init()
}

struct A : P {
  init() {}
}

struct B : P {
  init() {}
}

func makeIt<T : P>() -> T {
  return T()
}

I can use this function as follows:

let a: A = makeIt() // Creates a new ‘A'
let a: B = makeIt() // Creates a new ‘B’

Now suppose we allow P to self-conform. Then the following becomes valid:

let p: P = makeIt()

What exactly would makeIt() do in this case? There’s no concrete type passed in, or any way of getting one, so there’s nothing to construct. The same issue would come up with static methods here.

--
Brent Royal-Gordon
Architechies


(Charles Srstka) #13

My proposal is that in such cases, using :== would lead to a compiler error.

Charles

···

On Aug 16, 2016, at 5:30 PM, Xiaodi Wu <xiaodi.wu@gmail.com> wrote:

On Tue, Aug 16, 2016 at 5:19 PM, Charles Srstka via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

On Aug 16, 2016, at 5:13 PM, David Sweeris <davesweeris@mac.com <mailto:davesweeris@mac.com>> wrote:

Any proposal that expands the power of generic programming gets an almost automatic +1 from me.

I can't think of any circumstances in which I wouldn't want to use ":==" instead of ":". Are there any downsides to expanding ":" to mean what ":==" does?

Incidentally, I kinda thought things either already worked like this, or would work like this after generics were "completed", but I can't tell you why I thought that.

Me neither, but the last time I proposed that, people stated that there were some cases where this could not work. No concrete examples were given, but I assume it probably has something to do with associated type wackiness. :== seems like a workable compromise to me.

If an existential of a protocol P doesn't conform to itself, what can you do inside the body of a generic function that has a generic constraint specified with `:==`? In other words, what would we know about what's in common between such an existential of a protocol and types that conform to the protocol?


(Slava Pestov) #14

Here is why we must have that requirement. Consider the following code:

protocol P {
  init()
}

struct A : P {
  init() {}
}

struct B : P {
  init() {}
}

func makeIt<T : P>() -> T {
  return T()
}

I can use this function as follows:

let a: A = makeIt() // Creates a new ‘A'
let a: B = makeIt() // Creates a new ‘B’

Now suppose we allow P to self-conform. Then the following becomes valid:

let p: P = makeIt()

What exactly would makeIt() do in this case? There’s no concrete type passed in, or any way of getting one, so there’s nothing to construct. The same issue would come up with static methods here.

Argh, that’s particularly frustrating since in something like ‘func foo<T : P>(t: T)’ or ‘func foo<S : Sequence>(s: S) where S.IteratorElement: P’, you’re only ever getting instances anyway since the parameter is in the input, so calling initializers or static functions isn’t something you can even do (unless you call .dynamicType, at which point you *do* have a concrete type at runtime thanks to the dynamic check).

Well, if you have ‘func foo<T : P>(t: T)’, then you can write T.someStaticMember() to call static members — it’s true you also have an instance ’t’, but you can also work directly with the type. But I suspect this is not what you meant, because:

I wish there were a way to have partial conformance in cases like these. Like how this causes what’s probably Swift’s most confusing compiler error (certainly one of its most asked about):

protocol P: Equatable {
    static func ==(l: Self, r: Self) -> Bool
    
    func foo()
}

struct S: P {
    static func ==(l: S, r: S) -> Bool {
        return true
    }
    
    func foo() {
        print("foo")
    }
}

let s = S()
let p = s as P // error: Protocol ‘P’ can only be used as a generic constraint because it has Self or associated type requirements

Yep :slight_smile: So the property of ‘can be used as an existential type’ is actually a bit different from ‘protocol conforms to itself’. The rules here are:

- Self must not appear in contravariant position
- Protocol has no associated types

Note that static members and initializers are OK, and you can call them via ‘p.dynamicType.foo()’ where p : P.

It would make using protocols so much less teeth-grinding if the compiler *did* allow you to type the variable as P, but then would just throw an error if you tried to call one of the “problem” methods (in this case, using the ‘==' operator would be an error, but calling ‘foo’ would be fine). If this were possible, the conformance for a variable typed P would just not pick up “illegal” things like initializers, and would also leave out conformance for things like 'makeIt()' above which return the generic parameter in the output, rather than the input, necessitating a concrete type. I’m probably dreaming, I know.

In the type checker, this more precise, per-member check is already implemented, interestingly enough. It comes up with protocol extensions. Imagine you have a protocol ‘P’ that can be used as an existential, but an extension of P adds a problematic member:

protocol P {
  func f() -> Int
}

extension P {
  func ff(other: Self) -> Int { return f() + s.f()) }
}

Here, you don’t want to entirely ban the type ‘P’, because the extension might come from another module, and it shouldn’t just break everyone’s code. So the solution is that you can use ‘P’ as an existential, but if you try to reference ‘p.ff’ where p : P, you get a diagnostic, because that particular member is unavailable.

In fact, I think the separate restriction that rules out usage of the overall type when one of the protocol’s requirements is problematic, is mostly artificial, in that it could just be disabled and you’d be able to pass around ‘Equatable’ values, etc, because the lower layers don’t care (I think).

I do remember it was explained to me at one point that this is how it was in the early days of Swift, but it made code completion and diagnostics confusing, because with some protocols (like Sequence) most members became inaccessible.

A better approach is to implement more general existential types which expose ways of working with their associated types, rather than just banning certain members from being used altogether. This is described in Doug's ‘completing generics’ document, and again, it is quite a large project :slight_smile:

Actually, what I wish is that Swift had an equivalent of the 'id <P>’ type in Objective-C. That notation always stood for an instance of something that conformed to P, rather than "maybe P itself, and maybe something that conforms to it”. If we could do that, we could just pass sequences of 'id <P>’ (in whatever syntax we gave it in Swift) to a sequence where Element: P, and it’d work fine regardless of anything that prevented P from conforming to P.

In fact I think some of the proposals call for Any<P> as the syntax for the most general existential of type ‘P’, with other syntax when associated types are bound. I must admit I haven’t followed the discussions around generalized existentials very closely though.

So it sounds like your original :== operator idea is really about implementing self-conforming protocols, as well as generalized existentials. These are quite difficult projects, but I hope we’ll tackle them one day. Patches are welcome :slight_smile:

···

On Aug 16, 2016, at 8:52 PM, Charles Srstka <cocoadev@charlessoft.com> wrote:

On Aug 16, 2016, at 8:51 PM, Slava Pestov <spestov@apple.com <mailto:spestov@apple.com>> wrote:

Charles


(Charles Srstka) #15

Argh, that’s particularly frustrating since in something like ‘func foo<T : P>(t: T)’ or ‘func foo<S : Sequence>(s: S) where S.IteratorElement: P’, you’re only ever getting instances anyway since the parameter is in the input, so calling initializers or static functions isn’t something you can even do (unless you call .dynamicType, at which point you *do* have a concrete type at runtime thanks to the dynamic check).

Well, if you have ‘func foo<T : P>(t: T)’, then you can write T.someStaticMember() to call static members — it’s true you also have an instance ’t’, but you can also work directly with the type. But I suspect this is not what you meant, because:

Agh, you’re right, I’d forgotten about that. It’s days like this that I miss Objective-C’s “It just works” dynamism. :wink:

I wish there were a way to have partial conformance in cases like these. Like how this causes what’s probably Swift’s most confusing compiler error (certainly one of its most asked about):

protocol P: Equatable {
    static func ==(l: Self, r: Self) -> Bool
    
    func foo()
}

struct S: P {
    static func ==(l: S, r: S) -> Bool {
        return true
    }
    
    func foo() {
        print("foo")
    }
}

let s = S()
let p = s as P // error: Protocol ‘P’ can only be used as a generic constraint because it has Self or associated type requirements

Yep :slight_smile: So the property of ‘can be used as an existential type’ is actually a bit different from ‘protocol conforms to itself’. The rules here are:

- Self must not appear in contravariant position
- Protocol has no associated types

Note that static members and initializers are OK, and you can call them via ‘p.dynamicType.foo()’ where p : P.

It would make using protocols so much less teeth-grinding if the compiler *did* allow you to type the variable as P, but then would just throw an error if you tried to call one of the “problem” methods (in this case, using the ‘==' operator would be an error, but calling ‘foo’ would be fine). If this were possible, the conformance for a variable typed P would just not pick up “illegal” things like initializers, and would also leave out conformance for things like 'makeIt()' above which return the generic parameter in the output, rather than the input, necessitating a concrete type. I’m probably dreaming, I know.

In the type checker, this more precise, per-member check is already implemented, interestingly enough. It comes up with protocol extensions. Imagine you have a protocol ‘P’ that can be used as an existential, but an extension of P adds a problematic member:

protocol P {
  func f() -> Int
}

extension P {
  func ff(other: Self) -> Int { return f() + s.f()) }
}

Here, you don’t want to entirely ban the type ‘P’, because the extension might come from another module, and it shouldn’t just break everyone’s code. So the solution is that you can use ‘P’ as an existential, but if you try to reference ‘p.ff’ where p : P, you get a diagnostic, because that particular member is unavailable.

In fact, I think the separate restriction that rules out usage of the overall type when one of the protocol’s requirements is problematic, is mostly artificial, in that it could just be disabled and you’d be able to pass around ‘Equatable’ values, etc, because the lower layers don’t care (I think).

I do remember it was explained to me at one point that this is how it was in the early days of Swift, but it made code completion and diagnostics confusing, because with some protocols (like Sequence) most members became inaccessible.

Oh dear. I don’t know how confusing those things were, but if you Google the “self or associated type requirements” error to see how many people it has confused, I think you’ll find that it’d be quite hard for the more precise check to create more confusion than that. Perhaps I should write up a proposal to change this, if it’s easily enough done that it’s actually been done once already.

Imagine if other aspects of the system worked this way, like the ObjC bridge for instance. Imagine you had an NSObject-derived class that some ObjC code somewhere was calling, and the minute you add a method somewhere that returns a tuple or something, instead of just not giving ObjC access to that one method, it suddenly just up and said BZZT. NO OBJC BRIDGE FOR YOU. Wouldn’t that be frustrating?

The other trouble is that it’s not just confusing; it can very easily get in the way of your work even if you know exactly what’s going on, necessitating kludges like AnyHashable just to do things like have a dictionary that can take more than one key type (an example that’s particularly irritating since the only method you care about, hashValue, is just a plain old Int that doesn’t care about the Self requirement at all). I know that a while ago I ended up using my own Equatable substitute with an ObjC-style isEqual() method on some types, just because actually implementing Equatable was throwing a huge spanner into the rest of the design.

A better approach is to implement more general existential types which expose ways of working with their associated types, rather than just banning certain members from being used altogether. This is described in Doug's ‘completing generics’ document, and again, it is quite a large project :slight_smile:

Actually, what I wish is that Swift had an equivalent of the 'id <P>’ type in Objective-C. That notation always stood for an instance of something that conformed to P, rather than "maybe P itself, and maybe something that conforms to it”. If we could do that, we could just pass sequences of 'id <P>’ (in whatever syntax we gave it in Swift) to a sequence where Element: P, and it’d work fine regardless of anything that prevented P from conforming to P.

In fact I think some of the proposals call for Any<P> as the syntax for the most general existential of type ‘P’, with other syntax when associated types are bound. I must admit I haven’t followed the discussions around generalized existentials very closely though.

So it sounds like your original :== operator idea is really about implementing self-conforming protocols, as well as generalized existentials. These are quite difficult projects, but I hope we’ll tackle them one day. Patches are welcome :slight_smile:

Well, the idea was to create an easier-to-implement alternative to self-conforming protocols, which could be done if :== were expanded to one function that uses ==, and another with the same body that uses :, because I was under the impression that the compiler team did not want to implement self-conforming protocols.

Charles

···

On Aug 16, 2016, at 11:42 PM, Slava Pestov <spestov@apple.com> wrote:


(Alexis) #16

Slava and Joe's suggestion of self conformance and the constraints involved are something that's been explored in other languages with similar systems. There's a great series of posts discussing some of the issues at hand:

These describe the constraints of interest (“object safety”):
http://huonw.github.io/blog/2015/01/object-safety/
http://huonw.github.io/blog/2015/05/where-self-meets-sized-revisiting-object-safety/

These are in the context of the Rust language, whose traits are similar in many ways to Swift protocols. These posts should give enough background to those familiar with protocols but not traits:
http://huonw.github.io/blog/2015/01/peeking-inside-trait-objects/
http://huonw.github.io/blog/2015/01/the-sized-trait/

One idea presented here that's applicable to Swift is the ability to distinguish between “static type” and “dynamic type” via the Sized trait (Sized referring to "statically sized"). By default most locations that work with generics implicitly assume Sized, which leads to more efficient code, and allows things like:

let x = T.staticMethod()

to make sense. However, if a piece of code isn’t interested in these capabilities, it can add ?Sized to the type constraint to “remove” the assumption, constraining the body of the method. Let’s call `?Sized` in Swift `MaybeExistential` (because that’s what it would mean). So you would write something like:

func foo<T: MyProto & MaybeExistential>(input: T) { … }

and the effect would be that MyProto existentials could be passed to this function in the knowledge that the function would be forbidden from calling static initializers and any other problematic methods. This isn’t a totally unprecedented strategy in Swift either: this is the same kind of idea behind `@noescape`; constraining the user of the generic type to empower the provider.

···

On Aug 17, 2016, at 12:42 AM, Slava Pestov via swift-evolution <swift-evolution@swift.org> wrote:

On Aug 16, 2016, at 8:52 PM, Charles Srstka <cocoadev@charlessoft.com> wrote:

On Aug 16, 2016, at 8:51 PM, Slava Pestov <spestov@apple.com> wrote:

Here is why we must have that requirement. Consider the following code:

protocol P {
  init()
}

struct A : P {
  init() {}
}

struct B : P {
  init() {}
}

func makeIt<T : P>() -> T {
  return T()
}

I can use this function as follows:

let a: A = makeIt() // Creates a new ‘A'
let a: B = makeIt() // Creates a new ‘B’

Now suppose we allow P to self-conform. Then the following becomes valid:

let p: P = makeIt()

What exactly would makeIt() do in this case? There’s no concrete type passed in, or any way of getting one, so there’s nothing to construct. The same issue would come up with static methods here.

Argh, that’s particularly frustrating since in something like ‘func foo<T : P>(t: T)’ or ‘func foo<S : Sequence>(s: S) where S.IteratorElement: P’, you’re only ever getting instances anyway since the parameter is in the input, so calling initializers or static functions isn’t something you can even do (unless you call .dynamicType, at which point you *do* have a concrete type at runtime thanks to the dynamic check).

Well, if you have ‘func foo<T : P>(t: T)’, then you can write T.someStaticMember() to call static members — it’s true you also have an instance ’t’, but you can also work directly with the type. But I suspect this is not what you meant, because:

I wish there were a way to have partial conformance in cases like these. Like how this causes what’s probably Swift’s most confusing compiler error (certainly one of its most asked about):

protocol P: Equatable {
    static func ==(l: Self, r: Self) -> Bool
    
    func foo()
}

struct S: P {
    static func ==(l: S, r: S) -> Bool {
        return true
    }
    
    func foo() {
        print("foo")
    }
}

let s = S()
let p = s as P // error: Protocol ‘P’ can only be used as a generic constraint because it has Self or associated type requirements

Yep :slight_smile: So the property of ‘can be used as an existential type’ is actually a bit different from ‘protocol conforms to itself’. The rules here are:

- Self must not appear in contravariant position
- Protocol has no associated types

Note that static members and initializers are OK, and you can call them via ‘p.dynamicType.foo()’ where p : P.

It would make using protocols so much less teeth-grinding if the compiler *did* allow you to type the variable as P, but then would just throw an error if you tried to call one of the “problem” methods (in this case, using the ‘==' operator would be an error, but calling ‘foo’ would be fine). If this were possible, the conformance for a variable typed P would just not pick up “illegal” things like initializers, and would also leave out conformance for things like 'makeIt()' above which return the generic parameter in the output, rather than the input, necessitating a concrete type. I’m probably dreaming, I know.

In the type checker, this more precise, per-member check is already implemented, interestingly enough. It comes up with protocol extensions. Imagine you have a protocol ‘P’ that can be used as an existential, but an extension of P adds a problematic member:

protocol P {
  func f() -> Int
}

extension P {
  func ff(other: Self) -> Int { return f() + s.f()) }
}

Here, you don’t want to entirely ban the type ‘P’, because the extension might come from another module, and it shouldn’t just break everyone’s code. So the solution is that you can use ‘P’ as an existential, but if you try to reference ‘p.ff’ where p : P, you get a diagnostic, because that particular member is unavailable.

In fact, I think the separate restriction that rules out usage of the overall type when one of the protocol’s requirements is problematic, is mostly artificial, in that it could just be disabled and you’d be able to pass around ‘Equatable’ values, etc, because the lower layers don’t care (I think).

I do remember it was explained to me at one point that this is how it was in the early days of Swift, but it made code completion and diagnostics confusing, because with some protocols (like Sequence) most members became inaccessible.

A better approach is to implement more general existential types which expose ways of working with their associated types, rather than just banning certain members from being used altogether. This is described in Doug's ‘completing generics’ document, and again, it is quite a large project :slight_smile:

Actually, what I wish is that Swift had an equivalent of the 'id <P>’ type in Objective-C. That notation always stood for an instance of something that conformed to P, rather than "maybe P itself, and maybe something that conforms to it”. If we could do that, we could just pass sequences of 'id <P>’ (in whatever syntax we gave it in Swift) to a sequence where Element: P, and it’d work fine regardless of anything that prevented P from conforming to P.

In fact I think some of the proposals call for Any<P> as the syntax for the most general existential of type ‘P’, with other syntax when associated types are bound. I must admit I haven’t followed the discussions around generalized existentials very closely though.

So it sounds like your original :== operator idea is really about implementing self-conforming protocols, as well as generalized existentials. These are quite difficult projects, but I hope we’ll tackle them one day. Patches are welcome :slight_smile:

Charles

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


(Slava Pestov) #17

Argh, that’s particularly frustrating since in something like ‘func foo<T : P>(t: T)’ or ‘func foo<S : Sequence>(s: S) where S.IteratorElement: P’, you’re only ever getting instances anyway since the parameter is in the input, so calling initializers or static functions isn’t something you can even do (unless you call .dynamicType, at which point you *do* have a concrete type at runtime thanks to the dynamic check).

Well, if you have ‘func foo<T : P>(t: T)’, then you can write T.someStaticMember() to call static members — it’s true you also have an instance ’t’, but you can also work directly with the type. But I suspect this is not what you meant, because:

Agh, you’re right, I’d forgotten about that. It’s days like this that I miss Objective-C’s “It just works” dynamism. :wink:

Objective-C doesn’t have an equivalent of associated types or contravariant Self, but I understand your frustration, because Sequence and Equatable are pervasive in Swift.

The other trouble is that it’s not just confusing; it can very easily get in the way of your work even if you know exactly what’s going on, necessitating kludges like AnyHashable just to do things like have a dictionary that can take more than one key type (an example that’s particularly irritating since the only method you care about, hashValue, is just a plain old Int that doesn’t care about the Self requirement at all). I know that a while ago I ended up using my own Equatable substitute with an ObjC-style isEqual() method on some types, just because actually implementing Equatable was throwing a huge spanner into the rest of the design.

Yeah, AnyHashable is basically a hand-coded existential type. It would also be possible to do something similar for Equatable, where an AnyEquatable type could return false for two values with differing concrete types, removing the need for an == with contra-variant Self parameters.

Generalized existentials eliminate the restriction and thus the hacks. On the other hand, they add yet more complexity to the language, so designing them correctly involves difficult tradeoffs.

Well, the idea was to create an easier-to-implement alternative to self-conforming protocols, which could be done if :== were expanded to one function that uses ==, and another with the same body that uses :, because I was under the impression that the compiler team did not want to implement self-conforming protocols.

I think the underlying machinery would be the same. We only want to compile the body of a generic function body, without any kind of cloning like in C++ templates, producing a general uninstantiated runtime form. So :== T requirements would effectively require self-conforming protocols anyway, since your function will have to dynamically handle both cases.

The implementation for self-conforming opaque protocols is not difficult, because the value itself can already be of any size, so it’s really not a problem to have an existential in there. In theory, someone could cook it up in a week or so.

For class protocols, I don’t know how to do it without an efficiency hit unfortunately.

Consider these two functions, taking a homogeneous and heterogeneous array of a class-bound protocol type:

protocol P : class {}

func f<T : P>(array: [T]) {} // this takes an array of pointers to T, because there’s only one witness table for all of them
func ff(array: [P]) {} // this takes an array of <T, witness table> pairs, two pointers each, because each element can be a different concrete type

What you’re saying is that f() should in fact allow both representations, because you’ll be able to call f() with a value of type [P]. Right now, if we know a generic parameter is class-constrained, we use a much more efficient representation for values of that type, that is known to be fixed size in the LLVM IR. We would have to give that up to allow class-constrained existentials to self-conform, since now a class-constrained parameter can be an existential with any number of witness tables.

There might be some trick for doing this efficiently, but I don’t know of one yet.

Of course, we can just say that class-constrained protocols never self-conform, unless they’re @objc. That seems like a hell of an esoteric restriction though (can you imagine trying to come up with a clear phrasing for *that* diagnostic?)

And if you’re wondering, the reason that @objc protocols self-conform in Swift today, is because they their existentials don’t have *any* witness tables — @objc protocol method bodies are found by looking inside the instance itself.

AnyObject is the other kind of protocol that self-conforms — you can use it both as a generic constraint, and as a concrete type bound to a generic parameter, and it ‘just works’, because again it doesn’t have a witness table.

Charles

Slava

···

On Aug 16, 2016, at 10:16 PM, Charles Srstka <cocoadev@charlessoft.com> wrote:

On Aug 16, 2016, at 11:42 PM, Slava Pestov <spestov@apple.com <mailto:spestov@apple.com>> wrote:


(Charles Srstka) #18

Argh, that’s particularly frustrating since in something like ‘func foo<T : P>(t: T)’ or ‘func foo<S : Sequence>(s: S) where S.IteratorElement: P’, you’re only ever getting instances anyway since the parameter is in the input, so calling initializers or static functions isn’t something you can even do (unless you call .dynamicType, at which point you *do* have a concrete type at runtime thanks to the dynamic check).

Well, if you have ‘func foo<T : P>(t: T)’, then you can write T.someStaticMember() to call static members — it’s true you also have an instance ’t’, but you can also work directly with the type. But I suspect this is not what you meant, because:

Agh, you’re right, I’d forgotten about that. It’s days like this that I miss Objective-C’s “It just works” dynamism. :wink:

Objective-C doesn’t have an equivalent of associated types or contravariant Self, but I understand your frustration, because Sequence and Equatable are pervasive in Swift.

I was thinking of Equatable, which in Objective-C was just the -isEqual: method on NSObject, which we usually just started with a dynamic type check in the cases where that mattered. I’m sure performance on Swift’s version is much better, but the ObjC way was refreshingly surprise-free.

The other trouble is that it’s not just confusing; it can very easily get in the way of your work even if you know exactly what’s going on, necessitating kludges like AnyHashable just to do things like have a dictionary that can take more than one key type (an example that’s particularly irritating since the only method you care about, hashValue, is just a plain old Int that doesn’t care about the Self requirement at all). I know that a while ago I ended up using my own Equatable substitute with an ObjC-style isEqual() method on some types, just because actually implementing Equatable was throwing a huge spanner into the rest of the design.

Yeah, AnyHashable is basically a hand-coded existential type. It would also be possible to do something similar for Equatable, where an AnyEquatable type could return false for two values with differing concrete types, removing the need for an == with contra-variant Self parameters.

Also: changing something into a class when it otherwise didn’t need to be one, so you can use an ObjectIdentifier as a dictionary key, because using a protocol that conformed to Hashable was dropping an atom bomb on the entire rest of the project.

Generalized existentials eliminate the restriction and thus the hacks. On the other hand, they add yet more complexity to the language, so designing them correctly involves difficult tradeoffs.

Fair enough. I guess I’ll wait it out a bit and see what the team comes up with.

Well, the idea was to create an easier-to-implement alternative to self-conforming protocols, which could be done if :== were expanded to one function that uses ==, and another with the same body that uses :, because I was under the impression that the compiler team did not want to implement self-conforming protocols.

I think the underlying machinery would be the same. We only want to compile the body of a generic function body, without any kind of cloning like in C++ templates, producing a general uninstantiated runtime form. So :== T requirements would effectively require self-conforming protocols anyway, since your function will have to dynamically handle both cases.

The implementation for self-conforming opaque protocols is not difficult, because the value itself can already be of any size, so it’s really not a problem to have an existential in there. In theory, someone could cook it up in a week or so.

For class protocols, I don’t know how to do it without an efficiency hit unfortunately.

Consider these two functions, taking a homogeneous and heterogeneous array of a class-bound protocol type:

protocol P : class {}

func f<T : P>(array: [T]) {} // this takes an array of pointers to T, because there’s only one witness table for all of them
func ff(array: [P]) {} // this takes an array of <T, witness table> pairs, two pointers each, because each element can be a different concrete type

What you’re saying is that f() should in fact allow both representations, because you’ll be able to call f() with a value of type [P]. Right now, if we know a generic parameter is class-constrained, we use a much more efficient representation for values of that type, that is known to be fixed size in the LLVM IR. We would have to give that up to allow class-constrained existentials to self-conform, since now a class-constrained parameter can be an existential with any number of witness tables.

There might be some trick for doing this efficiently, but I don’t know of one yet.

Of course, we can just say that class-constrained protocols never self-conform, unless they’re @objc. That seems like a hell of an esoteric restriction though (can you imagine trying to come up with a clear phrasing for *that* diagnostic?)

And if you’re wondering, the reason that @objc protocols self-conform in Swift today, is because they their existentials don’t have *any* witness tables — @objc protocol method bodies are found by looking inside the instance itself.

AnyObject is the other kind of protocol that self-conforms — you can use it both as a generic constraint, and as a concrete type bound to a generic parameter, and it ‘just works’, because again it doesn’t have a witness table.

Ah… because of the static dispatch, mapping the protocol members to address offsets which may vary from member to member, as opposed to @objc protocols, which I’d guess are probably doing the old-school lookup by selector name à la objc_msgSend(). Hmm. I’d still probably argue that it’s worth it, because I get the impression that Apple prefers the use of generic sequence and collections for parameters rather than hard-coding arrays, and frankly, with the current behavior it is slightly difficult to do that. I guess it’s up to the compiler team, though.

I will say that this has been an interesting discussion. Thanks for offering your knowledge and insight.

Charles

···

On Aug 17, 2016, at 12:35 AM, Slava Pestov <spestov@apple.com> wrote:

On Aug 16, 2016, at 10:16 PM, Charles Srstka <cocoadev@charlessoft.com <mailto:cocoadev@charlessoft.com>> wrote:

On Aug 16, 2016, at 11:42 PM, Slava Pestov <spestov@apple.com <mailto:spestov@apple.com>> wrote:


(Karl) #19

Any proposal that expands the power of generic programming gets an almost automatic +1 from me.

I can't think of any circumstances in which I wouldn't want to use ":==" instead of ":". Are there any downsides to expanding ":" to mean what ":==" does?

Incidentally, I kinda thought things either already worked like this, or would work like this after generics were "completed", but I can't tell you why I thought that.

Me neither, but the last time I proposed that, people stated that there were some cases where this could not work. No concrete examples were given, but I assume it probably has something to do with associated type wackiness. :== seems like a workable compromise to me.

If an existential of a protocol P doesn't conform to itself, what can you do inside the body of a generic function that has a generic constraint specified with `:==`? In other words, what would we know about what's in common between such an existential of a protocol and types that conform to the protocol?

My proposal is that in such cases, using :== would lead to a compiler error.

Charles

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

I think the point is that existentials not conforming to their protocols is the underlying reason this doesn’t work already.

From the previous thread:

There are a couple of reasons this is the case. IIRC in some cases it actually isn't possible for the existential to conform to the protocol in a sound way. And even when it is possible, I believe it has been said that it is more difficult to implement than you might think. Hopefully the situation will improve in the future but I'm not aware of any specific plans at the moment.

It seems like a reasonably straightforward axiom. I would be interested to learn more about those edge-cases.

Karl

···

On 17 Aug 2016, at 00:34, Charles Srstka via swift-evolution <swift-evolution@swift.org> wrote:

On Aug 16, 2016, at 5:30 PM, Xiaodi Wu <xiaodi.wu@gmail.com <mailto:xiaodi.wu@gmail.com>> wrote:
On Tue, Aug 16, 2016 at 5:19 PM, Charles Srstka via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

On Aug 16, 2016, at 5:13 PM, David Sweeris <davesweeris@mac.com <mailto:davesweeris@mac.com>> wrote:


(Slava Pestov) #20

Any proposal that expands the power of generic programming gets an almost automatic +1 from me.

I can't think of any circumstances in which I wouldn't want to use ":==" instead of ":". Are there any downsides to expanding ":" to mean what ":==" does?

Incidentally, I kinda thought things either already worked like this, or would work like this after generics were "completed", but I can't tell you why I thought that.

Me neither, but the last time I proposed that, people stated that there were some cases where this could not work. No concrete examples were given, but I assume it probably has something to do with associated type wackiness. :== seems like a workable compromise to me.

If an existential of a protocol P doesn't conform to itself, what can you do inside the body of a generic function that has a generic constraint specified with `:==`? In other words, what would we know about what's in common between such an existential of a protocol and types that conform to the protocol?

My proposal is that in such cases, using :== would lead to a compiler error.

Charles

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

I think the point is that existentials not conforming to their protocols is the underlying reason this doesn’t work already.

From the previous thread:

There are a couple of reasons this is the case. IIRC in some cases it actually isn't possible for the existential to conform to the protocol in a sound way. And even when it is possible, I believe it has been said that it is more difficult to implement than you might think. Hopefully the situation will improve in the future but I'm not aware of any specific plans at the moment.

It seems like a reasonably straightforward axiom. I would be interested to learn more about those edge-cases.

Hmm, re-reading that makes me worry about this proposal at a practical level. IIUC, this is something that is pretty much desired across the board, and if we could have it for `:` it'd be best.
But, it sounds like the reason `:` doesn't work that way isn't that the core team has a different opinion, but rather that it's very difficult to implement. And, IIUC, the situation is that no protocol existential currently conforms to itself, not that some do and some don't. The implementation work wouldn't be any easier if we called the operator `:==`...

There are various ways to work around the problem using a new operator, though, depending on how much work you wanted to do in implementing it. At the very least you could take the ‘preprocessor’ approach and turn one function using :== into two separate functions, one using == and one using :, with both functions sharing the same body. This would still have the code bloat in the binary, but at least it wouldn’t be bloating up the source. We could then solve some of the binary bloat by spinning off the function body into a third function and having both the two original functions call that. Or maybe we could have the : variant reinterpret the sequence as an == sequence and send it to the == variant. There are multiple ways that this could be handled without forcing protocols to conform to themselves.

Not an expert, but wouldn't this blow up a whole bunch of compile-time "stuff" like the type checker? If no protocol existential conforms to itself, and it's unknown to the compiler whether it's even theoretically possible for a particular protocol, then what's to say what the body of a function that uses this constraint should be able to do?

What happens if you try to do that by hand?

func foo<Foo: Sequence>(bar: Foo) where Foo.Iterator.Element == MyProto {
    for eachFoo in bar {
        eachFoo.baz()
    }
}

func foo<Foo: Sequence>(bar: Foo) where Foo.Iterator.Element: MyProto {
    for eachFoo in bar {
        eachFoo.baz()
    }
}

Answer: If either Element == MyProto or Element: MyProto can’t handle the baz() method, it’ll throw a compiler error.

Generating the above code via a preprocessor would get the same result. :== would only compile if the body worked with both == and with :.

I don’t think it’s reasonable to specify language features as requiring a pre-processor for implementation. It would break a lot of things in the language design, and mental model.

···

On Aug 16, 2016, at 6:05 PM, Charles Srstka via swift-evolution <swift-evolution@swift.org> wrote:

On Aug 16, 2016, at 7:48 PM, Xiaodi Wu <xiaodi.wu@gmail.com <mailto:xiaodi.wu@gmail.com>> wrote:
On Tue, Aug 16, 2016 at 7:43 PM, Charles Srstka <cocoadev@charlessoft.com <mailto:cocoadev@charlessoft.com>> wrote:

On Aug 16, 2016, at 7:08 PM, Xiaodi Wu <xiaodi.wu@gmail.com <mailto:xiaodi.wu@gmail.com>> wrote:
On Tue, Aug 16, 2016 at 6:59 PM, Karl <razielim@gmail.com <mailto:razielim@gmail.com>> wrote:

On 17 Aug 2016, at 00:34, Charles Srstka via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

On Aug 16, 2016, at 5:30 PM, Xiaodi Wu <xiaodi.wu@gmail.com <mailto:xiaodi.wu@gmail.com>> wrote:
On Tue, Aug 16, 2016 at 5:19 PM, Charles Srstka via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

On Aug 16, 2016, at 5:13 PM, David Sweeris <davesweeris@mac.com <mailto:davesweeris@mac.com>> wrote:

Charles

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