From mboxrd@z Thu Jan  1 00:00:00 1970
Received: from mail1-relais-roc.national.inria.fr (mail1-relais-roc.national.inria.fr [192.134.164.82])
	by walapai.inria.fr (8.13.6/8.13.6) with ESMTP id p798FoE6018597
	for <caml-list@sympa-roc.inria.fr>; Tue, 9 Aug 2011 10:15:50 +0200
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: AgcCAITrQE7Nm0HimWdsb2JhbABCmBoCjw8UAQEBAQEICwsHFCWBboFfiDWdR6AUhWdfBIdciyiFEot3
X-IronPort-AV: E=Sophos;i="4.67,342,1309730400"; 
   d="scan'208";a="115347617"
Received: from diamond.nps.edu ([205.155.65.226])
  by mail1-smtp-roc.national.inria.fr with ESMTP; 09 Aug 2011 10:15:44 +0200
Received: from virginia.nps.edu ([205.155.65.15]) by diamond.nps.edu with Microsoft SMTPSVC(6.0.3790.4675);
	 Tue, 9 Aug 2011 01:15:41 -0700
Received: from Adric.ern.nps.edu ([172.20.216.170]) by virginia.nps.edu with Microsoft SMTPSVC(6.0.3790.4675);
	 Tue, 9 Aug 2011 01:15:41 -0700
Received: by Adric.ern.nps.edu (Postfix, from userid 760)
	id 6C177170AF; Tue,  9 Aug 2011 01:13:12 -0700 (PDT)
From: oleg@okmij.org
To: caml-list@inria.fr
Message-Id: <20110809081312.6C177170AF@Adric.ern.nps.edu>
Date: Tue,  9 Aug 2011 01:13:12 -0700 (PDT)
X-OriginalArrivalTime: 09 Aug 2011 08:15:41.0792 (UTC) FILETIME=[87930E00:01CC566C]
X-Validation-by: oleg@okmij.org
Subject: [Caml-list] ANN: Generators in OCaml


The announced small library of generators in OCaml lets us write
generators like those in Python 2 -- as well as generators that go
beyond Python.  The library is a simple overlay over the library
delimcc of delimited continuations in OCaml. The library delimcc is
the only dependency of the generator library.

The library offers three primitives: yield, msplit, and new_prompt.
Prompts, created by new_prompt, are like loop labels in Perl.  The
yield expression delivers its value to any enumerator in scope, not
necessarily the innermost one. One might be surprised at the absence
of enumerators among the primitives. Enumerators are programmed-in;
the library does provide a few popular enumerators such as
for_loop. Users may write enumerators of their own, like for-loop-while
or for-loop-upto, etc. The sample code shows examples of custom
enumerators (including zipWith for parallel loops).  The library also
provides a few generators, such as the analogue of Icon's find -- so
that we can write the examples from Icon's tutorial.

Generator expressions are _expressions_: they may return a value, in
addition to yielding intermediate results. A good example is the
traversal of a binary tree post-order yielding the running sum of
labels of tree branches. Here is the complete code.

type label = int
type tree = Leaf | Node of label * tree * tree;;

let pint = new_prompt ()

let rec post_order = function
  | Leaf -> 0
  | Node (label, left, right) ->
      let sum_left  = post_order left in
      let sum_right = post_order right in
      let sum = sum_left + sum_right + label in
      yield pint sum; sum

for_loop pint (fun () -> Printf.printf "Final: %d\n" (post_order tree1))
   (fun x -> Printf.printf "Got %d\n" x)

Our generators can run side-by-side, hence supporting not only nested
loops but also parallel loops.


The library is simple, consisting of generator.mli and generator.ml,
which can be found in
	http://okmij.org/ftp/ftp/continuations/caml-gen/

The file test_gen.ml has several tests, including tests from Icon's
tutorial. The Makefile tells how to compile the tests as a stand-alone
executable (bytecode or native).

Please see 
	http://okmij.org/ftp/continuations/generators.html#ML

for explanations and derivations of generators. Incidentally, the
comments in generator.ml _derive_ the implementation.