[ANN] SDFlow: combinatorial dataflow programming library

[ANN] SDFlow: combinatorial dataflow programming library

[Zheng Li]

Hi,

The recent discussion [1] reminds me of some previous exploration on related
topics. By making some clean up to the old code, I'd like to announce the
availability of SDFlow, a small library for high-level combinatorial dataflow
programming in OCaml.

The library is licensed under LGPL+linking exception. You can get everything
related at http://www.pps.jussieu.fr/~li/software/index.html#sdflow 

Note that the code is still experimental, and poorly documented for the
moment. 

[1] http://groups.google.com/group/fa.caml/browse_frm/thread/e4a5674c28233a0b/012d1433d5053ce1?lnk=raot#012d1433d5053ce1


The following part is extracted from README:

-----------------------------------------------------------------------------

== Description ==

SDFlow stands for Structured Data Flow. It's a high-level combinatorial
dataflow programming library based upon destructive(*) lazy streams. Its base
type is compatible with stream of standard OCaml. 


== Introduction ==

Besides the only kind of practical applications we have in mind --- to help
constructing alternative dataflow interfaces for other libraries, the main
functionality of the library is just "for fun". You can experience the
following programming paradigms with SDFlow in plain OCaml:

  * combinatorial dataflow programming
  * programming with lazy sequence 
  * deterministic non-strict evaluation
  * pointfree programming (or one-liner programming)

Primitives provided:

  * conversion: 
      of_fun, of_list, of_string, of_channel
      to_fun, to_list, to_string, to_channel
  * flow creation: 
      seq, enum, repeat, cycle, (--)
  * flow consuming:
      peek, next, iter, foldl/foldr/fold
  * flow arithmetic:
      cons, apnd, is_empty, filter, concat, 
      take/drop, take_/drop_while, span/break, group
  * flows pair arithmetic:
      dup, comb/split, merge/switch
  * flows array arithmetic:
      dupn, combn/splitn, mergen/switchn
  * computation over flow
      map, map2, scanl, scan, map_fold
  * circular flow
      feedl/feelr, circ
  * high-level flow combinator
      while_do/do_while, farm, pipe(///), pardo(//)
  * shorthand operator and helper
      |>, @., |-, -|, //, curry/uncurry, id

The library is currently short of documentation, you'd better refer to the
manual page.


== Example ==

* sum(n) sequence

# let sums = enum 1 |> scan (+);;
val sums : int flow = <abstr>
# sums |> take_while ((>) 100) |> to_list;;
- : int list = [1; 3; 6; 10; 15; 21; 28; 36; 45; 55; 66; 78; 91]

* Fibonacci number sequence 

# let fibs = map2 (+) |- circ [<'1>] |> circ [<'0;'0>];;
val fibs : int flow = <abstr>
# fibs |> take 10 |> to_list;;
- : int list = [1; 1; 2; 3; 5; 8; 13; 21; 34; 55]

* stupid computation

      3+33  6+33  9+33  12+33  15+33  18+33
c = [ ----, ----, ----, -----, -----, -----, ... )
        2     4     8     10     14     16

# let modv v x = x mod v = 0;;
# let cl = uncurry (map2(/)) -| map((+)33) // filter(modv 2) -| switch(modv 3);;
val cl : int flow -> int flow = <fun>
# enum 1 |> cl |> take_while ((<) 1) |> iter print_int;;
1895433222222- : unit = ()

* remove every 3th

# let mv3 = cycle [<'true;'true;'false>] |> curry comb |- filter fst |- map snd;;
val mv3 : '_a flow -> '_a flow = <fun>
# enum 1 |> mv3 |> take 15 |> to_list;;
- : int list = [1; 2; 4; 5; 7; 8; 10; 11; 13; 14; 16; 17; 19; 20; 22]

* group sum 

group and sum when (sum mod 6) = 0 
e.g. [ 1+2+3, 4+5+6+7+8, 9+10+11, 12+13+14+15, 16+17+18+19+20, 21+22+23, ... ]

# let f a x = let r = a+x in r, if modv 6 r then Some true else None;;
# enum 1 |> map_fold f |> take 10 |> to_list;;
- : int list = [6; 30; 30; 54; 90; 66; 102; 150; 102; 150]

* non-strict evaluation

Strict computation over 5 loops forever, all the rest computation is blocked.

# 1--9 |> (while_do ((=)5) (map id) |- iter (print_int |- flush_all));;
1234  C-c C-cInterrupted.

We can still evaluate the rest if we increase the capacity of do_while's sub
dataflow network. Note that the evaluation is non-strict but deterministic.

# 1--9 |> (while_do ~size:2 ((=)5) (map id) |- iter (print_int |- flush_all));;
12346789
  C-c C-cInterrupted.


(*) It won't be particularly difficult to implement another persistent version,
like lazy list. But for now I haven't seen enough reason to do so.

-------------------------------------------------------------------------------

-- 
Zheng Li
http://www.pps.jussieu.fr/~li