continuations in the VM

Or, how to finish a job twice.

Or, anything worth starting is anything worth starting is anything worth starting is anything worth starting is ...

Introduction

A continuation, simply put, is a reference to the rest of some program P, as of some given point in the midst of P. It is an interesting design problem to introduce continuations into the JVM. I don't know of a full design for JVM continuations, yet, but it's possible to observe both the easy and the hard parts, and to survey some of the reasons we should care.

More specifically, in a language with statements and procedure calls, a continuation at a given statement M.S within a procedure M consists of an indication of the statement after S. If M was called from another procedure N at a statement N.T, then the continuation also includes an indication of the statement after N.T, and so on down to some primal call. Adding expressions complicates the account superficially; it is as if the expressions were broken up (with temporaries) so that each expression contains at most one call statement, and the call statement (plus assignment of its value) is the last action in the expression.

The structure of a continuation, therefore, is much like the backtrace you see in a debugger. Unlike a debugger, continuations are not generally created between any two instructions, but at predetermined points. As with a debugger, you can issue a command to continue from a continuation. As a decisive difference from debuggers, a continuation is not literally a suspended computation state, but is rather a recorded copy (or virtual copy) of one. Your application can continue on its way, pushing and popping the control stack, perhaps recording new continuations. At some later point, if a saved continuation is resumed, the application drops what it is currently doing and continues from that saved point... with the old backtrace.

A method that resumes a continuation abandons its future execution, and the the future of each of its callers, all the way back to some boundary state that the continuation and the caller share in common. This is very similar to a non-local jump: Throwing an exception make the current method exit, and forces its callers also to abandon their normal executions. The boundary state in this case is the catch block which receives the exception. (We will talk about try/finally blocks later.) What is different about continuations is that they can “throw” downward and sideways also. Resuming a continuation in general unwinds the stack back to a shared state and then restores a bunch of stack frames.

It is almost as if the saved continuation were being held by a suspended thread somewhere, and when it is invoked, the current thread gives up all claim to its future, passing all execution responsibilities to the suspended thread. This allows continuations to implement (or simulate) coroutining structures, where method entry and exit are not rigorously paired bracket operations, manageable by a control stack. Continuations are not equivalent to coroutines (or generators), because a coroutine can yield control to another coroutine without losing its own future; the other coroutine eventually yields control back. But the difference is not huge, since you can always record a new continuation and save it somewhere for the next yield, just before invoking an old one. In fact, threading packages (“green” style) have been built on top of continuations. Building coroutines and threads from continuations is actually efficient if stacks can somehow be switched by altering a few registers. This becomes straightforward if stack frames are allocated on a heap (at which point we start calling them activation frames). It is more painful on ordinary C-style stacks, where resumption requires overwriting the control stack with new bits.

You may have noticed that continuations can simulate an interesting variety of control flow patterns. In fact, they seem to be a universal primitive for building single-threaded programming constructs. Since Sussman and Steele’s famous Lambda Papers and specifically Guy Steele’s Rabbit thesis, optimizing compilers use the continuation passing style to represent and transform all kinds of (localized) control flow. In a compiler’s intermediate representation, a continuation can reify (make concrete) the control flow of a program as just another data value. The result is such flexibility and precision that no other representation of control flow is necessary. For example, an if statement turns into an expression which selects one of two continuations and jumps into it. The actual selection involves no control flow, so all the control flow happens via the continuations themselves.

Continuations native to the JVM

Most runtime systems provide only limited access to the control stack or to the intended future of a computation. Typically, the high water mark is some ability to abort a computation back to some cut point (a longjump or exception throw). Some languages also allow a certain amount of stack introspection. The JVM was designed with such features, but not with full continuations in mind. It is time to consider how to add them in, now that the JVM is being used as the substrate for a variety of languages. There is a very good thread on the JVM languages group, CPS languages in Java which discusses various tactics for emulating continuations on the JVM. In this note we will think about low-level extensions to the JVM itself, to remove the need for difficult workarounds.

The essential primitive operations read and write the control stack as a whole. An API which is sufficient for this would include a copyStack method and a resumeStack method. Because of the security loopholes in these operations, they must be highly privileged. In a prototype, I have placed them in an internal class called sun.misc.Unsafe, which already supplies risky operations like reading and writing bytes to arbitrary addresses. The API looks like this:

