2009 ICFP programming contest reflections

This year, unlike last year, I had the good fortune to be physically located in the same place as several other people interested in competing in the 2009 ICFP Programming Contest. We only ended up with three people—we could have used more—but it was quite a lot of fun.

The problem this year (controlling some satellites to accomplish certain goals) was a good one. I especially liked the approach of distributing binaries to be run on a virtual machine, and requiring execution traces as submissions—as opposed to last year’s contest, it removed all the ickiness with wrangling execution platforms and ensuring your code would run on the organizers’ servers. And the problem itself was nifty, easy to get started on, difficult to finish, and always left room for improvements. My only complaint is that I would have been more excited about something with a more discrete flavor, since this was the second contest in a row with a simulation of physical objects, vector math, trig, and so on—but that’s only a small complaint. We did respectably, solving 8 of the 16 scenarios (100x and 200x)—although of course hindsight is 20/20, and I think in particular we could have pretty easily solved all the 300x scenarios. We ended up spending too much time trying to work things out mathematically and not enough just doing simulation and search (although I’m definitely biased since I’m the one who wrote a physics simulator module… =).

We used Haskell, of course, which seemed to mostly work well. I wrote our VM, and although it wasn’t blazing fast, it was fast enough for what we ended up doing with it. The only truly annoying part was serializing and deserializing IEEE doubles, since Data.Binary doesn’t use IEEE format, and I didn’t know about the data-binary-ieee754 package until too late. I ended up doing some ugliness involving ByteStrings, foreign pointers, peek and poke… yuck!

The first scenario was easy enough, using the provided information about Hohmann transfer orbits and looking up some math on computing the required vectors (my teammate Julien did most of the heavy lifting mathematics-research-wise… I just typed what he told me to =). For the second scenario, we were able to figure out how to compute the correct angle at which to initiate a Hohmann transfer in order to meet up with the second satellite, but the problem at first was that it wasn’t accurate enough—but we finally got it to work doing some simple searches with a physics simulator (after I spent two hours figuring out that negating an angle is NOT the same thing as adding pi to it!). I’m confident we could have gotten the third scenario to work similarly, by first transferring to a circular orbit tangent to an apogee of the target orbit (doing some sort of calculation/simulation to work out the timing correctly), but oh well, we didn’t get there. This is also where having more people would have helped, both to be able to code more stuff in parallel and for some fresh ideas.

But, all in all, a most enjoyable experience, and I look forward to putting together a (hopefully larger) team again next summer!

Hac φ!

If you live anywhere near Philadelphia (or even if you don’t) and you’re interested in spending a weekend hacking on some Haskell code with a bunch of other awesome hackers, you should come to Hac φ! Check out the official announcement and the wiki for more details.

A strange dream

Last night I dreamed that my dad had this really dangerous pet lizard (it was poisonous and really strong—kind of like a Komodo dragon but somewhat smaller). My dad was gone and it started to get really agitated and angry—it was jumping up on people and running all over the place and we were afraid it was going to maim someone. I finally tricked it into going into the microwave and slammed the door shut, but it was trying to get out and it took all my strength to keep it inside. Since it was my dad’s pet we didn’t want to hurt it, but eventually there was no alternative—I couldn’t hold it in the microwave much longer and it was definitely going to hurt someone if it got out. You can probably guess what I did next.

That’s right, I multiplied it by 3000, and it turned into a bunch of random bits. Problem solved!

BumpTop private beta invite

I just got an email with an invite to download the BumpTop private beta, but right now there’s only a version for Windows. If you want it, let me know.

Monad.Reader #13 is out!

Issue 13 of the Monad.Reader, which includes a revised version of the Typeclassopedia, is out. This version of the Typeclassopedia contains many updates and revisions. There are also three other great articles in this issue of the Monad.Reader, I hope you’ll check it out!

First explorations in computer music

This week, I have taken some first steps in exploring computer music and live coding. Seeing as I am a

• classical and jazz pianist,
• amateur composer, and
• programming nerd,

it seems odd that it’s taken me so long to get around to combining these interests; but it’s one of those things that I’ve intended to explore for a long time and have just never gotten around to until now. Anyway, I have what I think are some really fantastic ideas about possibilities for real-time musical expression using computer-based tools—but at the moment there is a rather large gap between my ambitions and the reality of my knowledge and abilities. But that is obviously to be expected. Hopefully in a few years I’ll be posting videos of my awesome live performances; in the meantime I thought I’d write about my experiences getting things set up. More below the fold.

