In a previous post, I noted the inclusion of the “functor” feature in OCaml, which allows us to define functions from modules to modules. This post will demonstrate how to use functors. The ability to define functors depends on the ability to define modules nested inside of other modules, which this post will also explain.

Nested Modules and Signatures

Previously, I simplified things by claiming that a signature consists of the following components:

• A set of data types defining the sorts of entities that can be manipulated.
• A set of operations to be performed on the entities.
• A specification–that is, a set of laws–constraining what behaviors the signature’s clients may observe when invoking a sequence of its operations.

We now expand the provisional definition of signature to include two additional sets of components:

• A set of nested signature definitions that any module implementing S must define.
• A set of declarations of submodules that must be nested inside any module implementing S. Each submodule declaration must be ascribed with a signature.

A signature definition occurring in a signature has the following form:

module type R = sig
  ... components of subsignature go here ...
end

The right-hand side of the above example is just another signature recursively occurring inside S; its components have the five forms listed in the above bullet points.

A submodule declaration has the following form:

module X : T

Above, X is the name of the declared submodule and T is its signature, which can either have been declared in S or in some outer scope.

A nested signature definition can appear in a struct just as it would appear in a signature:

module type R = sig
  ... components of subsignature go here ...
end

A nested module within a struct might have the following form:

module X = M

and also might have this form:

module X : S = M

above, X is a module name, M is a module expression, and S is a signature to seal it with. A common type of module expression we’ve already seen is the struct construct, but there are others. Also, there are other variants for defining nested module components, which we’ll soon describe.

After adding nested modules and signature definitions, we revise our definition of what it means for a struct to implement a signature S:

• For each type declaration in S, the struct must have a matching (same name) concrete type definition.
• For each val declaration in S, the struct must have a concrete value definition (a let binding) whose name and type matches the declaration’s.
• For each inner signature definition named T in S, the struct must have a signature definition named T whose components are exactly the same as those in S’s definition of T.
• For each declaration of a module named X ascribed with signature R in S, the struct must define a nested module named X that implements signature R.
• The operations defined in the struct must obey the laws defined in S.

Pragmatics and Semantics of Nesting

Why nest a module in another module? Why nest a signature definition in a module?

Let M be a module with a nested module N. If M is sealed with a signature that does not include a declaration of N then N can be used as a “private vending machine” that only M has access to. The signature S that we seal N with need not be relevant to any module outside of M, so the definition of S can be nested inside of M as well. Here is a rough sketch of the scenario described above:

module type T = sig
   ... no "module N" or "module type S" components listed ...
end

module M : T = struct
  module type S = sig
    ...
  end

  module N : S = struct
    ...
  end

  ...
end

More generally, we could expose a module N from M’s signature T, but ascribed with a more restrictive signature S than the signature R that M’s components view N with. This would give M greater control over N than what outside clients would have. For example, below M has access to both the make and to_int operations, whereas clients of M only have access to make:

module type S = sig
  type t
  val make : int -> t
end

module type T = sig
   module N : S
end

module M : T =  struct
  module type R = sig
    type t = int
    val make : int -> t
    val to_int : t -> int
  end
  module N : R = struct
    type t = int
    let make x = x
    let to_int x = x
  end
  ...
end

Nesting can also be used as a composition and namespace management mechanism:

module type Poset = sig
  type t
  (** An element of the partially ordered set. *)

  val leq : t -> t -> bool
  (** The poset ordering *)

  (* LAW:
     The relation Leq defined such that

        a Leq b  iff  (leq a b) = true

     is reflexive, antisymmetric, and transitive
  *)
end

