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 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:

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"}

!t reads the value stored in reference.

OCaml REPL

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

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

t := e changes the value stored in 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.

3.3.1 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: ;; 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.

3.4.1 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🔗

In OCaml, variable bindings are immutable by default. You can’t do this:

let counter = 0;;
counter = counter + 1  (* This is a comparison, not assignment! Returns false *)

Therefore, let counter = 0 is a permanent binding. There is no way to update it. The = operator is equality checking, not assignment.

So if you want state that changes over time (like a counter that remembers its value between calls), you need ref to opt into mutability explicitly.

This reflects OCaml’s functional-first philosophy: immutability is the default (safer, easier to reason about), and mutation is available but you have to ask for it explicitly with ref, !, and :=.

In this section, we will implement a counter, which generates a unique value every time it is called.

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 using a closure. Here is a refined version of the previous counter. The key difference is ctr is now local to next, hidden via a closure.

OCaml REPL

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

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

Here’s what happens step by step:

let ctr = ref 0 in ... — Creates the ref cell, but scoped inside the let ... in expression. Nobody outside can access ctr directly.
fun () -> ctr := !ctr + 1; !ctr — Returns a closure (a function that "captures" ctr from its environment).
let next = ... — next is bound to that returned closure. The let ... in is evaluated once, so only one ctr is ever created.

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

3.6.1 Order of Evaluation🔗

To understand the order of evaluation, let us look at a C example:

int x = 10;
foo(x++, ++x)

If C evaluation order is left to right, then x++ will be evaluated before ++x. The first argument x++ returns 10 (then increments x to 11), and ++x increments x to 12 (then returns 12). In this case, foo is called with foo(10, 12).

If C evaluation order is right to left, then ++x will be evaluated before x++. The argument ++x increments x to 11 (then returns 11), and x++ returns 11 (then increments x to 12). In this case, foo is called with foo(11, 11).

Clearly, order of evaluation matters.

So far in OCaml, we did not have to worry about evaluation order. When everything is immutable, evaluation order does not matter. But now that we have introduced ref, evaluation order becomes important. 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

If f’s arguments are evaluated left to right, the w=3.
If f’s arguments are evaluated right to left, the w=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.

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
Yes
No

Answer: No. Both (f y) calls mutate y and read it. Regardless of which side is evaluated first, both calls to f increment y and return the new value. The sum is the same either way because both subexpressions have the same side effect.

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
Yes
No

Answer: Yes. The value of !y depends on whether f y has already been evaluated. If left to right, f y runs first (incrementing y to 2), then !y reads 2, giving 2 + 2 = 4. If right to left, !y reads 1 first, then f y increments and returns 2, giving 2 + 1 = 3.

Which f is not referentially transparent? (i.e., it is not the case that f x = f y for all x = y)
let f z = let y = ref z in y := !y + z; !y
let f = let y = ref 0 in fun z -> y := !y + z; !y
let f z = let y = z in y + z
let f z = z + 1

Answer: B. In B, y is a ref created once when f is defined, and shared across all calls. Each call to f accumulates into y, so f 1 returns 1 the first time but 2 the second time. The other functions create fresh local state (A) or use no mutation (C, D), so they always return the same result for the same input.

3.7 Structural vs. Physical Equality🔗

In OCaml, there are two kinds of equality:Structural equality and 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.

3.7.1 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 Optional Reading: 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 Optional Reading: 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 Optional Reading: Build a Map Using Functions🔗

Here’s a functional implementation of the Hashmap. The 2-line code 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

3.15 Optional Reading: State Monad🔗

A state monad is a pattern for managing state in pure functions without using mutation. Rather than modifying a variable directly, each function takes the current state as input and returns both a result and an updated state as output. This is the approach Haskell uses to model mutable state.

Monads are beyond the scope of CMSC330. Here, we present a simple example that reimplements the next function from the previous section using a state monad. The ids function takes an integer argument and returns a list of three consecutive integers starting from that value.

type state = int -> int * int;;

let return x s = (x, s);;

let bind m f s =
  let x, s' = m s in
  f x s';;

let ( let* ) = bind;;
let next : state = fun s -> (s, s + 1);;

let ids =
    let* a = next in
    let* b = next in
    let* c = next in
    return [a;b;c;];;

(* create a list of 3 ids starting from 10 *)
ids 10;;
(* - : int list * int = ([10; 11; 12], 13) *)

contents ← prev up next →

1	Introduction
2	Functional Programming with OCaml
3	Imperative Programming with OCaml
4	Property-Based Randomized Testing (PBT)
5	Regular Expressions
6	Finite Automata
7	Context Free Grammars
8	Parsing
9	Operational Semantics
10	Type System
11	Rust
12	Exercises

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	Optional Reading: Arrays
3.11	Optional Reading: Control structures
3.12	Hashtbl Module
3.13	List.assoc as Map
3.14	Optional Reading: Build a Map Using Functions
3.15	Optional Reading: State Monad