Fun with Continuations Blog

Version 2


    Imagine that your program is an object. Yes, the whole thing -- the memory, program counter, code, and call stack. What is possible when you have access to this object? What kind of abstractions can you build?

    We don't have to look far for an answer. Operating system designers have to think about this question. In an operating system, a process is an object. Each process has its own memory, program counter, code space, and call stack. The operating system is free to start, stop, and restart the processes under its control.

    Operating system designers build abstractions from this. The operating system remembers which processes are waiting for which things. When the wait is complete, the operating system restarts the proper process. Processes trying to read from a socket sleep until data is available. Paused programs as objects make this common idiom possible.

    This is great for operating systems, but what about user-land?Continuationsare the answer here. A continuation is a fancy name for an object that references a paused function. This object has the data, program counter, code, and call stack for the paused function. A paused function continues from its last point of execution when called.

    Here I introduce continuations and abstractions that you can build with them using the Sleep scripting language. Continuations are a powerful tool for creating new types of flow control, for inverting control, and even as a tool for manipulating live programs as data.

    Sleep Basics (Syntax and All That)

    Sleep is a Perl-inspired language for the Java platform. No surprise here, Sleep syntax borrows heavily from Perl. Sleep also supports "first-class" functions and continuations. A feature is first-class if a programmer can pass, assign, and manipulate it. Sleep functions are akin to class definitions in Java. A block of code is a template for one or more function objects. Each instance of a function has its own variable scope and a shared pointer to the compiled code. Sleep uses paused functions as continuation objects.

    This example demonstrates the syntax for anonymous functions. I represent an anonymous function with an inline block of code. The&lambda function creates a new instance of the anonymous function.

    $function = lambda({ println("Where's $1 $+ ?"); }); @args = @("Waldo"); invoke($function, @args); 

    This example outputs Where's Waldo? and demonstrates function arguments. Sleep numbers arguments from$1 to $n. The array @_contains all anonymous arguments. Scripts can also pass named arguments with the $variable => valuesyntax.

    Scripts declare a named function with the subcommand. Named functions refer to the same function instance. A reference to the named function is available as&functionName. Now that you understand Sleep functions, we can discuss continuations. Sleep functions pause themselves and pass control with the callcccommand.

    sub foo { println("I am foo! w/ $1"); return "foo: " . invoke($1); } sub bar { println("Enter the bar"); callcc &foo; println("Leave the bar"); return "bar value"; } println("output--" . bar()); 

    This example illustrates the weird flow control possible with continuations. Here is the output.

    Enter the bar I am foo! w/ &closure[]#16 Leave the bar output--foo: bar value

    The program starts by printing the return value of&bar. The &bar function does acallcc to &foo. Readcallcc as "pause this function and call the specified function with the continuation of the current function as a parameter." When called, &foo prints a value and invokes the paused &bar to build a return value. The print statement that called &bar ends up with the return value of &foo. callcc is like a functional goto, passing control from one function to another.

    Coroutines and Continuations

    A coroutine is a function that pauses and returns a value. On the next call the coroutine resumes from its last execution point. Programming languages with this ability use the yieldcommand to pause and return a value. Continuations are more general than coroutines and you can add the coroutine feature with them. Sleep supports the yield command, but for fun here is a callcc implementation of yield. Note: I name the function &yield2 to avoid conflict with the built-in yield command.

    inline yield2 { callcc lambda( { return $value; }, $value => $1); } 

    I use an inline function to hide the details of theyield implementation. The ability to abstract continuations is key to using them. Sleep inline functions execute as if they are part of the parent function. Within an inline function, callcc and return affect the calling parent.

    This code shows a generator function and how to iterate over it. Each call to a generator returns the next value in a sequence.

    sub range { # Returns a generator that returns the next number in # the range with each call. return lambda({ local('$counter'); for ($counter = $begin; $counter <= $end; $counter++) { yield2($counter); } }, $begin => $1, $end => $2); } foreach $value (range(8, 13)) { println($value); } 

    This example displays the following output:

    8 9 10 11 12 13

    Now you understand the basics of continuations. From this point on, I'd like to share some fun tricks with continuations. We'll start with the inversion of control abstraction.

    Inversion of Control

    Some software abstractions require user code to call into a library, receive a result, and then go on its merry way. The burden of making decisions about when to do things is placed on the caller. The inversion of control abstraction lets callers provide code to call in response to events. In this way, flow control is inverted from the caller to the callee. Event-driven programming is an example of inversion of control. Inversion of control becomes messy when the caller must track state and respond differently to each event. Continuations allow a request and respond imperative style for response code. I will show you how to use continuations to hide inversion of control. Here I will show how to use continuations as the mechanism to track state.

    Here is the client handler code for a chat server. It is written in a request and respond style.

    debug(7); include(""); sub handleClient { local('$socket $name $message'); $socket = $1; try { println($socket, "What is your name?"); readLine($socket, $name); writeAll($socket, "$name joined the chat!"); while (1) { readLine($socket, $message); writeAll($socket, "$name $+ : $message"); } } catch $error { writeAll($socket, "$name left the chat"); closef($socket); } } startServer($clientFunction => &handleClient); 

    Notice anything about the code? It is to the point. Imagine writing something like this in Java. Not too hard. You would probably use threads. Imagine writing this without threads as a listener for an event-driven network programming library. I'll discuss why you want this later.

    The abstraction for this server depends on&readLine, &writeAll, and&startServer. In the next section I implement these with a polling I/O implementation. Figure 1 shows a typical chat session using telnet as a client.

    The Chat Server in Action
    Figure 1. The chat server in action

    Polling I/O

    The library supports several connections that must communicate with each other. This library requires two threads total and supports as many connections as your CPU and memory will allow.

    The library shares an array of connections and a lock between the current thread and the polling thread. I use the lock to protect access to the shared connections list. If Sleep supported a non-blocking version of &listen I could build this example using a single thread and no locks.

    global('@connections $lock'); $lock = semaphore(1); 

    &startServer accepts a generic client handler function as a parameter. It spawns a thread to poll and process all active connections. The current thread loops and listens for new connections.

    sub startServer { local('$server'); fork(&pollConnections, \@connections, \$lock); while (1) { $server = listen(8888, 0); invoke(lambda($clientFunction), @($server)); } } 

    Recall that our example client handler sends a message to the client with &println. Its first order of business is getting a user name from the client. Scripts using this polling I/O library call &readLine to read from a client.&readLine is an inline function that hides acallcc.

    &readLine uses callcc to pause the client handler function and save it to the connections list. Each entry in the connections list is an array. This array holds the handle, the continuation of the client handler that called&readLine, and the arguments to use when calling the continuation later. I save the arguments I want later because resuming the continuation will overwrite anonymous arguments.

    When a client handler resumes, it continues execution in the last part of &readLine. This is where the text is actually read. If the handle is disconnected,&readLine will throw an exception.

    Here is the code to &readLine:

    inline readLine { callcc lambda( { # add an array to our connection list: # 0: the handle # 1: the continuation of the client # 2: arguments to reinvoke the continuation with acquire($lock); push(@connections, @($handle, $1, $args)); release($lock); }, $handle => $1, $args => @_); if (-eof $1) { throw "disconnected!"; } else { $2 = readln($1); } } 

    &startServer created the polling thread from the &pollConnections function. The polling thread loops forever assigning the result of &select to a variable. &select returns a disconnected or ready to read connection. The polling thread extracts the stored handle, associated continuation, and extra arguments from the variable. It then invokes the continuation of the client handler.

    Here is the code for &pollConnections.

    sub pollConnections { local('@client $socket $continuation $args'); while @client (select()) { ($socket, $continuation, $args) = @client; invoke($continuation, $args); } } 

    For completeness, I include the code for the&select function. I use semaphores in this function to protect the integrity of the @connectionsvariable shared between the listener and polling thread. The first time a client handler calls &readLine is in the listener thread. Subsequent calls to &readLine by a client handler occur from the polling thread.

    sub select { local('@client $handle $continuation $args'); while (1) { acquire($lock); foreach @client (@connections) { if (available(@client[0], "\n") || -eof @client[0]) { remove(); release($lock); return @client; } } release($lock); sleep(50); } } 

    Now let's go back to the process analogy. Think of each client handler as a cooperative thread. This example is not different from how an operating system manages processes with blocking calls. Of course, a thread is just a lightweight process. With continuations, you have the power to create these abstractions that operating system designers have provided all along.

    You may think this is silly right about now. After all, we can use Java threads to implement this behavior. Each thread makes a blocking call to read data and resumes when the data is available. And one thread per client allows each thread to track state implicitly. Ignoring the issues of protecting shared data between multiple threads, what is the value of this?

    Well, imagine that the connection we're tracking state for is not persistent like a TCP/IP connection. For example,&startServer could start a web server that creates a new client handler for each session. Here&readLine would flush any data to the client's browser and pause the current session. The next time the user makes a request, &readLine would resume execution and provide the session code the latest form data from the user. This is the conceptual basis of those new-fangled continuation web servers we keep hearing about.

    Continuations allow you to hide inversion of control in places where threads are inadequate. After all, a continuation can be thought of a user-level thread with no preemption.

    Serialization of Continuations

    What is the point of thinking of a continuation as a user-level thread? What can a continuation possibly offer that threads can't? In Java, most objects are serializable. What is possible when threads are serializable?


    One option is fault recovery through checkpointing. Checkpointing saves state so you can restore it after something bad occurs. Think of it as a "save game" feature. Sleep scripts can implement checkpointing with continuations. The trick is to serialize the continuation. The inline function&save pauses the caller, writes the continuation to the state.bin file, and then resumes the caller. Sleep uses &writeObject to serialize objects to a handle.

    inline save { callcc { # save the continuation local('$handle'); $handle = openf(">state.bin"); writeObject($handle, $1); closef($handle); # continue execution of our paused function. return invoke($1); }; } 

    This next example is a hypothetical caller of the&save function. Just like a video game, this function calls &save occasionally.

    sub doBigCalculation { local('$x $result'); for ($x = 0; $x < 7; $x++) { $result = $x + $result; # intense, I know. println("result[ $+ $x $+ ] = $result"); save(); sleep(1000); # simulate long running calculations } return $result; } 

    If the program exits from unforeseen circumstances, you can restore it later. This next example is the preamble to the hypothetical caller. If the state.bin file exists, it will read an object from the file and delete it. I assumestate.bin contains a serialized continuation written by the &save function. Once these steps are complete, I set the named function&doBigCalculation to the continuation that was just read in.

    For the curious, the total size of the saved continuation object in this example is 3.9 KB. I can get it down to 1.7 KB with GZip compression. Here is the restore code:

    # attempt to restore our state (if it exists) if (-exists "state.bin") { $handle = openf("state.bin"); $restore = readObject($handle); closef($handle); deleteFile("state.bin"); setf('&doBigCalculation', $restore); } 

    The final step is to actually execute the hypothetical caller. Here is the code:

    $value = doBigCalculation(); println("Done: $value"); 

    And this is the output to this example. I simulate disaster with an occasional Ctrl-C to stop the program.

    java -jar sleep.jar result[0] = 0 result[1] = 1 result[2] = 3 $ 
    java -jar sleep.jar result[3] = 6 result[4] = 10 $ 
    java -jar sleep.jar result[5] = 15 result[6] = 21 Done: 21

    Now that you can save a continuation to a file, what about writing it to a socket?

    Mobile Agents

    Programs that move from computer to computer are mobile agents. Agent programming is a paradigm for distributed computing. Each agent performs some action independent of the others. Clever programmers will create a generic agent with a class of functionality and customize each instance with parameters on deployment. In this way, you get a lot of functionality with little code.

    Here we will implement mobile agents with Sleep functions. This next example is an agent that visits two machines, finds all users they have in common, and returns home with the data. To function properly, this program includes the agent library The &move function relocates the agent and &sendAgent sends an agent to a host.

    include(""); sub CommonUsersAgent { local('@usersA @usersB @users'); move($systemA); @usersA = map({ return split(':', $1)[0]; }, readAll(openf("/etc/passwd"))); if (size(@usersA) > 0) { move($systemB); @usersB = map({ return split(':', $1)[0]; }, readAll(openf("/etc/passwd"))); # set intersect operation on user lists @users = retainAll(@usersA, @usersB); } # make these two lists null, no need to move them (@usersA, @usersB) = $null; move($home); println("Common Users on $systemA and $systemB are:"); printAll(@users); } sendAgent("", lambda(&CommonUsersAgent, $systemA => '', $systemB => '', $home => '')); 

    Surprise, surprise! The inline function &movehides a callcc. &move pauses the current function and calls &sendAgent with the continuation as a parameter. This function is like the checkpointing example. It writes a continuation to a handle. In this case, the handle is a socket rather than a file.

    The agent library defines &sendAgent and&move as:

    sub sendAgent { local('$handle'); $handle = connect($1, 8888); writeObject($handle, $2); closef($handle); } inline move { callcc lambda({ sendAgent($host, $1); }, $host => $1); } 

    Code that moves around a network unchecked is a scary thought. Fortunately, agents can't hop from computer to computer arbitrarily. These agents require a server to receive and execute them. This server is called "middleware" because it sits between the agents and the host operating system.

    The Sleep agent middleware is an infinite loop. It listens for clients on port 8888. When a client connects, a serialized continuation is read in and the handle is closed. The middleware then resumes the connection in its own thread. Here is the code for the middleware. Note that I did not address security in this example.

    include(""); while (1) { local('$handle $agent'); $handle = listen(8888, 0); $agent = readObject($handle); closef($handle); fork({ [$agent]; }, \$agent); } 

    Now we have the code. Let's see this in action. In this example, the agent middleware is running on,, and The agent starts at home. Figure 2 shows the migration path of the agent between foo, bar, andhome.

    Agent Migration
    Figure 2. Migration path of the common users agent

    Here is the output of the agent middleware onhome.

    [raffi@home ~]$ 
    java -jar sleep.jar Common Users on and are: root bin daemon adm lp uucp ftp nobody

    I've shown you how to create abstractions that we take for granted. I've hinted at how continuations can aid recovery of failed systems. And now I've shown mobility. Why does this matter?

    The Next Frontier: Going Distributed

    There is chatter in the community about concurrent computing. A lot of us are looking for solutions to build scalable and dependable systems. A secondary (or primary) goal is to build these systems without complexity. With continuations, you can create systems that borrow many of the idioms we use now. Thinking of your programs as data opens up many possibilities. The Canadian media guru Marshall McLuhan once said:

    "We become what we behold. We shape our tools and then our tools shape us."

    If this isn't fun, I don't know what is.


    The examples from this article are available in ready-to-run form at:

    Are you interested in learning Sleep after all these fun examples? These sites will help you with the Sleep language.

    Support for continuations isn't rare in the JVM language world. Serializable continuations is another story. To my knowledge, JavaScript, Scheme, and Sleep are the only JVM languages with this support. The ideas from this article should port to these languages.