ML語言

**ML**（**M**eta **L**anguage：元語言），是一個函數式、指令式的通用的程式語言，它著稱於使用了多態的 Hindley–Milner 類型推論。ML 能自動的指定多數表達式的類型，不要求顯式的類型標註，而且能夠確保類型安全，已經正式證明了有良好類型的 ML 程序不會導致運行時間類型錯誤。

ML 提供了對函數實際參數的模式匹配、垃圾回收、指令式編程、傳值調用和柯里化。它被大量的用於程式語言研究之中，並且是全面規定了的和使用形式語義驗證了的少數語言之一。它的類型和模式匹配使得它非常適合併且經常用於在其他形式語言上進行操作，比如在編譯器構造、自動化定理證明和形式驗證中。

## 歷史

在 1970 年代早期，ML 由愛丁堡大學的羅賓・米爾納及他人研製出來，用於在 LCF 定理證明器中開發證明策略。LCF 的語言是「PPλ」，它是一階邏輯演算與有類型的多態 λ 演算的結合，以 ML 作為元語言。ML 的語法從 ISWIM 及其擴展實現 PAL 得到了啟發，LCF ML 運行在 DEC-10/TOPS-10 主機的 Stanford LISP 1.6 下。

在 1980 年，Luca Cardelli 於愛丁堡大學的 VAX/VMS 系統上開發了 ML 編譯器，它被稱為「VAX ML」，以區別於 LCF 版本的「DEC-10 ML」。VAX ML 的編譯器和運行時間系統二者，都是用 Pascal 書寫而建立在「函數抽象機器」（FAM）之上。在 1982 年，愛丁堡大學的 Kevin Mitchell，用 VAX ML 重寫了 VAX ML 編譯器，隨即 John Scott 和 Alan Mycroft 加入了開發，在又進行一系列重寫改進之後，新的編譯器被稱為「Edinburgh ML」。

在 1981 年，INRIA 的 Gérard Huet，將最初的 LCF ML 適配到 Multics 系統的 Maclisp 下，並且增加了編譯器。這個實現被描述於 INRIA 內部文檔「ML 手冊」之中，它被開發者自稱為「Le\_ML」。劍橋大學的 Lawrence Paulson 用它開發了基於 Franz Lisp 的 Cambridge LCF，進而劍橋大學的 Michael J. C. Gordon 又用它開發了基於 Common Lisp 的第一版的 HOL。

在 1983 年，Robin Milner 由兩個動機驅使開始重新設計 ML。其一是愛丁堡大學的 Rod Burstall 及其小組在規定上的工作，具體化為規定語言 CLEAR，和表達可執行規定的函數式語言 HOPE。這項工作與 ML 有關的是兩方面成果：首先，HOPE 擁有優雅的編程特徵，特別是模式匹配，和子句式函數定義；其次，是使用在接口中的簽名，進行規定的模塊化構造的想法。其二是 Luca Cardelli 在 VAX ML 上的工作，通過增加命名記錄和可變類型，擴展了 ML 中數據類型的品目。

在 1984 年，貝爾實驗室的 David MacQueen 提出了對 Standard ML 的模塊系統的設計。在 Standard ML 的持續設計期間，Edinburgh ML 被漸進的修改，充當了 Standard ML 的近似原型實現。在 1986 年，普林斯頓大學的 Andrew Appel 和貝爾實驗室的 David MacQueen，以 Edinburgh Standard ML 作為起步開發環境，開始了專注於生成高質量機器代碼的 Standard ML of New Jersey 的活躍開發。

在 1990 年，Robin Milner、Mads Tofte 和 Robert Harper 制定的 Standard ML 的正式規定《The Definition of Standard ML》最終完成；在 1997 年，這個標準規定增補了 David MacQueen 為作者並進行了修訂。在 1989 年，Mads Tofte、Nick Rothwell 和 David N. Turner 於愛丁堡大學開始開發 ML Kit 編譯器，為了強調清晰性而非高效，將標準定義直接轉譯成一組 Standard ML 模塊；在 1992 年和 1993 年期間，主要通過愛丁堡大學的 Nick Rothwell 和哥本哈根大學計算機科學系（DIKU）的 Lars Birkedal 的工作，ML Kit 第一版完成並開源發行。

在 1987 年，INRIA 的 Ascánder Suárez，基於巴黎第七大學的 Guy Cousineau 的「範疇抽象機器」（CAM），利用 Le Lisp 的運行時間系統重新實現了 Le\_ML，並正式命名為 Caml。在 1990 年和 1991 年，INRIA 的 Xavier Leroy 基於用 C 實現的字節碼解釋器，利用 Damien Doligez 提供的內存管理系統重新實現了 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、ATS 和 Elm。

## 解釋與編譯

ML 代碼片段很容易通過將其錄入到「頂層」來研習，它也叫作讀取﹣求值﹣輸出循環或 REPL。這是列印結果或定義的表達式的推論類型的交互式會話。很多 SML 實現提供交互式 REPL，比如 SML/NJ：

可以在提示符 `-` 後鍵入代碼。例如計算 `1 + 2 * 3`:

頂層推論這個表達式的類型為 `int` 並給出結果 `7`。如果輸入不完全則列印第二提示符 `=`，這時經常可以用 `;` 終結輸入。`it` 是給未指定變量的表達式的標準變量。輸入 control-C 可返回解釋器頂層，輸入 control-D 可退出解釋器。

下面是 hello, world! 的程序代碼在 SML/NJ 解釋器下執行的結果：

和使用 MLton 編譯器進行編譯執行的例子：

## 核心語言

不同於純函數式編程語言，ML 是兼具一些指令式特徵的函數式編程語言。ML 的特徵包括：傳值調用的求值策略，頭等函數，帶有垃圾收集的自動內存管理，參數多態，靜態類型，類型推論，代數數據類型，模式匹配和異常處理。不同於 Haskell，ML 與大多數程式語言一樣使用及早求值。

用 ML 書寫的程序構成自要被求值的表達式，而非語句或命令，儘管一些表達式返回一個平凡的 `unit` 值並且只為其副作用而求值。以下章節介紹採用 Standard ML 的語法和語義。

### 函數

就像所有的函數式語言一樣，ML 的關鍵特徵是函數，它被用於進行抽象。例如階乘函數用純 ML 可表達為：

這裡將階乘描述為遞歸函數，具有一個單一的終止基礎情況。它類似於在數學教科書見到的階乘描述。多數 ML 代碼在設施和語法上類似於數學。

憑藉類型推論編譯器能推導出，`fac` 接受整數 `0` 作為實際參數，則形式參數 `n` 也是整數類型 `int`，而 `fac 0` 的結果是整數 `1`，則函數 `fac` 的結果也是整數類型。函數 `fac` 接受一個整數的形式參數並返回一個整數結果，它作為一個整體從而有著「從整數到整數的函數」類型 `int -> int`。函數及其形式參數的 "類型" 還可以用類型標註（annotation）來描述，使用 `E : t` 表示法，它可以被讀作表達式 `E` 有類型 `t`，它是可選也可忽略的。使用類型標註，這個例子可重寫為如下：

這個函數還依賴於模式匹配，這是 ML 語言的重要部份。注意函數形式參數不必須在圓括號內但要用空格分隔。當一個函數的實際參數是 `0`，它將返回整數 `1`。對於所有其他情況，嘗試第二行。這是一個遞歸，並且再次執行這個函數直到達到基礎情況。它可以使用 `case` 表達式重寫為：

這裡 `case` 介入了模式和對應表達式的序列。它還可以重寫為將標識符綁定到 lambda 函數：

這裡的關鍵字 `val` 介入了標識符到值的綁定，`fn` 介入了匿名函數的定義，它可以用在 `fun` 的位置上，但使用 `=>` 算符而非 `=`。綁定到遞歸的匿名函數需要使用 `rec` 關鍵字來指示。

通過將主要工作寫入尾遞歸風格的內部迭代函數，藉助於語言編譯或解釋系統進行的尾調用優化，這個函數可以得以增進性能，它的調用棧不需要隨函數調用數目而成比例的增長。對這個函數可以採用向內部函數增加額外的「累加器」形式參數 `acc` 來實現：

