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 <address@hidden> writes:

> Andy Wingo <address@hidden> 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/