ML

ML is a general-purpose functional programming language developed by Robin Milner and others in the early 1970s at the University of Edinburgh,^[1] whose syntax is inspired by ISWIM. It has roots in the Lisp language, and has been characterized as "LISP with types". Historically, ML stands for MetaLanguage: it was conceived to develop proof tactics in the LCF theorem prover (whose language, pplambda, a combination of the first-order predicate calculus and the simply-typed polymorphic lambda calculus, had ML as its metalanguage). It is known for its use of the Hindley–Milner type system, whose type inference algorithm can automatically assign the types of most expressions without requiring explicit type annotations. Additionally, the use of this algorithm ensures type safety – there is a formal proof that a well-typed ML program does not cause runtime type errors.^[2]

The following examples use the syntax of Standard ML. The other most widely used ML dialect, OCaml, differs in various insubstantial ways.

Factorial[edit]

The factorial function expressed as pure ML:

fun fac (0 : int) : int = 1
  | fac (n : int) : int = n * fac (n - 1)

This describes the factorial as a recursive function, with a single terminating base case. It is similar to the descriptions of factorials found in mathematics textbooks. Much of ML code is similar to mathematics in facility and syntax.

Part of the definition shown is optional, and describes the types of this function. The notation E : t can be read as expression E has type t. For instance, the argument n is assigned typeinteger (int), and fac (n : int), the result of applying fac to the integer n, also has type integer. The function fac as a whole then has type function from integer to integer (int -> int), that is, fac accepts an integer as an argument and returns an integer result. Thanks to type inference, the type annotations can be omitted and will be derived by the compiler. Rewritten without the type annotations, the example looks like:

fun fac 0 = 1
  | fac n = n * fac (n - 1)

The function also relies on pattern matching, an important part of ML programming. Note that parameters of a function are not necessarily in parentheses but separated by spaces. When the function's argument is 0 (zero) it will return the integer 1 (one). For all other cases the second line is tried. This is the recursion, and executes the function again until the base case is reached.

This implementation of the factorial function is not guaranteed to terminate, since a negative argument causes an infinite descending chain of recursive calls. A more robust implementation would check for a nonnegative argument before recursing, as follows:

fun fact n = let
  fun fac 0 = 1
    | fac n = n * fac (n - 1)
  in
    if (n < 0) then raise Fail "negative argument"
    else fac n
  end

The problematic case (when n is negative) demonstrates a use of ML's exception system.

The function can be improved further by writing its inner loop in a tail-recursive style, such that the call stack need not grow in proportion to the number of function calls. This is achieved by adding an extra, "accumulator", parameter to the inner function. At last, we arrive at

fun factorial n = let
  fun fac (0, acc) = acc
    | fac (n, acc) = fac (n - 1, n * acc)
  in
    if (n < 0) then raise Fail "negative argument"
    else fac (n, 1)
  end