标准 ML 编程/类型

标准 ML 具有特别强大的静态类型系统。与许多语言不同，它没有子类型（“is-a”关系）或类型之间的隐式转换。

静态类型

在内部，计算机中的所有数据都由位（二进制数字，要么是 0 要么是 1）组成，这些位被分组为字节（最小的可寻址位组 - 在所有现代机器中都是 8 位），通常又进一步分组为字（CPU 可以作为一个单元处理的字节组 - 如今通常是 4 个字节，即 32 位，或 8 个字节，即 64 位）。

然而，程序旨在对位、字节和字本身进行操作的情况相当罕见。通常程序需要对人类可理解的抽象数据类型进行操作：例如整数，或实数，或字符字符串 - 或者所有这些。程序主要通过位和字节进行操作，因为这些是计算机实现或表示这些数据类型的机制。编程语言解决这种差异的方法有很多种

• 一种语言可以不提供任何数据类型抽象，并要求程序员代码显式地处理位和字节。它可以提供旨在用于某些抽象数据类型的操作（例如 32 位整数的加法），但完全由程序代码来确保它只将这些操作用于表示这些类型的字节。这种方法是汇编语言的特征，在一定程度上也是 C 语言的特征。
• 一种语言可以提供只有一种数据类型抽象，供所有程序员代码使用。这种方法是 shell 脚本语言的特征，这些语言通常几乎完全操作字符字符串。
• 一种语言可以为每个数据片段（每个值）分配一个类型，并将该类型分配与值本身一起存储。当尝试对不合适数据类型的值进行操作时，语言要么自动将其转换为合适的类型（例如，将整数值提升为等效的实数类型的值），要么发出错误。这种方法，其中类型信息仅在运行时存在，被称为动态类型，它是 Lisp、Python、Ruby 等语言的特征。
• 一种语言可以为每个代码片段（每个表达式）分配一个类型。如果一段代码对不合适数据类型的表达式应用操作，编译器要么推断出执行类型转换的附加代码，要么发出错误。这种方法，其中类型信息仅在编译时存在，被称为静态类型，它是标准 ML、OCaml、Haskell 等语言的特征。

大多数语言并不严格地遵循上述方法之一，而是使用多种方法的元素。然而，标准 ML 的类型系统几乎完全使用静态类型。这意味着一个类型错误的程序甚至不会编译。（ML 程序员认为这是一件好事，因为它允许在编译时捕获许多编程错误，而动态类型的语言只会在运行时捕获这些错误。）在标准 ML 支持动态类型的程度上，它是在静态类型框架内的。

强类型

术语强类型在很多不同的情况下使用（参见维基百科文章“强类型编程语言”以获得一个相当完整的列表）；尽管如此，可以说标准 ML 类型系统在几乎所有定义下都提供强类型。SML 程序中的每个表达式在编译时都有一个特定类型，并且它在运行时的类型永远不会违反这一点。所有类型转换都是显式的（使用诸如real之类的函数，该函数接受一个整数并返回一个等效的实数），并且采取有意义的转换形式，而不是仅仅重新解释原始位。

基本类型

有许多可以被认为是“内置”的基本类型，首先是因为它们是由标准 ML 基础库预定义的（因此标准 ML 程序不需要定义它们），其次是因为语言为它们提供了文字表示法，例如34（这是一个整数），或"34"（这是一个字符字符串）。一些最常用的类型是

• int（整数），例如3或~12。（注意，波浪号~用于负数。）
• real（浮点数），例如4.2或~6.4。
  • 标准 ML 不会隐式地将整数提升为浮点数；因此，诸如2 + 5.67之类的表达式是无效的。它必须写成2.0 + 5.67，或real(2) + 5.67（使用real函数将2转换为2.0）。
• string（字符字符串），例如"this is a string"或""。（后者是空字符串，它不包含任何字符。）
• char（一个字符），例如#"y"或#"\n"。（后者表示换行符，ASCII 码 10。）
• bool（布尔值），它要么是true要么是false。

以下代码片段声明了两个变量

val n : int = 66
val x : real = ~23.0

在这个代码片段之后，n 的类型为int，值为 66；x 的类型为real，值为 -23。注意，与某些语言不同，这些变量绑定是永久的；这个n将始终具有值 66（虽然程序中其他地方可能存在其他不相关的变量，也具有名称n，这些变量可以具有完全不同的类型和值）。

类型推断

在上面的例子中，我们提供了显式的类型注释来告知编译器变量的类型。但是，这种类型注释是可选的，很少有必要。在大多数情况下，编译器会简单地推断出正确的类型。因此，以下两个代码片段是等效的

