Real World OCaml.

TOC

Part I Language Concepts

Chapter 1 A Guided Tour

1.1 Ocaml As A Calculator
1.2 Functions And Type Inference
1. Type Inference
2. Inferring Generic Types
1.3 Tuples, Lists, Options, Pattern Matching
1. Tuples
2. Lists
3. Options
1.4 Records And Variants
1.5 Imperative Programming
1. Arrays
2. Mutable Record Fields
3. Refs
4. For And While Loops
1.6 A Complete Program
1. Compiling And Running

1.7 Where to Go From Here

Chapter 2 Variables and Functions

2.1 Variables
1. Pattern Matching And Let
2.2 Functions
1. Anonymous Functions
2. Multiargument Functions
3. Recursive Functions
4. Prefix And Infix Operators
5. Declaring Functions with Function
6. Labeled arguments
7. Optional arguments

Chapter 3 Lists And Patterns

3.1 List Basics
3.2 Using Patterns To Extract Data From a List
3.3 Limitations (And Blessings) of Pattern Matching
1. Performance
2. Detecting Errors
3.4 Using the List module Effectively
1. More Useful List Functions
3.5 Tail Recursion
3.6 Terser And Faster Programs

Chapter 4 Files, Modules, Programs

4.1 Single File Programs
4.2 Multifile Programs And Modules
4.3 Signatures And Abstract Types
4.4 Concrete Types in Signatures
4.5 Nested Modules
4.6 Opening Modules
4.7 Common Errors With Modules
1. Type Mismatches
2. Missing Definitions
 3. Type Definition Mismatches
4. Cyclic Dependencies
4.8 Designing With Modules
1. Expose Concrete Types Rarely
2. Design For The Call Site
3. Create Uniform Interfaces
4. Interfaces Before Implementation

Chapter 5 Records
5.1 Patterns And Exhaustiveness
5.2 Field Punning
5.3 Reusing Field Names
5.4 Functional Updates

Chapter 6 Variants
6.1 Catch-all Cases And Refactoring
6.2 Combining Records And Variants
6.3 Variants And Recursive Data Structures
6.4 Polymorphic Variants
1. Example: Terminal Colors Redux
2. When to Use Polymorphic Variants

Chapter 7 Error Handling

7.1 Error Aware Return Types
1. Encoding Errors With Results
2. Error and Or_Error
3. bind and other Error handling idioms
7.2 Exceptions
1. Helper Functions For Throwing Exceptions
2. Exception Handlers
3. Cleaning Up in the Presence Of Exceptions
7.3 Choosing An Error Handling Strategy

Chapter 8 Imperative Programming

8.1 Example: Imperative Dictionaries.
8.2 Primitive Mutable Data
1. Array Like Data
2. Mutable Record And Object Fields and Ref Cells
3. Foreign Functions
8.3 For and While Loop
8.4 Example: Doubly Linked Lists
1. Modifying The Lists
2. Iteration Functions
8.5 Lazyness and other Benign Effects
1. Memoization And Dynamic Programming
8.6 Input and Output
1. Terminal I/O
2. Formatted Output with printf
3. File I/O
8.7 Order Of Evaluation
8.8 Side Effects And Weak Polymorphism
1. The Value Restriction
2. Partial Application And The Value Restriction
3. Relaxing The Value Restriction
8.9 Summary

Chapter 9 Functors
9.1 A Trivial Example
9.2 A Bigger Example: Computing With Intervals
1. Making The Functor Abstract
2. Sharing Constraints
3. Destructive Substitution
4. Using Multiple Interfaces
9.3 Extending Modules

Chapter 10 First Class Modules

10.1 Working With First Class Modules
10.2 Example: A Query Handling Framework
1. Implementing A Query Handler
2. Dispatching to Multiple Query Handlers
3. Loading and unloading Query Handlers
10.3 Living Without First Class Modules

Chapter 11 Objects
11.1 OCaml Obects
11.2 Object Polymorphism
11.3 Immutable Objects
11.4 When To Use Objects
11.5 Subtyping
1. Width Subtyping
2. Depth Subtyping
3. Variance
4. Narrowing
5. Subtyping vs Row Polymorphism

