OCaml — Types as a Design Tool

Why its own arc, and why before Rust. Arc I asks what the machine does; Arc III asks how work is divided. This arc asks a third question: what can the type system be made to carry? OCaml is the place to ask it, because almost everything that makes Rust's type system feel novel — sum types, exhaustive pattern matching, Option, Result, traits in the shape of typeclasses, inference at the expression level — is ML, and predates Rust by two decades. Read Rust first and those look like Rust's ideas. Read OCaml first and Rust reduces to one genuinely new idea, which is ownership.

Q1 · Origin and niche

OCaml is the working descendant of ML, the language Robin Milner built as the meta-language of the Edinburgh LCF proof assistant around 1980. The lineage is documented by the maintainers themselves in A History of OCaml, and the dates matter because they explain the priorities:

Two things follow. First, OCaml was built by and for people writing compilers and proof tools, and the language is shaped accordingly: fast compilation, exhaustive pattern matching over tree-shaped data, and a module system designed for programs assembled out of interchangeable parts. Second, the object layer that gave the language its name is the part practitioners use least — modules and functors cover most of what classes are for, and the O is largely a historical artifact.

Who pays for it today, from the maintainers' industrial users page: Jane Street runs its trading systems on it at a stated scale of 500+ OCaml programmers and 30M lines of code; Ahrefs runs petabyte-scale web crawling; Bloomberg, LexiFi and SimCorp use it in finance; Tezos is an OCaml blockchain. The other cluster is program analysis, where the type system pays for itself directly: Meta's Flow and Hack, Semgrep, Frama-C, Astrée, and the Rocq (formerly Coq) proof assistant.

The release line is short and fast. OCaml 5.4.1 and 4.14.3 shipped February 2026; OCaml 5.5.0 followed on 19 June 2026, adding module-dependent functions, polymorphic function parameters, a relocatable compiler, and roughly sixty standard-library functions. The 4.14 line is still maintained for code that has not moved to the 5.x runtime — 4.14.4 shipped June 2026 — which is the closest thing OCaml has to an LTS.

Further reading:

• A History of OCaml — the maintainers' own chronology, with the attributions above.
• Robin Milner, A Theory of Type Polymorphism in Programming, JCSS 17(3), 1978 — the origin of the inference algorithm every language in this arc inherits.
• Real World OCaml, Minsky, Madhavapeddy & Hickey — free online, written from Jane Street's practice. The book to read after this track.
• OCaml Changelog — release cadence and what each version actually changed.

Q2 · Hello, build

The canonical toolchain is opam (the package manager, native on Windows since 2.2) plus Dune (the build system). A real project is a dune-project file, a dune file per directory, and dune build / dune exec.

This track uses neither, and the reason is the interesting part of the section.

The official Windows route is winget install Git.Git OCaml.opam followed by opam init, which scans for a Unix environment, creates and manages its own Cygwin installation, and builds a compiler switch. On this machine winget install blocks indefinitely under automation — it wants a session it can raise an elevation prompt from — the same failure the Go track hit. The compiler is also available from MSYS2, which the C track already installed:

pacman -S mingw-w64-ucrt-x86_64-ocaml mingw-w64-ucrt-x86_64-flexdll

That is 28 MB down, 174 MB installed, no elevation, and a complete compiler with no package ecosystem at all. For a stdlib-only program it is sufficient; the first opam install you need, it is a dead end. Which route to take is a real decision, not a shortcut:

What a build is in this toolchain:

  logagg.ml
     │
     ├─ parse ─► typecheck ─► logagg.cmi   (the inferred interface — types only)
     │                        logagg.cmo   (bytecode)  ──► ocamlc  ──► logagg.byte
     │                                                                     │
     │                                                              ocamlrun ◄── runs it
     └───────────────────────► logagg.cmx  (native)    ──► ocamlopt ──► .o ──► flexlink
                                                                              ╳ BLOCKED
                                                          Device Guard policy on this
                                                          machine. See NOTES.md.

Two artifacts matter. The .cmi is the module's interface — the types OCaml inferred, or the ones a hand-written .mli file chose to expose. It is the unit of separate compilation and the thing that makes a .mli a real access-control mechanism rather than a convention. The .cmo/.cmx is the code. OCaml compiles to native code or to bytecode from the same source; this track ships bytecode because the native linker is blocked by machine policy, and the diagram records that rather than hiding it.

OCAMLLIB='C:\msys64\ucrt64\lib\ocaml' \
  ocamlrun ocamlc.byte -w +a-4-9-40-41-42-44-45-70 -o build/logagg.byte logagg.ml
ocamlrun build/logagg.byte ../../bench/data/access.log

-w +a turns on every warning and then subtracts the handful that fire on idiomatic code — 4 (fragile pattern match), 9 (missing record fields in a pattern), 40–45 (constructor and label disambiguation), 70 (missing .mli). Warning 8, non-exhaustive match, stays on and is the one that does the work described in Q5.

Further reading:

• Dune documentation — what a real OCaml build looks like, which this track deliberately does not.
• OCaml on Windows — the official route, including what opam init does to your machine.
• opam 2.2.0 and Windows — how native Windows support was added, and why Cygwin is still in the picture.
• MSYS2 environments — UCRT64 versus MINGW64, the same distinction the C track pinned.

Q3 · Type and memory model

A variable is an immutable binding from a name to a value. Not a memory cell, not a reference slot — a name that is bound once. let x = 5 introduces a new x; it never modifies an old one. Mutation exists, and it is spelled: a mutable record field, a ref cell, an array element. Everything else is fixed at the moment of binding.

logagg.ml splits cleanly along that line, and the split is worth drawing:

  IMMUTABLE (the parsing half)          MUTABLE (the aggregation half)
  ────────────────────────────          ──────────────────────────────
  fields    : string -> string list     stats.count       : mutable int
  classify  : string list -> reason     stats.errors      : mutable int
              option                    stats.sum_micros  : mutable int
  valid_latency, all_digits             stats.max_micros  : mutable int
  parse_micros, fmt_ms, half_up         result.lines/blank/ok
  row, truncate20                       result.malformed  (list, rebuilt)
                                        Hashtbl            (imperative by nature)
                                        t_count/t_errors/t_sum/t_max : int ref

  Every name on the left is bound once. Every name on the right carries the
  keyword that says so. There is no third category, and nothing is mutable by
  accident -- the contrast with Java, where `final` is opt-in and therefore rare.

Typing is static and strong, with Hindley–Milner inference: the types above are not written in the source, they are reconstructed. This is the opposite of the annotation burden people expect from static typing — let half_up num den = if den = 0 then 0 else (num + den / 2) / den is inferred as int -> int -> int because / is integer division, with nothing declared. Where Java makes you write the type and Python makes you skip it, OCaml derives it and then holds you to it.

Three consequences visible in this program:

Sum types make the illegal state unrepresentable. type reason = Fields | Status | Latency has exactly three values. There is no fourth, no empty string, no null. The C track used const char * with NULL meaning "fine"; Go used ""; both encode "no reason" as a value that is also a valid reason's shape. OCaml's reason option makes absence a distinct constructor the compiler tracks.

The pattern is the validation. classify has no arity check:

match f with
| [ _ts; _svc; _meth; _path; status; latency ] -> (* six fields: check them *)
| _ -> Some Fields

A six-element list pattern matches only six-element lists. Destructuring and validating are one operation, and the names status and latency are bound by the same construct that proved they exist.

int is 63 bits, not 64. OCaml's uniform value representation tags every word so the GC can distinguish a pointer from an immediate, and the tag costs one bit:

  63 bits of value                                              tag
  ┌─────────────────────────────────────────────────────────────┬─┐
  │ v v v v v v v v v v v v v v v v v v v v v v v v v v v ... v │1│  immediate int
  └─────────────────────────────────────────────────────────────┴─┘
  ┌───────────────────────────────────────────────────────────────┐
  │ aligned heap address                                        │0│  pointer
  └───────────────────────────────────────────────────────────────┘

  SPEC 2 asks for a 64-bit signed accumulator. This fixture's total is 3.6e7
  micros against a 4.6e18 ceiling, so 63 bits is ample -- but "ample" is a
  measurement, not a guarantee, and Int64 is the exact type. Int64 is BOXED:
  every value is a heap block. The unboxed 63-bit int is the right trade here
  and the wrong one for a program that must round-trip a real int64.

