recursive modules: Cannot safely evaluate the definition

recursive modules: Cannot safely evaluate the definition

[Hendrik Tews]

Hi,

for the following program

    module type Result_sig = sig
      val result : int
    end

    module type Build_sig = sig
      val compute : int -> unit
    end

    module rec Rec : functor(Arg : Result_sig) -> Build_sig = 
      functor(Arg : Result_sig) ->
    struct
      let compute = function
	| 0 -> Printf.printf "result: %d\n" Arg.result
	| n ->
	    let module Arg_x_2 = struct
	      let result = Arg.result * 2
	    end
	    in
	    let module Rec_tail = Rec(Arg_x_2)
	    in
	      Rec_tail.compute (n-1)
    end


I get the compiler error 

  Cannot safely evaluate the definition of the recursively-defined module Rec

Could somebody explain to me why? As far as I can see, module Rec
is safe in the sense of section 7.9 of the reference manual. 

[Background: I am trying to solve the following Ocaml puzzle:
Build a (nested) functor application, where the functors applied
depend on an input value of the program. In particular the depth
of the functor application depends on the input value and could
be arbitrary high.]


Bye,

Hendrik

Re: [Caml-list] recursive modules: Cannot safely evaluate the definition

[Keiko Nakata]

Hello.

I think that functors cannot be recursive in the current OCaml.

You may want to look at the paper found at:

caml.inria.fr/pub/papers/xleroy-recursive_modules-03.pdf

In particular, the footnote in page 6.

With best regards,
Keiko

Re: [Caml-list] recursive modules: Cannot safely evaluate the definition

[Jean-Christophe Filliâtre]

Keiko Nakata wrote:
> Hello.
> 
> I think that functors cannot be recursive in the current OCaml.

They can:

-----------------------------------------------------------------
module type S = sig type t = int end

module rec F : functor(X : S) -> S = functor(X: S) -> struct
  type t = M.t
end
and M : S = F(struct type t = int end)

let x : M.t = 42
-----------------------------------------------------------------

But it is likely that you won't do anything useful with a functor like
this (try adding a "val x : t" in the signature and to define x in F as
equal to M.x and you'll bump on the "Cannot safely evaluate the
definition of ..." error).

-- 
Jean-Christophe

Re: [Caml-list] recursive modules: Cannot safely evaluate the definition

[Hendrik Tews]

Jean-Christophe Filliâtre <Jean-Christophe.Filliatre@lri.fr>
writes:

   Keiko Nakata wrote:
   > Hello.
   > 
   > I think that functors cannot be recursive in the current OCaml.

   They can:

   [example deleted]


For those who are interested but were too lazy to read the paper
that Keiko pointed to: In a set of recursive modules every
dependency cycle has to go through a safe module, whose signature
consists only of functions, lazy values and exceptions and
submodules with the same requirement.

Initialization first initializes all safe modules by providing
function bodies that throw execptions. Then initialize the
remaining modules in the order of their dependency. In the end
the functions in the safe modules are replace in place with the
right closures. For this replacement trick to work you need to
know the size of the safe modules. Functors are closures whose
size cannot determined from their signature, thus functors are
never safe.

This does not exclude functors in recursive modules. It only
means that apart from the functors you need at least one safe
module. See 7.9 in the reference manual for a very sensible
example with a functor.

If there are dependency cycles without a safe module, you
apparently get the "Cannot safely evaluate ..." error. 

If you have dependency cycles with two or more safe modules than
the compiler might choose an initialization order that does not
work. Then it might help to make some of the safe modules unsafe. 

Bye,

Hendrik

Re: [Caml-list] recursive modules: Cannot safely evaluate the definition

[Keiko Nakata]

Thank you for the correction and citation.

>    Keiko Nakata wrote:
>    > I think that functors cannot be recursive in the current OCaml.

Yes, I was incorrect.
We have: 

module rec F: functor (X:sig end) -> sig val f : int -> int end = 
  functor(X:sig end) -> struct  
    let f x = if x = 0 then 0 else M.f (x-1)
  end

and M : sig val f: int -> int end = F(M)

This should imply interesting examples are available. 

Best,
Keiko

Re: [Caml-list] recursive modules: Cannot safely evaluate the definition

[Sebastien Ferre]

Hi,

Keiko Nakata wrote:
> Thank you for the correction and citation.
> 
>>    Keiko Nakata wrote:
>>    > I think that functors cannot be recursive in the current OCaml.
> 
> Yes, I was incorrect.
> We have: 
> 
> module rec F: functor (X:sig end) -> sig val f : int -> int end = 
>   functor(X:sig end) -> struct  
>     let f x = if x = 0 then 0 else M.f (x-1)
>   end
> 
> and M : sig val f: int -> int end = F(M)
> 
> This should imply interesting examples are available. 

For such examples, you can look at my library LogFun, which
massively uses functors and recursive modules.

http://www.irisa.fr/LIS/ferre/logfun/

It defines a set of components, in the form of OCaml functors,
which can be composed in a recursive way. The most illustrative
component is the file 'mltype.ml' that defines a language of ML
types and patterns by a recursive combination of simpler components.
It is used in Camelis (http://www.irisa.fr/LIS/ferre/camelis/)
for browsing ML functions from a set of .mli files. It is not very
well documented, but if you are interested, you can contact me.

Best,
Sebastien