Covariance and Contravariance


(Simon Pilkington) #1

Hi,

Is providing Covariance and Contravariance[1] of generics going to be part of the work on generics for Swift 3? I am sure this topic has come up within the core team and I was wondering what their opinion on the topic was.

I can see this as beneficial as it would allow the compiler - in conjunction with type inference - to retain more type information and hence allow code be more type safe. For example -

class ConcreteClass<GenType : GenericType> {
    ...
    
    func getFunction() -> GenType {
        ...
    }
    
    func putFunction(input: GenType) -> Bool {
        return ...
    }
    
}

protocol GenericType {
    ...
}

class GenericType1 : GenericType {
    ...
}

class GenericType2 : GenericType {
    ...
}

let array = [ConcreteClass<GenericType2>(...), ConcreteClass<GenericType1>(...)]

let x : GenericType = array[0].getFunction() // this would compile as array would be of type ConcreteClass<types that extend GenericType>
                      // currently array is of type AnyObject so this line doesn’t compile
array[0].putFunction(…) // this would still not compile as it would break type guarantees

As a downside I can see it as making generics more complex and difficult to understand. On balance I think probably the benefit in improved type safety is worth it but I was interested in what others thought.

Cheers,
Simon

[1] https://dzone.com/articles/covariance-and-contravariance


What is a covariant generalization?
(John McCall) #2

One challenge here is that subtyping in Swift doesn’t mean equivalence of representation. For example, Int is a subtype of Int?, but the later requires extra space to store in memory. So while it would make sense to allow, say, [Int] to be a subtype of [Int?], the actual conversion at runtime wouldn’t be trivial — we’d either need to eagerly apply the element-wise transform, or Array would need some ability to apply it lazily. Both come with fairly serious performance costs.

John.

···

On Dec 8, 2015, at 11:47 PM, Simon Pilkington via swift-evolution <swift-evolution@swift.org> wrote:

Hi,

Is providing Covariance and Contravariance[1] of generics going to be part of the work on generics for Swift 3? I am sure this topic has come up within the core team and I was wondering what their opinion on the topic was.

I can see this as beneficial as it would allow the compiler - in conjunction with type inference - to retain more type information and hence allow code be more type safe. For example -

class ConcreteClass<GenType : GenericType> {
    ...
    
    func getFunction() -> GenType {
        ...
    }
    
    func putFunction(input: GenType) -> Bool {
        return ...
    }
    
}

protocol GenericType {
    ...
}

class GenericType1 : GenericType {
    ...
}

class GenericType2 : GenericType {
    ...
}

let array = [ConcreteClass<GenericType2>(...), ConcreteClass<GenericType1>(...)]

let x : GenericType = array[0].getFunction() // this would compile as array would be of type ConcreteClass<types that extend GenericType>
                      // currently array is of type AnyObject so this line doesn’t compile
array[0].putFunction(…) // this would still not compile as it would break type guarantees

As a downside I can see it as making generics more complex and difficult to understand. On balance I think probably the benefit in improved type safety is worth it but I was interested in what others thought.


(Joe Groff) #3

Another thing that makes covariance in Swift interesting compared to other OO languages is value semantics. Mutation operations on value types like Array and Dictionary can be safely covariant, whereas this is unsafe in Java or C#. This is great for expressivity, but it means that a generalized covariance proposal needs to do some legwork to decide what operations exactly can be safely covariant, and how far the compiler can verify that. I haven't thought extensively about this, but it seems potentially complex.

-Joe

···

On Dec 9, 2015, at 12:04 AM, John McCall via swift-evolution <swift-evolution@swift.org> wrote:

On Dec 8, 2015, at 11:47 PM, Simon Pilkington via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

Hi,

Is providing Covariance and Contravariance[1] of generics going to be part of the work on generics for Swift 3? I am sure this topic has come up within the core team and I was wondering what their opinion on the topic was.

I can see this as beneficial as it would allow the compiler - in conjunction with type inference - to retain more type information and hence allow code be more type safe. For example -

class ConcreteClass<GenType : GenericType> {
    ...
    
    func getFunction() -> GenType {
        ...
    }
    
    func putFunction(input: GenType) -> Bool {
        return ...
    }
    
}

