For the 2014 ICFP programming contest, most of the fun I extracted from it in those 72 hours was in having an excuse to play with programming language design ideas — and then not actually implement most of them. I have to admit that my solution to the actual competition problem was kind of mediocre, and the language toolchain I wound up with wasn’t as interesting as it could have been. In the aftermath I wrote up the general ideas and motivations/context (and helpfully left covering the specifics to my then-future self).

And for some reason I thought it was a good idea to title the sections like video game levels…

Level 1

You start out with some simple but sort of serviceable ghost programs, but basically nothing for Lambda-Man. So that probably seems like the place to start. It’s also the more complex and capable machine by far, and has the more straightforward side of the game rules; and, before the second-day spec changes, that’s all that was being scored.

It also has to do everything itself — no help from the game rules like the ghosts — and needs more work to do basic things like map square lookup, which strongly suggests a compiler rather than hand-coding.

And Lambda-Man’s SECD machine is basically Scheme. Every instruction immediately brings to mind one of its core forms or primitives. (Or not so immediately, judging by the comments on IRC, but… just look at the difference between let and letrec, then at AP and RAP.)

Which is backwards, of course: we have always already seen the lambda calculus as the stuff of programming and tried to program in it — including by creating Scheme — because of the SECD machine and Peter Landin’s other greatest hits, if I recall my CS history correctly.

Anyway. I also didn’t feel like writing a parser, so it came to pass that I dusted off Racket (because it was either that or relearn Common Lisp) so I could quasiquote a Lisp dialect and straightforwardly compile it. And wrote some simple programs.

At this point I could see how I could develop a library of more sophisticated functional (or mutable!) data structures for traversing the map and such, and build some kind of pathfinding / search algorithm, and try to come up with heuristics based on it.

But I really wasn’t all that excited about dealing with the pathfinding and strategy stuff. I might have been willing to put in a little time on data structure implementation, but having no debugging or type-checking facilities if I didn’t write them first was a little scary. In any case, there was something more interesting I wanted to play with:

Level 2a

The time limit.

There’s usually one in some form; there kind of has to be when the organizers are being sent programs to run, but for the ICFP contest it’s a little more than that. The original idea, from what I can tell, was to be a competition among languages more than among people, and in that capacity it was meant to reward both expressivity and machine performance (i.e., there was to be none of the usual “sure, functional programming is great, but it’s just too slow to be practical”; see also “Ousterhout’s dichotomy”).

But when you’re dealing with a time limit on a “real” CPU, you usually have some kind of facility to check how much you have and/or signal you when you need to stop. Here, you don’t. If you go over the limit, you get mysterious catastrophic failure. And it’s small enough that it could matter if things are too naive or overcomplicated — how many breadth-first-search iterations do you run? How much safety margin do you need to make sure you don’t hit all the slow paths in a row?

Beyond that, it’s interesting theoretically. What could I do to a language to make it easier to statically analyze running time? And in a context where there are no cache effects (or pipelines, or page faults, or external interrupts, or…) to reason about, and no existing codebase to accommodate.

Level 2b

Continuations.

Given the time limit, it might be nice to have some kind of generator-like construct to suspend and resume a computation written in direct style, instead of needing to manually convert it into an incremental form. This suggests a conversion to continuation-passing style — or, looked at another way, changing the function call ABI to pass return values on the environment stack instead of the data stack. As a convenient side-effect, this pleasant symmetry of call and return allows a treatment of multiple return values that doesn’t go horribly wrong in case of arity mismatch, the way using the data stack would.

Also, this has some useful interactions with a time analysis. If the whole program can’t easily be statically time-analyzed — due to recursion and/or indirect calls — then maybe it can be analyzed from one yield point to the next. That leads to the idea of the main program bouncing on a trampoline, each step returning a closure for the next step paired with the worst-case time to run it (and/or the time actually used), and maintaining the best result it could find in a mutable cell for use when time is up.

But having to impose that kind of overhead on every non-statically-obvious function call seemed like not the best idea, especially given a Scheme-like source language and the ideas I was having about using closures to implement mutable data structures (i.e., frequent calls to closures that were fished out of the heap). It’d work, sure — but could it work better?

(To be continued…)