Nested functors: Compiler can't determine type equality

Learning
18

I would like to attempt to summarize at least. (Disclaimer, I’m not much experienced with OCaml yet, but I want to give it a try.)

  • When creating a module Output thorugh a functor F by invoking F with some input module Input, i.e. F (Input), then the abstract types of the Output module will be equal to abstract types of another module if and only if that other module is created by passing the same Input to F. Specifically the module identity of the input needs to be equal.
type t1 = F(Input).t
type t2 = F(Input).t (* [t1] and [t2] are equal types. *)

type t3 = F(A).t
type t4 = F(B).t
(* [t3] and [t4] are equal if [A] and [B] have the same module identity. *)

  • A new module identity is created if

    • we pass a distinct input to the functor,
    • we pass an anonymous structure to the functor,
    • or if we store the result of a functor application in a module binding. E.g. module M1 = F (Input) and module M2 = F (Input) currently creates two distinct modules M1 and M2, even though they share the same abstract types because in both types we pass the same input module to F. This behavior may change in future versions of OCaml such that M1 and M2 may have the same module identity in future.

  • If we perform functor application and don’t bind the result to a module name, then the resulting modules have the same identity, i.e. even if M1 and M2 have different identities, calling F (Input) in one place and F (Input) in another place creates the same module. Only storing it under a specific name will generate a new identity for those modules.

module M1 = F (Input)
module M2 = F (Input)
(* Now [M1], [M2], and [F(Input)] have three different identities,
   but invoking [F(Input)] in one place and [F(Input)] in another place later,
   gives two modules with the same identity.
  • Functor application may come at a runtime cost. So when several modules use the same functor output (e.g. several modules share a Set.Make (Int)), you should create that module once, store the result (e.g. as Int_set), and then use that module which has been created once. See:

  • As stored modules may have a distinct identity, it may (as of today’s OCaml) matter that we re-use exactly those created/stored modules, because if we re-create them elsewhere with the same input, they will not have the same module identity as our stored modules. Because functor application comes with a runtime cost, re-using already instantiated functors is advisable anyway. (Following the argumentation of @octachron here.)

  • When some functors are instantiated only internally, it may be okay to do that only locally and not use a common (outside) instantiation.

I hope this more-or-less summarizes the state of the discussion, and, of course, feel free to correct me.

I’m not sure how I feel about it. As of now, I think I would prefer a more functional rather than generative approach. I believe it would support generic programming better. Specifically, I would like to be able to make module generation (using functors and input modules) be part of a (generic) library without paying a runtime-penalty, running into problems with distinct abstract types, or having to externalize that module generation. But these wishes may be rooted in ignorance about how functors are actually implemented. Always evaluating everything at compile-time probably comes at a price too (if even possible).

1 Like