[Caml-list] Higher order functors over tuples

[Caml-list] Higher order functors over tuples

[Ivan Gotovchits]

Good day,

1. A problem in general 

In general, the problem is to compute a tuple of objects that have
types different, but conforming to the same interface, i.e., given a
group of modules (A,B,C), conforming to signature S to construct some 

   module M: functor(A:S) -> functor(B:S) -> functor(C:S) -> S

that will, in a some way, «map/reduce» computation on corresponding
modules.

The problem can be generalized further, but, it seems to me, that it is
already quite (too?) abstract.

As far as I can see, there is no ad hoc solution for this problem in
OCaml, except, of course, objects with their late binding. But, in some
circumstances, the late binding can be avoided. In particular, when
types of modules and their amount are known and fixed at compile time.


2. Particular problem 

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. 

The «list» can be made of pairs, using the cons (meta)constructor:

   module Cons :
     functor(G1:Generator) -> functor(G2:Generator) -> Generator

So, if I have three modules A,B,C, I can construct module

   M = Cons(A)(Cons(B)(C))

and call M.step, to move a chain of generators forward, or M.result to
get the current result.


3. Particular solution

Here is the implementation on Cons module (named ConsGenerator), that "steps"
contained generators in a sequence (swapping them on each step).

   module ConsGenerator
       (G1:Generator)
       (G2:Generator with type r = G1.r)
       : Generator with type r = G2.r = 
   struct
     type t =
       | G1G2 of (G1.t option * G2.t option )
       | G2G1 of (G2.t option * G1.t option )

     type r = G2.r

     let create () =
       G1G2 ((Some (G1.create ())), Some (G2.create ()))

     let step = function
       | G1G2 (g1, Some g2)   -> Some (G2G1 (G2.step g2, g1))
       | G2G1 (g2, Some g1)   -> Some (G1G2 (G1.step g1, g2))
       | G2G1 (Some g2, None) -> Some (G2G1 (G2.step g2, None))
       | G1G2 (Some g1, None) -> Some (G1G2 (G1.step g1, None))
       | G1G2 (None,None) | G2G1 (None,None) -> None

     let result = function
       | G1G2 (Some g1,_) -> G1.result g1
       | G2G1 (Some g2,_) -> G2.result g2
       | G1G2 (None,_) | G2G1 (None,_) -> None
   end

Function `proceed' iterates module M and print results

   let rec proceed oe = match M.step oe with 
     | Some oe -> begin 
       match M.result oe with
         | Some r -> print_int r; proceed oe
         | None   -> proceed oe
     end
     | None -> print_newline (); 
         print_endline "generator finished"      

Just for a completness of the example a pair of simple generators:

   module Odd : Generator with type r = int = struct
     type t = int
     type r = int
     let create () = -1
     let step v = if v < 10 then Some (v+2) else None
     let result v = if v <= 9 then Some v else None
   end

   module Even : Generator with type r = int = struct
     type t = int
     type r = int
     let create () = 0
     let step v = if v < 10 then Some (v+2) else None
     let result v = if v <= 8 then Some v else None
   end

and the result was
   # module M = Cons(Even)(Cons(Cons(Odd)(Even))(Even))
   # let _  = proceed (M.create ())
   22244618648365879
   generator finished
   - : unit = ()


4. Question

And now the questions!

1) Is there any idiomatic solution to this pattern?

2) If not, can my solution be improved in some way? And how?

3) My intution says that it can be solved with monads (Generator really
incapsulates side effects in a step. Several computation are combined in
one big chain... ). Am I right? If so, how to implement it in monads?

Thanks for reading down to this line =) Any comments are welcome!

P.S. Sorry for such a long article. I haven't enough brains to make it
shorter =)

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

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

[Didier Cassirame]

[-- Attachment #1: Type: text/plain, Size: 5049 bytes --]

Hi Ivan,

2012/10/31 Ivan Gotovchits <ivg@ieee.org>

>
> Good day,
>
> 1. A problem in general
>
> In general, the problem is to compute a tuple of objects that have
> types different, but conforming to the same interface, i.e., given a
> group of modules (A,B,C), conforming to signature S to construct some
>
>    module M: functor(A:S) -> functor(B:S) -> functor(C:S) -> S
>
> that will, in a some way, «map/reduce» computation on corresponding
> modules.
>

Do you wish to have parallel computation done with these modules, or do you
mean that you want them to be combined sequentially?


>
> The problem can be generalized further, but, it seems to me, that it is
> already quite (too?) abstract.
>
> As far as I can see, there is no ad hoc solution for this problem in
> OCaml, except, of course, objects with their late binding. But, in some
> circumstances, the late binding can be avoided. In particular, when
> types of modules and their amount are known and fixed at compile time.
>

> 2. Particular problem
>
> 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.
>
> The «list» can be made of pairs, using the cons (meta)constructor:
>
>    module Cons :
>      functor(G1:Generator) -> functor(G2:Generator) -> Generator
>
> So, if I have three modules A,B,C, I can construct module
>
>    M = Cons(A)(Cons(B)(C))
>
> and call M.step, to move a chain of generators forward, or M.result to
> get the current result.
>
>
> 3. Particular solution
>
> Here is the implementation on Cons module (named ConsGenerator), that
> "steps"
> contained generators in a sequence (swapping them on each step).
>
>    module ConsGenerator
>        (G1:Generator)
>        (G2:Generator with type r = G1.r)
>        : Generator with type r = G2.r =
>    struct
>      type t =
>        | G1G2 of (G1.t option * G2.t option )
>        | G2G1 of (G2.t option * G1.t option )
>
>      type r = G2.r
>
>      let create () =
>        G1G2 ((Some (G1.create ())), Some (G2.create ()))
>
>      let step = function
>        | G1G2 (g1, Some g2)   -> Some (G2G1 (G2.step g2, g1))
>        | G2G1 (g2, Some g1)   -> Some (G1G2 (G1.step g1, g2))
>        | G2G1 (Some g2, None) -> Some (G2G1 (G2.step g2, None))
>        | G1G2 (Some g1, None) -> Some (G1G2 (G1.step g1, None))
>        | G1G2 (None,None) | G2G1 (None,None) -> None
>
>      let result = function
>        | G1G2 (Some g1,_) -> G1.result g1
>        | G2G1 (Some g2,_) -> G2.result g2
>        | G1G2 (None,_) | G2G1 (None,_) -> None
>    end
>
> Function `proceed' iterates module M and print results
>
>    let rec proceed oe = match M.step oe with
>      | Some oe -> begin
>        match M.result oe with
>          | Some r -> print_int r; proceed oe
>          | None   -> proceed oe
>      end
>      | None -> print_newline ();
>          print_endline "generator finished"
>
> Just for a completness of the example a pair of simple generators:
>
>    module Odd : Generator with type r = int = struct
>      type t = int
>      type r = int
>      let create () = -1
>      let step v = if v < 10 then Some (v+2) else None
>      let result v = if v <= 9 then Some v else None
>    end
>
>    module Even : Generator with type r = int = struct
>      type t = int
>      type r = int
>      let create () = 0
>      let step v = if v < 10 then Some (v+2) else None
>      let result v = if v <= 8 then Some v else None
>    end
>
> and the result was
>    # module M = Cons(Even)(Cons(Cons(Odd)(Even))(Even))
>    # let _  = proceed (M.create ())
>    22244618648365879
>    generator finished
>    - : unit = ()
>
>
> 4. Question
>
> And now the questions!
>
> 1) Is there any idiomatic solution to this pattern?
>
> 2) If not, can my solution be improved in some way? And how?
>

