July 01, 2003

CPS and tail calls--two great tastes that taste great together

Or something like that, at least.

Using tail calls is a nice way to not obliterate your stack, and close to a requirement for the functional language family. In a traditional calling scheme, where stuff goes onto and off of a stack, implementing tail calls can be a bit of a pain. Not a huge pain, mind, but a bit of one, as you have to screw around with the stack some, which is often awkward, painful, or just annoying. I hate complex stack manipulation. Fooey.


If, rather than using a stack calling system you use a CPS system instead, almost all of the pain goes away, which is always nice. (If you don't guarantee timely destruction, all of the pain goes away, which would be nice if timely destruction wasn't actually nicer) How, you ask?

Well, if you remember with CPS, when you call a function you pass in a continuation that represents the place you're going to return to when you're done. In the normal case, a continuation is taken immediately before the call (with a resume address for the code right after the call, otherwise you'd call over and over and over...) and passed into the function you're calling. If you remember with tail calls, when you make a tail call you pretend to be whoever called you, so it's like you never existed.

If you think for a second, how they work together is pretty obvious. In a CPS system, making a tail call is as simple as calling a function and passing in the continuation you got, rather than generating your own. Which is about as dead simple as you can get, unless your code generation system loses the passed-in continuation, in which case you've got bigger problems. In pseudocode, a function making a tail call that looks like:

sub a (int foo) {
  // Do some stuff
  return b(foo + 1);

gets turned into

sub a (int foo, continuation hidden_continuation_thingie) {
  // Do some stuff
  b(foo + 1, hidden_continuation_thingie);

Since function calls in a CPS system are just gotos (and remember, we're working at the implementation/machine level here--gotos are generally necessary, normal, and not particularly evil) there's no need to clean up a's state before making the call, as the GC system will clean up after it soon enough.

Without CPS, it'd look rather messy, and a plain source transform won't do it (which is another nice thing about CPS--while there isn't really a source transform before compiling, there could be) so it'd look rather confusing and I'm not going to try and sketch it out. (Besides, I've already done that in the tail call entry) With CPS, well... tail calls are remarkably simple and elegant. And, while simple and elegant doesn't necessarily transform to fast (in fact, it often transforms to slow, as the complex messy stuff generally runs faster) in a language where continuations are a requirement it falls out with no extra cost, something that I always like, being something of a speed fiend. In fact, with a CPS system in place, doing tail calls makes things faster, which is something I definitely like.

Posted by Dan at July 1, 2003 03:36 PM | TrackBack (0)