Simple maps/sets: parameterize the comparator?

David Bruant bruant.d at gmail.com
Thu Dec 29 05:58:55 PST 2011


Le 29/12/2011 05:08, Mark S. Miller a écrit :
> On Wed, Dec 28, 2011 at 6:48 PM, Mark S. Miller <erights at google.com
> <mailto:erights at google.com>> wrote:
> [...]
>
>     For example, regarding sorting, leaving aside sparseness, I
>     suspect our shared model is that any sort algorithm implementation
>     itself takes only the following observable steps, but in some
>     arbitrary order and not necessarily terminating:
>
>
>     obj.[[Get]](String(i)), where i is an integer && 0 <= i && i < len
>     (recall that len is already the result of array.[[Get]]('length'))
>     obj.[[Put]](String(i), x), where i as above, and x is only a value
>     previously gotten with a [[Get]]
>     ToNumber(comparefn(x, y)), where x and y are only values
>     previously gotten with a [[Get]]
>
More explicitely, here:
comparefn.[[Call]] with 'this' bound to 'undefined'.

David
>
>
>     To adjust for sparseness, the sort function may also invoke
>
>     obj.[[HasProperty]](String(i))
>     obj.[[HasOwnProperty]](String(i)) // perhaps? I see no mention of
>     it in the algorithm
>     obj.[[Delete]](String(i))
>     obj.[[Put]]('length', String(i))
>
>     Notice that this specification does not assume away the
>     possibility of arbitrary side effects or I/O caused by the
>     comparefn or by accessor properties at obj indexes or 'length'.
>
>
> And a call to sort stops performing any of these observable actions
> once it completes (whether by returning or throwing).
>
> Are there any implementation freedoms that we actually wish to allow
> that are outside the above limits? I cannot think of any.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.mozilla.org/pipermail/es-discuss/attachments/20111229/ac205c84/attachment-0001.html>


More information about the es-discuss mailing list