[Amendment] SE-0240: Ordered Collection Diffing

[jrose (Jordan Rose)]

@GarthSnyder

inverse is a noun, but more specifically, it's a participle of the verb invert . If the stdlib were to provide both mutating and nonmutating versions of this operation, the naming guidelines would fairly unambiguously require that they be called invert() and inverted() :

This is the most bikesheddy of bikesheds, but I find this pretty convincing myself.

[Ben_Cohen]

(not exactly review manager hat, more API guidelines interpretation here...)

@GarthSnyder

the naming guidelines would fairly unambiguously require that they be called invert() and inverted():

When the operation is naturally described by a verb , use the verb’s imperative for the mutating method and apply the “ed” or “ing” suffix to name its nonmutating counterpart. [boldface original]

I agree that inverse is more consistent with math terminology. But consistency with the language's own specific naming guidelines is more important than consistency with abstract algebra, especially in a case like this where the options are close to being interchangeable from a linguistic standpoint.

I think the selective quoting of the guidelines is a little misleading here. Both the verb and noun sections start with the words "When the operation is naturally described by a (verb|noun)", whereas your quote of only the verb one implies that the verb form is called out as preferred over the noun form. It isn't.

So my view is there is no indication in the current API guidelines that inverted is preferred over inverse. Any argument that one is better than the other should therefore be on the relative merits of the noun versus the verb, not adherence to the guidelines.

(it's also a reasonable discussion to have in future as to whether we should change the guidelines to have a preference for the verb over the noun... but they don't today)

I do sympathize with the view that formNoun naming is downright nasty and better avoided by the verb when there are naturally mutating/nonmutating pairs. But this proposal doesn't include a mutating one and, I suspect, a mutating version isn't all that likely an addition (as is the case with several other APIs: there is no rule that we have to provide both when one isn't likely to be useful, as discussed during the removeAll(where:) proposal).

[jeremy]

@GarthSnyder

inverse is a noun, but more specifically, it's a participle of the verb invert .

inverse is not a participle of invert (present participle: inverting, past participle: inverted). Etymologically, it is derived from a Latin past participle, but that is irrelevant to its grammatical status in English.

[SDGGiesbrecht (Jeremy David Giesbrecht)]

Great minds think alike ...and even share their name. I had drafted exactly that language lesson yesterday but refrained from actually posting it. Seeing as it earned you 7 hearts, I guess I should have.

[matux]

Can we stop this weirdly obsessive divorce between CS and Math, sit in a circle around a campfire and read together the Curry-Howard correspondence aloud while holding hands, and get over this whole programming isn’t math thing?

[toph42 (Topher Hickman)]

Just to make sure I’m understanding: If I have an ordered collection, make changes, diff the changes, then get the inverse of those changes, applying that inverse will return the collection to its original state?

If so, this seems a very useful feature, and would especially ease the burden on tracking changes for implementing Undo.

[Karl]

@Ben_Cohen

But this proposal doesn't include a mutating one and, I suspect, a mutating version isn't all that likely an addition (as is the case with several other APIs: there is no rule that we have to provide both when one isn't likely to be useful, as discussed during the removeAll(where:) proposal)

I don't understand why there isn't also a mutating version of this. It seems weird that to use this API, you would first need to create a diff (allocating memory), then create an inverse (allocating more memory), and then apply it. If you're using this API for an undo stack, you likely do not care about holding on to the first diff. So it should absolutely be possible to flip the enum's discriminator in-place. Doing that should also result in less ARC traffic for reference-type elements.

Another thing I don't understand is why the fields of the CollectionDifference struct are declared as immutable, preventing anybody from mutating a diff in-place. Diffs that have been mutated to an incompatible state will fail to apply, so this seems overly restrictive.

[Ben_Cohen]

@Karl

So it should absolutely be possible to flip the enum's discriminator in-place. Doing that should also result in less ARC traffic for reference-type elements.

Don't take it as a given that an in-place method is needed for performance reasons in all cases. There needs to be a stronger justification to add to the surface area with mutating/nonmutating pairs than just a generalized "it'll help avoid reference counting".

inverse will be marked as a consuming method, so it should be possible for inversion of a uniquely referenced difference to move elements to the inverse without reallocating or requiring reference counting, resulting in the same performance as the in-place version. Which is not to say that's going to happen on today's compiler, but it ought to happen in the long-run. The inversion itself would need to be written very carefully (and/or rely heavily on the optimizer) to avoid reference counting even in the in-place case because the payloads of the enum need to be taken and transferred into a payload in the opposite enum.

[Karl]

@Ben_Cohen

Which is not to say that's going to happen on today's compiler, but it ought to happen in the long-run.

I've heard this before, but I'm sceptical whether it is really possible.

In any case, I think it would be useful to make the diff's stored properties mutable so you can do the inversion or other operations in-place if you want.

[sveinhal (Svein Halvor Halvorsen)]

@Karl

If you're using this API for an undo stack, you likely do not care about holding on to the first diff. So it should absolutely be possible to flip the enum's discriminator in-place. Doing that should also result in less ARC traffic for reference-type elements.

If all you want is a diff that turns the current state into a previous state, you can replace

let undo = state.difference(from: oldState).inverse

with

let undo = oldState.difference(from: state)

[dabrahams (Dave Abrahams)]

Programming = Math + Memory

—A. Stepanov