Week 0 · Lesson 6

OCaml crash course

You're going to write your compiler in OCaml. This is the subset of the language you need to start, taught with examples that have nothing to do with compilers, so that every line of compiler code is yours.

Which track is this?

This lesson is for the OCaml track. If you picked Python under Language in the sidebar, lesson 0.7 is yours instead, and you can skip this one.

Why the examples are cards and bank accounts

This page teaches the language, not the course. You won't find a UOp type, a parser, or an evaluator here, on purpose. Translating "deck of cards" ideas into "graph of ops" ideas is part of the learning.

Install

Option A: native Windows

opam (OCaml's package manager) 2.2 and later support Windows directly. Do these once, in PowerShell:

winget install Git.Git OCaml.opam
# close this terminal and open a NEW one, so opam is on your PATH
opam init                     # take the defaults, including the "internal Cygwin" option
opam install dune utop ocaml-lsp-server

opam init downloads its own small Unix environment (Cygwin) and builds the OCaml compiler from source, so expect 10 to 30 minutes. If it offers to set up your shell or profile, say yes. If utop fails to build, drop it from the install line. The plain ocaml REPL is enough.

If you said no to the shell setup, run this in every new terminal before using OCaml. It loads opam's PATH settings into that window:

(& opam env) -split '\r?\n' | ForEach-Object { Invoke-Expression $_ }
ocaml -version                # should print a version number

Option B: WSL (Ubuntu inside Windows)

If option A fights you, use WSL. Everything in the OCaml world assumes a Unix shell, and later weeks need clang and CUDA, which also work well there.

wsl --install                 # once, then reboot and open "Ubuntu"
sudo apt update && sudo apt install -y opam clang
opam init -y
eval $(opam env)
opam install -y dune utop ocaml-lsp-server
Running the exercises

The editors in these lessons are graded by python tools/serve.py, which runs ocaml from your PATH. Start it from a terminal where ocaml -version works. With WSL, OCaml lives inside Ubuntu, so run python3 tools/serve.py inside Ubuntu too (your Windows files are under /mnt/c/...). Until OCaml is installed you can borrow it from Docker (this needs Docker Desktop running): python tools/serve.py --ocaml "docker run --rm -i ocaml/opam:alpine-ocaml-5.2 ocaml".

For an editor, use VS Code with the OCaml Platform extension. It uses ocaml-lsp-server to show the type of anything you hover. Turn this on early: in OCaml, the types are the documentation. utop is a REPL where you can try every snippet on this page.

A dune project

dune is the build system. It makes a project skeleton for you:

dune init project words
cd words
dune build                     # compile everything
dune exec words                # run it: prints "Hello, World!" for now
# the binary lands at _build/default/bin/main.exe

You get bin/main.ml (the program), lib/ (a library for the rest of your code), and test/. Every .ml file is automatically a module: lib/deck.ml becomes Deck. dune wraps the library in a module named after it, so from bin/main.ml you call Words.Deck.shuffle, or write open Words at the top and then just Deck.shuffle. Forgetting this is the usual cause of "Unbound module Deck". Arguments for your program go after --, as in dune exec words -- count notes.txt. The count example near the end of this page is what makes that one work.

Warnings are errors in dev builds

dune's default profile turns some warnings into errors, including an unused variable. That's annoying for the first hour and very useful after that. Prefix a name with _ to say "unused on purpose".

Values and functions

let binds a name to a value. Names never change. Functions are values too, and you call them without parentheses or commas.

let tax_rate = 0.08
let with_tax price = price *. (1.0 +. tax_rate)    (* float ops end in a dot *)
let rec factorial n = if n <= 1 then 1 else n * factorial (n - 1)

let () = Printf.printf "%.2f %d\n" (with_tax 10.0) (factorial 5)   (* 10.80 120 *)

Integers use + - * / and floats use +. -. *. /.. There's no automatic conversion. 1 + 1.0 is a type error, and you write float_of_int 1 +. 1.0. Recursive functions need let rec. let () = ... is how you write "run this when the program starts".

Syntax you'll see in every starter

Each line below runs. Paste them into utop and check: area is 12, double 5 is 10, first pair is 1, show (safe_div 7 2) is "3", show (safe_div 1 0) is "none", add 2 3 is 5, greeting is "hello, world", and c1 and c2 are 1 and 2.

let area = let w = 3 in let h = 4 in w * h       (* let ... in: a name used only in what follows *)
let double = fun x -> 2 * x                       (* fun: a function with no name *)
let pair : int * string = (1, "one")              (* a tuple; its type is written with * *)
let first (a, _) = a                              (* taking a tuple apart *)
let safe_div a b = if b = 0 then None else Some (a / b)   (* type: int -> int -> int option *)
let show o = match o with Some v -> string_of_int v | None -> "none"
let counter = ref 0
let () = counter := !counter + 1                  (* := sets a ref, ! reads it *)
let add (x : int) (y : int) : int = x + y         (* optional type annotations *)
let greeting = "hello, " ^ "world"                (* ^ joins strings *)
let make_counter () = let n = ref 0 in fun () -> incr n; !n   (* returns a function *)
let next = make_counter ()
let c1 = next ()
let c2 = next ()

An option is either Some value or None: OCaml's way of saying "maybe a result". A type like card list -> int reads "a function from a list of cards to an int". The last three lines show a function that returns a function: each call to make_counter () makes its own private n.

Variants and pattern matching

This is the feature you're choosing OCaml for. A variant type lists every shape a value can have, and each shape can carry data. match takes a value apart by its shape.

type suit = Hearts | Diamonds | Clubs | Spades
type card =
  | Number of int * suit        (* 2 through 10 *)
  | Jack of suit | Queen of suit | King of suit
  | Ace of suit

let points card =
  match card with
  | Number (n, _) -> n
  | Jack _ | Queen _ | King _ -> 10
  | Ace _ -> 11

let suit_of = function            (* "function" is shorthand for fun x -> match x with *)
  | Number (_, s) | Jack s | Queen s | King s | Ace s -> s

let is_red c = match suit_of c with Hearts | Diamonds -> true | Clubs | Spades -> false

(* guards with "when", and nested patterns *)
let describe = function
  | Number (n, Hearts) when n >= 9 -> "a high heart"
  | Ace Spades -> "the ace of spades"
  | _ -> "some card"

Each | line in the type is a constructor. Number of int * suit means the Number constructor carries a pair: an int and a suit (here * means "and", not multiplication).

The compiler checks that every match covers every case. Add a Joker constructor and every match that forgot about it gets a warning that points at the line. When your types grow all semester, this is what keeps old code honest.

The catch-all hides new cases

A final | _ -> ... case matches everything, including constructors you add next month, so the exhaustiveness check can't help you there anymore. Use _ on purpose, not by habit.

Records, mutation, exceptions

A record is a struct with named fields. Fields are immutable unless you mark them mutable. An exception can carry data and is caught with try ... with, which pattern matches just like match.

type account = { owner : string; mutable balance : int }
exception Insufficient_funds of int

let withdraw acct amount =
  if amount > acct.balance then raise (Insufficient_funds (amount - acct.balance));
  acct.balance <- acct.balance - amount

let () =
  let a = { owner = "Sam"; balance = 100 } in
  withdraw a 30;
  (try withdraw a 500 with Insufficient_funds short -> Printf.printf "short by %d\n" short);
  Printf.printf "%s has %d\n" a.owner a.balance

; sequences two expressions and <- assigns a mutable field. A single mutable variable is a ref: let count = ref 0 in incr count; !count. Prefer immutable data, and reach for mutation when it actually makes the code simpler.

Lists and arrays

Lists are immutable and singly linked, written [a; b; c] (semicolons, not commas). Arrays are fixed size, mutable, and indexed with a.(i).

type task = { title : string; finished : bool }    (* "done" is a keyword *)
let todos = [ { title = "buy milk"; finished = true };
              { title = "call the bank"; finished = false };
              { title = "water plants"; finished = false } ]

let left = todos |> List.filter (fun t -> not t.finished) |> List.map (fun t -> t.title)
let n_done = List.fold_left (fun acc t -> if t.finished then acc + 1 else acc) 0 todos

let rec total = function [] -> 0 | x :: rest -> x + total rest    (* matching on a list *)

let scores = Array.make 5 0
let () = scores.(2) <- 7; Printf.printf "%d %d\n" (Array.length scores) scores.(2)   (* 5 7 *)

|> pipes a value into a function: x |> f |> g is g (f x). x :: rest is the pattern for "first element, then the rest".

Blackjack hand value

Using the card type above, write hand_value : card list -> int. Numbers are worth their number, faces 10, and an Ace 11. But while the total is over 21, an Ace may count as 1 instead, one Ace at a time.

Pattern match for the points, then fold with List.fold_left (shown just above). Keep the types in the starter exactly as they are: the tests build cards with those constructors.

A recursive type: a tree of words

Variants can refer to themselves. Here's a binary search tree of strings. Smaller words go left, bigger ones go right, and you never change a tree. insert builds a new one that shares the untouched branches with the old one.

type tree = Leaf | Node of tree * string * tree

let rec insert w t =
  match t with
  | Leaf -> Node (Leaf, w, Leaf)
  | Node (l, x, r) ->
    if w < x then Node (insert w l, x, r)
    else if w > x then Node (l, x, insert w r)
    else t                                       (* already there *)

let rec to_list = function Leaf -> [] | Node (l, x, r) -> to_list l @ [x] @ to_list r

let t = List.fold_left (fun t w -> insert w t) Leaf ["pear"; "apple"; "zebra"; "mango"; "kiwi"]

Hashtbl and equality

Hashtbl is a mutable hash table. It uses structural hashing and equality by default, so it works with any key type.

let counts : (string, int) Hashtbl.t = Hashtbl.create 64

let see word =
  let n = Option.value ~default:0 (Hashtbl.find_opt counts word) in
  Hashtbl.replace counts word (n + 1)

let () =
  List.iter see ["kiwi"; "pear"; "kiwi"];
  Hashtbl.iter (fun w n -> Printf.printf "%s: %d\n" w n) counts   (* order is not guaranteed *)

~default:0 is a labelled argument: you pass it by name. Hashtbl.find_opt returns an option, and Option.value ~default:0 turns None into 0.

OCaml has two equalities. a = b is structural: it walks both values and compares everything inside, which can take as long as the values are big. a == b is physical: it asks whether they're the very same object in memory, which is one pointer comparison. Remember this distinction. It matters in week 1.

Hashtbl.hash doesn't look at everything

The default hash only looks at a limited number of nodes inside a value, about ten meaningful ones. Two big values that differ deep inside can hash the same, and they're still told apart correctly by =, just slowly. If you ever key a table on large nested values, think about what you're actually hashing.

The k most common words

Write top_words : int -> string list -> (string * int) list. Count every word, then return the k most frequent as (word, count) pairs: higher counts first, and ties broken alphabetically (plain compare on strings, so "A" sorts before "a"). If there are fewer than k distinct words, return them all.

Tools: Hashtbl to count, Hashtbl.fold to get a list out, List.sort with your own comparison, and List.filteri to take a prefix.

Modules

A module groups related types and functions. Each file is one module, and you can nest more with module Name = struct ... end. A .mli file next to a .ml file lists what the module exposes. Anything not listed is private.

module Deck = struct
  let suits = [Hearts; Diamonds; Clubs; Spades]
  let full = List.concat_map
      (fun s -> List.init 9 (fun i -> Number (i + 2, s)) @ [Jack s; Queen s; King s; Ace s]) suits
end

let () = Printf.printf "%d cards\n" (List.length Deck.full)   (* 52 cards *)

Integers: the trap for this course

OCaml's plain int is 63 bits on a 64-bit machine. One bit is used internally to tell integers apart from pointers. So max_int is 262 − 1 = 4,611,686,018,427,387,903, and 2147483647 + 1 is just 2147483648. It does not wrap at 32 bits.

The language you're compiling has a 32-bit i32 that must wrap. The Int32 module gives you true 32-bit integers. Literals end in l.

let a = Int32.max_int                 (* 2147483647l *)
let b = Int32.add a 1l                (* -2147483648l: wrapped *)
let c = 2147483647 + 1                (* 2147483648: a plain int did not *)
let () = Printf.printf "%ld %ld %d\n" a b c

(* the other Int32 operations you'll want: *)
(* Int32.mul  Int32.div  Int32.rem  Int32.logxor  Int32.shift_left
   Int32.compare  Int32.of_int  Int32.to_int  Int32.to_float  Int32.of_float *)

Int32.div and Int32.rem truncate toward zero, like C, and raise Division_by_zero on zero. Int32.of_int keeps the low 32 bits. Int32.of_float truncates, and its result is unspecified for NaN or anything out of range, so check those cases yourself. Read the docs for each function before you use it. The exact edge-case behavior is what the tests check.

You can also keep using plain int and normalize to 32 bits after every operation. Either way works. Pick one and be consistent.

C-style 32-bit division

Write div32 a b for i32 values held in plain ints: truncate toward zero, wrap to 32 bits, and raise Division_by_zero when b = 0. (Lesson 1.2 has a variant that returns an option instead of raising.)

OCaml's / already truncates toward zero, so the starter is almost right. Exactly one i32 quotient doesn't fit in 32 bits. Which one?

Floats are doubles

OCaml's float is a 64-bit double. The course's f32 is single precision. To round a double to the nearest single, convert it to the 32-bit encoding and back:

let to_f32 x = Int32.float_of_bits (Int32.bits_of_float x)
let () = Printf.printf "%.17g\n%.17g\n" 0.1 (to_f32 0.1)
(* 0.10000000000000001
   0.10000000149011612 *)

Int32.bits_of_float rounds to single precision and gives you its 32 bits. Int32.float_of_bits reads them back as a double holding that exact single value. Comparisons on floats follow IEEE: nan = nan is false. Test for NaN with Float.is_nan.

Is it already an f32?

Write is_f32 : float -> bool: true when the double x is exactly representable in single precision. NaN and the infinities count as representable.

Round it with the trick above and compare. Then check what your answer says about nan.

Files, arguments, exit codes

let () =
  match Sys.argv with
  | [| _; "count"; path |] ->
    let lines = In_channel.with_open_text path In_channel.input_lines in
    Printf.printf "%d lines\n" (List.length lines);
    exit 0
  | _ ->
    prerr_endline "usage: words count FILE";     (* stderr *)
    exit 2

Sys.argv.(0) is the program name. exit n ends the program with status n, which is how the course's test runner learns whether a test passed. [| _; "count"; path |] matches an array of exactly three elements. prerr_endline prints a line to stderr, and Printf.eprintf prints formatted text to stderr. In_channel.input_lines needs OCaml 5.1 or newer, which any fresh install has. (Splitting the whole text on '\n' instead overcounts by one when the file ends with a newline.)

Capstone: the toposort from lesson 0.3

Toposort a tiny DAG, in OCaml

This is lesson 0.3's toposort, now that you have the language. A graph is a list of records { name : string; srcs : string list }, each name appearing once. Write topo graph root: every name reachable from root, each exactly once, in depth-first post-order. Visit a node's srcs left to right, then emit the node itself.

For (a + b) * (a + b) that's ["a"; "b"; "add"; "mul"]. Nodes not reachable from root are left out. One hidden test is the 31-level doubling DAG from lesson 0.3's trap, so remember what you've visited.

OCaml hints

List.find (fun n -> n.name = x) graph looks a node up (it raises Not_found if nothing matches). A Hashtbl remembers what you've seen. Build the output in a ref list with out := x :: !out, then List.rev it at the end.

Check yourself

On 64-bit OCaml, what is max_int?

OCaml ints are not quite 64 bits. One bit is used for something else.

If the int has 63 bits and one of them is the sign, what is the largest positive value?

63-bit ints, so the top value is 262 − 1. One bit tags integers so the garbage collector can tell them from pointers.

Predict the value of Int32.add Int32.max_int 1l.

The Int32 module wraps around at 32 bits, like C's int32_t.

Adding 1 to the largest 32-bit value goes to the other end of the range. Remember the l suffix.

Int32 wraps at 32 bits, so it becomes Int32.min_int, -2147483648l.

What happens with let x = 1 + 1.0?

Look at the types of the two operands. Does OCaml ever convert between int and float for you?

No implicit conversion. The course's IR works the same way: add on an i32 and an f32 is a type error.

In the bank account example, what does the last line print?

Trace the balance through each withdrawal. Does the failing withdrawal change the balance before it raises?

The last line uses "%s has %d\n".

The 30 withdrawal succeeds (100 → 70). The 500 one raises before it changes anything, prints "short by 430", and the balance stays 70.

Predict: [1; 2; 3] |> List.map (fun x -> x * 2)

|> passes the list on the left as the last argument to the function on the right.

Answer in OCaml list syntax, with semicolons.

[2; 4; 6].

let a = List.init 3 (fun i -> i) and let b = List.init 3 (fun i -> i). What are a = b and a == b?

= compares contents. == asks whether two values are the same object in memory.

Were the two lists built separately?

Same contents, so structurally equal. They're two separately built lists, so they aren't physically equal. If you had a way to guarantee that equal values are always the same object, == would be enough. Hold that thought until week 1.

After inserting "pear", "apple", "zebra", "mango", "kiwi", what does to_list t return?

A binary search tree keeps smaller words on the left and larger ones on the right. What order does an in-order walk visit them in?

An in-order walk of a binary search tree visits the words in sorted order.

You add | Joker to the card type and rebuild. What happens to points?

Pattern matches are checked for exhaustiveness at compile time. What does the compiler do when a case is missing?

This is the safety net. Every function that takes apart a card gets flagged.

Code it

Wrap a native int to 32 bits

OCaml's int is 63 bits, but your compiler's i32 wraps at 32. Write wrap32 x: the signed 32-bit value with the same low 32 bits as x.

Two roads: the Int32 module, or bit operations (land, lsl, asr).