Well, that comes with a few caveats:

1. OCaml generates additional information that it stores in .cmi/.cmx files.

2. OCaml does not allow for mutual dependencies between modules, even in the linking stage. Object files must be provided in topologically sorted order to the linker.

3. OCaml supports shared generics, which cuts down on the amount of code replication (at the expense of requiring additional boxing and tagged integers in order to have a uniform data representation).

All true except #3 (partially).

> 1. OCaml generates additional information that it stores in .cmi/.cmx files.

On this point I'd say that it could probably embed the cmx file as "NOTE" sections in the ELF object files, but likely they didn't do it that way because it's easier to make it work cross-platform. Every "pre-compiled header" system I've seen generates some kind of extra file of compiled data which you have to manage, so I don't think this is a roadblock.

> 2. OCaml does not allow for mutual dependencies between modules, even in the linking stage. Object files must be provided in topologically sorted order to the linker.

I believe this is to do with the language rather than to do with modules? For safety reasons, OCaml doesn't allow uninitialized data to exist.

Although (and I say this as someone who likes OCaml) it does sometimes produce contortions where you have to split a natural module in order to satisfy the dependency requirement. I've long said that OCaml needs a better system for hierarchical modules and hiding submodules (better than functors, which are obscure for most programmers).

> 3. [...] at the expense of requiring additional boxing and tagged integers [...]

I think this is fixed by OCaml GADTs: https://blogs.janestreet.com/why-gadts-matter-for-performanc... However this is a new feature and maybe not everyone is using it so #3 is still a fair point.

> I believe this is to do with the language rather than to do with modules?

Both, sort of. The problem is that mutually recursive modules are tricky. So, it's a limitation of the language, but one that is there for a reason.

> I think this is fixed by OCaml GADTs

No, GADTs solve a different problem. Essentially, normal ADTs lose type information (due to runtime polymorphism). GADTs give you compile time polymorphism, so the compiler can track which variant a given expression uses. Consider this:

  # type t = Int of int | String of string;;
  type t = Int of int | String of string
  # [ Int 1; String "x" ];;
  - : t list = [Int 1; String "x"]
  # type _ t = Int: int -> int t | String: string -> string t;;
  type _ t = Int : int -> int t | String : string -> string t
  # [ Int 1; String "x" ];;
  Error: This expression has type string t
         but an expression was expected of type int t
         Type string is not compatible with type int 

The problem with functors (and also type parameters) is the following. Assume that you have a functor such as:

  module F(S: sig type t val f: t -> t end) = struct ... end

To avoid code duplication, F has to pass arguments to S.f using the same stack layout, regardless of whether it's (say) a float, an int, or a list. This means that floats need to get boxed (so that they use the same memory layout) and integers have to be tagged (because the GC can't tell from the stack frame what the type of the value is).

Where can I learn more about it in a high level way instead of delving into source code?

I am curious how it is done in a portable way across all OSes, specially crude system linkers and OSes without POSIX semantics.

For example, I imagine this can be made via ELF sections, but not all OSes use ELF.

These links explain the extra files: https://ocaml.org/learn/tutorials/filenames.html https://realworldocaml.org/v1/en/html/the-compiler-frontend-... https://realworldocaml.org/v1/en/html/the-compiler-backend-b...

The cmx data could be converted to ELF note sections, but the whole thing has to work on Windows as well, so I guess they didn't want to depend on ELF.

In most projects, you can add this to your Makefile and forget about it:

    .mli.cmi:
            ocamlfind ocamlc $(OCAMLFLAGS) $(OCAMLPACKAGES) \
                -c $< -o $@
    .ml.cmo:
            ocamlfind ocamlc $(OCAMLFLAGS) $(OCAMLPACKAGES) \
                -c $< -o $@
    .ml.cmx:
            ocamlfind ocamlopt $(OCAMLFLAGS) $(OCAMLPACKAGES) \
                -c $< -o $@

    clean:
            rm -f *.cmi *.cmo *.cmx *.cma *.cmxa

Thanks for the hints.

My guess: The trick is not to have "template instantiation" but "module instantiation" (aka Functors in OCaml). Now you can instantiate only once. For example, if the compiler encounters "List<Foo>", it would instantiate into the "List$Foo.o" file or not if it already exists. Java works similarly, except the files have the extension "class" instead of "o".

More generally speaking: The trick must be to not generate identical instantiations multiple times. So you must have a way to check, if you already generated it. Of course, the devil is in the details (e.g. is equivalence on the syntactic level enough?).

You are focusing only on generics and missing all the module metadata and related module type information.

In module based languages, the symbol table is expected to be stored on the binary, either to be directly used by tools or to generate human readable formats (.mli).

So if one uses the system C linker, it means being constrained to the file format used by such linker.