Programming Languages Part A Section3 翻译

这里对Section 3进行翻译。

课程主页：

https://www.coursera.org/learn/programming-languages/home

B站搬运：

https://www.bilibili.com/video/BV1dL411j7L7

Coursera编程语言课程 第3节总结

标准说明：本总结涵盖的材料与课堂视频以及随视频发布的材料（幻灯片、代码）大致相同。它有助于以叙述的方式阅读材料，并将整个课程部分的材料放在一份文件中，特别是在以后复习材料时。请在讨论板上报告这些笔记中的错误。

目录

• 介绍和一些术语
• 将函数作为参数
• 以多态类型和函数作为参数
• 匿名函数
• 不必要的函数封装
• Maps和filters
• 返回函数
• 不仅仅适用于数字和列表
• 词法作用域
• 环境和闭包
• （愚蠢的）包括高阶函数的例子
• 为什么要使用词法作用域
• 将闭包传递给迭代器，如filter
• Fold和更多的闭包实例
• 另一个闭包习语：合并函数
• 另一个闭包习语：currying和部分应用
• 值限制
• 通过ML引用进行突变
• 另一个闭包习语：回调
• 可选的：另一个闭合习语：抽象数据类型
• 可选的：其他语言中的闭包
• 可选的：在Java中使用对象和接口的闭包
• 可选的：C语言中使用显式环境的闭包
• 标准库文件

为什么要使用词法作用域

本节重点介绍头等函数和函数闭包。“头等”的意思是，只要其他值可以被计算、传递、存储等，函数就可以被计算、传递、存储等。例如，我们可以将它们传递给函数，从函数返回它们，将它们放入pair，让它们成为数据类型构造函数携带的数据的一部分，等等。“函数闭包”指的是使用在它们之外定义的变量的函数，这使得头等函数更加强大，正如我们从不使用这种能力的更简单的高阶函数开始后所看到的那样。术语高阶函数只是指一个可以接受或返回其他函数的函数。

像头等函数、函数闭包和高阶函数这样的术语经常被相互混淆或被认为是同义词。因为世界上有很多人对这些术语并不小心，所以我们也不会太担心。但头等函数的概念和函数闭包的概念确实是不同的，我们经常一起使用它们来编写优雅的、可重用的代码。出于这个原因，我们将推迟闭包的概念，这样我们就可以把它作为一个单独的概念来介绍。

还有一个更通用的术语，即函数式编程。这个术语也经常被不精确地用来指代几个不同的概念。最重要和最常见的两个是：

• 在大多数或所有情况下不使用可变数据。到目前为止，我们在整个课程中都避免了突变，并且大部分情况下会继续这样做。
• 使用函数作为值，这就是本节的内容。

还有其他一些事情也被认为与函数式编程有关：

• 一种鼓励递归和递归数据结构的编程风格
• 语法或风格更接近于传统数学中的函数表示的编程方式
• 任何不是面向对象的编程（这一点确实不对）
• 使用某些与laziness有关的编程习语，这是一个技术术语，我们将在以后的课程中研究某种编程结构/习语

一个明显的相关问题是：”是什么使一种编程语言成为一种函数式语言？”你的老师已经得出结论，这不是一个有准确答案的问题，作为一个问题几乎没有意义。但可以说，函数式语言是指以函数式风格（如上所述）编写的程序比以其他风格编写的程序更方便、更自然、更常见。至少，你需要对不可变的数据、头等函数和函数闭包有良好的支持。我们越来越多地看到新的语言提供这种支持，同时也为其他风格提供良好的支持，如面向对象编程，我们将在课程结束时研究一些。

以函数为参数

头等函数最常见的用途是把它们作为参数传递给其他函数，所以我们首先鼓励这种用途。

下面是一个函数接受另一个函数的一个例子：

fun n_times (f,n,x) =
    if n=0
    then x
    else f (n_times(f,n-1,x))

我们知道参数f是一个函数，因为最后一行用一个参数来调用f。n_times所做的是计算f(f(...(f(x))))，其中对f的调用次数为n。这是一个真正有用的辅助函数。例如，这里有三个不同的用法：

fun double x = x+x
val x1 = n_times(double,4,7) (* answer: 112 *)

fun increment x = x+1
val x2 = n_times(increment,4,7) (* answer: 11 *)

val x3 = n_times(tl,2,[4,8,12,16]) (* answer: [12,16] *)

像任何辅助函数一样，n_times让我们抽象出多个计算的共同部分，因此我们可以通过传递不同的参数，以不同的方式重用一些代码。主要的创新之处在于使这些参数之一成为一个函数，这是一个强大的、可执行的编程习惯。这也很有意义——我们在这里没有引入任何新的语言结构，只是以你可能没有想到的方式使用我们已经知道的语言结构。

一旦我们知道了这种抽象，我们就可以为它们找到更多的用途。例如，即使我们今天的程序不需要对任何数值进行$n$次翻3倍，也许明天就会了，在这种情况下，我们就可以使用n_times定义triple_n_times：

fun triple x = 3*x

fun triple_n_times (n,x) = n_times(triple,n,x)

多态类型和函数作为参数

现在让我们考虑n_times的类型，即('a -> 'a) * int * 'a -> 'a。首先考虑类型(int -> int) * int * int -> int可能更简单，这就是上面n_times用于x1和x2的方式。它需要3个参数，其中第一个参数本身就是一个函数，需要并返回一个int。同样地，对于x3，我们使用n_times，就好像它的类型是(int list -> int list) * int * int list -> int list。但是为n_times选择这两种类型中的任何一种都会使它变得不那么有用，因为只有我们的例子中的一些使用会进行类型检查。类型('a -> 'a) * int * 'a -> 'a表示第三个参数和结果可以是任何类型，但是必须和第一个参数的输入参数和返回类型一样。当类型可以是任何类型，并且不必与其他类型相同时，我们使用不同的字母（'b、'c等）。

这被称为参数多态性，或者更常见的通用类型。它允许函数接受任何类型的参数。这是一个与头等函数不同的问题。 有一些函数接受函数，但没有多态类型；也有一些具有多态类型的函数不接受函数。

然而，许多带有头等函数的例子都有多态类型。这是一件好事，因为它使我们的代码更容易复用。

如果没有参数化的多态性，我们将不得不为列表中可能有的每一种类型的元素重新设计列表。相反，我们可以有适用于任何类型的list的函数，比如length，它的类型是'a list -> int，尽管它没有使用任何函数参数。相反，这里有一个高阶函数，它不是多态的：它的类型是(int->int) * int -> int（最好是用一个累加器使这个函数尾部递归）:

fun times_until_zero (f,x) =
    if x = 0 then 0 else 1 + times_until_zero(f, f x)