protocol GenericType {
    ...
}

class GenericType1 : GenericType {
    ...
}

class GenericType2 : GenericType {
    ...
}

let array = [ConcreteClass<GenericType2>(...), ConcreteClass<GenericType1>(...)]

let x : GenericType = array[0].getFunction() // this would compile as array would be of type ConcreteClass<types that extend GenericType>
                      // currently array is of type AnyObject so this line doesn’t compile
array[0].putFunction(…) // this would still not compile as it would break type guarantees

As a downside I can see it as making generics more complex and difficult to understand. On balance I think probably the benefit in improved type safety is worth it but I was interested in what others thought.

One challenge here is that subtyping in Swift doesn’t mean equivalence of representation. For example, Int is a subtype of Int?, but the later requires extra space to store in memory. So while it would make sense to allow, say, [Int] to be a subtype of [Int?], the actual conversion at runtime wouldn’t be trivial — we’d either need to eagerly apply the element-wise transform, or Array would need some ability to apply it lazily. Both come with fairly serious performance costs.


(André Videla) #4

I’m curious, what does that mean?
In my experience," Int <: Int?" means Int can be used when "Int?" is expected.
Imagine this scenario:

class A {}
class B {}
class C : A {}
class D : B {}

func processDict(d: [C : B]) {}

let dict1 = [C: B]()
let dict2 = [A: D]() //dict 2 <: dict1
processDict(dict1)
processDict(dict2)

I get a type error when it should type check. Because it is safe to output D wherever I expect a B and It is safe to use A whenever I need to input a C.

About your example on covariant arrays: Variance on arrays depends on if they are read only or read and write.
Read and write arrays need to be invariant to be safe. But read-only arrays can be covariant. If the compiler can make this distinction, it seem reasonable to assume it can eagerly do the transformation at no runtime cost.

- André

···

On 09 Dec 2015, at 09:04, John McCall via swift-evolution <swift-evolution@swift.org> wrote:

One challenge here is that subtyping in Swift doesn’t mean equivalence of representation.


(Michel Fortin) #5

But the compiler already lets you use a [Derived] as a [Base?], as long as the representation is the same. It'd be nice if that could apply with generics too, even if the limitation was that it would work only as long as there is no difference in representation.

If you want the restriction to depend a little less on low-level representation details, allow it only for class pointers. You won't have any representation problem there. This is also where people will expect it the most.

···

Le 9 déc. 2015 à 3:04, John McCall via swift-evolution <swift-evolution@swift.org> a écrit :

One challenge here is that subtyping in Swift doesn’t mean equivalence of representation. For example, Int is a subtype of Int?, but the later requires extra space to store in memory. So while it would make sense to allow, say, [Int] to be a subtype of [Int?], the actual conversion at runtime wouldn’t be trivial — we’d either need to eagerly apply the element-wise transform, or Array would need some ability to apply it lazily. Both come with fairly serious performance costs.

--
Michel Fortin
michel.fortin@michelf.ca
https://michelf.ca


(John McCall) #6

One challenge here is that subtyping in Swift doesn’t mean equivalence of representation. For example, Int is a subtype of Int?, but the later requires extra space to store in memory. So while it would make sense to allow, say, [Int] to be a subtype of [Int?], the actual conversion at runtime wouldn’t be trivial — we’d either need to eagerly apply the element-wise transform, or Array would need some ability to apply it lazily. Both come with fairly serious performance costs.

But the compiler already lets you use a [Derived] as a [Base?], as long as the representation is the same. It'd be nice if that could apply with generics too, even if the limitation was that it would work only as long as there is no difference in representation.

I was using Array as an example of a generic type, but I’d forgotten that we already had the subtyping rule in place as a special case there.

If you want the restriction to depend a little less on low-level representation details, allow it only for class pointers. You won't have any representation problem there. This is also where people will expect it the most.

I’d rather we not design a general-purpose language mechanism that’s only actually useful for class pointers, especially given the importance of value types in the language.

John.

···

On Dec 9, 2015, at 11:50 AM, Michel Fortin <michel.fortin@michelf.ca> wrote:
Le 9 déc. 2015 à 3:04, John McCall via swift-evolution <swift-evolution@swift.org> a écrit :