The ICFP Programming Contest 2011

Introduction

Last weekend saw yet another iteration of the ICFP Programming Contest, an event the glorious team Funktion im Kopf der Mensch could not miss.

The task

The task this year was to build a program that would play a card game, Lambda The Gathering, to be run on the contest organizer’s machines. The game is played with two players each, taking turns. In each round, a player must play one out of several kinds of cards, for each of which there is an infinite supply. Each player owns 256 slots, each of which has some “vitality”, initially 10000. If a slot’s vitality drops to zero it is dead and cannot be used anymore (unless it is explicitly revived). The object of the game is to kill all the opponent’s slots.

Apart from its vitality, a slot also holds a value, which is where the real action happens. A value can be either a number or a function. The cards in the game also represent functions, and the number 0. When a card is played, it must be played to a specific slot, meaning that the card’s value and the slot’s value are combined. The combination can be either that the slot’s value is applied to the card (right) or the other way around (left). Initially, each slot holds the identity function, I.

As an example, let’s say we want to generate the number 4 in a slot. Initially it will hold I, so we play zero right, giving I(zero), which is reduced to 0. Now we play the function succ, which takes a number and returns that number plus one, left, giving succ(0), which reduces to 1. In each of the next two turns we play the card dbl left. dbl is a function that doubles a number, so we end up with 4.

To actually do something, like attacking your opponent’s slots, there are cards whose functions have side effects. One of them is attack, which you supply with three numbers (it’s a curried function). The first is the number of one of your slots, the second the number of one your opponent’s slots and the third is the “strength” of the attack. Once the function has all of its arguments it will subtract the third number from your slot’s vitality and then subtract nine tenths of that number from your opponent’s slot. There is another function, help, which you can use to top up your vitality, so if you first help and then attack with the right strengths you will have damaged your opponent without having lost any vitality yourself.

Also among the cards in the game are S, K and I, representing the homonymous functions of the SKI combinator calculus. These three simple functions, together with function application, are Turing complete, which means that it is possible to build programs in slots.

Strategy

Actual programs can potentially damage the opponent much quicker than would be possible by building each attack by playing the respective cards anew. (Note that I’m talking about the programs (functions) in the game’s slots now, not about the program that plays the card game).

There is a limit to how long a slot’s function is allowed to “execute”, however, which is 1000 function applications. If it has not finished until then, execution is stopped and the slot’s value is reset to I. Any side effects stay, however, so an endless attack loop would do damage, though only a limited amount.

There is a good reason for not using endless loops, however, namely that, since the slot’s value is reset, the function is “lost”, so it has to be copied to another slot first (which is possible with the get function, but somewhat costly, since the function’s slot number has to be built first) or, even worse, generated again.

A better strategy is to use a function that does some more or less fixed amount of damage and then returns itself, or some slightly different variant of itself. The actual result of the function will, after all, be the new value of the slot. So, suppose we could build a function like this:

1:  function make_killer (slot) {
2:    return function (dummy) {
3:      kill_opponent_slot (slot);
4:      return make_killer (slot + 1);
5:    }
6:  }

If we generate this function and give it the number 0, it will result in a function that, given a dummy argument, will kill the opponent’s slot 0 and return a function that when called with a dummy argument will kill the opponent’s slot 1 and return a function that when called with a dummy argument etc. In other words, once we have this function we can kill one enemy slot per turn. In comparison, just launching a single attack without building more complex functions requires more than 50 turns, and that’s not sufficient to kill an enemy’s slot. If you factor in the help calls to top up your own vitality so as not to die quicker than the enemy you’re looking at more than 200 rounds just to kill a single slot of the enemy (assuming it has the initial vitality of 10000).

Feasibility

Unfortunately, it’s not completely trivial to write a function like this in SKI calculus. In fact, compared to SKI, x86 machine code looks incredibly high level. Fortunately, there is help. As luck would have it, I wrote a Scheme subset to Unlambda compiler many years ago. Scheme is essentially Lambda calculus and Unlambda is essentially SKI. In other words I was already a bit familiar with both SKI as well as the compilation algorithm (which is quite simple).

