Simple maps/sets: parameterize the comparator?

Mark S. Miller erights at google.com
Thu Dec 29 12:13:24 PST 2011


On Thu, Dec 29, 2011 at 9:48 AM, Allen Wirfs-Brock <allen at wirfs-brock.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'.
>
>
> This is very close to how sort is actually specified in ES5.1(See
> 15.4.4.11 and particularly step 1 of the first algorithm with numbered
> steps). I'm not sure how this is particularly relevant as we seem to agree
> that it would be impractical to detect misbehaving  sort functions (for
> which we already have a specification) or hash functions.
>

My point is that we could specify that sort takes only the above actions
whether on not comparefn misbehaves (or its other similar preconditions are
violated) -- without any need to detect whether comparefn misbehaves (or
any of its other preconditions are violated). Sort is only require to
terminate and produce a sorted list if all these preconditions hold, as
now, but the only allowed "implementation defined behavior" is the repeated
taking of the above steps, in any order, possible forever, but without any
further such actions once the call to sort completes.

My guess is that *all* current and anticipated implementations of sort
already obey this tighter spec. But by codifying this tighter spec, we
repair a hole in efforts to reason formally and precisely about safety and
security properties of JS.

If anyone knows or can even imagine a realistic counter example to my
guess, please post.

>
>
>
>
>>
>> > 3) we'd like to avoid yet more under-specification. The similar
>> under-specification of Array.prototype.sort is already bad enough.
>>
>>
>> But, I think that the key point here is that if we allow specification of
>> an arbitrary comparator function then we must require that a corresponding
>> hash function is also provided. That seems like a big step down a slippery
>> slope.
>>
>> We should probably avoid pressures for the build-ins to cover all
>> possible use cases. In ES.next we will should have all the primitives
>> necessary for JS programmers to define their own efficient collection
>> objects, including various kinds of hash-tables.  Hopefully some good
>> libraries of such will get written.
>>
>
> I take it you are simply reiterating the desire for a standard system
> provided high entropy object-identity hash that is guaranteed to correspond
> to === and is. I agree (though it didn't make it into ES6), but that's the
> dual of the question Axel is asking.
>
>
> Actually, that wasn't my point. The existence of WeakMap/Map implies the
> existence of an internal object identify hash value.  Using them,
> application level code can associate its own identify associated hash
> values with arbitrary objects and in some cases might even use private
> names to decorate objects with such hash values.  This isn't as simple and
> probably slightly less efficient then using a system exposed identify hash
> value but practical enough for anybody who want to built special has tables
> that need to make use of identify comparisons.
>
> My real point, was that extending the Map specification to allow for use
> of arbitrary comparison functions (and hence arbitrary hash functions) is
> perhaps a step too far because of the issues we were discussing above.  I
> was using the fact that in ES.next application level code can implement
> efficient hash based data structures as a supporting argument to that
> conclusion.
>

I had missed this point, and it is an excellent one. I agree. Let's keep
Map as simple as possible while still providing collection library authors
the primitive they need to author great collection libraries.



>
> Note that I wouldn't object to limited parameterization of  Map that
> allows selection among ==, ===, and *is* as the comparison function as
> these all use the same object identify hash function.
>

Since neither or these so-called equality operators even
define equivalence classes over their inputs, the cannot be the equality
portion of any correct comparator. Please let's omit *this* extension
especially. If our fear of extension is comparator misbehavior, it seems
insane to avoid this by allowing only incorrect comparators.


>
>



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


More information about the es-discuss mailing list