Chapter 12 Classes
12.1 OCaml classes
12.2 Class Parameters And Polymorphism
12.3 Object Types As Interfaces
1. Functional Iterators
12.4 Inheritance
12.5 Class Types
12.6 Open Recursion
12.7 Private Methods
12.8 Binary Methods
12.9 Virtual Classes And Methods
12.10 Initializers
12.11 Multiple Inheritance
1. How Names Are Resolved
2. Mixins
3. Displaying Animated Shapes

Part II Tools And Techniques

Chapter 13 Maps And Hashtables

13.1 Maps
1. Creating Maps With Comparators
2. Trees
3. The Polymorphic Comparator
4. Sets
5. Satisfying the Comparator.S Interface
13.2 Hashtables
1. Satisfying the Hashtable.S Interface
13.3 Choosing between Maps And Hashtables

Chapter 14 Command Line Parsing

Chapter 15 Handling JSON Data

Chapter 16 Parsing With OCamllex And Menhir

Chapter 17 Data Serialization With S-Expressions

Chapter 18 Concurrent Programming With Async

Part III The Runtime System

Chapter 19 Foreign Function Interface

Chapter 20 Memory Representation Of Values

Chapter 21 Understanding The Garbage Collector

Chapter 22 The Compiler Frontend: Parsing And Type Checking

Chapter 23 The Compiler Backend: Bytecode and Native Code

23.1 The Untyped Lambda Form
1. Pattern Matching Optimization
2. Benchmarking Pattern Matching

Notes:

Chapter 1 A Guided Tour

1.1 Ocaml As A Calculator

utop # open Core.Std;;

utop # 3 + 4;;
- : int = 7

Notes: We need to type ;; to tell the toplevel to evaluate an expression. Not

needed in files, though useful to improve error reporting
2. After evaluation, the top level prints the type of the value and then the value

utop # sqrt 9. ;;
- : float = 3.

Notes:
Function arguments are separated by spaces.
Floats and integers are distinct, both in literals ( 9. ) and operators (+.)

Values are bound to variables with let

let x = 3.5;;
utop # let x = 3.5;;
val x : float = 3.5

1.2 Functions And Type Inference

let can be used to define functions.

utop # let square x = x * x;;

val square : int -> int = <fun>
utop # square 3;;
- : int = 9

multi argument functions

utop # let ratio x y = Float.of_int x /. Float.of_int y;;
val ratio : int -> int -> float = <fun>

utop # ratio 2 3;;

- : float = 0.666666666667

Float.of_int is the function of_int in module Float (note beginning must be capital
letter)

Note functions seem to be curried

utop # ratio 3;;

- : int -> float = <fun>

utop # (ratio 3) 2;;

- : float = 1.5

Functions can be parameters too

# let sum_if_true test first second =

(if test first then first else 0)
+ (if test second then second else 0)
;;
val sum_if_true : (int -> bool) -> int -> int -> int = <fun>

# let even x =
x mod 2 = 0 ;;
val even : int -> bool = <fun>
# sum_if_true even 3 4;;
- : int = 4
# sum_if_true even 2 4;;
- : int = 6

Note that (unlike in Haskell) = serves as the equality check operator besides the
binding operator (In Haskell, =, ==)

Note: explicit type annotation for each argument, then for return type just before
= in the function definition

1. Type Inference

Explicit type annotation is done thus

let sum_if_true (test : int -> bool) (x : int) (y : int) : int =

(if test x then x else 0)
+ (if test y then y else 0)
;;
 2. Inferring Generic Types

# let first_if_true test x y =

if test x then x else y
;;
val first_if_true : ('a -> bool) -> 'a -> 'a -> 'a = <fun>

'a is a type variable

1.3 Tuples, Lists, Options, Pattern Matching

1. Tuples

# let a_tuple = (3,"three");;

val a_tuple : int * string = (3, "three")
# let another_tuple = (3,"four",5.);;
val another_tuple : int * string * float = (3, "four", 5.)

Tuple values can be extracted thus

# let (x,y) = a_tuple;;
val x : int = 3
val y : string = "three"

2. Lists
# let languages = ["OCaml";"Perl";"C"];;
val languages : string list = ["OCaml"; "Perl"; "C"]

Note: ; as list separator. , builds tuples

use of labeled functions (in detail in Chapter 2)

# List.map languages ~f:String.length;;
- : int list = [5; 4; 1]

constructing lists with ::

# "French" :: "Spanish" :: languages;;

- : string list = ["French"; "Spanish"; "OCaml"; "Perl"; "C"]

Using 'match' to pattern match on lists

# let my_favorite_language languages =
match languages with
| first :: the_rest -> first
| [] -> "OCaml" (* A good default! *)

Note: comments with (* *) Same format for single line and multiline comments

Recursive List Functions

)
# let rec sum l =
match l with
| [] -> 0 (* base case *)
| hd :: tl -> hd + sum tl (* inductive case *)
;;
val sum : int list -> int = <fun>
# sum [1;2;3];;
- : int = 6
 3. Options
# let divide x y =
if y = 0 then None else Some (x/y) ;;
val divide : int -> int -> int option = <fun>

let .. in example
# let log_entry maybe_time message =
let time =
match maybe_time with
| Some x -> x
| None -> Time.now ()
in
Time.to_sec_string time ^ " -- " ^ message
;;

val log_entry : Time.t option -> string -> string = <fun>

# log_entry (Some Time.epoch) "A long long time ago";;

- : string = "1970-01-01 01:00:00 -- A long long time ago"
# log_entry None "Up to the minute";;
- : string = "2013-08-18 14:48:08 -- Up to the minute

1.4 Records And Variants

Creating new types in OCaml.

A product type, called a 'record'.

# type point2d = { x : float; y : float };; (* Note: Field separator is ; not , *)

type point2d = { x : float; y : float; }

can be accesed (in function argument position, say) by pattern matching

# let magnitude { x = x_pos; y = y_pos } =

sqrt (x_pos ** 2. +. y_pos ** 2.);;
val magnitude : point2d -> float = <fun>

Note the variable on the *right* side of the = is what is used in the function
body. The record parameter names (here x and y) are on the left

Field Punning: When the record field and function parameter names are the same, we
don't have to write them both down.

so
# let magnitude { x ; y } = sqrt (x ** 2. +. y ** 2.);;

Variants

# type circle_desc = { center: point2d; radius: float }

type rect_desc = { lower_left: point2d; width: float; height: float }
type segment_desc = { endpoint1: point2d; endpoint2: point2d } ;;
type circle_desc = { center : point2d; radius : float; }
type rect_desc = { lower_left : point2d; width : float; height : float; }
type segment_desc = { endpoint1 : point2d; endpoint2 : point2d; }

then

# type scene_element =
| Circle of circle_desc
| Rect of rect_desc
| Segment of segment_desc
;;
type scene_element =
Circle of circle_desc
| Rect of rect_desc
| Segment of segment_

then function on variants (actually sum of products)S

let is_inside_scene_element point scene_element =

match scene_element with
| Circle { center; radius } ->
distance center point < radius
| Rect { lower_left; width; height } ->
point.x > lower_left.x && point.x < lower_left.x +. width
&& point.y > lower_left.y && point.y < lower_left.y +. height
| Segment { endpoint1; endpoint2 } -> false
;;
val is_inside_scene_element : point2d -> scene_element -> bool = <fun>

1.5 Imperative Programming

1. Arrays

declaring

# let numbers = [| 1; 2; 3; 4 |];;

val numbers : int array = [|1; 2; 3; 4|]

updating

# numbers.(2) <- 4;;

- : unit = ()

# numbers;;
- : int array = [|1; 2; 4; 4|]

extracting
utop # numbers.(0);;
- : int = 1

2. Mutable Record Fields

Record fields are immutable by default, but can be explicitily declared mutable

