1. 背景
Standard ML 語言由1983提案（proposed），經(jīng)過1984年至1988年進(jìn)行設(shè)計（designed）眯亦，
規(guī)范《The Definition of Standard ML》，最終在1990年完成（defined）般码。
Standard ML '97 是 Standard ML 的簡化版妻率，
修訂版規(guī)范《The Definition of Standard ML (Revised)》于1997年完成。
修訂版的 Standard ML '97 有時候也稱為 Standard ML板祝，或者 Standard ML '97宫静，SML '97，
為了區(qū)分券时，1990年的 Standard ML 也稱為 SML '90孤里。
2. 模塊語言
Standard ML 程序可以劃分為獨立的單元（unit），程序單元也稱為結(jié)構(gòu)（structure）橘洞。
結(jié)構(gòu)中包含了一些類型（type）和值（value）捌袜，
借助簽名（signature）可以將多個結(jié)構(gòu)組合成更大的結(jié)構(gòu)，
因此震檩，較大的結(jié)構(gòu)可以按層級劃分成不同的子結(jié)構(gòu)（substructure）琢蛤。
其中，簽名可以看做是結(jié)構(gòu)自身的類型（type）抛虏，
泛型化或參數(shù)化的結(jié)構(gòu)博其，也被稱為函子（functor）。
3. 簽名和結(jié)構(gòu)
A signature may be thought of as a description of a structure, and a structure may correspondingly be thought of as an implementation of a signature.
簽名可以看做是結(jié)構(gòu)的規(guī)范描述迂猴，結(jié)構(gòu)可以看做是簽名的具體實現(xiàn)慕淡。
其他語言中也有類似的概念，簽名通常被稱為接口沸毁，或包的規(guī)范（package speci?cations）峰髓，
結(jié)構(gòu)通常被稱為實現(xiàn)（implementation）或包（package）。
而與其他語言不同的是息尺，Standard ML 中的簽名和結(jié)構(gòu)之間是多對多關(guān)系携兵。
一個簽名可以描述多個不同的結(jié)構(gòu)，一個結(jié)構(gòu)可以同時滿足多個不同的簽名搂誉。
3.1 簽名
A signature is a speci?cation, or a description, of a program unit, or structure.
簽名是一段程序單元（或結(jié)構(gòu)）的規(guī)范徐紧，或描述。
結(jié)構(gòu)由類型構(gòu)造器炭懊，異常構(gòu)造器并级，值的綁定關(guān)系構(gòu)成，
而簽名則指定了結(jié)構(gòu)的約束條件（requirement）侮腹，例如嘲碧，
結(jié)構(gòu)應(yīng)當(dāng)包含哪些類型，包含哪些值父阻，這些值的類型是什么愈涩，等等。
一個結(jié)構(gòu)如果滿足了這些約束條件（requirement）至非，
我們就說它匹配了（match）或?qū)崿F(xiàn)了（implement）該簽名钠署。
signature QUEUE =
sig
type ’a queue
exception Empty
val empty : ’a queue
val insert : ’a * ’a queue -> ’a queue
val remove : ’a queue -> ’a * ’a queue
end
以上代碼定義了一個名為QUEUE的簽名。
匹配該簽名的結(jié)構(gòu)荒椭，必須滿足以下條件：
（1）有一個單參類型構(gòu)造器谐鼎，'a queue，
（2）有一個零參異常趣惠，Empty狸棍，
（3）有一個值empty，它是多態(tài)類型的'a queue味悄，
（4）有兩個多態(tài)函數(shù)草戈，insert和remove。
3.2 簽名的繼承（inheritance）
通過包含（signature inclusion）和特化（signature specialization）侍瑟，
我們可以使用現(xiàn)有的簽名唐片，得到另一個新的簽名丙猬，
這是繼承（inheritance）簽名的兩種形式。
（1）包含
包含用于得到费韭，比已有簽名具有更多內(nèi)容的簽名茧球。
signature QUEUE_WITH_EMPTY =
sig
include QUEUE
val is empty : ’a queue -> bool
end
（2）特化
特化用于得到，比已有簽名中的類型更具體的簽名星持。
signature QUEUE_AS_LISTS =
QUEUE where type ’a queue = ’a list * ’a list
3.3 結(jié)構(gòu)
結(jié)構(gòu)由類型構(gòu)造器抢埋，異常構(gòu)造器，值的綁定關(guān)系構(gòu)成督暂。
Structures are implementations of signatures; signatures are the types of structures.
結(jié)構(gòu)實現(xiàn)了簽名揪垄，簽名是結(jié)構(gòu)的類型。
structure Queue =
struct
type ’a queue = ’a list * ’a list
exception Empty
val empty = (nil, nil)
fun insert (x, (b,f)) = (x::b, f)
fun remove (nil, nil) = raise Empty
| remove (bs, nil) = remove (nil, rev bs)
| remove (bs, f::fs) = (f, (bs, fs))
end
以上代碼定義一個名為Queue的結(jié)構(gòu)逻翁，它實現(xiàn)了簽名QUEUE饥努。
3.4 匹配（mathing）
我們說一個解構(gòu)實現(xiàn)了某個簽名，指的是八回，
該結(jié)構(gòu)滿足簽名中所要求的一切類型定義肪凛。
結(jié)構(gòu)中提供的類型構(gòu)造器，必須與簽名中所要求的具有相同數(shù)目的參數(shù)辽社，
結(jié)構(gòu)中提供的值伟墙，必須滿足簽名中所要求的類型，
結(jié)構(gòu)中提供的異常滴铅，其參數(shù)類型也必須與簽名中所要求的一樣戳葵。
我們把結(jié)構(gòu)所能滿足的最嚴(yán)格（stringent），最精確的（precise）簽名汉匙，稱為它的主簽名（principal signature）拱烁。
我們說一個結(jié)構(gòu)精確（exactly）匹配（match）到了一個簽名上，
如果該簽名沒有比主簽名提供更多的約束條件噩翠。
如果簽名sigexp_1戏自，具有sigexp_2中所有的約束條件，
我們就說伤锚，簽名sigexp_1可以匹配簽名sigexp_2擅笔。
signature QUEUE =
sig
type ’a queue
exception Empty
val empty : ’a queue
val insert : ’a * ’a queue -> ’a queue
val remove : ’a queue -> ’a * ’a queue
end
signature QUEUE_WITH_EMPTY =
sig
include QUEUE
val is empty : ’a queue -> bool
end
signature QUEUE_AS_LISTS =
QUEUE where type ’a queue = ’a list * ’a list
其中，簽名QUEUE_WITH_EMPTY和QUEUE_AS_LISTS都可以匹配到QUEUE上屯援。
3.5 歸屬（ascription）
簽名歸屬（signature ascription）將一個結(jié)構(gòu)強(qiáng)行指定到一個簽名上面猛们，
從而限制了以后該結(jié)構(gòu)的被使用的靈活度。
Standard ML中有兩種方式對結(jié)構(gòu)進(jìn)行歸屬狞洋，
（1）透明或描述性歸屬（transparent, or descriptive ascription）
structure strid : sigexp = strexp
（2）不透明或限制性的歸屬（opaque, or restrictive ascription）
structure strid :> sigexp = strexp
透明歸屬使用冒號:弯淘，不透明歸屬使用:>。
這兩種歸屬方式中吉懊，確定結(jié)構(gòu)strid簽名的步驟如下庐橙，
（1）驗證strexp是否實現(xiàn)了sigexp假勿，
我們通過strexp的主簽名sigexp_0，是否可以匹配到sigexp上來確定态鳖。
（2）在匹配過程中废登，主簽名sigexp_0中，可能包含了比sigexp中更多的類型郁惜，
于是，我們將得到一個sigexp的增強(qiáng)版sigexp'
（3）對于透明歸屬甲锡，strid的簽名為增強(qiáng)版sigexp'兆蕉，
而對于不透明歸屬，strid的簽名為原版sigexp缤沦。
例子虎韵，
（1）不透明歸屬
signature QUEUE =
sig
type ’a queue
exception Empty
val empty : ’a queue
val insert : ’a * ’a queue -> ’a queue
val remove : ’a queue -> ’a * ’a queue
end
structure Queue :> QUEUE =
struct
type ’a queue = ’a list * ’a list
val empty = (nil, nil)
fun insert (x, (bs, fs)) = (x::bs, fs)
exception Empty
fun remove (nil, nil) = raise Empty
| remove (bs, f::fs) = (f, (bs, fs))
| remove (bs, nil) = remove (nil, rev bs)
end
不透明歸屬Queue :> QUEUE保證了類型'a queue的抽象性，
Queue可以更改具體實現(xiàn)缸废，而不會影響用戶代碼包蓝，
用戶不用關(guān)心'a queue的具體類型。
（2）透明歸屬
透明歸屬簡化了在簽名中顯式指定所有類型的工作企量。
我們總是可以將透明歸屬测萎，替換成不透明歸屬，再手動擴(kuò)充一些類型届巩。
signature ORDERED =
sig
type t
val lt : t * t -> bool
end
structure String : ORDERED =
struct
type t = string
val clt = Char.<
fun lt (s, t) = ... clt ...
end
其中硅瞧，輔助函數(shù)clt對外是不可見的，
雖然ORDERED簽名中沒有指定恕汇，String.t的類型也為string腕唧，
透明歸屬，根據(jù)ORDERED計算出來了一個增強(qiáng)版的簽名瘾英，包含了這個類型定義枣接，
所以，String的真實簽名是缺谴，
ORDERED where type t = string
4. 子結(jié)構(gòu)
一個子結(jié)構(gòu)就是“結(jié)構(gòu)中的結(jié)構(gòu)”但惶，
signature MY_GEN_DICT =
sig
type key
type ’a dict
val empty : ’a dict
val insert : ’a dict * key * ’a -> ’a dict
end
signature MY_STRING_DICT =
MY_GEN_DICT where type key = string
signature MY_INT_DICT =
MY_GEN_DICT where type key = int
其中，MY_GEN_DICT是一個一般化的簽名湿蛔，類型key被抽象出來榆骚。
而在簽名MY_STRING_DICT，MY_INT_DICT中煌集，我們可以指定具體的key妓肢。
除了可以指定簽名中具體的類型，還可以指定簽名中的具體結(jié)構(gòu)苫纤。
signature ORDERED =
sig
type t
val lt : t * t -> bool
val eq : t * t -> bool
end
signature DICT =
sig
structure Key : ORDERED
type ’a dict
val empty : ’a dict
val insert : ’a dict * Key.t * ’a -> ’a dict
val lookup : ’a dict * Key.t -> ’a option
end
signature STRING_DICT =
DICT where type Key.t=string
signature INT_DICT =
DICT where type Key.t=int
以上代碼碉钠，先定義了一個名為ORDERED的簽名纲缓，
然后在簽名DICT中，指定其子結(jié)構(gòu)Key滿足簽名ORDERED喊废。
最后祝高，簽名STRING_DICT和INT_DICT，通過指定子結(jié)構(gòu)Key中類型t的具體值完成實例化污筷。
4. 參數(shù)化
為了復(fù)用工闺，支持定義泛型化或參數(shù)化的模塊十分重要，
模塊的實現(xiàn)中瓣蛀，留下一部分未完全確定（unspeci?ed）的部分陆蟆，然后再用不同的方式實例化（instantiated），
那些共同部分惋增，就只需要實現(xiàn)了一次叠殷，被所有實例所共享了。
在Standard ML中诈皿，這些一般化模塊稱為函子（functor）林束，
函子是一個模塊級別的（module-level）函數(shù)，它接受一個結(jié)構(gòu)（structure）作為參數(shù)稽亏，
然后生成一個結(jié)構(gòu)作為結(jié)果壶冒。
signature ORDERED =
sig
type t
val lt : t * t -> bool
val eq : t * t -> bool
end
signature DICT =
sig
structure Key : ORDERED
type ’a dict
val empty : ’a dict
val insert : ’a dict * Key.t * ’a -> ’a dict
val lookup : ’a dict * Key.t -> ’a option
end
functor DictFun
(structure K : ORDERED) :>
DICT where type Key.t = K.t =
struct
structure Key : ORDERED = K
datatype ’a dict =
Empty |
Node of ’a dict * Key.t * ’a * ’a dict
val empty = Empty
fun insert (None, k, v) =
Node (Empty, k, v, Empty)
fun lookup (Empty, ) = NONE
| lookup (Node (dl, l, v, dr), k) =
if Key.lt(k, l) then
lookup (dl, k)
else if Key.lt (l, k) then
lookup (dr, k)
else
v
end
DictFun是一個函子，它接受一個結(jié)構(gòu)K作為參數(shù)截歉，返回了一個結(jié)構(gòu)依痊。
其中K透明歸屬于ORDERED，DictFun不透明歸屬于DICT怎披。
它保證了'a dict的抽象性（不透明歸屬）胸嘁，而K.t則是具體的（透明歸屬），由函子的參數(shù)決定凉逛。
函子的調(diào)用方式如下性宏，
structure LtIntDict = DictFun (structure K = LessInt)
structure LexStringDict = DictFun (structure K = LexString)
structure DivIntDict = DictFun (structure K = DivInt)
