Three things are needed to support continuation-passing-style programming:

1. First-class procedure objects or some equivalent.
2. General tail recursion.
3. A type system that won't have conniptions if you try to program in CPS.

This last one can be a serious problem. Let me demonstrate with a simple example. Suppose I have a table that can contain aliases for keys. An entry in a table could map a key to a value, or it could map a key to another key. The basic way to probe the table would be with this CPS function:

(define (lookup key table if-alias if-key if-not-found)
   ....)

(lookup 'my-key *the-table*
    (lambda (another-key) ....)
    (lambda (value) ...)
    (lambda () ...))

.
Of course the point of the aliases is to have multiple names sharing the same value, so the typical use would be to perform a chained lookup if you find an alias. You'd have a procedure like this:

(define (chained-lookup key table if-found if-not-found)
  (lookup key table
     (lambda (another-key)
       (chained-lookup another-key table if-found if-not-found))
     if-found
     if-not-found))

.
Scheme is a unityped language. (Bear with me here. I'm going to use the terminology of the static type community.) Both `if-found' and `if-not-found' will produce the same type of object: a `Scheme object'. And whoever consumes the result will expect nothing more nor less. But what if our language has static types?
Chained-lookup clearly produces an object of the same type as lookup, so we'll start there. Lookup consumes a key, a table that maps keys to values or keys, and three procedures that are constrained by the logic of lookup.
lookup: K x Table x (K -> R1) x (V -> R2) x ( - -> R3) -> R
This is a bit nasty. There is a key and value type, K and V respectively, but what are these R1, R2, and R3? The continuations can pretty much compute what they want, so R1, R2, and R3 are the return value types. We know that the lookup will return one of these, so R is the most narrow supertype of R1 R2 and R3. I'm cheating a little bit here. The argument of the continuation K->R1 can accept objects of a narrower subtype than K. So in the type description above, the different types actually express upper and lower limits on the types of the arguments. (The upper limits are co-variant and the lower limits are contra-variant.)
So what about chained lookup? Intuitively it ought to be this:
chained-lookup: K x Table x (V -> R2) x ( - -> R3) -> R
But is chained-lookup calling lookup correctly? What is that first continuation? Intuitively, we know it maps K -> R (where R is the most narrow supertype of R2 and R3), but is the compiler's type system able to deduce or accept this?
Well, that depends. Some languages have pretty complex type systems that can figure out what is going on. Others have ways to decorate your code with type variables (templates or generics). Others have ways to turn off the type checking (casting to void * and back). Or you may be screwed.
The point I'm trying to make here is that even if your language supports first-class procedures and tail recursion, it still might be impractical to write in continuation-passing-style because the type decorations become unmanageable.

Claim 2: General tail-recursion is an essential element of a programming language.

By `general' tail-recursion I mean that all calls that occur in `tail' position avoid allocating. Many languages or implementations support `self' tail-recursion in which tail-recursive calls to the same procedure are compiled or interpreted as loops, but fewer support the completely general case of arbitrary mutual tail-recursive procedures acting as a loop.

`Essential' is trickier to justify. There are many arguments for it and one really big argument against it. Might as well play devil's advocate first.

General tail recursion cannot be `essential' in a meaningful way because few programming languages support it and no one is complaining.

That is certainly a true statement, so let's compare a hypothetical language that has two variants, one has no tail recursion, the other supports general tail recursion. The first observation we can make is this: Any program that runs in a language without tail recursion will also run in a language with tail recursion. (That is, if it completes with an answer, both versions would produce the same answer.) The second observation is this: There are programs that run in a tail recursive language that will fail to run in a language without tail recursion. These would obviously be the programs that run out of stack or memory. So the claim that general tail recursion is essential is equivalent to the claim that there exist interesting programs that run in a tail recursive language and fail to run in a language without tail recursion. The devil's advocate position would deny this:

General tail recursion cannot be `essential' because there are no interesting programs that require a general tail-recursive implementation.

It seems unlikely that this is an a priori truth. Even the fact that there exists a class of programs that require general tail-recursion is interesting in itself. There is a slightly weaker argument that gets around this objection without much difficulty:

There are no interesting programs that require a general tail-recursive implementation because there are equivalent programs that do not require a general tail-recursive implementation.

This is also true, but the argument has been critically weakened. The equivalent programs are not, in general, `macro expressible' in the original language. You can turn the self tail-recursion into a loop fairly easily but you cannot make a loop out of mutually tail-recursive procedures without whole-program analysis (that is, an analysis at the level above the scoping of the mutually recursive procedures).

So why doesn't anyone complain about this? Most programming languages require you to write loops using special primitive looping constructs. These languages encourage the programmer to indentify and separate out the iterative and recursive forms. The programmer is trained from very early on to perform the larger analysis needed to identify iterative control flow and rewrite it as a looping construct. It isn't all that difficult, you have to do it anyway, so what's there to complain about?

Continuation passing style.

Continuation passing style is an example of a programming paradigm that can be very difficult to convert into a looping construct. Every CPS function performs a tail-recursive call to another CPS function, and rather than keep nested state on the stack, the state is kept in nested closures. If every function takes exactly one continuation argument, then it isn't too hard to `unravel' the CPS code into an equivalent `direct style' program, but the more complicated CPS code that takes more than one continuation cannot be easily converted to direct style.

There are few loops in continuation passing style. Control is transferred from function to function in a uniform manner and the difference between `iteration' and `recursion' is seen only as a difference in the space complexity of the continuation arguments. The interpreter or compiler must be sure to avoid inessential allocation when transferring control or an otherwise iterative construct would consume an arbitrary amount of memory (or stack).

If you agree with my claim that languages that support continuation-passing-style are more expressive than ones that do not, and that general tail recursion is a necessary prerequisite for continuation-passing-style, then you ought to agree that languages that have general tail recursion are more expressive than ones that do not.

Some more about general tail recursion later.

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.

Linearity

What exactly is ‘linear’ about ‘linear logic’?

How many strings can you intern?

Assuming a 32-bit OS and processor. Suppose we define INTERN to take a series of bytes with an upper limit on the number of bytes (say 128 bytes) and return an unsigned integer in [0, 2^32). Another function SYMBOL-NAME takes the unsigned integer and returns the associated bytes (or stuffs them in a buffer, or whatever). How many strings could we reasonably intern? Could we get to 2^32 without going to disk?

You're a regular when...

your picture appears on the web page of the pub you hang out at.

That's me and the missus hanging out.

Drop in if you want to talk Lisp or Scheme. I'm there nearly every evening.

I saw that Google is putting up $20M dollars as a prize for landing a rover on the moon. (See http://www.googlelunarxprize.org/) I was wondering if that were remotely worth the effort.

You can just hire a company to put a satellite in orbit. The Falcon 9 is supposed to be “the lowest cost per pound to orbit” and it costs $35M to put a small satellite into geosynchronous transfer orbit. Of course the Falcon 9 doesn't actually exist yet, but if it did, you'd only start out $15M in the hole.

Part of the problem of a rocket is that you spend a lot of the energy lifting the fuel and oxygen to the altitude where you plan to use them. I was daydreaming a way to avoid that. If you use a ramjet or scramjet for the lower altitudes, you can use the existing oxygen in the air. This cuts the amount of lifting you have to do by half. Now if you could just figure out a way to get the fuel to where you need it without having to carry it with you.

My initial infeasible idea was to have a long hose.

But then I was thinking that you don't really need a hose to keep the fuel confined. If you squirt a droplet or two of fuel in the path of the oncoming jet, it can be sucked into the intake just like the oxygen. It shouldn't be that hard to time it right. Of course it wouldn't be possible to build a tower tall enough to make this useful, but maybe if you put the tower on the side of a mountain so you can get a few miles of thrust before you have to use the internal fuel supply.