Software Simply

Haskell Web Framework Matrix

2012-12-20T17:20:00.000-05:00

A comparison of the big three Haskell web frameworks on the most informative two axes I can think of.

Note that this is not intended to be a definitive statement of what is and isn't possible in each of these frameworks. As I've written elsewhere, most of the features of each of the frameworks are interchangeable and can be mixed and matched. The idea of this matrix is to reflect the general attitude each of the frameworks seem to be taking, because sometimes generalizations are useful.

Using Cabal With Large Projects

2012-11-08T10:46:00.001-05:00

In the last post we talked about basic cabal usage. That all works fine as long as you're working on a single project and all your dependencies are in hackage. When Cabal is aware of everything that you want to build, it's actually pretty good at dependency resolution. But if you have several packages that depend on each other and you're working on development versions of these packages that have not yet been released to hackage, then life becomes more difficult. In this post I'll describe my workflow for handling the development of multiple local packages. I make no claim that this is the best way to do it. But it works pretty well for me, and hopefully others will find this information helpful.

Consider a situation where package B depends on package A and both of them depend on bytestring. Package A has wide version bounds for its bytestring dependency while package B has narrower bounds. Because you're working on improving both packages you can't just do "cabal install" in package B's directory because the correct version of package A isn't on hackage. But if you install package A first, Cabal might choose a version of bytestring that won't work with package B. It's a frustrating situation because eventually you'll have to end up worrying about dependencies issues that Cabal should be handling for you.

The best solution I've found to the above problem is cabal-meta. It lets you specify a sources.txt file in your project root directory with paths to other projects that you want included in the package's build environment. For example, I maintain the snap package, which depends on several other packages that are part of the Snap Framework. Here's what my sources.txt file looks like for the snap package:

./
../xmlhtml
../heist
../snap-core
../snap-server

My development versions of the other four packages reside in the parent directory on my local machine. When I build the snap package with cabal-meta install, cabal-meta tells Cabal to look in these directories in addition to whatever is in hackage. If you do this initially for the top-level package, it will correctly take into consideration all your local packages when resolving dependencies. Once you have all the dependencies installed, you can go back to using Cabal and ghci to build and test your packages. In my experience this takes most of the pain out of building large-scale Haskell applications.

Another tool that is frequently recommended for handling this large-scale package development problem is cabal-dev. cabal-dev allows you to sandbox builds so that differing build configurations of libraries can coexist without causing problems like they do with plain Cabal. It also has a mechanism for handling this local package problem above. I personally tend to avoid cabal-dev because in my experience it hasn't played nicely with ghci. It tries to solve the problem by giving you the cabal-dev ghci command to execute ghci using the sandboxed environment, but I found that it made my ghci workflow difficult, so I prefer using cabal-meta which doesn't have these problems.

I should note that cabal-dev does solve another problem that cabal-meta does not. There may be cases where two different packages may be completely unable to coexist in the same Cabal "sandbox" if their set of dependencies are not compatible. In that case, you'll need cabal-dev's sandboxes instead of the single user-level package repository used by Cabal. I am usually only working on one major project at a time, so this problem has never been an issue for me. My understanding is that people are currently working on adding this kind of local sandboxing to Cabal/cabal-install. Hopefully this will fix my complaints about ghci integration and should make cabal-dev unnecessary.

There are definitely things that need to be done to improve the cabal tool chain. But in my experience working on several different large Haskell projects both open and proprietary I have found that the current state of Cabal combined with cabal-meta (and maybe cabal-dev) does a reasonable job at handling large project development within a very fast moving ecosystem.

A Practical Cabal Primer

2012-11-02T13:09:00.000-04:00

I've been doing full-time Haskell development for almost three years now, and while I recognize that Cabal has been painful to use at times, the current reality is that Cabal does what I need it to do and for the most part stays out of my way. In this post, I'll describe the Cabal best practices I've settled on for my Haskell development.

First, some terminology. GHC is the de facto Haskell compiler, Hackage is the package database, Cabal is a library providing package infrastructure, and cabal-install is a command line program (confusingly called "cabal") for building and installing packages, and downloading and uploading them from Hackage. This isn't a tutorial for installing Haskell, so I'll assume that you at least have GHC and cabal-install's "cabal" binary. If you have a very recent release of GHC, then you're asking for problems. At the time of this writing GHC 7.6 is a few months old, so don't use it unless you know what you're doing. Stick to 7.4 until maintainers have updated their packages. But do make sure you have the most recent version of Cabal and cabal-install because it has improved significantly.

cabal-install can install things as global or user. You usually have to have root privileges to install globally. Installing locally will put packages in your user's home directory. Executable binaries go in $HOME/.cabal/bin. Libraries go in $HOME/.ghc. Other than the packages that come with GHC, I install everything as user. This means that when I upgrade cabal-install with "cabal install cabal-install", the new binary won't take effect unless $HOME/.cabal/bin is at the front of my path.

Now I need to get the bad news over with up front. Over time your local Cabal package database will grow until it starts to cause problems. Whenever I'm having trouble building packages, I'll tinker with things a little to see if I can isolate the problem, but if that doesn't work, then I clean out my package repository and start fresh. On linux this can be done very simply with rm -fr ~/.ghc. Yes, this feels icky. Yes, it's suboptimal. But it's simple and straightforward, so either deal with it, or quit complaining and help us fix it.

I've seen people also say that you should delete the ~/.cabal directory as well. Most of the time that is bad advice. If you delete .cabal, you'll probably lose your most recent version of cabal-install, and that will make life more difficult. Deleting .ghc completely clears out your user package repository, and in my experience is almost always sufficient. If you really need to delete .cabal, then I would highly recommend copying the "cabal" binary somewhere safe and restoring it after you're done.

Sometimes you don't need to go quite so far as to delete everything in ~/.ghc. For more granular control over things, use the "ghc-pkg" program. "ghc-pkg list" shows you a list of all the installed packages. "ghc-pkg unregister foo-2.3" removes a package from the list. You can also use unregister without the trailing version number to remove every installed version of that package. If there are other packages that depend on the package you're removing, you'll get an error. If you really want to remove it, use the --force flag.

If you force unregister a package, then "ghc-pkg list" will show you all the broken packages. If I know that there's a particular hierarchy of packages that I need to remove, then I'll force remove the top one, and then use ghc-pkg to tell me all the others that I need to remove. This is an annoying process, so I only do it when I think it will be quicker than deleting everything and rebuilding it all.

So when do you need to use ghc-pkg? Typically I only use it when something breaks that I think should build properly. However, I've also found that having multiple versions of a package installed at the same time can sometimes cause problems. This can show up when the package I'm working on uses one version of a library, but when I'm experimenting in ghci a different version gets loaded. When this happens you may get perplexing error messages for code that is actually correct. In this situation, I've been able to fix the problem by using ghc-pkg to remove all but one version of the library in question.

If you've used all these tips and you still cannot install a package even after blowing away ~/.ghc, then there is probably a dependency issue in the package you're using. Haskell development is moving at a very rapid pace, so the upstream package maintainers may not be aware or have had time to fix the problem. You can help by alerting them to the problem, or better yet, including a patch to fix it.

Often the fix may be a simple dependency bump. These are pretty simple to do yourself. Use "cabal unpack foo-package-0.0.1" to download the package source and unzip it into the current directory. Then edit the .cabal file, change the bounds, and build the local package with "cabal install". Sometimes I will also bump the version of the package itself and then use that as the lower bound in the local package that I'm working on. That way I know it will be using my fixed version of foo-package. Don't be afraid to get your hands dirty. You're literally one command a way from hacking on upstream source.

For the impatient, here's a summary of my tips for basic cabal use:

Install the most recent versions of cabal-install
Don't install things with --global
Make sure $HOME/.cabal/bin is at the front of your path
Don't be afraid to use rm -fr ~/.ghc
Use ghc-pkg for fine-grained package control
User "cabal unpack" to download upstream code so you can fix things yourself

Using these techniques, I've found that Cabal actually works extremely well for small scale Haskell development--development where you're only working on a single package at a time and everything else is on hackage. Large scale development where you're developing more than one local package requires another set of tools. But fortunately we've already have some that work reasonably well. I'll discuss those in my next post.

Why Cabal Has Problems

2012-11-01T18:01:00.001-04:00

Haskell's package system, henceforth just "Cabal" for simplicity, has gotten some harsh press in the tech world recently. I want to emphasize a few points that I think are important to keep in mind in the discussion.

First, this is a hard problem. There's a reason the term "DLL hell" existed long before Cabal. I can't think of any package management system I've used that didn't generate quite a bit of frustration at some point.

Second, the Haskell ecosystem is also moving very quickly. There's the ongoing iteratees/conduits/pipes debate of how to do IO in an efficient and scalable way. Lenses have recently seen major advances in the state of the art. There is tons of web framework activity. I could go on and on. So while Hackage may not be the largest database of reusable code, the larger ones like CPAN that have been around for a long time are probably not moving as fast (in terms of advances in core libraries).

Third, I think Haskell has a unique ability to facilitate code reuse even for relatively small amounts of code. The web framework scene demonstrates this fairly well. As I've said before, even though there are three main competing frameworks, libraries in each of the frameworks can be mixed and matched easily. For example, web-routes-happstack provides convenience code for gluing together the web-routes package with happstack. It is 82 lines of code. web-routes-wai does the same thing for wai with 81 lines of code. The same thing could be done for Snap with a similar amount of code.

The languages with larger package repositories like Ruby and Python might also have small glue packages like this, but they don't have the powerful strong type system. This means that when a Cabal build fails because of dependency issues, you're catching an interaction much earlier than you would have caught it in the other languages. This is what I'm getting at when I say "unique ability to facilitate code reuse".

When you add Haskell's use of cross-module compiler optimizations to all these previous points, I think it makes a compelling case that the Haskell community is at or near the frontier of what has been done before even though we may be a ways away in terms of raw number of packages and developers. Thus, it should not be surprising that there are problems. When you're at the edge of the explored space, there's going to be some stumbling around in the dark and you might go down some dead end paths. But that's not a sign that there's something wrong with the community.

Note: The first published version of this article made some incorrect claims based on incorrect information about the number of Haskell packages compared to the number of packages in other languages. I've removed the incorrect numbers and adjusted my point.

LTMT Part 2: Monads

2012-04-17T08:30:00.000-04:00

In part 1 of this tutorial we talked about types and kinds. Knowledge of kinds will help to orient yourself in today's discussion of monads.

What is a monad? When you type "monad" into Hayoo the first result takes you to the documentation for the type class Monad. If you don't already have a basic familiarity with type classes, you can think of a type class as roughly equivalent to a Java interface. A type class defines a set of functions involving a certain data type. When a data type defines all the functions required by the type class, we say that it is an instance of that type class. When a type Foo is an instance of the Monad type class, you'll commonly hear people say "Foo is a monad". Here is a version of the Monad type class.

class Monad m where
    return :: a -> m a
    (=<<) :: (a -> m b) -> m a -> m b

