Semantic MathML

I don't know what they were thinking, but there is a much better way to encode MathML in RDF. One can be tempted to assign an RDF property to every element in MathML, but that wouldn't be the OpenMath way. Since MathML3 is getting more and more dependent on OpenMath, it seems appropriate to encode as much as possible using this combined system. MathML3 is split up into several sections: Presentation, Pragmatic Content, and Strict Content. The last one requires only 10 XML Elements to be understood by MathML3 processors, namely: m:apply, m:bind, m:bvar, m:csymbol, m:ci, m:cn, m:cs, m:share, m:semantics, m:cerror, and m:cbytes. This provides for a great economy of thought, and a chance to easily define a total mapping from MathML to RDF. MathML3 already defines a mapping from MathML2 to Strict Content MathML3, so this is the only set of Elements we need to consider. These are the prefixes we will use:

@prefix ari: <http://www.openmath.org/cd/arith1#> .
@prefix fns: <http://www.openmath.org/cd/fns1#> .
@prefix sts: <http://www.openmath.org/cd/sts#> .
@prefix sm: <http://example.com/SemanticMath/> .
@prefix m: <http://www.w3.org/1998/Math/MathML> .

These are the rdfs:Class's we will define:

• sm:Content (all MathML Content)
• sm:Number (for <cn/>, subclass of sts:NumericalValue)
• sm:String (for <cs/>, subclass of xs:string)

and these are the rdf:Property's we will define:

• sm:apply :: Property * sm:Content
• sm:applyTo :: Property * (List sm:Content)
• sm:bind :: Property * (List sm:Content)
• sm:bindOp :: Property * sm:Content
• sm:bindIn :: Property * sm:Content
• sm:error :: Property sm:Error sm:Content
• sm:errorWas :: Property sm:Error (List sm:Content)

Strict Content MathML3 can be translated with the following algorithm:

• <m:cn> NUM </m:cn>
"NUM"^^sm:Number
• <m:cs> TEXT </m:cs>
" TEXT "^^sm:String
• <m:ci> Name </m:ci>
Use blank node identifier (like _:Name)
• <m:csymbol> Symbol </m:csymbol>
Use URIs (http://www.openmath.org/cd/arith1#plus for <m:csymbol cd="arith1">plus</m:csymbol>, or the value of the definitionURL for MathML2)
• <m:share/>
Use URIs
• <m:cbytes> DATA </m:cbytes>
" DATA "^^xs:base64Binary
• <m:cerror> Symbol Content* </m:cerror>

[] rdf:type sm:Error ;
   sm:error Symbol ;
   sm:errorWas LIST(Content) .

• <m:apply> Symbol Content* </m:apply>

[] sm:apply Symbol ;
   sm:applyTo LIST(Content) .

• <m:bind> Symbol Vars* Content* </m:bind>

[] sm:bindOp Symbol ;
   sm:bind LIST(Vars) ;
        sm:bindIn LIST(Content) .

This allows all of Strict Content MathML to be encoded in a set of RDF triples. In order to have the full semantics of MathML and OpenMath there would have to be an OM-interpretation, OM-entailment, and so on, just as there is with every other application of RDF. Although I have not worked out the details of this, an OM-interpretation of an RDF graph that contains these properties would have to treat sts:mapsTo special, and maybe map it to an appropriate rdfs:Class. As an example of how this might be used, this is how the Haskell code (\x -> x + 2) would be translated into RDF using the properties listed above as follows:

_:f sm:bindOp fns:lambda ;
    sm:bind LIST(_:x) ;
    sm:bindIn LIST(
    [ sm:apply ari:plus ; 
      sm:applyTo LIST(_:x "2"^^sm:Number) ]).

Now that RDF has lambdas, the possibilities are endless!

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.

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.

Haskell - Encodings

The ASCII character set has withstood the test of time. However, as the use of computers and the internet becomes global, it is only natural that people speak in their native language. To this end, the Unicode character set was developed to meet this need. Since Unicode uses much more than 255 code points to represent these characters, there are many ways of mapping the much larger space of 4-bytes into a sequence of one or more bytes. The two most popular schemes for doing this are UTFs (UTF-8 and UTF-16), and Guóbiāo (GB2312 and GB18030). In particular, UTF-8 is a very organized and methodical scheme, which makes it well suited for purposes other than text encoding.

XML has become terrifyingly popular in acedemic and commercial circles, and while the overhead that it incurs is usually negligible, there are some who want to use an XML model while keeping a small memory footprint. For this, the W3C has designed a binary XML format called EXI for the transmission of XML documents in binary form. Parts of this standard are not very nice (which is out of the scope of this post), whereas some parts are quite ingenious, like the integer and date-time formats.

Here are some examples of EXI (efficient XML interchange) unsigned integers. EXI is little-endian, so the As are the low bits and the Cs are the high bits.

• 0b0AAAAAAA (EXI encoding for 1-byte)
• 0b1AAAAAAA,0b0BBBBBBB (EXI encoding for 2-bytes)
• 0b1AAAAAAA,0b1BBBBBBB,0b0CCCCCCC (3-bytes)

Here are some examples of UTF (Unicode transformation format) characters. UTF-8 is big-endian, so the Cs are the low bits and the As are the high bits.

• 0b0AAAAAAA (UTF-8 encoding for 1-byte)
• 0b110AAAAA,0b10BBBBBB (UTF-8 encoding for 2-bytes)
• 0b1110AAAA,0b10BBBBBB,0b10CCCCCC (3-bytes)

In the C programming language, all structs can be thought of as parsers. In the Haskell programming language, one can write parsers quite easily with the help of a library called Parsec, which stands for parser combinators. Suppose we have a Bit datatype with the constructors On and Off, and suppose we have definitions for the following functions in Haskell:

bit :: Bit -> Parser Bit
bitstring :: [Bit] -> Parser [Bit]
manyBits :: Int -> Parser [Bit]
oneBit :: Parser Bit

These parsers would allow writing versions of EXI and UTF-8 parsers without any knowledge of characters. An EXI parser can be described as follows

exi :: Parser [Bit]
exi = do
  firstBit <- oneBit
  restBits <- manyBits 7
  case firstBit of
    Off -> return restBits
    On -> do 
      highBits <- exi
      return (highBits ++ restBits)

and a UTF-8 parser can be described as

utf8continue = do
  bitstring [On, Off]
  manyBits 6

utf8 :: Parser [Bit]
utf8 =  do bit Off
           manyBits 7

    <|> do bitstring [On, On, Off]
           highBits <- manyBits 5
           restBits <- utf8continue 
           return (highBits ++ restBits)

    <|> do bitstring [On, On, On, Off]
           highBits <- manyBits 4
           rests <- sequence (replicate 2 utf8continue)
           return (highBits ++ (concat rests))

    <|> do bitstring [On, On, On, On, Off]
           highBits <- manyBits 3
           rests <- sequence (replicate 3 utf8continue)
           return (highBits ++ (concat rests))

As you can see, EXI has a much more elegant implementation in Haskell. Although Parsec was designed to be used on characters and strings, similar techniques can be used for byte-parsers and bit-parsers as shown above. Since C structs can be viewed as byte-parsers, it should be possible to build Parsec style parsers for some common C structs and common file formats like JPEG or MPEG. Bringing this to its logical conclusion, most file formats could be described as some kind of bit-parser or byte-parser, so if such parsers were written in Haskell, what would they look like?