# How to deal with "recursive" modules?

**URL:** <https://discuss.ocaml.org/t/how-to-deal-with-recursive-modules/898>\
**Category:** Learning\
**Tags:** module\
**Created:** [September 29, 2017, 5:22pm UTC](https://discuss.ocaml.org/t/how-to-deal-with-recursive-modules/898 "2017-09-29T17:22:06Z")\
**Posts on this page:** 11\
**Page:** 1

<div class="post-metadata">

**Author:** ![cedlemo](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/cedlemo/32/1213_2.png) [@cedlemo](https://discuss.ocaml.org/u/cedlemo)\
**Post date:** [September 29, 2017, 5:22pm UTC](https://discuss.ocaml.org/t/how-to-deal-with-recursive-modules/898/1 "2017-09-29T17:22:06Z")

</div>

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

```auto
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](http://caml.inria.fr/pub/docs/manual-ocaml/extn.html#sec219)) a solution to this? if yes how it works ?

---

<div class="post-metadata">

**Author:** ![jeffsco](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/jeffsco/32/45_2.png) [@jeffsco](https://discuss.ocaml.org/u/jeffsco)\
**Post date:** [September 29, 2017, 5:56pm UTC](https://discuss.ocaml.org/t/how-to-deal-with-recursive-modules/898/2 "2017-09-29T17:56:16Z")

</div>

I wrote up this little example of recursive modules:

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

---

<div class="post-metadata">

**Author:** ![gersonmoraes](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/gersonmoraes/32/485_2.png) [@gersonmoraes](https://discuss.ocaml.org/u/gersonmoraes)\
**Post date:** [September 29, 2017, 6:20pm UTC](https://discuss.ocaml.org/t/how-to-deal-with-recursive-modules/898/3 "2017-09-29T18:20:43Z")

</div>

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:

```ocaml
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:

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

```

---

<div class="post-metadata">

**Author:** ![cedlemo](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/cedlemo/32/1213_2.png) [@cedlemo](https://discuss.ocaml.org/u/cedlemo)\
**Post date:** [September 29, 2017, 6:49pm UTC](https://discuss.ocaml.org/t/how-to-deal-with-recursive-modules/898/4 "2017-09-29T18:49:08Z")

</div>

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

```auto
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:

```auto
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.

---

<div class="post-metadata">

**Author:** ![ivg](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/ivg/32/103_2.png) [@ivg](https://discuss.ocaml.org/u/ivg)\
**Post date:** [June 21, 2018, 4:41pm UTC](https://discuss.ocaml.org/t/how-to-deal-with-recursive-modules/898/5 "2018-06-21T16:41:22Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![christophe-riolo](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/christophe-riolo/32/1053_2.png) [@christophe-riolo](https://discuss.ocaml.org/u/christophe-riolo)\
**Post date:** [June 21, 2018, 5:02pm UTC](https://discuss.ocaml.org/t/how-to-deal-with-recursive-modules/898/6 "2018-06-21T17:02:33Z")

</div>

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?

---

<div class="post-metadata">

**Author:** ![octachron](https://avatars.discourse-cdn.com/v4/letter/o/49beb7/32.png) [@octachron](https://discuss.ocaml.org/u/octachron)\
**Post date:** [June 21, 2018, 5:13pm UTC](https://discuss.ocaml.org/t/how-to-deal-with-recursive-modules/898/7 "2018-06-21T17:13:44Z")

</div>

> [@cedlemo](#):
>
> line 35, characters 6-1063: Error: Cannot safely evaluate the definition of the recursively-defined module Byte

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](http://caml.inria.fr/pub/docs/manual-ocaml-4.07/extn.html#sec236) .

---

<div class="post-metadata">

**Author:** ![ivg](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/ivg/32/103_2.png) [@ivg](https://discuss.ocaml.org/u/ivg)\
**Post date:** [June 21, 2018, 5:16pm UTC](https://discuss.ocaml.org/t/how-to-deal-with-recursive-modules/898/8 "2018-06-21T17:16:51Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![octachron](https://avatars.discourse-cdn.com/v4/letter/o/49beb7/32.png) [@octachron](https://discuss.ocaml.org/u/octachron)\
**Post date:** [June 21, 2018, 5:21pm UTC](https://discuss.ocaml.org/t/how-to-deal-with-recursive-modules/898/9 "2018-06-21T17:21:59Z")

</div>

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

?

---

<div class="post-metadata">

**Author:** ![ivg](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/ivg/32/103_2.png) [@ivg](https://discuss.ocaml.org/u/ivg)\
**Post date:** [June 21, 2018, 5:31pm UTC](https://discuss.ocaml.org/t/how-to-deal-with-recursive-modules/898/10 "2018-06-21T17:31:18Z")

</div>

yep, something like this

```auto
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)
```

---

<div class="post-metadata">

**Author:** ![octachron](https://avatars.discourse-cdn.com/v4/letter/o/49beb7/32.png) [@octachron](https://discuss.ocaml.org/u/octachron)\
**Post date:** [June 21, 2018, 10:18pm UTC](https://discuss.ocaml.org/t/how-to-deal-with-recursive-modules/898/11 "2018-06-21T22:18:19Z")

</div>

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