Discuss
  • ES3 quasi incompatibilities

ES3 quasi incompatibilities

# Kris Zyp (18 years ago)

or whether ES4 precludes the use of current ES3 AOP patterns and how that might be solved. Among other things.)

ES3 AOP is in a class of patterns that is not strictly incompatible as ES3 code alone won't break, but ES3 code would no longer behave as expected when interacting with ES4 code. AOP and other patterns in ES3 rely on the ability to add or modify properties on any object. Another example that should be noted is the O(n) algorithm for duplicate item and cyclic reference detection. For example: function findDuplicate(array){ var map={}; for (var i = 0; i < array.length; i++) { if (typeof array[i] == 'object') { if (array[i].__marker) alert('found duplicate'); array[i].__marker = true; } else { if (map[array[i]]) alert('found duplicate'); map[array[i]] = true; } } } This algorithm will fail if an array of objects is passed in that includes instances of non-dynamic (default for user created) classes. Temporarily marking objects with dynamic properties is the only way I am aware of to create O(n) algorithms in ES3 to detect duplicates and cyclic references. I don't think there is anything that can be done about this, it is just a result of static classes. Code written for ES4 can use maps (I think anyway) to solve this problem. This has probably already been discussed, but I just wanted to make sure it was noted. Kris

# Lars Hansen (18 years ago)

Map and intrinsic::hashcode are your friends, indeed. Cleaner solution, too.

<rambling>

For non-dynamic classes you can still use meta::set and meta::get to allow for limited applications like this. I keep thinking that there are use cases for global meta::get and meta::set functions, so just like operator overloading can be done by extending global, generic functions a la intrinsic::+, it ought to be possible to hook into catchalls on the global level, using generic functions.

class C { ... } // not dynamic

meta generic function get(c: C, name) { if (name == "__marker") ... else return nextMethod() }

meta generic function set(c: C, name, val) { if (name == "__marker") ... else nextMethod() } </rambling>

# Garrett Smith (18 years ago)

Function findDuplicate is more like "mark duplicates". The side effect is that it adds a __marker property to each object. As it stands, this function can not be called more than once. The second call might be passed a different array, but containing one of those objects that had the __marker left over. Calling delete in a second loop would make the algorithm 2n (best time). But this is not entirely safe; calling delete on a Host object or window property will throw errors in JScript env; and the property will still be there. So you can set __marker = false, but then you've got a 2N algorithm that leaks a "__marker" to objects in the program.

Unsafe: if (map[array[i]]) // array[i].toString() returns a property name that exists in the prototype chain of map (such as "toString").

