Re: [Caml-list] Undefined_recursive_module

[Alain Frisch <Alain.Frisch@ens.fr>]

On Mon, 26 Jul 2004, Hawkins, Thomas wrote:

> I just started experimenting with recursive modules, but have hit a snag
> with Undefined_recursive_module.
>
> Basically I need to define an ADT where the data structure contains Sets
> and the Set elements reference back to the data structure.  In the
> following example, the mutually recursive modules include the main data
> structure (Process), an ordered type (Files), and a set (FileSet
> returned from the Set functor). Both the Process and the File modules
> define only function values, therefore I believe the example satisfies
> the "safe module" requirement.  It does compile and run for one case
> (see does_work).  However, if I make multiple calls to Process.add_file,
> Undefined_recursive_module is raised (see does_not_work).
>
> Any suggestions?  (I'm using 3.08.0)

I guess the problem is that when you apply the functor Set.Make, OCaml has
to perform a coercion on the argument (File) to create a structure of the
expected type (OrderedSet). This coercion copies the fields from the yet
uninitialized File structure (dummy slots). The fields in File are
eventually filled up to close the recursion loop, but the copy, used by
Set.Make implementation, is left untouched, hence the problem.

This very example would probably have worked correctly with OCaml 3.07,
because an optimization was then used to avoid the coercion when it was
only a prefix-extraction of the structure (it was then replaced by the
identity), but it seems this optimization is unsound with recursive
modules. Now, it's very difficult to avoid coercions (a simple reordering
of the fields requires a coercion), and so the technique of using
recursive modules to define a type t and the type of t sets is rather
fragile.

(The reason why a single call does not produce the error is that you
don't need to call File.compare for the first call to FileSet.add.)


I faced the same problem. The solution I choosed was to eta-expand
the argument of the functor (yet another instance of the "We can solve any
problem by introducing an extra level of indirection" theorem):

In your example, you can replace Set.Make(File) by:

  Set.Make(struct type t = File.t let compare x = File.compare x end)


Hope this helps,


 Alain

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners