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.

Webizing Common Lisp

Lisp is a very old language, but it is by no means old in the derogatory sense. Being the oldest language (except Fortran) has given it time to mature and grow into a language capable of amazing things. It has been said many places that Lisp and XML are similar in that they are both data (and if you include XAML and XSLT, code too). I would argue, though, that Common Lisp has vastly more features. However, to make a true comparison, we have to webize Lisp. At the very least, this requires a URI for every symbol. We can start by giving a namespace to all symbols in the COMMON-LISP package.

http://www.lispworks.com/documentation/HyperSpec/

For convinience, we will use the cl prefix for this namespace. We can now start relating Web standards and Lisp, or even writing ontologies using Lisp functions.

Lets compare lists, which are a fundamental part of Lisp. In Lisp, a cons (x . y) would correspond to the RDF graph given by [ a rdf:List ; rdf:first _:x ; rdf:rest _:y ] and cl:nil would correspond to rdf:nil. We can do this with almost all Lisp syntax, except perhaps for the syntax based on the hash (#) symbol. For example, #c(3 4) would correspond to the MathML <cn type="complex-cartesian">3<sep/>4</cn>, so the mapping can get complicated.

Considering such a mapping between Lisp and XML has many advantages. One thing they both have in common is the idea of homogenous data, however, when viewed as two separate syntaxes, they are incompatible, because XML would be a string in Lisp, and Lisp would be a string in XML, losing all structure. When considering such a mapping, it may seem equally advantageous to express XML in Lisp, and conversely, Lisp in XML. If only it were a bijection...