Call-with-current-continuation
the.brown....@gmail.com
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
> 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
"return" from (define (control-state return)) _is_ the continuation -
or I'm *totally* confused! :-)
cheers,
BD
leppie
> "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
> 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
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
> 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
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
> 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
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
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
> 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
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
> 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
> 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
> 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
> 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
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
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
I'd say yes - they are easier to implement than understand.
--
Jens Axel Søgaard
leppie
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
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
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
> I am busy implementing them (full re-invokable continuations) for
> IronScheme at the moment.
Awesome!
the.brown....@gmail.com
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
Correct, Jos