The ICFP Programming Contest is an annual international programming contest, hosted each year by a different programming language research group. It works like this: On a well-known date, the hosts release a problem, usually in the form of a specification, on the Internet. The participants (working alone or in groups) then have exactly three days to solve the problem and to submit their solutions. The solutions are then compared by the hosts (usually mechanically and very objectively) and at some point the results are announced.
The 2006 contest came to an end today and, as in the past five years, I’ve participated as a member of the glorious team “Funktion im Kopf der Mensch”. Last year we were not very motivated by the problem, so we kind of gave up. The four years before, though, we always finished in the top 10 percent.
This year’s problem was not directly specified by the task description. Rather, a virtual machine was specified, and a program to be run on that machine provided. The machine is very simple, so it took us only about an hour to get it running. The result of running the program (called the “codex”) on the machine is another, bigger program, obviously uncompressed by the codex.
The second program is a very simple, UNIX-like “operating system” (or rather an imitation of an operating system), called “UMIX”. The first thing you do is log in as “guest” and see what’s around. There are several home directories, but you don’t have the passwords for those users. However, the guest account contains a BASIC interpreter and part of a program for hacking passwords (similar to the well-known “crack”). Finishing and running that program gives you the passwords for a few users. The stuff in those user’s home directories gives you further clues, so sooner or later you have all the passwords.
The real problems, though, are specified in the user’s home directories. Most of them are in the form of a programming language, for which there is an interpreter, and specifications for one or more programs to implement in that language. For each subproblem you solve, the machine spits out a “publication”, which is a string that gives you points if you submit it on the contest website (though it’s too late for that now, obviously). Usually, the shorter your solution, the more points you get.
The first problem I worked on was the “O’Cult” programming language. O’Cult is a term rewriting system, but instead of having sane rules for how terms are rewritten, O’Cult has one particularly nasty twist: If the rule to be applied can be applied an equal number of times in the main term’s subterms, it is not applied at all, which makes it very easy to reach a deadlock-state, where, although in theory further rewriting could happen, it is not done. My solution was to introduce two new terms, “Down” and “Up”, and guarantee that the whole term always contains exactly one Down or Up. The rules can then be written so as to always include a Down or Up in the left-hand-side, thereby ensuring that no rule’s left-hand-side matches more than once. This problem was pretty easy once I figured out what needed to be done, which wasn’t too difficult either. Here are my O’Cult programs for multiplying two numbers and bringing an “XML”-Term into normal form.
My “big” problem was the “2D” language. It’s basically an ASCII-art language with very basic operations. Here’s how my programs for multiplying two number and reversing a list look like in 2D. I drew those by hand in an editor.
The third 2D-subproblem was implementing a one-dimensional raytracer. Drawing it myself seemed out of the question for me, so I implemented (in Common Lisp) a compiler for a higher-level (functional) language which emits 2D code. My mistake here was not sorting out the theory before I started, because I underestimated the difficulty of the compiler’s task. As a result I had to spend about twice the amount of time that I saved in the implementation of the language with writing the raytracer in a way that the compiler could compile without producing incorrect code. Nevertheless, I got it working, albeit with a bit of cheating. The raytracer is supposed to calculate a fix-point, i.e., apply a step repeatedly until the result doesn’t change anymore. I was much too lazy to implement that as well, so I just figured out how often I would have to apply my raytracer step to pass the verification program. The answer is 9. Here, then, is my 2D raytracer, automatically generated and then manually optimized!
As always, my teammates were at least as successful as I was, so we were at fifth place (out of 346) 8 hours before the end of the contest, when the hosts turned off the online score-keeping to make the last hours of the competition even more thrilling.
Overall, this was quite an exciting contest, although I have to say that I really missed the teamwork that usually comes with it. When you have four people and six problems to solve, the teamwork chiefly consists of figuring out who wants to give which problem a try. My favorite ICFP contest is still the 2004 one. Nothing’s more fun than watching your little virtual ants search for food on a hexagonal grid! ;-)
If you want to try out UMIX yourself or even give a few of the problems a shot, look no further! Download this package, which contains our UM interpreter, the UMIX code and the passwords to all the users.
Mostly Software 