<html><head><meta http-equiv="content-type" content="text/html; charset=utf-8"></head><body dir="auto"><br><br><div id="AppleMailSignature">Sent from my iPhone</div><div><br>On Dec 2, 2017, at 1:37 PM, Matthew Johnson <<a href="mailto:matthew@anandabits.com">matthew@anandabits.com</a>> wrote:<br><br></div><blockquote type="cite"><div><meta http-equiv="Content-Type" content="text/html charset=utf-8"><br class=""><div><blockquote type="cite" class=""><div class="">On Nov 30, 2017, at 6:28 PM, Douglas Gregor via swift-evolution <<a href="mailto:swift-evolution@swift.org" class="">swift-evolution@swift.org</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><meta http-equiv="Content-Type" content="text/html; charset=utf-8" class=""><div style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class="">Hello Swift community,<div class=""><br class=""></div><div class="">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 <a href="https://github.com/apple/swift-evolution/blob/master/proposals/0108-remove-assoctype-inference.md" class="">SE-0108 “Remove associated type inference”.</a> </div><div class=""><br class=""></div><div class="">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.</div><div class=""><br class=""></div><div class=""><b class="">A Motivating Example</b></div><div class="">As a motivating example, let’s consider a “minimal” random access collection:</div><div class=""><br class=""></div><blockquote style="margin: 0 0 0 40px; border: none; padding: 0px;" class=""><div class=""><div class=""><font face="Menlo" class="">struct MyCollection<T> {</font></div></div><div class=""><div class=""><font face="Menlo" class=""> var contents: [T]</font></div></div><div class=""><div class=""><font face="Menlo" class="">}</font></div></div><div class=""><div class=""><font face="Menlo" class=""><br class=""></font></div></div><div class=""><div class=""><font face="Menlo" class="">extension MyCollection: RandomAccessCollection { </font></div></div><div class=""><div class=""><font face="Menlo" class=""> var startIndex: Int { return contents.startIndex }</font></div></div><div class=""><div class=""><font face="Menlo" class=""> var endIndex: Int { return contents.endIndex }</font></div></div><div class=""><div class=""><font face="Menlo" class=""> subscript(index: Int) -> T { return contents[index] }</font></div></div><div class=""><div class=""><font face="Menlo" class="">}</font></div></div></blockquote><div class=""><br class=""></div><div class="">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:</div><div class=""><br class=""></div><div class=""><br class=""></div><div class=""><blockquote style="margin: 0px 0px 0px 40px; border: none; padding: 0px;" class=""><div class=""><font face="Menlo" class="">extension MyCollection: RandomAccessCollection {</font></div><div class=""><font face="Menlo" class=""><b class=""> typealias Element = T</b></font></div><div class=""><font face="Menlo" class=""><b class=""> typealias Index = Int</b></font></div><div class=""><font face="Menlo" class=""><b class=""> typealias Indices = CountableRange<Int></b></font></div><div class=""><font face="Menlo" class=""><b class=""> typealias Iterator = IndexingIterator<MyCollection<T>></b></font></div><div class=""><font face="Menlo" class=""><b class=""> typealias SubSequence = RandomAccessSlice<MyCollection<T>></b></font></div><div class=""><font face="Menlo" class=""> </font></div><div class=""><font face="Menlo" class=""> var startIndex: Int { return contents.startIndex }</font></div><div class=""><font face="Menlo" class=""> var endIndex: Int { return contents.endIndex }</font></div><div class=""><font face="Menlo" class=""> subscript(index: Int) -> T { return contents[index] }</font></div><div class=""><font face="Menlo" class="">}</font></div><div class=""><font face="Menlo" class=""><br class=""></font></div></blockquote></div><div class="">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?</div><div class=""><br class=""></div><div class="">The issue would get worse with, e.g., <a href="https://github.com/apple/swift-evolution/blob/master/proposals/0174-filter-range-replaceable.md" class="">SE-0174 “Change filter to return an associated type”</a>, 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.</div><div class=""><br class=""></div><div class=""><b class="">Associated Type Defaults</b></div><div class="">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:</div><div class=""><br class=""></div><blockquote style="margin: 0 0 0 40px; border: none; padding: 0px;" class=""><div class=""><font face="Menlo" class="">protocol Collection : Sequence {</font></div><div class=""><font face="Menlo" class=""> associatedtype Indices = DefaultIndices<Self></font></div><div class=""><font face="Menlo" class=""> // ...</font></div><div class=""><font face="Menlo" class="">}</font></div><div class=""><font face="Menlo" class=""><br class=""></font></div><div class=""><div class=""><font face="Menlo" class="">protocol BidirectionalCollection : Collection {</font></div></div><div class=""><div class=""><font face="Menlo" class=""> associatedtype Indices = DefaultBidirectionalIndices<Self></font></div></div><div class=""><div class=""><font face="Menlo" class=""> // ...</font></div></div><div class=""><div class=""><font face="Menlo" class="">}</font></div></div><div class=""><font face="Menlo" class=""><br class=""></font></div><div class=""><div class=""><font face="Menlo" class="">protocol RandomAccessCollection : BidirectionalCollection {</font></div></div><div class=""><div class=""><font face="Menlo" class=""> associatedtype Indices = DefaultRandomAccessIndices<Self></font></div></div><div class=""><div class=""><font face="Menlo" class=""> // ...</font></div></div><div class=""><div class=""><font face="Menlo" class="">}</font></div></div></blockquote><div class=""><br class=""></div><div class="">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>.</div><div class=""><br class=""></div><div class="">(Aside: DefaultRandomAccessIndices and DefaultBidirectionalIndices got collapsed into DefaultIndices now that we have <a href="https://github.com/apple/swift/pull/12913" class="">conditional conformances for the standard library</a>, but the issues I’m describing remain).</div><div class=""><br class=""></div><div class="">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?</div><div class=""><br class=""></div><div class=""><b class="">Associated Type Inference</b></div><div class="">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:</div><div class=""><br class=""></div><blockquote style="margin: 0 0 0 40px; border: none; padding: 0px;" class=""><div class=""><font face="Menlo" class="">protocol RandomAccessCollection : BidirectionalCollection {</font></div><div class=""><font face="Menlo" class=""> associatedtype Element</font></div><div class=""><font face="Menlo" class=""> associatedtype Index</font></div><div class=""><font face="Menlo" class=""><br class=""></font></div><div class=""><font face="Menlo" class=""> var startIndex: Index { get }</font></div><div class=""><font face="Menlo" class=""> var endIndex: Index { get }</font></div><div class=""><font face="Menlo" class=""> subscript (i: Index) -> Element { get }</font></div><div class=""><font face="Menlo" class="">}</font></div></blockquote><div class=""><br class=""></div><div class="">Associated type inference wil try to satisfy those requirements for MyCollection, and will find these declarations:</div><div class=""><br class=""></div><div class=""><blockquote style="margin: 0px 0px 0px 40px; border: none; padding: 0px;" class=""><div class=""><font face="Menlo" class="">extension MyCollection: RandomAccessCollection { </font></div><div class=""><font face="Menlo" class=""> var startIndex: Int { return contents.startIndex }</font></div><div class=""><font face="Menlo" class=""> var endIndex: Int { return contents.endIndex }</font></div><div class=""><font face="Menlo" class=""> subscript(index: Int) -> T { return contents[index] }</font></div><div class=""><font face="Menlo" class="">}</font></div><div class=""><br class=""></div></blockquote></div><div class="">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.</div><div class=""><br class=""></div><div class="">Associated type inference often has to deal with ambiguities. For example, there is an extension of Collection that provides a range subscript operator:</div><div class=""><br class=""></div><blockquote style="margin: 0 0 0 40px; border: none; padding: 0px;" class=""><div class=""><font face="Menlo" class="">extension Collection {</font></div><div class=""><font face="Menlo" class=""> subscript (bounds: Range<Index>) -> Slice<Self> { … }</font></div><div class=""><font face="Menlo" class="">}</font></div></blockquote><div class=""><br class=""></div><div class="">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>).</div><div class=""><br class=""></div><div class="">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:</div><div class=""><br class=""></div><div class=""><blockquote style="margin: 0px 0px 0px 40px; border: none; padding: 0px;" class=""><div class=""><font face="Menlo" class="">protocol RandomAccessCollection : BidirectionalCollection {</font></div><div class=""><font face="Menlo" class=""> associatedtype Index</font></div><div class=""><font face="Menlo" class=""> associatedtype Indices: RandomAccessCollection where Indices.Element == Index</font></div><div class=""><br class=""></div><div class=""><font face="Menlo" class=""> var indices: Indices { get }</font></div><div class=""><span style="font-family: Menlo;" class="">}</span></div><div class=""><font face="Menlo" class=""><br class=""></font></div></blockquote></div><div class="">We will match that requirement for an “indices” property against a member of a constrained protocol extension of RandomAccessCollection:</div><div class=""><br class=""></div><blockquote style="margin: 0 0 0 40px; border: none; padding: 0px;" class=""><div class=""><div class=""><font face="Menlo" class="">extension RandomAccessCollection where Index : Strideable, Index.Stride == IndexDistance, Indices == CountableRange<Index> {</font></div></div><div class=""><div class=""><font face="Menlo" class=""> public var indices: CountableRange<Index> {</font></div></div><div class=""><div class=""><font face="Menlo" class=""> return startIndex..<endIndex</font></div></div><div class=""><div class=""><font face="Menlo" class=""> }</font></div></div><div class=""><font face="Menlo" class="">}</font></div></blockquote><div class=""><br class=""></div><div class="">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.</div><div class=""><br class=""></div><div class=""><br class=""></div><div class=""><b class="">What’s a Good Solution Look Like?</b></div><div class="">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?</div><div class=""><br class=""></div><div class=""><ul class="MailOutline"><li class="">It should allow the author of a protocol to provide reasonable defaults, so the user doesn’t have to write them</li><li class="">It shouldn’t require users to write typealiases for “obvious” cases, even when they aren’t due to defaults</li><li class="">It shouldn’t infer an inconsistent set of typealiases</li><li class="">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</li><li class="">It should admit a reasonable implementation in the compiler that is performant and robust</li></ul></div><div class=""><br class=""></div><div class=""><b class="">A Rough Proposal</b></div><div class="">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:</div><div class=""><br class=""></div><div class=""><ol class="MailOutline"><li class="">Associated type defaults, which are specified with the associated type itself, e.g.,<br class=""><br class=""><font face="Menlo" class=""> associatedtype Indices = DefaultIndices<Self><br class=""></font><br class="">These are easy to reason about for both the programmer and the compiler.</li><li class="">Typealiases in (possibly constrained) protocol extensions, e.g.,<br class=""><br class=""><font face="Menlo" class=""> extension RandomAccessCollection where Index : Strideable, Index.Stride == IndexDistance {</font><br class=""><font face="Menlo" class=""> typealias RandomAccessCollection.Indices = CountableRange<Index></font><br class=""><font face="Menlo" class=""> }</font><br class=""><br class="">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”. <br class=""><br class="">Note that this mechanism technically obviates the need for (1), in the same sense that <a href="https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md#default-implementations-in-protocols-" class="">default implementations in protocols</a> are merely syntactic sugar.</li><li class="">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:<br class=""><br class=""><div class=""><font face="Menlo" class=""> extension MyCollection: RandomAccessCollection { </font></div><div class=""><font face="Menlo" class=""> var startIndex: Int { return contents.startIndex }</font></div><div class=""><font face="Menlo" class=""> var endIndex: Int { return contents.endIndex }</font></div><div class=""><font face="Menlo" class=""> subscript(index: Int) -> T { return contents[index] }</font></div><div class=""><font face="Menlo" class=""> }<br class=""><br class=""></font></div>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.</li></ol></div><div class=""><div class=""><br class=""></div></div><div class=""><b class="">Thoughts?</b></div><div class="">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?</div></div></div></blockquote><div><br class=""></div>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. </div></div></blockquote><div><br></div>Thank you for staying this further!<div><br><blockquote type="cite"><div><div><br class=""></div><div>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!<br class=""></div></div></blockquote><div><br></div><div>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. </div><div><br></div> - Doug</div><div><br><blockquote type="cite"><div><div><br class=""><blockquote type="cite" class=""><div class=""><div style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class=""><div class=""><br class=""></div><div class=""><span class="Apple-tab-span" style="white-space:pre"> </span>- Doug</div><div class=""><br class=""></div></div>_______________________________________________<br class="">swift-evolution mailing list<br class=""><a href="mailto:swift-evolution@swift.org" class="">swift-evolution@swift.org</a><br class=""><a href="https://lists.swift.org/mailman/listinfo/swift-evolution">https://lists.swift.org/mailman/listinfo/swift-evolution</a><br class=""></div></blockquote></div><br class=""></div></blockquote></div></body></html>