Sent from my iPad
> On Dec 2, 2017, at 4:40 PM, Douglas Gregor <dgre...@apple.com> wrote:
>
>
>
> Sent from my iPhone
>
>> On Dec 2, 2017, at 1:37 PM, Matthew Johnson <matt...@anandabits.com> wrote:
>>
>>
>>> On Nov 30, 2017, at 6:28 PM, Douglas Gregor via swift-evolution
>>> <swift-evolution@swift.org> wrote:
>>>
>>> Hello Swift community,
>>>
>>> Associated type inference, which is the process by which the Swift compiler
>>> attempts to infer typealiases to satisfy associated-type requirements based
>>> on other requirements, has caused both implementation problems and user
>>> confusion for a long time. Some of you might remember a previous (failed)
>>> attempt to remove this feature from the Swift language, in SE-0108 “Remove
>>> associated type inference”.
>>>
>>> I’m not sure we can remove this feature outright (i.e., the concerns that
>>> sank that proposal are still absolutely valid), because it is so very
>>> convenient and a lot of user code likely depends on it in some form or
>>> other. So, here I’d like to describe the uses of the feature, its current
>>> (very problematic) implementation approach, and a half-baked proposal to
>>> narrow the scope of associated type inference to something that I think is
>>> more tractable. I need help with the design of this feature, because I feel
>>> like it’s going to be a delicate balance between implementability and
>>> expressiveness.
>>>
>>> A Motivating Example
>>> As a motivating example, let’s consider a “minimal” random access
>>> collection:
>>>
>>> struct MyCollection<T> {
>>> var contents: [T]
>>> }
>>>
>>> extension MyCollection: RandomAccessCollection {
>>> var startIndex: Int { return contents.startIndex }
>>> var endIndex: Int { return contents.endIndex }
>>> subscript(index: Int) -> T { return contents[index] }
>>> }
>>>
>>> This is actually pretty awesome: by providing just two properties and a
>>> subscript, we get the full breadth of the random access collection API!
>>> This is relying heavily on associated type inference (for associated type
>>> requirements) and default implementations specified on protocol extensions.
>>> Without associated type inference, we would have had to write:
>>>
>>>
>>> extension MyCollection: RandomAccessCollection {
>>> typealias Element = T
>>> typealias Index = Int
>>> typealias Indices = CountableRange<Int>
>>> typealias Iterator = IndexingIterator<MyCollection<T>>
>>> typealias SubSequence = RandomAccessSlice<MyCollection<T>>
>>>
>>> var startIndex: Int { return contents.startIndex }
>>> var endIndex: Int { return contents.endIndex }
>>> subscript(index: Int) -> T { return contents[index] }
>>> }
>>>
>>> where the bolded typealiases are currently inferred. It was worse back when
>>> we reviewed SE-0108, because IIRC there were a few underscored associated
>>> types (e.g., _Element) that have since been removed. Still, that’s a bit of
>>> additional work to define a “minimal” collection, and requires quite a bit
>>> more understanding: how do I know to choose IndexingIterator, and
>>> CountableRange, and RandomAccessSlice?
>>>
>>> The issue would get worse with, e.g., SE-0174 “Change filter to return an
>>> associated type”, which adds an associated type Filtered that almost nobody
>>> will ever customize, and isn’t really fundamental to the way collections
>>> work. Adding Filtered to the standard library would be a source-breaking
>>> change, because users would have to write a typealias giving it its default.
>>>
>>> Associated Type Defaults
>>> One of the ways in which we avoid having to specify typealiases is to use
>>> associated type defaults. For example, the standard library contains
>>> associated type defaults for Indices, Iterator, and SubSequence. Let’s
>>> focus on Indices:
>>>
>>> protocol Collection : Sequence {
>>> associatedtype Indices = DefaultIndices<Self>
>>> // ...
>>> }
>>>
>>> protocol BidirectionalCollection : Collection {
>>> associatedtype Indices = DefaultBidirectionalIndices<Self>
>>> // ...
>>> }
>>>
>>> protocol RandomAccessCollection : BidirectionalCollection {
>>> associatedtype Indices = DefaultRandomAccessIndices<Self>
>>> // ...
>>> }
>>>
>>> The basic idea here is that different protocols in the hierarchy provide
>>> different defaults, and you presumably want the default from the most
>>> specific protocol. If I define a type and make it conform to
>>> BidirectionalCollection, I’d expect to get
>>> DefaultBidirectionalIndices<Self> for Indices. If a define a type and make
>>> it conform to RandomAccessIterator, I’d expect to get
>>> DefaultRandomAccessIndices<Self>.
>>>
>>> (Aside: DefaultRandomAccessIndices and DefaultBidirectionalIndices got
>>> collapsed into DefaultIndices now that we have conditional conformances for
>>> the standard library, but the issues I’m describing remain).
>>>
>>> Associated type defaults seem like a reasonable feature that fits well
>>> enough into the design. However, it’s not the only thing in place with our
>>> MyCollection example, for which Indices was inferred to CountableRange.
>>> How’s that happen?
>>>
>>> Associated Type Inference
>>> Associated type inference attempts to look at the requirements of a
>>> protocol, and then looks into the conforming type for declarations that
>>> might satisfy those requirements, and infers associated types from the
>>> types of those declarations. Let’s look at some examples.
>>> RandomAccessCollection has some requirements that mention the Index and
>>> Element types:
>>>
>>> protocol RandomAccessCollection : BidirectionalCollection {
>>> associatedtype Element
>>> associatedtype Index
>>>
>>> var startIndex: Index { get }
>>> var endIndex: Index { get }
>>> subscript (i: Index) -> Element { get }
>>> }
>>>
>>> Associated type inference wil try to satisfy those requirements for
>>> MyCollection, and will find these declarations:
>>>
>>> extension MyCollection: RandomAccessCollection {
>>> var startIndex: Int { return contents.startIndex }
>>> var endIndex: Int { return contents.endIndex }
>>> subscript(index: Int) -> T { return contents[index] }
>>> }
>>>
>>> and match them up. From startIndex, we infer Index := Int. From endIndex,
>>> we infer Index := Int. From subscript, we infer Index := Int and Element :=
>>> T. Those results are all consistent, so we’ve properly inferred Index and
>>> Element. Yay.
>>>
>>> Associated type inference often has to deal with ambiguities. For example,
>>> there is an extension of Collection that provides a range subscript
>>> operator:
>>>
>>> extension Collection {
>>> subscript (bounds: Range<Index>) -> Slice<Self> { … }
>>> }
>>>
>>> When we look at that and match it to the subscript requirement in
>>> RandomAccessCollection (remembering that argument labels aren’t significant
>>> for subscripts by default!), we infer Index := Range<Index> (admittedly
>>> weird) and Element := Slice<Self> (could be legitimate). We have to discard
>>> this candidate because the deduction from startIndex/endIndex (Index :=
>>> Int) collides with this deduction (Index := Range<Index>).
>>>
>>> In our initial example, we saw that Indices was inferred to
>>> CountableRange<Int>. Let’s look at another slice of the
>>> RandomAccessCollection protocol that’s relevant to this associated type:
>>>
>>> protocol RandomAccessCollection : BidirectionalCollection {
>>> associatedtype Index
>>> associatedtype Indices: RandomAccessCollection where Indices.Element ==
>>> Index
>>>
>>> var indices: Indices { get }
>>> }
>>>
>>> We will match that requirement for an “indices” property against a member
>>> of a constrained protocol extension of RandomAccessCollection:
>>>
>>> extension RandomAccessCollection where Index : Strideable, Index.Stride ==
>>> IndexDistance, Indices == CountableRange<Index> {
>>> public var indices: CountableRange<Index> {
>>> return startIndex..<endIndex
>>> }
>>> }
>>>
>>> Associated type inference can determine here that Indices :=
>>> CountableRange<Index>, but only when Index: Strideable and Index.Stride ==
>>> IndexDistance. In other words, there are a whole bunch of other constraints
>>> to verify before we can accept this inference for Indices.
>>>
>>>
>>> What’s a Good Solution Look Like?
>>> Our current system for associated type inference and associated type
>>> defaults is buggy and complicated. The compiler gets it right often enough
>>> that people depend on it, but I don’t think anyone can reasonably be
>>> expected to puzzle out what’s going to happen, and this area is rife with
>>> bugs. If we were to design a new solution from scratch, what properties
>>> should it have?
>>>
>>> It should allow the author of a protocol to provide reasonable defaults, so
>>> the user doesn’t have to write them
>>> It shouldn’t require users to write typealiases for “obvious” cases, even
>>> when they aren’t due to defaults
>>> It shouldn’t infer an inconsistent set of typealiases
>>> It should be something that a competent Swift programmer could reason about
>>> when it will succeed, when and why it will fail, and what the resulting
>>> inferred typealiases would be
>>> It should admit a reasonable implementation in the compiler that is
>>> performant and robust
>>>
>>> A Rough Proposal
>>> I’ve been thinking about this for a bit, and I think there are three ways
>>> in which we should be able to infer an associated type witness:
>>>
>>> Associated type defaults, which are specified with the associated type
>>> itself, e.g.,
>>>
>>> associatedtype Indices = DefaultIndices<Self>
>>>
>>> These are easy to reason about for both the programmer and the compiler.
>>> Typealiases in (possibly constrained) protocol extensions, e.g.,
>>>
>>> extension RandomAccessCollection where Index : Strideable, Index.Stride
>>> == IndexDistance {
>>> typealias RandomAccessCollection.Indices = CountableRange<Index>
>>> }
>>>
>>> I’m intentionally using some odd ‘.’ syntax here to indicate that this
>>> typealias is intended only to be found when trying to satisfy an associated
>>> type requirement, and is not a general typealias that could be found by
>>> normal name lookup. Let’s set the syntax bike shed aside for the moment.
>>> The primary advantage of this approach (vs. inferring Indices from “var
>>> Indices: CountableRange<Index>” in a constrained protocol extension) is
>>> that there’s a real typealias declaration that compiler and programmer
>>> alike can look at and reason about based just on the name “Indices”.
>>>
>>> Note that this mechanism technically obviates the need for (1), in the same
>>> sense that default implementations in protocols are merely syntactic sugar.
>>> Declarations within the nominal type declaration or extension that declares
>>> conformance to the protocol in question. This is generally the same
>>> approach as described in “associated type inference” above, where we match
>>> requirements of the protocol against declarations that could satisfy those
>>> requirements and infer associated types from there. However, I want to turn
>>> it around: instead of starting with the requirements of the protocol any
>>> looking basically anywhere in the type or any protocol to which it conforms
>>> (for implementations in protocol extensions), start with the declarations
>>> that the user explicitly wrote at the point of the conformance and look for
>>> requirements they might satisfy. For example, consider our initial example:
>>>
>>> extension MyCollection: RandomAccessCollection {
>>> var startIndex: Int { return contents.startIndex }
>>> var endIndex: Int { return contents.endIndex }
>>> subscript(index: Int) -> T { return contents[index] }
>>> }
>>>
>>> Since startIndex, endIndex, and subscript(_:) are declared in the same
>>> extension that declares conformance to RandomAccessIterator, we should look
>>> for requirements with the same name as these properties and subscript
>>> within RandomAccessCollection (or any protocol it inherits) and infer Index
>>> := Int and Element := T by matching the type signatures. This is still the
>>> most magical inference rule, because there is no declaration named “Index”
>>> or “Element” to look at. However, it is much narrower in scope than the
>>> current implementation, because it’s only going to reason from the
>>> (probably small) set of declarations that the user wrote alongside the
>>> conformance, so it’s more likely to be intentional. Note that this is again
>>> nudging programmers toward the style of programming where one puts one
>>> protocol conformance per extension, which is admittedly my personal
>>> preference.
>>>
>>> Thoughts?
>>> I think this approach is more predictable and more implementable than the
>>> current model. I’m curious whether the above makes sense to someone other
>>> than me, and whether it covers existing use cases well enough. Thoughts?
>>
>> Hi Doug. I’ve had a chance to give this some thought and spent a little bit
>> of time looking at some code. This approach would be sufficient for some
>> use cases I’ve been having trouble with lately.
>
> Thank you for staying this further!
>
>>
>> One other heuristic that may make sense comes to mind: piggyback on other
>> conformances that are visible where the conformance in question is declared.
>> If an associated type can’t be inferred where T: P is declared but an
>> associated type with the same name is inferred in another conformance of T
>> visible from the T: P declaration use that type. I’ll leave it up to you to
>> evaluate if and when this might be worth considering, you’re the expert!
>
> Yes, this is a good point. The tricky thing here is that it’s a different
> kind of “global” inference, where at worst we are considering all of the
> protocols to which a given type conforms at once... but I suspect we have to
> do something along these lines.
The global nature of this and potential complexity associated with that is
exactly why I’m happy leaving it to your judgement.
>
> - Doug
>
>>
>>>
>>> - Doug
>>>
>>> _______________________________________________
>>> swift-evolution mailing list
>>> swift-evolution@swift.org
>>> https://lists.swift.org/mailman/listinfo/swift-evolution
>>
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution
