How to deal with "recursive" modules?

Learning
1

I have two OCaml modules that are automatically generated with that kind of signatures :

module A : sig
  type t
  val a_fn: t -> B.t  
end

module B : sig
  type t
  val another_fn: t -> A.t
end

How would deal with this kind of problem ?

  • should I merge the two modules ?
  • is the form " module rec ... and ... " (recursive modules) a solution to this? if yes how it works ?
2 Likes
2

I wrote up this little example of recursive modules:

    module rec A : sig
        type t
        val a_fn : t -> B.t
        val of_float : float -> t
    end = struct
        type t = int
        let a_fn x = B.of_int x
        let of_float x = int_of_float x
    end

    and B : sig
        type t val
        another_fn : t -> A.t
        val of_int : int -> t
    end = struct
        type t = float
        let another_fn x = A.of_float x
        let of_int x = float_of_int x
    end

It works, though I’m not sure it does what you’re looking for:

# A.a_fn (A.of_float 14.0);;
- : B.t = <abstr>
# B.another_fn (B.of_int 122);;
- : A.t = <abstr>
3 Likes
3

Hi,

What you need is something like this:

  1. Describe your interfaces, since recursive modules require an explicit signature. Doing this before hand makes your code esier to read.
  2. Create an extra type in each signature to reference the type in the other module you want to access.
  3. Declare your recursive modules replacing the reference to the foreign type with the real one. (If you use :=, you don’t have to mention this reference type in your implementations).
  4. Optionally, you can explicitly describe the main type used in each of these modules, so you have concrete types known to the caller.

Here’s the signatures:

module S = struct
  module type A = sig
    type t
    type aux

    val a_fn: t -> aux
  end

  module type B = sig
    type t
    type aux

    val another_fn: t -> aux
  end
end

And the implementations with ints and strings for the types:

module rec A : S.A
  with type t = int
  and type aux := B.t =
struct
  type t = int
  let a_fn v = string_of_int v
end

and B : S.B
  with type t = string
  and type aux := A.t =
struct
  type t = string
  let another_fn v = int_of_string v
end
3 Likes
4

@jeffsco,

That is in fact what I would like to use but if I take the raw code I have and tweak it manually in order to use the rec module .. and form, I have the following:

module rec Bytes : sig
  type t
  val t_typ : t structure typ
  (*Not implemented g_bytes_new argument types not handled*)
  (*Not implemented g_bytes_new_take argument types not handled*)
  val compare:
  t structure ptr -> t structure ptr -> int32

  val equal:
  t structure ptr -> t structure ptr -> bool

  (*Not implemented g_bytes_get_data argument types not handled*)
  val get_size:
  t structure ptr -> Unsigned.uint64

  val hash:
  t structure ptr -> Unsigned.uint32

  val new_from_bytes:
  t structure ptr -> Unsigned.uint64 -> Unsigned.uint64 -> t structure ptr

  val _ref:
  t structure ptr -> t structure ptr

  val unref:
  t structure ptr -> unit

  val unref_to_array:
  t structure ptr -> Byte_array.t structure ptr

  (*Not implemented g_bytes_unref_to_data argument types not handled*)
end = struct
  type t
  let t_typ : t structure typ = structure "Bytes"
  (*Not implemented g_bytes_new argument types not handled*)
  (*Not implemented g_bytes_new_take argument types not handled*)
  let compare =
  foreign "g_bytes_compare" (ptr t_typ @-> ptr t_typ @-> returning (int32_t))

  let equal =
  foreign "g_bytes_equal" (ptr t_typ @-> ptr t_typ @-> returning (bool))

  (*Not implemented g_bytes_get_data argument types not handled*)
  let get_size =
  foreign "g_bytes_get_size" (ptr t_typ @-> returning (uint64_t))

  let hash =
  foreign "g_bytes_hash" (ptr t_typ @-> returning (uint32_t))

  let new_from_bytes =
  foreign "g_bytes_new_from_bytes" (ptr t_typ @-> uint64_t @-> uint64_t @-> returning (ptr t_typ))

  let _ref =
  foreign "g_bytes_ref" (ptr t_typ @-> returning (ptr t_typ))

  let unref =
  foreign "g_bytes_unref" (ptr t_typ @-> returning (void))

  let unref_to_array =
  foreign "g_bytes_unref_to_array" (ptr t_typ @-> returning (ptr Byte_array.t_typ))

  (*Not implemented g_bytes_unref_to_data argument types not handled*)
end

