[swift-evolution] [Draft] Rename Sequence.elementsEqual

[Xiaodi Wu]

On Sun, Oct 15, 2017 at 12:33 AM, Jonathan Hull <jhull at gbis.com> wrote:

>
> On Oct 14, 2017, at 9:59 PM, Xiaodi Wu <xiaodi.wu at gmail.com> wrote:
>
> On Sat, Oct 14, 2017 at 11:48 PM, Jonathan Hull <jhull at gbis.com> wrote:
>
>>
>> On Oct 14, 2017, at 9:21 PM, Xiaodi Wu <xiaodi.wu at gmail.com> wrote:
>>
>> On Sat, Oct 14, 2017 at 10:55 PM, Jonathan Hull <jhull at gbis.com> wrote:
>>
>>>
>>> On Oct 14, 2017, at 7:55 PM, Xiaodi Wu via swift-evolution <
>>> swift-evolution at swift.org> wrote:
>>>
>>> > 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?
>>>
>>>
>>> Single-pass, but where two dictionaries/sets with the same elements
>>> would be guaranteed to output the same ordering.
>>>
>>
>> I'm not sure I understand. A single-pass sequence is one where iteration
>> can happen only once because it is destructive. By definition, then, it is
>> not guaranteed to "iterate the same" a second time. Neither sets nor
>> dictionaries are single-pass sequences. Kevin says that his definition of a
>> "Sequence" is something "guaranteed to iterate the same every time," which
>> requires them to be multi-pass, does it not?
>>
>>
>> But if I am comparing two single-pass things, the order can still be
>> defined when they compare that one time.  Single-pass doesn’t mean that the
>> order is undefined.  On the contrary, as you point out, it has a “first”
>> thing, and then a thing after that, and so on.
>>
>> Regardless, most of the objects we are talking about here are multi-pass
>> collections (e.g. sets).
>>
>
> Right, but I'm trying to figure out why Kevin wants a Sequence to "iterate
> the same every time" and in what way that's not simply a Collection.
>
>
> I guess you will have to ask Kevin that.
>

Indeed, I'm asking Kevin that.

 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?

I am not arguing that that is necessarily the right approach, just that we
>> need more thought/discussion around what is actually causing the confusion
>> here: The fact that we are assuming an ordering on something where the
>> ordering is undefined.
>>
>
> The underlying source of the confusion is clear; I'm trying to encourage
> us *not* to talk about it here, though, as it's not a tractable problem for
> Swift 5.
>
>
> I find that problematic.
>
> There are a range of potential solutions that are being offered, from
> renaming the ‘elementsEqual’ to other things besides
> ‘lexicographicallyEquals’ to updating our sequence/collection protocols in
> a minimally source breaking (or even source compatible) way.
>

...to fundamentally changing the protocol hierarchy, which is what I'm
encouraging us *not* to talk about. If it's source-compatible or
justifiably limited to breaking only provably harmful behavior, then of
course we should discuss it.


> Also, I would also argue that if we do find that there are real problems
> with the sequence protocols, now is the time to fix them before the ABI is
> set.
>
> Thanks,
> Jon
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20171015/7afd7a74/attachment.html>