// low-level hook, to be wrapped in one or more safe APIs:
class sun.misc.Unsafe;
public native
Object copyStack(Object context, CopyStackException ex)
    throws CopyStackException;
public native /\*unreached\*/
void resumeStack(Object stack, Object value, Throwable exception);
public static
class CopyStackException extends RuntimeException {
    /\*\* The JVM state, in an implementation dependent format. \*/
    protected Object stack;
}
public native
void doCopyStackContext(Object context, Runnable r);
A call to copyStack captures a snapshot of the current thread, places it into the given exception, and throws that exception. The caller may choose to catch it immediately, or let someone up the call-chain catch it. The normal return value (typed as a simple object) does not come into play at first. If and whenever the captured thread snapshot is resumed, the function returns normally, with whatever value the resumer provides, or (again) throws an exception, with whatever throwable the resumer provides. This can happen any number of times. Thus, we distinguish between the initial call to copyStack, and any number (zero or more) of returns from copyStack.

If the context argument to copyStack is null, the captured thread state specifies all frames of the current thread. Otherwise, the context must correspond to a live call (in the same thread, not yet returned) to doCopyStackContext. The captured JVM state then specifies only stack frames which are younger than that call to doCopyStackContext. It is an error for a resumed computation to attempt to return to that call to doCopyStackContext. The context is stored into the supplied CopyStackException, which must not already have a stored context. (That is, its stack field must be null.)

The basic idea is simple and powerful: An application can control its own continuation on the JVM by reading and writing its own thread stack, or recent sections of its thread stack.

A stack of difficulties

As a wise webslinger once said, with great power comes great responsibility. A corollary in this case is that great power can blow a limb off. That is why the above primitives are in a class named “unsafe” with limited access.

For example, try/finally blocks are usually enforcing a program invariant that depends on paired brackets. The finally clause cleans up something (a close bracket) set up earlier (as an open bracket) near the try. When continuations are introduced, if a method exits twice (say, once to checkpoint, and once later after it is done), then the close bracket will happen twice, mismatching with a single open bracket. Language with continuations deal with this by requiring the programmer to express a three-part initially/try/finally structure, so then when control re-enters the block, the initially action has a chance to re-assert the open bracket. Retrofitting this to the JVM will be challenging.

Locals in the JVM are part of the continuation. This means that when a program returns to an earlier state, the locals will assume their old values. This might be surprising. Languages in which continuations are native work with this fact by moving mutable variables to the heap (boxing them, in effect). In this way, their state is independent of the thread stack, and of any continuations built from it.

Uncontrolled introspection of thread state is a huge security loophole. If I am able to build an inspectable continuation, and I can convince a privileged routine to call me (as a callback or even handler), then I can use the continuation to look at the local variables of the privileged routine, perhaps revealing secrets like passwords. If I can invoke the continuation, I can also forge a clever copy (and here I use the word “forge” in its dark sense) of the privileged routine, and perhaps restart it on values of my choosing. The unsafe continuation API presented here allows all this, and it therefore badly needs to be tamed by a suitable security model.

Applications

Let’s quickly overview some of the applications of this design for continuations.

Reification

The JVM reveals the stack state as an explicit object, which (as we say) reifies the stack state (which was only implicit before). The object is placed by the JVM in CopyStackException.stack. (This is a protected field; the encapsulation prevents random exception handlers from accessing the state.) This object will be be given an API which allows the application to inspect the state of the stack as a whole, and each stack frame. This includes locals, stack, monitors, current method, and BCI (bytecode index within method).

In the first prototype, the object happens to be is an array of objects, starting with a byte array of serialized structure information. Indexes in the serialization call out to other elements of the object array. The format is non-opaque, and allows new JVM stack states to be created from whole cloth, supporting a low-level form of thread mobility. Previously captured states can be modified, supporting advanced performance tuning or configuration management, as Hotspot does internally at present. This simplicity is appealing, but requires stack frames to be parsed and unparsed into the external representation, always. A more tightly coupled representation could have more opaque handles to JVM data, with less representational distance to live stack frames. It could still be unparsed when the occasion arises.

Inspection

Given reification, it is then simple to write browsers and reporte generators which walk the stack and present its contents.

Intercession

If the reificiation can be copied, adjusted, or forged from raw materials, then the resumeStack operation can put any contents whatever into the stack. If inspection is a read-only operation, intercession is the powerful update operation.

Migration