`let` 表達式的值是在 `in` 和 `end` 之間表達式的值。這個遞歸函數的實現不保證能夠終止，因為負數實際參數會導致遞歸調用的無窮降鏈條件。更健壯的實現會在遞歸前檢查實際參數為非負數，並在有問題的情況，即 `n` 是負數的時候，啟用異常處理：

### 類型

有一些基本類型可以當作是「內建」的，因為它們是在 Standard ML 標準基本庫中預先定義的，並且語言為它們提供文字表示法，比如 `34` 是整數，而 `"34"` 是字符串。一些最常用的基本類型是：

* `int` 整數，比如 `3` 或 `~12`。注意波浪號~表示負號。
* `real` 浮點數，比如 `4.2` 或 `~6.4`。Standard ML 不隱含的提升整數為浮點數，因此表達式 `2 + 5.67` 是無效的。
* `string` 字符串，比如 `"this is a string"` 或 `""`（空串）。
* `char` 字符，比如 `#"y"` 或 `#"\n"`（換行符）。
* `bool` 布爾值，它是要麼 `true` 要麼 `false`。產生 `bool` 值的有比較算符 `=`、`<>`、`>`、`>=`、`<`、`<=`，邏輯函數 `not` 和短路求值的中綴算符 `andalso`、`orelse`。

包括上述基本類型的各種類型可以用多種方式組合。一種方式是元組，它是值的有序集合，比如表達式 `(1, 2)` 的類型是 `int * int`，而 `("foo", false)` 的類型是 `string * bool`。可以使用 `#1 ("foo", false)` 這樣的語法來提取元組的指定次序的成員。

有 0 元組 `()`，它的類型指示為 `unit`。但是沒有 1 元組，或者說在例子 `(1)` 和 `1` 之間沒有區別，都有類型 `int`。元組可以嵌套，`(1, 2, 3)` 不同於 `((1, 2), 3)` 和 `(1, (2, 3))` 二者。前者的類型是 `int * int * int`，其他兩個的類型分別是 `(int * int) * int` 和 `int * (int * int)`。

組合值的另一種方式是記錄。記錄很像元組，除了它的成員是有名字的而非有次序的，例如 `{a = 5.0, b = "five"}` 有類型 `{a : real, b : string}`，這同於類型 `{b : string, a : real}`。可以使用 `#a {a = 5.0, b = "five"}` 這樣的語法來選取記錄的指定名字的欄位。

Standard ML 中的函數隻接受一個值作為參數，而不是參數的一個列表，可以使用上述元組模式匹配來實際上傳遞多個參數。函數還可以返回一個元組。例如：

這裡第一段創建了兩個類型是 `int * int -> int` 的函數 `sum` 和 `average`。第二段創建中綴算子 `averaged_with`，接著定義它為類型 `int * int -> int` 的函數。最後的 `int_pair` 函數的類型是 `int -> int * int`。

下列函數是多態類型的一個例子：

編譯器無法推論出的 `pair` 的特殊化了的類型，它可以是 `int -> int * int`、`real -> real * real` 甚至是 `(int * real -> string) -> (int * real -> string) * (int * real -> string)`。在 Standard ML 中，它可以簡單指定為多態類型 `'a -> 'a * 'a`，這裡的 `'a`（讀作「alpha」）是一個類型變量，指示任何可能的類型。在上述定義下，`pair 3` 和 `pair "x"` 都是有良好定義的，分別產生 `(3, 3)` 和 `("x", "x")`。

SML 標準基本庫包括了重載標識符：`+`、`-`、`*`、`div`、`mod`、`/`、`~`、`abs`、`<`、`>`、`<=`、`>=`。標準基本庫提供了多態函數：`!`、`:=`、`o`、`before`、`ignore`。中綴運算符可以有從預設最低 `0` 到最高 `9` 的任何運算符優先級。標準基本庫提供了如下內建中綴規定：

### 等式類型

算符 `=` 和 `<>` 分別被定義為多態的等式和不等式。`=` 它確定兩個值是否相等，有著類型 `''a * ''a -> bool`。這意味著它的兩個運算數必須有相同的類型，這個類型必須是等式類型（`eqtype`）。上述基本類型中除了 `real` 之外，`int`、`real`、`string`、`char` 和 `bool` 都是等式類型。

