July 26, 2008

I’ve been an xmonad user since November, and a contrib developer since December. I love it, and really miss it when I have to use Windows or a friend’s Linux machine. I’ve introduced several classmates to it, and the ones who use Linux regularly use xmonad as well.

One of the best features of xmonad is that the configuration file is a Haskell source file. This allows for great extensibility, flexibility and control of one’s setup.

One of the great weaknesses of xmonad is that the configuration file is a Haskell source file. This means that a user must have a working GHC 6.8 (does 6.6 still work?) installed in order to change their xmonad configuration.

For someone already involved in Haskell, this is not a problem, of course. For someone looking for a good tiling window manager, GHC is a dependency of the heaviest sort. It totals some 150MB of disk on Ubuntu Hardy, for example.

To most people that’s nothing as far as disk space itself goes; gigabytes of storage are cheap and plentiful, even on laptops. Except for the new breed of EEE PCs and similar! The ritziest models of these have 8GB, most have 4GB. Now GHC is starting to be actually expensive.

Above and beyond the actual disk space cost is the psychological cost of a big dependency. It hardly fits the presentation of xmonad as a minimalist window manager to require the installation a complete compiler toolchain.

There are blog posts and mailing list posts about the problem, and a few days ago a user on #xmonad balked at the problem, though the combined weight of Don Stewart, Spencer Janssen and I persuaded him to try it anyway and he seems well pleased with the investment of space.

That last one really drives home the point: GHC is an initial hurdle only; once a user has discovered how awesome xmonad is, they will gladly sacrifice the space for it.

Strictly speaking, xmonad doesn’t require GHC, you can run GHC’s binaries without the compiler present. For xmonad, however, this is extremely limiting, as a user cannot even change the mod key without recompiling their xmonad.hs and therefore requiring GHC.

And so we are left with a conundrum. Certainly we do not wish to sacrifice the flexibility and power of using Haskell as a configuration language. So the solution, if any, lies in improving the situation for the user who does not have GHC. Since he current has no options at all, any alternatives are an improvement. I have three ideas for consideration. All are discussed in detail below.

1. An archive of precompiled configuration files alongside the config archive on the wiki.
3. A supplementary plain-text config file, that a precompiled xmonad.hs could parse, generating an `XConfig` and passing that to the `xmonad` function.

1. Config Archive
This solution requires the least effort, just a bit of web hosting space. It’s also the most limiting, since users can’t mix and match, just select from the existing models. Better than nothing, but not by much. I don’t have much more to say about it, I support the below ideas more.

2. Web Service
This solution is the most flexible, allowing users to have their cake and eat it too: the full power of Haskell configurations without the cost of GHC. This would be the approach I would support, except that there are serious challenges here. Template Haskell allows arbitrary execution at compile-time, there’s an infinite loop in the typechecker. There might be other bugs to allow arbitrary compile-time execution even if we could disable TH. Finally, we need a box to run this on, and no one volunteered.

3. `PlainConfig`
This option is actually implemented already, at least in proof-of-concept form. I wrote `XMonad.Config.PlainConfig` in April to demonstrate that this idea could work, and could really run with a precompiled xmonad.hs and without GHC. It works, though of course it is far more limiting than a Haskell configuration. Key bindings are done using `EZConfig`, and drawing from a list of predefined actions. Layouts are selected from a predefined list as well. Workspaces have arbitrary labels, and as many as you like (though no list comprehensions for the new key bindings!). Mod and NumLock keys can be set freely, as can the colours, border width, terminal and focus-follows-mouse. `ManageHook`s use a parser from Roman Cheplyaka to handle arbitrary `resource`, `className`, and `title` queries, and the two standard actions `doFloat` and `doIgnore`. `doShift` wasn’t in core when I wrote `PlainConfig`, but it is very easy to add.

Similarly, it would be easy to add more layouts and keybinding actions, they are just entries in a `Data.Map String Whatever`. The two most common configuration elements that are missing are `logHook`s for status bars and `layoutHook` modifiers like `avoidStruts`. The latter is straightforward to add (there are only a few of them, after all), and the former is only slightly more difficult, though it doesn’t allow a lot of flexibility.

The Kicker

From the relative volume of those three possiblities, it should be fairly clear which I think is the most practical approach to lightweight xmonad configuration. `PlainConfig` works, and was designed to be easily extended to add more contrib modules (`ManageDocks`, `EwmhDesktops`, layouts), more keybinding actions (`CopyWindow`, `Prompt`).

The next key piece of the puzzle is the idea of nightly builds. It’s been a long time since the 0.7 release, and contrib has been zipping ahead as ever. Not everyone wants to install darcs, check out xmonad, and build xmonad from the darcs source just to get at the new modules and changes. A system of nightly builds would allow these users to stay up-to-date and take advantage of the active development, without needing darcs or indeed, GHC.

It would be straightforward to provide two distinct builds every night. The first would be xmonad as packaged presently for Debian, Arch et al., using the stock config and with no xmonad.hs. Alongside this, however, could be a version which includes the prebuilt xmonad.hs that parses the user’s xmonad.conf using `PlainConfig`.

And the Gateway Drug

