ICFP programming contest 2009!

Not too long ago, Lindsey Kuper and I stepped into the ring once again to compete in the ICFP Programming Contest!

She's writing up the full story over on Geek Buffet.

The quick recap, however! The problem had to deal with orbital mechanics -- we were to control a simulated satellite as it orbits a simulated earth. First, you just had to transfer orbits, then meet other satellites, and it got increasingly complex from there.

Thankfully, the physics simulator for each kind of problem was included. All you had to do to use it was implement the contest-specific VM! (Easy, right?) Thankfully, the specification for the VM was super-clear, and we got it working surprisingly quickly.

By the end of the contest, we could handle the first two problem types, and that was competitive enough for 120th place worldwide, by the morning when they turned off the leaderboard. Good show, us!

For the full scoop, go read Lindsey's account.

Here's the code! We used Scheme and Python, and R for the visualizations.

Lisp insights from learning Logo

So I was just writing a simple recursive procedure in Logo. I wanted to go down a list, cons up a new list, and return the empty list when I get to the end.

My first pass, once I found out how to return something from a function (Logo procedures aren't expressions -- you have to explicitly return) had a line like this:

if (stacks = []) (output [])

Running the procedure gave me the helpful error message:
output didn't output to if in astep
[if (stacks = [] ) (output [] )]

Pardon?

When I remembered that Logo's "if" wants a list of instructions, it clicked with my new nugget of knowledge that literal lists are quoted in Logo. Then I understood what was going on: this "if" is neither a macro (like in Scheme, or most languages) nor lazily evaluated (like Haskell). It's a regular function, but one that expects quoted code to evaluate on demand at runtime. Rubyists and Smalltalkers: this is something like how an if block works for you, yes?

Here's an analogy into Python, for the non-Lispers out there:

def myIf(tf, truecode, falsecode):
  code = {True : truecode, False : falsecode}
  return eval(code[tf])

>>> myIf(0 == 1, "'it was ' + 'true'", "'it was not true'.upper()")
'IT WAS NOT TRUE'

>>> myIf(0 == 0, "'it was ' + 'true'", "'it was not true'.upper()")
'it was true'

Also, apparently Logo in general has dynamic scope -- which shouldn't surprise me, since lexical scope is relatively new in Lisp. And Berkeley Logo in particular has macros. Maybe my little compiler project is going to be harder than I expected. Honestly, I was imagining I'd be done if I could just parse it, do some simple transformations on the tree and spit JavaScript.

Debian on the OLPC

I should go to bed, but I'm having so much fun setting up Debian on my XO laptop.

It was super-easy getting it installed (instructions here); you use the same command for updating to a new version of the standard olpc software and for installing Debian. Or Edubuntu, apparently.

For extra disk space, I blew away the default Sugar/Fedora install -- it's pretty easy to get back to a fresh state, just in case I want to set that up again later.

In 472 megs, I have the base Debian, X.org, subversion, vim, fluxbox, mzscheme, and the Glasgow Haskell Compiler, the install for which pulled in gcc, so was big.

Lisp snippets on a Tuesday night

The ICFP contest is coming up, and Lindsey Kuper and I have been building our Scheme muscles. I was looking for an implementation of hash tables (or just some quick way to do a map), and I ran across the SRFIs -- Scheme Requests for Implementation. It's a semi-standard library of useful stuff for Scheme, and it's bundled with recent PLT Schemes! You can just say: (require srfi/n) to load up the nth SRFI; they're numbered. Particularly, I've been playing with the extended libraries for lists, strings, and hash tables.

On the Common Lisp side of things; I just ran across the insanely useful describe, which prints out what the system knows about a given object -- if it's a function with a docstring, the docstring will be in there. Also potentially useful: disassemble. Give it a function; it does what it sounds like!

You get spoiled by languages with first-class functions

Earlier today, I needed to take a list of strings and grab all of them that end with ".html". Very simple task. My first thought is of course something like:

[fn for fn in fns if fn.endswith(".html")]

Or even:
filter( lambda x: x.endsWith(".html"), fns)

Or the equivalent Lisp. Y'know, with "loop" and "collect". (Common Lisp has, as they say, the Cadillac of loop syntax)

Or something to that extent. But then I remembered that I was writing in Java, and I ended up writing a for-loop. There's no clean, idiomatic way to say that in Java, is there? Do you have to build up the list procedurally? ...

java 6: apparently even less of a loss than java 5!

Java 6. It's so hot right now. Java 6.

Well, I'm excited anyway. The new Scripting API provides a standard interface for embedding other languages in Java and making calls between the two. See if there's already a project to handle your favorite language here -- there probably is, unless you like Common Lisp. There's even a mechanism for manipulating namespaces in the embedded language, pretty snappy.

Apparently recent releases of Jython already have hooks to support the new API. Maybe the next version of JES should be rewritten with that in mind, say once Jython 2.2 is stable. And perhaps we'll see ABCL ported to the new standard...

Also in Java 6, the built-in support for splash screens is kinda cute. And they're saying that the whole shebang is faster and prettier. Good job, guys!

things that start with p

Programmable completion for bash (mentioned earlier) is still a pretty exciting idea. I came up against the first situation where I felt like it needed to be extended today, though.

I've taken to using jar to deal with .zip files, so I can use consistent tar syntax and don't have to remember how to use the zip options. But! The bash_completion file for Ubuntu doesn't include ".zip" as an extension that it looks for when tab-completing files for jar, oh noes!

Easy enough to fix, right? I pop open /etc/bash_completion and start searching for "jar". There's a section near the second occurrence that looks like:

         _filedir '?(e|j|w)ar'

After some fiddling, I change that one line to " _filedir '?(ear|jar|war|zip)' ". And it works! For reference, that the _filedir function looks like this. It's painfully obvious to everyone what this does, yes?

To be totally fair, there's some explanatory comments right above it... but it's obtuse things like this that make we want to switch to a shell with a more sensible scripting language. bash is often line noise. We claim that allowing users to modify their environments to fit their needs is one of the major benefits of Free Software, but are we doing enough to encourage that? How is your mom supposed to pick up bash script? It seems like scsh isn't meant for interactive use as your daily shell, but what if your everyday environment had a more modern language embedded in it? Are things like that already out there?

Also: speaking of Scheme embedded in things, JScheme is a dialect of Scheme with a very simple interface to Java, called the Javadot notation . It's by Peter Norvig and crew, fairly recently updated and feature-complete. Also on Peter's (fantastic) site, you can find his older "mercilessly small, easily modifiable version". I very badly to embed this in JES. Media Computation in Scheme ahoy.

Mapping and reducing is like popping and locking for programmers

If you don't read Lambda the Ultimate, that's quite alright. But fairly often over there, you find a link to Why Functional Programming Matters, by John Hughes. Recently, I decided to sit down and actually read it. It's mind-expanding!

Previously, I'd thought about mapping functions onto lists as an operational thing, a set of steps to complete, but that's not the cleanest way to think about it. Mapping is actually a special case of "reduce", an operation where you just go through and replace the all the "cons" functions in a list expression with something else, then evaluate the expression again. "map" functions have a cons in the function they're reducing with, so the end result is another list.

For example: you might write, in lisp: "(mapcar #'(lambda(x) (* x 2)) '(1 2 3 4))", yielding (2 4 6 8).. and you might think of that procedurally... but a map is just a reduce where "cons composed with the mapped function" replaces every "cons". Append can be written similarly; it's all essentially just replacement, function composition and evaluation. The paper also goes into beautiful issues like lazy evaluation (the author says that if he wrote the paper now, the examples would be in Haskell!) and continues to do some lovely examples, some numerical and one very close to our heart: a bot that plays tic-tac-toe, optimally, with pruned game trees.

Years ago, Kurt Eiselt told me that the future of computing was going to be functional languages on very-parallel hardware; functional languages, at least in principle, make synchronization easier by limiting or removing-altogether side effects. (although reconciling this idea with stateful, event-driven end-user applications is another issue!) To an extent, it looks like he was right, and the future is here! MapReduce is the method Google is using to crunch super-giant datasets with enormously parallel clusters. It's not just for functional languages, of course, but the idea is there.

rapid-feedback poetry and lisp environments

I think, ultimately, TEB is going to want to be less of a fully automated thing and more of a computer-aided composition tool for poetry. Or maybe it'd be better to think of it as a generator, with a human in the loop. Something that would let you get really rapid feedback and come up with suggestions. It would let you build poetry by search, recognizing what you like and what you don't like. And it'll keep versioning information...

Hey, speaking of development environments! On Lemonodor, I just found out that there's an Eclipse plugin for writing Lisp called Cusp. It uses SBCL and swank, like all right-thinking lispers, letting you do SLIME-like things without Emacs -- SLIME being the currently en-vogue common lisp development environment, and swank being the backend. There's a similar project out there that I've been watching too -- Slim-Vim, which is an attempt to make that same swank code work with vim. (the mailing list has been a little quiet, but it might pick up steam again)

python generators and more live coding music!

I just found out about the yield python keyword, which lets you produce generator functions. This came up, in a practical context, because I wanted a clean way to get n items at a time out of a list, and the Python Cookbook approach uses generator functions. They let you build an object that essentially contains a closure of the current environment, which can be iterated on. Sort of like lazy lists! Of course, the same behavior could be done with C-style static variables, but this is really pretty.

- yield keyword from the Python docs
- a discussion of generator functions over at IBM Developerworks.

Also! Brett alerts us to Impromptu, another live coding environment for making music and stuff! From their site:

Impromptu is an OSX programming environment for composers, sound artists, VJ's and graphic artists with an interest in live or interactive programming. Impromptu is a Scheme language environment, a member of the Lisp family of languages.

Beautiful educational software :)

