|Paradigm||Multi-paradigm: functional, imperative, modular|
|First appeared||1983; 39 years ago (1983)|
Standard ML '97 / 1997; 25 years ago (1997)
|Typing discipline||Inferred, static, strong|
|Alice, Concurrent ML, Dependent ML|
|ML, Hope, Pascal|
|Elm, F#, F*, Haskell, OCaml, Python, Rust, Scala|
Standard ML (SML) is a general-purpose, modular, functional programming language with compile-time type checking and type inference. It is popular among compiler writers and programming language researchers, as well as in the development of theorem provers.
Standard ML is a modern dialect of ML, the language used in the Logic for Computable Functions (LCF) theorem-proving project. It is distinctive among widely used languages in that it has a formal specification, given as typing rules and operational semantics in The Definition of Standard ML.
Standard ML is a functional programming language with some impure features. Programs written in Standard ML consist of expressions as opposed to statements or commands, although some expressions of type unit are only evaluated for their side-effects.
Like all functional languages, a key feature of Standard ML is the function, which is used for abstraction. The factorial function can be expressed as follows:
fun factorial n = if n = 0 then 1 else n * factorial (n - 1)
An SML compiler must infer the static type
val factorial : int -> int without user-supplied type annotations. It has to deduce that
n is only used with integer expressions, and must therefore itself be an integer, and that all terminal expressions are integer expressions.
The same function can be expressed with clausal function definitions where the if-then-else conditional is replaced with templates of the factorial function evaluated for specific values:
fun factorial 0 = 1 | factorial n = n * factorial (n - 1)
fun factorial n = let val i = ref n and acc = ref 1 in while !i > 0 do (acc := !acc * !i; i := !i - 1); !acc end
or as a lambda function:
val rec factorial = fn 0 => 1 | n => n * factorial (n - 1)
Here, the keyword
val introduces a binding of an identifier to a value,
fn introduces an anonymous function, and
rec allows the definition to be self-referential.
The encapsulation of an invariant-preserving tail-recursive tight loop with one or more accumulator parameters within an invariant-free outer function, as seen here, is a common idiom in Standard ML.
Using a local function, it can be rewritten in a more efficient tail-recursive style:
local fun loop (0, acc) = acc | loop (m, acc) = loop (m - 1, m * acc) in fun factorial n = loop (n, 1) end
A type synonym is defined with the keyword
type. Here is a type synonym for points on a plane, and functions computing the distances between two points, and the area of a triangle with the given corners as per Heron's formula. (These definitions will be used in subsequent examples).
type loc = real * real fun square (x : real) = x * x fun dist (x, y) (x', y') = Math.sqrt (square (x' - x) + square (y' - y)) fun heron (a, b, c) = let val x = dist a b val y = dist b c val z = dist a c val s = (x + y + z) / 2.0 in Math.sqrt (s * (s - x) * (s - y) * (s - z)) end
Standard ML provides strong support for algebraic datatypes (ADT). A datatype can be thought of as a disjoint union of tuples (or a "sum of products"). They are easy to define and easy to use, largely because of pattern matching as well as most Standard ML implementations' pattern-exhaustiveness checking and pattern redundancy checking.
In object-oriented programming languages, a disjoint union can be expressed as class hierarchies. However, as opposed to class hierarchies, ADTs are closed. Thus the extensibility of ADTs is orthogonal to the extensibility of class hierarchies. Class hierarchies can be extended with new subclasses which implement the same interface, while the functionality of ADTs can be extended for the fixed set of constructors. See expression problem.
A datatype is defined with the keyword
datatype, as in:
datatype shape = Circle of loc * real (* center and radius *) | Square of loc * real (* upper-left corner and side length; axis-aligned *) | Triangle of loc * loc * loc (* corners *)
Note that a type synonym cannot be recursive; datatypes are necessary to define recursive constructors. (This is not at issue in this example.)
Patterns are matched in the order in which they are defined. C programmers can use tagged unions, dispatching on tag values, to accomplish what ML accomplishes with datatypes and pattern matching. Nevertheless, while a C program decorated with appropriate checks will, in a sense, be as robust as the corresponding ML program, those checks will of necessity be dynamic; ML's static checks provide strong guarantees about the correctness of the program at compile time.
Function arguments can be defined as patterns as follows:
fun area (Circle (_, r)) = Math.pi * square r | area (Square (_, s)) = square s | area (Triangle p) = heron p (* see above *)
The so-called "clausal form" of function definition, where arguments are defined as patterns, is merely syntactic sugar for a case expression:
fun area shape = case shape of Circle (_, r) => Math.pi * square r | Square (_, s) => square s | Triangle p => heron p
Pattern-exhaustiveness checking will make sure that each constructor of the datatype is matched by at least one pattern.
The following pattern is not exhaustive:
fun center (Circle (c, _)) = c | center (Square ((x, y), s)) = (x + s / 2.0, y + s / 2.0)
There is no pattern for the
Triangle case in the
center function. The compiler will issue a warning that the case expression is not exhaustive, and if a
Triangle is passed to this function at runtime,
exception Match will be raised.
The pattern in the second clause of the following (meaningless) function is redundant:
fun f (Circle ((x, y), r)) = x + y | f (Circle _) = 1.0 | f _ = 0.0
Any value that would match the pattern in the second clause would also match the pattern in the first clause, so the second clause is unreachable. Therefore, this definition as a whole exhibits redundancy, and causes a compile-time warning.
The following function definition is exhaustive and not redundant:
val hasCorners = fn (Circle _) => false | _ => true
If control gets past the first pattern (
Circle), we know the shape must be either a
Square or a
Triangle. In either of those cases, we know the shape has corners, so we can return
true without discerning the actual shape.
Functions can consume functions as arguments:
fun map f (x, y) = (f x, f y)
Functions can produce functions as return values:
fun constant k = (fn _ => k)
Functions can also both consume and produce functions:
fun compose (f, g) = (fn x => f (g x))
List.map from the basis library is one of the most commonly used higher-order functions in Standard ML:
fun map _  =  | map f (x :: xs) = f x :: map f xs
A more efficient implementation with tail-recursive
fun map f = List.rev o List.foldl (fn (x, acc) => f x :: acc) 
Exceptions are raised with the keyword
raise and handled with the pattern matching
handle construct. The exception system can implement non-local exit; this optimization technique is suitable for functions like the following.
local exception Zero; val p = fn (0, _) => raise Zero | (a, b) => a * b in fun prod xs = List.foldl p 1 xs handle Zero => 0 end
exception Zero is raised, control leaves the function
List.foldl altogether. Consider the alternative: the value 0 would be returned, it would be multiplied by the next integer in the list, the resulting value (inevitably 0) would be returned, and so on. The raising of the exception allows control to skip over the entire chain of frames and avoid the associated computation. Note the use of the underscore (
_) as a wildcard pattern.
The same optimization can be obtained with a tail call.
local fun p a (0 :: _) = 0 | p a (x :: xs) = p (a * x) xs | p a  = a in val prod = p 1 end
Standard ML's advanced module system allows programs to be decomposed into hierarchically organized structures of logically related type and value definitions. Modules provide not only namespace control but also abstraction, in the sense that they allow the definition of abstract data types. Three main syntactic constructs comprise the module system: signatures, structures and functors.
A signature is an interface, usually thought of as a type for a structure; it specifies the names of all entities provided by the structure as well as the arity of each type component, the type of each value component, and the signature of each substructure. The definitions of type components are optional; type components whose definitions are hidden are abstract types.
For example, the signature for a queue may be:
signature QUEUE = sig type 'a queue exception QueueError; val empty : 'a queue val isEmpty : 'a queue -> bool val singleton : 'a -> 'a queue val fromList : 'a list -> 'a queue val insert : 'a * 'a queue -> 'a queue val peek : 'a queue -> 'a val remove : 'a queue -> 'a * 'a queue end
This signature describes a module that provides a polymorphic type
exception QueueError, and values that define basic operations on queues.
A structure is a module; it consists of a collection of types, exceptions, values and structures (called substructures) packaged together into a logical unit.
A queue structure can be implemented as follows:
structure TwoListQueue :> QUEUE = struct type 'a queue = 'a list * 'a list exception QueueError; val empty = (, ) fun isEmpty (, ) = true | isEmpty _ = false fun singleton a = (, [a]) fun fromList a = (, a) fun insert (a, (, )) = singleton a | insert (a, (ins, outs)) = (a :: ins, outs) fun peek (_, ) = raise QueueError | peek (ins, outs) = List.hd outs fun remove (_, ) = raise QueueError | remove (ins, [a]) = (a, (, List.rev ins)) | remove (ins, a :: outs) = (a, (ins, outs)) end
This definition declares that
structure TwoListQueue implements
signature QUEUE. Furthermore, the opaque ascription denoted by
:> states that any types which are not defined in the signature (i.e.
type 'a queue) should be abstract, meaning that the definition of a queue as a pair of lists is not visible outside the module. The structure implements all of the definitions in the signature.
The types and values in a structure can be accessed with "dot notation":
val q : string TwoListQueue.queue = TwoListQueue.empty val q' = TwoListQueue.insert (Real.toString Math.pi, q)
A functor is a function from structures to structures; that is, a functor accepts one or more arguments, which are usually structures of a given signature, and produces a structure as its result. Functors are used to implement generic data structures and algorithms.
(* after Okasaki, ICFP, 2000 *) functor BFS (Q: QUEUE) = struct datatype 'a tree = E | T of 'a * 'a tree * 'a tree local fun bfsQ q = if Q.isEmpty q then  else search (Q.remove q) and search (E, q) = bfsQ q | search (T (x, l, r), q) = x :: bfsQ (insert (insert q l) r) and insert q a = Q.insert (a, q) in fun bfs t = bfsQ (Q.singleton t) end end structure QueueBFS = BFS (TwoListQueue)
functor BFS, the representation of the queue is not visible. More concretely, there is no way to select the first list in the two-list queue, if that is indeed the representation being used. This data abstraction mechanism makes the breadth-first search truly agnostic to the queue's implementation. This is in general desirable; in this case, the queue structure can safely maintain any logical invariants on which its correctness depends behind the bulletproof wall of abstraction.