type running_sum =
{ mutable sum: float;
mutable sum_sq: float; (* sum of squares *)
mutable samples: int;
}
;;

# let mean rsum = rsum.sum /. float rsum.samples

let stdev rsum =
sqrt (rsum.sum_sq /. float rsum.samples
-. (rsum.sum /. float rsum.samples) ** 2.) ;;
val mean : running_sum -> float = <fun>
val stdev : running_sum -> float = <fun>

Note: .access for record fields

creating and updating

let create () = { sum = 0.; sum_sq = 0.; samples = 0 }
let update rsum x =
rsum.samples <- rsum.samples + 1;
rsum.sum <- rsum.sum +. x;
rsum.sum_sq <- rsum.sum_sq +. x *. x
;;
val create : unit -> running_sum = <fun>
val update : running_sum -> float -> unit = <fun>

Note: use of ; to sequence.

3. Refs

Single mutable values are created by ref. The ref type comes predefined in the
stdlib but there is nothing special about it. It is justa record with one field.

# let x = { contents = 0 };;

val x : int ref = {contents = 0}
# x.contents <- x.contents + 1;;
- : unit = ()
# x;;
- : int ref = {contents = 1}

Some syntax to make creating updating and extracting values (from refs) convenient.

# let x = ref 0 (* create a ref, i.e., { contents = 0 } *) ;;

val x : int ref = {contents = 0}
# !x (* get the contents of a ref, i.e., x.contents *) ;;
- : int = 0
# x := !x + 1 (* assignment, i.e., x.contents <- ... *) ;;
- : unit = ()
# !x ;;
- : int = 1

Note, := is used only with refs

If you want you can completely reimplement this by

# type 'a ref = { mutable contents : 'a }

let ref x = { contents = x }
let (!) r = r.contents
let (:=) r x = r.contents <- x
;;
type 'a ref = { mutable contents : 'a; }
val ref : 'a -> 'a ref = <fun>
val ( ! ) : 'a ref -> 'a = <fun>
val ( := ) : 'a ref -> 'a -> unit = <fun>
 4. For And While Loops

for loop
# let permute array =
let length = Array.length array in
for i = 0 to length - 2 do
(* pick a j to swap with *)
let j = i + Random.int (length - i) in
(* Swap i and j *)
let tmp = array.(i) in
array.(i) <- array.(j);
array.(j) <- tmp
done
;;
val permute : 'a array -> unit = <fun>

# let ar = Array.init 20 ~f:(fun i -> i);;

val ar : int array =
[|0; 1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 13; 14; 15; 16; 17; 18; 19|]
# permute ar;;
- : unit = ()
# ar;;
- : int array =
[|1; 2; 4; 6; 11; 7; 14; 9; 10; 0; 13; 16; 19; 12; 17; 5; 3; 18; 8; 15|]

While Loop

# let find_first_negative_entry array =

let pos = ref 0 in
while !pos < Array.length array && array.(!pos) >= 0 do
pos := !pos + 1
done;
if !pos = Array.length array then None else Some !pos
;;
val find_first_negative_entry : int array -> int option = <fun>
# find_first_negative_entry [|1;2;0;3|];;
- : int option = None
# find_first_negative_entry [|1;-2;0;3|];;
- : int option = Some 1

1.6 A Complete Program

(* in sum.ml *)
open Core.Std
let rec read_and_accumulate accum =
let line = In_channel.input_line In_channel.stdin in
match line with
| None -> accum
| Some x -> read_and_accumulate (accum +. Float.of_string x)
let () =
printf "Total: %F\n" (read_and_accumulate 0.)

1. Compiling And Running

We build with corebuild, a small wrapper on top of ocamlbuild, a build tool that
ships with the ocaml compiler.
corebuild sum.native

1.7 Where to Go From Here

Chapter 2 Variables and Functions
2.1 Variables
At the simplest, a variable is an identifier bound to a particular value.
Variable names must start with a letter or underscore

let var_name = expression;;

let var_name = expression in expression;;

A common idiom is to use nested lets to build up a computation

e.g:

# let area_of_ring inner_radius outer_radius =

let pi = acos (-1.) in
let area_of_circle r = pi *. r *. r in
area_of_circle outer_radius -. area_of_circle inner_radius
;;
val area_of_ring : float -> float -> float = <fun>

# area_of_ring 1. 3.;;
- : float = 25.1327412287

1. Pattern Matching And Let

utop # let (myints, mystrings) = List.unzip [(1,"one");(2,"two");(3,"three")];;

val myints : int list = [1; 2; 3]
val mystrings : string list = ["one"; "two"; "three"]

utop # myints;;
- : int list = [1; 2; 3]

utop # mystrings;;
- : string list = ["one"; "two"; "three"]

essentially pattern matching is used to destructure the result (which is a tuple)

into two named values.

Using a pattern in a let binding makes sense when the pattern is *irrefutable*,
i.e, when *any* value of the type in question is guaranteed to match the pattern.
Tuples and records patterns are irrefutable.

List patterns are not. eg first :: rest doesn't match against []

2.2 Functions

In depth details of functions

1. Anonymous Functions

let f = (fun x y -> x + y);; (* == let f x y = x + y;; *)

List.map ~f:(fun x -> x + 1) [1;2;3]
etc

2. Multiargument Functions
are curried. -> associates to the right

3. Recursive Functions
letrec find_first_stutter ls =
match ls with
| [] | [_] -> None (* zero element or single element lists don't
have repeated elements)
| first :: second :: rest -> if first == second then Some first
else find_first_stutter (second::rest) ;;

Mutually Recursive Functions are created by letrec ... and

letrec is_even x = if x == 0 then true else is_odd (x -1)

and is_odd x = if x == 0 then false else is_even (x -1);;

4. Prefix And Infix Operators

Functions can be used in both prefix and infix style.

2 + 3;;
(+) 2 3 ;;

Functions whose names begin with one of a set of symbols {! $ .. +} are considered
infix.

we can redefine existing functions

utop # let (+) x y = x * y;;

val ( + ) : int -> int -> int = <fun>

utop # 2 + 6 ;;
- : int = 12

be careful to put spaces between braces of any function ( *blah ) to avoid it

being treated as a comment

Note: associativity of operators depends on beginning character! Insane!

5. Declaring Functions with Function

function has built in pattern matching so

let sum_or_zero = function

| Some x -> x
| None -> 0
;;
6. Labeled arguments

Upto now function arguments have been specified *positionally*. They can also be
defined by name , i.e by labels

utop # let ratio ~num ~denom = float num /. float denom;;

val ratio : num:int -> denom:int -> float = <fun>

utop # ratio ~denom:10 ~num:3 ;; (* note 'out of order' arguments)

- : float = 0.3

label punning
 let num = 3 in
let denom = 4 in
ratio ~num ~denom;;
- : float = 0.75

A 'gotcha' with labeled arguments is that

1. order doesn't matter when calling a function with labeled arguments BUT
2. (some weirdness here. Essentially named parameter order can clash with use of
function as parameter to higher order ones)

7. Optional arguments

let concat ?sep x y =

let sep = match sep with None -> "" or Some x -> x in
x ^ sep ^ y ;;

# concat "foo" "bar" (* without the optional argument *);;

- : string = "foobar"
# concat ~sep:":" "foo" "bar" (* with the optional argument *);;
- : string = "foo:bar"

This is a common enough situation that there is some special syntax for this

let concat ?(sep="") x y = x ^ sep ^ y;;

(some weirdness when you want to explicitly pass Some/None as a value for optional
parameter. Elided.
More weirdness about choosing between labels and options etc etc.
Basically don't use these. Just do 'normal' FP as with Haskell.

Chapter 3 Lists

3.1 List Basics

3.2 Using Patterns To Extract Data From a List
3.3 Limitations (And Blessings) of Pattern Matching
1. Performance
2. Detecting Errors
3.4 Using the List module Effectively
1. More Useful List Functions
3.5 Tail Recursion
3.6 Terser And Faster Programs