(Note: If you're the untrusting type and looked up the real definition to verify that mine is accurate, you'll find that my version is slightly different. Don't worry about that right now. I did it intentionally, and there is a method to my madness.)

This basically says that in order for a data type to be an instance of the Monad type class, it has to define the two functions return and (=<<) (pronounced "bind") that have the above type signatures. What do these type signatures tell us? Let's look at return first. We see that it returns a value of type m a. This tells us that m has the kind signature m :: * -> *. So whenever we hear someone say "Foo is a monad" we immediately know that Foo :: * -> *.

In part 1, you probably got tired of me emphasizing that a type is a context. When we look at return and bind, this starts to make more sense. The type m a is just the type a in the context m. The type signature return :: a -> m a tells us that the return function takes a plain value a and puts that value into the context m. So when we say something is a monad, we immediately know that we have a function called return that lets us put arbitrary other values into that context.

Now, what about bind? It looks much more complicated and scary, but it's really pretty simple. To see this, let's get rid of all the m's in the type signature. Here's the before and after.

before :: (a -> m b) -> m a -> m b
after  :: (a -> b) -> a -> b

The type signature for after might look familiar. It's exactly the same as the type signature for the ($) function! If you're not familiar with it, Haskell's $ function is just syntax sugar for function application. (f $ a) is exactly the same as (f a). It applies the function f to its argument a. It is useful because it has very low precedence is right associative, so it is a nice syntax sugar that allows us to eliminate parenthesis in certain situations. When you realize that (=<<) is roughly analogous to the concept of function application (modulo the addition of a context m), it suddenly makes a lot more sense.

So now what happens when we look at bind's type signature with the m's back in? (f =<< k) applies the function f to the value k. However, the crucial point is that k is a value wrapped in the context m, but f's parameter is an unwrapped value a. From this we see that the bind function's main purpose is to pull a value out of the context m and apply the function f, which does some computation, and returns the result back in the context m again.

The monad type class does not provide any mechanism for unconditionally pulling a value out of the context. The only way to get access to the unwrapped value is with the bind function, but bind does this in a controlled way and requires the function to wrap things up again before the result is returned. This behavior, enabled by Haskell's strong static type system, provides complete control over side effects and mutability.

Some monads do provide a way to get a value out of the context, but the choice of whether to do so is completely up to the author of said monad. It is not something inherent in the concept of a monad.

Monads wouldn't be very fun to use if all you had was return, bind, and derived functions. To make them more usable, Haskell has a special syntax called "do notation". The basic idea behind do notation is that there's a bind between every line, and you can do a <- func to unwrap the return value of func and make it available to later lines with the identifier 'a'.

You can find a more detailed treatment of do notation elsewhere. I hear that Learn You a Haskell and Real World Haskell are good.

In summary, a monad is a certain type of context that provides two things: a way to put things into the context, and function application within the context. There is no way to get things out. To get things out, you have to use bind to take yourself into the context. Once you have these two operations, there are lots of other more complicated operations built on the basic primitives that are provided by the API. Much of this is provided in Control.Monad. You probably won't learn all this stuff in a day. Just dive in and use these concepts in real code. Eventually you'll find that the patterns are sinking in and becoming clearer.

The Less Travelled Monad Tutorial: Understanding Kinds

2012-04-16T08:30:00.000-04:00

This is part 1 of a monad tutorial (but as we will see, it's more than your average monad tutorial). If you already have a strong grasp of types, kinds, monads, and monad transformers, and type signatures like newtype RST r s m a = RST { runRST :: r -> s -> m (a, s) } don't make your eyes glaze over, then reading this won't change your life. If you don't, then maybe it will.

More seriously, when I was learning Haskell I got the impression that some topics were "more advanced" and should wait until later. Now, a few years in, I feel that understanding some of these topics earlier would have significantly sped up the learning process for me. If there are other people out there whose brains work somewhat like mine, then maybe they will be able to benefit from this tutorial. I can't say that everything I say here will be new, but I haven't seen these concepts organized in this way before.

This tutorial is not for absolute beginners. It assumes a basic knowledge of Haskell including the basics of data types, type signatures, and type classes. If you've been programming Haskell for a little bit, but are getting stuck on monads or monad transformers, then you might find some help here.

data Distance = Dist Double
data Mass = Mass Double

This code defines data types called Distance and Mass. The name on the left side of the equals sign is called a type constructor (or sometimes shortened to just type). The Haskell compiler automatically creates functions from the names just to the right of the equals sign. These functions are called data constructors because they construct the types Distance and Mass. Since they are functions, they are also first-class values, which means they have types as seen in the following ghci session.

$ ghci ltmt.hs
GHCi, version 7.0.3: http://www.haskell.org/ghc/  :? for helpghci> :t Dist
Dist :: Double -> Distance
ghci> :t Mass
Mass :: Double -> Mass
ghci> :t Distance
<interactive>:1:1: Not in scope: data constructor `Distance'

We see here that Dist and Mass are functions that return the types Distance and Mass respectively. Frequently you'll encounter code where the type and the constructor have the same name (as we have here with Mass). Distance, however, illustrates that these are really two separate entities. Distance is the type and Dist is the constructor. Types don't have types, so the ":t" command fails for Distance.

Now, we need to pause for a moment and think about the meaning of these things. What is the Distance type? Well, when we look at the constructor, we can see that a value of type Distance contains a single Double. The constructor function doesn't actually do anything to the Double value in the process of constructing the Distance value. All it does is create a new context for thinking about a Double, specifically the context of a Double that we intend to represent a distance quantity. (Well, that's not completely true, but for the purposes of this tutorial we'll ignore those details.) Let me repeat that. A type is just a context. This probably seems so obvious that you're starting to wonder about me. But I'm saying it because I think that keeping it in mind will help when talking about monads later.

Now let's look at another data declaration.

data Pair a = MkPair a a

This one is more interesting. The type constructor Pair takes an argument. The argument is some other type a and that is used in some part of the data constructor. When we look to the right side, we see that the data constructor is called MkPair and it constructs a value of type "Pair a" from two values of type "a".

MkPair :: a -> a -> Pair a

The same thing we said for the above types Distance and Mass applies here. The type constructor Pair represents a context. It's a context representing a pair of values. The type Pair Int represents a pair of Ints. The type Pair String represents a pair of strings. And on and on for whatever concrete type we use in the place of a.

Again, this is all very straightforward. But there is a significant distinction between the two type constructors Pair and Distance. Pair requires a type parameter, while Distance does not. This brings us to the topic of kinds. (Most people postpone this topic until later, but it's not hard to understand and I think it helps to clarify things later.) You know those analogy questions they use on standardized tests? Here's a completed one for you:

values : types    ::   types : kinds

Just as we categorize values by type, we categorize type constructors by kind. GHCi lets us look up a type constructor's kind with the ":k" command.

ghci> :k Distance
Distance :: *
ghci> :k Mass
Mass :: *
ghci> :k Dist
<interactive>:1:1: Not in scope: type constructor or class `Dist'
ghci> :k Pair
Pair :: * -> *
ghci> :k Pair Mass
Pair Mass :: *

In English we would say "Distance has kind *", and "Pair has kind * -> *". Kind signatures look similar to type signatures because they are. When we use Mass as Pair's first type argument, the result has kind *. The Haskell report defines kind signatures with the following two rules.

The symbol * represents the kind of all nullary type constructors (constructors that don't take any parameters).
If k1 and k2 are kinds, then k1->k2 is the kind of types that take one parameter that is a type of kind k1 and return a type of kind k2.

As an exercise, see if you can work out the kind signatures for the following type constructors. You can check your work with GHCi.

data Tuple a b = Tuple a b
data HardA a = HardA (a Int)
data HardB a b c = HardB (a b) (c a Int)

Before reading further, I suggest attempting to figure out the kind signatures for HardA and HardB because they involve a key pattern that will come up later.

Welcome back. The first example is just a simple extension of what we've already seen. The type constructor Tuple has two arguments, so it's kind signature is Tuple :: * -> * -> *. Also if you try :t you'll see that the data constructor's type signature is Tuple :: a -> b -> Tuple a b.

In the case of the last two types, it may be a little less obvious. But they build on each other in fairly small, manageable steps. For HardA, in the part to the left of the equals sign we see that there is one type parameter 'a'. From this, we can deduce that HardA's kind signature is something of the form ? -> *, but we don't know exactly what to put at the question mark. On the right side, all the individual arguments to the data constructor must have kind *. If (a Int) :: *, then the type 'a' must be a type constructor that takes one parameter. That is, it has kind * -> *, which is what we must substitute for the question mark. Therefore, we get the final kind signature HardA :: (* -> *) -> *.

HardB is a very contrived and much more complex case that exercises all the above simple principles. From HardB a b c we see that HardB has three type parameters, so it's kind signature has the form HardB :: a -> b -> c -> *. On the right side the (a b) tells us that b :: * and a :: * -> *. The second part (c a Int) means that c is a type constructor with two parameters where its first parameter is a, which has the type signature we described above. So this gives us c :: (* -> *) -> * -> *. Now, substituting all these in, we get HardB :: (* -> *) -> * -> ((* -> *) -> * -> *) -> *.

The point of all this is to show that when you see juxtaposition of type constructors (something of the form (a b) in a type signature), it is telling you that the context a is a non-nullary type constructor and b is its first parameter.

Continue on to Part 2 of the Less Travelled Monad Tutorial

Four Tips for New Haskell Programmers

2012-04-15T09:00:00.000-04:00

The Haskell programming language is widely considered to have a fairly steep learning curve--at least compared with mainstream languages. In my experience with Haskell and specifically helping newcomers I've noticed a few common issues that seem to come up again and again. Some of these issues might be more avoidable if the Haskell community did a better job communicating them. Four points I have noticed are:

Read Haddock API docs
Pay attention to type class instances
Learn about kinds
Learn monad transformers

Read Haddock API Docs

I mention this point at the risk of stating the obvious. If you are going to become a proficient Haskell programmer, it's absolutely essential that you get used to reading the API docs for the packages you use. I often hear newcomers ask for tutorials demonstrating how to use packages. Our community would definitely be better off with tutorials for every package, but it would also be better if newcomers would pay more attention to the API docs. Now I know you're probably thinking, "yeah, but most packages are poorly documented." That is true, but Haskell's type signatures tell you a lot more about a function than other languages. For instance, consider the following example:

readChan :: Chan a -> IO a

A Chan is essentially a queue. You can put values in and get them out in FIFO order. When you are trying to understand the above function, one of the first things you might wonder about it is whether it blocks or not. But if you think about it a little more, you'll realize that this function has to block. If it didn't block, then there might not be a value and there would be no way to return something of type a (because Haskell has no null pointers). A non-blocking version would have to have a type signature like this:

tryReadChan :: Chan -> IO (Maybe a)

So even with no prose documentation added at all, you can still learn a lot from the type signatures. This is more significant in Haskell than other languages because of Haskell's purity and its strong type system. Also, I would recommend that you bookmark the url "http://hackage.haskell.org/package/". Actually, better yet, type it into your web browser frequently so it is the first thing given to you by the autocorrect when you start typing "hack...". Once you auto-complete that url, you can just type the name of the package you are looking for and you'll immediately get to the most recent API docs for that package. It's way faster than hitting control-f and searching through the package list on that page.

Also, bookmark http://www.haskell.org/ghc/docs/latest/html/libraries/index.html because it has links to documentation for the core libraries.

Pay Attention to Type Class Instances

I can't emphasize this point enough. One of the most common questions I get from beginners is how to run an IO function in some random monad. This information is trivially visible in the API docs, but for some reason beginners never seem to notice. Take for example the Snap monad. Go ahead, click that link and look at the documentation. The clue that you can run IO actions inside that monad is tucked away near the end of the "Instances" block. It's one little innocuous line MonadIO Snap. Newcomers might not be familiar with MonadIO, but if they click the link they'll see that it defines one function liftIO :: IO a -> m a that converts any function in the IO monad to a function in the current m monad. Those instance lines contain a treasure trove of information. Don't neglect them.

Learn About Kinds

In Haskell all values have a type. Analogously, all types have a kind. This topic is often not brought up until later, but I feel that understanding kinds gives beginners a big advantage in understanding type signatures. I'm not going to go into it in detail here, but I think it's an important concept that is too often ignored.

Learn About Monad Transformers

This is another one of those topics that is often put off until later. When I was learning monads, I distinctly remember getting the impression that monad transformers were a much more complicated beast and that I didn't need to learn about them at that time. But when I finally did learn about monad transformers a lot of things became clearer for me. Also, monad transformers are used all the time in real world applications. Transformers are a much simpler concept than monads, especially if you know about kinds. There's no reason not to learn them at the same time.

A Hopefully Fair and Useful Comparison of Haskell Web Frameworks

2012-04-10T22:46:00.000-04:00

Recently there has been a lot of discussion and questions about the differences between the big three Haskell web frameworks: Happstack, Yesod, and Snap. Different pieces of the answer have been discussed in a number of places. In this post, I'd like to try to give a more complete comparison. Hopefully it will be relatively unbiased, but without being too watered down to be useful. I've succeeded if you can't tell which framework I'm a major contributor to based solely on the text of this post.

Happstack

First, up is Happstack, the oldest of the three with original commit history as early as February, 2005. Happstack used to be called HAppS. It was primarily composed of a web server based on lazy IO, a fairly radical (for the time) in-memory persistence approach for storing and versioning native Haskell data types, and a library called IxSet for making it easier to use this state system with relational data access patterns. I've heard a number of people describe HAppS (and Happstack) as being synonymous with this unconventional state system, but today the state system has been completely rewritten and rebranded as a standalone persistence system called acid-state.

Of the three frameworks, Happstack is probably the least monolithic and exists mostly as a loose collection of libraries that can be mixed and matched to suit one's needs. A quick search for "happstack" on hackage will reveal a large number of libraries providing a diverse range of functionality. This includes support for at least four template systems: Hamlet, Heist, HSP, and StringTemplate. The main Happstack maintainer also maintains a type-safe URL called web-routes which, if carefully used, provides compile-time guarantees that your site won't have broken internal links.

While Happstack includes support for the widest range of choices, its most visible members do seem to favor a few in particular. Based on the current Happstack Crash Course, I would guess that the canonical libraries[1] for Happstack probably include BlazeHtml and HSX/HSP for templating, web-routes for routing, and acid-state for persistence. Acid-state and its all-haskell persistence philosophy combine with the type-safe routing and templates to create a set of libraries for web development where Haskell's expressive type system is king.

Yesod

The next of the big three to hit the scene was Yesod, which released in March of 2010. While Happstack (and later Snap) applications only worked as standalone binaries that were their own web server, Yesod provided FastCGI support which enabled Yesod applications to run on shared hosting where running a standalone web server was not an option. Perhaps Yesod's defining characteristic is its strong emphasis on static type checking for all aspects of the web app enabled by a number of custom DSLs used in different areas. In January 2011, the Yesod team released a new modern web server called Warp sporting the fastest benchmark numbers of any Haskell web server, a title still held today.

Yesod's type safety starts with the Hamlet compile time template language with syntax derived from HAML, a markup language that is lighter than (X)HTML. Hamlet's syntax makes it really simple to put dynamic data in templates while remaining strongly typed. This fits really well with Yesod's type-safe routing DSL that generates links for you. The paradigm is very similar to using Happstack with HSX/HSP and web-routes, but with a custom DSL that is more compact. Yesod has taken things a step further though with their Shakespearean template system which they have used to create Cassius and Julius, two strongly typed compile-time DSLs for generating CSS and Javascript.

In working with this paradigm, Yesod developers observed that some amount of boilerplate code was usually required to accomplish all this type safety. Leveraging the power of TemplateHaskell and quasiquoting, Yesod provides small domain-specific languages with syntax customized to each unique purpose that let you specify your site with very little unnecessary cruft.

Additionally, Yesod created a generalized database library called persistent, which uses these same design patterns to create a DSL for specifying your site's data model and lets you easily use MySQL, PostgreSQL, SQLite, or MongoDB to store your data and interact with it in a type safe manner.

This week Yesod released 1.0 milestone, communicating that they have reached a point where they will be maintaining longer-term API stability and support.

Snap

Snap is the youngest of the three frameworks. It went public in May of 2010, two months after Yesod. Its initial release featured a template system called Heist, and the first web server implementation to use the new modern concept of left-fold enumerators, a technique for achieving more predictable space usage than lazy IO. The web server API provides a set of combinators that provides a flexible framework for creating both simple and complex routes. This API is essentially a slimmed down and simplified version of the API that Happstack has been using since the early days of HAppS, and as such it should be fairly straightforward to port applications and libraries between the two.

The Heist template system differs from Hamlet and HSP in that it reads templates at runtime rather than compile-time, essentially thinking of templates as data rather than code. This means that it can't do truly type-safe URLs like the other two, but it enforces a much stronger division between code and view. It also makes it possible for templates to be reloaded without recompiling the application. Aside from the fact that it allows you to define your own tags dynamically, Heist's template syntax is valid HTML.

More recently, Snap released a component system called Snaplets which is designed to allow web apps to be built from self-contained modular components. The Snaplets API provides a composable way to handle things like built-in filesystem resources and installation, config file support, and in-memory state. Since the release of the Snaplets API, the Snap team and third-party developers have released a number of snaplets providing support for sessions, authentication, database integration, etc. Yesod provides something called subsites that looks similar, and based on Happstack's roadmap it sounds like they will be working on another take on this problem in the future.

Snap's canonical libraries appear to be just Snap and Heist. The Snap web server is actually split out into two separate libraries snap-core and snap-server while the Snaplet API is the umbrella project. Other than that, the Snap team hasn't pledged allegiance to any particular database library so you should be free to use anything.

Conclusion

Each of the three frameworks has their own unique perspective. They make different tradeoffs, and have different senses of code aesthetic. There's the tradeoff of static, type-safe, and determined at compile-time versus less type-safe, more flexible, and determined at run-time. There's also the tradeoff of concise custom DSLs versus expressive and powerful combinator libraries. Do you go with a generalized database library that provides unified and necessarily watered-down interface to a number of different backends or tie yourself to a single specific database and leverage its full power? These are not always binary choices either. Each of these tradeoffs may be an axis on which there are several or a continuum of valid points to choose from.

Keep in mind that in most cases, different components of the above frameworks can be mixed and matched to suit your needs. Hopefully this post paints a clearer picture of the landscape and helps you find the framework (or combination of frameworks) that fits your needs and preferences best.

[1] When I use the term "canonical libraries" in this article I'm talking about what I infer is probably the preference used by the main developers maintaining each web framework, and this is likely to be the direction the framework as a whole moves in with a more holistic solution if it chooses to do so.

What's in a name? A lot.

2011-12-06T11:20:00.001-05:00

One letter identifier names have been getting bad press recently. The other day a post entitled Name Your Type Variables! got some discussion on the Haskell reddit. I agree with the author's value of good names, but I disagree with the specific examples he uses as well as his sweeping condemnation of one letter names. Since I am the primary author of one of his examples and have contributed code to his other example, I believe I am qualified to comment.

Here's the executive summary for the tl;dr crowd:

Different naming scopes have different needs for names. Call the two extremes of this continuum rare and prevalent.
Sometimes (especially with prevalent names that have large scope) there's too much context to communicate, so no name of reasonable length can be as descriptive as the one-letter critics seem to want.
A general rule of thumb is that prevalent abstractions should be given shorter names and rare abstractions should be given longer names.
Single letter names communicate patterns, long names communicate meaning. Both have their place.

Names are crucially important to writing readable, maintainable code. As I've said before, I consider this one of the most significant things I've learned over my programming career. I came to Haskell as a Java developer who had completely embraced the philosophy of using long, descriptive, unabbreviated identifiers. But writing code that is easy to read and maintain is about communication, and as any good writer will tell you, longer is not always better. A good name is one that clearly and concisely communicates the meaning of the abstraction it represents.

Like their corresponding language constructs, names have different scope. This means that they will have varying degrees of importance. A rare name used for an intermediate value deep in the internals of a library has much less impact on developers than a prevalent name used pervasively throughout a public API. I would like to suggest that longer, more descriptive names are more appropriate for rare concepts, while shorter abbreviated names are often appropriate for prevalent concepts.

First of all, it should be obvious that this argument is supported from a data compression standpoint. (The idea that this perspective is a useful axis in the space of code assessment metrics is argued nicely by Paul Graham in his essay Holding a Program in One's Head, so I will not go into it here.) Second, prevalent concepts will be closer to the reader's top-of-mind, so a well-chosen short name may be sufficient to jog the reader's memory and identify the concept. Third, prevalent concepts will generally require more involved explanations. It will be much less likely that a standalone name will fully communicate everything the reader needs to know about the concept. Why use a long name, when it still won't be enough to get the job done?

With this in mind, let's look at specific examples. Patrick mentions that the use of single letter type variables in Handler b v a contributed to slow progress in understanding the snaplet API we recently released in version 0.6 of the Snap Framework. If I were changing the code to satisfy his article, I would probably go with Handler base view a as the best verbose alternative. But would this really be helpful?

First of all, scan the above paragraph with your eyes. Which is more recognizable? I intentionally didn't use quotation marks or font distinctions. Handler b v a jumps right off the page at me, while Handler base view a blends in. This isn't necessarily a 100% valid point because the surrounding context is prose rather than code, but I think it does make the point that the shorter names are easier to scan. And of course, it makes perfect sense. There's less noise for the eye to sort through.

Secondly, if you saw the type Handler base view a, would that really aid a newcomer's understanding more than the single letter variant? I contend that in this case it would not. base could refer to a numerical radix, and view could have any number of meanings. Because they are more familiar to people, their meaning is more ambiguous. To help people more, we'd probably have to go to something like Handler baseSnaplet viewSnaplet a. But that's just starting to get noisy. It would give us the following type signature:

nestSnaplet :: ByteString
            -> (Lens viewSnapletA (Snaplet viewSnapletB))
            -> SnapletInit baseSnaplet viewSnapletB
            -> Initializer baseSnaplet viewSnapletA (Snaplet viewSnapletB)

which I find much less readable than the current one:

nestSnaplet :: ByteString
            -> (Lens v (Snaplet v1))
            -> SnapletInit b v1
            -> Initializer b v (Snaplet v1)

In the second type signature it's immediately obvious to the naked eye where the type variables are. But in the first one it's difficult to tell the long type variables apart from the type constructors. It might not be obvious, but I did put significant thought into the choice of b v a [1], and as a result, any time you see this general pattern of type variables, you instantly have a pretty good idea that you're dealing with a MonadSnaplet.

On top of all this, the new reader still probably wouldn't understand what viewSnaplet and baseSnaplet mean. There is a lot of context that needs to be communicated before someone can really understand them. We spent a lot of effort trying to make it as simple as possible, but I think the OP is confusing essential complexity of the problem domain with "ambiguity" allegedly caused by short names [2]. That is why the newcomer will find the convention clearly described in the API documentation.

The same argument can be applied to the other example Patrick mentioned of Form m i e v a in the digestive-functors library. It's a pervasive paradigm where that sequence of single letter type variables is very distinct and makes it easier to recognize patterns in the types.

In Haskell, type variables have an especially prevalent scope. As we have seen, they can embody patterns that exist across entire APIs. This makes them especially good candidates for single letter names. In a StackExchange discussion about why mathematicians use single letter variables one person commented, "Because it's long, it makes it hard to see patterns, and it makes you think about interpretation when you should be thinking about form." This concept is especially important in type signatures.

However, on the other end of the spectrum, I think it's extremely helpful to have more descriptive names for rare abstractions. For examples of me using longer names, see functions like getSnapletUserConfig or runChildrenWithText.

Good names make software more readable and maintainable. Long, descriptive names do serve a valuable purpose in making code more understandable. But we shouldn't just assume that they are always better. Sometimes, patterns can be more important than meaning, and maintainability is better achieved by explicit rather than implicit documentation. Just make sure that if you go this route, you don't neglect to inform the reader of the meaning behind the letters.

As evidenced by the existence of this commit.↩
As Albert Einstein said, "Make things as simple as possible, but not simpler." ↩

Patterns in Chess Square Enumerations

2011-04-20T06:52:00.000-04:00

In my bit manipulation post awhile back I posed a problem involving "closed form" calculation of chess endgame table indices. Back when I originally solved the problem, it was a big help to create some visualizations of some of the patterns embedded in the square numbering scheme. I had mentioned that I thought the patterns were interesting, so I thought I'd come back and elaborate on that statement.

One way of visualizing some of the patterns involved is to partition the squares according to the equivalence classes defined by the binary bits of the index. Bits 0-2 are the three low-order bits and bits 3-5 are the three high-order bits. Here are the equivalence classes defined by each of the bits of the natural square numbering.

Bit 0

70	71	72	73	74	75	76	77
60	61	62	63	64	65	66	67
50	51	52	53	54	55	56	57
40	41	42	43	44	45	46	47
30	31	32	33	34	35	36	37
20	21	22	23	24	25	26	27
10	11	12	13	14	15	16	17
00	01	02	03	04	05	06	07

Bit 3

70	71	72	73	74	75	76	77
60	61	62	63	64	65	66	67
50	51	52	53	54	55	56	57
40	41	42	43	44	45	46	47
30	31	32	33	34	35	36	37
20	21	22	23	24	25	26	27
10	11	12	13	14	15	16	17
00	01	02	03	04	05	06	07

Bit 1

70	71	72	73	74	75	76	77
60	61	62	63	64	65	66	67
50	51	52	53	54	55	56	57
40	41	42	43	44	45	46	47
30	31	32	33	34	35	36	37
20	21	22	23	24	25	26	27
10	11	12	13	14	15	16	17
00	01	02	03	04	05	06	07

Bit 4

70	71	72	73	74	75	76	77
60	61	62	63	64	65	66	67
50	51	52	53	54	55	56	57
40	41	42	43	44	45	46	47
30	31	32	33	34	35	36	37
20	21	22	23	24	25	26	27
10	11	12	13	14	15	16	17
00	01	02	03	04	05	06	07

Bit 2

70	71	72	73	74	75	76	77
60	61	62	63	64	65	66	67
50	51	52	53	54	55	56	57
40	41	42	43	44	45	46	47
30	31	32	33	34	35	36	37
20	21	22	23	24	25	26	27
10	11	12	13	14	15	16	17
00	01	02	03	04	05	06	07

Bit 5

70	71	72	73	74	75	76	77
60	61	62	63	64	65	66	67
50	51	52	53	54	55	56	57
40	41	42	43	44	45	46	47
30	31	32	33	34	35	36	37
20	21	22	23	24	25	26	27
10	11	12	13	14	15	16	17
00	01	02	03	04	05	06	07

Here we can clearly see the natural row and column oriented behavior of the index. Nothing earth shattering. If we take octal digits instead of binary digits to define our equivalence class, we get the following more colorful partition.

Low Digit

70	71	72	73	74	75	76	77
60	61	62	63	64	65	66	67
50	51	52	53	54	55	56	57
40	41	42	43	44	45	46	47
30	31	32	33	34	35	36	37
20	21	22	23	24	25	26	27
10	11	12	13	14	15	16	17
00	01	02	03	04	05	06	07

High Digit

70	71	72	73	74	75	76	77
60	61	62	63	64	65	66	67
50	51	52	53	54	55	56	57
40	41	42	43	44	45	46	47
30	31	32	33	34	35	36	37
20	21	22	23	24	25	26	27
10	11	12	13	14	15	16	17
00	01	02	03	04	05	06	07

Now on to the interesting stuff. Here are the same six equivalence classes of the less obvious square numbering for which I posed my puzzle.

Bit 0

64	04	14	24	26	16	06	66
05	65	34	44	46	36	67	07
15	35	74	54	56	76	37	17
25	45	55	75	77	57	47	27
21	41	51	71	73	53	43	23
11	31	70	50	52	72	33	13
01	61	30	40	42	32	63	03
60	00	10	20	22	12	02	62

Bit 3

64	04	14	24	26	16	06	66
05	65	34	44	46	36	67	07
15	35	74	54	56	76	37	17
25	45	55	75	77	57	47	27
21	41	51	71	73	53	43	23
11	31	70	50	52	72	33	13
01	61	30	40	42	32	63	03
60	00	10	20	22	12	02	62

Bit 1

64	04	14	24	26	16	06	66
05	65	34	44	46	36	67	07
15	35	74	54	56	76	37	17
25	45	55	75	77	57	47	27
21	41	51	71	73	53	43	23
11	31	70	50	52	72	33	13
01	61	30	40	42	32	63	03
60	00	10	20	22	12	02	62

Bit 4

64	04	14	24	26	16	06	66
05	65	34	44	46	36	67	07
15	35	74	54	56	76	37	17
25	45	55	75	77	57	47	27
21	41	51	71	73	53	43	23
11	31	70	50	52	72	33	13
01	61	30	40	42	32	63	03
60	00	10	20	22	12	02	62

Bit 2

64	04	14	24	26	16	06	66
05	65	34	44	46	36	67	07
15	35	74	54	56	76	37	17
25	45	55	75	77	57	47	27
21	41	51	71	73	53	43	23
11	31	70	50	52	72	33	13
01	61	30	40	42	32	63	03
60	00	10	20	22	12	02	62

Bit 5

64	04	14	24	26	16	06	66
05	65	34	44	46	36	67	07
15	35	74	54	56	76	37	17
25	45	55	75	77	57	47	27
21	41	51	71	73	53	43	23
11	31	70	50	52	72	33	13
01	61	30	40	42	32	63	03
60	00	10	20	22	12	02	62

And for the octal digits...

Low Digit

64	04	14	24	26	16	06	66
05	65	34	44	46	36	67	07
15	35	74	54	56	76	37	17
25	45	55	75	77	57	47	27
21	41	51	71	73	53	43	23
11	31	70	50	52	72	33	13
01	61	30	40	42	32	63	03
60	00	10	20	22	12	02	62

High Digit

64	04	14	24	26	16	06	66
05	65	34	44	46	36	67	07
15	35	74	54	56	76	37	17
25	45	55	75	77	57	47	27
21	41	51	71	73	53	43	23
11	31	70	50	52	72	33	13
01	61	30	40	42	32	63	03
60	00	10	20	22	12	02	62

Ahhhhhh....I don't know about you, but I think that's a beautiful square numbering. There's also plenty of group theory going on. What do you see here?

The Haskell code used to generate these tables is here.

Splice Subtleties

2011-04-18T10:18:00.014-04:00

In the recent release of Heist 0.5.1, there was performance bug in my implementation of head merging. I turned off the head merging, and then fixed the bug but did not reenable head merging. If you want to turn it back on, you need to bind the html tag to the htmlImpl function from the Text.Templating.Heist.Splices.Html module. I think I'll continue to leave it off by default because it does have some potential to impact performance.

While analyzing the problem, I realized that it involves fairly obscure details of Heist internals that have not been mentioned in any of our tutorial materials. And if I, the original author of Heist fell prey to this problem, it's probably safe to assume that eventually someone else will too. So let's take a look at some details of Heist's internal behavior and the implications for splice developers.

As I alluded to in Heist in 60 Seconds, you can think of a splice as follows:

type Splice = Node -> m [Node]

The actual implementation is slightly different because we use a reader monad for the parameter node, but this is a useful mental model.

Heist is kind of like one big fmap on the whole DOM tree. If there were no splices bound, the fmapped function would be id. When you bind a splice to a tag <foo>, the splice function is applied to every occurrence of that tag. The whole tag and all its children become the splice's parameter, and they are replaced by the output of the splice in the rendered document.

Splices can be divided into two broad categorizations: substitutions and filters. Substitution splices are where the spliced tag disappears in the output. If the spliced tag is preserved in the output, then it's a filter splice.

Substitution splices probably the most common. All uses of the bind tag are substitutions. But my initial implementation of head merging in Heist 0.5.1.0 used a filter splice bound to the html tag. If you're writing a filter splice, you MUST call the stopRecursion function somewhere in the splice or you'll get either wrong or slow behavior! If you're not interested in the details behind this, you can stop reading now. Otherwise, let's look at the function Heist uses to process nodes.

runNode :: Monad m => X.Node -> Splice m
runNode (X.Element nm at ch) = do
    newAtts <- mapM attSubst at
    let n = X.Element nm newAtts ch
    s <- liftM (lookupSplice nm) getTS
    maybe (runKids newAtts) (recurseSplice n) s
  where
    runKids newAtts = do
        newKids <- runNodeList ch
        return [X.Element nm newAtts newKids]
runNode n                    = return [n]

The highlighted lines are the important ones here. First it does a lookup to see if there are any splices bound to the tag that we're currently processing. Then, if we found a splice, we call recurseSplice and pass it the current node. Here's the code for recurseSplice.

recurseSplice :: Monad m => X.Node -> Splice m -> Splice m
recurseSplice node splice = do
    result <- localParamNode (const node) splice
    ts' <- getTS
    if _recurse ts' && _recursionDepth ts' < mAX_RECURSION_DEPTH
        then do modRecursionDepth (+1)
                res <- runNodeList result
                restoreTS ts'
                return res
        else return result
  where
    modRecursionDepth :: Monad m => (Int -> Int) -> TemplateMonad m ()
    modRecursionDepth f =
        modifyTS (\st -> st { _recursionDepth = f (_recursionDepth st) })

The first highlighted line here executes the splice. The second one runs all the result nodes--which executes all the splices again. If the splice is a filter splice, then the the same splice will appear in the result list and you'll get infinite recursion.

As you can see, Heist does have checks to detect this situation and terminate if the recursion gets too deep. There is also a flag that can be set to prevent recursion altogether. You can set this flag inside your splices by calling the stopRecursion function. Recursion is turned on by default because that's what you usually want to happen for substitution splices. But remember this, and make sure you call stopRecursion if you're writing filter splices!

Heist Template Abstractions in a Nutshell

2011-04-15T15:10:00.000-04:00

In the last post I discussed how logic and control flow can (and I argue should) be done in splices where types, higher order functions, and the full power of Haskell can be applied to the problem. In this post I want to take some time to think about the raw materials that are available in templates.

At the lowest level, we have just Text (...which is certainly /= Nothing). The templates are read in as Text and parsed into HTML DOM structures: elements, children, and attributes. Heist's abstractions for these entities are roughly analogous to the lambda calculus. The lambda calculus primitives are function definition and function application. HTML structures don't have any kind of representation for functions, so Heist uses lists of DOM tree nodes as the fundamental unit. Two different ways of representing them are splices and templates. The following table summarizes Heist's HTML abstraction tools.

	Definition	Application /Evaluation
Splices	<bind>	use the tag
Templates	file on disk	<apply>

To define a splice, use the bind tag. To define a template, create a file on disk. To apply/evaluate a splice, just use the tag that you bound. To apply/evaluate a template, use the apply tag. The Heist tutorial has the details on how to use <bind> and <apply>. Splices and templates can both be thought of as functions because their methods of application allow data to be passed in to modify the output.

We've consciously avoided introducing generalized control flow that requires expressions and types--things that HTML is not suited for. But the abstractions that are available in templates work well with the primitives naturally available in the domain. This yields a powerful template system with syntax that designers already understand and can manipulate with existing tools.

Looping and Control Flow in Heist

2011-04-14T08:20:00.003-04:00

One of the most frequent questions I get about Heist is how to do loops or control flow in Heist templates. I usually respond that we've tried to avoid introducing these constructs into templates to encourage a better separation between view and model/controller. In this post I want to discuss the issue in more detail so that my thoughts are stored and I can refer people here in the future.

Since Haskell is pure and has a strong static type system, the first thing to think about when discussing this question is what types will be involved. Since templates are processed at runtime, they do not have access to Haskell's type system. This puts us square in the middle of byte-land. No generalized looping over things like the list of registered users or recent posts. No type-safe evaluation of arbitrary expressions. It is my contention that you're better off solving these problems with a language designed for that purpose...i.e. in Haskell splices, and not in HTML templates.

Let's continue the example of displaying blog posts used previously. We developed a function postSplice :: Splice m (don't worry about the 'm' for now) that our templates could use to render a single post using whatever markup the template designer specified. Now we want to use a looping structure to reuse that code for a list of posts. Where does this list come from? It comes from Haskell code (not templates), so it's logical to do our looping abstraction in Haskell. I would probably refactor the postSplice function as follows.

renderPost :: Monad m => Post -> Splice m
renderPost post = do
  runChildrenWithText [("postTitle", postTitle post)
                      ,("postBody", postBody post)]

Notice that this function is no longer a splice. It's a function that takes a Post as input and generates a splice as output. Now we can use the new mapSplices function introduced in Heist 0.5.1.0 to render a list of posts.

renderPosts :: Monad m => [Post] -> Splice m
renderPosts = mapSplices renderPost

That was easy. Now one more step gets us a splice that we can bind to the <recentPosts/> tag and use in our templates.

recentPostsSplice :: Splice Application
recentPostsSplice = getRecentPosts >>= renderPosts

This splice can be used in a template exactly the same way we did before. The only difference is that the view we passed into the splice is now applied to each post in the list and the results are concatenated.

I specialized this function to the Application monad which will contain functionality specific to your application that provides the necessary context for the getRecentPosts function. I left out the details of that function because those details aren't something the template author should worry about. And here we get to the main point. The core of Heist's keep-application-logic-out-of-the-view philosophy boils down to the idea that you're better off creating a domain-specific set of query functionality than exposing too much generality to the templates.

One likely avenue of domain-specific query generalization might be to look at only the posts with a certain tag. We might do something like this.

postsWithTag :: Text -> Splice Application
postsWithTag tag = getTaggedPosts tag >>= renderPosts

postsWithTagSplice :: Splice Application
postsWithTagSplice = do
    node <- getParamNode
    maybe (return []) postsWithTag $ getAttribute "tag" node

Then with the appropriate splice binding, we can do this in our templates.

<postsWithTag tag="heist"/>

Or, instead of getting the tag from an attribute of the param node, we could do this instead.

postsWithTagSplice :: Splice Application
postsWithTagSplice = do
    tag <- lift $ getParam "tag"
    maybe (return []) postsWithTag tag

In the Snap template project, Application has a MonadSnap instance, so we can lift the getParam function into the splice's monad. This gets the tag from the HTTP request parameters of whatever request is being processed when <postsWithTag> is rendered. This makes it easy to tie into values gathered from a form or even specified manually in the query string.

Hopefully this demonstrates how templates can interact with looping and control flow defined in Haskell code using the gorgeous syntax we all know and love, and how we can leverage Haskell's powerful abstraction constructs to create nice domain-specific markup languages that are easy for designers to incorporate into their web designs. In the next post I'll look more closely into the abstractions available exclusively in templates.

EDIT: To clarify, the splices in this post will be used in exactly the same way the <post> splice was used in the last post. The different splice just changes the context in which the passed-in parameters are used. For example:

<recentPosts>
<h1><postTitle/></h1>
<div><postBody/></div>
</recentPosts>

Views, Controllers, and Heist

2011-04-13T08:55:00.010-04:00

A very common question when using Heist is how to specify views in a splice. There are three different approaches one can take:

1. Specify a splice's view in the Haskell code implementing the splice.
2. Get a splice's view from a template.
3. Pass the desired view to the splice as the spliced tag's child nodes.

Aproach #1 tends to be ugly and violates the principle of separating logic and view. There are always exceptions to every rule, so we've done a little bit to ease the implementation of #1 by allowing xmlhtml DOM structures to be built with blaze-html syntax. However, I believe that one of the other approaches will usually be preferable.

Approach #2 seems kind of awkward. It would result in a whole bunch of small templates on disk that define little pieces of web pages. An architecture like this might be desireable in some situations as a way to eliminate repetition (and it certainly fits into the functional programming mentality of lots of small functions), but it is quite different from the page-oriented structure most designers are used to.

Approach #3 is our recommended pattern. It allows you to keep your view completely in the template and the logic completely in the splice. Here's an example of how this might work. Let's use the simple example of displaying blog posts. We want to create a <post> splice.

data Post = Post
  { postTitle :: Text
  , postBody :: Text
  }

postSplice = do
  post <- getPostFromDatabase
  runChildrenWithText [("postTitle", postTitle post)
                      ,("postBody", postBody post)]

Then we might use it in a template like this:

<post>
  <h1><postTitle/></h1>
  <div><postBody/></div>
</post>

The template is basically saying, "Give me a post, but here's how I want it to look." The splice is only responsible for getting the appropriate data and passing it back to the template as raw text.

The function runChildrenWithText makes this more convenient. It binds a list of constant text splices before getting the children from the param node, "running" them to expand all referenced splices, and returning the result. After the child nodes are run, the newly bound splices are unbound. They only exist in the scope of the child nodes.

This model provides a nice division of labor between programmers and designers. The programmers build a library of splices that provide access to dynamic site data. This creates a domain-specific markup language with syntax that designers are already familiar with. It's similar to what Facebook has done with FBML. And I have found that from my perspective as a Haskell programmer, it even makes writing HTML kind of fun.

Heist in 60 Seconds

2011-04-11T09:04:00.088-04:00

A template system is a bridge between static data (templates) and dynamic data.

Heist is a template system bridging HTML templates and Haskell code.

A splice is code that Heist binds to an HTML tag.

Every time the tag appears in a template, Heist runs the splice bound to that tag and passes the tag (including its attributes and its children) as input to the splice.

A splice's output is a list of tags that get substituted into the template in place of the original input tag.

Splices can be thought of as functions that can be called from templates to get dynamic data.

Splices can pass this dynamic data back to templates by (temporarily) binding new splices.

<bind> is a tag you can use in your templates to create new splices on the fly.

<apply> is a tag that lets you insert one template into another.

A more in-depth tutorial is here.

Heist Gets Blaze Syntax

2010-12-26T10:36:00.004-05:00

Update: Heist has switched from using hexpat to using xmlhtml as of version 0.5. You can still use blaze syntax as described in this post, but you have to import Text.Blaze.Renderer.XmlHtml instead.

Users of Heist, my Haskell templating system, got a very nice surprise for Christmas this year when Jasper Van der Jeugt uploaded a new package blaze-html-hexpat to Hackage. If you're not familiar with Heist, you should probably check out the tutorial before reading further. Heist uses the Haskell XML library hexpat for XML template parsing and internal representation. Users are encouraged to put as much markup as possible into templates and keep Haskell-generated markup to a minimum. However, it is impractical to do this 100% of the time.

When the situation arises where you do want to generate bits of markup in code, you have to generate hexpat data structures. Hexpat does provide some convenience functions for this purpose (see the Tree and NodeClass modules), but most would agree that it's a rather poor way to generate HTML from Haskell. Here's an example:

postSplice :: ByteString -> ByteString -> ByteString -> Splice Application
postSplice title author body = do
    return $
      [X.Element "div" [("class","post")] $
        [ X.Element "h1" [("class", "post_title")] $
            [X.Text title]
        , X.Element "div" [("class", "post_author")] $
            [X.Text author]
        , X.Element "div" [("class", "post_body")] $
            [X.Text body]
        ]
      ]

With the new blaze-html-hexpat package, we can use the same DSL used by blaze-html. This allows us to rewrite the above code like this:

postSplice2 :: Text -> Text -> Text -> Splice Application
postSplice2 title author body = return . renderHtml $ do
    H.div ! A.class_ "post" $ do
        H.h1 ! A.class_ "post_title" $ H.text title
        H.div ! A.class_ "post_author" $ H.text author
        H.div ! A.class_ "post_body" $ H.text body

Ahhhhh, much nicer. Blaze is encoding-aware, so it works better with Text than ByteString. However, we could have done a manual conversion or used H.unsafeByteString instead of H.text if we had wanted to stick with the ByteStrings. The renderHtml function comes in the new blaze-html-hexpat package and generates the Hexpat Node list required by splices. Here are the imports blaze-related imports needed for this code:

import Text.Blaze.Html5 (Html, (!))
import qualified Text.Blaze.Html5 as H
import qualified Text.Blaze.Html5.Attributes as A
import Text.Blaze.Renderer.Hexpat

Blaze is only concerned with generation of HTML, so you will still need to use the Hexpat API for HTML processing. But I think this will be a big help for those places where you need Haskell generated HTML for Heist templates.

Numerical Sequence Puzzle

2010-11-21T13:49:00.002-05:00

What's the next number in this sequence, and how is it determined?

1, 3, 5, 9, 15, 31, 61, 125, 251, 503, 1015, 2035, 4081, 8177, 16367, 32747, 65511, ?

Years ago I spent some time playing around with integer sequence puzzles. I ended up constructing a few puzzles based on ideas I had never seen used before. Sometime between 1995 and 1998 I published four of them in my user profile on the Free Internet Chess Server. Over the years since then I've had a number of people contact me with attempted solutions. A couple dozen or so people were able to solve three of them, but the one shown above remained unsolved for years. Several people submitted solutions that matched as far out as I had revealed terms but diverged later, so I kept publishing more and more terms hoping someone would be able to solve it.

Finally in 2006, someone sent me a solution that matched my sequence as far out as I cared to check. I recently discovered that the puzzle generated more activity than I realized. From what I have been able to piece together, one of the guys on the chess server who attempted to solve it posted the problem to http://forum.fok.nl/topic/267468 in 2003. People kept posting to that thread for almost two years, but nobody got the correct answer. Some of the attempts were relayed to me by the original poster, but he never referred me to the forum. Then, in 2005, someone reposted the puzzle to another forum. A few weeks later, someone posted the solution that was sent to me in 2006.

However, the specification for that solution was much more complicated than my original one. So I decided to post this problem here. I omitted the link to the post with the matching answer to encourage you to try it on your own. But I'm looking for the simple solution I originally used, which to my knowledge has not been published anywhere.

EDIT @ 22:07 on 11/21: And we have a winner. The first comment was submitted by Anonymous and had the correct answer. I'm curious whether (s)he derived it from the one already posted or figured it out from scratch.

Log Analysis Commentary

2010-06-10T06:21:00.005-04:00

I've hade some requests to explain some of the less common functions used in my log analysis screencast. I think the most straightforward approach is to examine each of the lines in a literate Haskell style. This is going to be a long-winded description of exactly what's going on. If you understood everything in the screencast, this post will probably bore you. But if you found yourself wondering what the heck was going on, this post might help.

> :m + Data.List Data.Function
> contents <- readFile "user.log"
> let l = lines contents
> let t = map words l
> mapM print $ take 2 t

These four lines are pretty straightforward. ":m +" is GHCi syntax that is similar to an import. readFile :: FilePath -> IO String reads the contents of a file into a string. The lines function splits the string on newlines and creates a list of strings representing each line in the file. We map the words function over each of these lines to split the lines around whitespace. At this point t :: [[String]]. You can think of it as a table (hence the name 't') where each row is a line in the file and each column is a field. The "mapM print" displays the first two elements of t on separate lines.

> let noDay = map (\(d:ds) -> take 7 d : ds) t
> let months = groupBy ((==) `on` head) noDay

Now we get into the meat of the analysis. The noDay line uses a simple map and a lambda to strip off the last three characters of the first field in every line, turning the field into unique month identifier. "groupBy" is a handy function that groups a list into "partitions" where the elements in a partition are all equal for a user-specified definition of equality. In this case, we're grouping the rows in noDay and we want to use equality of the first field to define our groups. The 'on' function is a handy little tool defined in Data.Function that makes this easier.

on :: (b -> b -> c) -> (a -> b) -> a -> a -> c

On's first argument is a binary operator "b -> b -> c". It's second argument is a function that transforms a's into b's. It returns a new binary operator "a -> a -> c" that applies the transform function to the a's to get two b's that it can use with the original binary operator. In our example, the "a -> a -> c" is equivalent to "row -> row -> Bool" (straight out of the definition of groupBy). So the 'on' function helps us construct this row comparator by first transforming the row and then comparing those things. Our comparison function is (==), and our row transformation is "head", which gets us the month field.
Here's a simple example:

> let exampleList = [ (1,9), (1,7), (2,16), (2,6) ]
> groupBy ((==) `on` fst) exampleList

This groupBy call returns [ [(1,9),(1,7)], [(2,16),(2,6)] ]. It has grouped all the consecutive tuples with 1 as the first element into one list and all the 2's into a second list. These lists then must be grouped with a surrounding list. In the original example, we get a list of groups by months. The result can be conceptualized as list of bins representing each month where each of those bins is a list of all the log entries that happened in that month.

> let monthUniqs = map (nubBy ((==) `on` (!!2))) months

Our next line has the form "map ... months". This means that we're doing some operation on each of the "month bins" we just created. In this case our operation is "nubBy ((==) `on` (!!2))". It's very similar to the groupBy line. 'nubBy' removes duplicates from a list, where the supplied comparison function defines what things are duplicates.

> nubBy (==) [1,1,2,2,1] == [1,2]

We again call on the trusty 'on' function to make nubBy use the third field (the username) to determine equality. This removes all duplicate usernames from each of the month bins, so the number of items in each of the bins is the number of unique registered users that came to the site in that month.

> zip (map (head . head) monthUniqs) (map length monthUniqs)

Now we want to display the length of each of the bins. The lengths are more interesting when we know which months they go with, so we use the zip function to combine two lists into one list of tuples.

> let user = groupBy ((==) `on` (!!2)) $ sortBy (compare `on` (!!2)) t

By now these patterns should be looking familiar. Here we're grouping by the username field just like we grouped by the month field before. The only difference is that we have to sort the list by the username field first because groupBy only groups equivalent elements that are adjacent. The result of this is a list of bins representing each user.

> length users

The length of this list tells us the number of registered users that have logged in.

> let userDays = map (nubBy ((==) `on` head)) user

Now we're nubbing the user bins to remove duplicate days. (It's days because user was created from t instead of noDay.)

> let visitCounts = map length userDays

This tells us how many different days each user has visited the site.

None of what we have done here is particularly difficult. It wouldn't be hard to do the same thing with Ruby or Python. The point of the screencast is to show that it can also be done easily in Haskell, a statically typed, compiled language; and to demonstrate some useful functions in Haskell's standard library.

Heist 0.2 Released

2010-06-08T15:37:00.012-04:00

Yesterday I released version 0.2 of the Heist XML templating library. This release makes some significant API changes, so it may break existing applications. But if you're only using Heist for basic templating, then you probably won't have to change anything. However, http://snapframework.com uses Heist extensively; and it did not require any code changes to upgrade. Here is a summary of what changed in 0.2:

String substitution in attributes
Support for DOCTYPE in templates
New implementation for TemplateMonad
Windows support
Typeable instance
Documentation improvements
Bug fixes

The biggest new feature in 0.2 is attribute string substitution. Because Heist's templating mechanism uses XML tags, it didn't automatically work for string substitution inside tag attributes. You don't have to do very much web development before you find yourself wanting this. Now you can get substitution in attributes using the syntax "$(name)". The Heist Tutorial describes this in more detail.

Previously Heist did not allow DOCTYPE declarations inside its templates. This was caused by implementation details, but needed to be fixed. Now you can put DOCTYPEs in your templates. Heist removes the DOCTYPE and copies it into the rendered page. If it encounters more than one DOCTYPE while recursing through your templates, it will use the first one.

Thanks to help from Edward Kmett we have a complete rewrite of TemplateMonad internals in this release. Previously we were using RWST because Heist uses Reader and State functionality under the hood. The rewrite eliminates the unnecessary Writer overhead. In the process, we decided to make it more convenient to use TemplateMonad as a monad transformer. TemplateMonad now provides instances of the most common monad type classes, eliminating the need to use "lift" to access standard monad functionality in the inner monad. This will make it easier to use Heist with more complex monad stacks.

In addition to these improvements, our users also contributed Windows compatibility and a Typeable instance. The Typeable instance makes it possible to use Heist dynamically with the Hint runtime haskell interpreter. We love getting community contributions and hope to see more of them in the future.

For more information about Heist and the Snap Web Framework see http://snapframework.com.

Haskell Scripting: Log Analysis

2010-06-07T08:50:00.004-04:00

The other day I wanted to analyze some of my website log files to get a better idea of how many active users I have. I've been meaning to do this for quite some time, but have kept putting it off. I decided to see what I could accomplish by just doing some experimenting in GHCI. It was so easy and convenient that I decided to do a screencast demonstrating what I did and how easy it was. The conciseness of Haskell combined with the instant feedback of an interpreter make a very powerful combination. Here's the screencast on vimeo.

Standardizing Go

2009-11-11T11:59:00.017-05:00

The web is abuzz with the recent announcement of the Go Programming Language. I've put a decent bit of thought into similar issues over the years, so I thought I'd chime in on the discussion.

To start with, Go is targeting a niche which I think has been need of filling for a long time. The Go home page bills it as "a systems programming language", but I don't think that name completely reflects the niche's whole scope. My interest in this niche came from writing programs to play games like chess and other zero-sum board games. At the bleeding edge of chess programming, developers always want to milk the limits of optimization to boost their search speed. This inexorably leads to the desire to write critical code in assembly language, and has generally led to these programs being written in C or C++. You don't usually think of chess programs as "systems programs", so instead of using the name "systems" to describe this niche, I'll use the term "performance-oriented".

Performance-oriented languages are used in a large number of domains such as artificial intelligence (specifically game tree search as mentioned above), mainstream game programming (3D graphics), OS/infrastructure development, and anyone who has decided (prematurely or not) to that low-level optimization is important. So Go's niche is large and important. (As a side note, my personal preference has recently begun to shift towards languages like Haskell that give you more powerful abstractions in exchange for hiding the underlying von Neumann architecture, but I recognize that performance-oriented languages still have an important place in software development.)

The main problem with C and C++ as the canonical performance-oriented languages is that time and technological advancement have rendered them too onerous for programmers. There's much debate about precisely which characteristics are the problem, but whatever your particular favorite issue, it's hard to argue that writing good, efficient, portable C code is quite tedious. I haven't yet looked at the actual language specification, but so far it looks like Go's feature set nicely addresses the most prominent of these problems. And it's about time.

But there are some problems with the ecosystem surrounding C/C++ that contributed to the problems. First, there is the lack of a good set of standard C libraries. Good, standard libraries could have solved some of C's problems by providing de facto solutions. Languages like PHP and Java did an outstanding job of solving this issue. Go needs something similar. With the inclusion of higher-level concepts like maps as a part of the language, Go has reduced the damage that can be done by the lack of standard libraries, but this will still be an important requirement if Go is to succeed.

C's second major problem was the lack of a controlling body. This is related to the first problem because libraries that could have become good standards suffered from non-portability across different C compilers. The profusion of subtly incompatible C compilers made it very difficult to write portable C code. Here too Java provided a great solution. I think the fact that Sun was able to legally prevent Microsoft from creating their own bastardized Java implementation was crucial in allowing Java to maintain its portability. Microsoft went on to create something similar called .NET that did essentially the same thing as Java (for them). But it did not destroy Java's unity in the process. My conclusion from this is that names, and the ability for the controlling organization to legally enforce them, are important. So in some ways being closed is good.

But if you're going to have a controlling organization, it is also important that the community be able to trust them. I think Sun did a decent job in how they managed this with Java. They provided a good quality, reasonably open, reference implementation for free. But they also kept control of the brand name to ensure compatibility. Google seems like it would be a decent owning organization for Go, although I know plenty of people would probably disagree. If Google owns the trademark for Go, they should be able to open source their implementation while still enforcing standards on anyone wanting to release a Go compiler. I would feel safe enough to use the language for commercial code if I know that the implementation is open source and there is no chance of Google making the Go implementation proprietary in the future. I think ownership and enforcement of the Go trademark is orthogonal to this issue.

Now, it could be that trademark ownership and enforcement is no longer a critical issue, and that Go can do just fine without it. However, I don't think it will hurt anything to have a the legal backing of an enforceable trademark to aid in standardization.

In conclusion, the Go Programming Language looks like a great step in the right direction. The next time I'm writing a new performance-oriented application, I'll be very likely to use Go. I hope the people developing Go have given these less technical issues some thought and that we can finally have a better standard for modern performance-oriented programming.

Edit: The original post used the term "bare-metal" instead of "performance-oriented". This was a bad choice of words and caused a lot of confusion. For whatever reason, when I hear the term "systems software" I think of operating systems, filesystems, device drivers, etc. I don't tend to include things like 3D games, chess engines, or computational fluid dynamics simulations in the meaning of "systems software" because I perceive these to be applications that run on top of the systems software layer. So I tried to define the term "bare-metal" to refer to all of these. But alas, it was a horrible choice of terminology--it gave some people exactly the opposite picture from what I intended. So I changed "bare-metal" to "performance-oriented". Hopefully this makes more sense.

Edit 2: Original article include a Microsoft slam that wasn't relevant and detracted from my point, so I removed it.

Dynamic List Formlets in Haskell

2009-08-11T15:33:00.009-04:00

The Haskell Formlets library (described here) provides an elegant abstraction that takes the tedium out of HTML form generation, validation, and processing (not to mention make it less error prone). This abstraction allows you to develop HTML form UIs while still thinking in and working with haskell's type system and data structures. It also fits very naturally with Happstack's ideas about using in-memory state to leverage the pure type system.

One important aspect of form abstraction is the handling of lists. Dynamic lists in particular are a bit more of a challenge because they require Javascript to handle the dynamic creation/removal of form fields. Until recently, the Formlets library has had poor support for list formlets. At the recent Hac-Phi Haskell hackathon, Chris Eidhoff and I worked on filling this gap. We made great progress at the hackathon, and it only took a little more work after the hackathon to finish the functionality we set out to solve. I would like to provide some help to potential users via a description some of the issues and design decisions we encountered.

Design Issues

Default Values

One critical aspect of form handling is the ability to specify default values for form fields. I encountered this issue very soon after I started using Formlets. If you want to edit the state of stored objects through an HTML form, you will probably want to be able to create a form where the object's current values for all the fields are already filled in. Then the user just changes the appropriate fields and doesn't have to re-enter all the other data. The Form type by itself is inadequate for this purpose. We added a new type alias to server this purpose:

> type Formlet xml m a = Maybe a -> Form xml m a

In my experience, working with Formlet instead of Form will make things easier in the long run. There are certainly simple situations where Form is sufficient, but Formlet is an important abstraction to have around.

Error Handling

The second important issue with list formlets in particular is error handling. When a single field has an error, the HTML whole form usually needs to be regenerated with an appropriate error indication. This is especially important in the context of list formlets.

Type Signature

Before continuing, we need to understand the type signature of a list formlet. Ultimately a list formlet will have the type Form xml m [a]. But we don't want to construct these formlets manually. We would like to be able to specify the formlet for a single item and have a function that automatically constructs a formlet representing the list of items. In the old version of formlets, this function was called massInput. We might define massInput as follows:

> massInput :: Form xml m a -> Form xml m [a]

But this isn't quite right because, as described above, we need the ability to specify default values in a list form. Here's where our Formlet type synonym becomes nice:

> massInput :: Formlet xml m a -> Formlet xml m [a]

Implementation Possibilities

There are two common approaches to representing a list of items: arrays and linked lists. The same is true of lists of fields in HTML. We could do a linked list implementation by adding a hidden element to each list item and have the value of the hidden element somehow tell us how to determine the name of the field(s) for the next item in the list. A hidden item with an empty value would indicate the end of the list. This is the approach used by the old massInput implementation. Its hidden items contained the prefix to the names of all the fields for the next item.

The other possibility would be to just use a predictable numbering scheme for the field names of list items. Then, instead of traversing next pointers, we would just increment through the form values until we find one that doesn't appear in submitted data.

It wasn't until after I did a significant amount of work with the linked list approach that I realized it has a fatal flaw. When a list item doesn't validate properly, massInput isn't able to recover the value of the hidden "next pointer" for that item. This means that if a user enters a list of 10 items, but makes a mistake in the first item, then the resulting error form will only have one item in the list. An error in any item will require the user to re-enter all subsequent items in the list. If you are using lists of complex items, this can be a lot of work and frustration for the user.

New and Improved

The new version of massInput fixes these problems. It uses the array approach to avoid the problem of vanishing elements when a form has errors, and it allows you to specify a list of default values for the list. This massInput function is in the Text.Formlets package, and provides the core dynamic list functionality.

We also introduced a new package Text.Formlets.MassInput with some higher level convenience functionality. In that package, we include javascript code to drive the dynamic "Add Item" and "Remove Item" buttons. This comes with another massInput function which bundles the core massInput with the add/remove buttons. Many applications will require javascript that is customized to their HTML structure, but the supplied code should be suitable for basic out of the box use as well as provide an example from which to guide customization.

The last code has not been uploaded to Hackage yet, but it is available from the Github repository. If you have any questions, comments, or improvements please let us know.

Bit Manipulation Problem

2009-05-14T16:21:00.010-04:00

This post is a bit different from my usual content. It's not about Haskell or functional programming, and not strictly about software. But I think it's a nice little brain teaser that may be of interest. Some may view it as too much tedium (congruent to 3 or 4 mod 5 in Knuth's scoring system), but I found the multitude of beautiful patterns in this problem interesting enough that I didn't notice the tedium.

Consider a chessboard with squares numbered as follows (in octal):

8|  70 71 72 73 74 75 76 77
7|  60 61 62 63 64 65 66 67
6|  50 51 52 53 54 55 56 57
5|  40 41 42 43 44 45 46 47
4|  30 31 32 33 34 35 36 37
3|  20 21 22 23 24 25 26 27
2|  10 11 12 13 14 15 16 17
1|  00 01 02 03 04 05 06 07
     a  b  c  d  e  f  g  h

This is a natural 0-63 (decimal) numbering where the 3 high bits (first octal digit) of the position index indicate the row and the 3 low bits (second octal digit) indicate the column. This isn't the only way the chessboard can be enumerated. Consider the following numbering scheme (also in octal):

8|  64 04 14 24 26 16 06 66
7|  05 65 34 44 46 36 67 07
6|  15 35 74 54 56 76 37 17
5|  25 45 55 75 77 57 47 27
4|  21 41 51 71 73 53 43 23
3|  11 31 70 50 52 72 33 13
2|  01 61 30 40 42 32 63 03
1|  60 00 10 20 22 12 02 62
     a  b  c  d  e  f  g  h

You might want to take a moment to analyze the patterns in this numbering. They're very interesting.

The bottom line is that the location of a piece can be described using 6 bits and some known numbering system. Therefore, all possible locations of one piece are equivalent to all 6 bit numbers. All possible arrangements of two pieces can be enumerated with a 12 bit number, 6 bits for the location of each piece. (Note that this representation includes positions where two pieces are on the same square, but we won't worry about that for the purpose of this problem.) And of course this can be extended to more pieces very easily. But instead of just storing 6 bits of one piece and then 6 bits of the other, it's useful to put the 3 high bits of each piece together and the 3 low bits together.

To illustrate, let's assume that our piece list is an array {rook, king} and their positions are another array {052, 046} (octal. I'll use the C notation of starting with a leading zero to denote octal from now on.).

Our index for this position will be the 12 bit number 04562. To make it very clear, the ordering here is: piece 1 high bits, piece 0 high bits, piece 1 low bits, piece 0 low bits. The nice thing about having this index all in one number is that you can do operations on all the piece positions at the same time rather than looping through an array handling each piece location individually.

It is useful to be able to flip the board in different directions. When there are no pawns, there are 3 ways to flip the board that do not change the meaning of the position. You can flip around the horizontal, vertical, and diagonal axes. If you are using the first square numbering, you can flip a single piece position around the horizontal axis by calculating highBits XOR 7. You can flip around the vertical axis by calculating lowBits XOR 7. And you can flip around the diagonal axis by swapping the high bits and low bits. But that's for a single piece. For an n-piece endgame position index with the high and low bits together as described above, the following C code will do it.

const uint numBits = 3*numPieces;
const u64 lowBits = ((1ULL << numBits)-1);
const u64 highBits = lowBits << numBits;

// Flip around horizontal axis
flippedIndex = index ^ lowBits;

// Flip around vertical axis
flippedIndex = index ^ highBits;

// Flip around diagonal axis
flippedIndex = ((index&highBits) >> numBits) | ((index&lowBits) << numBits);

Again, this code works for the first square numbering. The puzzle is to write code that does these flips for the second square numbering. Now the easy way would be to create three tables of 64 values each that you can use to look up the flipped squares. But in order to use that, you'd have to loop through each piece, extract the piece's location from the index, lookup that square in the table, and store the flipped square into the correct bits of the new index. Looping through the pieces is slow. How can you do it without having to loop through the pieces?

Adding Authentication to the Blog App

2009-04-08T09:00:00.000-04:00

In the last post, we developed a very basic blog application using Happstack. Now that we have a simple application without an authentication mechanism, let's see how much effort it takes to add authentication using the Happstack-Auth module mentioned here. First let's make an outline of what needs to be done. We need the following pieces of functionality:

Pages for login/registration
Routines to handle the POSTed form data from the above
A page to log the user out
Blog posts should contain the name of the author
Only authenticated users should be able to create new posts.

The first thing we have to do is import the auth module.

> import Happstack.Auth

Let's start by looking at the first three bullets of functionaliy mentioned above. I'll implement the login/registration pages in pretty much the same way they were implemented in my old posts. A single login.html file will have a form for both registration and login. This suggests the following code block:

>  , dir "newuser" $ methodSP POST $ newUserHandler exists noMatch regGood
>  , dir "login" $ withSession (\_ -> redir "/") $
>      msum [methodSP GET $ (fileServe ["login.html"] ".")
>           ,methodSP POST $ loginHandler loginGood loginBad]
>  , dir "logout" $ logoutHandler $ redir "/"

These server parts get added to the list we already started in the impl function. The newuser line introduces newUserHandler from our auth library. It returns the first parameter if the user already exists or the username is invalid, the second parameter if the two passwords did not match, and the third parameter if the registration was good and the user was created. In this case, the user is also automatically logged in. newUserHandler requires three form fields with the names "username", "password", and "password2". It even takes care of sanitizing the username field to make sure this doesn't happen to you. If you need more fine-grained control over your user registration process, the auth library provides other functions to facilitate this. I won't describe them in detail here. Read the code. The login lines introduce two functions provided by the auth library. They are withSession and loginHandler. Here is the type signature for withSession:

withSession :: (MonadIO m)
            => (SessionData -> ServerPartT m a)
            -> ServerPartT m a
            -> ServerPartT m a

The first parameter is a function that takes a SessionData and returns a ServerPartT. withSession takes care of the details involved in getting the session data, so all you have to do is supply a function that uses it. The second parameter is a ServerPartT that gets returned if the user is not currently logged in. This allows you to specify custom guest functionality. It could be a "401 unauthorized" response, or something else entirely. If the user is already logged in, we simply skip the login page and redircect to root. If the user is not logged in, then we have two server parts to handle GET and POST. On a GET we just return the contents of login.html. On a POST, we need to handle the form data. loginHandler is provided to take care of all these details. Its first two arguments are ServerPartTs that will be returned on good login and bad login respectively. loginHandler requires that your form contain fields named "username" and "password". The logout line calls upon the logoutHandler function to take care of the details of logging out. All you have to do is pass it something to return afterwards. In this case we just redirect the user to the root page. Now we need to define the functions we just used.

> loginGood = redir "/new"
> loginBad = ok $ toResponse $ "Invalid login"
> exists = anyRequest $ ok $ toResponse $ "Username was invalid or already exists."
> noMatch = anyRequest $ ok $ toResponse $ "Passwords did not match"
> regGood = redir "/new"

If the user successfully logged in, we assume that they are logging in so they can create a new blog post and redirect them to "/new". Otherwise we return an invalid login page. We define a couple generic error message pages for the previously mentioned registration errors, and if their registration is good, we redirect to "/new" just like on a good login. Everything we've done so far has been new functionality. We might have been able to have the auth framework abstract it a little more and require us to write less code, but for the most part the functionality we have written is unique to the layout and design choices made by our site. Now we need to go back and modify our existing functionality to give it an awareness of users. First, we add an item to our Post data type to store the author of the post. We want to use the Username type defined by the auth library since that's how it will be available to us.

>   postAuthor :: Username,

Since we're changing the Post data constructor, we will have to make a corresponding change in addPostHandler. But addPostHandler doesn't know what username to use. This is an ideal place to call upon the withSession function that we've already seen. We just add one parameter to addPostHandler representing the current session. Here is the new function (only the first and third lines changed):

> addPostHandler ses = do
>   (Just title) <- getDataFn $ look "title"
>   (Just body) <- getDataFn $ look "body"
>   update $ AddPost (Post title (sesUsername ses) body)
>   redir "/"

We need to modify the part of impl that handles new pages by adding withSession and an action to take when the user is not logged in. If you're going to "/new" and you're not logged in, we'll just assume you want to log in and redirect you to "/login". This is complemented by the code we already wrote which redirects you to "/new" after login. Since our website is simple, this will provide a seamless flow when the user goes to "/new" without them needing to know about "/login".

> dir "new" $ withSession newPostHandlers (redir "/login")

This means that newPostHandlers has to accept the session data as a parameter and pass it to addPostHandler according to our above modifications.

> newPostHandlers ses = msum [methodSP GET $ fileServe ["new_post.html"] "."
>                            ,methodSP POST $ addPostHandler ses])

Finally, we have to tell Happstack that our application's state includes the state Component defined in another Happstack.Auth. All we have to do is add "AuthState :+: " to the BlogState dependencies.

>   type Dependencies BlogState = AuthState :+: End

And that's all there is to it. You still have to integrate your login pages with the rest of your site just like you normally would, but all the details of session management are nicely hidden away. You don't have to know about browser cookies or worry about generating session IDs. You don't have to worry about storing your user database or keeping track of open sessions. You don't have to understand how to build a secure password storage scheme. The library's password storage hasn't been vetted enough for me to call it secure, but it's already more secure than reddit's database once was. All this at the bargain price of 13 additional lines of code with simple modifications to 6 others. This auth library is a work in progress. It still needs a mechanism for cleaning up expired sessions, and could probably benefit from improved defense against session hijacking. I'm sure there are many other problems I haven't thought of. If you find this library useful, or have suggestions or any other comments, I'd love to hear them. The full source for this modified app is in github.

Basic Happstack Blog App

2009-04-07T11:00:00.010-04:00

Happstack is improving, and my old blog posts on HAppS are now out of date. So we're in need of a bare-bones app to demonstrate functionality. I also wanted a simple app without authentication capability to demonstrate how to integrate Happstack-Auth into a project. Blog apps seem to be one of the canonical beginner's examples in the web framework world, so I thought that would be a good choice to start with. As usual, this post is literate haskell and should compile as Main.lhs.

> {-# OPTIONS -fglasgow-exts #-}
> {-# LANGUAGE TemplateHaskell , FlexibleInstances,
>              FlexibleContexts, UndecidableInstances, OverlappingInstances,
>              MultiParamTypeClasses, GeneralizedNewtypeDeriving #-}
> 
> module Main where
> 
> import Control.Concurrent
> import Control.Monad
> import Control.Monad.Reader
> import Control.Monad.State (modify,put,get,gets,MonadState)
> import Data.Generics hiding ((:+:))
> import Happstack.Server
> import Happstack.State

First, we define a blog post. A post has a title and a body, both of type String. The deriving clause is required by the Happstack state mechanism. The Ord instance isn't actually required for this example, but it is required if you want to build an IxSet from this data type, so I'm in the habit of including it.

> data Post = Post {
>   postTitle :: String,
>   postBody :: String
> } deriving (Read,Show,Ord,Eq,Typeable,Data)

Our top level blog state will be a simple list of posts.

> data BlogState = BlogState {
>   postDB :: [Post]
> } deriving (Read,Show,Ord,Eq,Typeable,Data)

These are the standard Version and Serialize instances needed by Happstack's state mechanism. I won't go into detail about them here. Jeremy Shaw has a nice post describing them in much more detail.

> instance Version Post
> $(deriveSerialize ''Post)
> instance Version BlogState
> $(deriveSerialize ''BlogState)

Our state has to be an instance of component. We have no dependencies and our state's initial value is a simple empty list.

> instance Component BlogState where
>   type Dependencies BlogState = End
>   initialValue = BlogState []

Now we need some accessor functions. For now we'll keep it simple with a function to add a post, and one to get the list of all posts.

> addPost :: (MonadState BlogState m) => Post -> m ()
> addPost p = modify $ (\s -> BlogState $ p:(postDB s))
>
> getPosts :: (MonadReader BlogState m) => m [Post]
> getPosts = asks postDB

Now the required Template Haskell voodoo to build these methods for us.

   
> $(mkMethods ''BlogState ['addPost, 'getPosts])

Before we go further I want to add a little infrastructure code that will simplify things later. It's a simple function that redirects the client to the specified URL.

> redir url = seeOther url (toResponse "")

New we define the layout of our site. We have one URL at "http://site.com/new". A GET request to this url returns a static HTML file containing a new post form. The form POSTS the results to the same URL, so we have to define a function to handle this request. The last "methodSP GET" matches the root URL "http://site.com/" and will just display the list of posts.

> impl = msum
>   [ dir "new" newPostHandlers 
>   , methodSP GET viewPostsHandler
>   ]
>
> newPostHandlers = msum [methodSP GET $ fileServe ["new_post.html"] "."
>                        ,methodSP POST addPostHandler]

The msum in newPostHandlers is new as of Happstack 0.2. In prior versions, some functions required or returned data of type ServerPartT, and some used [ServerPartT]. Other functions required WebT data. In Happstack 0.2, everything was unified to work around a single ServerPartT. If you have an abstraction that needs several ServerPartTs, you usually want to collapse them using msum. Our new post handler gets POSTed values from the HTTP request, constructs a Post, passes that to AddPost, and redirects to the root.

> addPostHandler = do
>   (Just title) <- getDataFn $ look "title"
>   (Just body) <- getDataFn $ look "body"
>   update $ AddPost (Post title body)
>   redir "/"

The view posts handler queries the GetPosts action for the list of posts. If the list is empty, it returns a simple message, otherwise it returns the posts as a string. toResponse converts strings into responses with a content type of text/plain. Generating proper HTML pages is not hard, but is beyond the scope of this example.

> viewPostsHandler = do
>   posts <- query $ GetPosts
>   case posts of
>     [] -> ok $ toResponse "No posts yet"
>     otherwise -> ok $ toResponse $ unlines $ map show posts

The rest of the code is standard infrastructure for a Happstack application. The only thing we have to do is declare an entry point with our state Component and pass it to startSystemState. Then we pass our previously defined impl function to simpleHTTP and we're done. A clean, working Happstack application in 75 lines of code.

> entryPoint :: Proxy BlogState
> entryPoint = Proxy
> 
> main = do 
>   control <- startSystemState entryPoint
>   tid <- forkIO $ simpleHTTP nullConf impl
>   waitForTermination
>   putStrLn "Shutting down..."
>   killThread tid
>   shutdownSystem control
>   putStrLn "Shutdown complete"

The code for this app is available in the Happstack-Auth github repository in the demos/Blog-NoAuth directory. In the next post I will show how to add authentication to this app using the auth framework I mentioned in the last post.

70	71	72	73	74	75	76	77
60	61	62	63	64	65	66	67
50	51	52	53	54	55	56	57
40	41	42	43	44	45	46	47
30	31	32	33	34	35	36	37
20	21	22	23	24	25	26	27
10	11	12	13	14	15	16	17
00	01	02	03	04	05	06	07

70	71	72	73	74	75	76	77
60	61	62	63	64	65	66	67
50	51	52	53	54	55	56	57
40	41	42	43	44	45	46	47
30	31	32	33	34	35	36	37
20	21	22	23	24	25	26	27
10	11	12	13	14	15	16	17
00	01	02	03	04	05	06	07

70	71	72	73	74	75	76	77
60	61	62	63	64	65	66	67
50	51	52	53	54	55	56	57
40	41	42	43	44	45	46	47
30	31	32	33	34	35	36	37
20	21	22	23	24	25	26	27
10	11	12	13	14	15	16	17
00	01	02	03	04	05	06	07

70	71	72	73	74	75	76	77
60	61	62	63	64	65	66	67
50	51	52	53	54	55	56	57
40	41	42	43	44	45	46	47
30	31	32	33	34	35	36	37
20	21	22	23	24	25	26	27
10	11	12	13	14	15	16	17
00	01	02	03	04	05	06	07

70	71	72	73	74	75	76	77
60	61	62	63	64	65	66	67
50	51	52	53	54	55	56	57
40	41	42	43	44	45	46	47
30	31	32	33	34	35	36	37
20	21	22	23	24	25	26	27
10	11	12	13	14	15	16	17
00	01	02	03	04	05	06	07

70	71	72	73	74	75	76	77
60	61	62	63	64	65	66	67
50	51	52	53	54	55	56	57
40	41	42	43	44	45	46	47
30	31	32	33	34	35	36	37
20	21	22	23	24	25	26	27
10	11	12	13	14	15	16	17
00	01	02	03	04	05	06	07

70	71	72	73	74	75	76	77
60	61	62	63	64	65	66	67
50	51	52	53	54	55	56	57
40	41	42	43	44	45	46	47
30	31	32	33	34	35	36	37
20	21	22	23	24	25	26	27
10	11	12	13	14	15	16	17
00	01	02	03	04	05	06	07

70	71	72	73	74	75	76	77
60	61	62	63	64	65	66	67
50	51	52	53	54	55	56	57
40	41	42	43	44	45	46	47
30	31	32	33	34	35	36	37
20	21	22	23	24	25	26	27
10	11	12	13	14	15	16	17
00	01	02	03	04	05	06	07

64	04	14	24	26	16	06	66
05	65	34	44	46	36	67	07
15	35	74	54	56	76	37	17
25	45	55	75	77	57	47	27
21	41	51	71	73	53	43	23
11	31	70	50	52	72	33	13
01	61	30	40	42	32	63	03
60	00	10	20	22	12	02	62

64	04	14	24	26	16	06	66
05	65	34	44	46	36	67	07
15	35	74	54	56	76	37	17
25	45	55	75	77	57	47	27
21	41	51	71	73	53	43	23
11	31	70	50	52	72	33	13
01	61	30	40	42	32	63	03
60	00	10	20	22	12	02	62

70	71	72	73	74	75	76	77
60	61	62	63	64	65	66	67
50	51	52	53	54	55	56	57
40	41	42	43	44	45	46	47
30	31	32	33	34	35	36	37
20	21	22	23	24	25	26	27
10	11	12	13	14	15	16	17
00	01	02	03	04	05	06	07

70	71	72	73	74	75	76	77
60	61	62	63	64	65	66	67
50	51	52	53	54	55	56	57
40	41	42	43	44	45	46	47
30	31	32	33	34	35	36	37
20	21	22	23	24	25	26	27
10	11	12	13	14	15	16	17
00	01	02	03	04	05	06	07

70	71	72	73	74	75	76	77
60	61	62	63	64	65	66	67
50	51	52	53	54	55	56	57
40	41	42	43	44	45	46	47
30	31	32	33	34	35	36	37
20	21	22	23	24	25	26	27
10	11	12	13	14	15	16	17
00	01	02	03	04	05	06	07

70	71	72	73	74	75	76	77
60	61	62	63	64	65	66	67
50	51	52	53	54	55	56	57
40	41	42	43	44	45	46	47
30	31	32	33	34	35	36	37
20	21	22	23	24	25	26	27
10	11	12	13	14	15	16	17
00	01	02	03	04	05	06	07

70	71	72	73	74	75	76	77
60	61	62	63	64	65	66	67
50	51	52	53	54	55	56	57
40	41	42	43	44	45	46	47
30	31	32	33	34	35	36	37
20	21	22	23	24	25	26	27
10	11	12	13	14	15	16	17
00	01	02	03	04	05	06	07

70	71	72	73	74	75	76	77
60	61	62	63	64	65	66	67
50	51	52	53	54	55	56	57
40	41	42	43	44	45	46	47
30	31	32	33	34	35	36	37
20	21	22	23	24	25	26	27
10	11	12	13	14	15	16	17
00	01	02	03	04	05	06	07

70	71	72	73	74	75	76	77
60	61	62	63	64	65	66	67
50	51	52	53	54	55	56	57
40	41	42	43	44	45	46	47
30	31	32	33	34	35	36	37
20	21	22	23	24	25	26	27
10	11	12	13	14	15	16	17
00	01	02	03	04	05	06	07

70	71	72	73	74	75	76	77
60	61	62	63	64	65	66	67
50	51	52	53	54	55	56	57
40	41	42	43	44	45	46	47
30	31	32	33	34	35	36	37
20	21	22	23	24	25	26	27
10	11	12	13	14	15	16	17
00	01	02	03	04	05	06	07

64	04	14	24	26	16	06	66
05	65	34	44	46	36	67	07
15	35	74	54	56	76	37	17
25	45	55	75	77	57	47	27
21	41	51	71	73	53	43	23
11	31	70	50	52	72	33	13
01	61	30	40	42	32	63	03
60	00	10	20	22	12	02	62

64	04	14	24	26	16	06	66
05	65	34	44	46	36	67	07
15	35	74	54	56	76	37	17
25	45	55	75	77	57	47	27
21	41	51	71	73	53	43	23
11	31	70	50	52	72	33	13
01	61	30	40	42	32	63	03
60	00	10	20	22	12	02	62

70	71	72	73	74	75	76	77
60	61	62	63	64	65	66	67
50	51	52	53	54	55	56	57
40	41	42	43	44	45	46	47
30	31	32	33	34	35	36	37
20	21	22	23	24	25	26	27
10	11	12	13	14	15	16	17
00	01	02	03	04	05	06	07

70	71	72	73	74	75	76	77
60	61	62	63	64	65	66	67
50	51	52	53	54	55	56	57
40	41	42	43	44	45	46	47
30	31	32	33	34	35	36	37
20	21	22	23	24	25	26	27
10	11	12	13	14	15	16	17
00	01	02	03	04	05	06	07

70	71	72	73	74	75	76	77
60	61	62	63	64	65	66	67
50	51	52	53	54	55	56	57
40	41	42	43	44	45	46	47
30	31	32	33	34	35	36	37
20	21	22	23	24	25	26	27
10	11	12	13	14	15	16	17
00	01	02	03	04	05	06	07

70	71	72	73	74	75	76	77
60	61	62	63	64	65	66	67
50	51	52	53	54	55	56	57
40	41	42	43	44	45	46	47
30	31	32	33	34	35	36	37
20	21	22	23	24	25	26	27
10	11	12	13	14	15	16	17
00	01	02	03	04	05	06	07

70	71	72	73	74	75	76	77
60	61	62	63	64	65	66	67
50	51	52	53	54	55	56	57
40	41	42	43	44	45	46	47
30	31	32	33	34	35	36	37
20	21	22	23	24	25	26	27
10	11	12	13	14	15	16	17
00	01	02	03	04	05	06	07

70	71	72	73	74	75	76	77
60	61	62	63	64	65	66	67
50	51	52	53	54	55	56	57
40	41	42	43	44	45	46	47
30	31	32	33	34	35	36	37
20	21	22	23	24	25	26	27
10	11	12	13	14	15	16	17
00	01	02	03	04	05	06	07

70	71	72	73	74	75	76	77
60	61	62	63	64	65	66	67
50	51	52	53	54	55	56	57
40	41	42	43	44	45	46	47
30	31	32	33	34	35	36	37
20	21	22	23	24	25	26	27
10	11	12	13	14	15	16	17
00	01	02	03	04	05	06	07

70	71	72	73	74	75	76	77
60	61	62	63	64	65	66	67
50	51	52	53	54	55	56	57
40	41	42	43	44	45	46	47
30	31	32	33	34	35	36	37
20	21	22	23	24	25	26	27
10	11	12	13	14	15	16	17
00	01	02	03	04	05	06	07

64	04	14	24	26	16	06	66
05	65	34	44	46	36	67	07
15	35	74	54	56	76	37	17
25	45	55	75	77	57	47	27
21	41	51	71	73	53	43	23
11	31	70	50	52	72	33	13
01	61	30	40	42	32	63	03
60	00	10	20	22	12	02	62

64	04	14	24	26	16	06	66
05	65	34	44	46	36	67	07
15	35	74	54	56	76	37	17
25	45	55	75	77	57	47	27
21	41	51	71	73	53	43	23
11	31	70	50	52	72	33	13
01	61	30	40	42	32	63	03
60	00	10	20	22	12	02	62