Balisage Paper: JSOX: A Justly Simple Objectization for XML

An example of a trivial document portion

It is sadly true that those who argue that JSON, SQL, or other data formats are perfectly adequate for documents, rarely show any examples of realistic documents. Rather, the examples virtually always lack hierarchy; even more frequently lack mixed content (an extraordinarily important omission); often have no relevant order; and usually include nothing notionally like attributes (such as properties of elements as wholes; the occasional exception is IDs).

Such examples are unconvincing.

CSV and its kin cannot handle documents well because they lack hierarchy; because (in theory though seldom in practice) they lack order), and because while they may have names (for fields) they lack the ability to put named objects in meaningful orders. About the best you can do is (Way01, sec. 10):

"h1", "10: The Argonauts"
...
"p", But the hero essayed to hush their laments and assuage their pain
With words of cheer, and he spake,"
"quo", "Take up my war-array,"
"p-resume", "To the thralls, and with downcast eyes did these in silence obey."

Even in this tiny and unusually simple snippet there are many problems: After the quotation the containing paragraph ought to continue on, but because there is no hierarchy some hack must be used to re-start it. The same thing would happen if we tried to separate the section-heading's number and title; reality is far more complex.

Documents require an abstract collection type that permits two important kinds of retrieval at every level of a hierarchy: By order (for global processing such as rendering, indexing, and the like); as well as by position (for many analytic and transformation processes). Moreover, these need to work together. Users must be able to refer to things like the 3rd footnote in chapter 4, the last word of each speech attributed to Medea, all the images, and so on.

JSON is vastly more capable than CSV, and so can make a more credible attempt to represent documents; the presence of hierarchy is particularly helpful. But the unavailability of collections whose members are both ordered and named still makes it awkward, and to my knowledge JSON has never been seriously used for substantial documents, such as books, articles, manuals, and so on. It is hard to see a general solution much cleaner than this, because arrays are needed to keep order, while something else is needed to distinguish attributes (which form a dictionary) from sub-elements and text:

{ "book": [
  { "section": [
    { "title": [
      { "n": 10 },
      "The Argonauts"
    ]},
    { "p": [
      "But the hero essayed to hush their laments and assuage their pain
       With words of cheer, and he spake, ",
      { "quo": [
        "Take up my war-array,"
      ]},
      " To the thralls, and with downcast eyes did these in silence obey."
    ]}
  ]}
]}

This does represent the needed relationships of precedence and containment; but it is far less readable and far more error-prone than XML.

<book>
  <section>
    <title><n>10</n> The Argonauts</title>
    <p>But the hero essayed to hush their laments and assuage their pain
    With words of cheer, and he spake,
    <quo>Take up my war-array,</quo>
    To the thralls, and with downcast eyes did these in silence obey.</p>
  </section>
</book>