Memory is garbage collected, generational, with a minor heap that makes short-lived allocation close to free — which is what lets the idiomatic style allocate a list of freshly String.sub-ed fields per line without it mattering. Under OCaml 5 each domain has its own minor heap and shares a major heap.

Further reading:

• The OCaml Manual — the core language — inference and pattern matching, worked.
• Milner (1978) and Damas–Milner (1982) — the inference algorithm, if you want the proof rather than the practice.
• Real World OCaml, "Memory Representation of Values" — the tag bit, boxing, and what a record actually is at runtime.

Q4 · The unit of abstraction

The module — and in OCaml the module system is a second language layered over the first, with its own types (module type), its own functions (functor), and its own application. Xavier Leroy's A modular module system (JFP 10(3):269–303, 2000; free PDF) presents it as a component parameterised over the base language — the design is deliberately separable from OCaml itself.

The three pieces:

• Structure (module M = struct … end) — a bundle of values, types, and submodules. Every .ml file is one implicitly, which is why logagg.ml needs no wrapper.
• Signature (module type S = sig … end) — the interface. A .mli file beside a .ml is a signature, and anything absent from it is inaccessible outside the module. Types listed without a definition become abstract: callers cannot see the representation, which is stronger than private because it is a type-level guarantee rather than a visibility rule.
• Functor (module F (X : S) = struct … end) — a function from modules to modules.

The production-scale idiom is the functor, and the standard library's Hashtbl shows it in the shape this program uses. Hashtbl.Make takes a module supplying equal and hash and returns a hash table specialised to that key type. logagg.ml uses the polymorphic interface — Hashtbl.create 16 over string keys — which is the convenient default; a program with a compound key would take the functor and get a table that cannot be given the wrong key type. Both interfaces live in one file, and reading it is the Q9 assignment.

What the module system replaces from Arc II: dependency injection (pass a different module), interface-with-one-implementation (a signature), and most uses of inheritance. OCaml has classes and inheritance — the O in the name — and they are rarely reached for.

Further reading:

• Leroy, A modular module system, JFP 10(3), 2000 — the design, from the person who built it.
• The OCaml Manual — modules and functors.
• Real World OCaml, "Functors" — the industrial patterns, including why Jane Street's Base is built the way it is.

Q5 · The error model

Two mechanisms, used for two different things, and the separation is enforced by taste rather than by the compiler.

Exceptions are OCaml's escape hatch: raise, try … with, cheap to throw, and — like Java's unchecked exceptions and unlike its checked ones — invisible in the type. A function that raises Not_found has the same signature as one that does not. This is the known weak point of the model, and the standard library's response over the last decade has been to add _opt variants of everything: List.find raises, List.find_opt returns 'a option. logagg.ml uses Hashtbl.find_opt and String.index_opt for exactly this reason.

Values are the other half: option for "might be absent" and result for "might have failed, here is why". Both are ordinary sum types with no special status, which is the point — Go's error interface and Rust's Result are the same idea, and OCaml got there first because it had the sum types already.

SPEC 1's ordered reason is where this pays off:

                    classify : string list -> reason option
                                                    │
              ┌─────────────────────────────────────┴────────────────┐
              ▼                                                      ▼
          Some r                                                   None
    ┌────────┴────────┐                                   the six fields are valid
    ▼        ▼        ▼
 Fields   Status   Latency      Adding a fourth reason turns every `match` on
                                `reason` into a compile error -- including
                                reason_to_string, which is where the report
                                text lives. The C track's `const char *` and
                                the Go track's `string` would both have
                                compiled fine and printed nothing.

The comparison across tracks, for the same malformed line 31:

That is the whole argument for this arc, in one row: the difference is not that OCaml has a nicer spelling, it is that the compiler will not let the set of cases and the set of handlers drift apart.

One honest gap, marked in the source. After classify returns None, the caller re-matches the list and needs an assert false branch, because the fact that the list has six elements lives in classify's body and not in its type. Returning a parsed record from classify would remove it. For one call site the assert is the trade; it is the one place in the file where the type system is doing less than it appears to.

Further reading:

• The OCaml Manual — exceptions.
• Stdlib API — the _opt convention, and the comparison warnings quoted in Q8.
• Real World OCaml, "Error Handling" — when to raise and when to return, argued rather than asserted.

