Lecture 6.1: Parameterizing Programs by Modules
What we saw last week is the power of modules, which provide modularity by hiding implementation details from outside components. For example, let's look at a module type for a counter:
This counter is meant to just keep track of the number of times we have calledbump.Then, our workflow so far is to implement the counter:
module Counter : CounterSig = struct
type t = int
let fresh () = 0
let bump x = x + 1
let get x = x
end
Counter.t:
let count_evens (xs : int list) (acc : Counter.t) =
match xs with
| [] -> Counter.get acc
| x :: xs' ->
let acc' = if x mod 2 = 0 then Counter.bump acc else acc in
count_evens xs' acc'
However, we realize that there are other verions of the counter we want to use. For example, a version that gives identifiers to counters, and logs to the console whenever we call bump:
module CounterLogged : CounterSig = struct
type t = {
id : int;
value : int
}
let fresh () =
let id = Random.int 10000 in
{ id = id; value = 0 }
let bump c =
print_endline ("Bumping counter " ^ string_of_int (c.id));
{ c with value = c.value + 1 }
let get c = c.value
end
count_evens) to use this new version? We could just find-and-replace Counter with CounterLogged everywhere. But this seems really ugly. Going back and forth between Counter and CounterLogged requires modifying the application code --- and could potentially modify thousands of lines of code, if the application is large. Thus, we hope that there is a better way.
An Analogy
To see the solution, let's think about an analogous problem. We have a way to obtain strings via the network:
and then we will build an application based on this primitive:Now, instead of using read_string, we want to use another function read_file which reads from a file instead of the network --- in such a way that it is easy to go back and forth between read_string and read_file. The solution is to parameterize process by this function:
Thus, we can now just say let process_network = process read_network.
Thus, we chose to re-express process as a function from readers to applications.
Functors: Functions from Modules to Modules
We can do the the same for our Counter/CounterLogged example. We want to re-express the application code (count_evens)
as a "function". We can do that as follows:
module AppBuilder (C : CounterSig) = struct
let count_evens (xs : int list) (acc : C.t) =
match xs with
| [] -> C.get acc
| x :: xs' ->
let acc' = if x mod 2 = 0 then C.bump acc else acc in
count_evens xs' acc
end
module App = AppBuilder(Counter)
module AppDebug = AppBuilder(CounterLogged)
count_evens in a special kind of module, AppBuilder which has a
module argument of module type CounterSig. Modules which have arguments can be
thought of as functions from modules to modules, and are called functors.
The name is mysterious, but we just use the word "functor" to distinguish it
from "function", which is about values (rather than modules).
We call it AppBuilder because it is, indeed, not an application itself --- but a way to build an application, given a module for CounterSig.
We can then call App.count_evens and AppDebug.count_evens as we wish.
Using Functors for Generic Testing
Using functors, we can create better, generic structures for testing modules.
If we take a look at a Counter, what properties should be true? A natural one would be to relate get and bump:
How could we test this for a generic implementation of Counter? We can do this by having the testing framework be a functor, that is parameterized by the counter we are testing:
module CounterTester (C : CounterSig) = struct
let rec gen_counter (n : int) : C.t =
if n <= 0 then C.fresh () else
C.bump (gen_counter (n - 1))
let test_counter (n : int) : bool =
let c = gen_counter n in
C.get (C.bump c) = (C.get c + 1)
let test () =
if test_counter (Random.int 100) then
()
else print_endline "Test Failed!"
end
module CounterLoggedTest = CounterTester(CounterLogged)
let _ = CounterLoggedTest.test ()
Example: Generic Data Structures
Throughout the last week, we have seen modules like below:
module type StringSetSig = sig
type t
val empty : t
val insert : string -> t -> t
val lookup : string -> t -> bool
end
string. What if we want to not fix this choice ahead of time?
We could do something like this:
(* Version 1 *)
module type SetSig = sig
type 'a t
val empty : 'a t
val insert : 'a -> t -> t
val lookup : 'a -> t -> bool
end
'a. Thus, if our set is built using a list, the only thing we can do is use OCaml's built-in polymorphic equality:
The issue with this function is that for user-defined types, OCaml guesses the right definition of = for that type. This might not be the verison we want!
For example, suppose we are storing unordered pairs of integers, where (2, 3) should be equal to (3, 2).
compare
For a realistic version of sets, we don't only need a custom equality, but need a custom notion of comparison. Equality will work for now, though.
Thus, instead, we will use a design based on functors. First, we specify using a module type the elements of the set:
Then, we will specify our module type for sets. We will do this by having two types in the signature: one for elements, and one for the sets.
(* Final version *)
module type SetSig = sig
type elem
type t
val empty : t
val insert : elem -> t -> t
val lookup : elem -> t -> bool
end
Now, we can make our set implmentation a functor from EqType to SetSig.
(* Version 1 *)
module ListSet (T : EqType) : SetSig = struct
type elem = T.t
type t = elem list
let empty = []
let insert x xs = x :: xs
let rec lookup x xs =
match xs with
| [] -> false
| x' :: xs' -> if T.equals x x' then true else lookup x xs'
end
The return type of ListSet is the module type SetSig with type elem = T.t. We can think of this as modifying SetSig by assigning the type elem to be equal to T.t.
Now, let's see how we can use ListSet:
module UnorderedPair = struct
type t = int * int
let equals (p1 : t) (p2 : t) =
(fst p1 = fst p2 && snd p1 = snd p2)
||
(snd p1 = fst p2 && fst p1 = snd p2)
end
module MySet = ListSet(UnorderedPair)
let _ =
let s1 = MySet.empty in
let s2 = MySet.insert (2, 3) s1 in (* ERROR: this expression has type ('a * 'b) but expected something of type MySet.elem *)
if MySet.lookup (3, 2) s2 then
print_endline "Good!"
else
print_endline ":("
The issue here is that the type for MySet, SetSig, keeps the elem type abstract, and thus we don't learn that elem = int * int. We can fix this by changing the ListSet module to a different return type that exposes it:
Note that we do not want to "seal" UnorderedPair behaind EqType when we define it:
t, and not allow us to actually use the set for the same reason as before, when elem was abstract.
Why does this work, even if we don't assign EqType to UnorderedPair? Because OCaml knows that UnorderedPair defines at least the required elements as EqType requires, so it can fit into a functor that expects something of type EqType. In particular, OCaml infers the type of UnorderedPair to be
EqType is defined to be
Since the first type has "more information" than the second, applying the functor here works.
Alternatively, we can seal UnorderedPair by restricting to EqType and then use with type to expose (or unseal) the extra information about type t:
OCaml's Map
This is exactly how maps work in the OCaml standard library. Let's take a look at the Map module (slightly simplified):
(* Input module type of map functor *)
module type OrderedType = sig
type t
val compare : t -> t -> int
end
compare returns a negative number if the first argument is smaller; zero if they are "equal"; and a positive number if the first argument is larger.
Then, we have the type for a Map:
(* Output module type of map functor *)
module type S = sig
type key (* Like our elem *)
type 'a t (* Maps holding values of type 'a *)
val empty : 'a t
val add : key -> 'a -> 'a t -> 'a t
....
end
This type is just like our SetSig, but adapted to maps. Then, we have a functor which constructs a Map module (which implements S) out of an OrderedType: