3 Imperative Programming with OCaml

So Far, Only Functional Programming We haven’t given you any way so far to change something in memory. All you can do is create new values from old. This makes programming easier since it supports mathematical (i.e., functional) reasoning.

Don’t care whether data is shared in memory
Aliasing is irrelevant
Calling a function f with the same argument always produces the same result. For all ‘x‘ and ‘y‘, we have ‘f x = f y‘ when ‘x = y‘

But sometimes it is useful for values to change. We may need a unique counter that increments in every call or we may need an efficient hash table. OCaml variables are immutable, but OCaml has references, fields, and arrays that are actually mutable, I.e., they can change

3.2 Immutability vs. Mutability🔗

Functional programming emphasizes immutability, pure functions, and referential transparency because they reduce side effects and make reasoning about program correctness easier. These properties enable equational reasoning, local reasoning, and simpler proofs of correctness.

However, immutability can sometimes make code less efficient and more complex for inherently stateful problems.

For example, in graph algorithms such as BFS or Dijkstra’s shortest path algorithm, we need to:

Mark nodes as visited
Update distances
Maintain queues or priority queues

Mutation expresses these operations naturally and directly. While immutable implementations are possible, they are often more complex, slower, and harder to read.

3.2.1 When Mutability Is Useful🔗

Mutability is useful in programming for scenarios that require:

High performance with frequent data changes
Managing shared state among different components
Modeling real-world systems that evolve over time

Below are common scenarios where mutability is especially beneficial.

3.2.2 Performance and Efficiency🔗

For algorithms and data structures that require frequent updates, in-place modification is often more time- and memory-efficient than creating a new object for every change.

Growing Data Structures
Mutable data structures such as arrays or lists are well suited for collections that change frequently (e.g., shopping carts or playlists). In-place updates:
- Avoid allocating new arrays or intermediate structures
- Are faster and more memory-efficient
- Are especially important in tight loops, numerical code, or large-scale data processing
As a result, many functional languages allow local mutability while keeping the overall program pure.
Avoiding Object Creation
Creating new objects involves memory allocation and garbage collection, which can be expensive. Mutability reduces this overhead in performance-critical code.
For example, Java’s ‘StringBuilder‘ is mutable to support efficient string construction, avoiding the creation of many temporary immutable strings.

3.2.3 Interfacing with the Real World (I/O and Stateful APIs)🔗

The real world is inherently mutable:

Files change
Network connections open and close
GUIs respond to events
Databases update records

Interacting with these systems naturally involves state changes, making controlled mutability essential.

3.2.4 Algorithms That Are Naturally Stateful🔗

Some algorithms are conceptually clearer when expressed with mutation.

Examples include graph algorithms such as DFS and BFS, which involve:

Marking nodes as visited
Updating distances
Maintaining queues or priority queues

Using immutable data structures is possible, but often:

More complex
Slower
Harder to understand

Mutation makes the algorithm’s intent explicit.

3.2.5 4. Caching and Memoization🔗

Caching stores the results of expensive computations so they can be reused.

Mutation is useful because:

The cache persists across function calls
Recomputation is avoided
The implementation is clear and efficient

Pure memoization is possible but often awkward or slower.

OCaml example:

OCaml REPL

let expensive x = x * x;; 
 
 let memo_f = 
    let table = Hashtbl.create 16 in 
    fun x -> 
      match Hashtbl.find_opt table x with 
      | Some v -> v 
      | None -> 
          let v = expensive x in 
          Hashtbl.add table x v; 
          v;; 


[Output]
val expensive : int -> int = <fun>
val memo_f : int -> int = <fun>

3.2.6 Modeling Evolving State (Simulations, Games, Systems)🔗

Many real-world systems naturally evolve over time:

Game state (player position, score)
Simulations (time steps, physical systems)
Servers maintaining session state

It is often more intuitive to model a car by updating its fuel level than by creating a new car object for every change.

Mutability matches the mental model:

“This thing changes over time.”

Forcing immutability in such cases can obscure the logic.

3.2.7 Internal Implementation of Pure Abstractions🔗

Even in functional languages, many abstractions use mutation internally while exposing a pure interface, including:

Maps and sets
Compilers
Garbage collectors

This approach combines:

The performance benefits of mutability
The reasoning benefits of immutability

3.2.8 Programming Paradigms and Algorithms🔗

Object-Oriented Programming (OOP) often relies on mutable objects whose state changes over their lifetime.
Certain algorithms, such as some in-place sorting algorithms, are simpler or more efficient when implemented using mutation, even though immutable versions exist.

3.2.9 Summary🔗

While immutability provides strong benefits such as predictability, simpler reasoning, and improved safety in concurrent programs, mutability remains a powerful tool for performance and clarity in problems involving frequent or natural state changes.

Functional programming does not say “Never use mutability.” It says “Use immutability by default, and use mutability deliberately.”

Best practice is to:

Keep mutation local
Hide it behind clean interfaces
Avoid shared, uncontrolled mutable state

This balance is why languages such as OCaml, F#, Scala, and even Haskell (via ‘ST‘ and ‘IO‘) support mutability.

3.3 Refs🔗

There are two built-in mutable data structures in OCaml: ‘refs‘ and ‘arrays‘. ‘’a ref‘ is pointer to a mutable value of type ‘’a‘. There are three basic operations on references: Allocate a reference: ref e creates a new reference cell containing the value of expression e.

OCaml REPL

ref ;; 
 
 let x = ref 10;; 
 let y = ref "hello";;

[Output]
- : 'a -> 'a ref = <fun>
val x : int ref = {contents = 10}
val y : string ref = {contents = "hello"}

Read the value stored in reference: !t dereferences the reference cell t to get the current value.

OCaml REPL

(!) ;; 
 let t = ref 10;; 
 !t ;;

[Output]
- : 'a ref -> 'a = <fun>
val t : int ref = {contents = 10}
- : int = 10

Change the value stored in reference: t := e updates the reference cell t with the value of expression e.

OCaml REPL

(:=) ;; 
 
 let t = ref "hello";; 
 !t ;; 
 t := "world";; 
 !t ;;

[Output]
- : 'a ref -> 'a -> unit = <fun>
val t : string ref = {contents = "hello"}
- : string = "hello"
- : unit = ()
- : string = "world"

Binding variable ‘x‘ to a reference is immutable. The contents of the reference x points to may change.

OCaml REPL

let z = 3;; 
 let x = ref z;; 
 let y = x;; 
 
 x := 4;; 
 !y;; 
 ;;

[Output]
val z : int = 3
val x : int ref = {contents = 3}
val y : int ref = {contents = 3}
- : unit = ()
- : int = 4

Here, ‘z‘ is bound to 3. It is immutable. ‘x‘ and ‘y‘ are bound to a reference. The ‘contents‘ of the reference is mutable. x := 4 will update the ‘contests‘ to 4. ‘x‘ and ‘y‘ now points to the value 4. Therefore, reading y using !y will return int = 4.

Here, variables y and x are aliases. In ‘let y = x‘, variable ‘x‘ evaluates to a location, and ‘y‘ is bound to the same location. So, changing the contents of that location will cause both ‘!x‘ and ‘!y‘ to change.

Evaluation of References

Evaluate ‘e‘ to a value ‘v‘, allocate a new location loc in memory to hold ‘v‘, store ‘v‘ in ‘contents‘ of memory at loc, return loc (which is itself a value). For example, e1 := e2 evaluates ‘e2‘ to a value ‘v2‘, evaluates e1 to a location loc, stores ‘v2‘ in ‘contents‘ of memory at loc, returns ‘()‘

Type checking Rules:


(ref e)  : t ref  if  e : t 
(e1 := e2)  : unit if e1 : t ref and e2 : t

