ML (programming language)

ML (programming language)
ML
Paradigm(s) multi-paradigm: imperative, functional
Appeared in 1973
Designed by Robin Milner & others at the University of Edinburgh
Typing discipline static, strong, inferred
Dialects Standard ML, OCaml, F#
Influenced by ISWIM
Influenced Miranda, Haskell, Cyclone, C++, F#, Clojure, Felix, Opa

ML is a general-purpose functional programming language developed by Robin Milner and others in the early 1970s at the University of Edinburgh,[1] whose syntax is inspired by ISWIM. Historically, ML stands for metalanguage: it 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). It is known for its use of the Hindley–Milner type inference algorithm, which can automatically infer the types of most expressions without requiring explicit type annotations.

Contents

Overview

ML is often referred to as an impure functional language, because it encapsulates side-effects, unlike purely functional programming languages such as Haskell.

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.

Unlike Haskell, ML uses eager evaluation, which means that all subexpressions are always evaluated. However, lazy evaluation can be achieved through the use of closures. Thus one can create and use infinite streams as in Haskell, but their expression is comparatively indirect.

Today there are several languages in the ML family; the two major dialects are Standard ML (SML) and Caml, but others exist, including F#  — a language that Microsoft supports for their .NET platform. Ideas from ML have influenced numerous other languages, like Haskell, Cyclone[citation needed], and Nemerle.

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, financial systems, and applications including a genealogical database, a peer-to-peer client/server program, etc.

ML uses static scoping rules.

Examples

The following examples use the syntax of Standard ML. The other most widely-used ML dialect, OCaml, differs in various insubstantial ways.

Factorial

The factorial function expressed as pure ML:

fun fac (0 : int) : int = 1
  | fac (n : int) : int = n * fac (n - 1)

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). 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:

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

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:

fun fact n = let
  fun fac 0 = 1
    | fac n = n * fac (n - 1)
  in
    if (n < 0) then raise Fail "negative argument"
    else fac n
  end

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 in a tail-recursive style, such that the 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

fun factorial n = let
  fun fac (0, acc) = acc
    | fac (n, acc) = fac (n - 1, n*acc)
  in
    if (n < 0) then raise Fail "negative argument"
    else fac (n, 1)
  end

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.

fun reverse [] = []
  | reverse (x::xs) = (reverse xs) @ [x]

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 in the following more efficient, though less easy-to-read, style:

fun reverse xs = let
  fun rev nil acc = acc
    | rev (hd::tl) acc = rev tl (hd::acc)
in
  rev xs nil
end

Notably, 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.

See also

Dialects

  • Alice
  • Caml, a dialect of ML, which became...
  • Moscow ML - a popular implementation of Standard ML descended from Caml light
  • Objective Caml, the famous dialect of Caml with support for object-oriented programming

Books

References

  1. ^ Gordon, Michael J. C. (1996). "From LCF to HOL: a short history". http://www.cl.cam.ac.uk/~mjcg/papers/HolHistory.html. Retrieved 2007-10-11. 

External links


Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Look at other dictionaries:

  • Programming language — lists Alphabetical Categorical Chronological Generational A programming language is an artificial language designed to communicate instructions to a machine, particularly a computer. Programming languages can be used to create programs that… …   Wikipedia

  • Programming language theory — (commonly known as PLT) is a branch of computer science that deals with the design, implementation, analysis, characterization, and classification of programming languages and programming language features. It is a multi disciplinary field, both… …   Wikipedia

  • Programming Language Design and Implementation — (PLDI) is one of the ACM SIGPLAN s most important conferences. The precursor of PLDI was the Symposium on Compiler Optimization, held July 27–28, 1970 at the University of Illinois at Urbana Champaign and chaired by Robert S. Northcote. That… …   Wikipedia

  • Programming Language for Business — or PL/B is a business oriented programming language originally called DATABUS and designed by Datapoint in the early 1970s as an alternative to COBOL because its 8 bit computers could not fit COBOL into their limited memory, and because COBOL did …   Wikipedia

  • programming language — ➔ language * * * programming language UK US noun [C] ► COMPUTER LANGUAGE(Cf. ↑computer language) …   Financial and business terms

  • programming language — Language Lan guage, n. [OE. langage, F. langage, fr. L. lingua the tongue, hence speech, language; akin to E. tongue. See {Tongue}, cf. {Lingual}.] [1913 Webster] 1. Any means of conveying or communicating ideas; specifically, human speech; the… …   The Collaborative International Dictionary of English

  • Programming Language One — Programming Language One, oft als PL/I (auch PL/1, PL1 oder PLI) abgekürzt ist eine Programmiersprache, die in den 1960er Jahren von IBM entwickelt wurde. Die Bezeichnung PL/1 ist vor allem in Deutschland gebräuchlich. Ursprünglich wurde PL/I… …   Deutsch Wikipedia

  • Programming Language 1 — noun A computer programming language which combines the best qualities of commercial and scientific oriented languages (abbrev PL/1) • • • Main Entry: ↑programme …   Useful english dictionary

  • Programming Language —   [engl.], Programmiersprache …   Universal-Lexikon

  • Programming language specification — A programming language specification is an artifact that defines a programming language so that users and implementors can agree on what programs in that language mean.A programming language specification can take several forms, including the… …   Wikipedia

  • programming language — noun (computer science) a language designed for programming computers • Syn: ↑programing language • Topics: ↑computer science, ↑computing • Hypernyms: ↑artificial language …   Useful english dictionary

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”