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

[Austin Zheng]

Hi Howard,

> On Jan 13, 2016, at 8:35 PM, Howard Lovatt <howard.lovatt at gmail.com> wrote:
> 
> @ Austin,
> 
> Comments inline below.
> 
> On 14 January 2016 at 10:02, Austin Zheng <austinzheng at gmail.com <mailto:austinzheng at gmail.com>> wrote:
> Hi Howard,
> 
> Making generics covariant by default would add even more of a burden to users. They would need to check the type property of a generic object any time they wanted to mutate that generic object or risk their program terminating.
> 
> Its a matter of balance, is that checking necessary. You certainly don't see it with Java arrays and this isn't a problem in practice. If you burden everyone with an annotation and in real programs that imperceptibly reduces the number of error then it was a bad call. The Java use case indicates that it is a bad call.

I don't agree. Java Lists are generic and invariant; AFAICT they are preferred over arrays in many cases except when primitives are being stored et al. I suspect this is why the number of errors is "imperceptible" (if it actually is; is there any data on the subject?), because people are using the (sound) abstraction.
 
> 
> I don't think the fact that array accesses are checked at runtime is a good example:
> 
> 1. The Swift team has stated that subscripting into an array returns a non-optional at least in part because of performance issues. (Unfortunately, I think this was mentioned on the old Apple developer forums, which are now inaccessible, so don't take my word for it until someone with more insight says so one way or another :).
> 
> What about write to an array, you still have to check bounds. An optional won't help.

I don't think it's relevant. Checking the bounds before writing to an array is still trivial.

>  
> 2. The fact that this specific aspect of Swift is checked at runtime doesn't provide insight as to whether or not another aspect of Swift should be compile-time or runtime-checked; it just indicates that there exists the possibility of some checks being done at runtime (and every mainstream statically typed language performs runtime checks to some extent, this isn't a novel conclusion).
> 
> Yes it says that they are making pragmatic choices, the designers will be well aware of type systems that check array bounds but chose, in my opinion correctly, to go down the path of a runtime check for reasons of practicality. The dependant type system or similar does not pay for itself in terms of improved programmer productivity and application reliability.

Dependent types have nothing to do with this; the point of the Swift array is to model a collection of items whose size is not known at compile-time and therefore must be checked at runtime. This is distinct from a fixed-length array or some other type of construct where the size and/or bounds are known at compile time and can reasonably be checked then.

>  
> 3. Checking that an array access is in bounds is trivial from a conceptual standpoint. The index needs to be at least 0 and at most the length of the array - 1.
> 
> Type checking is equally trivial and can often be optimised away.

No it's not. Maybe if you think your type is a bottom type you can reason away the type checks. But if your bottom type is a protocol or non-final class, and code in a dependency inherits from that class or protocol, suddenly code you thought was sound might start breaking. This is a far cry from a binary 'nil or not nil' type of check.

>  
> 4. The length of a Swift array is not part of the type contract, whereas the type enclosed within a generic type is. Swift doesn't have fixed-length arrays.
> 
> Well it isn't in Swift, but in some languages it is. Proponents of these languages would point to a matrix math API and note how the compiler can check matrix size for conformance at compile time. Whereas in Swift that is a runtime check. The proponents would point to the inefficiency of runtime checking and the fact that you now need to test the code. I think the Swift team have taken the right approach and are saying typing the size of an array is not worth it.

There's a discussion going on right now about what it would take to add compile-time dimensional analysis to the language. Engineers have expressed interest in things like fixed-length arrays and non-type generic parameters to support exactly such a use case. I wouldn't read too much into what the current capabilities and limitations of Array mean and don't mean in terms of Swift's future design, although a core team member is free to pop in and clear things up again :).

> 
> 
> I think a proposal to get rid of optionals and non-nullable types would be a better analogy. Here is a comparison to that hypothetical proposal:
> 
> 1. The most popular objection to Swift's optional system seems to be either clutter (from the ?, ! sigils) and ease of use. (Your proposal cites the ugliness of variance annotations in other languages as a primary motivation.)
> 
> Not really, you are not comparing like with like. If Swift didn't have explicit optionals it would most likely have implicit optionals like Obj-C and Java. IE everything is an optional. I like Swift's solution since most things aren't actually optional and therefore overall it reduces the burden on the programmer (in other systems you are continuously testing for nil). In terms of variance for generics if there were a method of giving static type checking without burdening the programmer with annotations then I would be in favour (unfortunately I do not know of such a system).

The whole point is that declarations of optionality at the definition site are analogous to declarations of variance at the definition site (rather than checking at the use site). In Swift's system every single variable, property, parameter, return type needs to be annotated with whether or not it is nullable. If annotating variance is a burden but annotating nullability isn't then we probably have two fundamentally incompatible ideas of what burdensomeness entails.

>  
> 2. Removing the optional system would result in moving a compile-time check to a run-time check. (Your proposal states that the burden of ensuring the access is valid lies at the use site, which introduces the possibility of runtime failures that cannot be currently expressed.)
> 
> No it would most likely mean that there were nil checks everywhere, just like Java and to some extent Obj-C. IE an overall increase in programmer burden.

Yes, and the argument is that I shouldn't have to worry about whether one of my Foo<Bar>s is actually a Foo<Bar> or a Foo<Baz> that will crash my program if I don't explicitly check and guess wrong, because the language's variance rules allow two incompatible kinds of objects to be represented by the same type. Just like I shouldn't have to worry about whether or not my Qux instance is actually a Qux or a null pointer because the language's optionality rules allow two incompatible kinds of objects to be represented by the same type, and I didn't explicitly check and guessed wrong.

