Re: call/cc and recursive vm invocations

[Andy Wingo <wingo@pobox.com>]

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/