The ML family

Robin Milner created ML at Edinburgh in the early 1970s. The name is short for Meta Language: ML was the language for writing the tactics that drove LCF (Logic for Computable Functions), an interactive proof assistant. The type system carried a heavy load — it made theorem an abstract type whose values could be produced only by the rules of the logic, so the type checker itself guaranteed that anything of type theorem had actually been proved.

That setting shaped the language. ML was functional, it had algebraic datatypes and pattern matching to take them apart, and — the part that travelled furthest — it had a type system with full inference, so the programmer wrote tactics without spelling out types and the compiler filled them in.

The type system Milner reached for had also been found, independently, by the logician J. Roger Hindley (1969); Milner published his account in 1978, A Theory of Type Polymorphism in Programming, and the inference algorithm — Algorithm W — was set out by Luis Damas and Milner in 1982. Hence Hindley–Milner, and the algorithm is often called Damas–Milner.

It delivers three things at once: full type inference (a type is rarely written down), parametric polymorphism (a function over 'a works for every type), and soundness — Milner's slogan, well-typed programs do not go wrong. Select an expression below to see the most general type the algorithm assigns it.

The ML family tree below shows where the inference travelled. From Milner's ML, two lines branch: Standard ML, formally specified, and the French Caml/OCaml line from INRIA — the dialect F# most resembles.

Standard ML is the formally defined member of the family. The Definition of Standard ML — by Milner, Tofte, and Harper, 1990, revised 1997 — specifies the language down to its operational semantics, a rare degree of rigour. SML gives the family its module system with functors, its datatypes, and pattern matching.

The other line is French. Caml grew at INRIA in the mid-1980s; it led through Caml Light to Objective Caml, or OCaml, released in 1996 (Xavier Leroy and colleagues), which added an object system and a fast native-code compiler. OCaml is the dialect F# most directly resembles in syntax and core semantics — the next dive is about how F# put that core on .NET.

The first dive made functions first-class. This one made them typed — without making a programmer write the types. Hindley–Milner inference, parametric polymorphism, datatypes, and pattern matching are the ML family's gift, and F# takes them whole through OCaml.

The last dive in this module, C0.1.3, is about the move that made F# its own language: OCaml's core retargeted to the .NET runtime, with full access to the platform's libraries.