Inevitably, many `PlainConfig` users are going to want something it can’t provide, and can’t easily be modified to provide. To avoid making this a dilemma between improved configuration power and having to rewrite their existing config into an xmonad.hs, I plan to write a “cross-compiler” from xmonad.conf files to an equivalent xmonad.hs which can be a drop-in replacement.

Concerning Evangelism

During discussion of the web compilation idea on the mailing list, there was a rather emphatic post cursing the drive in others for evangelising open source projects, since it just invites a load of clueless newbies who were “attracted to the *marketing* instead of the functionality”. I certainly try to avoid being a zealot, and readily suggest to users taking exception to fundamental aspects of xmonad that they consider one of the alternative WMs. On the other hand, more users for xmonad means more potential contributors, more people checking bugs, new sources of ideas (whether they can code them personally or not) and more buzz for Haskell. I consider all of these worthy goals, and so if adding a feature like GHC-less configuration to xmonad makes me an evangelist, I will bear that label gladly.

In the spirit of “patches welcome”, I plan to work on the “cross-compiler” and nightly builds, both normal and `PlainConfig`-ready, in the next week. I will donate my own desktop to the cause as a build box until an alternative can be found. I hope that once this system is in place, we can manage to put out the word that xmonad doesn’t require GHC anymore loudly enough to overcome the inertia. Perhaps more importantly, to kill the untruth that one must learn Haskell to use xmonad! There are unfortunately numerous blog posts out there that compare tiling WMs and cite one or both as a disadvantage of xmonad. The latter is particularly insidious, and though xmonad users have said in many places that this was simply not true, that far more users have zero Haskell knowledge than have some, it persists.

Of course, the reverse rumour, that xmonad has crippled their configuration, that Haskell isn’t a good language for configuration, will need a strong pre-emptive strike. It needs to be blindingly obvious that both options for configuration are still supported!

## Fixed Point Datatypes

July 7, 2008

This is more Haskell translation of my reading of “Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire”, this time concerning fixed points of data types.

First, what is a fixed point (aka. fixpoint)? In calculus, functions can have fixed points. These are values $x$ such that $f(x) = x$. As an example, $f(x) = x^2$ has a fixed point at both 0 and 1. For $f(x) = x$, every $x$ is a fixpoint!

The notion of fixpoints in programming is somewhat different, though related. In programming fixed points are about self-application, rather than the calculus definition above. I hope the distinction will become clear with some examples.

First, consider the following definition of a simple pair-like type:

`data Pair a b = Pair a b`

I can use any type I like for a and b, including, say, Pair a b:

`example1 = Pair 1 (Pair 2 'a')`

I could go further:

`example2 = Pair 1 (Pair 2 (Pair 3 (Pair 4 (Pair 5 'a'))))`

Is that starting to look familiar? This is an approximation of lists, though not exactly a pleasant one to work with.
Note that Pair a is a Functor. This idea of applying a Functor to itself is exactly fixpoints of data types. With the Pair a Functor, there is nothing to stop the self-application, so we have something isomorphic to an infinite [a].
Augmenting Pair to include a second, nullary, constructor, thus:

`data Pair a b = Stop | Pair a b`

We can then take the fixpoint of the Functor Pair a, which is isomorphic to:

`data PairFix a = Stop | Pair a (PairFix a)`

And that is clearly isomorphic to desugared lists:

`data List a = Empty | Cons a (List a)`

We can even abstract this notion of self-application of a Functor in a curious newtype:

`newtype Functor f => Mu f = In (f (Mu f))`

Such that PairFix a = Mu (Pair a), assuming we’ve declared an instance of Functor for Pair a.

Lists are actually only one example. Mu can be applied to any Functor. Using the binary tree implementation from a previous post ,

`data Tree a = Empty | Tree a (Tree a) (Tree a)`

This is the fixpoint of the following type:

`data Cell a b = Empty | Cell a b b`

Since Cell a forms a Functor, Mu (Cell a) == Tree a.

This is all merely an intriguing bit of type theory until we make the realization that all of these structures have something in common. That something is that they can all be recursed over. This can be seen most clearly by looking at lists, which as I demonstrated above are isomorphic to Mu (Pair a) using the second definition of Pair. The main thrust of Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire is that recursion patterns (ie. higher-order functions) we generally think of as being for lists are in fact applicable to any fixpoint data structure.

The paper goes on to describe four core “foomorphisms”: catamorphisms, anamorphisms, hylomorphisms and paramorphisms. The names are from Greek, and like “monad” and “functor” are far scarier than the things they name. These are generalizations of foldr, unfoldr, primitive recursion and primitive recursion with an accumulating parameter, respectively.

I had originally planned to describe these in more detail here, but Edward Kmett (edwardk) has begun writing a Field Guide to all of these recursion schemes. His posts on each of the foomorphisms include both category theory and concrete examples, and are an excellent read. As you can see from the front page of his Field Guide, there are many, many more than the four described in the original paper. Implementations of all of these and much more are available in category-extras on Hackage.

I will still describe some of the core examples and definitions from the paper in later posts. In particular my explorations of the standard examples (Peano numbers, factorial, trees) from Edward Kmett’s Guide and elsewhere. My goal is to learn to recognize them well “in the wild”, since they aid understanding even when the function doesn’t explicitly use the foomorphism.