Modular Explicits in OCaml › First-class Modules and Existentials [abs-fcm-exist]

Patrick Ferris

Sitting somewhere inbetween polymorphism and functors are first-class modules with existentials. This is a rather advanced use of OCaml's type system to be able to pack together a value of a particular type alongside a module that works with those kinds of values.

type set = Set : ((module Set.S with type t = 'a) * 'a) -> set
let size (Set ((module S), s)) = S.cardinal s

Packaging up integer sets is fairly straight-forward.

# let int_empty_set = Set ((module IntSet), IntSet.empty)
val int_empty_set : set = Set (<module>, <poly>)

From a user's perspective we are now closer to the realm of dynamic typing. Indeed, existentials are the way to do that in OCaml.

# type any = Any : 'a -> any
type any = Any : 'a -> any
# let any v = Any v
val any : 'a -> any = <fun>

Getting back into a typed world often involves some type witness gymnastics or runtime exceptions. Used sparingly, however, it can be very effective particularly when a user is none the wiser about the use of FCMs and existentials. I have made use of this trick to package together Irmin stores with implementations.

You could not, however, simply return the value that was packed away inside the existential.

# let woops (Set (_, s)) = s
Line 1, characters 26-27:
Error: The value s has type $a but an expression was expected of type 'a
       The type constructor $a would escape its scope
       Hint: $a is an existential type bound by the constructor Set.

There is also a runtime cost to the packing (and unpacking) of the module, not to mention the need for the extra allocation to create the existential in the first place. This will likely not be too significant, but is worth considering.

Context

Modular Explicits in OCaml [modular-explicits]

Patrick Ferris

Abstraction, in OCaml, often refers to hiding a particular type's implementation using a signature. For example:

module S : sig
  type t
  val add : t -> t -> t
end = struct
  type t = int
  let add = Int.add
end

In this post, however, I use abstraction to refer to the notion of code-reuse. Using features of the OCaml language to allow one piece of code to be used across different implementations or instantiations of a particular kind of value.

The goal of this post is to eventually discuss OCaml 5.5's modular explicits which is yet another feature that can allow a single piece of code to be used in various situations.

Polymorphism [abs-polymorphism]

Patrick Ferris

The most prevalent kind of abstraction is polymorphism. For example, List.length will work for all lists regardless of what kind of elements the list contains. However, polymorphism requires you to keep the polymorphic part of the type at arm's length. This can lead to suboptimal performance and/or limited usefulness.

List.mem is a good example; in order to be polymorphic List.mem relies on Stdlib.(=), the polymorphic equality operator. In turn, this operator achieves its polymorphism by performing a structural comparison of the runtime representation of its arguments.

A common way to overcome this is to use higher-order functions (functions that take functions as arguments).

# let rec mem ?(eq=Stdlib.(=)) v = function
  | [] -> false
  | x :: xs -> eq v x || mem ~eq v xs
val mem : ?eq:('a -> 'a -> bool) -> 'a -> 'a list -> bool = <fun>
# let mem_int_list = mem ~eq:Int.equal
val mem_int_list : int -> int list -> bool = <fun>

This works well in plenty of cases (List.map, Hashtbl.iter, etc.), however, it doesn't scale well from a user's perspective if the body of the function requires lots of specific functions (e.g. compare, length, pp). At the same time, we want to avoid the precarious duck-typing of something like Python too.

Functors [abs-functors]

Patrick Ferris

Functors are perhaps the second most prevalent feature of OCaml when it comes to code reuse. In the OCaml sense, a functor is a module that is parameterised by other modules. Set.Make is a functor that requires a module adhereing to the Set.OrderedType interface.

module IntSet = Set.Make (Int)
module StringSet = Set.Make (String)

Functors make it a lot easier to write implementations that depend on a large variety of functionality. Set.OrderedType is relatively tame in this sense, only needing a type t and a compare : t -> t -> int function.

Irmin, on the other hand, has functors that require users to provide Schemas. I have more thoughts about this API design in my Irmin retrospective.

It is important to consider the runtime costs of functors too. Whilst most of the time functors are instantiated at the toplevel, it does not come for free. You can have a play around with js_of_ocamlopt and see the generated output for how functors are applied.

First-class Modules and Existentials [abs-fcm-exist]

Patrick Ferris

type set = Set : ((module Set.S with type t = 'a) * 'a) -> set
let size (Set ((module S), s)) = S.cardinal s

Packaging up integer sets is fairly straight-forward.

# let int_empty_set = Set ((module IntSet), IntSet.empty)
val int_empty_set : set = Set (<module>, <poly>)

From a user's perspective we are now closer to the realm of dynamic typing. Indeed, existentials are the way to do that in OCaml.

# type any = Any : 'a -> any
type any = Any : 'a -> any
# let any v = Any v
val any : 'a -> any = <fun>

You could not, however, simply return the value that was packed away inside the existential.

# let woops (Set (_, s)) = s
Line 1, characters 26-27:
Error: The value s has type $a but an expression was expected of type 'a
       The type constructor $a would escape its scope
       Hint: $a is an existential type bound by the constructor Set.

Modular Explicits [abs-modular-explicits]

Patrick Ferris

OCaml 5.5 has module-dependent function types also known as modular explicits. The type of a function can now depend on types that come from a module that is also part of the function definition.

# let set_length : (module S : Set.S) -> S.t -> int =
  fun (module S) v -> S.cardinal v;;
val set_length : (module S : Set.S) -> S.t -> int = <fun>
# set_length (module IntSet) IntSet.empty;;
- : int = 0
# set_length (module StringSet) StringSet.empty;;
- : int = 0

In fact, we can now return values of a particular type that depends on a particular module!

# let empty_set : (module S : Set.S) -> S.t = 
  fun (module S) -> S.empty;;
val empty_set : (module S : Set.S) -> S.t = <fun>
# empty_set (module IntSet);;
- : IntSet.t = <abstr>
# empty_set (module StringSet);;
- : StringSet.t = <abstr>

Or, we can dynamically select implementations and values.

# let with_impl : 
    config:string -> ((module S : Set.S) -> S.t -> 'a) -> 'a = 
  fun ~config fn ->
  match String.lowercase_ascii config with
  | "string" -> fn (module StringSet) StringSet.empty
  | "int" -> fn (module IntSet) IntSet.empty
  | c -> invalid_arg c
val with_impl : config:string -> ((module S : Set.S) -> S.t -> 'a) -> 'a =
  <fun>

This is like a more usable version of the FCM-existential trick, though does require more manual type annotations on functions. For instance, I tried switching out OBuilder's use of existentials with modular explicits:

-type builder = Builder : (module Obuilder.BUILDER with type t = 'a) * 'a -> builder
-
 let log tag msg =
   match tag with
   | `Heading -> Fmt.pr "%a@." Fmt.(styled (`Fg (`Hi `Blue)) string) msg
   | `Note -> Fmt.pr "%a@." Fmt.(styled (`Fg `Yellow) string) msg
   | `Output -> output_string stdout msg; flush stdout

-let create_builder store_spec conf =
+let create_builder :
+  Store_spec.store Lwt.t -> Native_sandbox.config ->
+    ((module B : Obuilder.BUILDER) -> B.t -> 'a) -> 'a Lwt.t =
+  fun store_spec conf fn ->
   store_spec >>= fun (Store_spec.Store ((module Store), store)) ->
   let module Builder = Obuilder.Builder (Store) (Native_sandbox) (Docker_extract) in
   Native_sandbox.create ~state_dir:(Store.state_dir store / "sandbox") conf >|= fun sandbox ->
   let builder = Builder.v ~store ~sandbox in
-  Builder ((module Builder), builder)
+  fn (module Builder) builder

I think the code is more pragmatic; there is no longer an indirection via a type called builder. The extra type annotations do add a little noise. Roll on modular implicits.