[Caml-list] Coroutines

[Jerome Vouillon <vouillon@pps.jussieu.fr>]

On Fri, Oct 04, 2002 at 03:25:44AM -0700, Chris Hecker wrote:
> I'm looking at implementing fibers/coroutines/cooperative-threads 
> (described below for reference) in ocaml, and I've run into a small issue, 
> a question, and a couple confusions.

I just spent a few hours implementing a small coroutine library.  It
is fully written in Ocaml.  Below is a quick description.  Would it
satisfy your needs ? I can send you a copy, or make it available on the
Web if you like.

-- Jérôme

A coroutine returning values of type 'a has type 'a output.

    type 'a output

You can spawn it.  You then get an handle of type 'a input

    type 'a input
    val spawn : 'a output -> 'a input

The caller can get a value from the coroutine.

    val receive : 'a input -> 'a

A coroutine can return a value of type 'a.

    val send : 'a -> 'a output

It can also exit.  If a caller try to get more values from the
coroutine afterwards, an exception Exited will be raised.

    exception Exited
    val exit : 'a output

Coroutines can be combined sequentially: "e >> fun  () -> e'" is a
routine that behaves first as "e", then as "e'".

    val (>>) : 'a output -> (unit -> 'a output) -> 'a output

It is sometimes useful to have a coroutine "nop" that does nothing.
Note that the expression "nop >> fun () -> e" behaves as "e", while
the expression "exit >> (fun ()-> e)" behaves as "exit".

    val nop : 'a output

So for instance, the coroutine f below returns the integers 1, 2 and
3, then exits.

    # let f =
        spawn
          (send 1 >> fun () ->
           send 2 >> fun () ->
           send 3);;
    val f : int Coroutines.input = <abstr>
    # receive f;;
    - : int = 1
    # receive f;;
    - : int = 2
    # receive f;;
    - : int = 3
    # receive f;;
    Exception: Coroutines.Exited.

You can define a coroutine "indexed ~len:n f" which returns
successively "f 0", "f 1", ... "f (n - 1)".

    let rec indexed_rec f n l =
      if n = l then exit else
      send (f n) >> fun () ->
      indexed_rec f (n + 1) l

    let indexed ?(len = -1) f = spawn (indexed_rec f 0 len)

You can use it to define an array iterator.

    let array_iterator a = indexed ~len:(Array.length a) (fun i -> a.(i))

So, "array_iterator [|1;2;3|]" will behave just the same as "f" above.

The coroutine below returns all integers starting from "first".

    let integers first = indexed (fun i -> i + first)

As a more complex example, here is the Erathostenes sieve implemented
using coroutines.

    let rec filter_rec p st =
      let v = receive st in
      (if p v then send v else nop) >> fun () ->
      filter_rec p st

    let filter p st = spawn (filter_rec p st)

    let filter_multiples n st = filter (fun m -> not (m mod n = 0)) st

    let rec primes_rec st =
      let n = receive st in
      send n >> fun () ->
      primes_rec (filter_multiples n st)

    let primes = spawn (primes_rec (integers 2))
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners