ML (programming language): Difference between revisions

Revision as of 17:32, 9 March 2020

Latest revision as of 18:17, 29 April 2025

(68 intermediate revisions by 48 users not shown)

Line 1:

{{shortShort description|General purpose functional programming language}}

{{Other uses|ML (disambiguation){{!}}ML}}

{{More citations needed|date= May 2015}}

{{Infobox programming language

| name = ML

| logo =

| paradigm = [[multiMulti-paradigm programming language|Multi-paradigm]]: [[Functional programming|functional]], [[Generic programming|functionalgeneric]], [[imperativeImperative programming|imperative]]

| designer = [[Robin Milner]] and, others at the [[University of Edinburgh]]

| year = {{start date and age|1973}}

| developer =

| designer = [[Robin Milner]] and others at the [[University of Edinburgh]]

| year released = {{startStart date and age|1973}}

| developer =

| latest release version =

| latest release date =

| typing = [[Type inference|Inferred]], [[staticStatic typing|static]], [[strongStrong and weak typing|strong]]

| implementations =

| dialects = [[F Sharp (programming language)|F#Caml]], [[OCaml]], [[Standard ML]], [[F Sharp (programming language)|F#]]

| influenced by = [[ISWIM]]

| influenced = [[Caml]], [[Clojure]], [[Coq (software)|Coq]], [[Cyclone (programming language)|Cyclone]], [[C++]], [[Elm (programming language)|Elm]], [[F Sharp (programming language)|F#]], [[F* (programming language)|F*]], [[Haskell]], [[Idris (programming language)|HaskellIdris]], [[IdrisKotlin (programming language)|IdrisKotlin]], [[Miranda (programming language)|Miranda]], [[Nemerle]], [[OCaml]], [[Opa (programming language)|Opa]], [[Erlang (programming language)|Erlang]], [[Rust (programming language)|Rust]], [[Scala (programming language)|Scala]], [[Standard ML]]

| operating system =

| license =

| website =

}}

'''ML''' ("'''Meta Language"''') is a general[[General-purpose [[functional programming language|general-purpose]]. It has roots in, [[LispHigh-level (programming language)|Lisphigh-level]], and has been characterized as "Lisp with types".{{citation[[Functional neededprogramming|date=January 2019}} ML is a statically-scoped functional]] [[programming language like Scheme]]. It is known for its use of the polymorphic [[Hindley–Milner type system]], which automatically assigns the [[data type|types]]s of most [[Expression (programming)|expressions]] without requiring explicit type annotations ([[type inference]]), and ensures type safety{{snd}}; there is a [[formal proof]] that a well-typed ML program does not cause runtime type errors.<ref>Robin Milner. A theory of type polymorphism in programming. Journal of Computer and System Sciences, 17(3):348–375, 1978.</ref> ML provides pattern matching for function arguments, [[Garbage collection (computer science)|garbage collection]], [[imperative programming]], [[call-by-value]] and [[currying]]. While Ita [[general-purpose programming language]], ML is used heavily in [[Programming language theory|programming language research]] and is one of the few languages to be completely specified and verified using [[Formal semantics of programming languages|formal semantics]]. Its types and pattern matching make it well-suited and commonly used to operate on other formal languages, such as in [[compiler writing]], [[automated theorem proving]], and [[formal verification]].

'''ML''' ("Meta Language") is a general-purpose [[functional programming language]]. It has roots in [[Lisp (programming language)|Lisp]], and has been characterized as "Lisp with types".{{citation needed|date=January 2019}} ML is a statically-scoped functional programming language like Scheme. It is known for its use of the polymorphic [[Hindley–Milner type system]], which automatically assigns the [[data type|types]] of most [[Expression (programming)|expressions]] without requiring explicit type annotations, and ensures type safety{{snd}}there is a formal proof that a well-typed ML program does not cause runtime type errors.<ref>Robin Milner. A theory of type polymorphism in programming. Journal of Computer and System Sciences, 17(3):348–375, 1978.</ref> ML provides pattern matching for function arguments, [[Garbage collection (computer science)|garbage collection]], [[imperative programming]], [[call-by-value]] and [[currying]]. It is used heavily in programming language research and is one of the few languages to be completely specified and verified using [[Formal semantics of programming languages|formal semantics]]. Its types and pattern matching make it well-suited and commonly used to operate on other formal languages, such as in [[compiler writing]], [[automated theorem proving]], and [[formal verification]].

==Overview==

Features of ML include a call-by-value [[evaluation strategy]], [[first-class function]]s, automatic memory management through [[garbage collection (computer science)|garbage collection]], [[parametric polymorphism]], [[Type system#Static typing|static typing]], [[type inference]], [[algebraic data types]], [[pattern matching]], and [[exception handling]]. ML uses [[Scope (computer science)#Lexical scoping|static scoping]] rules.<ref>{{citationcite book |last1=Milner |first1=Robin |last2=Tofte |first2=Mads |title=Commentary on Standard ML needed|date=May1991 |publisher=The MIT Press |isbn=0-262-63137-7 |pages=35–36|chapter=4.1 Contexts, environments and 2015scope}}</ref>

ML can be referred to as an ''impure'' functional language, because although it encourages functional programming, it does allow [[side-effect (computer science)|side-effects]]<ref>{{cite book |last1=Sebesta |first1=Robert |title=Concepts of Programming Languages |date=1999 |publisher=Addison-Westley |isbn=0-201-38596-1 |page=54 |edition=4th}}</ref> (like languages such as [[Lisp (programming language)|Lisp]], but unlike a [[purely functional language]] such as [[Haskell (programming language)|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 [[Closure (computer science)|closures]]. Thus, oneinfinite streams can createbe created and use infinite streamsused 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]],<ref name="Gordon1996">{{cite web | last = Gordon | first = Michael J. C. | authorlink author-link= Michael J. C. Gordon | year=1996 | title = From LCF to HOL: a short history | url = http://www.cl.cam.ac.uk/~mjcg/papers/HolHistory.html | accessdate access-date= 2007-10-11}}</ref> whoseand its syntax is inspired by [[ISWIM]]. Historically, ML was conceived to develop proof tactics in the [[Logic for Computable Functions|LCF theorem prover]] (whose language, ''pplambda'', a combination of the [[First-order logic|first-order predicate calculus]] and the simply- typed [[Polymorphism (computer science)|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 Sharp (programming language)|F#]]. Ideas from ML have influenced numerous other languages, like [[Haskell]], [[Cyclone (programming language)|Cyclone]], [[Nemerle]],<ref>{{Citation |title=Programming language for "special forces" of developers |publisher=Nemerle Project Team |publication-place=Russian Software Development Network |url=http://nemerle.org/About |access-date=January 24, 2021}}</ref> [[ATS (programming language)|ATS]],{{Citation needed|date=August 2010}} and [[Elm (programming language)|Elm]].<ref>{{cite book|last1=Tate|first1=Bruce A.|last2=Daoud|first2=Fred|last3=Dees|first3=Ian|last4=Moffitt|first4=Jack|title=Seven More Languages in Seven Weeks|date=2014|publisher=The Pragmatic Programmers, LLC|isbn=978-1-941222-15-7|pages=97, 101|edition=Book version: P1.0-November 2014|chapter=3. Elm|quote=On page 101, Elm creator Evan Czaplicki says: 'I tend to say "Elm is an ML-family language" to get at the shared heritage of all these languages.' ["these languages" is referring to Haskell, OCaml, SML, and F#.]}}</ref>

==Examples==

The following examples use the syntax of Standard ML. Other ML dialects such as [[OCaml]] and [[F Sharp (programming language)|F#]] differ in small ways.

===Factorial===

The [[factorial]] function expressed as pure ML:

<sourcesyntaxhighlight lang="sml">

fun fac (0 : int) : int = 1

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

</syntaxhighlight>

</source>

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.

Line 48:

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:

<sourcesyntaxhighlight lang="sml">

fun fac 0 = 1

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

</syntaxhighlight>

</source>

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 (computer science)|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:

<sourcesyntaxhighlight lang="sml">

fun fact n = let

fun fac 0 = 1

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

in

if (n < 0) then raise FailDomain "negativeelse argument"fac n

else fac n

end

</syntaxhighlight>

</source>

The problematic case (when n is negative) demonstrates a use of ML's [[exception handling|exception system]].

The function can be improved further by writing its inner loop inas a [[tail-recursive call]] style, 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

<sourcesyntaxhighlight lang="sml">

fun fact n = let

fun fac 0 acc = acc

| fac n acc = fac (n - 1) (n * acc)

in

if (n < 0) then raise FailDomain "negativeelse argument"fac n 1

else fac n 1

end

</syntaxhighlight>

</source>

===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.

<sourcesyntaxhighlight lang="sml">

fun reverse [] = []

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

</syntaxhighlight>

</source>

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:

<sourcesyntaxhighlight lang="sml">

fun 'a reverse xs : 'a list = letList.foldl (op ::) [] xs

</syntaxhighlight>

fun rev [] acc = acc

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

| rev (hd::tl) acc = rev tl (hd::acc)

in

rev xs []

end

</source>

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.

===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 [[Interface (Java)|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:

<sourcesyntaxhighlight lang="sml">

signature ARITH =

sig

type t;

val zero : t;

val sumsucc : t * t -> t;

val succsum : t * t -> t ;

val sum : t * t -> t;

end

</syntaxhighlight>

</source>

<sourcesyntaxhighlight lang="sml">

structure Rational : ARITH =

struct

datatype t = Rat of int * int;

val zero = Rat (0, 1);

fun succ (Rat (a, b)) = Rat( (a +b b, b );

fun sum (Rat (a, b), Rat (c, d)) = Rat (a * d + c *b b , b * d) : t ;

end

</syntaxhighlight>

</source>

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.

Line 131 ⟶ 122:

==See also==

* [[Standard ML]] and its{{section implementations:link|Standard ML|Implementations}}

* [[Dependent ML]]: a dependently typed extension of ML

:* [[SML/NJ]], an implementation with [[Concurrent ML|extensions for concurrent programming]] developed at [[Princeton University]] and [[Bell Laboratories]]

** [[PALATS (programming language)|ATS]],: ana educationalfurther languagedevelopment relatedof todependent ML

:* [[Moscow ML]], an implementation originally based on Caml Light

* [[Lazy ML]],: an experimental lazily evaluated ML dialect from the early 1980s

:* [[Alice (programming language)|Alice ML]], an extension of Standard ML with support for parallel programming using [[Futures and promises|futures]]

* [[PAL (programming language)]]: an educational language related to ML

:* [[MLton]], a powerful [[Whole program optimization|whole-program optimizing]] compiler strictly conforming to the Definition

* [[OCaml]]: an ML dialect used to implement [[Coq (software)|Coq]] and [[OCaml#Software written in OCaml|various software]]

* [[Dependent ML]], an extension of ML with dependent typing that led to the development of:

:* [[ATSF Sharp (programming language)|ATSF#]]: an open-source cross-platform functional-first language for the [[.NET]] framework

* [[Lazy ML]], an experimental lazily evaluated ML dialect from the early 1980s

* [[PAL (programming language)]], an educational language related to ML

* [[OCaml]], an "industrial strength"<ref>[http://ocaml.org/ "OCaml is an industrial strength programming language supporting functional, imperative and object-oriented styles"]. Retrieved on January 2, 2018.</ref> ML dialect used to implement the [[Coq]] theorem prover

==References==

Line 146 ⟶ 134:

==Further reading==

{{refbegin}}

* ''The Definition of Standard ML'', Robin Milner, [[Mads Tofte]], [[Robert Harper (computer scientist)|Robert Harper]], MIT Press 1990; (revised edition adds author David MacQueen), MIT Press 1997, {{ISBN|0-262-63181-4}} [https://smlfamily.github.io/sml97-defn.pdf The Definition of Standard ML (Revised)].

* ''Commentary on Standard ML'', [[Robin Milner]], [[Mads Tofte]], MIT Press 1997, {{ISBN|0-262-63137-7}}.

* ''ML for the Working Programmer'', [[Lawrence Paulson]], Cambridge University Press 1991, 1996, {{ISBN|0-521-57050-6}}.

* {{cite book |url=https://www.cs.cmu.edu/~rwh/isml/book.pdf |format=PDF|first=Robert |last=Harper |title=Programming in Standard ML|publisher= Carnegie Mellon University |year=2011}}

* ''Elements of ML Programming'', [[Jeffrey D. Ullman]], Prentice-Hall 1994, 1998, {{ISBN|0-13-790387-1}}.

{{refend}}

==External links==

* [http://smlnj.org Standard ML of New Jersey, another popular implementation]

* [http://msdn.microsoft.com/en-us/fsharp/default.aspx F#, an ML implementation using the Microsoft .NET framework] {{Webarchive|url=https://web.archive.org/web/20100218004857/http://msdn.microsoft.com/en-us/fsharp/default.aspx |date=2010-02-18}}

* [http://mlton.org MLton, a whole-program optimizing Standard ML compiler]

* [https://github.com/SMLFamily/Successor-ML Successor ML]{{snd}} or sML

* [https://cakeml.org CakeML, a read-eval-print loop version of ML with formally verified runtime and translation to assembler]

{{ML programming}}

{{Programming languages}}

{{Authority control}}

{{DEFAULTSORT:ML (Programming Language)}}

[[Category:Academic programming languages]]

[[Category:ProceduralHigh-level programming languages]]

[[Category:Functional languages]]

[[Category:Procedural programming languages]]

[[Category:ML programming language family]]

[[Category:Pattern matching programming languages]]

[[Category:Statically typedProcedural programming languages]]

[[Category:Programming languages created in 1973]]

[[Category:Statically typed programming languages]]