Modularizing a recursive module

Learning
1

I have the following code that works:

module rec Types : sig
  type nat = int
  type var = string
  type env = Unspec(Types).value list
end = Types

Where Unspec is something like this:

module type TYPES = sig
  type env
  type nat
  type var
end

module Unspec (T: TYPES) = struct
  include T

  type value =
  | Nat of nat
  | Clos of (var * expr * env)

  (* Some more stuff *)
end

I would like to make it modular, in the sense that the Types module would be split in 2: one for the nat part, and one for the rest. Unfortunately I do not know how to do that, as I would need to parameterize a module type by another module type, and I don’t think it’s possible.

Do you have a suggestion to make this work, or an alternate approach?

2 
module type BASETYPES = sig
  type nat
end

module type TYPES = sig
  type env
  type var
end

module Unspec (BT: BASETYPES) (T: TYPES) = struct
  include T

  type value =
  | Nat of BT.nat
  | Clos of (var * expr * env)

  (* Some more stuff *)
end

module BaseTypes = struct
  type nat = int
end

module rec Types : sig
  type var = string
  type env = Unspec(BaseTypes)(Types).value list
end = Types

Something like that ? (I haven’t checked whether it compiles)

3

Thank you for the suggestion, but what I’m looking after is a way to have the definition of the env type be in another file from the Unspec one. More precisely, I would like a file providing the implementation of environments when given the type of values. It could be either

module Type (M:sig type value end) = struct
  type var = string
  type env = M.value SMap.t
end

or

module Type = struct
  type value
  type var = string
  type env = value SMap.t
end

Then I want a way to give this implementation to a functor that provides the value type, which recursively depends on var and env.

4

Here is an alternative solution:

(* types.ml *)
module Type (M:sig type value end) = struct
  type var = string
  type env = M.value SMap.t
end

(* unspec.ml *)
module type TYPES = functor (M: sig type value end) ->
  sig
    type var
    type env
  end

module Unspec (T:TYPES) = struct
  module rec M : sig
    type value =
    | Nat of int
    | Clos of (T(M).var * value * T(M).env)
  end = M

  include T(M)
  include M
end

I’m not sure how usable it will be in practice; in particular the signature of the result of the Unspec functor is a bit complicated and I don’t think you can abstract the intermediary module M away.

5

(@vlaviron I just saw your reply as I was writing this. Thank you again for the suggestion, but the solution below might be simpler.)

One of the great things of simplifying a problem to explain it is that one can find a solution… Here it is:

(* File 1 *)

module type ARITHTYPE = sig
  type nat = int
end

(* File 2 *)
module type ENVTYPE = sig
  type value
  type var = string
  type env = (var * value) list
end

(* File 3 *)

module type TYPES = sig
  type env
  type nat
  type var
end

module Unspec (T: TYPES) = struct
  include T

  type expr =
  | Const of nat

  type value =
  | Nat of nat
  | Clos of (var * expr * env)
end

module rec Types : sig
  include ARITHTYPE
  include ENVTYPE with type value = Unspec(Types).value
end = Types
6

Ah, indeed this is much simpler. To me it looks so similar to your initial code that I didn’t even think that you could be looking for something like that. Glad to have helped though.