Specifically, my own sloppiness about using the term continuation to describe the closure (anonymous method) and generator (iterator) facilities in C# 2.0.
I'll rise to Cedric's challenge and try to clear the air here.
C# 2.0 supports for
lexical closures. Both anonymous methods and iterators capture the current
lexical scope for use after current method has returned. Java has a similar feature called
inner classes, however, inner classes only have access to const/final variables in the current method. C# anonymous methods and iterators have full read/write access to the locals.
To make lexical closures work in C#, the enclosing method's locals are actually allocated on the heap, not the stack.
Now, what does this have to do with continuations?
Nothing. Well, almost nothing.
Continuations in their full glory capture more than a lexical closure does. A continuation as defined by
call/cc captures not only the in-scope variables, but also the current control flow
including pending return statements. The curmudgeons in the crowd probably recognize this as
setjmp/
longjmp.
This is not what's happening with C# anonymous methods. For example, consider the following program:
public static string b(out Function<int> r2) {
int count = 0;
r2 = delegate() { return (++count); }
return "Hello, world";
}
public static string a() {
Function<int> f;
string s = b(out f);
Console.WriteLine(f());
return s.ToUpper();
}
Note that when a() calls back into the closure f, there's no way for the anonymous method to "re-return" a string value to a. It can't. The return already happened and the stack remnants (e.g., esp, ebp) are long gone. All that is left of the old (logical) frame are the local variable declarations.
C# iterators are closer to continuations than anonymous methods are. However, iterators are a very constrained version of what continuations can do.
With C# iterators, the caller and callee's control flow gets interleaved at every yield statement. The C# yield statement must appear inside the iterator method. You can't yield from a subordinate method.
More importantly, there's no explicit delegate/function pointer that you can squirrel away to call from some other context later on. The reason for this is that the caller of an iterator is just a plain-old method whose frame is allocated on the stack. There's no magic heap-allocated frame for the callee to go back to.
For example:
public static IEnumerable<int> d() {
int count = 0;
while (true)
yield return ++count;
}
public static string c() {
int total = 0;
foreach (int n in d()) {
total += n;
if (n > 100) break;
}
return total.ToString();
}
In this code, the locals for d are allocated on the heap, but not c. After c returns, the storage for total is long gone.
So, what about call/cc as implemented in Scheme or Ruby? You can't get there from here, at least not all the way.
To make call/cc work, the runtime, the libraries and the languages all need to participate to some degree. As the world sits today, neither the JVM, the CLR, nor CPython (unless
Christian Tismer gets his way) support the feature.
CPS is based on the notion that instead of returning a value from a function, the value is passed to the code that will continue the computation. Here's the trivial example in C#:
// non-CPS style
int Add1(int a, int b) { return a + b; }
void UseAdd1() {
int n = Add1(4, 5);
Console.WriteLine(n);
}
// CPS-style
public static void Add2(int a, int b, Action<int> next) {
next(a + b);
}
void UseAdd2() {
Add2(4, 5, delegate (int n) {
Console.WriteLine(n);
});
}
Note that in CPS, method don't return meaningful values (in C# speak, they return void). Instead the value is passed back to caller when jumping to the caller's continuation.
The code above almost does CPS, but not quite. Here's why.
The C# return statement (which Add2 never uses) serves two purposes. First, it is used to pass a value from the callee to the caller. We got that functionality covered when Add2 called back through the next delegate.
The other purpose the return statement serves is that of control flow. That is, when the return statement is encountered, control flow "returns" to the caller. Had our Add2 method included statements after the next call, they would have executed after the continuation was complete:
public static void Add2(int a, int b, Action<int> next) {
next(a + b);
Console.WriteLine("This code should be unreachable");
}
contrast this to what would happen in our non-CPS Add1 method:
int Add1(int a, int b) {
return a + b;
Console.WriteLine("This code should be and is unreachable");
}
To get the control flow right, we can emulate one-shot continuations (
call/1cc) using the following helper routine:
public static void CallWithContinuation<T>(Action<Action<T>> target,
Action<T> continuation) {
int callbackCount = 0; // how many times has the target called back?
int catchCount = 0; // how many times have we caught an exception?
T cachedValue = default(T);
try {
target(delegate(T value) {
++callbackCount;
if (callbackCount > 1)
throw new InvalidOperationException("CallWithContinuation cannot continue more than once");
cachedValue = value;
throw new ContinuationException();
});
}
catch (ContinuationException ex) {
catchCount++;
}
if (callbackCount == 0)
throw new Exception("Continuation never came back");
if (catchCount == 0)
throw new Exception("Target intercepted our internal exception");
continuation(cachedValue);
}
public sealed class ContinuationException : Exception {}
To use this routine, we'd modify UseAdd2 as follows:
void UseAdd2() {
CallWithContinuation<int>(
delegate(Action<int> next) { Add2(4, 5, next); },
delegate(int n) {
Console.WriteLine(n);
}
);
}
Note that when Add2 calls into the callback to "return" its value, the CallWithContinuation method steals back control using an exception. This solution is fragile, as the target can still inject itself in the exception handling stack and hijack our internal throw. We can detect it (this code does) but we can't prevent it.
Notice also that we take steps to detect when someone tries to call back into the continuation a 2nd time. We need to do this because a 2nd call would no longer have our try/catch block to do the control flow hackery (that's right, anonymous methods do not inherit the ambient try/catch or try/finally blocks of their surrounding method).
Now, let's say that you're willing to live with the somewhat fragile solution presented above. How bad is it? There's at least one other problem you'd want to address. That problem is stack growth.
When our CallWithContinuation routine passes control to the continuation delegate:
continuation(cachedValue);
it leaves an activation frame on the call stack until the continuation routine returns.
Ideally, we'd apply the
tail call optimization here using the CLR's
tail. prefix, but alas the C# compiler doesn't support it. This means either resorting to hacking the generated IL or using a compiler that supports the feature (like
SML.NET or a modified version of the Rotor CSC.EXE).
Posted
Apr 27 2005, 09:25 AM
by
don-box