This post originated from an RSS feed registered with Agile Buzz by James Robertson. Original Post: Continueing Continuations Feed Title: Michael Lucas-Smith Feed URL: http://www.michaellucassmith.com/site.atom Feed Description: Smalltalk and my misinterpretations of life Latest Agile Buzz Posts Latest Agile Buzz Posts by James Robertson Latest Posts From Michael Lucas-Smith

As I mentioned previously, the core of continuations is that you don't need a stack. At least, not for passing parameters. Actually, using a stack can become quite awkward with continuation passing style.

So lets get in to some more guts of it. I'm going to be putting a Smalltalk spin on all of this. So if you don't know Smalltalk, pick up a book now and play with it.

The key to continuations is to turn every statement in a program in to a tail call. In a stack passing scheme, you pass to the method you're calling the pointer to return to. This has some implicit requirements that once you've returned all the state will be as it was.

In continuations, you pass the pointer to jump to next. This is significant, as you can see the program as "always going forward, never going backward". If you never 'return', then you certainly don't need to preserve the state on your way out or way back.

A procedural programming language could pick this up very readily and you'd end up with a compiled form that ran faster than standard C instantly. But for a language like Smalltalk, where ever call is a dynamic dispatch, we have to do a bit more work.

First of all, I don't want a VM, I don't like VM's. We already have one too many VM's in a bare computer and that's the CPU. More on my wacky philosophies later though. So, without a VM, DD must come from an inline lookup. Thankfully, people have solved this puzzle before, inventing the concept of the Polymorphic Inline Cache.

Use more memory, have a pointer to a collection in your method that you do the lookup in. Inline all lookup code, then jump to the code you've looked up. There are huge performance disadvantages to this, where standard ML will transform parameters because it knows who you're calling. In Smalltalk this is simply not possible, you only know that you may be calling one of 'x' methods, and even that may fail and fall in to a DNU.

All that aside, is it faster to do stack manipulation or is it faster to do the dynamic lookup? - well, it doesn't really matter because current Smalltalkers do the stack manipulation at two levels already. First they have the C level stack and second they have the Smalltalk level stack. Still, they somehow manage to make the code run only 4x slower than a C++ program. What if it were 1.2x slower than a C program instead? Continuations can possibly give us that.

Okay, back to making a Smalltalk program in to a continuation passing style. This is where things get wonky with my mind, so bare with me as I make mistakes and mislead you all...

An innocent piece of code, but we can learn much from it. First step in CPS it to separate substatements in to their own statements and store them in to a variable.

We see here that Smalltalk makes it very easy to do this. Smalltalk has neatly separated out all subexpressions for us, we just have to give them a label. The next step is to give every method call a continuation argument and to label each part of the program that is a continuation. I'm going to resort to {} syntax here, because I'm adding a new argument to every call.

At this point we need to investigate how parameters will be passed around, given that no state is preserved from the past. How do we remember what we need to remember? Well, in this scenario we're storing things in to local variables, so it turns out we don't need so many arguments in memory after all.

In fact, at most there are three variables being used as arguments - one is the continuation. Then add a fourth for the return value. Wow, a normal program can use the same number of arguments as in a CPU.

What about more complex programs? Simple answer: I don't know yet. I haven't read that chapter of the book. They call it 'register spill', when you run out of registers to pass arguments in. My guess is this: Because you've assigned each statement to a variable, regardless of whether its on the heap or stack, you only have to worry about how many registers are being used in the call you're about to make.

If you have too many, they assume the method you're calling follows a convention of accepting an n-tuple as the parameters. This is reasonable. Don't forget though that using a closure may also reduce the number of arguments being sent. It may be more reasonable to say the n-tuple will be stored on the stack.

At this point, we can discover stuff about our program, like the fact that using a register machine we don't need as many variables. Consider the first few statements:

The only user of 'a' is 'b'. And since the result of the 'a' call will be in a register, we don't need to use memory space for it. In assembly it turns out something like this:

This may still seem like a lot of work, but in actual fact with a modern CPU most of that work disappears in to a single cycle. Also, we may discover through analysis that the best first argument is not ebx, but in fact eax.. and that some operations such as + can be done using an ASm instruction, so the program can become:

There, that's much better. we inlined the operation of +, used eax as the first parameter and the first few statements shrunk incredibly. Better still, the program was written in a high level OO language and we've ended up with extremely optimised ASM underneath. C is often hard pressed to do that kind of optimisation, simply because of all its stack work it needs to do.

Mind you, there is nothing stopping anybody from implementing a C version of continuation passing style. So when I compare this stuff to 'C', I compare it to current C compilers that use stack passing style.