Thanks to a very recent post, I rediscovered that OCaml can handle modules
as first class values (since ver. 3.12) :

- you can define types based on module types like this.

module type M = sig ... end

type m = (module M)

and then you should be able to build simple lists of type m.



> 3) My intution says that it can be solved with monads (Generator really
> incapsulates side effects in a step. Several computation are combined in
> one big chain... ). Am I right? If so, how to implement it in monads?
>

I guess that you could use the type above with regular monads too.

If you don't have access to that feature, you could perhaps use higher
order functors?


Cheers,

didier

[-- Attachment #2: Type: text/html, Size: 6293 bytes --]

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

[Ivan Gotovchits]

Didier Cassirame <didier.cassirame@gmail.com> writes:

> Do you wish to have parallel computation done with these modules, or
> do you mean that you want them to be combined sequentially?

Ideally, computation must be combined arbitrary. It will be nice to have
MAP functor, or MAP2 functor, etc. 

> Thanks to a very recent post, I rediscovered that OCaml can handle modules as first class values (since ver. 3.12) :
>
> - you can define types based on module types like this.
>
> module type M = sig ... end
>
> type m = (module M)
>
> and then you should be able to build simple lists of type m.

I've heard that it is possible, but unfortunately I'm stucked with 3.11
;'( And I'm not still sure that it will work. Need to try it myself =)


>     3) My intution says that it can be solved with monads (Generator really
>     incapsulates side effects in a step. Several computation are combined in
>     one big chain... ). Am I right? If so, how to implement it in monads?
>
> I guess that you could use the type above with regular monads too.

Hmmm, the problem is that I do not understand monads quite well. So I've
solved the task in a «my» way. And so I want to know how the problem can
(and could it?) be solved with monads, which are considered a common and
idiomatic way of solving such problems.

>
> If you don't have access to that feature, you could perhaps use higher order functors?

I do use them. I generate a list of modules using higher order
functor. For example I build structure of modules [Even, Odd, Even, Odd] 
with 
   module M = Cons(Even)(Cons(Odd)(Cons(Even)(Odd)))

Calling ``let m = M.create ()'' will build some structure of objects of different
types. (Their can be more two types of modules). A call to ``M.step m''
will apply ``Even.step'' or ``Odd.step'' to the last objects in a list,
and move it to the head. A call ``M.result m'' will return the
result of calling ``Even.result m'' or ``Odd.result m'' dependingly on a
current type in head of list.

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

