Le 13/06/2013 21:16, Kevin Gadd a écrit :
I have read the ES specs multiple times, and still accidentally
shipped an application that was broken by Array.sort's default
behavior in the wild. I know other people who have had the same
issues, and people who have read the spec and don't happen to have
particular quirks defined in the spec memorized. People are not great
at remembering spec details.
Agreed. The spec on the web. I re-read it the parts I have doubts about
regularly. I write and read doc because spec prose can be tiresome. I
just changed MDN to be very clear on the fact that sorts aren't expected
to be stable. Feel free to contribute to MDN (or WebPlatform at your
preference, both are wikis) whenever you feel that something should be
easily found and shouldn't have to be remembered by developers.
Modern development isn't a person against a programming language. The
web is part of modern development.
Simply demanding that all JS developers in the wild read the spec will
*not* address these issues. Modern application development occurs on
multiple platforms, in multiple languages, using multiple libraries.
No matter how many times the spec is read, if the developer is
regularly writing and thinking in different languages using different
primitives, the primitives that defy trends and act in unexpected ways
will always be a stumbling block. The v8 issue and related issue
reports against Underscore both serve to demonstrate this.
I don't understand why you would intentionally sidetrack a discussion
about a simple problem with academic details. Yes, if your goal is to
write proofs or rigorously demonstrate that your software is correct
all the time, the exact definition of different sort algorithms and
terminology really does matter
I only cared about the words "stable" and "unstable" which are at the
heart of the debate. I'm not sure I understand what academic details
you're referring to and why you're talking about proofs.
A sort being stable is a property on the position of elements which are
considered equal by the sort algorithm. If people want equal elements to
not be moved, they should let the comparator believe that they are equal.
This is not about academics or proof. It's about understanding what
you're doing. Properly understanding the tools at your disposals, the
abstractions. In essence, it's asking the very skills that are required
to build any sort of software.
and yes, it is valuable for people to read the spec. But that is not
remotely relevant to the original post in this discussion thread and
was not suggested by my replies either. This thread *should* be about
whether the ES spec can protect developers from subtle mistakes and
errors by changing the specification of Array.sort. Is the point
trying to be made here that it is impossible for the spec to clearly
communicate that implementations should not do what V8 does, and this
communication is impossible because of the academic definition? You
haven't even once addressed the original core question of whether it
would be possible to switch Array.sort to being stable, and what the
obstacles to that would be.
My (implicit, sorry about that) point was that there is no need to
change the sort function. Just for people to read the spec or doc. No
one is a hero and expected to remember everything, but reading the
second sentence of the Array.prototype.sort spec seems rather low-cost
to me.
There are examples out there in the wild of how difficult it is to
write a performant sort in JS from scratch; you need only look at the
Bugzilla bug about self-hosting Array.sort in Spidermonkey. Or we can
look at the number of *broken* binary search implementations out in
the wild caused by people copying from broken algorithms in textbooks
that behave incorrectly in boundary cases. Please, for the love of
$deity, do not just tell developers to type a query into stackoverflow
and grab the top result.
That was a joke obviously :-) But open source, robust, well-tested
algorithms exist.
Alternate proposal to forcing stable sorts in the spec based on the idea
that "equal" elements shouldn't be equal:
Have the original index of a value passed to the comparator function. A
stable sort can then be a few characters away:
arr.sort(compare)
becomes:
arr.sort((v1, v2, i1, i2) => { return compare(v1, v2) || i1 > i2; })
Where the compare function considers v1 and v2 to be equal (returns 0,
only falsy number), original indices are used to decide which is
greater. This should stabilize the output I think (by fully ordering
elements either by their value when one is greater than the other and by
original index when the 2 values are considered equal by the compare
function)
A simple and optimistic static analysis (no "arguments", no "eval", 3rd
and 4th arg undeclared, etc.) on the comparator body should leave perf
roughly intact.
David
_______________________________________________
es-discuss mailing list
[email protected]
https://mail.mozilla.org/listinfo/es-discuss
