GeezerVison

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)

or iteratively:

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 data type 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, and 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, in contrast 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 functions 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 do what ML does 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

fun center (Circle (c, _)) = c
  | center (Square ((x, y), s)) = (x + s / 2.0, y + s / 2.0)

fun f (Circle ((x, y), r)) = x + y
  | f (Circle _) = 1.0
  | f _ = 0.0

val hasCorners = fn (Circle _) => false | _ => true

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))

The function 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 List.foldl:

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

When 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.

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

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

val q : string TwoListQueue.queue = TwoListQueue.empty
val q' = TwoListQueue.insert (Real.toString Math.pi, q)

(* 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)

The following is a "Hello, World!" program:

print "Hello, world!\n";

$ mlton hello.sml
$ ./hello
Hello, world!

Note the relative ease with which a small expression language can be defined and processed:

exception TyErr;

datatype ty = IntTy | BoolTy

fun unify (IntTy, IntTy) = IntTy
  | unify (BoolTy, BoolTy) = BoolTy
  | unify (_, _) = raise TyErr

datatype exp
    = True
    | False
    | Int of int
    | Not of exp
    | Add of exp * exp
    | If  of exp * exp * exp

fun infer True = BoolTy
  | infer False = BoolTy
  | infer (Int _) = IntTy
  | infer (Not e) = (assert e BoolTy; BoolTy)
  | infer (Add (a, b)) = (assert a IntTy; assert b IntTy; IntTy)
  | infer (If (e, t, f)) = (assert e BoolTy; unify (infer t, infer f))
and assert e t = unify (infer e, t)

fun eval True = True
  | eval False = False
  | eval (Int n) = Int n
  | eval (Not e) = if eval e = True then False else True
  | eval (Add (a, b)) = (case (eval a, eval b) of (Int x, Int y) => Int (x + y))
  | eval (If (e, t, f)) = eval (if eval e = True then t else f)

fun run e = (infer e; SOME (eval e)) handle TyErr => NONE

Example usage on well-typed and ill-typed expressions:

val SOME (Int 3) = run (Add (Int 1, Int 2)) (* well-typed *)
val NONE = run (If (Not (Int 1), True, False)) (* ill-typed *)

The IntInf module provides arbitrary-precision integer arithmetic. Moreover, integer literals may be used as arbitrary-precision integers without the programmer having to do anything.

The following program implements an arbitrary-precision factorial function:

fun fact n : IntInf.int = if n = 0 then 1 else n * fact (n - 1);

fun printLine str = TextIO.output (TextIO.stdOut, str ^ "\n");

val () = printLine (IntInf.toString (fact 120));

$ mlton fact.sml
$ ./fact
6689502913449127057588118054090372586752746333138029810295671352301
6335572449629893668741652719849813081576378932140905525344085894081
21859898481114389650005964960521256960000000000000000000000000000

Curried functions have many applications, such as eliminating redundant code. For example, a module may require functions of type a -> b, but it is more convenient to write functions of type a * c -> b where there is a fixed relationship between the objects of type a and c. A function of type c -> (a * c -> b) -> a -> b can factor out this commonality. This is an example of the adapter pattern.

In this example, fun d computes the numerical derivative of a given function f at point x:

- fun d delta f x = (f (x + delta) - f (x - delta)) / (2.0 * delta)
val d = fn : real -> (real -> real) -> real -> real

The type of fun d indicates that it maps a "float" onto a function with the type (real -> real) -> real -> real. This allows us to partially apply arguments, known as currying. In this case, function d can be specialised by partially applying it with the argument delta. A good choice for delta when using this algorithm is the cube root of the machine epsilon.

- val d' = d 1E~8;
val d' = fn : (real -> real) -> real -> real

The inferred type indicates that d' expects a function with the type real -> real as its first argument. We can compute an approximation to the derivative of $f\left(x\right)=x^3-x-1$ at $x=3$. The correct answer is $f^{\prime }\left(3\right)=27-1=26$.

- d' (fn x => x * x * x - x - 1.0) 3.0;
val it = 25.9999996644 : real

The Basis Library^[9] has been standardized and ships with most implementations. It provides modules for trees, arrays, and other data structures, and input/output and system interfaces.

For numerical computing, a Matrix module exists (but is currently broken), https://www.cs.cmu.edu/afs/cs/project/pscico/pscico/src/matrix/README.html.

For graphics, cairo-sml is an open source interface to the Cairo graphics library. For machine learning, a library for graphical models exists.