[Caml-list] Undefined_recursive_module

[Caml-list] Undefined_recursive_module

[Hawkins, Thomas]

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)

Thanks,

Tom






module rec Process :
  sig
    type t
    val create    : unit -> t
    val add_file  : File.t -> t -> unit 
    val print     : t -> unit
  end
  =
  struct
    type t = { mutable files : FileSet.t }
    
    let create () =
      { files = FileSet.empty }

    let add_file file process =
      process.files <- FileSet.add file process.files

    let print process =
      FileSet.iter File.print process.files
  end

and File :
  sig
    type t
    val compare   : t -> t -> int
    val create    : Process.t -> string -> t
    val print     : t -> unit
  end
  =
  struct
    type t = Process.t * string

    let compare a b =
      match a, b with (_, a), (_, b) -> String.compare a b

    let create process name =
      process, name

    let print (_, name) =
      print_string name;
      print_newline ()
  end

and FileSet :
  Set.S with type elt = File.t
  =
  Set.Make(File)
;;



let does_work () =
  let p = Process.create () in
  Process.add_file (File.create p "file1") p;
  Process.print p
;;


let does_not_work () =
  let p = Process.create () in
  Process.add_file (File.create p "file1") p;
  Process.add_file (File.create p "file2") p;
  Process.print p
;;


(*
does_work ();;
*)
does_not_work ();;

-------------------
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

Re: [Caml-list] Undefined_recursive_module

[Alain Frisch]

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

Re: [Caml-list] Undefined recursive module

[Yotam Barnoy]

