<html><head><meta http-equiv="Content-Type" content="text/html charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><div class="">Hi Jonathan,</div><div class=""><br class=""></div><div class="">It looks like the majority of this is about finite vs infinite collections. This should be a separate thread, and one we certainly need to have, but doesn’t need to be mixed together with the wider one-sided ranges discussion. For now, I think it’s reasonable to say that 1) left-one-sided ranges of countable things can be sequences, 2) right-sided ranges shouldn’t, and 3) <i class="">if</i> infinite collections end up being a thing, left-sided ranges should be one.</div><div class=""><br class=""></div><br class=""><div><blockquote type="cite" class=""><div class="">On Feb 7, 2017, at 9:18 AM, Jonathan Hull 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=""><div class=""><br class=""><blockquote type="cite" class=""><blockquote type="cite" class="">Oh, sorry, I was referring to an earlier post I made in this thread,<br class="">but didn’t make that clear. I’ll give a longer explanation of my<br class="">reasoning behind the statement that partial ranges shouldn’t conform<br class="">to Sequence (on their own) below... but the short version is that the<br class="">conformance, like cake, is a lie... and we are using the trap to lie<br class="">to ourselves about it.<br class=""></blockquote><br class="">*If* the trap is a lie (and I'm not saying it is), it's a lie we tell<br class="">ourselves about Int, because practically speaking, most people can't<br class="">program correctly always keeping in mind that Int has finite expressive<br class="">range. This is a conscious decision made by the Swift language a long<br class="">time ago. It is *not* a lie about ranges, but if you make a range based<br class="">on Int it will contain a lie, just like everything else that uses Int.<br class=""></blockquote><br class="">I think I touched a 3rd rail here by mentioning trapping. Trapping is a symptom of a design issue here, not the underlying problem.<br class=""><br class="">I wasn’t saying that the trap itself is a lie, just that it lets us lie to ourselves about how the types fit together. Basically we are trying to shove things into collection which aren’t collections, and then things like ‘count’ and ‘dropLast()’ start failing. You can no longer write reliable generic code under those conditions.<br class=""><br class="">I am not arguing against trapping in general here, or that Int shouldn’t trap. I am saying that PartialRange and Collection don’t mesh correctly, and it is REALLY useful for them to mesh correctly. I am also saying that problem can be fixed by providing an upper bound (such as Int.max) instead of saying it is infinite (with respect to Collection). As you pointed out, for something like Int, it won’t even get to the trap before locking up the computer by counting through billions of numbers anyway, so it shouldn’t make much practical difference there. It will make a big practical difference in being able to call things like ‘count’ and ‘dropLast()’ and write generic code that works for all Collections.<br class=""><br class=""><br class=""><br class=""><blockquote type="cite" class=""><blockquote type="cite" class="">If we continue down this path, we will find more and more edge cases<br class="">that need to be papered over, until the design eventually needs to be<br class="">scrapped or buttressed with compiler magic. For example, let’s say we<br class="">define a PartialRange as a simple struct with optional endpoints, then<br class="">we conform it to Sequence. Now we can say ’n…’ and get a sequence.<br class="">But what happens when we say ‘…n’? <br class=""></blockquote><br class="">You don't get a Sequence.<br class=""><br class=""><blockquote type="cite" class="">Where does that sequence start if it has an implicit start point of<br class="">negative infinity? Well, we promised a Sequence, so our only real<br class="">option is to trap (for some types anyway). For UInt, ‘…n’ is a<br class="">perfectly valid sequence (though we could trap on that as well for<br class="">consistency sake and say that you have to say '0…n’). We are using<br class="">trapping to let us ignore the fact that we are promising something<br class="">(conformance to Sequence) that isn’t really true...<br class=""></blockquote><br class="">This is a red herring. Nobody has proposed making ...n a Sequence.<br class=""></blockquote><br class="">If ’n…’ and ‘…n’ are represented by different types, then I remove my objection about adhering to Sequence. I could have sworn the last version I saw had them as a single type (and thus there was no way to enable one without the other), but that may not have been an official version. If they are separate types, then it isn’t an issue (and trapping when the sequence reaches above Int’s limit is perfectly fine here). <br class=""><br class=""></div></div></blockquote><div><br class=""></div><div>Don’t worry, you’re not imagining it :)</div><div><br class=""></div><div>There have been some prototypes pass by on this list of one-sided ranges where left- and right-sided ranges were covered by the same type. I think one example had it so the upper and lower bound were optional. This has the benefit of simplicity, but misses out on the opportunity for the type system to enforce certain behavior so I don’t think would be the final implementation we want.</div><br class=""><blockquote type="cite" class=""><div class=""><div class="">I am still worried about adhering to Collection though.<br class=""><br class=""><br class=""></div></div></blockquote><div><br class=""></div><div>Will take this up on a separate thread.</div><br class=""><blockquote type="cite" class=""><div class=""><div class=""><blockquote type="cite" class="">We had several discussions about infinite collections last year. My<br class="">conclusion was that they were useful and there was no reason to prohibit<br class="">them, so we should lift the reachability requirement for endIndex.<br class=""></blockquote><br class="">I agree that it could be useful, but I believe we need to be able to spell infinite collections differently than finite collections in the type system. That would solve all of these issues.<br class=""><br class=""><br class=""><blockquote type="cite" class=""><blockquote type="cite" class="">As others have pointed out, 2 & 3 are similar, but have slightly<br class="">different semantics. In the case of 2, we have an implicit boundary<br class="">being filled in: ’n…’ means a range from ’n’ up to that boundary. <br class=""></blockquote><br class="">Presumably, the type of n needs to have a representation for “infinity”<br class="">in some cases, because after all, given `x = n...`,<br class="">`x[x.startIndex...x.endIndex]` must be an infinite range.<br class=""></blockquote><br class="">I could potentially be talked into something like this. How would it work for things like Int, which don’t currently have a concept of infinity? Would it be added?<br class=""><br class=""><br class=""></div></div></blockquote><div><br class=""></div><div>This needs to be part of the Infinite Collection discussion, but you could basically do something like this along similar lines to Optional (not necessarily with this naming…):</div><div><br class=""></div><div>enum InfiniteIndex<T: Comparable>: Comparable {</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>case Finite(T)</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>case Infinity</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>// Comparable requirements</div><div>}</div><div><br class=""></div><blockquote type="cite" class=""><div class=""><div class=""><br class=""><blockquote type="cite" class=""><blockquote type="cite" class="">In the case of 3, we are giving it a different meaning: ’n…’ means<br class="">starting with n, count higher until you run out of numbers… then,<br class="">crash. <br class=""></blockquote><br class="">No, “n...” does not mean that. There's absolutely no counting until you<br class="">combine it with “for...in” in the same way that “n...” doesn't mean<br class="">you're going to slice anything until you combine it with a a<br class="">collection's subscript.<br class=""></blockquote><br class="">Oh, I had thought you wanted conformance of ’n…’ to sequence so you could stick it in things like zip. I have no issue at all with passing it around as a PartialRange, and then using it for whatever as a PartialRange.<br class=""><br class=""></div></div></blockquote><div><br class=""></div><div>To try and clarify what Dave is saying: n… does not mean “starting with n, count higher until you run out of numbers” any more than “0…5” means “count from 0 through 5”. They don’t start counting when you create them any more than they start slicing. In both cases, they do conform to Sequence, so have a makeIterator() method, that returns an iterator that has a next() method, that counts up by one each call, starting from the lower bound. But unlike 0…5, 0… doesn’t return nil once it hits some point, it just keeps going. The crashing happens because you call next too many times on a Bound type that can’t increase any further. for i in n… { } crashing is to be expected just like `var i = 0; while true { i += 1 }` is.</div><br class=""><blockquote type="cite" class=""><div class=""><div class=""><br class=""><blockquote type="cite" class=""><blockquote type="cite" class="">These appear very similar at first glance, but need to be thought<br class="">about subtly differently. For example, we have to be extremely careful<br class="">using #3 with functional map/filter/reduce, <br class=""></blockquote><br class="">Yes, you need to use lazy algorithms if you don't want your program to<br class="">stop.<br class=""></blockquote><br class="">Touche. I kind of feel like we should make sequences/collections from Ranges (and now PartialRanges) lazy by default.<br class=""><br class=""></div></div></blockquote><div><br class=""></div><div>This probably won’t fly. The main reason why all map/filter operations aren’t lazy by default is because of the sometimes-unexpected consequences of passing stateful closures to them (i.e. if the closure mutates some external state, then give different results over multiple passes, a no-no for collections). This problem is universal over any kind of sequence, so it would probably be very surprising to be lazy for some subset of them (other than the explicitly lazy ones, of course).</div><br class=""><blockquote type="cite" class=""><div class=""><div class=""><br class=""><blockquote type="cite" class=""><blockquote type="cite" class="">We need to be really careful with #3 in general, because it breaks so<br class="">many of the implicit guarantees around Collection<br class=""></blockquote><br class="">What implicit guarantees are you saying Collection gives?<br class=""></blockquote><br class="">Basically that I can call the methods enabled by Collection on any collection. That may no longer be safely true with an infinite collection. I don’t want to have a situation when writing algorithms generic over Collection where some portion of the methods I call (e.g. count) may no longer work. Suddenly the standard library is full of minefields where I have to know whether the implementation of a method calls things like ‘count' to know if it is safe to call with my collection.<br class=""></div></div></blockquote><blockquote type="cite" class=""><div class=""><div class=""><br class="">As a straw man example, let’s say someone creates a library with a version of something like zip on collections, which pre-allocates the array buffer based on the size of the collections which are passed to it. In the calculation of that size, the implementer takes the min of the counts of both collections, which is a completely valid thing to do based on the type. It would trap in the case of an infinite collection, so now the users of the function need to understand a bit of the implementation to know when they can use it safely.<br class=""><br class=""></div></div></blockquote><blockquote type="cite" class=""><div class=""><div class=""><br class=""><blockquote type="cite" class=""><blockquote type="cite" class="">That is, partial ranges are just partially defined ranges, and they<br class="">don’t give us a sequence or collection by themselves. In fact, they<br class="">don’t even work as a Range by themselves. To work as a<br class="">RangeExpression, Sequence, or Collection, we need to be able to<br class="">provide that implicit boundary and make it explicit. <br class=""></blockquote><br class="">Again, a partial range of BigInts or Floats is a useful thing I want to<br class="">be able to express. In the former case there's no expressible upper<br class="">bound and in the latter the upper bound is unreachable.<br class=""></blockquote><br class="">Sure. I don’t think I have ever suggested that these wouldn’t be able to be expressed as PartialRanges. Just that if you want to be able to plug it in as a (non-partial) Range or (finite) Collection, you need a way to provide the missing/implicit bound, because that information is required by those types.<br class=""><br class=""><br class=""><blockquote type="cite" class=""><blockquote type="cite" class="">In the case of slicing collections, the collection provides that<br class="">implicit boundary. In the case of types, we would have a protocol<br class="">that defines the implicit/natural boundaries for that type. Then we<br class="">can conditionally conform to Collection based on that protocol. Types<br class="">which are unable to conform to the protocol (like BigInt) would not<br class="">gain the conditional conformance to Collection/Sequence, and would<br class="">have to do it themselves, if desired.<br class=""></blockquote><br class="">BigInt is not supposed to conform to Collection; only<br class="">LowerBoundedRange<BigInt> is supposed to do that.<br class=""></blockquote><br class="">I meant PartialRanges of BigInt, not BigInt itself. I don’t see how it can conform to Collection without an upper bound.<br class=""><br class=""><br class=""><blockquote type="cite" class=""><blockquote type="cite" class="">For clarity, in my mind, PartialRange is a struct which has optional<br class="">bounds and conforms to the RangeExpression protocol. RangeExpression<br class="">is a protocol which defines a function that returns an actual Range<br class="">given a set of concrete bounds to replace any missing ones. In the<br class="">case of slicing a collection, the collection is calling that function<br class="">with its own bounds to get the resulting range. In the case of ‘for i<br class="">in 0…’, the protocol defining the implicit/natural bounds gives us the<br class="">bounds for that function, and the resulting range is used. Ranges<br class="">themselves conform to RangeExpression by just returning self.<br class=""><br class="">Now, things like ‘…n’ work just fine. <br class=""></blockquote><br class="">They would work fine as proposed. In the proposal the type of “...n” is<br class="">different from that of “n…”<br class=""></blockquote>This is something I had not realized. I remove my objection about Sequences, but not Collections.<br class=""><br class=""><br class=""><blockquote type="cite" class="">What do *you* mean by “work just fine?” Would they be collections?<br class=""></blockquote><br class="">Yes, as long as they are also countable.<br class=""><br class=""><br class=""><blockquote type="cite" class=""><blockquote type="cite" class="">We could even have ‘…’ mean “the whole thing” if we decide we want<br class="">that. <br class=""></blockquote><br class="">That's achievable independently of any of the rest of this:<br class=""><a href="https://github.com/apple/swift/blob/unicode-rethink/test/Prototypes/Unicode.swift#L93" class="">https://github.com/apple/swift/blob/unicode-rethink/test/Prototypes/Unicode.swift#L93</a><br class=""></blockquote><br class="">Good to know<br class=""><br class=""><blockquote type="cite" class=""><br class=""><blockquote type="cite" class="">We can conform to collection in most cases.<br class=""></blockquote><br class="">What is “we?” PartialRange? It seems to me that no matter how you<br class="">measure, it can't conform to Collection in most cases, because many<br class="">Comparables aren't also countable.<br class=""></blockquote><br class="">Yes, of course. I didn’t want to complicate my argument by talking about countable everywhere (I only mentioned it once near the beginning). We are only talking about countable things here. Non-countable things can still be PartialRanges and RangeExpressions, of course, but they wouldn’t conform to Sequence/Collection out of the tin.<br class=""><br class=""><br class=""><blockquote type="cite" class=""><blockquote type="cite" class="">For things like BigInt, conformance to Sequence would have to be<br class="">provided explicitly (if desired)… but I view that as a good thing.<br class="">When you go to add that conformance, you again run into issues like:<br class="">what does ‘…n’ do? There are different answers/hacks (maybe you trap,<br class="">maybe you just start at zero or something), each with tradeoffs. It is<br class="">good that those tradeoffs are limited to the edge cases, as opposed to<br class="">spread across all RangeExpressions (breaking the ability to conform to<br class="">collection, for example). My preference would be not to provide<br class="">Sequence conformance for PartialRanges of BigInt at all, forcing the<br class="">user to think about and provide explicit bounds.<br class=""></blockquote><br class="">“Forcing users to think about” bounds on the expressive capability of<br class="">Int runs counter to Swift's design. That ship sailed a long time ago.<br class=""></blockquote><br class="">I want to force users to think about the fact that Conforming to collection means providing explicit bounds. If that isn’t possible because the “Collection” you are trying to make doesn’t have those bounds, then you are fighting the type system.<br class=""><br class=""><br class=""><blockquote type="cite" class=""><blockquote type="cite" class=""><blockquote type="cite" class=""><blockquote type="cite" class="">He hit on exactly what I had been feeling as well (but hadn’t been<br class="">able to put into words until I heard his). The thought is that this<br class="">will help the programmer find an error by trapping, <br class=""></blockquote><br class="">It will also prevent a program from wandering off into<br class="">unpredictable/broken behavior in the hands of a user. If your software<br class="">keeps running but writes a corrupted file, that's usually much worse<br class="">than a hard stop.<br class=""></blockquote><br class="">You forget that my version also has mistake prevention built in… at<br class="">compile time, instead of runtime.<br class=""></blockquote><br class="">No, I don't forget . “Preventing mistakes” by creating a reality that<br class="">doesn't match anyone's mental model when programming doesn't actually<br class="">work. Programmers subconsciously erase the expressive limitations of<br class="">Int from their mental model, in the same way they erase the possibility<br class="">of running out of stack space for making a function call... and the<br class="">explicitly chosen semantics of Swift encourage that erasure. Nothing<br class="">you've proposed changes the basic computational model for Int.<br class=""></blockquote><br class="">I don’t want to change anything about Int. What I really want to change (well tweak, really) is the collection model (so that it takes into account finite vs infinite). But I figure that ship sailed with Swift 3. So instead I am suggesting we tweak this design so that it doesn’t expose those issues.<br class=""><br class="">Thanks,<br class="">Jon<br class=""><br class=""><br class=""><br class="">_______________________________________________<br class="">swift-evolution mailing list<br class=""><a href="mailto:swift-evolution@swift.org" class="">swift-evolution@swift.org</a><br class="">https://lists.swift.org/mailman/listinfo/swift-evolution<br class=""></div></div></blockquote></div><br class=""></body></html>