neugierig.org: Tech Notes

The ICFP programming contests are a weekend-long programming contest that is affiliated with a functional programming conference. (It's functionally-oriented, but I recall in past years a team from Google dominated using C++, which I think is a good reminder that tools matter less than talent...) In 2006 I participated, really loved it, and then forgot about it.

Last Friday afternoon Rado invited me to try this year. We were relatively casual about it — I had dinner reservations, we both had kid stuff — but together we ranked 45th place and had a great time. (I saw one person reflecting, "this was the best one since 2006", so I think I got very lucky in picking up this one!) Here is a brief review of the contest biased towards the parts I worked on with some highlights.

The center of the contest was the "ICFP language", a tiny functional language (lambda calculus plus a bit) that serialized in an ASCII encoding. An example from that page: ICFP

B$ B$ L# L$ v# B. SB%,,/ S}Q/2,$_ IK

represents the abstract program

((\v2 -> \v3 -> v2) ("Hello" . " World!")) 42

which evaluates to the string

Hello World

Contestants submitted programs in IFCP that evaluate to a string, e.g. solve problem1 1234 and the server responded with another program that evaluated to a response string.

I hacked up a pretty straightforward evaluator/encoder on Friday afternoon while Rado was at work. From the 2006 contest I recalled that performance mattered so I wrote it in Rust, and in practice it was a couple hours and we didn't need to touch it much over the rest of the weekend. (Rado had never written Rust before but via Copilot managed to add some of the opcodes, more on this below!) For server communication we just used shell scripts driving curl which was also nice because it made it obvious to archive request/response text.

Once we were able to evaluate the first strings we unlocked the real puzzles. Beyond the hello-world evaluator checks there were four classes of problems that were the bulk of the contest. (In the below I have links to the problem descriptions which were posted after the end of the contest; during the contest we were unlocking these as we went and each was a surprise.)

In the first, "lambdaman", the puzzles were simple mazes and the task was to submit strings that were a sequence of up/down/left/right moves that visited every open cell. Rado wrote the necessary graph code (TypeScript) to solve these; I never looked at it. For these puzzles your score was the total size of the ICFP program you submitted (e.g. a string like the B$ B$ ... string in the example code at the top), not the string it evaluated to; for example, the lambaman6 solution was just to move right 199 times which is the string "R" repeated 199 times, but a program that loops to generate that is is smaller than sending the actual string. But even looping in this mini functional language required paying the byte cost for the y combinator; other solutions were smaller. I had a fun time building out my support for writing and measuring programs in the language.

I also built a string compressor, which took our solution strings, generated a recursive compression dictionary, then generated programs that were able to unpack them. This was super neat in that I was generating a custom program per target and the objective was minimizing the total size of the program plus its data, which meant instead of shipping an actual decompression dictionary I generated unpacking logic directly.

// Code to generate decompression dictionary.
// - Var(1) is labmda of the recursive self call;
// - Var(3) is the first letter of the input string;
// - Var(4) is the remainder of the input string.

// Base case: concat(letter, decompress(rest of compressed data)).
let mut decoder = concat(Var(3), apply(Var(1), Var(4)));
for (c, exp) in dictionary {
    // If letter is in compression dictionary,
    decoder = if_(
        bin(Eq, Var(3), Str(c)),
        // decompress(expansion prepended to compressed data)
        apply(Var(1), concat(Str(exp), Var(4))),
        // Else chain to other if expressions and base case
        decoder,
    );
}

In the second, "spaceship", the puzzles were traces of a spaceship's position and the task was to submit thrust changes to match the trace. Again, Rado solved this puzzle with some code that I didn't look at. It peaked as kind of a neat traveling-salesman-esque problem where you controlled the derivative of the position rather than the position itself and I wish I had time to look into it more. I thought to shovel his answers through the above compressor but for this one I realized too late that the program size didn't matter, bummer.

The third was "3d" and it was pretty amazing. The tasks were to write programs in a two dimensional programming language where data flowed around a grid. The language was very weak so even implementing simple functions like "absolute value" was tricky, but it also had a "time travel" operator which let you transport data back to a previous grid state which could be used for looping. For this task I built a web UI that let us interactively write programs. (Demo link of Rado's solution for isPrime, put in a value in the A box to see it go; solution is decent but not contest-winning!)

This probably wasn't absolutely necessary — I saw others wrote solutions just directly in a text editor — but I love making these simple web UIs and like to think my ability to crank these out is one of my relative strengths as a programmer.

For this task the score was based on the dimensions of your solution (grid width x grid height x time used) and so it became a 2d code golf competition, and I like to think my editor let us iterate quickly on new ideas. I had an awesome time thinking through and experimenting with how to reduce our solutions. The hardest problems in this set were quite complex and I thought about building a custom assembler to let us generate these grids. It sounds like some other contestants did this, but also it appears people were solving even the hardest problems by hand. For golf reasons those likely won so we're probably lucky I didn't try.

The final problem set was named "efficiency" and the task was simply to evaluate progressively more complex programs. My trivial evaluator crashed even on relatively simple inputs though so we (which really means "just Rado") instead dumped the programs as s-expressions and looked at the code directly. This turned out to be exactly the right approach, as the most challenging problems here were designed to be impossible to evaluate; afterwards the organizers admitted the intent was for us to read the code.

Rado used a SAT solver to solve one. I myself have never used a SAT solver and it's a pretty impressive tool to be able to pull out of your programmer bag when necessary. Another highlight here was application of AI: given our fake-lisp s-expressions, it turns out Rado could hand them to Claude and ask it to translate them to scheme, and Claude was even clever enough to be able to say unprompted "by the way, this program is a sudoku solver"!

Coincidentally I recently tried out GitHub's Copilot for the first time and I have been completely blown away by it. I had arrogantly assumed that the kinds of code I was writing would be "too weird" for it, but it has no problems with following along and making useful and correct suggestions as I have been writing e.g. Rust procedural macros that are code generating x86 assembly. For the contest, Copilot was similarly incredible, even providing useful suggestions when writing the above snippet that is generating ASTs in an invented language!?

It is interesting to me to consider the fate of programming competitions in our new AI world. For the spaceship problems we realized late that you could take the input traces of coordinates and hand them to Claude with the instruction to plot the spaceship's trajectory. This kind of exploratory data analysis is useful professionally and in decades past I have intentionally cultivated my ability to wield R for it, but AI systems make it so much easier to explore new data that I'm still trying to internalize using them in the way I approach problems.

The (only two) ICFP contests I've participated in are fascinating in that you aren't sure up front where the difficulty of the problem will lie. For the 2006 one my team lost time trying to initially build infrastructure to debug the programs in the minilanguage only to discover that for that problem set (at least in my recollection) the minilanguage only mattered as a way of transporting tasks and once you could evaluate you didn't need any of it. For this year's problem set in retrospect it again is a balance between diving into solving exactly what's in front of you vs trying to feel out what will be eventually necessary.

Relative to my 2006 experience we did a better job this time of trying to make forward progress quickly, but I think we again got ahead of ourselves in the solution complexity. For example, for the spaceship problems after visualizing the data in Claude we would have realized that some of the initial problems were trivial to solve without doing any sort of graph trick. But then also similarly by looking at the data from the advanced problems we could've better predicted what sorts of graph tricks we'd need. From that perspective, looking back, one thing I would do differently is invest a bit more up front time peering at the shape of the input data, probably using an AI to assist.

In all, I had a really great time this year working on this. I am very grateful to the organizers for setting it up, to my family for covering most of the child care, and for Rado for pulling me along!