Crash Course in OCaml Modules

Tim McGilchrist (@lambda_foo) lambda

1 / 34

What to expect?

What is OCaml?
Module Concepts
Comparison to Haskell
Code, Code and more Code

lambda

2 / 34

Things to expect from this talk.
OCaml functors ain't Haskell functors.
Hey man, where's my fmap. Such confuse, much wow.
introduce people to the OCaml module system
What OCaml functors are
What sorts of problems they let us solve.

Outcomes

Understand OCaml's module system
Appreciate difference between Modules and Type Classes
Perhaps write some OCaml, it's awesome!

3 / 34

The ML module system comes up in conversations around Haskell needing a module system, why building a Haskell module system is hard and just how do I relate ML Modules to things in other languages like Traits in Scala or Type Classes in Haskell. Rather than having a bunch of handwaving about modules can do this and type classes can do that, it'd be better if everyone had a basic understanding of what ML modules are. So the discussion can come from a place of knowledge

Anecdote about why I chose to learn OCaml rather than Haskell. be a contrarian

Lets dive into some terminology

Right-aligned image

4 / 34

Terminology

The key parts of OCaml's Module System are:

Structures
Signatures
Functors

lambda

5 / 34

OCaml has 2 levels or languages;

language of functions and value.
language of modules and functors

OCaml type declarations

Types are in lowercase.
Type variables are written with a single quote 'a
Type constructors are reversed

(Int, Int)       -- Haskell
int * int        -- OCaml
[Bool]           -- Haskell
bool list        -- OCaml
foldl :: (b -> a -> b) -> b -> [a] -> b
fold_left : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a
data Tree a = Node a (Tree a) (Tree a) | Leaf
type 'a tree = Node of 'a * 'a tree * 'a tree | Leaf

6 / 34

Explain the code examples.

Structures

Structures provide units of organistion within OCaml

module IntSet = struct
  type t = int
  type set = t list
  let empty = []
  let member i s = List.exists (fun x -> x = i) s
  let insert i s = if member i s then s else (i::s)
end

7 / 34

Values in the module language
Structures group together declarations of data types and functions. In a similar way to what you'd be familar with in Haskell.
Introduce a structure using struct end keyword pair.
Implicit structure name from the file name.

Calling Structures

Called via dot notation

IntSet.t
IntSet.empty
IntSet.member

8 / 34

Pretty much as you'd expect coming from another language

Nested Structures

module IntSet = struct
  module Compare = struct
    type t = int
    let eql x y = x = y
  end
end
IntSet.Compare.eql 1 1

Nested structures can be nested.

9 / 34

Using Structures

open structure at top of the file
local open at the call site
use module alias

open IntSet
Compare.eql 1 1
(* or *)
IntSet.Compare.(eq 1 1)
(* or *)
let module S  = IntSet.Compare
in S.eql 1 1

10 / 34

Using structures needs to more convenient that using the long form names especially if we want to use nested modules to organise our code.

Opening the module at the top of a file. Using open then the name of the module, everything that the module exports will be available in the opening module. This is convenient, no need to pre-pend anything with module names, the downside however is you pollute the namespace. Might not want to have everything in this namespace, eg name clashes. Good idea to keep it small.
Convenient option if you're only using the module in a few places within a file. Especially if you're using the same module repeatedly in a a statement.
Helpful to keep what the short name of a module is close to where it's being used.

Signatures

Defines an interface for a structure.

module type Set = sig
  type 't set
  val empty : 't set
  val member : 't set -> 't -> bool
  val insert : 't set -> 't -> 't set option
end

List of declarations without any implementation

11 / 34

List of declarations without any implementations
Definitions can be more abstract than structure
Introduced with sig end keywords
used to hide details. In this case we're not exporting the concrete type for set, making it abstract.
Typically, you'll have your struct in one file say set.ml and the signature defined in another file called set.mli.

Example

module type Monad = sig
  type t
  val bind : 'a t -> ('a -> 'b t) -> 'b t
  val return : 'a -> 'a t
  val (>>=): 'a t -> ('a -> 'b t) -> 'b t
  val (>>|): 'a t -> ('a -> 'b) -> 'b t
end

12 / 34

Lets introduce a signature for a Monad.

Functors

No Haskell functors here comrades.
Functions from struct to struct
aka Paramterised Structures

Right-aligned image

13 / 34

Functors in OCaml aren't like Haskell functors, they don't provide an fmap across a particular structure. Though they do perform a similar purpose, just it's at the module level. Think of functors as functions from struct to struct. Another way, to think of it is lifting functions into the module language

Let's look at an example!

Example I

module type ORDERING = sig
  type t
  val compare : t -> t -> int
end
module type Set = sig
  type 't set
  val empty : 't set
  val member : 't set -> 't -> bool
  val insert : 't set -> 't -> 't set option
end

14 / 34

Introduce this new signature called ORDERING
Repeat our Set signature from before