Here is the function from above in very simple Scheme:

1:  ((lambda (x) (x x))
2:   (lambda (self)
3:     (lambda (slot)
4:       (lambda (dummy)
5:         (kill-opponent-slot slot)
6:         ((self self) (succ slot))))))

Since there are no function names in SKI or pure Lambda calculus we have to achieve self-reference using a trick, namely the function (lambda (x) (x x)), which applies its argument to itself, so if you pass it your function then that function gets itself as its (first) argument, in this case named self. Note that I am assuming that we have sequential execution available, to first kill the opponent’s slot and then return the function for the next slot. This is not natively available in Lambda calculus, which doesn’t even deal with side effects, but can be implemented like so:

1:  ((lambda (dummy)
2:     do-this-afterwards)
3:   do-this-first)

How easily can we generate an attack function like the one above in a slot? The first step is to translate Lambda to SKI calculus. The simple algorithm (given in the task description) produces ridiculously huge programs. The problem is that since SKI calculus doesn’t know named function arguments the arguments must be passed downwards “manually” from where they originated. The simple algorithm passes them down all the way to all the leaves of the syntax tree, where they might or might not be needed. By cutting off the passing down at subtrees which don’t need the argument a significant reduction is achieved, but program size is still an issue, and depends a lot on how deeply nested the original function is.

Now that we have the function in SKI form, can we trivially play cards to summon it to a slot? It turns out that this is only possible in simple cases because a player’s turn can only apply a card left or right, so nesting on both sides of an application is not trivially possible. For example, it’s easy to generate S(S(SK)), starting from I, by applying K right and the S left three times. S((SS)K) also works: S right, S left, K right and S left. However, (SS)(KK) is not doable that easily.

There is a trick, though: Assume we already have some arbitrarily complex x, and we want x(MN). If we apply K left, S left and then M and N right we end up with ((S(Kx))M)N which, thanks to the way the S and K combinators work, reduces to x(MN).

This trick still only works if M and N are single cards. It can be used recursively however, and, using yet another similar trick, arbitrarily nested right sides can be produced, but at a great increase in the number of cards that have to be played. Before we figured out those tricks we came across a simpler general solution, using the card get, which, when given a slot number, reduces to the value that’s in that slot. If we use get and zero as the cards M and N in the trick above, the function will reduce to xy, with y being whatever is in slot 0. The generation algorithm built using this trick has to use more than one slot, and it depends vitally on slot 0, but it is reasonably simple and the overhead is small.

It looks as if we have all the pieces of the puzzle together now and can finally generate a function that does some serious damage quickly, but there is another problem. Let’s say we want to generate a function which, when given a dummy argument does the side effect of inc zero (the details of what inc does are not important here). In Scheme, that is (lambda (d) (inc zero)). Translated to SKI calculus it is K(inc zero). To generate it in a slot (assuming it holds I) we apply zero right, then inc and K left. After having applied the inc the slot’s function is inc zero, though, which is immediately reduced, thereby doing the side effect and giving as a result the function I, so after applying K left we end up with K(I) and a side effect we only wanted after giving the dummy argument.

Clearly, we need a way to “guard” side effects against immediate execution. The easiest way we found to do this is to build an equivalent function, but in a different way. From a completely functional point of view, i.e. ignoring possible side effects, the functions

1:  K(inc zero)

and

1:  (S(K inc))(K zero)

are the same – they both take an argument that is ignored and reduce to inc zero, but in the latter form the inc zero can only be reduced once the dummy argument is given. Let’s call such a function a “side effect function” – it requires a dummy argument and only once that is present will it produce a side effect.

What if we want to combine two such side effect functions, resulting in a new side effect function that does one first, then the other? It seems tempting to just apply the second to the first, like this:

1:  (lambda (d)
2:    (second-se-fn (first-se-fn d)))

The error in this approach is that even though (first-se-fn d) can only be reduced once the argument d is present, it is still, in terms of the SKI calculus, a function, and therefore a value, so second-se-fn can be reduced, even without d. What we need instead is a function that takes an argument and then applies first one function to that argument and then a second one. As luck would have it, that function is S. So, to combine two side effect functions, yielding a new side effect function, we have

