Friday, February 22, 2008

Claim 1: A language that supports the ability to program in continuation-passing-style is significantly more expressive than one that does not.

By `expressive' I mean something like Matthias Felleisen's `macro expressibility' — rewriting the entire program doesn't count.

This claim is pretty self-evident except for the word `significantly'. You might argue that continuation-passing-style is an unimportant triviality.

I'll argue that Steele's Lambda papers clearly show that continuation-passing-style can be used to express arbitrary control structure within the language. You don't need to modify the interpreter or compiler.

I need to define what I mean by `supports the ability'. The first thing you need is the ability to `pass a continuation' to a program and possibly invoke it. To do this, you need some mechanism for binding code to a context and using the result as an argument. Lisp does this trivially with anonymous lambda expressions. C# can use anonymous delegates. The anonymity saves you from having to think up a name that won't ever be used, and the lexical nesting of these constructs saves you from having to figure out the necessary context, but you can achieve the same effect (albeit with some extra work) with the popular class/interface constructs you might find in Java.

There are some other things you need to truly `support the ability', but I'll save them for another post.