09
Oct 08

Coroutines, closures and continuations

I ought start with a disclaimer: I don’t have experience with functional programming. I never studied it. Nevertheless recently I have had some contact with some of its concepts, specially with the idea of continuations and closures. From these contacts came up a question, an hypothesis: by definition, continuations ⊆ closures ⊆ coroutines?.

The first step should be find their formal definitions and establish their relationship as subsets. But find and understand formal definitions is not a piece of cake, at least for me, so I will try to expose the most clear definitions, in simple words, which I found in
the net:

coroutine

A coroutine is a generalization of a subroutine which can be paused at some point and returns a value. When the coroutine is called again, it is resumed right from the point it was paused and its environment remains intact.

In other words, a coroutine is a subroutine which has multiple entry points and multiple return points. The next entry point is where the last return point occurred or at the beginning of the coroutine if it reached its end previously. Meanwhile a subroutine only has one entry point and one or more return points.

Example:

In this example, the pause and return point is controlled by the token yield.

coroutine foo {
yield 1;
yield 2;
yield 3;
}

print foo (), "n";
print foo (), "n";
print foo (), "n";
print foo (), "n";
print foo (), "n";
print foo (), "n";

This code will print:

1
2
3
1
2
3

closure

A closure is a block of code (can be anonymous or a named subroutine) which can contains variables defined out of its lexical scope (free or bound variables). When that block of code is evaluated, all the external variables and arguments are used to resolve its free variables.

Example:

function foo (mylist) {
threshold = 150
return mylist.select ({ myitem, myitem.value > threshold })
}

In this example, the closure is the block code of { e, e.salary > threshold } which is evaluated for every item in the list (the select method traverse the list executing the passed closure for each element), and the free variable of threshold is resolved in
the lexical scope of the foo subroutine.

continuation

A continuation is a subroutine which represents the rest of the program.

In order to visualize this, you must break with the concept of the return of a subroutine, the subroutines don’t return values, they continue the execution of the program with another subroutine. The continuation, obviously, must receive the whole state of the program.

In other words, a continuation is a glorified “goto” sentence, where the execution pointer is transfered from a subroutine to another subroutine. The concept of the function stack and their dependency relationships are removed.

function foo (value, continuation) {
continuation (value + 1)
}

In the previous example, the continuation is passed to the foo subroutine as an argument, an contains, besides the next subroutine to execute, the whole state of the program, and receives the an argument which is processed by foo.

conclusion

Each concept, although extends or modifies the wide-used concept of a lexical scoped subroutine, is independent among them, but not mutually exclusive: in terms of implementation you may have a coroutine which is a closure, a continuation which is a closure, a coroutine which is a continuation or vice versa.

So, my hypothesis is incorrect, we must rephrase it as, by definition coroutine ∩ closure ∩ continuation = ∅

But, by implementation, ∃ coroutine ∪ closure ∪ continuation

references

what the heck is: a coroutine

http://www.sidhe.org/~dan/blog/archives/000178.html

Wikipedia Coroutine

http://en.wikipedia.org/wiki/Coroutines

Closure

http://martinfowler.com/bliki/Closure.html

A Definition of Closures

http://gafter.blogspot.com/2007/01/definition-of-closures.html

Wikipedia Closure

http://en.wikipedia.org/wiki/Closure_(computer_science)

Fake threads

http://mail.python.org/pipermail/python-dev/1999-July/000467.html

Continuations made simple and illustrated

http://www.ps.uni-sb.de/~duchier/python/continuations.html

Wikipedia Continuations

http://en.wikipedia.org/wiki/Continuations