A relatively short answer.

There are actually two problems with mutually recursive modules:
one is typing, and the other is initialization.

If your modules are dependent on each other at the typing level,
in particular if there is a cycle of dependencies between the mli files,
handling this kind of recursion (which is allowed in recursive modules
through a fixed point construction) would require compiling all the
interfaces simultaneously.
This goes against the ocaml policy of separate compilation.

The initialization problem is a bit simpler to solve, at least if you're
ready to allow some runtime errors for improper recursion.
Basically, one can reuse the scheme of recursive modules, of
starting by first building dummy modules, and then backpatching them
(i.e. writing the concrete definitions inside the structure).
Note that the layout of data in ocaml imposes some severe restrictions
on recursive modules, which could only be solved by changing this
layout. Also, some glue code would have to be generated at link time.

OCaml has been designed with separate compilation in mind from the
beginning.
This makes handling recursion between compilation units difficult, but
probably not impossible if we consider only the second case. Note
however that
a consequence is the possibility of initialization errors du to bad
recursion.

Jacques Garrigue

On 06/03/2020 17:06, Jan Rochel wrote:
> I'm sure that most of you have tripped at one point or another over the problem
> of OCaml not allowing for module files that mutually depend on each other. The
> fact that this is possible for modules within the same file raises the
> question: why not for module files?
>
> If I had to guess I'd say that the following reasoning led to that limitation:
> OCaml's semantics is script-like in that there is not a specific, explicitly
> defined entry point (such as a main-function in C), but each file is
> interpreted from top to bottom, so the order of the declarations within a file
> is critically important (due to side effects they may have). This also pertains
> to the order imposed on the module files before compilation and linking. (This
> order is either imposed by the user or a dependency generator). Now if one were
> to allow for recursive module files, then there would be no well-defined linear
> order imposable on them and therefore the semantics would become ambiguous.
>
> My first question:
> Is this the actual reasoning behind the limitation or are there other (perhaps
> more pertinent) reasons?
>
> My contention:
> The above-mentioned ambiguity already exists if a dependency generator is used.
> If we have modules A -> B <- C, then there are two orders possible: BAC and
> BCA. A and C may both produce side-effects within B during "initialisation" and
> unexpected things might happen in B. Given this fact, it should already be
> considered bad practice to write OCaml programs that are sensitive to module
> linking order. But if OCaml programs already have to be written with this
> semantic ambiguity in mind, then why not simply allow for mutually recursive
> module files?
>
> My second question:
> If the answer to my first question is yes, and if my contention is to the
> point, then I'd be curious to to know how difficult it would be to add a flag
> to the OCaml compiler allowing for mutually recursive dependencies?
>
> Jan