例如：`3 = 3`、`"3" = "3"`、`#"3" = #"3"` 和 `true = true`，都是有效的表達式並求值為 `true`；而 `3 = 4` 是有效表達式並求值為 `false`，`3.0 = 3.0` 是無效表達式而被編譯器拒絕。這是因為 IEEE 浮點數等式打破了 ML 中對等式的一些要求。特別是 `nan` 不等於自身，所以關係不是自反的。

元組和記錄類型是等式類型，當時且僅當它的每個成員類型是等式類型；例如 `int * string`、`{b : bool, c : char}` 和 `unit` 是等式類型，而 `int * real` 和 `{x : real}` 不是。函數類型永遠不是等式類型，因為一般情況下不可能確定兩個函數是否等價。

### 類型聲明

類型聲明或同義詞（synonym）使用 `type` 關鍵字來定義。下面是給在平面中的點的類型聲明，計算兩點間距離，和通過海倫公式計算給定角點的三角形的面積的函數。

### 數據類型

Standard ML 提供了對代數數據類型（ADT）的強力支持。一個 ML 數據類型可以被當作是元組的不交並（積之和）。數據類型使用 `datatype` 關鍵字來定義，比如：

這個數據類型聲明建立一個全新的數據類型 `int_or_string`，還有一起的新構造子（一種特殊函數或值）`INT`、`STRING` 和 `NEITHER`；每個這種類型的值都是要麼 `INT` 具有一個整數，要麼 `STRING` 具有一個字符串，要麼 `NEITHER`。寫為如下這樣：

這裡最後的一個聲明通過模式匹配，將變量 `j` 綁定到變量 `i` 所綁定的整數 `3`。`val 模式 = 表达式` 是綁定的一般形式，它是良好定義的，若且唯若模式和表達式有相同的類型。

數據類型可以是多態的：

這個數據類型聲明建立一個新的類型 `'a pair` 家族，比如 `int pair`，`string pair` 等等。

數據類型可以是遞歸的：

這個數據類型聲明建立一個新類型 `int_list`，這個類型的每個值是要麼 `EMPTY`（空列表），要麼是一個整數和另一個 `int_list` 的接合。

通過 `datatype` 創建的類型是等式類型，如果它的所有變體，要麼是沒有參數的空構造子，要麼是有等式類型參數的構造子，並且在多態類型情況下所有類型參數也都是等式類型。遞歸類型在有可能情況下是等式類型，否則就不是。

### 列表

基礎庫提供的複雜數據類型之一是列表 `list`。它是一個遞歸的、多態的數據類型，可以等價的定義為：

這裡的 `::` 是中綴算符，例如 `3 :: 4 :: 5 :: nil` 是三個整數的列表。列表是 ML 程序中最常用的數據類型之一，語言還為生成列表提供了特殊表示法 `[3, 4, 5]`。

`real list` 當然不是等式類型。但是沒有 `int list` 不能是等式類型的理由，所以它就是等式類型。注意類型變量不同就是不同的列表類型，比如 `(nil : int list) = (nil : char list)` 是無效的，因為兩個表達式有不同的類型，即使它們有相同的值。但是 `nil = nil` 和 `(nil : int list) = nil` 都是有效的。

基本庫 `rev` 函數「反轉」一個列表中的元素。它的類型是 `'a list -> 'a list`，就是說它可以接受其元素有任何類型的列表，並返回相同類型的列表。更準確的說，它返回其元素相較於給定列表是反轉次序的一個新列表，比如將 `[ "a", "b", "c" ]` 映射成 `[ "c", "b", "a" ]`。中綴算符 `@` 表示兩個列表的串接。

`rev` 和 `@` 一般被實現為基本庫函數 `revAppend` 的簡單應用：

### 模式匹配

Standard ML 的數據類型可以輕易的定義和用於編程，在很大程度上是由它的模式匹配，還有多數 Standard ML 實現的模式窮盡性檢查和模式冗餘檢查。

模式匹配可以在語法上嵌入到變量綁定之中，比如：

第一個 `val` 綁定了四個變量 `m`、`n`、`r` 和 `s`；第二個 `val` 綁定了一個變量 `url`；第三個 `val` 綁定了三個變量 `port`、`addr` 和 `name`，第四個叫分層模式，綁定了三個變量 `x`、`fst` 和 `snd`。

模式匹配可以在語法上嵌入到函數定義中，比如：

次序在模式匹配中是緊要的：模式按文本次序來依次進行匹配。在特定計算中，使用下劃線 `_`，來省略不需要它的值的子成員，這也叫做通配符（wildcard）模式。所謂的「子句形式」風格的函數定義，這裡的模式緊隨在函數名字之後出現，只是如下形式的一種語法糖：

模式窮盡性檢查將確保數據類型的每個情況都已經顧及到。
如果有遺漏，則產生警告。
如果模式存在冗餘，也會導致一個編譯時間警告。

### 高階函數

函數可以接受函數作為實際參數，比如：

函數可以產生函數作為返回值，比如：

函數可以同時接受和產生函數，比如複合函數：

基本庫的函數 `List.map`，是在 Standard ML 中最常用的 Curry 化高階函數，它在概念上可定義為：

在基本庫中將函數複合定義為多態中綴算符 `(f o g)`，`map` 和 `fold` 高階函數有較高效率的實現。

### 異常

異常可以使用 `raise` 關鍵字發起，並通過模式匹配 `handle` 構造來處理：

這裡的 `^` 是字符串串接算符。可以利用異常系統來實現非局部退出，例如這個函數所採用技術：

異常 `Zero` 在 `0` 情況下發起，控制從函數 `p` 中一起出離。

### 引用

初始化基礎庫還以引用的形式提供了可變的存儲。引用 `ref` 可以在某種意義上被認為是如下這樣定義的：

還定義了內建的 `:=` 函數來修改引用的內容，和 `!` 函數來檢索引用的內容。階乘函數可以使用引用定義為指令式風格：

這裡使用圓括號對以 `;` 分隔的表達式進行了順序複合。

可變類型 `'a ref` 是等式類型，即使它的成員類型不是。兩個引用被稱為是相等的，如果它們標識相同的「`ref` 單元」，就是說相同的對 `ref` 構造子調用生成的同一個指針。因此 `(ref 1) = (ref 1)` 和 `(ref 1.0) = (ref 1.0)` 都是有效的，並且都求值為 `false`，因為即使兩個引用碰巧指向了相同的值，引用自身是分立的，每個都可以獨立於其他而改變。

## 模塊語言

模塊是 ML 用於構造大型項目和庫的系統。

### 模塊

一個模塊構成自一個簽名（signature）文件和一個或多個結構文件。簽名文件指定要實現的 API（就像 C 語言頭文件或 Java 接口文件）。結構實現這個簽名（就像 C 語言源文件或 Java 類文件）。解釋器通過 `use` 命令導入它們。ML 的標準庫被實現為這種方式的模塊。

例如，下列定義一個算術簽名：

和這個簽名使用有理數的實現：

下面是這個結構的簡單用例：

Standard ML 只允許通過簽名函數同實現進行交互，例如不可以直接通過這個代碼中的 `Rat` 來建立數據對象。結構塊對外部隱藏所有實現細節。這裡的 `:` 叫做透明歸屬（ascription），可以通過所綁定的變量見到此結構的數據內容，與之相對的是 `:>`，它叫做不透明歸屬，此結構的數據內容對外完全不可見。比如上面用例有結果：`val c = Rat (4,3) : Rational.t`，如果改為不透明歸屬則有結果：`val c = - : Rational.t`。

要用有理數進行實際上的數值計算，需要處理分數形式中分母快速增大導致溢出整數類型大小範圍等問題。

### 函子

函子接受指定簽名的一個結構作為參數，並返回一個結構作為結果，下面示例的函子能在 `ARITH` 簽名的結構上計算移動平均：

和這個函子的簡單用例：