If a continuation can be forged from raw materials, it follows that, with suitable mechanisms for serialization, a computation can save itself to disk or network, and be picked up again in a different process or network node, to be continued there. There are big problems defining the edge of the computation, ripping it apart on serialization, and sewing it together again in the new location. But the problem is worth solving. (For a use case, consider that this is how the Second Life engine works.) Serializable reification provides the hook for relocating a much wider range of JVM computations.

Local migration is an interesting case also. As computers get larger and larger, the illusion of uniform memory gets fainter and fainter. Increasingly, threads will need to follow data. (When? Compare the bandwidth to move a thread with the bandwidth required to move the data it works on. It will sometimes be cheaper to ship the thread to the data than vice versa.) In this case, the movement could occur within a single space of managed objects, so serialization won’t be part of the migration sequence.

Generators

A generator is a small coroutine with a loop coupled to a caller’s loop in such a way that as the subroutine loop yields values, they are presented to the caller loop as an interation space. Generators are often compiled in a continuation passing style, so that they can be run on the caller&rqsuo;s stack. This can put limitations on the code of a generator. With limited continuations on the JVM, a generator could be compiled to normal code that natively coroutines (by switching continuations) with the caller loop. The limited switching never leaves control of the block containing the loop, and this condition can be naturally represented by a doCopyStackContext block. The generator and client continuations will contain only a couple of frames. We should be able to arrange things so that the JIT can see the whole thing, unfold the continuations at compile time, and generate the normal straight-line code for producing and consuming each generated value.

Coroutines

More generally, scoped coroutines are subroutines which run inside a parent block, passing control back and forth, but never leaving the block (except to exit the overall computation). This also can be represented in the JVM by contextual continuations.

Proper continuations

The Scheme language has a specific function (call/cc) to form a handle to the program’s continuation. This handle is opaque; it can only be invoked, not inspected. It allows the thread’s entire computation to be reset back to the execution state (of the control stack) where the continuation was formed.

This has been used in the past to implement large-scale coroutines, which behave like monoprocessor threads (aka “green threads”). It is more commonly used in Scheme for generator-like control structures. (And for brain-cracking code puzzles—enough said.)

User sessions

Third use case: Some programming frameworks for Java, notably RIFE, use continuations as a natural notation for web sessions and other intermittent or restartable processes. They current do this by transforming Java bytecodes into a stackless format. There would be less need for bytecode rewriting if the JVM stack did not get in the way, and editable continuations seem the likely native expression in the JVM of such patterns.

Reoptimization

At the level of a language runtime, reified continuations can provide a hook for the language runtime to refactor the programmer’s computations on the fly. For example, if a method is never overridden, it can be called directly (and perhaps inlined). If during a long loop, the method is overridden by class loading, the code might need to be adjusted to call a dispatch routine. In general, this requires rewriting stack frames. HotSpot has done this for a decade; we call the backoff process deoptimization. The first prototype of copyStack took a day or two to write, because it just exposed the underlying reification mechanism (written in C++) needed for reading and writing stack frames.

Beyond the problems of Java reoptimization, there is a big world of higher level optimizations. For example, a loop can be optimized very differently depending on the size of its iteration space; some language implementors may choose (like HotSpot itself) to wait until the application warms up, and then refactor it on the fly to (say) use a parallel algorithm for a large, important loop.

What’s next?

I have posted an initial version of JVM continuations in the mlvm project. HotSpot bug 6655643, “some dynamic languages need stack reification” tracks this line of investigation.

Lukas Stadler (at Johannes Kepler University) has gone much farther, implementing resumption of continuations. He will be updating this patch soon. A recent update from Lukas gives an idea of where he is headed. I expect we can turn the power on, soon.

Comments:

Thank you for your series of very interesting articles John. A newbie question I've had for a long time and googled for without finding any answer - what happens to changed mutable objects on the heap when we go back to an earlier continuation? Do we have some sort of hidden copy-on-write in the VM so the original values get saved away like your boxed local variables, or do we let them be changed and let the programmers handle it? Or am I thinking on completely the wrong level here...

The reason I wonder is that when I first read about continuations it was always in the context of web multipage-flow frameworks, and I wondered how how the saving of all these program state snapshots for all different users could be implemented without being expensive memorywise.

Posted by Lars Westergren on May 04, 2008 at 09:20 PM PDT #

Sorry. Never mind previous question... as usual I found the answer once I looked more carefully.
http://keithdevens.com/weblog/archive/2004/Jul/11/continuations

Posted by Lars Westergren on May 04, 2008 at 09:47 PM PDT #

Re: "Locals in the JVM are part of the continuation."

Sounds like a bug.

Posted by Neal Gafter on May 05, 2008 at 12:33 AM PDT #

Melding continuations with try/finally or more generally dynamic-wind has been solved by Matthew Flatt. If you haven't read it yet, http://www.cs.utah.edu/plt/publications/icfp07-fyff.pdf Adding Delimited and Composable Control to a Production Programming Environment</a> is very insightful.

Posted by Kevin Tew on May 05, 2008 at 01:29 AM PDT #

John, copying would be a huge overhead if many stack frames as part of the continuation state.

Have you considerered switching the stack to another one and protect managed <-> native transitions to restore the original one?

It would make for a constant time yield with the disavantage of a bit slower transition to unmanaged code.

Besides that, how you plan on handling native frames (either VM or user) during copyStack?

Posted by Rodrigo Kumpera on May 05, 2008 at 03:57 AM PDT #

Excellent article. A few ideas that sprung up after reading it:

Let's say the call stack contains 26 methods - A calls B, calls C, all the way up to Z. Only method Z does continuation-related stuff, A-Y do nothing of the sort.

When Z sets up a continuation, you still have to turn all mutable variables of A-Y into heap-allocated stuff. Imagine that Y calls Z twice; once in Y's middle, and Y when Y is 3/4ths done. Between the two calls, Y changes a local variable.

Unfortunately A-Y can't know at compile time that Z might do something with continuations.

Conclusion: \*ALL\* non-final local variables must go to the heap just in case.

Seems bad. However, hotspot can eliminate quite a lot of it. For example, any local variable which does not change value after the first method call done by the method since the creation of the value - does not need to go on the heap; it is 'final' as far as continuations are concerned.

Still, this leads me to my second point:

continuations are tres cool. In making the JVM better at being a platform for many languages, they are required. However, we can get quite a ways, without nearly as many problems, and without nearly as many issues for the current design of java (the language, not the VM), if only coroutine-style continuations are implemented. In other words: When you create a continuation, you must also immediately restore another continuation. You are not allowed to continue running your code. This saves a lot of hassle, and you can still do 95% of the useful things you can do with continuations.

Both chaoticjava.com and what RIFE does amount to hacking bytecode to do essentially that - continuations, yes, but the act of creating the continuation is immediately followed by termination of that stack frame's execution.

A final glimpse into perhaps a far off future: Software Transactional Memory requires logging all changes to any variables. Imagine we had this in java/JVM. You could now add a second method to continuation.goto(): continuation.restore(). The second method will undo everything that happened since the creation of the continuation - including restoring the state of attributes and not just local variables. Useful? Don't know. Lots of hurdles to jump over before you can actually make that work right? Yes. Still, kinda cool, if you think about it.

Posted by Reinier Zwitserloot on May 05, 2008 at 02:39 PM PDT #

It isn't necessary to copy stacks, or to put all activation frames on the heap. If you disallow continuation reentrance (and I don't know of any use of continuation reentrance other than the usual demonstrations of the power of continuations) then you can just treat call/cc() as a stack fork function.

Posted by Nico on May 07, 2008 at 03:05 AM PDT #

This is how we add migratable continuations to Mono for the Second Life scripting engine:

http://blog.secondlife.com/2006/05/05/microthreading-mono/

Here's a video of us talking about it at Lang.NET:

http://download.microsoft.com/download/9/4/1/94138e2a-d9dc-435a-9240-bcd985bf5bd7/Jim-Cory-SecondLife.wmv

Posted by Babbage Linden on May 19, 2008 at 11:31 PM PDT #

Another really nice paper for implementers is Clinger et al's "Implementation Strategies for First-Class Continuations" [http://www.springerlink.com/content/h5808n962434j275/fulltext.pdf].

--Dave

Posted by Dave Herman on October 02, 2008 at 07:05 AM PDT #

Please guide me on how we can implement the continuations in other languages like Scala.

Posted by guest on February 27, 2012 at 10:41 AM PST #

Post a Comment:
  • HTML Syntax: NOT allowed
About

John R. Rose

Java maven, HotSpot developer, Mac user, Scheme refugee.

Once Sun and present Oracle engineer.

Search

Categories
Archives
« April 2014
SunMonTueWedThuFriSat
  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
   
       
Today