3.4 Sequence🔗

In OCaml, the semicolon ; is used to sequence expressions. It means “evaluate the first expression for its side effects, discard its result, then evaluate the second expression and return its result.”

e1; e2

‘e1; e2‘ is the same as ‘let () = e1 in e2‘. When evaluating, evaluate e1 to a value ‘v1‘, evaluate ‘e2‘ to a value ‘v2‘, return ‘v2‘. It throws away ‘v1‘ – so ‘e1‘ is useful only if it has side effects, e.g., if it modifies a reference’s contents or accesses a file.

OCaml REPL

let print_both (s, t) = 
    print_string s; 
    print_string t; 
    "Printed s and t";;

[Output]
val print_both : string * string -> string = <fun>

For typechecking, e1;e2 : t if e1 : unit and e2 : t.

Note: Dafny verification may timeout. Bold{;;} versus ‘;‘. ‘;;‘ ends an expression in the top-level of OCaml. Use it to say: “Give me the value of this expression”. It is not used in the body of a function. It is not needed after each function definition.

Grouping Sequences

If you’re not sure about the scoping rules, use begin...end, or parentheses, to group together statements with semicolons

OCaml REPL

let x = ref 0 
    let f () = 
      begin 
        print_string "hello"; 
        x := !x + 1 
      end;; 
 
 let x = ref 0 
    let f () = 
      ( 
        print_string "hello"; 
        x := !x + 1 
      ) 
 ;;

[Output]
val x : int ref = {contents = 0}
val f : unit -> unit = <fun>
val x : int ref = {contents = 0}
val f : unit -> unit = <fun>

Semicolon Examples


1 ; 2 ;;
(* 2 – value of 2nd expression is returned *)   
(1 + 2) ; 4 ;;
(* 4 – value of 2nd expression is returned *)   
1 + (2 ; 4) ;;
(* 5 – value of 2nd expression is returned to 1 + *)
1 + 2 ; 4 ;;
(* 4 – because + has higher precedence than ; *)

3.5 Implement a Counter🔗

OCaml REPL

let counter = ref 0 ;; 
 
 let next = 
      fun () -> counter := !counter + 1; !counter ;; 
 
 next ();; 
 next ();; 
 ;;

[Output]
val counter : int ref = {contents = 0}
val next : unit -> int = <fun>
- : int = 1
- : int = 2

In this implementation, the ‘counter‘ is visible outside the ‘next‘ function. For example:


next ();;
 : int = 1
next ();;
 : int = 2
let _ = count := 0;
next ();;
 : int = 1

The last call to ‘next‘ did not increment the counter, instead returned 1. It is not the preferred behavior of ‘next‘.

To avoid this, we can hide the reference

OCaml REPL

let next = 
    let ctr = ref 0 in 
    fun () -> 
        ctr := !ctr + 1; !ctr;;

[Output]
val next : unit -> int = <fun>

Here is the visulization of hiding the Reference

3.6 The Trade-Off Of Side Effects🔗

Side effects are necessary. That’s usually why we run software! We want something to happen that we can observe. But they also make reasoning harder.

Order of evaluation now matters
No referential transparency. Calling the same function with the same arguments may produce different results
Aliasing may result in hard-to-understand bugs. If we call a function with refs r1 and r2, it might do strange things if r1 and r2 are aliases

Order of Evaluation

Consider this example

OCaml REPL

let y = ref 1;; 
 let f _ z = z+1;;  (* ignores first arg *) 
 let w = f (y:=2) !y;; 
 w;;

[Output]
val y : int ref = {contents = 1}
val f : 'a -> int -> int = <fun>
val w : int = 2
- : int = 2

What is w if f’s arguments are evaluated left to right? 3

What if they are evaluated right to left? 2

In OCaml, the order of evaluation is unspecified. This means that the language doesn’t take a stand, and different implementations may do different things. On Mac, OCaml bytecode interpreter and x86 native code evaluates right to left. You should strive to make your programs produce the same answer regardless of evaluation order.

