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