Technology
Prototype Trees as JavaScript Components

By "prototype tree" I mean a JavaScript structure that is a tree from the standpoint of the object-to-own-property-value relation, but in which prototype chains and functions may appear. Here is an example of such a structure:

Two operations can be defined which in combination make prototype trees suitable for use as components. The first is instantiation.

Normally, JavaScript instantiation is a one level operation, implemented by Object.create or new, which results in a new object that inherits its properties from the original. For a prototype tree, instantiation involves, very roughly, building a new tree which inherits atomic properties but copies objects. The new tree also retains the structure of prototypical inheritance of the original. The effect is that trees of arbitrary depth can serve as templates from which instances can be spawned at one blow. The details are below.

The second operation is serialization. This is implemented by assigning numeric codes to the nodes of the object graph to be serialized, and then building a JSON-compatible description of the graph, including prototype chains. Here is the implementation.

Together, these capabilities yield a component system in which applications are built by instantiation and assembly from stored elements. After instantiation the prototypes are still "live", that is, any adjustments are inherited by instances. The assemblies have a uniform structure which mates well PrototypeJungle's user interface in which prototype structure is exposed.

The remaining sections cover internals which needn't be plumbed for most coding purposes.

1.Definition

Here is a precise definition of the prototype tree structure.

1) Start with a JavaScript tree of the kind that is expressable in JSON, but allowing, unlike JSON, functions as leaves. Such a structure lacks prototypical inheritance, except from the Javascript core items: Object.prototype , Function.prototype, and Array.prototype.

2) Next, allow prototype chains in the tree. This places another sort of graph over the first. It has the same nodes as the original tree, but adds a new set of edges - edges which join nodes A and B if B is the prototype of A. This second graph is acyclic too, but is rarely connected.

3) Add a special property __parent, where if there is a tree-edge from node A to node B, B.__parent === A. There is a tree-edge from A to B if the value of some own property P on A is B, or if A is an array, and B is an element of A. As a convenience for coding, the special property __name is added too, such that whenever B.__parent === A, and A.P === B with P an own property of A, B.__name === P

4) Now that the __parent property explicitly picks out the tree, we can allow cross tree links. That is we allow A.P = B for any two nodes in the tree.

Prototype trees are also referred to as "items"

2. Instantiation

The algorithm is specified in detail below, but understanding this level of detail is not required to make use of the operation in coding; in practice, one might say, "it does the right thing".

Let T' = T.instantiate(). Then T' is a treewise copy of T, but initially omits its atomic-valued properties, which T' will acquire by inheritance. T' also has the same prototype structure as T, except that chains in T' are anchored back in T. The exact situation is this: consider corresponding nodes N and N' in T and T', that is, nodes appearing at the same paths from the roots of T and T'. Now consider the prototypes P and P' of N and N', that is, P and P' where P=Object.getPrototypeOf(N) and P'=Object.getPrototypeOf(N'). There are two cases. First, P might lie within T. Then P' is defined to be the corresponding node to P, treewise (ie the one at the same path). Second, P might lie outside of the tree T. Then P' is set to N itself. This is what I mean when I say that prototype chains in T' are anchored in T. If you follow a prototype chain C' in T', it will pass through nodes at the same paths as those of the corresponding chain C in T, as long as it is within the tree, but where it exits the tree, then it is anchored back over in T at the node in T from which the exit node in T' was copied.

There is one more step in the algorithm. Consider again the case where P, the prototype of N, lies within T. Then, as described above, N' will inherit from P', not N. In this case, the algorithm specifies that the own atomic properties of N be copied to N', since otherwise they would be, in a sense, lost.

Here is a simple example. iii is the initial tree.

Then after,


jjj = iii.instantiate();
jjj.a.y = 4;

we have:

So, eg, jjj.b.x === 1, since jjj.b inherits from jjj.a, which in turn inherits from iii.a. Note that jjj.b.z has been copied from iii.b.z, by the last-mentioned step of the algorithm mentioned above.

Here is the implementation.

3. An Ammendment

Until now, one aspect of the implementation has been supressed for simplicity of exposition, but it is time to correct this. Prototype trees as described so far contain interior nodes which either inherit prototype-wise from elsewhere in the tree, from components, or are basic objects {}, or arrays []. This is not quite right. Instead of using plain object and arrays, we instead introduce prototypes:

  
pj.Object = {};

pj.Array = [];

To construct a new node for use in an item, the primitives

  
pj.Object.mk = function () {return Object.create(pj.Object)}

pj.Array.mk = function () {return Object.create(pj.Array)}

are defined. (Note that Object.create is used here, and not any form of new. This new-avoidance is a general PrototypeJungle policy, as explained here). This means that we can define tree operations on pj.Object and pj.Array without polluting the basic JavaScript name spaces Object.prototype and Array.prototype. Such pollution would affect all JavaScript objects and arrays, not just the ones used in the PrototypeJungle implementation.

A final, and very useful, generalization can be made. The installation of the PrototypeJungle code base, assigned to window.prototypeJungle, is itself a prototype tree. For any object Y in this tree, it is possible to use Object.create(Y) as an interior node of the item that we are constructing. In serialization, Y is represented by its path within window.prototypeJungle, eg "/Object" or "/svg/tag/g". That is, items can be built over nodes derived by inheritance from arbitrary nodes in window.prototypeJungle.

This ammendment has no effect on the basic definitions. As always, an item is defined as a pair of graphs over the same set of nodes, graphs given by two sorts of edges: own-property-value edges, and isPrototypeOf edges. The former graph, as always, is restricted to be a tree. Before the ammendment, interior nodes either inherited from another node in a tree, or from Array.prototype or Object.prototype, or from a component. Now, interior nodes can inherit from any object in the PrototypeJungle installation as well.