1:  ((S first-se-fn) second-se-fn)

More strategy

With all of that in place we can come back to our self-returning slot-increasing attack function. As it turns out, passing around that extra slot number argument is quite an overhead when everything is translated down to SKI calculus, but we had already thought of a simpler solution. Instead of having the slot number inside the function we can use indirection: We store the number of the slot to be attacked in some other slot and use the get function to retrieve it from within the attack function. The disadvantage of this approach is that we need to increment the slot number after each attach, costing us one extra turn, but on the other hand we can switch to another slot to attack reasonably quickly.

After some optimizations, some of them directly on the generated SKI code, we managed to get the number of turns required to load this function down to below 180. After that we just have to load zero into a slot and we can kill one enemy slot every other turn.

One small detail I omitted above is that when attacking a slot the number you give will actually be inverted, i.e. giving 0 will attack slot 255, and vice versa. That makes it easy to attack high slot numbers but more difficult to attack lower ones, because higher numbers take more time to generate. Nonetheless, our bot doesn’t actually start its attack from the highest slot, as would be easiest. It first figures out which opponent slot holds the most complex function (using the trivial metric of counting the leaves of the syntax trees) and attack that first, then increment until we hit slot 0, then we start again from the highest slot, hopefully finishing off the opponent.

We did not have much time left to refine our bot beyond that. There are very few measures we take to defend ourselves. If one of our few vital slots is killed while we are generating our attack function, for example, we just revive the slot and the start over with generating the function. A smarter bot would try to salvage the pieces left in the other slots. If the slot we take the vitality from to launch attacks is killed, we’re dead in the water – we had code to help it get back into working condition, but we failed at the last minute to integrate it.

Overall, I think we’re doing quite well. We launch our first attack within about 200 rounds and can finish off a bot that doesn’t defend itself within a bit more than 500 turns after that. Against the best teams, however, we’re helpless – they can kill all 256 of out slots stone dead in less than 190 rounds, starting from scratch. Kudos!

Contest organization

In the past I have taken contest organizers to task for screwing up in minor and major ways. This year, I am happy to say, there was almost nothing to find fault with. The task was clear, not artificially obscured, many-layered, interesting and enjoyable. There was a test submission server but teams didn’t depend on it and it worked quite well in any case.

So, from Team Funktion im Kopf der Mensch a huge Thank You to the organizers for this amazing job! May all future contests be organized this well.

Programming languages

Last year was the first year we used Clojure after using OCaml almost exclusively in the years before. This time we stepped back a bit and used OCaml for the actual bot, i.e. the program that will run on the organizer’s servers. The main reasons for this were that OCaml has a much smaller footprint and more predictable performance than Clojure and we wanted to make sure we didn’t hit against any limits, and that we felt somewhat safer writing an unsupervised program when protected by OCaml’s type system.

We still used Clojure for developing the attack functions, starting from Lambda calculus, going down to SKI and then generating a sequence of card application.

Our visualizer was written in C.

All of these languages did their respective jobs well. No complaints this time.

The Code

All the code we wrote for this year’s contest is available on GitHub. If you need any assistance with it, please email me.

The 2010 ICFP Programming Contest

Introduction

Last weekend several hundred programming teams all over the world participated in the 2010 ICFP Programming Contest. Among them, of course, the glorious team Funktion im Kopf der Mensch.

The task

This year’s task was multi-layered. There was a core problem, but to even get to the point where we could submit part of a solution to it, we had to first make our way through a couple of secondary tasks.

The core task

The primary task was to submit “cars” and “fuels” to the organizers’ submission server. “Cars” are data structures describing operations performed on vectors called “air”, parameterized by matrices, called “fuel”. The thing of importance here is that cars don’t necessarily work with any fuel. Points were awarded only for fuel. The less fuels submitted for a specific car by different teams, the more those few teams scored for their fuels. Between fuels submitted for the same car, the one that was “shortest” scored the most.

Encodings