module type BoundedJoinSemilattice = sig
  type t
  (** The bounded join semilattice's elements *)

  module Poset : (Poset with type t = t)
  (** The partial ordering that forms the bounded join semilattice *)

  val join : t -> t -> t
  (** [join a b] is the least upper bound of [a] and [b] (with respect to Poset.leq) *)

  val bot : t
  (** [bot] is the bottom element (nullary join) of the bounded join semilattice *)

  (* LAW: For all values a,b of type t,
           (Poset.leq a (join a b)) and (Poset.leq b (join a b))
  *)

  (* LAW: For all values a,b,c of type t,
           (Poset.leq a c) and (Poset.leq b c) implies (Poset.leq (join a b) c)
  *)

  (* LAW: For all values a of type t,
           (Poset.leq bot a)
  *)
end

Above is a signature for bounded join semilattices (BJS). A BJS is a specific type of partially ordered set (poset) whose elements can be operated upon in ways that do not apply to arbitrary posets. Namely, we can take their finite joins. By nesting Poset inside BoundedJoinSemilattice, we can access general poset operations (namely, a “less than or equal to” operator) to perform on our BJS elements through the nested Poset module. We can even “upcast” a module M satisfying the BoundedJoinSemilattice signature to a module satisfying the Poset signature by projecting the nested Poset module from M.

Note that the signature ascribed to the Poset submodule is a sharing constraint signature, as described in my previous post. The constraint ensures that both the BoundedJoinSemilattice join operator and the Poset “less than or equal to” operator take elements of the same datatype as arguments.

Defining Functors

A functor is like a function, but instead of taking core-level values such as integers, strings, and functions as arguments, it takes modules as arguments, and likewise it returns a module as a result. Another way to think of a functor is that it is an implementation of a vocabulary (as described in the first post) in terms of another vocabulary.

Here is an example of implementing a vocabulary in terms of another. For illustration, let’s consider a simplified signature for the standard Set abstract datatype. It defines a vocabulary involving two entity types:

• The type t of sets
• The type item of elements contained in the sets of type t

And Set also provides type declarations for operations that can be performed on the above entity types:

• insert - to insert an element of type item into a set of type t
• member - to test whether an element of type item is contained in a set of type t
• etc.

It also defines some laws. The full signature is stated below

module type Set = sig
  (**
    A signature for manipulating *sets*, which are unordered collections of unique elements
  *)

  type t
  (** An unordered collection of unique elements *)

  type item
  (** An element which may be contained in a set of type t *)

  val emptyset : t
  (** [emptyset] is a set containing no elements *)

  val member : t -> item -> bool
  (** [member s v] Is [v] a member of [s]? *)

  val insert : t -> item -> t
  (** [insert s v] returns the smallest set containing [v] and all elements of [s] *)

  (* LAW: for all (v : item),
           (member emptyset v) = false
  *)

  (* LAW: for all (v : item) and (set : t),
           (member (insert set v) v) = true
  *)

  (* LAW: for all (v : item), (w : item), and (set : t) with not (v = w),
           (member (insert set v) w) = (member set w)
  *)
end

Examining the final law listed above, we notice something wrong: it mentions a predicate v = w, but our signature provides no operations that could be used to test whether two items v and w are equal. So instead of merely including a type component item, we will include a nested module Item of signature Equatable, where Equatable bundles the item type with an equality test operation as follows:

module type Equatable = sig
  type t
  (** The type of comparable values *)

  val eq : t -> t -> bool
  (** [eq a b] Is [a] equal to [b]? *)

  (* LAW:
     The relation Eq defined such that

     n Eq m <=> (eq n m) = true

     is an equivalence relation (reflexive, symmetric, and transitive)
  *)
end

Our revised Set signature follows:

module type Set = sig
  (**
    A signature for manipulating *sets*, which are unordered collections of unique elements
  *)

  type t
  (** An unordered collection of unique elements *)

  module Item : Equatable
  (** Defines a type [Item.t] of elements contained in sets of type [t],
      and provides [Item.t] with an equality test operator *)

  val emptyset : t
  (** [emptyset] is a set containing no elements *)

  val member : t -> Item.t -> bool
  (** [member s v] Is [v] a member of [s]? *)

  val insert : t -> Item.t -> t
  (** [insert s v] returns the smallest set containing [v] and all elements of [s] *)

  (* LAW: for all (v : Item.t),
           (member emptyset v) = false
  *)

  (* LAW: for all (v : Item.t) and (set : t),
           (member (insert set v) v) = true
  *)

  (* LAW: for all (v : Item.t), (w : Item.t), and (set : t) with (Item.eq v w) = false,
           (member (insert set v) w) = (member set w)
  *)
end

Now, our Set signature is self contained. We can implement the Set vocabulary in terms of the Equatable vocabulary by defining a functor MakeSet as follows:

module MakeSet = functor (Eq : Equatable) -> (struct
  type t = Eq.t list

  module Item = Eq

  let emptyset = []

  let rec member (set : t) (item : Item.t) : bool =
    match set with
    | w :: rest ->
      begin match Eq.eq w item with
      | true ->
        true
      | _ ->
        member rest item
      end
    | [] ->
      false

  let insert (set : t) (item : Item.t) : t =
    item :: set
end : (Set with module Item = Eq))

What we have above is the first variant of a nested module definition discussed previously: module X = M, where X is Set and the right-hand side M is a kind of module expression we have not yet seen. It is a functor, which has the form functor (X : S) -> M. A functor is essentially a module-level function that, when applied to a module argument of signature S named X, produces the result of evaluating module expression M which is in general defined in terms of X. In the above example, M is a sealing operation of the form N : (Set with module Item = Eq). It seals the module N with the signature Set with module Item = Eq.

The more readable syntactic sugar for nested functor definitions of the form module Y = functor (X:S) -> (M:T), where X and Y are module names, M is a module expressions, and S and T are signatures is module Y (X : S) : T = N:

module MakeSet (Eq : Equatable) : (Set with module Item = Eq) = struct
  type t = Eq.t list

  module Item = Eq

  let emptyset = []

  let rec member (set : t) (item : Item.t) : bool =
    match set with
    | w :: rest ->
      begin match Eq.eq w item with
      | true ->
        true
      | _ ->
        member rest item
      end
    | [] ->
      false

  let insert (set : t) (item : Item.t) : t =
    match (member set item) with
    | true ->
      set
    | false ->
      item :: set
end

In the first line of the above code, we have a construct we have not yet seen: the “module sharing constraint” with module Item = Eq. According to OCaml, it’s a shorthand for a sequence of type sharing constraints that equate each type defined in the nested module Item with the corresponding type defined by the argument module Eq; i.e. our module sharing constraint expands to the single type sharing constraint with type Item.t = Eq.t. When modules with nested submodules are shared, module sharing constraints recursively descend into submodules to share all types declared in them.

However, in the same way that we have chosen to view a signature as something more than OCaml does–i.e., unlike OCaml, which views a signature as a collection of type, val, signature, and module components, we view it as all of these things plus a collection of laws that the val (operation) implementations must satisfy–we also choose to view a module sharing constraint as something more than a shorthand for a sequence of type sharing constraints. A module sharing constraint should equate not only type components, but val components as well. We can share val components by inserting a collection of equational laws into the outer signature; for example, the above sharing constraint Set with module Item = Eq would insert a single law into the Set signature:

(** LAW:
  Item.eq = Eq.eq
*)

Now let’s apply our functor to construct a new module. We must first construct an argument to apply it to:

module IntEquatable : (Equatable with type t = int) = struct
  type t = int
  let eq (a : t) (b : t) = (a = b)
end

To construct an IntSet module, we apply MakeSet to IntEquatable and bind the result to a nested module identifier. The module expression for functor application is F(M), where F is the functor and M is the argument module. Therefore, we apply Set to IntEquatable in a nested module definition of the form module X : S = F(M) as follows:

module IntSet : (Set with module Item = IntEquatable) = MakeSet(IntEquatable)

The module sharing constraint, by equating IntSet.Item.eq with IntEquatable.eq, allows clients of IntSet to assume the following law:

  (** LAW: for all (v : Item.t), (w : Item.t), and (set : IntSet.t) with (IntEquatable.eq v w) = false,
                   (IntSet.member (IntSet.insert set v) w) = (IntSet.member set w)
  *)

which is obtained from

  (** LAW: for all (v : Item.t), (w : Item.t), and (set : t) with (Item.eq v w) = false,
           (member (insert set v) w) = (member set w)
  *)

by substituting IntEquatable.eq for Item.eq, substituting IntSet.member for member, and substituting IntSet.insert for insert.

The sharing constraint with module Item = Eq is also important because it allows us to obtain items to insert into our sets. Without it, the only operation available on the abstract type Item.t is eq : Item.t -> Item.t -> bool, which only consumes values of type Item.t but does not produce them. With the sharing constraint, we know that IntSet.Item.t = int. We can produce values of type int in a variety of well known ways, including integer literals and arithmetic operations.

Functor Signatures

All module-level expressions are classified using signatures. For example, a struct module expression appearing as struct ... component definitions ... end is classified using a signature of the form sig ... component declarations ... end. Functors are denoted using module-level expressions of the form functor (X : S) -> M, which are classified by functor signatures. A signature for a functor that transforms a module named X of signature S to a module of signature T, where T may depend on X, has the form functor (X : S) -> T.

For example, here is a signature that classifies the MakeSet functor:

module type MakeSetSig = functor (Eq : Equatable) -> (Set with module Item = Eq)

Conclusion

First, this post showed how modules can occur nested as submodules inside of other modules. Used in conjunction with module sharing, nested submodules allow the definition of laws that relate the operations and types of their containing modules to other modules in context. Second, it explained the use of functors, which define a “vocabulary” (as described in the first post) in terms of a variable input vocabulary. Among other uses, functors allow us to define standard library datatypes. For example, we demonstrated how a Set datatype vocabulary is parameterized by a vocabulary defining the sets’ element types via the MakeSet functor.

There is much more to say about functors. We have barely scratched the surface. In my next post, I will discuss more essential aspects of functors.