Rotating Header Image

November 27th, 2006:


Here I am again, delving into continuations for the fun of it. I am certain that by the time I have worked it out completely, I will have seen my error and my entire objection at the beginning of this entry will be flawed. But one never knows, besides, hopefully someone might get something useful out of this, besides me just rubberducking.

But let’s start at the beginning. When one learns about call-with-current-continuation, one of the first thing one wishes to do is actually save the continuation to later use it. A simple pattern for this is:

(define k (call/cc (lambda (k) k)))

Simple, no? Now it is very easy to go back there and to save a value into k, all you have to do is call it (k 1). For those that do not understand what continuations do, let’s look under the hood briefly (where I mean, let’s delve into the semantics, implementation details will be spared). A continuation is basically a place that is waiting to be filled by a value. For instance, if you have (+ 1 x), and you want the current continuation of x, you get (+ 1 []) or an expression with one hole to plug a value into, but then turned into a function so you can call it.

Now going back to the above explanation, what happens under the hood?

(define k (call/cc (lambda (k) k)))
=> Call (lambda (k) k) with the hole in:
(define k []) or {\x -> (define k x)]
=> (lambda (k) k) returns this hole, and then call/cc
returns the value returned by it's argument
(define k {\x -> (define k x)})
; Yes I know, but this is the best syntax I can come up with

So if we call it later:
(k 1), we will go back to the return-continuation of
call/cc which is the define statement itself, and end up with
(define k 1)

Now one often introduced idiom that many schemers like to use instead of (call/cc (lambda (k) k)) is (call/cc call/cc), and indeed, in mzscheme it behaves just the same. At first I thought that it should not behave exactly the same, but as I was writing the explanation I figured why it should. Therefore I will detail that here. Unlike last time, I will not try to get the full CPS form of what goes on. So let’s get started:

(define k (call/cc call/cc))
Let's call them cc1 and cc2 to differentiate:
(define k (cc1 cc2))
The hole []1 for cc1 is:
(define k []1) or {\x -> (define k x)}

How does it go:
(define k (cc1 cc2))
=> call cc2 with []{\x -> (define k x)}
=> call {\x -> (define k x)} with []2 or
{\x -> (define k (cc1R x))}
Here I use cc1R as "returning" because by the time we create []2,
cc1 is already called.
This is the crucial aspect which I was missing first, when []2
is created, it's cc1 on the return path (aka already called and
being filled in with return value).
The behaviour of call/cc is that whatever value is returned to it,
it just returns itself.

So what has happened:
(define k []2) where []2 = {\x -> (define k (cc1R x))}
(k 1) => ([]2 1) => (define k (cc1R 1)) => (define k 1)