匿名函数

像triple这样被传递给另一个函数（如n_times）的函数，没有理由需要在顶层进行命名。像往常一样，如果这些函数只在本地需要，那么在本地定义这些函数是更好的方式。所以我们可以这样写：

fun triple_n_times (n,x) = 
  let fun triple x = 3*x in n_times(triple,n,x) end

事实上，我们可以给triple函数一个更小的范围：我们只需要它作为n_times的第一个参数，所以我们可以有一个let表达式，对triple函数进行求值：

fun triple_n_times (n,x) = n_times((let fun triple y = 3*y in triple end), n, x)

注意在这个例子中，我们需要let表达式（let-expression）返回”triple“，因为和以往一样，let表达式产生in和end之间表达式的结果。在这种情况下，我们只需在环境中查找triple，结果函数就是我们传递给n_times的第一个参数的值。

ML有一个更简洁的方法，在你使用函数的地方指定它们，就像下面这个最好的版本：

fun triple_n_times (n,x) = n_times((fn y => 3*y), n, x)

这个代码指定了一个匿名函数fn y => 3*y。它是接受参数y并具有主体3*y的函数。fn是一个关键字，=>（不是=）也是语法的一部分。我们从未给这个函数起过名字（它是匿名的，看到了吗？），这很方便，因为我们不需要名字。我们只是想把一个函数传给n_times，在n_times的主体中，这个函数被绑定到f。

使用匿名函数作为其他函数的参数是很常见的。此外，你可以把匿名函数放在任何可以放表达式的地方，它仅仅是一个值，即函数本身。你唯一不能用匿名函数做的事情是递归，正是因为你没有名字可以用于递归调用。在这种情况下，你需要像以前一样使用一个函数绑定，而函数绑定必须是在let-表达式中或者在顶层。

对于非递归函数，你可以使用匿名函数与val绑定，而不是使用fun绑定。例如，这两个绑定是完全一样的：

fun increment x = x + 1
val increment = fn x => x+1 

它们都将increment绑定到一个值上，这个值是一个返回其参数加1的函数。因此，函数绑定几乎是语法糖，但它们支持递归，这一点至关重要。

不必要的函数包装

虽然匿名函数非常方便，但它们常常被毫无理由地使用。考虑：

fun nth_tail_poor (n,x) = n_times((fn y => tl y), n, x)

什么是fn y => tl y？它是一个返回其参数的列表尾数的函数。但是已经有一个与函数绑定的变量做了完全相同的事情：tl! 一般来说，当我们可以直接使用f时，没有理由写fn x => f x。这类似于初学者写if x then true else false而不是x的习惯。对于上述函数，只要这样做就行了：

fun nth_tail (n,x) = n_times(tl, n, x) 

Maps和filters

我们现在考虑一个对列表非常有用的高阶函数：

fun map (f,xs) = 
    case xs of
        [] => []
      | x::xs' => (f x)::(map(f,xs')) 

map函数接收一个列表和函数f，通过对列表中的每个元素应用f来产生一个新的列表。下面是两个使用实例：

val x1 = map (increment, [4,8,12,16]) (* answer: [5,9,13,17] *)
val x2 = map (hd, [[1,2],[3,4],[5,6,7]]) (* answer: [1,3,5] *)

map的类型很有启发性：('a -> 'b) * 'a list -> 'b list。你可以把map传给你想要的任何种类的列表，但是f的参数类型必须是列表的元素类型（它们都是'a）。但是f的返回类型可以是不同类型的'b。结果列表是一个'b列表。对于x1，'a和'b都是用int来实例化的。对于x2，'a是int list，'b是int。

ML标准库提供了一个非常类似的函数List.map，但是它是以curried形式表示的，这个话题我们将在本节后面讨论。

尽管我们的例子很简单，但map的定义和使用是一个非常重要的习语。 我们本来可以很容易地在整数列表上写一个递归函数来增加所有的元素，但我们却把工作分为两部分。map实现者知道如何遍历一个递归数据结构，在这个例子中是一个列表。map客户端知道如何处理这些数据，在这种情况下，每个数字都要递增。你可以想象，这些任务中的任何一项——遍历复杂的数据或为每一个数据做一些计算——都要复杂得多，最好由不同的开发者来完成，而不需要对另一项任务进行假设。这正是把map写成一个辅助函数，并接受一个函数让我们做的。

这里有第二个非常有用的高阶函数，用于列表。它接收一个'a -> bool类型的函数和一个'a list，并返回只包含输入列表中该函数返回true的元素的'a list：

