Haskell

Last week, I competed in this years Flemish Programming Contest (VPW for short in Flemish/Dutch). After attending the first VPW edition in Leuven in 2009 as an impartial observer and co-organizing VPW-2010 in Ghent, I wanted to experience the contest from the perspective of the competitors.

First, a brief description of the contest: each team of max. 3 members is given 5 assignments of varying difficulty, and needs to solve as many as they can in just 3 hours. Naturally, the teams that solves the most assignments wins. The time needed since the start of the contest per solved problem is summed up to rank teams that correctly solved an equal number of problems, a punishment of 20 minutes is added for each incorrect submission made and a bonus of 60 minutes deduction is granted to the teams that are able to solve one particular problem sufficiently efficient. Important side-notes are that each team is only allowed to use one single laptop/keyboard/mouse, that teams are not allowed to access the internet during the contest and that solutions to problems are tested on non-disclosed input sets.

To make things more interesting (and maybe also harder), I picked Haskell as the sole language my team would use to implement my solutions. After finding two like-minded team mates in the GhentFPG community, we chose "Avoid Success At All Costs" (the Haskell motto) as team name and started prepping for the contest.

By second hand experience, I knew that having a set of functions handy to process input and write out answers in a structured way, implement some standard programming paradigms (backtracking, binary search, etc.) and handle with 'special' data structures like matrices and such is a big plus. Since only the Haskell Platform would be available on the contest servers, we put together a template which contains a whole bunch of functions that might come in useful during the contest. We also held a couple of training sessions in which we mimiced the contest setting a closely a possible, to figure out what tactic to use, decide who would sit behind the single available laptop (that turned out to be me in the end) and who would draft the algorithms for the hardest problems. A last minute dropout of one of the team members caused some minor headaches, but we were able to find a very worthy replacement in the end, i.e. a guy who co-organized VPW-2009.

I was fairly confident that we would perform well, given that our team was fairly well prepared and that two of us were closely involved with the design of assignments and/or organization during previous contests. However, it turned out I grosly underestimated the impact of the contest setting. Working together with three people you're not very familiar with, on a single laptop andunder the pressure of time and competition was harder than I anticipated.

We finished 6th out of 24 teams in our category, by solving two of the five assignments correctly in the 3-hour time span that was given us. We felt we were pretty close to also solving a third one, but didn't manage to weed out the bugs before the end of the contest. After seeing the final ranking (see screenshot), we realized that we were really close to actually winning. If we had managed to solve the third assignment in time, we might have taken 1st place because we had very little punishment time compared to the only team that had three solved assignments. The morning after the contest I finished the assignment we were working on in just 10 minutes on the train ride to work, which makes things even more painful.

Nevertheless, we had fun. The only way we could have been better prepared for such a contest was gaining experience through competing, so we had no regrets. Using another language wouldn't have changed things much, because the emphasis was on the algorithms to solve the assignments and less on the code you were write. Haskell is a very expressive language which is a significant advantage under the pressure of time, and the type system weeds out stupid bugs early, which is again a win in terms of time. Having only one laptop available for 3 people is a huge bottleneck, but something you can learn to deal with by working out assignments thoroughly on paper (something you usually don't do if you have a computer handy).

I haven't decided yet what I'll do next year. Maybe I'll compete again, and if I do I'll again only use Haskell. Another option is to rejoin the team of jury members that design and select the assignments (which is more work but easier than actually competing in my opinion), at the informal request of some jury members. Both sides are interesting, so I'll refrain from making a decision on this for a while longer and enjoy the good feeling I retain from competing in VPW-2011.

(Before you ask: yes, I'm growing a beard, and yes, I'm using the lack of a Belgian government 250+ days after the elections as a lousy excuse.)

The last couple of months, I've been trying to get back to an old love of mine: Haskell. I haven't really used it for years until recently, but I'm planning to change that in the near future. I'll briefly outline my world-shocking (well, almost) plans here. But first, a bit of history...

Back in 2005, I used Haskell for my Masters thesis entitled "Modeling and implementing a ray tracer using functional languages", which resulted in HRay. Besides a couple of minor hiccups, I haven't really done anything serious with Haskell since. And it's not that I didn't want to, I just didn't find the time nor opportunities for it during my PhD. The tools I used for my research usually needed to chew through a large amount of data quickly and I decided to resort to C for that, because I didn't have enough experience with Haskell to produce tools that are competitive performance-wise with ones written in C.

During my PhD I promised myself I would get back to Haskell once I finished, and so I did.

I took my first steps back to Haskell during the Google AI Challenge, by putting together a bot in Haskell (code here) that played the contest version of Galcon against another bot. I relied on jaspervdj's Haskell starter package for the bare metal stuff. The bot ended at 497th place in the contest (6th Belgian, 6th Haskeller), a nice result with just over 4600 bots competing.

During BelHac, the first Belgian Haskell hackathon, I had some discussions about starting an effort for a new Haskell benchmark suite, i.e. one worthy of that name, and I also made some minor patches to HRay, which I had ignored for too long. I also met a couple of infamous Haskell hackers, including Don Stewart a.k.a. dons and Duncan Coutts , who helped me with some GUI-related stuff for HRay back in 2005. And last but not least, I won a copy of Real World Haskell (RWH), because I submitted stuff to Hackage during the hackathon and won the lottery draw. That earned me the right to be on a picture together with dons, see below (I'm on the left, dons is right next to me \o/). He even signed my copy of RWH, how cool is that!

Since BelHac, my hands have been itching to use Haskell for all sorts of things. My sysadmin job doesn't really allow using Haskell at work, I mostly use Python there, and finding time for side-projects isn't easy since my wife and 8-month old son are also competing for attention (and frankly, they are winning hands down over anything else). Nevertheless, I do have plans with Haskell in the near future.

First of all, I will be competing in the Flemish Programming Contest next month, and would like to do so using only Haskell. I found two team mates in the GhentFPG community, and we've been preparing for the contest for a couple of weeks now. We're hoping to blow the competition away by exploiting some of the strengths of Haskell, i.e. fast, obvious-bug-free programming, and chose the Haskell motto "Avoid Success At All Costs" as team name.

Something I would like to look into is using genetic programming to evolve Haskell programs. Recently, a Haskell library for genetic programming was announced on the Haskell mailing lists: genprog. I played with it for a while, and found the concept of being able to evolve expressions that evaluate to a specified value as closely as possible very interesting. There are several problems that come forward when trying to evolve actual Haskell programs, and although I have no idea what I'm getting myself into, I'd love to dive in and see what I can come up with. One idea I have that might turn out useful is to use Hoogle somehow to figure out how two existing Haskell programs can be recombined to form two others (the crossover operation in genetic algorithms).

Another Haskell-related project that I find interesting is looking into the low-level behavior of Haskell programs, and compare it to that of programs written in procedural languages. My attention was drawn to this after reading a tweet by dons, which pointed to excellent slides by David Peixotto on exactly this topic. David has compared the dynamic instruction mix of Haskell programs with that of programs written in C/C++, and found them to be remarkably different. Using MICA, a tool I implemented during my PhD that allows to collect so-called microarchitecture-independent workload characteristics, it would be interesting to compare not only the instruction mix, but also other aspects of low-level program behavior, e.g. the spatial and temporal locality of memory accesses, or the amount of instruction-level parallelism (ILP). I believe that kind of research could result in very interesting insights on how Haskell programs are different from programs in other languages, and might contribute to improving code generation for Haskell.