[Caml-list] Wrapping up the Set module in another

[Caml-list] Wrapping up the Set module in another

[John Whitington]

Hi,

Suppose I want to benchmark various toy set implementations, so I have 
already written:

module type SetType =
   sig
     type 'a t
     val set_of_list : 'a list -> 'a t
     val list_of_set : 'a t -> 'a list
     val insert : 'a -> 'a t -> 'a t
     val size : 'a t -> int
     val member : 'a -> 'a t -> bool
   end

and then, for example:

module SetList : sig include SetType end =
   struct
     type 'a t = 'a list

     let list_of_set x = x

     let rec set_of_list l =
       match l with
         [] -> []
       | h::t ->
           if List.mem h t then set_of_list t else h :: set_of_list t

     let insert x l = x :: l

     let size = List.length

     let member = List.mem
   end

This works fine -- I can put them into a little list, and run tests:

let implementations =
   [("Lists", (module SetList : SetType));
    ("Trees", (module SetTree : SetType));
    ("Red-black trees", (module SetRedBlack : SetType));
    ("Hash tables", (module SetHashtbl : SetType))]

Now, it would be nice to include OCaml's Set module, but can it be made 
to fit the signature? So far I have:

let make_setset (type s) () =
   let module SetSet : sig include SetType end =
     struct
       module S = Set.Make (struct type t = s let compare = compare end)

       type 'a t = S.t

       let list_of_set s = S.elements s

       let set_of_list l = List.fold_right S.add l S.empty

       let member = S.mem

       let insert = S.add

       let size = S.cardinal
     end
   in
     (module SetSet : SetType)

and

let implementations =
   let module SetSet = (val (make_setset ())) in
     [("Lists", (module SetList : SetType));
      ("Trees", (module SetTree : SetType));
      ("Red-black trees", (module SetRedBlack : SetType));
      ("Hash tables", (module SetHashtbl : SetType));
      ("OCaml sets", (module SetSet : SetType))]

The problem here, it seems to me, is that the connection between 'a in 
make_setset and (type s) and S.elt is not established, and so the return 
types of list_of_set etc. don't type-check.

Is there any way to do this, or is the functorised implementation of Set 
fundamentally opposed to the normal polymorphism of the type 'a t in 
SetType?

Thanks,

-- 
John Whitington
Director, Coherent Graphics Ltd
http://www.coherentpdf.com/

Re: [Caml-list] Wrapping up the Set module in another

[John Carr]

I think your distinction between types of polymorphism is correct.
Set.S contains monomorphic functions.  You want [forall] but Set.Make
gives you [exists].

The library needs a different Set.OrderedType module for every type to
be stored in a Set.S.t.  You only create one such module per call to
make_setset.


> Hi,
> 
> Suppose I want to benchmark various toy set implementations, so I have
> already written:
> 
> module type SetType =
>   sig
>     type 'a t
>     val set_of_list : 'a list -> 'a t
>     val list_of_set : 'a t -> 'a list
>     val insert : 'a -> 'a t -> 'a t
>     val size : 'a t -> int
>     val member : 'a -> 'a t -> bool
>   end
> 
> and then, for example:
> 
> module SetList : sig include SetType end =
>   struct
>     type 'a t = 'a list
> 
>     let list_of_set x = x
> 
>     let rec set_of_list l =
>       match l with
>         [] -> []
>       | h::t ->
>           if List.mem h t then set_of_list t else h :: set_of_list t
> 
>     let insert x l = x :: l
> 
>     let size = List.length
> 
>     let member = List.mem
>   end
> 
> This works fine -- I can put them into a little list, and run tests:
> 
> let implementations =
>   [("Lists", (module SetList : SetType));
>    ("Trees", (module SetTree : SetType));
>    ("Red-black trees", (module SetRedBlack : SetType));
>    ("Hash tables", (module SetHashtbl : SetType))]
> 
> Now, it would be nice to include OCaml's Set module, but can it be
> made to fit the signature? So far I have:
> 
> let make_setset (type s) () =
>   let module SetSet : sig include SetType end =
>     struct
>       module S = Set.Make (struct type t = s let compare = compare end)
> 
>       type 'a t = S.t
> 
>       let list_of_set s = S.elements s
> 
>       let set_of_list l = List.fold_right S.add l S.empty
> 
>       let member = S.mem
> 
>       let insert = S.add
> 
>       let size = S.cardinal
>     end
>   in
>     (module SetSet : SetType)
> 
> and
> 
> let implementations =
>   let module SetSet = (val (make_setset ())) in
>     [("Lists", (module SetList : SetType));
>      ("Trees", (module SetTree : SetType));
>      ("Red-black trees", (module SetRedBlack : SetType));
>      ("Hash tables", (module SetHashtbl : SetType));
>      ("OCaml sets", (module SetSet : SetType))]
> 
> The problem here, it seems to me, is that the connection between 'a in
> make_setset and (type s) and S.elt is not established, and so the
> return types of list_of_set etc. don't type-check.
> 
> Is there any way to do this, or is the functorised implementation of
> Set fundamentally opposed to the normal polymorphism of the type 'a t
> in SetType?
> 
> Thanks,
> 
> -- 
> John Whitington
> Director, Coherent Graphics Ltd
> http://www.coherentpdf.com/
> 
> 
> -- 
> Caml-list mailing list.  Subscription management and archives:
> https://sympa.inria.fr/sympa/arc/caml-list
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs

Re: [Caml-list] Wrapping up the Set module in another

[Leo White]

It is not at all ideal, and there is almost certainly a better way, but
you could wrap the set module up with the actual set. I also don't know
how much the overhead might affect your benchmarks.

  # module SetSet : SetType = struct
      module type SetS = sig include Set.S val s : t end;;

      type 'a t = (module SetS with type elt = 'a)

      let list_of_set (type elt) ((module S) : elt t) = S.elements S.s

      let set_of_list (type elt) (l : elt list) : elt t =
        (module struct
          include Set.Make (struct type t = elt let compare = compare end)
          let s = List.fold_right add l empty
        end)

      let member (type elt) (x : elt) ((module S) : elt t) = S.mem x S.s

      let insert (type elt) (x : elt) ((module S) : elt t) : elt t =
        (module struct
           include S
           let s = add x S.s
         end)

      let size (type elt) ((module S) : elt t) = S.cardinal S.s

    end;;
  module SetSet : SetType

  # let implementations =
    [("Lists", (module SetList : SetType));
     ("Sets", (module SetSet : SetType))];;
  val implementations : (string * (module SetType)) list =
    [("Lists", <module>); ("Sets", <module>)]

Regards,

Leo

John Whitington <john@coherentgraphics.co.uk> writes:

> Hi,
>
> Suppose I want to benchmark various toy set implementations, so I have already written:
>
> module type SetType =
>   sig
>     type 'a t
>     val set_of_list : 'a list -> 'a t
>     val list_of_set : 'a t -> 'a list
>     val insert : 'a -> 'a t -> 'a t
>     val size : 'a t -> int
>     val member : 'a -> 'a t -> bool
>   end
>
> and then, for example:
>
> module SetList : sig include SetType end =
>   struct
>     type 'a t = 'a list
>
>     let list_of_set x = x
>
>     let rec set_of_list l =
>       match l with
>         [] -> []
>       | h::t ->
>           if List.mem h t then set_of_list t else h :: set_of_list t
>
>     let insert x l = x :: l
>
>     let size = List.length
>
>     let member = List.mem
>   end
>
> This works fine -- I can put them into a little list, and run tests:
>
> let implementations =
>   [("Lists", (module SetList : SetType));
>    ("Trees", (module SetTree : SetType));
>    ("Red-black trees", (module SetRedBlack : SetType));
>    ("Hash tables", (module SetHashtbl : SetType))]
>
> Now, it would be nice to include OCaml's Set module, but can it be made to fit the signature? So far I have:
>
> let make_setset (type s) () =
>   let module SetSet : sig include SetType end =
>     struct
>       module S = Set.Make (struct type t = s let compare = compare end)
>
>       type 'a t = S.t
>
>       let list_of_set s = S.elements s
>
>       let set_of_list l = List.fold_right S.add l S.empty
>
>       let member = S.mem
>
>       let insert = S.add
>
>       let size = S.cardinal
>     end
>   in
>     (module SetSet : SetType)
>
> and
>
> let implementations =
>   let module SetSet = (val (make_setset ())) in
>     [("Lists", (module SetList : SetType));
>      ("Trees", (module SetTree : SetType));
>      ("Red-black trees", (module SetRedBlack : SetType));
>      ("Hash tables", (module SetHashtbl : SetType));
>      ("OCaml sets", (module SetSet : SetType))]
>
> The problem here, it seems to me, is that the connection between 'a in make_setset and (type s) and S.elt is not
> established, and so the return types of list_of_set etc. don't type-check.
>
> Is there any way to do this, or is the functorised implementation of Set fundamentally opposed to the normal
> polymorphism of the type 'a t in SetType?
>
> Thanks,
>
> -- 
> John Whitington
> Director, Coherent Graphics Ltd
> http://www.coherentpdf.com/

