[Haskell-cafe] Coroutines

[Ryan Ingram]

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 <ok at 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 at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>