Call-with-current-continuation

10 views
Skip to first unread message

the.brown....@gmail.com

unread,
Oct 21, 2008, 3:53:37 AM10/21/08
to
Hello,

I have just started learning scheme using and got pretty confused when
I reached call-with-current-continuation.

After reading up on Wikipedia (http://en.wikipedia.org/wiki/Call-with-
current-continuation) I think I've got some idea of how what call/cc
is. But I'm still a bit confused by the example given:

1 ;; [LISTOF X] -> ( -> X u 'you-fell-off-the-end)
2 (define (generate-one-element-at-a-time lst)
3 (define (generator)
4 (call/cc control-state))
5
6 (define (control-state return)
7 (for-each
8 (lambda (element)
9 (set! return
10 (call/cc
11 (lambda (resume-here)
12 (set! control-state resume-here)
13 (return element)))))
14 lst)
15 (return 'you-fell-off-the-end))
16
17 generator)


Basically, what's confusing me is line 9 - why is "return" getting
set! at this point? And how can it be? Won't the continuation jump out
of the current context so it no longer continues?

Help?

BD

leppie

unread,
Oct 21, 2008, 5:32:41 AM10/21/08
to
On Oct 21, 9:53 am, the.brown.dragon.b...@gmail.com wrote:
> Basically, what's confusing me is line 9 - why is "return" getting
> set! at this point? And how can it be? Won't the continuation jump out
> of the current context so it no longer continues?

You calling 'return' and not the continuation. Unless you call
'resume-here', the procedure will always exit, and set! 'return'.

Cheers

leppie

PS: Continuations confuse the crap out of me. For a beginner I would
not worry about it too much, there are much nicer things to learn :)

the.brown....@gmail.com

unread,
Oct 21, 2008, 5:52:52 AM10/21/08
to

"return" from (define (control-state return)) _is_ the continuation -
or I'm *totally* confused! :-)

cheers,
BD

leppie

unread,
Oct 21, 2008, 6:08:34 AM10/21/08
to
On Oct 21, 11:52 am, the.brown.dragon.b...@gmail.com wrote:
> "return" from (define (control-state return)) _is_ the continuation -
> or I'm *totally* confused! :-)

Ah, I see what you mean! Now I am confused too :o)

Abdulaziz Ghuloum

unread,
Oct 21, 2008, 6:47:40 AM10/21/08
to
the.brown....@gmail.com wrote:
> Hello,
>
> I have just started learning scheme using and got pretty confused when
> I reached call-with-current-continuation.
>
> After reading up on Wikipedia (http://en.wikipedia.org/wiki/Call-with-
> current-continuation) I think I've got some idea of how what call/cc
> is. But I'm still a bit confused by the example given:

The example is confusing, a little.

Start by rewriting the code so that the lambdas are explicit,
and copy propagate the two lambdas to their single use cites:


(define (generate-one-element-at-a-time lst)
(define (generator)
(call/cc control-state))
(define (control-state return)
(for-each
(lambda (element)
(set! return
(call/cc
(lambda (resume-here)
(set! control-state resume-here)
(return element)))))
lst)
(return 'you-fell-off-the-end))
generator)
==>
(define (generate-one-element-at-a-time lst)
(define control-state #f)
(lambda ()
(call/cc
(lambda (return)
(for-each
(lambda (element)
(set! return
(call/cc
(lambda (resume-here)
(set! control-state resume-here)
(return element)))))
lst)
(return 'you-fell-off-the-end)))))

Now try a simple value for lst like '(1 2 3):

(let ()
(define control-state #f)
(lambda ()
(call/cc
(lambda (return)
(for-each
(lambda (element)
(set! return
(call/cc
(lambda (resume-here)
(set! control-state resume-here)
(return element)))))
'(1 2 3))
(return 'you-fell-off-the-end)))))

Then expand the for-each:

(let ()
(define control-state #f)
(lambda ()
(call/cc
(lambda (return)
(set! return
(call/cc
(lambda (resume-here1)
(set! control-state resume-here1)
(return 1))))) ;;; (1)
(set! return
(call/cc
(lambda (resume-here2)
(set! control-state resume-here2)
(return 2)))) ;;; (2)
(set! return
(call/cc
(lambda (resume-here3)
(set! control-state resume-here3)
(return 3)))) ;;; (3)
(return 'you-fell-off-the-end))))


At point (1), we capture a continuation that, when invokes with
a value, will set! return to that value, the continue to the next
block. We capture that continuation and set it to control-state
and return 1 to the original caller (the top-most return).

If calling (return 1) at the line marked (1) returns a continuation,
call it k1, then we have (set! return k1), and control proceeds up
to line (2), when the control-state variable is updated with a new
continuation, 2 is returned, waiting for a new continuation k2,
which updates the "return" variable.

And so on and so forth until you fall off the end.

Stare at it for a while. See if it says something to you. :-)

Aziz,,,

the.brown....@gmail.com

unread,
Oct 21, 2008, 7:54:29 AM10/21/08
to
On Oct 21, 3:47 pm, Abdulaziz Ghuloum <aghul...@cee.ess.indiana.edu>
wrote:

My head is spinning :)

I'm still not entirely clear - what is wrong with this version?

1 (let ()
2 (define control-state #f)
3 (lambda ()
4 (call/cc
5 (lambda (return)
6 (call/cc
7 (lambda (resume-here1)
8 (set! control-state resume-here1)
9 (return 1)))) ;;; (1)
10 (call/cc
11 (lambda (resume-here2)
12 (set! control-state resume-here2)
13 (return 2))) ;;; (2)
14 (call/cc
15 (lambda (resume-here3)
16 (set! control-state resume-here3)
17 (return 3))) ;;; (3)
18 (return 'you-fell-off-the-end))))

cheers
bd

Abdulaziz Ghuloum

unread,
Oct 21, 2008, 10:48:33 AM10/21/08
to
the.brown....@gmail.com wrote:

> I'm still not entirely clear - what is wrong with this version?

It's not wrong. It's just different. The difference happens when
you capture and re-invoke a generator, say, after it returns 1 from
the sequence (1 2 3). So, you get 1, you "capture" the generator,
invoke it and get 2, then you re-invoke the captured generator.
Should you get the next element, 3, or should it restart and give
you 2? This is the difference.

the.brown....@gmail.com

unread,
Oct 21, 2008, 12:46:40 PM10/21/08
to
On Oct 21, 7:48 pm, Abdulaziz Ghuloum <aghul...@cee.ess.indiana.edu>
wrote:

I think I get what you mean but I'm unable to actually try it out. How
would I go about "capturing" the generator?

cheers,
bd

Jussi Piitulainen

unread,
Oct 21, 2008, 2:10:51 PM10/21/08
to
Abdulaziz Ghuloum writes:

> The example is confusing, a little.
>
> Start by rewriting the code so that the lambdas are explicit,
> and copy propagate the two lambdas to their single use cites:
>
>
> (define (generate-one-element-at-a-time lst)

...
> ==>
> (define (generate-one-element-at-a-time lst)
...

Does something go wrong here, or is there something wrong in the
following exercise? In the exercise, the original version works as I
expect, and the new version spins at the first element. See below.

First, I take the code above, and rename the two versions:

(define (generate-one-element-at-a-time.org lst)


(define (generator)
(call/cc control-state))
(define (control-state return)
(for-each
(lambda (element)
(set! return
(call/cc
(lambda (resume-here)
(set! control-state resume-here)
(return element)))))
lst)
(return 'you-fell-off-the-end))
generator)
;==>

(define (generate-one-element-at-a-time.new lst)


(define control-state #f)
(lambda ()
(call/cc
(lambda (return)
(for-each
(lambda (element)
(set! return
(call/cc
(lambda (resume-here)
(set! control-state resume-here)
(return element)))))
lst)
(return 'you-fell-off-the-end)))))

Then I run them both:

(define elements '(d a r e))

(define org
(let ((p (generate-one-element-at-a-time.org elements)))
(list (p) (p) (p) (p) (p) (p))))

(define new
(let ((p (generate-one-element-at-a-time.new elements)))
(list (p) (p) (p) (p) (p) (p))))

Welcome to MzScheme version 202, Copyright (c) 1995-2002 PLT, load all
the code above, and the results are:

Value of org: (d a r e you-fell-off-the-end you-fell-off-the-end)
Value of new: (d d d d d d)

All cut-and-pasted as far as possible.

the.brown....@gmail.com

unread,
Oct 21, 2008, 3:12:37 PM10/21/08
to
On Oct 21, 11:10 pm, Jussi Piitulainen <jpiit...@ling.helsinki.fi>
wrote:

From what I understand of the code, the second version assigns the
continuation to "control-state" but does nothing with it. So every
call simply starts from the beginning, returning the (expected) first
element.

Jussi Piitulainen

unread,
Oct 21, 2008, 4:46:30 PM10/21/08
to
the.brown....@gmail.com writes:

Seems so to me, now that I've stared at the code for some time. In the
first version, the returned generator passes control-state to call/cc,
which then calls it, and during that call it gets re-assigned, so that
a different control-state is called next time; in the second version,
where is control-state ever called?

I think Abdulaziz meant them to be the same, but when I tried to use
them for something, I noticed the difference.

Abdulaziz Ghuloum

unread,
Oct 21, 2008, 11:25:09 PM10/21/08
to
Jussi Piitulainen wrote:

> I think Abdulaziz meant them to be the same, but when I tried to use
> them for something, I noticed the difference.

Obviously, I completely messed this up. Sorry. Mostly, I was
confused by the interface to this generator (e.g., how would one
use it). I thought it required a coroutine or something more
involved to use it than to simply call it. But now I'm confused
for why this needs call/cc at all. Why would one not just do:

(define (generate-one-element-at-a-time ls)
(lambda ()
(if (null? ls)
'last-element
(let ([a (car ls)])
(set! ls (cdr ls))
a))))

Aziz,,,

the.brown....@gmail.com

unread,
Oct 22, 2008, 2:31:44 AM10/22/08
to
On Oct 22, 8:25 am, Abdulaziz Ghuloum <aghul...@cee.ess.indiana.edu>
wrote:

I'm just going to conclude that the example was poorly written and
continue for now.

Thanks for your help!

cheers
bd

Michele Simionato

unread,
Oct 22, 2008, 3:28:45 AM10/22/08
to
On Oct 22, 8:31 am, the.brown.dragon.b...@gmail.com wrote:
> I'm just going to conclude that the example was poorly written and
> continue for now.

You may be interested in this implementation of Python generators
which more or less
does what you mean:

(define-syntax save/cc!
(syntax-rules ()
((_ name body ...)
(call/cc (lambda (cont) (set! name cont) body ...)))))

(define (generator next)
(define exit #f)
(lambda ()
(save/cc! exit ; reassigned the same 'exit' at each iteration
(next (lambda (v) (save/cc! next (exit v))))
(error 'generator "stop-iteration")); exits here
))

(define (list->generator lst)
(generator
(lambda (yield) (for-each yield lst))))

(define g (list->generator '(1 2 3)))

(list (g) (g) (g)); => (1 2 3)

(g) ;=> error stop-iteration

If you don't like the error, you can return a sentinel value to mean
generator termination.

Jussi Piitulainen

unread,
Oct 22, 2008, 8:33:06 AM10/22/08
to
Michele Simionato writes:
> You may be interested in this implementation of Python generators
> which more or less does what you mean:

Hey, thanks, this is cool. It actually does what I tried to do with
that other thing upthread.

> (define-syntax save/cc!
> (syntax-rules ()
> ((_ name body ...)
> (call/cc (lambda (cont) (set! name cont) body ...)))))
>
> (define (generator next)
> (define exit #f)
> (lambda ()
> (save/cc! exit ; reassigned the same 'exit' at each iteration
> (next (lambda (v) (save/cc! next (exit v))))
> (error 'generator "stop-iteration")); exits here
> ))

I modified this so that the "yield" procedure can receive more than
one value at each step, the change marked *** below. (I also added an
optional "then" to be called after the elements are generated.)

(define generator
(case-lambda ; I don't know how standard case-lambda is
((next then)


(define exit #f)
(lambda ()
(save/cc! exit ; reassigned the same 'exit' at each iteration

(next (lambda vs (save/cc! next (apply exit vs)))) ;***
(then)))); exits here
((next)
(generator next (lambda () (error 'generator "stop-iteration"))))))

> (define (list->generator lst)
> (generator
> (lambda (yield) (for-each yield lst))))

There are several ways to iterate over combinations of values. I had
lying around a procedure (select proc elements) that passes to proc
each triple of prefix-element-suffix of elements. I had a procedure
(permute proc elements) that passes to proc each permutation of
elements, using select. (for-each proc list1 list2) passes proc all
pairs of elements in matching positions. Nested for-each calls can
pass a proc each pair in the cartesian product of lists.

To illustrate, a simple procedure (threes proc elements) below passes
proc each triple of adjacent elements.

Now all such calls can be, it seems, turned into generators.

(define (threes p things)
(do ((things things (cdr things))
(n (length things) (- n 1)))
((< n 3))
(p (car things) (cadr things) (caddr things))))

(define g (generator
(lambda (yield)
(threes yield (string->list "daring")))))

(call-with-values g string) => "dar"
(call-with-values g string) => "ari"
(call-with-values g string) => "rin"
(call-with-values g string) => "ing"

A laboratory case:

(define g (generator (lambda (yield) (yield 'dear 'dare 'read))))
(call-with-values g list) => (dear dare read)

Another:

(define g (generator (lambda (yield) (yield) (yield))))
(call-with-values g string) => ""
(call-with-values g string) => ""


> (define g (list->generator '(1 2 3)))
>
> (list (g) (g) (g)); => (1 2 3)
>
> (g) ;=> error stop-iteration
>
> If you don't like the error, you can return a sentinel value to mean
> generator termination.

(define g (generator
(lambda (yield)
(threes yield (string->list "daring")))
(lambda ()
(values #\- #\- #-))))

Is there something I should read?

Jussi Piitulainen

unread,
Oct 22, 2008, 8:41:39 AM10/22/08
to
Abdulaziz Ghuloum writes:
> Jussi Piitulainen wrote:
>> I think Abdulaziz meant them to be the same, but when I tried to
>> use them for something, I noticed the difference.
>
> Obviously, I completely messed this up. Sorry. Mostly, I was

Ok, thanks. No problem.

> But now I'm confused for why this needs call/cc at all. Why would
> one not just do:
>
> (define (generate-one-element-at-a-time ls)
> (lambda ()
> (if (null? ls)
> 'last-element
> (let ([a (car ls)])
> (set! ls (cdr ls))
> a))))

So it falls flat. But perhaps the for-each call inside the original
generate-one-element-at-a-time was struggling to get out, in the way
that becomes so much more apparent in Michele Simionato's interesting
post. It did what I wanted, at least.

Grant Rettke

unread,
Oct 24, 2008, 2:45:01 PM10/24/08
to
On Oct 21, 4:32 am, leppie <xacc....@gmail.com> wrote:
> PS: Continuations confuse the crap out of me. For a beginner I would
> not worry about it too much, there are much nicer things to learn :)

Leppie, you implemented a R6RS interpreter and still you say this, is
there hope for the rest of us?! :)

Aaron W. Hsu

unread,
Oct 24, 2008, 7:12:47 PM10/24/08
to
Grant Rettke <gre...@gmail.com> writes:

Implementing continuations is probably much harder than using them. I
know that I am able to use continuations fairly easily if I take a little
time to think about the problem.

Aaron Hsu

--
+++++++++++++++ ((lambda (x) (x x)) (lambda (x) (x x))) +++++++++++++++
Email: <arc...@sacrideo.us> | WWW: <http://www.sacrideo.us>
Scheme Programming is subtle; subtlety can be hard.
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

jos koot

unread,
Oct 26, 2008, 6:23:29 AM10/26/08
to
18 (define x (generate-one-element-at-a-time '(1 2 3)))
19 (x)

The set! first evaluates the call/cc call at line 10, and stores the
value only after call/cc has returned. But call/cc does not return
yet.
In line 13 it returns an element to the continuation of the call to x
in line 19. So line 19 produces element 1.
However, in line 12 variable control-state is updated such as to
contain a continuation that finishes the assignment of line 9.

20 (x)

So now the assignment of line 9 is completed. The value is that of
(return element) which is the continuation of line 20 as passed to
control-state by procedure generator.
After the assignment of line 9 is completed, for-each does the next
cycle while return points to the continuation of line 20.

You may want to have a look at: http://schemecookbook.org/Cookbook/CoRoutines

Jos

Jens Axel Soegaard

unread,
Oct 26, 2008, 1:13:58 PM10/26/08
to
Grant Rettke skrev:

I'd say yes - they are easier to implement than understand.

--
Jens Axel Søgaard

leppie

unread,
Oct 28, 2008, 6:03:21 AM10/28/08
to
On Oct 26, 7:13 pm, Jens Axel Soegaard

I am just now implementing them (full re-invokable continuations), but
both implementing and understanding is hard, but I have had some good
help from #scheme on freenode.

Hopefully within the next few weeks I will have something working :)

Stay tuned!

leppie

unread,
Oct 28, 2008, 11:33:35 AM10/28/08
to
On Oct 26, 7:13 pm, Jens Axel Soegaard
<findrealaddresswithgoo...@soegaard.net> wrote:

I am busy implementing them (full re-invokable continuations) for
IronScheme at the moment.

Hopefully I will have something working in a few weeks :)

Stay tuned

leppie

leppie

unread,
Oct 28, 2008, 11:35:49 AM10/28/08
to

Full continuations are coming soon to IronScheme :)

leppie

PS: this is a duplicate message as my replies do not seem to come
through...

Grant Rettke

unread,
Oct 28, 2008, 11:45:40 PM10/28/08
to
On Oct 28, 10:33 am, leppie <xacc....@gmail.com> wrote:
> I am busy implementing them (full re-invokable continuations) for
> IronScheme at the moment.

Awesome!

the.brown....@gmail.com

unread,
Oct 29, 2008, 2:26:27 AM10/29/08
to

Thanks Jos. I re-read your message 3 times and I think I get it.

So if I understand correctly - a continuation (cont value) returns the
next "continuation context". In the example, this is saved in the
"return" variable and used in the next iteration.

cheers,
BD

jos koot

unread,
Oct 29, 2008, 6:34:29 AM10/29/08
to

Correct, Jos

Reply all
Reply to author
Forward
0 new messages