Non-stack-copying call-with-current-continuation?

Non-stack-copying call-with-current-continuation?

[David Kastrup]

Hi,

I am just meddling around with coding and have come up with the
following:

(define-public (find-child music predicate)
  "Find the first node in @var{music} that satisfies @var{predicate}."
  (catch 'music-found
	 (lambda ()
	   (fold-some-music predicate
			    (lambda (music . _) (throw 'music-found music))
			    #f music))
	 (lambda (key music) music)))

Now the problem with that is that it is unhygienic.  If fold-some-music
were to use music-found signals, or if the predicate did, things would
be awkward.  One would need to work with a uniquely generated symbol.
It turns out that the above can be expressed much clearer and cleaner as

(define-public (find-child music predicate)
  "Find the first node in @var{music} that satisfies @var{predicate}."
  (call-with-current-continuation
   (lambda (music-found)
     (fold-some-music predicate
		      (lambda (music . _) (music-found music))
		      #f music))))

at least if I did not make some thinko here.  It is basically the same
code and stack-upwards-only, but hygienic.  Nothing can call the
continuation but what is inside.  Well, of course fold-some-music could
save the closure calling music-found for later.  But it doesn't.

Is there a way to get a call-with-current-continuation that does not
create a stack copy?  It is fine if it fails with an exception if one
still tries calling the continuation after it has already returned.

-- 
David Kastrup

Re: Non-stack-copying call-with-current-continuation?

[Noah Lavine]

If I understand correctly, you only need to call the continuation
once. Is that right?

In that case, I think you could use either catch and throw or prompts.
(And catch and throw are implemented with prompts, so really, you can
just choose how you want to use prompts.)

Noah

On Thu, Mar 1, 2012 at 7:00 PM, David Kastrup <dak@gnu.org> wrote:
>
> Hi,
>
> I am just meddling around with coding and have come up with the
> following:
>
> (define-public (find-child music predicate)
>  "Find the first node in @var{music} that satisfies @var{predicate}."
>  (catch 'music-found
>         (lambda ()
>           (fold-some-music predicate
>                            (lambda (music . _) (throw 'music-found music))
>                            #f music))
>         (lambda (key music) music)))
>
> Now the problem with that is that it is unhygienic.  If fold-some-music
> were to use music-found signals, or if the predicate did, things would
> be awkward.  One would need to work with a uniquely generated symbol.
> It turns out that the above can be expressed much clearer and cleaner as
>
> (define-public (find-child music predicate)
>  "Find the first node in @var{music} that satisfies @var{predicate}."
>  (call-with-current-continuation
>   (lambda (music-found)
>     (fold-some-music predicate
>                      (lambda (music . _) (music-found music))
>                      #f music))))
>
> at least if I did not make some thinko here.  It is basically the same
> code and stack-upwards-only, but hygienic.  Nothing can call the
> continuation but what is inside.  Well, of course fold-some-music could
> save the closure calling music-found for later.  But it doesn't.
>
> Is there a way to get a call-with-current-continuation that does not
> create a stack copy?  It is fine if it fails with an exception if one
> still tries calling the continuation after it has already returned.
>
> --
> David Kastrup
>
>

Re: Non-stack-copying call-with-current-continuation?

[David Kastrup]

Noah Lavine <noah.b.lavine@gmail.com> writes:

> On Thu, Mar 1, 2012 at 7:00 PM, David Kastrup <dak@gnu.org> wrote:
>>
>> Hi,
>>
>> I am just meddling around with coding and have come up with the
>> following:
>>
>> (define-public (find-child music predicate)
>>  "Find the first node in @var{music} that satisfies @var{predicate}."
>>  (catch 'music-found
>>         (lambda ()
>>           (fold-some-music predicate
>>                            (lambda (music . _) (throw 'music-found music))
>>                            #f music))
>>         (lambda (key music) music)))
>>
>> Now the problem with that is that it is unhygienic.  If fold-some-music
>> were to use music-found signals, or if the predicate did, things would
>> be awkward.  One would need to work with a uniquely generated symbol.
>> It turns out that the above can be expressed much clearer and cleaner as
>>
>> (define-public (find-child music predicate)
>>  "Find the first node in @var{music} that satisfies @var{predicate}."
>>  (call-with-current-continuation
>>   (lambda (music-found)
>>     (fold-some-music predicate
>>                      (lambda (music . _) (music-found music))
>>                      #f music))))
>>
>> at least if I did not make some thinko here.  It is basically the same
>> code and stack-upwards-only, but hygienic.  Nothing can call the
>> continuation but what is inside.  Well, of course fold-some-music could
>> save the closure calling music-found for later.  But it doesn't.
>>
>> Is there a way to get a call-with-current-continuation that does not
>> create a stack copy?  It is fine if it fails with an exception if one
>> still tries calling the continuation after it has already returned.
>
> If I understand correctly, you only need to call the continuation
> once. Is that right?
>
> In that case, I think you could use either catch and throw or prompts.

Neither of which are hygienic and also less straightforward.  It is not
like I did not start my posting by giving the catch/throw-based example
and saying what I disliked about it.

-- 
David Kastrup

Re: Non-stack-copying call-with-current-continuation?

[Noah Lavine]

Oh yes, you're right. I'm sorry I missed it.

I believe you can do it hygienically though. With prompts, you can use
(make-prompt-tag) to generate a new, unique tag. With catch and throw,
you could use (gensym) to do the same thing. You first example would
become something like

(define-public (find-child music predicate)
 "Find the first node in @var{music} that satisfies @var{predicate}."
  (let ((music-found-tag (gensym)))
   (catch music-found-tag
          (lambda ()
            (fold-some-music predicate
                             (lambda (music . _) (throw music-found-tag music))
                             #f music))
          (lambda (key music) music)))

Does that work?

Noah


On Thu, Mar 1, 2012 at 7:42 PM, David Kastrup <dak@gnu.org> wrote:
> Noah Lavine <noah.b.lavine@gmail.com> writes:
>
>> On Thu, Mar 1, 2012 at 7:00 PM, David Kastrup <dak@gnu.org> wrote:
>>>
>>> Hi,
>>>
>>> I am just meddling around with coding and have come up with the
>>> following:
>>>
>>> (define-public (find-child music predicate)
>>>  "Find the first node in @var{music} that satisfies @var{predicate}."
>>>  (catch 'music-found
>>>         (lambda ()
>>>           (fold-some-music predicate
>>>                            (lambda (music . _) (throw 'music-found music))
>>>                            #f music))
>>>         (lambda (key music) music)))
>>>
>>> Now the problem with that is that it is unhygienic.  If fold-some-music
>>> were to use music-found signals, or if the predicate did, things would
>>> be awkward.  One would need to work with a uniquely generated symbol.
>>> It turns out that the above can be expressed much clearer and cleaner as
>>>
>>> (define-public (find-child music predicate)
>>>  "Find the first node in @var{music} that satisfies @var{predicate}."
>>>  (call-with-current-continuation
>>>   (lambda (music-found)
>>>     (fold-some-music predicate
>>>                      (lambda (music . _) (music-found music))
>>>                      #f music))))
>>>
>>> at least if I did not make some thinko here.  It is basically the same
>>> code and stack-upwards-only, but hygienic.  Nothing can call the
>>> continuation but what is inside.  Well, of course fold-some-music could
>>> save the closure calling music-found for later.  But it doesn't.
>>>
>>> Is there a way to get a call-with-current-continuation that does not
>>> create a stack copy?  It is fine if it fails with an exception if one
>>> still tries calling the continuation after it has already returned.
>>
>> If I understand correctly, you only need to call the continuation
>> once. Is that right?
>>
>> In that case, I think you could use either catch and throw or prompts.
>
> Neither of which are hygienic and also less straightforward.  It is not
> like I did not start my posting by giving the catch/throw-based example
> and saying what I disliked about it.
>
> --
> David Kastrup
>
>

Re: Non-stack-copying call-with-current-continuation?

[David Kastrup]

Noah Lavine <noah.b.lavine@gmail.com> writes:

> Oh yes, you're right. I'm sorry I missed it.
>
> I believe you can do it hygienically though. With prompts, you can use
> (make-prompt-tag) to generate a new, unique tag. With catch and throw,
> you could use (gensym) to do the same thing. You first example would
> become something like
>
> (define-public (find-child music predicate)
>  "Find the first node in @var{music} that satisfies @var{predicate}."
>   (let ((music-found-tag (gensym)))
>    (catch music-found-tag
>           (lambda ()
>             (fold-some-music predicate
>                              (lambda (music . _) (throw music-found-tag music))
>                              #f music))
>           (lambda (key music) music)))
>
> Does that work?

Sure, but things like gensym and make-prompt-tag (and (list '()) for
creating an eq?-unique object) are artificial hygiene coming at a cost
in symbol table and symbol generation time rather than "lexical"
hygiene.  They need _extra_ work, whereas the
call-with-current-continuation approach needed _less_ work.  Basically I
want something like call-with-single-continuation that will only allow
one return (and any dynwind out counts and should work if it is the
first, so it is not exactly equivalent to using
with-continuation-barrier) and come without the stack-copying cost of
call-with-current-continuation.

Sure, you can do

(define (call-with-single-continuation proc)
  (let ((tag (gensym)))
    (catch tag
	   (proc (lambda x (throw tag x)))
	   (lambda (tag x) (apply values x)))))

Oops.  (apply values ...)?  Does this even work?  Anyway, you get the
drift.  But it is not pretty and it is not primitive.  And its failure
mode when you disobey the "single" contract is an uncaught exception
with a weird symbol.

-- 
David Kastrup

Re: Non-stack-copying call-with-current-continuation?

[Noah Lavine]

Hello,

> Sure, but things like gensym and make-prompt-tag (and (list '()) for
> creating an eq?-unique object) are artificial hygiene coming at a cost
> in symbol table and symbol generation time rather than "lexical"
> hygiene.  They need _extra_ work, whereas the
> call-with-current-continuation approach needed _less_ work.  Basically I
> want something like call-with-single-continuation that will only allow
> one return (and any dynwind out counts and should work if it is the
> first, so it is not exactly equivalent to using
> with-continuation-barrier) and come without the stack-copying cost of
> call-with-current-continuation.

I agree that it's not pretty. We have hygienic macros so we don't have
to use gensym, after all. But I don't know of a better way.

> Sure, you can do
>
> (define (call-with-single-continuation proc)
>  (let ((tag (gensym)))
>    (catch tag
>           (proc (lambda x (throw tag x)))
>           (lambda (tag x) (apply values x)))))
>
> Oops.  (apply values ...)?  Does this even work?  Anyway, you get the
> drift.  But it is not pretty and it is not primitive.  And its failure
> mode when you disobey the "single" contract is an uncaught exception
> with a weird symbol.

Well, I can't fix all of that, but you could at least make it fail
better like this:

(define (call-with-single-continuation proc)
  (let ((tag (gensym))
        (thrown #f))
    (catch tag
      (proc (lambda x (if thrown (error "Single continuation called
twice") (throw tag x)))
      (lambda (tag . x) (apply values x)))))

I think that will do what you want. It doesn't look too bad to me,
although I agree with your point in general - using symbols to denote
names, like prompts, undoes the hygiene that Scheme is supposed to
have. But the only solution I can think of is pretty messy.

Noah

Re: Non-stack-copying call-with-current-continuation?

[David Kastrup]

Noah Lavine <noah.b.lavine@gmail.com> writes:

> Hello,
>
>> Sure, but things like gensym and make-prompt-tag (and (list '()) for
>> creating an eq?-unique object) are artificial hygiene coming at a cost
>> in symbol table and symbol generation time rather than "lexical"
>> hygiene.  They need _extra_ work, whereas the
>> call-with-current-continuation approach needed _less_ work.  Basically I
>> want something like call-with-single-continuation that will only allow
>> one return (and any dynwind out counts and should work if it is the
>> first, so it is not exactly equivalent to using
>> with-continuation-barrier) and come without the stack-copying cost of
>> call-with-current-continuation.
>
> I agree that it's not pretty. We have hygienic macros so we don't have
> to use gensym, after all. But I don't know of a better way.

Well, to wrap this up: the manual (not current) states

    It is traditional in Scheme to implement exception systems using
    `call-with-current-continuation'.  Continuations (*note
    Continuations::) are such a powerful concept that any other control
    mechanism -- including `catch' and `throw' -- can be implemented in
    terms of them.

[...]

       The more targeted mechanism provided by `catch' and `throw' does not
    need to save and restore the C stack because the `throw' always jumps
    to a location higher up the stack of the code that executes the
    `throw'.  Therefore Guile implements the `catch' and `throw' primitives
    independently of `call-with-current-continuation', in a way that takes
    advantage of this _upwards only_ nature of exceptions.


I think that using something like "call-with-single-continuation" as the
underlying primitive would make Guile quite more similar to
"traditional" systems in the code base.  It would also provide a
minimally-invasive tool for tuning existing code based on
call-with-current-continuation in case that the stack copying semantics
are _not_ required.  Definitely more Schemeish than stuff like, uh,
prompts?

> Well, I can't fix all of that, but you could at least make it fail
> better like this:
>
> (define (call-with-single-continuation proc)
>   (let ((tag (gensym))
>         (thrown #f))
>     (catch tag
>       (proc (lambda x (if thrown (error "Single continuation called
> twice") (throw tag x)))
>       (lambda (tag . x) (apply values x)))))
>
> I think that will do what you want.

It would help to actually set "thrown" somewhere (which is sort of
tricky considering that you need to set it also on regular return).  You
wrap x into a list once too often (first with lambda x, then with lambda
(tag . x)).  But I get the drift.

> It doesn't look too bad to me, although I agree with your point in
> general - using symbols to denote names, like prompts, undoes the
> hygiene that Scheme is supposed to have. But the only solution I can
> think of is pretty messy.

Yup.  call-with-single-continuation would make best sense as a primitive
for building other stuff, not the other way round.

-- 
David Kastrup

Re: Non-stack-copying call-with-current-continuation?

[Andreas Rottmann]

David Kastrup <dak@gnu.org> writes:

> Noah Lavine <noah.b.lavine@gmail.com> writes:
>
>> Hello,
>>
>>> Sure, but things like gensym and make-prompt-tag (and (list '()) for
>>> creating an eq?-unique object) are artificial hygiene coming at a cost
>>> in symbol table and symbol generation time rather than "lexical"
>>> hygiene.  They need _extra_ work, whereas the
>>> call-with-current-continuation approach needed _less_ work.  Basically I
>>> want something like call-with-single-continuation that will only allow
>>> one return (and any dynwind out counts and should work if it is the
>>> first, so it is not exactly equivalent to using
>>> with-continuation-barrier) and come without the stack-copying cost of
>>> call-with-current-continuation.
>>
>> I agree that it's not pretty. We have hygienic macros so we don't have
>> to use gensym, after all. But I don't know of a better way.
>
> Well, to wrap this up: the manual (not current) states
>
>     It is traditional in Scheme to implement exception systems using
>     `call-with-current-continuation'.  Continuations (*note
>     Continuations::) are such a powerful concept that any other control
>     mechanism -- including `catch' and `throw' -- can be implemented in
>     terms of them.
>
> [...]
>
>        The more targeted mechanism provided by `catch' and `throw' does not
>     need to save and restore the C stack because the `throw' always jumps
>     to a location higher up the stack of the code that executes the
>     `throw'.  Therefore Guile implements the `catch' and `throw' primitives
>     independently of `call-with-current-continuation', in a way that takes
>     advantage of this _upwards only_ nature of exceptions.
>
>
> I think that using something like "call-with-single-continuation" as the
> underlying primitive would make Guile quite more similar to
> "traditional" systems in the code base.  It would also provide a
> minimally-invasive tool for tuning existing code based on
> call-with-current-continuation in case that the stack copying semantics
> are _not_ required.  Definitely more Schemeish than stuff like, uh,
> prompts?
>
Just to throw my two cents in: Racket (and probably other Schemes)
provide this primitive under the name call-with-escape-continuation
(call/ec):

http://docs.racket-lang.org/reference/cont.html?q=call/ec#%28def._%28%28quote._~23~25kernel%29._call-with-escape-continuation%29%29

Regards, Rotty
-- 
Andreas Rottmann -- <http://rotty.yi.org/>

Re: Non-stack-copying call-with-current-continuation?

[Andreas Rottmann]

David Kastrup <dak@gnu.org> writes:

> Noah Lavine <noah.b.lavine@gmail.com> writes:
>
>> Hello,
>>
>>> Sure, but things like gensym and make-prompt-tag (and (list '()) for
>>> creating an eq?-unique object) are artificial hygiene coming at a cost
>>> in symbol table and symbol generation time rather than "lexical"
>>> hygiene.  They need _extra_ work, whereas the
>>> call-with-current-continuation approach needed _less_ work.  Basically I
>>> want something like call-with-single-continuation that will only allow
>>> one return (and any dynwind out counts and should work if it is the
>>> first, so it is not exactly equivalent to using
>>> with-continuation-barrier) and come without the stack-copying cost of
>>> call-with-current-continuation.
>>
>> I agree that it's not pretty. We have hygienic macros so we don't have
>> to use gensym, after all. But I don't know of a better way.
>
> Well, to wrap this up: the manual (not current) states
>
>     It is traditional in Scheme to implement exception systems using
>     `call-with-current-continuation'.  Continuations (*note
>     Continuations::) are such a powerful concept that any other control
>     mechanism -- including `catch' and `throw' -- can be implemented in
>     terms of them.
>
> [...]
>
>        The more targeted mechanism provided by `catch' and `throw' does not
>     need to save and restore the C stack because the `throw' always jumps
>     to a location higher up the stack of the code that executes the
>     `throw'.  Therefore Guile implements the `catch' and `throw' primitives
>     independently of `call-with-current-continuation', in a way that takes
>     advantage of this _upwards only_ nature of exceptions.
>
>
> I think that using something like "call-with-single-continuation" as the
> underlying primitive would make Guile quite more similar to
> "traditional" systems in the code base.  It would also provide a
> minimally-invasive tool for tuning existing code based on
> call-with-current-continuation in case that the stack copying semantics
> are _not_ required.  Definitely more Schemeish than stuff like, uh,
> prompts?
>
Just to throw my two cents in: Racket (and probably other Schemes)
provide this primitive under the name call-with-escape-continuation
(call/ec):

http://docs.racket-lang.org/reference/cont.html?q=call/ec#%28def._%28%28quote._~23~25kernel%29._call-with-escape-continuation%29%29

Regards, Rotty
-- 
Andreas Rottmann -- <http://rotty.yi.org/>

Re: Non-stack-copying call-with-current-continuation?

[Andy Wingo]

On Fri 02 Mar 2012 02:35, David Kastrup <dak@gnu.org> writes:

> Sure, but things like gensym and make-prompt-tag (and (list '()) for
> creating an eq?-unique object) are artificial hygiene coming at a cost
> in symbol table and symbol generation time rather than "lexical"
> hygiene.

"Hygiene" is not right the word here.  "Hygiene" applies lexically --
statically.  You want a continuation that only works within a certain
dynamic extent -- that's dynamic.  Unique objects are well-suited to the
needs of dynamic problems.

But really, your concerns are entirely misplaced.  Choose clean, clear,
optimizable abstractions.  Call/ec is a good example.  If you need to
implement it, do so using whatever tools are at hand.  If you can't
implement it or it's slow, then bring these concerns forward.  But to
dismiss Noah's suggestions out of hand is inappropriate at this time.

Andy
-- 
http://wingolog.org/

Re: Non-stack-copying call-with-current-continuation?

[David Kastrup]

Andy Wingo <wingo@pobox.com> writes:

> On Fri 02 Mar 2012 02:35, David Kastrup <dak@gnu.org> writes:
>
>> Sure, but things like gensym and make-prompt-tag (and (list '()) for
>> creating an eq?-unique object) are artificial hygiene coming at a cost
>> in symbol table and symbol generation time rather than "lexical"
>> hygiene.
>
> "Hygiene" is not right the word here.  "Hygiene" applies lexically --
> statically.  You want a continuation that only works within a certain
> dynamic extent -- that's dynamic.  Unique objects are well-suited to the
> needs of dynamic problems.

The problem is not a unique object (you get one with every (list 0)
call), the problem is a unique symbol.  Of course an escape continuation
works only in a dynamic context.  But that does not mean that its
identity needs to be represented by a globally persisting symbol.  The
global symbol space is a different identity space than heap equality,
and it never gets garbage collected: the lifetime of a gensym is
eternal.

> But really, your concerns are entirely misplaced.  Choose clean,
> clear, optimizable abstractions.  Call/ec is a good example.  If you
> need to implement it, do so using whatever tools are at hand.  If you
> can't implement it or it's slow, then bring these concerns forward.
> But to dismiss Noah's suggestions out of hand is inappropriate at this
> time.

I am not dismissing his suggestions.  I am saying that I find call/ec a
nicer primitive than catch/throw exactly because it does not need a name
or symbol to work but has its identity and life-time coupled to an
object rather than a symbol.

And frankly: the manual talks about prompts being composable and gives
an example which seems utterly wrong to me since it does not actually
abort a computation but rather half-finishes it.  It is unclear what
part of the computation will finish and what will complete.

-- 
David Kastrup

Re: Non-stack-copying call-with-current-continuation?

[Andy Wingo]

Hi David,

On Sun 04 Mar 2012 13:01, David Kastrup <dak@gnu.org> writes:

> The global symbol space is a different identity space than heap
> equality, and it never gets garbage collected: the lifetime of a
> gensym is eternal.

This is not true in Guile, where symbols can be garbage collected.

> I am not dismissing his suggestions.  I am saying that I find call/ec a
> nicer primitive than catch/throw exactly because it does not need a name
> or symbol to work but has its identity and life-time coupled to an
> object rather than a symbol.

OK.

> And frankly: the manual talks about prompts being composable and gives
> an example which seems utterly wrong to me since it does not actually
> abort a computation but rather half-finishes it.  It is unclear what
> part of the computation will finish and what will complete.

That is an interesting point.  I guess there are two ways of answering
it.  One is to note that in Scheme, it's difficult in general to
determine whether a computation is finished or will finish, because of
call/cc.

But you ask about a specific point, here: an abort to a prompt is
basically boils down to a longjmp to the prompt's handler.  The partial
continuation is logically passed as an argument to the handler.  I say
"logically" because, if Guile can prove that the continuation is not
referenced, then it no continuation is reified.  In practice, that means
that if the handler is of the form (lambda (k . other-args) FORM), and
FORM does not reference `k', then an abort to that prompt does not cause
the stack to be captured.

We should probably say something in the manual about this.  (We should
probably also add higher-level interfaces like call/ec and generators,
as well.)

Regards,

Andy
-- 
http://wingolog.org/

Re: Non-stack-copying call-with-current-continuation?

[David Kastrup]

Andy Wingo <wingo@pobox.com> writes:

> Hi David,
>
> On Sun 04 Mar 2012 13:01, David Kastrup <dak@gnu.org> writes:
>
>> The global symbol space is a different identity space than heap
>> equality, and it never gets garbage collected: the lifetime of a
>> gensym is eternal.
>
> This is not true in Guile, where symbols can be garbage collected.

The symbol name is not garbage collected.  That is the difference
between gensym and make-symbol.

>> And frankly: the manual talks about prompts being composable and
>> gives an example which seems utterly wrong to me since it does not
>> actually abort a computation but rather half-finishes it.  It is
>> unclear what part of the computation will finish and what will
>> complete.
>
> That is an interesting point.  I guess there are two ways of answering
> it.  One is to note that in Scheme, it's difficult in general to
> determine whether a computation is finished or will finish, because of
> call/cc.
>
> But you ask about a specific point, here: an abort to a prompt is
> basically boils down to a longjmp to the prompt's handler.  The
> partial continuation is logically passed as an argument to the
> handler.

But where does the "partial continuation" start and where does it end?
If I am doing a "longjmp to the prompt's handler", how can it be that
the calling stack frame inside of the thunk that is supposed to be
exited can finish a calculation?  Where is the difference between

(+ 34 (abort-to-prompt 'foo))

and

(let ((x (abort-to-prompt 'foo))) (+ 34 x)) ?

Why is the first allowed to complete and return a result, and the second
(presumably) not?  Or _if_ the second is allowed to complete, what does
"abort" in "abort-to-prompt" even mean?

All this does not really make discernible sense to me.  Whereas call/ec
has rather clear semantics and usage.  The one thing that is not
self-evident is its behavior in case of misuse, namely when it is asked
to do a job only call/cc can.

-- 
David Kastrup

Re: Non-stack-copying call-with-current-continuation?

[Andy Wingo]

Hello,

On Sun 04 Mar 2012 14:59, David Kastrup <dak@gnu.org> writes:

> Andy Wingo <wingo@pobox.com> writes:
>
>> This is not true in Guile, where symbols can be garbage collected.
>
> The symbol name is not garbage collected.  That is the difference
> between gensym and make-symbol.

Not sure I catch your meaning here...

>> But you ask about a specific point, here: an abort to a prompt is
>> basically boils down to a longjmp to the prompt's handler.  The
>> partial continuation is logically passed as an argument to the
>> handler.
>
> But where does the "partial continuation" start and where does it end?

It starts at the abort, and is delimited by the prompt.  Or you can see
it as the other way around.

> If I am doing a "longjmp to the prompt's handler", how can it be that
> the calling stack frame inside of the thunk that is supposed to be
> exited can finish a calculation?

You longjmp, yes: but after having reified (or not) the continuation.
It's the continuation that lets you continue.

> Where is the difference between
>
> (+ 34 (abort-to-prompt 'foo))
>
> and
>
> (let ((x (abort-to-prompt 'foo))) (+ 34 x)) ?

There is no semantic difference.

> Why is the first allowed to complete and return a result, and the second
> (presumably) not?  Or _if_ the second is allowed to complete, what does
> "abort" in "abort-to-prompt" even mean?

Whether it is allowed to complete or not depends on the prompt's
handler, as I mentioned before.

Here is an analogy.  Consider a prompt as creating a new process, in the
UNIX sense.  Consider "abort" as calling abort() and dumping core (or
not).  Consider calling the partial continuation as taking the core file
and running it as a program (as used to be possible in some UNIX
systems).

Sometimes you enable cores because you are interested in them.
Sometimes you just want to let a process quit and return a value.  The
analogy with reifying continuations or not is clear, I hope.

> All this does not really make discernible sense to me.  Whereas call/ec
> has rather clear semantics and usage.

Please do use call/ec, if you prefer its interface.

> The one thing that is not self-evident is its behavior in case of
> misuse, namely when it is asked to do a job only call/cc can.

For the implementation based on "throw", you would get an error that
would be caught by the nearest (catch #t ...).  For prompts, you would
get an error "abort to unknown prompt", which would also be caught by
the nearest (catch #t ...), or a catch of `misc-error'.  (Guile's error
handling is not very systematic right now; something to work on.)

Regards,

Andy
-- 
http://wingolog.org/

Re: Non-stack-copying call-with-current-continuation?

[Mark H Weaver]

David Kastrup <dak@gnu.org> writes:

> Andy Wingo <wingo@pobox.com> writes:
>
>> On Sun 04 Mar 2012 13:01, David Kastrup <dak@gnu.org> writes:
>>
>>> The global symbol space is a different identity space than heap
>>> equality, and it never gets garbage collected: the lifetime of a
>>> gensym is eternal.
>>
>> This is not true in Guile, where symbols can be garbage collected.
>
> The symbol name is not garbage collected.  That is the difference
> between gensym and make-symbol.

Integers are plentiful and cheap.  Anyway, there's a well-known
"Efficient Gensym Hack" where gensyms are given names lazily.  We
haven't yet implemented that in Guile, but I hope to add it before 2.2.
With that optimization, if you never ask for the name of a gensym
(e.g. by printing it) then it is never assigned a name or even a number.
Dybvig reports that in Chez Scheme, this optimization made gensym 25
times faster.

Also, in Guile 2, prompt tags need not be symbols.  Anything that can be
compared with 'eq?' will work.

>>> And frankly: the manual talks about prompts being composable and
>>> gives an example which seems utterly wrong to me since it does not
>>> actually abort a computation but rather half-finishes it.  It is
>>> unclear what part of the computation will finish and what will
>>> complete.
>>
>> That is an interesting point.  I guess there are two ways of answering
>> it.  One is to note that in Scheme, it's difficult in general to
>> determine whether a computation is finished or will finish, because of
>> call/cc.
>>
>> But you ask about a specific point, here: an abort to a prompt is
>> basically boils down to a longjmp to the prompt's handler.  The
>> partial continuation is logically passed as an argument to the
>> handler.
>
> But where does the "partial continuation" start and where does it end?

A partial continuation captures the stack from the prompt to the abort.
If you later call the partial continuation with some values, those
values will be returned by 'abort-to-prompt', and the computation will
continue until it returns to the prompt, at which point the partial
continuation will return the values returned to the prompt.

An approximate way to think about it is as follows.  In the following:

  (call-with-prompt
   'foo
   (lambda () (let ((x (abort-to-prompt 'foo))) (+ 34 x)))
   (lambda (k) k))

The returned partial continuation will be equivalent to the following
procedure:

  (lambda xs (let ((x (apply values xs))) (+ 34 x)))

To a first (very rough) approximation, you can imagine that you took the
body of the thunk passed to 'call-with-prompt', wrapped it within
(lambda xs ...), replaced the 'abort-to-prompt' that was invoked with
(apply values xs), and that's sort of what the partial continuation acts
like.

How does this approximation fall short?  First of all, it's not quite
right to replace the 'abort-to-prompt' with (apply values xs), because
if that 'abort-to-prompt' is called again (e.g. if it's within a loop)
then it will abort again.  More importantly, when you call a partial
continuation, it jumps directly to the 'abort-to-prompt', rather than
re-running the outer layers of code.  Any mutable local variables bound
between prompt and abort will have whatever values they were last set!
to, rather than being rebound.

> If I am doing a "longjmp to the prompt's handler", how can it be that
> the calling stack frame inside of the thunk that is supposed to be
> exited can finish a calculation?

If the compiler cannot prove that the partial continuation is ignored by
the handler passed to 'call-with-prompt', then the stack segment between
the prompt and abort must be copied.  If the partial continuation is
later called, that stack segment will be copied back.

> Where is the difference between
>
> (+ 34 (abort-to-prompt 'foo))
>
> and
>
> (let ((x (abort-to-prompt 'foo))) (+ 34 x)) ?
>
> Why is the first allowed to complete and return a result, and the second
> (presumably) not?  Or _if_ the second is allowed to complete, what does
> "abort" in "abort-to-prompt" even mean?

What makes you think that the second would not be allowed to complete?
In both of these cases, assuming that what you've written above is the
entire body of the thunk passed to 'call-with-prompt', the partial
continuation will be equivalent to (lambda (x . rest) (+ 34 x)).

> All this does not really make discernible sense to me.  Whereas call/ec
> has rather clear semantics and usage.  The one thing that is not
> self-evident is its behavior in case of misuse, namely when it is asked
> to do a job only call/cc can.

I agree that Guile should have 'call/ec' (ideally backed by an efficient
VM instruction), and that for many purposes 'call/ec' is more natural.
However, it should be noted that prompts are strictly more powerful than
'call/ec', and that 'call/ec' can be implemented easily and efficiently
using prompts.

For now, you can use this definition:

  (cond-expand
   (guile-2 (define (call-with-escape-continuation proc)
              (let ((tag (make-prompt-tag "call/ec")))
                (call-with-prompt
                 tag
                 (lambda () (proc (lambda xs (abort-to-prompt tag xs))))
                 (lambda (k xs) (apply values xs))))))
  
   (guile (define (call-with-escape-continuation proc)
            (let ((key (gensym "call/ec")))
              (catch key
                (lambda () (proc (lambda xs (throw key xs))))
                (lambda (key xs) (apply values xs)))))))
  
  (define call/ec call-with-escape-continuation)

      Mark

Re: Non-stack-copying call-with-current-continuation?

[David Kastrup]

Mark H Weaver <mhw@netris.org> writes:

> David Kastrup <dak@gnu.org> writes:
>
>> Andy Wingo <wingo@pobox.com> writes:
>>
>>> On Sun 04 Mar 2012 13:01, David Kastrup <dak@gnu.org> writes:
>>>
>>>> The global symbol space is a different identity space than heap
>>>> equality, and it never gets garbage collected: the lifetime of a
>>>> gensym is eternal.
>>>
>>> This is not true in Guile, where symbols can be garbage collected.
>>
>> The symbol name is not garbage collected.  That is the difference
>> between gensym and make-symbol.
>
> Integers are plentiful and cheap.

We are not talking about an integer generated statically here.  We are
talking about integers getting burned through every time a control
structure is being used.  Not at compilation time, but at runtime.  And
with today's computers, executing a loop often enough that the integers
don't fit into a single Scheme cell anymore and stop being cheap is not
really an extraordinary event.

> Anyway, there's a well-known "Efficient Gensym Hack" where gensyms are
> given names lazily.  We haven't yet implemented that in Guile, but I
> hope to add it before 2.2.  With that optimization, if you never ask
> for the name of a gensym (e.g. by printing it) then it is never
> assigned a name or even a number.

That would help.

> Also, in Guile 2, prompt tags need not be symbols.  Anything that can
> be compared with 'eq?' will work.

I suppose there is no compelling technical reason why this could not be
made to also work with catch/throw, right?  Being able to use something
like (list #f) instead of gensym would seriously reduce the cost, both
felt as well as actual.

-- 
David Kastrup

Re: Non-stack-copying call-with-current-continuation?

[Mark H Weaver]

David Kastrup <dak@gnu.org> writes:

> Mark H Weaver <mhw@netris.org> writes:
>
>> David Kastrup <dak@gnu.org> writes:
>>
>>> The symbol name is not garbage collected.  That is the difference
>>> between gensym and make-symbol.
>>
>> Integers are plentiful and cheap.
>
> We are not talking about an integer generated statically here.  We are
> talking about integers getting burned through every time a control
> structure is being used.  Not at compilation time, but at runtime.  And
> with today's computers, executing a loop often enough that the integers
> don't fit into a single Scheme cell anymore and stop being cheap is not
> really an extraordinary event.

Indeed, this is a good point, and another reason why we need the
efficient gensym hack.

>> Also, in Guile 2, prompt tags need not be symbols.  Anything that can
>> be compared with 'eq?' will work.
>
> I suppose there is no compelling technical reason why this could not be
> made to also work with catch/throw, right?  Being able to use something
> like (list #f) instead of gensym would seriously reduce the cost, both
> felt as well as actual.

Indeed, I see no reason why catch/throw shouldn't accept non-symbol
tags.  Looking through the code of Guile 1.8, I see nothing that depends
upon the tag being a symbol.  Unfortunately, catch/throw have long been
documented as requiring a symbol, and raise an error if given a
non-symbol, at least as far back as Guile 1.4.

However, catch/throw _will_ accept uninterned symbols created with
'make-symbol'.

Here's a faster implementation of call/ec that uses (list 'call/ec) to
create prompt tags on Guile 2, and (make-symbol "call/ec") on earlier
versions of Guile:

  (cond-expand
   (guile-2 (define (call-with-escape-continuation proc)
              (let ((tag (list 'call/ec)))
                (call-with-prompt
                 tag
                 (lambda () (proc (lambda xs (abort-to-prompt tag xs))))
                 (lambda (k xs) (apply values xs))))))
  
   (guile (define (call-with-escape-continuation proc)
            (let ((key (make-symbol "call/ec")))
              (catch key
                (lambda () (proc (lambda xs (throw key xs))))
                (lambda (key xs) (apply values xs)))))))
  
  (define call/ec call-with-escape-continuation)

     Regards,
       Mark

Re: Non-stack-copying call-with-current-continuation?

[David Kastrup]

Mark H Weaver <mhw@netris.org> writes:

> However, catch/throw _will_ accept uninterned symbols created with
> 'make-symbol'.

Personally, I like uninterned symbols much better.  They can be a bit
confusing in Lisp because they share print names, but one can't exactly
say that they do in Guile:

guile> (make-symbol "xxx")
#<uninterned-symbol xxx b7838a10>
guile> 

Which feels a bit like gensym-on-demand, except that the serialization
happens by address rather than counting.

> Here's a faster implementation of call/ec that uses (list 'call/ec) to
> create prompt tags on Guile 2, and (make-symbol "call/ec") on earlier
> versions of Guile:
>
>   (cond-expand
>    (guile-2 (define (call-with-escape-continuation proc)
>               (let ((tag (list 'call/ec)))
>                 (call-with-prompt
>                  tag
>                  (lambda () (proc (lambda xs (abort-to-prompt tag xs))))
>                  (lambda (k xs) (apply values xs))))))
>   
>    (guile (define (call-with-escape-continuation proc)
>             (let ((key (make-symbol "call/ec")))
>               (catch key
>                 (lambda () (proc (lambda xs (throw key xs))))
>                 (lambda (key xs) (apply values xs)))))))
>   
>   (define call/ec call-with-escape-continuation)

Given the constraints of current guile-1 and guile-2, I doubt that there
is much to take away anymore from this solution.

Thanks

-- 
David Kastrup

Re: Non-stack-copying call-with-current-continuation?

[Nala Ginrut]

[-- Attachment #1: Type: text/plain, Size: 1827 bytes --]

On Fri, Mar 2, 2012 at 8:00 AM, David Kastrup <dak@gnu.org> wrote:

>
> Hi,
>
> I am just meddling around with coding and have come up with the
> following:
>
> (define-public (find-child music predicate)
>  "Find the first node in @var{music} that satisfies @var{predicate}."
>  (catch 'music-found
>         (lambda ()
>           (fold-some-music predicate
>                            (lambda (music . _) (throw 'music-found music))
>                            #f music))
>         (lambda (key music) music)))
>
> Now the problem with that is that it is unhygienic.  If fold-some-music
> were to use music-found signals, or if the predicate did, things would
> be awkward.  One would need to work with a uniquely generated symbol.
> It turns out that the above can be expressed much clearer and cleaner as
>
> (define-public (find-child music predicate)
>  "Find the first node in @var{music} that satisfies @var{predicate}."
>  (call-with-current-continuation
>   (lambda (music-found)
>     (fold-some-music predicate
>                      (lambda (music . _) (music-found music))
>                      #f music))))
>
> at least if I did not make some thinko here.  It is basically the same
> code and stack-upwards-only, but hygienic.  Nothing can call the
> continuation but what is inside.  Well, of course fold-some-music could
> save the closure calling music-found for later.  But it doesn't.
>
> Is there a way to get a call-with-current-continuation that does not
> create a stack copy?


IIRC, the stack copying in Guile's continuation implementation is
inevitable. Though it's inefficient, the consideration is to cooperate with
other languages such as C.


> It is fine if it fails with an exception if one
> still tries calling the continuation after it has already returned.
>
> --
> David Kastrup
>
>
>

[-- Attachment #2: Type: text/html, Size: 2523 bytes --]

Re: Non-stack-copying call-with-current-continuation?

[Noah Lavine]

Hello,

> IIRC, the stack copying in Guile's continuation implementation is
> inevitable. Though it's inefficient, the consideration is to cooperate with
> other languages such as C.

It's inevitable in the general case, where the continuation might
return multiple times.

However, in this situation, he knows the continuation will only ever
return once, so it is not necessary to copy the stack. This control
structure will be the equivalent of setjmp and longjmp in C.

Prompts have an optimization where they don't actually copy the stack
if it is clear that they can only return once. That is why catch and
throw are implemented that way.

Noah

Re: Non-stack-copying call-with-current-continuation?

[Andy Wingo]

Hi David,

On Fri 02 Mar 2012 01:00, David Kastrup <dak@gnu.org> writes:

> Is there a way to get a call-with-current-continuation that does not
> create a stack copy?

This is usually referred to as `call-with-escape-continuation'.

For example, here are Racket's words on the topic:

  http://docs.racket-lang.org/reference/cont.html#(def._((quote._~23~25kernel)._call-with-escape-continuation))

Here is a good definition of call/ec in Guile:

  (define (call/ec proc)
    (let ((tag (make-prompt-tag)))
      (define (abort . args)
        (abort-to-prompt tag args))
      (call-with-prompt tag
        (lambda () (proc abort))
        (lambda (k args) (apply values args)))))

That one won't work in Guile 1.8 though.  A portable definition:

  (define (call/ec proc)
    (let ((key (gensym "escape ")))
      (define (abort . args)
        (throw key args))
      (catch key
        (lambda () (proc abort))
        (lambda (key args) (apply values args)))))

Regards,

Andy
-- 
http://wingolog.org/