[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