Safer: if(map.hasOwnProperty([array[i]])

However, relying on toString in the second part is still unsafe.

findDuplicate([1, "1", !window, "false", new Date()+'', new Date()+'']);

What is really going into this Array?

I think I see the intent, but the function is easily breakable, even if fixed to have a second loop to set marker to null when done; and including the hasOwnProperty fix.

Interop might be an issue, but the code is broken even in ES3.

JavaScript does not provide basic functionality for unique collections.

Consider a case where we have an array-like collection of objects and we want to exclude duplicates. Not uncommon at all.

This could be a shopping cart of unique items (properties), a list of attendees, a ledger of customers, a merge of n number of Lists, containing top-scoring players We want a unique collection.

Using SortedSet: //----------------------------------------------------------- // lis1, lis2 and lis3 are NodeList of LI, in Abstract View.

function compareFn(a, b) { return getScore(a) - getScore(b); }

var players:Set = new SortedSet( compareFn );

players.addAll(lis1); players.addAll(lis2); players.addAll(lis3); var top10:Set = new Set(players); top10.trimToSize(10);

//----------------------------------------------------------- Pros: fast, explicit

What's missing from ES4: Set, SortedSet

Using Array: //----------------------------------------------------------- // Copy of array-like, as array, w/o duplicates. var players = Array.concat(lis1, lis2).concat(lis3).unique(); players.sort(compareFn); var top10 = players.toArray(); top10.length = 10; //----------------------------------------------------------- Pros: compact Cons:

  1. probably not as efficient (using quicksort)
  2. slightly less explicit than the SortedSet example

What's missing from ES4: Array.prototype.unique(); Array.prototype.toArray( arrayLike ) (also as Array.toArray(arrayLike))

ES3 concat and splice are the only way to obtain a copy of an array. These are not explicit uses, but workarounds for a missing arraycopy function.

I don't know how this problem could be solved with a Map. Doesn't feel natural here. Here's my best shot at it:

//---------------------------------------------------------- var players = new Map<Object,Object>();

// Add all the players from each list into the players Map. for(var i = 0; i < lis1.length; i++) { if(!Map.containsKey(lis1[i]) players.add(lis1[i], null); } for(var i = 0; i < lis2.length; i++) { if(!Map.containsKey(lis2[i]) players.add(lis2[i], null); } for(var i = 0; i < lis3.length; i++) { if(!Map.containsKey(lis3[i]) players.add(lis3[i], null); }

var keys = map.getKeys(); var newPlayers = Array.toArray(keys); newPlayers.sort(compareFn); newPlayers.length = 10; //----------------------------------------------------------

Pros: Cons:

  1. not very straightforward or intuitive; not explicit
  2. Verbose, requires two collections and a for loop.
  3. Not efficient

What's missing: Array.toArray( arraylike );

# Yuh-Ruey Chen (18 years ago)

Garrett Smith wrote:

JavaScript does not provide basic functionality for unique collections.

It's trivial to implement an efficient Set class even in ES3 (with certain restrictions on the "type" of the key) - just use objects which are pretty much specialized hash tables (maps from string to values, keys collides with prototype keys). For ES4, we have maps which are hash tables as bareboned as you'll get in the language. I'm not sure why you have all those |!Map.containsKey(lisx[i])| checks in your Map example, since they're totally unnecessary.

A SortedSet is a bit trickier, because that would require some sort of binary search tree to be efficient. But it can be done.

# Garrett Smith (18 years ago)

On Nov 11, 2007 7:18 PM, Yuh-Ruey Chen <maian330 at gmail.com> wrote:

Garrett Smith wrote:

JavaScript does not provide basic functionality for unique collections.

It's trivial to implement an efficient Set class even in ES3 (with certain restrictions on the "type" of the key) - just use objects which are pretty much specialized hash tables (maps from string to values, keys collides with prototype keys). For ES4, we have maps which are hash tables as bareboned as you'll get in the language. I'm not sure why you have all those |!Map.containsKey(lisx[i])| checks in your Map example, since they're totally unnecessary.

Where is the string value in something like: {a:1}

I wrote an Array-backed sorted set before but ended up not using it. I did not like all the runtime checks and found another way to do what I wanted to do.

# Lars T Hansen (18 years ago)

On Nov 11, 2007 6:01 PM, Garrett Smith <dhtmlkitchen at gmail.com> wrote:

Function findDuplicate is more like "mark duplicates". The side effect is that it adds a __marker property to each object. As it stands, this function can not be called more than once. The second call might be passed a different array, but containing one of those objects that had the __marker left over. Calling delete in a second loop would make the algorithm 2n (best time). But this is not entirely safe; calling delete on a Host object or window property will throw errors in JScript env; and the property will still be there. So you can set __marker = false, but then you've got a 2N algorithm that leaks a "__marker" to objects in the program.

The standard trick to avoid resetting the mark is to treat it not as a bit, but to set it to a distinguished value every time (a serial number).

Just to complete the example for ES4,

function findDuplicate(array) { let m = new Map.<*,null> for ( let i=0, limit=array.length ; i < limit ; i++ ) { let v = array[i] if (v is Object) { if (m.has(v)) alert("Found duplicate") else m.put(v,null) } } }

Obviously that's reentrant and all that.

By default, Map uses intrinsic::hashcode and intrinsic::=== to handle objects, so the above code handles object identity without any string conversions, and unless intrinsic::hashcode is out to lunch, it's roughly constant time, giving an O(n) algorithm for duplicate finding. Rehashing behind the scene may in practice make it more expensive, of course. (We've not seen fit to add a method to give a hint to the Map about how large it may need to be.)

Consider a case where we have an array-like collection of objects and we want to exclude duplicates. Not uncommon at all.

Map provides a collection of key-value mappings without duplicates; you can always use "null" for the value as I did above. It does not have the Array methods, nor do the generic Array methods work on it, because you can't talk about elements in terms of their indices.

On the other hand, "Array-like" and "exclude duplicates" don't combine all that well, maybe. I suspect what you're saying is an object that behaves like an Array so that the Array generic methods can be used on it, but to which elements are added by special functionality, or excluded later by calls to unique().

It's pretty simple in ES4 to create objects that behave like Arrays in their Get/Put/HasProperty/Delete behavior. For example, here's a sketch for an implementation of UniqueArray.<T> that does not store

duplicates:

class UniqueArray.<T> { private var m = new Map.<uint,T> private var s = new Map.<T,null> private var _length = 0;

// meta methods intercept all requests for unknown properties

meta function get(n) { if (m.has(n)) return m.get(n) return undefined }

meta function set(n,v) { // do not store duplicates if (!(s.has(v))) m.put(n,v) if (n >= _length) _length = n+1 }

meta function has(n) m.has(n)

meta function delete(n) m.remove(n)

function get length() _length

function set length(n) { if (n < _length) { for ( let i=n ; i < _length ; i++ ) m.remove(i) _length = n; } } }

What's missing from ES4: Set, SortedSet

type Set.<T> = Map.<T,null>, though obviously does not have

intersect, union -- clearly a weakness. Good enough in simple cases.