So many of you are probably aware that my job (ie: research assistantship, ie: how I'm getting gradschool paid for) is to work on JES, the Jython Environment for Students -- it's the little IDE that we use at Georgia Tech to teach introductory CS classes to non-majors and for summer camps as part of our "media computation" effort. A number of other schools use our stuff too, which makes me pretty happy. We're releasing a new version soon, and it's going to rock hard and be faster and include LOGO-style turtles! I'll put up links when it's out.

But speaking of LOGO-style turtles and media computation:
- The KDE Project has KTurtle out now, which looks pretty cool. It's part of their bigger KDE Edutainment effort.
- TuxPaint is also pretty cool! My friend (and noted cartoonist) Brett finds it pretty amusing. It reminds me of KidPix, which you might remember from your childhood if you're about as old as me -- and that's still out there, apparently?
- Tux Paint comes to us from New Breed Software, which has a bunch of other cool educational products.
- And if you only click one link on this post: Pictures Kids Made With TuxPaint

And, for completeness:
- Alice is a programmable 3D environment up outta CMU that rocks harder than I can describe in a quick blog post. As they put it on their site, "Alice will make programming a means to an exciting end." That exciting end is really easy 3D storytelling.

Red pandas and rhinoceri and turtles? ...

Why is there not a client-side javascript version of LOGO?

How cool would that be? Turtles in your browser? ... Small children having access to Papertian goodness wherever the Internets are tubin'?

Lisp is still really pretty.

So I'm building some decision trees for a project I've been working on -- this automatic typo correction for tiny blackberry-style keyboards. The motivation for this is pretty obvious -- we have to decide when to do the correction and when to let the user type what they're typing!

I'm going through some code I'd had for an earlier project, this one done in Common Lisp. And I've been really excited about Python recently -- but man, Lisp is so nice for data structures. There's so little punctuation for building things. I mean, goodness -- it's as if the language was made for dealing with recursively nested things. I'm a little reluctant to translate this stuff -- why am I not just using CL, again? ...

Oh yeah, because I need to make it talk to other programs.

Also! Roughly the hippest thing ever is the __call__ construct on Python classes. If an object has a __call__() method defined on it, then for object foo, you just go foo(arg), and it does its Pre-Defined Thing. Check it out! ("emulating callable objects")