Thursday, May 21, 2009

New release: LHC 0.8

It's been about 5 months but, finally, a new release of LHC has been born and is on hackage - so you should get it now!

This new release has been a lot of hard work on behalf of David especially, and we've spent the past day or two working out a lot of installation issues on my MacBook etc.. But the result is looking really nice, even if premature. There are still some bugs to work out, but for the most part all our installation issues are fixed, and development can steam ahead on more interesting stuff.

Perhaps the biggest change in this release is that LHC is now a backend for GHC instead of its own codebase. Amongst other things, this pretty much means that LHC already has support for all of GHC's language extensions. Also, it shares the exact same command line options (and a few more,) so it's pretty similar to GHC on the hood.

The code base is very small, but it is simple: there is no garbage collection or exceptions, threading etc.. Everything is slow right now and the heap etc. are dummy. The result already works well though, and so we're releasing it now for your pleasure.

There are full installation instructions for LHC + libraries HERE.

Enjoy.

Monday, May 4, 2009

Constructor specialization and laziness.

Edward recently publicised some experiments with constructor specialization and the state monad. You can find the sources here.

What he did was basically to remove laziness and polymorphism from the state monad using a fancy new GHC feature called indexed type families. Benchmarking the different implementation was done by calculating the Fibonacci sequence and printing the 400,000th element.

There are quite a number of such adaptive data types. They range from lists to maps to monads but they all share two fundamental drawbacks: (1) All usage combinations must be explicitly enumerated, (2) laziness must be eliminated. Fortunately for LHC, using whole-program optimization solve both problems (by static analysis and unboxing at a higher granularity).

I believe it's important to realise that polymorphism and laziness are two sides of the same coin. Destroy one and you are likely to inadvertently destroy the other. 'Is this a bad thing?' you might ask. Well, the short answer is "yes!". Laziness, when used correctly, is incredibly powerful. Let's have another look at the State monad benchmark.

The following program implements the above mentioned benchmark. It is 10 times faster and uses 50 times less memory than the most efficient strict version.

{-# OPTIONS_GHC -O2 -XBangPatterns #-}
import Control.Monad
import Control.Monad.State

main = print . last . fst $ fib 400000

fib n = unS (fibN n) (0,1::Int)
fibN n = replicateM' n oneFib
oneFib = (get >>= \(m,n) -> put (n,m+n) >> return m)

replicateM' 0 fn = return []
replicateM' n fn
= do !e ← fn
r ← replicateM' (n−1 ∷ Int) fn
return (e:r)


So, in conclusion: Constructor specialization is an interesting technique but its full power can only be realised as an interprocedural optimization pass.