Typeclassopedia — a generic response

Thanks for all the fantastic feedback on the Typeclassopedia! Please keep it coming!

Such an outpouring of helpful comments and suggestions deserves a response, so I just wanted to write a quick note to say that I am reading every piece of feedback—whether here, on haskell-cafe, in #haskell, or on reddit—and fully intend to respond to each as appropriate. However, I probably won’t get around to it for a week or so, as at the moment I am focusing on digging myself out from all the other obligations that piled up while I was finishing the first draft. In the meantime, please keep sending me your suggestions!

However, there is one common suggestion I’ve received that I’d like to respond to now, which is that the Typeclassopedia should be put into wiki form. There are two main reasons I am submitting it for publication in the Monad.Reader, instead of creating it as a wiki in the first place:

1. There is something about the permanence and elegance of a finely typeset, well-edited publication that a collection of wiki pages cannot capture. This isn’t just an issue of presentation; it also affects the content: writing for the Monad.Reader means that my writing and presentation are better than if I had created pages on a wiki.
2. The Monad.Reader has a deadline; creating a wiki does not. Without a deadline, I probably never would have finished.

With that said, I think wikifying it after publication is a fantastic idea, and I hope that someone will take the initiative to do this. The Monad.Reader publishes all the source for each issue under a BSD license, so I don’t think this should be a problem.

The Typeclassopedia — request for feedback

I have just submitted a draft article for inclusion in the Monad.Reader entitled “The Typeclassopedia”. I will let the abstract speak for itself:

The standard Haskell libraries feature a number of type classes with algebraic or categorical underpinnings. Becoming a fluent Haskell hacker requires intimate familiarity with them all, yet acquiring this familiarity often involves combing through a mountain of tutorials, blog posts, mailing list archives, and IRC logs.

The goal of this article is to serve as a starting point for the student of Haskell wishing to gain a firm grasp of its standard type classes. The essentials of each type class are introduced, with examples, commentary, and extensive references for further reading.

I would love feedback from anyone, from the newest newb to the expertest expert, who would be kind enough to take a look. Particular types of feedback I would appreciate include:

• Are there parts that are confusing or could be worded more clearly?
• Are there parts that are stated incorrectly?
• Do you know of any additional references that could be included?

I am looking for more references for Foldable, Traversable, and Comonad in particular, so if you know of any good resources/examples/papers related to any of those, please let me know.

At 48 pages and 110 citations, the article is rather hefty, so I certainly don’t expect most people to read through all of it anytime soon—but even if you only take a look at a section or two about which you are particularly interested and/or knowledgeable, your feedback would be greatly appreciated! I hope that this can become a valuable reference for the Haskell community.

Edit, 16 March 2009: a revised and updated version of the Typeclassopedia has now been published in the Monad.Reader.

a chicken monad

Yesterday, Mark Dominus took a picture of me eating a monad:

It was a delicious Chicken monad.

data Chicken a = Chicken (Egg a)
data Egg a = Egg (Chicken a)

instance Monad Chicken where
  ...(exercise for the reader)

Diagrams 0.2 release

After meaning to get around to it for quite a while, I’ve finally released version 0.2 of the Haskell diagrams library. Here’s the release announcement. And here’s one of my favorite examples showing off the new path support:

Heighway dragon

I made this Heighway dragon curve in just a few minutes of hacking this afternoon, with the following code:

{- Heighway dragon.  See http://en.wikipedia.org/wiki/Dragon_curve. -}
module Main where

import Graphics.Rendering.Diagrams
import Control.Monad.State
import Data.Maybe

dragonStr :: Int -> String
dragonStr 0 = "FX"
dragonStr n = concatMap rules $ dragonStr (n-1)
  where rules 'X' = "X+YF+"
        rules 'Y' = "-FX-Y"
        rules c = [c]

strToPath :: String -> Path
strToPath s = pathFromVectors . catMaybes $ evalState c (0,-1)
  where c        = mapM exec s
        exec 'F' = Just `fmap` get
        exec '-' = modify left >> return Nothing
        exec '+' = modify right >> return Nothing
        exec _   = return Nothing
        left (x,y)  = (-y,x)
        right (x,y) = (y,-x)

dragon :: Int -> Diagram
dragon = lc red . curved 0.8 . strToPath . dragonStr

main = renderAs PNG "dragon.png" (Width 300) (dragon 12)

A special thank you to Dougal Stanton for adding text rendering support and other features, switching diagrams over to Russell O’Connor’s colour library, and generally helping out with this release.