[swift-evolution] Make generics covariant and add generics to protocols

Howard Lovatt howard.lovatt at gmail.com
Wed Jan 13 01:22:20 CST 2016


@Austin,

I don't see a problem with the collections in general, that's why I chose
`Box` as an example - the smallest possible collection!

Is this what you had in mind?

//: Use a Box as an example of a minimal collection, a colection of exactly
one value!


//: - note:

//: In earlier examples I used the generic type name as the feild name
directly, in practice you need a unique name.

//: I would propose TypeName.GenericName for the unique name?

//: In examples below I have used TypeNameGenericName as the nearest
approximation possible at present.

//: I chose upper case, but maybe lower case better?

//: Maybe the syntax without a . is good enough?


//:     protocol Boxable<T> { var value: T { get set } }

protocol Boxable {

    var BoxableT: Any.Type { get }

    var value: Any { get set }

}


//:     protocol Generatable<T> { var generator: Generator<T> { get } }

protocol Generatable {

    var GeneratableT: Any.Type { get }

    var generator: Generator { get }

}


//:     struct Box<T>: Boxable<T>, Generatable<T> {

//:         var value: T

//:         var generator: Generator<T> { return BoxGenerator(box: self) }

//:     }

struct Box: Boxable, Generatable {

    let BoxT: Any.Type // Box only has one 'real' generic type BoxT

    var BoxableT: Any.Type { // BoxableT declared as same as BoxT
(Boxable<T>)

        return BoxT

    }

    var GeneratableT: Any.Type { // GeneratableT declared as same as BoxT
(Generatable<T>)

        return BoxT

    }



    private var _value: Any

    var value: Any {

        get {

            return _value

        }

        set {

            precondition(BoxT == /* >= */ newValue.dynamicType, "Type of
newValue, \(newValue.dynamicType), is not a sub-type of generic type BoxT, \
(BoxT)")

            _value = newValue

        }

    }



    var generator: Generator {

        return BoxGenerator(BoxT, box: self)

    }



    // Generated from `init(_ initialValue: T)` and noting that `T`'s upper
bound is `AnyObject`.

    init(_ lowestCommonDeclaredT: Any.Type, value: Any) {

        BoxT = lowestCommonDeclaredT

        _value = value

    }

}


//:     protocol Generator<T> { var next: T? { get } }

protocol Generator {

    var GeneratorT: Any.Type { get }

    var next: Any? { get }

}


//:     class BoxGenerator<T>: Generator<T> {

//:         private var isFinished = false

//:         private let box: Box<t>

//:         var next: T? {

//:             if isFinished { return nil }

//:             isFinished = true

//:             return box.value

//:         }

//:         init(box: Box<T>) {

//:             self.box = box

//:         }

//:     }

class BoxGenerator: Generator {

    let BoxGeneratorT: Any.Type

    var GeneratorT: Any.Type {

        return BoxGeneratorT

    }

    private var isFinished = false

    private let box: Box

    var next: Any? {

        if isFinished { return nil }

        isFinished = true

        return box.value

    }

    init(_ lowestCommonDeclaredT: Any.Type, box: Box) {

        self.BoxGeneratorT = lowestCommonDeclaredT

        self.box = box

    }

}


//:     let ints = Box(value: 1)

let ints = Box(Int.self, value: 1) // Box<Int>, compiler determins declared
type

sizeofValue(ints) // 40

let intsGen = ints.generator // BoxGenerator<Int>

sizeofValue(intsGen) // 40

intsGen.next as! Int? // 1, compiler adds cast

intsGen.next as! Int? // nil, compiler adds cast


Do you have something else in mind? Happy to take a look at *short*
examples?

