Monday, October 31, 2005

Why Are Continuations So Confusing, and What Do They Really Do?

I recently watched a video trying to explain, in simple terms, what continuations are. The quick answer was "Continuations are just the remaining work to be done." WTF?! I had been wondering what the heck continuations were, but this answer gave me absolutely no clue. Oh! Of course! The remaining work to be done! It makes complete sense now. Unfortunately, this is one of those explanations that only makes sense if you already understand what is being explained. Kind of like 'a Java classpath is just the set of paths where all your classes are'. Completely useless to you if you don't already get it. Even the examples in the video confused me. I sort of got it, but not really. So I started digging into Ruby to see if I could figure it out, given the sparse clues I already had, and you know what ... continuations are so freaking simple that it boggles my mind why it was so difficult to understand them. Correction: It doesn't boggle my mind; I know exactly why continuations are confusing. And so, I hope to once and for all cut through all the confusion and explain what continuations are, and how to use them, in actual simple terms.

What are continuations?
That's actually the wrong question to ask. The answer will probably confuse you more than necessary. The better question to start with is:

Why are continuations so confusing?
The answer is quite simple: Wrong metaphor. The word 'continuation' provides no clue as to what it does. In fact, it describes its implementation rather than its purpose. So, it is necessary for you to understand the implementation before you can understand the purpose. But for someone new to continuations, this is completely backwards! We want to understand what continuations are for before we understand how the implementation works. Could you imagine if a class' methods were called 'virtual table entries'? Or if floating point numbers were called 'exponentiated mantissas'? Of course, the implementation is important to understand to become an expert, but I shouldn't need to know exactly how an internal combustion engine works just to drive a car.

What do they really do?
You know, I'm not even going to bother calling them continuations anymore, as that's a complete red herring. I'm going to explain to you a brand-spanking-new concept called 'execution sites'. Execution sites allow you to specify (or mark) a point of execution in your code, and store a representation of that site in a variable so that you can return to the original site later. Not only that, but it allows you to pass information back to the original site, so that it evaluates to a different value. I'll explain how this works with some simple Ruby code. (Note that the code below will not work in plain old Ruby. It requires some simple definitions which I'll provide at the end of the article. You can, for now, pretend that this is 'wishful' Ruby, or Ruby-as-I-would-like-it. I'll also use some redundant syntax to make the code more natural to non-Rubyists.)

I need to be able to mark my execution site and store it in a variable, like this:
theSite = mark();
'mark' is a special keyword (again, not in real Ruby, but in wishful-Ruby) that captures the site of execution, wraps it in an object, and returns it. 'theSite' is simply a local variable where we store the site. Later on, we can return to the site by using the 'return' method of the site object, like this:
theSite.return();
Here's a 'hello world' type of program that uses execution site marking:
theSite = mark();
puts "Hello, World!"
theSite.return();
This code performs an infinite loop, outputting "Hello, World!" over and over. You may be familiar with labels and gotos from other languages, which allow you to do something very similar to this. Here's a simple script to demonstrate how gotos and labels work:
:theSite
echo Hello
goto theSite
"So, an execution site is like a goto label?" Sort of, but actually more powerful. First, you can store an execution site in a variable, array, object field, or whatever, so it is more like an object than a label. Second, labels typically are limited in scope, depending on the language. For example, you usually can't goto from one method/function to another. With execution sites, you can return from deep inside some arbitrary code, back to wherever the site was marked:
# Method definitions
def startloop
startloopSite = mark();
puts "Inside startloop";
return startloopSite;
end

def endloop(startloopSite)
puts "Inside endloop";
startloopSite.return();
end

# Main execution path
theSite = startloop();
puts "Middle of the loop";
endloop(theSite);
This code will output "Inside startloop", "Middle of the loop", and "Inside endloop" over and over again. Notice that the main code execution path goes into startloop, marks the execution site, outputs "Inside startloop", and then returns the execution site. So, later, when endloop calls 'return' on the execution site, code execution goes right back inside startloop and outputs "Inside startloop" again. The site always returns to where it was marked, no matter where that is. Simple, but potentially much more powerful than a plain goto label.

The third major difference between labels and execution sites is that execution sites remember everything about where they were marked, whereas goto labels are more 'global' in this aspect. A label only knows where it is declared, but when you mark an execution site, it remembers how the execution path got there (such as the method call stack) and also what local variables have been declared up to that point. In essence, it stores the complete execution state in a little object so that you can return to that same state at any point in the future. Here's an example:
def remember(aValue)
theSite = mark();
puts "The value is " + aValue.to_s();
return theSite;
end

siteToReturnTo = 2;

# Remember the values and execution state
firstSite = remember(1234); # Line A
secondSite = remember("ABCD"); # Line B

