\section{s:recursive-modules}{Recursive modules}
%HEVEA\cutname{recursivemodules.html}
\ikwd{module\@\texttt{module}}
\ikwd{and\@\texttt{and}}

(Introduced in Objective Caml 3.07)

% TODO: relaxed syntax

\begin{syntax}
definition:
        ...
      | 'module' 'rec' module-name ':' module-type '=' module-expr \\
        { 'and' module-name ':' module-type '=' module-expr }
;
specification:
        ...
      | 'module' 'rec' module-name ':' module-type
                 { 'and' module-name':' module-type }
\end{syntax}

Recursive module definitions, introduced by the @"module rec"@ \ldots
@"and"@ \ldots\ construction, generalize regular module definitions
@'module' module-name '=' module-expr@ and module specifications
@'module' module-name ':' module-type@ by allowing the defining
@module-expr@ and the @module-type@ to refer recursively to the module
identifiers being defined.  A typical example of a recursive module
definition is:
\begin{caml_example*}{verbatim}
module rec A : sig
  type t = Leaf of string | Node of ASet.t
  val compare: t -> t -> int
end = struct
  type t = Leaf of string | Node of ASet.t
  let compare t1 t2 =
    match (t1, t2) with
    | (Leaf s1, Leaf s2) -> Stdlib.compare s1 s2
    | (Leaf _, Node _) -> 1
    | (Node _, Leaf _) -> -1
    | (Node n1, Node n2) -> ASet.compare n1 n2
end
and ASet
  : Set.S with type elt = A.t
  = Set.Make(A)
\end{caml_example*}
It can be given the following specification:
\begin{caml_example*}{signature}
module rec A : sig
  type t = Leaf of string | Node of ASet.t
  val compare: t -> t -> int
end
and ASet : Set.S with type elt = A.t
\end{caml_example*}

This is an experimental extension of OCaml: the class of
recursive definitions accepted, as well as its dynamic semantics are
not final and subject to change in future releases.

Currently, the compiler requires that all dependency cycles between
the recursively-defined module identifiers go through at least one
``safe'' module.  A module is ``safe'' if all value definitions that
it contains have function types @typexpr_1 '->' typexpr_2@.  Evaluation of a
recursive module definition proceeds by building initial values for
the safe modules involved, binding all (functional) values to
@'fun' '_' '->' '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.  If a
function component of a safe module is applied during this computation
(which corresponds to an ill-founded recursive definition), the
"Undefined_recursive_module" exception is raised at runtime:

\begin{caml_example}{verbatim}
module rec M: sig val f: unit -> int end = struct let f () = N.x end
and N:sig val x: int end = struct let x = M.f () end
\end{caml_example}

If there are no safe modules along a dependency cycle, an error is raised

\begin{caml_example}{verbatim}[error]
module rec M: sig val x: int end = struct let x = N.y end
and N:sig val x: int val y:int end = struct let x = M.x let y = 0 end
\end{caml_example}

Note that, in the @specification@ case, the @module-type@s must be
parenthesized if they use the @'with' mod-constraint@ construct.