Tuesday, 30 March 2010

Bubble sort in a Mathematica pattern

The Mathematica programming language has many unusual characteristics, two of which are:

  • Everything is an expression.
  • Pattern-based rewrite rules are obscenely powerful.

These kinds of characteristics are the foundation of what makes Mathematica a powerful programming language. For example, the bubble sort algorithm can be implemented in a single line without a loop in Mathematica using a single conditional rewrite rule that exchanges adjacent elements when they are out of order:

bubble[xs___, x_, y_, ys___] := bubble[xs, y, x, ys] /; x > y

This definition causes a new rewrite rule to be injected into Mathematica's global table of rewrite rules. Mathematica then applies this rule to any subexpression it sees that has the form bubble[..]. The pattern on the left side of the rule searches for a pair of adjacent arguments (x and y) to bubble where x>y. If the pattern matches then the expression is rewritten such that x and y are exchanged.

This example not only demonstrates the remarkable expressiveness of the Mathematica programming language but also some of the ensuing problems. We have no idea how efficiently Mathematica's pattern matcher will find adjacent elements that are out of order and it is unlikely that Mathematica will optimize this down to an in-place swap. Consequently, we cannot begin to predict how much time or space this function will require. A quick benchmark shows that sorting 100 small integers this way takes a whopping 0.63 seconds!

Thursday, 11 March 2010

KDE 4 drove us to Windows Vista

We just finished a week of hell after trying and failing to upgrade from Debian Lenny to Debian Squeeze. None of the Debian Linux kernels working correctly on our stock Dell PowerEdge T605 hardware was the first major headache and KDE 4 was the second. In our 10 years of using Linux its user unfriendliness seems to be as poor as ever.

With the latest KDE 4, it seems that KDE itself has also gone from bad to worse. We migrated from Gnome to KDE many years ago because we found Gnome to be buggy and user unfriendly only to discover that KDE was only superficially stable. KDE 4 takes this to a new level and our log files are filled with records of segfaults. KMail was once riddled with serious bugs but these were ironed out in KDE 3 and it became a usably-stable e-mail client a few years ago and served us well. Not so with KMail from KDE 4, which regularly segfaults, losing and/or corrupting data and has consistently failed even to move significant numbers of e-mails around within its own Maildir.

Following our catastrophic encounter with the latest round of open source software we have decided to migrate everything from Linux+OCaml to Windows, .NET and F#. Unfortunately, KMail quickly threw another spanner into the works because it is almost entirely incapable of exporting e-mails to other usable formats. We eventually managed to migrate essential e-mails by setting up a local IMAP server using dovecot, painstakingly copying a few mails at a time from KMail's local store to the IMAP server and then downloading them using Microsoft Outlook. Any attempt to copy a significant proportion of our 3.2GB of e-mails resulted in KMail either crashing with an error after it had corrupted its own file store or dying completely with a segfault.

Back in 2007, we were reluctant to adopt Windows due to previous bad experiences but this latest round of failures is the last nail in the Linux coffin from our perspective. Goodbye and good riddance, Linux!

Sunday, 7 March 2010

The HLVM Reddit

The Reddit user ethicszen has kindly created a subreddit for HLVM-related news and discussion. Please post links to interesting HLVM articles there.

Also, don't forget to join our mailing list if you want to hear what is going on or discuss HLVM in any way.