Editing Standard ML (section)

==Language==
{{multiple issues|section=y|
{{How-to|section|date=November 2021}}
{{Unreferenced section|date=November 2021}}
}}

Standard ML is a functional [[programming language]] with some impure features. Programs written in Standard ML consist of [[Expression (computer science)|expressions]] in contrast to statements or commands, although some expressions of type [[Unit type|unit]] are only evaluated for their [[Side effect (computer science)|side-effects]].

===Functions===
Like all functional languages, a key feature of Standard ML is the [[function (programming)|function]], which is used for abstraction. The factorial function can be expressed as follows:

<syntaxhighlight lang="sml">
fun factorial n = 
    if n = 0 then 1 else n * factorial (n - 1)
</syntaxhighlight>

===Type inference===
An SML compiler must infer the static type {{code|lang=sml|val factorial : int -> int}} without user-supplied type annotations. It has to deduce that {{code|n}} is only used with integer expressions, and must therefore itself be an integer, and that all terminal expressions are integer expressions.

===Declarative definitions===
The same function can be expressed with [[clausal function definition]]s where the ''if''-''then''-''else'' conditional is replaced with templates of the factorial function evaluated for specific values:

<syntaxhighlight lang="sml">
fun factorial 0 = 1
  | factorial n = n * factorial (n - 1)
</syntaxhighlight>

===Imperative definitions===
or iteratively:

<syntaxhighlight lang="sml">
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
</syntaxhighlight>

===Lambda functions===
or as a lambda function:

<syntaxhighlight lang="sml">
val rec factorial = fn 0 => 1 | n => n * factorial (n - 1)
</syntaxhighlight>

Here, the keyword {{code|lang=sml|val}} introduces a binding of an identifier to a value, {{code|lang=sml|fn}} introduces an [[anonymous function]], and {{code|lang=sml|rec}} allows the definition to be self-referential.

===Local definitions===
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:

<syntaxhighlight lang="sml">
local
    fun loop (0, acc) = acc
      | loop (m, acc) = loop (m - 1, m * acc)
in
    fun factorial n = loop (n, 1)
end
</syntaxhighlight>

===Type synonyms===
A type synonym is defined with the keyword {{code|lang=sml|type}}. Here is a type synonym for points on a [[Plane (geometry)|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).

<syntaxhighlight lang="sml">
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
</syntaxhighlight>

===Algebraic datatypes===
Standard ML provides strong support for [[algebraic datatype]]s (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' [[Partial function|pattern-exhaustiveness]] checking and pattern redundancy checking.

In [[object-oriented programming]] languages, a disjoint union can be expressed as [[Class (computer programming)|class]] hierarchies. However, in contrast to [[Class hierarchy|class hierarchies]], ADTs are [[Closed-world assumption|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 {{code|lang=sml|datatype}}, as in:

<syntaxhighlight lang="sml">
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 *)
</syntaxhighlight>

Note that a type synonym cannot be recursive; datatypes are necessary to define recursive constructors. (This is not at issue in this example.)

===Pattern matching===
Patterns are matched in the order in which they are defined. [[C (programming language)|C]] programmers can use [[tagged union]]s, 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 program analysis|static checks]] provide strong guarantees about the correctness of the program at compile time.

Function arguments can be defined as patterns as follows:

<syntaxhighlight lang="sml">
fun area (Circle (_, r)) = Math.pi * square r
  | area (Square (_, s)) = square s
  | area (Triangle p) = heron p (* see above *)
</syntaxhighlight>

The so-called "clausal form" of function definition, where arguments are defined as patterns, is merely [[syntactic sugar]] for a case expression:

<syntaxhighlight lang="sml">
fun area shape = case shape of
    Circle (_, r) => Math.pi * square r
  | Square (_, s) => square s
  | Triangle p => heron p
</syntaxhighlight>

====Exhaustiveness checking====
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:

<syntaxhighlight lang="sml">
fun center (Circle (c, _)) = c
  | center (Square ((x, y), s)) = (x + s / 2.0, y + s / 2.0)
</syntaxhighlight>

There is no pattern for the {{code|Triangle}} case in the {{code|center}} function. The compiler will issue a warning that the case expression is not exhaustive, and if a {{code|Triangle}} is passed to this function at runtime, {{code|lang=sml|exception Match}} will be raised.

====Redundancy checking====
The pattern in the second clause of the following (meaningless) function is redundant:

<syntaxhighlight lang="sml">
fun f (Circle ((x, y), r)) = x + y
  | f (Circle _) = 1.0
  | f _ = 0.0
</syntaxhighlight>

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:

<syntaxhighlight lang="sml">
val hasCorners = fn (Circle _) => false | _ => true
</syntaxhighlight>

If control gets past the first pattern ({{code|Circle}}), we know the shape must be either a {{code|Square}} or a {{code|Triangle}}. In either of those cases, we know the shape has corners, so we can return {{code|lang=sml|true}} without discerning the actual shape.

===Higher-order functions===
Functions can consume functions as arguments:
<syntaxhighlight lang="sml">fun map f (x, y) = (f x, f y)</syntaxhighlight>

Functions can produce functions as return values:
<syntaxhighlight lang="sml">fun constant k = (fn _ => k)</syntaxhighlight>

Functions can also both consume and produce functions:
<syntaxhighlight lang="sml">fun compose (f, g) = (fn x => f (g x))</syntaxhighlight>

The function {{code|List.map}} from the basis [[Library (computing)|library]] is one of the most commonly used higher-order functions in Standard ML:
<syntaxhighlight lang="sml">
fun map _ [] = []
  | map f (x :: xs) = f x :: map f xs
</syntaxhighlight>

A more efficient implementation with tail-recursive {{code|List.foldl}}:
<syntaxhighlight lang="sml">
fun map f = List.rev o List.foldl (fn (x, acc) => f x :: acc) []
</syntaxhighlight>

===Exceptions===
Exceptions are raised with the keyword {{code|lang=sml|raise}} and handled with the pattern matching {{code|lang=sml|handle}} construct. The exception system can implement [[non-local exit]]; this optimization technique is suitable for functions like the following.

<syntaxhighlight lang="sml">
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
</syntaxhighlight>

When {{code|lang=sml|exception Zero}} is raised, control leaves the function {{code|lang=sml|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 ({{code|_}}) as a wildcard pattern.

The same optimization can be obtained with a [[tail call]].

<syntaxhighlight lang="sml">
local
    fun p a (0 :: _) = 0
      | p a (x :: xs) = p (a * x) xs
      | p a [] = a
in
    val prod = p 1
end
</syntaxhighlight>

===Module system===
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 type]]s. Three main syntactic constructs comprise the module system: signatures, structures and functors.

====Signatures====
A ''signature'' is an [[Interface (computing)|interface]], usually thought of as a type for a structure; it specifies the names of all entities provided by the structure, 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 (data structure)|queue]] may be:

<syntaxhighlight lang="sml">
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
</syntaxhighlight>

This signature describes a module that provides a polymorphic type {{code|lang=sml|'a queue}}, {{code|lang=sml|exception QueueError}}, and values that define basic operations on queues.

====Structures====
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:

<syntaxhighlight lang="sml">
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
</syntaxhighlight>

This definition declares that {{code|lang=sml|structure TwoListQueue}} implements {{code|lang=sml|signature QUEUE}}. Furthermore, the ''opaque ascription'' denoted by {{code|lang=sml|:>}} states that any types which are not defined in the signature (i.e. {{code|lang=sml|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":

<syntaxhighlight lang="sml">
val q : string TwoListQueue.queue = TwoListQueue.empty
val q' = TwoListQueue.insert (Real.toString Math.pi, q)
</syntaxhighlight>

====Functors====
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 programming|generic]] data structures and algorithms.

One popular algorithm<ref name="bfs"/> for [[breadth-first search]] of trees makes use of queues. Here is a version of that algorithm parameterized over an abstract queue structure:

<syntaxhighlight lang="sml">
(* 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)
</syntaxhighlight>

Within {{code|lang=sml|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.