puts siteToReturnTo;

# First go back to secondSite, then back to firstSite, then quit
if (siteToReturnTo == 2) then
siteToReturnTo = 1;
secondSite.return();
elsif (siteToReturnTo == 1) then
siteToReturnTo = -1;
firstSite.return();
end
This code outputs the following:

The value is 1234
The value is ABCD
2
The value is ABCD
1
The value is 1234
The value is ABCD
-1

The first two lines of output come from the first time the 'remember' lines were executed. Inside the 'remember' method, the parameter 'aValue' takes on different values depending on what was passed. Note that the execution site is marked inside the 'remember' method, so the site will remember the value assigned to the 'aValue' parameter, as each call to the method essentially creates a separate variable called 'aValue'. So, essentially, 'firstSite' remembers that 'aValue' is 1234, and 'secondSite' remembers that it is "ABCD". Not only that, but firstSite remembers that the 'remember' method call should return to Line A, and secondSite remembers that it should return to Line B. So local variables, the state of the call stack, and even the exact location in the code are all remembered when an execution site is marked.

When secondSite.return() is called, execution jumps inside the 'remember' method, where 'aValue' has the value "ABCD", and the 'remember' method will return to Line B. Hence, we get the fourth line of output, "The value is ABCD". By this time, our switch variable, 'siteToReturnTo' has been updated to cause firstSite.return() to be called. When this happens, execution jumps again into the 'remember' method, but this time 'aValue' has its original value of 1234, and the method call will return to Line A. (Note that firstSite and secondSite do not remember that 'siteToReturnTo' was initially given the value of 2. Sites remember the variables themselves not the values of the variables. The fact that 'aValue' exists as a local parameter inside the 'remember' method makes it act like two distinct variables, one for each method call, which happen to have the same name. It's a subtle distinction, and important to keep in mind. Those familiar with closures and code blocks in Ruby should have no trouble with this.)

Now, this is all fine and dandy, but doesn't this make execution sites seem like glorified gotos? In essence, that is very much what they are. Dijkstra's advice should be heeded: Goto Considered Harmful. Marking execution sites for the purposes of using them like gotos sounds to me like a recipe for spaghetti. I like spaghetti for a good meal, but not in my code! I really believe that execution sites have the potential to royally mess up your code, so I don't recommend using them without a very good reason. I would say that it is unlikely that most programmers will code directly with execution sites. Instead, it is more likely that they would be useful for specialized frameworks and services to give concise ways to express complex solutions to problems. However, that shouldn't stop you from playing around with them to get a solid feel for what they do. Hey, maybe you'll be the one writing that cool framework or service that uses execution sites.

What's the big deal?
There is one last capability of execution sites which I've been holding up my sleeve. I think this is what makes them truly powerful and useful, and worthy of taking the time to understand them. I'll be honest and admit that I personally can not think of very many practical uses for execution sites, although some very practical examples exist. I imagine that I'll start to see practical uses as my understanding improves and my imagination catches up with me (as happened to me with closures and macros). In any case, the final capability:

So far, you've seen that execution sites can mark a place in code execution that can be returned to at some later time. Wouldn't it be great if they could also return some useful information back to the original site? Then they could be used as a way to 'hold' a calculation until future information is available that can allow the calculation to 'continue' (Hmm, there's that word 'continue'.... I wonder if there's a connection to continuations? Patience, please. :-)

Maybe, in wishful-Ruby, it could look like this:
tryForBetter = true;
theSite = nil;
theCalculation = mark() { |site|
theSite = site;
# Do some work to get an initial value for the calculation
initialCalculation = 3;
theSite.return(initialCalculation); # Line A
}

puts "The calculation is " + theCalculation.to_s();

if (tryForBetter) then
tryForBetter = false;
# We discover a better value for the calculation
betterValue = 3.1415;
theSite.return(betterValue); # Line B
end
This usage of 'mark' is significantly different than the simple usage of 'mark'. In the simple usage, 'mark' returns the execution site itself:
theSite = mark();
In the new version, 'mark' returns a value, and the execution site is provided as a parameter to the accompanying code block. This syntax structure allows us to return different values in the future. The execution site is merely a book-keeping tool that we use to provide this capability.

The first time through the code, 'mark' captures the execution site, and then executes the code block. The code block is given the site object as a parameter, called 'site' in this example. We store the site object in the local variable 'theSite' so we can use it later. Then we return an initial value. This initial value becomes the value of the 'mark' expression. Note that the code block is only executed once, when the 'mark' expression is first evaluated. You can think of the code block as the initializer which performs book-keeping (storing the execution site object for future use), as well as producing an initial value for the 'mark' expression.

Thus, the initial value of 'theCalculation' is 3, because that's the value determined by the block, specifically by the expression theSite.return(initialCalculation) on Line A. So the first line of output is "The calculation is 3".

Since the site object is stored in 'theSite', we can essentially go back and change the value of 'theCalculation' by passing in a different value to return on Line B. Now 'theCalculation' gets the value 3.1415, and the second line of output is "The calculation is 3.1415". If we wanted to, we could keep using the site object to return successively better approximations of pi. This is admittedly a trivial example, but hopefully it will give you a spark to let your imagination consider the possibilities.

Summary

So that's it. An execution site provides three things: A way to mark a specific point in execution, including all the important context; an object which represents the execution site so you can store it, use it, abuse it, or what have you; and a mechanism to return back to the site mark, optionally returning some useful information.

"Wait a second, you've just told me about 'execution sites'. You just made that crap up. I want to know what continuations are, you jerk!"

Whoah, whoah, no need to be upset. It's very simple, really. A 'continuation' is an 'execution site'. You create continuations using a special command named 'callcc', which works exactly like the value-returning version of the 'mark' command, and you can return to the location of the 'callcc' by invoking the 'call' method on the continuation object. All I've really done is give better names to the concepts, 'callcc' becomes 'mark', 'continuation' becomes 'execution site', and the 'call' method becomes 'return'. Oh, and I also provide a simplified way to mark sites where you don't care about the return value and only want to capture a continuation (oops, I mean execution site). In fact, it's so simple there are only a few lines of Ruby code which will transform Ruby into wishful-Ruby:
class Continuation
alias_method :return, :call
end

def mark &block
if block != nil then return callcc(&block) end
theSite = nil
callcc{|s| theSite = s}
return theSite
end
So, wishful-Ruby code that looks like this:
theSite = nil;
aValue = mark { | site |
theSite = site;
}
...
site.return(someValue)
Looks like this in normal Ruby:
theContinuation = nil;
aValue = callcc { | cc |
theContinuation = cc;
}
...
cc.call(someValue)
In other words, continuations are cryptic and nearly incomprehensible. Still not satisfied? Okay. Fine. A continuation is just a reification of execution context. Or, in 'simple terms', a continuation is just the remaining work to be done. But you already know that now, don't you?

Now if someone could just explain to me what monads are....

18 Comments:

Anonymous Anonymous said...

I got kicked in the monads once .. it really hurts ;-)