fun filter (f,xs) = 
    case xs of 
        [] => [] 
      | x::xs' => if f x 
                     then x::(filter (f,xs')) 
                     else filter (f,xs') 

下面是一个使用的例子，它假设列表元素是第二部分为int类型的pair；它返回第二部分为偶数的列表元素：

fun get_all_even_snd xs = filter((fn (_,v) => v mod 2 = 0), xs)

（注意我们是如何使用一个模式作为我们匿名函数的参数的。）

返回函数

函数也可以返回函数。下面是一个例子：

fun double_or_triple f = 
    if f 7
    then fn x => 2*x
    else fn x => 3*x 

double_or_triple的类型是(int -> bool) -> (int -> int)。if测试使f的类型变得清晰，而且像往常一样，if的两个分支必须有相同的类型，在这种情况下是int->int。然而，ML会将类型打印为(int -> bool) -> int -> int，这是同样的事情。小括号是不必要的，因为->“向右结合”，即t1->t2->t3->t4是t1->(t2->(t3->t4))。

不仅仅是对数字和列表

因为ML程序倾向于经常使用列表，你可能会忘记高阶函数对列表以外的东西也很有用。我们最初的一些例子只是使用了整数。但是高阶函数对我们自己的数据结构也很有用。这里我们使用is_even函数来查看一个算术表达式中的所有常数是否为偶数。我们可以很容易地将true_of_all_constants用于我们想要检查的任何其他属性：

datatype exp = Constant of int 
	     | Negate of exp 
	     | Add of exp * exp
	     | Multiply of exp * exp

fun is_even v =
    (v mod 2 = 0)

fun true_of_all_constants(f,e) =
    case e of
	Constant i => f i
      | Negate e1 => true_of_all_constants(f,e1)
      | Add(e1,e2) => true_of_all_constants(f,e1)
		      andalso true_of_all_constants(f,e2)
      | Multiply(e1,e2) => true_of_all_constants(f,e1)
			   andalso true_of_all_constants(f,e2)

fun all_even e = true_of_all_constants((fn x => x mod 2 = 0),e)

词汇范围

到目前为止，我们传递给其他函数或从其他函数返回的函数都是封闭的：函数体只使用函数的参数和任何本地指定的变量。但我们知道，函数可以做得更多：它们可以使用范围内的任何绑定。这样做与高阶函数结合起来是非常强大的，所以学习使用这种技术的有效习语是至关重要的。但首先，正确掌握语义是更重要的。这可能是整个课程中最微妙和最重要的概念，所以要慢慢来，仔细阅读。

一个函数的主体是在定义该函数的环境中被评估的，而不是在调用该函数的环境中。下面是一个非常简单的例子来证明这种区别：

val x = 1
fun f y = x + y
val x = 2
val y = 3
val z = f (x+y)

在这个例子中，f被绑定到一个接受参数y的函数上，其主体也在定义f的环境中查找x。因此，这个函数总是增加它的参数，因为命名时的环境将x映射为1。后来我们有一个不同的环境，f映射到这个函数，x映射到2，y映射到3，然后我们调用f x。以下是评估过程：

• 查阅f，得到之前描述的函数。
• 在当前环境中通过查找x和y来评估参数x+y，产生5。
• 用参数5调用该函数，这意味着在 “旧 “环境中评估主体x+y，其中x映射为1，y映射为5。所以结果是6。

注意，参数是在当前环境中被评估的（产生5），但函数体是在“旧”环境中被评估的。我们将在下面讨论为什么这种语义是可取的，但首先我们要更精确地描述这种语义，并通过使用高阶函数的其他愚蠢的例子来理解这种语义。

这种语义被称为词法作用域。另一种较差的语义，即使用当前环境（在上面的例子中会产生7），称为动态作用域。

环境和闭包

我们已经说过，函数是值，但我们并没有精确地说明这个值到底是什么。现在我们解释一下，一个函数值有两部分，函数的代码（显然）和我们创建函数时的环境。这两部分确实形成了一个”对”，但我们把”对”放在引号里，因为它不是一个ML pair，只是有两个部分的东西。你不能单独访问”pair”的各个部分；你能做的就是调用这个函数。这个调用使用了两个部分，因为它使用环境部分评估了代码部分。

这种”对”被称为函数闭包或者闭包。原因是，虽然代码本身可以有自由变量（在代码中没有绑定的变量，所以它们需要被一些外部环境所绑定），但闭包带有一个提供所有这些绑定的环境。因此，闭包总体上是”封闭的”——它拥有给定一个函数参数后产生一个函数结果所需的一切。

在上面的例子中，绑定fun y = x + y将f绑定到一个闭包中。代码部分是函数fn y => x + y，环境部分将x映射为1。因此，对这个闭包的任何调用都将返回y+1。

（愚蠢的）包括高阶函数的例子

当我们有高阶函数时，词法作用域和闭包会变得更加有趣，但已经描述的语义会引导我们找到正确的答案。

例1：

val x = 1
fun f y = 
    let 
        val x = y+1
    in
        fn z => x + y + z
    end
val x = 3
val g = f 4 
val y = 5
val z = g 6

这里，f被绑定到一个环境部分将x映射为1的闭包中。因此，当我们后来评估f 4时，我们评估let val x = y + 1 in fn z => x + y + z end，在一个x映射为1的环境中扩展到y映射为4。但后来由于let绑定，我们对x进行了shadow，因此我们在一个x映射为5，y映射为4的环境中评估fn z => x + y + z。我们如何评估一个像fn z => x + y + z的函数？我们用当前环境创建一个闭包。所以f 4返回一个闭包，当被调用时，无论在任何调用地点的环境是什么，它都会在其参数上加上9。因此，在例子的最后一行，z将被绑定为15。

例2：

fun f g = 
    let 
        val x = 3
    in
        g 2
    end
val x = 4
fun h y = x + y 
val z = f h

在这个例子中，f被绑定到一个闭包上，该闭包接受另一个函数g作为参数，并返回g 2的结果。绑定到h的闭包总是将4加到它的参数上，因为参数是y，函数体是x+y，并且函数是在x映射到4的环境下被表示的。 所以在最后一行，z将被绑定到6。绑定val x = 3是完全不相关的：调用g 2的评估是通过查找g来获得传入的闭包，然后使用该闭包及其环境（其中x映射为4），参数为2。

为什么使用词法作用域

虽然词法作用域和高阶函数需要一些时间来适应，但几十年的经验表明，这种语义是我们所需要的。本节剩下的大部分内容将描述各种广泛存在的依赖于词法作用域的强大习语。

但首先我们也可以通过展示动态作用域（即你只有一个当前环境并使用它来评估函数体）如何导致一些基本问题来给出词法作用域的动机。

首先，假设在上面的例1中，f的主体被改成let val q = y+1 in fn z => q + y + z。在词法作用域下，这是很正常的：我们总是可以改变一个局部变量的名字和它的用途而不影响任何东西。在动态作用域下，现在对g 6的调用将毫无意义：我们将尝试查找q，但在调用地点的环境中没有q。

第二，再考虑一下例1的原始版本，但现在把val x = 3这一行改为val x = "hi"。在词法作用域下，这也是ok的：这个绑定从未被实际使用过。在动态作用域下，对g 6的调用将查找x，得到一个字符串，并试图把它加进去，这在一个有类型检查的程序中不应该发生。

例2也有类似的问题：这个例子中f的主体很糟糕：我们有一个从未使用过的局部绑定。在词法作用域内，我们可以删除它，将主体改为g 2，并且知道这对程序的其他部分没有影响。而在动态作用域下，它就会产生影响。另外，在词法作用域下，我们知道任何使用与h绑定的闭包都会给它的参数增加4，而不管其他像g这样的函数是如何实现的，以及它们使用什么变量名。这是一个关键的关注点分离，只有词法作用域才能提供。

对于程序中的”常规”变量，词法作用域是最合适的方式。对于某些习语来说，动态作用域有一些令人信服的用途，但是很少有语言对这些有特殊的支持（Racket有），而且很少有现代语言将动态作用域作为默认的。但是你已经看到了一个比词法作用域更像动态作用域的特性：异常处理。当一个异常被引发时，评估必须”查找”哪个处理表达式应该被评估。这种”查找”是使用动态调用堆栈完成的，而不考虑程序的词法结构。

将闭包传递给迭代器，如filter

上面的例子很傻，所以我们需要展示依赖词法作用域的有用程序。我们要展示的第一个习语是将函数传递给map和filter等迭代器。我们之前传递的函数没有使用它们的环境（只有它们的参数和可能的局部变量），但是能够传递闭包使得高阶函数的作用更加广泛。考虑：

fun filter (f,xs) =
    case xs of
        [] => []
      | x::xs’ => if f x then x::(filter(f,xs’)) else filter(f,xs’)

fun allGreaterThanSeven xs = filter (fn x => x > 7, xs)

fun allGreaterThan (xs,n) = filter (fn x => x > n, xs)

在这里，allGreaterThanSeven是”旧闻”——我们传入一个函数，从结果中删除列表中任何小于7的数字。但更有可能的是，你想要一个像allGreaterThan这样的函数，它把”阈值”作为一个参数n，并使用函数fn x => x > n。注意这需要一个闭包和词法作用域！当filter的实现调用这个函数时，我们需要在定义了fn x => x > n的环境中查找n。

下面是另外两个例子：

fun allShorterThan1 (xs,s) = filter (fn x => String.size x < String.size s, xs)

fun allShorterThan2 (xs,s) =
    let
        val i = String.size s
    in
        filter(fn x => String.size x < i, xs)
    end

这两个函数都接收一个字符串列表xs和一个字符串s，并返回一个只包含xs中短于s的字符串的列表。它们都使用闭包，在匿名函数被调用时查找s或i。第二种方法更复杂，但效率更高一些。第一种是对xs中的每个元素重新计算String.size s一次（因为filter多次调用它的函数参数，而函数体每次都会评估String.size s）。第二种是”预先计算”String.size s并将其绑定到函数fn x => String.size x < i可用的变量i上。

Fold和更多的闭包例子

除了map和filter，第三个非常有用的高阶函数是fold，它可以有几个稍微不同的定义，也有一些其他的名字，如reduce和inject。下面是一个常见的定义：

fun fold (f,acc,xs) =
  case xs of
    []     => acc
  | x::xs’ => fold (f, f(acc,x), xs’)

fold需要一个”初始答案”acc，并使用f来”组合”acc和列表的第一个元素，将其作为新的”初始答案”来”fold”列表的其他元素。我们可以使用fold来处理列表的迭代，同时提供一些表达如何组合元素的函数。例如，要对一个列表foo中的元素进行求和，我们可以这样做：

fold ((fn (x,y) => x+y), 0, foo)

与map和filter一样，fold的大部分功能来自于客户端传递的闭包，这些闭包可以有”私有字段”（以变量绑定的形式）来保存他们想要查询的数据。这里有两个例子。第一个是计算在某个整数范围内有多少个元素。第二个是检查所有元素是否都是比其他字符串长度短的字符串。

fun numberInRange (xs,lo,hi) =
  fold ((fn (x,y) =>
            x + (if y >= lo andalso y <= hi then 1 else 0)),
         0, xs)
         
fun areAllShorter (xs,s) =
    let
        val i = String.size s
    in
        fold((fn (x,y) => x andalso String.size y < i), true, xs)
    end

这种将递归遍历（fold或map）与元素上的数据处理（传入的闭包）分开的模式是最基本的。在我们的例子中，这两部分都很简单，我们可以用几行简单的文字就把整个事情做完。更普遍的情况是，我们可能有一组非常复杂的数据结构需要遍历，或者我们可能有非常多的数据处理需要做。把这些问题分开是很好的，这样就可以分别解决编程问题了。

另一个闭包习语：组合函数

函数组合

当我们用大量的函数编程时，创建新的函数是很有用的，这些函数只是其他函数的组合。你可能在数学中做过类似的事情，比如你对两个函数进行组合。例如，这里有一个函数，正是做函数组合的。

fun compose (f,g) = fn x => f (g x)

它接收两个函数f和g，并返回一个将其参数应用于g并使之成为f的参数的函数。关键是，代码fn x => f (g x)使用的是定义它的环境中的f和g。注意compose的类型被推断为('a -> 'b) * ('c -> 'a) -> 'c -> ‘b，这等同于你可能写的：('b -> 'c) * ('a -> 'b) -> ('a -> ‘c)，因为这两种类型只是统一使用不同的类型变量名。

作为一个可爱而方便的库函数，ML库将infix运算符o定义为函数组合，就像数学中一样。因此，与其写：

fun sqrt_of_abs i = Math.sqrt(Real.fromInt (abs i))

你可以写：

fun sqrt_of_abs i = (Math.sqrt o Real.fromInt o abs) i

但第二个版本更清楚地表明，我们可以直接使用函数组合来创建一个函数，并将其绑定到一个带有val绑定的变量上，如第三个版本：

val sqrt_of_abs = Math.sqrt o Real.fromInt o abs

虽然这三个版本都相当可读，但第一个版本并没有立即向读者表明sqrt_of_abs只是其他函数的组合。

管道操作符

在函数式编程中，对其他函数进行组合以创建更大的函数是非常常见的，所以为其定义方便的语法是有意义的。虽然上面的第三个版本是简洁的，但它和数学中的函数组合一样，有一个对许多程序员来说很奇怪的特性，即计算是从右到左进行的。”取绝对值，转换为实数，然后计算平方根”可能比”取绝对值转换为实数后的平方根”更容易理解。

我们也可以为从左到右定义方便的语法。让我们首先定义我们自己的infix操作符，让我们把函数放在我们调用它的参数的右边。

infix |> (* tells the parser |> is a function that appears between its two arguments *)
fun x |> f = f x

现在我们可以写：

fun sqrt_of_abs i = i |> abs |> Real.fromInt |> Math.sqrt

这个运算符，通常被称为管道运算符，在F#编程中非常流行。（F#是一种ML的方言，在.Net上运行，与其他.Net语言编写的库互动良好)。正如我们所见，流水线运算符的语义并不复杂。

另一个闭包习语：Currying和部分应用

我们考虑的下一个习语在一般情况下非常方便，在定义和使用map、filter和fold等高阶函数时经常使用。我们已经看到，在ML中，每个函数都只需要一个参数，所以你必须使用一个习语来获得多个参数的效果。我们之前的方法是将一个元组作为一个参数来传递，所以元组的每一部分在概念上都是多个参数中的一个。另一种更巧妙、更方便的方法是让一个函数接受第一个概念性参数，并返回另一个接受第二个概念性参数的函数，以此类推。词汇范围对于这种技术的正常工作至关重要。

这种技术被称为currying，是以一个叫Haskell Curry的逻辑学家的名字命名的，他研究了相关的想法（所以如果你不知道他，那么currying这个词就没有什么意义了）。

定义和使用curried函数

下面是一个使用curry的”三参数”函数的例子：

val sorted3 = fn x => fn y => fn z => z >= y andalso y >= x

如果我们调用sorted3 4，我们将得到一个在其环境中包含x的闭包。如果我们再以5来调用这个闭包，我们将得到一个环境中包含x和y的闭包。如果我们再用6来调用这个闭包，我们将得到真，因为6大于5，5大于4，这就是闭包的工作原理。

所以((sorted3 4) 5) 6的计算结果正是我们想要的，而且感觉非常接近于用3个参数调用sorted3。更好的是，括号是可选的，所以我们可以写出与sorted3 4 5 6完全相同的东西，这实际上比我们以前的元组方法要少一些字符：

fun sorted3_tupled (x,y,z) = z >= y andalso y >= x
val someClient = sorted3_tupled(4,5,6)

一般来说，语法e1 e2 e3 e4是隐含的嵌套函数调用(((e1 e2) e3) e4)，做出这样的选择是因为它使使用curried函数变得如此方便。

部分应用

尽管我们可能期望我们的curried sorted3的大多数客户提供所有的3个概念参数，但他们可能提供较少的参数，并在以后使用产生的闭包。这被称为”部分应用”，因为我们提供的是概念参数的一个子集（更确切地说，是一个前缀）。作为一个愚蠢的例子，sorted3 0 0返回一个函数，如果它的参数是非负的，则返回true。

局部应用和高阶函数

Currying对于创建带有迭代器的类似函数特别方便。例如，这里有一个curried的折叠函数，用于列表：

fun fold f = fn acc => fn xs =>
  case xs of
    []     => acc
  | x::xs’ => fold f (f(acc,x)) xs’

现在我们可以用这个fold按如下方式定义一个对列表元素求和的函数：

fun sum1 xs = fold (fn (x,y) => x+y) 0 xs 

但这比直接使用部分应用要复杂得多：

val sum2 = fold (fn (x,y) => x+y) 0

部分应用的便利性是ML标准库中的许多迭代器使用它们作为第一个参数的函数的原因。例如，所有这些函数的类型都使用currying：

val List.map = fn : ('a -> 'b) -> 'a list -> 'b list 
val List.filter = fn : ('a -> bool) -> 'a list -> 'a list
val List.foldl = fn : ( 'a * 'b -> 'b) -> 'b -> 'a list -> 'b 

作为例子，List.foldl((fn (x,y) => x+y), 0, [3,4,5])没有通过进行类型检查，因为List.foldl期望的是一个'a * 'b -> 'b函数，而不是一个triple。正确的调用是List.foldl (fn (x,y) => x+y) 0 [3,4,5]，它用函数调用List.foldl，后者返回一个闭包，依此类推。

有语法糖来定义curried函数；你可以只用空格来分隔概念参数，而不是使用匿名函数。因此，对于我们的fold函数来说，更好的风格应该是：

fun fold f acc xs =
  case xs of
    []     => acc
  | x::xs’ => fold f (f(acc,x)) xs’

另一个有用的库函数是List.existence，我们在下面的回调例子中使用它。这些库函数很容易自己实现，所以我们应该明白它们并不花哨：

fun exists predicate xs =
    case xs of
      [] => false
    | x::xs’ => predicate x orelse exists predicate xs’

一般的currying

虽然currying和部分应用对高阶函数来说是很好的，但它们在一般情况下也是很好的。它们适用于任意多参数函数，而且部分应用也会有令人惊讶的便利。在这个例子中，zip和range都是用currying定义的，countup部分应用了range。add_numbers函数将列表[v1,v2,...,vn]变成 [(1,v1),(2,v2),...,(n,vn)]。

fun zip xs ys =
    case (xs,ys) of
        ([],[]) => []
      | (x::xs’,y::ys’) => (x,y) :: (zip xs’ ys’)
      | _ => raise Empty
      
fun range i j = if i > j then [] else i :: range (i+1) j

val countup  = range 1

fun add_numbers xs = zip (countup (length xs)) xs

组合函数以curry和uncurry其他函数

有时，函数被curry了，但参数的顺序与你所希望的部分应用不一致。或者有时当你想让一个函数使用元组时，它却被curry了，反之亦然。幸运的是，我们早期的组合函数的习语可以使用一种方法的函数，并产生使用另一种方法的函数：

fun other_curry1 f = fn x => fn y => f y x
fun other_curry2 f x y = f y x
fun curry f x y = f (x,y)
fun uncurry f (x,y) = f x y

看一下这些函数的类型可以帮助你理解它们的作用。顺便说一句，这些类型也很吸引人，因为如果你把->读作”暗示”，把*读作”和”，那么所有这些函数的类型都是逻辑上的同义现象。

效率

最后，你可能会想知道currying和tupling哪个更快。这几乎不重要；它们的工作都与概念参数的数量成正比，而这个数量通常是相当小的。对于你的软件中的性能关键函数，选择更快的方式可能很重要。在我们使用的ML编译器的版本中，tupling刚好更快。在广泛使用的OCaml、Haskell和F#的实现中，curried函数更快，所以它们是这些语言中定义多参数函数的标准方式。

值限制

一旦你学会了currying和部分应用，你可能会尝试用它来创建一个多态的函数。不幸的是，某些用法，比如说如下，在ML中是不起作用的：

val mapSome = List.map SOME (*turn [v1,v2,...,vn] into [SOME v1, SOME v2, ..., SOME vn]*)
val pairIt = List.map (fn x => (x,x)) (*turn [v1,v2,...,vn] into [(v1,v1),(v2,v2),...,(vn,vn)]*)

鉴于我们到目前为止所学到的知识，没有理由如下示例不起作用，尤其是所有这些函数都是有效的：

fun mapSome xs = List.map SOME xs
val mapSome = fn xs => List.map SOME xs
val pairIt : int list -> (int * int) list = List.map (fn x => (x,x))
val incrementIt = List.map (fn x => x+1)

这个原因被称为值限制，它有时是令人讨厌的。它出现在语言中是有原因的：如果没有它，类型检查器可能会允许一些代码破坏类型系统。这只可能发生在使用突变的代码中，而上面的代码不是，但类型检查器并不知道。

最简单的方法是忽略这个问题，直到你得到一个关于值限制的警告/错误。当你这样做的时候，把val-binding转回fun-binding，就像上面的第一个例子中的做法。

当我们在下一节研究类型推理时，我们将更详细地讨论值限制问题。

使用ML引用进行突变

我们现在终于介绍了ML对突变的支持。突变在某些情况下是可以的。函数式编程中的一个关键方法是，只有当”更新某物的状态以便该状态的所有用户都能看到发生了变化”是对计算进行建模的自然方式时，才使用它。此外，我们希望将突变的功能分开，这样我们就能知道什么时候不使用突变了。

在ML中，大多数东西确实不能被突变。相反，你必须创建一个引用，它是一个容器，其内容可以被改变。你用表达式ref e创建一个新的引用（初始内容是对e进行评估的结果）。你用!r得到一个引用的当前内容（不要与Java 或 C 中的否定相混淆），你用r := e改变r的内容。

一个好的方法是把引用看成是一个有一个字段的记录，这个字段可以用:=操作符来更新。

下面是一个简短的例子：

val x = ref 0
val x2 = x (* x and x2 both refer to the same reference *)
val x3 = ref 0
(* val y = x + 1*) (* wrong: x is not an int *)
val y = (!x) + 1 (* y is 1 *)
val _ = x := (!x) + 7 (* the contents of the reference x refers to is now 7 *) valz1=!x (*z1is 7*)
val z2 = !x2 (* z2 is also 7 -- with mutation, aliasing matters*)
val z3 = !x3 (* z3 is 0 *)

另一个闭包习语：回调

我们考虑的下一个常见的习语是实现一个库，当”事件”发生时检测并通知那些先前”注册”了他们并对事件感兴趣的客户。客户端可以通过提供一个”回调”来注册他们的兴趣——当事件发生时被调用的一个函数。你可能需要这种库的事件的例子包括像用户移动鼠标或按下一个键。从网络接口到达的数据是另一个例子。计算机玩家在游戏中”轮到你了”的事件，也是一个例子。

这些库的目的是允许多个客户端注册回调。库的实现者不知道当事件发生时客户端需要计算什么，而且客户端可能需要”额外的数据”来进行计算。所以库的实现者不应该限制每个客户端使用什么”额外数据”。闭包是理想的选择，因为函数的类型t1->t2并没有指定闭包使用的任何其他变量的类型，所以我们可以把”额外数据”放在闭包的环境中。

如果你在Java的Swing库中使用过”事件监听器”，那么你就在面向对象的环境中使用过这个习语。在Java中，你通过定义一个带有额外字段的子类来获得”额外数据”。对于一个简单的监听器来说，这可能需要大量的按键，这也是Java语言增加匿名内类的一个主要原因（在本课程中你不需要知道，但我们将在后面展示一个例子），它更接近闭包的便利性。

在ML中，我们将使用突变来展示回调习语。这是合理的，因为我们确实希望注册一个回调来”改变世界的状态”——当一个事件发生时，现在有更多的回调可以调用了。

我们的例子使用了这样的想法：当键盘上的一个键被按下时，回调应该被调用。我们将向回调传递一个表示哪个键的int。我们的接口只需要一种方法来注册回调。（在一个真正的库中，你可能还需要一个取消注册的方法。)

val onKeyEvent : (int -> unit) -> unit 

客户端将传递一个int -> unit类型的函数，当后来用一个int调用时，将做他们想做的事情。为了实现这个函数，我们只是使用一个持有回调列表的引用。然后，当一个事件实际发生时，我们假设函数onEvent被调用，它调用列表中的每个回调：

val cbs : (int -> unit) list ref = ref []
fun onKeyEvent f = cbs := f::(!cbs) (* The only "public" binding *)
fun onEvent i =
   let fun loop fs =
        case fs of
          [] => ()
        | f::fs’ => (f i; loop fs’)
    in loop (!cbs) end

最重要的是，onKeyEvent的类型对一个回调在被调用时可以访问哪些额外的数据没有限制。这里有不同的客户端（对onKeyEvent的调用），在他们的环境中使用不同类型的绑定。(val _ = e这个习语在执行表达式时很常见，只是为了它的副作用，在这种情况下注册一个回调。)

val timesPressed = ref 0
val _ = onKeyEvent (fn _ => timesPressed := (!timesPressed) + 1)

fun printIfPressed i =
    onKeyEvent (fn j => if i=j
                        then print ("you pressed " ^ Int.toString i ^ "\n")
                        else ())
                        
val _ = printIfPressed 4
val _ = printIfPressed 11
val _ = printIfPressed 23

可选：另一个闭包习语：抽象数据类型

我们要考虑的最后一个闭包习语是最夸张和最微妙的。它不是程序员通常会做的事情——在现代编程语言中通常有更简单的方法来做。它作为一个高级例子被包括进来，以证明具有相同环境的闭包记录很像面向对象编程中的对象：函数是方法，环境中的绑定是私有字段和方法。这里没有新的语言特征，只是词法作用域。它（正确地）表明，函数式编程和面向对象编程比它们最初看起来更相似（这个话题我们将在本课程后面重新讨论；也有重要的区别）。

抽象数据类型（ADT）的关键是要求客户通过一个函数集合来使用它，而不是直接访问其私有实现。由于这种抽象性，我们以后可以改变数据类型的实现方式而不改变它对客户的行为方式。在面向对象的语言中，你可以通过定义一个具有所有私有字段（客户无法访问）和一些公共方法（与客户的接口）的类来实现一个ADT。我们可以在ML中用闭包记录做同样的事情；闭包使用的环境变量与私有字段对应。

作为一个例子，考虑一个整数集合的实现，它支持创建一个新的更大的集合，并查看一个整数是否在一个集合中。我们的集合是无突变的，即在一个集合中添加一个整数会产生一个新的、不同的集合。（我们可以很容易地使用ML的引用来定义一个可变的版本。）在ML中，我们可以定义一个类型来描述我们的接口:

datatype set = S of { insert : int -> set, member : int -> bool, size : unit -> int }

粗略地说，一个集合是一个有三个字段的记录，每个字段都持有一个函数。用如下方式描述会更简单：

type set = { insert : int -> set, member : int -> bool, size : unit -> int }

但这在ML中是行不通的，因为类型绑定不能是递归的。所以我们必须处理轻微的不便，即在我们定义集合的函数记录周围有一个构造函数S，尽管集合是each-of类型的，而不是one-of类型的。注意，我们没有使用任何新的类型或特征；我们只是有一个描述记录的类型，其字段名为insert、member和size，每个字段都持有一个函数。

一旦我们有了一个空集合，我们就可以使用它的insert字段来创建一个单元素集合，然后再使用这个集合的insert字段来创建一个双元素集合，以此类推。所以我们的接口唯一需要的就是这样的一个绑定：

val empty_set = ... : set

在实现这个接口之前，让我们看看客户端如何使用它（许多括号是可选的，但可能有助于理解代码）：

fun use_sets () =
    let val S s1 = empty_set
        val S s2 = (#insert s1) 34
        val S s3 = (#insert s2) 34
        val S s4 = #insert s3 19
    in
        if (#member s4) 42
        then 99
        else if (#member s4) 19
        then 17 + (#size s3) ()
        else 0
end

我们没有使用新的功能。#insert s1正在读取一个记录字段，在这种情况下，它产生一个函数，然后我们可以用34来调用。如果我们是在Java中，我们可以写s1.insert(34)来做类似的事情。val绑定使用模式匹配来”剥离”set类型的值上的S构造函数。

我们有很多方法可以定义empty_set；它们都使用了使用闭包来”记住”一个集合有哪些元素的技术。下面是一种方法：

val empty_set =
    let
        fun make_set xs = (* xs is a "private field" in result *)
            let (* contains a "private method" in result *)
                fun contains i = List.exists (fn j => i=j) xs
            in
                S { insert = fn i => if contains i
                                     then make_set xs
                                     else make_set (i::xs),
                    member = contains,
                    size   = fn () => length xs
                  }
             end
    in
          make_set []
    end

所有有趣的东西都在make_set中，而empty_set只是make_set []返回的记录。make_set返回的是一个类型为set的值。它本质上是一个带有三个闭包的记录。这些闭包可以使用xs、辅助函数contains和make_set。像所有的函数体一样，它们在被调用之前不会被执行。

可选的：其他语言中的闭包

为了结束我们对函数闭包的研究，我们从ML中抽离出来，展示Java（使用泛型和接口）和C（使用带有明确环境参数的函数指针）中的类似编程模式。我们不会在这个材料上测试你，欢迎你跳过它。然而，通过在其他环境中看到类似的想法，它可能会帮助你理解闭包，而且它应该帮助你看到一种语言中的中心思想如何影响你如何处理其他语言中的问题。也就是说，它可以使你成为一个更好的Java或C语言的程序员。

对于Java和C语言，我们将”移植”这段ML代码，它定义了我们自己的多态链列类型构造器和该类型的三个多态函数（两个高阶）。我们将研究在Java或C中编写类似代码的几种方法，这将有助于我们更好地理解闭包和对象之间的相似性（对于Java）以及如何使环境显性化（对于C）。在ML中，没有理由定义我们自己的类型构造器，因为’a list已经写好了，但这样做将有助于我们与Java和C的版本进行比较：

datatype ’a mylist = Cons of ’a * (’a mylist) | Empty

fun map f xs =
    case xs of
        Empty => Empty
      | Cons(x,xs) => Cons(f x, map f xs)
      
fun filter f xs =
    case xs of
        Empty => Empty
      | Cons(x,xs) => if f x then Cons(x,filter f xs) else filter f xs
      
fun length xs =
    case xs of
        Empty => 0
      | Cons(_,xs) => 1 + length xs

使用这个库，这里有两个客户端函数。（后者不是特别有效，但显示了对length和filter的简单使用）：

val doubleAll = map (fn x => x * 2)
fun countNs (xs, n : int) = length (filter (fn x => x=n) xs)

可选的：Java中使用对象和接口的闭包

Java 8包括对闭包的支持，就像现在大多数其他主流的面向对象语言一样（C#、Scala、Ruby……），但值得考虑的是，如果没有这种支持，我们如何在Java中编写类似的代码，因为近二十年来一直需要这样做。虽然我们没有头等的函数、currying或类型推理，但我们有泛型（Java过去没有），我们可以用一个方法定义接口，我们可以像函数类型一样使用这些接口。闲话少说，下面是这段代码的Java类似物，接下来是对你可能没有见过的功能和我们可以用其他方式编写代码的简要讨论：

interface Func<B,A> {
    B m(A x);
}
interface Pred<A> {
    boolean m(A x);
}
class List<T> {
    T       head;
    List<T> tail;
    List(T x, List<T> xs) {
        head = x;
        tail = xs; 
    }
    static <A,B> List<B> map(Func<B,A> f, List<A> xs) {
        if(xs==null)
            return null;
        return new List<B>(f.m(xs.head), map(f,xs.tail));
    }
    static <A> List<A> filter(Pred<A> f, List<A> xs) {
        if(xs==null)
            return null;
        if(f.m(xs.head))
            return new List<A>(xs.head, filter(f,xs.tail));
        return filter(f,xs.tail);
    }
    static <A> int length(List<A> xs) {
        int ans = 0;
        while(xs != null) {
            ++ans;
            xs = xs.tail;
        }
        return ans;
    }
}

class ExampleClients {
    static List<Integer> doubleAll(List<Integer> xs) {
        return List.map((new Func<Integer,Integer>() {
                             public Integer m(Integer x) { return x * 2; }
                         }), 
                         xs);
    }
    static int countNs(List<Integer> xs, final int n) {
        return List.length(List.filter((new Pred<Integer>() {
                                           public boolean m(Integer x) { return x==n; }
                                      }), 
                                      xs));
    }
}

这段代码使用了几个有趣的技术和特征：

• 为了取代map的'a -> ‘b和filter的'a -> bool的（filter）函数类型，我们有一个方法的通用接口。实现这些接口之一的类可以拥有它所需要的任何类型的字段，这将起到闭包环境的作用。
• 通用类List起到了数据类型绑定的作用。构造函数按照预期初始化了head和tail的字段，使用标准的Java惯例null表示空的列表。
• Java中的静态方法可以是泛型的，只要在返回类型的左边明确提到类型变量。除了这一点和语法，map和filter的实现与它们的ML对应物类似，使用Func或Pred接口中的一个方法作为参数传递的函数。对于长度，我们可以使用递归，但选择遵循Java对循环的偏爱。
• 如果你从未见过匿名内部类，那么doubleAll和countNs这两个方法看起来会很奇怪。有点像匿名函数，这个语言特性让我们创建一个实现了一个接口的对象，而不用给这个对象的类命名。相反，我们使用new来实现接口（适当地实例化类型变量），然后为方法提供定义。作为一个内部类，这个定义可以使用包围对象的字段或最终的局部变量和包围方法的参数，以更繁琐的语法获得封闭环境的大部分便利。(匿名内部类被添加到Java中，以支持回调和类似的习语）。

我们可以用很多不同的方法来编写Java代码。特别值得注意的是：

• 在Java的实现中，尾递归的效率不如循环高，所以更倾向于基于循环的map和filter的实现是合理的。在不反转中间列表的情况下做到这一点比你想象的要复杂（你需要保留一个指向前一个元素的指针，并为第一个元素编写特殊的代码），这就是为什么这种程序在编程面试时经常被问到。递归版本很容易理解，但对于很长的列表来说是不明智的。

• 一个更加面向对象的方法是使map、filter和length成为实例方法而不是静态方法。方法的签名将改变为：

  <B> List<B> map(Func<B,T> f) {...}
  List<T> filter(Pred<T> f) {...}
  int length() {...}

  这种方法的缺点是，如果客户端可能有一个空的列表，我们必须在这些方法的任何使用中添加特殊情况。原因是空列表被表示为null，使用null作为调用的接收方会引发NullPointerException。所以方法doubleAll和countNs必须检查它们的参数是否为空，以避免这种异常。

• 另一种更加面向对象的方法是不对空列表使用null。相反，我们会有一个抽象的list类，其中有两个子类，一个用于空列表，一个用于非空列表。这种方法对具有多个构造函数的数据类型来说是一种更忠实的面向对象的方法，使用它可以使前面的实例方法建议在没有特殊情况下得以实现。对于习惯于使用null的程序员来说，这种方法确实更复杂、更长。

• 匿名内类只是一种方便。我们可以定义一些”正常”的类来实现Func<Integer,Integer>和Pred<Integer>，并创建实例来传递给map和filter。对于countNs的例子，我们的类将有一个int字段用于保存$n$，我们将把这个字段的值传递给类的构造函数，后者将初始化这个字段。

可选的：C语言中使用显式环境的闭包

C语言确实有函数，但它们不是闭包。如果你向一个函数传递一个指针，它只是一个代码指针。正如我们所研究的，如果一个函数参数只能使用它的参数，那么高阶函数的作用就大打折扣。那么，在C语言中，我们能做什么呢？我们可以对高阶函数做如下的改变：

• 明确地把环境作为另一个参数。
• 让函数的参数也取一个环境。
• 当调用函数参数时，把环境传给它。

因此，高阶函数不再是这样的了：

int f(int (*g)(int), list_t xs) { ... g(xs->head) ... }

我们会让它看起来像这样：

int f(int (*g)(void*,int), void* env, list_t xs) { ... g(env,xs->head) ... }

我们使用void*是因为我们希望f能与使用不同类型环境的函数一起工作，所以没有好的选择。客户端将不得不从其他兼容的类型中转换到void*。我们在此不讨论这些细节。

虽然C语言的代码有很多其他的细节，但在map和filter的定义和使用中使用明确的环境是与其他语言的版本的关键区别：

#include <stdlib.h>
#include <stdint.h>
#include <stdbool.h>

typedef struct List list_t;
struct List {
void * head;
  list_t * tail;
};
list_t * makelist (void * x, list_t * xs) {
  list_t * ans = (list_t *)malloc(sizeof(list_t));
  ans->head = x;
  ans->tail = xs;
  return ans;
}
list_t * map(void* (*f)(void*,void*), void* env, list_t * xs) {
  if(xs==NULL)
    return NULL;
  return makelist(f(env,xs->head), map(f,env,xs->tail));
}
list_t * filter(bool (*f)(void*,void*), void* env, list_t * xs) {
  if(xs==NULL)
    return NULL;
  if(f(env,xs->head))
    return makelist(xs->head, filter(f,env,xs->tail));
  return filter(f,env,xs->tail);
}
int length(list_t* xs) {
  int ans = 0;
  while(xs != NULL) {
    ++ans;
    xs = xs->tail;
  }
return ans; }
void* doubleInt(void* ignore, void* i) { // type casts to match what map expects
  return (void*)(((intptr_t)i)*2);
}
list_t * doubleAll(list_t * xs) { // assumes list holds intptr_t fields
  return map(doubleInt, NULL, xs);
}
bool isN(void* n, void* i) { // type casts to match what filter expects
  return ((intptr_t)n)==((intptr_t)i);
}
int countNs(list_t * xs, intptr_t n) { // assumes list hold intptr_t fields
  return length(filter(isN, (void*)n, xs));
}

就像在Java中一样，使用递归而不是循环要简单得多，但效率可能较低。另一个选择是定义结构，将代码和环境放在一个值中，但我们的方法是对每个高阶函数使用是一个额外的void*参数，这在C代码中更常见。

对于那些对C规范的细节感兴趣的人来说。还要注意上面的客户端代码，特别是函数doubleInt、isN和countNs中的代码，是不可移植的，因为假设一个intptr_t可以被转换到void *，然后转换回来在技术上是不合法的，除非这个值是以一个指针（而不是一个适合intptr_t的数字）开始。虽然上面写的代码是一个相当常见的方法，但可移植的版本需要使用一个数字的指针，或者用intptr_t替换库中void*的使用。后一种方法仍然是一个可重用的库，因为任何指针都可以转换为intptr_t并返回。

标准库文档

这个话题与本节的其他部分没有密切关系，但我们在作业3中有点需要它，它对任何编程语言都是有用的，而且它显示了ML中预定义的一些有用的函数（高阶或非高阶）。

ML，像许多语言一样，有一个标准库。这是语言中的程序可以假设总是可用的代码。在标准库中的代码有两个常见而不同的原因：

• 我们需要一个标准库来与”外部世界”对接，以提供否则不可能实现的功能。例如，打开一个文件或设置一个定时器。
• 标准库可以提供一些常用的、有用的功能，以至于只需要定义一次就可以了，这样所有的程序都可以使用相同的函数名称、参数顺序等。例如，拼接两个字符串的函数、映射一个列表的函数等等。

标准库通常是如此之大，以至于期望教它们是没有意义的。你需要自己地寻找文档，并对”可能提供的东西”和”可能存在的地方”形成一个粗略的直觉。因此，在作业3中，我们让你去寻找更多关于ML的标准库中的几个简单函数。

与大多数现代语言相比，在线文档是非常原始的，但它完全可以满足我们的需要。只要去：

http://www.standardml.org/Basis/manpages.html

这些函数是用ML的模块系统组织起来的，我们将在下一节研究它的基本原理。例如，对字符有用的函数在结构Char中。要使用Bar结构中的函数foo，你就写Bar.foo，这正是我们使用List.map等函数的方法。有一个问题是，字符串结构的函数是在签名STRING下记录的。签名基本上是结构的类型，我们将在后面研究。某些库函数被认为是非常有用的，它们不在一个结构中，比如hd。这些绑定的描述在http://www.standardml.org/Basis/top-level-chapter.html。

没有什么可以替代精确和完整的代码库文档，但有时当你在编程过程中只需要快速提醒时，查找完整的文档会很不方便。例如，很容易忘记参数的顺序，或者一个函数是Curried还是Tupled。通常情况下，你可以使用REPL来快速获得你需要的信息。毕竟，如果你输入一个像List.map这样的函数，它会评估这个表达式并返回其类型。如果你不记得一个函数叫什么，你甚至可以猜测它的名字。如果你错了，你只会得到一个未定义变量的信息。最后，利用我们将要学习的功能，你可以让REPL打印出一个结构所提供的所有绑定关系。举例来说，只需这样做：

structure X = List; (* List is the structure we want to know about *)
structure X : LIST  (* This is what the REPL gives back *)
signature X = LIST; (* Write LIST because that is what follows the : on the previous line *)

由于在REPL中查找东西非常方便，其他语言的一些REPL更进一步，提供了打印与函数或库相关的文档的特殊命令。