val s : string = "example"
val b : bool = true

val s = "example"
val b = true

在下面的例子中，我们偶尔会提供类型注释作为一种文档形式；这有一个很好的属性，即文档的正确性是可以强制执行的，因为编译器会报告任何类型注释不正确的错误。在其他情况下，我们可能会包含普通的注释，形式为(* this is a comment *)；这是一种更灵活的文档形式，因为它可以包含任何类型的文本（而不仅仅是类型信息），但当然它的准确性无法由编译器强制执行。

元组

类型，包括上面的基本类型，可以以多种方式组合。一种方式是使用元组，它是一个有序的值集；例如，表达式(1, 2)的类型为int * int，而("foo", false)的类型为string * bool。还有一个 0 元组()，其类型用unit表示。然而，没有 1 元组；或者更确切地说，（例如）(1)和1之间没有区别，两者都具有类型int。

元组可以嵌套，并且（与某些数学形式主义不同），(1,2,3)与((1,2),3)和(1,(2,3))都不同。第一个的类型为int * int * int；后两个的类型分别为(int * int) * int和int * (int * int)。

表达式	类型	注释
()	unit	0 元组
(3, "yes", "yes")	int * string * string	3 元组（有序三元组）
(3, "yes", true)	int * string * bool	3 元组（有序三元组）
((1, 2), 3)	(int * int) * int	2 元组（有序对），其第一个元素是另一个 2 元组

以下代码片段声明了四个变量。右侧显示了执行后的环境。请注意使用模式匹配将类型和值分配给a和b，以及在分配also_a时使用投影。这使得符号表示非常方便。

val pair = ("a", "b") val (a, b) = pair val also_a = #1 pair

标识符 值 类型 对 ("a", "b") string * string a "a" string b "b" string also_a "a" string

记录

另一种组合值的方式是使用记录。记录很像元组，区别在于记录的组件是命名的，而不是有序的；例如，{ a = 5.0, b = "five" } 的类型是 { a : real, b : string }（与 { b : string, a : real } 类型相同）。

事实上，在 Standard ML 中，元组只是记录的一种特殊情况；例如，int * string * bool 类型与 { 1 : int, 2 : string, 3 : bool } 类型相同。

函数

函数接受一个值，通常会返回一个值。例如，我们在引言中定义的factorial函数

fun factorial n =  if n < 1  then 1  else n * factorial (n - 1)

的类型是 int -> int，意味着它接受一个 int 类型的值，并返回一个 int 类型的值。

即使函数在运行时不返回值——例如，如果它引发异常，或者如果它进入无限循环——它在编译时仍然具有静态返回类型。

与其他类型一样，我们可以提供显式的类型注释

fun factorial (n : int) : int = if n < 1  then 1  else n * factorial (n - 1)

如果需要。

元组作为参数

虽然 Standard ML 函数必须接受恰好一个值（而不是接受参数列表），但元组和前面提到的模式匹配完全没有限制。例如，这段代码

fun sum (a, b) = a + b
fun average pair = sum pair div 2

创建了两个类型为 int * int -> int 的函数。这种方法也可以用来创建中缀运算符。这段代码

infix averaged_with
fun a averaged_with b = average (a, b)
val five = 3 averaged_with 7

将 averaged_with 建立为中缀运算符，然后将其创建为 int * int -> int 类型的函数。

由于元组是一种普通类型，因此函数也可以返回一个元组。在这段代码中

fun pair (n : int) = (n, n)

pair 的类型是 int -> int * int。

多态数据类型

在这段代码中

fun pair x = (x, x)

编译器无法推断出pair的特定类型；它可能是int -> int * int，real -> real * real，甚至(int * real -> string) -> (int * real -> string) * (int * real -> string)。幸运的是，它不需要推断；它可以简单地为其分配多态类型'a -> 'a * 'a，其中'a（读作“alpha”）是一个类型变量，表示任何可能的类型。在上述定义之后，pair 3和pair "x"都是有效的，分别产生(3, 3)和("x", "x")。函数甚至可以依赖多个类型变量；在这个片段中

fun swap (x, y) = (y, x)

swap 的类型是 'a * 'b -> 'b * 'a。所有或部分内容可以显式指示

fun swap (x : 'a, y : 'b) : 'b * 'a = (y, x)

函数作为参数，以及柯里化函数

函数可以接受另一个函数作为参数。例如，考虑这段代码

fun pair_map (f, (x, y)) = (f x, f y)

