- Standard ML
Infobox programming language

name = Standard ML

logo =

paradigm = multi-paradigm: functional, imperative

year =

designer =

typing = strong, static, inferred

dialects = Alice,Dependent ML

implementations =MLton ,MLWorks ,Moscow ML , Poly/ML, SML/NJ, SML.NET

influenced_by = ML

influenced =

website =**Standard ML**(**SML**) is a general-purpose, modular,functional programming language withcompile-time type checking andtype inference . It is popular amongcompiler writers andprogramming language research ers, as well as in the development of theorem provers.SML is a modern descendant of the

ML programming language used in the LCF theorem-proving project. It is distinctive among widely used languages in that it has a formal specification, given as typing rules andoperational semantics in "The Definition of Standard ML" (1990, revised and simplified as "The Definition of Standard ML (Revised)" in 1997). [*cite book*]

last = Milner

first = R.

authorlink = Robin Milner

coauthors = M. Tofte, R. Harper and D. MacQueen.

title = The Definition of Standard ML (Revised)

publisher = MIT Press

year = 1997

id = ISBN 0-262-63181-4**Language**Standard ML is a mostly functional programming language. Programs written in Standard ML mostly consist of expressions whose values are to be calculated.

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 x =**if**x = 0**then**1**else**x * factorial (x-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 "x" 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)Using a local function, this function can be rewritten to use

tail recursion :**fun**factorial x =**let****fun**tail_fact p 0 = p

tail_fact p n = tail_fact (p * n) (n - 1)**in**tail_fact 1 x**end**The value of a

**let**-expression is that of the expression between**in**and**end**.**Module System**Standard ML has an advanced module system, allowing programs to be decomposed into hierarchically organized "structures" of logically related type and value declarations. SML modules provide not only namespace control but also abstraction, in the sense that they allow programmers to define

abstract data type s.Three main syntactic constructs comprise the SML module system: signatures, structures and functors. 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 "signature" is an interface, usually thought of as a type for a structure: it specifies the names of all the entities provided by the structure as well as the arities of type components, the types of value components, and signatures for substructures. The definitions of type components may or may not be exported; type components whose definitions are hidden are "abstract types". Finally, 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.

For example, the signature for a queue data structure might be:

**signature**QUEUE =**sig****type**'a queue**exception**Queue**val**empty : 'a queue**val**insert : 'a * 'a queue -> 'a queue**val**isEmpty : 'a queue -> bool**val**peek : 'a queue -> 'a**val**remove : 'a queue -> 'a * 'a queue**end**This signature describes a module that provides a parameterized type

`queue`

of queues, an exception called`Queue`

, and five values (four of which are functions) providing the basic operations on queues. One can now implement the queue data structure by writing a structure with this signature:**structure**TwoListQueue :> QUEUE =**struct****type**'a queue = 'a list * 'a list**exception**Queue**val**empty = ( [] , [] )**fun**insert (a,(ins,outs)) = (a::ins,outs)**fun**isEmpty ( [] , [] ) = true

isEmpty _ = false**fun**peek ( [] , [] ) =**raise**Queue

peek (ins, [] ) = hd (rev ins)

peek (ins,a::outs) = a**fun**remove ( [] , [] ) =**raise**Queue

remove (ins, [] ) =**let****val**newouts = rev ins**in**(hd newouts,( [] ,tl newouts))**end**

remove (ins,a::outs) = (a,(ins,outs))**end**This definition declares that

`TwoListQueue`

is an implementation of the`QUEUE`

signature. Furthermore, the "opaque ascription" (denoted by`:>`

) states that any type components whose definitions are not provided in the signature ("i.e.,"`queue`

) should be treated as abstract, meaning that the definition of a queue as a pair of lists is not visible outside the module. The body of the structure provides bindings for all of the components listed in the signature.To use a structure, one can access its type and value members using "dot notation". For instance, a queue of strings would have type

`string TwoListQueue.queue`

, the empty queue is`TwoListQueue.empty`

, and to remove the first element from a queue called`q`

one would write`TwoListQueue.remove q`

.**Code examples**Snippets of SML code are most easily studied by entering them into a "top-level", also known as a

read-eval-print loop . This is an interactive session that prints the inferred types of resulting or defined expressions. Many SML implementations provide an interactive top-level, including SML/NJ:$ sml Standard ML of New Jersey v110.52 [built: Fri Jan 21 16:42:10 2005] -

Code can then be entered at the "-" prompt. For example, to calculate 1+2*3:

- 1 + 2 * 3; val it = 7 : int

The top-level infers the type of the expression to be "int" and gives the result "7".

**Hello world**The following program "hello.sml":

print "Hello world! ";

can be compiled with MLton:

$ mlton hello.sml

and executed:

$ ./hello Hello world! $

**Merge Sort**"Main article:"

Merge sort Here, Merge Sort is implemented in three functions: split, merge and MergeSort.

The split function is implemented with a local function named split_iter, which has an additional parameter. One uses such a function because it is tail recursive. This function makes use of SML's pattern matching syntax, being defined for both the non-empty ('x::xs') and empty (' [] ') list cases.

(* Given a list of elements, split it into two elements of * about the same size. * O(n) *) local fun split_iter (x::xs, left, right) = split_iter(xs, right, x::left)

split_iter ( [] , left, right) = (left, right) in fun split(x) = split_iter(x, [] , [] ) end;The local-in-end syntax could be replaced with a let-in-end syntax, yielding the equivalent definition:

fun split(x) = let fun split_iter (x::xs, left, right) = split_iter(xs, right, x::left)

split_iter ( [] , left, right) = (left, right) in split_iter(x, [] , [] ) end;As with split, merge also uses a local function merge_iter for efficiency. Merge_iter is defined in terms of cases: when two non-empty lists are passed, when one non-empty list is passed, and when two empty lists are passed. Note the use of '_' as a wildcard pattern.

This function merges two "'ascending" lists into one "descending" because of how lists are constructed in SML. Because SML lists are implemented as imbalanced binary trees, it is efficient to prepend an element to a list, but very inefficient to append an element to a list. (* Given two lists in ascending order, merge them into * a single list in descending order. * The function lt(a,b) iff a < b * O(n) *) local fun merge_iter (out, left as (x::xs), right as (y::ys), lt) = if lt(x, y) then merge_iter(x::out, xs, right, lt) else merge_iter(y::out, left, ys, lt)

merge_iter (out, x::xs, [] , lt) = merge_iter( x::out, xs, [] , lt)

merge_iter (out, [] , y::ys, lt) = merge_iter( y::out, [] , ys, lt)

merge_iter (out, [] , [] , _) = out in fun merge(x,y,lt) = merge_iter( [] ,x,y,lt) end; Finally, the MergeSort function.(* Sort a list in ascending order according to lt(a,b) <=> a < b * O(n log n) *) fun MergeSort(empty as [] , _) = empty

MergeSort(single as _:: [] , _) = single

MergeSort(x, lt) = let val (left, right) = split(x) val sl = MergeSort(left, lt) val sr = MergeSort(right, lt) val s = merge(sl,sr,lt) in rev s end;Also note that the code makes no mention of variable types, with the exception of the :: and [] syntax which signify lists. This code will sort lists of any type, so long as a consistent ordering function lt can be defined. Using

Hindley-Milner type inference , the compiler is capable of inferring the types of all variables, even complicated types such as that of the lt function.**Arbitrary-precision factorial function (libraries)**In SML, 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 "fact.sml" implements an arbitrary-precision factorial function and prints the factorial of 120:

fun fact n : IntInf.int = if n=0 then 1 else n * fact(n - 1) val () = print (IntInf.toString (fact 120)^" ")

and can be compiled and run with:

$ mlton fact.sml $ ./fact 66895029134491270575881180540903725867527463331380298102956713523016335 57244962989366874165271984981308157637893214090552534408589408121859898 481114389650005964960521256960000000000000000000000000000

**Numerical derivative (higher-order functions)**Since SML is a functional programming language, it is easy to create and pass around functions in SML programs. This capability has an enormous number of applications. Calculating the numerical derivative of a function is one such application. The following SML function "d" computes the numerical derivative of a given function "f" at a given point "x":

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

This function requires a small value "delta". A good choice for delta when using this algorithm is the cube root of the

machine epsilon .Fact|date=August 2008The type of the function "d" indicates that it maps a "float" onto another function with the type "(real -> real) -> real -> real". This allows us to partially apply arguments. This functional style is known as

currying . In this case, it is useful to partially apply the first argument "delta" to "d", to obtain a more specialised function:- val d = d 1E~8; val d = fn : (real -> real) -> real -> real

