I was pleasantly surprised to discover that OCaml has been supporting modules as first-class objects since v3.12 (2011). Intuition suggests that first-class modules should be expressive enough to simulate Haskell-style typeclasses in OCaml. Turns out this is the route taken by Leo White et al to introduce adhoc polymorphism via Modular Implicits to OCaml. White et al’s paper describes their principled approach in detail, and is definitely worth a read. In this blog, I present a series of OCaml examples involving (first-class) modules that gradually build up to modular implicits. The full code (with directions to run) is available here.

First lets recall the basics of modules and module types (signatures) in OCaml. Lets define a module type T1:

Lets also define a couple of modules of type T1:

Below is a functor that creates a module of type T1.

The type of XT1 is:

OCaml has first class modules. A first-class module is created by “packing” a module with a signature. Done using the “module” keyword.

It is possible to create a list of first-class modules, each encapsulating a different type:

However, i and b cannot be used as modules themselves; they need to be unpacked first. Unpacking is done using the “val” keyword:

Note that the information that type a in I is int is lost while packing it into a module of type T1. Thus I.eg is an abstract value of type I.a, as confirmed by utop:

Likewise, B.eg is an <abstr> value of type B.a.

Alternatively, we could’ve packed IntT1 into a module of type (T1 with type a = int), but that makes it impossible to create [i;b].

It would have been clear by now that first-class modules are simply variables with existential types. We pack a module to introduce an existential type, and unpack it to eliminate the existential. Like the values of other types, values of existential types are first class. The t2_of_t1 function shown below takes a value of type module T1, which is an existential type, and returns a value of type module T2, which is another existential type:

Unpacking an existential (i.e., conversion from a first-class module to a normal module) is done automatically by OCaml during pattern matches, so t2_of_t1 can be simplified as following:

We can now construct modules at run-time:

This feature lets us choose between various implementations of a signature at run-time, depending on the execution parameters. Another big advantage of first-class modules is that it helps us achieve qualified/bounded/adhoc polymorphism, and lets us obtain Haskell-style typeclasses in ML. For instance, lets consider a SERIALIZABLE signature that characterizes all serializable types:

Abstract type t is supposed to be instantiated with any concrete serializable type. Base types such as int, float etc., are obviously serializable:

Polymorphic types like lists are serializable iff their type parameters are serializable:

An aside: we implemented a serializable list as a functor above. An alternative approach is to implement it as a function. The second approach is more general than the first because functions can have polymorphic types but functors cannot (in OCaml).

We now have multiple to_string and of_string functions from SInt, SFloat, SList, and their compositions. Using first-class modules, we can write to_string and of_string wrappers for these functions that accept module parameters:

Observe that in the above examples, single to_string/of_string function is being used for various SERIALIZABLE types. This is exactly the behavior that typeclasses offer in Haskell! There is, however, one significant difference. While GHC infers typeclasses automatically, here we have to explicitly pass the module parameters to to_string/of_string functions. This seems redundant, given that such module parameters can be inferred from the context. For example, when the to_string function is applied on [[2;3];[4;5]], the only module parameter that lets this expression typecheck is SList(SList(SInt)), which must be inferable. This is infact the sort of reasoning performed by Modular Implicits (Leo White et al) OCaml extension, which lets us mark module parameters to a function as implicit, and later elide them when applying the function. This is demonstrated below:

We first mark the modules that serve as typeclass instances with the keyword implicit:

Functors can also be marked implicit, as long as their arguments are implicit (marked via the curly braces).

Lastly, we mark the module parameters of functions (for which adhoc polymorphism is intended) as implicit (again using curly braces):

Module parameters can now be elided:

Observe that to_string and of_string do not take module parameters. The code behaves as if both the functions are part of a typeclass, for which int, float and list instances exist.

So, to conclude, First-class modules + implicits = typeclasses in ML!.