3.1 Why Modules?🔗

When a program is small enough, we can keep all of its details in one file and hold the whole design in our heads. Real application programs are simply too large and too complex for that. To manage this complexity, we practice modular programming: the code is composed of many separate modules that are developed and understood independently.

A module groups together associated types, functions, and data. Each module has an interface that describes what it provides to its clients, while its implementation details stay hidden inside. You have already been using modules: the OCaml standard library is organized as a collection of modules such as List, String, and Printf. When you write List.filter, you are calling the filter function of the List module.

3.2 Creating a Module🔗

Modules in OCaml are created by module definitions with the following syntax:

module ModuleName = struct
  (* definitions *)
end

The definitions inside struct ... end may be anything we can write at the top level: let bindings, type definitions, exception definitions, even nested modules. Module names must begin with an uppercase letter.

Here is our first version of a stack module. It represents a stack as an OCaml list, where the head of the list is the top of the stack:

OCaml REPL

module ListStack = struct 
    let empty = [] 
 
    let is_empty s = (s = []) 
 
    let push x s = x :: s 
 
    let peek = function 
      | []   -> failwith "Empty" 
      | x::_ -> x 
 
    let pop = function 
      | []    -> failwith "Empty" 
      | _::xs -> xs 
 end;;

[Output]
module ListStack :
  sig
    val empty : 'a list
    val is_empty : 'a list -> bool
    val push : 'a -> 'a list -> 'a list
    val peek : 'a list -> 'a
    val pop : 'a list -> 'a list
  end

Notice that the toplevel replies with the module’s signature: the names and types of everything defined inside it. Recall that let peek = function ... is shorthand for let peek x = match x with ....

3.3 Scope and the Dot Operator🔗

After a module has been defined, you can access the names within it using the . (dot) operator:

OCaml REPL

module M = struct 
    let x = 42 
 end;; 
 
 M.x;;

[Output]
module M : sig val x : int end
- : int = 42

let f x =
  let y = List.filter ((>) 0) x in ...

let f x =
  let open List in
  let y = filter ((>) 0) x in ...

3.4 Module Signatures🔗

A signature is the interface of a structure. A signature specifies which components of a structure are accessible from the outside, and with which types. Signatures are written with module type:

module type SIGNAME = sig
  (* val and type declarations *)
end

A signature can be used to hide some components of a structure, such as local helper functions. In the following example, the signature FOO only declares add, so the mult function of Foo is not accessible from outside:

OCaml REPL

module type FOO = sig 
    val add : int -> int -> int 
 end;; 
 
 module Foo : FOO = struct 
    let add x y = x + y 
    let mult x y = x * y 
 end;; 
 
 Foo.add 3 4;; 
 
 Foo.mult 3 4;;

[Output]
module type FOO = sig val add : int -> int -> int end
module Foo : FOO
- : int = 7
Line 2, characters 1-9:
2 |  Foo.mult 3 4;;
     ^^^^^^^^
Error: Unbound value Foo.mult

The call Foo.add 3 4 succeeds, but Foo.mult 3 4 is rejected: mult exists inside the module, yet the signature makes it invisible to clients. A few things to know about signatures:

• Convention: signature names are often written in all-caps (this is a convention, not a requirement).

• Items can be omitted from a signature. This is what gives us the ability to hide values.

• The default signature of a module hides nothing. If you enter a module with no signature ascription, OCaml infers a signature that exposes everything — exactly what the toplevel printed back for ListStack above.

3.5 The Stack Signature🔗

Let us give our stack a proper interface. Here is a signature for stacks, including the type of stacks themselves:

module type Stack = sig
  type 'a stack = 'a list
  val empty    : 'a stack
  val is_empty : 'a stack -> bool
  val push     : 'a -> 'a stack -> 'a stack
  val peek     : 'a stack -> 'a
  val pop      : 'a stack -> 'a stack
end

