Functors + polymorphism = confusion

Functors + polymorphism = confusion

[Jonathan T Bryant]

I'm having some trouble getting functors to play nice with polymorphism.

I'm using a functor to parallelize a function, so given a function 
wrapped up in a module, I apply a functor to it get a module with 
several parallel versions of the function.  The in/output of the 
functions have to be types wrapped up in a Message module (as they may 
need to be serialized).

This is pretty trivial for monomorphic functions, but I can't seem to 
define the Bind functor correctly to allow a polymorphic function 
definition which is bound to two message types at functor application.  
I've tried every variation on the theme I can think of, but I can't 
seem to make it work.

Is what I'm trying to do possible?  I think it is because I did 
something similar for polymorphic messages (included in code, but not 
used).  Maybe someone could point out to me something I'm overlooking?

(Code inlined below)

Thanks,
--Jonathan

functor_test.mli
----------------

module type Message =
  sig
    type t
    val to_string : t -> string
    val of_string : string -> t
  end

module type PolyMessage =
  functor (M : Message) ->
  sig
    type 'a t
    val to_string : M.t t -> string
    val of_string : string -> M.t t
  end

module BindMessage :
  functor (P : PolyMessage) ->
  functor (M : Message) ->
  Message

module type Function =
  sig
    module A : Message
    module B : Message
    val f : A.t -> B.t
  end

module type PolyFunction =
  (*
  functor (A : Message) ->
  functor (B : Message) ->
  *)
  sig
    (* val f : A.t -> B.t *)
    val f : 'a -> 'b
  end

module BindFunction :
  functor (F : PolyFunction) ->
  functor (A : Message) ->
  functor (B : Message) ->
  Function

module type ParallelFunction =
  sig
    module A : Message
    module B : Message
    val sequential : A.t -> B.t
    val concurrent : A.t -> B.t
    val parallel : A.t -> B.t
    val remote : A.t -> B.t
  end

module Parallelize : functor (F : Function) -> ParallelFunction

module IntMessage : Message
module FloatMessage : Message

module Double : Function

module Identity : PolyFunction
module BoundIdentity : Function

module ParallelDouble : ParallelFunction
module ParallelIdentity : ParallelFunction

functor_test.ml
----------------

module type Message =
  sig
    type t
    val to_string : t -> string
    val of_string : string -> t
  end

module type PolyMessage = functor (M : Message) ->
  sig
    type 'a t
    val to_string : M.t t -> string
    val of_string : string -> M.t t
  end

module BindMessage =
  functor (P : PolyMessage) ->
  functor (M : Message) ->
  struct
    module P = P (M)
    type t = M.t P.t
    let to_string m = P.to_string m
    let of_string s = P.of_string s
  end

module type Function =
  sig
    module A : Message
    module B : Message
    val f : A.t -> B.t
  end

module type PolyFunction =
  (*
  functor (A : Message) ->
  functor (B : Message) ->
  *)
  sig
    (* val f : A.t -> B.t *)
    val f : 'a -> 'b
  end

module BindFunction =
  functor (F : PolyFunction) ->
  functor (A : Message) ->
  functor (B : Message) ->
  struct
    module A = A
    module B = B
    let f x = F.f x
  end

module type ParallelFunction =
  sig
    module A : Message
    module B : Message
    val sequential : A.t -> B.t
    val concurrent : A.t -> B.t
    val parallel : A.t -> B.t
    val remote : A.t -> B.t
  end

module Parallelize = functor (F : Function) ->
  struct
    module A = F.A
    module B = F.B
    let sequential x = F.f x
    let concurrent x = F.f x
    let parallel x = F.f x
    let remote x = F.f x
  end

module IntMessage =
  struct
    type t = int
    let to_string m = string_of_int m
    let of_string s = int_of_string s
  end

module FloatMessage =
  struct
    type t = float
    let to_string m = string_of_float m
    let of_string s = float_of_string s
  end

module Double =
  struct
    module A = IntMessage
    module B = IntMessage
    let f x = 2 * x
  end

