Skip to main content

Fun with Continuations

July 24, 2008

{cs.r.title}







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?
"http://en.wikipedia.org/wiki/Continuations">Continuations are
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.

[prettify]$function = lambda({
   println("Where's $1 $+ ?");
});

@args = @("Waldo");
invoke($function, @args);
[/prettify]

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 => value
syntax.

Scripts declare a named function with the sub
command. 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 callcc
command.


[prettify]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());
[/prettify]

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

[prettify]Enter the bar
I am foo! w/ &closure[example.sl:9-13]#16
Leave the bar
output--foo: bar value
[/prettify]

The program starts by printing the return value of
&bar. The &bar function does a
callcc to &foo. Read callcc 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 yield
command 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.


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

I use an inline function to hide the details of the yield
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.


[prettify]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); 
} 
[/prettify]

This example displays the following output:

[prettify]8
9
10
11
12
13
[/prettify]

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.


[prettify]debug(7);

include("pollio.sl");

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);
[/prettify]

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 pollio.sl 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.


[prettify]global('@connections $lock');
$lock = semaphore(1);
[/prettify]

&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.


[prettify]sub startServer
{
   local('$server');

   fork(&pollConnections, \@connections, \$lock);

   while (1)
   {
      $server = listen(8888, 0);
      invoke(lambda($clientFunction), @($server));
   }
}
[/prettify]

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 a
callcc.

&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:


[prettify]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);
   }
}
[/prettify]

&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.


[prettify]sub pollConnections
{
   local('@client $socket $continuation $args');

   while @client (select())
   {
      ($socket, $continuation, $args) = @client;
      invoke($continuation, $args);
   }
}
[/prettify]

For completeness, I include the code for the
&select function. I use semaphores in this
function to protect the integrity of the @connections
variable 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.


[prettify]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);
   }
}
[/prettify]

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?

Checkpointing

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.


[prettify]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);
   };
}
[/prettify]

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


[prettify]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;
}
[/prettify]

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 assume
state.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:


[prettify]# 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);
}
[/prettify]

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


[prettify]$value = doBigCalculation();
println("Done: $value");
[/prettify]

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

[prettify]$ <b>java -jar sleep.jar calc.sl</b>
result[0] = 0
result[1] = 1
result[2] = 3
$ <b>java -jar sleep.jar calc.sl</b>
result[3] = 6
result[4] = 10
$ <b>java -jar sleep.jar calc.sl</b>
result[5] = 15
result[6] = 21
Done: 21
[/prettify]

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 "http://en.wikipedia.org/wiki/Mobile_agents">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 in
agentlib.sl. The &move function
relocates the agent and &sendAgent sends an agent
to a host.


[prettify]include("agentlib.sl");

sub CommonUsersAgent
{
   local('@usersA @usersB @users');

   move($systemA);
   @usersA = map({ return split(':', $1)[0]; }, 
                        readAll(openf("/etc/passwd")));

   if (size(@usersA) &gt; 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("127.0.0.1", lambda(&amp;CommonUsersAgent,
                        $systemA =&gt; 'foo.example.net',
                        $systemB =&gt; 'bar.example.net',
                        $home    =&gt; 'home.example.net'));
[/prettify]

Surprise, surprise! The inline function &move
hides 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:


[prettify]sub sendAgent 
{ 
   local('$handle'); 
   $handle = connect($1, 8888); 
   writeObject($handle, $2); 
   closef($handle); 
} 

inline move 
{ 
   callcc lambda({
      sendAgent($host, $1); 
   }, $host =&gt; $1); 
}
[/prettify]

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.


[prettify]include("agentlib.sl");

while (1) 
{ 
   local('$handle $agent');

   $handle = listen(8888, 0); 
   $agent = readObject($handle); 
   closef($handle); 

   fork({ [$agent]; }, \$agent); 
}
[/prettify]

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

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

Here is the output of the agent middleware on
home.

[prettify][raffi@home ~]$ <b>java -jar sleep.jar mw.sl</b>
Common Users on foo.example.net and bar.example.net are:
root
bin
daemon
adm
lp
uucp
ftp
nobody
[/prettify]

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.

Resources

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.


width="1" height="1" border="0" alt=" " />
Raphael Mudge is the developer behind the scripting language Sleep and the IRC client jIRCii.
Related Topics >> Programming   |