```kotlin
val mutable1: 'a list
method clear: unit
method fold: ('b -> 'a -> 'b) -> 'b -> 'b
method length: int
method pop: 'a
method push: 'a -> unit
end
```

### 8.2.3 Hashtbl

A simplified version of object-oriented hash tables should have the following class type.

```kotlin
# class type ['a', 'b'] hash_table =
object
    method find: 'a -> 'b
    method add: 'a -> 'b -> unit
end;

class type ['a', 'b'] hash_table =
    object method add: 'a -> 'b -> unit method find: 'a -> 'b end
```

A simple implementation, which is quite reasonable for small hash tables is to use an association list:

```kotlin
# class ['a', 'b'] small_hashtbl : ['a', 'b'] hash_table =
object
    val mutable table = []
    method find key = List.assoc key table
    method add key value = table <- (key, value) :: table
end;

class ['a', 'b'] small_hashtbl : ['a', 'b'] hash_table
```

A better implementation, and one that scales up better, is to use a true hash table... whose elements are small hash tables!

```kotlin
# class ['a', 'b'] hashtbl size: ['a', 'b'] hash_table =
object (self)
    val table = Array.init size (fun i -> new small_hashtbl)
    method private hash key =
        (Hashtbl.hash key) mod (Array.length table)
    method find key = table.(self#hash key) # find key
    method add key = table.(self#hash key) # add key
end;

class ['a', 'b'] hashtbl: int -> ['a', 'b'] hash_table
```

### 8.2.4 Sets

Implementing sets leads to another difficulty. Indeed, the method `union` needs to be able to access the internal representation of another object of the same class.
```kotlin
val mutable1: 'a list
method clear: unit
method fold: ('b -> 'a -> 'b) -> 'b -> 'b
method length: int
method pop: 'a
method push: 'a -> unit
end
```

### 8.2.3 Hashtbl

A simplified version of object-oriented hash tables should have the following class type.

```kotlin
# class type ['a', 'b'] hash_table =
object
    method find: 'a -> 'b
    method add: 'a -> 'b -> unit
end;

class type ['a', 'b'] hash_table =
    object method add: 'a -> 'b -> unit method find: 'a -> 'b end
```

A simple implementation, which is quite reasonable for small hash tables is to use an association list:

```kotlin
# class ['a', 'b'] small_hashtbl : ['a', 'b'] hash_table =
object
    val mutable table = []
    method find key = List.assoc key table
    method add key value = table <- (key, value) :: table
end;

class ['a', 'b'] small_hashtbl : ['a', 'b'] hash_table
```

A better implementation, and one that scales up better, is to use a true hash table... whose elements are small hash tables!

```kotlin
# class ['a', 'b'] hashtbl size: ['a', 'b'] hash_table =
object (self)
    val table = Array.init size (fun i -> new small_hashtbl)
    method private hash key =
        (Hashtbl.hash key) mod (Array.length table)
    method find key = table.(self#hash key) # find key
    method add key = table.(self#hash key) # add key
end;

class ['a', 'b'] hashtbl: int -> ['a', 'b'] hash_table
```

### 8.2.4 Sets

Implementing sets leads to another difficulty. Indeed, the method `union` needs to be able to access the internal representation of another object of the same class.
This is another instance of friend functions as seen in section 3.17. Indeed, this is the same mechanism used in the module `Set` in the absence of objects.

In the object-oriented version of sets, we only need to add an additional method `tag` to return the representation of a set. Since sets are parametric in the type of elements, the method `tag` has a parametric type `'a tag`, concrete within the module definition but abstract in its signature. From outside, it will then be guaranteed that two objects with a method `tag` of the same type will share the same representation.

```python
# module type SET =
sig
type 'a tag
class ['a] c :
    object ('b')
        method is_empty : bool
        method mem : 'a -> bool
        method add : 'a -> 'b
        method union : 'b -> 'b
        method iter : ('a -> unit) -> unit
        method tag : 'a tag
end
end;
```
This is another instance of friend functions as seen in section 3.17. Indeed, this is the same mechanism used in the module `Set` in the absence of objects.

In the object-oriented version of sets, we only need to add an additional method `tag` to return the representation of a set. Since sets are parametric in the type of elements, the method `tag` has a parametric type `'a tag`, concrete within the module definition but abstract in its signature. From outside, it will then be guaranteed that two objects with a method `tag` of the same type will share the same representation.

```python
# module type SET =
sig
type 'a tag
class ['a] c :
    object ('b')
        method is_empty : bool
        method mem : 'a -> bool
        method add : 'a -> 'b
        method union : 'b -> 'b
        method iter : ('a -> unit) -> unit
        method tag : 'a tag
end
end;;

# module Set : SET =
struct
    let rec merge l1 l2 =
        match l1 with
            [] -> l2
        | h1 :: t1 ->
            match l2 with
                [] -> l1
            | h2 :: t2 ->
                if h1 < h2 then h1 :: merge t1 l2
                else if h1 > h2 then h2 :: merge l1 t2
                else merge t1 l2
        type 'a tag = 'a list
class ['a] c =
    object (_ : 'b)
        val repr = ([] : 'a list)
        method is_empty = (repr = [])
        method mem x = List.exists (( = ) x) repr
        method add x = {< repr = merge [x] repr >}
        method union (s : 'b) = {< repr = merge repr s#tag >}
        method iter (f : 'a -> unit) = List.iter f repr
        method tag = repr
end
end;;
```
## 8.3 The subject/observer pattern

The following example, known as the subject/observer pattern, is often presented in the literature as a difficult inheritance problem with inter-connected classes. The general pattern amounts to the definition a pair of two classes that recursively interact with one another.

The class `observer` has a distinguished method `notify` that requires two arguments, a subject and an event to execute an action.

```sfml
# class virtual ['subject, 'event] observer =
object
    method virtual notify : 'subject -> 'event -> unit
end;;

class virtual ['subject, 'event] observer :
    object method virtual notify : 'subject -> 'event -> unit end
```

The class `subject` remembers a list of observers in an instance variable, and has a distinguished method `notify_observers` to broadcast the message `notify` to all observers with a particular event `e`.

```sfml
# class ['observer, 'event] subject =
object (self)
    val mutable observers = ( []: 'observer list)
    method add Observer obs = observers <- (obs :: observers)
    method notify_observers (e : 'event) =
        List.iter (fun x -> x#notify self e) observers
end;;

class ['a, 'event] subject :
    object ('b)
        constraint 'a = < notify : 'b -> 'event -> unit; .. >
        val mutable observers : 'a list
        method addObserver : 'a -> unit
        method notify_observers : 'event -> unit
end
```

The difficulty usually lies in defining instances of the pattern above by inheritance. This can be done in a natural and obvious manner in OCaml, as shown on the following example manipulating windows.

```sfml
# type event = Raise | Resize | Move;;
type event = Raise | Resize | Move

# let string_of_event = function
    Raise -> "Raise" | Resize -> "Resize" | Move -> "Move";;
val string_of_event : event -> string = <fun>

# let count = ref 0;;
val count : int ref = {contents = 0}

# class ['observer] window_subject =
    let id = count := succ !count; !count in
```
## 8.3 The subject/observer pattern

The following example, known as the subject/observer pattern, is often presented in the literature as a difficult inheritance problem with inter-connected classes. The general pattern amounts to the definition a pair of two classes that recursively interact with one another.

The class `observer` has a distinguished method `notify` that requires two arguments, a subject and an event to execute an action.

```sfml
# class virtual ['subject, 'event] observer =
object
    method virtual notify : 'subject -> 'event -> unit
end;;

class virtual ['subject, 'event] observer :
    object method virtual notify : 'subject -> 'event -> unit end
```

The class `subject` remembers a list of observers in an instance variable, and has a distinguished method `notify_observers` to broadcast the message `notify` to all observers with a particular event `e`.

```sfml
# class ['observer, 'event] subject =
object (self)
    val mutable observers = ([]:'observer list)
    method addObserver obs = observers <- (obs :: observers)
    method notify_observers (e : 'event) =
        List.iter (fun x -> x#notify self e) observers
end;;

class ['a, 'event] subject :
    object ('b)
        constraint 'a = < notify : 'b -> 'event -> unit; .. >
        val mutable observers : 'a list
        method addObserver : 'a -> unit
        method notify_observers : 'event -> unit
end
```

The difficulty usually lies in defining instances of the pattern above by inheritance. This can be done in a natural and obvious manner in OCaml, as shown on the following example manipulating windows.

