call-with-current-continuation - state saving conc

Question

After reading The Seasoned Schemer I felt I understood call/cc properly. But, after seeing some WOW tricks with call/cc I found I was wrong.

(define cc 0)
(define (f)
  (call/cc (lambda (k)
             (set! cc k)
             3)))

(+ 1 2 4 (f)) ; eval's to 10
(cc 13) ; eval's to 20

That perfectly match my understanding. I think when I reach a call/cc call I am just saving the program state. and calling the function next to it with a function. If that function (k) is called from somewhere than I just replacing the entire (call/cc ...) stuff with the parameter given to it. The above program seems to worked that way too

---

But,

(define (itr lst)
  (define (state k)
    (for-each (lambda (item)
                (call/cc (lambda (h)
                           (set! state h)
                           (k item))))
              lst)
    (k 'done))

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

(define (next)
  (itr (range 2)))

Calling next 3 times produces 0, 1 and 'done. That means when state used the function k given by generator it didn't restore the state of the program. I just showed you I tried to understand it.

---

So, how does call/cc actually work?

Answer 1

With Continuation Passing Style (without call/cc)

It may be easier to understand this example if you implement a version that uses explicit continuation passing style rather than call/cc first. In this case, let's start with a continuation passing version of map:

(define (kmap fn list k)
  (if (null? list)
      (k list)
      (fn (car list)
          (lambda (head)
            (kmap fn
                  (cdr list)
                  (lambda (tail)
                    (k (cons head tail))))))))

(define (identity x) x)

(kmap (lambda (x k) (k (+ 1 x))) '(1 2 3 4) identity)
;=> (2 3 4 5)

If you're not familiar with continuation passing style, this may be a bit to wrap your head around, but it's not too too hard. Remember that kmap and fn each take an additional parameter at the end that should be called with "the result". So when we call fn with (car list), we also pass it a procedure (lambda (head) ...) that's responsible for taking care of the rest of the mapping for us. The rest of the mapping is defined in terms of kmap again. Each call to kmap takes a final continuation that expects to receive the list that results from mapping fn over the list.

Now, since we can see how a mapping can be implemented with continuation passing style, we can write an iterator generation procedure using it. The procedure iterator takes a list and returns a procedure that we can call to get each element of list.

(define (iterator list)
  (define (next k)
    (kmap (lambda (item more-next)
            (set! next more-next)
            (k item))
          list
          (lambda (results)
            (k 'done))))
  (lambda ()
    (next identity)))

> (define get (iterator '(1 2)))
> (get)
1
> (get)
2
> (get)
done
> (get)
done

> (define get (iterator '(a b c)))
> (get)
a
> (get)
b
> (get)
c
> (get)
done
> (get)
done

The trick here is that we define a local procedure next. It calls kmap with a procedure that redfines next when each element of list is processed to be the procedure that will process the remaining part of list. After redefining next, it calls k with the element. The final continuation passed to kmap actually ignores the results passed to it, and just calls k with the symbol done. What we return from iterator is not the value of next, but a procedure that calls next with the continuation identity. The indirection here means that we always call the latest value of next with identity. Passing identity as the continuation means that we just get the list element back.

With call/cc

Now that we see how can we do this without call/cc, we're better equipped to see how we can use call/cc to do it. Recall the definition from the question:

(define (itr lst)
  (define (state k)
    (for-each (lambda (item)
                (call/cc (lambda (h)
                           (set! state h)
                           (k item))))
              lst)
    (k 'done))

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

  generator)                            

Returning the generator

First note that

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

  generator

can be simplified to

(lambda () (call/cc (lambda (k) (state k))))

and that's just about what we did in our implementation. When you're calling this from the REPL, all that the k wants to do is get the value and return it (and print it). In our version, we approximate that by simply returning it unchanged. That is, we use identity, and we used the name next instead of state. So

(lambda () (call/cc (lambda (k) (state k))))

is just like

(lambda () (next identity))

The state (or next) procedure

The rest of it

  (define (state k)
    (for-each (lambda (item)
                (call/cc (lambda (h)
                           (set! state h)
                           (k item))))
              lst)
    (k 'done))

is very similar to what we did, too. Instead of using kmap and a fn that takes two arguments (the item and the continuation), we use for-each which takes a procedure of a single argument (the item) and inside that procedure, we use call/cc to grab the continuation. So

(for-each
  (lambda (item)
    (call/cc (lambda (h)
               ...

is just like

(kmap (lambda (item h)
        ...

for-each doesn't need a final continuation argument, so we can't pass the result-ignoring (lambda () (k 'done)). Instead, we just call (k 'done) after the for-each call. That is,

(for-each fn list)
(k 'done)

is just like

(kmap fn
      list
      (lambda (result)
        (k 'done)))

Saving program state

In both of these implementations, you're "saving the program state" in some sense. The important state that you're saving is the one that will continue iterating over the list.

Answer 2

Your suspicion that something is wrong is correct. The code is totally broken, and this is obvious from the fact that the generator fails to capture a new continuation for the mainline program whenever it is invoked to call the item. Or rather, it fumbles and throws that continuation away. The result is that the wrong continuation is called on the attempt to get the second item, resulting in an infinite loop.

Firstly, let's correct something from the wording of your question. Calling next doesn't yield items; calling next yields the generator function. The way next is supposed to be used is exemplified like this:

(let ((g (next)))
  (list (g) (g) (g)))  ;; should return (0 1 done)

But, in fact it cannot work. Let's examine it:

(define (itr lst)
  (define (state k)
    (for-each (lambda (item)
                (call/cc (lambda (h)
                           (set! state h)
                           (k item))))
              lst)
    (k 'done))

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

(define (next)
  (itr (range 2)))

Let's trace through what is happening.

The setup: When (next) is called, the expression (iter (range 2)) returns generator, a closure captured in an environment where the itr, lst and state variables are bound.

The first iteration: The first call to the generator returned by next therefore invokes generator. Now generator captures its own continuation, which appears as k in the lambda, and passes it to state. So then state runs, and has generator's continuation bound to k. It enters into the first iteration, and saves its own state by replacing itself with a new continuation: (set! state h). At this point, the previous binding of state to the define-d function is overwritten; state is now a continuation function to resume the for-each. The next step is to yield the item back to the k continuation, which brings us back to generator which returns the item. Great, so that's how the first item appears out of the first call to (next).

The second iteration: From here on, things go wrong. The second call to the generator that was returned by next again, captures a continuation again and invokes state which is now the continuation of the generating co-routine. The generator passes its own continuation into state. But state is no longer the function that was define-d by itr! And so the newly captured continuation in generator does not connect with the k parameter that is in the lexical scope of the for-each. When (k item) is called to yield the second item, this k still refers to the original k binding which holds the originally captured continuation in the first call to generator. This is analogous to a backwards goto and results in non-terminating behavior.

Here is how we can fix it:

(define (itr lst)
  (define yield '()) ;; forward definition (could use let for this).

  (define (state)    ;; k parameter is gone
    (for-each (lambda (item)
                (call/cc (lambda (h)
                           (set! state h)
                           (yield item))))  ;; call yield, not k
              lst)
    (yield 'done))  ;; yield, not k.

  (define (generator)
    (call/cc (lambda (self) 
               (set! yield self) ;; save new escape on each call
               (state))))
  generator)

;; test
(let ((g (itr (range 2))) ;; let's eliminate the "next" wrapper
  (display (list (g) (g) (g))))

The output is (0 1 done).