The declaration type ’a stack = ’a list says: a stack of ’as is a list of ’as. We can now ascribe this signature to our module and use it:

OCaml REPL

module type Stack = sig 
    type 'a stack = 'a list 
    val empty    : 'a stack 
    val is_empty : 'a stack -> bool 
    val push     : 'a -> 'a stack -> 'a stack 
    val peek     : 'a stack -> 'a 
    val pop      : 'a stack -> 'a stack 
 end;; 
 
 module ListStack : Stack = struct 
    type 'a stack = 'a list 
    let empty = [] 
    let is_empty s = (s = []) 
    let push x s = x :: s 
    let peek = function 
      | []   -> failwith "Empty" 
      | x::_ -> x 
    let pop = function 
      | []    -> failwith "Empty" 
      | _::xs -> xs 
 end;; 
 
 let t = ListStack.empty;; 
 let t2 = ListStack.push 10 t;; 
 let t3 = ListStack.push 20 t2;; 
 ListStack.peek t3;; 
 let t4 = ListStack.pop t3;;

[Output]
module type Stack =
  sig
    type 'a stack = 'a list
    val empty : 'a stack
    val is_empty : 'a stack -> bool
    val push : 'a -> 'a stack -> 'a stack
    val peek : 'a stack -> 'a
    val pop : 'a stack -> 'a stack
  end
module ListStack : Stack
val t : 'a ListStack.stack = []
val t2 : int ListStack.stack = [10]
val t3 : int ListStack.stack = [20; 10]
- : int = 20
val t4 : int ListStack.stack = [10]

Look carefully at the toplevel’s answers: the values of t2 and t3 are printed as lists like [10] and [20; 10]. Because the signature made the type equal to ’a list, the representation is visible to the user. Clients can see — and worse, exploit — the fact that a stack is a list. Nothing stops a client from writing [1;2;3] |> ListStack.peek or pattern matching a stack against x::xs, which defeats the purpose of the interface.

3.6 Abstract Types🔗

We can fix this by making the type abstract: declare the type in the signature without giving its definition.

module type Stack = sig
  type 'a stack            (* type is abstract *)
  val empty    : 'a stack
  val is_empty : 'a stack -> bool
  val push     : 'a -> 'a stack -> 'a stack
  val peek     : 'a stack -> 'a
  val pop      : 'a stack -> 'a stack
end

OCaml REPL

module type Stack = sig 
    type 'a stack 
    val empty    : 'a stack 
    val is_empty : 'a stack -> bool 
    val push     : 'a -> 'a stack -> 'a stack 
    val peek     : 'a stack -> 'a 
    val pop      : 'a stack -> 'a stack 
 end;; 
 
 module ListStack : Stack = struct 
    type 'a stack = 'a list 
    let empty = [] 
    let is_empty s = (s = []) 
    let push x s = x :: s 
    let peek = function 
      | []   -> failwith "Empty" 
      | x::_ -> x 
    let pop = function 
      | []    -> failwith "Empty" 
      | _::xs -> xs 
 end;; 
 
 let t = ListStack.empty;; 
 let t2 = ListStack.push 10 t;; 
 let t3 = ListStack.push 20 t2;; 
 ListStack.peek t3;; 
 let t4 = ListStack.pop t3;;

[Output]
module type Stack =
  sig
    type 'a stack
    val empty : 'a stack
    val is_empty : 'a stack -> bool
    val push : 'a -> 'a stack -> 'a stack
    val peek : 'a stack -> 'a
    val pop : 'a stack -> 'a stack
  end
module ListStack : Stack
val t : 'a ListStack.stack = <abstr>
val t2 : int ListStack.stack = <abstr>
val t3 : int ListStack.stack = <abstr>
- : int = 20
val t4 : int ListStack.stack = <abstr>

The implementation is not visible anymore: every stack value is printed as <abstr>. The only way to build or inspect a stack is through empty, push, peek, pop, and is_empty. This is data abstraction, the same idea as private fields plus a public interface in object-oriented languages — but enforced by the type system at the module boundary.

