Before You Code

OCaml Crash Course

This course uses OCaml for all exercises and labs. Before diving into the warm-up exercises, let's build intuition for the key OCaml features you'll use throughout: pattern matching for deconstructing data, algebraic types for modeling domains, and functors for writing generic analysis frameworks.

Why OCaml for Program Analysis?

OCaml is the language of choice for compiler and analysis tool development. Its type system catches bugs at compile time, pattern matching makes AST traversal concise, and algebraic data types let you model complex structures naturally. Many real-world tools — including parts of the Rust compiler, Flow (Facebook's JS type checker), and Infer (Facebook's static analyzer) — are written in OCaml.

Type Safety

The compiler catches missing cases, type mismatches, and unhandled variants at compile time — not at runtime.

Pattern Matching

Destructure complex data in one step. The compiler warns if you miss a case — essential for handling every AST node type.

Modules & Functors

Parameterize code over abstract types. Write one analyzer framework, plug in different domains — sign, interval, taint.

Pattern Matching

Pattern matching is OCaml's superpower. Instead of chains of if-else or switch statements, you destructure values directly. The compiler checks that every case is covered — if you forget a variant, you get a warning.

let describe x =
  match x with
  | 0 -> "zero"
  | 1 -> "one"
  | n when n > 0 -> "positive"
  | _ -> "negative"

describe 0→"zero"

describe 42→"positive"

describe (-3)→"negative"

Algebraic Data Types

Algebraic data types (ADTs) let you define types with variants — each variant can carry different data. This is exactly how ASTs, lattice elements, and analysis results are modeled throughout this course.

Building an Expression Tree

(* Define the type *)
type expr =
  | Num of int
  | Add of expr * expr
  | Mul of expr * expr

(* Build a tree: (2 + 3) * 4 *)
let tree = Mul (Add (Num 2, Num 3), Num 4)

(* Evaluate recursively *)
let rec eval = function
  | Num n -> n
  | Add (a, b) -> eval a + eval b
  | Mul (a, b) -> eval a * eval b

This Pattern Is Everywhere

The same ADT + recursive function pattern appears in every module: AST nodes (M2), CFG blocks (M3), lattice elements (M4), taint values (M5), and finding types (M6). Master it here and it unlocks the entire course.

Exhaustiveness Checking

If you add a Sub variant to expr but forget to handle it in eval, OCaml gives a compile-time warning. This catches bugs that would be silent runtime errors in Python or JavaScript.

Modules & Functors

OCaml modules are like interfaces on steroids. A module type defines a contract (what types and functions must exist), and a functor is a module parameterized by another module — essentially a “function from module to module.” This is how we build domain-generic analyzers in M4-M6.

The Lattice Pattern (Preview)

(* 1. Define the contract *)
module type LATTICE = sig
  type t
  val bottom : t
  val top    : t
  val join   : t -> t -> t
  val meet   : t -> t -> t
end

(* 2. Implement it for signs *)
module SignLattice : LATTICE = struct
  type t = Bot | Neg | Zero | Pos | Top
  let bottom = Bot
  let top = Top
  let join a b = match a, b with
    | Bot, x | x, Bot -> x
    | x, y when x = y -> x
    | _ -> Top
  let meet a b = match a, b with
    | Top, x | x, Top -> x
    | x, y when x = y -> x
    | _ -> Bot
end

(* 3. Build a generic analyzer *)
module MakeAnalyzer (L : LATTICE) = struct
  let analyze env = (* works with ANY lattice! *)
    L.join env L.bottom
end

Why This Matters

In Module 4, you'll implement the ABSTRACT_DOMAIN module type and use the MakeEnv functor to build environments for any domain. In Module 5, the taint lattice plugs into the same framework. The functor pattern means you write the analysis engine once and reuse it for every domain — exactly how real tools work.

Ready to Practice?

You now have a mental model of the OCaml features you'll use throughout this course: pattern matching for AST traversal, algebraic types for modeling domains, and functors for building generic analysis frameworks. Time to practice.

Exercise 1: OCaml Basics

Start with fundamentals: let bindings, tuples, string operations, and basic functions.

Start exercise →

Exercise 2: Types & Recursion

Build your first ADT (a tiny expression tree) and write recursive pattern-matching functions.

Start exercise →