Standard ML

Standard ML (SML) is a general-purpose, modular, functional programming language with compile-time type checking and type inference. It is one of the most influential programming languages ever designed, having directly shaped the development of OCaml, Haskell, F#, Rust, and many other modern languages.

History & Origins

Standard ML’s story begins with ML (Meta Language), created by Robin Milner at Stanford University in 1972 as the meta-language for the LCF (Logic for Computable Functions) theorem prover. What started as a scripting language for proofs became recognized as a powerful programming language in its own right.

The Road to Standardization

In the late 1970s and early 1980s, ML implementations began to diverge. Luca Cardelli created the first standalone ML compiler in 1980-81, and the Hope language at Edinburgh introduced new ideas like algebraic data types. By 1983, Milner recognized the need for a standard, and began work on what would become Standard ML.

Key Contributors:

• Robin Milner - The original designer of ML and leader of the standardization effort
• Mads Tofte - Co-author of the Definition, developed the module system semantics
• Robert Harper - Co-author of the Definition, developed type theory foundations
• David MacQueen - Co-author of the 1997 revision, co-created SML/NJ

The Definition

Unlike most languages defined by implementation, Standard ML is defined by a formal semantics document: The Definition of Standard ML. The original 1990 Definition and the 1997 Revised Definition provide a rigorous mathematical specification of the language, making SML one of the few languages with a complete formal definition.

Major Implementations

Standard ML of New Jersey (SML/NJ) - The reference implementation, developed at Bell Labs and Princeton. Known for its interactive environment and extensive library support. Still actively maintained with version 110.99.9 released in 2025.

MLton - A whole-program optimizing compiler that produces highly efficient native code. MLton performs aggressive inlining, unboxing, and defunctionalization, often producing executables that rival hand-written C.

Moscow ML - A lightweight implementation based on the Caml Light runtime, popular for teaching.

Poly/ML - Known for its parallel garbage collector and large address space support.

What Makes Standard ML Different

1. Hindley-Milner Type Inference

SML pioneered type inference - the compiler deduces types without explicit annotations:

1
2
3
4
5
6
7
8
9

(* The compiler infers: int -> int -> int *)
fun add x y = x + y