Cars and fuels could not be submitted directly, however. Both had to be encoded as ternary strings, in an undisclosed format. What’s more, before we could submit a car we had to submit a fuel for an existing car first, and fuels had an additional encoding step added – fuel factories.

Fuel factories

To submit a ternary fuel string it had to be encoded as a “fuel factory” first. A fuel factory is a circuit of individual gates of identical function. Each gate has two inputs and two outputs, all of which have to be wired. The whole circuit has one input and one output. The gate function was not disclosed.

To make the task of figuring out how gates work possible, the submission server would accept circuits and give back the first 17 “trits” of the circuit’s output. By submitting an empty circuit, wiring the circuit input to the output directly, without any intervening gates, we learned the first 17 trits of the input. Next we let the server produce the output for all circuits containing one (wired) gate. Those four output strings were enough to determine the gate function by brute-forcing (trying all possible gate functions and seeing which ones fit). We assumed (correctly) that the gates have no state.

The key

Another roadblock on the way to submitting fuels was that the fuel circuit had to produce a string that contained not only the encoded fuel but a 17 trit prefix – the “key” – before it. In order to gain the rights to submit a car we first had to produce a circuit that output this prefix. We brute-forced this circuit as well, trying all combinations of gates until we found one that generated the key. The shortest ones have 6 gates.

Now that we could submit cars as well as fuels, we had two problems to work on in parallel: How are cars and fuels encoded, and how do we produce a circuit that generates a given, arbitrarily long, ternary string?

Cars

We knew from the task description that cars were encoded as a combination of lists, tuples, and natural numbers. Discovering the actual encoding was aided not only by the availability of one sample car and several cars already submitted by other teams, but also by the contest organizers’ server, which gave helpful error messages for incorrectly encoded cars.

Here are a few examples of numbers and lists of numbers. Note that the encoding assumes that the type of the encoded object is known, i.e., the encoding of a particular list and some number might be the same, but since it is known which one of the two types is expected, that is not a problem.

Thing	Encoding
0	0
1	10
2	11
3	12
4	22000
7	22010
13	2210000
()	0
(1)	110
(1 2)	2201011
(1 2 3)	2210101112

Generator circuits

We had several ideas for how to generate circuits to produce arbitrary ternary strings. The one we settled on was to reverse-chain together a sequence of adding sub-circuits. Consider this circuit:

One thing I haven’t mentioned about circuits yet is that transfer along forward wires is instantaneous, but is delayed by one step along backward wires. In the first step, all backward wires carry the value 0. What that means for this circuit is that in the first step, the one-adder gets an input of 0 and produces 1, which is the first step’s circuit output. Also, the two-adder produces a 2, but its delivery to the one-adder is delayed until the second step, at which point the one-adder produces a 0 (because 1+2 is 0 modulo 3). The output for the third step already depends on the circuit input from the first step. This circuit, then, will, no matter what the input, always produce the two trits 10 in its first two steps. It is easy to see how to extend this pattern to produce an arbitrary string, given only the three adders as building blocks.

Of course we didn’t have the three adders starting out, but it was not too hard to brute-force them, like we did for the key generator. In fact, we even went so far as to brute-force circuits that combined up to three of those adders, reverse-chained together, to make our circuits shorter. Our adders also had a delay built-in, which made the last sub-circuit superfluous.

Fuel encoding

At this point we could use the server’s submission system to figure out the ternary encoding of fuels, which turned out to be quite simple – a list of lists of lists of numbers. With that done, we could concentrate on the actual task of the contest, namely the production of cars and fuel.

Producing fuels

The only way to score points was to produce fuels, either for our own cars, or for the cars of others, which we could download. As it turned out, a sizable proportion of the cars other teams submitted worked with one out of a handful of very basic fuels, so we wrote scripts that automatically tried to submit those fuels for any new cars that showed up.

We had two strategies for solving cars that didn’t give in so easily, both of which were rather unsophisticated and give away our complete lack of any deeper understanding of the problem.

The first approach, which I worked on, was to employ a genetic algorithm. The second was to translate the constraints a car placed on a fuel into a series of inequalities and feed them into Mathematica, hoping it would spit out a solution. Both approaches yielded a number of matching fuels.

