Standard ML - Language

Language

Standard ML is a functional programming language with some impure features. Programs written in Standard ML consist of expressions to be evaluated, as opposed to statements or commands, although some expressions return a trivial "unit" value and are only evaluated for their side-effects.

Like all functional programming languages, a key feature of Standard ML is the function, which is used for abstraction. For instance, the factorial function can be expressed as:

fun factorial n = if n = 0 then 1 else n * factorial (n-1)

A Standard ML compiler is required to infer the static type int -> int of this function without user-supplied type annotations. I.e., it has to deduce that n is only used with integer expressions, and must therefore itself be an integer, and that all value-producing expressions within the function return integers.

The same function can be expressed with clausal function definitions where the if-then-else conditional is replaced by a sequence of templates of the factorial function evaluated for specific values, separated by '|', which are tried one by one in the order written until a match is found:

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

This can be rewritten using a case statement like this:

val rec factorial = fn n => case n of 0 => 1 | n => n * factorial (n - 1)

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 the definition of an anonymous function, and case introduces a sequence of patterns and corresponding expressions.

Using a local function, this function can be rewritten in a more efficient tail recursive style.

fun factorial n = let fun lp (0, acc) = acc | lp (m, acc) = lp (m-1, m*acc) in lp (n, 1) end

(The value of a let-expression is that of the expression between in and end.) The encapsulation of an invariant-preserving tail-recursive tight loop with one or more accumulator parameters inside an invariant-free outer function, as seen here, is a common idiom in Standard ML, and appears with great frequency in SML code.