這個用例承上節示例，`Rational` 結構採用了透明歸屬，有結果如：`val d = ([Rat (4,5),Rat (2,3)],2,Rat (11,15)) : MLR.t`。如果它改為不透明歸屬，則對應結果為：`val d = ([-,-],2,-) : MLR.t`。

## 示例代碼

下列例子使用了 Standard ML 的語法和語義。

### 素數

下面是求素數的試除法實現：

基本庫 `find` 和 `exists` 函數在不存在符合條件元素的時候會遍歷整個列表，
這裡採用了特殊化了的 `existsDivisor`，用以在後續元素都不滿足條件時立即結束運算。

下面是埃拉托斯特尼篩法實現：

這裡基於列表的篩法實現符合埃拉托斯特尼的原初算法。篩法還有基於數組的直觀實現。
下面是其解釋器下命令行運行實例：

### 漢明數

正規數是形如 $\ 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`，並以此類推。

示例漢明數程序代碼，一般用來展示，確使計算只在需要時進行的純函數式編程方式。

產生指定範圍內的漢明數需要多輪運算，後面每輪中的三個列表元素乘積運算中都可能產生超出這個範圍的結果，它們不需要出現在後續的運算之中。
基本庫 `mapPartial` 函數與它所映射的函數，通過基於 `Option` 結構的 `SOME` 和 `NONE` 構造子的協定，可以將所映射函數認為不符合條件的元素或者結果排除掉，它會遍歷整個列表。
由於這個算法採用升序列表，故而這裡將它改寫為 `mapPrefix` 函數，用來在特定條件不滿足條件就立即結束。下面是漢明數程序在解釋器下命令行運行實例：

### 續體傳遞風格實例

下面是續體傳遞風格（CPS）的高階函數 foldr 和 map 的實現，和達成一個整數列表的合計函數的簡單用例：

對於輸入 `[e1, e2, ..., en]`，`sum` 函數等價於函數複合 `(fn x => x) o (fn x => e1 + x) o (fn x => e2 + x) o ... o (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)`，它等同於對反轉過的列表應用變體插入排序。

#### 希爾排序

希爾排序算法是對插入排序的改進，保持了自適應性，放棄了穩定性。
下面是希爾排序的實現：

這裡採用的間隔序列是 OEIS A108870，即 $\ {\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 < hk ≤ s < hk+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 A102549，它是 Marcin Ciura 在 2001 年通過實驗得到的。

#### 快速排序

下面是快速排序算法的自頂向下實現：

基本庫 `partition` 函數實現對快速排序而言有不必要的反轉，
這裡採用了它的簡化改寫。在 ML 中快速排序應採用自底向上實現：

#### 歸併排序

下面是歸併排序算法的自底向上法實現：

考慮輸入列表 `[x1, ..., xi, a0, ..., a9, xj, ..., xn]`，這裡在 `xi` 和 `xj` 之間的 `10` 個 `a`，具有相同的值並且需要保持其下標表示的次序，這裡的 `xi > a` 並且 `xj < a`，並且在這個區段前後的元素總數都能被 `3` 整除，則它被分解成子列表的列表 `[Xm, ..., [xj, a8, a9], [a5, a6, a7], [a2, a3, a4], [a0, a1, xi], ..., X1]`，這裡有 `m = n div 3`；假定這 `4` 個含有 `a` 的子列表兩兩歸併，在歸併正序子列表的歸併條件 `x < y` 下，能得到 `[X1, ..., [xi, a4, ..., a0], [a9, ..., a5, xj], ..., Xk]`；繼續推演下去，在歸併反序子列表的歸併條件 `x > y` 下，能得到 `[Xh, ..., [xj, a0, ..., a9, xi], ..., X1]`。可以看出這種歸併操作能夠保證排序算法的穩定性，即具有相同值的元素之間的相對次序保持不變。

分解初始的子列表採用了插入排序，還可進一步增加其大小。歸併排序也有自頂向下實現。

#### 堆排序

下面是堆排序的基於數組的實現：

在數組實現中，`siftdown` 函數融合了插入和篩選功能，它首先在暫時位於堆頂的要插入的元素，和從堆頂節點左右子堆的兩個堆頂元素中篩選出的那個元素，二者中選擇出哪個適合作堆頂元素；如果要插入元素適合，則以它為新堆頂元素而結束整個過程，否則以篩選出元素為新堆頂元素，並自頂向下逐級處理提供了新堆頂元素的子堆，將要插入元素暫時作為其堆頂元素並對它繼續進行 `siftdown`；`siftdown` 只要到達了某個堆底，就插入要插入的元素而結束整個過程。

在提取堆頂元素生成結果列表時，先提取走堆頂元素的內容，再摘掉最後的堆底元素將它的內容暫時放置在堆頂，這時堆的大小也相應的減一，隨後的 `siftdown` 函數，篩選出新的堆頂元素，並把原最後堆底元素插入回堆中。

在 `heapify` 函數建造堆的時候，首先自列表中間將元素分為前後兩組，後組中的元素被視為只有一個元素的堆，然後從後往前處理前組中的元素，這時它的左右子節點已經是已有的堆或者為空，在其上進行 `siftdown`，從而合成一個新堆。建造堆也可以採用 `siftup` 函數來實現，它自第二個元素開始從前往後逐個處理列表元素，其前面是已有的堆，將這個新元素自堆底向上插入到這個堆中。

堆排序算法也可以使用二元樹資料結構來實現二叉堆：

二元樹實現不能直接訪問堆底元素，從而不適宜通過摘掉它使堆的大小減一。這裡的 `insert` 函數，在原堆頂元素和要插入元素中選擇適合者作為新的堆頂元素，將落選的另一個元素作為新的要插入元素，插入到利於保持這個堆平衡的那個子樹之中。這裡的 `extract` 函數隻篩選不插入，它將堆的大小減一。

這裡的 `insert` 和 `extract` 函數也可以直接轉寫為等價的尾遞歸形式，與列表情況不同，只要樹結構能保持良好的平衡，採用尾遞歸形式就沒有太大的必要性。
在二元樹實現下，也可以採用 `siftdown` 函數來初始建造堆，而不需要在節點中保存關於樹狀態的統計信息。

#### 基數排序

下面是針對非負整數的基數排序算法的實現：

這裡採用的基數是 `2` 的 `3` 次冪 `8`，代碼所使用的列表元組大小與基數大小成正比，運算量與列表中元素的總數與最大數的位數的乘積成正比。

### 隨機數生成

編寫排序算法進行測試除了使用簡單的數列，
測試用列表還可以使用線性同餘偽隨機數函數來生成：

### 語言解釋器

定義和處理一個小型表達式語言是相對容易的：

將這段代碼錄入文件比如 `expr-lang.sml`，並在命令行下執行 `sml expr-lang.sml`，可以用如下在正確類型的和不正確類型上運行的例子，測試這個新語言：

## 注釋和附錄代碼

## 參見

* Standard ML 和它的實現：
  * SML/NJ，由普林斯頓大學和貝爾實驗室聯合開發的實現，它具有並發編程擴展 Concurrent ML。
  * MLton，嚴格遵循標準定義的強力的全程序優化編譯器。
  * HaMLet，由馬克斯・普朗克軟體系統研究所（MPI-SWS）的 Andreas Rossberg 編寫，是一個 SML 解釋器，意圖成為精確且合宜接近的標準定義參考實現。
* OCaml，由法國國家信息與自動化研究所（INRIA）維護，是一個「工業強度」的 ML 方言，演化自最初用來實現 Coq 定理證明器的 Caml。
* Alice，由薩爾蘭大學設計的 Alice ML，是基於 Standard ML 的函數式程式語言，擴展了對並發、分布式和約束式編程的豐富支持。
* ATS，由波士頓大學的 Hongwei Xi 和卡內基・梅隆大學的 Frank Pfenning 提出的 Dependent ML 發展而來，它向 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 的詞法分析器和語法解析器。
* Amulet，是一個類 ML 的函數式程式語言，其編譯器輸出 Lua 文件。
* Alpaca，是一個受 ML 啟發的運行在 Erlang 虛擬機上的函數式程式語言。

## 延伸閱讀

* Robin Milner, Mads Tofte, Robert Harper. The Definition of Standard ML (PDF). MIT Press. 1990 [2021-03-01]. （原始內容 (PDF) 存檔於 2021-01-14）.
* Robin Milner, Mads Tofte, Robert Harper, David MacQueen. The Definition of Standard ML, Revised (PDF). MIT Press. 1997 [2021-03-01]. ISBN0-262-63181-4. （原始內容 (PDF) 存檔於 2022-03-09）.
* Robin Milner, Mads Tofte. Commentary on Standard ML. MIT Press. 1991 [2021-08-31]. ISBN978-0-262-63137-2. （原始內容存檔於 2021-08-31）.
* Emden R. Gansner, John H. Reppy. The Standard ML Basis Library (PDF). Cambridge University Press. 2004 [2021-09-17]. （原始內容 (PDF) 存檔於 2022-01-29）.
* Mads Tofte. Four Lectures on Standard ML (PDF). University of Edinburgh. 1989 [2021-09-04]. （原始內容 (PDF) 存檔於 2022-01-28）.  Code examples in lectures. [2021-09-11]. 原始內容存檔於 2016-04-02.
* Mads Tofte. Essentials of Standard ML Modules. DIKU. 1996 [2021-09-04]. （原始內容存檔於 2021-09-04）.  The SML code (uuencoded compressed tar). [2021-09-18]. 原始內容存檔於 2005-03-07.
* Mads Tofte. Tips for Computer Scientists on Standard ML (Revised) (PDF). ITU. 2009 [2021-09-04]. （原始內容 (PDF) 存檔於 2021-11-27）.  Examples. [2022-01-03]. 原始內容存檔於 2017-09-15.
* Robert Harper. Programming in Standard ML (PDF). Carnegie Mellon University. 2011 [2021-02-27]. （原始內容 (PDF) 存檔於 2020-02-15）.  Examples. [2021-09-12]. （原始內容存檔於 2021-09-12）.
* Michael J. C. Gordon. Introduction to Functional Programming. Cambridge University. 1996 [2021-09-11]. （原始內容存檔於 2021-04-11）.  Lecture notes. [2021-09-11]. （原始內容存檔於 2006-06-23）.
* Lawrence Paulson. ML for the Working Programmer, 2nd Edition. Cambridge University Press. 1996 [2021-08-31]. ISBN0-521-56543-X. （原始內容存檔於 2022-02-24）.  Sample programs. [2021-09-12]. （原始內容存檔於 2022-01-19）.
* David MacQueen. Should ML be Object-Oriented? (PDF). 2002 [2021-09-10]. （原始內容 (PDF) 存檔於 2021-10-29）.
* David MacQueen, Robert Harper, John Reppy. The History of Standard ML. 2020 [2021-08-31]. （原始內容存檔於 2021-12-01）.
* Andrew W. Appel. Compiling with Continuations. Cambridge University Press. 1992 [2022-01-03]. （原始內容存檔於 2022-01-03）.
* Andrew W. Appel. Modern Compiler Implementation in ML. Cambridge University Press. 1998 [2022-01-12]. （原始內容存檔於 2022-01-12）.  Tiger compiler modules for programming exercises. [2021-09-12]. （原始內容存檔於 2022-05-06）.
* Jeffrey D. Ullman. Elements of ML Programming, ML97 Edition. Prentice-Hall. 1998 [2021-12-30]. ISBN0-13-790387-1. （原始內容存檔於 2022-03-12）.  Programs from the text. [2022-01-01]. （原始內容存檔於 2022-02-14）.
* Anthony L. Shipman. Unix System Programming with Standard ML (PDF). 2001 [2021-09-01]. （原始內容 (PDF) 存檔於 2021-01-21）.

## 引用

## 外部連結

* Andreas Rossberg. Standard ML and Objective Caml, Side by Side. 2011 [2021-08-31]. （原始內容存檔於 2021-12-30）.
* Adam Chlipala. Comparing Objective Caml and Standard ML. 2020 [2021-08-31]. （原始內容存檔於 2021-12-16）.
* SML Help （頁面存檔備份，存於網際網路檔案館）
* cmlib （頁面存檔備份，存於網際網路檔案館）