2010/11/16

Partial continuations and fun of stack fiddling

The 0.9.1 release will officially support partial continuations natively. The feature was added six months ago, but I finally managed to document it.

Partial continuations have been used in the continuation-based web application framework Kahua. It had a makeshift implementation of shift and reset in terms of full continuations, as shown in Gasbichler and Sperber's ICFP02 paper ( http://citeseer.ist.psu.edu/gasbichler02final.html ).

The implementation needs to copy full stack for every reset and shift, but it just worked, and it didn't seem to be a significant bottleneck. So I wasn't bothered to implement partial continuations natively.

It had come from unexpected corner. It was just a byproduct of something else.

In May I was working on a small project using Gauche, and it seemed I could write it neatly if I passed continuations among threads back and forth.

The implementation then, however, did not allow me to do that; a full continuation captured by call/cc grabs the chain of activation records; most of the elements in it were independent from the thread and the VM it was executed in. I had made so, expecting some day I'd want to invoke a continuation in different thread. However, there were a pitfall: When Scheme code is invoked from C routine, a reference to the C stack frame is recorded in the first activation record of VM. It is used to prevent the Scheme code from invoking a continuation which had become obsolete (since the C stack, on top of which the continuation was captured, could have been popped at the time the continuation was invoked.)

★ ★ ★

I tend to lose track while thinking about continuations, so let me go over my thoughts step by step. This is the initial state: a C stack ('C') at the bottom.

  C

A C routine calls a Scheme routine, and the Scheme routine calls other Scheme routines, pushing Scheme stacks ('S') into the chain of activation records.

  C <- S <- S <- S

Sometimes a Scheme routine calls back to C routine, which may in turn calls other Scheme routines. So the chain of activation records may look like this:

  C <- S <- S <- S <- C <- S <- S <- S

When call/cc is called, it creates a continuation object that keeps the pointer to this chain.

  C <- S <- S <- S <- C <- S <- S <- S
                                     ^
                               #<continuation>

When the continuation is invoked, the VM will restore this chain to the VM stack (actually, we copy activation records when a continuation is captured, but when it is invoked we directly refer activation records on heap. So there's no copy back. But that's an implementation detail.)

Now, suppose we return from the Scheme routines to the intermediate C callback. From C's point of view, it looks like it is returned from one of several APIs such as Scm_Eval.

  C <- S <- S <- S <- C

We further returns from this intermediate C frame:

  C <- S <- S

What happens if we invoke the continuation captured above here? VM can restore the chain of Scheme activation frames, since we have total control over VM stack frames. However, we cannot restore C stack frame... we can't save C stack frame totaly portably. There's a nasty technique to save C stack frames (SCM does that) but even using that, many C routines are not written in a way that function calls return more than once.

So, Gauche used to raise an error when an invoked continuation contained a reference to a C stack frame that was not in the current executing environment.

This, off course, prevented a continuation captured on one thread to be invoked on another thread, since C stack frames of the latter were totally different from the former.

However, this was unnecessarily strict limitation. What we wanted to prevent was to return to an obsoleted C stack. Even a continuation contained a reference to an obsoleted C stack, if we would never returned to it---e.g. by invoking another continuation before returning to the obsoleted C stack---we could safely execute the continuation.

  C <- S <- S

1) Captures a continuation (*)

  C <- S <- S
            *

2) Calls the continuation captured far above.  It has
 a reference to an obsoleted C stack frame (@)

  C <- S <- S <- S <- C <- S <- S <- S 
            *         @

3) Returns from Scheme routines:

  C <- S <- S <- S <- C <- S
                      @

4) Before returning to the obsoleted C stack frame, invokes
 the continuation captured by 1.  It is safe.

  C <- S <- S
            *

4') If we don't invoke the continuation(*) and the Scheme
 routine returns to the obsoleted C stack, we raise an error.

  C <- S <- S <- S <- C
            *         @

So, instead of raising an error at the step 2, we just allowed to invoke the continuation, and only checks the validity of C stack frames when we return from Scheme to C.

★ ★ ★

While pondering about this change, an idea occurred to me. What if we just never record references to the C stack frames? Instead, the first Scheme frame directly called from C routine can just have dangling end of activation record chain (indicated by 'o' below).

  o <- S <- S <- S

If a Scheme routine calls a C routine and it calls back to a Scheme routine, we make another chain.

  o <- S <- S <- S   (C-routine)   o <- S <- S <- S

The intermediate C routine knows which Scheme routine it should return to, so we can return normally even the activation chain itself isn't continuous.

This idea didn't replace the existing continuations because of other issues after all. But I realized that if we call the above (C-routine) as reset, we just get a partial continuation.

 Entering reset form:

  o <- S <- S <- S <- reset

 Executing some more expressions, then calls (shift k ...)

  o <- S <- S <- S <- reset  o <- S <- S <- S

 We capture a partial coninuation bound to k.

                             o <- S <- S <- S <- k

The actual implementation was a bit more involved, but in a couple of days we had both continuations that can be passed to another thread, and a native support of partial continuations.

Executing the amb example in Gasbichler&Sperber's paper is 3.5 times faster in this native shift/reset compared to the version emulating them with full continuations.

Tags: Continuation, shift, reset