Note that the inferred type indicates that the replacement "d" is expecting a function with the type "real -> real" as its first argument. We can compute a numerical approximation to the derivative of x^3-x-1 at x=3 with:

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

The correct answer is f'(x) = 3x^2-1 => f'(3) = 27-1 = 26.

The function "d" is called a "higher-order function" because it accepts another function ("f") as an argument.

Curried and higher-order functions can be used to eliminate redundant code. For example, a library 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 higher order function of type (a * c -> b) -> (a -> b) can factor out this commonality. This is an example of theadapter pattern .**Discrete Wavelet Transform (pattern matching)**The 1D

Haar wavelet transform of aninteger -power-of-two-length list of numbers can be implemented very succinctly in SML and is an excellent example of the use ofpattern matching over lists, taking pairs of elements ("h1" and "h2") off the front and storing their sums and differences on the lists "s" and "d", respectively:- fun haar l = let fun aux [s] [] d = s :: d

aux [] s d = aux s [] d

aux (h1::h2::t) s d = aux t (h1 + h2 :: s) (h1 - h2 :: d)

aux _ _ _ = raise Empty in aux l [] [] end; val haar = fn : int list -> int listFor example:

- haar [1, 2, 3, 4, ~4, ~3, ~2, ~1] ; val it = [0,20,4,4,~1,~1,~1,~1] : int list

Pattern matching is a useful construct that allows complicated transformations to be represented clearly and succinctly. Moreover, SML compilers turn pattern matches into efficient code, resulting in programs that are not only shorter but also faster.

**Implementations**Many SML implementations exist, including:

*

MLton is a whole-program optimizing compiler that produces very fast code compared to other ML implementations. [*http://www.mlton.org*]

*Standard ML of New Jersey (abbreviated SML/NJ) is a full compiler, with associated libraries, tools, an interactive shell, and documentation. [*http://www.smlnj.org/*]

*Moscow ML is a light-weight implementation, based on the CAML Light runtime engine. It implements the full SML language, including SML Modules, and much of the SML Basis Library. [*http://www.dina.kvl.dk/~sestoft/mosml.html*]

* [*http://www.polyml.org/ Poly/ML*] is a full implementation of Standard ML.

* [*http://www.tilt.cs.cmu.edu/ TILT*] is a full certifying compiler for SML. It uses typed intermediate languages to optimize code and ensure correctness, and can compile to typedAssembly language .

* [*http://www.ps.uni-sb.de/hamlet/ HaMLet*] is an SML interpreter that aims to be an accurate and accessible reference implementation of the standard.

* The [*http://www.it-c.dk/research/mlkit/ ML Kit*] integrates a garbage collector (which can be disabled) and region-based memory management with automatic inference of regions, aiming realtime applications. Its implementation is based very closely on the Definition.

* [*http://www.cl.cam.ac.uk/Research/TSG/SMLNET/ SML.NET*] allows compiling to the Microsoft CLR and has extensions for linking with other .NET code.

* SML2c is a batch compiler and compiles only module-level declarations (i.e. signatures, structures, functors) into C. It is based on SML/NJ version 0.67 and shares the front end, and most of its run-time system, but does not support SML/NJ style debugging and profiling. Module-level programs that run on SML/NJ can be compiled by sml2c with no changes.

* ThePoplog system implements a version of SML, withPOP-11 , and optionallyCommon Lisp , andProlog , allowing mixed language programming. For all, the implementation language is POP-11, which is compiled incrementally. It also has an integratedEmacs -like editor that communicates with the compiler.

* [*http://www.pllab.riec.tohoku.ac.jp/smlsharp/ SML#*] is a conservative extension of SML providing record polymorphism and C interoperability.All of these implementations areopen-source and freely available. Most are implemented themselves in SML. There are no longer any commercial SML implementations. Harlequin once produced a commercial IDE and compiler for SML calledMLWorks . The company is now defunct.MLWorks is believed to have been passed on toXanalys .**ee also*** Alice

* ML

*Concurrent ML

*Dependent ML

*EML

*Extended ML

* F#

*Objective Caml **External links*** [

*http://www.smlnj.org/sml.html What is SML?*]

* [*http://www.smlnj.org/sml97.html What is SML '97?*]

* [*http://www.successor-ml.org successor ML (sML)*] is intended to provide a vehicle for the continued evolution of ML, using Standard ML as a starting point.**References**

*Wikimedia Foundation.
2010.*