[swift-evolution] [swift-evolution-announce] [Review] SE-0089: Replace protocol<P1, P2> syntax with Any<P1, P2>

[Dave Abrahams]

on Wed Jun 08 2016, Austin Zheng <austinzheng-AT-gmail.com> wrote:

> On Wed, Jun 8, 2016 at 3:22 PM, Dave Abrahams <dabrahams at apple.com> wrote:
>
>>
>> on Wed Jun 08 2016, Austin Zheng <austinzheng-AT-gmail.com> wrote:
>>
>> > FWIW my opinion is that existentials either shouldn't be allowed to stand
>> > in for generic type parameters, or Dave's option #1 if they are.
>>
>> Don't you mean #2?  Otherwise I'm confused.  #1 is the one that
>> prohibits more usages.
>>
>
> I'm just being cautious until a better solution comes along.
>
>>
>> > The implied promise of a generic type parameter T right now is that T
>> > always stands for the same concrete type (modulo things like passing
>> > in a subclass where a class would do), and likewise for all of T's
>> > associated types (T.Foo is always the same type everywhere in the
>> > context where T is valid). This is what makes using anything with
>> > 'self' requirements in a generic context sound. Allowing existentials
>> > to satisfy T would violate that constraint.
>>
>> Not if you consider Any<Collection where Element == Int> to be a
>> concrete type.  Concrete w.r.t. to a generic parameter means something
>> different from Concrete w.r.t. subtyping.
>>
>
> You can consider Any<Collection where .Element == Int> to be a concrete
> type, but then you have the unprecedented situation where the associated
> types associated with a concrete type aren't necessarily the same for all
> instances (is this true for any type that can satisfy a generic type
> parameter today?).
>
> (For the sake of this argument, Array isn't a concrete type, but Array<T>
> or Array<Int> is. You can't use 'Array' anywhere in Swift today, so I think
> my assertion is fair.)
>
> My understanding is that fixing the generic type parameter T by
> specializing a function/type also fixes all the associated types associated
> with T. This 'contract' would have to be weakened to allow existential
> types to satisfy generic type parameters in any non-trivial way.
>
>>
>> > Relaxing these semantics would make it too easy to write code that
>> > traps at runtime "without the user having to reach" (to paraphrase
>> > Jordan from the "Swift philosophy" thread). Anyone who really really
>> > wants to write code that is 'compile-time unsound' in this way should
>> > have to explicitly type erase using concrete wrappers.
>>
>> I'd really like to see the use-cases, to make sure that these restricted
>> existentials will be useful enough to be worth implementing.
>>
>
> This is enormously important.
>
> First of all, (of course you know) there is a semantic difference between:
>
> protocol Pet : class { }; class Cat : Pet { }; class Dog : Pet { }
>
> class AnimalShelter<T : Pet> { var pet: T }
>
> and
>
> class AnimalShelter { var pet: Pet }
>
> This is something you can express for simple existentials today (the code
> above should run, with minor modifications), but not for existentials
> containing associated types or self requirements.

Sorry, what code?  The above code runs just fine.  Maybe you mean

   typealias T = AnimalShelter<Pet>

?

> I think a big part of what people want to do is to declare variables, pass
> args to functions, and get return values from functions that abstract over
> something like Collection. They want to do this without having to make
> their code generic, and without forcing their code to be homogenous at
> runtime (e.g. an instance of the dynamic AnimalShelter can be populated
> with a cat and later a dog, but the generic one can only ever contain
> either; extend this to Collections of Ints or whatnot).
>
> The big problem is that existentials can't guarantee that they satisfy the
> contract generic functions and types are expecting, as we've been
> discussing.
>
> To be honest, I think requiring existentials to be opened should be a
> prerequisite to using them generically. 

It's a reasonable approach.