Q6 · The concurrency model

Before 5.0, OCaml had a runtime lock: Thread existed, only one thread ran OCaml code, and parallelism meant separate processes. Concurrency meant a monadic library — Lwt or Async — where every I/O-performing function returns a promise and the code is written in >>= chains. That is the same colouring problem async/await produces elsewhere, and it split the ecosystem in two for fifteen years.

OCaml 5 replaced both halves:

• Domains are units of parallelism — roughly one per core, each with its own minor heap, sharing a major heap.
• Effect handlers are units of concurrency: a computation can perform an effect, and a handler up the stack decides what happens, with the continuation reified as a value. Direct-style code becomes non-blocking without changing its type.

The mechanism is documented in Retrofitting Effect Handlers onto OCaml (Sivaramakrishnan, Dolan, White, Kelly, Jaffer, Madhavapeddy — PLDI 2021), and the number that made it shippable is in the abstract: a mean 1% overhead on a macro benchmark suite that does not use effect handlers. Adding a control-flow feature to a twenty-five-year-old runtime for 1% is why this landed in the language rather than in a fork.

For --shard N (SPEC 6) the OCaml shape is domains, not effects — the work is CPU-bound and embarrassingly parallel, which is what domains are for:

              chunks of access.log
        ┌──────────┬──────────┬──────────┐
        ▼          ▼          ▼          ▼
   Domain.spawn ─► own minor heap, own Hashtbl, NO shared mutable state
        │          │          │          │
        └──────────┴────┬─────┴──────────┘
                        ▼
                 Domain.join × N
                        │
                        ▼
            merge : stats -> stats -> stats     (associative, so order is free)
                        │
                        ▼
             the same List.sort as the serial path

   Nothing is locked, because nothing is shared. The merge is where the
   `mutable` fields from Q3 would need care if the partials were shared --
   they are not, so it stays a fold.

What OCaml 5 makes easy to get wrong: the ecosystem is mid-migration. Lwt and Async still work under 5.x and are not parallelism-safe, so a library that transitively pulls in Lwt constrains what you can do with domains. Eio is the effects-based replacement, with Lwt_eio and Async_eio shims for running the old and new side by side. Semgrep's migration write-up is the honest account of what that costs in a real codebase.

Further reading:

• Sivaramakrishnan et al., Retrofitting Effect Handlers onto OCaml, PLDI 2021 — the design and the 1% number.
• Eio — the effects-based I/O stack and its interop story.
• Upgrading Semgrep from OCaml 4 to OCaml 5 — a production migration, including what broke.

Q7 · The idiom test — logagg

logagg.ml · lab notes in NOTES.md

PASS  ocaml

~250 lines, against C's ~330, Java's ~210, Go's ~250, Python's ~190. Where they go:

OCaml lands mid-pack on length, which is the honest result: it has no regex in the stdlib and no Fields, so it pays C-like costs on string handling, and it recovers them on the validation and the sort.

Three decisions only this language forced:

Binary mode on stdout. Fifth track, fifth spelling of the same platform fact:

Int.compare and String.compare, never bare compare. OCaml has a polymorphic structural comparison that works on any type, and it is a trap — see Q8. The code names the type at every comparison, which costs two words and removes the failure mode.

The assert false after a successful classify. Documented in Q5. It is the seam where the value-level refinement and the type-level one disagree.

One verified experiment, mirroring the Go track's. OCaml's Hashtbl can randomise its hash seed — Hashtbl.create ~random:true, or R in OCAMLRUNPARAM globally. Running the fixture three times under OCAMLRUNPARAM=R produced output byte-identical to the golden file every time, because SPEC 3's tie-break makes the bucket order irrelevant. Go found that clause's justification by breaking without it; OCaml confirms it by not breaking with randomisation switched on.

Q8 · How it fails

Ranked by cost to a working programmer, not by how often tutorials mention them.

