New backend.

The new C backend has been pushed to the repository and it seems to work without a hitch. No particular effort has been directed at making it efficient (and none will since this backend is only a temporary measure). Initial testing shows it to be around 40-50 times faster than the interpreter.
Writing this backend was surprisingly easy; low-level Grin (LHC's intermediate language) can be directly pretty-printing as C code. By far the hardest part was giving up on LLVM and settling for C.

Future development will focus on grin-to-grin optimizations and a native code generator.

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.

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.

A new beginning.

The LHC project has finally resumed development after a few weeks of inactivity. Things have taken big steps in a new direction, however, and nearly everything except the name has changed.
We're no longer a fork of JHC. Maintaining a complete Haskell front-end was too much of a hassle, especially considering we're only interested in optimization on the GRIN level. For this reason, LHC has reinvented itself as an alternative backend to the Glorious Glasgow Haskell Compiler.

The lack of testability was a major problem in the previous version of LHC but hopefully we've learned from our mistakes. The new development efforts will be structured around a decremental reliance on a GRIN evaluator. In other words, we want to run the full testsuite between each and every significant code transformation. That no transformation should change the external behaviour of a GRIN program is a very simple invariant.

The current toolchain looks as following:

david@desktop:basic$ cat Args.hs
import System

main :: IO ()
main = do
    as <- getArgs
    mapM_ putStrLn as
david@desktop:basic$ ghc -fforce-recomp -O2 -fext-core -c Args.hs 
david@desktop:basic$ lhc compile Args.hcr > Args.lhc
david@desktop:basic$ ./Args.lhc One Two Three
One
Two
Three

The contents of 'Args.lhc' is unoptimized GRIN code. It is not by any means efficient or fast but it serves its purpose.

Development will now focus on creating GRIN transformations that reduces the need for the RTS (our GRIN evaluator serves as the RTS).

Hello world!

After weeks of development, lhc is finally able to interpret Hello World!

david@desktop:lhc$ cat HelloWorld.hs
module Main where
main = putStr "Hello world\n"
david@desktop:lhc$ ghc -O2 -fext-core HelloWorld.hs -c
david@desktop:lhc$ lhc build HelloWorld.hcr > HelloWorld.grin
Parsing core files...
Tracking core dependencies...
Translating to grin...
Removing dead code...
Printing grin...
david@desktop:lhc$ wc -l HelloWorld.grin
8054 HelloWorld.grin
david@desktop:lhc$ lhc eval HelloWorld.hcr 
Parsing core files...
Tracking core dependencies...
Translating to grin...
Removing dead code...
Hello world
Node (Aliased 251 "ghc-prim:GHC.Prim.(#,#)") (ConstructorNode 0) [Empty,HeapPointer 263]

Supported primitives include: indexCharOffAddr#, newPinnedByteArray#, *MutVar, *MVar.

Exceptions are currently ignored and the heap is never garbage collected. However, since I'm evaluating the GRIN (as opposed to translating it to LLVM or C), adding these features should be easy as cake.

Ease of implementation.

Developing a usable compiler for a high-level language such as Haskell isn't a trivial thing to do. Any effort to trade developer time against CPU time is likely to be a wise choice. In this post I will outline a few attempts to deal with the complexity of LHC in high-level ways. Hopefully the end result won't be too slow.


Case short-circuiting.
Since case expressions in GRIN do not force the evaluation of the scrutinized value, they are usually preceded by a call to 'eval'. Then, after the 'eval' calls have been inlined, case-of-case patterns like this are very common:

do val <- case x of
            []         -> unit []
            CCons x xs -> unit (CCons x xs)
            Ffunc a    -> func a
case val of
  []         -> jumpToNilCase
  CCons x xs -> jumpToConsCase x xs

This is obviously inefficient since the case for Nil and Cons will be scrutinized twice. In the GRIN paper, Boquist deals with this by implementing a case short-circuiting optimization after the GRIN code has been translated to machine code. However, dealing with optimizations on the machine code level is quite a tricky thing to do and I'd much rather implement this optimization in GRIN. By making aggressive use of small functions we can do exactly that:

do case x of
   []         -> jumpToNilCase
   CCons x xs -> jumpToConsCase x xs
   Ffunc a    -> do val <- func a; checkCase val

checkCase val =
  case val of
    []         -> jumpToNilCase
    CCons x xs -> jumpToConsCase x xs

Register allocation and tail calls.
Using a fixed calling convention is not necessary for whole-program compilers like LHC. Instead, we choose to create a new calling method for each procedure (this is easier than it sounds).
This has the obvious consequence of requiring the convention for return values to be identical for procedures that invoke each other with tail-calls. This was deemed an unacceptable restriction in the GRIN paper, and all tail-calls were subsequently removed before register allocation took place. Afterwards, another optimization step reintroduced tail-calls where possible.
I believe this is too much trouble for too little gain. The possible performance hit is out-weighed by the ease of implementation and the guarantee of tail-calls.


Simple node layout.
An unevaluated value is represented simply by a function name (or tag) and a fixed number of arguments. This value is then overwritten once it has been evaluated. However, the new value may be bigger than what was allocated to represent the unevaluated function.
One way to deal with this is to have two different node layouts: a fixed size node for small values, and a variable size node for big values. This is the approach taken in the GRIN paper and it understandably adds quite a bit of complexity.
Another method is to use indirections. This trades smaller average node size and ease of implementation against more heap allocations.

Grin a little.

It has come to my attention that we are not using GRIN to it fullest. More specifically, it seems that the 'eval' and 'update' operations are handled by the RTS. This has unfortunate consequences for both the optimizer and the backend code.
Without an explicit control-flow graph (given by inlining eval/apply), many of our more important transformations cannot be performed. Even worse than the lost optimization opportunities is the increased complexity of the RTS. Dealing with issues of correctness is an annoying distraction from the more enjoyable endeavour of applying optimizations.

Moving away from the magical implementation of 'update' means we have to starting thinking about our memory model. The GRIN paper suggests using a fixed node size with a tail pointer for additional space if necessary. With this scheme we can update common-case nodes without allocating more heap space. However, since we're most likely to encounter complications with respect to concurrency and certain forms of garbage collection, I think a simpler approach is more apt.
Replacing nodes with indirections is very easy to implement, it doesn't clash with any optimizations (the original GRIN approach interfere with fetch movement), and it opens the door for advanced features such as concurrency.

So this is what I'll be working on in the near future. All magic has to be purged from the kingdom so logic and reason can reign supreme.