To test our code, we need a couple of things: we need to write tests, we need a framework to run our tests in, and we need to automatically run this framework regularly. The number of Javascript test frameworks is large these days, and we started by reviewing a few. We finally settled on QUnit. It provides a few simple functions to write tests, and a clean and useful page to present the results.

We then integrated QUnit into our work flow. We use a simple, home grown module system to write our Javascript. It uses keywords like Module, Class and Static to easily build modular code. We defined a new annotation, Test, to define a test in a module. All these tests are automatically collected. A separate test runner module imports the modules to test and calls a single function to run all tests in a module.

This provided us with a simple way to write tests. But if this was all, people would forget to run the tests, the tests would start failing without anyone seeing it, and the effort to write the tests would be wasted. To prevent this from happening, we wanted to integrate the running of tests in our work flow. Luckily, John Resig has written TestSwarm.

Traditionally, integrating Javascript tests in a build process or as a commit hook has been difficult, since Javascript generally depends on the browser to run. Different browsers have different quirks that might make your Javascript behave differently, and your code might also depend on the DOM, which is only available in a browser. However, you don’t want your developer machine to start many different browsers on each build or commit, and your server might not even have a GUI.

TestSwarm is a solution to this problem. It provides a central server, and new tests to be run can be pushed to this server. Clients willing to run tests can also connect to it, and are given tests to run. Results are reported back to the server. This allows TestSwarm to build reports, showing test results per browser for each test run. In our case, our server pushes a new test run to the server on each commit set that is pushed. We have a few browsers open pointing to our TestSwarm instance, which run these tests. This means that testing doesn’t get in our way, but if something breaks, we can easily see which commit broke it and on which browsers.

The final piece in our testing puzzle takes its inspiration from the Haskell world. QuickCheck is a tool that performs randomized testing. You supply a function testing a certain property of your code, and it generates random inputs of increasing size. For example, if you have written a function reversing a list, you can state the property (function) that given a list (the input argument which is randomly generated), reversing it twice produces the original list.

A Javascript version of QuickCheck exists, and we had a good use case. We use so-called reactive lists, that is, lists which can be connected to keep each other updated. For example, we can create two of these lists, and connect one to the other saying it is always the reverse of the first. When elements are inserted into the first, it sends an event to the second, which processes it, and generates an appropriate insert for the reversed list. The interesting thing is that we have an easily testable static property. Regardless of the mutations on the original list, at any point in time, the reverse of its values must be the same as the values in the output list.

QuickCheck has quickly proven its worth in testing these reactive list functions. Since it generates random values of increasing size, it quickly and reliably finds all the corner cases where bugs like to hide. We’ve written a small helper function around QuickCheck to integrate it with QUnit, so that we can write code like this:

function splitTest ()

{

  var l = new R.List();

  var splitfun = function (e) { return e === 1; }

  var s = l.split(splitfun);

  quickcheck([arbListOp(arbRange(0, 5))],

    function (c, op)

    {

      op(l);

      c.assert(QUnit.equiv(A.split(splitfun, l.unR()), s.unR()));

    });

}

This creates two lists: an input list l, and an output list s that is the result of splitting the input list at elements equal to 1. We then call the quickcheck function, which is our helper function. It takes a list of generators as a first argument. In Haskell, these generators can be derived from the types, but here, we have to supply them. In this case, we generate operations on reactive lists. This generator for list operations takes a generator as an argument, which it uses to generate list elements to insert. In this case we generate random integers between 0 and 4 to make sure we get at least a few 1’s.

The second argument to the quickcheck function is the test function to run. It gets a QuickCheck object as its first argument, followed by the output from all the generators. In this case it gets a function representing an operation on a reactive list. We perform this operation on the input list by calling the function. We then check if the values in the input list (the function unR performs a deep conversion from reactive to normal lists) split on 1’s are equal to the values in the output list. Here, A.split is a static splitting function, and QUnit.equiv performs a structural equality check on arrays.

Thanks to the availability of these three open source tools, setting all this up only took a few days, and has provided us with a testing setup that works, but doesn’t get in our way. In the future, we will probably also start testing DOM and user interface related code; hopefully, that will work just as well.

This post is really about Javascript, which will be the target language of this library. But most of the techniques and underlying thoughts actually come from a statically typed functional programming background. While reading this post it might be interesting to continuously keep in mind the types of the functions, which makes it much easier to understand what is going on and how this framework might be extended with more interesting transformations.

For the Haskell programmer: the framework we are about to describe here is very similar to the list arrows of the Haskell XML Toolkit. Looking at the documentation of this package might gain some additional insight.

