ML语言

{{Infobox programming language
|name = ML
|logo =
|paradigm = 多范型：函数式，指令式
|year =
|designer = 罗宾·米尔纳及爱丁堡大学其他人
|developer =
|latest release version = [https://smlfamily.github.io/sml97-defn.pdf Standard ML '97]
|latest release date =
|typing = 类型推论，静态类型，强类型
|implementations =
|dialects = Standard ML, OCaml
|influenced_by = ISWIM、Miranda、Nemerle。ML能自动的指定多数的类型，不要求显式的类型标注，而且能够确保类型安全，已经正式证明了有良好类型的ML程序不会导致运行时间类型错误，用于在定理证明器中开发证明策略。LCF的语言是“PPλ”，它是一阶逻辑演算与有类型的多态λ演算的结合，以ML作为元语言。ML的语法从ISWIM及其扩展实现PAL得到了启发， ML运行在DEC-10/TOPS-10主机的Stanford LISP 1.6下。

在1980年，于爱丁堡大学的VAX/VMS系统上开发了ML编译器，它被称为“VAX ML”，以区别于LCF版本的“DEC-10 ML”。VAX ML的编译器和运行时间系统二者，都是用Pascal书写而建立在“函数抽象机器”（FAM）之上。在1982年，爱丁堡大学的Kevin Mitchell，用VAX ML重写了VAX ML编译器，随即John Scott和加入了开发，在又进行一系列重写改进之后，新的编译器被称为“Edinburgh ML”。

在1981年，INRIA的，将最初的LCF ML适配到Multics系统的Maclisp下，并且增加了编译器，它被开发者自称为“Le_ML”，进而剑桥大学的又用它开发了基于Common Lisp的。

在1983年，Robin Milner由两个动机驱使开始重新设计ML。其一是爱丁堡大学的及其小组在规定上的工作，具体化为规定语言CLEAR，和表达可执行规定的函数式语言HOPE。这项工作与ML有关的是两方面成果：首先，HOPE拥有优雅的编程特征，特别是模式匹配，和子句式函数定义；其次，是使用在接口中的签名，进行规定的模块化构造的想法。其二是在VAX ML上的工作，通过增加命名记录和可变类型，扩展了ML中数据类型的品目。

在1984年，贝尔实验室的David MacQueen提出了对Standard ML的模块系统的设计。在Standard ML的持续设计期间，Edinburgh ML被渐进的修改，充当了Standard ML的近似原型实现。在1986年，普林斯顿大学的和贝尔实验室的David MacQueen，以Edinburgh Standard ML作为起步开发环境，开始了专注于生成高质量机器代码的Standard ML of New Jersey的活跃开发。

在1990年，Robin Milner、和制定的Standard ML的正式规定《The Definition of Standard ML》最终完成；在1997年，这个标准规定增补了David MacQueen为作者并进行了修订。在1989年，、Nick Rothwell和David N. Turner于爱丁堡大学开始开发ML Kit编译器，为了强调清晰性而非高效，将标准定义直接转译成一组Standard ML模块；在1992年和1993年期间，主要通过爱丁堡大学的Nick Rothwell和哥本哈根大学（DIKU）的Lars Birkedal的工作，ML Kit第一版完成并开源发行。

在1987年，INRIA的Ascánder Suárez，基于巴黎第七大学的的“”（CAM），利用Le Lisp的运行时间系统重新实现了Le_ML，并正式命名为Caml。在1990年和1991年，INRIA的基于用C实现的字节码解释器，利用提供的内存管理系统重新实现了Caml，并称其为Caml Light。在1995年，Xavier Leroy又增加了机器代码编译器和高层模块系统，这个版本也称为“Caml Special Light”。在1996年，INRIA的Didier Rémy和Jérôme Vouillon，向Caml Special Light增加了面向对象特征，从而形成了OCaml。

今天ML家族的两个主要的方言是Standard ML和OCaml。ML的实力大多被用于语言设计和操作，比如建构编译器、分析器、定理证明器，但是它作为通用语言也被用于生物信息和财务系统等领域。ML确立了静态类型函数式编程范型，从而在编程语言历史上占有显要地位，它的思想在影响了众多的语言，例如Haskell、Nemerle、和Elm。

解释与编译
ML代码片段很容易通过将其录入到“顶层”来研习，它也叫作读取-求值-输出循环或REPL。这是打印结果或定义的表达式的推论类型的交互式会话。很多SML实现提供交互式REPL，比如SML/NJ：

$ sml
Standard ML of New Jersey v110.79 [built: Mon Apr 22 10:14:55 2024]
-

可以在提示符-后键入代码。例如计算1 + 2 * 3:

1 + 2 * 3;

val it = 7 : int

顶层推论这个表达式的类型为int并给出结果7。如果输入不完全，解释器会打印第二提示符=，这时通常可以用;终结输入。it是给未指定变量的表达式的标准变量。输入control-C可返回解释器顶层，输入control-D可退出解释器。可以使用第三方工具rlwrap运行SML/NJ解释器，它处理用户输入并提供readline的行编辑、持久历史和补全功能。

下面是输出hello, world!的例子代码，在SML/NJ解释器下执行它：

print "Hello, world!\n";

Hello, world!
val it = () : unit

val _ = print "Hello, world!\n";

Hello, world!

使用MLton编译器进行编译执行它：

$ echo 'print "Hello, world!\n";' > hello-world.sml
$ mlton hello-world.sml
$ ./hello-world
Hello, world!

使用LunarML源到源编译器。筛法还有基于数组的直观实现。
下面是其解释器下命令行运行实例：

fun printIntList (l: int list) =

= print ((String.concatWith " " (map Int.toString l)) ^ "\n");
val printIntList = fn : int list -> unit

val _ = printIntList (prime 100);

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

汉明数
正规数是形如\ 2^i\cdot 3^j\cdot 5^k\ 的整数，对于非负整数\ i\ 、\ j\ 和\ k，它是可以整除\ 60^{\max(\lceil i\,/2\rceil,j,k)}\ 的数。计算升序的正规数的算法经由戴克斯特拉得以流行，理查德·汉明最初提出了这个问题，故而这个问题被称为“汉明问题”，这个数列也因而被称为汉明数。Dijkstra计算这些数的想法如下：

汉明数的序列开始于数1。
要加入序列中的数有下述形式：2h, 3h, 5h，这里的h是序列已有的任意的汉明数。
因此，可以生成最初只有一个1的序列H，并接着序列2H, 3H, 5H，并以此类推。

示例汉明数程序代码，一般用来展示，确使计算只在需要时进行的纯函数式编程方式。

fun Hamming_number n = let
fun merge (p, q) = let
fun revMerge (acc, p, q) =
if not (null p) andalso not (null q) then
if hd p hd q
then revMerge ((hd q) :: acc, p, tl q)
else revMerge ((hd p) :: acc, tl p, tl q)
else if null p
then List.revAppend (q, acc)
else List.revAppend (p, acc)
in
if (null p) then q
else if (null q) then p
else rev (revMerge ([], p, q))
end
fun mul m x =
if x mapp (xs, a :: acc)
| NONE => rev acc)
in
mapp (l, [])
end
fun mergeWith f (m, i) = merge (f m, i)
fun generate l = let
fun listMul m = mapPrefix (mul m) l
in
foldl (mergeWith listMul) [] [2, 3, 5]
end
fun iterate (acc, l) =
if (hd l) > (n div 2) then merge (l, acc)
else iterate (merge (l, acc), generate l)
in
if n > 0 then iterate ([], [1]) else []
end

产生指定范围内的汉明数需要多轮运算，后面每轮中的三个列表元素乘积运算中都可能产生超出这个范围的结果，它们不需要出现在后续的运算之中。
基本库mapPartial函数与它所映射的函数，通过基于Option结构的SOME和NONE构造子的协定，可以将所映射函数认为不符合条件的元素或者结果排除掉，它会遍历整个列表。
由于这个算法采用升序列表，故而这里将它改写为mapPrefix函数，用来在特定条件不满足条件就立即结束。下面是汉明数程序在解释器下命令行运行实例：

fun printIntList (l: int list) =

= print ((String.concatWith " " (map Int.toString l)) ^ "\n");
val printIntList = fn : int list -> unit

val _ = printIntList (Hamming_number 400);

1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36 40 45 48 50 54 60 64 72 75 80 81 90 96 100 108 120 125 128 135 144 150 160 162 180 192 200 216 225 240 243 250 256 270 288 300 320 324 360 375 384 400

续体传递风格实例
下面是（CPS）的高阶函数foldr和map的实现，和达成一个整数列表的合计函数的简单用例：

fun foldr' f b l = let
fun g ([], k) = k b
| g (a :: r, k) = g (r, fn x => k (f (a, x)))
in
g (l, fn x => x)
end

fun map' f l = foldr' (fn (x, y) => (f x) :: y) [] l

fun sum l = foldr' (fn (x, y) => (x + y)) 0 l

对于输入[e1, e2, …, en]，sum函数等价于将函数复合(fn x => x)∘(fn x => e1 + x)∘(fn x => e2 + x)∘…∘(fn x => en + x)，应用于0之上，它得到(e1 + (e2 + (… + (en + 0)…)))。

SML/NJ支持头等对象的续体。头等续体对一门语言而言是能完全控制指令执行次序的能力。它们可以用来跳转到产生对当前函数调用的那个函数，或者跳转到此前已经退出了的函数。头等续体保存了程序执行状态，它不保存程序数据，只保存执行上下文。

排序算法
排序算法关注计算复杂度，特别是时间复杂度，基本库函数的实现细节也要考虑在内，比如串接函数@，它被实现为fun l1 @ l2 = revAppend(rev l1, l2)，除非必需的情况避免使用遍历整个列表的rev和length函数。
通过比较于这些排序算法的周知过程式编程语言比如C语言的实现，可以体察到ML在控制流程和列表数据结构上的相关限制，和与之相适应的采用尾递归的特色函数式编程风格。

插入排序
下面是简单的插入排序算法的尾递归和等价的普通递归实现：

插入排序算法是稳定的，它在输入列表趋于正序的时候性能最佳，在输入列表趋于反序的时候性能最差，因此在算法实现中，需要insert函数所插入列表保持为反序，在插入都完成后经rev函数再反转回正序。在预期输入数据趋于随机化或者预知它经过了反转的情况下，可以采用保持要插入列表为正序的变体插入排序算法实现，它在输入列表趋于反序的时候性能最佳，在输入列表趋于正序的时候性能最差，它比自适应实现少作一次全列表反转。
采用foldr函数可以相应的保持要插入列表为正序，由于fun foldr f b l = foldl f b (rev l)，它等同于对反转过的列表应用变体插入排序。

希尔排序
希尔排序算法是对插入排序的改进，保持了，放弃了稳定性。
下面是希尔排序的实现：

fun shellSort l = let
fun insert pred (ins, l) = let
fun loop (acc, []) =
List.revAppend (acc, [ins])
| loop (acc, l as x :: xs) =
if pred (ins, x)
then List.revAppend (acc, ins :: l)
else loop (x :: acc, xs)
in
loop ([], l)
end
val rec lt = fn (x, y) => (x ([x] :: l, n + 1)) ([], 0) (rev l)
val incs = [1, 4, 9, 20, 46, 103, 233, 525, 1182, 2660,
5985, 13467, 30301, 68178, 153401, 345152,
776591, 1747331, 3931496, 8845866, 19903198,
44782196, 100759940, 226709866, 510097200]
val gap = let
val v = len * 3 div 4
val thold = if (v = 0) then 1 else v
fun loop (acc, h) =
if (hd h) > thold then acc
else loop ((hd h) :: acc, tl h)
in
loop ([], incs)
end
fun sort (h, lol) = map insertSort (group (lol, h))
in
hd (foldl sort lol gap)
end

这里采用的间隔序列是OEIS ，即\ \begin{smallmatrix} \left\lceil \frac{1}{5} \left(9\cdot \left(\frac{9}{4}\right)^{k-1} - 4 \right) \right\rceil \end{smallmatrix} \ ，它是徳田尚之在1992年提出的。这个序列用递推公式表示为：hk = ⌈h'k⌉，这里的h'k = 2.25·h'k-1 + 1而h'1 = 1。假定一个列表的长度s位于序列两个元素之间，即hk-1 k ≤ s k+1，如果hk ≤ \tfrac {n}{m}·s，这里的n ≤ m，则选择初始间隔为hk，否则为hk-1。在这个阈值下，对于不同长度s的列表和对应的初始间隔h，每个列表的这些初始子列表的平均长度\tfrac{s}{h}，约在\tfrac{m}{n} ≤ \tfrac{s}{h} \tfrac{9}{4}·\tfrac{m}{n}范围之内。间隔序列还可以采用OEIS ，它是Marcin Ciura在2001年通过实验得到的。

快速排序
下面是快速排序算法的自顶向下实现：

fun quickSort [] = []
| quickSort [x] = [x]
| quickSort [x, y] =
if x (x
基本库partition函数实现对快速排序而言有不必要的反转，
这里采用了它的简化改写。在ML中快速排序应采用自底向上实现：

fun quickSort l = let
fun partition pred l = let
fun loop ([], p, q) = (p, q)
| loop (h :: t, p, q) =
if (pred h)
then loop (t, h :: p, q)
else loop (t, p, h :: q)
in
loop (l, [], [])
end
fun iterate (acc, []) = acc
| iterate (acc, [] :: xs) = iterate (acc, xs)
| iterate (acc, [x] :: xs) = iterate (x :: acc, xs)
| iterate (acc, [x, y] :: xs) = let
val (x, y) = if x (x

归并排序
下面是归并排序算法的自底向上法实现：

fun mergeSort l = let
fun init (acc, []) = acc
| init (acc, [x]) = [x] :: acc
| init (acc, [x, y]) =
if x (x > y))
val revMerge = mergeWith (fn (x, y) => (x
考虑输入列表[x1, ..., xi, a0, ..., a9, xj, ..., xn]，这里在xi和xj之间的10个a，具有相同的值并且需要保持其下标表示的次序，这里的xi > a并且xj ，并且在这个区段前后的元素总数都能被3整除，则它被分解成子列表的列表[Xm, ..., [xj, a8, a9], [a5, a6, a7], [a2, a3, a4], [a0, a1, xi], ..., X1]，这里有m = n div 3；假定这4个含有a的子列表两两归并，在归并正序子列表的归并条件x 下，能得到[X1, ..., [xi, a4, ..., a0], [a9, ..., a5, xj], ..., Xk]；继续推演下去，在归并反序子列表的归并条件x > y下，能得到[Xh, ..., [xj, a0, ..., a9, xi], ..., X1]。可以看出这种归并操作能够保证排序算法的稳定性，即具有相同值的元素之间的相对次序保持不变。

分解初始的子列表采用了插入排序，还可进一步增加其大小。归并排序也有自顶向下实现。

堆排序
下面是堆排序的基于数组的实现：

fun heapSort l = let
val h = Array.fromList l
val len = Array.length h
fun get i = Array.sub (h, i)
fun set i v = Array.update (h, i, v)
fun siftdown (i, ins, n) = let
fun sift k = let
val l = k * 2 + 1
val r = l + 1
in
if (r (get l) then r
else if (l
在数组实现中，siftdown函数融合了插入和筛选功能，它首先在暂时位于堆顶的要插入的元素，和从堆顶节点左右子堆的两个堆顶元素中筛选出的那个元素，二者中选择出哪个适合作堆顶元素；如果要插入元素适合，则以它为新堆顶元素而结束整个过程，否则以筛选出元素为新堆顶元素，并自顶向下逐级处理提供了新堆顶元素的子堆，将要插入元素暂时作为其堆顶元素并对它继续进行siftdown；siftdown只要到达了某个堆底，就插入要插入的元素而结束整个过程。

在提取堆顶元素生成结果列表时，先提取走堆顶元素的内容，再摘掉最后的堆底元素将它的内容暂时放置在堆顶，这时堆的大小也相应的减一，随后的siftdown函数，筛选出新的堆顶元素，并把原最后堆底元素插入回堆中。

在heapify函数建造堆的时候，首先自列表中间将元素分为前后两组，后组中的元素被视为只有一个元素的堆，然后从后往前处理前组中的元素，这时它的左右子节点已经是已有的堆或者为空，在其上进行siftdown，从而合成一个新堆。建造堆也可以采用siftup函数来实现，它自第二个元素开始从前往后逐个处理列表元素，其前面是已有的堆，将这个新元素自堆底向上插入到这个堆中。

堆排序算法也可以使用二叉树数据结构来实现二叉堆：

fun heapSort l = let
datatype 'a heap
= Nil
| Leaf of 'a
| Node of 'a int 'a heap * 'a heap
fun key Nil =
let val SOME a = Int.minInt in a end
| key (Leaf k) = k
| key (Node (k, _, _, _)) = k
fun count Nil = 0
| count (Leaf _) = 1
| count (Node (_, c, _, _)) = c
fun left Nil = Nil
| left (Leaf _) = Nil
| left (Node (_, _, l, _)) = l
fun insert (Nil, x) = Leaf x
| insert (Leaf k, l) =
if l >= k
then Node (l, 2, Leaf k, Nil)
else Node (k, 2, Leaf l, Nil)
| insert (Node (k, _, Leaf l, Nil), r) =
if r >= k
then Node (r, 3, Leaf k, Leaf l)
else if r >= l
then Node (k, 3, Leaf r, Leaf l)
else Node (k, 3, Leaf l, Leaf r)
| insert (Node (k, c, l, r), x) = let
val (k, x) =
if k >= x then (k, x) else (x, k)
in
if (count l) = (key l)
then Node (k, c + 1, insert (r, x), l)
else Node (k, c + 1, l, insert (r, x))
end
fun extract Nil = Nil
| extract (Leaf _) = Nil
| extract (Node (_, _, l, Nil)) = l
| extract (Node (_, c, l, r)) = let
val k = key l
val n = left l
in
if n = Nil
then Node (k, c - 1, r, Nil)
else if (key n) >= (key r)
then Node (k, c - 1, extract l, r)
else Node (k, c - 1, r, extract l)
end
fun heapify () = let
fun loop (acc, []) = acc
| loop (acc, x :: xs) =
loop (insert (acc, x), xs)
in
loop (Nil, l)
end
fun generate h = let
fun loop (acc, Nil) = acc
| loop (acc, h) =
loop ((key h) :: acc, extract h)
in
loop ([], h)
end
in
generate (heapify ())
end

二叉树实现不能直接访问堆底元素，从而不适宜通过摘掉它使堆的大小减一。这里的insert函数，在原堆顶元素和要插入元素中选择适合者作为新的堆顶元素，将落选的另一个元素作为新的要插入元素，插入到利于保持这个堆平衡的那个子树之中。这里的extract函数只筛选不插入，它将堆的大小减一。

这里的insert和extract函数也可以直接转写为等价的尾递归形式，与列表情况不同，只要树结构能保持良好的平衡，采用尾递归形式就没有太大的必要性。
在二叉树实现下，也可以采用siftdown函数来初始建造堆，而不需要在节点中保存关于树状态的统计信息。

基数排序
下面是针对非负整数的基数排序算法的实现：

fun radixSort l = let
fun distribute (l, d) = let
val t0 = ([], [], [], [], [], [], [], [])
fun loop (t, []) = let
fun join (acc, i) = let
val f = case i
of 1 => (#1 t) | 2 => (#2 t) | 3 => (#3 t)
| 4 => (#4 t) | 5 => (#5 t) | 6 => (#6 t)
| 7 => (#7 t) | 8 => (#8 t) | _ => []
in
if i (x :: f0, f1, f2, f3, f4, f5, f6, f7)
| 1 => (f0, x :: f1, f2, f3, f4, f5, f6, f7)
| 2 => (f0, f1, x :: f2, f3, f4, f5, f6, f7)
| 3 => (f0, f1, f2, x :: f3, f4, f5, f6, f7)
| 4 => (f0, f1, f2, f3, x :: f4, f5, f6, f7)
| 5 => (f0, f1, f2, f3, f4, x :: f5, f6, f7)
| 6 => (f0, f1, f2, f3, f4, f5, x :: f6, f7)
| 7 => (f0, f1, f2, f3, f4, f5, f6, x :: f7)
| _ => t0
in
loop (t, xs)
end
in
loop (t0, l)
end
val SOME maxInt = Int.maxInt
val max = foldl (fn (x, y) => if x > y then x else y) 0 l
fun iterate (l, d) = let
val l' = distribute (l, d)
in
if d >= (maxInt div 8 + 1) orelse
((max div d) div 8) = 0 then l'
else iterate (l', d * 8)
end
in
iterate (l, 1)
end

这里采用的基数是2的3次幂8，代码所使用的列表元组大小与基数大小成正比，运算量与列表中元素的总数与最大数的位数的乘积成正比。

随机数生成
编写排序算法进行测试除了使用简单的数列，
测试用列表还可以使用线性同余伪随机数函数来生成：

fun randList (n, seed) = let
val randx = ref seed
fun lcg () = (randx := (!randx * 421 + 1663) mod 7875; !randx)
( fun lcg () = (randx := (!randx 1366 + 150889) mod 714025; !randx) *)
fun iterate (acc, i) =
if i

语言解释器
定义和处理一个小型表达式语言是相对容易的：

exception Err;

datatype ty
= IntTy
| BoolTy

fun typeOf (True) = BoolTy
| typeOf (False) = BoolTy
| typeOf (Int _) = IntTy
| typeOf (Not e) =
if typeOf e = BoolTy
then BoolTy
else raise Err
| typeOf (Add (e1, e2)) =
if (typeOf e1 = IntTy) andalso (typeOf e2 = IntTy)
then IntTy
else raise Err
| typeOf (If (e1, e2, e3)) =
if typeOf e1 <> BoolTy
then raise Err
else if typeOf e2 <> typeOf e3 then raise Err
else typeOf e2

fun exp_repr e = let
val msg = case e
of True => "True"
| False => "False"
| Int n => Int.toString n
| _ => ""
in
msg ^ "\n"
end

( 忽略TypeOf的返回值，它在类型错误时发起Err )
fun evalPrint e = (ignore (typeOf e); print (exp_repr (eval e)));

将这段代码录入文件比如expr-lang.sml，并在命令行下执行sml expr-lang.sml，可以用如下在正确类型的和不正确类型上运行的例子，测试这个新语言：

val e1 = Add (Int 1, Int 2); ( 正确的类型 )

val e1 = Add (Int 1,Int 2) : exp

val _ = evalPrint e1;

val e2 = Add (Int 1, True); ( 不正确的类型 )

val e2 = Add (Int 1,True) : exp

val _ = evalPrint e2;

uncaught exception Err
raised at: expr-lang.sml:25.20-25.23

注释和附录代码
参见

Standard ML和它的实现：

** SML/NJ，由普林斯顿大学和贝尔实验室联合开发的实现，它具有工具ML-Lex、ML-Yacc和并发编程扩展Concurrent ML。
** MLton，严格遵循标准定义的强力的编译器，它具有工具MLLex、MLYacc和MLNLFFIGen。
** HaMLet，是一个SML解释器，由Andreas Rossberg在（MPI-SWS）编写，意图成为精确且无障碍的标准定义参考实现。
**LunarML，产生Lua/JavaScript代码的Standard ML编译器。

OCaml，由法国国家信息与自动化研究所（INRIA）维护，是一个“工业强度”的ML方言，演化自最初用来实现Coq定理证明器的Caml。
，由萨尔兰大学设计的Alice ML，是基于Standard ML的函数式编程语言，扩展了对并发、分布式和约束式编程的丰富支持。
，由波士顿大学的Hongwei Xi和卡内基·梅隆大学的提出的发展而来，它向ML扩展了依赖类型。
F#，由微软研究院（MSR）开发，是一个基于OCaml的一个以.NET为目标的编程语言。
F*，由MSR和INRIA主导开发，是一个基于ML的依赖类型函数式编程语言。
Futhark，由哥本哈根大学（DIKU）开发，是属于ML家族的一个函数式、数据并行、阵列编程语言。
Ur，由麻省理工学院的Adam Chlipala开发，是语法基于Standard ML的专门用于web开发的一个函数式编程语言。
CM-Lex和CM-Yacc，由卡内基·梅隆大学的Karl Crary开发，是用于Standard ML、OCaml和Haskell的词法分析器和语法解析器。

延伸阅读
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*

引用
外部链接
*
*
*[https://smlhelp.github.io/book/ SML Help]
*[https://github.com/standardml/cmlib cmlib]

评论 (0)