Quiz: If evaluation order is left to right, rather than right to left? Will ‘w‘’s value differ?


let y   =  ref 1 in
let f z =  z := !z+1; !z in 
let w   =  (f y) + (f y) in
w

Answer: No

Quiz: If evaluation order is left to right, rather than right to left? , will w’s value differ?


let y   =  ref 1 in
let f z =  z := !z+1; !z in 
let w   =  (f y) + !y in
w

Answer: Yes.

Quiz: Which f is not referentially transparent? (I.e., not the case that f x = f y for all x = y) ?


A. let f z =
    let y = ref z in
    y := !y + z;
    !y
B. let f =
    let y = ref 0 in
    fun z -> 
     y := !y + z; !y
C. let f z =
    let y = z in
    y+z
D. let f z = z+1

Answer: B

3.7 Structural vs. Physical Equality🔗

‘=‘ compares objects structurally. ‘<>‘ is the negation of structural equality
‘==‘ compares objects physically. ‘!=‘ is the negation of physical equality


([1;2;3]  =  [1;2;3]) = true    
([1;2;3] <> [1;2;3]) = false 
([1;2;3] == [1;2;3]) = false  
([1;2;3]  != [1;2;3]) = true

We mostly use ‘=‘ and ‘<>‘. E.g., the ‘=‘ operator is used for pattern matching. But ‘=‘ is a problem with cyclic data structures. If a linked list have a cycle, ‘=‘ will not terminate.

Equality of refs

Refs are compared structurally by their contents, physically by their addresses

OCaml REPL

ref 1 = ref 1;;                 (* true *) 
 ref 1 <> ref 2 ;;              (* true *) 
 ref 1 != ref 1;;                (* true *) 
 let x = ref 1 in x == x ;;  (* true *) 
 ;;

[Output]
- : bool = true
- : bool = true
- : bool = true
- : bool = true

3.8 Mutable fields🔗

Fields of a record type can be declared as mutable. For example, here is a record type for students whose field ‘grade‘ is mutable:

OCaml REPL

(* create a record type student with fields name, id, and grade *) 
 type point={name:string; id:int; mutable grade:char};; 
 
 (* create a student record *) 
 let s = {name="john"; id=1234; grade='B'};; 
 
 (* mutate the grade for the student s *) 
 s.grade <- 'A';; 
 s;; 
 ;;

[Output]
type point = { name : string; id : int; mutable grade : char; }
val s : point = {name = "john"; id = 1234; grade = 'B'}
- : unit = ()
- : point = {name = "john"; id = 1234; grade = 'A'}

3.9 Implementing Refs🔗

Ref cells are essentially syntactic sugar for a record type with a mutable fiels called ‘contents‘.

OCaml REPL

type 'a ref = { mutable contents: 'a };; 
 let ref x = { contents = x };; 
 let (!) r = r.contents;; 
 let (:=) r newval = r.contents <- newval;;

[Output]
type 'a ref = { mutable contents : 'a; }
val ref : 'a -> 'a ref = <fun>
val ( ! ) : 'a ref -> 'a = <fun>
val ( := ) : 'a ref -> 'a -> unit = <fun>

‘ref‘ type is declared in Stdlib. ‘ref‘ functions are compiled to equivalents of above.

3.10 Arrays🔗

Arrays generalize ref cells from a single mutable value to a sequence of mutable values

OCaml REPL

let v = [|0.; 1.|];; 
 
 v.(0) <- 5.;; 
 
 v;; 
 ;;

[Output]
val v : float array = [|0.; 1.|]
- : unit = ()
- : float array = [|5.; 1.|]

Arrays Syntax:


[|e1; ...; en|]

It evaluates to an n-element array, whose elements are initialized to v1 … vn, where e1 evaluates to v1, ..., en evaluates to vn Evaluates them right to left

