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 程序可以劃分為獨(dú)立的單元（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)

參考

Standard ML '97
Programming in Standard ML