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?
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.
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)
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))
state
(or next
) procedureThe 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)))
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.
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)
.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With