Thursday night

I went looking for the contest start date and time, and bumped into the problem statement. Didn't get a iota about it (that's soo silly! why do you have functions that return functions that return functions?!), and went to bed after deciding to skip the contest this year.

Friday

woakas writes me about the contest in the morning. Went to read the problem statement again, and got hooked. I searched for some tutorials, and kept reading the statement at night.

Saturday

woakas and I met in my house in the morning, talked about the problem, and agreed on a task list: 1) get a simple simulator for every player's slots, 2) arrange the program to use stdin and stdout as required in the match, and 3) get a Bot that plays a very simple strategy: repeatedly kill the slot 0 of the opponent using the dec card. We would worry about "programming" with S and K later.

That was done by the afternoon. It's worth mentioning that we did pair programming to write the simulator/VM, and it worked really really well. We sent the bot to play and took a break. Ah, right, the team name. Jeu. (woakas hit the keyboard, and that was it.)

At night, we found that, when the program crashes, the opponent wins. We noticed that our program wasn't validating types properly (e.g., using a constant as a function). We corrected that and added that same instruction as a first attack. It won us at least one match.

The first 5 submissions (all of them implementing the same simple strategy) kept crashing in the tournaments. The cause was a stupid bug in one of the cards; we found it by throwing random (but syntactically valid) strings to the bot. After fixing it, we called it a day and stopped working.

Sunday

We could not meet that day; we spent the day trying to learn how to program using lambda calculus, and combinatory logic.

update 2011/06/21: I forgot to mention that woakas wrote a program to search for a loop using a brute force approach, which did yield something useful: the command sequence

('2', '0', 'get')
('1', 'S', '0')
('2', '0', 'dbl')
('2', '0', 'zero')

Which causes yet another infinite loop. It would prove useful.

I finally understood that last part of the problem statement (the one about translating lambda terms to CL expressions) and understood (maybe) why they wrote that there.

I re-read a tutorial I found on Friday, and finally understood it. It proved insightful (although not useful for the contest). The author explains how to:

  • Build numerals (Church numbers).
  • Build the succ function.
  • Build addition.
  • Build the pred(n) function, the predecessor of a number.
  • Define TRUE and FALSE, and all the logic operators.
  • Define tests (compare a number to zero, return TRUE or FALSE)
  • Define loops, using the Y combinator, and getting the loop to stop using a test. I don't fully understand this part yet.

With that, and (sort of) knowing how to translate lambda calculus to CL (with the hints provided at wikipedia), I tried to do that with the succ function.

T[\w.\y.\x.(y((wx)y))]
T[\w.T[\y.\x.(y((wx)y))]]
T[\w.T[\y.T[\x.(y((wx)y))]]]
T[\w.T[\y.(S T[\x.y] T[\x.((wx)y)])]]
T[\w.T[\y.(S (K T[y]) T[\x.((wx)y)])]]
T[\w.T[\y.(S (K T[y]) (S T[\x.(wx)] T[\x.y]))]]
T[\w.T[\y.(S (K T[y]) (S (S T[\x.w] T[\x.x]) T[\x.y]))]]
T[\w.T[\y.(S (K y) (S (S T[\x.w] T[\x.x]) T[\x.y]))]]
T[\w.T[\y.(S (K y) (S (S (K T[w]) I) (K T[y])))]]
T[\w.T[\y.(S (K y) (S (S (K w) I) (K T[y])))]]
T[\w.T[\y.(S (K y) (S (S (K w) I) (K y)))]]
T[\w.T[\y.((S (K y)) (S (S (K w) I) (K y)))]]
T[\w.(S T[\y.(S (K y))] T[\y.(S (S (K w) I) (K y))])]
T[\w.(S (S T[\y.S] T[\y.(K y)]) T[\y.(S (S (K w) I) (K y))])]
T[\w.(S (S (K S) T[\y.(K y)]) T[\y.(S (S (K w) I) (K y))])]
T[\w.(S (S (K S) (S T[\y.K] T[\y.y])) T[\y.(S (S (K w) I) (K y))])]
T[\w.(S (S (K S) (S (K K) I)) T[\y.(S (S (K w) I) (K y))])]
T[\w.(S (S (K S) (S (K K) I)) T[\y.((S (S (K w) I)) (K y))])]
T[\w.(S (S (K S) (S (K K) I)) (S T[\y.(S (S (K w) I))] T[\y.(K y)]))]
T[\w.(S (S (K S) (S (K K) I)) (S (S T[\y.S] T[\y.(S (K w) I)]) T[\y.(K y)]))]
...
...

it... got out of control, and since I was doing that manually, after I finished I wasn't too sure of its correctness.

I stopped there.

The wife had already put the Wii back together, and I was playing Super Mario Galaxy in no time after stopping :)

Monday

I think one can skip using the Y combinator, and perform a limited form of iteration (call something a fixed number of times), using the Church numerals; if you want to call something N times, build a Church numeral for it, and then apply it to the function you want to call, and its argument. We'll see if I don't run out of gas this week and get something along those lines.

Lessons learned

  • Do your best to understand completely the problem statement; don't get stuck on it, but do get back to it ASAP, once you get your head clear. That's a stupid mistake I've made twice.
  • I don't know a iota about functional programming. All of the sudden I felt like stopping mocking Haskell and its funny error messages, and got a moderate desire of learning to program using it. (update I think I'll skip types and go play with Umlambda instead. You know, I don't have chest hair yet, need to earn my manhood yaddayaddayadda.)
  • Going to bed before midnight, and getting up before 8am are far better strategies that coding 'till you can't stay awake and getting up at noon the next day feeling like crap.

And stuff that I already knew:

  • Pair programming is an excellent way of tackling nasty programs.
  • Clean dishes and good supplies of food (food, not Bachelor Chow (TM)) are exceedingly valuable resources. Make sure of having plenty of both before the contest starts (that would have saved us at least 2 hours.)

Notes and stuff

The Git repository for the code is available at http://git.devnull.li/icfp2011.git. You can clone it using that URL (it wasn't working in the morning, but it works now.)

Some interesting links:

When looking for information about how to program using CL, many pages made references to a book, to Mock a Mockingbird, about CL puzzles using birds as metaphors for S, K, derivatives and friends; it does look interesting. Dear Santa, yaddayaddayadda ;)

See you next year.