(* The compiler infers: 'a list -> int *)
fun length [] = 0
  | length (_::xs) = 1 + length xs

(* Polymorphic: 'a -> 'a -> bool *)
fun same x y = (x = y)

2. Algebraic Data Types and Pattern Matching

Define structured data and process it elegantly:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

(* Define a binary tree *)
datatype 'a tree = Empty
                 | Node of 'a * 'a tree * 'a tree

(* Pattern match to process it *)
fun sumTree Empty = 0
  | sumTree (Node(value, left, right)) =
      value + sumTree left + sumTree right

(* The compiler warns about incomplete patterns! *)

3. The Module System

SML’s module system is considered one of its greatest contributions to programming language design:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

(* Signature: defines an interface *)
signature STACK = sig
  type 'a stack
  val empty : 'a stack
  val push : 'a * 'a stack -> 'a stack
  val pop : 'a stack -> ('a * 'a stack) option
end

(* Structure: implements the signature *)
structure ListStack :> STACK = struct
  type 'a stack = 'a list
  val empty = []
  fun push (x, s) = x :: s
  fun pop [] = NONE
    | pop (x::xs) = SOME (x, xs)
end

Functors allow parameterizing modules over other modules:

1
2
3
4
5
6
7

(* A functor that adds logging to any stack *)
functor LoggedStack(S: STACK) :> STACK = struct
  type 'a stack = 'a S.stack
  val empty = (print "Creating empty stack\n"; S.empty)
  fun push (x, s) = (print "Pushing\n"; S.push(x, s))
  fun pop s = (print "Popping\n"; S.pop s)
end

4. Strict Evaluation with Explicit Effects

Unlike Haskell, SML uses strict (eager) evaluation, making side effects predictable:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

(* Side effects happen in order *)
fun greet name = (
  print "Hello, ";
  print name;
  print "!\n"
)

(* Mutable references when needed *)
val counter = ref 0
fun increment () = (counter := !counter + 1; !counter)

5. Exception Handling

SML has a robust exception system:

1
2
3
4
5
6
7
8

exception DivisionByZero
exception NotFound of string

fun safeDivide _ 0 = raise DivisionByZero
  | safeDivide x y = x div y

val result = safeDivide 10 2
             handle DivisionByZero => 0

The Basis Library

Standard ML comes with a standard library called the Basis Library, providing:

• Core Types: Int, Real, String, Char, Bool
• Collections: List, Array, Vector
• I/O: TextIO, BinIO
• OS Interface: OS.FileSys, OS.Process
• Utilities: Option, Result, StringCvt

1
2
3
4

(* Using the Basis Library *)
val lines = TextIO.inputAll (TextIO.openIn "file.txt")
val words = String.tokens Char.isSpace lines
val count = List.length words

Why Standard ML Matters

Influence on Modern Languages

• OCaml - Direct descendant, added objects and native compilation
• Haskell - Adopted type classes instead of modules, added laziness
• F# - Microsoft’s functional language for .NET, heavily SML-influenced
• Rust - Pattern matching, type inference, and algebraic data types
• Elm - Simplified SML for web programming
• Scala - Module system influenced by SML functors

Academic Impact

Standard ML transformed computer science education. The Definition showed that programming languages could be specified with mathematical precision, spawning the field of programming language theory.

CMU’s influential courses, MIT’s programming language courses, and countless others use SML to teach:

• Functional programming principles
• Type systems and type inference
• Module systems and abstraction
• Formal semantics

Compiler Implementation

SML is uniquely suited to writing compilers:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

(* A tiny expression language *)
datatype exp = Int of int
             | Var of string
             | Plus of exp * exp
             | Times of exp * exp

(* Evaluate expressions *)
fun eval env (Int n) = n
  | eval env (Var x) = lookup env x
  | eval env (Plus(e1, e2)) = eval env e1 + eval env e2
  | eval env (Times(e1, e2)) = eval env e1 * eval env e2

The pattern matching and algebraic data types make manipulating abstract syntax trees natural and safe.

Getting Started

File Structure

SML source files use the .sml extension. A simple program:

1
2
3

(* hello.sml *)
val greeting = "Hello, World!"
val () = print (greeting ^ "\n")

The REPL

SML implementations provide interactive environments:

- 1 + 2;
val it = 3 : int

- fun double x = x * 2;
val double = fn : int -> int

- double 21;
val it = 42 : int

- map double [1, 2, 3];
val it = [2, 4, 6] : int list

The - is the SML prompt. Expressions are terminated with ;.

Compilation

1
2
3
4
5
6

# Interactive mode (SML/NJ)
sml hello.sml

# Compile to executable (MLton)
mlton hello.sml
./hello

A Complete Example

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

(* Word frequency counter *)

structure WordCount = struct
  (* Use a simple association list *)
  type 'a counter = (string * int) list

  fun increment word [] = [(word, 1)]
    | increment word ((w, c)::rest) =
        if w = word then (w, c + 1) :: rest
        else (w, c) :: increment word rest

  fun count words =
    foldl (fn (w, acc) => increment w acc) [] words

  fun toString counts =
    String.concatWith "\n"
      (map (fn (w, c) => w ^ ": " ^ Int.toString c) counts)
end

val text = "the quick brown fox jumps over the lazy dog the"
val words = String.tokens Char.isSpace text
val counts = WordCount.count words
val () = print (WordCount.toString counts ^ "\n")

The SML Community

Resources

• SML Family GitHub - smlfamily.github.io
• SML/NJ Website - smlnj.org
• MLton Website - mlton.org
• The Definition - Available as PDF and in print

Learning Path

1. Programming in Standard ML - Robert Harper’s free textbook
2. ML for the Working Programmer - Paulson’s classic text
3. The Definition of Standard ML - The formal specification
4. Purely Functional Data Structures - Okasaki’s thesis (in SML)

Standard ML vs Similar Languages

Continue to the Hello World tutorial to write your first Standard ML program.