Re: [Caml-list] Wrapping up the Set module in another

[Thomas Braibant]

Hi,

I really like this trick of wrapping the module and an actual set
together. Do you have any idea of the runtime cost? I remember reading
that functor applications are runtime operations, but I wonder what is
the overhead.

Best
Thomas

On Wed, Mar 26, 2014 at 9:11 PM, Leo White <lpw25@cam.ac.uk> wrote:
> It is not at all ideal, and there is almost certainly a better way, but
> you could wrap the set module up with the actual set. I also don't know
> how much the overhead might affect your benchmarks.
>
>   # module SetSet : SetType = struct
>       module type SetS = sig include Set.S val s : t end;;
>
>       type 'a t = (module SetS with type elt = 'a)
>
>       let list_of_set (type elt) ((module S) : elt t) = S.elements S.s
>
>       let set_of_list (type elt) (l : elt list) : elt t =
>         (module struct
>           include Set.Make (struct type t = elt let compare = compare end)
>           let s = List.fold_right add l empty
>         end)
>
>       let member (type elt) (x : elt) ((module S) : elt t) = S.mem x S.s
>
>       let insert (type elt) (x : elt) ((module S) : elt t) : elt t =
>         (module struct
>            include S
>            let s = add x S.s
>          end)
>
>       let size (type elt) ((module S) : elt t) = S.cardinal S.s
>
>     end;;
>   module SetSet : SetType
>
>   # let implementations =
>     [("Lists", (module SetList : SetType));
>      ("Sets", (module SetSet : SetType))];;
>   val implementations : (string * (module SetType)) list =
>     [("Lists", <module>); ("Sets", <module>)]
>
> Regards,
>
> Leo
>
> John Whitington <john@coherentgraphics.co.uk> writes:
>
>> Hi,
>>
>> Suppose I want to benchmark various toy set implementations, so I have already written:
>>
>> module type SetType =
>>   sig
>>     type 'a t
>>     val set_of_list : 'a list -> 'a t
>>     val list_of_set : 'a t -> 'a list
>>     val insert : 'a -> 'a t -> 'a t
>>     val size : 'a t -> int
>>     val member : 'a -> 'a t -> bool
>>   end
>>
>> and then, for example:
>>
>> module SetList : sig include SetType end =
>>   struct
>>     type 'a t = 'a list
>>
>>     let list_of_set x = x
>>
>>     let rec set_of_list l =
>>       match l with
>>         [] -> []
>>       | h::t ->
>>           if List.mem h t then set_of_list t else h :: set_of_list t
>>
>>     let insert x l = x :: l
>>
>>     let size = List.length
>>
>>     let member = List.mem
>>   end
>>
>> This works fine -- I can put them into a little list, and run tests:
>>
>> let implementations =
>>   [("Lists", (module SetList : SetType));
>>    ("Trees", (module SetTree : SetType));
>>    ("Red-black trees", (module SetRedBlack : SetType));
>>    ("Hash tables", (module SetHashtbl : SetType))]
>>
>> Now, it would be nice to include OCaml's Set module, but can it be made to fit the signature? So far I have:
>>
>> let make_setset (type s) () =
>>   let module SetSet : sig include SetType end =
>>     struct
>>       module S = Set.Make (struct type t = s let compare = compare end)
>>
>>       type 'a t = S.t
>>
>>       let list_of_set s = S.elements s
>>
>>       let set_of_list l = List.fold_right S.add l S.empty
>>
>>       let member = S.mem
>>
>>       let insert = S.add
>>
>>       let size = S.cardinal
>>     end
>>   in
>>     (module SetSet : SetType)
>>
>> and
>>
>> let implementations =
>>   let module SetSet = (val (make_setset ())) in
>>     [("Lists", (module SetList : SetType));
>>      ("Trees", (module SetTree : SetType));
>>      ("Red-black trees", (module SetRedBlack : SetType));
>>      ("Hash tables", (module SetHashtbl : SetType));
>>      ("OCaml sets", (module SetSet : SetType))]
>>
>> The problem here, it seems to me, is that the connection between 'a in make_setset and (type s) and S.elt is not
>> established, and so the return types of list_of_set etc. don't type-check.
>>
>> Is there any way to do this, or is the functorised implementation of Set fundamentally opposed to the normal
>> polymorphism of the type 'a t in SetType?
>>
>> Thanks,
>>
>> --
>> John Whitington
>> Director, Coherent Graphics Ltd
>> http://www.coherentpdf.com/
>
> --
> Caml-list mailing list.  Subscription management and archives:
> https://sympa.inria.fr/sympa/arc/caml-list
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs

Re: [Caml-list] Wrapping up the Set module in another

[Leo White]

I'm afraid I don't have any real idea of the runtime cost.

The main additional cost would come from calling `Set.Make` in
`set_of_list` and creating new modules in `set_of_list` and `insert`.
`Set.Make` has to create a lot of closures which capture the `compare`
function. I think these closures are all allocated at once, but this
still means a lot of assignments. Creating the new modules is a record
allocation and assignment of all the record fields.

The cost of creating modules could probably be reduced a bit by
rewriting it as:

    module type SetS = sig module Ops : Set.S val s : Ops.t end;;

    type 'a t = (module SetS with type Ops.elt = 'a)

    let list_of_set (type elt) ((module S) : elt t) = S.Ops.elements S.s

    let set_of_list (type elt) (l : elt list) : elt t =
      (module struct
        module Ops = Set.Make (struct type t = elt let compare = compare end)
        let s = List.fold_right Ops.add l Ops.empty
      end)

    let member (type elt) (x : elt) ((module S) : elt t) = S.Ops.mem x S.s

    let insert (type elt) (x : elt) ((module S) : elt t) : elt t =
      (module struct
         module Ops = S.Ops
         let s = add x S.s
       end)

    let size (type elt) ((module S) : elt t) = S.Ops.cardinal S.s

There would also be a cost in the other functions for the indirection to
get to the actual set and the functions.

Theoretically it might also be slower than using the result of
`Set.Make` directly since that would be easier for the compiler to
optimise by calling the functions directly or inlining them, although
I'm not sure if the current compiler actually does this.

Regards,

Leo

Thomas Braibant <thomas.braibant@gmail.com> writes:

> Hi,
>
> I really like this trick of wrapping the module and an actual set
> together. Do you have any idea of the runtime cost? I remember reading
> that functor applications are runtime operations, but I wonder what is
> the overhead.
>
> Best
> Thomas
>
> On Wed, Mar 26, 2014 at 9:11 PM, Leo White <lpw25@cam.ac.uk> wrote:
>> It is not at all ideal, and there is almost certainly a better way, but
>> you could wrap the set module up with the actual set. I also don't know
>> how much the overhead might affect your benchmarks.
>>
>>   # module SetSet : SetType = struct
>>       module type SetS = sig include Set.S val s : t end;;
>>
>>       type 'a t = (module SetS with type elt = 'a)
>>
>>       let list_of_set (type elt) ((module S) : elt t) = S.elements S.s
>>
>>       let set_of_list (type elt) (l : elt list) : elt t =
>>         (module struct
>>           include Set.Make (struct type t = elt let compare = compare end)
>>           let s = List.fold_right add l empty
>>         end)
>>
>>       let member (type elt) (x : elt) ((module S) : elt t) = S.mem x S.s
>>
>>       let insert (type elt) (x : elt) ((module S) : elt t) : elt t =
>>         (module struct
>>            include S
>>            let s = add x S.s
>>          end)
>>
>>       let size (type elt) ((module S) : elt t) = S.cardinal S.s
>>
>>     end;;
>>   module SetSet : SetType
>>
>>   # let implementations =
>>     [("Lists", (module SetList : SetType));
>>      ("Sets", (module SetSet : SetType))];;
>>   val implementations : (string * (module SetType)) list =
>>     [("Lists", <module>); ("Sets", <module>)]
>>
>> Regards,
>>
>> Leo
>>
>> John Whitington <john@coherentgraphics.co.uk> writes:
>>
>>> Hi,
>>>
>>> Suppose I want to benchmark various toy set implementations, so I have already written:
>>>
>>> module type SetType =
>>>   sig
>>>     type 'a t
>>>     val set_of_list : 'a list -> 'a t
>>>     val list_of_set : 'a t -> 'a list
>>>     val insert : 'a -> 'a t -> 'a t
>>>     val size : 'a t -> int
>>>     val member : 'a -> 'a t -> bool
>>>   end
>>>
>>> and then, for example:
>>>
>>> module SetList : sig include SetType end =
>>>   struct
>>>     type 'a t = 'a list
>>>
>>>     let list_of_set x = x
>>>
>>>     let rec set_of_list l =
>>>       match l with
>>>         [] -> []
>>>       | h::t ->
>>>           if List.mem h t then set_of_list t else h :: set_of_list t
>>>
>>>     let insert x l = x :: l
>>>
>>>     let size = List.length
>>>
>>>     let member = List.mem
>>>   end
>>>
>>> This works fine -- I can put them into a little list, and run tests:
>>>
>>> let implementations =
>>>   [("Lists", (module SetList : SetType));
>>>    ("Trees", (module SetTree : SetType));
>>>    ("Red-black trees", (module SetRedBlack : SetType));
>>>    ("Hash tables", (module SetHashtbl : SetType))]
>>>
>>> Now, it would be nice to include OCaml's Set module, but can it be made to fit the signature? So far I have:
>>>
>>> let make_setset (type s) () =
>>>   let module SetSet : sig include SetType end =
>>>     struct
>>>       module S = Set.Make (struct type t = s let compare = compare end)
>>>
>>>       type 'a t = S.t
>>>
>>>       let list_of_set s = S.elements s
>>>
>>>       let set_of_list l = List.fold_right S.add l S.empty
>>>
>>>       let member = S.mem
>>>
>>>       let insert = S.add
>>>
>>>       let size = S.cardinal
>>>     end
>>>   in
>>>     (module SetSet : SetType)
>>>
>>> and
>>>
>>> let implementations =
>>>   let module SetSet = (val (make_setset ())) in
>>>     [("Lists", (module SetList : SetType));
>>>      ("Trees", (module SetTree : SetType));
>>>      ("Red-black trees", (module SetRedBlack : SetType));
>>>      ("Hash tables", (module SetHashtbl : SetType));
>>>      ("OCaml sets", (module SetSet : SetType))]
>>>
>>> The problem here, it seems to me, is that the connection between 'a in make_setset and (type s) and S.elt is not
>>> established, and so the return types of list_of_set etc. don't type-check.
>>>
>>> Is there any way to do this, or is the functorised implementation of Set fundamentally opposed to the normal
>>> polymorphism of the type 'a t in SetType?
>>>
>>> Thanks,
>>>
>>> --
>>> John Whitington
>>> Director, Coherent Graphics Ltd
>>> http://www.coherentpdf.com/
>>
>> --
>> Caml-list mailing list.  Subscription management and archives:
>> https://sympa.inria.fr/sympa/arc/caml-list
>> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
>> Bug reports: http://caml.inria.fr/bin/caml-bugs

[Caml-list] More efficient compilation of functors? (was: Wrapping up the Set module in another)

[Alain Frisch]

On 4/3/2014 4:28 PM, Leo White wrote:
> The main additional cost would come from calling `Set.Make` in
> `set_of_list` and creating new modules in `set_of_list` and `insert`.
> `Set.Make` has to create a lot of closures which capture the `compare`
> function. I think these closures are all allocated at once, but this
> still means a lot of assignments. Creating the new modules is a record
> allocation and assignment of all the record fields.

I'm wondering whether an alternative compilation scheme could make 
functor instantiation much faster.  Instead of having individual 
closures for all (non-closed) functions the functor exports, one could 
create a single big closure representing all functions at once.  It 
would typically contain the functor's argument itself, plus other non 
functional values computed during the functor's body initialization (or 
maybe one could even keep a reference to the block representing the 
functor's result).  The closure would be allocated at the beginning 
(with dummy values) and filled along the evaluation of the body.


-- Alain