 -- Howard.

On 13 January 2016 at 12:37, Austin Zheng <austinzheng at gmail.com> wrote:

> I posted this in your original thread; I am strongly against the notion
> that slightly prettier code is worth making the type system unsound, nor is
> it worth the performance hit from the necessary runtime checks (even if
> some fraction of them can be optimized out by the compiler).
>
> In terms of getting rid of associated types, I think that any such
> proposal should also include a description of how SequenceType is to be
> rewritten using the new system, both in terms of implementation as well as
> usage in APIs.
>
> Austin
>
> On Tue, Jan 12, 2016 at 5:31 PM, Howard Lovatt <howard.lovatt at gmail.com>
> wrote:
>
>> @Jordan & Austin,
>>
>> You raise two issues covariance and overhead of generic protocols instead
>> of associated types in protocols.
>>
>> Having used opt in covariance in other languages, Java & Scala, I am not
>> a fan. You end up littering all your code with a covariance annotation.
>> Just look at any Java or Scala code, look at their libraries. Also when Sun
>> ran there project coin, vaguely similar to swift-evolution, there was a ton
>> of correspondence saying that people wanted covariance by default. The
>> official answer from Oracle was that they wished they had made covariance
>> the default but it was now too late to change; therefore there is strong
>> presidency for covariance by default.
>>
>> There is some overhead with the approach I suggested, however I think
>> that the compiler can eliminate it. I will use the measure `sizeofValue` as
>> a proxy for any type of overhead (space or time). I chose this because it
>> is easy and because it is likely to be true that if `sizeofValue` return
>> the same size then the overhead is likely the same. Consider a `Boxable`
>> protocol and then an `Int` specialisation of that protocol.
>>
>> User writes:
>>
>>     protocol Boxable<T> {
>>
>>         var value: Any { get set }
>>
>>     }
>>
>> This gets translated, as per proposal, into:
>>
>>     // Size test for a generic protocol and generic struct as per
>> proposal and optimisation
>>
>>     protocol Boxable { // User would write `protocol Boxable<T> { var
>> value: T { get set } }`.
>>
>>         var T: Any.Type { get }
>>
>>         var value: Any { get set }
>>
>>     }
>>
>>
>> Then the user wants an `Int` specialisation:
>>
>>     struct BoxInt: Boxable<T> {
>>
>>         var value: Int
>>
>>     }
>>
>>
>> This gets translated, as per proposal, into:
>>
>>     struct BoxInt: Boxable { // User would write `struct BoxInt:
>> Boxable<Int> { var value: Int }`.
>>
>>         // No need for a stored property becuse `Int` is a struct and
>> cannot be sub-classed.
>>
>>         var T: Any.Type { // Compiler generated, user would not write
>> anything
>>
>>             return Int.self
>>
>>         }
>>
>>
>>
>>         var _value: Any // From user written `var value: Int`.
>>
>>         var value: Any {
>>
>>             get {
>>
>>                 return _value
>>
>>             }
>>
>>             set {
>>
>>                 precondition(newValue is Int, "Type of newValue, \(
>> newValue.dynamicType), is not \(Int.self)")
>>
>>                 _value = newValue
>>
>>             }
>>
>>         }
>>
>>
>>
>>         // No need for `lowestCommonDeclaredT` arg becuse `Int` is a
>> struct and cannot be sub-classed.
>>
>>         init(value: Any) { // Compiler generated, user would not write
>> anything
>>
>>             _value = value
>>
>>         }
>>
>>     }
>>
>>
>> There is some overhead:
>>
>>
>>     let bI = BoxInt(value: 1)
>>
>>     sizeofValue(bI) // 32, i.e. `BoxInt (due to `value: Any`) has
>> overhead since an `Int` size is 8
>>
>>     let boxable: Boxable = bI
>>
>>     sizeofValue(boxable) // 40, i.e. generic protocol has same overhead
>> as non-generic protocol
>>
>>
>> Encouragingly, once you type as a protocol, whether the protocol is a
>> proposed generic protocol or a non-generic protocol the overhead in the
>> same. However `BoxInt` is certainly more overhead than `Int`.
>>
>> Fortunately the compiler can optimise it away:
>>
>>
>>     struct NonGenericBoxInt { // Also generated from `struct BoxInt:
>> Boxable<Int> { var value: Int }`
>>
>>         var value: Int
>>
>>         var toBoxInt: BoxInt {
>>
>>             return BoxInt(value: value)
>>
>>         }
>>
>>     }
>>
>>
>>     let nGBI = NonGenericBoxInt(value: 1)
>>
>>     sizeofValue(nGBI) // 8, i.e. `NonGenericBoxInt has zero overhead
>>
>> When the user writes `BoxInt` the compiler substitutes `NonGenericBoxInt`
>> and when the user covariantly assigns to the protocol `Boxable` the
>> compiler calls `toBoxInt`.
>>
>> Therefore the original proposal could be extended to include this
>> optimisation.
>>
>> Hopefully therefore this `efficiency` question is addressed?
>>
>> Thanks for the feedback,
>>
>>   -- Howard.
>>
>> On 13 January 2016 at 05:19, Jordan Rose <jordan_rose at apple.com> wrote:
>>
>>> Agreed on both counts. Generics are more familiar but don't actually
>>> cover the use cases where the associated type is *not* independent of
>>> the model object (like a Sequence's Generator or a Collection's Index).
>>> Dropping that information results in a lot of extra indirection at runtime,
>>> which we don't want.
>>>
>>> Jordan
>>>
>>>
>>> On Jan 12, 2016, at 8:17, Austin Zheng via swift-evolution <
>>> swift-evolution at swift.org> wrote:
>>>
>>> Strong -1, covariance on generics should be explicitly opt-in. Also -1
>>> on generics replacing associated types in protocols.
>>>
>>> Austin
>>>
>>> On Jan 12, 2016, at 1:45 AM, Howard Lovatt via swift-evolution <
>>> swift-evolution at swift.org> wrote:
>>>
>>> Currently you generics are invariant whereas function arguments etc. are
>>> covariant. I am suggesting that if the way generics are implemented is
>>> changed then they can be made covariant and that this will add considerable
>>> utility to Swift generics.
>>>
>>> 1st a demonstration of the current situation of invariant generics:
>>>
>>>     // Current system
>>>     class Top {}
>>>     class Bottom: Top {}
>>>
>>>     struct Box<T: AnyObject> {
>>>         var value: T
>>>         init(_ initialValue: T) {
>>>             value = initialValue;
>>>         }
>>>     }
>>>
>>>     let boxB = Box(Bottom())
>>>     // let boxT: Box<Top> = boxB // Covariance currently not allowed
>>>
>>> The key point is although `Bottom` 'is a’ `Top`, `Box<Bottom>` *is not*
>>> a `Box<Top>`.
>>>
>>> I am suggesting:
>>>
>>> 1. That `Box<Bottom>` should be a `Box<Top>` (covariance).
>>> 2. An implementation that allows the above covariance.
>>> 3. That protocols are made generic, i.e. `protocol Box<T> { var value: T
>>> { get set } }` and that this mechanism replaces associated types for
>>> protocols.
>>>
>>>     // Proposal:
>>>     // 1. No change to Box, i.e. programmer would just write Box as
>>> before
>>>     // 2. Code transformed by comiler with write check for each
>>> specific, generic type instance
>>>     // Best approximation of resulting code in current Swift to
>>> demonstrate spirit of idea:
>>>
>>>     // Compiler writes a universal form using the upper bound (it
>>> writes the underlyting representation).
>>>     // In practice this would be called `Box` but used `BoxAnyObject`
>>> to indicate that it has a generic argument bounded by `AnyObject`.
>>>     struct BoxAnyObject {
>>>         // Generated from generic argument `<T: AnyObject>`.
>>>         let T: AnyObject.Type // Store the actual type.
>>>
>>>         // Generated from stored property `var value: T` and noting
>>> that `T`'s upper bound is `AnyObject`.
>>>         private var _value: AnyObject // Access the stored property
>>> through a setter so that type can be checked
>>>         var value: AnyObject {
>>>             get {
>>>                 return _value
>>>             }
>>>             set {
>>>                 // In all functions check that args declared as `T` are
>>> actually a `T` or a sub-type.
>>>                 // Note: `is` only works with type literal and there is
>>> no `>=` operator for types :(.
>>>                 // `is` would need changing or `>=` for types adding,
>>> nearest at moment `==`.
>>>                 precondition(T == /* >= */ newValue.dynamicType, "Type
>>> of newValue, \(newValue.dynamicType), is not a sub-type of generic type
>>> T, \(T)")
>>>                 _value = newValue
>>>             }
>>>         }
>>>
>>>         // Generated from `init(_ initialValue: T)` and noting that
>>> `T`'s upper bound is `AnyObject`.
>>>         init(_ lowestCommonDeclaredT: AnyObject.Type, _ initialValue:
>>> AnyObject) {
>>>             T = lowestCommonDeclaredT
>>>             _value = initialValue
>>>         }
>>>     }
>>>
>>>     // Demonstrate that all `Box`es are the same size and therefore can
>>> be bitwise copied
>>>     // Compiler supplies lowest-common, declared, generic type for all
>>> the `T`s in the `init` call.
>>>     var bT = BoxAnyObject(Top.self, Top()) // In practice user would
>>> write `let bT = Box(Top())`.
>>>     bT.T // Top.Type
>>>     sizeofValue(bT) // 16
>>>
>>>     var bB = BoxAnyObject(Bottom.self, Bottom()) // In practice user
>>> would write `let bB = Box(Bottom())`.
>>>     bB.T // Bottom.Type
>>>     sizeofValue(bB) // 16
>>>
>>>     // Demonstration covariance.
>>>     bT = bB // Compiler would check covariance of declared generic
>>> types.
>>>     bT.T // Bottom.Type
>>>
>>>     // Demonstrate generic returned type
>>>     // Compiler would add cast to declared, generic type.
>>>     bB.value as! Bottom // In practice user would write `bB.value`.
>>>
>>>     // Demonstrate type safety
>>>     bT = BoxAnyObject(Top.self, Top()) // In practice user would write
>>> `bT = Box(Top())`.
>>>     bT.value = Top() // OK
>>>     // bT.value = Bottom() // Doesn't work at present because need `>=`
>>> for types, but would work in practice
>>>     // bB.value = Top() // Runtime error - wrong type
>>>
>>> The implications of this proposal are:
>>>
>>> 1. The compiler can statically type check a read from a stored property.
>>> 2. A write to a stored property is type checked at runtime.
>>> 3. Protocols can be made generic instead of having an associated type
>>> and then they become a proper type with dynamic dispatch.
>>> 4. Generic protocols can be a type just like non-generic protocols,
>>> structs, and classes and unlike associated type protocols that can only be
>>> a generic constraint.
>>> 5. The awkwardness of dealing with associated type generics is replaced
>>> by a more powerful and easier to understand semantic of a type, just like
>>> the other types.
>>> 6. There is a lot of ‘non-obvoius’, long code, for example `inits`, that
>>> use a `where` clause to constrain an associated type protocol, this would
>>> be unnecessary.
>>> 7. There are whole types, `AnySequence`, `AnyGenerator`, etc., that
>>> would be replaced by a generic protocols, `Sequence`, `Generator`, etc.
>>>
>>> Advantages:
>>>
>>> 1. Covariant generics are a powerful addition to the language.
>>> 2. Generics’ invariance are inconsistent with the rest of the language.
>>> 3. Generic protocols would become a ‘proper’ type and you could have
>>> arrays and fields of a generic protocol.
>>> 4. There are many threads on swift-evolution looking at how protocols
>>> can be made into a ‘proper’ type or at least a concept that is easier to
>>> understand.
>>>
>>> Compatibility:
>>>
>>> 1. This would be a major change since associated types in protocols
>>> would be replaced by generics.
>>> 2. The new implementation of generics might break some existing `struct`
>>> and `class` code, for example if it is dependent on the exact size of an
>>> object because the class will have extra fields, one for each generic type,
>>> and therefore will be larger.
>>>
>>> Disadvantages:
>>>
>>> 1. Major change.
>>> 2. Object size increases.
>>>
>>> Thanks in advance for any comments,
>>>
>>>   — Howard.
>>>
>>> PS This is part of a collection of proposals previously presented as
>>> “Protocols on Steroids”.
>>>
>>> _______________________________________________
>>> swift-evolution mailing list
>>> swift-evolution at swift.org
>>> https://lists.swift.org/mailman/listinfo/swift-evolution
>>>
>>>
>>>  _______________________________________________
>>> swift-evolution mailing list
>>> swift-evolution at swift.org
>>> https://lists.swift.org/mailman/listinfo/swift-evolution
>>>
>>>
>>>
>>
>>
>> --
>>   -- Howard.
>>
>
>


-- 
  -- Howard.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20160113/287d5346/attachment.html>


More information about the swift-evolution mailing list