>  
> 3. Removing optionals would keep the language type-safe, as an exception would occur whenever calling a method on nil occurred at runtime (your proposal also keeps the language type-safe, in the formal sense). 
> 
> Yes. Whether you have explicit optionals or implicit optionals it is still type safe.
>  
> 4. The possibility of a run-time check failing and terminating the program with an NPE can be mitigated by user code performing an explicit check for nil at the use site. (Your proposal would require user code to check against the metatype property whenever a generic type is mutated to ensure that no preconditions can fail.)
> 
> Yes, you see a lot of that for implicit optionals. But tellingly not for Java arrays. Therefore the decision as to whether a type check should be static or dynamic should be based on the use case. You cannot simply say that everything should be static, it places enormous burden on the programmer. People do say that everything should be dynamic though! Myself, I think static is good if it is easy to do.
> 
> In practice you don't see runtime type checking in Java array code, therefore I don't think there is any evidence to suggest you would in Swift. Why would the two be different? Therefore I think runtime type errors due to incorrect writes to Java generics would not be a problem in practice.

Nobody is saying that everything should be static, that is a straw man. There is a perfectly good solution, which is to expose whatever mechanism Swift uses to internally mark things like Array<T> as covariant, and leave the default as invariant, which gives you both the flexibility of user-defined variance and the safety that Swift has right now. Whether or not something is covariant or contravariant rather than invariant should depend entirely on its semantics.

>  
> 5. Removing the optional system would cause the type system to be more imprecise, since a variable of type T would contain either an instance of T or nil. (Your proposal would cause the type system to be more imprecise, since a T<U> might actually be a T<V>, where V is a subtype of U, in a context where V cannot substitute for U.)
> 
> Sure, but for optionals that is a trade off well worth taking. The alternative is nil checks everywhere.
> 
> The trade off made at the moment of using associated types is a great burden on the programmer. Take a look at all the complexity in the collections library at present. To give an idea of how complicated this is take a look at the playground you can download from https://github.com/rnapier/MyAnySequence <https://github.com/rnapier/MyAnySequence>. Its mightily complicated compared to my proposal! Therefore I don't  think the current trade off is optimum. Its always a trade off, the trick is to make the best.

Removing associated types and making generics covariant are two different topics, although your proposal seems to have linked them. I'm only concerned about the covariance aspect right now, because if that were dropped the proposed impl would have to be modified anyways.

> 
> 
> Is that giving you an idea of where I am coming from?

I understand exactly where you are coming from. What I, and many other people in this thread are saying, is that we do not want to make the language less safe in order to spare the programmer the pain of typing out explicit variance annotations.

Arguing that some runtime checks for other things exist in Swift, therefore this unrelated specific thing should also be deferred to a runtime check, is not persuasive. Like you said, compile-time safety is a matter of balance; where I fall on that spectrum is a different point than where you fall. To you, the trade-off is worth it; to me (and the other people making the same arguments), it is not. To you, writing out your abstractions using associated types is painful; I haven't felt the same way.

In the end, this is just my opinion, I don't have any special veto powers, and I wouldn't want to bore you by restating my points again and again. If you can convince the core team and the other participants in the group that the trade-off is worth it and drive a proposal through to acceptance, all the better.

Best,
Austin

> 
>   -- Howard.
>  
> 
> I hope this explains my objections (and those expressed elsewhere within this thread) more clearly.
> 
> Best,
> Austin
> 
> 
> On Wed, Jan 13, 2016 at 1:54 PM, Howard Lovatt via swift-evolution <swift-evolution at swift.org <mailto:swift-evolution at swift.org>> wrote:
> @Simon,
> 
> In the Swift code below:
> 
>     let array = [1]
>     array[0] // 1, OK
>     array[1] // Error not detected by compiler but detected at runtime
> 
> you have an example of an error detected at runtime that terminates program execution, it doesn't return an optional.
> 
> In other languages this would be a type error, these languages are usually described as dependent type (https://en.wikipedia.org/wiki/Dependent_type <https://en.wikipedia.org/wiki/Dependent_type>). An example of the advantage of this would be vector (or matrix multiplication), e.g. imagine that Swift had dependent types:
> 
>     let row = RowVec(1, 2) // Type: matrix of int with 1 row and 0 columns (note size is part of the type)
>     let col = ColVec(3) // Type: matrix of int with 0 rows and 1 column
>     let scaler = row * col // Compile time error because both vectors should be the same length
> 
> At the moment if you wrote a matrix package in Swift the above example would be a runtime error and not a compile time error, but with dependent typing it would be a compile time error.
> 
> There is another discussion of Swift Evolution on calculable types that are closely related to dependent typing.
> 
> To me you just strike the balance, sometimes static checking is best sometimes runtime. You strike the balance by how practical it is to do the static checking, if the burden that the static checking adds to the users then it isn't worth it. This is the case with annotated variance in languages like Java and Scala, the annotations do not add much. Hence I am suggesting system that is simple to use, much like Swift arrays are easy to use but not totally, but largely, statically typed.
> 
> Hope that explains my reasoning for making most type error compile time checked but a small subset runtime checked,
> 
>  -- Howard.
> 
> 
> On 13 January 2016 at 14:01, Simon Pilkington <simonmpilkington at icloud.com <mailto:simonmpilkington at icloud.com>> wrote:
> I’d be interested in reading up on what the Oracle response was if you have links.
> 
> As you mentioned even Swift doesn’t get away from runtime type checking but in the two examples you mentioned - array out of bounds and casts - Swift makes use of the Optionals system to highlight that an operation may fail and allows the user to handle that failure. Covariance should have similar syntax support (for example use of optional chaining similar to optional protocol requirements to indicate that a call may fail due to incorrect types). For the compiler to understand when such failure is possible, some kind of covariance syntax would be required.
> 
> As a related question, do you see covariance syntax as such a burden?
> 
> -Simon

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