> On Dec 1, 2017, at 9:11 AM, Ben Langmuir <blangm...@apple.com> wrote:
>
>>
>> On Nov 30, 2017, at 4:28 PM, Douglas Gregor via swift-evolution
>> <swift-evolution@swift.org <mailto: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”.
>> <https://github.com/apple/swift-evolution/blob/master/proposals/0108-remove-assoctype-inference.md>
>>
>>
>> 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”
>> <https://github.com/apple/swift-evolution/blob/master/proposals/0174-filter-range-replaceable.md>,
>> 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 <https://github.com/apple/swift/pull/12913>, 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
>> <https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md#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.
>
> Hey Doug,
>
> I'm very much in favour of reducing the scope of associated type inference.
> Can you outline why you believe that (3) is necessary? If I am following
> correctly, if we had (1) and (2) the only thing you'd need to add to the
> "minimal collection" implementation would be a typealias for `Element`, which
> seems reasonable to me.
If we had (1) and (2) but not (3), we’d need to specify both Element and Index
in the “minimal collection”:
>> extension MyCollection: RandomAccessCollection {
>> typealias Element = T
>> typealias Index = Int
>>
>> var startIndex: Int { return contents.startIndex }
>> var endIndex: Int { return contents.endIndex }
>> subscript(index: Int) -> T { return contents[index] }
>> }
Indices would come from (2) and Iterator and SubSequence would come from (1).
- Doug
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution
