Python tip: 3.2 adds a memoization decorator

This is a really handy thing to have around, in case you've got expensive computations that you want done more than once. I've written a clumsier version of this myself, once or twice -- but it makes sense to have in the standard library!

http://docs.python.org/py3k/library/functools.html#functools.lru_cache

There's some other neat stuff in the functools package too: currying and reducing. Pretty slick!

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.

Scala article on the Scala site!

I helped Lex Spoon and Toby Reyelts write an article about running Scala on App Engine.

Here's the article! As of right now, it's linked from the front page on the Scala site.

In the article, we mention my Scala/GWT sudoku solver, which is now available on Google Code. It's also live on App Engine right now!

Further steps: Scala/GWT/App Engine/Eclipse

I've been excited about Scala recently, for a number of reasons -- it's a modern language with lots of great features that you might expect if you've been looking at Haskell or ML. It's got pattern matching, a concise syntax, type inference, and first-order functions. The really killer thing about Scala, though, is how well it integrates with Java.

You can very easily have a mixed Scala and Java project, and make calls back and forth; Scala and Java packages sit in the same package hierarchy and compile to the same bytecode -- it all just works, pretty much seamlessly.

So, clearly, the right thing to do is hook Scala up to GWT RPC and run it on App Engine. Let's do that. This is as awesome as it's going to get, at least until the GWT compiler supports Scala and we can do our client side in Scala too.

I assume you've already installed both the Google Pluin for Eclipse and the Scala IDE for Eclipse. I'm using Eclipse 3.4.

Make a new "Web Application" project (with File > New, or just click the blue "g" icon). Click the boxes for both "Google Web Toolkit" and "App Engine" -- our client side will be in GWT, and the server on App Engine.

Right now, our new project has "Java" nature, but not the "Scala" nature. Add Scala by right-clicking the project and choosing Scala > Add Scala Nature. We're also going to make sure we have a copy of the Scala runtime library once we deploy to the server. Find out where scala-library.jar sits (expand out the "Scala Library" container in your project) and copy it into the project's war/WEB-INF/lib.

Now, down to business. There's a RemoteServiceServlet currently implemented in Java, and we're going to replace it with Scala code -- this is the thing that gets called on the server side when the client makes an RPC request. Find GreetingServiceImpl.java and delete it.

To replace it with a class implemented in Scala, right-click your "gwtscalademo.server" package and select New > Other > Scala Wizards > Scala Class. The class we deleted was a servlet and referenced by the web.xml, so give the Scala class the same name: GreetingServiceImpl.

Here's my version:
package gwtscalademo.server
import gwtscalademo.client.GreetingService
import com.google.gwt.user.server.rpc.RemoteServiceServlet

class GreetingServiceImpl
extends RemoteServiceServlet
with GreetingService {
def greetServer(input:String):String = {
return "Hello from Scala, " + input + "!"
}
}
Note that while in Java, we'd have said implements, in Scala we say with. As I understand it, this means that Java interfaces get mapped onto Scala traits. Hip!

Now you should be able to run the app locally -- right-click your project and select Run As > Web Application. Once you've learned Scala and made it do something interesting (you're on your own there), you can deploy it to App Engine!

Woo!

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.

my code has a side effect: learning!

So I'm working through the exercises in Real World Haskell. Here's what I've got so far. As of this writing, I'm in the middle of chapter 4. RWH totally deserves all the buzz it's been getting; it's very approachable and well-written, and my Haskell is improving rapidly. The book is still free online, but I bought the printed copy, in large part because Bryan O'Sullivan gave such a great talk at OSCON.

My earlier Haskell project had stalled out due to my not being very good at the language yet. What I want to do is build a compiler for Logo that produces JavaScript, with the turtle graphics on a canvas tag. Logo is an acceptable Lisp! I'd love to see it get more use.

Interestingly, though:

• There's already a beautiful Logo implementation that runs in javascript: papert.
• Mark is working on something like papert, but for Processing -- he wants to put your Processing sketches, how you say, in the cloud.
  
• There are some really nice (and free!) introductory CS texts that feature Logo. Brian Harvey has a pretty serious three-volume set. And there's a version of How to Think Like a Computer Scientist done in Logo.
  

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!

Real World Haskell

In case you haven't been exposed to enough Haskell buzz recently, there's a new book in the works: Real World Haskell by Bryan O'Sullivan, to be published by O'Reilly. In addition to the abstract functional loveliness that you expect, they're going to build webapps that talk to databases, which is not the first thing that pops into my mind when I think "Haskell".

Beta chapters are here.

(if you knew where to look, there was an announcement on LtU about being an alpha reviewer, to get at the pre-pre-release chapters...)

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.