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 <o...@cs.otago.ac.nz> wrote: > 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 > _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe