call/cc and recursive vm invocations

call/cc and recursive vm invocations

[Andy Wingo]

Hey folks,

One of the last missing features / regressions on my list for 2.0 is to
fix make-stack and start-stack to work with the VM.

In case you haven't noticed yet, if you get an error at the REPL and ask
for a backtrace from the debugger, you get not only the frames that
pertain to your own computation, but also frames from the REPL
implementation itself. That's not good, and it's a regression.

The solution is to implement start-stack for the VM. Prompts provide an
ideal set of primitives. So start-stack can be this:

  (define (start-stack tag exp)
    (let ((prompt-tag (fresh-tag)))
      (with-fluids ((stacks (acons tag prompt-tag (fluid-ref stacks))))
        (% prompt-tag
           exp
           (lambda (k . args)
             (apply values k args))))))

This assumes some fluid is around named "stacks". Then we can implement
make-stack:

  (define (make-stack tag . narrowing)
    (let ((prompt-tag (assq-ref (fluid-ref stacks) tag)))
      (unless prompt-tag
        (error "prompt tag not found quoi"))
      (narrow-stack
       (continuation->stack
        (call/cc
         (lambda (k) k)
          prompt-tag))
       narrowing)))
  
And this assumes that we factor out stack narrowing to its own
procedure, and that continuation->stack exists (it does now, inside
scm_make_stack)...

...and, that we have a call/cc that takes two arguments.

Now, currently "full" continuations integrate just fine with delimited
continuations. (Recall that full continuations copy the whole stack,
both on the C and Scheme level.) But here we'd like the ability to
capture just the Scheme stack, and only up to a certain delimiter
(prompt).

In fact this actually adds more power to call/cc, by allowing the user
to delimit the scope of the continuations that it captures (via
prompts). However it seems that one cannot implement call/cc purely in
terms of prompt and abort -- because with prompt and abort, reifying a
continuation only happens on an abort, which unwinds the dynamic state.
Likewise invoking a "full" (but delimited) continuation needs to replace
the continuation from a prompt, but might not need to unwind all the way
to the prompt, if the current and future continuations share part of
their dynamic extents.

Finally, delimiting call/cc makes it more expressive when invoked from a
callback API. Imagine you have some inversion-of-control library that
calls your code every so often -- currently in Guile you can't capture
the continuation in one callback, then invoke it in the next, because it
means your first callback would return twice. Well, truth is you can,
but often callback-style APIs are implemented in C or such, and often
such code can't handle multiple returns.

Reinstating a full-but-delimited continuation, on the other hand, can
happen in different dynamic contexts -- each callback can set up a
prompt, and calling a continuation with a specific prompt tag will
overwrite the stack only up to the prompt with that tag.

Relatedly, delimiting the continuations makes it easier to think about
shipping them across the network.


                              *  *  *

So, that's the upside. The downside of delimiting "full" continuations
is that you can't capture the C stack.

This has a number of ramifications, but first, a little eulogy for
Guile's current implementation of "full" continuations: it has been nice
to be able to capture the C stack. It makes C coding more like Scheme
coding, to know that control may flow through your functions in more
than one way. I enjoyed it.

But of course, to each implementation its own time, and this approach to
continuations has been nearing its expiration date for years now. Most C
code can't deal with nonlocal exits, let alone multiple returns. So the
utility of this construct has been limited.

Now, with the VM and partial continuations, we have the ability to
capture the Scheme stack apart from the C stack, and more and more can
be done within the VM itself. Call/cc is mostly useful in a pure Scheme
context anyway, so it's natural to start thinking of an implementation
of continuations that does not capture the C stack.

(FWIW, the ability to exit from C code nonlocally is key to Guile's C
API, and I don't see a move away from that in any foreseeable future.
The issue at hand here is *capture* of the C stack.)


Anyway, enough about that. Practically speaking, not capturing the C
stack means that you cannot invoke a continuation that was captured
outside the current VM invocation. For example, there are a number of
primitive functions that end up calling scm_call_1 or such, like
scm_map. So this wouldn't work:

  (let ((k (call/cc (lambda (k) k))))
    (map (lambda (x) (k x)) list-of-things))

because the lambda gets called within a recursive VM invocation, so
there are intermediate C frames on the stack, so the continuation cannot
be invoked. (The code to detect this exists already.)