Some functions we will see are selection functions that can be used to select parts of a document, other functions can be seen as filtering functions that exclude parts of the output, some are creation functions that introduce new structure in the output. In these post we call all of these function just transformations. The resulting framework is some hybrid comparable to XPath and XSLT.

Primitive transformations

Let’s first look at the structure of the transformations performed in XPath and XSLT. Both languages can be seen as ways of describing a function that takes one input, the context node, and produces a list of outputs, a node set. Primitive examples of such transformation functions are: getChildren (/* in XPath), getParent (.. in XPath) and getID (@id in XPath). Implementing these three functions in Javascript is very easy:

function getChildren (ctx) toArray(ctx.childNodes);

function getParent   (ctx) [ctx.parentNode];

function getID       (ctx) [ctx.getAttribute("id")];

For the ease of reading most functions in this post are written down as Javascript 1.8 lambdas. This syntax, which leaves away the braces and the return statement of functions, is currently only supported by Firefox’s SpiderMonkey engine. Note that all three functions have exactly the same type, they take one context node as input and return an array of nodes (node set) as output. There is a good reason to have a consistent type signature for these primitive transformations: this allows us to easily compose multiple primitive operations into more advanced transformations.

Sequential composition

To illustrate composition, lets see how we would like to write down a transformation that selects all the grandchildren of a context node. Ideally we would like to sequentially compose two invocations of getChildren into one. With sequential composition we mean applying some transformation to the result of some earlier transformation. Something like this:

var getGrandchildren = seq(getChildren, getChildren);

But what would the seq function look like? To make it more easy to come up with the correct implementation of the seq function it might help to write down the types of all the functions involved and work from there. We first write down the Haskell style type signatures for our getChildren function, which takes one context node and produces a list of child nodes:

getChildren :: Node -> [Node]

Because we want the result of the expression seq(getChildren, getChildren) itself to be transformation with the same type again, the type of seq must be:

seq :: (Node -> [Node]) -> (Node -> [Node]) -> (Node -> [Node])

Which means: take two transformations as input and produce one transformation as output. By only looking at the type we can already deduce the following skeleton of the seq function:

function seq (tr0, tr1) function (ctx) /* [some nodes] */ ;

Note that this function is higher-order, it takes two functions and returns a new function. Now we only have to fill in the gap, which we can do by looking at the desired semantics. In the case of the getGrandChildren function we want to apply the first getChildren transformation to the context node and then apply the second transformation (getChildren again) over all the results of the first transformation and group together the results. Translating this to code would become something like: apply tr0 to ctx, than map tr1 over all these results and concatthe output.

function seq(tr0, tr1) function (ctx) concat(tr0(ctx).map(tr1));

function concat (xs) [].concat.apply([], xs); // stand-alone concat

Now we worked out the skeleton of the function by looking at the derived type and we have come up with an implementation by looking at the desired semantics. The function is now both type correct and works as expected!

For the Haskell programmer: we just worked out Kleisli composition for the list monad. This composition internally uses the monadic bind for the list monad instance, which happens to be the concatMap function. The concatMap function has type [a] -> (a -> [b]) -> [b], which (in our context) shows exactly how we apply a transformation (a -> [b]) to the results of another transformation ([a]) and come up with the result of the composition ([b]).

To illustrate the generic behavior of our sequential composition we use it to define some other useful transformations.

getSiblings    = seq(getParent, getChildren);

getGrandParent = seq(getParent, getParent);

Alternative composition

Now we have defined sequential composition we can also try to define another form of composition which just sums up the results of two transformations working over the same context node. For example when we want to create a transformation that selects both the grand parent and the grand children of a context node, we might want to write down something like this:

getGrands = alt(getGrandParent, getGrandChildren);

We call this composition function alt because it combines two alternative transformation paths into one. The type signature of the alt function is similar to that of seq, it takes two transformations as input and is itself again a transformation. The semantics of this transformation combinator is really easy, it just applies the two input transformation to the same context node and groups the results.

For the Haskell programmer: we just worked out the <+> function of the ArrowPlus instance for the list arrow. This function is defined in terms of the append function for lists, with type [a] -> [a] -> [a]. The semantics are very similar to that of the Alternative and MonadPlus type classes. Where the seq function is the algebraic and, product, sequence, /, times, etc, the alt function is the algebraic or, sum, alternative, |, plus, etc.

Deep recursion, filtering and creating.

Now we have two basic transformation combinators: sequential and alternative composition. Combining these two functions can get us some powerful transformation combinators. E.g. we can make the deep function that applies a transformation at arbitrary depth in document.

function deep (tr) alt(tr, seq(getChildren, lazy(deep, tr)));

function lazy (f, a) function (n) f(a)(n); // postponed function application

The deep function applies a transformation and groups the results with a recursive deep invocation for all the child nodes of the current context. Because, unfortunately, JavaScript is a strict language we have to explicitly delay the recursion in order to prevent infinite loops. Before we will test the deep transformation combinator we define three other useful primitive transformations.

function self (ctx) [ctx];

This transformation self is a bit special, it is the identity transformation which outputs a singleton list containing the context node itself. This transformation can be compared to the dot (.) in XPath.

function isElem (name) function (ctx) ctx.nodeName == name ? [ctx] : [];

This function isElem is a filter transformation function which includes or excludes a context node based on the nodeName. When the node name matches it is included as a singleton list, when there is no match the empty lists will be returned.

function mkElem (name) function (tr)

  function (ctx) [createElemWithChildren(name, tr(ctx))];

The third function mkElem is neither a selection or filtering functions, it is a creation function which takes the output node set of a transformation and surrounds it with a new element. This element will be returned as a singleton node set again.

Using the set of primitives and combinators to create a transformation that produces a simple table of contents from an input document is now very easy. The following transformation shows how to select all H1 and H2 elements from the entire document. All headers will be surrounded by a LI and inserted into an unordered list UL.

var isHeader = sum(isElem("h1"), isElem("h2"));

var toc = mkElem("ul")(seq(deep(isHeader, mkElem("li")(self))));



var myToc = toc(document.body);

Now toc is a true JavaScript function that computes a table of contents from an input document.

Comparison to XPath

Here is a (far from complete) table showing a comparison between XPath queries and our transformation functions. With the very few combinators defined, we can already rebuild a powerful set of XPath queries. Some primitives shown below, like hasAttr and precedingSiblings, have not been defined in this post. Defining them is very easy, please try it for yourself and see how far you can get with other exotic XPath axes.

Conclusion and goal

So we have seen how easy it is to create a powerful XML query and transformation language with a bare minimum of code. The trick is to define some primitive transformation functions and only two powerful ways to compose transformations. By using functions from one context node to a list of outputs selecting, filtering and creating elements all becomes possible. Using the composition functions you can easily build more advanced and high-level transformations like the deep function that traverses an entire document tree. The comparison between XPath and the selection primitives is quite clear. Adding an element creation function shows that the query language can quite easily become a true transformation language in which we can add new structure to the output.

While building such a library yourself is fun, it might feel a bit useless at first sight. Why reinvent XPath or XSLT while most browsers have built-in support for these tools? There are two main reasons to perform transformations this way.

The first reason is that is now very easy to add extra power to the library by plugging in new JavaScript functions. Using XSLT as a programming language, which unfortunately happens a lot in practice, almost always ends up shooting yourself in the foot with large and unmanageable recursive templates that fuzz what is really going on.

The second reason is more subtle. Here at typLAB we have shown that it is possible to change the primitive transformations and the two composition functions with their functional reactive counterparts. This enables us to incrementally rebuild the output of a transformation when only small parts of the input document change. This incremental reactivity is an extremely powerful paradigm that allows for very fast live queries over semantic and structured documents.

As you can see, this framework is very simple. Try playing with it yourself!

As an example, we will represent a simple user data type:

data User = User

          { name  :: String

          , email :: String

          , admin :: Bool

          }

The generic representation of this type is called a pattern functor. For the user data type, it will look like this:

type instance PF User = C User_User_

  (   S User_User_name_  (K String)

  :*: S User_User_email_ (K String)

  :*: S User_User_admin  (K Bool)

  )

Here we see a few of the functors that are the building blocks of our generic representation: The C type marks constructors, the S type marks record labels, K marks the types that make up the fields of our record, and (:*:) is the product mentioned earlier, and is very similar to the (,) used for constructing tuples. There are three more functors in regular: I, which marks recursive positions in a type; (:+:), which sums together different constructors; and U, for constructors without fields.

To write a generic function, we define a type class which contains this generic function, and give an instance for each of these functors. If we then also define conversion functions from our data type to the generic representation and back, we can apply the function to our data type. Note that for regular, these conversion functions, and the representation given above, can all be generated using Template Haskell.

Since we want to write a generic XML pickler for use with the HXT library, we’ll define a type class containing such a pickler:

class GXmlPickler f where

  gxpicklef :: PU a -> PU (f a)

This says that we can give a generic pickler for one of the functors f, containing a’s at the recursive positions, if we have a pickler for a’s. I’ll now show the instances for all the functors, and explain them one by one.

The first is the instance for I, marking recursive positions. Since we get a pickler for the resursive positions, all we have to do is wrap it in the I constructor when unpickling, and remove that constructor when pickling. HXT provides the xpWrap function to transform a pickler like this.

instance GXmlPickler I where

  gxpicklef = xpWrap (I, unI)

Next, we’ll tackle K. Here, we require that the type of the field has its own pickler, and use that. We again use xpWrap to add and remove the constructor of the functor. We provide a special instance for String, since it doesn’t have a standard pickler. We choose to use the pickler that allows empty strings.

instance XmlPickler a => GXmlPickler (K a) where

  gxpicklef _ = (K, unK) `xpWrap` xpickle



instance GXmlPickler (K String) where

  gxpicklef _ = (K, unK) `xpWrap` xpText0

U works similarly. We use the pickler for (), and use xpWrap to go from a () to a U and back.

instance GXmlPickler U where

  gxpicklef _ = (const U, const ()) `xpWrap` xpUnit

The case for (:+:) is interesting. Remember that (:+:) represents a choice between two functors. If we have picklers for both of these, we can define a pickler for the sum as follows: during conversion to XML, we can pattern match on L or R (the constructors of (:+:)) and choose the left or right pickler appropriately. During conversion from XML, we try the first pickler. If it fails (an unpickler returns a Maybe value) we try the second. Since HXT doesn’t seem to have a combinator that follows this logic, let’s define one ourselves:

xpEither :: PU (f r) -> PU (g r) -> PU ((f :+: g) r)

xpEither (PU fl tl sa) (PU fr tr sb) = PU

  (\(x, st) -> case x of

                 L y -> fl (y, st)

                 R y -> fr (y, st))

  (\x -> case tl x of

           (Nothing, _) -> lmap (fmap R) (tr x)

           r            -> lmap (fmap L) r)

  (sa `scAlt` sb)

  where lmap f (a, b) = (f a, b)

Note that we take apart the PU type, and create a pretty printer, a parser and a schema separately. We can use this function in the GXmlPickler instance by supplying it with two picklers, created by recursive calls to gxpicklef.

instance (GXmlPickler f, GXmlPickler g) => GXmlPickler (f :+: g) where

  gxpicklef f = xpEither (gxpicklef f) (gxpicklef f)

The instance for (:*:) is easy again. Since (:*:) combines two functors, we can require that these two have a pickler. We use xpPair to combine these into a pickler for a pair, and then use xpWrap again to convert it into a pickler for (:*:).

instance (GXmlPickler f, GXmlPickler g) => GXmlPickler (f :*: g) where

  gxpicklef f = (uncurry (:*:), \(a :*: b) -> (a, b))

                `xpWrap`

                (gxpicklef f `xpPair` gxpicklef f)

Note that so far, we haven’t created any XML tags ourselves. We’ve only combined picklers. Now we come to the instances for constructors and record selectors. Here, we’ll use the constructor or selector name (converted to lowercase) to generate and parse xml tags. This is done with the xpElem combinator.

instance (Constructor c, GXmlPickler f) => GXmlPickler (C c f) where

  gxpicklef f = xpElem (map toLower $ conName (undefined :: C c f r))

                  ((C, unC) `xpWrap` gxpicklef f)



instance (Selector s, GXmlPickler f) => GXmlPickler (S s f) where

  gxpicklef f = xpElem (map toLower $ selName (undefined :: S s f r))

                  ((S, unS) `xpWrap` gxpicklef f)

We now have picklers for all generic representations built from the standard functors in regular. We still need a top level function that works on our real data types, though. Regular provides the two functions to and from to convert between data types and their generic representation. We can use these together with xpWrap to change our generic pickler into a pickler for real data types. Another matter we have not addressed is the first argument to gpicklef, which is a pickler for the recursive positions. Here we pass the top level function, since the recursive position contains our original data type again.

gxpickle :: (Regular a, GXmlPickler (PF a)) => PU a

gxpickle = (to, from) `xpWrap` gxpicklef gxpickle

And that’s all for the generic XML pickler. Using it is very simple. To use it for our user data type above, we import Generic.Regular, Generic.Regular.TH, Generic.Regular.XmlPickler and Text.XML.HXT.Arrow.Pickle. We can then derive the Regular instance for user (note that we need a little bit of extra code, since Template Haskell cannot generate type family instances yet), and make an XmlPickler instance:

$(deriveAll ''User "PFUser")

type instance PF User = PFUser



instance XmlPickler User where

  xpickle = gxpickle

And that’s it! The package is available as regular-xmlpickler on hackage, and the source can also be found on github. The packages regular and HXT can also be found on hackage.

We’ve already talked about some of the technology choices we’re making as a company. And while our choices on the back-end can hardly be labeled as mainstream, the most difficult choice we actually had to make was related to the client-side as it directly affects our users. Obviously, Javascript on the client is a given, and we love it. However, as most web developers know, the differences between browsers are enormous and developing for all of them is almost impossible¹. Still, current conventional wisdom dictates that you should support recents versions of Internet Explorer², Firefox and the WebKit based browsers (basically, Safari and Google Chrome). We, however, have decided to drop Internet Explorer support entirely³.

In general, the trade-off you face when choosing which platform to develop for is between development time and a larger potential customer base that’s associated with the platform. Looking at the web right now, Internet Explorer still leads the market by a large margin⁴. So even if it seems annoying that you have to work around some CSS bugs or still write Internet Explorer specific event handling code for a web site, the payoff in user reach will usually still be worth it. Modern Javascript libraries such as jQuery or Mootools lower cross-browser development time even more by abstracting away lots of differences between browsers, tipping the equation even more in favor of Internet Explorer support.

So why did we choose to ignore the most used browser on the planet? It’s because we decided that in our case, the development costs would simply not be worth it. Obviously, this assessment is very specific for the type of application we’re building. We didn’t just base this on a hunch, we actually have quite some experience in this field: most of us have worked on products like Xopus before. Xopus is an awesome, browser based wysiwyg XML editor. It consist of more than 120,000 lines of client-side Javascript code. A non-trivial part of that is code that completely works around standard Internet Explorer behavior because of its bugginess or complete lack of support. This isn’t about your father’s unsupported CSS selectors or the lack of addEventListener. We’re talking about stuff like having to write your own cursor because contentEditable becomes basically useless when working on complex documents. The amount of bugs that are related to contentEditable, text ranges, drag and drop and the Document Object Model in general are staggering. Most JavaScript projects, including some popular libraries, don’t even deal with these advanced aspects of the browser at all.

Now obviously, the other browsers aren’t all free of bugs. Which brings us to the second problem with Internet Explorer: lack of real progress and transparency. Even if you consider relatively easy and popular features (such as support for addEventListener), it’s hard to understand why they haven’t been implemented yet and if there is any timeline at all to implement them. That makes the probability of low visibility improvements and bug fixes in the rendering or selection code practically zero. The contrast with the open development of Mozilla and WebKit is huge, where almost everything is publicly discussed and with a focus on constant improvement of the rendering engines and pretty clear timeline.

The current state of the web is actually very exciting right now, if we ignore Internet Explorer for a moment. Thanks to HTML5 there is a lot of progress allowing us to make almost desktop class applications, with support for things like drag and drop from the desktop, background processes and offline support⁵. All of this should greatly improve the user experience with web applications and bridge the gap with desktop applications. No amount of code or smart engineering will allow us to bring that level of experience to browsers that lack these features.

Does this mean that no complex web application should support Internet Explorer? Obviously, it depends on many factors. There are large differences between applications that are targeted to tech-savvy users (where Internet Explorer is quickly becoming a minority browser) or to large organizations (where Internet Explorer 6 is still widely used). We’re a small team and we have to prioritize our development goals aggressively. Large teams with lots of resources are in a different situation altogether. That being said, we were pleased to see that the Google Wave team also chose to drop Internet Explorer support and having Google develope the Chrome Frame plug-in.

Finally, although this might seem less important than the above considerations from a business perspective, there is the loss of friction and return of enjoyment in developing web applications again. Not developing for Internet Explorer means that we can do amazing things with CSS, use new Javascript features in our codebase, and in general rediscover the excitement of the possibilities of the web. And that makes us love web development again.

1. Try using Netscape 4.7 today, if you’re curious.
2. Usually, this means Internet Explorer 6 and newer. However support for Internet Explorer 6 is slowly declining, as it’s dropped by major sites like YouTube, Orkut and products like Basecamp.
3. Note that what we’re discussing here is browser support for our application. The content that resides inside the application will always be available to any web browser, whether it’s a text-based browser with no Javascript support, a low capability mobile browser or Internet Explorer 6. This is based on the principe of graceful degradation.
4. Wikipedia has a nice summary of various sources with browser usage statisics.
5. To be fair, Internet Explorer 8 does provide some offline support.

All modern browsers have support for W3C’s mutation events. Safari, Chrome, FireFox and Opera all do them. But not all do all of them.

Notably WebKit fails to fire DOMAttrModified events when an attribute is changed. It does however fire the DOMSubtreeModified event after an attribute is modified. So at least that gives us something to work with until the good folks at WebKit squash the bug.

Here is how we fixed the lack of DOMAttrModified. First we need to detect whether the fix is needed:

var attrModifiedWorks = false;

var listener = function(){ attrModifiedWorks = true; };

document.documentElement.addEventListener("DOMAttrModified", listener, false);

document.documentElement.setAttribute("___TEST___", true);

document.documentElement.removeAttribute("___TEST___", true);

document.documentElement.removeEventListener("DOMAttrModified", listener, false);

The code is straightforward. Add an attribute and have a listener register the firing of the subsequent DOMAttrModified event. If the event is not fired our repair code kicks in:

if (!attrModifiedWorks)

{

Next we store and override HTMLElement.setAttribute:

HTMLElement.prototype.__setAttribute = HTMLElement.prototype.setAttribute



HTMLElement.prototype.setAttribute = function(attrName, newVal)

{

  var prevVal = this.getAttribute(attrName);

  this.__setAttribute(attrName, newVal);

  newVal = this.getAttribute(attrName);

  if (newVal != prevVal)

  {

    var evt = document.createEvent("MutationEvent");

    evt.initMutationEvent(

      "DOMAttrModified",

      true,

      false,

      this,

      prevVal || "",

      newVal || "",

      attrName,

      (prevVal == null) ? evt.ADDITION : evt.MODIFICATION

    );

    this.dispatchEvent(evt);

  }

}

The new code fetches the current value of the attribute, soon to become the previous value.
It then proceeds to set the attribute using the original setAttribute method that we stored.
We don’t know whether that method does fancy stuff to the new attribute value, so, just to be sure, we fetch the new value by calling getAttribute once again.
If and only if the new and previous value differ we proceed to dispatch the appropriately initialised mutation event.

This covers added and modified attributes. But it won’t help us with removed attributes. For those we can override the removeAttribute method of HTMLElement:

HTMLElement.prototype.__removeAttribute = HTMLElement.prototype.removeAttribute;

HTMLElement.prototype.removeAttribute = function(attrName)

{

  var prevVal = this.getAttribute(attrName);

  this.__removeAttribute(attrName);

  var evt = document.createEvent("MutationEvent");

  evt.initMutationEvent(

    "DOMAttrModified",

    true,

    false,

    this,

    prevVal,

    "",

    attrName,

    evt.REMOVAL

  );

  this.dispatchEvent(evt);

}

This concludes our fix for the lack of DOMAttrModified in WebKit.
Is this fix perfect? Nope. Some known issues:

• a DOMSubtreeModified event is fired before instead of after the (artificial) DOMAttrModified event
• assigning a value to an attribute will not trigger our setAttribute method. Most noticeably assigning a value to a className or id attribute will not result in the appropriate DOMAttrModified event

We’re open for suggestions. But best would be if some WebKit developer would fix the bug so we can throw this code away.

We figured that using DBXML would give us some important advantages:

• Collections of HTML5 documents will form the basis of data model. Only one trivial conversion from HTML5 to syntactically valid XML is needed to get our documents into the XML database. Once stored we can perform some interesting queries over our data.
• XML databases allow for the storage of complex data layouts without having a strict schema. Without a schema it will be easier to adjust our data model over time without instantly breaking our software.
• XQuery is a very expressive (almost-purely functional) querying language which is at least as powerful as SQL and far more flexible in the structure of the data to target.
• XML can be used to both encode strictly defined datatypes and store free-form documents in the same document collection. This will enable us to put both our meta data and our documents in the same database.
• A quick look on Hackage revealed there is an out-of-the-box easy-to-use Haskell binding available for the Berkeley XML database. No need to create custom bindings ourselves.
• We are in the advantage (or disadvantage) of having Haskell as our language of choice for our server software. Because of the hierarchical nature of both XML and Haskell algebraic datatypes, an XML database feels like a perfect fit.

Once we decided to go for an DBXML back-end we had to figure out how to easily get values form our Haskell program in and out of the database. The rest of this post will be dealing with the last point of our enumeration: how to get a nice mapping from Haskell’s algebraic datatypes to our DBXML back-end.

XML queries

The DBXML binding for Haskell is a shallow wrapper around the existing C++ API. This library allows us to perform the common create, read, update and delete queries for entire XML documents or parts of it. Communication with the XML database happens mainly via XQuery. Queries and query parameters are passed into the API (and results will come out) using Haskell ByteStrings. It is up to the programmer to setup the queries with the right XML structure and encoding. Take for example the (somewhat simplified) type signature of the query function:

query :: Collection -> Query -> Parameters -> IO [ByteString]

This function takes an identification of the XML collection, which is somewhat like a database handle, an XML query, a set of query parameters and returns a possibly empty list of XML snippets as ByteStrings. Too bad that all our domain objects are well-typed Haskell algebraic datatypes and not raw sequences of bytes. We need a simple XML (de)serialization tool for this.

XML picklers

The Haskell XML Toolbox (HXT) is a library containing a (quite extended) collection of XML processing tools. The library has support for XML parsing, pretty printing, XPath queries, XSL stylesheets, DTD, XSD and RelaxNG schemas and a lot more. Interestingly, HXT exposes a type class and an accompanying set of combinators called XML picklers. XML picklers can be used to build conversion functions from Haskell datatypes to XML and vice versa. The type class looks like this:

  class XmlPickler a where

    xpickle :: PU a

So for every type in the XmlPickler type class there is some PU available. The PU datatype is composed of a pair of pickle (serialize) and unpickle (deserialize) functions together with a schema description. Because we won’t be using the schema definitions we will ignore them for now. There is probably no need to ever touch the functions inside the PU type, because the library supplies a vast amount of basic pickler combinators to be used instead.

To illustrate the usage of HXT picklers take this simple Haskell datatype representing a single user in our system:

data User = User

  { name     :: String

  , email    :: String

  , password :: String

  , openID   :: String

  }

Using some of the basic pickler combinators from the library it is very easy to come up with a suitable XmlPickler instance:

class XmlPickler User where

  userPickle =

    xpElem "user"

    $ xpWrap

      ( (\(a, b, c, d, e) -> User a b c d e)

      , (\(User a b c d e) -> (a, b, c, d, e))

      )

    $ xp5Tuple

      (xpElem "username" xpText)

      (xpElem "name"     xpText)

      (xpElem "password" xpText)

      (xpElem "email"    xpText)

      (xpElem "openid"   xpText0)

This instance uses the xp5Tuple function to pickle five sub-picklers into a big tuple. The five fields will be appropriately named elements from which the text value will be used. The tuple will be converted into a value of the User datatype using the xpWrap function. This is all you to need to manually write XML serialization and deserialization code.

A bit off topic but interesting to note is the fact that the xpWrap function can be seen as a pickler specific and bidirectional version of the well known fmap for Functors. The xpWrap is used to define true isomorphisms. When we generalize the type of xpWrap to work arbitrary containers, lets call this function bifmap, and compare the type signatures this similarity becomes obvious:

fmap   :: (a -> b)         -> f a -> f b

bifmap :: (a -> b, b -> a) -> f a -> f b

So, taking the XmlPickler instance for our User datatype we can now easily convert users into XML and read them back in, like the following example:

User "jd" "John Doe" "secret" "john@doe" "none"

<user>

  <username>jd</username>

  <name>John Doe</name>

  <password>secret</password>

  <email>john@doe</email>

  <openid>none</openid>

</user>

Using the xpickle function from the type class and the xunpickleVal from the HXT library we can now write a more suitable query function on top of the raw version. This version does not return ByteStrings, but values of any type we can convert to. Off course, the information in the database should match your datatype, otherwise the unpickler function will just produce parse errors resulting in an empty list.

query :: XmlPickler a => Collection -> Query -> Parameters -> IO [a]

Although this pickler example for our user is a very simple one, even more complicated datatypes, including multi-constructor and possibly mutual recursive datatypes, can quite easily be made an instance of the XmlPickler class. Unfortunately we still have to write them all by hand.

Going generic

After a few of years at the University of Utrecht we learned at least one valuable lesson, never write functions by hand when they can be derived generically. We decided to write a generic XML pickler function using the generic programming library Regular, developed (not entirely coincidentally) at the University of Utrecht. Regular is a relatively simple but powerful tool for writing data type generic functions. The library has support for deriving embedding projection pairs (conversions from and to a generic representation) using Template Haskell and provides enough reflection to inspect constructor names and record labels.

The generic representation is encoded as a type family (the pattern functor, or PF) over the original data type. The generic pickler function we developed has the following signature:

gxpickle :: (Regular a, GXmlPickler (PF a)) => PU a

This means that for every type that we can convert to a generic representation (indicated by the Regular type class) and for every type that has a GXmlPickler instance for its generic representation, we can deliver a PU. The regular-xmlpickler package implements the GXmlPickler type class and the instances for the types of which the representations are composed. So, all we need now for our User datatype is to derive a generic representation and use the generic implementation for the XmlPickler instance.

$(deriveAll ''User "PFUser")

type instance PF User = PFUser



instance XmlPickler User where

  xpickle = gxpickle

Using this automatically derived XML pickler and the query function described above we can now query the DBXML backend for all users that satisfy a certain property:

jd :: IO [User]

jd = query myCollection "/user[username=$name]" [("name", "jd")]

Now we’re able to query a database for pieces of XML and reify these as true Haskell values with almost no boilerplate involved! Because of the bidirectional behavior of the XmlPickler type class it shouldn’t be difficult to imagine that the same trick is applicable to inserting and updating database entries.

We will discuss writing generic functions using the Regular library in a later post.

On the client, there wasn’t much discussion. Javascript is the only viable choice, unless you want to use Flash or similar plugin-based models. But on the server, we had more freedom. Popular choices for web applications are dynamically typed languages like Ruby, Python and PHP, and statically typed languages like Java and C#.

However, there was another option. Two of us (me and Sebas) are enrolled in the Software Technology master program at Utrecht University, where we often use the programming language Haskell. Haskell is a functional programming language, which means that a program is composed of expressions instead of statements, as is the case in an imperative programming language.

As you might have guessed from the title of this post, we decided to use Haskell for our server side programming. What are the features that made us choose Haskell?

First, we like the functional programming model. Modeling programs based on what values are, instead of what bits to move where, is much closer to the way we think. We write down what we mean, and let the compiler figure out how to calculate it. This also leads to shorter code: Haskell is often surprisingly concise.

Another important consideration is the strong type system that Haskell has. It has powerful features that prevent you from running incorrect programs, while not getting in the way, as is often the case in traditional statically typed languages like Java or C#. This is due to the fact that Haskell has type inference: it can deduce the types of variables and functions without programmer specifications.

Something that sets Haskell apart from almost all other programming languages, is its purity: an expression in Haskell is not allowed to do anything on evaluation other than return its value (functions are not allowed to have side-effects). This has many implications. For example, data is immutable: if you modify a list, for example, you create a new copy (although smart compilers share duplicate parts for efficiency). This means that you never have to think about other parts of the code changing your data: you can always reason locally. Another implication is that your language can be lazy (and in fact, Haskell is). This means that expressions are not evaluated unless their results are needed. This can lead to performance improvements, and allows you to use infinite data structures.

If we disallow side effects, how do we perform I/O, for example? Haskell uses an abstraction called a monad to do this. A monad shows up in the type, indicating that we are performing side effects. The I/O monad allows us to force an ordering on actions, allowing us to safely perform the actions in a lazy setting. We can also use monads to keep state, have mutable variables, and many other things.

Purity also makes concurrency a lot easier: if data is immutable, there is no risk in sharing it between different threads. If you need to share mutable data between different threads, Haskell offers a few ways of dealing with this, the most interesting of which is software transactional memory (STM), a lock-free way of building composable atomic actions.

Since Haskell is a functional language, functions are first class: you can create them on the fly, pass them as arguments, return them as results, store them in a data structure, etc. This allows you to easily create powerful abstractions. For example, one often-used Haskell function is map. It takes an argument that turns a value of type a into a value of type b, and uses this to transform a list of a’s into a list of b’s by applying it to each element. This function abstracts away looping over a list. In a similar way we can create our own abstractions. This often leads to the creation of lightweight EDSLs (embedded domain specific languages), especially since Haskell allows the creation of (infix) operators as well.

The combination of conciseness, locality of data, strong types and explicit side-effects has a very important consequence: it makes refactoring easy and risk-free. You can change your code, and if it still type checks, you can often be sure that it still works. Combined with the power of abstraction this means we can quickly develop programs that can be easily understood and modified by others.

Finally, another positive aspect of Haskell is its community. There is an active blog community, a large and helpful IRC channel (#haskell) and an online package repository. There is an industrial strength compiler, a dependency tracking package manager and built-in tools like code coverage.

Of course, there are also a few risks involved in choosing a language like Haskell. Since it doesn’t have a user base as large as some other languages, there are less libraries available. This is alleviated in part by a strong C interface that Haskell provides. Because of laziness, performance problems can be harder to diagnose and fix. And of course, there are less programmers who have experience with Haskell, so finding people to help you can be harder.

But all in all, we feel that the benefits Haskell can bring us outweigh the risks. And most of all, Haskell makes programming fun!

‘What’s typLAB then?’, you might ask.

typLAB is our initiative to investigate and develop new ways of creating and consuming web-based content. We aim to explore the boundaries of what’s possible using contemporary internet technologies. The result of our endeavors should enable you to read and write rich, dynamic and smart articles like you’ve never read nor written them before.

Next question. ‘Who are those “we” you keep referring to?’

We are Erik Hesselink, Sebastiaan Visser, Salar al Khafaji and Lon Boonen. That’s the team; small, smart, focused and eager to learn and share. Most of us share a history at Xopus, the web based XML editor.

One more question? ‘What about lablog, what can we expect from it?’

Through lablog we want to inform you of our ponderings and wonderings. Our steps forward, backward and sideways. We’ll write about our progress, our discoveries and the things that make us tick.

You can expect articles on HTML5, CSS3, web development in general, Haskell, XQuery, usability, semantics, JavaScript and all stuff that makes a nerd’s heart jump a beat. Or two.

And we’d love to hear from you. Through the comments, Twitter or plain old e-mail.