Lambda the Ultimate

Like math puzzles and physics puzzles, there are many different kinds of programming puzzles. One way to classify programming puzzles is by the skills they exercise or the concepts they illustrate: knowledge of a language, designing a new algorithm, understanding a specification, etc.

On LtU, I'm interested in puzzles that are not specific to a language yet rely on a PL notion. Here's one attempt of mine, inspired by my student Jun Dai:

Your stair-climbing robot has a very simple low-level API: the "step" function takes no argument and attempts to climb one step as a side effect. Unfortunately, sometimes the attempt fails and the robot clumsily falls one step instead. The "step" function detects what happens and returns a boolean flag: true on success, false on failure. Write a function "step_up" that climbs one step up (by repeating "step" attempts if necessary). Assume that the robot is not already at the top of the stairs, and neither does it ever reach the bottom of the stairs. How small can you make "step_up"? Can you avoid using variables (even immutable ones) and numbers?

What do you think? What is your solution? How are the solutions related to each other? (If "step" fails with a fixed probability, then how many times does "step_up" expect to call "step"?)

More importantly, what is your favorite PL puzzle that is not (terribly) language-specific?

Ralph Johnson mentions an interesting project from Pavel Krivanek to modularize Squeak. For example, there's a KernelImage that excludes the GUI (it's 2.8 MB compared to 15 MB for the full 3.9 release). The modularized images are created automatically from the complete image, by Squeak code.

It's been awhile since we discussed Squeak, which remains as far as I can tell, an interesting project worth keeping an eye on.