Simple maps/sets: parameterize the comparator?

Mark S. Miller erights at google.com
Wed Dec 28 20:08:04 PST 2011


On Wed, Dec 28, 2011 at 6:48 PM, Mark S. Miller <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]]
>
> 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.


-- 
    Cheers,
    --MarkM
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.mozilla.org/pipermail/es-discuss/attachments/20111228/0f003c8e/attachment.html>


More information about the es-discuss mailing list