exceptions in recursive modules

exceptions in recursive modules

[Aaron Bohannon]

I was trying to use a recursive module but was getting unexpected 
"Undefined_recursive_modules" exceptions.  After a long debugging 
session, I discovered the source of my problem to be exception 
declarations in the module.  I don't intuitively understand why they 
cause a problem, and as I cannot find documentation of the behavior, I 
am wondering if it might be a bug.

Here is the example.  This is essentially the example in the manual, but 
I have added an exception to the module:

module rec A : sig
   type t = Leaf of int | Node of ASet.t
   exception Fail
   val compare : t -> t -> int
end = struct
   type t = Leaf of int | Node of ASet.t
   exception Fail
   let rec compare = (* suitable definition *)
end
and ASet : Set.S with type elt = A.t = Set.Make(A)

Then we can try to use it:

# let x = A.Leaf(3);;
val x : A.t = A.Leaf 3
# let s = ASet.add x ASet.empty;;
val s : ASet.t = <abstr>
# let s' = ASet.add x s;;
Exception: Undefined_recursive_module ("recmodtest.ml", 6, 6).

If we remove the "exception Fail" from the signature, everything works 
just fine.  Is this behavior correct?  (I am using OCaml 3.08.1)

Aaron

--
Aaron Bohannon
http://www.cis.upenn.edu/~bohannon/

[Caml-list] exceptions in recursive modules

[Tom Hirschowitz]

 > Here is the example.  This is essentially the example in the manual, but 
 > I have added an exception to the module:
 > 
 > module rec A : sig
 >    type t = Leaf of int | Node of ASet.t
 >    exception Fail
 >    val compare : t -> t -> int
 > end = struct
 >    type t = Leaf of int | Node of ASet.t
 >    exception Fail
 >    let rec compare = (* suitable definition *)
 > end
 > and ASet : Set.S with type elt = A.t = Set.Make(A)
 > 
 > Then we can try to use it:
 > 
 > # let x = A.Leaf(3);;
 > val x : A.t = A.Leaf 3
 > # let s = ASet.add x ASet.empty;;
 > val s : ASet.t = <abstr>
 > # let s' = ASet.add x s;;
 > Exception: Undefined_recursive_module ("recmodtest.ml", 6, 6).
 > 
 > If we remove the "exception Fail" from the signature, everything works 
 > just fine.  Is this behavior correct?  (I am using OCaml 3.08.1)

I think this is due to the necessary coercion between your A and the
OrderedType argument expected by Set.Make. Your code is compiled to
something like

module rec A : sig
   type t = Leaf of int | Node of ASet.t
   exception Fail
   val compare : t -> t -> int
end = struct
   type t = Leaf of int | Node of ASet.t
   exception Fail
   let rec compare = (* suitable definition *)
end
and ASet : Set.S with type elt = A.t = Set.Make(
  struct
    type t = A.t
    let compare = A.compare
  end)

According to the (brief) explanation in the manual, 

"Evaluation of a recursive module definition proceeds by building
initial values for the safe modules involved, binding all (functional)
values to fun x -> raise Undefined_recursive_module. The defining
module expressions are then evaluated, and the initial values for the
safe modules are replaced by the values thus computed."

Here, the argument passed to Set.Make is never replaced with a proper
value. If you explicit the coercion with some A' as below, the code
works. Is it all well this way, or did I miss something?

module rec A : sig
  type t = Leaf of int | Node of ASet.t
  exception Fail
  val compare: t -> t -> int
end
    = struct
      type t = Leaf of int | Node of ASet.t
      exception Fail
      let compare t1 t2 =
        match (t1, t2) with
          (Leaf s1, Leaf s2) -> Pervasives.compare s1 s2
        | (Leaf _, Node _) -> 1
        | (Node _, Leaf _) -> -1
        | (Node n1, Node n2) -> ASet.compare n1 n2
    end
and A' : Set.OrderedType with type t = A.t = struct 
    type t = A.t
    let compare = A.compare
  end   
and ASet : Set.S with type elt = A'.t
      = Set.Make(A')

let x = A.Leaf(3)
let s = ASet.add x ASet.empty
let s' = ASet.add x s