Producing cars

My approach to producing cars was the same as for producing fuel – a genetic algorithm. We have a running joke in our team: For every problem that comes up I first suggest a genetic algorithm, even if it’s completely unsuited. This year was the first time a genetic algorithm was actually a somewhat feasible approach. The problem with producing a car this way is the fitness function. We had the idea of generating a random pool of fuels and then scoring cars so that they came out on top if they matched exactly one of those fuels, hoping that would make finding a matching fuel harder. The cars produced with this approach were solved by about 20 to 25 other teams.

Another approach, which I was not involved with and therefore cannot describe in any detail, was more successful: Only 5 or 6 teams solved those cars, so we ended up not using the genetically-produced cars much – there was a limit of 72 cars per team.

The result

We finished the contest in 23rd place. Around 210 teams ended up with a non-zero score, with the total number of participating teams probably considerably higher.

Contest organization

This contest was organized quite well, more so in contrast to last year’s debacle. The biggest organizational issue was the submission server, which was down often, as a result of being hammered by hundreds of teams, most of which probably used scripts to automatically download cars and submit fuels. In fact, for the first few hours of the contest, the server was completely unresponsive.

The organizers tried to remedy the situation with a variety of approaches, at one point limiting the length of submitted cars to something ridiculously low – around 100 trits if memory serves me right.

Still, I do not think that we were significantly held back by these problems, at least not more so than all the other teams.

Suggestions to future organizers

I’ve been thinking a bit about what I liked and didn’t like about the ICFP contest tasks over the past 10 or so years. Here are a few wishes to the organizers of future contests:

Visual

I found that having a problem that can be visualized makes it much more enjoyable to work on. The best example for this is probably 2004′s contest, where we had to write software for ants’ brains that had to work together to search for and gather food and to defend against attackers. Watching those ants move about and improve with each version of the code was a joy.

Despite all the other issues, I did like this aspect about last year’s task, as well.

Programming

The task should really be a programming task at heart. The contest is, after all, a Programming contest. This year’s task, after you stripped all the intentional obscurity, was a mathematical problem. I’m not saying that mathematical problems aren’t nice or interesting. Neither am I saying that there shouldn’t be any math involved in the contest, but don’t make the core problem a mathematical one.

No obscurity

It seems that all the obscure bits that were put into this year’s task had the purpose of disguising the fact that, as already mentioned, the core task was not first and foremost a programming one. Please don’t do this in the future! Give us a task where all the non-essentials have been stripped, where the hard and interesting part is actually the task, not all the stuff you have to go through to finally get to it, discovering that it wasn’t all it was cracked up to be.

Last year’s task also had a bit of completely unmotivated obscurity – the format of their VM instructions was slightly different depending on whether the instruction address was odd or even. Why, oh why?

Self-containment

The more we have to rely on the contest organizers’ servers to go about our task, it seems, the more problems crop up. Last year was a total failure due to a bug in the submission system, and this year the server was down or at least very hard to reach for considerable stretches of time. Please give us something self-contained again! If you must have some interaction, make is as simple as possible. The submission system for the 2006 contest, for example, only required sending a short hash for each solved sub-problem, and it worked very well.

Don’t show off

You’re smart, we know, but that’s not what the contest is about. The contest is about how smart we are, so please refrain from making the task a monument to your intellect, as was the case in 2007.

Clojure

After our disillusionment with OCaml we had been looking for a language to replace it with as our first choice. To my surprise and joy we managed to settle on Clojure, which turned out to work quite well for us.

We stumbled across some rough edges, most of them having their roots in the integration of Clojure with the JVM, but they posed no significant obstacles, and will most likely be ironed out soon. The biggest problem with Clojure right now, and this is generally acknowledged in the community, is the lack of its error reporting, which can make finding bugs quite an ordeal sometimes, until one accommodates, at which point it is still at best bearable.

On the positive side most of us found working in Clojure fun and, after some learning period, quite productive. Having an interactive environment like Emacs/SLIME certainly accelerates not only the learning process, but development in general.

Clojure’s dynamic nature allowed us to do stuff we hardly would have considered with, say, OCaml. A few weeks before the contest I put together a simple job distribution service which allowed us to interactively distribute several workloads over a number of computing nodes with relative ease.

The dynamicism does come at a price, though: Like many Lisps, Clojure’s performance model is non-intuitive. It is not clear, at least without considerable experience, which operations, under which circumstances, are cheap and which are expensive, the gulf between which can be vast. As a result, we have resorted to implementing a few critical pieces of code in Java, which, to be fair, was quick, easy, and gave us efficient code.

I am looking forward to using Clojure more in the future.

The Code

All the code we wrote for this year’s contest is available on GitHub. If you need any assistance with it, please email me.

The ICFP Programming Contest 2009

Two weeks ago the annual ICFP Programming Contest took place and, once again, the glorious team Funktion im Kopf der Mensch participated.

This year’s task was to control a satellite orbiting the earth in two-dimensional space and make it meet a few increasingly difficult goals. We were given the specification of a very simple virtual machine and a few programs for that machine, which simulate the motions of the satellite to be controlled and of zero or more target satellites (and later also of the moon). Each run of such a program simulates a timestep of one second and outputs various data, such as the satellite’s positions, the remaining fuel and the score via variables called “output ports”. Commands can be given via “input ports”. Apart from the “scenario selection” command before the first timestep the only commands that can be given are thruster actuations, which are only limited by the available fuel, i.e. the whole remaining fuel can be spent in one timestep if necessary.

The first problem was a transfer from one circular orbit around the earth into another circular one and to stay in that orbit within a radius of one kilometer for 900 seconds. A very simple and efficient way of achieving such an orbit change is the Hohmann transfer, which requires only two thrusts. Here’s what it looks like in our visualization tool:

It wasn’t too hard to correctly perform this transfer, but already a few problems cropped up. Using the formulae for calculating the thrusts for a Hohmann transfer analytically we saw that the simulated orbits differed a tiny bit from what they would be in reality, which was enough to throw us off by more than one kilometer.

Another approach we followed was to find the correct thrust by simply trying out some value, simulating the flight path of the satellite and, depending on whether our flight was too short or too long, adjust the thrust, until we arrived at the correct distance within some arbitrary tolerance. We discovered that by doing this binary search we could find the thrust to bring us within one micrometer of the mark.

For the second problem we again had to transfer from a circular to another circular orbit, but this time we had to meet with another satellite there. In other words, not only did we have to get to the right place, but also at the right time.

A very simple approach to this problem is to just wait until the two satellites are lined up in such a way that when our satellite does the transfer, it arrives in the target orbit at exactly the location of the target satellite at that time. The downside of this solution is that the wait might be a very long one.

To avoid having to wait one can instead do a bi-elliptic transfer, which requires three thrusts and first transports the satellite into a higher (or lower) elliptical orbit which can be freely chosen within some limits. Because the height of that orbit determines how long it takes the satellite to come back, we can choose an orbit which exactly makes up for the time difference in the target orbit between the two satellites. Here’s what it looks like:

The third problem is like the second one, except that the orbits are not circular anymore, but elliptical, which requires some intricate navigation. We came up with this maneuver:

We start out in the elliptical orbit between points A and B and want to meet the target satellite at point E. The trick here is point C, which we can choose arbitrarily high or low, to adjust our timing, like in the second problem. By searching for the correct thrusts this works out pretty well, more or less, and looks like this:

When working on this problem we came upon an approach we should have though of much earlier: Just blindly follow the target satellite, orbital mechanics be damned. Doing this correctly is not entirely trivial, but much simpler than calculating thrusts, and in cases where the satellites are close, it works amazingly well:

It can also gives some very amusing results when they’re not close:

Here our satellite, which, left on its own, would have remained in a comparatively low orbit, makes a 90 degree turn to catch up with the satellite in the much higher orbit, and once it’s close to it, makes another 90 degree turn to follow it.

At this point we hit our biggest hold-up. The organizers of the competition had set up a system for submitting traces of the instructions given to the satellite, the scores of which were displayed on a publicly visible scoreboard, so the teams could compare their progress. The other function that this system served for the teams was to be able to verify their implementations of their virtual machines. When submitting this trace, and various variations of it, we always got the automatic reply that it “CRASHED”, so naturally we assumed that our virtual machine was at fault, and spent hours upon hours trying to identify the problem or to work around it. The issue wasn’t cleared up until after the contest was over, and I’ll discuss it below.

The fourth and last problem was to meet not one but 11 satellites in various orbits. Originally the specification mentioned 12 satellites, and the fact that the 12th satellite didn’t move relative to ours, combined with our earlier problems, convinced us even more that our virtual machine was faulty, so we spent even more time trying to find the issue. Alas, the error in the specification was corrected and we continued working on the rendezvous.

Two complications in this problem were that the satellite’s fuel was very limited and that there was the moon, in addition to the earth, exerting gravity. To get by with the satellite’s small fuel tank, there was a fueling station in low earth orbit which would refuel the satellite on contact, so we could meet one or two satellites and then return to refuel, etc.

We tried meeting a few satellites with the maneuver we had developed for problem three, but soon discovered that for the satellites in the outer orbits, we were very far off our mark. We had calculated the time-delay point not by doing the simulation, but with a simple formula, which worked perfectly for problem three, but in problem four our orbits were distorted by the moon, so that we could easily be off by a hundred seconds, which is quite a lot for a satellite that travels at several kilometers per second. In addition to that, the points at which we thrusted were no longer necessarily the apsides of the orbits, so the error accumulated. Even for the satellites in lower orbits our path would be distorted enough to spoil the rendezvous with the fueling station, so we used the simple follower algorithm to catch up with it. Here we ran into another issue: The fueling station was in a very low orbit, and the follower algorithm was not concerned with orbits at all, so when it had done its job it would sometimes leave us on a collision course with earth, which we had to correct.

At this point there were only a few hours left until the end of the contest, but we came up with two new, very simple approaches. The first was to do only simple transfers from circular to circular orbits (as circular as the moon’s gravity permits), to meet the target satellites in those orbits and to do time-delays by transferring into lower or higher elliptical orbits and then back into the circular orbits again. All these transfers would be exactly calculated by our binary search method, so there would be very little that could go wrong.

The second approach was to do our more complicated maneuver, but instead of single thrusts to go from orbit to orbit, suffering from the moon’s gravity, we would calculate the orbits as if there was no moon and then use our follower algorithm to chase a “virtual” satellite traveling along those orbits. All we had to do was to calculate them correctly and the follower algorithm would do the rest. The only question remaining was whether it wouldn’t waste too much fuel doing corrective thrusts. Our first tests suggested that it would work just fine. Unfortunately time ran out and we weren’t able to finish either algorithm.

I mentioned earlier that the problems we had with our virtual machine were eventually resolved, but only after the contest had ended. In fact, we had two almost completely independent virtual machine implementations – one an interpreter written in OCaml, the other a compiler written in Python, which generates C code. Both VMs gave exactly the same results on our traces, whereas submitting them always failed.

We did our best to find the bug. We examined our code multiple times, ran it on different machines to see if the floating point math might be the culprit, tried other team’s traces that were made public by them. When we found nothing we contacted the organizers, mailed them our traces, described our problems and asked them to give us more information about why our traces failed, but all we got back was the equivalent of “Sorry, we can’t help you.”. All the information we ever got from the submission system was “CRASHED”.

After the contest we were contacted Andy Gill, the contest’s chair. He sent us their virtual machine implementation, which, on my machines, accepted our traces just fine. I asked him to try our trace on his machine, where it also worked fine. In the end it transpired that their submission system had a bug and would silently truncate all traces to 64K.

Drawing a conclusion over the contest I must say that the task was interesting and well chosen, but that the contest was organized and executed very poorly. The task description made the impression of not having gone through a single round of testing, the submission system gave no feedback as to why a submission failed, making it very hard to find problems in the virtual machine (or, as would have been even more important, in the submission system itself) and trying to get non-trivial information from the organizers during the contest was essentially impossible. I do realize that organizing such a contest is a huge and difficult task, but out of the eight ICFP programming contests I’ve participated in, this was the worst-organized one.