Here is the type checking rule for arrays;


[|e1; …; en|] : t array  If for all i, each ei : t

Random access


e1.(e2)

It evaluate e2 to integer value v2, evaluate e1 to array value v1, If 0 ≤ v2 < n, where n is the length of array v1, then return element at offset v2 of v1 Else raise Invalid_argument exception

Here is the type checking rule for the array access:


 e1.(e2) : t if e1 : t array and e2 : int

Array update


e1.(e2) <- e3

To evaluate array update, you evaluate e3 to v3, evaluate e2 to integer value v2, evaluate e1 to array value v1, if 0 ≤ v2 < n, where n is the length of array v1, then update element at offset v2 of v1 to v3, else raise Invalid_argument exception. It returns ‘()‘.

Here is the type checking rule for the array update:


e1.(e2) <- e3 : unit if e1 : t array and e2 : int and e3 : t

3.11 Control structures🔗

Traditional loop structures are useful with imperative features:


while e1 do e2 done
for x=e1 to e2 do e3 done
for x=e1 downto e2 do e3 done

OCaml REPL

for i = 1 to 5  do 
    Printf.printf "%d " i 
 done;;

[Output]
1 2 3 4 5 
- : unit = ()

3.12 Hashtbl Module🔗

OCaml REPL

let h = Hashtbl.create 1331;; 
 Hashtbl.add h "alice" 100;; 
 Hashtbl.add h "bob" 200;; 
 Hashtbl.iter (Printf.printf "(%s,%d)\n")  h;;

[Output]
val h : ('_weak1, '_weak2) Hashtbl.t = <abstr>
- : unit = ()
- : unit = ()
(bob,200)
(alice,100)
- : unit = ()

3.13 List.assoc as Map🔗

An association list is an easy implementation of a map (aka dictionary)

OCaml REPL

let d = [("alice", 100); ("bob", 200); 
          ("cathy", 300)];; (* (string * int) list *) 
 
 List.assoc "frank" d;;

[Output]
val d : (string * int) list = [("alice", 100); ("bob", 200); ("cathy", 300)]
Exception: Not_found.

3.14 Build a Map Using Functions🔗

Here’s a functional implementation of the Hashmap, which is noticeably simpler than the equivalent version in C or Java.

OCaml REPL

let empty v = fun _-> 0;; 
 let update m k v = fun s->if k=s then v else m s 
 let m = empty 0;; 
 let m = update m "foo" 100;; 
 let m = update m "bar" 200;; 
 let m = update m "baz" 300;; 
 m "foo";; (* 100 *) 
 m "bar";; (* 200 *) 
 let m = update m "foo" 101;; 
 m "foo";; (* 101 *)

[Output]
val empty : 'a -> 'b -> int = <fun>
val update : ('a -> 'b) -> 'a -> 'b -> 'a -> 'b = <fun>
val m : '_weak1 -> int = <fun>
val m : string -> int = <fun>
val m : string -> int = <fun>
val m : string -> int = <fun>
- : int = 100
- : int = 200
val m : string -> int = <fun>
- : int = 101

Challenge: change the code to return all the values for a key

contents ← prev up next →

1	Introduction
2	Functional Programming with OCaml
3	Imperative Programming with OCaml
4	Property-Based Randomized Testing
5	OCaml Regular Expressions
6	Finite Automata
7	Context Free Grammars
8	Parsing
9	Operational Semantics
10	Type Checking
11	Lambda Calculus

3.1	OCaml Imperative Programming
3.2	Immutability vs. Mutability
3.3	Refs
3.4	Sequence
3.5	Implement a Counter
3.6	The Trade-Off Of Side Effects
3.7	Structural vs. Physical Equality
3.8	Mutable fields
3.9	Implementing Refs
3.10	Arrays
3.11	Control structures
3.12	Hashtbl Module
3.13	List.assoc as Map
3.14	Build a Map Using Functions