Call-with-current-continuation

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

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

On Oct 21, 2:32*pm, leppie <xacc....@gmail.com> wrote:
> 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

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

cheers,
BD

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 )

the.brown.dragon.blog@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,,,

On Oct 21, 3:47*pm, Abdulaziz Ghuloum <aghul...@cee.ess.indiana.edu>
wrote:
> the.brown.dragon.b...@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,,,

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

the.brown.dragon.blog@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.

On Oct 21, 7:48*pm, Abdulaziz Ghuloum <aghul...@cee.ess.indiana.edu>
wrote:
> the.brown.dragon.b...@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.

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

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.

On Oct 21, 11:10*pm, Jussi Piitulainen <jpiit...@ling.helsinki.fi>
wrote:
> 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.

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.

the.brown.dragon.blog@gmail.com writes:
> On Oct 21, 11:10*pm, Jussi Piitulainen wrote:
> > 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.
>
> 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.

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.

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,,,

On Oct 22, 8:25*am, Abdulaziz Ghuloum <aghul...@cee.ess.indiana.edu>
wrote:
> 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,,,

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

Thanks for your help!

cheers
bd

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.

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?