On Sat, Oct 14, 2017 at 6:17 PM, Kevin Nattinger <sw...@nattinger.net> wrote:
> […] >> * A Swift `Sequence` is, to put it simplistically, a thing that can be >> iterated over in a `for...in` loop. If it would make you happy, for the >> rest of the discussion, let's suppose we called the protocol `ForLoopable` >> instead of `Sequence`. >> >> >> ForLoopable is so ugly. Since we’re just iterating over the elements, how >> about, oh, say, `Iterable`? Hey, that looks familiar. >> > > I'm not trying to bikeshed the name of `Sequence`. I'm picking an > intentionally unwieldy name for the purposes of discussing the semantics of > this particular protocol. The point is that the underlying issue has > nothing to do with the name; it can be `Iterable` or it can be `SpongeBob` > for all I care. > > > I’m not trying to bikeshed the name either, The underlying issue is that > (what is currently) Sequence actually encompasses two separate > functionalities, and those functionalities need to be separated with their > separate semantic requirements documented. “Sequence: Iterable,” > “OrderedSequence: Sequence,” “SpongeBob: ForLoopable,” the names are 100% > irrelevant at this point; what’s important is that one is not necessarily > ordered and the other guarantees an order. > > What are the "two separate functionalities"? All the extension methods on Sequence are ways of spelling things that you can write in a few lines of code using a `for...in` loop; they're in the stdlib to allow a more functional style which some prefer. If you accept that a type should support iteration with a `for...in` loop, then what is your basis for claiming that these extension methods are "separate functionalities"? > […] >> >> * If a type `T` conforms to `ForLoopable` and an instance `t` of that >> type has at least one element, then *something* has to be the first element >> in a `for element in t { ... }` loop. Put another way, every instance of a >> type that conforms to `ForLoopable` must have at least one publicly >> observable order (although, intriguingly, I'm not sure it has to be a >> repeatable one). It is possible, therefore, to have a semantic answer to >> the question of which element is `first` or (if finite) `last`; one can >> also `drop(while:)`, etc., and perform lexicographical comparisons. >> >> >> As a side effect of Swift being a procedural language each iteration >> happens to occur in some order, yes, but that order is meaningless and >> reflects nothing about the Set itself. In fact, I’d say that *`first`, >> `last`, etc. are not even defined on the original Set per se, only on the >> specific order that a particular iteration resulted in*. And that order >> is not necessarily predictable, nor necessarily stable, as you yourself >> said. >> >> Consider an Iterable that gives a different order every time it’s >> iterated. >> Should calling `.first` or `last` give a different object every time? >> That’s absurd. >> Should an object lexicographically compare not equal to itself? Even more >> absurd. >> > > What's your basis for saying that such behavior is absurd? It is > explicitly permitted for instances of types conforming to `SpongeBob` to be > single-pass and/or infinite. For a single-pass `SpongeBob`, `first` will > certainly return a different value every time it is invoked. > > > Is `first` mutating? No. Should it be? No! `first` and `last` are a peek > at the state of the object. > You're right, `first` should not be mutating; that's actually an important design consideration, as Ole pointed out, and it's not actually available on `Sequence` for that reason. However, `first { _ in true }` is available and is potentially mutating, as are all methods on Sequence by design. Is `elementsEqual` (or *shudder* lexicographicallyEqual) reflexive? IMO it > clearly should be. Especially with the “lexicographically” part—from > everything I can find, a lexicographical ordering is by definition > reflexive. Do you have a citation for the idea that lexicographical > equality can legitimately be non-reflexive? > Clearly (tautologically?), such a function should be reflexive for any argument ordered with respect to itself. However, if there is no lexicographical comparison possible, then a thing cannot compare lexicographically equal to anything, even itself. A random number generator fulfills all the semantic requirements of conforming to `SpongeBob`, and in fact I do just that in NumericAnnex <https://github.com/xwu/NumericAnnex/blob/master/Sources/PRNG.swift#L53>. `first` gives a different value every time, and a randomly generated `SpongeBob` would unsurprisingly compare lexicographically not equal to itself. > IMO that’s a bug in the implementation; lexicographical equality is reflexive, period. > Presumably the `elementsEqual` method contains something along these lines (take from SequenceAlgorithms.swift.gyb): var iter1 = self.makeIterator() var iter2 = other.makeIterator() > By creating two iterators, you’re mutating while iterating. Turns out there’s even a warning against this in Sequence.swift: /// Using Multiple Iterators /// ======================== /// /// Whenever you use multiple iterators (or `for`-`in` loops) over a single /// sequence, be sure you know that the specific sequence supports repeated /// iteration, either because you know its concrete type or because the /// sequence is also constrained to the `Collection` protocol. /// /// Obtain each separate iterator from separate calls to the sequence's /// `makeIterator()` method rather than by copying. Copying an iterator is /// safe, but advancing one copy of an iterator by calling its `next()` method /// may invalidate other copies of that iterator. `for`-`in` loops are safe in /// this regard. *> The default implementation of elementsEqual is therefore unsafe* because it has the potential for using an invalidated iterator. You are misunderstanding the warning in the second paragraph here. The implementation (not a default implementation, unless I'm mistaken, as it cannot be overridden) makes each iterator using separate calls to `makeIterator()`, just as the documentation tells you to do. Calling next() on one iterator does not invalidate the other iterator, because the second is not a copy of the first. You are, however, right that calling `rng.elementsEqual(rng)` is not advised. It isn't unsafe; it's just not useful. That said, calling `array.elementsEqual(array)` is equally safe and equally useless, and the uselessness of such a reflexive comparison is neither here nor there. On the other hand, if I have a collection of objects that I want iterated > in a particular order, I can use a container that iterates in a specific, > known, well-defined way, and use that to construct the sequence of > objects. That’s clearly an Iterable collection, but the guarantee is > stronger than that. Since it iterates objects in a specific sequence, the > logical way to express that would be `Sequence: Iterable`. Again, we’ve > seen that before. > > Now, since a Sequence is guaranteed to iterate the same every time, > suddenly our `first`, `last`, `drop*`, etc. methods have a meaning inherent > to the collection itself, rather than a specific iteration. > What you call a "Sequence" here would have to be multi-pass, finite, and ordered. > Ordered, yes, but it’s only admittedly poor wording that suggests multi-pass, and I don’t think anything there suggests finite. If a Sequence is "guaranteed to iterate the same every time," then surely it must be multi-pass; what's the alternative? > It would be better to say that the iteration order is well-defined. That > will almost always mean documented, and usually predictable though > obviously e.g. RNGs and iterating in random order will not be predictable > by design. > > That's actually more semantically constrained than what Swift calls a > `Collection` (which requires conforming types to be multi-pass and(?) > finite). By contrast, Swift's `SpongeBob` protocol explicitly permits > conforming single-pass, infinite, and/or unordered types. > > > I think you’re talking about Sequence here, I’ve lost track of your > nonsense by now. Yes, the current Swift protocol named Sequence allows > unordered types. You seem to keep asserting that but not actually > addressing my argument, which is *that allowing Sequences to be unordered > with the current API is undesired and actively harmful, and should* > *therefore** be changed*. > What is harmful about it? > As long as it is possible to iterate over a `SpongeBob`, it is meaningful > to ask what element is first obtained upon iteration or to drop the first > element obtained upon iteration. > > And as long as iteration is not required to be repeatable (and it isn't), > it is perfectly acceptable for these algorithms to return a different > result every time. > > > It is “meaningful” in the sense that it can technically be programmed. The > actual results are meaningless beyond returning or dropping a random* > element. > > *: Don’t nitpick the word “random”, you know exactly what I mean. It’s > just shorter and no less clear than “technically more-or-less deterministic > but not documented, not generally predictable, and probably but not > necessarily consistent from one call to the next." > > I fail to see the issue here. If it's not providing you with utility, then don't use it. Since Collections do guarantee multi-pass iteration, Brent's example of `set.dropFirst().reduce(set.first!, ...)` provides just one instance where an unordered Collection can profitably make use of `first`. Permitting generic algorithms that can operate on either arrays or sets, for example, is the desired effect of having such a protocol; a generic algorithm that takes a Collection can ask for the first element, and in the case of an unordered Collection, an arbitrary element will do just fine. > > `first` is the first object in the Sequence. It doesn’t matter how the >> sequence came to be in that order; it doesn’t matter whether or not the >> sequence has already been iterated or how many times. `first` is the first >> object that is, was, and always will be presented by the Sequence’s >> Iterator. (Until the collection is mutated, obviously). >> >> *To summarize,* >> A Set has no intrinsic order. You can iterate over it, and a specific >> iteration of a set has an order, but that order is not tied to the Set >> itself beyond including all and only the items therein. Therefore, the Set >> itself has no intrinsic `first`, `last`, lexicographical comparison, etc.; >> only its iterations do, and they are not themselves Sets. >> A Sequence does have an intrinsic order. The order of iteration reflects >> the order inherent to the Sequence. Therefore, a Sequence has a `first`, >> `last`, lexicographical comparison, etc. >> >> Just in case it’s not obvious, `Set` here is pretty much interchangeable >> with any other unordered iterable. >> > > What you want to call a "Sequence" is what Swift calls a `Collection`, > with additional restrictions. What you want to be called "Iterable" is what > Swift calls `Sequence` (or now, `SpongeBob`). Clearly, shuffling names will > not make these protocols support any more functionality, so that can be put > aside. > > > No, no, no! What I want to call “Iterable” is specified below. It is about > HALF of what’s currently in Sequence—the half that has to do with > iterating, whence the name. > What I want to call Sequence is precisely what Swift now calls > Sequence—the methods that are in Iterable by virtue of adopting Iterable, > PLUS some methods that only make sense on iterable groups of objects where > the iteration order is well-defined. > > > Now, with that out of the way, why do you think that only `Collection` > types should have `first` and `last`? These helper properties and methods > are simply convenient ways to spell things that can be done with > `for...in`--the whole point of supplying them is to allow people to work > with these types in a more functional style. > > > Apparently “collection" was a bad choice of word. What I clearly meant was > not the current Swift Collection protocol, but rather an unordered > assemblage of objects. UnorderedCollection, perhaps, or if that’s still > going to cause issues, try UnorderedAssemblage. What `first` and `last` > really mean in an UnorderedAssemblage is give me some object from the > assembled objects, I don’t care which one. For which it’s much more clear > to have an `anyObject()` as on NSSet; as another user has pointed out, > `assemblage.makeIterator().next()` works just as well. (I just checked, > and that’s actually how `first` is implemented. But it’s on Collection, > which is guaranteed to be multipass,) > Again, the point of having a protocol-based design is to allow useful _generic_ algorithms to be written; that `first` and `last` would be equivalent to an arbitrary element in the case that a collection is unordered is not at all an argument against these types conforming to `Collection`; if anything, it's an argument for it. Just as `Sequence.underestimatedCount` is equivalent to `Collection.count` for types that conform to `Collection`, or the instance `BinaryInteger.bitWidth` is equivalent to a static `bitWidth` for types that conform to `FixedWidthInteger`. > > public protocol Iterable { >>>>> associatedtype Iterator: IteratorProtocol >>>>> func map<T>(...) -> [T] // Iterable where .Iterator.Element == T >>>>> func filter(...) -> [Iterator.Element] // Iterable where >>>>> .Iterator.Element == Self.Iterator.Element >>>>> func forEach(...) >>>>> func makeIterator() -> Iterator >>>>> var underestimatedCount: Int { get } >>>>> } >>>>> >>>>> public protocol Sequence: Iterable { // Maybe OrderedSequence just to >>>>> make the well-defined-order requirement explicit >>>>> associatedtype SubSequence >>>>> func dropFirst(...) -> SubSequence // Sequence where >>>>> .Iterator.Element == Self.Iterator.Element >>>>> func dropLast(...) -> SubSequence // " " >>>>> func drop(while...) -> SubSequence // " " >>>>> func prefix(...) -> SubSequence // " " >>>>> func prefix(while...) -> SubSequence // " " >>>>> func suffix(...) -> SubSequence // " " >>>>> func split(...where...) -> [SubSequence] // Iterable where >>>>> .Iterator.Element == (Sequence where .Iterator.Element == >>>>> Self.Iterator.Element) >>>>> } >>>>> >>>> >> And just to be explicit, >> struct Set: Iterable {…} >> struct Dictionary: Iterable {…} >> struct Array: Sequence {…} >> etc. >> >> Hopefully at some point: >> struct OrderedSet: Sequence {…} >> > >
_______________________________________________ swift-evolution mailing list swift-evolution@swift.org https://lists.swift.org/mailman/listinfo/swift-evolution