From mboxrd@z Thu Jan  1 00:00:00 1970
Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id UAA21618; Sun, 6 Oct 2002 20:13:51 +0200 (MET DST)
X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f
Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id UAA21598 for <caml-list@pauillac.inria.fr>; Sun, 6 Oct 2002 20:13:50 +0200 (MET DST)
Received: from shiva.jussieu.fr (shiva.jussieu.fr [134.157.0.129])
	by concorde.inria.fr (8.11.1/8.11.1) with ESMTP id g96IDn523389
	for <caml-list@inria.fr>; Sun, 6 Oct 2002 20:13:49 +0200 (MET DST)
Received: from helium.pps.jussieu.fr (helium.pps.jussieu.fr [134.157.168.2])
          by shiva.jussieu.fr (8.12.5/jtpda-5.4) with ESMTP id g96IDljR058656
          ; Sun, 6 Oct 2002 20:13:47 +0200 (CEST)
Received: from strontium.pps.jussieu.fr (mail@strontium.pps.jussieu.fr [134.157.168.38])
          by helium.pps.jussieu.fr (8.11.6/jtpda-5.3.2) with ESMTP id g96IDjt45297
          ; Sun, 6 Oct 2002 20:13:47 +0200 (CEST)
Received: from vouillon by strontium.pps.jussieu.fr with local (Exim 3.35 #1 (Debian))
	id 17yFuT-0006D2-00; Sun, 06 Oct 2002 20:13:45 +0200
Date: Sun, 6 Oct 2002 20:13:45 +0200
To: Chris Hecker <checker@d6.com>
Cc: caml-list@inria.fr
Subject: [Caml-list] Coroutines
Message-ID: <20021006181345.GA23808@strontium.pps.jussieu.fr>
References: <4.3.2.7.2.20021004000748.030bd2c0@mail.d6.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=iso-8859-1
Content-Disposition: inline
Content-Transfer-Encoding: 8bit
In-Reply-To: <4.3.2.7.2.20021004000748.030bd2c0@mail.d6.com>
User-Agent: Mutt/1.4i
From: Jerome Vouillon <vouillon@pps.jussieu.fr>
X-Antivirus: scanned by sophie at shiva.jussieu.fr
Sender: owner-caml-list@pauillac.inria.fr
Precedence: bulk

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