and Byte_array : sig
  type t
  val t_typ : t structure typ
  val f_data: (Unsigned.uint8 ptr, t structure) field
  val f_len: (Unsigned.uint32, t structure) field
  val free:
  t structure ptr -> t structure ptr -> bool -> Unsigned.uint8 ptr

  val free_to_bytes:
  t structure ptr -> t structure ptr -> Bytes.t structure ptr

  val _new:
  t structure ptr -> t structure ptr

  (*Not implemented g_byte_array_new_take argument types not handled*)
  val unref:
  t structure ptr -> t structure ptr -> unit
end = struct
  type t
  let t_typ : t structure typ = structure "Byte_array"
  let f_data = field t_typ "data" (ptr uint8_t)
  let f_len = field t_typ "len" (uint32_t)
  let free =
  foreign "g_byte_array_free" (ptr t_typ @-> ptr t_typ @-> bool @-> returning (ptr uint8_t))

  let free_to_bytes =
  foreign "g_byte_array_free_to_bytes" (ptr t_typ @-> ptr t_typ @-> returning (ptr Bytes.t_typ))

  let _new =
  foreign "g_byte_array_new" (ptr t_typ @-> returning (ptr t_typ))

  (*Not implemented g_byte_array_new_take argument types not handled*)
  let unref =
  foreign "g_byte_array_unref" (ptr t_typ @-> ptr t_typ @-> returning (void))
end

But when I compile it I have the following error:

line 35, characters 6-1063:
Error: Cannot safely evaluate the definition
       of the recursively-defined module Byte

It seems that one of my problem is that my modules are Ctypes C structure bindings. I have to find out how to try both your solution and the one provided by @gersonmoraes.

1 Like
5

Just in case if someone will stumble with the same (or equivalent) problem or if the topic starter is still seeking the solution - this could be solved by converting the t_typ value in both modules to a function (of type unit -> t structure typ (alternatively, you can hide it, provide it in some other module, that is not recursive with those two, or provide it only in one module).

The underlying reason is that the compiler needs to ensure, that no elements of the recursive definition are used before initialized. Functions and lazy values are always initialized with default values (that raise exception), thus they are considered safe. All other values may not be used safely. The compiler performs a check that relies only on module types (it doesn’t look into the definition, thus the check is pessimistic - it disallows programs that do not really access unsafe components of other modules but may, as per the type). A module that defines only functions and lazy values is considered a safe module. The check marks the recursive definition as safe if all modules involved in the definition are safe, or if some are unsafe, but they could be initialized before those modules that depend on them.

So in your case, the only value that is unsafe is the t_typ definition. That is neither used recursively nor is dependent on anything besides the type. The easy solution is just to make it a function, and call it later, to instantiate the C type. You can also factor this type into a separate module.

3 Likes
6

For learning, if I understand properly, the module Bytes_array has three unsafe values (t_typ, f_value and f_len), so removing only t_typ from this module wouldn’t be enough, but removing it from Bytes would work as there would then be only one unsafe module?

7

Note that this error message has been improved in 4.07:

Error: Cannot safely evaluate the definition of the following cycle
of recursively-defined modules: Bytes → Byte_array → Bytes.
There are no safe modules in this cycle (see manual section 8.4)

and the manual itself has been expanded to include an example in http://caml.inria.fr/pub/docs/manual-ocaml-4.07/extn.html#sec236 .

8

Yes, you’re right f_value and f_len are also unsafe, I missed them, that’s why I’m preferring to rely on a type checker :))

And yes, if all unsafe definitions are consolidated in one of the two modules (e.g., in Bytes), then the definition will be accepted as safe, since at least one of two modules is safe (and neither Byte_array nor Bytes are, apparently, self-recursive - though the type checker will say if they are), so there is an initialization order that is safe.

@octachron, I wish the error message will also refer the actual sources of unsafeness.

9

Do you mean to point to an example of unsafe value in each modules in the cycle? Something like

Error: Cannot safely evaluate the definition of the following cycle
of recursively-defined modules: Bytes → Byte_array → Bytes.
Line _, characters , :
Line _, characters , :
Those values are unsafe

?

10

yep, something like this

Error: Cannot safely evaluate the definition of the following cycle
of recursively-defined modules: Bytes -> Byte_array -> Bytes.
Note: module Bytes defines a value `f_typ` that is unsafe, defined _here_
Note: module Byte_arra defines a value `f_typ` that is unsafe, defined _here_
Note: A value is safe if it is a function or a lazy value. A recursively defined module may contain unsafe values only if it doesn't have a mutual dependency on another module with unsafe values  (see manual section 8.4)
1 Like
11

It sounds like a nice idea, I would try to have a look during the 4.08 cycle.

2 Likes