[Caml-list] ocamlc, ocamlopt stackoverflow on list

[Christophe Raffalli]

[-- Attachment #1: Type: text/plain, Size: 1307 bytes --]


Hello,

On my machine (ocaml 3.12.1 on linux 64 bits) with unlimited stack,
ocamlc and ocamlopt fails to compile a list constant of length 30000
which is a problem in code generated by another program.

Should this be considered a bug ?

Here is how to reproduce with grandelist.ml give below:

raffalli@d45-lama:~/Caml/patoline$ ocaml grandeliste.ml > foo.ml
raffalli@d45-lama:~/Caml/patoline$ ocamlc -c foo.ml
Fatal error: exception Stack_overflow
raffalli@d45-lama:~/Caml/patoline$ ocamlopt -c foo.ml
Fatal error: exception Stack_overflow

----------------- grandeliste.ml --------------------
open Printf

let _ =
  printf "let l = [";
  for i = 0 to 30000 do
    printf "%d;\n" i
  done;
  printf "0]"
----------------- grandeliste.ml --------------------

-- 
Christophe Raffalli
Universite de Savoie
Batiment Le Chablais, bureau 21
73376 Le Bourget-du-Lac Cedex

tel: (33) 4 79 75 81 03
fax: (33) 4 79 75 87 42
mail: Christophe.Raffalli@univ-savoie.fr
www: http://www.lama.univ-savoie.fr/~RAFFALLI
---------------------------------------------
IMPORTANT: this mail is signed using PGP/MIME
At least Enigmail/Mozilla, mutt or evolution
can check this signature. The public key is
stored on www.keyserver.net
---------------------------------------------


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 259 bytes --]

Re: [Caml-list] ocamlc, ocamlopt stackoverflow on list

[Gabriel Scherer]

My (entirely personal) understanding of the matter is that making
every part of the compiler tail-recursive is a pain in the ass, and
the kind of issues that never really stop happening (fix some case and
the stack will blow somewhere else). Given the potential decrease of
readability¹ that such changes may incur, there is even less incentive
to accept fixes on these issues.

¹: and eventual decrease of performance on small inputs, even if that
is less important in the compiler code

I would therefore suggest changing the generated code to look like the
following (modulo order-of-evaluation issues):

  let li = 29000::29001::...::[] in
  let li = 28000::28001::...::li in
  ...
  let li = 0::1::2::...::li in
  li

Remark: if the list is "quadratically too long", you may still
segfault because of the excessive nesting of (let .. in ..) in this
code. I'm unsure this could happen with a reasonable lower bound on
permitted stack usage, but this could be fixed as well with another
level of splitting: let li = (let li = ... in let li = ... in ... li)
in let li = ( ... ) in ...

On Fri, Nov 30, 2012 at 1:49 PM, Christophe Raffalli
<christophe.raffalli@univ-savoie.fr> wrote:
>
> On my machine (ocaml 3.12.1 on linux 64 bits) with unlimited stack,
> ocamlc and ocamlopt fails to compile a list constant of length 30000
> which is a problem in code generated by another program.

Re: [Caml-list] ocamlc, ocamlopt stackoverflow on list

[Christophe Raffalli]

[-- Attachment #1: Type: text/plain, Size: 911 bytes --]

Le 30/11/2012 14:20, Gabriel Scherer a écrit :
> My (entirely personal) understanding of the matter is that making
> every part of the compiler tail-recursive is a pain in the ass, and

I Think with list of size 30000 it might not be only a problem of tailrec (it seems
to fail to parse in fact with a difference error message with ocamlc and ocamlc -pp camlp4o).

Cheers,
Christophe

-- 
Christophe Raffalli
Universite de Savoie
Batiment Le Chablais, bureau 21
73376 Le Bourget-du-Lac Cedex

tel: (33) 4 79 75 81 03
fax: (33) 4 79 75 87 42
mail: Christophe.Raffalli@univ-savoie.fr
www: http://www.lama.univ-savoie.fr/~RAFFALLI
---------------------------------------------
IMPORTANT: this mail is signed using PGP/MIME
At least Enigmail/Mozilla, mutt or evolution
can check this signature. The public key is
stored on www.keyserver.net
---------------------------------------------


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 259 bytes --]

Re: [Caml-list] ocamlc, ocamlopt stackoverflow on list

[Gabriel Scherer]

It works with small lists, blows up with a Stack Overflow on a
really-unbalanced parsetree, I would really assume it is a
tail-recursion issue. I checked that the failure happens after parsing
time (-dparsetree produces an output); camlp4 must also have a
(different) non-tail-rec code path somewhere.

The easiest way to find out where this particular instance
of the problem lies would be to build a version of the compiler
with debug information and invoke
  OCAMLRUNPARAM="b ocamlc ...

On Fri, Nov 30, 2012 at 2:31 PM, Christophe Raffalli
<christophe.raffalli@univ-savoie.fr> wrote:
>
> I Think with list of size 30000 it might not be only a problem of tailrec (it seems
> to fail to parse in fact with a difference error message with ocamlc and ocamlc -pp camlp4o).

[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