Rovers and Martians and Compilers, Oh My!

The ICFP Programming Contest

The seven computers in the basement of Hinds that spent this July “churning away”, as John Reppy, Professor in Computer Science, put it, were neither supercomputers dedicated to cutting edge scientific research nor workstations pushing the frontiers of theoretical computer science.

Instead, they ran simulations for the eleventh annual International Conference on Functional Programming (ICFP) programming contest, a light-hearted contest that pits functional programmers from around the world against one another in a battle for programing glory. The contest is organized in conjunction with the ACM SIGPLAN International Conference on Functional Programming,

The University of Chicago and Portland State University are co-hosting the contest this year; past hosts include MIT, Bell Laboratories, and Ultrecht University (The Netherlands).

The lucky evaluators at University of Chicago received over 470 submissions in total. “It was very successful; we had a record number of submissions,” continues Reppy. “People all over the world and writing in all sorts of different languages, so it was very successful in terms of participation.”

The ICFP programming contest challenges programers to code a program in response to a particularly challenging prompt. Programing teams only have three days to complete the task for the normal round, and merely twenty-four hours to compete in the lightning round, but beyond time limitations, the rules are loose. Team size is unlimited and the hackers code in any language of their choosing. They simply must write a program that works.

The awards are minimal, so competitors sacrifice their time and effort for little compensation besides the joy of coding. “It's held over the weekend, so people are just expected to get together with friends and spend a weekend doing something challenging and fun,” says Adam Shaw, a PhD student helping out with the project, who notes that nobody is paid to put together the mamoth effort to organize and host the competition.

In fact, the University of Chicago group spent months preparing for and running the contest. Writing contest task description started long before July, but the organizers weren’t in the clear once the contest started. Some contest tasks, like simulating the maps of Mars, were easy to automate, but others, like sorting through 470 submissions to find which worked, took quite a bit of time.

Simulating the contest and evaluating the programs lasted a month. To speed things along, PhD student Mike Rainey wrote a program using fractals rather than real sections of Mars to generate the virtual playing field, which worked well for most rounds of competition, where group members ended up drafting maps by hand in order to create difficult enough Mars maps. One such map was particularly “devilish,” reports Shaw; essentially a spiral of boulders and craters sprinkled with Martians.

All the hours of work are offset by–or maybe are what create–the contest’s strong sense of humor. Last year’s challenge came with a page-long backstory about an alien named Endo who crashed to Earth in an intelligent spaceship named Arrow. (In case you are wondering, Endo fell asleep at the wheel and was dropped on Earth by a garbage collecting alien race.) The actual challenge involved reverse-engineering Endo’s DNA. In 2005, University of Chicago organizers asked competitors to program robots to play both sides of cops and robbers in a completely automated Hyde Park. Another year’s task was to implement a virtual machine and then crack it using a computer language of their invention.

This year's competition task is to create software that controls a Martian rover and promises that, absent budget shortfalls, NASA will use the winning entry. Could a prize this good really be true?

“Absolutely not,” says Shaw. As a tip off that this promise is absolutely farcical, the contest task includes fourteen-fingured Martians who worship the Gods of Barsoom, deities that the project recomends against discussing. The project originally included a clearer disclaimer, something that seems to have be lost in later revisions, but, says Shaw, nobody dared ask about NASA's involvement in the contest.

Reppy came up with the idea from background research that he did in his Game Engineering class, a simulation in which a vehicle crosses a terrain, avoiding enemies, pits, and other obstacles. As he further developed the idea, the Martian setting became obvious, he says, and the pits and enemies turned into craters and Martians.

To win, entrants’ programs must safely navigate the rover to its home base from a starting position in as little time as possible. Three types of obstacles dot the Martian landscape: boulders, craters of varying size, and Martians, of which only two, craters and Martians, are deadly. For every trial, teams have five attempts to manouvre their rover from its starting position to its home base without being killed. They run under a time limit and can be slowed down by running out of bounds or running into a boulder. Ideally, the rovers run from the start to the home base without running out of bounds or running into obstacles.

The prize money, $1000 for first place winners and $500 for other categories, is not the focus of the awards. Instead, peer aclaim is bestowed upon the winners. The judges declare that the winning team's programming language is, “the programming tool of choice for discriminating hackers.” The organizers also hand out a prize to winners of the lightning round division–their languages is declared “very suitable for rapid prototyping”–and a judge's prize to one team, who are pronounced to be, “an extremely cool group of hackers”.

So was all the work worth it? Definitely, say the University of Chicago organizers.

“There were really smart people asking really sophisticated questions, so it was nice to be a part of that,” says Shaw, adding that, “It was really fun. If anybody ever has a chance to participate, they really, really should.”

The University of Chicago members involved in the ICFP 2008 effort are: Lars Bergstrom, Mike Rainey, Adam Shaw, Virgil Gheorghiu, and John Reppy.