Example II

module MakeSet (O : ORDERING) = struct
  type t = O.t
  let empty = []
  let rec member s x =
    match s with
       [] -> false
      | hd::tl ->
        match O.compare x hd with
           0  -> true
         | 1  -> false
         | -1 -> member tl x
  let rec insert x s =
    ...
end

15 / 34

How is the functor defined?
Use O in implementation of other functions.
MkSet is completely defined in terms of it's argument O
Functors can be defined over multiple modules, just tack another set of brackets after the first and before the equals

Using Functor

module IntOrdering = struct
  type t = int
  let compare = Int.compare
end
module IntSet = MakeSet(IntOrdering)
let a = IntSet.insert 1 IntSet.empty
IntSet.member 1 a
(* Using local opens *)
let a = IntSet.(insert 1 empty)

16 / 34

Introduce an ordering for ints
Call functor using our Int ordering
make go now!

Review

Structures group together types and functions with implementations
Signatures interface for a structure
Functors are functions from struct to struct

17 / 34

So let's take a moment to review what we've covered so far. If nothing else, I'd be great if you can take these defintions away with you.

Comparison to Type Classes

Type Classes provide adhoc polymorphism
Module system explicit configuration of program components and the use of data abstraction
Different purposes but significant overlap

18 / 34

Type classes focus on bringing implict program construction and adhoc polymorphism to Haskell. By implicit construction I mean in using type classes you don't need to say which instance of a type class to use. Haskell works that out for you. Providing some sort of guarantee that there is only 1 possible implementation (Though there are a snumber of ways around this if you're sufficiently devious)

Modules on the other hand emphasise explicit configuration of program components and the use of data abstraction. Namely a means for decomposing large programs into smaller pieces.

I'm probably oversimplifying the motivations on both sides, the point is they're not trying to solve the same problem. However there is some overlap in functionality.

So lets see some code showing how to translate Haskell Type Classes into OCaml

Type Classes to Signatures

Haskell

class Show a where
    show :: a -> String

OCaml

module type SHOW = sig
  type t
  val show : t -> string
end

19 / 34

So type classes in Haskell become signatures in OCaml. Lets look at the show type class as a simple example, though this applies to any type class.

Instances to Structures

Haskell

instance Show Int where
    show = ... -- provided in ghc

OCaml

module ShowInt = struct
  type t = int
  let show = string_of_int
end

20 / 34

Haskell you declare an instance of Show for your type.
OCaml we create a struct that has the right interface

Using Type Class

Haskell

csv :: Show a => [a] -> String
csv []  = ""
csv [x] = show x
csv h:t = show h ++ "," ++ csv t
csv [1,2,3] => "1,2,3"

Functions that use type classes do not need to do anything special

21 / 34

Using Type Class Modules

OCaml

module Csv(S:SHOW) = struct
  let rec to_csv : S.t list -> string =
    function
        []   -> ""
      | [x]  -> S.show x
      | h::t -> S.show h ^ "," ^ to_csv t
end
module X = Csv(ShowInt)
X.to_csv [1;2;3] => "1,2,3"

Callers Get Wrapped In Functors
Manually instantiate the version of the function

22 / 34

VerdictType Classes can be translated into ModulesType Classes become Signatures
Instances become Structures
Callers Get Wrapped In Functors
Manually instantiate the version of the function

OCaml version is slightly more verbose
OCaml requires specifying the instance
Haskell finds the instance you want
23 / 34

more verbose The OCaml code is more verbose that the corresponding Haskell code. Even if you use a less simplistic example where there isn't a built in implementation for the type class. For example using Aeson where you do need to create your own instance.
for non-trivial type classes, you'll need to define an instance
Having said that, modules aren't really built for ad-hoc polymorphism, so they don't fare too badly.
Very useful to translate Haskell code examples in papers into OCaml versions.
Verbosity due to passing around the instance of show for that type.
Haskell also tracks the mapping from type to implementation, it's just not exposed.

Module Extras

A few things that aren't quite possible in Haskell:

Type safe extensions to existing modules
Parameterising library by architecture/platform/compiler
Library parameterised by their dependencies (Backpack)
Instantiate modules with state

24 / 34

talk through each of these in turn.
type safe extension, 2 standard library replacements use this technique to extend the basic standard library.
Cohttp library uses this technique to parameterise over 3 different concurrency platforms, Lwt, Async and Javascript

Type Safe Extensions

Using the include keyword we can extend an existing struct or signature.

module Listy = struct
  include List
  let intersperse t sep =
    match t with
      | [] | [_] -> t
      | x :: List.fold_right
          (fun y acc -> sep :: y :: acc) xs []
end
module List = Listy
include (module type of List)

25 / 34

Here include is bringing in contents of List into our Listy module
Then we're adding our own function intersperse
Export the module back out as List, effectively replacing List with our own version.
You can perform a similar thing with signatures, to bring in all the functions and types, then re-exporting them. *

