Saturday, May 30, 2009

Set Exponentiation

Exponentiation is the operation of multiplying the same element by itself a given number of times. Defined by the relation yx = yyx − 1, it can be evaluated by multiplication until y1 is encountered, which is just y. It can then be extended to rational numbers by solving an equation, then to the real numbers by the limit of a sequence, then to complex numbers by Euler's formula. Complex exponentiation is one of the most pervasive operations in all of mathematics. It can express all trigonometric functions such as sin, cos, tan, sec, csc, cot, and so on. It can express powers, polynomials, power series, Fourier series (with the help of addition), and much more. Simply put, it's everywhere.

Exponentiation can even be extended to matrices with the help of the equation YX = exp(log(Y)X) for square matrices, where exp and log are defined in terms of the usual power series. Exponentiation can also be extended to sets by noticing that the cardinalities of the domain |X| and codomain |Y| of a function, give |Y||X| = |YX| when exponentiated. This is the idea behind the notation of a power set (denoted 2X), which can be thought of as the set of all functions from X to a boolean (which represents whether or not it is contained). This is illustrated by the following maps in JSON syntax:

  • {"a": 0, "b": 0, "c": 0}
  • {"a": 0, "b": 0, "c": 1}
  • {"a": 0, "b": 1, "c": 0}
  • {"a": 0, "b": 1, "c": 1}
  • {"a": 1, "b": 0, "c": 0}
  • {"a": 1, "b": 0, "c": 1}
  • {"a": 1, "b": 1, "c": 0}
  • {"a": 1, "b": 1, "c": 1}

Clearly, the number of such functions is 8, the cardinality of the domain is 3, and the cardinality of the codomain is 2, and we all know 23 is 8. Following this to its logical conclusion, we arrive at a justification for currying. Currying is the concept that a function of two variables that returns a value is the isomorphic to a function of one variable that returns a function of one variable that returns a value. In set-theory notation this would be ZX×Y = (ZY)X, and in Haskell notation this would be X -> Y -> Z. So just as complex exponentiation is everywhere in Mathematics, so too is set exponentiation everywhere in most computer programming languages, whether or not they recognize the concept of currying. With this in mind, if the theory of algebraic datatypes includes type exponentiation, then pretty much all functions are accounted for. This is the approach that the Z notation specification language, because it defines functions as equivalent to their relations. In other words f(x) = y iff (x, y) is a member of f. To illustrate how set exponentiation characterizes many concepts in programming languages, here is a list of common structures:

  • 2X - Predicates - functions that return a boolean.
  • X2 - If/Then/Else - functions from booleans to a value.
  • Xn - Switch/Case - functions from an enumeration to a value.
  • YX - Unary Functions - functions from any value to any value.
  • XX - Unary Operations - functions from a value to a value.
  • XX2 - Binary Operations - functions from two values.
  • XXn - n-ary Operations - functions from many values.
  • 2X2 - Binary Relations - also called multi-functions.
  • 2Xn - n-ary Relations - also called multi-functions.

This is quite a vast array of functions, which cover most basic structured programming concepts like if/then/else and switch/case. But there is one more: XXX. What does this stand for? Well, conceptually, it takes a Unary Operation over X, and gives a value from X. This is exactly what happens when you evaluate a function at a value, which means the "evaluate at 0" function is in XXX. What's more, is that this is the beginnings of a set-theoretic Tetration (my other website), which I could talk about for hours, but I will save it for another time.

Nonstandard Namespaces

XML namespaces are inherently vendor-neutral, and as such, anyone can define one, even me. So in order to help standardize XML dialects that do not define a namespace, I have put together a list of document types that really should have a namespace, but have not taken the time to define one.

r6rs (Scheme R6RS)
http://www.r6rs.org/final/html/r6rs/r6rs.html
r5rs (Scheme R5RS)
http://www.schemers.org/Documents/Standards/R5RS/
cl (Common Lisp)
http://www.lispworks.com/documentation/HyperSpec/
cs (CS, CEL)
http://www.crystalspace3d.org/2000/cs_world
x3d (X3D, VRML)
http://www.web3d.org/specifications/x3d-namespace
pl (Apple PList)
http://www.apple.com/DTDs/PropertyList-1.0.dtd

There really isn't much to say about these. Some of them are based on resources which describe the XML dialects, whereas others (like x3d-namespace) are a version-neutral namespace (while some X3D implementors have used x3d-3.0.xsd or x3d-3.2.xsd, for which files actually exist). If anyone thinks some of these are poor choices, then let me know, and I'll change it.

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...

Friday, May 22, 2009

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.

Monday, May 18, 2009

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.

Monday, May 11, 2009

Water Shortages

We have water everywhere. Water flows off mountains, collects in lakes, and comprises 70% of the Earth's surface. It is hard to imagine our world without water. So when the idea of it running out is mentioned, it seems so funny that we pay little attention. If we listen, then we find the signs of its disappearance are also everywhere.

Places all across the globe are experiencing short-term water shortages (For example, Putrajaya, Malaysia; Hechi, Guangxi, China; San Diego, California, US; Roane County, West Virginia, US; Montgomery County, Maryland, US; Durham, North Carolina, US). Nations such as Australia and Spain are already noticing significant long-term water shortages, who say

The battles of yesterday were fought over land, they warn. Those of the present center on oil. But those of the future -- a future made hotter and drier by climate change in much of the world -- seem likely to focus on water, they say.

Two great examples of works that discuss a future without water are this Spanish poem (also in English and video), and the legacy of John Titor. While John Titor has made several predictions that turned out to be false (for example, he said Y2K would be devastating), he also predicted that water would become more scarce. This seems to be exactly what we are starting to see in many cities today.

Although a total water shortage is still a very far away, water contamination may be a problem sooner. It is already starting to kill off many spicies to the brink of extinction (for example Fish and Frogs). Modern apathy may compel one to dismiss these, since they're just frogs, but ask yourself: What can we learn from frogs? Frogs (and most amphibians) are both land and water-based creatures, so they represent the future health of both fish and mammals. Since humans are mammals, that means we're next! If that wasn't enough, you might also be interested to know that the science of cryogenics (freezing people and bringing them back to life) rests on the study of tree frogs. Any selfish ego-centric person would love to get frozen when they're 80, and wake up in a hundred years when there's a cure waiting just for them. So regardless of your disposition, selfish or selfless, clean water is important.

We find that there is a growing awareness that water will not be as plentiful as it is now. Lessons given by John Titor and Tree Frogs both indicate we should reevaluate our water situation soon. Avoiding to do so would mean its scarcity would surpass that of both land and oil. Just as oil has been called Black Gold it may be inevitable that in our near future, all power struggles will be for Liquid Gold.

Images Copyright (c) 2007 Associated Press.

Saturday, May 9, 2009

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.

Friday, May 1, 2009

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?