call-with-current-continuation - state saving concept

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 redefines 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.