open ListStack
let s  = empty
let s2 = push 10 s
let s3 = push 20 s2

3.7 Case Study: A Fraction Module with an Invariant🔗

Abstraction is not just about hiding helper functions; it lets a module enforce invariants on its data. Consider a module for fractions with the invariant that fractions are always stored in reduced form (e.g., 2/8 is stored as 1/4).

First, a version whose signature exposes the representation:

OCaml REPL

module type FRACTION = sig 
    type fraction = Frac of int * int 
    exception BadFrac 
    val make : int * int -> fraction 
    val add : fraction * fraction -> fraction 
    val toString : fraction -> string 
 end;; 
 
 module Fraction : FRACTION = struct 
    type fraction = Frac of int * int 
    exception BadFrac 
 
    (* gcd and reduce are not in the signature: hidden helpers *) 
    let rec gcd (x,y) = 
      let (x,y) = if x >= y then (x,y) else (y,x) in 
      if y = 0 then x else gcd (y, x mod y) 
 
    let reduce (Frac(x,y)) = 
      let d = gcd (x,y) in 
      Frac (x/d, y/d) 
 
    (* the denominator cannot be 0 *) 
    let make (x,y) = 
      if y = 0 then raise BadFrac 
      else reduce (Frac(x,y)) 
 
    let add (r1,r2) = 
      match (r1,r2) with 
        (Frac(a,b), Frac(c,d)) -> reduce (Frac(a*d + b*c, b*d)) 
 
    let toString (Frac(a,b)) = 
      if b = 1 then string_of_int a 
      else if a = 0 then "0" 
      else string_of_int a ^ "/" ^ string_of_int b 
 end;; 
 
 let f1 = Fraction.make (2,8);; 
 let f2 = Fraction.make (25,100);; 
 Fraction.toString (Fraction.add (f1,f2));; 
 
 let bad = Fraction.Frac (10,20);; 
 Fraction.toString bad;;

[Output]
module type FRACTION =
  sig
    type fraction = Frac of int * int
    exception BadFrac
    val make : int * int -> fraction
    val add : fraction * fraction -> fraction
    val toString : fraction -> string
  end
module Fraction : FRACTION
val f1 : Fraction.fraction = Fraction.Frac (1, 4)
val f2 : Fraction.fraction = Fraction.Frac (1, 4)
- : string = "1/2"
val bad : Fraction.fraction = Fraction.Frac (10, 20)
- : string = "10/20"

The functions gcd and reduce are omitted from the signature, so they are invisible outside the module — clients only get make, add, and toString, and every fraction built with make is reduced. But there is a hole: because the signature reveals type fraction = Frac of int * int, a client can bypass make and build Fraction.Frac (10,20) directly — an unreduced fraction (and nothing would stop Frac (1,0) either). The invariant is broken.

The fix is the same as for stacks: make the type abstract.

OCaml REPL

module type FRACTION = sig 
    type fraction            (* hide the representation *) 
    exception BadFrac 
    val make : int * int -> fraction 
    val add : fraction * fraction -> fraction 
    val toString : fraction -> string 
 end;; 
 
 module Fraction : FRACTION = struct 
    type fraction = Frac of int * int 
    exception BadFrac 
 
    let rec gcd (x,y) = 
      let (x,y) = if x >= y then (x,y) else (y,x) in 
      if y = 0 then x else gcd (y, x mod y) 
 
    let reduce (Frac(x,y)) = 
      let d = gcd (x,y) in 
      Frac (x/d, y/d) 
 
    let make (x,y) = 
      if y = 0 then raise BadFrac 
      else reduce (Frac(x,y)) 
 
    let add (r1,r2) = 
      match (r1,r2) with 
        (Frac(a,b), Frac(c,d)) -> reduce (Frac(a*d + b*c, b*d)) 
 
    let toString (Frac(a,b)) = 
      if b = 1 then string_of_int a 
      else if a = 0 then "0" 
      else string_of_int a ^ "/" ^ string_of_int b 
 end;; 
 
 let f1 = Fraction.make (2,8);; 
 let f2 = Fraction.make (25,100);; 
 Fraction.toString (Fraction.add (f1,f2));; 
 
 Fraction.Frac (10,20);;