这将创建一个类型为 ('a -> 'b) * ('a * 'a) -> ('b * 'b) 的函数 pair_map，它将第一个参数（函数）应用于第二个参数（对）的每个元素，并返回结果对。

相反，函数可以返回一个函数。在上面，我们看到了创建二元函数的一种方法：接受一个二元组。另一种方法称为柯里化，就是只接受第一个参数，然后返回一个接受第二个参数的函数

fun sum i j = i + j
val add_three = sum 3
val five = add_three 2
val ten = sum 5 5

这将创建一个类型为 int -> int -> int（意思是 int -> (int -> int)）的函数 sum，一个类型为 int -> int 的函数 add_three，它返回其参数加三，以及整数 five 和 ten。

类型声明

type 关键字可以用来创建现有数据类型的同义词。例如，这段代码

type int_pair = int * int

为数据类型 int * int 创建了同义词 int_pair。在创建该同义词后，像这样的声明

fun swap_int_pair ((i,j) : int_pair) = (j,i)

与像这样的声明完全等效

fun swap_int_pair (i : int, j : int) = (j,i)

正如我们将看到的，这在模块化编程中非常有用，当创建结构以匹配给定的签名时。

数据类型声明

datatype 关键字可以用来声明新的数据类型。例如，这段代码

datatype int_or_string = INT of int | STRING of string | NEITHER

创建一个全新的数据类型 int_or_string，以及新的构造函数（一种特殊的函数或值）INT、STRING 和 NEITHER；该类型中的每个值要么是一个带有整数的 INT，要么是一个带有字符串的 STRING，要么是一个 NEITHER。然后我们可以写

val i = INT 3
val s = STRING "qq"
val n = NEITHER
val INT j = i

其中最后一个声明使用模式匹配功能将j绑定到整数 3。

从概念上讲，这些类型类似于 C++ 等语言的枚举或联合，但它们是完全类型安全的，因为编译器会将 int_or_string 类型与所有其他类型区分开来，并且在运行时，值的构造函数将可用以区分类型的不同变体（不同的分支/分支/备选方案）。

这些数据类型可以是递归的

datatype int_list = EMPTY | INT_LIST of int * int_list

创建一个新的类型 int_list，其中该类型的每个值要么是 EMPTY（空列表），要么是整数与另一个 int_list 的连接。

这些数据类型，像函数一样，可以是多态的

datatype 'a pair = PAIR of 'a * 'a

创建一个新的类型族 'a pair，例如 int pair、string pair 等。

列表

Basis 提供的一种复杂数据类型是 list。这是一种递归的、多态的数据类型，定义等效于

datatype 'a list = nil | :: of 'a * 'a list

其中 :: 是一个中缀运算符。因此，例如，3 :: 4 :: 5 :: nil 是一个包含三个整数的列表。列表是 ML 程序中最常见的数据类型之一，该语言还提供特殊符号 [3, 4, 5] 来生成它们。

Basis 还提供了一些用于处理列表的函数。其中一个是 length，它的类型是 'a list -> int，它计算列表的长度。它可以这样定义

fun length nil = 0
|   length (_::t) = 1 + length t

另一个是 rev，类型为 'a list -> 'a list，它计算列表的反转——例如，它将 [ "a", "b", "c" ] 映射到 [ "c", "b", "a" ]——并且可以这样定义

local
  fun rev_helper (nil, ret) = ret
  |   rev_helper (h::t, ret) = rev_helper (t, h::ret)
in
  fun rev L = rev_helper (L, nil)
end

异常声明

内置类型 exn（异常）类似于使用 datatype 声明创建的类型：它具有变体，每个变体都有自己的构造函数。但是，与这些类型不同的是，可以使用 exception 声明向该类型添加新的变体，以及新的构造函数。这段代码

exception StringException of string
val e = StringException "example"
val StringException s = e

创建一个类型为 string -> exn 的构造函数 StringException，一个类型为 exn 的变量 e，以及一个类型为 string 的变量 s（它的值为 "example"）。

exn 类型在这方面是独一无二的；程序中创建的类型不能以这种方式“添加”。

引用

以上所有内容都描述了不可变的存储形式；例如，一旦创建了一个元组，它就不能更改（变异）。在以下语句之后

val x = (3, 4)

无法将 x 的值更改为，例如，(3, 5)。（确实有可能创建一个全新的 x，它“覆盖”了旧的 x，并且具有完全不同的值——甚至完全不同的类型——但这只是隐藏了旧的 x，并且不会影响任何其他引用它的值。）

