Andrew was recently asking about co-routines. A couple of years ago,
I was in much the same position as him; although I am pretty sure I
had heard the term before, it seemed like a mysterious idea with no
practical use.
Then I learned Ruby. Ruby makes extensive use of coroutines; it's not
uncommon to have three or more coroutines executing cooperatively,
made simple by how easy it is to pass blocks of code around in that
language. The entire collection iteration system in Ruby is based on
coroutines; if an object implements "each", it can be iterated over:
[1, 2, 3].each { |x| print x }
Implementing "each" for a container is generally simple; you just
write a loop and call "yield"
def each
[1 .. length].each { |index| yield self[index] }
end
It surprised me how simple and powerful this concept was; code that
previously was incredibly ugly to write became simple. I think this
abstraction is one of the big reasons for Ruby's current success.
At the Haskell Symposium this year, Jesse Tov gave a talk about
Session Types in Haskell, and it struck me that they are ideal for
implementing coroutines in a type-safe manner. Here you can write
pure functions that represent a communicating routines, and guarantee
that the communication completes successfully (assuming the routines
terminate, of course).
Consider these two values:
f1 :: Int -> (Char, ())
f2 :: (Int, Char -> String)
You can see a natural way to connect them, using the duality of (a, _)
and (a -> _):
connect_f1f2 :: ((), String)
connect_f1f2 =
let (arg1, k2) = f2
(arg2, result1) = f1 arg1
result2 = k2 arg2
in (result1, result2)
I implemented this idea, along with a nice syntax for these
coroutines, in http://hackage.haskell.org/cgi-bin/hackage-scripts/package/Coroutine-0.1.0.0:
f1 :: InSession (Int :?: Char :!: Eps) ()
f1 = runSession $ do
x <- get
put (head $ show x)
return ()
f2 :: InSession (Int :!: Char :?: Eps) String
f2 = runSession $ do
put 6
result <- get
return ("the answer is " ++ [result])
(Caveat: while this uses the do-notation, it's not *exactly* a monad;
it's something more general than that. See Control.Monad.Indexed for
the details. Thanks to the GHC team for NoImplicitPrelude!)
You can then add choice, looping constructs, etc., to allow
increasingly complicated protocols:
peer1 :: InSession ((Int :?: Int :!: Eps) :?* Eps) Int
-- read an Int, then write an Int, any number of times we are told to do so
-- then return an Int
peer2 :: InSession ((Int :!: Int :?: Eps) :!* Eps) [Int]
-- write an Int, then read an Int, any number of times we want
-- then return a list of Ints.
The neat thing about this library is that the communication is
completely pure! No side effects required!
ghci> :t connect peer1 peer2
connect peer1 peer2 :: (Int, [Int])
-- ryan
On Wed, Dec 17, 2008 at 6:54 PM, Richard O'Keefe
On 18 Dec 2008, at 11:26 am, Andrew Coppin wrote:
(Also, "coroutines"? Seriously? That's hardly an obscure term in programming circles.)
Well now, I'm curios. I've been writing computer programs since I was 9 years old. I hold a diploma *and* an honours degree in computer science. And I have never even *heard* of a coroutine. To this day I still don't know what it means. I rather suspect I'm not the only "programmer" on earth who finds themselves in this position. ;-)
Shame on you for not reading Knuth's "The Art of Computer Programming", Volume 1, "Fundamental Algorithms". The then available three volumes of TAOCP "were named among the best twelve physical-science monographs of the century by American Scientist" "at the end of 1999". (Fasicles 0, 2, 3, and 4 of volume 4 are now available, and parts of fasicle 1 are on-line. Hooray hooray!)
Quoting the first two paragraphs of the Wikipedia entry: "In computer science, coroutines are program components that generalize subroutines to allow multiple entry points for suspending and resuming of execution at certain locations. Coroutines are well-suited for implementing more familiar program components such as cooperative tasks, iterators, infinite lists and pipes. The term "coroutine" was originated by Melvin Conway in his seminal 1963 paper.[1]"
So "coroutine" has been standard hacker-type programming terminology since 1963. I was able to use coroutines in Burroughs Extended Algol (designed in the mid to late 60s), Simula 67, and Interlisp-D (80s). Current languages supporting them include (thanks, Wikipedia) Lua, Limbo, JavaScript, Python, and Ruby. Since anything with continuations can do coroutines, we add Scheme and SML/NJ. Sather's iterators may be a more familiar form of coroutine. You will commonly find something like a "yield e" statement that reports the value of e to the caller without actually returning, and "resume c" that resumes a coroutine to get the next value.
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Andrew was recently asking about co-routines. A couple of years ago, I was in much the same position as him; although I am pretty sure I had heard the term before, it seemed like a mysterious idea with no practical use.
Besides the point that people have already made that lazy evaluation gives you similar control as coroutines, I wanted to point out how simple it is to implement coroutines. Here's a simple implementation that ddarius made on IRC a few months back off-the-cuff. I kept it around on codepad because its cool: http://codepad.org/GwtS6wMj
-- ryan
Tim Newsham http://www.thenewsh.com/~newsham/
Another implementation of coroutines is in the Streaming Component Combinators on Hackage (http://hackage.haskell.org/cgi-bin/hackage-scripts/package/scc). In this version, a coroutine is a monad transformer that can be laid over any monad, including Id and IO. Furthermore, you can have an arbitrary number of inputs/output channels but they are restricted to communicating a single value type.
participants (3)
-
Mario Blazevic -
Ryan Ingram -
Tim Newsham