> On Oct 16, 2017, at 1:08 PM, Xiaodi Wu via swift-evolution > <swift-evolution@swift.org> wrote: > > > On Mon, Oct 16, 2017 at 13:15 David Sweeris <daveswee...@mac.com > <mailto:daveswee...@mac.com>> wrote: > > On Oct 16, 2017, at 09:21, Michael Ilseman <milse...@apple.com > <mailto:milse...@apple.com>> wrote: > >> >> >>> On Oct 16, 2017, at 8:46 AM, David Sweeris via swift-evolution >>> <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote: >>> >>> >>> On Oct 16, 2017, at 07:20, Xiaodi Wu via swift-evolution >>> <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote: >>> >>>> >>>> On Mon, Oct 16, 2017 at 05:48 Jonathan Hull <jh...@gbis.com >>>> <mailto:jh...@gbis.com>> wrote: >>>> >>>>> On Oct 15, 2017, at 9:58 PM, Xiaodi Wu <xiaodi...@gmail.com >>>>> <mailto:xiaodi...@gmail.com>> wrote: >>>>> >>>>> On Sun, Oct 15, 2017 at 8:51 PM, Jonathan Hull <jh...@gbis.com >>>>> <mailto:jh...@gbis.com>> wrote: >>>>> >>>>>> On Oct 14, 2017, at 10:48 PM, Xiaodi Wu <xiaodi...@gmail.com >>>>>> <mailto:xiaodi...@gmail.com>> wrote: >>>>>>>> That ordering can be arbitrary, but it shouldn’t leak internal >>>>>>>> representation such that the method used to create identical things >>>>>>>> affects the outcome of generic methods because of differences in >>>>>>>> internal representation. >>>>>>>> >>>>>>>> >>>>>>>>> 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? >>>>>>>> >>>>>>>> After thinking about it, I think the harmful bit is that unordered >>>>>>>> sequences are leaking internal representation (In your example, this >>>>>>>> is causing people to be surprised when two sets with identical >>>>>>>> elements are generating different sequences/orderings based on how >>>>>>>> they were created). You are correct when you say that this problem is >>>>>>>> even true for for-in. >>>>>>>> >>>>>>>> I would not say it is a problem. Rather, by definition, iteration >>>>>>>> involves retrieving one element after another; if you're allowed to do >>>>>>>> that with Set, then the elements of a Set are observably ordered in >>>>>>>> some way. Since it's not an OrderedSet--i.e., order doesn't >>>>>>>> matter--then the only sensible conclusion is that the order of >>>>>>>> elements obtained in a for...in loop must be arbitrary. If you think >>>>>>>> this is harmful, then you must believe that one should be prohibited >>>>>>>> from iterating over an instance of Set. Otherwise, Set is inescapably >>>>>>>> a Sequence by the Swift definition of Sequence. All extension methods >>>>>>>> on Sequence like drop(while:) are really just conveniences for common >>>>>>>> things that you can do with iterated access; to my mind, they're >>>>>>>> essentially just alternative ways of spelling various for...in loops. >>>>>>> >>>>>>> I think an argument could be made that you shouldn’t be able to iterate >>>>>>> over a set without first defining an ordering on it (even if that >>>>>>> ordering is somewhat arbitrary). Maybe we have something like a >>>>>>> “Sequenc(e)able” protocol which defines things which can be turned into >>>>>>> a sequence when combined with some sort of ordering. One possible >>>>>>> ordering could be the internal representation (At least in that case we >>>>>>> are calling it out specifically). If I had to say >>>>>>> “setA.arbitraryOrder.elementsEqual(setB.arbitraryOrder)” I would >>>>>>> definitely be less surprised when it returns false even though setA == >>>>>>> setB. >>>>>>> >>>>>>> Well, that's a totally different direction, then; you're arguing that >>>>>>> `Set` and `Dictionary` should not conform to `Sequence` altogether. >>>>>>> That's fine (it's also a direction that some of us explored off-list a >>>>>>> while ago), but at this point in Swift's evolution, realistically, it's >>>>>>> not within the realm of possible changes. >>>>>> >>>>>> I am actually suggesting something slightly different. Basically, Set >>>>>> and Dictionary’s conformance to Collection would have a different >>>>>> implementation. They would conform to another protocol declaring that >>>>>> they are unordered. That protocol would fill in part of the conformance >>>>>> to sequence/collection using a default ordering, which is mostly >>>>>> arbitrary, but guaranteed to produce the same ordering for the same list >>>>>> of elements (even across collection types). This would be safer, but a >>>>>> tiny bit slower than what we have now (We could also potentially develop >>>>>> a way for collections like set to amortize the cost). For those who need >>>>>> to recover speed, the new protocol would also define a property which >>>>>> quickly returns a sequence/iterator using the internal ordering (I >>>>>> arbitrarily called it .arbitraryOrder). >>>>>> >>>>>> I believe it would not be source breaking. >>>>>> >>>>>> That is indeed something slightly different. >>>>>> >>>>>> In an ideal world--and my initial understanding of what you were >>>>>> suggesting--Set and Dictionary would each have a member like >>>>>> `collection`, which would expose the underlying data as a >>>>>> `SetCollection` or `DictionaryCollection` that in turn would conform to >>>>>> `Collection`; meanwhile, Set and Dictionary themselves would not offer >>>>>> methods such as `prefix`, or indexing by subscript, which are not >>>>>> compatible with being unordered. For those who want a particular >>>>>> ordering, there'd be something like `collection(ordered >>>>>> areInIncreasingOrder: (T, T) -> Bool) -> {Set|Dictionary}Collection`. >>>>>> >>>>>> What you suggest here instead would be minimally source-breaking. >>>>>> However, I'm unsure of where these guarantees provide benefit to justify >>>>>> the performance cost. Certainly not for `first` or `dropFirst(_:)`, >>>>>> which still yields an arbitrary result which doesn't make sense for >>>>>> something _unordered_. We *could* have an underscored customization >>>>>> point named something like `_customOrderingPass` that is only invoked >>>>>> from `elementsEqual` or other such methods to pre-rearrange the internal >>>>>> ordering of unordered collections in some deterministic way before >>>>>> comparison. Is that what you have in mind? >>>>> >>>>> >>>>> Something like that. Whatever we do, there will be a tradeoff between >>>>> speed, correctness, and ergonomics. >>>>> >>>>> My suggestion trades speed for correctness, and provides a way to recover >>>>> speed through additional typing (which is slightly less ergonomic). >>>>> >>>>> You haven't convinced me that this is at all improved in "correctness." >>>>> It trades one arbitrary iteration order for another on a type that tries >>>>> to model an unordered collection. >>>>> >>>>> We could do something like you suggest. I don’t think the method would >>>>> need to be underscored… the ordering pass could just be a method on the >>>>> protocol which defines it as unordered. Then we could provide a special >>>>> conformance for things where order really matters based on adherence to >>>>> that protocol. That might be an acceptable tradeoff. It would give us >>>>> speed at the cost of having the correct implementation being less >>>>> ergonomic and more error prone (you have to remember to check that it is >>>>> unordered and call the ordering method when it mattered). >>>>> >>>>> I’d still be a bit worried that people would make incorrect generic >>>>> algorithms based on expecting an order from unordered things, but at >>>>> least it would be possible for them check and handle it correctly. I >>>>> think I could get behind that tradeoff/compromise, given where we are in >>>>> the swift process and Swift's obsession with speed (though I still >>>>> slightly prefer the safer default). At least the standard library would >>>>> handle all the things correctly, and that is what will affect the >>>>> majority of programmers. >>>>> >>>>> What is an example of such an "incorrect" generic algorithm that would be >>>>> made correct by such a scheme? >>>> >>>> To start with, the one you gave as an example at the beginning of this >>>> discussion: Two sets with identical elements which have different internal >>>> storage and thus give different orderings as sequences. You yourself have >>>> argued that the confusion around this is enough of a problem that we need >>>> to make a source-breaking change (renaming it) to warn people that the >>>> results of the ‘elementsEqual’ algorithm are undefined for sets and >>>> dictionaries. >>>> >>>> No, I am arguing that the confusion about ‘elementsEqual’ is foremost a >>>> problem with its name; the result of this operation is not at all >>>> undefined for two sets but actually clearly defined: it returns true if >>>> two sets have the same elements in the same iteration order, which is a >>>> publicly observable behavior of sets (likewise dictionaries). >>> >>> How is the iteration order of an unordered set or dictionary “publicly >>> observable”? If either is implemented such that it can asynchronously >>> optimize its storage (maybe by rebalancing a tree or merging two >>> non-contiguous array segments or something), its iteration order could >>> change without changing what values it contains. Seems like consecutive >>> calls to “elementsEquals” (or whatever we’re calling it) should return the >>> same answer, if we don’t add, remove, or mutate elements. >>> >> >> Sets are values. If you add, remove, or mutate any elements you have a >> different Set and thus a potentially different ordering of elements. > > From the “value semantics” PoV, yes. But from the “unordered collection of > values” PoV, Sets/Dictionaries, being unordered, are semantically free to > rearrange the in-memory ordering of their elements without user intervention. > > No, they are not semantically free to do so. The semantics of Collection > forbid it, because the iteration order must be multi-pass. As long as the > value is unchanged, the iteration order is unchanged. That is a documented, > public guarantee of the API.
Of the Collection API. But `elementsEqual` is on Sequence, which carries no such guarantee. > > Maybe we need to add a mechanism for expressing the idea of a “value type > which has referential tendencies“ for these “managed” types of values? > > Perhaps a less abstract example would be a “RemoteDictionary”, which maps > each key to a remote server where the value is actually stored... I would > expect it to iterate over its values in whatever order it gets them back from > all the servers. And since dictionaries are unordered and network conditions > & server loads can change (quickly), I wouldn’t expect consecutive iterations > to necessarily be in the same order. > > - Dave Sweeris > _______________________________________________ > 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