Which means that next year it’s almost certainly going to be much better – hurray!

Why O’Caml is not my favorite programming language

A few hours ago the ICFP Programming Contest 2007 ended, and the team Funktion im Kopf der Mensch participated again, this year slightly demotivated by the fact that the organizer’s main goal seems to have been to show off how smart they are instead of letting the participant practice their creative skills.

As always we were using Objective Caml for most of our programming work. O’Caml has always had some annoying sides, but this year I ran into so many of them that I got seriously pissed off, and will now have to investigate other options.

For us, O’Caml’s main attraction are its type system, which, when used correctly, makes it surprisingly hard to write incorrect code, and its performance. O’Caml’s big weakness is its standard library. To be frank, it sucks, big time.

I’ll present the issues I ran into during the past three days, and I’ll compare the way O’Caml handles those things with Common Lisp, because in the areas I’ll discuss here, it is a good example of how to do it right. Note that I’m not saying that Common Lisp does everything else better. There is a reason why we’ve been using O’Caml, after all.

Let’s start with numbers. Say we need a function which adds the number 3 to a given number. Should be a trivial task, right? Indeed, in Lisp it is:

(defun add-3 (x)
  (+ x 3))


Let’s see if it works:

[2]> (add-3 0)
3
[3]> (add-3 4.5)
7.5
[4]> (add-3 3/2)
9/2
[6]> (add-3 (sqrt -4))
#C(3 2)


Great – we can give the function any kind of number, and it adds 3. How do we implement this in O’Caml? Well, first we’ll have to decide which kind of number we want to operate on, because, you see, you can’t mix different kinds of numbers. Ok, let’s concentrate on integers. There can’t be more than one kind of them, can there? Well, it turns out there are several. There’s “int”, “int32″, “int64″, “nativeint” and “big_int”. Here’s the code for all of them:

let add_3_int x =
  x + 3
let add_3_int32 x =
  Int32.add x (Int32.of_int 3)
let add_3_int64 x =
  Int64.add x (Int64.of_int 3)
let add_3_nativeint x =
  Nativeint.add x (Nativeint.of_int 3)
let add_3_big_int x =
  add_big_int x (big_int_of_int 3)


And those are just for the integer types! How ridiculous can it get?

Next issue: Arrays. Let’s say we need a function which returns an array with all the elements of the array it was given in reverse order, except for the last one. A triviality in Lisp:

(defun chop-rev (seq)
  (reverse (subseq seq 0 (1- (length seq)))))


Let’s see if it works:

[10]> (chop-rev #("abc" "123" "xyz"))
#("123" "abc")
[9]> (chop-rev "abcdef")
"edcba"


Notice that in Lisp string are arrays, too. As an added bonus, our function even works on lists:

[8]> (chop-rev '(1 2 3 4))
(3 2 1)


What can O’Caml do for us? Again, we first need to ask: Which kind of arrays are we talking about? There’s the built-in array type “array”. Then there’s strings, which O’Caml doesn’t treat as arrays, for no apparent reason. There’s another type called “Buffer”, which is really just a string that can grow, but is, of course, completely incompatible with “real” strings. There’s also something called “bigarray”, which is an array that can be big. In any other language such a data structure would be obsolete, because standard arrays wouldn’t have any size limits. Not so in O’Caml! You can enjoy all the comforts of the built in array type, but only if you don’t need to put in more than about 4 million elements (on 32 bit systems), unless you work with floats, in which case you’re limited to 2 million elements. Perhaps I should also mention that strings are limited to 16 million characters, but they forgot to implement big strings. What a joy!

We’re 7th!

The results from the ICFP Programming Contest 2006 are in, and our team Funktion im Kopf der Mensch placed 7th, out of 361. Not bad, I dare say! I, at least, am very happy with the result – yippee!

The ICFP Programming Contest 2006

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.