Paramterising LibraryCohttp is a library for creating HTTP daemons.Supports 4 different asynchronous libraries
LWT - Unix threads
Async - Unix threads
OS-independent used in Mirage unikernel
Javascript / XMLHTTPRequests

Mirage Unikernelapplications functorised across OS components

Irmin, a distributed databasedistributed storage functorised across storage implmentations

OCamlgraph, a generic graph library for OCaml
26 / 34

Heavy use of functors to divide abstract parts of http from plaform specific ones.
4 different async backends
Applications in MirageOS are functorized across all the operating system components that they depend on.
In Haskell you're forced to resort to CPP to do this sort of thing. While CPP is comparitively portable, it's untyped, has a different syntax than Haskell and is just kind of gross.

What are we savages???

Mirage OS

module type DEVICE = sig
  type error
end
module type CONSOLE = sig
  type error = [ ‘Invalid_console of string ]
  include DEVICE with type error := error
  val log_s : t -> string -> unit io
end
module Main (C: V1_LWT.CONSOLE) = struct
  let start c =
    let rec print () =
      C.log_s c "hello" >>= fun () ->
      OS.Time.sleep 1.0 >>= fun () ->
      C.log_s c "world" >>= print
      in print ()
end

27 / 34

Explain code
taken from Mirage OS
Some places use mutiple arguments inside a functor
see Metaprogramming with ML modules in the MirageOS

Mirage OS II

module Main
  (C: V1_LWT.CONSOLE) (FS: V1_LWT.KV_RO) (TMPL:
       V1_LWT.KV_RO)
  (S: Cohttp_lwt.Server)
  = struct ... end

28 / 34

Core Monad.make

module type Basic = sig
  type 'a t
  val bind : 'a t -> ('a -> 'b t) -> 'b t
  val return : 'a -> 'a t
end
module type S = sig .... end
module Make (M : Basic) : S with
  type 'a t := 'a M.t = struct
    let bind   = M.bind
    let return = M.return
    let join t = t >>= fun t' -> t'
    let ignore t = map t ~f:(fun _ -> ())
    ...
end

29 / 34

Modular Implicits

Proposal to improve ad-hoc polymorphism in OCaml

module type Show = sig
    type t
    val show : t -> unit
end
let print (implicit S : Show) x = S.show x
implicit module Show_int = struct
    type t = int
    let show x = Printf.printf "Show_int: %i\n" x
end
print 3

30 / 34

Extension to OCaml to provide better support for adhoc polymorphism.
Follows the ML discipline of maintaining explicit control over the namespace
Ambiguities in resolving an implicit module type resulting in a type error.
Taking inspiration from Scala’s implicits.
Work in progress

Records as Modules

Haskell records-as-modules style

data Index f = Index {
    record :: Descriptor -> f ()
  , lookup :: LogKey ->
      EitherT IndexError f (Maybe Descriptor)
}
makeS3Index root = Index {
    record = record' root
  , lookup = lookup' root
}
record' :: Address -> Descriptor -> S3Action ()
record root d = ...

31 / 34

Define a record for accessing log files
Clunky, record selectors everywhere
Performance, double dispatch everywhere
No closure over the types involved in the record
Record names must be unique
Useful technique

SummaryOCaml modules are worth knowing about
Structures combine types and function implementations
Signatures combine types and function signatures
Functors are functions from struct to struct
Simple translation of Type Classes to Modules
32 / 34

OCaml Modules provide features Haskell can't.

Thanks!

Tim McGilchrist @lambda_foo

Software Engineer @ Ambiata

Thanks!

33 / 34

Further ReadingML Modules and Haskell Type Classes: A Constructive Comparison.
Lightweight higher-kinded polymorphism
Metaprogramming with ML modules in the MirageOS
Designing a Generic Graph Library using ML Functors
1ML unifying the type level and module level in ML
github.com/mirage/mirage
github.com/mirage/ocaml-cohttp
github.com/mirage/irmin
34 / 34

↑, ←, Pg Up, k	Go to previous slide
↓, →, Pg Dn, Space, j	Go to next slide
Home	Go to first slide
End	Go to last slide
b / m / f	Toggle blackout / mirrored / fullscreen mode
c	Clone slideshow
p	Toggle presenter mode
t	Restart the presentation timer
?, h	Toggle this help

Crash Course in OCaml Modules

What to expect?

Outcomes

Terminology

OCaml type declarations

Structures

Calling Structures

Nested Structures

Using Structures

Signatures

Example

Functors

Example I

Example II

Using Functor

Review

Comparison to Type Classes

Type Classes to Signatures

Instances to Structures

Using Type Class

Using Type Class Modules

Verdict

Module Extras

Type Safe Extensions

Paramterising Library

Mirage OS

Mirage OS II

Core Monad.make

Modular Implicits

Work in progress

Records as Modules

Summary

Thanks!

Further Reading

What to expect?

Help