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