[Caml-list] Higher order functors over tuples

[Caml-list] Higher order functors over tuples

[oleg]

Ivan Gotovchits wrote
> In general, the problem is to compute a tuple of objects that have
> types different, but conforming to the same interface
That seems to be the right problem for existentials -- which exist in
OCaml under the name of objects. Methods are the interface and fields
are private data. Of course we can get by with mere records -- but if
we have objects anyway we might as well use them.

> For example, we have several different data generator modules conforming
> to the signature

>    module type Generator =
>    sig
>      type t
>      type r
>      val create: unit  -> t
>      val result: t -> r option
>      val step:   t -> t option
>    end

> Each generator can be stepped forward and queried for a result. Generator
> can expire, in such case it will return None as a result. I want to make a
> ?list? of different generators and do some arbitary iterations on them.

Here is the implementation of that example using objects. It seems the
object implementation provides the same static assurances and
abstractions as the module implementation. Since generators can
expire, the effective number of generators does change
dynamically. The static tupling doesn't buy us much.

(* The interface of generators *)

class type ['r] generator = object ('self)
    method result : unit -> 'r option
    method step   : unit -> 'self option
end;;


(* Function `proceed' iterates over the generator and print results *)

let rec proceed : int generator -> unit = fun gen ->
  match gen#step () with
  | Some gen -> begin
      match gen#result () with
      | Some r -> print_int r; proceed gen
      | None   -> proceed gen
  end
  | None -> print_newline ();
      print_endline "generator finished"
;;

(* Just for a completness of the example a pair of simple generators: *)

class odd : int -> [int] generator = fun init -> object
    val v = init
    method step () = if v <= 10 then Some {< v = v + 2 >} else None
    method result () = if v <= 9 then Some v else None
end
;;

(* A different way to constrain the type *)
class even init = object (self : int #generator)
    val v = init
    method step () = if v <= 10 then Some {< v = v + 2 >} else None
    method result () = if v <= 8 then Some v else None
end
;;

(* Make a list of generators itself a generator *)

let gen_list : 'r generator list -> 'r generator = fun gens -> object
    val v = gens
    method step () = 
      let rec loop = function
	| [] -> None
	| h :: t -> 
	    begin match h#step () with 
            | None -> loop t
	    | Some gen -> Some {< v = t @ [gen]  >}
	    end
      in loop v

    (* find the first generator that gives a result *)
    method result () =
      let rec loop = function
	| [] -> None
	| h :: t -> 
	    begin match h#result () with 
            | None -> loop t
	    | r    ->  r
	    end
      in loop (List.rev v)
end
;;


let a_gen_list = gen_list [new even 0;
			   new odd (-1);
			   new even 0;
			   new even 0];;


proceed a_gen_list;;

212243446566878889999
generator finished

[Caml-list] Re: Higher order functors over tuples

[Ivan Gotovchits]

oleg@okmij.org writes:
> That seems to be the right problem for existentials -- which exist in
> OCaml under the name of objects. Methods are the interface and fields
> are private data. Of course we can get by with mere records -- but if
> we have objects anyway we might as well use them.

Yes, but objects suffer from two slight problems: lower performance due
to dynamic method dispatching and some issues with type system. Well,
not an issues really, but I think that you understood me. Though it
seems that this problems do not outweight the power of object system,
that was gracefully demonstrated by you.

In my real application I do shifted to objects. Though I still define
modules and then use functors as factories, producing objects of the
particular types. I'm not sure that this dual solution worths, but I
feel myself more comfortable with modules, rather than objects.

And, by the way, I've met the following signatures many times in
different frameworks written in different languages (matlab functional
objects, GnuRadio blocks, to name a few):

>>    module type Generator =
>>    sig
>>      type t
>>      type r
>>      val create: unit  -> t
>>      val result: t -> r option
>>      val step:   t -> t option
>>    end

extended with Transformer and Consumer:

  module type Consumer = 
  sig 
    type t
    type d
    val push: d -> t -> t
    val step: t -> t option
  end

  module type Transformer =
  sig
    type t
    type d
    type r
    val push: d -> t -> t
    val step: t -> t option
    val result: t -> r option
    (* or include Transformer and Consumer in ocaml 3.12+ *)        
  end

Haven't you seen this pattern in functional programming? May be it can
be expressed in a more natural way using FP idioms?


-- 
         (__) 
         (oo) 
   /------\/ 
  / |    ||   
 *  /\---/\ 
    ~~   ~~   
...."Have you mooed today?"...

[Caml-list] Re: Higher order functors over tuples

[oleg]

> And, by the way, I've met the following signatures many times in
> different frameworks written in different languages (matlab functional
> objects, GnuRadio blocks, to name a few):

>>    module type Generator =
>>    sig
>>      type t
>>      type r
>>      val create: unit  -> t
>>      val result: t -> r option
>>      val step:   t -> t option
>>    end

Well, if we re-write it in object style, but without objects, we obtain

    type 'r stream_v = EOF | Stream of 'r option * 'r stream
    and 'r stream = unit -> 'r stream_v

which is what it says. Here's the important paper that describes the
pattern in great detail and with many applications:

	Duncan Coutts and Roman Leshchinskiy and Don Stewart
	Stream Fusion. From Lists to Streams to Nothing at All
	ICFP 07
	http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.104.7401

Incidentally, iteratees are somewhat similar.

[Caml-list] Re: Higher order functors over tuples

[Ivan Gotovchits]

oleg@okmij.org writes:

>
> Well, if we re-write it in object style, but without objects, we obtain
>
>     type 'r stream_v = EOF | Stream of 'r option * 'r stream
>     and 'r stream = unit -> 'r stream_v
>
> which is what it says. Here's the important paper that describes the
> pattern in great detail and with many applications:
>
> 	Duncan Coutts and Roman Leshchinskiy and Don Stewart
> 	Stream Fusion. From Lists to Streams to Nothing at All
> 	ICFP 07
> 	http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.104.7401
>
> Incidentally, iteratees are somewhat similar.
>
Many thanks! This is what I was searching for.