Monday, July 23, 2007

Python to the rescue: ICFP contest 2007

The ICFP contest was great fun this year, as usual, and I actually arranged travel and moving plans so that I would be in one place for the weekend to work on it.

I resolved to work in Scala this year, because it seemed like a practical functional language I'd like to know better; and it allows imperative programming with the java libraries, so I thought it would be a smooth learning curve.

Well, I spent the first day butting my head up against Scala, and dealing with condo repair contractors and a fussy HOA board in the meantime: at the end of the day I had basically no running code and a splitting headache. The cure: beer and python.

The second day I changed to Python, which I really haven't used *that* much, but it's easier to figure out how to do things. I'm not sure why -- maybe it's a question of documentation, or maybe it's just that I don't get functional programming as well as I thought I did.

In Python I managed to get an interpreter that basically worked, reading the DNA file and creating images using Tkinter. I don't think it was ever flawless. There was a self-test screen that I eventually got all "OK"s on, but I never did see these manual pages that people on the discussion list were talking about.

The Python was still too slow to make further debugging feasible, so I rewrote it in C. Got that working sometime Sunday, and it was faster, but it wasn't faster enough. The real solution needed to be linked lists to pointers to memory, so one wouldn't need to shuffle megabytes of DNA around -- but I had no mental energy to implement anything like that by that point.

Lessons learned:
Either scala documentation needs work, or I just need to spend more time learning the paradigm
When the problem statement says that shifting byte strings around needs to be done in faster than linear time, that's an optimization I should think through up front, not "get to it later". It made all my implementations useless.
Python is the best language I know of for expressing algorithms. It isn't fast enough, though. (although I wonder what if I tried the linked-list thing in python? I may try that as an experiment)

There were some complaints on the discussion list by people saying that the up-front work was too hard, and that most people never got to the meat of the problem. I totally disagree with that. ICFP is all about making functional programming usable and efficient. If, with current tools, we are forced into low-level bit-schlepping in C, it points to a deficiency with the most common tools of functional programming, or in the training of programmers. The contest ought to be about illustrating that kind of issue in a fun way.

Here's an interesting point: languages with higher-order kinds of functionality tend to abstract one away from the machine more; working with heavy integer "objects", for example, instead of raw machine integers as C does. Is it possible to have a language where you can talk about bare metal, even registers and such, but do it in a higher-order abstract way when desired? I guess C++ attempts to do this in some ways, but it's an extremely complex language. Is there no better compromise?

1 comment:

Clive said...

Nice to find a writeup by someone else who also used Python!

I decided it looked like a C/C++ kind of thing when I read the spec, but couldn't face all that extra code cutting (basically working on my own this year), so started with Python, and never progressed past it!

I had at least one bug during most of the contest but still managed to find some additional images with a bit of extra work to sidestep the various problems, plus a bit of "hacking into the DNA". Everything was working correctly (AFAIK) by the end of the contest butit was still too much much slow anyway!

I have also been toying with trying to see how fast I can get my Python implementation to run, just as an experiment. Another thought was to wrap the C cords library with Pyrex and use that.

Clive Gifford (K.I.S.S. Team)