1. Polymorphic comparison. =, <, and compare work on any type by walking the runtime representation. The Stdlib documentation states the limits plainly: "Equality between functional values raises Invalid_argument" and "Equality between cyclic data structures may not terminate." It also compares abstract types by representation rather than by their intended equality, so two Sets with the same elements built in different orders may compare unequal. Jane Street's Base removes the polymorphic version from scope entirely; this track's convention of naming the type at each comparison is the lighter form of the same defence.
2. = versus ==. = is structural, == is physical identity. The documentation: "Mutable structures are equal if and only if their current contents are structurally equal, even if the two mutable objects are not the same physical object." Reaching for == because it looks like C or Java gives a test that passes for small integers and fails for everything else.
3. Exceptions are invisible in types. Nothing in a signature says a function raises. The _opt convention mitigates it; a library that predates the convention does not.
4. Warning 8 turned off. Non-exhaustive match is a warning by default. A build that does not promote it to an error has discarded the main benefit of the sum types in Q5. -w +a -warn-error +8 in CI, or (flags (:standard -w +a-4-9-40-41-42-44-45-70)) in a dune file.
5. Float arrays and boxing. float is boxed except in a float array or an all-float record, which are specially flattened. A polymorphic container of floats allocates per element. SPEC 2's integer-only rule sidesteps this entirely, which is a second reason the rule was worth having.
6. Operator arity on int vs float. + is integer addition and +. is float addition; there is no overloading. This is a day-one annoyance and a lifetime benefit: the arithmetic in logagg.ml is visibly integer arithmetic, with no implicit widening available to hide a bug in.

The tooling layer — what catches these:

Q9 · Read real code

Read stdlib/hashtbl.ml — the standard library's hash table, and the direct counterpart to the ~60 lines the C track wrote by hand. It is the right file for this series specifically because you have now implemented it once and used it twice.

What to look for:

• The bucket type is a record-in-constructor with mutable fields — Cons of { mutable key; mutable data; mutable next } — which is the C track's struct Node with the next pointer, expressed as a variant.
• resize doubles and rehashes, and is disabled during an active traversal (ongoing_traversal), so that iterating while inserting cannot corrupt the table. The C version had no resize at all; this is what the missing code costs.
• Seed randomisation is real: caml_runtime_hashtbl_randomize, with the PRNG state in domain-local storage so that OCaml 5 domains do not share it. Compare directly against Go's per-run map shuffle in the Go track's Q7.
• Both interfaces coexist in one file: the polymorphic functions, and Make / MakeSeeded as functors over a HashedType. That is Q4's abstraction question answered by the standard library in ~400 lines.

Shorter alternative: stdlib/option.ml — 69 lines, 58 of them code, and it is the whole mechanism Q5 rests on: bind, map, fold, to_result, and a Syntax submodule providing let* and let+. Reading it makes option stop looking like a language feature and start looking like the ordinary sum type it is, with a library on top.

Q10 · What transfers

• Make the illegal state unrepresentable. A closed sum type plus an exhaustive match means the set of cases and the set of handlers cannot drift. Carry it to Rust enum, TypeScript discriminated unions, Java 17 sealed interfaces with pattern matching, and Python Literal types — each is the same idea with a different amount of enforcement, and after this track you can rank them.
• Absence is a constructor, not a value. option instead of null, _opt instead of raising. This is the idea Go's (T, error) pair and Rust's Result implement, and it is why NullPointerException reads as a design failure rather than bad luck once you have used the alternative.
• Inference removes annotations; it does not remove types. The most common misreading of this arc is that OCaml is "dynamic-feeling". It is the opposite: the types are total and checked, and the compiler wrote them down for you. Take the distinction to every argument about var, auto, and gradual typing.
• Parameterise over a module, not over a class. Functors do dependency injection, strategy objects, and generic containers with one construct, checked at compile time. It is the single idea from this track with no close equivalent in any other track in the series, and the one worth revisiting when a Java codebase's interface hierarchy stops making sense.
• Separate concurrency from parallelism, and name which one you have. Domains for cores, effects for interleaving. The distinction is muddled in most languages' vocabulary and OCaml 5 gives you two different words for it, which makes the --shard N design decision a one-line answer rather than an argument.

Status

done — PASS ocaml, byte-exact against the golden file, including under OCAMLRUNPARAM=R. Native compilation is blocked by this machine's Device Guard policy at the flexlink step; the track builds and runs bytecode instead, which is the same accommodation the COBOL lab makes with cobcrun. Details, and the OCAMLLIB trap, in NOTES.md.

Outstanding: --shard N (SPEC 6) with Domain.spawn, which needs native compilation to be worth benchmarking.