```sfml
# type event = Raise | Resize | Move;;
type event = Raise | Resize | Move

# let string_of_event = function
    Raise -> "Raise" | Resize -> "Resize" | Move -> "Move";;
val string_of_event : event -> string = <fun>

# let count = ref 0;;
val count : int ref = {contents = 0}

# class ['observer] window_subject =
    let id = count := succ !count; !count in
```
object (self)
    inherit ['observer, event] subject
    val mutable position = 0
    method identity = id
    method move x = position <- position + x; self#notifyobservers Move
    method draw =FORMAT printf "{Position = %d}\n" position;
end;

class ['a] window_subject :
    object ('b)
        constraint 'a = <notify : 'b -> event -> unit; .. >
        val mutable observers : 'a list
        val mutable position : int
        method add Observer : 'a -> unit
        method draw : unit
        method identity : int
        method move : int -> unit
        method notifyobservers : event -> unit
end

# class ['subject] window Observer =
    object
        inherit ['subject, event] observer
        method notify s e = s#draw
end;

class ['a] window Observer :
    object
        constraint 'a = <draw : unit; .. >
        method notify : 'a -> event -> unit
end

As can be expected, the type of window is recursive.

# let window = new window_subject;;
val window :
  (< notify : 'a -> event -> unit; .. > as '_weak3') window_subject as 'a =
  <obj>

However, the two classes of window_subject and window Observer are not mutually recursive.

# let windowObserver = new windowObserver;;
val windowObserver : (< draw : unit; .. > as '_weak4') windowObserver =
  <obj>

# window#addObserver windowObserver;;
- : unit = ()

# window#move 1;;
{Position = 1}
- : unit = ()
```kotlin
object (self)
    inherit ['observer, event] subject
    val mutable position = 0
    method identity = id
    method move x = position <- position + x; self#notifyobservers Move
    method draw =FORMAT printf "{Position = %d}\n" position;
end;

class ['a] window_subject :
    object ('b)
        constraint 'a = < notify : 'b -> event -> unit; .. >
        val mutable observers : 'a list
        val mutable position : int
        method addObserver : 'a -> unit
        method draw : unit
        method identity : int
        method move : int -> unit
        method notifyobservers : event -> unit
end

# class ['subject] window Observer =
    object
        inherit ['subject, event] observer
        method notify s e = s#draw
end;

class ['a] windowObserver :
    object
        constraint 'a = < draw : unit; .. >
        method notify : 'a -> event -> unit
end
```

As can be expected, the type of window is recursive.

```kotlin
# let window = new window_subject;;
val window :
    (< notify : 'a -> event -> unit; .. > as '_weak3') window_subject as 'a =
    <obj>
```

However, the two classes of `window_subject` and `windowObserver` are not mutually recursive.

```kotlin
# let windowObserver = new window Observer;;
val windowObserver : (< draw : unit; .. > as '_weak4') windowObserver =
    <obj>

# window#addObserver windowObserver;;
- : unit = ()

# window#move 1;;
{Position = 1}
- : unit = ()
```
Classes `window Observer` and `window_subject` can still be extended by inheritance. For instance, one may enrich the `subject` with new behaviors and refine the behavior of the observer.

```kotlin
# class ['observer'] richer_windows_subject =
object (self)
    inherit ['observer'] window_subject
    val mutable size = 1
    method resize x = size <- size + x; self#notifyobservers Resize
    val mutable top = false
    method raise = top <- true; self#notifyobservers Raise
    method draw = Printf Acid printf "{Position = %d; Size = %d}\n" position size;
end;
```

```kotlin
class ['a'] richer_windows_subject :
object ('b)
    constraint 'a = < notify : 'b -> event -> unit; .. >
    val mutable observers : 'a list
    val mutable position : int
    val mutable size : int
    val mutable top : bool
    method addobserver : 'a -> unit
    method draw : unit
    method identity : int
    method move : int -> unit
    method notifyobservers : event -> unit
    method raise : unit
    method resize : int -> unit
end
```

```kotlin
# class ['subject'] richer_windows observer =
object
    inherit ['subject'] window Observer as super
    method notify s e = if e <> Raise then s#raise; super#notify s e
end;
```

```kotlin
class ['a'] richer_windows observer :
object
    constraint 'a = < draw : unit; raise : unit; .. >
    method notify : 'a -> event -> unit
end
```

We can also create a different kind of observer:

```kotlin
# class ['subject'] traceObserver =
object
    inherit ['subject, event] observer
    method notify s e =
        Printf Acid printf "<Window %d <== %s>\n" s#identity (string_of_event e)
end;
```

```kotlin
class ['a'] traceObserver :
```
Classes `windowObserver` and `window_subject` can still be extended by inheritance. For instance, one may enrich the `subject` with new behaviors and refine the behavior of the observer.

```ksharp
# class ['observer] richer_windows_subject =
    object (self)
        inherit ['observer] window_subject
        val mutable size = 1
        method resize x = size <- size + x; self#notifyobservers Resize
        val mutable top = false
        method raise = top <- true; self#notifyobservers Raise
        method draw = Printfprintf "{Position = %d; Size = %d}\n" position size;
    end;
```

```ksharp
class ['a] richer_windows_subject :
    object ('b)
        constraint 'a = < notify : 'b -> event -> unit; .. >
        val mutable observers : 'a list
        val mutable position : int
        val mutable size : int
        val mutable top : bool
        method add observer : 'a -> unit
        method draw : unit
        method identity : int
        method move : int -> unit
        method notifyobservers : event -> unit
        method raise : unit
        method resize : int -> unit
```

end

```ksharp
# class ['subject] richer_windows observer =
    object
        inherit ['subject] window observer as super
        method notify s e = if e <> Raise then s#raise; super#notify s e
    end;
```

```ksharp
class ['a] richer_windows observer :
    object
        constraint 'a = < draw : unit; raise : unit; .. >
        method notify : 'a -> event -> unit
end
```

We can also create a different kind of observer:

```ksharp
# class ['subject] trace observer =
    object
        inherit ['subject, event] observer
        method notify s e =
            Printfprintf "<Window %d <== %s>\n" s#identity (string_of_event e)
    end;
```

```ksharp
class ['a] trace observer :
```
object
  constraint 'a = < identity : int; .. >'
  method notify : 'a -> event -> unit
end

and attach several observers to the same object:

# let window = new richer_windows_subject;;
val window :
  (< notify : 'a -> event -> unit; .. > as '_weak5') richer_windows_subject
  as 'a = <obj>

# window#addObserver (new richer_windowsObserver);;
- : unit = ()

# window#addObserver (new traceObserver);;
- : unit = ()

# window#move 1; window#resize 2;;
<Window 1 <== Move>
<Window 1 <== Raise>
{Position = 1; Size = 1}
{Position = 1; Size = 1}
<Window 1 <== Resize>
<Window 1 <== Raise>
{Position = 1; Size = 3}
{Position = 1; Size = 3}
- : unit = ()
object
  constraint 'a = < identity : int; .. >
  method notify : 'a -> event -> unit
end

and attach several observers to the same object:

# let window = new richer_windows_subject;;
val window :
  (< notify : 'a -> event -> unit; .. > as '_weak5') richer_windows_subject
  as 'a = <obj>

# window#addObserver (new richer_windowsObserver);;
- : unit = ()

# window#addObserver (new traceObserver);;
- : unit = ()

# window#move 1; window#resize 2;;
<Window 1 <== Move>
<Window 1 <== Raise>
{Position = 1; Size = 1}
{Position = 1; Size = 1}
<Window 1 <== Resize>
<Window 1 <== Raise>
{Position = 1; Size = 3}
{Position = 1; Size = 3}
- : unit = ()
# Chapter 9

## Parallel programming

In this chapter, we shall look at the parallel programming facilities in OCaml. The OCaml standard library exposes low-level primitives for parallel programming. We recommend the users to utilise higher-level parallel programming libraries such as `domainslib`. This tutorial will first cover the high-level parallel programming using `domainslib` followed by low-level primitives exposed by the compiler.

OCaml distinguishes concurrency and parallelism and provides distinct mechanisms for expressing them. Concurrency is overlapped execution of tasks (section 12.24.2) whereas parallelism is simultaneous execution of tasks. In particular, parallel tasks overlap in time but concurrent tasks may or may not overlap in time. Tasks may execute concurrently by yielding control to each other. While concurrency is a program structuring mechanism, parallelism is a mechanism to make your programs run faster. If you are interested in the concurrent programming mechanisms in OCaml, please refer to the section 12.24 on effect handlers and the chapter 33 on the threads library.

### 9.1 Domains

Domains are the units of parallelism in OCaml. The module `Domain[28.14]` provides the primitives to create and manage domains. New domains can be spawned using the `spawn` function.

```ocaml
Domain spawn (fun _ -> print_endline "I ran in parallel")
I ran in parallel
- : unit Domain.t = <abstr>
```

The `spawn` function executes the given computation in parallel with the calling domain.

Domains are heavy-weight entities. Each domain maps 1:1 to an operating system thread. Each domain also has its own runtime state, which includes domain-local structures for allocating memory. Hence, they are relatively expensive to create and tear down.

> It is recommended that the programs do not spawn more domains than cores available.

In this tutorial, we shall be implementing, running and measuring the performance of parallel programs. The results observed are dependent on the number of cores available on the target machine. This tutorial is being written on a 2.3 GHz Quad-Core Intel Core i7 MacBook Pro with 4 cores and 8 hardware threads. It is reasonable to expect roughly 4x performance on 4 domains for parallel programs with little coordination between the domains, and when the machine is not
# Chapter 9

## Parallel programming

In this chapter we look at the parallel programming facilities in OCaml. The OCaml standard library exposes low-level primitives for parallel programming. We recommend that users make use of higher-level parallel programming libraries such as `domainslib`. This tutorial will first cover high-level parallel programming using `domainslib` followed by low-level primitives exposed by the compiler.

OCaml distinguishes between concurrency and parallelism and provides distinct mechanisms for expressing them. Concurrency is interleaved execution of tasks (section 12.24.2) whereas parallelism is simultaneous execution of tasks. In particular, parallel tasks overlap in time but concurrent tasks may or may not overlap in time. Tasks may execute concurrently by yielding control to each other. While concurrency is a program structuring mechanism, parallelism is a mechanism to make your programs run faster. If you are interested in the concurrent programming mechanisms in OCaml, please refer to section 12.24 on effect handlers and chapter 34 on the threads library.

### 9.1 Domains

Domains are the units of parallelism in OCaml. The module `Domain[29.14]` provides the primitives to create and manage domains. New domains can be spawned using the `spawn` function.

```
Domain spawn (fun _ -> print_endline "I ran in parallel")
I ran in parallel
- : unit Domain.t = <abstr>
```

The `spawn` function executes the given computation in parallel with the calling domain.

Domains are heavy-weight entities. Each domain maps 1:1 to an operating system thread. Each domain also has its own runtime state, which includes domain-local structures for allocating memory. Hence, they are relatively expensive to create and tear down.

*It is recommended that programs do not spawn more domains than the number of available cores.*

In this tutorial we will be implementing, running and measuring the performance of parallel programs. The results observed are dependent on the number of cores available on the target machine. This tutorial was written on a 2.3 GHz Quad-Core Intel Core i7 MacBook Pro with 4 cores and 8 hardware threads. It is reasonable to expect roughly 4x performance on 4 domains for parallel programs with little coordination between the domains, and when the machine is not
under load. Beyond 4 domains, the speedup is likely to be less than linear. We shall also use the command-line benchmarking tool `hyperfine` for benchmarking our programs.

### 9.1.1 Joining domains

We shall use the program to compute the nth Fibonacci number using recursion as a running example. The sequential program for computing the nth Fibonacci number is given below.

```
(* fib.ml *)
```

``` Ocaml
let n = try int_of_string Sys.argv.(1) with _ -> 1
```

``` Ocaml
let rec fib n = if n < 2 then 1 else fib (n - 1) + fib (n - 2)
```

``` Ocaml
let main () =
```

``` Ocaml
let r = fib n in
```

``` Ocaml
printf printf "fib(%d) = %d\n%!" n r
```

``` Ocaml
let _ = main ()
```

The program can be compiled and benchmarked as follows.

```
$ ocamlopt -o fib.exe fib.ml
```

```
$ ./fib.exe 42
```

```
fib(42) = 433494437
```

```
$ hyperfine './fib.exe 42' # Benchmarking
```

```
Benchmark 1: ./fib.exe 42
```

```
Time (mean ± sd):   1.193 s ± 0.006 s      [User: 1.186 s, System: 0.003 s]
```

```
Range (min ... max):   1.181 s ... 1.202 s    10 runs
```

We see that it takes around 1.2 seconds to compute the 42nd Fibonacci number.

Spawned domains can be joined using the `join` function to get their results. The `join` function waits for target domain to terminate. The following program computes the nth Fibonacci number twice in parallel.

```
(* fib_twice.ml *)
```

``` Ocaml
let n = int_of_string Sys.argv.(1)
```

``` Ocaml
let rec fib n = if n < 2 then 1 else fib (n - 1) + fib (n - 2)
```

``` Ocaml
let main () =
```

``` Ocaml
let d1 = Domain spawn (fun _ -> fib n) in
```

``` Ocaml
let d2 = Domain spawn (fun _ -> fib n) in
```

``` Ocaml
let r1 = Domain.join d1 in
```

``` Ocaml
printf printf "fib(%d) = %d\n%!" n r1;
```

``` Ocaml
let r2 = Domain.join d2 in
```

``` Ocaml
printf printf "fib(%d) = %d\n%!" n r2
```

``` Ocaml
let _ = main ()
```
under load. Beyond 4 domains, the speedup is likely to be less than linear. We will also use the command-line benchmarking tool `hyperfine` to benchmark our programs.

### 9.1.1 Joining domains

We will write a program to compute the nth Fibonacci number using recursion as a running example. The sequential program for computing the nth Fibonacci number is given below.

```
(* fib.ml *)
```

``` Ocaml
let n = try int_of_string Sys.argv.(1) with _ -> 1
```

``` Ocaml
let rec fib n = if n < 2 then n else fib (n - 1) + fib (n - 2)
```

``` Ocaml
let main () =
```

``` Ocaml
let r = fib n in
```

``` Ocaml
printf printf "fib(%d) = %d\n%!" n r
```

``` Ocaml
let _ = main ()
```

The program can be compiled and benchmarked as follows:

```
$ ocamlopt -o fib.exe fib.ml
```

```
$ ./fib.exe 42
```

```
fib(42) = 267914296
```

```
$ hyperfine './fib.exe 42' # Benchmarking
```

```
Benchmark 1: ./fib.exe 42
```

```
Time (mean ± sd):   1.193 s ± 0.006 s      [User: 1.186 s, System: 0.003 s]
```

```
Range (min ... max):  1.181 s ... 1.202 s      10 runs
```

We see that it takes around 1.2 seconds to compute the 42nd Fibonacci number.

Spawned domains can be joined using the `join` function to get their results. The `join` function waits for target domain to terminate. The following program computes the nth Fibonacci number twice in parallel.

```
(* fib_twice.ml *)
```

``` Ocaml
let n = int_of_string Sys.argv.(1)
```

``` Ocaml
let rec fib n = if n < 2 then n else fib (n - 1) + fib (n - 2)
```

``` Ocaml
let main () =
```

``` Ocaml
let d1 = Domain spawn (fun _ -> fib n) in
```

``` Ocaml
let d2 = Domain spawn (fun _ -> fib n) in
```

``` Ocaml
let r1 = Domain.join d1 in
```

``` Ocaml
printf printf "fib(%d) = %d\n%!" n r1;
```

``` Ocaml
let r2 = Domain.join d2 in
```

``` Ocaml
printf printf "fib(%d) = %d\n%!" n r2
```

``` Ocaml
let _ = main ()
```
The program spawns two domains which compute the nth Fibonacci number. The spawn function returns a Domain.t value which can be joined to get the result of the parallel computation. The join function blocks until the computation runs to completion.

```
$ ocamlopt -o fib_twice.exe fib_twice.ml
$ ./fib_twice.exe 42
fib(42) = 433494437
fib(42) = 433494437
$ hyperfine './fib_twice.exe 42'
Benchmark 1: ./fib_twice.exe 42
Time (mean ± sd):   1.249 s ±  0.025 s   [User: 2.451 s, System: 0.012 s]
Range (min ... max):   1.221 s ...   1.290 s   10 runs
```

As one can see that computing the nth Fibonacci number twice almost took the same time as computing it once thanks to parallelism.

## 9.2 Domainslib: A library for nested-parallel programming

Let us attempt to parallelise the Fibonacci function. The two recursive calls may be executed in parallel. However, naively parallelising the recursive calls by spawning domains for each one will not work as it spawns too many domains.

```
(* fib_par1.ml *)
let n = try int_of_string Sys.argv.(1) with _ -> 1
```

```
let rec fib n =
    if n < 2 then 1 else begin
        let d1 = Domain spawn (fun _ -> fib (n - 1)) in
        let d2 = Domain spawn (fun _ -> fib (n - 2)) in
        Domain.join d1 + Domain.join d2
    end
```

```
let main () =
    let r = fib n in
    Printfprintf "fib(%d) = %d\n%!" n r
```

```
let _ = main ()
fib(1) = 1
val n : int = 1
val fib : int -> int = <fun>
val main : unit -> unit = <fun>
```

```
$ ocamlopt -o fib_par1.exe fib_par1.ml
$ ./fib_par1.exe 42
Fatal error: exception Failure("failed to allocate domain")
```

OCaml has a limit of 128 domains that can be active at the same time. An attempt to spawn more domains will raise an exception. How then can we parallelise the Fibonacci function?
The program spawns two domains which compute the *n*th Fibonacci number. The **spawn** function returns a **Domain.t** value which can be joined to get the result of the parallel computation. The **join** function blocks until the computation runs to completion.

```bash
$ ocamlopt -o fib_twice.exe fib_twice.ml
$ ./fib_twice.exe 42
fib(42) = 267914296
fib(42) = 267914296
$ hyperfine './fib_twice.exe 42'
Benchmark 1: ./fib_twice.exe 42
Time (mean ± sd):   1.249 s ±  0.025 s   [User: 2.451 s, System: 0.012 s]
Range (min ... max):  1.221 s ...  1.290 s   10 runs
```

As one can see, computing the *n*th Fibonacci number twice takes almost the same time as computing it once, thanks to parallelism.

## 9.2 Domainslib: A library for nested-parallel programming

Let us attempt to parallelise the Fibonacci function. The two recursive calls may be executed in parallel. However, naively parallelising the recursive calls by spawning domains for each one will not work as it spawns too many domains.

```
(* fib_par1.ml *)
let n = try int_of_string Sys.argv.(1) with _ -> 1

let rec fib n =
    if n < 2 then n else begin
        let d1 = Domain spawn (fun _ -> fib (n - 1)) in
        let d2 = Domain spawn (fun _ -> fib (n - 2)) in
        Domain.join d1 + Domain.join d2
    end

let main () =
    let r = fib n in
    printf printf "fib(%d) = %d\n%!" n r

let _ = main ()

fib(1) = 1
val n : int = 1
val fib : int -> int = <fun>
val main : unit -> unit = <fun>

$ ocamlopt -o fib_par1.exe fib_par1.ml
$ ./fib_par1.exe 42
Fatal error: exception Failure("failed to allocate domain")
```

OCaml has a limit of 128 domains that can be active at the same time. An attempt to spawn more domains will raise an exception. How then can we parallelise the Fibonacci function?
9.2.1 Parallelising Fibonacci using domainslib

The OCaml standard library provides only low-level primitives for concurrent and parallel pro-
gramming, leaving high-level programming libraries to be developed and distributed outside the
core compiler distribution. `Domainslib` is such a library for nested-parallel programming, which
is epitomised by the parallelism available in the recursive Fibonacci computation. Let us use
domainslib to parallelise the recursive Fibonacci program. It is recommended that you install
domainslib using the `opam` package manager. This tutorial uses domainslib version 0.5.0.

Domainslib provides an async/await mechanism for spawning parallel tasks and awaiting their
results. On top of this mechanism, domainslib provides parallel iterators. At its core, domainslib
has an efficient implementation of work-stealing queue in order to efficiently share tasks with other
domains. A parallel implementation of the Fibonacci program is given below.

(* fib_par2.ml *)
let num_domain = int_of_string Sys.argv.(1)
let n = int_of_string Sys.argv.(2)

let rec fib n = if n < 2 then 1 else fib (n - 1) + fib (n - 2)

module T = Domainslib.Task

let rec fib_par pool n =
  if n > 20 then begin
    let a = T async pool (fun _ -> fib_par pool (n-1)) in
    let b = T async pool (fun _ -> fib_par pool (n-2)) in
    T await pool a + T await pool b
  else fib n

let main () =
  let pool = T.setup_pool ~num_domain:(num_domain - 1) () in
  let res = T.run pool (fun _ -> fib_par pool n) in
  T.teahrung_pool pool;
  Printf printf "fib(%d) = %d\n" n res

let _ = main ()

The program takes the number of domains and the input to the Fibonacci function as the first
and the second command-line arguments respectively.

Let us start with the main function. First, we set up a pool of domains on which the nested
parallel tasks will run. The domain invoking the run function will also participate in executing the
tasks submitted to the pool. We invoke the parallel Fibonacci function fib_par in the run function.
Finally, we tear down the pool and print the result.

For sufficiently large inputs (n > 20), the `fib_par` function spawns the left and the right
recursive calls asynchronously in the pool using the `async` function. The `async` function returns
a promise for the result. The result of an asynchronous computation is obtained by awaiting the
promise using the `await` function. The `await` function call blocks until the promise is resolved.
### 9.2.1 Parallelising Fibonacci using domainslib

The OCaml standard library provides only low-level primitives for concurrent and parallel programming, leaving high-level programming libraries to be developed and distributed outside the core compiler distribution. `Domainslib` is such a library for nested-parallel programming, which is epitomised by the parallelism available in the recursive Fibonacci computation. Let us use `domainslib` to parallelise the recursive Fibonacci program. It is recommended that you install `domainslib` using the `opam` package manager. This tutorial uses `domainslib` version 0.5.0.

`Domainslib` provides an `async/await` mechanism for spawning parallel tasks and awaiting their results. On top of this mechanism, `domainslib` provides parallel iterators. At its core, `domainslib` has an efficient implementation of `work-stealing queues` in order to efficiently share tasks with other domains. A parallel implementation of the Fibonacci program follows:

```ocaml
(* fib_par2.ml *)
let num_domain = int_of_string Sys.argv.(1)
let n = int_of_string Sys.argv.(2)

let rec fib n = if n < 2 then n else fib (n - 1) + fib (n - 2)

module T = Domainslib.Task

let rec fib_par pool n =
  if n > 20 then begin
    let a = T async pool (fun _ -> fib_par pool (n-1)) in
    let b = T async pool (fun _ -> fib_par pool (n-2)) in
    T await pool a + T await pool b
  else fib n

let main () =
  let pool = T.setup_pool ~num_domain:(num_domain - 1) () in
  let res = T.run pool (fun _ -> fib_par pool n) in
  T.teahrung_pool pool;
  Printfprintf "fib(%d) = %d\n" n res

let _ = main ()
```

The program takes the number of domains and the input to the Fibonacci function as the first and the second command-line arguments respectively.

Let us start with the main function. First, we set up a pool of domains on which the nested parallel tasks will run. The domain invoking the `run` function will also participate in executing the tasks submitted to the pool. We invoke the parallel Fibonacci function `fib_par` in the `run` function. Finally, we tear down the pool and print the result.

For sufficiently large inputs (n > 20), the `fib_par` function spawns the left and the right recursive calls asynchronously in the pool using the `async` function. The `async` function returns a promise for the result. The result of an asynchronous computation is obtained by awaiting the promise using the `await` function. The `await` function call blocks until the promise is resolved.
For small inputs, the `fib_par` function simply calls the sequential Fibonacci function `fib`. It is important to switch to sequential mode for small problem sizes. If not, the cost of parallelisation will outweigh the work available.

For simplicity, we use `ocamlfind` to compile this program. It is recommended that the users use `dune` to build their programs that utilise libraries installed through `opam`.

```
$ ocamlfind ocamlopt -package domainslib -linkpkg -o fib_par2.exe fib_par2.ml
```

```
$ ./fib_par2.exe 1 42
```

```
fib(42) = 433494437
```

```
$ hyperfine './fib.exe 42' './fib_par2.exe 2 42' \
./fib_par2.exe 4 42' './fib_par2.exe 8 42'
```

Benchmark 1: ./fib.exe 42

Time (mean ± sd): 1.217 s ± 0.018 s [User: 1.203 s, System: 0.004 s]

Range (min ... max): 1.202 s ... 1.261 s 10 runs

Benchmark 2: ./fib_par2.exe 2 42

Time (mean ± sd): 628.2 ms ± 2.9 ms [User: 1243.1 ms, System: 4.9 ms]

Range (min ... max): 625.7 ms ... 634.5 ms 10 runs

Benchmark 3: ./fib_par2.exe 4 42

Time (mean ± sd): 337.6 ms ± 23.4 ms [User: 1321.8 ms, System: 8.4 ms]

Range (min ... max): 318.5 ms ... 377.6 ms 10 runs

Benchmark 4: ./fib_par2.exe 8 42

Time (mean ± sd): 250.0 ms ± 9.4 ms [User: 1877.1 ms, System: 12.6 ms]

Range (min ... max): 242.5 ms ... 277.3 ms 11 runs

Summary

```
./fib_par2.exe 8 42' ran
```

```
1.35 ± 0.11 times faster than './fib_par2.exe 4 42'
```

```
2.51 ± 0.10 times faster than './fib_par2.exe 2 42'
```

```
4.87 ± 0.20 times faster than './fib.exe 42'
```

The results show that, with 8 domains, the parallel Fibonacci program runs 4.87 times faster than the sequential version.

### 9.2.2 Parallel iteration constructs

Many numerical algorithms use for-loops. The parallel-for primitive provides a straight-forward way to parallelise such code. Let us take the `spectral-norm` benchmark from the computer language benchmarks game and parallelise it. The sequential version of the program is given below.

```
(* spectralnorm.ml *)
```

```
let n = try int_of_string Sys.argv.(1) with _ -> 32
```

```
let eval_A i j = 1. ./ float((i+j)*(i+j+1)/2+i+1)
```
For small inputs, the `fib_par` function simply calls the sequential Fibonacci function `fib`. It is important to switch to sequential mode for small problem sizes. If not, the cost of parallelisation will outweigh the work available.

For simplicity, we use `ocamlfind` to compile this program. In general, it is recommended that users use `dune` to build programs that use libraries installed through `opam`.

$ ocamlfind ocamlopt -package domainslib -linkpkg -o fib_par2.exe fib_par2.ml

$ ./fib_par2.exe 1 42

fib(42) = 267914296

$ hyperfine './fib.exe 42' './fib_par2.exe 2 42' \
'./fib_par2.exe 4 42' './fib_par2.exe 8 42'

Benchmark 1: ./fib.exe 42

Time (mean ± sd): 1.217 s ± 0.018 s [User: 1.203 s, System: 0.004 s]

Range (min ... max): 1.202 s ... 1.261 s 10 runs

Benchmark 2: ./fib_par2.exe 2 42

Time (mean ± sd): 628.2 ms ± 2.9 ms [User: 1243.1 ms, System: 4.9 ms]

Range (min ... max): 625.7 ms ... 634.5 ms 10 runs

Benchmark 3: ./fib_par2.exe 4 42

Time (mean ± sd): 337.6 ms ± 23.4 ms [User: 1321.8 ms, System: 8.4 ms]

Range (min ... max): 318.5 ms ... 377.6 ms 10 runs

Benchmark 4: ./fib_par2.exe 8 42

Time (mean ± sd): 250.0 ms ± 9.4 ms [User: 1877.1 ms, System: 12.6 ms]

Range (min ... max): 242.5 ms ... 277.3 ms 11 runs

Summary

./fib_par2.exe 8 42' ran

1.35 ± 0.11 times faster than './fib_par2.exe 4 42'

2.51 ± 0.10 times faster than './fib_par2.exe 2 42'

4.87 ± 0.20 times faster than './fib.exe 42'

The results show that, with 8 domains, the parallel Fibonacci program runs 4.87 times faster than the sequential version.

### 9.2.2 Parallel iteration constructs

Many numerical algorithms use for-loops. The parallel-for primitive provides a straight-forward way to parallelise such code. Let us take the `spectral-norm` benchmark from the computer language benchmarks game and parallelise it. The sequential version of the program is given below.

(* spectralnorm.ml *)

let n = try int_of_string Sys.argv.(1) with _ -> 32

let eval_A i j = 1. ./ float((i+j)*(i+j+1)/2+i+1)
```h
let eval_A_times_u u v =
  let n = Array.length v - 1 in
  for i = 0 to n do
    let vi = ref 0. in
    for j = 0 to n do vi := !vi +. eval_A i j *. u.(j) done;
    v.(i) <- !vi
  done
```

```h
let eval_At_times_u u v =
  let n = Array.length v - 1 in
  for i = 0 to n do
    let vi = ref 0. in
    for j = 0 to n do vi := !vi +. eval_A j i *. u.(j) done;
    v.(i) <- !vi
  done
```

```h
let eval_AtA_times_u u v =
  let w = Array.make (Array.length u) 0.0 in
  eval_A_times_u u w; eval_At_times_u w v
```

```h
let () =
  let u = Array.make n 1.0 and v = Array.make n 0.0 in
  for _i = 0 to 9 do
    eval_AtA_times_u u v; eval_AtA_times_u v u
  done;
```

```h
let vv = ref 0.0 and vBv = ref 0.0 in
for i=0 to n-1 do
  vv := !vv +. v.(i) *. v.(i);
  vBv := !vBv +. u.(i) *. v.(i)
done;
```

```h
printf printf "%0.9f\n" (sqrt(!vBv / !vv))
```

Observe that the program has nested loops in `eval_A_times_u` and `eval_At_times_u`. Each iteration of the outer loop body reads from `u` but writes to disjoint memory locations in `v`. Hence, the iterations of the outer loop are not dependent on each other and can be executed in parallel.

The parallel version of spectral norm is shown below.

```c
(* spectralnorm_par.ml *)
let num.COates = try int_of_string Sys.argv.(1) with _ -> 1
let n = try int_of_string Sys.argv.(2) with _ -> 32

let eval_A i j = 1. ./ float((i+j)*(i+j+1)/2+i+1)

module T = Domainslib.Task
```
```h
let eval_A_times_u u v =
  let n = Array.length v - 1 in
  for i = 0 to n do
    let vi = ref 0. in
    for j = 0 to n do vi := !vi +. eval_A i j *. u.(j) done;
    v.(i) <- !vi
  done
```

```h
let eval_At_times_u u v =
  let n = Array.length v - 1 in
  for i = 0 to n do
    let vi = ref 0. in
    for j = 0 to n do vi := !vi +. eval_A j i *. u.(j) done;
    v.(i) <- !vi
  done
```

```h
let eval_AtA_times_u u v =
  let w = Array.make (Array.length u) 0.0 in
  eval_A_times_u u w; eval_At_times_u w v
```

```h
let () =
  let u = Array.make n 1.0 and v = Array.make n 0.0 in
  for _i = 0 to 9 do
    eval_AtA_times_u u v; eval_AtA_times_u v u
  done;

let vv = ref 0.0 and vBv = ref 0.0 in
  for i=0 to n-1 do
    vv := !vv +. v.(i) *. v.(i);
    vBv := !vBv +. u.(i) *. v.(i)
  done;
printf printf "%0.9f\n" (sqrt(!vBv / . !vv))
```

Observe that the program has nested loops in `eval_A_times_u` and `eval_At_times_u`. Each iteration of the outer loop body reads from `u` but writes to disjoint memory locations in `v`. Hence, the iterations of the outer loop are not dependent on each other and can be executed in parallel.

The parallel version of spectral norm is shown below.

```h
(* spectralnorm_par.ml *)
let num_domain = try int_of_string Sys.argv.(1) with _ -> 1
let n = try int_of_string Sys.argv.(2) with _ -> 32

let eval_A i j = 1. ./ float((i+j)*(i+j+1)/2+i+1)

module T = Domainslib.Task
```
```h
let eval_A_times_u pool u v =
  let n = Array.length v - 1 in
  T.parallel_for pool ~start:0 ~finish:n ~body:(fun i ->
    let vi = ref 0. in
    for j = 0 to n do vi := !vi +. eval_A i j *. u.(j) done;
    v.(i) <- !vi
  )
```

```h
let eval_At_times_u pool u v =
  let n = Array.length v - 1 in
  T.parallel_for pool ~start:0 ~finish:n ~body:(fun i ->
    let vi = ref 0. in
    for j = 0 to n do vi := !vi +. eval_A j i *. u.(j) done;
    v.(i) <- !vi
  )
```

```h
let eval_AtA_times_u pool u v =
  let w = Array.make (Array.length u) 0.0 in
  eval_A_times_u pool u w; eval_At_times_u pool w v
```

```h
let () =
  let pool = T.setup_pool ~num_domain:(num_domain - 1) () in
  let u = Array.make n 1.0 and v = Array.make n 0.0 in
  T.run pool (fun _ ->
    for _i = 0 to 9 do
      eval_AtA_times_u pool u v; eval_AtA_times_u pool v u
    done);
```

```h
let vv = ref 0.0 and vBv = ref 0.0 in
for i=0 to n-1 do
  vv := !vv +. v.(i) *. v.(i);
  vBv := !vBv +. u.(i) *. v.(i)
done;
T.teardown_pool pool;
printf printf "%0.9f\n" (sqrt(!vBv / . !vv))
```

Observe that the `parallel_for` function is isomorphic to the for-loop in the sequential version. No other change is required except for the boiler plate code to set up and tear down the pools.

```bash
$ ocamopt -o spectralnorm.exe spectralnorm.ml
$ ocamlfind ocamopt -package domainslib -linkpkg -o spectralnorm_par.exe \ spectralnorm_par.ml
$ hyperfine './spectralnorm.exe 4096' './spectralnorm_par.exe 2 4096' \ ./spectralnorm_par.exe 4 4096' './spectralnorm_par.exe 8 4096'
Benchmark 1: ./spectralnorm.exe 4096
```
let eval_A_times_u pool u v =
let n = Array.length v - 1 in
T.parallel_for pool ~start:0 ~finish:n ~body:(fun i ->
let vi = ref 0. in
for j = 0 to n do vi := !vi +. eval_A i j *. u.(j) done;
v.(i) <- !vi
)

let eval_At_times_u pool u v =
let n = Array.length v - 1 in
T.parallel_for pool ~start:0 ~finish:n ~body:(fun i ->
let vi = ref 0. in
for j = 0 to n do vi := !vi +. eval_A j i *. u.(j) done;
v.(i) <- !vi
)

let eval_AtA_times_u pool u v =
let w = Array.make (Array.length u) 0.0 in
eval_A_times_u pool u w; eval_At_times_u pool w v

let () =
let pool = T.setup_pool ~num_domain:(num_domain - 1) () in
let u = Array.make n 1.0 and v = Array.make n 0.0 in
T.run pool (fun _ ->
for _i = 0 to 9 do
  eval_AtA_times_u pool u v; eval_AtA_times_u pool v u
done);

let vv = ref 0.0 and vBv = ref 0.0 in
for i=0 to n-1 do
  vv := !vv +. v.(i) *. v.(i);
  vBv := !vBv +. u.(i) *. v.(i)
done;
T.teahrung_pool pool;
printf printf "%0.9f\n" (sqrt(!vBv / . !vv))

Observe that the `parallel_for` function is isomorphic to the for-loop in the sequential version. No other change is required except for the boilerplate code to set up and tear down the pools.

```bash
$ ocamopt -o spectralnorm.exe spectralnorm.ml
$ ocamlfind ocamopt -package domainslib -linkpkg -o spectralnorm_par.exe \ spectralnorm_par.ml
$ hyperfine './spectralnorm.exe 4096' './spectralnorm_par.exe 2 4096' \ ./spectralnorm_par.exe 4 4096' './spectralnorm_par.exe 8 4096'
Benchmark 1: ./spectralnorm.exe 4096
```
Time (mean ± sd): 1.989 s ± 0.013 s [User: 1.972 s, System: 0.007 s]
Range (min ... max): 1.975 s ... 2.018 s 10 runs

Benchmark 2: ./spectralnorm_par.exe 2 4096

Time (mean ± sd): 1.083 s ± 0.015 s [User: 2.140 s, System: 0.009 s]
Range (min ... max): 1.064 s ... 1.102 s 10 runs

Benchmark 3: ./spectralnorm_par.exe 4 4096

Time (mean ± sd): 698.7 ms ± 10.3 ms [User: 2730.8 ms, System: 18.3 ms]
Range (min ... max): 680.9 ms ... 721.7 ms 10 runs

Benchmark 4: ./spectralnorm_par.exe 8 4096

Time (mean ± sd): 921.8 ms ± 52.1 ms [User: 6711.6 ms, System: 51.0 ms]
Range (min ... max): 838.6 ms ... 989.2 ms 10 runs

Summary

./spectralnorm_par.exe 4 4096' ran
1.32 ± 0.08 times faster than './spectralnorm_par.exe 8 4096'
1.55 ± 0.03 times faster than './spectralnorm_par.exe 2 4096'
2.85 ± 0.05 times faster than './spectralnorm.exe 4096'

On the author's machine, the program scales reasonably well up to 4 domains but performs worse with 8 domains. Recall that the machine only has 4 physical cores. Debugging and fixing this performance issue is beyond the scope of this tutorial.

## 9.3 Parallel garbage collection

An important aspect of the scalability of parallel OCaml programs is the scalability of the garbage collector (GC). The OCaml GC is designed to have both low latency and good parallel scalability. OCaml has a generational garbage collector with a small minor heap and a large major heap. New objects (upto a certain size) are allocated in the minor heap. Each domain has its own domain-local minor heap arena into which new objects are allocated without synchronising with the other domains. When a domain exhausts its minor heap arena, it calls for a stop-the-world collection of the minor heaps. In the stop-the-world section, all the domains collect their minor heap arenas in parallel evacuating the survivors to the major heap.

For the major heap, each domain maintains domain-local, size-segmented pools of memory into which large objects and survivors from the minor collection are allocated. Having domain-local pools avoids synchronisation for most major heap allocations. The major heap is collected by a concurrent mark-and-sweep algorithm that involves a few short stop-the-world pauses for each major cycle.

Overall, the users should expect the garbage collector to scale well with increasing number of domains, with the latency remaining low. For more information on the design and evaluation of the garbage collector, please have a look at the ICFP 2020 paper on *Retrofitting Parallelism onto OCaml*.
Time (mean ± sd): 1.989 s ± 0.013 s [User: 1.972 s, System: 0.007 s]
Range (min ... max): 1.975 s ... 2.018 s 10 runs

Benchmark 2: ./spectralnorm_par.exe 2 4096
Time (mean ± sd): 1.083 s ± 0.015 s [User: 2.140 s, System: 0.009 s]
Range (min ... max): 1.064 s ... 1.102 s 10 runs

Benchmark 3: ./spectralnorm_par.exe 4 4096
Time (mean ± sd): 698.7 ms ± 10.3 ms [User: 2730.8 ms, System: 18.3 ms]
Range (min ... max): 680.9 ms ... 721.7 ms 10 runs

Benchmark 4: ./spectralnorm_par.exe 8 4096
Time (mean ± sd): 921.8 ms ± 52.1 ms [User: 6711.6 ms, System: 51.0 ms]
Range (min ... max): 838.6 ms ... 989.2 ms 10 runs

Summary

'./spectralnorm_par.exe 4 4096' ran
1.32 ± 0.08 times faster than './spectralnorm_par.exe 8 4096'
1.55 ± 0.03 times faster than './spectralnorm_par.exe 2 4096'
2.85 ± 0.05 times faster than './spectralnorm.exe 4096'

On the author's machine, the program scales reasonably well up to 4 domains but performs worse with 8 domains. Recall that the machine only has 4 physical cores. Debugging and fixing this performance issue is beyond the scope of this tutorial.

## 9.3 Parallel garbage collection

An important aspect of the scalability of parallel OCaml programs is the scalability of the garbage collector (GC). The OCaml GC is designed to have both low latency and good parallel scalability. OCaml has a generational garbage collector with a small minor heap and a large major heap. New objects (upto a certain size) are allocated in the minor heap. Each domain has its own domain-local minor heap arena into which new objects are allocated without synchronising with the other domains. When a domain exhausts its minor heap arena, it calls for a stop-the-world collection of the minor heaps. In the stop-the-world section, all the domains collect their minor heap arenas in parallel evacuating the survivors to the major heap.

For the major heap, each domain maintains domain-local, size-segmented pools of memory into which large objects and survivors from the minor collection are allocated. Having domain-local pools avoids synchronisation for most major heap allocations. The major heap is collected by a concurrent mark-and-sweep algorithm that involves a few short stop-the-world pauses for each major cycle.

Overall, users should expect the garbage collector to scale well with as the number of domains increases, with latency remaining low. For more information on the design and evaluation of the garbage collector, please have a look at the ICFP 2020 paper on *Retrofitting Parallelism onto OCaml*.
## 9.4 Memory model: The easy bits

Modern processors and compilers aggressively optimise programs. These optimisations accelerate without otherwise affecting sequential programs, but cause surprising behaviours to be visible in parallel programs. To benefit from these optimisations, OCaml adopts a *relaxed memory model* that precisely specifies which of these *relaxed behaviours* programs may observe. While these models are difficult to program against directly, the OCaml memory model provides recipes that retain the simplicity of sequential reasoning.

Firstly, immutable values may be freely shared between multiple domains and may be accessed in parallel. For mutable data structures such as reference cells, arrays and mutable record fields, programmers should avoid *data races*. Reference cells, arrays and mutable record fields are said to be *non-atomic* data structures. A data race is said to occur when two domains concurrently access a non-atomic memory location without *synchronisation* and at least one of the accesses is a write. OCaml provides a number of ways to introduce synchronisation including atomic variables (section 9.7) and mutexes (section 9.5).

Importantly, for data race free (DRF) programs, OCaml provides sequentially consistent (SC) semantics – the observed behaviour of such programs can be explained by the interleaving of operations from different domains. This property is known as DRF-SC guarantee. Moreover, in OCaml, DRF-SC guarantee is modular – if a part of a program is data race free, then the OCaml memory model ensures that those parts have sequential consistency despite other parts of the program having data races. Even for programs with data races, OCaml provides strong guarantees. While the user may observe non sequentially consistent behaviours, there are no crashes.

For more details on the relaxed behaviours in the presence of data races, please have a look at the chapter on the hard bits of the memory model (chapter 10).

## 9.5 Blocking synchronisation

Domains may perform blocking synchronisation with the help of Mutex[28.36], Condition[28.13] and Semaphore[28.50] modules. These modules are the same as those used to synchronise threads created by the threads library (chapter 33). For clarity, in the rest of this chapter, we shall call the threads created by the threads library as *systhreads*. The following program implements a concurrent stack using mutex and condition variables.

``` OCaml
module Blocking_stack : sig
    type 'a t
    val make : unit -> 'a t
    val push : 'a t -> 'a -> unit
    val pop : 'a t -> 'a
end = struct
    type 'a t = {
        mutable contents: 'a list;
        mutex : Mutex.t;
        nonempty : Condition.t
    }
}
```
## 9.4 Memory model: The easy bits

Modern processors and compilers aggressively optimise programs. These optimisations accelerate without otherwise affecting sequential programs, but cause surprising behaviours to be visible in parallel programs. To benefit from these optimisations, OCaml adopts a *relaxed memory model* that precisely specifies which of these *relaxed behaviours* programs may observe. While these models are difficult to program against directly, the OCaml memory model provides recipes that retain the simplicity of sequential reasoning.

Firstly, immutable values may be freely shared between multiple domains and may be accessed in parallel. For mutable data structures such as reference cells, arrays and mutable record fields, programmers should avoid *data races*. Reference cells, arrays and mutable record fields are said to be *non-atomic* data structures. A data race is said to occur when two domains concurrently access a non-atomic memory location without *synchronisation* and at least one of the accesses is a write. OCaml provides a number of ways to introduce synchronisation including atomic variables (section 9.7) and mutexes (section 9.5).

Importantly, for data race free (DRF) programs, OCaml provides sequentially consistent (SC) semantics – the observed behaviour of such programs can be explained by the interleaving of operations from different domains. This property is known as the DRF-SC guarantee. Moreover, in OCaml, the DRF-SC guarantee is modular – if a part of a program is data race free, then the OCaml memory model ensures that those parts have sequential consistency despite other parts of the program having data races. Even for programs with data races, OCaml provides strong guarantees. While the user may observe non-sequentially consistent behaviours, there are no crashes.

For more details on the relaxed behaviours in the presence of data races, please have a look at the chapter on the hard bits of the memory model (chapter 10).

## 9.5 Blocking synchronisation

Domains may perform blocking synchronisation with the help of Mutex[29.38], Condition[29.13] and Semaphore[29.55] modules. These modules are the same as those used to synchronise threads created by the threads library (chapter 34). For clarity, in the rest of this chapter, we refer to the threads created by the threads library as *systhreads*. The following program implements a concurrent stack using mutex and condition variables.

``` OCaml
module Blocking_stack : sig
    type 'a t
    val make : unit -> 'a t
    val push : 'a t -> 'a -> unit
    val pop : 'a t -> 'a
end = struct
    type 'a t = {
        mutable contents: 'a list;
        mutex : Mutex.t;
        nonempty : Condition.t
    }
}
```
```javascript
let make () = {
    contents = [];
    mutex = Mutex.create ();
    nonempty = Condition.create ()
}
```

```javascript
let push r v =
    Mutex.lock r.mutex;
    r contents <- v::r contents;
    Condition.signal r.nonempty;
    Mutex unlock r.mutex
```

```javascript
let pop r =
    Mutex.lock r.mutex;
    let rec loop () =
        match r contents with
        | [] ->
            Condition.wait r.nonempty r.mutex;
        loop ()
        | x::xs -> r contents <- xs; x
    in
    let res = loop () in
    Mutex unlock r.mutex;
    res
```

end

The concurrent stack is implemented using a record with three fields: a mutable field `contents` which stores the elements in the stack, a `mutex` to control access to the `contents` field, and a condition variable `nonempty`, which is used to signal blocked domains waiting for the stack to become non-empty.

The `push` operation locks the mutex, updates the `contents` field with a new list whose head is the element being pushed and the tail is the old list. The condition variable `nonempty` is signalled while the lock is held in order to wake up any domains waiting on this condition. If there are waiting domains, one of the domains is woken up. If there are none, then the `signal` operation has no effect.

The `pop` operation locks the mutex and checks whether the stack is empty. If so, the calling domain waits on the condition variable `nonempty` using the `wait` primitive. The `wait` call atomically suspends the execution of the current domain and unlocks the `mutex`. When this domain is woken up again (when the `wait` call returns), it holds the lock on `mutex`. The domain tries to read the contents of the stack again. If the `pop` operation sees that the stack is non-empty, it updates the `contents` to the tail of the old list, and returns the head.

The use of `mutex` to control access to the shared resource `contents` introduces sufficient synchronisation between multiple domains using the stack. Hence, there are no data races when multiple domains use the stack in parallel.
```javascript
let make () = {
    contents = [];
    mutex = Mutex.create ();
    nonempty = Condition.create ()
}
```

```javascript
let push r v =
    Mutex.lock r.mutex;
    r contents <- v::r contents;
    Condition.signal r.nonempty;
    Mutex unlock r.mutex
```

```javascript
let pop r =
    Mutex.lock r.mutex;
    let rec loop () =
        match r contents with
        | [] ->
            Condition.wait r.nonempty r.mutex;
        loop ()
        | x::xs -> r contents <- xs; x
        in
    let res = loop () in
    Mutex unlock r.mutex;
    res
```

end

The concurrent stack is implemented using a record with three fields: a mutable field `contents` which stores the elements in the stack, a mutex to control access to the `contents` field, and a condition variable `nonempty`, which is used to signal blocked domains waiting for the stack to become non-empty.

The `push` operation locks the mutex, updates the `contents` field with a new list whose head is the element being pushed and the tail is the old list. The condition variable `nonempty` is signalled while the lock is held in order to wake up any domains waiting on this condition. If there are waiting domains, one of the domains is woken up. If there are none, then the `signal` operation has no effect.

The `pop` operation locks the mutex and checks whether the stack is empty. If so, the calling domain waits on the condition variable `nonempty` using the `wait` primitive. The `wait` call atomically suspends the execution of the current domain and unlocks the mutex. When this domain is woken up again (when the `wait` call returns), it holds the lock on mutex. The domain tries to read the contents of the stack again. If the `pop` operation sees that the stack is non-empty, it updates the `contents` to the tail of the old list, and returns the head.

The use of mutex to control access to the shared resource `contents` introduces sufficient synchronisation between multiple domains using the stack. Hence, there are no data races when multiple domains use the stack in parallel.
### 9.5.1 Interaction with systerthreads

How do systerthreads interact with domains? The systerthreads created on a particular domain remain pinned to that domain. Only one systerthread at a time is allowed to run OCaml code on a particular domain. However, systerthreads belonging to a particular domain may run C library or system code in parallel. Systerthreads belonging to different domains may execute in parallel.

When using systerthreads, the thread created for executing the computation given to `Domain spawn` is also treated as a systerthread. For example, the following program creates in total two domains (including the initial domain) with two systerthreads each (including the initial systerthread for each of the domains).

```c
(* dom thr.ml *)
let m = Mutex.create ()
let r = ref None (* protected by m *)

let task () =
    let my thr_id = Thread.(id (self ())) in
    let my dom_id :> int = Domain.self () in
    Mutex.lock m;
    begin match !r with
    | None ->
        Printf printf "Thread %d running on domain %d saw initial write\n%!"
            my thr_id my dom_id
    | Some their thr_id ->
        Printf printf "Thread %d running on domain %d saw the write by thread %d\n%!"
            my thr_id my dom_id their thr_id;
    end;
    r := Some my thr_id;
    MutexUnlock m

let task' () =
    let t = Thread.create task () in
    task ();
    Thread.join t

let main () =
    let d = Domain spawn task' in
    task' ();
    Domain.join d

let _ = main ()

$ ocamopt -I +threads unix.cmxa threads.cmxa -o dom thr.exe dom thr.ml
$ ./dom thr.exe
Thread 1 running on domain 1 saw initial write
Thread 0 running on domain 0 saw the write by thread 1
```
9.5.1 Interaction with sylthreads

How do sylthreads interact with domains? The sylthreads created on a particular domain remain pinned to that domain. Only one sylthread at a time is allowed to run OCaml code on a particular domain. However, sylthreads belonging to a particular domain may run C library or system code in parallel. Sylthreads belonging to different domains may execute in parallel.

When using sylthreads, the thread created for executing the computation given to Domain spawn is also treated as a sylthread. For example, the following program creates in total two domains (including the initial domain) with two sylthreads each (including the initial sylthread for each of the domains).

(* dom thr ml *)
let m = Mutex.create ()
let r = ref None (* protected by m *)

let task () =
  let my thr id = Thread.(id (self ())) in
  let my dom id :> int = Domain.self () in
  Mutex.lock m;
  begin match !r with
  | None ->
      Printf printf "Thread %d running on domain %d saw initial write
      %!"
        my thr id my dom id
  | Some their thr id ->
      Printf printf "Thread %d running on domain %d saw the write by thread
      %d
      %!"
        my thr id my dom id their thr id;
  end;
  r := Some my thr id;
  Mutex unlock m

let task' () =
  let t = Thread.create task () in
  task ();
  Thread.join t

let main () =
  let d = Domain spawn task' in
  task' ();
  Domain.join d

let _ = main ()

$ ocamopt -I +threads -I +unix unix.cmxa threads.cmxa -o dom thr.exe dom thr.ml
$ ./dom thr.exe
Thread 1 running on domain 1 saw initial write
Thread 0 running on domain 0 saw the write by thread 1
Thread 2 running on domain 1 saw the write by thread 0

Thread 3 running on domain 0 saw the write by thread 2

This program uses a shared reference cell protected by a mutex to communicate between the different systhreads running on two different domains. The systhread identifiers uniquely identify systhreads in the program. The initial domain gets the domain id and the thread id as 0. The newly spawned domain gets domain id as 1.

## 9.6 Interaction with C bindings

During parallel execution with multiple domains, C code running on a domain may run in parallel with any C code running in other domains even if neither of them has released the "domain lock". Prior to OCaml 5.0, C bindings may have assumed that if the OCaml runtime lock is not released, then it would be safe to manipulate global C state (e.g. initialise a function-local static value). This is no longer true in the presence of parallel execution with multiple domains.

## 9.7 Atomics

Mutex, condition variables and semaphores are used to implement blocking synchronisation between domains. For non-blocking synchronisation, OCaml provides *Atomic*[28.4] variables. As the name suggests, non-blocking synchronisation does not provide mechanisms for suspending and waking up domains. On the other hand, primitives used in non-blocking synchronisation are often compiled to atomic read-modify-write primitives that the hardware provides. As an example, the following program increments a non-atomic counter and an atomic counter in parallel.

(* incr.ml *)

let twice_in_parallel f =
    let d1 = Domain spawn f in
    let d2 = Domain spawn f in
    Domain.join d1;
    Domain.join d2

let plain_ref n =
    let r = ref 0 in
    let f () = for _i=1 to n do incr r done in
    twice_in_parallel f;
    Printf printf "Non-atomic ref count: %d\n" !r

let atomic_ref n =
    let r = Atomic.make 0 in
    let f () = for _i=1 to n do Atomic.incr r done in
    twice_in_parallel f;
    Printf printf "Atomic ref count: %d\n" (Atomic.get r)

let main () =
Thread 2 running on domain 1 saw the write by thread 0

Thread 3 running on domain 0 saw the write by thread 2

This program uses a shared reference cell protected by a mutex to communicate between the different
systhreads running on two different domains. The systhread identifiers uniquely identify systhreads
in the program. The initial domain gets the domain id 0 and thread id 0. The newly spawned
domain gets the domain id 1.

9.6 Interaction with C bindings

During parallel execution with multiple domains, C code running on a domain may run in parallel
with any C code running in other domains even if neither of them has released the "domain lock".
Prior to OCaml 5.0, C bindings may have assumed that if the OCaml runtime lock is not released,
then it would be safe to manipulate global C state (e.g. initialise a function-local static value). This
is no longer true in the presence of parallel execution with multiple domains.

9.7 Atomics

Mutexes, condition variables and semaphores are used to implement blocking synchronisation
between domains. For non-blocking synchronisation, OCaml provides *Atomic*[29.4] variables. As
the name suggests, non-blocking synchronisation does not provide mechanisms for suspending and
waking up domains. On the other hand, primitives used in non-blocking synchronisation are often
compiled to atomic read-modify-write primitives that the hardware provides. As an example, the
following program increments a non-atomic counter and an atomic counter in parallel.

(* incr.ml *)

let twice_in_parallel f =
  let d1 = Domain spawn f in
  let d2 = Domain spawn f in
  Domain.join d1;
  Domain.join d2

let plain_ref n =
  let r = ref 0 in
  let f () = for _i=1 to n do incr r done in
  twice_in_parallel f;
  Printf printf "Non-atomic ref count: %d\n" !r

let atomic_ref n =
  let r = Atomic.make 0 in
  let f () = for _i=1 to n do Atomic.incr r done in
  twice_in_parallel f;
  Printf printf "Atomic ref count: %d\n" (Atomic.get r)

let main () =
```k
let n = try int_of_string Sys.argv.(1) with _ -> 1 in
plain_ref n;
atomic_ref n

let _ = main ()

$ ocamlopt -o incr.exe incr.ml
$ ./incr.exe 1_000_000
Non-atomic ref count: 1187193
Atomic ref count: 2000000
```

Observe that the result from using the non-atomic counter is lower than what one would naively expect. This is because the non-atomic `incr` function is equivalent to:

```k
let incr r =
    let curr = !r in
    r := curr + 1
```

Observe that the load and the store are two separate operations, and the increment operation as a whole is not performed atomically. When two domains execute this code in parallel, both of them may read the same value of the counter `curr` and update it to `curr + 1`. Hence, instead of two increments, the effect will be that of a single increment. On the other hand, the atomic counter performs the load and the store atomically with the help of hardware support for atomicity. The atomic counter returns the expected result.

The atomic variables can be used for low-level synchronisation between the domains. The following example uses an atomic variable to exchange a message between two domains.

```k
let r = Atomic.make None

let sender () = Atomic.set r (Some "Hello")

let rec receiver () =
    match Atomic.get r with
    | None -> Domain.cpu_relax (); receiver ()
    | Some m -> print_endline m

let main () =
    let s = Domain spawn sender in
    let d = Domain spawn receiver in
    Domain.join s;
    Domain.join d

let _ = main ()
Hello
val r : string option Atomic.t = <abstr>
val sender : unit -> unit = <fun>
val receiver : unit -> unit = <fun>
val main : unit -> unit = <fun>
```
```k
let n = try int_of_string Sys.argv.(1) with _ -> 1 in
plain_ref n;
atomic_ref n

let _ = main ()

$ ocamlopt -o incr.exe incr.ml
$ ./incr.exe 1_000_000
Non-atomic ref count: 1187193
Atomic ref count: 2000000
```

Observe that the result from using the non-atomic counter is lower than what one would naively expect. This is because the non-atomic `incr` function is equivalent to:

```k
let incr r =
    let curr = !r in
    r := curr + 1
```

Observe that the load and the store are two separate operations, and the increment operation as a whole is not performed atomically. When two domains execute this code in parallel, both of them may read the same value of the counter `curr` and update it to `curr + 1`. Hence, instead of two increments, the effect will be that of a single increment. On the other hand, the atomic counter performs the load and the store atomically with the help of hardware support for atomicity. The atomic counter returns the expected result.

Atomic variables can be used for low-level synchronisation between domains. The following example uses an atomic variable to exchange a message between two domains.

```k
let r = Atomic.make None

let sender () = Atomic.set r (Some "Hello")

let rec receiver () =
    match Atomic.get r with
    | None -> Domain.cpu_relax (); receiver ()
    | Some m -> print_endline m

let main () =
    let s = Domain spawn sender in
    let d = Domain spawn receiver in
    Domain.join s;
    Domain.join d

let _ = main ()
Hello
val r : string option Atomic.t = <abstr>
val sender : unit -> unit = <fun>
val receiver : unit -> unit = <fun>
val main : unit -> unit = <fun>
```
While the sender and the receiver compete to access r, this is not a data race since r is an atomic reference.

### 9.7.1 Lock-free stack

The `Atomic` module is used to implement non-blocking, lock-free data structures. The following program implements a lock-free stack.

```python
module Lockfree_stack : sig
    type 'a t
    val make : unit -> 'a t
    val push : 'a t -> 'a -> unit
    val pop : 'a t -> 'a option
end = struct
    type 'a t = 'a list Atomic.t

    let make () = Atomic.make []

    let rec push r v =
        let s = Atomic.get r in
        if Atomic compare_and_set r s (v::s) then ()
        else (Domain.cpu_relax (); push r v)

    let rec pop r =
        let s = Atomic.get r in
        match s with
        | [] -> None
        | x::xs ->
            if Atomic compare_and_set r s xs then Some x
            else (Domain.cpu_relax (); pop r)
end
```

The atomic stack is represented by an atomic reference that holds a list. The `push` and `pop` operations use the `compare_and_set` primitive to attempt to atomically update the atomic reference. The expression `compare_and_set r seen v` sets the value of `r` to `v` if and only if its current value is physically equal to `seen`. Importantly, the comparison and the update occur atomically. The expression evaluates to `true` if the comparison succeeded (and the update happened) and `false` otherwise.

If the `compare_and_set` fails, then some other domain is also attempting to update the atomic reference at the same time. In this case, the `push` and `pop` operations call `Domain.cpu_relax` to back off for a short duration allowing competing domains to make progress before retrying the failed operation. This lock-free stack implementation is also known as Treiber stack.
Although the sender and the receiver compete to access r, this is not a data race since r is an atomic reference.

9.7.1 Lock-free stack

The Atomic module is used to implement non-blocking, lock-free data structures. The following
program implements a lock-free stack.

module Lockfree_stack : sig
type 'a t
val make : unit -> 'a t
val push : 'a t -> 'a -> unit
val pop : 'a t -> 'a option
end = struct
type 'a t = 'a list Atomic.t

let make () = Atomic.make []

let rec push r v =
let s = Atomic.get r in
if Atomic compare_and_set r s (v::s) then ()
else (Domain.cpu_relax (); push r v)

let rec pop r =
let s = Atomic.get r in
match s with
| [] -> None
| x::xs ->
  if Atomic compare_and_set r s xs then Some x
  else (Domain.cpu_relax (); pop r)

end

The atomic stack is represented by an atomic reference that holds a list. The push and pop operations use the `compare_and_set` primitive to attempt to atomically update the atomic reference. The expression `compare_and_set r seen v` sets the value of `r` to `v` if and only if its current value is physically equal to `seen`. Importantly, the comparison and the update occur atomically. The expression evaluates to `true` if the comparison succeeded (and the update happened) and `false` otherwise.

If the `compare_and_set` fails, then some other domain is also attempting to update the atomic reference at the same time. In this case, the `push` and `pop` operations call `Domain.cpu_relax` to back off for a short duration allowing competing domains to make progress before retrying the failed operation. This lock-free stack implementation is called a *Treiber stack*.

9.7.2 Atomic record fields

The type `'a Atomic.t` is the atomic counterpart of the type of OCaml references, `'a ref`. Since OCaml 5.4, we also support atomic record fields, which must be mutable, via the `[@atomic]`
# Chapter 10

## Memory model: The hard bits

This chapter describes the details of OCaml relaxed memory model. The relaxed memory model describes what values an OCaml program is allowed to witness when reading a memory location. If you are interested in high-level parallel programming in OCaml, please have a look at the parallel programming chapter 9.

This chapter is aimed at experts who would like to understand the details of the OCaml memory model from a practitioner's perspective. For a formal definition of the OCaml memory model, its guarantees and the compilation to hardware memory models, please have a look at the PLDI 2018 paper on *Bounding Data Races in Space and Time*. The memory model presented in this chapter is an extension of the one presented in the PLDI 2018 paper. This chapter also covers some pragmatic aspects of the memory model that are not covered in the paper.

### 10.1 Why weakly consistent memory?

The simplest memory model that we could give to our programs is sequential consistency. Under sequential consistency, the values observed by the program can be explained through some interleaving of the operations from different domains in the program. For example, consider the following program with two domains `d1` and `d2` executing in parallel:

```ocaml
let d1 a b =
    let r1 = !a * 2 in
    let r2 = !b in
    let r3 = !a * 2 in
    (r1, r2, r3)
```

```ocaml
let d2 b = b := 0
```

```ocaml
let main () =
    let a = ref 1 in
    let b = ref 1 in
    let h = Domain spawn (fun _ ->
        let r1, r2, r3 = d1 a b in
        Printf printf "r1 = %d, r2 = %d, r3 = %d\n" r1 r2 r3)
```
attribute.

For example:

```typescript
type 'a refcounted = {
    value : 'a;
    mutable readers : int [@atomic];
}
```

The field `readers` is atomic, so that reading and writing to this field are atomic operations similar to `Atomic.get` and `Atomic.set`. It is possible to perform other atomic operations on this field by using a built-in extension node, `%atomic.loc`: if `rc` is a value of type `foo refcounted`, then `[%atomic.loc rc.readers]` is an expression of the built-in type `foo Atomic.Loc.t`, which allows atomic operations defined in the `Atomic[29.4]`. `Loc` module of the standard library, mirroring the operations exposed for atomic references in the `Atomic[29.4]` module:

```typescript
# let add_reader rc =
    Atomic.Loc.fetch_and_add [%atomic.loc rc.readers] 1;;

val add_reader : 'a refcounted -> int = <fun>

# #show Atomic.Loc;;
module Loc :
    sig
        type 'a t = 'a atomic_loc
        external get : 'a t -> 'a = "%atomic_load_loc"
        val set : 'a t -> 'a -> unit
        external exchange : 'a t -> 'a -> 'a = "%atomicExchange_loc"
        external compare_and_set : 'a t -> 'a -> 'a -> bool = "%atomic_cas_loc"
        external fetch_and_add : int t -> int -> int = "%atomic_fetch_add_loc"
        val incr : int t -> unit
        val decr : int t -> unit
    end
```

**Limitation** Currently there is no analogue of `Atomic.make_contended` for atomic record fields. If false sharing is an issue for a specific record field, the best supported approach is to use a field of type `Atomic.t`. We hope to implement support for on-demand padding of record fields in the future.

**Performance note** Internally `[%atomic.loc rc.readers]` is represented as a pair of the record value and a field offset. Whenever this expression is directly applied to an atomic primitive of the `Atomic[29.4]`. `Loc` module, the compiler will optimize away the creation of the pair; it passes the value and the offset as separate parameters to an underlying runtime primitive. On the other hand, storing an atomic location in a data-structure or passing it to another, non-inlined function may allocate a pair. When in doubt, you can inspect the `-dcm` intermediate representation of your code.
```
in
d2 b;
Domain.join h
```

The reference cells `a` and `b` are initially 1. The user may observe `r1 = 2`, `r2 = 0`, `r3 = 2` if the write to `b` in `d2` occurred before the read of `b` in `d1`. Here, the observed behaviour can be explained in terms of interleaving of the operations from different domains.

Let us now assume that `a` and `b` are aliases of each other.

```hml
let d1 a b =
let r1 = !a * 2 in
let r2 = !b in
let r3 = !a * 2 in
(r1, r2, r3)

let d2 b = b := 0

let main () =
let ab = ref 1 in
let h = Domain spawn (fun _ ->
let r1, r2, r3 = d1 ab ab in
assert (not (r1 = 2 && r2 = 0 && r3 = 2)))
in
d2 ab;
Domain.join h
```

In the above program, the variables `ab`, `a` and `b` refer to the same reference cell. One would expect that the assertion in the `main` function will never fail. The reasoning is that if `r2` is 0, then the write in `d2` occurred before the read of `b` in `d1`. Given that `a` and `b` are aliases, the second read of `a` in `d1` should also return 0.

### 10.1.1 Compiler optimisations

Surprisingly, this assertion may fail in OCaml due to compiler optimisations. The OCaml compiler observes the common sub-expression `!a * 2` in `d1` and optimises the program to:

```hml
let d1 a b =
let r1 = !a * 2 in
let r2 = !b in
let r3 = r1 in (* CSE: !a * 2 ===> r1 *)
(r1, r2, r3)

let d2 b = b := 0
```

```hml
let main () =
let ab = ref 1 in
let h = Domain spawn (fun _ ->
let r1, r2, r3 = d1 ab ab in
assert (not (r1 = 2 && r2 = 0 && r3 = 2)))
```
```
in
d2 ab;
Domain.join h
```

This optimisation is known as the common sub-expression elimination (CSE). Such optimisations are valid and necessary for good performance, and do not change the sequential meaning of the program. However, CSE breaks sequential reasoning.

In the optimized program above, even if the write to `b` in `d2` occurs between the first and the second reads in `d1`, the program will observe the value 2 for `r3`, causing the assertion to fail. The observed behaviour cannot be explained by interleaving of operations from different domains in the source program. Thus, CSE optimization is said to be invalid under sequential consistency.

One way to explain the observed behaviour is as if the operations performed on a domain were reordered. For example, if the second and the third reads from `d2` were reordered,

```
let d1 a b =
let r1 = !a * 2 in
let r3 = !a * 2 in
let r2 = !b in
(r1, r2, r3)
```

then we can explain the observed behaviour (2,0,2) returned by `d1`.

### 10.1.2 Hardware optimisations

The other source of reordering is by the hardware. Modern hardware architectures have complex cache hierarchies with multiple levels of cache. While cache coherence ensures that reads and writes to a single memory location respect sequential consistency, the guarantees on programs that operate on different memory locations are much weaker. Consider the following program:

```
let a = ref 0
and b = ref 0

let d1 () =
  a := 1;
  !b

let d2 () =
  b := 1;
  !a
```

```
let main () =
  let h = Domain spawn d2 in
  let r1 = d1 () in
  let r2 = Domain.join h in
  assert (not (r1 = 0 && r2 = 0))
```

Under sequential consistency, we would never expect the assertion to fail. However, even on x86, which offers much stronger guarantees than ARM, the writes performed at a CPU core are not immediately published to all of the other cores. Since `a` and `b` are different memory locations, the reads of `a` and `b` may both witness the initial values, leading to the assertion failure.
# Chapter 10

## Memory model: The hard bits

This chapter describes the details of OCaml relaxed memory model. The relaxed memory model describes what values an OCaml program is allowed to witness when reading a memory location. If you are interested in high-level parallel programming in OCaml, please have a look at the parallel programming chapter 9.

This chapter is aimed at experts who would like to understand the details of the OCaml memory model from a practitioner's perspective. For a formal definition of the OCaml memory model, its guarantees and the compilation to hardware memory models, please have a look at the PLDI 2018 paper on *Bounding Data Races in Space and Time*. The memory model presented in this chapter is an extension of the one presented in the PLDI 2018 paper. This chapter also covers some pragmatic aspects of the memory model that are not covered in the paper.

### 10.1 Why weakly consistent memory?

The simplest memory model that we could give to our programs is sequential consistency. Under sequential consistency, the values observed by the program can be explained through some interleaving of the operations from different domains in the program. For example, consider the following program with two domains `d1` and `d2` executing in parallel:

```ocaml
let d1 a b =
    let r1 = !a * 2 in
    let r2 = !b in
    let r3 = !a * 2 in
    (r1, r2, r3)

let d2 b = b := 0

let main () =
    let a = ref 1 in
    let b = ref 1 in
    let h = Domain spawn (fun _ ->
        let r1, r2, r3 = d1 a b in
        Printf printf "r1 = %d, r2 = %d, r3 = %d\n" r1 r2 r3)
```
This behaviour can be explained if a load is allowed to be reordered before a preceding store to a different memory location. This reordering can happen due to the presence of in-core store-buffers on modern processors. Each core effectively has a FIFO buffer of pending writes to avoid the need to block while a write completes. The writes to **a** and **b** may be in the store-buffers of cores **c1** and **c2** running the domains **d1** and **d2**, respectively. The reads of **b** and **a** running on the cores **c1** and **c2**, respectively, will not see the writes if the writes have not propagated from the buffers to the main memory.

## 10.2 Data race freedom implies sequential consistency

The aim of the OCaml relaxed memory model is to precisely describe which orders are preserved by the OCaml program. The compiler and the hardware are free to optimize the program as long as they respect the ordering guarantees of the memory model. While programming directly under the relaxed memory model is difficult, the memory model also describes the conditions under which a program will only exhibit sequentially consistent behaviours. This guarantee is known as *data race freedom implies sequential consistency* (DRF-SC). In this section, we shall describe this guarantee. In order to do this, we first need a number of definitions.

### 10.2.1 Memory locations

OCaml classifies memory locations into *atomic* and *non-atomic* locations. Reference cells, array fields and mutable record fields are non-atomic memory locations. Immutable objects are non-atomic locations with an initialising write but no further updates. Atomic memory locations are those that are created using the `Atomic` [28.4] module.

### 10.2.2 Happens-before relation

Let us imagine that the OCaml programs are executed by an abstract machine that executes one action at a time, arbitrarily picking one of the available domains at each step. We classify actions into two: *inter-domain* and *intra-domain*. An inter-domain action is one which can be observed and be influenced by actions on other domains. There are several inter-domain actions:

* Reads and writes of atomic and non-atomic locations.

* Spawn and join of domains.

* Operations on mutexes.

On the other hand, intra-domain actions can neither be observed nor influence the execution of other domains. Examples include evaluating an arithmetic expression, calling a function, etc. The memory model specification ignores such intra-domain actions. In the sequel, we use the term action to indicate inter-domain actions.

A totally ordered list of actions executed by the abstract machine is called an *execution trace*. There might be several possible execution traces for a given program due to non-determinism.

For a given execution trace, we define an *irreflexive, transitive happens-before relation* that captures the causality between actions in the OCaml program. The happens-before relation is defined as the smallest transitive relation satisfying the following properties:
```
in
d2 b;
Domain.join h
```

The reference cells `a` and `b` are initially 1. The user may observe `r1 = 2`, `r2 = 0`, `r3 = 2` if the write to `b` in `d2` occurred before the read of `b` in `d1`. Here, the observed behaviour can be explained in terms of interleaving of the operations from different domains.

Let us now assume that `a` and `b` are aliases of each other.

```ocaml
let d1 a b =
    let r1 = !a * 2 in
    let r2 = !b in
    let r3 = !a * 2 in
    (r1, r2, r3)

let d2 b = b := 0

let main () =
    let ab = ref 1 in
    let h = Domain spawn (fun _ ->
        let r1, r2, r3 = d1 ab ab in
        assert (not (r1 = 2 && r2 = 0 && r3 = 2)))
    in
    d2 ab;
    Domain.join h
```

In the above program, the variables `ab`, `a` and `b` refer to the same reference cell. One would expect that the assertion in the `main` function will never fail. The reasoning is that if `r2` is 0, then the write in `d2` occurred before the read of `b` in `d1`. Given that `a` and `b` are aliases, the second read of `a` in `d1` should also return 0.

### 10.1.1 Compiler optimisations

Surprisingly, this assertion may fail in OCaml due to compiler optimisations. The OCaml compiler observes the common sub-expression `!a * 2` in `d1` and optimises the program to:

```ocaml
let d1 a b =
    let r1 = !a * 2 in
    let r2 = !b in
    let r3 = r1 in (* CSE: !a * 2 ===> r1 *)
    (r1, r2, r3)

let d2 b = b := 0
```

```ocaml
let main () =
    let ab = ref 1 in
    let h = Domain spawn (fun _ ->
        let r1, r2, r3 = d1 ab ab in
        assert (not (r1 = 2 && r2 = 0 && r3 = 2)))
```
* We define the order in which a domain executes its actions as the *program order*. If an action *x* precedes another action *y* in program order, then *x* precedes *y* in happens-before order.

* If *x* is a write to an atomic location and *y* is a subsequent read or write to that memory location in the execution trace, then *x* precedes *y* in happens-before order. For atomic locations, `compare_and_set`, `fetch_and_add`, `exchange`, `incr` and `decr` are considered to perform both a read and a write.

* If *x* is `Domain spawn f` and *y* is the first action in the newly spawned domain executing *f*, then *x* precedes *y* in happens-before order.

* If *x* is the last action in a domain *d* and *y* is `Domain.join d`, then *x* precedes *y* in happens-before order.

* If *x* is an unlock operation on a mutex, and *y* is any subsequent operation on the mutex in the execution trace, then *x* precedes *y* in happens-before order.

### 10.2.3 Data race

In a given trace, two actions are said to be *conflicting* if they access the same non-atomic location, at least one is a write and neither is an initialising write to that location.

We say that a program has a *data race* if there exists some execution trace of the program with two conflicting actions and there does not exist a happens-before relationship between the conflicting accesses. A program without data races is said to be *correctly synchronised*.

### 10.2.4 DRF-SC

**DRF-SC guarantee:** A program without data races will only exhibit sequentially consistent behaviours.

DRF-SC is a strong guarantee for the programmers. Programmers can use *sequential reasoning* i.e., reasoning by executing one inter-domain action after the other, to identify whether their program has a data race. In particular, they do not need to reason about reorderings described in section 10.1 in order to determine whether their program has a data race. Once the determination that a particular program is data race free is made, they do not need to worry about reorderings in their code.

## 10.3 Reasoning with DRF-SC

In this section, we will look at examples of using DRF-SC for program reasoning. In this section, we will use the functions with names `dN` to represent domains executing in parallel with other domains. That is, we assume that there is a `main` function that runs the `dN` functions in parallel as follows:

```hml
let main () =
  let h1 = Domain spawn d1 in
  let h2 = Domain spawn d2 in
  ...
  ignore @@ Domain.join h1;
  ignore @@ Domain.join h2
```
```
in
d2 ab;
Domain.join h
```

This optimisation is known as the common sub-expression elimination (CSE). Such optimisations are valid and necessary for good performance, and do not change the sequential meaning of the program. However, CSE breaks sequential reasoning.

In the optimized program above, even if the write to `b` in `d2` occurs between the first and the second reads in `d1`, the program will observe the value 2 for `r3`, causing the assertion to fail. The observed behaviour cannot be explained by interleaving of operations from different domains in the source program. Thus, CSE optimization is said to be invalid under sequential consistency.

One way to explain the observed behaviour is as if the operations performed on a domain were reordered. For example, if the second and the third reads from `d1` were reordered,

```
let d1 a b =
let r1 = !a * 2 in
let r3 = !a * 2 in
let r2 = !b in
(r1, r2, r3)
```

then we can explain the observed behaviour (2,0,2) returned by `d1`.

### 10.1.2 Hardware optimisations

The other source of reordering is by the hardware. Modern hardware architectures have complex cache hierarchies with multiple levels of cache. While cache coherence ensures that reads and writes to a single memory location respect sequential consistency, the guarantees on programs that operate on different memory locations are much weaker. Consider the following program:

```
let a = ref 0
and b = ref 0

let d1 () =
  a := 1;
  !b

let d2 () =
  b := 1;
  !a
```

```
let main () =
  let h = Domain spawn d2 in
  let r1 = d1 () in
  let r2 = Domain.join h in
  assert (not (r1 = 0 && r2 = 0))
```

Under sequential consistency, we would never expect the assertion to fail. However, even on x86, which offers much stronger guarantees than ARM, the writes performed at a CPU core are not immediately published to all of the other cores. Since `a` and `b` are different memory locations, the reads of `a` and `b` may both witness the initial values, leading to the assertion failure.
Here is a simple example with a data race:

(* Has data race *)

let r = ref 0
let d1 () = r := 1
let d2 () = !r

r is a non-atomic reference. The two domains race to access the reference, and d1 is a write.
Since there is no happens-before relationship between the conflicting accesses, there is a data race.

Both of the programs that we had seen in the section 10.1 have data races. It is no surprise that
they exhibit non sequentially consistent behaviours.

Accessing disjoint array indices and fields of a record in parallel is not a data race. For example,

(* No data race *)

let a = [| 0; 1 |]
let d1 () = a.(0) <- 42
let d2 () = a.(1) <- 42

(* No data race *)

type t = {
    mutable a : int;
    mutable b : int
}
let r = {a = 0; b = 1}
let d1 () = r.a <- 42
let d2 () = r.b <- 42

do not have data races.

Races on atomic locations do not lead to a data race.

(* No data race *)

let r = Atomic.make 0
let d1 () = Atomic.set r 1
let d2 () = Atomic.get r

10.3.1 Message-passing

Atomic variables may be used for implementing non-blocking communication between domains.

(* No data race *)

let msg = ref 0
let flag = Atomic.make false
let d1 () =
    msg := 42; (* a *)
    Atomic.set flag true (* b *)
let d2 () =
    if Atomic.get flag (* c *) then
        !msg (* d *)
    else 0
This behaviour can be explained if a load is allowed to be reordered before a preceding store to a different memory location. This reordering can happen due to the presence of in-core store-buffers on modern processors. Each core effectively has a FIFO buffer of pending writes to avoid the need to block while a write completes. The writes to *a* and *b* may be in the store-buffers of cores *c1* and *c2* running the domains *d1* and *d2*, respectively. The reads of *b* and *a* running on the cores *c1* and *c2*, respectively, will not see the writes if the writes have not propagated from the buffers to the main memory.

## 10.2 Data race freedom implies sequential consistency

The aim of the OCaml relaxed memory model is to precisely describe which orders are preserved by the OCaml program. The compiler and the hardware are free to optimize the program as long as they respect the ordering guarantees of the memory model. While programming directly under the relaxed memory model is difficult, the memory model also describes the conditions under which a program will only exhibit sequentially consistent behaviours. This guarantee is known as *data race freedom implies sequential consistency* (DRF-SC). In this section, we shall describe this guarantee. In order to do this, we first need a number of definitions.

### 10.2.1 Memory locations

OCaml classifies memory locations into *atomic* and *non-atomic* locations. Reference cells, array fields and mutable record fields are non-atomic memory locations. Immutable objects are non-atomic locations with an initialising write but no further updates. Atomic memory locations are those that are created using the *Atomic*[29.4] module.

### 10.2.2 Happens-before relation

Let us imagine that the OCaml programs are executed by an abstract machine that executes one action at a time, arbitrarily picking one of the available domains at each step. We classify actions into two: *inter-domain* and *intra-domain*. An inter-domain action is one which can be observed and be influenced by actions on other domains. There are several inter-domain actions:

* Reads and writes of atomic and non-atomic locations.

* Spawn and join of domains.

* Operations on mutexes.

On the other hand, intra-domain actions can neither be observed nor influence the execution of other domains. Examples include evaluating an arithmetic expression, calling a function, etc. The memory model specification ignores such intra-domain actions. In the sequel, we use the term action to indicate inter-domain actions.

A totally ordered list of actions executed by the abstract machine is called an *execution trace*. There might be several possible execution traces for a given program due to non-determinism.

For a given execution trace, we define an *irreflexive, transitive happens-before relation* that captures the causality between actions in the OCaml program. The happens-before relation is defined as the smallest transitive relation satisfying the following properties:
Observe that the actions `a` and `d` write and read from the same non-atomic location `msg`, respectively, and hence are conflicting. We need to establish that `a` and `d` have a happens-before relationship in order to show that this program does not have a data race.

The action `a` precedes `b` in program order, and hence, `a` happens-before `b`. Similarly, `c` happens-before `d`. If `d2` observes the atomic variable `flag` to be `true`, then `b` precedes `c` in happens-before order. Since happens-before is transitive, the conflicting actions `a` and `d` are in happens-before order. If `d2` observes the `flag` to be `false`, then the read of `msg` is not done. Hence, there is no conflicting access in this execution trace. Hence, the program does not have a data race.

The following modified version of the message passing program does have a data race.

```
(* Has data race *)
let msg = ref 0
let flag = Atomic.make false
let d1 () =
    msg := 42; (* a *)
    Atomic.set flag true (* b *)
let d2 () =
    ignore (Atomic.get flag); (* c *)
!msg (* d *)
```

The domain `d2` now unconditionally reads the non-atomic reference `msg`. Consider the execution trace:

```
Atomic.get flag; (* c *)
!msg; (* d *)
msg := 42; (* a *)
Atomic.set flag true (* b *)
```

In this trace, `d` and `a` are conflicting operations. But there is no happens-before relationship between them. Hence, this program has a data race.

## 10.4 Local data race freedom

The OCaml memory model offers strong guarantees even for programs with data races. It offers what is known as *local data race freedom sequential consistency (LDRF-SC)* guarantee. A formal definition of this property is beyond the scope of this manual chapter. Interested readers are encouraged to read the PLDI 2018 paper on *Bounding Data Races in Space and Time*.

Informally, LDRF-SC says that the data race free parts of the program remain sequentially consistent. That is, even if the program has data races, those parts of the program that are disjoint from the parts with data races are amenable to sequential reasoning.

Consider the following snippet:

```
let snippet () =
    let c = ref 0 in
    c := 42;
    let a = !c in
    (a, c)
```
* We define the order in which a domain executes its actions as the *program order*. If an action *x* precedes another action *y* in program order, then *x* precedes *y* in happens-before order.

* If *x* is a write to an atomic location and *y* is a subsequent read or write to that memory location in the execution trace, then *x* precedes *y* in happens-before order. For atomic locations, `compare_and_set`, `fetch_and_add`, `exchange`, `incr` and `decr` are considered to perform both a read and a write.

* If *x* is `Domain spawn f` and *y* is the first action in the newly spawned domain executing *f*, then *x* precedes *y* in happens-before order.

* If *x* is the last action in a domain *d* and *y* is `Domain.join d`, then *x* precedes *y* in happens-before order.

* If *x* is an unlock operation on a mutex, and *y* is any subsequent operation on the mutex in the execution trace, then *x* precedes *y* in happens-before order.

### 10.2.3 Data race

In a given trace, two actions are said to be *conflicting* if they access the same non-atomic location, at least one is a write and neither is an initialising write to that location.

We say that a program has a *data race* if there exists some execution trace of the program with two conflicting actions and there does not exist a happens-before relationship between the conflicting accesses. A program without data races is said to be *correctly synchronised*.

### 10.2.4 DRF-SC

**DRF-SC guarantee:** A program without data races will only exhibit sequentially consistent behaviours.

DRF-SC is a strong guarantee for the programmers. Programmers can use *sequential reasoning* i.e., reasoning by executing one inter-domain action after the other, to identify whether their program has a data race. In particular, they do not need to reason about reorderings described in section 10.1 in order to determine whether their program has a data race. Once the determination that a particular program is data race free is made, they do not need to worry about reorderings in their code.

## 10.3 Reasoning with DRF-SC

In this section, we will look at examples of using DRF-SC for program reasoning. In this section, we will use the functions with names `dN` to represent domains executing in parallel with other domains. That is, we assume that there is a `main` function that runs the `dN` functions in parallel as follows:

```hml
let main () =
  let h1 = Domain spawn d1 in
  let h2 = Domain spawn d2 in
  ...
  ignore @@ Domain.join h1;
  ignore @@ Domain.join h2
```
Observe that `c` is a newly allocated reference. Can the read of `c` return a value which is not 42? That is, can `a` ever be not 42? Surprisingly, in the C++ and Java memory models, the answer is yes. With the C++ memory model, if the program has a data race, even in unrelated parts, then the semantics is undefined. If this snippet were linked with a library that had a data race, then, under the C++ memory model, the read may return any value. Since data races on unrelated locations can affect program behaviour, we say that C++ memory model is not bounded in space.

Unlike C++, Java memory model is bounded in space. But Java memory model is not bounded in time; data races in the future will affect the past behaviour. For example, consider the translation of this example to Java. We assume a prior definition of `Class c {int x;}` and a shared *non-volatile* variable `C g`. Now the snippet may be part of a larger program with parallel threads:

```c
(* Thread 1 *)
C c = new C();
c.x = 42;
a = c.x;
g = c;
```

```c
(* Thread 2 *)
g.x = 7;
```

The read of `c.x` and the write of `g` in the first thread are done on separate memory locations. Hence, the Java memory model allows them to be reordered. As a result, the write in the second thread may occur before the read of `c.x`, and hence, `c.x` returns 7.

The OCaml equivalent of the Java code above is:

``` Ocaml
let g = ref None

let snippet () =
    let c = ref 0 in
    c := 42;
    let a = !c in
    (a, c)

let d1 () =
    let (a,c) = snippet () in
    g := Some c;
    a

let d2 () =
    match !g with
    | None -> ()
    | Some c -> c := 7
```

Observe that there is a data race on both `g` and `c`. Consider only the first three instructions in `snippet`:

``` Ocaml
let c = ref 0 in
```
Here is a simple example with a data race:

(* Has data race *)

let r = ref 0
let d1 () = r := 1
let d2 () = !r

r is a non-atomic reference. The two domains race to access the reference, and d1 is a write.
Since there is no happens-before relationship between the conflicting accesses, there is a data race.

Both of the programs that we had seen in the section 10.1 have data races. It is no surprise that they exhibit non sequentially consistent behaviours.

Accessing disjoint array indices and fields of a record in parallel is not a data race. For example,

(* No data race *)

let a = [ | 0; 1 | ]
let d1 () = a.(0) <- 42
let d2 () = a.(1) <- 42

(* No data race *)

type t = {
    mutable a : int;
    mutable b : int
}
let r = {a = 0; b = 1}
let d1 () = r.a <- 42
let d2 () = r.b <- 42

do not have data races.

Races on atomic locations do not lead to a data race.

(* No data race *)

let r = Atomic.make 0
let d1 () = Atomic.set r 1
let d2 () = Atomic.get r

10.3.1 Message-passing

Atomic variables may be used for implementing non-blocking communication between domains.

(* No data race *)

let msg = ref 0
let flag = Atomic.make false
let d1 () =
    msg := 42; (* a *)
    Atomic.set flag true (* b *)
let d2 () =
    if Atomic.get flag (* c *) then
        !msg (* d *)
    else 0
c := 42;
let a = !c in
...

The OCaml memory model is bounded both in space and time. The only memory location here is `c`. Reasoning only about this snippet, there is neither the data race in space (the race on `g`) nor in time (the future race on `c`). Hence, the snippet will have sequentially consistent behaviour, and the value returned by `!c` will be `42`.

The OCaml memory model guarantees that even for programs with data races, memory safety is preserved. While programs with data races may observe non-sequentially consistent behaviours, they will not crash.

## 10.5 An operational view of the memory model

In this section, we describe the semantics of the OCaml memory model. A formal definition of the operational view of the memory model is presented in section 3 of the PLDI 2018 paper on *Bounding Data Races in Space and Time*. This section presents an informal description of the memory model with the help of an example.

Given an OCaml program, which may possibly contain data races, the operational semantics tells you the values that may be observed by the read of a memory location. For simplicity, we restrict the intra-thread actions to just the accesses to atomic and non-atomic locations, ignoring domain spawn and join operations, and the operations on mutexes.

We describe the semantics of the OCaml memory model in a straightforward small-step operational manner. That is, the semantics is described by an abstract machine that executes one action at a time, arbitrarily picking one of the available domains at each step. This is similar to the abstract machine that we had used to describe the happens-before relationship in section 10.2.2.

### 10.5.1 Non-atomic locations

In the semantics, we model non-atomic locations as finite maps from timestamps `t` to values `v`. We take timestamps to be rational numbers. The timestamps are totally ordered but dense; there is a timestamp between any two others.

For example,

a: [t1 -> 1; t2 -> 2]

b: [t3 -> 3; t4 -> 4; t5 -> 5]

c: [t6 -> 5; t7 -> 6; t8 -> 7]

represents three non-atomic locations `a`, `b` and `c` and their histories. The location `a` has two writes at timestamps `t1` and `t2` with values `1` and `2`, respectively. When we write `a: [t1 -> 1; t2 -> 2]`, we assume that `t1 < t2`. We assume that the locations are initialised with a history that has a single entry at timestamp `0` that maps to the initial value.
Observe that the actions `a` and `d` write and read from the same non-atomic location `msg`, respectively, and hence are conflicting. We need to establish that `a` and `d` have a happens-before relationship in order to show that this program does not have a data race.

The action `a` precedes `b` in program order, and hence, `a` happens-before `b`. Similarly, `c` happens-before `d`. If `d2` observes the atomic variable `flag` to be `true`, then `b` precedes `c` in happens-before order. Since happens-before is transitive, the conflicting actions `a` and `d` are in happens-before order. If `d2` observes the `flag` to be `false`, then the read of `msg` is not done. Hence, there is no conflicting access in this execution trace. Hence, the program does not have a data race.

The following modified version of the message passing program does have a data race.

(* Has data race *)
let msg = ref 0
let flag = Atomic.make false
let d1 () =
    msg := 42; (* a *)
    Atomic.set flag true (* b *)
let d2 () =
    ignore (Atomic.get flag); (* c *)
!msg (* d *)

The domain `d2` now unconditionally reads the non-atomic reference `msg`. Consider the execution trace:

Atomic.get flag; (* c *)
!msg; (* d *)
msg := 42; (* a *)
Atomic.set flag true (* b *)

In this trace, `d` and `a` are conflicting operations. But there is no happens-before relationship between them. Hence, this program has a data race.

## 10.4 Local data race freedom

The OCaml memory model offers strong guarantees even for programs with data races. It offers what is known as *local data race freedom sequential consistency (LDRF-SC)* guarantee. A formal definition of this property is beyond the scope of this manual chapter. Interested readers are encouraged to read the PLDI 2018 paper on *Bounding Data Races in Space and Time*.

Informally, LDRF-SC says that the data race free parts of the program remain sequentially consistent. That is, even if the program has data races, those parts of the program that are disjoint from the parts with data races are amenable to sequential reasoning.

Consider the following snippet:

let snippet () =
    let c = ref 0 in
    c := 42;
    let a = !c in
    (a, c)
### 10.5.2 Domains

Each domain is equipped with a *frontier*, which is a map from non-atomic locations to timestamps. Intuitively, each domain's frontier records, for each non-atomic location, the latest write known to the thread. More recent writes may have occurred, but are not guaranteed to be visible.

For example,

d1: [a -> t1; b -> t3; c -> t7]

d2: [a -> t1; b -> t4; c -> t7]

represents two domains d1 and d2 and their frontiers.

### 10.5.3 Non-atomic accesses

Let us now define the semantics of non-atomic reads and writes. Suppose domain *d1* performs the read of *b*. For non-atomic reads, the domains may read an arbitrary element of the history for that location, as long as it is not older than the timestamp in the domains's frontier. In this case, since *d1* frontier at *b* is at *t3*, the read may return the value 3, 4 or 5. A non-atomic read does not change the frontier of the current domain.

Suppose domain *d2* writes the value 10 to *c* (*c := 10*). We pick a new timestamp *t9* for this write such that it is later than *d2*'s frontier at *c*. Note a subtlety here: this new timestamp might not be later than everything else in the history, but merely later than any other write known to the writing domain. Hence, *t9* may be inserted in *c*'s history either (a) between *t7* and *t8* or (b) after *t8*. Let us pick the former option for our discussion. Since the new write appears after all the writes known by the domain *d2* to the location *c*, *d2*'s frontier at *c* is also updated. The new state of the abstract machine is:

(* Non-atomic locations *)

a: [t1 -> 1; t2 -> 2]

b: [t3 -> 3; t4 -> 4; t5 -> 5]

c: [t6 -> 5; t7 -> 6; t9 -> 10; t8 -> 7] (* new write at t9 *)

(* Domains *)

d1: [a -> t1; b -> t3; c -> t7]

d2: [a -> t1; b -> t4; c -> t9] (* frontier updated at c *)

### 10.5.4 Atomic accesses

Atomic locations carry not only values but also synchronization information. We model atomic locations as a pair of the value held by that location and a frontier. The frontier models the synchronization information, which is merged with the frontiers of threads that operate on the location. In this way, non-atomic writes made by one thread can become known to another by communicating via an atomic location.

For example,

(* Atomic locations *)

A: 10, [a -> t1; b -> t5; c -> t7]

B: 5, [a -> t2; b -> t4; c -> t6]
Observe that `c` is a newly allocated reference. Can the read of `c` return a value which is not 42? That is, can `a` ever be not 42? Surprisingly, in the C++ and Java memory models, the answer is yes. With the C++ memory model, if the program has a data race, even in unrelated parts, then the semantics is undefined. If this snippet were linked with a library that had a data race, then, under the C++ memory model, the read may return any value. Since data races on unrelated locations can affect program behaviour, we say that C++ memory model is not bounded in space.

Unlike C++, Java memory model is bounded in space. But Java memory model is not bounded in time; data races in the future will affect the past behaviour. For example, consider the translation of this example to Java. We assume a prior definition of `Class c {int x;}` and a shared *non-volatile* variable `C g`. Now the snippet may be part of a larger program with parallel threads:

```c
(* Thread 1 *)
C c = new C();
c.x = 42;
a = c.x;
g = c;
```

```c
(* Thread 2 *)
g.x = 7;
```

The read of `c.x` and the write of `g` in the first thread are done on separate memory locations. Hence, the Java memory model allows them to be reordered. As a result, the write in the second thread may occur before the read of `c.x`, and hence, `c.x` returns 7.

The OCaml equivalent of the Java code above is:

``` Ocaml
let g = ref None

let snippet () =
    let c = ref 0 in
    c := 42;
    let a = !c in
    (a, c)

let d1 () =
    let (a,c) = snippet () in
    g := Some c;
    a

let d2 () =
    match !g with
    | None -> ()
    | Some c -> c := 7
```

Observe that there is a data race on both `g` and `c`. Consider only the first three instructions in `snippet`:

``` Ocaml
let c = ref 0 in
```
shows two atomic variables A and B with values 10 and 5, respectively, and frontiers of their own.
We use upper-case variable names to indicate atomic locations.

During atomic reads, the frontier of the location is merged into that of the domain performing
the read. For example, suppose d1 reads B. The read returns 5, and d1's frontier updated by
merging it with B's frontier, choosing the later timestamp for each location. The abstract machine
state before the atomic read is:

(* Non-atomic locations *)
a: [t1 -> 1; t2 -> 2]
b: [t3 -> 3; t4 -> 4; t5 -> 5]
c: [t6 -> 5; t7 -> 6; t9 -> 10; t8 -> 7]

(* Domains *)
d1: [a -> t1; b -> t3; c -> t7]
d2: [a -> t1; b -> t4; c -> t9]

(* Atomic locations *)
A: 10, [a -> t1; b -> t5; c -> t7]
B: 5, [a -> t2; b -> t4; c -> t6]

As a result of the atomic read, the abstract machine state is updated to:

(* Non-atomic locations *)
a: [t1 -> 1; t2 -> 2]
b: [t3 -> 3; t4 -> 4; t5 -> 5]
c: [t6 -> 5; t7 -> 6; t9 -> 10; t8 -> 7]

(* Domains *)
d1: [a -> t2; b -> t4; c -> t7] (* frontier updated at a and b *)
d2: [a -> t1; b -> t4; c -> t9]

(* Atomic locations *)
A: 10, [a -> t1; b -> t5; c -> t7]
B: 5, [a -> t2; b -> t4; c -> t6]

During atomic writes, the value held by the atomic location is updated. The frontiers of both
the writing domain and that of the location being written to are updated to the merge of the two
frontiers. For example, if d2 writes 20 to A in the current machine state, the machine state is
updated to:

(* Non-atomic locations *)
a: [t1 -> 1; t2 -> 2]
b: [t3 -> 3; t4 -> 4; t5 -> 5]
c: [t6 -> 5; t7 -> 6; t9 -> 10; t8 -> 7]

(* Domains *)
c := 42;
let a = !c in
...

The OCaml memory model is bounded both in space and time. The only memory location here is `c`. Reasoning only about this snippet, there is neither the data race in space (the race on `g`) nor in time (the future race on `c`). Hence, the snippet will have sequentially consistent behaviour, and the value returned by `!c` will be 42.

The OCaml memory model guarantees that even for programs with data races, memory safety is preserved. While programs with data races may observe non-sequentially consistent behaviours, they will not crash.

## 10.5 An operational view of the memory model

In this section, we describe the semantics of the OCaml memory model. A formal definition of the operational view of the memory model is presented in section 3 of the PLDI 2018 paper on *Bounding Data Races in Space and Time*. This section presents an informal description of the memory model with the help of an example.

Given an OCaml program, which may possibly contain data races, the operational semantics tells you the values that may be observed by the read of a memory location. For simplicity, we restrict the intra-thread actions to just the accesses to atomic and non-atomic locations, ignoring domain spawn and join operations, and the operations on mutexes.

We describe the semantics of the OCaml memory model in a straightforward small-step operational manner. That is, the semantics is described by an abstract machine that executes one action at a time, arbitrarily picking one of the available domains at each step. This is similar to the abstract machine that we had used to describe the happens-before relationship in section 10.2.2.

### 10.5.1 Non-atomic locations

In the semantics, we model non-atomic locations as finite maps from timestamps `t` to values `v`. We take timestamps to be rational numbers. The timestamps are totally ordered but dense; there is a timestamp between any two others.

For example,

a: [t1 -> 1; t2 -> 2]

b: [t3 -> 3; t4 -> 4; t5 -> 5]

c: [t6 -> 5; t7 -> 6; t8 -> 7]

represents three non-atomic locations `a`, `b` and `c` and their histories. The location `a` has two writes at timestamps `t1` and `t2` with values 1 and 2, respectively. When we write `a: [t1 -> 1; t2 -> 2]`, we assume that `t1 < t2`. We assume that the locations are initialised with a history that has a single entry at timestamp 0 that maps to the initial value.
d1: [a -> t2; b -> t4; c -> t7]

d2: [a -> t1; b -> t5; c -> t9] (* frontier updated at b *)

(* Atomic locations *)

A: 20, [a -> t1; b -> t5; c -> t9] (* value updated. frontier updated at c. *)

B: 5, [a -> t2; b -> t4; c -> t6]

### 10.5.5 Reasoning with the semantics

Let us revisit an example from earlier (section 10.1).

let a = ref 0

and b = ref 0

let d1 () =

a := 1;

!b

let d2 () =

b := 1;

!a

let main () =

let h = Domain spawn d2 in

let r1 = d1 () in

let r2 = Domain.join h in

assert (not (r1 = 0 && r2 = 0))

This program has a data race on a and b, and hence, the program may exhibit non sequentially consistent behaviour. Let us use the semantics to show that the program may exhibit
r1 = 0 && r2 = 0.

The initial state of the abstract machine is:

(* Non-atomic locations *)

a: [t0 -> 0]

b: [t1 -> 0]

(* Domains *)

d1: [a -> t0; b -> t1]

d2: [a -> t0; b -> t1]

There are several possible schedules for executing this program. Let us consider the following schedule:

1: a := 1 @ d1

2: b := 1 @ d2

3: !b @ d1

4: !a @ d2
### 10.5.2 Domains

Each domain is equipped with a *frontier*, which is a map from non-atomic locations to timestamps. Intuitively, each domain's frontier records, for each non-atomic location, the latest write known to the thread. More recent writes may have occurred, but are not guaranteed to be visible.

For example,

d1: [a -> t1; b -> t3; c -> t7]

d2: [a -> t1; b -> t4; c -> t7]

represents two domains d1 and d2 and their frontiers.

### 10.5.3 Non-atomic accesses

Let us now define the semantics of non-atomic reads and writes. Suppose domain *d1* performs the read of *b*. For non-atomic reads, the domains may read an arbitrary element of the history for that location, as long as it is not older than the timestamp in the domains's frontier. In this case, since *d1* frontier at *b* is at *t3*, the read may return the value 3, 4 or 5. A non-atomic read does not change the frontier of the current domain.

Suppose domain *d2* writes the value 10 to *c* (*c* := 10). We pick a new timestamp *t9* for this write such that it is later than *d2*'s frontier at *c*. Note a subtlety here: this new timestamp might not be later than everything else in the history, but merely later than any other write known to the writing domain. Hence, *t9* may be inserted in *c*'s history either (a) between *t7* and *t8* or (b) after *t8*. Let us pick the former option for our discussion. Since the new write appears after all the writes known by the domain *d2* to the location *c*, *d2*'s frontier at *c* is also updated. The new state of the abstract machine is:

(* Non-atomic locations *)

a: [t1 -> 1; t2 -> 2]

b: [t3 -> 3; t4 -> 4; t5 -> 5]

c: [t6 -> 5; t7 -> 6; t9 -> 10; t8 -> 7] (* new write at t9 *)

(* Domains *)

d1: [a -> t1; b -> t3; c -> t7]

d2: [a -> t1; b -> t4; c -> t9] (* frontier updated at c *)

### 10.5.4 Atomic accesses

Atomic locations carry not only values but also synchronization information. We model atomic locations as a pair of the value held by that location and a frontier. The frontier models the synchronization information, which is merged with the frontiers of threads that operate on the location. In this way, non-atomic writes made by one thread can become known to another by communicating via an atomic location.

For example,

(* Atomic locations *)

A: 10, [a -> t1; b -> t5; c -> t7]

B: 5, [a -> t2; b -> t4; c -> t6]
After the first action `a:=1` by `d1`, the machine state is:

```
(* Non-atomic locations *)
a: [t0 -> 0; t2 -> 1] (* new write at t2 *)
b: [t1 -> 0]
```

```
(* Domains *)
d1: [a -> t2; b -> t1] (* frontier updated at a *)
d2: [a -> t0; b -> t1]
```

After the second action `b:=1` by `d2`, the machine state is:

```
(* Non-atomic locations *)
a: [t0 -> 0; t2 -> 1]
b: [t1 -> 0; t3 -> 1] (* new write at t3 *)
```

```
(* Domains *)
d1: [a -> t2; b -> t1]
d2: [a -> t0; b -> t3] (* frontier updated at b *)
```

Now, for the third action `!b` by `d1`, observe that `d1`'s frontier at `b` is at `t1`. Hence, the read may return either `0` or `1`. Let us assume that it returns `0`. The machine state is not updated by the non-atomic read.

Similarly, for the fourth action `!a` by `d2`, `d2`'s frontier at `a` is at `t0`. Hence, this read may also return either `0` or `1`. Let us assume that it returns `0`. Hence, the assertion in the original program, `assert (not (r1 = 0 && r2 = 0))`, will fail for this particular execution.

## 10.6 Non-compliant operations

There are certain operations which are not memory model compliant.

* `Array.blit` function on float arrays may cause tearing. When an unsynchronized blit operation runs concurrently with some overlapping write to the fields of the same float array, the field may end up with bits from either of the writes.

* With flat-float arrays or records with only float fields on 32-bit architectures, getting or setting a field involves two separate memory accesses. In the presence of data races, the user may observe tearing.

* The `Bytes` module `Bytes`[28.8] permits mixed-mode accesses where reads and writes may be of different sizes. Unsynchronized mixed-mode accesses lead to tearing.
shows two atomic variables A and B with values 10 and 5, respectively, and frontiers of their own.
We use upper-case variable names to indicate atomic locations.

During atomic reads, the frontier of the location is merged into that of the domain performing
the read. For example, suppose d1 reads B. The read returns 5, and d1's frontier updated by
merging it with B's frontier, choosing the later timestamp for each location. The abstract machine
state before the atomic read is:

(* Non-atomic locations *)
a: [t1 -> 1; t2 -> 2]
b: [t3 -> 3; t4 -> 4; t5 -> 5]
c: [t6 -> 5; t7 -> 6; t9 -> 10; t8 -> 7]

(* Domains *)
d1: [a -> t1; b -> t3; c -> t7]
d2: [a -> t1; b -> t4; c -> t9]

(* Atomic locations *)
A: 10, [a -> t1; b -> t5; c -> t7]
B: 5, [a -> t2; b -> t4; c -> t6]

As a result of the atomic read, the abstract machine state is updated to:

(* Non-atomic locations *)
a: [t1 -> 1; t2 -> 2]
b: [t3 -> 3; t4 -> 4; t5 -> 5]
c: [t6 -> 5; t7 -> 6; t9 -> 10; t8 -> 7]

(* Domains *)
d1: [a -> t2; b -> t4; c -> t7] (* frontier updated at a and b *)
d2: [a -> t1; b -> t4; c -> t9]

(* Atomic locations *)
A: 10, [a -> t1; b -> t5; c -> t7]
B: 5, [a -> t2; b -> t4; c -> t6]

During atomic writes, the value held by the atomic location is updated. The frontiers of both the
writing domain and that of the location being written to are updated to the merge of the two
frontiers. For example, if d2 writes 20 to A in the current machine state, the machine state is
updated to:

(* Non-atomic locations *)
a: [t1 -> 1; t2 -> 2]
b: [t3 -> 3; t4 -> 4; t5 -> 5]
c: [t6 -> 5; t7 -> 6; t9 -> 10; t8 -> 7]

(* Domains *)
d1: [a -> t2; b -> t4; c -> t7]

d2: [a -> t1; b -> t5; c -> t9] (* frontier updated at b *)

(* Atomic locations *)

A: 20, [a -> t1; b -> t5; c -> t9] (* value updated. frontier updated at c. *)

B: 5, [a -> t2; b -> t4; c -> t6]

### 10.5.5 Reasoning with the semantics

Let us revisit an example from earlier (section 10.1).

let a = ref 0

and b = ref 0

let d1 () =
    a := 1;
    !b

let d2 () =
    b := 1;
    !a

let main () =
    let h = Domain spawn d2 in
    let r1 = d1 () in
    let r2 = Domain.join h in
    assert (not (r1 = 0 && r2 = 0))

This program has a data race on a and b, and hence, the program may exhibit non sequen-
tially consistent behaviour. Let us use the semantics to show that the program may exhibit
r1 = 0 && r2 = 0.

The initial state of the abstract machine is:

(* Non-atomic locations *)

a: [t0 -> 0]

b: [t1 -> 0]

(* Domains *)

d1: [a -> t0; b -> t1]

d2: [a -> t0; b -> t1]

There are several possible schedules for executing this program. Let us consider the following
schedule:

1: a := 1 @ d1

2: b := 1 @ d2

3: !b @ d1

4: !a @ d2
# Part II

## The OCaml language
After the first action `a:=1` by `d1`, the machine state is:

```
(* Non-atomic locations *)
a: [t0 -> 0; t2 -> 1] (* new write at t2 *)
b: [t1 -> 0]
```

```
(* Domains *)
d1: [a -> t2; b -> t1] (* frontier updated at a *)
d2: [a -> t0; b -> t1]
```

After the second action `b:=1` by `d2`, the machine state is:

```
(* Non-atomic locations *)
a: [t0 -> 0; t2 -> 1]
b: [t1 -> 0; t3 -> 1] (* new write at t3 *)
```

```
(* Domains *)
d1: [a -> t2; b -> t1]
d2: [a -> t0; b -> t3] (* frontier updated at b *)
```

Now, for the third action `!b` by `d1`, observe that `d1`'s frontier at `b` is at `t1`. Hence, the read may return either `0` or `1`. Let us assume that it returns `0`. The machine state is not updated by the non-atomic read.

Similarly, for the fourth action `!a` by `d2`, `d2`'s frontier at `a` is at `t0`. Hence, this read may also return either `0` or `1`. Let us assume that it returns `0`. Hence, the assertion in the original program, `assert (not (r1 = 0 && r2 = 0))`, will fail for this particular execution.

## 10.6 Non-compliant operations

There are certain operations which are not memory model compliant.

* `Array.blit` function on float arrays may cause tearing. When an unsynchronized blit operation runs concurrently with some overlapping write to the fields of the same float array, the field may end up with bits from either of the writes.

* With flat-float arrays or records with only float fields on 32-bit architectures, getting or setting a field involves two separate memory accesses. In the presence of data races, the user may observe tearing.

* The `Bytes` module `Bytes`[29.8] permits mixed-mode accesses where reads and writes may be of different sizes. Unsynchronized mixed-mode accesses lead to tearing.
<figure><img src="image_3.png" /></figure>
# Chapter 11

## The OCaml language

### Foreword

This document is intended as a reference manual for the OCaml language. It lists the language constructs, and gives their precise syntax and informal semantics. It is by no means a tutorial introduction to the language. A good working knowledge of OCaml is assumed.

No attempt has been made at mathematical rigor: words are employed with their intuitive meaning, without further definition. As a consequence, the typing rules have been left out, by lack of the mathematical framework required to express them, while they are definitely part of a full formal definition of the language.

### Notations

The syntax of the language is given in BNF-like notation. Terminal symbols are set in typewriter font (`like this`). Non-terminal symbols are set in italic font (`like that`). Square brackets `[...]` denote optional components. Curly brackets `{...}` denotes zero, one or several repetitions of the enclosed components. Curly brackets with a trailing plus sign `{...}^+` denote one or several repetitions of the enclosed components. Parentheses (...) denote grouping.

### 11.1 Lexical conventions

#### Blanks

The following characters are considered as blanks: space, horizontal tabulation, carriage return, line feed and form feed. Blanks are ignored, but they separate adjacent identifiers, literals and keywords that would otherwise be confused as one single identifier, literal or keyword.

#### Comments

Comments are introduced by the two characters (`*`, with no intervening blanks, and terminated by the characters `*`), with no intervening blanks. Comments are treated as blank characters. Comments do not occur inside string or character literals. Nested comments are handled correctly.

<footnote>(* single line comment *)</footnote>
# Part II

## The OCaml language
(* multiple line comment, commenting out part of a program, and containing a nested comment:

```
let f = function
  | 'A'..'Z' -> "Uppercase"
  (* Add other cases later... *)
*)
```

## Identifiers

`ident ::= (letter | _){letter | 0...9 | _ | '}`

`capitalized-ident ::= (A...Z) {letter | 0...9 | _ | '}`

`lowercase-ident ::= (a...z | _){letter | 0...9 | _ | '}`

`letter ::= A...Z | a...z`

Identifiers are sequences of letters, digits, _ (the underscore character), and ' (the single quote), starting with a letter or an underscore. Letters contain at least the 52 lowercase and uppercase letters from the ASCII set. The current implementation also recognizes as letters some characters from the ISO 8859-1 set (characters 192–214 and 216–222 as uppercase letters; characters 223–246 and 248–255 as lowercase letters). This feature is deprecated and should be avoided for future compatibility.

All characters in an identifier are meaningful. The current implementation accepts identifiers up to 16000000 characters in length.

In many places, OCaml makes a distinction between capitalized identifiers and identifiers that begin with a lowercase letter. The underscore character is considered a lowercase letter for this purpose.

## Integer literals

`integer-literal ::= [-] (0...9) {0...9 | _} | [-] (0x | 0X) (0...9 | A...F | a...f) {0...9 | A...F | a...f | _} | [-] (0o | 0O) (0...7) {0...7 | _} | [-] (0b | 0B) (0...1) {0...1 | _}`

`int32-literal ::= integer-literal 1`

`int64-literal ::= integer-literal L`

`nativeint-literal ::= integer-literal n`

An integer literal is a sequence of one or more digits, optionally preceded by a minus sign. By default, integer literals are in decimal (radix 10). The following prefixes select a different radix:

<table><thead><tr><td>Prefix</td><td>Radix</td></tr></thead><tbody><tr><td>0x, 0X</td><td>hexadecimal (radix 16)</td></tr><tr><td>0o, 0O</td><td>octal (radix 8)</td></tr><tr><td>0b, 0B</td><td>binary (radix 2)</td></tr></tbody></table>
<figure><img src="image_4.png" /></figure>
(The initial `0` is the digit zero; the `0` for octal is the letter `O`.) An integer literal can be followed by one of the letters `l`, `L` or `n` to indicate that this integer has type `int32`, `int64` or `nativeint` respectively, instead of the default type `int` for integer literals. The interpretation of integer literals that fall outside the range of representable integer values is undefined.

For convenience and readability, underscore characters (`_`) are accepted (and ignored) within integer literals.

```ocaml
# let house_number = 37
let million = 1_000_000
let copyright = 0x00A9
let counter64bit = ref 0L;;
val house_number : int = 37
val million : int = 1000000
val copyright : int = 169
val counter64bit : int64 ref = {contents = 0L}
```

## Floating-point literals

```
float-literal ::= [-] (0...9) {0...9 | _} [. {0...9 | _}] [(e | E) [+ | -] (0...9) {0...9 | _}]
| [-] (0x | 0X) (0...9 | A...F | a...f) {0...9 | A...F | a...f | _}
| [. {0...9 | A...F | a...f | _}] [(p | P) [+ | -] (0...9) {0...9 | _}]
```

Floating-point decimal literals consist in an integer part, a fractional part and an exponent part. The integer part is a sequence of one or more digits, optionally preceded by a minus sign. The fractional part is a decimal point followed by zero, one or more digits. The exponent part is the character `e` or `E` followed by an optional `+` or `-` sign, followed by one or more digits. It is interpreted as a power of 10. The fractional part or the exponent part can be omitted but not both, to avoid ambiguity with integer literals. The interpretation of floating-point literals that fall outside the range of representable floating-point values is undefined.

Floating-point hexadecimal literals are denoted with the `0x` or `0X` prefix. The syntax is similar to that of floating-point decimal literals, with the following differences. The integer part and the fractional part use hexadecimal digits. The exponent part starts with the character `p` or `P`. It is written in decimal and interpreted as a power of 2.

For convenience and readability, underscore characters (`_`) are accepted (and ignored) within floating-point literals.

```ocaml
# let pi = 3.141_592_653_589_793_12
let smalltram = -1e-5
let machine epsilon = 0x1p-52;;
val pi : float = 3.14159265358979312
val smalltram : float = -1e-05
val machine epsilon : float = 2.22044604925031308e-16
```
# Chapter 11

## The OCaml language

### Foreword

This document is intended as a reference manual for the OCaml language. It lists the language constructs, and gives their precise syntax and informal semantics. It is by no means a tutorial introduction to the language. A good working knowledge of OCaml is assumed.

No attempt has been made at mathematical rigor: words are employed with their intuitive meaning, without further definition. As a consequence, the typing rules have been left out, by lack of the mathematical framework required to express them, while they are definitely part of a full formal definition of the language.

### Notations

The syntax of the language is given in BNF-like notation. Terminal symbols are set in typewriter font (`like this`). Non-terminal symbols are set in italic font (`like that`). Square brackets `[...]` denote optional components. Curly brackets `{...}` denotes zero, one or several repetitions of the enclosed components. Curly brackets with a trailing plus sign `{...}^+` denote one or several repetitions of the enclosed components. Parentheses (...) denote grouping.

### 11.1 Lexical conventions

#### Source file encoding

OCaml source files are expected to be valid UTF-8 encoded Unicode text. The interpretation of source files which are not UTF-8 encoded is unspecified. Such source files may be rejected in the future.

#### Blanks

The following characters are considered as blanks: space, horizontal tabulation, carriage return, line feed and form feed. Blanks are ignored, but they separate adjacent identifiers, literals and keywords that would otherwise be confused as one single identifier, literal or keyword.
## Character literals

<table><tr><td>char-literal</td><td>::= ' regular-char '<br>| ' escape-sequence '</td></tr><tr><td>escape-sequence</td><td>::= \ ( \ | " | ' | n | t | b | r | space)<br>| \ (0...9) (0...9) (0...9)<br>| \x (0...9 | A...F | a...f) (0...9 | A...F | a...f)<br>| \o (0...3) (0...7) (0...7)</td></tr></table>

Character literals are delimited by ' (single quote) characters. The two single quotes enclose either one character different from ' and \, or one of the escape sequences below:

<table><thead><tr><td>Sequence</td><td>Character denoted</td></tr></thead><tbody><tr><td>\\</td><td>backslash (\)</td></tr><tr><td>\"</td><td>double quote (")</td></tr><tr><td>\'</td><td>single quote (')</td></tr><tr><td>\n</td><td>linefeed (LF)</td></tr><tr><td>\r</td><td>carriage return (CR)</td></tr><tr><td>\t</td><td>horizontal tabulation (TAB)</td></tr><tr><td>\b</td><td>backspace (BS)</td></tr><tr><td>\space</td><td>space (SPC)</td></tr><tr><td>\ddd</td><td>the character with ASCII code ddd in decimal</td></tr><tr><td>\xhh</td><td>the character with ASCII code hh in hexadecimal</td></tr><tr><td>\oooo</td><td>the character with ASCII code ooo in octal</td></tr></tbody></table>

```pascal
# let a = 'a'
let single_quote = '\''
let copyright = '\xA9';
val a : char = 'a'
val single_quote : char = '\''
val copyright : char = '\169'
```

## String literals

<table><tr><td>string-literal</td><td>::= " {string-character} "<br>| {quoted-string-id | {any-char} | quoted-string-id }</td></tr><tr><td>quoted-string-id</td><td>::= {a... z | _}</td></tr><tr><td>string-character</td><td>::= regular-string-char<br>| escape-sequence<br>| \u{ {0...9 | A...F | a...f} + }</td></tr><tr><td></td><td>| \ newline {space | tab}</td></tr></table>

String literals are delimited by " (double quote) characters. The two double quotes enclose a sequence of either characters different from " and \, or escape sequences from the table given above for character literals, or a Unicode character escape sequence.
## Comments

Comments are introduced by the two characters (`*`), with no intervening blanks, and terminated by the characters `*`), with no intervening blanks. Comments are treated as blank characters. Comments do not occur inside string or character literals. Nested comments are handled correctly.

```ocaml
let f = function
  | 'A'..'Z' -> "Uppercase"
(* Add other cases later... *)
```

## Identifiers

```
ident ::= (letter | _){letter | 0...9 | _ | '}
capitalized-ident ::= uppercase-letter {letter | 0...9 | _ | '}
lowercase-ident ::= (lowercase-letter | _){letter | 0...9 | _ | '}
letter ::= uppercase-letter | lowercase-letter
lowercase-letter ::= a...z | U+00DF...U+00F6 | U+00F8...U+00FF | U+0153 | U+0161 | U+017E
uppercase-letter ::= A...Z | U+00C0...U+00D6 | U+00D8...U+00DE
                     | U+0152 | U+0160 | U+017D | U+0178 | U+1E9E
```

Identifiers are sequences of letters, digits, `_` (the underscore character), and `'` (the single quote), starting with a letter or an underscore. Letters contain the 52 lowercase and uppercase letters from the ASCII set, letters `ÀÁÁÁÁÆÇÈÉÊÊÈÎÍÎÏDÑÒÓÔÔÖÖÖÚÚÜÜÝÞßááååäåæçèéêêëìíîïðñòóôôöøùúúüýþŷ` from the Latin-1 Supplement block, letters `ŠšŽžŒœÝ` from the Latin Extended-A block and upper case SS (`U+189E`). Any byte sequence which is equivalent to one of these Unicode characters under NFC<fnref n="1" /> is supported too.

All characters in an identifier are meaningful. The current implementation accepts identifiers up to 16000000 characters in length.

In many places, OCaml makes a distinction between capitalized identifiers and identifiers that begin with a lowercase letter. The underscore character is considered a lowercase letter for this purpose.

<footnote>(* single line comment *)</footnote>

<footnote>(* multiple line comment, commenting out part of a program, and containing a nested comment:</footnote>

<footnote>*)</footnote>

<footnote n="1">¹Normalization Form C</footnote>
A Unicode character escape sequence is substituted by the UTF-8 encoding of the specified Unicode scalar value. The Unicode scalar value, an integer in the ranges 0x0000...0xD7FF or 0xE000...0x10FFFF, is defined using 1 to 6 hexadecimal digits; leading zeros are allowed.

```ocaml
# let greeting = "Hello, World!\n"
let superscript_PLUS = "\u{207A}";;
val greeting : string = "Hello, World!\n"
val superscript_PLUS : string = "+"
```

To allow splitting long string literals across lines, the sequence `\newline spaces-or-tabs` (a backslash at the end of a line followed by any number of spaces and horizontal tabulations at the beginning of the next line) is ignored inside string literals.

```ocaml
# let longstr =
"Call me Ishmael. Some years ago --- never mind how long \ 
precisely --- having little or no money in my purse, and \ 
nothing particular to interest me on shore, I thought I \ 
\ would sail about a little and see the watery part of t \ 
the world.";
val longstr : string =
"Call me Ishmael. Some years ago --- never mind how long precisely --- having little or no money in my purse, and ";
```

Quoted string literals provide an alternative lexical syntax for string literals. They are useful to represent strings of arbitrary content without escaping. Quoted strings are delimited by a matching pair of `{quoted-string-id |` and `|quoted-string-id }` with the same `quoted-string-id` on both sides. Quoted strings do not interpret any character in a special way but requires that the sequence `|quoted-string-id }` does not occur in the string itself. The identifier `quoted-string-id` is a (possibly empty) sequence of lowercase letters and underscores that can be freely chosen to avoid such issue.

```ocaml
# let quoted_greeting = {"Hello, World!"};
let nested = {ext|hello {|world|}|ext};;
val quoted_greeting : string = "\"Hello, World!\""
val nested : string = "hello {|world|}"
```

The current implementation places practically no restrictions on the length of string literals.

## Naming labels

To avoid ambiguities, naming labels in expressions cannot just be defined syntactically as the sequence of the three tokens `~`, `ident` and `:` , and have to be defined at the lexical level.

`label-name ::= lowercase-ident`

`label ::= ~ label-name :`

`optlabel ::= ? label-name :`

Naming labels come in two flavours: `label` for normal arguments and `optlabel` for optional ones. They are simply distinguished by their first character, either `~` or `?`.

Despite `label` and `optlabel` being lexical entities in expressions, their expansions `~ label-name :` and `? label-name :` will be used in grammars, for the sake of readability. Note also that inside type
## Integer literals

integer-literal ::= [-] (0...9) {0...9 | _}
| [-] (0x | 0X) (0...9 | A...F | a...f) {0...9 | A...F | a...f | _}
| [-] (0o | 0O) (0...7) {0...7 | _}
| [-] (0b | 0B) (0...1) {0...1 | _}

int32-literal ::= integer-literal 1

int64-literal ::= integer-literal L

nativeint-literal ::= integer-literal n

An integer literal is a sequence of one or more digits, optionally preceded by a minus sign. By default, integer literals are in decimal (radix 10). The following prefixes select a different radix:

<table><thead><tr><td>Prefix</td><td>Radix</td></tr></thead><tbody><tr><td>0x, 0X</td><td>hexadecimal (radix 16)</td></tr><tr><td>0o, 0O</td><td>octal (radix 8)</td></tr><tr><td>0b, 0B</td><td>binary (radix 2)</td></tr></tbody></table>

(The initial 0 is the digit zero; the 0 for octal is the letter O.) An integer literal can be followed by one of the letters 1, L or n to indicate that this integer has type `int32`, `int64` or `nativeint` respectively, instead of the default type `int` for integer literals. The interpretation of integer literals that fall outside the range of representable integer values is undefined.

For convenience and readability, underscore characters (`_`) are accepted (and ignored) within integer literals.

```pascal
# let house_number = 37
let million = 1_000_000
let copyright = 0x00A9
let counter64bit = ref OL;;
val house_number : int = 37
val million : int = 1000000
val copyright : int = 169
val counter64bit : int64 ref = {contents = OL}
```

## Floating-point literals

float-literal ::= [-] (0...9) {0...9 | _} [. {0...9 | _}] [(e | E) [+ | -] (0...9) {0...9 | _}]
| [-] (0x | 0X) (0...9 | A...F | a...f) {0...9 | A...F | a...f | _}
| [. {0...9 | A...F | a...f | _}] [(p | P) [+ | -] (0...9) {0...9 | _}]
```

Floating-point decimal literals consist in an integer part, a fractional part and an exponent part. The integer part is a sequence of one or more digits, optionally preceded by a minus sign. The fractional part is a decimal point followed by zero, one or more digits. The exponent part is the character `e` or `E` followed by an optional `+` or `-` sign, followed by one or more digits. It is interpreted as a power of 10. The fractional part or the exponent part can be omitted but not both, to avoid ambiguity with integer literals. The interpretation of floating-point literals that fall outside the range of representable floating-point values is undefined.
expressions, this expansion can be taken literally, i.e. there are really 3 tokens, with optional blanks between them.

## Prefix and infix symbols

infix-symbol ::= (core-operator-char | % | <) {operator-char}
                  | # {operator-char} +

prefix-symbol ::= ! {operator-char}
                  | (? | ~) {operator-char} +

operator-char ::= ~ | ! | ? | core-operator-char | % | < | : | .

core-operator-char ::= $ | & | * | + | - | / | = | > | @ | ^ | |

See also the following language extensions: extension operators, extended indexing operators, and binding operators.

Sequences of “operator characters”, such as `<=>` or `!!`, are read as a single token from the `infix-symbol` or `prefix-symbol` class. These symbols are parsed as prefix and infix operators inside expressions, but otherwise behave like normal identifiers.

## Keywords

The identifiers below are reserved as keywords, and cannot be employed otherwise:

<table><tr><td>and</td><td>as</td><td>assert</td><td>asr</td><td>begin</td><td>class</td></tr><tr><td>constraint</td><td>do</td><td>done</td><td>downto</td><td>else</td><td>end</td></tr><tr><td>exception</td><td>external</td><td>false</td><td>for</td><td>fun</td><td>function</td></tr><tr><td>functor</td><td>if</td><td>in</td><td>include</td><td>inherit</td><td> initializer</td></tr><tr><td>land</td><td>lazy</td><td>let</td><td>lor</td><td>lsl</td><td>lsr</td></tr><tr><td>lxor</td><td>match</td><td>method</td><td>mod</td><td>module</td><td>mutable</td></tr><tr><td>new</td><td>nonrec</td><td>object</td><td>of</td><td>open</td><td>or</td></tr><tr><td>private</td><td>rec</td><td>sig</td><td>struct</td><td>then</td><td>to</td></tr><tr><td>true</td><td>try</td><td>type</td><td>val</td><td>virtual</td><td>when</td></tr><tr><td>while</td><td>with</td><td></td><td></td><td></td><td></td></tr></table>

The following character sequences are also keywords:

!= # & && ' ( ) * + , -
- . -> . .. .~ : :: := :> ; ;;
< <- = > >] >} ? [ [< [> [|
] _ ' { {< | |] || } ~

Note that the following identifiers are keywords of the now unmaintained Camlp4 system and should be avoided for backwards compatibility reasons.

parser value $ $$ $: <: << >> ??
Floating-point hexadecimal literals are denoted with the `0x` or `0X` prefix. The syntax is similar to that of floating-point decimal literals, with the following differences. The integer part and the fractional part use hexadecimal digits. The exponent part starts with the character `p` or `P`. It is written in decimal and interpreted as a power of 2.

For convenience and readability, underscore characters (`_`) are accepted (and ignored) within floating-point literals.

```ocaml
# let pi = 3.141_592_653_589_793_12
let small negative = -1e-5
let machine epsilon = 0x1p-52;;
val pi : float = 3.14159265358979312
val small negative : float = -1e-05
val machine epsilon : float = 2.22044604925031308e-16
```

## Character literals

```
char-literal ::= ' regular-char '
                  | ' escape-sequence '

escape-sequence ::= \
                     ( \ | " | ' | n | t | b | r | space )
                     | \ ( 0...9 ) ( 0...9 ) ( 0...9 )
                     | \x ( 0...9 | A...F | a...f ) ( 0...9 | A...F | a...f )
                     | \o ( 0...3 ) ( 0...7 ) ( 0...7 )
```

Character literals are delimited by `'` (single quote) characters. The two single quotes enclose either one character different from `'` and `\`, or one of the escape sequences below:

<table><thead><tr><td>Sequence</td><td>Character denoted</td></tr></thead><tbody><tr><td>\\</td><td>backslash (\)</td></tr><tr><td>\"</td><td>double quote (")</td></tr><tr><td>\'</td><td>single quote (')</td></tr><tr><td>\n</td><td>linefeed (LF)</td></tr><tr><td>\r</td><td>carriage return (CR)</td></tr><tr><td>\t</td><td>horizontal tabulation (TAB)</td></tr><tr><td>\b</td><td>backspace (BS)</td></tr><tr><td>\space</td><td>space (SPC)</td></tr><tr><td>\ddd</td><td>the character with ASCII code <i>ddd</i> in decimal</td></tr><tr><td>\xhh</td><td>the character with ASCII code <i>hh</i> in hexadecimal</td></tr><tr><td>\oooo</td><td>the character with ASCII code <i>ooo</i> in octal</td></tr></tbody></table>

```ocaml
# let a = 'a'
let single_quote = '\''
let copyright = '\xA9';;
val a : char = 'a'
val single_quote : char = '\''
val copyright : char = '\169'
```
## Ambiguities

Lexical ambiguities are resolved according to the “longest match” rule: when a character sequence can be decomposed into two tokens in several different ways, the decomposition retained is the one with the longest first token.

## Line number directives

```
linenum-directive ::= # {0...9}+ " {string-character} "
```

Preprocessors that generate OCaml source code can insert line number directives in their output so that error messages produced by the compiler contain line numbers and file names referring to the source file before preprocessing, instead of after preprocessing. A line number directive starts at the beginning of a line, is composed of a # (sharp sign), followed by a positive integer (the source line number), followed by a character string (the source file name). Line number directives are treated as blanks during lexical analysis.

## 11.2 Values

This section describes the kinds of values that are manipulated by OCaml programs.

### 11.2.1 Base values

#### Integer numbers

Integer values are integer numbers from $-2^{30}$ to $2^{30} - 1$, that is $-1073741824$ to $1073741823$. The implementation may support a wider range of integer values: on 64-bit platforms, the current implementation supports integers ranging from $-2^{62}$ to $2^{62} - 1$.

#### Floating-point numbers

Floating-point values are numbers in floating-point representation. The current implementation uses double-precision floating-point numbers conforming to the IEEE 754 standard, with 53 bits of mantissa and an exponent ranging from $-1022$ to $1023$.

#### Characters

Character values are represented as 8-bit integers between 0 and 255. Character codes between 0 and 127 are interpreted following the ASCII standard. The current implementation interprets character codes between 128 and 255 following the ISO 8859-1 standard.

#### Character strings

String values are finite sequences of characters. The current implementation supports strings containing up to $2^{24} - 5$ characters (16777211 characters); on 64-bit platforms, the limit is $2^{57} - 9$.
## String literals

<table><tr><td>string-literal</td><td>::= " {string-character} "<br> | {quoted-string-id | newline<br> | any-char} | quoted-string-id }</td></tr><tr><td>quoted-string-id</td><td>::= {lowercase-letter | _}</td></tr><tr><td>string-character</td><td>::= regular-string-char<br> | escape-sequence<br> | \u{0...9 | A...F | a...f}<sup>+</sup>}</td></tr><tr><td></td><td> | newline<br> | \ newline {space | tab}</td></tr></table>

String literals are delimited by " (double quote) characters. The two double quotes enclose a sequence of either characters different from " and \, or escape sequences from the table given above for character literals, or a Unicode character escape sequence.

A Unicode character escape sequence is substituted by the UTF-8 encoding of the specified Unicode scalar value. The Unicode scalar value, an integer in the ranges 0x0000...0xD7FF or 0xE000...0x10FFFF, is defined using 1 to 6 hexadecimal digits; leading zeros are allowed.

```pascal
# let greeting = "Hello, World!\n"
let superscript_PLUS = "\u{207A}";;
val greeting : string = "Hello, World!\n"
val superscript_PLUS : string = ""
```

A newline sequence is a line feed optionally preceded by a carriage return. Since OCaml 5.2, a newline sequence occurring in a string literal is normalized into a single line feed character.

To allow splitting long string literals across lines, the sequence `\newline spaces-or-tabs` (a backslash at the end of a line followed by any number of spaces and horizontal tabulations at the beginning of the next line) is ignored inside string literals.

```pascal
# let longstr =
"Call me Ishmael. Some years ago - never mind how long \n
precisely - having little or no money in my purse, and \n
nothing particular to interest me on shore, I thought I\n
\ would sail about a little and see the watery part of t\n
the world.";;
val longstr : string =
```

"Call me Ishmael. Some years ago - never mind how long precisely - having little or no money in my purse."

Escaped newlines provide more convenient behavior than non-escaped newlines, as the indentation is not considered part of the string literal.

```pascal
# let contains_unexpected-spaces =
"This multiline literal
contains three consecutive spaces.";
```

```pascal
let no_unexpected-spaces =
"This multiline literal \n\n
uses a single space between all words.";;
```
### 11.2.2 Tuples

Tuples of values are written $(v_1, ..., v_n)$, standing for the $n$-tuple of values $v_1$ to $v_n$. The current implementation supports tuple of up to $2^{22} - 1$ elements (4194303 elements).

### 11.2.3 Records

Record values are labeled tuples of values. The record value written `{ field₁ = v₁ ; ... ; fieldₙ = vₙ }` associates the value $v_i$ to the record field $field_i$, for $i = 1...n$. The current implementation supports records with up to $2^{22} - 1$ fields (4194303 fields).

### 11.2.4 Arrays

Arrays are finite, variable-sized sequences of values of the same type. The current implementation supports arrays containing up to $2^{22} - 1$ elements (4194303 elements) unless the elements are floating-point numbers (2097151 elements in this case); on 64-bit platforms, the limit is $2^{54} - 1$ for all arrays.

### 11.2.5 Variant values

Variant values are either a constant constructor, or a non-constant constructor applied to a number of values. The former case is written `constr`; the latter case is written `constr` ($v_1, ..., v_n$), where the $v_i$ are said to be the arguments of the non-constant constructor `constr`. The parentheses may be omitted if there is only one argument.

The following constants are treated like built-in constant constructors:

<table><thead><tr><td>Constant</td><td>Constructor</td></tr></thead><tbody><tr><td>false</td><td>the boolean false</td></tr><tr><td>true</td><td>the boolean true</td></tr><tr><td>()</td><td>the “unit” value</td></tr><tr><td>[]</td><td>the empty list</td></tr></tbody></table>

The current implementation limits each variant type to have at most 246 non-constant constructors and $2^{30} - 1$ constant constructors.

### 11.2.6 Polymorphic variants

Polymorphic variants are an alternate form of variant values, not belonging explicitly to a predefined variant type, and following specific typing rules. They can be either constant, written `tag-name`, or non-constant, written `tag-name` ($v$).

### 11.2.7 Functions

Functional values are mappings from values to values.
```ocaml
val contains_unexpected-spaces : string =
    "This multiline literal \n contains three consecutive spaces."

val no_unexpected-spaces : string =
    "This multiline literal \nuses a single space between all words."
```

Quoted string literals provide an alternative lexical syntax for string literals. They are useful to represent strings of arbitrary content without escaping. Quoted strings are delimited by a matching pair of `{ quoted-string-id |` and `| quoted-string-id }` with the same `quoted-string-id` on both sides. Quoted strings do not interpret any character in a special way<fnref n="2" /> but requires that the sequence `| quoted-string-id }` does not occur in the string itself. The identifier `quoted-string-id` is a (possibly empty) sequence of lowercase letters and underscores that can be freely chosen to avoid such issue.

```ocaml
# let quoted_greeting = { | "Hello, World!" | }
let nested = { ext | hello { | world | } | ext } ; ;
val quoted_greeting : string = " "Hello, World! " "
val nested : string = "hello { | world | } "
```

The current implementation places practically no restrictions on the length of string literals.

## Naming labels

To avoid ambiguities, naming labels in expressions cannot just be defined syntactically as the sequence of the three tokens `-`, `ident` and `:` , and have to be defined at the lexical level.

```
label-name ::= lowercase-ident
label       ::= ~ label-name :
optlabel    ::= ? label-name :
```

Naming labels come in two flavours: `label` for normal arguments and `optlabel` for optional ones. They are simply distinguished by their first character, either `~` or `?`.

Despite `label` and `optlabel` being lexical entities in expressions, their expansions `~ label-name` : and `? label-name` : will be used in grammars, for the sake of readability. Note also that inside type expressions, this expansion can be taken literally, i.e. there are really 3 tokens, with optional blanks between them.

## Prefix and infix symbols

```
infix-symbol ::= (core-operator-char | % | <) {operator-char}
               | # {operator-char} +

prefix-symbol ::= ! {operator-char}
                 | (? | ~) {operator-char} +

operator-char ::= ~ | ! | ? | core-operator-char | % | < | : | .

core-operator-char ::= $ | & | * | + | - | / | = | > | @ | ^ | |
```

See also the following language extensions: extension operators, extended indexing operators, and binding operators.

<footnote n="2">²Except for the normalization of newline sequences into a single line feed mentioned earlier.</footnote>
### 11.2.8 Objects

Objects are composed of a hidden internal state which is a record of instance variables, and a set of methods for accessing and modifying these variables. The structure of an object is described by the toplevel class that created it.

## 11.3 Names

Identifiers are used to give names to several classes of language objects and refer to these objects by name later:

* value names (syntactic class *value-name*),

* value constructors and exception constructors (class *constr-name*),

* labels (*label-name*, defined in section 11.1),

* polymorphic variant tags (*tag-name*),

* type constructors (*typeconstr-name*),

* record fields (*field-name*),

* class names (*class-name*),

* method names (*method-name*),

* instance variable names (*inst-var-name*),

* module names (*module-name*),

* module type names (*modtype-name*).

These eleven name spaces are distinguished both by the context and by the capitalization of the identifier: whether the first letter of the identifier is in lowercase (written *lowercase-ident* below) or in uppercase (written *capitalized-ident*). Underscore is considered a lowercase letter for this purpose.
Sequences of "operator characters", such as `<=>` or `!!`, are read as a single token from the `infix-symbol` or `prefix-symbol` class. These symbols are parsed as prefix and infix operators inside expressions, but otherwise behave like normal identifiers.

## Keywords

The identifiers below are reserved as keywords, and cannot be employed otherwise:

<table><tr><td>and</td><td>as</td><td>assert</td><td>asr</td><td>begin</td><td>class</td></tr><tr><td>constraint</td><td>do</td><td>done</td><td>downto</td><td>else</td><td>end</td></tr><tr><td>exception</td><td>external</td><td>false</td><td>for</td><td>fun</td><td>function</td></tr><tr><td>functor</td><td>if</td><td>in</td><td>include</td><td>inherit</td><td> initializer</td></tr><tr><td>land</td><td>lazy</td><td>let</td><td>lor</td><td>lsl</td><td> lsr</td></tr><tr><td>lxor</td><td>match</td><td>method</td><td>mod</td><td>module</td><td>mutable</td></tr><tr><td>new</td><td>nonrec</td><td>object</td><td>of</td><td>open</td><td>or</td></tr><tr><td>private</td><td>rec</td><td>sig</td><td>struct</td><td>then</td><td>to</td></tr><tr><td>true</td><td>try</td><td>type</td><td>val</td><td>virtual</td><td>when</td></tr><tr><td>while</td><td>with</td><td></td><td></td><td></td><td></td></tr></table>

The following character sequences are also keywords:

```
!= # & && ' ( ) * + , -
-. -> . .. .~ : :: := :> ; ;;
< <- = > >] >} ? [ [< [> [|
] _ ` { {< | |] || } ~
```

Note that the following identifiers are keywords of the now unmaintained Camlp4 system and should be avoided for backwards compatibility reasons.

`parser` `value` `$` `$$` `$:` `<:` `<<` `>>` `??`

## Ambiguities

Lexical ambiguities are resolved according to the "longest match" rule: when a character sequence can be decomposed into two tokens in several different ways, the decomposition retained is the one with the longest first token.

## Line number directives

`linenum-directive ::= # {0...9}^+ " {string-character} "`

Preprocessors that generate OCaml source code can insert line number directives in their output so that error messages produced by the compiler contain line numbers and file names referring to the source file before preprocessing, instead of after preprocessing. A line number directive starts at the beginning of a line, is composed of a `#` (sharp sign), followed by a positive integer (the source line number), followed by a character string (the source file name). Line number directives are treated as blanks during lexical analysis.
Naming objects

<table><tr><td>value-name</td><td>::= lowercase-ident<br>| ( operator-name )</td></tr><tr><td>operator-name</td><td>::= prefix-symbol | infix-op</td></tr><tr><td>infix-op</td><td>::= infix-symbol<br>| * | + | - | -. | = | != | &lt; | &gt; | or | || | &amp; | && | :=<br>| mod | land | lor | lxor | lsl | lsr | asr</td></tr><tr><td>constr-name</td><td>::= capitalized-ident</td></tr><tr><td>tag-name</td><td>::= capitalized-ident</td></tr><tr><td>typeconstr-name</td><td>::= lowercase-ident</td></tr><tr><td>field-name</td><td>::= lowercase-ident</td></tr><tr><td>module-name</td><td>::= capitalized-ident</td></tr><tr><td>modtype-name</td><td>::= ident</td></tr><tr><td>class-name</td><td>::= lowercase-ident</td></tr><tr><td>inst-var-name</td><td>::= lowercase-ident</td></tr><tr><td>method-name</td><td>::= lowercase-ident</td></tr></table>

See also the following language extension: *extended indexing operators*.

As shown above, prefix and infix symbols as well as some keywords can be used as value names, provided they are written between parentheses. The capitalization rules are summarized in the table below.

<table><thead><tr><td>Name space</td><td>Case of first letter</td></tr></thead><tbody><tr><td>Values</td><td>lowercase</td></tr><tr><td>Constructors</td><td>uppercase</td></tr><tr><td>Labels</td><td>lowercase</td></tr><tr><td>Polymorphic variant tags</td><td>uppercase</td></tr><tr><td>Exceptions</td><td>uppercase</td></tr><tr><td>Type constructors</td><td>lowercase</td></tr><tr><td>Record fields</td><td>lowercase</td></tr><tr><td>Classes</td><td>lowercase</td></tr><tr><td>Instance variables</td><td>lowercase</td></tr><tr><td>Methods</td><td>lowercase</td></tr><tr><td>Modules</td><td>uppercase</td></tr><tr><td>Module types</td><td>any</td></tr></tbody></table>

*Note on polymorphic variant tags:* the current implementation accepts lowercase variant tags in addition to capitalized variant tags, but we suggest you avoid lowercase variant tags for portability and compatibility with future OCaml versions.
## 11.2 Values

This section describes the kinds of values that are manipulated by OCaml programs.

### 11.2.1 Base values

#### Integer numbers

Integer values are integer numbers from $-2^{30}$ to $2^{30} - 1$, that is $-1073741824$ to $1073741823$. The implementation may support a wider range of integer values: on 64-bit platforms, the current implementation supports integers ranging from $-2^{62}$ to $2^{62} - 1$.

#### Floating-point numbers

Floating-point values are numbers in floating-point representation. The current implementation uses double-precision floating-point numbers conforming to the IEEE 754 standard, with 53 bits of mantissa and an exponent ranging from $-1022$ to $1023$.

#### Characters

Character values are represented as 8-bit integers between 0 and 255. Character codes between 0 and 127 are interpreted following the ASCII standard. The current implementation interprets character codes between 128 and 255 following the ISO 8859-1 standard.

#### Character strings

String values are finite sequences of characters. The current implementation supports strings containing up to $2^{24} - 5$ characters (16777211 characters); on 64-bit platforms, the limit is $2^{57} - 9$.

### 11.2.2 Tuples

Tuples of values are written $(v_1, ..., v_n)$, standing for the $n$-tuple of values $v_1$ to $v_n$. The current implementation supports tuple of up to $2^{22} - 1$ elements (4194303 elements).

### 11.2.3 Records

Record values are labeled tuples of values. The record value written `{ field₁ = v₁ ; ... ; fieldₙ = vₙ }` associates the value $v_i$ to the record field `field_i`, for $i = 1...n$. The current implementation supports records with up to $2^{22} - 1$ fields (4194303 fields).

### 11.2.4 Arrays

Arrays are finite, variable-sized sequences of values of the same type. The current implementation supports arrays containing up to $2^{22} - 1$ elements (4194303 elements) unless the elements are floating-point numbers (2097151 elements in this case); on 64-bit platforms, the limit is $2^{54} - 1$ for all arrays.
## Referring to named objects

`value-path` ::= `[module-path .] value-name`

`constr` ::= `[module-path .] constr-name`

`typeconstr` ::= `[extended-module-path .] typeconstr-name`

`field` ::= `[module-path .] field-name`

`modtype-path` ::= `[extended-module-path .] modtype-name`

`class-path` ::= `[module-path .] class-name`

`classtype-path` ::= `[extended-module-path .] class-name`

`module-path` ::= `module-name { . module-name }`

`extended-module-path` ::= `extended-module-name { . extended-module-name }`

`extended-module-name` ::= `module-name { ( extended-module-path ) }`

A named object can be referred to either by its name (following the usual static scoping rules for names) or by an access path `prefix . name`, where `prefix` designates a module and `name` is the name of an object defined in that module. The first component of the path, `prefix`, is either a simple module name or an access path `name₁ . name₂ ...`, in case the defining module is itself nested inside other modules. For referring to type constructors, module types, or class types, the `prefix` can also contain simple functor applications (as in the syntactic class `extended-module-path` above) in case the defining module is the result of a functor application.

Label names, tag names, method names and instance variable names need not be qualified: the former three are global labels, while the latter are local to a class.
### 11.2.5 Variant values

Variant values are either a constant constructor, or a non-constant constructor applied to a number of values. The former case is written `constr`; the latter case is written `constr` ($v_1, ..., v_n$), where the $v_i$ are said to be the arguments of the non-constant constructor `constr`. The parentheses may be omitted if there is only one argument.

The following constants are treated like built-in constant constructors:

<table><thead><tr><td>Constant</td><td>Constructor</td></tr></thead><tbody><tr><td>false</td><td>the boolean false</td></tr><tr><td>true</td><td>the boolean true</td></tr><tr><td>()</td><td>the “unit” value</td></tr><tr><td>[]</td><td>the empty list</td></tr></tbody></table>

The current implementation limits each variant type to have at most 246 non-constant constructors and $2^{30} - 1$ constant constructors.

### 11.2.6 Polymorphic variants

Polymorphic variants are an alternate form of variant values, not belonging explicitly to a predefined variant type, and following specific typing rules. They can be either constant, written `tag-name`, or non-constant, written `tag-name` ($v$).

### 11.2.7 Functions

Functional values are mappings from values to values.

### 11.2.8 Objects

Objects are composed of a hidden internal state which is a record of instance variables, and a set of methods for accessing and modifying these variables. The structure of an object is described by the toplevel class that created it.

## 11.3 Names

Identifiers are used to give names to several classes of language objects and refer to these objects by name later:

* value names (syntactic class `value-name`),

* value constructors and exception constructors (class `constr-name`),

* labels (`label-name`, defined in section 11.1),

* polymorphic variant tags (`tag-name`),

* type constructors (`typeconstr-name`),

* record fields (`field-name`),
## 11.4 Type expressions

```
typexpr ::= ' ident
             | -
             | ( typexpr )
             | [[?] label-name :] typexpr -> typexpr
             | typexpr {\* typexpr}^+
             | typeconstr
             | typexpr typeconstr
             | ( typexpr {, typexpr} ) typeconstr
             | typexpr as ' ident
             | polymorphic-variant-type
             | < [..] >
             | < method-type {; method-type} [; | ; ..] >
             | # classtype-path
             | typexpr # class-path
             | ( typexpr {, typexpr} ) # class-path
```

```
poly-typexpr ::= typexpr
               | {' ident}^+ . typexpr
```

```
method-type ::= method-name : poly-typexpr
```

See also the following language extensions: first-class modules, attributes and extension nodes.

The table below shows the relative precedences and associativity of operators and non-closed type constructions. The constructions with higher precedences come first.

<table><thead><tr><td>Operator</td><td>Associativity</td></tr></thead><tbody><tr><td>Type constructor application</td><td>-</td></tr><tr><td>#</td><td>-</td></tr><tr><td>*</td><td>-</td></tr><tr><td>-&gt;</td><td>right</td></tr><tr><td>as</td><td>-</td></tr></tbody></table>

Type expressions denote types in definitions of data types as well as in type constraints over patterns and expressions.

### Type variables

The type expression ' ident stands for the type variable named ident. The type expression _ stands for either an anonymous type variable or anonymous type parameters. In data type definitions, type variables are names for the data type parameters. In type constraints, they represent unspecified types that can be instantiated by any type to satisfy the type constraint. In general the scope of a named type variable is the whole top-level phrase where it appears, and it can only be generalized when leaving this scope. Anonymous variables have no such restriction. In the following cases, the scope of named type variables is restricted to the type expression where they appear: 1) for universal (explicitly polymorphic) type variables; 2) for type variables that only appear in public method specifications (as those variables will be made universal, as described in section 11.9.1); 3)
* class names (*class-name*),

* method names (*method-name*),

* instance variable names (*inst-var-name*),

* module names (*module-name*),

* module type names (*modtype-name*).

These eleven name spaces are distinguished both by the context and by the capitalization of the identifier: whether the first letter of the identifier is in lowercase (written lowercase-ident below) or in uppercase (written capitalized-ident). Underscore is considered a lowercase letter for this purpose.

## Naming objects

<table><tr><td>value-name</td><td>::= lowercase-ident<br/>&nbsp;&nbsp;&nbsp;&nbsp;| ( operator-name )</td></tr><tr><td>operator-name</td><td>::= prefix-symbol | infix-op</td></tr><tr><td>infix-op</td><td>::= infix-symbol<br/>&nbsp;&nbsp;&nbsp;&nbsp;| * | + | - | - . | = | != | &lt; | &gt; | or | || | &amp; | &&& | :=<br/>&nbsp;&nbsp;&nbsp;&nbsp;| mod | land | lor | lxor | lsl | lsr | asr</td></tr><tr><td>constr-name</td><td>::= capitalized-ident</td></tr><tr><td>tag-name</td><td>::= capitalized-ident</td></tr><tr><td>typeconstr-name</td><td>::= lowercase-ident</td></tr><tr><td>field-name</td><td>::= lowercase-ident</td></tr><tr><td>module-name</td><td>::= capitalized-ident</td></tr><tr><td>modtype-name</td><td>::= ident</td></tr><tr><td>class-name</td><td>::= lowercase-ident</td></tr><tr><td>inst-var-name</td><td>::= lowercase-ident</td></tr><tr><td>method-name</td><td>::= lowercase-ident</td></tr></table>

See also the following language extension: *extended indexing operators*.

As shown above, prefix and infix symbols as well as some keywords can be used as value names, provided they are written between parentheses. The capitalization rules are summarized in the table below.
for variables used as aliases, when the type they are aliased to would be invalid in the scope of the enclosing definition (i.e. when it contains free universal type variables, or locally defined types.)

## Parenthesized types

The type expression `( typexpr )` denotes the same type as `typexpr`.

## Function types

The type expression `typexpr₁ -> typexpr₂` denotes the type of functions mapping arguments of type `typexpr₁` to results of type `typexpr₂`.

`label-name : typexpr₁ -> typexpr₂` denotes the same function type, but the argument is labeled `label`.

? `label-name`: `typexpr₁ -> typexpr₂` denotes the type of functions mapping an optional labeled argument of type `typexpr₁` to results of type `typexpr₂`. That is, the physical type of the function will be `typexpr₁ option -> typexpr₂`.

## Tuple types

The type expression `typexpr₁ *...* typexprₙ` denotes the type of tuples whose elements belong to types `typexpr₁, ... typexprₙ` respectively.

## Constructed types

Type constructors with no parameter, as in `typeconstr`, are type expressions.

The type expression `typexpr typeconstr`, where `typeconstr` is a type constructor with one parameter, denotes the application of the unary type constructor `typeconstr` to the type `typexpr`.

The type expression (`typexpr₁, ..., typexprₙ`) `typeconstr`, where `typeconstr` is a type constructor with `n` parameters, denotes the application of the `n`-ary type constructor `typeconstr` to the types `typexpr₁` through `typexprₙ`.

In the type expression `_ typeconstr`, the anonymous type expression `_` stands in for anonymous type parameters and is equivalent to `(_ ,..., _)` with as many repetitions of `_` as the arity of `typeconstr`.

## Aliased and recursive types

The type expression `typexpr` as `ident` denotes the same type as `typexpr`, and also binds the type variable `ident` to type `typexpr` both in `typexpr` and in other types. In general the scope of an alias is the same as for a named type variable, and covers the whole enclosing definition. If the type variable `ident` actually occurs in `typexpr`, a recursive type is created. Recursive types for which there exists a recursive path that does not contain an object or polymorphic variant type constructor are rejected, except when the `-rectypes` mode is selected.

If `ident` denotes an explicit polymorphic variable, and `typexpr` denotes either an object or polymorphic variant type, the row variable of `typexpr` is captured by `ident`, and quantified upon.
<table><thead><tr><td>Name space</td><td>Case of first letter</td></tr></thead><tbody><tr><td>Values</td><td>lowercase</td></tr><tr><td>Constructors</td><td>uppercase</td></tr><tr><td>Labels</td><td>lowercase</td></tr><tr><td>Polymorphic variant tags</td><td>uppercase</td></tr><tr><td>Exceptions</td><td>uppercase</td></tr><tr><td>Type constructors</td><td>lowercase</td></tr><tr><td>Record fields</td><td>lowercase</td></tr><tr><td>Classes</td><td>lowercase</td></tr><tr><td>Instance variables</td><td>lowercase</td></tr><tr><td>Methods</td><td>lowercase</td></tr><tr><td>Modules</td><td>uppercase</td></tr><tr><td>Module types</td><td>any</td></tr></tbody></table>

Note on polymorphic variant tags: the current implementation accepts lowercase variant tags in addition to capitalized variant tags, but we suggest you avoid lowercase variant tags for portability and compatibility with future OCaml versions.

## Referring to named objects

value-path ::= [module-path .] value-name

constr ::= [module-path .] constr-name

typeconstr ::= [extended-module-path .] typeconstr-name

field ::= [module-path .] field-name

modtype-path ::= [extended-module-path .] modtype-name

class-path ::= [module-path .] class-name

classtype-path ::= [extended-module-path .] class-name

module-path ::= module-name { . module-name }

extended-module-path ::= extended-module-name { . extended-module-name }

extended-module-name ::= module-name { ( extended-module-path ) }

A named object can be referred to either by its name (following the usual static scoping rules for names) or by an access path *prefix* . *name*, where *prefix* designates a module and *name* is the name of an object defined in that module. The first component of the path, *prefix*, is either a simple module name or an access path *name*₁ . *name*₂ . . . , in case the defining module is itself nested inside other modules. For referring to type constructors, module types, or class types, the *prefix* can also contain simple functor applications (as in the syntactic class *extended-module-path* above) in case the defining module is the result of a functor application.

Label names, tag names, method names and instance variable names need not be qualified: the former three are global labels, while the latter are local to a class.
## Polymorphic variant types

$$
\begin{align*}
\texttt{polymorphic-variant-type} &::= [ \texttt{tag-spec-first} \{ | \texttt{tag-spec} \} ] \\
& | [ > [ \texttt{tag-spec} ] \{ | \texttt{tag-spec} \} ] \\
& | [ < [ | \texttt{tag-spec-full} \{ | \texttt{tag-spec-full} \} ] > \{ ` \texttt{tag-name} \}^+ ] ] \\[1em]
\texttt{tag-spec-first} &::= ` \texttt{tag-name} [ \texttt{of} \texttt{typexpr} ] \\
& | [ \texttt{typexpr} ] | \texttt{tag-spec} \\[1em]
\texttt{tag-spec} &::= ` \texttt{tag-name} [ \texttt{of} \texttt{typexpr} ] \\
& | \texttt{typexpr} \\[1em]
\texttt{tag-spec-full} &::= ` \texttt{tag-name} [ \texttt{of} [ \& ] \texttt{typexpr} \{ \& \texttt{typexpr} \} ] \\
& | \texttt{typexpr}
\end{align*}
$$

Polymorphic variant types describe the values a polymorphic variant may take.

The first case is an exact variant type: all possible tags are known, with their associated types, and they can all be present. Its structure is fully known.

The second case is an open variant type, describing a polymorphic variant value: it gives the list of all tags the value could take, with their associated types. This type is still compatible with a variant type containing more tags. A special case is the unknown type, which does not define any tag, and is compatible with any variant type.

The third case is a closed variant type. It gives information about all the possible tags and their associated types, and which tags are known to potentially appear in values. The exact variant type (first case) is just an abbreviation for a closed variant type where all possible tags are also potentially present.

In all three cases, tags may be either specified directly in the `tag-name [of typexpr]` form, or indirectly through a type expression, which must expand to an exact variant type, whose tag specifications are inserted in its place.

Full specifications of variant tags are only used for non-exact closed types. They can be understood as a conjunctive type for the argument: it is intended to have all the types enumerated in the specification.

Such conjunctive constraints may be unsatisfiable. In such a case the corresponding tag may not be used in a value of this type. This does not mean that the whole type is not valid: one can still use other available tags. Conjunctive constraints are mainly intended as output from the type checker. When they are used in source programs, unsolvable constraints may cause early failures.

## Object types

An object type `<[method-type {; method-type}]>` is a record of method types.

Each method may have an explicit polymorphic type: `{' ident}^+`. `typexpr`. Explicit polymorphic variables have a local scope, and an explicit polymorphic type can only be unified to an equivalent one, where only the order and names of polymorphic variables may change.

The type `<{method-type;}..>` is the type of an object whose method names and types are described by `method-type₁, ..., method-typeₙ`, and possibly some other methods represented by the ellipsis. This ellipsis actually is a special kind of type variable (called *row variable* in the literature) that stands for any number of extra method types.
## 11.4 Type expressions

```
typexpr ::= ' ident
             | -
             | ( typexpr )
             | [[?] label-name :] typexpr -> typexpr
             | typexpr {\* typexpr}^+
             | typeconstr
             | typexpr typeconstr
             | ( typexpr {, typexpr} ) typeconstr
             | typexpr as ' ident
             | polymorphic-variant-type
             | < [..] >
             | < method-type {; method-type} [; | ..] >
             | # classtype-path
             | typexpr # class-path
             | ( typexpr {, typexpr} ) # class-path

poly-typexpr ::= typexpr
                 | { ' ident }^+ . typexpr

method-type ::= method-name : poly-typexpr
```

See also the following language extensions: first-class modules, attributes, extension nodes and labeled tuples.

The table below shows the relative precedences and associativity of operators and non-closed type constructions. The constructions with higher precedences come first.

<table><thead><tr><td>Operator</td><td>Associativity</td></tr></thead><tbody><tr><td>Type constructor application</td><td>—</td></tr><tr><td>#</td><td>—</td></tr><tr><td>*</td><td>—</td></tr><tr><td>-&gt;</td><td>right</td></tr><tr><td>as</td><td>—</td></tr></tbody></table>

Type expressions denote types in definitions of data types as well as in type constraints over patterns and expressions.

### Type variables

The type expression `ident` stands for the type variable named `ident`. The type expression `_` stands for either an anonymous type variable or anonymous type parameters. In data type definitions, type variables are names for the data type parameters. In type constraints, they represent unspecified types that can be instantiated by any type to satisfy the type constraint. In general the scope of a named type variable is the whole top-level phrase where it appears, and it can only be generalized when leaving this scope. Anonymous variables have no such restriction. In the following cases, the scope of named type variables is restricted to the type expression where they appear: 1) for universal (explicitly polymorphic) type variables; 2) for type variables that only appear in public
## #-types

The type `# classtype-path` is a special kind of abbreviation. This abbreviation unifies with the type of any object belonging to a subclass of the class type `classtype-path`. It is handled in a special way as it usually hides a type variable (an ellipsis, representing the methods that may be added in a subclass). In particular, it vanishes when the ellipsis gets instantiated. Each type expression `# classtype-path` defines a new type variable, so type `# classtype-path -> # classtype-path` is usually not the same as type (`# classtype-path as ' ident`)-`-> ' ident`.

## Variant and record types

There are no type expressions describing (defined) variant types nor record types, since those are always named, i.e. defined before use and referred to by name. Type definitions are described in section 11.8.1.

## 11.5 Constants

```
constant ::= integer-literal
           | int32-literal
           | int64-literal
           | nativeint-literal
           | float-literal
           | char-literal
           | string-literal
           | constr
           | false
           | true
           | ()
           | begin end
           | []
           | [ ]
           | ` tag-name
```

See also the following language extension: extension literals.

The syntactic class of constants comprises literals from the four base types (integers, floating-point numbers, characters, character strings), the integer variants, and constant constructors from both normal and polymorphic variants, as well as the special constants `false`, `true`, `()`, `[]`, and `[ ]`, which behave like constant constructors, and `begin end`, which is equivalent to `()`.
method specifications (as those variables will be made universal, as described in section 11.9.1); 3) for variables used as aliases, when the type they are aliased to would be invalid in the scope of the enclosing definition (i.e. when it contains free universal type variables, or locally defined types.)

## Parenthesized types

The type expression (`typexpr`) denotes the same type as `typexpr`.

## Function types

The type expression `typexpr₁ -> typexpr₂` denotes the type of functions mapping arguments of type `typexpr₁` to results of type `typexpr₂`.

`label-name : typexpr₁ -> typexpr₂` denotes the same function type, but the argument is labeled `label`.

`? label-name : typexpr₁ -> typexpr₂` denotes the type of functions mapping an optional labeled argument of type `typexpr₁` to results of type `typexpr₂`. That is, the physical type of the function will be `typexpr₁ option -> typexpr₂`.

## Tuple types

The type expression `typexpr₁ *...* typexprₙ` denotes the type of tuples whose elements belong to types `typexpr₁, ..., typexprₙ` respectively.

## Constructed types

Type constructors with no parameter, as in `typeconstr`, are type expressions.

The type expression `typexpr typeconstr`, where `typeconstr` is a type constructor with one parameter, denotes the application of the unary type constructor `typeconstr` to the type `typexpr`.

The type expression (`typexpr₁, ..., typexprₙ`) `typeconstr`, where `typeconstr` is a type constructor with `n` parameters, denotes the application of the `n`-ary type constructor `typeconstr` to the types `typexpr₁` through `typexprₙ`.

In the type expression `_ typeconstr`, the anonymous type expression `_` stands in for anonymous type parameters and is equivalent to `(_ ,..., _)` with as many repetitions of `_` as the arity of `typeconstr`.

## Aliased and recursive types

The type expression `typexpr` as ' ident denotes the same type as `typexpr`, and also binds the type variable `ident` to type `typexpr` both in `typexpr` and in other types. In general the scope of an alias is the same as for a named type variable, and covers the whole enclosing definition. If the type variable `ident` actually occurs in `typexpr`, a recursive type is created. Recursive types for which there exists a recursive path that does not contain an object or polymorphic variant type constructor are rejected, except when the `-rectypes` mode is selected.

If ' ident denotes an explicit polymorphic variable, and `typexpr` denotes either an object or polymorphic variant type, the row variable of `typexpr` is captured by ' ident, and quantified upon.
## 11.6 Patterns

pattern ::= value-name
| -
| constant
| pattern as value-name
| ( pattern )
| ( pattern : typexpr )
| pattern | pattern
| constr pattern
| ` tag-name pattern
| # typeconstr
| pattern {, pattern}+
| { field [ : typexpr ] [= pattern ] {; field [ : typexpr ] [= pattern ]} [ ; ] [ ; ] }
| [ pattern {; pattern} [ ; ] ]
| pattern :: pattern
| [ | pattern {; pattern} [ ; ] | ]
| char-literal .. char-literal
| lazy pattern
| exception pattern
| module-path . ( pattern )
| module-path . [ pattern ]
| module-path . [ | pattern | ]
| module-path . { pattern }

See also the following language extensions: first-class modules, attributes and extension nodes.

The table below shows the relative precedences and associativity of operators and non-closed pattern constructions. The constructions with higher precedences come first.

<table><thead><tr><td>Operator</td><td>Associativity</td></tr></thead><tbody><tr><td>..</td><td>-</td></tr><tr><td>lazy (see section 11.6.1)</td><td>-</td></tr><tr><td>Constructor application, Tag application</td><td>right</td></tr><tr><td>::</td><td>right</td></tr><tr><td>'</td><td>-</td></tr><tr><td>|</td><td>left</td></tr><tr><td>as</td><td>-</td></tr></tbody></table>

Patterns are templates that allow selecting data structures of a given shape, and binding identifiers to components of the data structure. This selection operation is called pattern matching; its outcome is either “this value does not match this pattern”, or “this value matches this pattern, resulting in the following bindings of names to values”.

### Variable patterns

A pattern that consists in a value name matches any value, binding the name to the value. The pattern `_` also matches any value, but does not bind any name.
## Polymorphic variant types

polymorphic-variant-type ::= [ tag-spec-first { | tag-spec } ]
                          | [ > [tag-spec] { | tag-spec } ]
                          | [< [ l ] tag-spec-full { | tag-spec-full } ] > { ` tag-name } + ] ]

tag-spec-first ::= ` tag-name [ of typexpr ]
                  | [ typexpr ] | tag-spec

tag-spec       ::= ` tag-name [ of typexpr ]
                  | typexpr

tag-spec-full  ::= ` tag-name [ of [&] typexpr { & typexpr } ]
                  | typexpr

Polymorphic variant types describe the values a polymorphic variant may take.

The first case is an exact variant type: all possible tags are known, with their associated types, and they can all be present. Its structure is fully known.

The second case is an open variant type, describing a polymorphic variant value: it gives the list of all tags the value could take, with their associated types. This type is still compatible with a variant type containing more tags. A special case is the unknown type, which does not define any tag, and is compatible with any variant type.

The third case is a closed variant type. It gives information about all the possible tags and their associated types, and which tags are known to potentially appear in values. The exact variant type (first case) is just an abbreviation for a closed variant type where all possible tags are also potentially present.

In all three cases, tags may be either specified directly in the ` tag-name [of typexpr] form, or indirectly through a type expression, which must expand to an exact variant type, whose tag specifications are inserted in its place.

Full specifications of variant tags are only used for non-exact closed types. They can be understood as a conjunctive type for the argument: it is intended to have all the types enumerated in the specification.

Such conjunctive constraints may be unsatisfiable. In such a case the corresponding tag may not be used in a value of this type. This does not mean that the whole type is not valid: one can still use other available tags. Conjunctive constraints are mainly intended as output from the type checker. When they are used in source programs, unsolvable constraints may cause early failures.

## Object types

An object type `< [method-type {; method-type}] >` is a record of method types.

Each method may have an explicit polymorphic type: `{' ident}^+`. `typexpr`. Explicit polymorphic variables have a local scope, and an explicit polymorphic type can only be unified to an equivalent one, where only the order and names of polymorphic variables may change.

The type `< {method-type ;} .. >` is the type of an object whose method names and types are described by `method-type_1, ..., method-type_n`, and possibly some other methods represented by the ellipsis. This ellipsis actually is a special kind of type variable (called *row variable* in the literature) that stands for any number of extra method types.
```ocaml
# let is_empty = function
| [] -> true
| _ :: _ -> false;;
val is_empty : 'a list -> bool = <fun>
```

Patterns are *linear*: a variable cannot be bound several times by a given pattern. In particular, there is no way to test for equality between two parts of a data structure using only a pattern:

```ocaml
# let pair_equal = function
| x, x -> true
| x, y -> false;;

Error: Variable x is bound several times in this matching
```

However, we can use a `when` guard for this purpose:

```ocaml
# let pair_equal = function
| x, y when x = y -> true
| _ -> false;;
val pair_equal : 'a * 'a -> bool = <fun>
```

## Constant patterns

A pattern consisting in a constant matches the values that are equal to this constant.

```ocaml
# let bool_of_string = function
| "true" -> true
| "false" -> false
| _ -> raise (Invalid_argument "bool_of_string");
val bool_of_string : string -> bool = <fun>
```

## Alias patterns

The pattern `pattern₁` as `value-name` matches the same values as `pattern₁`. If the matching against `pattern₁` is successful, the name `value-name` is bound to the matched value, in addition to the bindings performed by the matching against `pattern₁`.

```ocaml
# let sort_pair ((x, y) as p) =
    if x <= y then p else (y, x);;
val sort_pair : 'a * 'a -> 'a * 'a = <fun>
```

## Parenthesized patterns

The pattern (`pattern₁`) matches the same values as `pattern₁`. A type constraint can appear in a parenthesized pattern, as in (`pattern₁`: `typexpr`). This constraint forces the type of `pattern₁` to be compatible with `typexpr`.

```ocaml
# let int_triple_is_ordered ((a, b, c) : int * int * int) =
    a <= b && b <= c;;
val int_triple_is_ordered : int * int * int -> bool = <fun>
```
## `-types`

The type `# classtype-path` is a special kind of abbreviation. This abbreviation unifies with the type of any object belonging to a subclass of the class type `classtype-path`. It is handled in a special way as it usually hides a type variable (an ellipsis, representing the methods that may be added in a subclass). In particular, it vanishes when the ellipsis gets instantiated. Each type expression `# classtype-path` defines a new type variable, so type `# classtype-path -> # classtype-path` is usually not the same as type (`# classtype-path as ' ident`)-`-> ' ident`.

## Variant and record types

There are no type expressions describing (defined) variant types nor record types, since those are always named, i.e. defined before use and referred to by name. Type definitions are described in section 11.8.1.

# 11.5 Constants

<table><tr><td>constant</td><td>::=</td><td>integer-literal</td></tr><tr><td></td><td></td><td>int32-literal</td></tr><tr><td></td><td></td><td>int64-literal</td></tr><tr><td></td><td></td><td>nativeint-literal</td></tr><tr><td></td><td></td><td>float-literal</td></tr><tr><td></td><td></td><td>char-literal</td></tr><tr><td></td><td></td><td>string-literal</td></tr><tr><td></td><td></td><td>constr</td></tr><tr><td></td><td></td><td>false</td></tr><tr><td></td><td></td><td>true</td></tr><tr><td></td><td></td><td>( )</td></tr><tr><td></td><td></td><td>begin end</td></tr><tr><td></td><td></td><td>[]</td></tr><tr><td></td><td></td><td>[ ]</td></tr><tr><td></td><td></td><td>[ ]</td></tr><tr><td></td><td></td><td>` tag-name</td></tr></table>

See also the following language extension: extension literals.

The syntactic class of constants comprises literals from the four base types (integers, floating-point numbers, characters, character strings), the integer variants, and constant constructors from both normal and polymorphic variants, as well as the special constants `false`, `true`, `()` `[]`, and `[ ]`, which behave like constant constructors, and `begin end`, which is equivalent to `()`.
## "Or" patterns

The pattern `pattern₁ | pattern₂` represents the logical "or" of the two patterns `pattern₁` and `pattern₂`. A value matches `pattern₁ | pattern₂` if it matches `pattern₁` or `pattern₂`. The two sub-patterns `pattern₁` and `pattern₂` must bind exactly the same identifiers to values having the same types. Matching is performed from left to right. More precisely, in case some value `v` matches `pattern₁ | pattern₂`, the bindings performed are those of `pattern₁` when `v` matches `pattern₁`. Otherwise, value `v` matches `pattern₂` whose bindings are performed.

```hkl
# type shape = Square of float | Rect of (float * float) | Circle of float

let isRectangular = function
  | Square _ | Rect _ -> true
  | Circle _ -> false;;

type shape = Square of float | Rect of (float * float) | Circle of float
val isRectangular : shape -> bool = <fun>
```

## Variant patterns

The pattern `constr ( pattern₁ , ..., patternₙ )` matches all variants whose constructor is equal to `constr`, and whose arguments match `pattern₁...patternₙ`. It is a type error if `n` is not the number of arguments expected by the constructor.

The pattern `constr _` matches all variants whose constructor is `constr`.

```hkl
# type 'a tree = Lf | Br of 'a tree * 'a * 'a tree

let rec total = function
  | Br (l, x, r) -> total l + x + total r
  | Lf -> 0;;

type 'a tree = Lf | Br of 'a tree * 'a * 'a tree
val total : int tree -> int = <fun>
```

The pattern `pattern₁::: pattern₂` matches non-empty lists whose heads match `pattern₁`, and whose tails match `pattern₂`.

The pattern `[ pattern₁ ; ... ; patternₙ ]` matches lists of length `n` whose elements match `pattern₁...patternₙ`, respectively. This pattern behaves like `pattern₁:::...::: patternₙ:: []`.

```hkl
# let rec destutter = function
  | [] -> []
  | [a] -> [a]
  | a :: b :: t -> if a = b then destutter (b :: t) else a :: destutter (b :: t);;

val destutter : 'a list -> 'a list = <fun>
```

## Polymorphic variant patterns

The pattern `tag-name pattern₁` matches all polymorphic variants whose tag is equal to `tag-name`, and whose argument matches `pattern₁`.
## 11.6 Patterns

pattern ::= value-name
| -
| constant
| pattern as value-name
| ( pattern )
| ( pattern : typexpr )
| pattern | pattern
| constr pattern
| ` tag-name pattern
| # typeconstr
| pattern {, pattern}+
| { field [ : typexpr ] [= pattern ] { ; field [ : typexpr ] [= pattern ] } [ ; ] [ ; ] }
| [ pattern { ; pattern } [ ; ] ]
| pattern :: pattern
| [ | pattern { ; pattern } [ ; ] | ]
| char-literal .. char-literal
| lazy pattern
| exception pattern
| module-path . ( pattern )
| module-path . [ pattern ]
| module-path . [ | pattern | ]
| module-path . { pattern }

See also the following language extensions: first-class modules, attributes, extension nodes, effect handlers, type-directed disambiguation of array literals and labeled tuples.

The table below shows the relative precedences and associativity of operators and non-closed pattern constructions. The constructions with higher precedences come first.

<table><thead><tr><td>Operator</td><td>Associativity</td></tr></thead><tbody><tr><td>..</td><td>-</td></tr><tr><td>lazy (see section 11.6.1)</td><td>-</td></tr><tr><td>Constructor application, Tag application</td><td>right</td></tr><tr><td>::</td><td>right</td></tr><tr><td>,</td><td>-</td></tr><tr><td>|</td><td>left</td></tr><tr><td>as</td><td>-</td></tr></tbody></table>

Patterns are templates that allow selecting data structures of a given shape, and binding identifiers to components of the data structure. This selection operation is called pattern matching; its outcome is either “this value does not match this pattern”, or “this value matches this pattern, resulting in the following bindings of names to values”.

### Variable patterns

A pattern that consists in a value name matches any value, binding the name to the value. The pattern _ also matches any value, but does not bind any name.