Continuations And Coroutines
Continuations And CoroutinesIf you understand continuations (see ContinuationExplanation) then CoRoutines are just two or more continuations that call each other whenever they block, end, or just feel like being polite. See SchemeCoroutineExample.
UseClosuresNotEnumerations explains itself at one point like so:
By turning the body of the iteration into an object, it opens possibilities for reuse.
I've just been learning about continuations from reading up on StacklessPython. Someone explained a continuation to me as the state a function is in when it is about to pass execution elsewhere.
The closest concept I have is the task-switching in a multi-tasking single processor system, you save and restore states.
This implies to me that a continuation as referred to on UseClosuresNotEnumerations somewhat like a loop, but is instead a 'function state' object with the arguments being reassignable.
Are closures and continuations identical? Am I confused?
See LexicalClosure
Closures and continuations are not identical, but are often seen together. Some confusion can occur because the things used as continuations often are closures.
A closure is basically a function with some variables that persist between function calls. For example, in SchemeLanguage, you can do this:
(define counter
(let ((i 0))
(lambda ()
(set! i (+ i 1))
i)))
In PerlLanguage, the equivalent code would be:
sub make_counter {
my $i = 0;
sub { $i++; $i }
}
*counter = make_counter();
In both of these cases, thanks to lexical scope, i is only accessible through the counter function, but since i is not actually a local variable of the function, its value persists between function calls.
A common space optimisation in FunctionalProgramming systems is to re-write recursive procedures so that there is at some point a continuation containing only the recursive call, then the same context can be used for each of the recursive calls until the base case occurs. (See TailCallOptimization.)
So how do you keep the program from doing the exact same thing (and thus getting into an infinite loop) every time the continuation is called? Somehow the state of the program has to be different on subsequent calls or you'll never get any work done.
In the recursive re-write the values in the argument list in each recursive call have to converge, in some sense, toward the base case, but that is true before the re-write, too, which is a refactoring in a very strong sense. In the case of coroutines the processes that execute between the procedures handing off to each other will do stuff thas causes changes outside the continuations but visible to them.
Windows 3.1 was a non-preemptive ("cooperative") task switching system, but it hardly counts as a system of coroutines because each process could only contain a single routine. Theoretically you could spawn one process from another and then have the two communicate like coroutines, but it generally wouldn't be worth the trouble. In Windows NT the ability to create cooperative threads was retained (created?), and these were called Fibers.
In a typical C/Java thread-based system, each thread has a distinct stack. A new thread always starts with a brand new stack, and stacks never mix. So the system can be considered to be a set of stacks. As I understand it, in lisp-like systems that supports closures and continuations, you have a tree instead of a stack, where each node is equivalent to a stack frame. A function call adds a new node to a tree as a child of whatever is the current stack frame. Returning from a function call moves to a parent node without necessarily deleting anything (the frame you left may or may not be garbage collected, depending on whether you keep a pointer to it). Continuations allow you to save pointers to other nodes in the tree and jump around to them arbitrarily, and the result is sort of like cooperative multithreading, except for the shared stack frames and the fact that you can continue from the same place more than once (I think?)
I haven't really used continuations because they're hard to think about compared to ordinary threads, which are no picnic either. It seems like you lose a lot of guarantees that a strict stack-based system gives you. Weird things happen like functions getting called once and returning multiple times - what does this do to things like exceptions and finally clauses?It causes a world of pain for the programmer who tries to implement a language with both continuations and exceptions. --sg I tend to think that tree-like data structures really ought to be data, not code. Then again on Unix we are used to the fork() call and that can be difficult to understand too.
On a slightly related note, see the discussion of exception handling in http://www.advogato.org/article/48.html
A world of pain? I'm not so sure. It just means that instead of a single return-address continuation, your typical function will have both a normal-return and exceptional-return continuation. I think it even makes try statements easier to sort out, since catch ends up looking like a closure wrapping the exceptional-return continuation, and finally wraps both the normal and exceptional returns.
In the March issue of DrDobbsJournal, there is an article about implementing cross-platform general coroutines in C++:
I (DavidPiepgrass) have also written an article on coroutines, with included (and essentially portable) C++ code, here: http://qdl.sourceforge.net/coroutines.html -- it is somewhat of a basic article, because regrettably I don't actually know any advanced uses of coroutines and continuations myself. I've had a really hard time learning about these things because most authors insist on expressing their ideas in Scheme or LISP or some other language I don't know (and want to learn but can't because the way it is explained just never matches the way my brain works, I guess). Why not explain these concepts in English, with Stackless Python as a fallback?. I fear that as long as these concepts are explained and promoted in unpopular languages, they will remain unpopular themselves.
Because StacklessPython does not have continuations anymore. They seem to have been removed due to being too powerful for python or too hard to explain (not in the sense of python being a dumb language, but because they break the OnlyOneWayToDoIt? rule). Here is a text that you may find interesting, it is ruby but is similar enough to python to be understandable: http://mikael.phubuh.org/Media/Writing/Continuations/ and about coroutines: http://www.sidhe.org/~dan/blog/archives/000178.html
You might also like to look at http://www.jpaulmorrison.com/cgi-bin/wiki.pl?TelegramProblem. The FlowBasedProgramming solution to this involves 4 threads that are essentially coroutines. Actually you can very simply convert this to a solution to the OddWordProblem by adding one more component (to reverse every other word) into the middle of the diagram!
I also built a coroutine implementation on C++ using multiple stacks and longjmp, called THREADS. It is available, if anyone wants to try it out, at http://www.jpaulmorrison.com/fbp/threads.zip. It is described in http://www.jpaulmorrison.com/fbp/threads.htm. Some assembly may be required. --PaulMorrison
The Win32 operating system supports a feature called "fibers":
A fiber is a unit of execution that must be manually scheduled by the application. Fibers run in the context of the threads that schedule them. Each thread can schedule multiple fibers. You schedule a fiber by switching to it from another fiber. The system still schedules threads to run. When a thread running fibers is preempted, its currently running fiber is preempted. The fiber runs when its thread runs. A fiber can use fiber local storage (FLS) to create a unique copy of a variable for each fiber. If no fiber switching occurs, FLS acts exactly the same as thread local storage (TLS).
The SwitchToFiber?() API function is very similar to the "yield" keyword discussed above.
http://msdn.microsoft.com/library/default.asp?url=/library/en-us/dllproc/base/fibers.asp
In fact, I just found an article about this:
http://msdn.microsoft.com/msdnmag/issues/03/09/CoroutinesinNET/default.aspx
POSIX has a set of functions that can be used in a similar way: setcontext, getcontext, swapcontext, and makecontext.
A new use for continuations and cothreads in general seems to be that of doing web pages flow control. In particular, the classic event-driven MVC pattern has difficulty dealing with the inevitability of users doing silly things like duplicating a page and continuing down two different paths, or going back and forwards with their browser buttons. I'm pretty new to this, but as I understand it, the idea to to have the web processing as one coroutine, and the user as the other. Whenever the web process needs input, it "yields" by giving the browser/user a webpage, which has a form, or a link, with an embedded continuation id, which points to a continuations repository on the server side.
There is a project done by Apache which works in this fashion, though I believe they use some funky java-rewriting and custom implementation of javascript to achieve this.
http://www-106.ibm.com/developerworks/library/j-contin.html
I have recently done something like this in PhpLanguage, however, it's not quite the same natural syntax that is in the above link.
CategoryFunctionalProgramming CategoryClosure CategoryContinuation
EditText of this page
(last edited March 3, 2011)
or FindPage with title or text search