[Caml-list] recursive module type

[Caml-list] recursive module type

[Michaël Lienhardt]

Hello,

I would like to define some recursive module type in caml, like
module type S = sig
  ...
  module Toto(M : S) : sig
   ...
  end
end

More precisely, I'd like to extend the Set module available in the ocaml distribution with a function that convert a set into another set.
Intuitively, I came up with the following signature S, which is not accepted by ocaml (Error: Unbound module type S):

   module type S = sig

     include Set.S

     module Convert : functor(SetTarget : S) -> sig
       val convert : (elt -> SetTarget.elt) -> t -> SetTarget.t
     end
   end

Is there a way to define such a module type in ocaml, and if not, is there a theoretical reason for this not being possible?

Thanks,
Michael Lienhardt

Re: [Caml-list] recursive module type

[Gabriel Scherer]

I did not need such form of self-reference to build converter from a
set to another.

(* binary converter functor *)
module SetConverter (S1 : Set.S) (S2 : Set.S) : sig
  val convert : (S1.elt -> S2.elt) -> (S1.t -> S2.t)
end = struct
  let convert f s1 =
    S1.fold (fun e s2 -> S2.add (f e) s2) s1 S2.empty
end

(* currified version as a Set.S overlay *)
module SetWithConverter (E : Set.OrderedType) : sig
  include Set.S
  module Converter (S2 : Set.S) : sig
    val convert : (elt -> S2.elt) -> (t -> S2.t)
  end
end = struct
  module S1 = Set.Make(E)
  include S1
  module Converter (S2:Set.S) = SetConverter(S1)(S2)
end


On Sat, May 4, 2013 at 2:23 PM, Michaël Lienhardt
<michael.lienhardt@inria.fr> wrote:
> Hello,
>
> I would like to define some recursive module type in caml, like
> module type S = sig
>  ...
>  module Toto(M : S) : sig
>   ...
>  end
> end
>
> More precisely, I'd like to extend the Set module available in the ocaml
> distribution with a function that convert a set into another set.
> Intuitively, I came up with the following signature S, which is not accepted
> by ocaml (Error: Unbound module type S):
>
>   module type S = sig
>
>     include Set.S
>
>     module Convert : functor(SetTarget : S) -> sig
>       val convert : (elt -> SetTarget.elt) -> t -> SetTarget.t
>     end
>   end
>
> Is there a way to define such a module type in ocaml, and if not, is there a
> theoretical reason for this not being possible?
>
> Thanks,
> Michael Lienhardt
>
> --
> 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] recursive module type

[Jacques Garrigue]

On 2013/05/04, at 21:23, Michaël Lienhardt <michael.lienhardt@inria.fr> wrote:

> Hello,
> 
> I would like to define some recursive module type in caml, like
> module type S = sig
> ...
> module Toto(M : S) : sig
>  ...
> end
> end
> 
> More precisely, I'd like to extend the Set module available in the ocaml distribution with a function that convert a set into another set.
> Intuitively, I came up with the following signature S, which is not accepted by ocaml (Error: Unbound module type S):
> 
>  module type S = sig
> 
>    include Set.S
> 
>    module Convert : functor(SetTarget : S) -> sig
>      val convert : (elt -> SetTarget.elt) -> t -> SetTarget.t
>    end
>  end

You first problem is syntactic.
You cannot define recursive signatures, just recursive modules.
But the signature may refer recursively to the module.
So you can attempt to write the following:

module rec M : sig
  module type S = sig  
     include Set.S
     module Convert : functor(SetTarget :M.S) -> sig          
       val convert : (elt -> SetTarget.elt) -> t -> SetTarget.t
     end
   end
end = M;;

unfortunately, this does not work:
Fatal error: exception Env.Recmodule

And this is not surprising, because this would let you indeed define
a recursive signature (i.e. a signature that unfolds infinitely).

Jacques Garrigue

Re: [Caml-list] recursive module type

[Michaël Lienhardt]

Thanks

I also thought about the SetConverter solution.
This is what I will use.

I was asking if such a recursive definition was possible because I have a tendency to compare the ocaml module system with Java-like objects.
 From that point of view, signatures are like tree-structured Java interfaces that can declare types, values and functions in addition to methods (functors).
While typing in object-oriented languages is recursive by default, I understand that it is not the case in ocaml because of type inference:
  annotating modules with their signatures then enable recursive modules.
Then, because signatures are types, and also have some similarities with Java interfaces, I imagined that some kind of recursion is possible.

Michael Lienhardt


Le 04/05/2013 14:47, Jacques Garrigue a écrit :
>
> On 2013/05/04, at 21:23, Michaël Lienhardt <michael.lienhardt@inria.fr> wrote:
>
>> Hello,
>>
>> I would like to define some recursive module type in caml, like
>> module type S = sig
>> ...
>> module Toto(M : S) : sig
>>   ...
>> end
>> end
>>
>> More precisely, I'd like to extend the Set module available in the ocaml distribution with a function that convert a set into another set.
>> Intuitively, I came up with the following signature S, which is not accepted by ocaml (Error: Unbound module type S):
>>
>>   module type S = sig
>>
>>     include Set.S
>>
>>     module Convert : functor(SetTarget : S) -> sig
>>       val convert : (elt -> SetTarget.elt) -> t -> SetTarget.t
>>     end
>>   end
>
> You first problem is syntactic.
> You cannot define recursive signatures, just recursive modules.
> But the signature may refer recursively to the module.
> So you can attempt to write the following:
>
> module rec M : sig
>    module type S = sig
>       include Set.S
>       module Convert : functor(SetTarget :M.S) -> sig
>         val convert : (elt -> SetTarget.elt) -> t -> SetTarget.t
>       end
>     end
> end = M;;
>
> unfortunately, this does not work:
> Fatal error: exception Env.Recmodule
>
> And this is not surprising, because this would let you indeed define
> a recursive signature (i.e. a signature that unfolds infinitely).
>
> Jacques Garrigue
>

Re: [Caml-list] recursive module type

[Alain Frisch]

On 05/04/2013 02:47 PM, Jacques Garrigue wrote:
> unfortunately, this does not work:
> Fatal error: exception Env.Recmodule

This exception was recently introduced to fix #5965.  Of course, it 
should never be reported like that to the user.  This is now fixed in 
the trunk, and you the following error message:

File "foo.ml", line 4, characters 41-44:
Error: Illegal recursive module reference


-- Alain