Subtly Different Linked Lists

If you don't know what a linked list is, then you probably shouldn't be reading this. However, the idea is very simple: a linked list is a list constructed from smaller lists of length two. So a list of length 3 would be constructed as (A, B, C) = (A, (B, (C, Nothing))), where Nothing would indicate that we have reached the end of the list. Most programming languages have some kind of linked list datatype. C++ has the list<T> type in STL, Lisp has the 'list type, Haskell has the [T] type, and RDF has the rdf:List type. We will not consider sequences here, so C types will be left for a future article.

Without any type restrictions, such a pair need not be required to make a list. For example, we could make the structure ((A, B), C), but we could not interpret it as a list. This is exactly how the Common Lisp cl:cons constructor works. The Common Lisp HyperSpec calls anything constructed with cl:cons a list. The special case where the second element of cl:cons is either another cl:cons or a cl:nil is called a proper list. This restriction makes a subtype which can always be interpreted as a list. This subtype corresponds to the lists found in scripting languages such as Perl, Python, and Ruby. RDF lists can also be described as proper lists, since an RDFS-interpretation requires that the range of rdf:rest is rdf:List, so any attempt to make an improper list with rdf:rest will result in an inconsistent RDF graph.

With the restriction that the second part of a pair is a list, we obtain so-called heterogeneous lists, because the members of the list (encoded as the first part of each pair) can be of any type. If we also enforce the restriction that each member of the list is of the same type, then we obtain what is called homogeneous lists for obvious reasons. This subtype is what is found in more strict languages, such as list<T> in C++ and [T] in Haskell. This is an overview of the different kinds of lists we have talked about:

• Improper list (a, (b, c))
• Proper list (a, (b, (c, ())))
• Heterogeneous list [1, "message"]
• Homogeneous list [1, 2, 3]

While we have talked about lists before, restricting RDF's heterogeneous lists to obtain homogeneous lists. However, in this article we are going to consider generalizing RDF's proper lists to obtain improper lists as well. In order to do this, we will make a distinction between cl:Cons the Class and cl:cons the constructor. First we need rdf:List rdf:subClassOf cl:Cons so that they can work together, and then cl:Cons will represent both improper lists and proper lists, and rdf:List will represent proper lists only. To represent an improper list, would would have to be an instance of cl:Cons but not rdf:List. For a heterogeneous list, one would have to be missing the ex:listType property, and for a homogeneous list, one would require the presence of the ex:listType property. This covers all the different list types discussed above.

XML Infoset Models

The XML Information Set (Infoset) defines a number of classes that can be used to model XML documents, and to some extent, this is exactly the model used in other W3C specifications. However, some specifications use less or more than this set of classes, and it is insightful to compare them in order to find common subsets, and exhaustive supersets. In the comparison below "Info" means XML Infoset and "Path" means the XPath/XQuery Data Model. Also, the abbreviations (Y = yes/required, N = no/unspecified, O = optional) are used.

Class Name	XML	DOM	EXI	Info	Path
Attribute	Y	Y	Y	Y	Y
CDATASection	Y	Y	N	N	N
CharacterData	Y	Y	Y	Y	N
Comment	Y	Y	O	Y	Y
Document	Y	Y	Y	Y	Y
DocumentFragment	N	Y	Y	N	N
DocumentType	Y	O	O	Y	N
Element	Y	Y	Y	Y	Y
Entity	Y	O	O	Y	N
EntityReference	Y	O	O	Y	N
Namespace	Y	O	O	Y	Y
Notation	Y	O	N	Y	N
ProcessingInstruction	Y	O	O	Y	Y
Text	Y	Y	Y	Y	Y

Technically, XML Infoset does not include a CharacterData class, but includes a Character class that can be made into a list, which would be isomorphic to the CharacterData class. DOM only requires the optional classes if hasFeature("XML", "1.0") is implemented, so for all XML DOM implementations, these are not optional. Also, EXI requires the Namespace class, even though preserving the namespace prefix strings is optional. XPath has the smallest model, which only supports 7 of the above classes.

It is also interesting to note that Comments, Namespaces and ProcessingInstructions are not forbidden by any of the standards considered above. Also, as you can see, the only classes required by all W3C models are: Attributes, Elements, Documents, Namespaces and Text. Why all the bloat?

The Web Metamodel

The Object Management Group (OMG) likes to consider classes in a 4-level model, in which there is data, metadata (models), metametadata (metamodels), etc. This is way too confusing, so it is fortunate that W3C's standard only take up roughly 3-levels (much like Lisp). The Resource Description Framework (RDF) defines 3 metaclasses that do not fit nicely into OMG's architecture, so they span several modeling levels. This can be seen in the image below, where containment indicates a rdf:subClassOf relationship, and the arrows indicate a rdf:type relationship.

Although there was no indication in the standards that owl:Class is an instance of rdfs:Class, it is a logical consequence, because owl:Class is a subclass of rdfs:Class, and rdfs:Class is an instance of itself. However, the same could be said of rdfs:Datatype, for which there is an explicit mention that rdfs:Datatype is both a subclass and an instance of rdfs:Class. There was also an issue about this, which decided the reason for owl:Class was to be distinct from rdfs:Datatype, not because of some cyclic dependancy stuff. So to keep the model simple, and to minimize cycles, we can ignore the fact that rdfs:Datatype is an instance of rdfs:Class, because this is implied by the fact that rdfs:Class is an instance of itself.