[Output]
module type FRACTION =
  sig
    type fraction
    exception BadFrac
    val make : int * int -> fraction
    val add : fraction * fraction -> fraction
    val toString : fraction -> string
  end
module Fraction : FRACTION
val f1 : Fraction.fraction = <abstr>
val f2 : Fraction.fraction = <abstr>
- : string = "1/2"
Line 2, characters 1-14:
2 |  Fraction.Frac (10,20);;
     ^^^^^^^^^^^^^
Error: Unbound constructor Fraction.Frac

Now the constructor Frac is unbound outside the module: the only way to create a fraction is make, which validates the denominator and reduces. Every fraction in the program is guaranteed to satisfy the invariant. This pattern — a hidden representation, a small set of smart constructors, and operations that re-establish the invariant — is one of the most important uses of the module system.

3.8 Modules and Files🔗

So far we defined modules interactively. In real projects, modules correspond to files:

• A file foo.ml automatically defines a module named Foo (the file name, capitalized).

• A file foo.mli, if present, is the signature for Foo: only what is declared in the .mli is visible to other files. With no .mli, everything in foo.ml is exposed.

Let us organize the abstract stack as a small project with three files. The complete code is in the course repository under notes/modules/code/.

Stack.mli — the shared signature:

module type Stack = sig
  (* The type of a stack whose elements are type 'a *)
  type 'a stack

  (* The empty stack *)
  val empty : 'a stack

  (* Whether the stack is empty *)
  val is_empty : 'a stack -> bool

  (* [push x s] is the stack [s] with [x] pushed on the top *)
  val push : 'a -> 'a stack -> 'a stack

  (* [peek s] is the top element of [s].
     Raises Failure if [s] is empty. *)
  val peek : 'a stack -> 'a

  (* [pop s] pops and discards the top element of [s].
     Raises Failure if [s] is empty. *)
  val pop : 'a stack -> 'a stack
end

liststack.ml — an implementation:

(* Stack implemented as an OCaml list *)
open Stack

module ListStack : Stack = struct
  type 'a stack = 'a list

  let empty = []
  let is_empty s = (s = [])
  let push x s = x :: s
  let peek = function
    | []   -> failwith "Empty"
    | x::_ -> x
  let pop = function
    | []    -> failwith "Empty"
    | _::xs -> xs
end

main.ml — a client program:

open Liststack

let () =
  print_endline "ListStack example";
  let s = ListStack.empty in
  let s = ListStack.push 10 s in
  let s = ListStack.push 20 s in
  let s = ListStack.push 30 s in
  Printf.printf "%d\n" (ListStack.peek s);
  let s = ListStack.pop s in
  Printf.printf "%d\n" (ListStack.peek s)

Compile each unit in dependency order, then link:

ocamlc -c Stack.mli      # produces Stack.cmi (compiled interface)
ocamlc -c liststack.ml   # produces liststack.cmo (compiled object)
ocamlc -c main.ml
ocamlc -o main liststack.cmo main.cmo
./main

Expected output:

30
20

Compiling an .mli produces a .cmi (compiled interface) file; compiling an .ml produces a .cmo (compiled object) file. To swap in the variant-based implementation, we would compile varstack.ml instead and change open Liststack to open Varstack — nothing else in main.ml changes, because the client only relies on the Stack signature. For larger projects, dune (see the previous chapter) automates this: it discovers the dependencies among files and invokes the compiler in the right order.

#directory "_build";;
#load "liststack.cmo";;
open Liststack;;

#show ListStack;;
module ListStack : Stack.Stack

# ListStack.empty;;
- : 'a Liststack.ListStack.stack = <abstr>

3.9 Extending a Module with include🔗

Suppose we want to add a function max to the standard List module. We cannot modify the standard library, but we can build a new module that includes it:

module MyList = struct
  include List
  let max lst = fold_left Stdlib.max (hd lst) (tl lst)
end

include List re-exports all of List’s definitions inside MyList, so #show MyList;; lists every standard list function plus our new max. Clients can use MyList as a drop-in replacement for List:

# MyList.length [1;2;3];;
- : int = 3
# MyList.max [3;7;2];;
- : int = 7

Note the difference between include and open: open List would only bring names into scope inside the definition of MyList; include List makes them part of MyList’s own interface.

3.10 Exercises🔗

Basic

1. Define a module Circle containing a constant pi = 3.14159 and a function area : float -> float that computes the area of a circle from its radius. Use it both with the dot operator and after open.

2. Given module A = struct let v = 1 end and module B = struct let v = 2 end, what is the value of v after open B followed by open A? Explain.

3. Write a signature MATH that exposes only double : int -> int from a module that also defines a helper times : int -> int -> int. Verify that times is inaccessible from outside.

4. The signature Sig declares val f : int -> int. Which of these implementations satisfy it, and why?

   let f x = x + 1
   let f x = x
   let f x = string_of_int x

Intermediate

1. Write a signature Queue with an abstract type ’a queue and operations empty, enqueue, front, and dequeue. Implement it with a module ListQueue that represents a queue as a list.

2. Give a second implementation TwoListQueue of your Queue signature that stores the queue as a pair of lists (a front list and a reversed back list). Client code should run unchanged against either implementation.

3. Extend the abstract Fraction module with mult : fraction * fraction -> fraction and equal : fraction * fraction -> bool. Make sure mult preserves the reduced-form invariant. Why can equal be implemented with = on the representation, given the invariant?

4. Split your Queue exercise into files (Queue.mli, listqueue.ml, main.ml) and compile it with ocamlc, then with dune.

Advanced

1. Suppose the Stack signature made the type concrete (type ’a stack = ’a list). Give a concrete example of client code that works with ListStack but breaks when the implementation is switched to VarStack, and explain how the abstract type prevents this situation from ever arising.

2. Design a module IntSet for sets of integers with an abstract type, maintaining the invariant that the internal list is sorted and duplicate-free. Which operations must re-establish the invariant? Could a client observe the difference if you later switched the representation to a binary search tree?

3. Using include, build a module SafeList that extends List with safe_hd : ’a list -> ’a option and safe_tl : ’a list -> ’a list option, which return None instead of raising exceptions. Then restrict SafeList with a signature that hides the exception-raising hd and tl it inherited.

inventory/
├── dune-project
├── lib/
│   ├── dune
│   ├── item.ml            <- module Item  (you complete this)
│   └── stock.ml           <- module Stock (you complete this)
├── bin/
│   ├── dune
│   └── main.ml            <- demo executable (given)
└── test/
    ├── dune
    └── test_inventory.ml  <- OUnit test suite (given)

dune build
dune runtest
dune exec bin/main.exe

Keyboard: 7 in stock
Total value: $825.73

3.11 Summary🔗

Terminology: module / structure (the implementation, struct ... end), signature / module type (the interface, sig ... end), signature ascription (module M : Sig), abstract type, invariant, persistent data structure, open vs. include.

Looking ahead, signatures and abstract types are OCaml’s take on ideas you will meet repeatedly in this course: interfaces and information hiding in object-oriented languages, type classes and traits (in Rust), and the general principle that a type system can enforce a design discipline. The stack and fraction modules also preview algebraic data types at work in real APIs, and the persistent-data-structure style reappears when we study interpreters and garbage collection.