<div><br><div class="gmail_quote"><div dir="auto">On Tue, Oct 17, 2017 at 01:24 Thorsten Seitz <<a href="mailto:tseitz42@icloud.com">tseitz42@icloud.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="auto"><div></div><div><br></div><div><br>Am 17.10.2017 um 03:20 schrieb Xiaodi Wu via swift-evolution <<a href="mailto:swift-evolution@swift.org" target="_blank">swift-evolution@swift.org</a>>:<br><br></div><blockquote type="cite"><div><div>On Mon, Oct 16, 2017 at 8:03 PM, David Sweeris <span><<a href="mailto:davesweeris@mac.com" target="_blank">davesweeris@mac.com</a>></span> wrote:<br><div class="gmail_extra"><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word"><br><div><div><div class="m_7468686282206694046h5"><blockquote type="cite"><div>On Oct 16, 2017, at 1:07 PM, Xiaodi Wu <<a href="mailto:xiaodi.wu@gmail.com" target="_blank">xiaodi.wu@gmail.com</a>> wrote:</div><br class="m_7468686282206694046m_-4820453147793127968Apple-interchange-newline"><div><div dir="auto" style="font-family:Helvetica;font-size:12px;font-style:normal;font-variant-caps:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px"><br class="m_7468686282206694046m_-4820453147793127968Apple-interchange-newline">On Mon, Oct 16, 2017 at 13:15 David Sweeris <<a href="mailto:davesweeris@mac.com" target="_blank">davesweeris@mac.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="font-family:Helvetica;font-size:12px;font-style:normal;font-variant-caps:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><div dir="auto"><br><div>On Oct 16, 2017, at 09:21, Michael Ilseman <<a href="mailto:milseman@apple.com" target="_blank">milseman@apple.com</a>> wrote:<br><br></div><blockquote type="cite"><br><div><br><blockquote type="cite"><div>On Oct 16, 2017, at 8:46 AM, David Sweeris via swift-evolution <<a href="mailto:swift-evolution@swift.org" target="_blank">swift-evolution@swift.org</a>> wrote:</div><br class="m_7468686282206694046m_-4820453147793127968m_-1027262864272297505Apple-interchange-newline"><div><div style="font-family:Helvetica;font-size:12px;font-style:normal;font-variant-caps:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px"><br class="m_7468686282206694046m_-4820453147793127968m_-1027262864272297505Apple-interchange-newline">On Oct 16, 2017, at 07:20, Xiaodi Wu via swift-evolution <<a href="mailto:swift-evolution@swift.org" target="_blank">swift-evolution@swift.org</a>> wrote:<br><br></div><blockquote type="cite" style="font-family:Helvetica;font-size:12px;font-style:normal;font-variant-caps:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px"><br><div class="gmail_quote"><div dir="auto">On Mon, Oct 16, 2017 at 05:48 Jonathan Hull <<a href="mailto:jhull@gbis.com" target="_blank">jhull@gbis.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><div style="word-wrap:break-word"><br><div><blockquote type="cite"><div>On Oct 15, 2017, at 9:58 PM, Xiaodi Wu <<a href="mailto:xiaodi.wu@gmail.com" target="_blank">xiaodi.wu@gmail.com</a>> wrote:</div><br class="m_7468686282206694046m_-4820453147793127968m_-1027262864272297505m_9149467250014663021Apple-interchange-newline"><div><div style="font-family:Helvetica;font-size:12px;font-style:normal;font-variant-caps:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px">On Sun, Oct 15, 2017 at 8:51 PM, Jonathan Hull<span class="m_7468686282206694046m_-4820453147793127968m_-1027262864272297505m_9149467250014663021Apple-converted-space"> </span><span><<a href="mailto:jhull@gbis.com" target="_blank">jhull@gbis.com</a>></span><span class="m_7468686282206694046m_-4820453147793127968m_-1027262864272297505m_9149467250014663021Apple-converted-space"> </span>wrote:<br><div class="gmail_extra"><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><div style="word-wrap:break-word"><br><div><blockquote type="cite"><div>On Oct 14, 2017, at 10:48 PM, Xiaodi Wu <<a href="mailto:xiaodi.wu@gmail.com" target="_blank">xiaodi.wu@gmail.com</a>> wrote:</div><div><blockquote class="gmail_quote" style="font-family:Helvetica;font-size:12px;font-style:normal;font-variant-caps:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><div style="word-wrap:break-word"><div><span><div></div><blockquote type="cite"><div style="font-family:Helvetica;font-size:12px;font-style:normal;font-variant-caps:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px"><div class="gmail_extra"><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><div style="word-wrap:break-word"><div><span><blockquote type="cite"><div><div style="font-family:Helvetica;font-size:12px;font-style:normal;font-variant-caps:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px"><div class="gmail_extra"><div class="gmail_quote"><div> 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.</div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><div style="word-wrap:break-word"><div><span><div><br></div><br><blockquote type="cite"><span><div style="font-family:Helvetica;font-size:12px;font-style:normal;font-variant-caps:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px"> 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.</div></span><blockquote class="gmail_quote" style="font-family:Helvetica;font-size:12px;font-style:normal;font-variant-caps:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><div><div dir="auto"><div><span class="m_7468686282206694046m_-4820453147793127968m_-1027262864272297505m_9149467250014663021m_4152895516219150710m_490495919921887324m_-4349070227452406246m_-6190350261235986415m_-208421619427395776gmail-"><br><span><blockquote type="cite"><div style="font-family:Helvetica;font-size:12px;font-style:normal;font-variant-caps:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px"><div class="gmail_extra"><div class="gmail_quote"><div>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.<span class="m_7468686282206694046m_-4820453147793127968m_-1027262864272297505m_9149467250014663021m_4152895516219150710m_490495919921887324m_-4349070227452406246m_-6190350261235986415m_-208421619427395776Apple-converted-space"> </span></div></div></div></div></blockquote><div><br></div></span></span><span>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 <b>that allowing Sequences to be unordered with the current API is undesired and actively harmful, and should</b> <b>therefore</b><b> be changed</b>.</span></div></div></div></blockquote><span><div style="font-family:Helvetica;font-size:12px;font-style:normal;font-variant-caps:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px"><br></div><div style="font-family:Helvetica;font-size:12px;font-style:normal;font-variant-caps:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px">What is harmful about it?</div></span></blockquote></span></div><br><div>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.</div></div></blockquote><div><br></div><div>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.</div></div></div></div></div></blockquote><br></span></div><div>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.</div></div></blockquote><div><br></div><div>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.<br></div></div></div></div></blockquote><div><br></div></span><div>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).</div><div><br></div><div>I believe it would not be source breaking.</div></div></div></blockquote><div style="font-family:Helvetica;font-size:12px;font-style:normal;font-variant-caps:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px"><br></div><div style="font-family:Helvetica;font-size:12px;font-style:normal;font-variant-caps:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px">That is indeed something slightly different.</div><div style="font-family:Helvetica;font-size:12px;font-style:normal;font-variant-caps:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px"><br></div><div style="font-family:Helvetica;font-size:12px;font-style:normal;font-variant-caps:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px">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`.</div><div style="font-family:Helvetica;font-size:12px;font-style:normal;font-variant-caps:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px"><br></div><div style="font-family:Helvetica;font-size:12px;font-style:normal;font-variant-caps:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px">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?</div></div></blockquote><br></div><div><br></div><div>Something like that. Whatever we do, there will be a tradeoff between speed, correctness, and ergonomics.</div><div><br></div><div>My suggestion trades speed for correctness, and provides a way to recover speed through additional typing (which is slightly less ergonomic).</div></div></blockquote><div><br></div><div>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.</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><div style="word-wrap:break-word"><div></div><div>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).</div><div><br></div><div>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.</div></div></blockquote><div><br></div><div>What is an example of such an "incorrect" generic algorithm that would be made correct by such a scheme?</div></div></div></div></div></blockquote><br></div></div><div style="word-wrap:break-word"><div>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.</div></div></blockquote><div dir="auto"><br></div><div dir="auto">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).</div></div></blockquote><br style="font-family:Helvetica;font-size:12px;font-style:normal;font-variant-caps:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px"><div style="font-family:Helvetica;font-size:12px;font-style:normal;font-variant-caps:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px">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<span class="m_7468686282206694046m_-4820453147793127968m_-1027262864272297505Apple-converted-space"> </span><i>without</i><span class="m_7468686282206694046m_-4820453147793127968m_-1027262864272297505Apple-converted-space"> </span>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.</div><div style="font-family:Helvetica;font-size:12px;font-style:normal;font-variant-caps:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px"><br></div></div></blockquote><div><br></div><div>Sets are values. If you add, remove, or mutate any elements you have a different Set and thus a potentially different ordering of elements.</div></div></blockquote><br></div><div dir="auto"><div>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<span class="m_7468686282206694046m_-4820453147793127968Apple-converted-space"> </span><i>without</i><span class="m_7468686282206694046m_-4820453147793127968Apple-converted-space"> </span>user intervention.</div></div></blockquote><div dir="auto" style="font-family:Helvetica;font-size:12px;font-style:normal;font-variant-caps:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px"><br></div><div dir="auto" style="font-family:Helvetica;font-size:12px;font-style:normal;font-variant-caps:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px">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.</div></div></blockquote><div><br></div></div></div><div>If the semantics of unordered collections (with a lowercase c) and of `Collection` (with an uppercase C) differ on such a basic level, then why are we trying to force them together? I mean, I understand that source-compatibility is important, but so is correctly modeling that which we claim to model.</div></div></div></blockquote><div><br></div><div>Modeling is, by definition, imperfect. The question is, what imperfect model is most useful _to Swift_. The idea is that conforming Set and Dictionary to Collection is on balance more useful than not doing so; that having two protocols, Sequence and Collection, is on balance more useful than having one or three, and that the set of semantic guarantees of Collection are on balance more useful than other possible sets of semantic guarantees.<br></div></div></div></div>
</div></blockquote><div><br></div></div><div dir="auto">That is your idea</div></blockquote><div dir="auto"><br></div><div dir="auto">It most certainly is not my idea.</div><div dir="auto"><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="auto">which is disputed</div></blockquote><div dir="auto"><br></div><div dir="auto">Which part?</div><div dir="auto"><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="auto">and underlined with arguments whereas you keep repeating that Set behaves as dictated by its conformance without giving use cases why this should be useful.</div></blockquote><div dir="auto"><br></div><div dir="auto">Where what is useful? Set’s conformance to Collection? Collection’s semantic guarantees? Having two protocols named Sequence and Collection?</div><div dir="auto"><br></div><div dir="auto">Set having elementsEqual is an emergent property of these three factors. It doesn’t have to be independently useful (though it isn’t useless). The overall design which entails its existence merely has to be superior to the alternative design that doesn’t include it.</div><div dir="auto"><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="auto"></div><div dir="auto"><div><br></div><div>-Thorsten</div></div><div dir="auto"><div><br><blockquote type="cite"><div><span>_______________________________________________</span><br><span>swift-evolution mailing list</span><br><span><a href="mailto:swift-evolution@swift.org" target="_blank">swift-evolution@swift.org</a></span><br><span><a href="https://lists.swift.org/mailman/listinfo/swift-evolution" target="_blank">https://lists.swift.org/mailman/listinfo/swift-evolution</a></span><br></div></blockquote></div></div></blockquote></div></div>