初始的基础还提供可变存储，以引用的形式。在某些方面，引用表现得好像它们是像这样定义的

datatype 'a ref = ref of 'a

例如，以下代码片段

val reference : int ref = ref 12
val ref (twelve : int) = reference

将变量reference绑定到包含值 12 的引用，并将变量twelve绑定到值 12。

但是，上面的代码片段只指定了引用的初始内容；内容可以更改。此代码片段

val () = reference := 13
val ref (thirteen : int) = reference

使用内置:=函数修改reference的内容。然后，它将新变量thirteen绑定到新值。

Standard ML 基础库定义了一个便利函数!，它检索引用的内容。它可以这样定义

fun ! (ref x) = x

并像这样使用

val () = reference := 14
val fourteen = ! reference

等式类型

上面讨论了多态类型的概念，我们已经看到了诸如'a * 'b -> 'b * 'a和'a list之类的示例。在这些示例中，类型适用于所有可能的类型'a和'b。还存在一种稍微更严格的多态类型，它仅限于等式类型，表示为''a，''b等。这种类型多态由多态等式运算符=生成，它确定两个值是否相等，并且具有类型''a * ''a -> bool。这意味着它的两个操作数必须是相同类型，并且该类型必须是等式类型^。

在上面讨论的“基本类型”中——int、real、string、char和bool——除了real之外，所有类型都是等式类型。这意味着3 = 3、"3" = "3"、#"3" = #"3"和true = true都是求值为true的有效表达式；3 = 4、"3" = "4"、#"3" = #"4"和true = false都是求值为false的有效表达式；3.0 = 3.0和3.0 = 4.0是编译器将拒绝的无效表达式。造成这种情况的原因是 IEEE 浮点等式违反了 ML 中等式的一些要求。特别是，nan 不等于自身，因此关系不是自反的。

元组类型和记录类型当且仅当每个组件类型都是等式类型时，才是等式类型；例如，int * string、{ b : bool, c : char }和unit是等式类型，而int * real和{ x : real }则不是。

函数类型永远不是等式类型，因为在一般情况下，无法确定两个函数是否等效。

由datatype声明创建的类型是等式类型，如果每个变体要么是空构造函数（没有参数的构造函数），要么是带有等式类型参数的构造函数，并且（在多态类型的情况下）每个类型参数都是等式类型。例如，此代码片段

datatype suit = HEARTS | CLUBS | DIAMONDS | SPADES
datatype int_pair = INT_PAIR of int * int
datatype real_pair = REAL_PAIR of real * real
datatype 'a option = NONE | SOME of 'a

创建了等式类型suit（只有空构造函数）、int_pair（只有一个构造函数，它的参数是等式类型int * int）和int option（一个空构造函数，以及一个带有等式类型参数int的构造函数），更不用说char option和string option等等了。它还创建了非等式类型real_pair（一个带有非等式类型real * real参数的构造函数）、real option、(int -> int) option等等。

如果可能，递归类型是等式类型，否则就不是。例如，考虑上面提到的多态类型'a list

datatype 'a list = nil | :: of 'a * 'a list

当然real list不是等式类型，因为它的类型参数不是等式类型，并且因为real * real list（::参数的类型）不能是等式类型。但是，没有理由int list不能是等式类型，所以它就是一个。请注意，这种等式类型化只在类型内；类似(nil : int list) = (nil : char list)的东西将是无效的，因为这两个表达式是不同类型的，即使它们具有相同的值。但是，nil = nil和(nil : int list) = nil都是有效的（并且都求值为true）。

可变类型'a ref是等式类型，即使它的组件类型不是。这是因为两个引用被认为是相等的，如果它们标识相同的ref cell（即，相同的指针，由对ref构造函数的相同调用生成）。因此，例如，(ref 1) = (ref 1)和(ref 1.0) = (ref 1.0)都是有效的——并且都求值为false，因为即使两个引用碰巧指向相同的值，引用本身是分开的，并且每个引用都可以独立于另一个进行变异。

但是，像这样的代码片段

datatype 'a myref = myref of 'a ref

不生成等式类型real myref，因为它的类型参数不是等式类型——即使它的唯一构造函数接受等式类型参数。如上所述，使用datatype声明创建的多态类型只有在它们的类型参数是等式类型时才是等式类型，虽然内置引用不受此限制，但它们不能用于规避此限制。如果希望myref类型始终是等式类型，则必须使用此方法

datatype ''a myref = myref of ''a ref

这完全禁止real myref（因为等式类型变量''a不能表示非等式类型real）。