5

So far, there seem to be two opposing solutions to immutability in Javascript:

  • immutable.js
  • seamless-immutable

immutable.js introduces their own (shallowly) immutable objects that are incompatible with the default javascript protocols for objects and arrays.

seamless-immutable uses POJOs that are completely immutable without any magic, but do without structural sharing.

It would be great to combine the best of both worlds. Could immutable prototype chains/trees be a proper solution?

The underlying prototype mechanism gives hope:

var a = [1, 2, 3];
var b = Object.create(a);

b[0]; // 1
b.map(function (x) { return ++x; }); // 2, 3, 4 

b.push(4, 5, 6); // initial assignment of b
a; // 1, 2, 3
b;  // 1, 2, 3, 4, 5, 6

for (var i = 0; i < b.length; i++) {
  console.log(b[i]);
} // 1, 2, 3, 4, 5, 6

a[1] = null; // prototype mutation
a; // 1, null, 3
b; // 1, null, 3, 4, 5, 6

b.unshift(0); // instance mutation
a; // 1, null, 3
b; // 0, 1, null, 3, 4, 5, 6 !!!

Whenever a mutation (unshift) of the current instance (b) makes it impossible for its prototypes to provide their values, the js engine seems to copy these values straight into the instance automatically. I didn't know that, but it makes total sense.

However, working with immutable (keyed/indexed) objects one quickly encounters problems:

var a = [1, 2, 3];
Object.freeze(a);
var b = Object.create(a);
b.push(4, 5, 6); // Error: Cannot assign to read only property "length"
Object.freeze(b);

This one is simple: The length property is inherited from the immutable prototype and hence not mutable. Fixing the problem isn't hard:

var b = Object.create(a, {length: {value: a.length, writable: true}});

But there will probably be other issues, in particular in more complex, real world scenarios.

Maybe someone have already dealt with this idea and can tell me, if it's worth reasoning about it.

Aadit's answer to a related question and Bergi's comment on it touches my question without giving an answer.

Community
  • 1
  • 1
  • I feel like this would make a **really** interesting discussion, but isn't exactly the right kind of discussion for Stack Overflow (which is more for specific problems). Once you hit 20 rep you should totally come and discuss it with us at [chat](https://chat.stackoverflow.com/rooms/17/javascript). – Madara's Ghost Nov 07 '15 at 16:01
  • Yeah, I didn't want to get into this discussion with Aadit over there, but I'm happy to provide an answer here. And hope that @AaditMShah can give some counterpoints, I'd like to learn something new :-) – Bergi Nov 07 '15 at 16:52

2 Answers2

0

the js engine seems to copy these values straight into the instance automatically

That's because all the array methods (shift, push etc) just use assignment to indices (and fortunately, to .length, which isn't automatically updated on non-arrays). As you know, assignment just creates a new property on the inheriting object, even if the prototype had that property (unless it has weird attributes, like in your frozen-length example).

Regardless, your actual question was

Could immutable prototype chains/trees be a proper solution?

No. The problem is that a prototype chain is never garbage-collected. The engine doesn't know that you "don't need" the prototype any more once all the inherited properties are overwritten by your new "mutated" instance - and keeps it around forever.
You'd need to manually garbage-collect (dereference) it, which is just what immutable.js with its structural sharing does. Only that mutating the [[prototype]] is a bad idea, so you better manage your structures in other ways and do property lookup manually.

Community
  • 1
  • 1
Bergi
  • 630,263
  • 148
  • 957
  • 1,375
  • I refered to the idea of shared prototypes when I mentioned prototype trees. This is in fact misleading and clumsy in the prototype context. Of course, each javascript object can have only a single direct prototype. Thanks for the clarification! –  Nov 07 '15 at 18:36
  • @IvenMarquardt: Ah, I see. It's just that there are other languages that indeed allow multiple prototypes to inherit from, and swap them out much more easily, so I wanted to to assure you weren't confused by those. – Bergi Nov 07 '15 at 18:37
  • Yes, `[[prototype]]` isn't an option. I guess you can't prevent memory leaking, at least not on this low level. –  Nov 08 '15 at 19:59
  • Maybe you can determine the relative complement of an instance i and its prototype p regarding their properties at creation time of i. Since i and p are guaranteed to remain unchanged (just like all other prototypes within the chain), these computation should take place only once (at creation time of new instances). If no difference is left or a certain threshold reached, i is deeply copied and marked for GC. If i holds no more implicit or explicit refs, it gets garbage collected. This sounds complicated and I don't have a clue, if it's practical in any way. –  Nov 08 '15 at 20:00
  • I just realized that you loose array in `[[Class]]` when you subclass arrays and therefore break `Object.prototype.toString.call`. Too bad! –  Nov 08 '15 at 21:01
  • Yes, you might be able to come up with a pattern that describes this threshold and whose computation is reasonably efficient (amortized `O(1)` should be achieved!), but it'll probably get much more complicated and less efficient than sharing structures without prototype inheritance. – Bergi Nov 08 '15 at 21:32
  • `Array` subclassing is a solved problem with ES6, so this should not be a concern for any prototype implementation of such a sharing pattern – Bergi Nov 08 '15 at 21:33
0

In addition to memory leaking you encounter further problems when you use the prototype system for structural sharing:

  • unfavorable lookup time in long prototype chains
  • in ES5 loss of [[DefineOwnProperty]] in connection with arrays

Lookups in hash tables are usually very efficient. If an object is frequently mutated, however, very long prototype chains may arise. In the worst case the entire chain must be traversed. If such behavior occurs on a regular basis, it can have an adverse effect on performance.

Array subclassing leads to the loss of [[DefineOwnProperty]]. This internal method is responsible for synchronizing the length property with the actual number of elements in arrays:

function A() {}
A.prototype = Array.prototype;
var a = new A();

a[0] = 0, a[1] = 1;
console.log(a.length); // 0
a.length = 2;
console.log(a); // [0, 1]
a.length = 1;
console.log(a[1]); // 1

[opinion]I am convinced that all these problems can be solved and that with incredibly little code, a tiny API and a shallow learning curve. Such a system would likely not be as efficient as immutable data structures based on vector or hash map tries. But it would be much more efficient than mere copying of objects.[/opinion]