[-- Attachment #1: Type: text/plain, Size: 3294 bytes --]

Thank you for the detailed explanation. That makes sense, as much as I wish
there was a static detection mechanism in place for this kind of thing.

On Wed, Sep 10, 2014 at 6:50 PM, Jeremy Yallop <yallop@gmail.com> wrote:

> On 10 September 2014 23:26, Yotam Barnoy <yotambarnoy@gmail.com> wrote:
> > On Wed, Sep 10, 2014 at 6:20 PM, Jeremy Yallop <yallop@gmail.com> wrote:
> >>
> >> On 10 September 2014 21:32, Yotam Barnoy <yotambarnoy@gmail.com> wrote:
> >> > I just encountered this nasty RUNTIME error in my code. What does it
> >> > mean?
> >> > How does it happen?
> >>
> >> The behaviour is documented in the manual:
> >>
> >>    http://caml.inria.fr/pub/docs/manual-ocaml-400/manual021.html#toc75
> >>
> >> See the paragraph beginning "Currently, the compiler requires [...]".
> >
> > Thanks. Does it make sense that changing a function definition from
> > point-free to an explicit definition should eliminate this exception?
>
> Yes, that's the expected behaviour.  Initially the fields in a
> recursive module are bound to functions that raise an exception.  The
> module initialization then overwrites each field with its actual
> value, which is determined by evaluating the expression on the right
> hand side of the field definition.  If evaluating the right hand side
> involves reading one of the fields of the module that has not yet been
> overwritten then the field will resolve to the exception-raising
> function, which may lead to the runtime error that you've seen.
>
> Here's an example.  Suppose you have a recursive module like this:
>
>   module rec M1
>     : sig val x : unit -> unit end =
>   struct
>       let x = M1.x
>   end
>
> Then the initial state of the module at runtime has x bound to a
> function that raises an exception:
>
>    module rec M1
>      : sig val x : unit -> unit end =
>    struct
>        let x = fun _ -> raise Undefined_recursive_module
>    end
>
> Module initialization then overwrites the field with the result of
> evaluating the right-hand side -- that is, by the result of evaluating
> M1.x:
>
>    M1.x <- (fun _ -> raise Undefined_recursive_module)
>
> Calling M1.x will lead to the exception being raised:
>
>    M1.x ()
>      => raise Undefined_recursive_module
>
> Now consider what happens when you eta-expand the definition of x.
> Here's the source program
>
>    module rec M2 : sig val x : unit -> unit end =
>    struct
>        let x = fun e -> M2.x e
>    end
>
> The initial state of the module at runtime is the same as for M1:
>
>    module rec M2 : sig val x : unit -> unit end =
>    struct
>        let x = fun _ -> raise Undefined_recursive_module end
>    end
>
> Once again, module initialization overwrites the field with the result
> of evaluating the right-hand side.  This time, however, evaluating the
> right-hand side doesn't require resolving M2.x, since M2.x is under a
> 'fun' binding:
>
>    M2.x <- (fun e -> M2.x e)
>
> When you come to call M2.x the recursive reference resolves to the new
> value of the field and evaluation proceeds as expected:
>
>    M2.x ()
>      => M2.x ()
>
> As the manual says, all of this is subject to change, and it's best
> not to rely on the current behaviour.  I recommend that you avoid
> using recursive modules for value-level recursion, if possible.
>

[-- Attachment #2: Type: text/html, Size: 4371 bytes --]

Re: [Caml-list] Undefined recursive module

[Jeremy Yallop]

On 10 September 2014 23:26, Yotam Barnoy <yotambarnoy@gmail.com> wrote:
> On Wed, Sep 10, 2014 at 6:20 PM, Jeremy Yallop <yallop@gmail.com> wrote:
>>
>> On 10 September 2014 21:32, Yotam Barnoy <yotambarnoy@gmail.com> wrote:
>> > I just encountered this nasty RUNTIME error in my code. What does it
>> > mean?
>> > How does it happen?
>>
>> The behaviour is documented in the manual:
>>
>>    http://caml.inria.fr/pub/docs/manual-ocaml-400/manual021.html#toc75
>>
>> See the paragraph beginning "Currently, the compiler requires [...]".
>
> Thanks. Does it make sense that changing a function definition from
> point-free to an explicit definition should eliminate this exception?

Yes, that's the expected behaviour.  Initially the fields in a
recursive module are bound to functions that raise an exception.  The
module initialization then overwrites each field with its actual
value, which is determined by evaluating the expression on the right
hand side of the field definition.  If evaluating the right hand side
involves reading one of the fields of the module that has not yet been
overwritten then the field will resolve to the exception-raising
function, which may lead to the runtime error that you've seen.

Here's an example.  Suppose you have a recursive module like this:

  module rec M1
    : sig val x : unit -> unit end =
  struct
      let x = M1.x
  end

Then the initial state of the module at runtime has x bound to a
function that raises an exception:

   module rec M1
     : sig val x : unit -> unit end =
   struct
       let x = fun _ -> raise Undefined_recursive_module
   end

Module initialization then overwrites the field with the result of
evaluating the right-hand side -- that is, by the result of evaluating
M1.x:

   M1.x <- (fun _ -> raise Undefined_recursive_module)

Calling M1.x will lead to the exception being raised:

   M1.x ()
     => raise Undefined_recursive_module

Now consider what happens when you eta-expand the definition of x.
Here's the source program

   module rec M2 : sig val x : unit -> unit end =
   struct
       let x = fun e -> M2.x e
   end

The initial state of the module at runtime is the same as for M1:

   module rec M2 : sig val x : unit -> unit end =
   struct
       let x = fun _ -> raise Undefined_recursive_module end
   end

Once again, module initialization overwrites the field with the result
of evaluating the right-hand side.  This time, however, evaluating the
right-hand side doesn't require resolving M2.x, since M2.x is under a
'fun' binding:

   M2.x <- (fun e -> M2.x e)

When you come to call M2.x the recursive reference resolves to the new
value of the field and evaluation proceeds as expected:

   M2.x ()
     => M2.x ()

As the manual says, all of this is subject to change, and it's best
not to rely on the current behaviour.  I recommend that you avoid
using recursive modules for value-level recursion, if possible.

Re: [Caml-list] Undefined recursive module

[Yotam Barnoy]

[-- Attachment #1: Type: text/plain, Size: 635 bytes --]

Thanks. Does it make sense that changing a function definition from
point-free to an explicit definition should eliminate this exception?
Because that seems to have been the problem.

On Wed, Sep 10, 2014 at 6:20 PM, Jeremy Yallop <yallop@gmail.com> wrote:

> On 10 September 2014 21:32, Yotam Barnoy <yotambarnoy@gmail.com> wrote:
> > I just encountered this nasty RUNTIME error in my code. What does it
> mean?
> > How does it happen?
>
> The behaviour is documented in the manual:
>
>    http://caml.inria.fr/pub/docs/manual-ocaml-400/manual021.html#toc75
>
> See the paragraph beginning "Currently, the compiler requires [...]".
>

[-- Attachment #2: Type: text/html, Size: 1139 bytes --]

Re: [Caml-list] Undefined recursive module

[Jeremy Yallop]

On 10 September 2014 21:32, Yotam Barnoy <yotambarnoy@gmail.com> wrote:
> I just encountered this nasty RUNTIME error in my code. What does it mean?
> How does it happen?

The behaviour is documented in the manual:

   http://caml.inria.fr/pub/docs/manual-ocaml-400/manual021.html#toc75

See the paragraph beginning "Currently, the compiler requires [...]".

[Caml-list] Undefined recursive module

[Yotam Barnoy]

[-- Attachment #1: Type: text/plain, Size: 102 bytes --]

I just encountered this nasty RUNTIME error in my code. What does it mean?
How does it happen?

Yotam

[-- Attachment #2: Type: text/html, Size: 147 bytes --]