Standard ML

from Wikipedia, the free encyclopedia
Standard ML
Paradigms : functional
Publishing year: 1990
Developer: Robin Milner
Current  version : '97   (1997)
Typing : strong, static, implicit
Important implementations : HaMLet, Moscow ML, MLj, ML Kit, MLton, MLWorks, Poly / ML, Poplog Standard ML, SML / NJ , SOSML
Influenced by: ML
Affected: Ocaml , Haskell , Rust
www.standardml.org

Standard ML ( SML ) is a functional programming language derived from ML with some imperative features (for example in the area of ​​File IO).

ML creator Robin Milner proposed SML in 1983 to standardize the various dialects of ML. The language was developed from 1984 to 1988 and finally formalized in 1990 by Robin Milner, Mads Tofte and Robert Harper. In 1997 , with SML'97, a revision of the language was published which, in addition to some simplifications, also contains an SML basic library.

Important characteristics of SML include static typing , polymorphism at the function and data type level, automatic garbage collection, and strict evaluation and exception handling . In addition, SML supports higher-order functions , modules and so-called functors , which here denote parameterized data types.

A special feature of SML is that the language is completely formally defined. Thereby important properties of the language can be proven mathematically .

Program examples

Recursive calculation of the factorial

The factorial of a natural number can be calculated in SML using the following program: 

fun fak (n) = if n < 1 then 1 else n * fak (n-1)

Recursive calculation of the Fibonacci numbers

The nth Fibonacci number can be calculated in SML using the following program: 

fun fib (0) = 0
  | fib (n) = if n <= 2 then 1 else fib(n-1) + fib(n-2)

The arity of a number

fun stell (x:int) = if x<1 then 0 else stell(x div 10) + 1

The checksum of a number

fun quer (x:int) = if x<1 then 0 else quer(x div 10) + x mod 10

The folding procedure foldl for lists 

fun foldl f s nil = s
  | foldl f s (x::xr) = foldl f (f(x,s)) xr

Converting a string that represents a number to int 

fun toInt x = foldl(fn(i,k)=>ord(i)-ord #"0" + k*10) 0 (explode x)

Insert location

fun insert (x, nil) = [x]
  | insert (x, y::yr) = if x<=y then x::y::yr else y::insert(x,yr)
fun isort xs = foldl insert nil xs

Merge sort

fun split xs = foldl (fn(i, (ys,zs)) =>(zs, i::ys)) (nil,nil) xs
fun merge (xs,nil) = xs
  | merge (nil,ys) = ys
  | merge (x::xr,y::yr) = if x<=y then x::merge(xr,y::yr) else y::merge(x::xr,yr)
fun mergesort nil = nil
  | mergesort [x] = [x]
  | mergesort xs = let val (ys,zs) = split(xs) in merge(mergesort ys, mergesort zs) end

"in situ" reversal of an array 

fun reverse (a) = let
  fun swap l r = 
    let
      val vl = Array.sub(a,l)
      val vr = Array.sub(a,r)
    in
      if l >= r then () else
        (Array.update(a,l,vr); Array.update(a,r,vl);swap (l+1) (r-1))
    end
  in
    swap (0) (Array.length (a) -1)
  end;

Implementations

There are different compilers for SML that generate either bytecode or machine code. The reference implementation is SML / NJ. Sml2c is a special compiler that translates SML into C code.

literature

  • Robin Milner , Mads Tofte, Robert Harper, D. MacQueen: The Definition of Standard ML (Revised) . MIT Press, 1997, ISBN 0-262-63181-4 (official language definition).
  • Gert Smolka : Programming - an introduction to computer science with Standard ML . Oldenbourg Wissenschaftsverlag, Munich 2008, ISBN 978-3-486-58601-5

Web links