On Wed, Dec 28, 2011 at 4:23 PM, Allen Wirfs-Brock <al...@wirfs-brock.com>wrote:
> > On Dec 27, 2011, at 10:20 AM, Mark S. Miller wrote: > > > Hi Axel, yes, I would like to extend their constructor in this way. > However, I'm not sure how to spec it -- help appreciated. The problem is > that the comparator needs to provide both an equivalence operation and a > corresponding hash operation. When these agree, all is well. What should we > specify happens when passing in a misbehaving comparator? The dilemma is > that > [responding out of order] > > 2) having a deterministic collection misbehavior in the face of > comparator misbehavior seems hard, and > > But it isn't clear that this is a requirement. > I agree. In fact, I think such detection is likely hard enough that it is effectively a requirement that the spec not obligate an implementation to detect such misbehavior. > > 1) detecting misbehavior is expensive, > > For sort comparison function we simply say that the behavior is undefined > for a misbehaving comparison function. It isn't clear that this has cause > any significant problems or that it is very likely that we will require > detection of misbehaving sort comparison functions. > 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'. > > > 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. What do you think of my approach to limiting the possible misbehavior of sort? -- Cheers, --MarkM
_______________________________________________ es-discuss mailing list es-discuss@mozilla.org https://mail.mozilla.org/listinfo/es-discuss