How does this Scheme list iterator use call-with-current-continuation?

Question

I'm trying to read this code:

(define list-iter
  (lambda (a-list)
    (define iter
      (lambda ()
        (call-with-current-continuation control-state)))
    (define control-state
      (lambda (return)
        (for-each
          (lambda (element)
            (set! return (call-with-current-continuation
                           (lambda (resume-here)
                             (set! control-state resume-here)
                             (return element)))))
          a-list)
        (return 'list-ended)))
    iter))

Can anyone explain how call-with-current-continuation works in this example?

Thanks

Duplicate of probably a zillion other "what is call/cc" questions on SO. The most canonical and apparently-helpful one I could find: http://stackoverflow.com/questions/612761/what-is-call-cc. — amalloy, Apr 12 '11 at 03:19
I figured this specific example, using a `yield`-like pattern, was useful enough to stand on its own. Maybe it should be retitled, though. — acfoltzer, Apr 12 '11 at 03:23

score 3 · Answer 1 · answered Apr 12 '11 at 03:17

The essence of call-with-concurrent-continuation, or call/cc for short, is the ability to grab checkpoints, or continuations, during the execution of a program. Then, you can go back to those checkpoints by applying them like functions.

Here's a simple example where the continuation isn't used:

> (call/cc (lambda (k) (+ 2 3)))
5

If you don't use the continuation, it's hard to tell the difference. Here's a few where we actually use it:

> (call/cc (lambda (k) (+ 2 (k 3))))
3
> (+ 4 (call/cc (lambda (k) (+ 2 3))))
9
> (+ 4 (call/cc (lambda (k) (+ 2 (k 3)))))
7

When the continuation is invoked, control flow jumps back to where the continuation was grabbed by call/cc. Think of the call/cc expression as a hole that gets filled by whatever gets passed to k.

list-iter is a substantially more complex use of call/cc, and might be a difficult place to begin using it. First, here's an example usage:

> (define i (list-iter '(a b c)))
> (i)
a
> (i)
b
> (i)
c
> (i)
list-ended
> (i)
list-ended

Here's a sketch of what's happening:

list-iter returns a procedure of no arguments i.
When i is invoked, we grab a continuation immediately and pass it to control-state. When that continuation, bound to return, is invoked, we'll immediately return to whoever invoked i.
For each element in the list, we grab a new continuation and overwrite the definition of control-state with that new continuation, meaning that we'll resume from there the next time step 2 comes along.
After setting up control-state for the next time through, we pass the current element of the list back to the return continuation, yielding an element of the list.
When i is invoked again, repeat from step 2 until the for-each has done its work for the whole list.
Invoke the return continuation with 'list-ended. Since control-state isn't updated, it will keep returning 'list-ended every time i is invoked.

As I said, this is a fairly complex use of call/cc, but I hope this is enough to get through this example. For a gentler introduction to continuations, I'd recommend picking up The Seasoned Schemer.

score 0 · Answer 2 · edited Jun 27 '15 at 15:46

This is essentially:

(define (consume)
  (write (call/cc control)))

(define (control ret)
   (set! ret (call/cc (lambda (resume)
                        (set! control resume)
                        (ret 1))))
   (set! ret (call/cc (lambda (resume)
                        (set! control resume)
                        (ret 2))))
   (set! ret (call/cc (lambda (resume)
                        (set! control resume)
                        (ret 3)))))

(consume)
(consume)
(consume)

Hope it is easier to understand.

score 0 · Answer 3 · answered Apr 12 '11 at 03:22

Basically it takes a function f as its parameter, and applies f to the current context/state of the program.

From wikipedia:
(define (f return)
(return 2)
3)

(display (f (lambda (x) x))) ; displays 3

(display (call-with-current-continuation f)) ; displays 2

So basically when f is called without current-continuation (cc), the function is applied to 2, and then returns 3. When using current-continuation, the parameter is applied to 2, which forces the program to jump to the point where the current-continuation was called, and thus returns 2. It can be used to generate returns, or to suspend execution flow.

If you know C, think about it like this: in C, you can take a pointer to a function. You also have a return mechanism. Suppose the return took a parameter of the same type the function takes. Suppose you could take its address and store that address in a variable or pass it as a parameter, and allow functions to return for you. It can be used to mimic throw/catch, or as a mechanism for coroutines.

How does this Scheme list iterator use call-with-current-continuation?

3 Answers3