Simple maps/sets: parameterize the comparator?

Allen Wirfs-Brock allen at wirfs-brock.com
Thu Dec 29 09:48:07 PST 2011


On Dec 28, 2011, at 6:48 PM, Mark S. Miller wrote:

> ...
> 
> Likewise, I expect that detecting misbehavior sort comparison functions is too hard to be practical. However, I strongly disagree that the current underspecification isn't a problem. How undefined is this behavior? (Actually, the language in 15.4.4.11 is "implementation defined", which isn't really any better.) Can [1,2,3].sort(function(){return 1;}) evaluate to the password of the current user? Can it violate same origin restrictions or memory safety? Can it launch the nukes? If so, then none of our reasoning about security (whether conventional or ocap) or safely of any kind is sound. Rather, we get away with such reasoning because we all share an unstated model about the real limits on this misbehavior. Since *any* sound reasoning about safety or security depends on this shared understanding, it behooves us as authors of the specification to codify these limits.
> 
> 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.


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

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.  

Allen
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.mozilla.org/pipermail/es-discuss/attachments/20111229/7bc00a31/attachment.html>


More information about the es-discuss mailing list