November 01, 2005 4:51 AM  
Anonymous Anonymous said...

Very very nice. Thanks a lot for the explanations. Do you happen to know a static typed language which supports continuations or this is dynamic language only thingie ?

November 01, 2005 3:06 PM  
Blogger Patrick Lightbody said...

There are Java implementations of continuations. RIFE has a RIFE/Continuations sub-project that WebWork takes advantage of for continuation support. See the docs here

November 01, 2005 8:29 PM  
Anonymous Anonymous said...

Very informative article. You could post it to the Artima developer community and see what you stir up there
(http://www.artima.com)

Proposal link
(http://www.artima.com/write.html)

November 01, 2005 9:51 PM  
Anonymous Anonymous said...

An "execution site", n'est-ce pas? A "site"? Hmmm, let's see what Dictionary (you are on Mac OS X, right?) says about that:

site |sīt| noun an area of ground on which a town, building, or monument is constructed : the proposed site of a hydroelectric dam. • a place where a particular event or activity is occurring or has occurred : the site of the Battle of Antietam | materials for repairs are always on site. • short for building site . • short for Web site.

How about "point"? Would that cover it: "execution point"?

All fun aside, I think I'm beginning to grasp continuations... Thanks!

November 04, 2005 4:01 PM  
Anonymous Anonymous said...

Hi Rob,

Thanks for that excellent explanation. Would you please do closures next?

Thanks,
Phil

February 17, 2006 6:53 PM  
Anonymous Anonymous said...

Why are you using semi-colons? Just don't use them. Same with doing

"if (statement) then
...
end"

Drop the parentheses and the 'then'.

March 07, 2006 11:58 PM  
Anonymous Anonymous said...

Oh, and please don't use camelCase in Ruby. It is standard convention to use whatever_this_is_called.

March 08, 2006 12:01 AM  
Anonymous Anonymous said...

(Boy you got a lot of comment spam on this.)

Nice explanation! You might check out Nickle, which provides continuations as just setjmp()/longjmp() without the restrictions. :-)

There's also a nice example there of what continuations are for: namely, extending the language. Like any other language extension tool, they should definitely be used with caution. But it's very occasionally nice to be able to create new control flows in the same way you can create new datatypes.

March 08, 2006 12:06 AM  
Anonymous Anonymous said...

Well, that was a pretty bad attempt at a 'simple' explanation. But at least you were trying. setjmp/lngjmp? I shudder.

If I understand continuations then continuations are just lambdas with better syntax, and a different way to create them.

The only difference between a lambda and a continuation is that instead of creating the lambda and executing it being two seperate steps, a Call/CC does both steps at once.

So the way to emulate a continuation using lambdas is to store the lambda in a method variable and then execute the lambda. If the lambda references itself in any way, which is probably typical for continuations, then this is officially Very Ugly Code.

So a lambda is executed 0 or more times, whereas a continuation is executed 1 or more times.

And voila, those are continuations. Syntactic sugar for lambdas.

Or at least, that's what I've got from your explanation so you know who to blame if it's wrong.

March 08, 2006 8:25 AM  
Blogger Laurie Cheers said...

I think you've hit on the reason why so many people find functional language concepts hard - their terminology and syntax get chosen by mathematicians.

By the way, instead of "site.return()", perhaps "site.goto()" or "site.resume()" would be more appropriate?

March 08, 2006 1:48 PM  
Blogger Laurie Cheers said...

If you're interested in rephrasing monads in a similar way, then Monads for the Working Haskell Programmer explains them fairly well from a programmer's standpoint.
(that's in stark contrast to most "tutorials" on monads - for instance The Haskell Programmer's Guide to the IO Monad)

March 08, 2006 4:30 PM  
Blogger Christopher Parker said...

Paul Graham has a great description of Continuations in his book On Lisp if you are a Lisper.

Really, really great article.

March 08, 2006 5:01 PM  
Anonymous Anonymous said...

Continuations are more general than lambda's?

You can easily build lambdas with continuations, but not the other way around. Or am I wrong now?

Lambdas/functions have 2 jump steps:

f = function(a)
{
print(a);
return();
}

f(1);

The first step is from f(); to the start of the function, when the function gets called. The second step is the return from the function to the place where it was called.

Now the same example using continuations (somewhat Io style, a continuations based programming language):

f = continuation(a, return)
{
print(a);
return();
}

f(1, mark());

The continuation has two parameters here: the value to be printed, and the place to return to. The place to return to is created by mark. This value is stored in the parameter "return" of the continuation. We call that continuation: return();

So what happens if we don't call return?

f = continuation(a, return)
{
print(a);
}

f(1, mark());

Then the execution terminates. There is no continuation to continue with.

So actually, continuations are more general that lambdas.

March 08, 2006 6:23 PM  
Anonymous Anonymous said...

In an environment that supports threads, how is this different than threads? the ability to return something?

March 08, 2006 7:38 PM  
Anonymous Anonymous said...

lambdas are more fundamental than continuations. Any program can be transformed to what is called 'continuation-passing style', where the point execution should continue at next is always explicitly passed as an argument.

If you transformed a program in a language that doesn't support first-class continuations, such as C, into continuation-passing style, you would essentially be passing the function return address explicitly as a parameter to every function call, and the end of every function would be calling that return address with the value to return.

This transformation makes the continuation explicit, and easily understood, but the programs themselves become much harder to follow. So, languages like Ruby and Scheme give you access to the implicit continuation that lies under the covers, so to speak, so you get the ability to do things with it aside from the standard return from a function call, but you also get the readability benefits of having your standard continuation be implicit.

Guy Steele wrote about this in his paper entitled: "Debunking the 'Expensive Procedure Call' Myth, or, Procedure Call Implementations Considered Harmful, or, Lambda: The Ultimate GOTO", which you can find at http://library.readscheme.org/page1.html

Another correction I'd like to make is this; the continuation does not, in fact, contain a record of the history of the computation. It seems like it does, because invoking a continuation 'rewinds' the program to a past state, but it only remembers the state left at that point needed to finish the computation. Much of the history of the execution may have been discarded at that point; only the frames left on the stack (which contain the rest of the computation to perform) are retained.

If that's unclear, Dave Herman said it better at http://calculist.blogspot.com/2006/03/call-stack-is-not-history.html/

Anyway, thanks for the intro to continuations! They're nifty, and helping more people understand them is definitely a laudable goal. :)

March 08, 2006 9:39 PM  
Anonymous Anonymous said...

Thanks for the introduction.

The word 'continuation' has already got an entry in Wikipedia: http://en.wikipedia.org/wiki/Continuation

Maybe you can add a link to your blog entry in the wiki page.

March 13, 2006 3:06 AM  
Anonymous Anonymous said...

As for Monads, some Ruby folk are dabbling with these - check out

Monads, Ruby and OO
http://cwilliams.textdriven.com/articles/2005/11/07/monads-ruby-and-oo

for a nice and quite readable expose...

March 28, 2006 7:44 AM  

Post a Comment

<< Home