> This would define away the impedance mismatch at the expense of making
> certain things marginally harder to do. (An alternate way of thinking
> about it is that it would make the potential for a runtime error
> explicit, and localize it):
>
> func doSomething<T : Collection where T.Element == Int>(x: C, y: C) { ... }
>
> let a : Any<Collection where .Element == Int>
> let b : Any<Collection where .Element == Int>
>
> // Prohibit this...
> // doSomething(a, b)
>
> // Allow this:
> if let a = a openas? T, b = b as? T {
>   // We've recovered the 'strong guarantee' that doSomething expects for T
>   doSomething(a, b)
> } else {
>   // Here's our trap
> }
>
> The biggest problem is that this sort of solution would prohibit
> existentials from being used in generic contexts where the existentials
> only have to be "similar enough", not identical, for things to work out.
> Given how fuzzy "similar enough" has proven to be, maybe that's not a
> terrible tradeoff.

Maybe not.  More info is needed, is all I'm saying.

>> >
>> >
>> > Best,
>> > Austin
>> >
>> > On Wed, Jun 8, 2016 at 2:37 PM, Austin Zheng <austinzheng at gmail.com>
>> wrote:
>> >
>> >> We might be talking past each other. I think Matthew is talking about
>> >> using an existential outside the context of generic functions. For
>> example,
>> >> something like this should be trap-proof (as long as 'x' is immutable,
>> >> which it is in this example):
>> >>
>> >> func copySequenceIntoArray(x: Any<Sequence where .Iterator.Element ==
>> >> Int>) -> [Int] {
>> >> var buffer : [Int] = []
>> >>         // Stupid implementation to make a point
>> >> var iterator : x.Iterator = x.makeIterator()
>> >> while true {
>> >> let nextItem : Int? = iterator.next()
>> >> if let nextItem = nextItem {
>> >> buffer.append(nextItem)
>> >> } else {
>> >> return buffer
>> >> }
>> >> }
>> >> }
>> >>
>> >> Even this would never trap as well:
>> >>
>> >> func copySequenceIntoArray<T>(x: Any<Sequence where .Iterator.Element ==
>> >> T>) -> [T] {
>> >> var buffer : [T] = []
>> >> for item in x {
>> >> buffer.append(item)
>> >> }
>> >> return buffer
>> >> }
>> >>
>> >> Where we run into difficulty is something like this (forgive my abuse of
>> >> the collections API; I don't remember all the new indexing APIs off the
>> top
>> >> of my head):
>> >>
>> >> func doSomething<T : Collection where T.Element == Int>(x: T, y: T) {
>> >> // Get indexes out of x and use them to index into y
>> >> var idx = x.startIndex
>> >> while (idx != x.endIndex || idx != y.endIndex) {
>> >> print(x[idx])
>> >> print(y[idx])
>> >> idx = x.nextIndex(idx)
>> >> }
>> >> }
>> >> let someSeq : Any<Collection where .Element == Int> = // ...
>> >> let anotherSeq : Any<Collection where .Element == Int> = // ...
>> >> // Trouble!
>> >> // someSeq and anotherSeq are the same existential type
>> >> // But the concrete index types within each of the existential variables
>> >> may be different
>> >> doSomething(someSeq, anotherSeq)
>> >>
>> >> It's this situation (using an existential type to fulfill a generic type
>> >> parameter constrained to the same requirements that comprise that
>> >> existential) that requires either of the two options that Dave
>> presented,
>> >> due to our lack of compile-time type information about the fulfilling
>> >> type's associated types.
>> >>
>> >> Best,
>> >> Austin
>> >>
>> >> On Wed, Jun 8, 2016 at 2:33 PM, Matthew Johnson via swift-evolution <
>> >> swift-evolution at swift.org> wrote:
>> >>
>> >>>
>> >>>
>> >>> Sent from my iPad
>> >>>
>> >>> > On Jun 8, 2016, at 3:16 PM, Dave Abrahams via swift-evolution <
>> >>> swift-evolution at swift.org> wrote:
>> >>> >
>> >>> >
>> >>> >> on Wed Jun 08 2016, Thorsten Seitz <swift-evolution at swift.org>
>> wrote:
>> >>> >>
>> >>> >> Ah, thanks, I forgot!  I still consider this a bug, though (will
>> have
>> >>> >> to read up again what the reasons are for that behavior).
>> >>> >
>> >>> > Yes, but in the case of the issue we're discussing, the choices are:
>> >>> >
>> >>> > 1. Omit from the existential's API any protocol requirements that
>> depend
>> >>> >   on Self or associated types, in which case it *can't* conform to
>> >>> >   itself because it doesn't fulfill the requirements.
>> >>>
>> >>> They don't need to be omitted.  They are exposed in different ways
>> >>> depending on how the existential is constrained.  Austin's proposal was
>> >>> originally written to omit some members but it was modified based on
>> >>> feedback from Doug Gregor IIRC (Austin, is that right?).  Now it
>> contains
>> >>> examples showing how these members are made available in a safe way.
>>  Some
>> >>> members may still not be usable because you can't form an argument but
>> IIRC
>> >>> the suggestion was that they be exposed anyway for consistency.
>> >>>
>> >>> >
>> >>> > 2. Erase type relationships and trap at runtime when they don't line
>> up.
>> >>> >
>> >>> > Matthew has been arguing against #2, but you can't “fix the bug”
>> without
>> >>> > it.
>> >>> >
>> >>> >>
>> >>> >> -Thorsten
>> >>> >>
>> >>> >>> Am 08.06.2016 um 21:43 schrieb Austin Zheng <austinzheng at gmail.com
>> >:
>> >>> >>>
>> >>> >>> It's not possible, even with Swift's current implementation of
>> >>> >>> existentials. A protocol type P isn't considered to conform to
>> >>> >>> itself, thus the following is rejected:
>> >>> >>>
>> >>> >>> let a : MyProtocol = // ...
>> >>> >>> func myFunc<T : MyProtocol>(x: T) {
>> >>> >>>  // ....
>> >>> >>> }
>> >>> >>> myFunc(a) // "Cannot invoke 'myFunc' with an argument list of type
>> >>> MyProtocol"
>> >>> >>>
>> >>> >>> Changing how this works is probably worth a proposal by itself.
>> >>> >>>
>> >>> >>> Austin
>> >>> >>>
>> >>> >>>
>> >>> >>> On Wed, Jun 8, 2016 at 12:34 PM, Thorsten Seitz via swift-evolution
>> >>> >>> <swift-evolution at swift.org
>> >>> >>> <mailto:swift-evolution at swift.org>>
>> >>> >>> wrote:
>> >>> >>>
>> >>> >>>> Am 08.06.2016 um 20:33 schrieb Dave Abrahams via swift-evolution
>> >>> >>>> <swift-evolution at swift.org
>> >>> >>>> <mailto:swift-evolution at swift.org>>:
>> >>> >>>>
>> >>> >>>>
>> >>> >>>> on Tue Jun 07 2016, Matthew Johnson <matthew-AT-anandabits.com>
>> >>> wrote:
>> >>> >>>>
>> >>> >>>>>> On Jun 7, 2016, at 9:15 PM, Dave Abrahams
>> >>> >>>>>> <dabrahams at apple.com
>> >>> >>>>>> <mailto:dabrahams at apple.com>>
>> >>> >>>>>> wrote:
>> >>> >>>>>>
>> >>> >>>>>>
>> >>> >>>>>> on Tue Jun 07 2016, Matthew Johnson <matthew-AT-anandabits.com
>> >>> >>>>>> <http://matthew-at-anandabits.com/
>> >>> >>>>>> <http://matthew-at-anandabits.com/>>> wrote:
>> >>> >>>>>
>> >>> >>>>>>>> On Jun 7, 2016, at 4:13 PM, Dave Abrahams via swift-evolution
>> >>> >>>>>>>> <swift-evolution at swift.org
>> >>> >>>>>>>> <mailto:swift-evolution at swift.org>>
>> >>> >>>>>>>> wrote:
>> >>> >>>>>>>>
>> >>> >>>>>>>>
>> >>> >>>>>>>> on Tue Jun 07 2016, Matthew Johnson
>> >>> >>>>>>>> <swift-evolution at swift.org
>> >>> >>>>>>>> <mailto:swift-evolution at swift.org>>
>> >>> >>>>>>>> wrote:
>> >>> >>>>>>>
>> >>> >>>>>>>>>> , but haven't realized
>> >>> >>>>>>>>>> that if you step around the type relationships encoded in
>> Self
>> >>> >>>>>>>>>> requirements and associated types you end up with types that
>> >>> appear to
>> >>> >>>>>>>>>> interoperate but in fact trap at runtime unless used in
>> >>> exactly the
>> >>> >>>>>>>>>> right way.
>> >>> >>>>>>>>>
>> >>> >>>>>>>>> Trap at runtime?  How so?  Generalized existentials should
>> >>> still be
>> >>> >>>>>>>>> type-safe.
>> >>> >>>>>>>>
>> >>> >>>>>>>> There are two choices when you erase static type
>> relationships:
>> >>> >>>>>>>>
>> >>> >>>>>>>> 1. Acheive type-safety by trapping at runtime
>> >>> >>>>>>>>
>> >>> >>>>>>>> FloatingPoint(3.0 as Float) + FloatingPoint(3.0 as Double) //
>> >>> trap
>> >>> >>>>>>>>
>> >>> >>>>>>>> 2. Don't expose protocol requirements that involve these
>> >>> relationships,
>> >>> >>>>>>>> which would prevent the code above from compiling and prevent
>> >>> >>>>>>>> FloatingPoint from conforming to itself.
>> >>> >>>>>>>>
>> >>> >>>>>>>>> Or are you talking about the hypothetical types / behaviors
>> >>> people
>> >>> >>>>>>>>> think they want when they don’t fully understand what is
>> >>> happening...
>> >>> >>>>>>>>
>> >>> >>>>>>>> I don't know what you mean here.  I think generalized
>> >>> existentials will
>> >>> >>>>>>>> be nice to have, but I think most people will want them to do
>> >>> something
>> >>> >>>>>>>> they can't possibly do.
>> >>> >>>>>>>
>> >>> >>>>>>> Exactly.  What I meant is that people think they want that
>> >>> expression
>> >>> >>>>>>> to compile because they don’t understand that the only thing it
>> >>> can do
>> >>> >>>>>>> is trap.  I said “hypothetical” because producing a compile
>> time
>> >>> error
>> >>> >>>>>>> rather than a runtime trap is the only sane thing to do.  Your
>> >>> comment
>> >>> >>>>>>> surprised me because I can’t imagine we would move forward in
>> >>> Swift
>> >>> >>>>>>> with the approach of trapping.
>> >>> >>>>>>
>> >>> >>>>>> I would very much like to be able to create instances of
>> >>> “Collection
>> >>> >>>>>> where Element == Int” so we can throw away the wrappers in the
>> >>> stdlib.
>> >>> >>>>>> That will require some type mismatches to be caught at runtime
>> via
>> >>> >>>>>> trapping.
>> >>> >>>>>
>> >>> >>>>> For invalid index because the existential accepts a type erased
>> >>> index?
>> >>> >>>>
>> >>> >>>> Exactly.
>> >>> >>>>
>> >>> >>>>> How do you decide where to draw the line here?  It feels like a
>> very
>> >>> >>>>> slippery slope for a language where safety is a stated priority
>> to
>> >>> >>>>> start adopting a strategy of runtime trapping for something as
>> >>> >>>>> fundamental as how you expose members on an existential.
>> >>> >>>>
>> >>> >>>> If you don't do this, the alternative is that “Collection where
>> >>> Element
>> >>> >>>> == Int” does not conform to Collection.  That's weird and not very
>> >>> >>>> useful.  You could expose all the methods that were on protocol
>> >>> >>>> extensions of Collection on this existential, unless they used
>> >>> >>>> associated types other than the element type.  But you couldn't
>> pass
>> >>> the
>> >>> >>>> existential to a generic function like
>> >>> >>>>
>> >>> >>>>  func scrambled<C: Collection>(_ c: C) -> [C.Element]
>> >>> >>>
>> >>> >>> I don’t understand. Why couldn’t an existential be passed to that
>> >>> function?
>> >>> >>>
>> >>> >>> -Thorsten
>> >>> >>>
>> >>> >>>
>> >>> >>>
>> >>> >>>>
>> >>> >>>>> IMO you should *have* to introduce unsafe behavior like that
>> >>> manually.
>> >>> >>>>
>> >>> >>>> Collection where Element == Int & Index == *
>> >>> >>>>
>> >>> >>>> ?
>> >>> >>>>
>> >>> >>>>> Collection indices are already something that isn’t fully
>> statically
>> >>> >>>>> safe so I understand why you might want to allow this.
>> >>> >>>>
>> >>> >>>> By the same measure, so are Ints :-)
>> >>> >>>>
>> >>> >>>> The fact that a type's methods have preconditions does *not* make
>> it
>> >>> >>>> “statically unsafe.”
>> >>> >>>>
>> >>> >>>>> But I don’t think having the language's existentials do this
>> >>> >>>>> automatically is the right approach.  Maybe there is another
>> >>> approach
>> >>> >>>>> that could be used in targeted use cases where the less safe
>> >>> behavior
>> >>> >>>>> makes sense and is carefully designed.
>> >>> >>>>
>> >>> >>>> Whether it makes sense or not really depends on the use-cases.
>> >>> There's
>> >>> >>>> little point in generalizing existentials if the result isn't very
>> >>> useful.
>> >>> >>>> The way to find out is to take a look at the examples we currently
>> >>> have
>> >>> >>>> of protocols with associated types or Self requirements and
>> consider
>> >>> >>>> what you'd be able to do with their existentials if type
>> >>> relationships
>> >>> >>>> couldn't be erased.
>> >>> >>>>
>> >>> >>>> We have known use-cases, currently emulated in the standard
>> library,
>> >>> for
>> >>> >>>> existentials with erased type relationships.  *If* these represent
>> >>> the
>> >>> >>>> predominant use cases for something like generalized
>> existentials, it
>> >>> >>>> seems to me that the language feature should support that.  Note:
>> I
>> >>> have
>> >>> >>>> not seen anyone build an emulation of the other kind of
>> generalized
>> >>> >>>> existential.  My theory: there's a good reason for that :-).
>> >>> >>>>
>> >>> >>>> --
>> >>> >>>> Dave
>> >>> >>>> _______________________________________________
>> >>> >>>> swift-evolution mailing list
>> >>> >>>> swift-evolution at swift.org
>> >>> >>>> <mailto:swift-evolution at swift.org>
>> >>> >>>> https://lists.swift.org/mailman/listinfo/swift-evolution
>> >>> >>>> <https://lists.swift.org/mailman/listinfo/swift-evolution>
>> >>> >>>
>> >>> >>> _______________________________________________
>> >>> >>> swift-evolution mailing list
>> >>> >>> swift-evolution at swift.org
>> >>> >>> <mailto:swift-evolution at swift.org>
>> >>> >>> https://lists.swift.org/mailman/listinfo/swift-evolution
>> >>> >>> <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
>> >>> >
>> >>> > --
>> >>> > Dave
>> >>> >
>> >>> > _______________________________________________
>> >>> > 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
>> >>>
>> >>
>> >>
>>
>> --
>> Dave
>>

-- 
Dave