module Identity =
  (*
  functor (A : Message) ->
  functor (B : Message) ->
  *)
  struct
    let f x = (Obj.magic x : 'b)
    
    (* Fails type checking, why?
    let f x = x
    *)
  end

module BoundIdentity = BindFunction (Identity) (IntMessage) (IntMessage)

(* Fails type checking, as it should:
module BoundIdentity = Bind (Identity) (IntMessage) (FloatMessage)
*)

module ParallelDouble = Parallelize (Double)
module ParallelIdentity = Parallelize (BoundIdentity)

Re: [Caml-list] Functors + polymorphism = confusion

[Chris King]

The important thing to remember with Caml modules is that it will hide
type relations unless you tell it otherwise:

On 6/21/07, Jonathan T Bryant <jtbryant@valdosta.edu> wrote:
> module BindFunction :
>   functor (F : PolyFunction) ->
>   functor (A : Message) ->
>   functor (B : Message) ->
>   Function

Recall your definition of Function above:

> module type Function =
>  sig
>    module A : Message
>    module B : Message
>    val f : A.t -> B.t
>  end

Here modules A and B are of type Message, which define an abstract
type t.  Caml doesn't automatically fill in this type definition for
you, so the module returned by BindFunction will only be able to
operate over a pair of abstract types.  Not good!

The solution to this (which you will see used in functorized library
modules such as Map and Set) is to add the derivation of types A.t and
B.t to your output signature using the "with" syntax:

module BindFunction :
 functor (F : PolyFunction) ->
 functor (A : Message) ->
 functor (B : Message) ->
 Function with type A.t = A.t and type B.t = B.t

This tells Caml to modify the Function signature so that, instead of
having abstract types A.t and B.t, it contains those type equations.
So the actual output signature will look like this:

sig
  module A :
    sig
      type t = A.t
      val to_string : t -> string
      val of_string : string -> t
    end
  module B :
    sig
      type t = B.t
      val to_string : t -> string
      val of_string : string -> t
    end
 val f : A.t -> B.t
end


> module Parallelize : functor (F : Function) -> ParallelFunction

You'll need to do the same thing here, tell Caml that the abstract
types within ParallelFunction are really the same as the types in F:

module Parallelize : functor (F : Function) ->
  ParallelFunction with type A.t = F.A.t and type B.t = F.B.t


Note that you can actually do this at the module level, too:

module Parallelize : functor (F : Function) ->
  ParallelFunction with module A = F.A and module B = F.B

In this case it only serves to save a couple keystrokes but it is
useful if either (a) you have lots of types you want to copy en masse
to the output signature or (b) the output signature contains a
restricted form of one of the input modules and you want to retain the
extra types and values.


> module BindMessage =
>   functor (P : PolyMessage) ->
>   functor (M : Message) ->
>   struct
>     module P = P (M)
>     type t = M.t P.t
>     let to_string m = P.to_string m
>     let of_string s = P.of_string s
>   end

Because you are not restricting the output signatures in your
implementation, Caml preserves the type relationships (it only
discards them at the interface level).  However if you did specify the
output signature here (as the library modules do) you would need to
use the same construct.


Hope this helps... I can attest that this stuff is pretty confusing at first. :)

- Chris

Re: [Caml-list] Functors + polymorphism = confusion

[Jonathan Bryant]

On Jun 21, 2007, at 10:08 AM, Chris King wrote:

> The important thing to remember with Caml modules is that it will hide
> type relations unless you tell it otherwise:
>
> Here modules A and B are of type Message, which define an abstract
> type t.  Caml doesn't automatically fill in this type definition for
> you, so the module returned by BindFunction will only be able to
> operate over a pair of abstract types.  Not good!

Ah, I see the error now!

>
> The solution to this (which you will see used in functorized library
> modules such as Map and Set) is to add the derivation of types A.t and
> B.t to your output signature using the "with" syntax:
>
> module BindFunction :
> functor (F : PolyFunction) ->
> functor (A : Message) ->
> functor (B : Message) ->
> Function with type A.t = A.t and type B.t = B.t
>

Works perfectly!  I had always been a little confused as to exactly  
what the "with" syntax was accomplishing, and even with your  
explanation it took a while for me to see how to use it.  Thanks for  
the clarification.

>
>> module BindMessage =
>>   functor (P : PolyMessage) ->
>>   functor (M : Message) ->
>>   struct
>>     module P = P (M)
>>     type t = M.t P.t
>>     let to_string m = P.to_string m
>>     let of_string s = P.of_string s
>>   end
>
> Because you are not restricting the output signatures in your
> implementation, Caml preserves the type relationships (it only
> discards them at the interface level).  However if you did specify the
> output signature here (as the library modules do) you would need to
> use the same construct.
>

I have gone back and used the same "with" syntax on my prebuilt  
messages and it solved another type issue I was having :)

I do specify the output signature (in the .mli file):

module BindMessage :
   functor (P : PolyMessage) ->
   functor (M : Message) ->
   Message

but now it's:

module BindMessage :
   functor (P : PolyMessage) ->
   functor (M : Message) ->
   Message with type t = M.t P(M).t

>
> Hope this helps... I can attest that this stuff is pretty confusing  
> at first. :)

Yes.  I am learning more about the module system than I think I ever  
wanted to know.  My project makes heavy use of (read: abuses) the  
modules system :)

--Jonathan

>
> - Chris
>
> _______________________________________________
> Caml-list mailing list. Subscription management:
> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs