Continuations - part 2

Back to my attempt to explain continuations.

What is a continuation? The short answer is "What the program should do next". Another way of putting it would be "Everything the program hasn't done yet, wrapped up in something that looks sort-of like a function". Now I'm going to make the possibly arrogant assumption that as that wasn't sufficient explaination for me, that wasn't sufficient here.

Let's go back and reconsider an LCO example, this time we want to write a sigma function: takes a non-empty list of numbers and returns the sum of the list.

; (sigma '(1 2 3 4)) -> 10
(define (sigma lst)
  (if (null? (cdr lst))
      (car lst)
      (+ (car lst) (sigma (cdr list)))))

Now the astute reader will be wondering why I've defined sigma like this, associating to the right, rather than to the left (which would have been simpler). The reason for this is that this function cannot be trivially converted into the accumulator form we used in the previous LCO example. More importantly, there are a number of recursive functions which are easier to define associating to the right than the left (I recommend trying to use append in place of + to define map in this manner). Now it would be nice to be able to manage this sort of function in constant stack, and this is a nice simple example to demonstrate how we can do exactly this. In case any readers are wondering what I mean by associating left vs. right, I suggest you compare the above to the left-associative version below and consider the order in which the elements of the list are combined.

(1 + (2 + (3 + 4))) - right assoc
(((1 + 2) + 3) + 4) - left assoc

; Left associative
(define (sigma lst)
  (letrec ((sigma-iter
    (lambda (lst accum)
       (if (null? lst)
           accum
           (sigma-iter (cdr lst) (+ accum (car lst)))))))
  (sigma-iter (cdr lst) (car lst))))

(Note we could have defined sigma-iter the same way we did earlier, as a global with (define...), however it really is a helper function, and so is better defined locally to sigma. --- besides, it also gives me a chance to introduce lambda, which we will be using later)

The secret to converting the right-associative version into LCO is to recognise that the last thing we want to do before returning is call sigma on the tail of the list. Now this looks difficult, as the last thing we need to do is the addition. Still, I'm a great believer in wishful thinking, so I'm going to pretend I have an function that will take the result of the recursive call and finish off everything I was supposed to do next for me. Then I can pass that into the next call to sigma and have it finish for me.

(define (sigma lst finisher)
  (if (null? (cdr lst))
      (finisher (car lst))
      (finisher (sigma (cdr lst) finishing-function))))

Opps, now we have a call to 'finisher' in the road. Still that's ok, we can just pretend that we have a new finishing-function each time that will both handle the addition for this call, and the call to the finisher we were passed.

(define (sigma lst finisher)
  (if (null? (cdr lst))
      (finisher (car lst))
      (sigma (cdr lst) new-finishing-function)))

Now this is looking better, all we have to do is work out how to define an appropriate finishing function and we're done. Before we do that however it is worth noting (as most of you will have noticed by now anyway) that the new-finishing-function's definition "finish off everything I want to do next" is just a rephrasing of the definition I gave for a continuation at the start.

Lets compare the non-tail-recursive call to the continuation based tail-recursive call:

; non-tail-recursive
(+ (car lst) (sigma (cdr lst)))
; tail-recursive
(sigma (cdr lst) continuation)

Remember the definition of the continuation is that it will be receiving the result of the recursive call to sigma as a parameter so lets call that x and substitute into the non-tail-recursive version:

; let x <- (sigma (cdr lst))
(+ (car lst) x)

This will calcuate the result of our call, but we have one thing left to do, we have to return the result to our caller. However our caller has finished (its call to us was a tail-call remember), and the destination of our result was passed as a continuation. So we don't actually return as much as make a tail-call to the continuation (note this is a major reason why LCO is so useful, if we didn't have LCO our stack frame would be leaked, but with LCO there is no leak).

; pass (+ (car lst) x) to the continuation.
(continuation (+ (car lst) x))

So what we need is to define a small function that can capture this idea and pass this into the recursive call to sigma.

; Scheme
(lambda (x) (continuation (+ (car lst) x)))

# Python - just in case it's useful understanding the closure above.
# NOTE: As python dosn't provide LCO this *will* leak stack.
lambda x: continuation(lst[0] + x)

Now put the pieces together and we're almost there:

(define (sigma lst continuation)
  (if (null? (cdr lst))
      (continuation (car lst))
      (sigma (cdr lst)
	     (lambda (x) (continuation (+ (car lst) x))))))

The next step is to restore the original signature, and make this CPS version a helper function (along the way we rename continuation to k, it's shorter ;).

(define (sigma-helper lst k)
  (if (null? (cdr lst))
      (k (car lst))
      (sigma (cdr lst) (lambda (x) (k (+ (car lst) x))))))

(define (sigma lst)
  (sigma-helper lst initial-continuation))

Final step.... what do we want as the initial-continuation? Well it will be passed the result of the outer sigma, and what we want is the result of the outer sigma.... sounds like a job for the most trivial function you can think of; also known as the I combinator, let me introduce id()

(define (id x) x)

(define sigma lst)
  (sigma-helper lst id))

And we're done. Lets step back and take a look at what we've done. We have taken a non-tail-recursive function and split into two pieces seperated by a tail-call. We execute the first half, and pass the second half as a parameter, a continuation, to the tail-call. It is worth noting three points:

• There is nothing special about the precise point we decided to split the function, at any point we could have wrapped the rest of the function in a continuation and passed it into another function, we'll come back to this when we discuss call-with-current-continuation later
• The continuation ends up being an ordinary function. We can save this function and call it as many times as we like; from other places than inside the sigma call. After all, once we have it, it's just a function. This dosn't make much sense with sigma, but other algorithms do make use of this trick. Again, we will come back to this with call/cc.
• The sigma-helper function never returns! In every case the helper function substitutes return with a call to its continuation parameter. For this reason the sort of continuation used in this example is called a return-continuation. Every return in every function can be treated as a call to an implicit return-continuation. There are other uses for continuations, return-continuations are just the easiest to grasp, hence the subject of this post. Again, I'll come back to other uses when I discuss call/cc.

This technique where you pass return-continuations around instead of returning normally is called CPS. It is a powerful approach to programming that is a common transformation, especially in compilers for functional languages.

I would also appreciate any feedback on this introduction, both positive and suggestions for improvement. Hopefully I'll have time to do a worked example and a discussion on call/cc soon.