I did an informal experiment to see what code caused recursive VM
invocations during a repl startup. The total was about 3500 VM
invocations, most of those singly-recursive. I don't think this is
expensive, but it's a bit unnecessary.

The most common causes for recursive incovations for a repl startup
were, in no order:

  primitive-load
  load-compiled/vm
  primitive-load-path
  call-with-input-string (only once or so)
  map
  for-each
  hash-for-each
  scm_eval_closure_lookup (?)
  scm_thunk_p (calls program's meta-thunk to get arity; wasteful GC-wise)
  scm_resolve_module (calls Scheme resolve-module)
  filter

Note that dynamic-wind and with-fluids are no longer on there,
thankyouverymuch. thunk? is only on the list because of the dynamic-wind
invocations that are there, many of which could be replaced by
with-fluids I think. (We should expose the current ports as fluids I
think.)

Map and for-each are interesting cases, actually:

  http://www.r6rs.org/formal-comments/comment-36.txt
  http://lists.r6rs.org/pipermail/r6rs-discuss/2007-March/001956.html

But regardless of that, I think they should be in Scheme for purposes of
inlining. (map (lambda (x) ...) '(list of few things)) should be
inlined, and (for-each (lambda (x) ...) l) should always be inlined,
because it allows further optimizations.

                              *  *  *

Practically speaking... I think I can delimit call/cc with not much work
(perhaps tomorrow). But it is a visible change (if you're looking), so I
wanted to put this mail out there to get comments. I had thought this
was a 2.2 feature, but given the make-stack implications, I'm thinking
it's a 1.9.9 feature. Reactions?

Happy hacking,

Andy
-- 
http://wingolog.org/

Re: call/cc and recursive vm invocations

[Neil Jerram]

Andy Wingo <wingo@pobox.com> writes:

> Hey folks,
>
> One of the last missing features / regressions on my list for 2.0 is to
> fix make-stack and start-stack to work with the VM.

Yes, I'd noticed that.

> The solution is to implement start-stack for the VM. Prompts provide an
> ideal set of primitives.

Really?  I'm anticipating some of what you've written below, here, but
isn't using prompts and continuations, and maybe completely changing how
continuations can be used, a bit of a sledgehammer, when all we want to
do is tell `backtrace' to limit the set of frames that it prints out?

>   (define (make-stack tag . narrowing)
>     (let ((prompt-tag (assq-ref (fluid-ref stacks) tag)))
>       (unless prompt-tag
>         (error "prompt tag not found quoi"))
>       (narrow-stack
>        (continuation->stack
>         (call/cc
>          (lambda (k) k)
>           prompt-tag))
>        narrowing)))
>   
> And this assumes that we factor out stack narrowing to its own
> procedure, and that continuation->stack exists (it does now, inside
> scm_make_stack)...
>
> ...and, that we have a call/cc that takes two arguments.

But, instead of requiring call/cc to change, couldn't we also write a
new primitive equivalent to the combination:

    (continuation->stack (call/cc identity prompt-tag))

(Actually this sounds pretty similar to the current scm_make_stack, with
an added search for prompt-tag.)

> Now, currently "full" continuations integrate just fine with delimited
> continuations. (Recall that full continuations copy the whole stack,
> both on the C and Scheme level.)

Do you mean in theory, or in current Guile?  I'm afraid I'm not up to
speed with where things have reached.

<pause to check code...>

OK, so it looks like we now have abort and prompt as primitives, and
catch, throw etc. implemented in terms of them, but that continuations
are thus far unchanged from their old form.  Is that correct?

I think this means that the idea of composable continuations, as
discussed in your blog, is still pending.  Also, if I'm understanding
correctly, it seems to me that that idea is the same as having a 2 arg
call/cc.

If so, I think your email isn't proposing any new concepts beyond what
you raised before, but rather highlighting an implication of
implementing those concepts.

Is that all correct?

> In fact this actually adds more power to call/cc, by allowing the user
> to delimit the scope of the continuations that it captures (via
> prompts).

Agreed - but this is just repeating what you've said before, isn't it?

> Finally, delimiting call/cc makes it more expressive when invoked from a
> callback API. Imagine you have some inversion-of-control library that
> calls your code every so often -- currently in Guile you can't capture
> the continuation in one callback, then invoke it in the next, because it
> means your first callback would return twice. Well, truth is you can,
> but often callback-style APIs are implemented in C or such, and often
> such code can't handle multiple returns.

Yes, I've hit this issue.  It can be solved though, with Guile 1.8.x.

> Relatedly, delimiting the continuations makes it easier to think about
> shipping them across the network.

Interesting.

>                               *  *  *
>
> So, that's the upside. The downside of delimiting "full" continuations
> is that you can't capture the C stack.

Why?  Also I'm not sure what "full" means here.

>                               *  *  *
>
> Practically speaking... I think I can delimit call/cc with not much work
> (perhaps tomorrow). But it is a visible change (if you're looking), so I
> wanted to put this mail out there to get comments.

Well, I hope that some of mine are useful.

I'm afraid I don't yet understand well enough (despite all of the
explanation above) what the impact of this visible change would be;
perhaps some more concrete examples would help.  But it seems a very big
change, if it's only to produce delimited backtraces.

> I had thought this
> was a 2.2 feature, but given the make-stack implications, I'm thinking
> it's a 1.9.9 feature. Reactions?

My feeling is to do something smaller to get make-stack working for 2.0,
and look at the wider change for 2.2.  But I'm far from sure about that.

Also, is there any possibility of keeping both old- and new-style
continuations side by side?

> Happy hacking,
>
> Andy

Regards,
      Neil

Re: call/cc and recursive vm invocations

[Andy Wingo]

Hi Neil,

Thanks for looking at this!

On Sat 06 Mar 2010 18:13, Neil Jerram <neil@ossau.uklinux.net> writes:

> Andy Wingo <wingo@pobox.com> writes:
>
>> Hey folks,
>>
>> One of the last missing features / regressions on my list for 2.0 is to
>> fix make-stack and start-stack to work with the VM.
>
> Yes, I'd noticed that.
>
>> The solution is to implement start-stack for the VM. Prompts provide an
>> ideal set of primitives.
>
> Really?

Yes, because prompts allow you to correlate function-call frames with
the dynamic environment (wind stack) -- because a prompt captures the
frame pointer, stack pointer, etc.

>> ...and, that we have a call/cc that takes two arguments.
>
> But, instead of requiring call/cc to change, couldn't we also write a
> new primitive equivalent to the combination:
>
>     (continuation->stack (call/cc identity prompt-tag))
>
> (Actually this sounds pretty similar to the current scm_make_stack, with
> an added search for prompt-tag.)

Good point! Perhaps this is the solution, then.

Note that if we used call/cc in this way, we wouldn't be requiring
call/cc to change, we would just be adding an optional second argument.

>> Now, currently "full" continuations integrate just fine with delimited
>> continuations. (Recall that full continuations copy the whole stack,
>> both on the C and Scheme level.)
>
> Do you mean in theory, or in current Guile?  I'm afraid I'm not up to
> speed with where things have reached.

It is true that some of my thinking on this was a bit muddy, and
that muddiness translated to the explanation. So let me try again.

I mentioned at some point that the PLT people prefer to speak of
"composable continuations" versus "non-composable continuations", and I
wasn't sure why. Now I know, I think: continuations captured by
prompt/abort can be invoked for a value, so you can have continuations
invoking continuations for a value -- the continuations can be composed
together.

On the other hand, continuations captured by call/cc are not composable.
When you invoke a non-composable continuation, your continuation is
trashed, and replaced with the one you invoked. When I said "full" in
that mail, I meant "non-composable".

So that's one axis. The other axis is delimited versus undelimited,
and perhaps I have been able to convey this difference in the past. But
in my earlier posts I had been lumping "delimited" together with
"composable", and that's not necessarily the case -- you can also make a
call/cc that is delimited, and that's what this mail was about.

Guile's current call/cc is both non-composable, by nature (RnRS), and
undelimited, by accident. It captures the whole continuation, regardless
of prompts; and invoking a captured continuation reinstates the entire
continuation, instead of reinstating just to a prompt.

Call/cc is not implementable in terms of prompt and abort, because with
prompt and abort, the continuation is captured only on abort, and that
unwinds the dynamic state to the prompt. But (call/cc identity) implies
no unwinding.

> OK, so it looks like we now have abort and prompt as primitives, and
> catch, throw etc. implemented in terms of them, but that continuations
> are thus far unchanged from their old form.  Is that correct?

Yes.

> I think this means that the idea of composable continuations, as
> discussed in your blog, is still pending.  Also, if I'm understanding
> correctly, it seems to me that that idea is the same as having a 2 arg
> call/cc.

No we definitely have composable continuations. (Yay!) What we don't
have are delimited non-composable continuations.

>> Finally, delimiting call/cc makes it more expressive when invoked from a
>> callback API. Imagine you have some inversion-of-control library that
>> calls your code every so often -- currently in Guile you can't capture
>> the continuation in one callback, then invoke it in the next, because it
>> means your first callback would return twice. Well, truth is you can,
>> but often callback-style APIs are implemented in C or such, and often
>> such code can't handle multiple returns.
>
> Yes, I've hit this issue.  It can be solved though, with Guile 1.8.x.

This can be worked around in the inversion-of-control library via
rewindable frames, or prohibited via with-continuation-barrier; but if
the library is not continuation-safe, you can't invoke continuations
captured in a callback outside of that callback, even in 1.8.

Delimited non-composable continuations could solve this, though, because
invoking a delimited non-composable continuation replaces the current
continuation *only up to a prompt*, just as it was captured only up to a
prompt. So you wrap each callback invocation in a prompt, and the Scheme
programmer gets her call/cc, and the library implementor is left in
peace.

>> Relatedly, delimiting the continuations makes it easier to think about
>> shipping them across the network.
>
> Interesting.

It turns out we already have a serializer for most Guile objects, in the
compiler. We'd just need to add cases for closures and continuations --
for which most of the work is already done.

>> So, that's the upside. The downside of delimiting "full" continuations
>> is that you can't capture the C stack.
>
> Why?  Also I'm not sure what "full" means here.

"Non-composable". The reason is that invoking a delimited non-composable
continuation reinstates it relative to a prompt -- and the location of
that prompt on the stack (both C and VM) is determined dynamically, so
the internal stack pointers would need to be readjusted (frame pointers,
etc). We can do that for the VM, because we know the stack format, but
not for foreign code.

>> Practically speaking... I think I can delimit call/cc with not much work
>> (perhaps tomorrow). But it is a visible change (if you're looking), so I
>> wanted to put this mail out there to get comments.
>
> Well, I hope that some of mine are useful.

They were indeed, thanks for your comments.

> I'm afraid I don't yet understand well enough (despite all of the
> explanation above) what the impact of this visible change would be;
> perhaps some more concrete examples would help.  But it seems a very big
> change, if it's only to produce delimited backtraces.

Yes, perhaps it would be better to use prompts for start-stack, and then
have make-stack search for prompts when narrowing its stack.

But I do think we want non-composable continuations to be delimited.
This will allow code entered at Guile's REPL, for example, to freely use
call/cc, but not capture that part of the continuation that corresponds
to the REPL itself -- because every expression entered there would be
wrapped in a prompt.

Anyway, thanks much for your comments. Let me know your reactions, and
now on to Ludo's mail :-)

Cheers,

Andy
-- 
http://wingolog.org/

Re: call/cc and recursive vm invocations

[Ludovic Courtès]

Hi Andy!

Andy Wingo <wingo@pobox.com> writes:

> In case you haven't noticed yet, if you get an error at the REPL and ask
> for a backtrace from the debugger, you get not only the frames that
> pertain to your own computation, but also frames from the REPL
> implementation itself. That's not good, and it's a regression.

It’s a regression in ‘make-stack’, right?  Can you remind me what caused
it?

> The solution is to implement start-stack for the VM. Prompts provide an
> ideal set of primitives. So start-stack can be this:
>
>   (define (start-stack tag exp)
>     (let ((prompt-tag (fresh-tag)))
>       (with-fluids ((stacks (acons tag prompt-tag (fluid-ref stacks))))
>         (% prompt-tag
>            exp
>            (lambda (k . args)
>              (apply values k args))))))
>
> This assumes some fluid is around named "stacks". Then we can implement
> make-stack:
>
>   (define (make-stack tag . narrowing)
>     (let ((prompt-tag (assq-ref (fluid-ref stacks) tag)))
>       (unless prompt-tag
>         (error "prompt tag not found quoi"))
>       (narrow-stack
>        (continuation->stack
>         (call/cc
>          (lambda (k) k)
>           prompt-tag))
>        narrowing)))

Looks nice!  :-)

> So, that's the upside. The downside of delimiting "full" continuations
> is that you can't capture the C stack.

[...]

> But of course, to each implementation its own time, and this approach to
> continuations has been nearing its expiration date for years now. Most C
> code can't deal with nonlocal exits, let alone multiple returns. So the
> utility of this construct has been limited.

Indeed.  In libguile, out of 40 ‘scm_dynwind_begin ()’ invocations, only
7 are ‘SCM_F_DYNWIND_REWINDABLE’ (and that doesn’t mean multiple returns
would actually provide a sensible result in those cases.)

[...]

> Anyway, enough about that. Practically speaking, not capturing the C
> stack means that you cannot invoke a continuation that was captured
> outside the current VM invocation.

IIUC, two things could happen (assuming ‘filter’ is a C function):

  1. Failure at ‘call/cc’-time, because the stack contains multiple VM
     invocations intertwined with C function calls.  For example:

       (filter (lambda (x)
                 (call/cc ...))
               lst)

  2. Failure at the time the continuation is invoked, because it’s
     invoked in the context of a different VM invocation than
     ‘call/cc’.  For example:

       (call/cc (lambda (k)
                  (filter (lambda (x)
                            (k ...))
                          lst)))

You were referring to case #2.  Is this correct?

[...]

> The most common causes for recursive incovations for a repl startup
> were, in no order:
>
>   primitive-load
>   load-compiled/vm
>   primitive-load-path
>   call-with-input-string (only once or so)
>   map
>   for-each
>   hash-for-each
>   scm_eval_closure_lookup (?)
>   scm_thunk_p (calls program's meta-thunk to get arity; wasteful GC-wise)
>   scm_resolve_module (calls Scheme resolve-module)
>   filter

That’s for a REPL startup, but we have lots of primitives written in C.
I’d expect a ‘call/cc’ failure to be likely in an arbitrary program.
What do you think?

> Practically speaking... I think I can delimit call/cc with not much work
> (perhaps tomorrow). But it is a visible change (if you're looking), so I
> wanted to put this mail out there to get comments. I had thought this
> was a 2.2 feature, but given the make-stack implications, I'm thinking
> it's a 1.9.9 feature. Reactions?

I’d be rather inclined to wait until 2.2.  While I agree that the
usability of ‘call/cc’ is currently limited for the reasons you gave, I
fear that doing away with the C stack capture may render ‘call/cc’ even
less usable for code that exists, mixes C and Scheme, and has been able
to work around the limitations.

I also think that we should be stabilizing things if we want to release
Real Soon Now, and that 2.2 doesn’t have to wait until 2020 anyway.  :-)

Another question is: can ‘make-stack’ be fixed in the current framework?
This would be less elegant but also less disruptive.

Cheers,
Ludo’.

Re: call/cc and recursive vm invocations

[Andy Wingo]

Hi Ludo!

On Sun 07 Mar 2010 00:23, ludo@gnu.org (Ludovic Courtès) writes:

> Andy Wingo <wingo@pobox.com> writes:
>
>> In case you haven't noticed yet, if you get an error at the REPL and ask
>> for a backtrace from the debugger, you get not only the frames that
>> pertain to your own computation, but also frames from the REPL
>> implementation itself. That's not good, and it's a regression.
>
> It’s a regression in ‘make-stack’, right?  Can you remind me what caused
> it?

It's more that start-stack didn't work, see:

    d79d908ef0c421798b79bd72403b2a8fd196173c
    373d251b4dd5153c6909898dc225d37d4948e3d6
    107139eaadab946e9713748cdeacd07b22a181db

>> Anyway, enough about that. Practically speaking, not capturing the C
>> stack means that you cannot invoke a continuation that was captured
>> outside the current VM invocation.
>
> IIUC, two things could happen (assuming ‘filter’ is a C function):
>
>   1. Failure at ‘call/cc’-time, because the stack contains multiple VM
>      invocations intertwined with C function calls.  For example:
>
>        (filter (lambda (x)
>                  (call/cc ...))
>                lst)

I thought about making this fail, but it seemed a bit petty. Also it
would preclude call/cc for the purpose of *inspecting* the continuation,
as in the make-stack case.

But of course this would work:

       (filter (lambda (x)
                 (% suitable-prompt-tag (call/cc ...) ...))
               lst)

The mechanics of defining what prompt would delimit a one-arg call/cc
are a little unspecified now; using the PLT idiom would fix that tho:

       (filter (lambda (x)
                 (call-with-continuation-prompt (lambda () (call/cc ...))))
               lst)

>   2. Failure at the time the continuation is invoked, because it’s
>      invoked in the context of a different VM invocation than
>      ‘call/cc’.  For example:
>
>        (call/cc (lambda (k)
>                   (filter (lambda (x)
>                             (k ...))
>                           lst)))
>
> You were referring to case #2.  Is this correct?

No, actually this would usually work. The problem comes when the call/cc
is not in the same VM invocation as the prompt; the location of the
continuation invocation actually doesn't matter.

To be clear:

       (call-with-continuation-prompt
         (lambda ()
           (filter (lambda (x)
                     (call/cc (lambda (k) (k x))))
                   lst)))

I don't know how to make this work, because reinstating the continuation
crosses foreign code (namely, filter).

On the other hand I can imagine avoiding a longjmp() in this case,
because the continuation is invoked within the same VM invocation as its
capture, so we can avoid messing with the C stack at all; but this
probably would not work:

       (call-with-continuation-prompt
         (lambda ()
           (filter (lambda (x)
                     (call/cc (lambda (k)
                                (filter (lambda (x) (k x))
                                        lst))))
                   lst)))

Of course, assuming filter is implemented in C.

>> The most common causes for recursive incovations for a repl startup
>> were, in no order:
>>
>>   primitive-load
>>   load-compiled/vm
>>   primitive-load-path
>>   call-with-input-string (only once or so)
>>   map
>>   for-each
>>   hash-for-each
>>   scm_eval_closure_lookup (?)
>>   scm_thunk_p (calls program's meta-thunk to get arity; wasteful GC-wise)
>>   scm_resolve_module (calls Scheme resolve-module)
>>   filter
>
> That’s for a REPL startup, but we have lots of primitives written in C.
> I’d expect a ‘call/cc’ failure to be likely in an arbitrary program.
> What do you think?

Yeah it looks like in libguile there are about 200 instances of
scm_call_*, but most of them probably aren't sensibly rewindable.

Given that call/cc is not exposed to C programs, except via the
now-internal scm_make_continuation, I don't expect breakage on the C
front; and on the Scheme front, Guile 1.8 regularized a lot of that code
by making scm_with_guile/scm_without_guile almost mandatory, and those
create continuation barriers -- so I don't see this creating many
problems from callback code.

We're just left with people capturing continuations in filter functions
&c, possible but not likely :)

>> Practically speaking... I think I can delimit call/cc with not much work
>> (perhaps tomorrow). But it is a visible change (if you're looking), so I
>> wanted to put this mail out there to get comments. I had thought this
>> was a 2.2 feature, but given the make-stack implications, I'm thinking
>> it's a 1.9.9 feature. Reactions?
>
> I’d be rather inclined to wait until 2.2.  While I agree that the
> usability of ‘call/cc’ is currently limited for the reasons you gave, I
> fear that doing away with the C stack capture may render ‘call/cc’ even
> less usable for code that exists, mixes C and Scheme, and has been able
> to work around the limitations.
>
> I also think that we should be stabilizing things if we want to release
> Real Soon Now, and that 2.2 doesn’t have to wait until 2020 anyway.  :-)

Hm, OK :) I will finish my patch today then and push it to a branch. But
let me know if you have a change of heart :)

Andy
-- 
http://wingolog.org/

Re: call/cc and recursive vm invocations

[Ludovic Courtès]

Happy septidi!

Andy Wingo <wingo@pobox.com> writes:

> On Sun 07 Mar 2010 00:23, ludo@gnu.org (Ludovic Courtès) writes:
>
>> Andy Wingo <wingo@pobox.com> writes:
>>
>>> In case you haven't noticed yet, if you get an error at the REPL and ask
>>> for a backtrace from the debugger, you get not only the frames that
>>> pertain to your own computation, but also frames from the REPL
>>> implementation itself. That's not good, and it's a regression.
>>
>> It’s a regression in ‘make-stack’, right?  Can you remind me what caused
>> it?
>
> It's more that start-stack didn't work, see:
>
>     d79d908ef0c421798b79bd72403b2a8fd196173c
>     373d251b4dd5153c6909898dc225d37d4948e3d6
>     107139eaadab946e9713748cdeacd07b22a181db

That was in Sept. 2008, but now ‘(make-stack #t)’, at least, works,
right?  (See, e.g., ‘stack->frames’ in ‘eval.test’.)

What doesn’t work is ‘make-stack’ with an argument other than #t, right?

>        (filter (lambda (x)
>                  (call-with-continuation-prompt (lambda () (call/cc ...))))
>                lst)

(For those wondering:
<http://docs.plt-scheme.org/reference/cont.html#%28def._%28%28quote._~23~25kernel%29._call-with-continuation-prompt%29%29>.)

>>   2. Failure at the time the continuation is invoked, because it’s
>>      invoked in the context of a different VM invocation than
>>      ‘call/cc’.  For example:
>>
>>        (call/cc (lambda (k)
>>                   (filter (lambda (x)
>>                             (k ...))
>>                           lst)))
>>
>> You were referring to case #2.  Is this correct?
>
> No, actually this would usually work. The problem comes when the call/cc
> is not in the same VM invocation as the prompt;

Sure, but this example doesn’t use any prompt; IOW, the default prompt
is at the beginning of the program.

[...]

>> That’s for a REPL startup, but we have lots of primitives written in C.
>> I’d expect a ‘call/cc’ failure to be likely in an arbitrary program.
>> What do you think?
>
> Yeah it looks like in libguile there are about 200 instances of
> scm_call_*, but most of them probably aren't sensibly rewindable.
>
> Given that call/cc is not exposed to C programs,

I’m also assuming that ‘call/cc’ is only ever used from Scheme.

> except via the now-internal scm_make_continuation, I don't expect
> breakage on the C front;

The examples of possible breakage above are written entirely in Scheme.

> and on the Scheme front, Guile 1.8 regularized a lot of that code by
> making scm_with_guile/scm_without_guile almost mandatory,

One is only supposed to leave guile mode when doing something that may
block, like I/O.  So you could have a C library that calls back to
Scheme without ever leaving guile mode.

> We're just left with people capturing continuations in filter functions
> &c, possible but not likely :)

I feel that this is more likely than you think.  :-)  There are all the
cases inside libguile (we can eliminate some of them but perhaps not
all, notably because it’d be a bit of work), and bindings to C library
that callback to Scheme (Guile-Avahi, Guile-GNOME I guess, etc.).

>>> Practically speaking... I think I can delimit call/cc with not much work
>>> (perhaps tomorrow). But it is a visible change (if you're looking), so I
>>> wanted to put this mail out there to get comments. I had thought this
>>> was a 2.2 feature, but given the make-stack implications, I'm thinking
>>> it's a 1.9.9 feature. Reactions?
>>
>> I’d be rather inclined to wait until 2.2.  While I agree that the
>> usability of ‘call/cc’ is currently limited for the reasons you gave, I
>> fear that doing away with the C stack capture may render ‘call/cc’ even
>> less usable for code that exists, mixes C and Scheme, and has been able
>> to work around the limitations.
>>
>> I also think that we should be stabilizing things if we want to release
>> Real Soon Now, and that 2.2 doesn’t have to wait until 2020 anyway.  :-)
>
> Hm, OK :) I will finish my patch today then and push it to a branch. But
> let me know if you have a change of heart :)

Sure, thanks!  :-)

Ludo’.

Re: call/cc and recursive vm invocations

[Andy Wingo]

Greetings!

On Sun 07 Mar 2010 17:55, ludo@gnu.org (Ludovic Courtès) writes:

> Andy Wingo <wingo@pobox.com> writes:
>
>> On Sun 07 Mar 2010 00:23, ludo@gnu.org (Ludovic Courtès) writes:
>>
>>> Andy Wingo <wingo@pobox.com> writes:
>>>
>>>> In case you haven't noticed yet, if you get an error at the REPL and ask
>>>> for a backtrace from the debugger, you get not only the frames that
>>>> pertain to your own computation, but also frames from the REPL
>>>> implementation itself. That's not good, and it's a regression.
>>>
>>> It’s a regression in ‘make-stack’, right?  Can you remind me what caused
>>> it?
>>
>> It's more that start-stack didn't work, see:
>>
>>     d79d908ef0c421798b79bd72403b2a8fd196173c
>>     373d251b4dd5153c6909898dc225d37d4948e3d6
>>     107139eaadab946e9713748cdeacd07b22a181db
>
> That was in Sept. 2008, but now ‘(make-stack #t)’, at least, works,
> right?  (See, e.g., ‘stack->frames’ in ‘eval.test’.)
>
> What doesn’t work is ‘make-stack’ with an argument other than #t,
> right?

That's correct, and the reason was that there were no delimiters
produced by start-stack, because start-stack was stubbed out.

>>>   2. Failure at the time the continuation is invoked, because it’s
>>>      invoked in the context of a different VM invocation than
>>>      ‘call/cc’.  For example:
>>>
>>>        (call/cc (lambda (k)
>>>                   (filter (lambda (x)
>>>                             (k ...))
>>>                           lst)))
>>>
>>> You were referring to case #2.  Is this correct?
>>
>> No, actually this would usually work. The problem comes when the call/cc
>> is not in the same VM invocation as the prompt;
>
> Sure, but this example doesn’t use any prompt; IOW, the default prompt
> is at the beginning of the program.

Point taken; I had assumed this expression was at the repl (which
presumably would wrap each expression in a prompt). What I mean to say
is that your case #2 will generally work but sometimes not.

Incidentally, this unfortunate situation of "generally working but
sometimes not" seems endemic to prompts, as they rely on a dynamically
bound prompt, which might not be there, and whose presence cannot be
statically checked for, AFAIK.

>> and on the Scheme front, Guile 1.8 regularized a lot of that code by
>> making scm_with_guile/scm_without_guile almost mandatory,
>
> One is only supposed to leave guile mode when doing something that may
> block, like I/O.  So you could have a C library that calls back to
> Scheme without ever leaving guile mode.

Of course. Of course it is also unlikely that said library could handle
multiple returns, unless it were specifically designed for it.

FWIW, Guile-GNOME almost always has to do the with/without dance.

Ciao,

Andy
-- 
http://wingolog.org/

Re: call/cc and recursive vm invocations

[Ludovic Courtès]

Hey!

Andy Wingo <wingo@pobox.com> writes:

> On Sun 07 Mar 2010 17:55, ludo@gnu.org (Ludovic Courtès) writes:
>
>> Andy Wingo <wingo@pobox.com> writes:
>>
>>> On Sun 07 Mar 2010 00:23, ludo@gnu.org (Ludovic Courtès) writes:
>>>
>>>> Andy Wingo <wingo@pobox.com> writes:
>>>>
>>>>> In case you haven't noticed yet, if you get an error at the REPL and ask
>>>>> for a backtrace from the debugger, you get not only the frames that
>>>>> pertain to your own computation, but also frames from the REPL
>>>>> implementation itself. That's not good, and it's a regression.
>>>>
>>>> It’s a regression in ‘make-stack’, right?  Can you remind me what caused
>>>> it?
>>>
>>> It's more that start-stack didn't work, see:
>>>
>>>     d79d908ef0c421798b79bd72403b2a8fd196173c
>>>     373d251b4dd5153c6909898dc225d37d4948e3d6
>>>     107139eaadab946e9713748cdeacd07b22a181db
>>
>> That was in Sept. 2008, but now ‘(make-stack #t)’, at least, works,
>> right?  (See, e.g., ‘stack->frames’ in ‘eval.test’.)
>>
>> What doesn’t work is ‘make-stack’ with an argument other than #t,
>> right?
>
> That's correct, and the reason was that there were no delimiters
> produced by start-stack, because start-stack was stubbed out.

OK, got it.

>>> and on the Scheme front, Guile 1.8 regularized a lot of that code by
>>> making scm_with_guile/scm_without_guile almost mandatory,
>>
>> One is only supposed to leave guile mode when doing something that may
>> block, like I/O.  So you could have a C library that calls back to
>> Scheme without ever leaving guile mode.
>
> Of course. Of course it is also unlikely that said library could handle
> multiple returns, unless it were specifically designed for it.

Yes, right.

Thanks for taking the time to explain!

Ludo’.