ML (programming language)
- 8 min read
- 2 chapters
Related on Lably
Through High-level programming language, Data type and Expression (computer science)
Overview
Features of ML include a call-by-value evaluation strategy, first-class functions, automatic memory management through garbage collection, parametric polymorphism, static typing, type inference, algebraic data types, pattern matching, and exception handling. ML uses static scoping rules.
ML can be referred to as an impure functional language, because although it encourages functional programming, it does allow side-effects (like languages such as Lisp, but unlike a purely functional language such as Haskell). Like most programming languages, ML uses eager evaluation, meaning that all subexpressions are always evaluated, though lazy evaluation can be achieved through the use of closures. Thus, infinite streams can be created and used as in Haskell, but their expression is indirect.
ML's strengths are mostly applied in language design and manipulation (compilers, analyzers, theorem provers), but it is a general-purpose language also used in bioinformatics and financial systems.
ML was developed by Robin Milner and others in the early 1970s at the University of Edinburgh, and its syntax is inspired by ISWIM. Historically, ML 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).
Today there are several languages in the ML family; the three most prominent are Standard ML (SML), OCaml and F#. Ideas from ML have influenced numerous other languages, like Haskell, Cyclone, Nemerle, ATS, and Elm.
Sign in to keep reading
One more chapter is free with a Lably account.
Examples
The following examples use the syntax of Standard ML. Other ML dialects such as OCaml and F# differ in small ways.
Factorial
The factorial function expressed as pure ML:
<span id="mwXA"></span><span class="kr" id="mwXQ">fun</span> <span class="nf" id="mwXg">fac</span> <span class="p" id="mwXw">(</span><span class="mi" id="mwYA">0</span> <span class="p" id="mwYQ">:</span> <span class="n" id="mwYg">int</span><span class="p" id="mwYw">)</span> <span class="p" id="mwZA">:</span> <span class="n" id="mwZQ">int</span> <span class="p" id="mwZg">=</span> <span class="mi" id="mwZw">1</span> <span class="p" id="mwaA">|</span> <span class="nf" id="mwaQ">fac</span> <span class="p" id="mwag">(</span><span class="n" id="mwaw">n</span> <span class="p" id="mwbA">:</span> <span class="n" id="mwbQ">int</span><span class="p" id="mwbg">)</span> <span class="p" id="mwbw">:</span> <span class="n" id="mwcA">int</span> <span class="p" id="mwcQ">=</span> <span class="n" id="mwcg">n</span> <span class="n" id="mwcw">*</span> <span class="n" id="mwdA">fac</span> <span class="p" id="mwdQ">(</span><span class="n" id="mwdg">n</span> <span class="n" id="mwdw">-</span> <span class="mi" id="mweA">1</span><span class="p" id="mweQ">)</span>
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 type integer (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:
<span id="mwhA"></span><span class="kr" id="mwhQ">fun</span> <span class="nf" id="mwhg">fac</span> <span class="mi" id="mwhw">0</span> <span class="p" id="mwiA">=</span> <span class="mi" id="mwiQ">1</span> <span class="p" id="mwig">|</span> <span class="nf" id="mwiw">fac</span> <span class="n" id="mwjA">n</span> <span class="p" id="mwjQ">=</span> <span class="n" id="mwjg">n</span> <span class="n" id="mwjw">*</span> <span class="n" id="mwkA">fac</span> <span class="p" id="mwkQ">(</span><span class="n" id="mwkg">n</span> <span class="n" id="mwkw">-</span> <span class="mi" id="mwlA">1</span><span class="p" id="mwlQ">)</span>
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:
<span id="mwnA"></span><span class="kr" id="mwnQ">fun</span> <span class="nf" id="mwng">fact</span> <span class="n" id="mwnw">n</span> <span class="p" id="mwoA">=</span> <span class="kr" id="mwoQ">let</span> <span class="kr" id="mwog">fun</span> <span class="nf" id="mwow">fac</span> <span class="mi" id="mwpA">0</span> <span class="p" id="mwpQ">=</span> <span class="mi" id="mwpg">1</span> <span class="p" id="mwpw">|</span> <span class="nf" id="mwqA">fac</span> <span class="n" id="mwqQ">n</span> <span class="p" id="mwqg">=</span> <span class="n" id="mwqw">n</span> <span class="n" id="mwrA">*</span> <span class="n" id="mwrQ">fac</span> <span class="p" id="mwrg">(</span><span class="n" id="mwrw">n</span> <span class="n" id="mwsA">-</span> <span class="mi" id="mwsQ">1</span><span class="p" id="mwsg">)</span> <span class="kr" id="mwsw">in</span> <span class="kr" id="mwtA">if</span> <span class="p" id="mwtQ">(</span><span class="n" id="mwtg">n</span> <span class="n" id="mwtw"><</span> <span class="mi" id="mwuA">0</span><span class="p" id="mwuQ">)</span> <span class="kr" id="mwug">then</span> <span class="kr" id="mwuw">raise</span> <span class="n" id="mwvA">Domain</span> <span class="kr" id="mwvQ">else</span> <span class="n" id="mwvg">fac</span> <span class="n" id="mwvw">n</span> <span class="kr" id="mwwA">end</span>
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 as a tail call, 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
<span id="mwyA"></span><span class="kr" id="mwyQ">fun</span> <span class="nf" id="mwyg">fact</span> <span class="n" id="mwyw">n</span> <span class="p" id="mwzA">=</span> <span class="kr" id="mwzQ">let</span> <span class="kr" id="mwzg">fun</span> <span class="nf" id="mwzw">fac</span> <span class="mi" id="mw0A">0</span> <span class="n" id="mw0Q">acc</span> <span class="p" id="mw0g">=</span> <span class="n" id="mw0w">acc</span> <span class="p" id="mw1A">|</span> <span class="nf" id="mw1Q">fac</span> <span class="n" id="mw1g">n</span> <span class="n" id="mw1w">acc</span> <span class="p" id="mw2A">=</span> <span class="n" id="mw2Q">fac</span> <span class="p" id="mw2g">(</span><span class="n" id="mw2w">n</span> <span class="n" id="mw3A">-</span> <span class="mi" id="mw3Q">1</span><span class="p" id="mw3g">)</span> <span class="p" id="mw3w">(</span><span class="n" id="mw4A">n</span> <span class="n" id="mw4Q">*</span> <span class="n" id="mw4g">acc</span><span class="p" id="mw4w">)</span> <span class="kr" id="mw5A">in</span> <span class="kr" id="mw5Q">if</span> <span class="p" id="mw5g">(</span><span class="n" id="mw5w">n</span> <span class="n" id="mw6A"><</span> <span class="mi" id="mw6Q">0</span><span class="p" id="mw6g">)</span> <span class="kr" id="mw6w">then</span> <span class="kr" id="mw7A">raise</span> <span class="n" id="mw7Q">Domain</span> <span class="kr" id="mw7g">else</span> <span class="n" id="mw7w">fac</span> <span class="n" id="mw8A">n</span> <span class="mi" id="mw8Q">1</span> <span class="kr" id="mw8g">end</span>
List reverse
The following function reverses the elements in a list. More precisely, it returns a new list whose elements are in reverse order compared to the given list.
<span id="mw-A"></span><span class="kr" id="mw-Q">fun</span> <span class="nf" id="mw-g">reverse</span> <span class="p" id="mw-w">[]</span> <span class="p" id="mw_A">=</span> <span class="p" id="mw_Q">[]</span> <span class="p" id="mw_g">|</span> <span class="nf" id="mw_w">reverse</span> <span class="p" id="mwAQA">(</span><span class="n" id="mwAQE">x</span> <span class="n" id="mwAQI">::</span> <span class="n" id="mwAQM">xs</span><span class="p" id="mwAQQ">)</span> <span class="p" id="mwAQU">=</span> <span class="p" id="mwAQY">(</span><span class="n" id="mwAQc">reverse</span> <span class="n" id="mwAQg">xs</span><span class="p" id="mwAQk">)</span> <span class="n" id="mwAQo">@</span> <span class="p" id="mwAQs">[</span><span class="n" id="mwAQw">x</span><span class="p" id="mwAQ0">]</span>
This implementation of reverse, while correct and clear, is inefficient, requiring quadratic time for execution. The function can be rewritten to execute in linear time:
<span id="mwARM"></span><span class="kr" id="mwARQ">fun</span> <span class="nd" id="mwARU">'a</span> <span class="nf" id="mwARY">reverse</span> <span class="n" id="mwARc">xs</span> <span class="p" id="mwARg">:</span> <span class="nd" id="mwARk">'a</span> <span class="n" id="mwARo">list</span> <span class="p" id="mwARs">=</span> <span class="nn" id="mwARw">List</span><span class="p" id="mwAR0">.</span><span class="n" id="mwAR4">foldl</span> <span class="p" id="mwAR8">(</span><span class="kr" id="mwASA">op</span> <span class="n" id="mwASE">::</span><span class="p" id="mwASI">)</span> <span class="p" id="mwASM">[]</span> <span class="n" id="mwASQ">xs</span>
This function is an example of parametric polymorphism. That is, it can consume lists whose elements have any type, and return lists of the same type.
Modules
Modules are ML's system for structuring large projects and libraries. A module consists of a signature file and one or more structure files. The signature file specifies the API to be implemented (like a C header file, or Java interface file). The structure implements the signature (like a C source file or Java class file). For example, the following define an Arithmetic signature and an implementation of it using Rational numbers:
<span id="mwASw"></span><span class="kr" id="mwAS0">signature</span> <span class="nn" id="mwAS4">ARITH</span> <span class="p" id="mwAS8">=</span> <span class="kr" id="mwATA">sig</span> <span class="kr" id="mwATE">type</span> <span class="kt" id="mwATI">t</span> <span class="kr" id="mwATM">val</span> <span class="nv" id="mwATQ">zero</span> <span class="p" id="mwATU">:</span> <span class="n" id="mwATY">t</span> <span class="kr" id="mwATc">val</span> <span class="nv" id="mwATg">succ</span> <span class="p" id="mwATk">:</span> <span class="n" id="mwATo">t</span> <span class="p" id="mwATs">-></span> <span class="n" id="mwATw">t</span> <span class="kr" id="mwAT0">val</span> <span class="nv" id="mwAT4">sum</span> <span class="p" id="mwAT8">:</span> <span class="n" id="mwAUA">t</span> <span class="n" id="mwAUE">*</span> <span class="n" id="mwAUI">t</span> <span class="p" id="mwAUM">-></span> <span class="n" id="mwAUQ">t</span> <span class="kr" id="mwAUU">end</span>
<span id="mwAUg"></span><span class="kr" id="mwAUk">structure</span> <span class="nn" id="mwAUo">Rational</span> <span class="p" id="mwAUs">:</span> <span class="n" id="mwAUw">ARITH</span> <span class="p" id="mwAU0">=</span> <span class="kr" id="mwAU4">struct</span> <span class="kr" id="mwAU8">datatype</span> <span class="kt" id="mwAVA">t</span> <span class="p" id="mwAVE">=</span> <span class="nc" id="mwAVI">Rat</span> <span class="kr" id="mwAVM">of</span> <span class="n" id="mwAVQ">int</span> <span class="n" id="mwAVU">*</span> <span class="n" id="mwAVY">int</span> <span class="kr" id="mwAVc">val</span> <span class="nv" id="mwAVg">zero</span> <span class="p" id="mwAVk">=</span> <span class="n" id="mwAVo">Rat</span> <span class="p" id="mwAVs">(</span><span class="mi" id="mwAVw">0</span><span class="p" id="mwAV0">,</span> <span class="mi" id="mwAV4">1</span><span class="p" id="mwAV8">)</span> <span class="kr" id="mwAWA">fun</span> <span class="nf" id="mwAWE">succ</span> <span class="p" id="mwAWI">(</span><span class="n" id="mwAWM">Rat</span> <span class="p" id="mwAWQ">(</span><span class="n" id="mwAWU">a</span><span class="p" id="mwAWY">,</span> <span class="n" id="mwAWc">b</span><span class="p" id="mwAWg">))</span> <span class="p" id="mwAWk">=</span> <span class="n" id="mwAWo">Rat</span> <span class="p" id="mwAWs">(</span><span class="n" id="mwAWw">a</span> <span class="n" id="mwAW0">+</span> <span class="n" id="mwAW4">b</span><span class="p" id="mwAW8">,</span> <span class="n" id="mwAXA">b</span><span class="p" id="mwAXE">)</span> <span class="kr" id="mwAXI">fun</span> <span class="nf" id="mwAXM">sum</span> <span class="p" id="mwAXQ">(</span><span class="n" id="mwAXU">Rat</span> <span class="p" id="mwAXY">(</span><span class="n" id="mwAXc">a</span><span class="p" id="mwAXg">,</span> <span class="n" id="mwAXk">b</span><span class="p" id="mwAXo">),</span> <span class="n" id="mwAXs">Rat</span> <span class="p" id="mwAXw">(</span><span class="n" id="mwAX0">c</span><span class="p" id="mwAX4">,</span> <span class="n" id="mwAX8">d</span><span class="p" id="mwAYA">))</span> <span class="p" id="mwAYE">=</span> <span class="n" id="mwAYI">Rat</span> <span class="p" id="mwAYM">(</span><span class="n" id="mwAYQ">a</span> <span class="n" id="mwAYU">*</span> <span class="n" id="mwAYY">d</span> <span class="n" id="mwAYc">+</span> <span class="n" id="mwAYg">c</span> <span class="n" id="mwAYk">*</span> <span class="n" id="mwAYo">b</span> <span class="p" id="mwAYs">,</span> <span class="n" id="mwAYw">b</span> <span class="n" id="mwAY0">*</span> <span class="n" id="mwAY4">d</span><span class="p" id="mwAY8">)</span> <span class="kr" id="mwAZA">end</span>
These are imported into the interpreter by the 'use' command. Interaction with the implementation is only allowed via the signature functions, for example it is not possible to create a 'Rat' data object directly via this code. The 'structure' block hides all the implementation detail from outside.
ML's standard libraries are implemented as modules in this way.