Having an abstract collection type that actually corresponds to document topology is simply cleaner. A programming language can provide an appropriate interface to that abstract collection type, and thus enable a much clearer and easier interface to XML than hammering XML-shaped pegs into JSON-shaped holes (however nice the latter's fit for JSON-shaped pegs may be).

Python has a rich collection of abstract collection types; rich enough to reveal that the type XML most needs, while not built in, fits into a slot implied by the relationships of abstract collection types that are already available in Python. This type's properties are predicted by symmetry: the same distinctive properties displayed by types already observed can be combined in another way.

Defining the missing type is one small step for Python. But having taken that step, XML can be treated in Python much as JSON is treated in Javascript. An implementation in this form makes use of XML in Python nearly as trivial as use of JSON in Javascript. And although support for abstract collection types in Python is particularly strong, analogous APIs for XML can be made with little more work in other languages, vastly simplifying use of XML for developers in general.

On DOM

DOM, the Document Object Model, is a standard, widely-used interface to XML structure. The term Object Model can mean either the set of formal properties of some data object, or a collection of classes and APIs for accessing something. DOM involves mainly the second sense: it is essentially an API.

But DOM is not XML, nor the complete object model of XML in the first sense (although it constrains many things about that object model), nor the only way a programmer can access XML data. This paper discusses an alternative way of dealing with XML in programs, yielding the desired simplification for programmers:

On the implementation of abstract collection types

Computer scientists use the notion of abstract collection types to describe various ways in which data items can be aggregated, such as the arrays and dictionaries already discussed. Abstract in this case means that the datatypes are characterized by their storage and access behaviors (or topology, if you will), rather than by how they are implemented. Arrays are distinct from hashes because one indexes items by position, and the other by name (or more properly key).

Most any abstract collection type can be concretely implemented using most any concrete data structure; this is to be expected with Turing Machines. For example, arrays are often implemented using the array data structure (a contiguous series of equal-sized memory blocks), but we have already seen that Javascript is an exception. Sparse arrays such as used in high-dimensionality problems in NLP and physics commonly implement arrays using linked lists or even hashes in order not to waste space on large numbers of empty members.

Similarly, an abstract dictionary can be implemented in a concrete array: Just put each key and item together in an array, and then make an array out of those arrays as shown below. Large instances might be slow to access, but provide all needed functionality:

myDict = [
    [ 1,
        [ "Gouda",     [ "Netherlands" ] ],
        [ "Wisconsin", [ "Wisconsin"   ] ],
    ],
    [ 2,
        [ "Beemster",  [ "Japan"       ] ],
    ],
    [ 3,
        [ "Brie",      [ "France", "USA" ] ],
    ]
]

As should be clear even from this trivial example, implementing an abstract collection type by using a less-than-natural data structure type frequently involves inserting extra layers. In some cases it doubles the number of layers, commonly with alternating arrays and dictionaries. This introduces several problems:

First, it's hard to read. Many developers do not carefully align things as in the example above, although balancing brackets and braces by eye is otherwise difficult.

Second, debugging bracketing errors is difficult because there are so few notations (commonly 1 or 2) being used to express so many distinctions (one per layer).

Third, there are many different ways to introduce the extra layers, so different people will do so in different ways. Therefore, data with the same abstract structure will show up in various concrete forms, and receiving software is unlikely to copy without modification, compromising data portability.

A feature analysis of abstract collection types

There are several different abstract collection types beyond array and dictionary, that have substantial functional differences. The most obvious example is the set, which has quite different semantics because it has neither position nor identifiers, only data items.

The Priority queue (used to choose tasks in order of importance or urgency) is another abstract collection type, which introduces a new feature: Its members are accessed by priority, which is very much like a position in an array; however, unlike with an arrays there can be any number of tasks with the same priority. Dictionaries and sets also fail to encompass priority queues.

As before, introducing more layers is a likely if messy workaround, such as grouping tasks by level and then grouping the levels:

myDict = [
    [ "Brie",       "France",      3 ],
    [ "Gouda",      "Netherlands", 1 ],
    [ "Beemster",   "Japan",       2 ],
    [ "Wisconsin",  "Wisconsin",   1 ],
]

The priority queue is effectively an array but with duplicate positions. The bag or multiset provided in many programming libraries is, similarly, a set but with duplicate entries.

Some programming languages provide versions of some or all these abstract collection types, which are immutable, or restricted from being modified. When applicable, this can enable certain kinds of optimization.

In dynamic contexts queues and stacks are distinct abstract collection types: Their items, after all, are not accessed either by name or by position, but by rule which concern the collection as a whole. However, in immutable contexts (such as data representation) these distinctions are seldom relevant. Either would likely be transmitted as a simple list; the receiving application can do what it likes.

This leads me to suggest the following features for distinguishing abstract collection types:

These features define a space of distinct abstract collection types. The space is not entirely orthogonal; for example, the question of whether there can be multiple entries at the same position is moot if the collection type is not ordered (as dictionaries), and the question of whether there can be multiple entries with the same name is moot if the collection type has no names (as sets).

A few more properties are commonly distinguished, which are less relevant here:

The types and their properties are shown below (parenthesized names are not provided by Python).

Python's OrderedDict has much in common with XML child sequences. It is a variation on dictionaries, that also remembers in what order members were added. Members can be added with the usual od["aardvark"] = "Tubulidentata" syntax, and accessed by the same name. It remembers the order items were added, and can iterate in that order with for k,v in od.items() items.

However, members cannot be set or retrieved by position, nor can they be moved around (except by deleting each and re-adding it to move it to the end). There is not a method to find out what position an item is in. It also cannot support multiple members with the same name as needed for XML. So OrderedDict functions mainly like a regular dictionary, just with a special iterator.

From this table it is obvious that there are two case missing: First, Python does not have multisets (some other languages do). They can be simulated easily with Counter. The last row has no Python type, and no convenient way to simulate it. Sets have neither position nor name; arrays have position but no name; dictionaries have name but no position; but where is the final combination? Where is an abstract collection type that has both name and position, and can have repetitions of at least one of them?

A full-fledged abstract collection type for the final slot turns out to be exactly the structure that XML needs, but that is hardest to simulate using only arrays and/or dictionaries. I call it NamedArray, and it is described in the next section.^[4]

Simplifying XML node typing

Every XML node is one of several nodeTypes, as described by DOM. The fundamental ones are element, attribute, text, processing-instruction, root, namespace, and comment (others have to do with physical rather than logical structure, for example CDATA sections and entity references, which need not concern us here). But elements themselves have types (which DOM calls nodeNames), such as para or chapter. The overloading of type is confusing. The simplification proposed here begins by reducing the variety of node-types:

Let us call the new unified node construct an Elm, since it is largely similar to DOM Element, but subsumes the other nodes types as well. By introducing reserved Elm names such as _TEXT, _PI, _COMMENT, and _ROOT, and by treating the text content of such (empty, leaf) Elms as a special attribute, the inventory of node types drops to just Elms and attributes.

Conceptually, Elm leaves could treat individual characters as child nodes, rather than strings. This changes little; in Python strings are a list type, and all the usual list operations can apply to them anyway.

The attributes of any given Elm form a dictionary, so it is convenient to introduce a specific node to encapsulate an element's attribute list as a whole (including both regular and namespace attributes). This corresponds to the XML Attribute-list.

It has often been suggested that the type name of an XML element is merely a special case of an attribute (it applies to the element as a whole, has a simple token as value, comes from a schema-constrained namespace, etc.). So the element type can be treated merely as an attribute, which we may name _TYPE.

Conveniently, the attribute-list is a familiar type (dictionary), and the Elm has all the positive properties of an array (plus the presence and use of names).

Mapping to Javascript types and syntax

Javascript at least seems to have notions of accessing array members, and of accessing object properties. As we have seen, their syntax and semantics overlap somewhat; but to implement an abstract collection type for XML child sequences we can maintain the convention that the children of an Elm are identified by number and accessed via array notation; while the attributes of an Elm are identified by name and accessed via property notation.^[5]

This is enough to permit a much more palatable syntax for dealing with XML structures in Javascript. Such an implementation may want to support the existing DOM methods and properties as well, to ease the way for existing users.

Mapping to Python types and syntax

Given the same unification of subtypes of Node just discussed, the collection of a node's children fits neatly into the taxonomy of abstract collection types discussed earlier, as a more functional analog to OrderedDict. I call it NamedArray. The basic properties of this new type are:

The specific syntax for these operations is described below.

This provides the most commonly-needed operations for XML. Child nodes can be iterated over by number, and the sequence can be edited by the usual splice, append, and other list operations (as in DOM, but with more natural syntax). However, it is equally easy to iterate over all the comments, PIs, text nodes, elements, or elements of a given type, or simply slice out the elements of a given type. These are extremely common requirements in XML processing.

This idea led the author to investigate what it takes to support an additional collection type in Python, with the native syntactic niceties.

Python doesn’t have only the array[n] notation for arrays. It also provides slicing such as array[start:end] (note that the 2nd argument specifies the entry after the last one desired — this is commonly convenient). It also provides dict[key] notation, and a separate notion of object properties, accessed like object.propname^[6].

Finally, Python has an unusual but very useful array[start:end:interval] notation. For example, array[0:20:2] retrieves every other item from among the array's first 20 entries. This is said to be heavily used with the numpy/scipy scientific and math packages.

As with the abstract collection types, there turns out to be a natural combination of these features which is not built in to Python, but is an excellent fit for XML:

It is often helpful to be able to get all child Nodes that are in fact elements; as noted earlier n["*"] is defined to do this. The reserved Elm types _TEXT, _PI, _COMMENT, _ROOT, and _ATTLIST are simply names when XML uses NamedArray, so NamedArray itself has no awareness of XML convention.

NamedArray is mutable, and does not require homogeneity. The members can be data of whatever type. In an XML document many will be Elms, some of which contain NamedArrays of its own; leaf nodes, however, could be inserted as raw strings, or as separate objects corresponding to DOM's Text, Comment, and PI nodes; NamedArray doesn't care.

This seems, at least to this author, quite intuitive. The various slicing options make the interface considerably higher-level, and the general applicability of [] considerably reduces the number of methods and properties required to achieve DOM's functionality.

The subtlest detail is perhaps the distinction between n["p":1:21] and n[1:21:"p"]. The former retrieves all children named p, and then retrieves the first 20 of those; the second instead retrieves the first 20 children, and then extracts all of those that are named p. That is, the slicing operations go from left to right. This may seem familiar to users of XPath's successive [] filters.

The rest of the XML Nodes

So far we have modeled only the child-sequence requirements of XML, using a new abstract collection type that is not XML-specific, and that fits neatly into the pattern of Python's already-existing types. However, there is more to an XML node than a NamedArray of children: it also has attributes, references to neighboring nodes, properties related to namespaces, and a variety of methods.

To begin with attributes, in Javascript they are probably best implemented as properties; however, this can lead to name clashes in relation to properties that are part of the Node implementation (nextSibling, etc.). Another option, which seems better when it is possible, is to keep them all in a dictionary. The dictionary in turn can be a property, or as suggested below, the first member of the NamedArray.

JSOX has a full-fledged dictionary representing the attribute list as a whole. Because the Elm type (which subsumes DOM nodeType and nodeName) is always present, and considered a reserved attribute, every Elm has at least one member in that dictionary. I favor placing the Attlist dictionary at position 0 in the child sequence, considering it a node in the same way that PIs, comment, and text portions are nodes. Placing it at position 0 fits with where it appears in XML syntax, while also hinting that it is special. With slicing operations, it can be included or excluded at desired. I see this as a rather nice compromise between (a) most programming languages using 0-based arrays, and (b) many people thinking of the first element as #1. Those who disagree can put the attributes elsewhere with no substantial effect on the rest of this proposal.

The other DOM properties (parentNode, etc.) are provided as properties as usual, as are more Python-native synonyms: cloneNode (copy), textContent (toString), appendChild (append), hasChildNodes and hasAttribute (in), removeAttribute (del), removeChild (del), etc.