To overview some of the triples in this model, the standards say

• rdfs:Class rdf:type rdfs:Class .
• owl:Class rdf:subClassOf rdfs:Class .
• rdfs:Datatype rdf:subClassOf rdfs:Class .
• rdfs:Class rdf:subClassOf rdfs:Resource .
• rdfs:Resource rdf:type rdfs:Class .

Notably, we have ignored the rdf:Property class, which is part of the model level, not the metamodel level. So the image above is an accurate depiction of the Web metamodel, which consists of only four metaclasses: rdfs:Resource, rdfs:Datatype, rdfs:Class, and owl:Class. Aside from owl:DataRange, this is a fairly complete picture of the Web metamodel. For beginners, the distinctions between these five metaclasses are essential before more indepth discussions take place. If one has any confusion about these distinctions, then nothing else about OWL will make any sense.

Semantic Binary Data

There seems to be quite a few quite a few things missing from XML Schema, RDF and OWL, for example, a single unified type for binary octet-streams. The distinction between the two types used for binary octet-streams has caused more than a few issues during the implementation of these technologies. One indication is that OWL 2.0 is much more complex than the OWL 1.0, and another indication is a note in OWL 2 which talks about the consequences of the distinction between xs:base64Binary and xs:hexBinary. Both of these types are defined to have identical value spaces, but different lexical spaces. Their mutual value space is defined as all finite-length sequences of octets (numbers between 0 and 255).

If the Web metasystem is to understand anything, it must be able to understand octet-streams, since everything else is described in terms of these. Text can be viewed as an octet-stream. Pictures, movies, and music files can all be described as octet-streams, so unless XML, RDF and OWL allow clear expression of the concept of binary data, the application of these technologies will always be limited to vauge and abstract knowledge. There are many ways that a unified binary type could be brought to the XML world. One would be to make a owl:unionOf type that combined the two. Or another option would be to define an rdf:List type, and restrict the types of the members of the list to octets. Since the first option is trivial, and does not provide much structural knowledge about octet-streams, we will not consider it. The second approach does add structural knowledge, and so would be more appropriate for allowing the Web to understand more about octet-streams.

Neither RDF nor OWL allow restricting lists to be of a certain type, so in order to make a class of lists of octets, we must first have the ability to make lists of a type. To this end, we define a new rdf:Property called ex:listType. How would this property be used? To understand this, we must first understand how RDF handles higher-order types. For example, Properties in RDF can be thought of as higher-order types with two parameters. Using a Haskell-like syntax, this would mean (x :: Property a b) would correspond to the triples

_:x rdf:type rdf:Property .
_:x rdfs:domain _:a .
_:x rdfs:range _:b .

which means the appropriate way to encode list types in RDF, such as (x :: List a), would be with the triples

_:x rdf:type rdf:List .
_:x ex:listType _:a .

With this new construct, a unified ex:binary type could easily be defined as (List xs:unsignedByte). Or in simpler terms, the triple (_:x rdf:type ex:binary) would be equivalent to the triples

_:x rdf:type rdf:List .
_:x ex:listType xs:unsignedByte .

This would allow OWL ontologies about file formats, stream protocols, multimedia files, and much more. Using these two higher-order types as examples, it seems all higher-order types can be patterned after these two. Also, since it is abstract enough to represent these higher-order types, it seems that Web technologies are on the right track. RDF and OWL seem to be the most abstract way of expressing modeling ideas, even more abstract than systems like CORBA, IDL and UML. The fact that they allow expressing higher-order types such as those found in Haskell is promising. Perhaps the goal of model compilation (the OMG kind), is much closer than we think. However, the bloat of UML does more to complicate model translation than to simplify it.

Perhaps the simplicity of RDF is all we need.

The Web Metasystem

A recent TEDtalk given by Kevin Kelly came to my attention recently, which has a lot to do with the Web. In it, he gives a very interesting view of the Web, making the analogy that the number of transistors supporting it is about the same number of neurons in the human brain. Kevin Kelly says:

There is only One machine.
The web is its OS.
All screens look into the One.
No bits will live outside the web.
To share is to gain.
Let the One read it.
The One is us.

The most interesting part is when he talks about the complexity of the Web over time. If transistors are akin to neurons, then that means in 10 years the Web will be 2 brains, and in 20 years, the Web will be 4 brains, and so on. The human brain contains about 100 billion neurons, which are much more complex than a transistor in nature. I think that it would take on the order of 10 transistors to approximate a single neuron, making his estimates inaccurate.

In the long run, such an analogy could be viewed in the context of metasystem transition theory, in which evolution is not continuous as it is in Darwinian evolution, but happens in discrete steps marked by a metasystem transition. In this model, regardless of how many transistors there are in the Web at any one point in time, the evolutionary step in which the Web becomes a brain is when a control system emerges. Since the Web was designed by us, and continues to be re-structured by us. There is an obvious answer to what the control system behind the Web is. Everyone. The Web is us.