Re: continuations and threads Jim Blandy 18 Mar 2000 19:19 UTC

> Jim> Actually, this is less powerful than what I described.  In Roland's
> Jim> system, you don't need to unwind the C stack when s1 invokes a.  You
> Jim> only need to unwind the C stack when s0 returns.  If s0 instead
> Jim> invokes some continuation b captured by s1, that's fine.
>
> I'm not sure I'm getting what's going on here:  I *want* the C stack
> to be unwound (it's a trivial-enough operation), so that the Scheme
> heap references in the C activation records get freed---you might
> get a space leak otherwise.

Here's the idea:

Assume we're avoiding gross stack-copying tricks.  We're living within
the ANSI C rules.

C frames are handicapped.  Scheme frames are not.  If we mix Scheme
and C frames, it's impossible to give call/cc its full, unfettered
power, because the continuation can capture handicapped C frames.  Our
goal is to give up as little power as possible, while still respecting
the C frames' limitations.

So, how much power to we need to give up?  Let's define the C frames'
handicap in precise terms.

- Once a C stack frame has been "destroyed", it can never be used again.
- When we destroy a C frame, all younger C frames must also be destroyed.
- Returning to a C frame destroys all younger C frames.
- The longjmp function destroys all C frames younger than the C frame
  we're setjmping to.

Let's add another restriction:

- If a C frame invokes a Scheme function, that invocation returns at
  most once.

This allows C to believe that it's only calling other C functions.
After all, if an invocation returns more than once, its frame clearly
wasn't destroyed when it returned, so it couldn't have been a C frame.

So, here's my original scenario:

The C function C1
  calls the Scheme function S1,
    which captures some continuation KS1
    and calls the C function C2,
      which calls the Scheme function S2,
      which captures some continuation KS2

So, in S2, the stack looks like: C1 S1 C2 S2
                                    ^     ^
                                    KS1   KS2

Invoking KS1 will return to somewhere within S1's code.  Invoking KS2
will return to somewhere within S2's code.  In particular, KS1 is
*not* S1's continuation --- it does *not* directly return to C1.
Similarly for KS2.

Here's the answer to your question:

If S2 invokes KS1, passing it KS2, we must not pop C2, because S1
could invoke KS2 without violating any of the C rules.  If we want to
preserve as much power for call/cc as possible, we must allow this.

Furthermore:

Suppose S2 returns to C2, and C2 returns to S1.  S1 may still invoke
KS2 without violating any of the C rules, so we must allow that.
However, if S2 tries to return again, we signal an error, because that
would be a violation of the C rules.

Or, alternatively:

S2 could invoke KS1, and S1 could return to C1.  At this point, C2
must be destroyed.  Later code may still invoke KS1 or KS2 without
raising an error, but if either S1 or S2 return a second time, we
signal an error.

To implement this:

When you call Scheme from C, represent the Scheme function's
continuation by an object with indefinite extent, and arrange to mark
it as invalid whenever the underlying C frame is destroyed, whether by
being returned to or via a longjmp.  You'll need a wrapper around
longjmp to make it work right.