Array#sort() implementations not interoperable

Kevin Gadd kevin.gadd at gmail.com
Thu Jun 13 12:16:58 PDT 2013


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. 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, 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.

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. I don't
necessarily think that it is automatically the right choice to say 'do it
yourself' for a problem like this, though it could easily be correct in
this specific case, since Underscore ships a stable sort function. Most
developers probably use jQuery and/or Underscore already to make up for the
small number of useful primitives in the JS standard library, and that's
fine.

-kg


On Thu, Jun 13, 2013 at 9:50 AM, David Bruant <bruant.d at gmail.com> wrote:

> Le 13/06/2013 17:56, Kevin Gadd a écrit :
>
>  I don't really care about the precise language or semantics.
>>
> Maybe you should. In my opinion, that would certainly help having your
> case better understood and heard.
>
>
>  I just don't want applications to break in the wild because an Array.sort
>> implementation's stability changes based on the number of elements.
>>
> A stable sort is just a particular case of an unstable sort. So, if a sort
> is "sometimes unstable", then it is "always unstable". The impression of a
> stability for some cases is just a distraction.
>
> It's also not like if "sort" was confusing like isNaN. "sort" does its job.
>
>
>  That feels like a much easier problem to solve than the problem of some
>> browsers being unstable and some being stable. This is absolutely the sort
>> of thing that would bite me as a JS dev and will bite every person who uses
>> my compiler to convert an application. Why would they test with both small
>> and large element counts?
>>
> They can also read the spec and learn they can't rely on sort stability
> (second sentence of ES5 - 15.4.4.11 !). Specs aren't just for implementors.
> As a web developer, I feel it's a time-consuming yet very healthy exercise
> to read specs to avoid pain later down the road. I wouldn't have said that
> for ES3, but ES5 is decently developer friendly, especially
> http://es5.github.io/#x15.4.4.**11 <http://es5.github.io/#x15.4.4.11>with links and all that.
>
> If people are unsatisfied with the language sort function, maybe they
> should pick a different sort function, implement one that fits their need,
> why not.
> They can even monkeypatch array#sort!
> Why not try a stackoverflow sort [1][2]? Try with "stable sort" ;-)
>
> David
>
> [1] http://xkcd.com/1185/
> [2] http://gkoberger.github.io/**stacksort/<http://gkoberger.github.io/stacksort/>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.mozilla.org/pipermail/es-discuss/attachments/20130613/b6f4910e/attachment.html>


More information about the es-discuss mailing list